On Thu Aug 24 17:35:33 2023 +0000, Zebediah Figura wrote:
Currently there is a gap between reading the head, and pushing our node to the list at all. If a wake happens during that gap, there is no way for it to know that the new waiter needs its head updated. I.e. we have this race:
thread Q thread S ------------------------------ read head go through list, change head wake cmpxchg next cmpxchg tailI think you're onto a solution, although I'm not quite sure I correctly understand what you're saying, but in order for it to work, we *also* need to change the order of queueing:
- cmpxchg the "prev->next" pointer (compare to NULL), retry if failure
- read prev->head
- cmpxchg the "waiter.head" pointer (compare to NULL), ignore if failure
- cmpxchg the lock tail pointer; failure should be impossible if there
was a prev Then, when waking, we have to, as you say, not trust the tail to be the actual tail.
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.