`IODeferred`'s `CallbackStack` becomes unboundedly large about cats-effect HOT 11 CLOSED

We should expect require(clearCounter.addAndGet(-callbacks.pack(clearCount)) >= 0), right? That bombs for me (with and without this PR).

from cats-effect.

So are we sure this is growing unboundedly? The printlns don't really show that. If you squint, it does kinda look like half-ish is being cleared each time.

from cats-effect.

Yes, half-ish of the total is being cleared each time, but each time the total has doubled in size. You can run my reproducer with a larger replicateA_ value and see.

from cats-effect.

Not each time though. We repeat clearance points several times.

• 1
• 2
• 3
• 3
• 4
• 5
• 6
• 7
• 5
• 6
• 7
• 6
• 7
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 10
• 11
• 12
• 13
• 14
• 15
• 11
• 12
• 13
• 14
• 15
• 12
• 13
• 14
• 15
• 13
• 14
• 15
• 14
• 15
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 19
• 20
• 21
• 22
• 23

It certainly feels like something here is wrong, but I'm not sure if it's a conventional example of unbounded growth.

from cats-effect.

You're right, it's not each time, sorry. Every time we pack() we "lose" 1. So to move up to the next power of 2, first we have to "lose" that many.

from cats-effect.

Ah I see what you're pointing out. Okay gotcha. I'm surprised the off by one fix doesn't correct it then…

from cats-effect.

@mernst-github would you be able to post a self-contained reproducer somewhere? Thanks!

from cats-effect.

• same repro as in #3359
• your fix
• printing the result of clearCounter.addAndGet if != 0

I can see the printed values gradually plunge into negative territory.
JDK 17.0.9 and 21.0.1, macOS / AArch64 and Linux / x64.

from cats-effect.

@mernst-github thanks, I tried that before, but I was unable to replicate your result, I probably did something wrong/different. A self-contained reproducer would help a lot :) e.g. a branch of CE with your reproducer in the example project, with the println added.

from cats-effect.

If I'm not mistaken the 'pack' logic can overcount when called concurrently, since it may clear the same cell twice, for example like so:

 CBS: root -> c1(SET) -> c2(CLEARED) -> null
 T1:  c1.packInternal(bound, 0, root)
 T1:  c1 not cleared, call c2.packInternal(bound-1, 0, c1)
    ~~~context switch~~~~~
 <now c1 gets cleared>
 T2:  c1.packInternal(bound, 0, root)
 T2:  c1 cleared => root.CAS(c1, c2), call c2.packInternal(bound, 1, root)
 CBS:       root     ---->      c2(CLEARED) -> null
                 c1  (CLEARED) /
    ~~~context switch~~~~~
 T1 resumes @ c2.packInternal(bound-1, 0, c1)
 T1:  c2 cleared => c1.CAS(c2, null)
 CBS:       root  -> c2(CLEARED) -> null
                 c1 (CLEARED) -> null
 T1:  return 1
    ~~~context switch~~~~~
 T2 resumes @ c2.packInternal(bound, 1, root)
 T2:  c2 cleared => root.CAS(c2, null)
 CBS:       root  -> null
 T2:  return 2

=> 2 cells cleared, but c2 got double-counted => clearCounter decremented by 3

from cats-effect.

Thanks, you're right! I was able to capture it in a test in 6e2e87d, tracking in #3940.

from cats-effect.