Microsoft Developer Hoping To Land XArray Support For The Linux 4.17 Kernel
Written by Michael Larabel in Linux Kernel on 7 March 2018 at 05:28 AM EST. 16 Comments
LINUX KERNEL --
For the past several months Microsoft developer Matthew Wilcox has been working on an XArray implementation for the Linux kernel that he hopes to eventually replace the radix tree data structure. He's now hoping to land the initial XArray support in Linux 4.17.

Wilcox is hoping to slowly convert radix tree usage over to using XArrays that he feels is better fitted for how radix trees are currently being used within the Linux kernel to store data. What he considers improvements with this new data structure over radix trees is XArrays has locking as part of its API, memory is not being pre-loaded, and there are improvements to the page cache by using XArray. XArray in this context is short for an eXtensible Array.

Here's some of the latest documentation on XArray:
The XArray is an abstract data type which behaves like a very large array of pointers. It meets many of the same needs as a hash or a conventional resizable array. Unlike a hash, it allows you to sensibly go to the next or previous entry in a cache-efficient manner. In contrast to a resizable array, there is no need for copying data or changing MMU mappings in order to grow the array. It is more memory-efficient, parallelisable and cache friendly than a doubly-linked list. It takes advantage of RCU to perform lookups without locking.

The XArray implementation is efficient when the indices used are densely clustered; hashing the object and using the hash as the index will not perform well. The XArray is optimised for small indices, but still has good performance with large indices. If your index can be larger than ULONG_MAX then the XArray is not the data type for you. The most important user of the XArray is the page cache.

With the v8 patches for XArray, Matthew Wilcox believes the support is in good shape for merging into the upcoming Linux 4.17 kernel. With this initial 63 patches also includes migrating some of the first users of this code over to XArray.

We'll see soon enough if it's going to fly for Linux 4.17.
About The Author
Author picture

Michael Larabel is the principal author of Phoronix.com and founded the site in 2004 with a focus on enriching the Linux hardware experience. Michael has written more than 10,000 articles covering the state of Linux hardware support, Linux performance, graphics drivers, and other topics. Michael is also the lead developer of the Phoronix Test Suite, Phoromatic, and OpenBenchmarking.org automated benchmarking software. He can be followed via Twitter or contacted via MichaelLarabel.com.

Related Linux Kernel News
Popular News This Week