Local Bags?

[schets]

I was thinking about the reason why using the local bags can cause segfaults - In short, a thread can move two epochs ahead of one with a stale epoch counter if the timing is right - since global garbage two epochs old is collected, this leads to premature freeing of data (local garbage two visible epoch advancements old is collected, not just two epochs so I don't think the local collection itself is vulnerable to the issue you described).

This suggestion may seem a bit silly, but would using an epoch delay of 3 instead of two (4 different bags) solve this with local bags? I don't see a way that a leading thread can move more than two epochs ahead of recently generated garbage, meaning a delay of 3 avoids this issue.

Something else that may work is to have global GC rotate bags on visible epoch advancements as well and not on epoch advancement count. That seems trickier though, maybe not possible in a lock free setting.

I think trying to get local bags to work since using only the global GC in it's current (and in my opinion, any) incarnation seems pretty bad for performance -

• CAS contention when inserting into the global bag. Pushing into the global garbage stack is going to be a really, really big source of contention.
• Giant garbage bags - concentrating the garbage into one bag will result in really big GC runs. May not show up in a throughput measurement, but would easily in a latency one.

If you can send me the test code you used to reproduce this, I'll give this a go - it seems theoretically sound, and tests will tell even more.

[aturon]

I think trying to get local bags to work since using only the global GC in it's current (and in my opinion, any) incarnation seems pretty bad for performance

I agree with this, for exactly the reasons you mention -- it's why I added local bags originally.

My decision to revert to global bags was to try to get back to a conservative, known-good state for the library as quickly as possible. That, and the fact that the local bag code was a little smelly any, so I'd rather re-add a fresh version.

re: having four epochs, I agree that this seems the simplest approach to recovering local bags, and should address the bug I'm worried about.

I'll tidy up my test code and add it to the repo ASAP. Thanks!

[schets]

I think trying to get local bags to work since using only the global GC in it's current (and in my opinion, any) incarnation seems pretty bad for performance

I definitely wrote that sentence too late at night!

My decision to revert to global bags was to try to get back to a conservative, known-good state for the library as quickly as possible. That, and the fact that the local bag code was a little smelly any, so I'd rather re-add a fresh version.

I totally agree, especially at this stage of the project. Tonight I'll test out the 4-bag version and see how it goes. I'll add any interesting test cases I find as well.

[schets]

FWIW, the average push/pop time for MsQueue on my machine is ~120ns with local bags and ~160ns with only global bags.

[aturon]

Now that @msullivan's fix has landed, we should work on reincorporating local bags. As I said previously, the local bag code was due for a refactor anyway, so I'd be happy to start fresh. And I do think we can get away with the 3 epoch version, based on what you and @msullivan argued.

[schets]

Thanks @msullivan for #51!!