On Thu Aug 24 17:41:53 2023 +0000, Zebediah Figura wrote:
Ugh, no. *Now* I remember the unfixable race that I was seeing when I was trying to do this sort of thing with critical sections. I knew there was one, it was nagging at the back of my mind the entire time I was reviewing this series, but I couldn't remember what it was. The race is very simple, and very fundamental. The problem is that in order to queue, you have to do *something* to the previous tail, whether that's a read or write. In this case it's both—you need to read the previous head from the tail, and write the "next" pointer to it. The problem with this is that the tail can be woken, and removed from the list, at any time. As soon as you grab the address of the tail from the srwlock pointer, that memory can become invalid. At an unlikely extreme, the memory on that stack can simply be freed. At a more likely extreme, cmpxchg'ing the next pointer can scribble over a stack local in a different function.
hmm, you are entirely right. now i wonder how microsoft does it.
maybe the multiple owners bit is meaningful in some way.
below is just **me thinking out loud:**
so it seems to me the `transfer_ownership` process (let's call this the TO thread for brevity) have to be done in two steps, first it scans the list, find out who needs to be woken up, without actually waking them up. then it needs to detect if some thread has started acquiring the lock, in which case it should bail; if not, it updates the lock pointer to reflect the new tail, then wakes up the waiters and thus free the nodes.
this means the waiter side needs to coordinate to let the TO thread know its intention to append to the list. and because of the problem you pointed out, this coordination has to be done through the lock ptr itself, because list node could be freed before we write into them.
the easiest way is using the list_locked bit as a spin lock, which i did consider, but thought the potential of making releasing side block is bad. at least this would work as a last resort.