On Fri, Nov 24, 2017 at 07:01:31PM +0100, Martin Steigerwald wrote: > > The XArray is an abstract data type which behaves like an infinitely > > large array of pointers. The index into the array is an unsigned long. > > A freshly-initialised XArray contains a NULL pointer at every index. > > Yes, I think this is clearer already. > > Maybe with a few sentences on "Why does the kernel provide this?", "Where is > it used?" (if already known), "What use case is it suitable for – if I want to > implement something into the kernel (or in user space?) ?" and probably "How > does it differ from user data structures the kernel provides?" OK, I think this is getting more useful. Here's what I currently have: Overview ======== 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 is 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. A freshly-initialised XArray contains a ``NULL`` pointer at every index. Each non-``NULL`` entry in the array has three bits associated with it called tags. Each tag may be flipped on or off independently of the others. You can search for entries with a given tag set. Normal pointers may be stored in the XArray directly. They must be 4-byte aligned, which is true for any pointer returned from :c:func:`kmalloc` and :c:func:`alloc_page`. It isn't true for arbitrary user-space pointers, nor for function pointers. You can store pointers to statically allocated objects, as long as those objects have an alignment of at least 4. The XArray does not support storing :c:func:`IS_ERR` pointers; some conflict with data values and others conflict with entries the XArray uses for its own purposes. If you need to store special values which cannot be confused with real kernel pointers, the values 4, 8, ... 4092 are available. You can also store integers between 0 and ``LONG_MAX`` in the XArray. You must first convert it into an entry using :c:func:`xa_mk_value`. When you retrieve an entry from the XArray, you can check whether it is a data value by calling :c:func:`xa_is_value`, and convert it back to an integer by calling :c:func:`xa_to_value`. An unusual feature of the XArray is the ability to create entries which occupy a range of indices. Once stored to, looking up any index in the range will give the same entry as looking up any other index in the range. Setting a tag on one index will set it on all of them. Storing to any index will store to all of them. Multi-index entries can be explicitly split into smaller entries, or storing ``NULL`` into any entry will cause the XArray to forget about the range.
