[EdSchouten]

Exactly! At the same time you also don't want to call into the kernel's internal malloc() whenever a thread ends up blocking on a lock to allocate the data structures that are needed to keep track of queues of blocked threads for a given lock.

To prevent that, many operating systems allocate these 'queue objects' whenever threads are created and will attach a pointer to it from the thread object. Whenever a thread then stumbles upon a contended lock, it will effectively 'donate' this queue object to that lock, meaning that every lock having one or more waiters will have a linked list of 'queue objects' attached to it. When threads are woken up, they will each take one of those objects with them on the way out. But there's no guarantee that they will get their own queue object back; they may get shuffled! So by the time a thread terminates, it will free one of those objects, but that may not necessarily be the one it created.

I think the first operating system to use this method was Solaris. There they called these 'queue objects' turnstiles. The BSDs adopted the same approach, and kept the same name.

https://www.oreilly.com/library/view/solaristm-internals-cor...

https://www.bsdcan.org/2012/schedule/attachments/195_locking...

[senderista]

This is a really dumb question from someone unfamiliar with the kernel's futex implementation, so bear with me. In userspace locks (e.g. in parking_lot), wait queues can be threaded through nodes allocated on the stack of each waiting thread, so no static or dynamic allocation of wait queue nodes is necessary. Is it possible to allocate wait queue nodes on the kernel stacks of waiting threads as well?

[jlokier]

> Is it possible to allocate wait queue nodes on the kernel stacks of waiting threads as well?

Yes, this is exactly what's done. The queue node is an declared as a local variable in kernel code, i.e. on the kernel stack, and its address is passed to the wait function which links it into the waitqueue and then blocks in the scheduler.