The Maple Tree, A Modern Data Structure for a Complex Problem


In recent years, processors have experienced growth in core counts which have pushed software to be multi-threaded and increased contention in the virtual memory data structure. The memory management subsystem uses the mmap_sem lock for write protection of the VMAs. Optimizing the mmap_sem lock into a rw-semaphore helped contention but did not solve the underlying issue. Even with a single threaded program and a well-intended system admin, contention does arise through proc file accesses for application monitoring.

In this blog, we introduce a new data structure that can track gaps, store ranges, and be implemented in an RCU compatible manner. This is the Maple Tree.
Click to Read More at Oracle Linux Kernel Development