Hash tables are popular data structures that efficiently handle dictionary operations (search and insert/delete). The Linux kernel relies on them for a number of subsystems, including major core kernel areas, such as dcache/inode lookups, workqueues, timers, the PID table, TCP/UDP and futexes. This last being used as common building blocks for implementing userspace locking primitives, pthreads being, perhaps, the most popular user.
Futexes make use of single, chained, hash table. The user space address (uaddr) is used by the kernel to generate a unique futex_key to reference the futex. Each key is hashed to a bucket (hb), which contains a single priority based linked list -- real-time tasks are queued in front of regular tasks, otherwise ordered as FIFO. To synchronize updates to the list, a hb->lock spinlock is used. Note that collisions can occur where similar user addresses can hash to the same futex key, so
a single list can contain tasks blocked on different futexes. There are a total of 256 hash buckets in the entire table. For a much more thorough futex architectural overview, refer to:
Operations on futexes can be classified as putting a task to sleep/block to wait on a futex, or, the opposite, wake up one or more blocked tasks. Both commands make use of the architecture (very briefly) described above. Of course, each of these operations require hashing the uaddr, and thus taking the hb->lock to access the list.
In addition, the entire hash table is allocated on a single NUMA node, which creates remote node memory accesses. As systems become more powerful, having NUMA aware algorithms and data structures is paramount to take advantage of today's hardware trends. accessing the hash table from remote NUMA nodes can lead higher memory latencies.
- A futex overview and update. Darren Hart, LWN.net. Nov, 2009.
- Futexes Are Tricky. Ulrich Drepper. Nov, 2011.
- Requeue-PI: Making Glibc Condvars PI-Aware. Darren Hart, Dinakar Guniguntala.
Operations on futexes can be classified as putting a task to sleep/block to wait on a futex, or, the opposite, wake up one or more blocked tasks. Both commands make use of the architecture (very briefly) described above. Of course, each of these operations require hashing the uaddr, and thus taking the hb->lock to access the list.
Bottlenecks
The size of the hash table is evidently a major bottleneck in today's systems. Large systems, using many futexes, can be prone to high amounts of collisions; where these futexes hash and therefore lead to extra contention on the same hb->lock. Furthermore, cacheline bouncing occurs when we have multiple hash bucket spinlocks residing on the same cacheline and different futexes hash to adjacent buckets. If tasks operating on different futexes that are on the same list, the lock will become contended really fast.In addition, the entire hash table is allocated on a single NUMA node, which creates remote node memory accesses. As systems become more powerful, having NUMA aware algorithms and data structures is paramount to take advantage of today's hardware trends. accessing the hash table from remote NUMA nodes can lead higher memory latencies.
Optimizations & Results
Upstream commit a52b89eb deals with both bottlenecks. The hash table now contains 256 hash buckets per CPU as well as being NUMA aware. There was also some discussion on scaling the table up by RAM as well, and furthermore hashing on the uaddr's page node, thus reducing the cost of collisions. However this cannot be done as the pages can move between nodes at any point. In addition to enlarging the table, cacheline aligning the hash bucket structure also provided a nice optimization, as it avoids accesses across cacheline boundaries. The figure below (higher is better) shows the throughput of uaddr hashing for the different optimizations, where each thread operates on 1024 futexes.
Combining both cacheline aligning and larger, NUMA table provides the best results -- each percentage increase is added to the final value. As more futexes are dealt with, the more clear the benefits, with speedups from 78% to 800%.
Of course, performance goes down as more futexes are added to the equation. This is unavoidable given the overall architectural designs that govern futexes. Hashing on 512 threads isn't as fast as on 32 threads, but the proportion of baseline and both clearly becomes larger.
Another recent improvement is dealing with smarter wake-ups. Commit b0c29f79 avoids taking the hb->lock when there are not tasks waiting on the futex -- thus a free ride for futex(2) calls returning 0. This extends the parallelism of futexes, allowing other calls to be processed concurrently instead of wasting time spinning on a potentially contended spinlock.
These optimizations will be included in Linux 3.14.
Special thanks to, among others, Thomas Gleixner, Darren Hart and Peter Zijlstra for entertaining discussion and taking the time to review this work.
Of course, performance goes down as more futexes are added to the equation. This is unavoidable given the overall architectural designs that govern futexes. Hashing on 512 threads isn't as fast as on 32 threads, but the proportion of baseline and both clearly becomes larger.
Another recent improvement is dealing with smarter wake-ups. Commit b0c29f79 avoids taking the hb->lock when there are not tasks waiting on the futex -- thus a free ride for futex(2) calls returning 0. This extends the parallelism of futexes, allowing other calls to be processed concurrently instead of wasting time spinning on a potentially contended spinlock.
These optimizations will be included in Linux 3.14.
Special thanks to, among others, Thomas Gleixner, Darren Hart and Peter Zijlstra for entertaining discussion and taking the time to review this work.
SOCIAL SHARE CARD GENERATOR