GeezerVison

If the compare/exchange fails is it worth returning the greater of rd_seq and min_seq?

It doesn't matter for correctness and I'm not sure it's worth any extra complexity for performance.

Can we document why the shared write sequence is always odd? I'm assuming that's just to avoid issues with it wrapping around and colliding with QSBR_OFFLINE?

Yeah, that was the original motivation, but as I wrote in another comment, with 64-bit counters we don't really have to worry about wrap around.

I'm still tempted to keep this numbering scheme and the QBSR_LT wrap-around safe comparisons, but let me know what you think.

I think it's fine to keep it this way, it's just worth a comment on why it's that way :)

Can these be inited to QSBR_INITIAL (it seems like including pycore_qsbr.h shouldn't be an issue?)

It seems like this isn't safe to do with the mutex locked and not-detached? If another thread is trying to reserve at the same time it won't be detached, but it also won't be responding to the request for the eval breaker.

You are right -- I mixed up the locking discipline. The outer lock should not use _Py_LOCK_DONT_DETACH. I think the locking discipline with stop-the-world should be:

1. A lock can be acquired before starting a stop-the-world pause or after starting it, but not both (consistent lock ordering)
2. If acquired before the stop-the-world, the acquisition should use _Py_LOCK_DETACH (the default)
3. If acquired within the stop-the-world, the acquisition should use _Py_LOCK_DONT_DETACH

HEAD_LOCK(runtime) is an example of case 3. This is case 2.

The reasoning for case (3) is a bit subtle: locks can be directly handed off to a detached thread, so with a normal PyMutex_Lock(&m) a thread can both hold the mutex m and have paused for another thread's stop-the-world.

Maybe initialize_new_array or something like that? It's just that it's not only initing the free lists, it's also initializing all of the thread state pointers into the array (and the new part covers the re-initialization)

The FreeBSD version has logic to avoid making sure that wr_seq doesn't get too far ahead from rd_seq and if so blocks until it catches up to avoid extreme wrap around issues... Is there a reason we don't need that? :). Or should we at least add a TODO and/or an assertion?

We are using 64-bit sequence counters to avoid worrying about wrap around. FreeBSD uses 32-bit counters. (2^62 ns = ~146 years; 2^30 ns = ~1 sec)

We could consider using 32-bit counters and handling wrap around in the future. It wouldn't matter much for x86-64 and aarch64, but would probably be more efficient on some other platforms.

Okay, that makes sense, FreeBSD's is buried in a typedef so I hadn't noticed it was 32-bit.

This is probably just related to future scaling, but I wonder if we could pass in the goal and bail on the full-scan if any thread hasn't reached it yet. It might prevent us from updating the shared for someone else who would benefit from it though...

It's not clear to me if that case will happen often enough to be worth handling. Unfortunately, we can't really measure or test for that until we disable the GIL. With the GIL, only one thread is ever attached and active.