xarray.rst 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492
  1. .. SPDX-License-Identifier: GPL-2.0+
  2. ======
  3. XArray
  4. ======
  5. :Author: Matthew Wilcox
  6. Overview
  7. ========
  8. The XArray is an abstract data type which behaves like a very large array
  9. of pointers. It meets many of the same needs as a hash or a conventional
  10. resizable array. Unlike a hash, it allows you to sensibly go to the
  11. next or previous entry in a cache-efficient manner. In contrast to a
  12. resizable array, there is no need to copy data or change MMU mappings in
  13. order to grow the array. It is more memory-efficient, parallelisable
  14. and cache friendly than a doubly-linked list. It takes advantage of
  15. RCU to perform lookups without locking.
  16. The XArray implementation is efficient when the indices used are densely
  17. clustered; hashing the object and using the hash as the index will not
  18. perform well. The XArray is optimised for small indices, but still has
  19. good performance with large indices. If your index can be larger than
  20. ``ULONG_MAX`` then the XArray is not the data type for you. The most
  21. important user of the XArray is the page cache.
  22. Normal pointers may be stored in the XArray directly. They must be 4-byte
  23. aligned, which is true for any pointer returned from kmalloc() and
  24. alloc_page(). It isn't true for arbitrary user-space pointers,
  25. nor for function pointers. You can store pointers to statically allocated
  26. objects, as long as those objects have an alignment of at least 4.
  27. You can also store integers between 0 and ``LONG_MAX`` in the XArray.
  28. You must first convert it into an entry using xa_mk_value().
  29. When you retrieve an entry from the XArray, you can check whether it is
  30. a value entry by calling xa_is_value(), and convert it back to
  31. an integer by calling xa_to_value().
  32. Some users want to tag the pointers they store in the XArray. You can
  33. call xa_tag_pointer() to create an entry with a tag, xa_untag_pointer()
  34. to turn a tagged entry back into an untagged pointer and xa_pointer_tag()
  35. to retrieve the tag of an entry. Tagged pointers use the same bits that
  36. are used to distinguish value entries from normal pointers, so you must
  37. decide whether they want to store value entries or tagged pointers in
  38. any particular XArray.
  39. The XArray does not support storing IS_ERR() pointers as some
  40. conflict with value entries or internal entries.
  41. An unusual feature of the XArray is the ability to create entries which
  42. occupy a range of indices. Once stored to, looking up any index in
  43. the range will return the same entry as looking up any other index in
  44. the range. Storing to any index will store to all of them. Multi-index
  45. entries can be explicitly split into smaller entries, or storing ``NULL``
  46. into any entry will cause the XArray to forget about the range.
  47. Normal API
  48. ==========
  49. Start by initialising an XArray, either with DEFINE_XARRAY()
  50. for statically allocated XArrays or xa_init() for dynamically
  51. allocated ones. A freshly-initialised XArray contains a ``NULL``
  52. pointer at every index.
  53. You can then set entries using xa_store() and get entries
  54. using xa_load(). xa_store will overwrite any entry with the
  55. new entry and return the previous entry stored at that index. You can
  56. use xa_erase() instead of calling xa_store() with a
  57. ``NULL`` entry. There is no difference between an entry that has never
  58. been stored to, one that has been erased and one that has most recently
  59. had ``NULL`` stored to it.
  60. You can conditionally replace an entry at an index by using
  61. xa_cmpxchg(). Like cmpxchg(), it will only succeed if
  62. the entry at that index has the 'old' value. It also returns the entry
  63. which was at that index; if it returns the same entry which was passed as
  64. 'old', then xa_cmpxchg() succeeded.
  65. If you want to only store a new entry to an index if the current entry
  66. at that index is ``NULL``, you can use xa_insert() which
  67. returns ``-EBUSY`` if the entry is not empty.
  68. You can copy entries out of the XArray into a plain array by calling
  69. xa_extract(). Or you can iterate over the present entries in the XArray
  70. by calling xa_for_each(), xa_for_each_start() or xa_for_each_range().
  71. You may prefer to use xa_find() or xa_find_after() to move to the next
  72. present entry in the XArray.
  73. Calling xa_store_range() stores the same entry in a range
  74. of indices. If you do this, some of the other operations will behave
  75. in a slightly odd way. For example, marking the entry at one index
  76. may result in the entry being marked at some, but not all of the other
  77. indices. Storing into one index may result in the entry retrieved by
  78. some, but not all of the other indices changing.
  79. Sometimes you need to ensure that a subsequent call to xa_store()
  80. will not need to allocate memory. The xa_reserve() function
  81. will store a reserved entry at the indicated index. Users of the
  82. normal API will see this entry as containing ``NULL``. If you do
  83. not need to use the reserved entry, you can call xa_release()
  84. to remove the unused entry. If another user has stored to the entry
  85. in the meantime, xa_release() will do nothing; if instead you
  86. want the entry to become ``NULL``, you should use xa_erase().
  87. Using xa_insert() on a reserved entry will fail.
  88. If all entries in the array are ``NULL``, the xa_empty() function
  89. will return ``true``.
  90. Finally, you can remove all entries from an XArray by calling
  91. xa_destroy(). If the XArray entries are pointers, you may wish
  92. to free the entries first. You can do this by iterating over all present
  93. entries in the XArray using the xa_for_each() iterator.
  94. Search Marks
  95. ------------
  96. Each entry in the array has three bits associated with it called marks.
  97. Each mark may be set or cleared independently of the others. You can
  98. iterate over marked entries by using the xa_for_each_marked() iterator.
  99. You can enquire whether a mark is set on an entry by using
  100. xa_get_mark(). If the entry is not ``NULL``, you can set a mark on it
  101. by using xa_set_mark() and remove the mark from an entry by calling
  102. xa_clear_mark(). You can ask whether any entry in the XArray has a
  103. particular mark set by calling xa_marked(). Erasing an entry from the
  104. XArray causes all marks associated with that entry to be cleared.
  105. Setting or clearing a mark on any index of a multi-index entry will
  106. affect all indices covered by that entry. Querying the mark on any
  107. index will return the same result.
  108. There is no way to iterate over entries which are not marked; the data
  109. structure does not allow this to be implemented efficiently. There are
  110. not currently iterators to search for logical combinations of bits (eg
  111. iterate over all entries which have both ``XA_MARK_1`` and ``XA_MARK_2``
  112. set, or iterate over all entries which have ``XA_MARK_0`` or ``XA_MARK_2``
  113. set). It would be possible to add these if a user arises.
  114. Allocating XArrays
  115. ------------------
  116. If you use DEFINE_XARRAY_ALLOC() to define the XArray, or
  117. initialise it by passing ``XA_FLAGS_ALLOC`` to xa_init_flags(),
  118. the XArray changes to track whether entries are in use or not.
  119. You can call xa_alloc() to store the entry at an unused index
  120. in the XArray. If you need to modify the array from interrupt context,
  121. you can use xa_alloc_bh() or xa_alloc_irq() to disable
  122. interrupts while allocating the ID.
  123. Using xa_store(), xa_cmpxchg() or xa_insert() will
  124. also mark the entry as being allocated. Unlike a normal XArray, storing
  125. ``NULL`` will mark the entry as being in use, like xa_reserve().
  126. To free an entry, use xa_erase() (or xa_release() if
  127. you only want to free the entry if it's ``NULL``).
  128. By default, the lowest free entry is allocated starting from 0. If you
  129. want to allocate entries starting at 1, it is more efficient to use
  130. DEFINE_XARRAY_ALLOC1() or ``XA_FLAGS_ALLOC1``. If you want to
  131. allocate IDs up to a maximum, then wrap back around to the lowest free
  132. ID, you can use xa_alloc_cyclic().
  133. You cannot use ``XA_MARK_0`` with an allocating XArray as this mark
  134. is used to track whether an entry is free or not. The other marks are
  135. available for your use.
  136. Memory allocation
  137. -----------------
  138. The xa_store(), xa_cmpxchg(), xa_alloc(),
  139. xa_reserve() and xa_insert() functions take a gfp_t
  140. parameter in case the XArray needs to allocate memory to store this entry.
  141. If the entry is being deleted, no memory allocation needs to be performed,
  142. and the GFP flags specified will be ignored.
  143. It is possible for no memory to be allocatable, particularly if you pass
  144. a restrictive set of GFP flags. In that case, the functions return a
  145. special value which can be turned into an errno using xa_err().
  146. If you don't need to know exactly which error occurred, using
  147. xa_is_err() is slightly more efficient.
  148. Locking
  149. -------
  150. When using the Normal API, you do not have to worry about locking.
  151. The XArray uses RCU and an internal spinlock to synchronise access:
  152. No lock needed:
  153. * xa_empty()
  154. * xa_marked()
  155. Takes RCU read lock:
  156. * xa_load()
  157. * xa_for_each()
  158. * xa_for_each_start()
  159. * xa_for_each_range()
  160. * xa_find()
  161. * xa_find_after()
  162. * xa_extract()
  163. * xa_get_mark()
  164. Takes xa_lock internally:
  165. * xa_store()
  166. * xa_store_bh()
  167. * xa_store_irq()
  168. * xa_insert()
  169. * xa_insert_bh()
  170. * xa_insert_irq()
  171. * xa_erase()
  172. * xa_erase_bh()
  173. * xa_erase_irq()
  174. * xa_cmpxchg()
  175. * xa_cmpxchg_bh()
  176. * xa_cmpxchg_irq()
  177. * xa_store_range()
  178. * xa_alloc()
  179. * xa_alloc_bh()
  180. * xa_alloc_irq()
  181. * xa_reserve()
  182. * xa_reserve_bh()
  183. * xa_reserve_irq()
  184. * xa_destroy()
  185. * xa_set_mark()
  186. * xa_clear_mark()
  187. Assumes xa_lock held on entry:
  188. * __xa_store()
  189. * __xa_insert()
  190. * __xa_erase()
  191. * __xa_cmpxchg()
  192. * __xa_alloc()
  193. * __xa_set_mark()
  194. * __xa_clear_mark()
  195. If you want to take advantage of the lock to protect the data structures
  196. that you are storing in the XArray, you can call xa_lock()
  197. before calling xa_load(), then take a reference count on the
  198. object you have found before calling xa_unlock(). This will
  199. prevent stores from removing the object from the array between looking
  200. up the object and incrementing the refcount. You can also use RCU to
  201. avoid dereferencing freed memory, but an explanation of that is beyond
  202. the scope of this document.
  203. The XArray does not disable interrupts or softirqs while modifying
  204. the array. It is safe to read the XArray from interrupt or softirq
  205. context as the RCU lock provides enough protection.
  206. If, for example, you want to store entries in the XArray in process
  207. context and then erase them in softirq context, you can do that this way::
  208. void foo_init(struct foo *foo)
  209. {
  210. xa_init_flags(&foo->array, XA_FLAGS_LOCK_BH);
  211. }
  212. int foo_store(struct foo *foo, unsigned long index, void *entry)
  213. {
  214. int err;
  215. xa_lock_bh(&foo->array);
  216. err = xa_err(__xa_store(&foo->array, index, entry, GFP_KERNEL));
  217. if (!err)
  218. foo->count++;
  219. xa_unlock_bh(&foo->array);
  220. return err;
  221. }
  222. /* foo_erase() is only called from softirq context */
  223. void foo_erase(struct foo *foo, unsigned long index)
  224. {
  225. xa_lock(&foo->array);
  226. __xa_erase(&foo->array, index);
  227. foo->count--;
  228. xa_unlock(&foo->array);
  229. }
  230. If you are going to modify the XArray from interrupt or softirq context,
  231. you need to initialise the array using xa_init_flags(), passing
  232. ``XA_FLAGS_LOCK_IRQ`` or ``XA_FLAGS_LOCK_BH``.
  233. The above example also shows a common pattern of wanting to extend the
  234. coverage of the xa_lock on the store side to protect some statistics
  235. associated with the array.
  236. Sharing the XArray with interrupt context is also possible, either
  237. using xa_lock_irqsave() in both the interrupt handler and process
  238. context, or xa_lock_irq() in process context and xa_lock()
  239. in the interrupt handler. Some of the more common patterns have helper
  240. functions such as xa_store_bh(), xa_store_irq(),
  241. xa_erase_bh(), xa_erase_irq(), xa_cmpxchg_bh()
  242. and xa_cmpxchg_irq().
  243. Sometimes you need to protect access to the XArray with a mutex because
  244. that lock sits above another mutex in the locking hierarchy. That does
  245. not entitle you to use functions like __xa_erase() without taking
  246. the xa_lock; the xa_lock is used for lockdep validation and will be used
  247. for other purposes in the future.
  248. The __xa_set_mark() and __xa_clear_mark() functions are also
  249. available for situations where you look up an entry and want to atomically
  250. set or clear a mark. It may be more efficient to use the advanced API
  251. in this case, as it will save you from walking the tree twice.
  252. Advanced API
  253. ============
  254. The advanced API offers more flexibility and better performance at the
  255. cost of an interface which can be harder to use and has fewer safeguards.
  256. No locking is done for you by the advanced API, and you are required
  257. to use the xa_lock while modifying the array. You can choose whether
  258. to use the xa_lock or the RCU lock while doing read-only operations on
  259. the array. You can mix advanced and normal operations on the same array;
  260. indeed the normal API is implemented in terms of the advanced API. The
  261. advanced API is only available to modules with a GPL-compatible license.
  262. The advanced API is based around the xa_state. This is an opaque data
  263. structure which you declare on the stack using the XA_STATE()
  264. macro. This macro initialises the xa_state ready to start walking
  265. around the XArray. It is used as a cursor to maintain the position
  266. in the XArray and let you compose various operations together without
  267. having to restart from the top every time.
  268. The xa_state is also used to store errors. You can call
  269. xas_error() to retrieve the error. All operations check whether
  270. the xa_state is in an error state before proceeding, so there's no need
  271. for you to check for an error after each call; you can make multiple
  272. calls in succession and only check at a convenient point. The only
  273. errors currently generated by the XArray code itself are ``ENOMEM`` and
  274. ``EINVAL``, but it supports arbitrary errors in case you want to call
  275. xas_set_err() yourself.
  276. If the xa_state is holding an ``ENOMEM`` error, calling xas_nomem()
  277. will attempt to allocate more memory using the specified gfp flags and
  278. cache it in the xa_state for the next attempt. The idea is that you take
  279. the xa_lock, attempt the operation and drop the lock. The operation
  280. attempts to allocate memory while holding the lock, but it is more
  281. likely to fail. Once you have dropped the lock, xas_nomem()
  282. can try harder to allocate more memory. It will return ``true`` if it
  283. is worth retrying the operation (i.e. that there was a memory error *and*
  284. more memory was allocated). If it has previously allocated memory, and
  285. that memory wasn't used, and there is no error (or some error that isn't
  286. ``ENOMEM``), then it will free the memory previously allocated.
  287. Internal Entries
  288. ----------------
  289. The XArray reserves some entries for its own purposes. These are never
  290. exposed through the normal API, but when using the advanced API, it's
  291. possible to see them. Usually the best way to handle them is to pass them
  292. to xas_retry(), and retry the operation if it returns ``true``.
  293. .. flat-table::
  294. :widths: 1 1 6
  295. * - Name
  296. - Test
  297. - Usage
  298. * - Node
  299. - xa_is_node()
  300. - An XArray node. May be visible when using a multi-index xa_state.
  301. * - Sibling
  302. - xa_is_sibling()
  303. - A non-canonical entry for a multi-index entry. The value indicates
  304. which slot in this node has the canonical entry.
  305. * - Retry
  306. - xa_is_retry()
  307. - This entry is currently being modified by a thread which has the
  308. xa_lock. The node containing this entry may be freed at the end
  309. of this RCU period. You should restart the lookup from the head
  310. of the array.
  311. * - Zero
  312. - xa_is_zero()
  313. - Zero entries appear as ``NULL`` through the Normal API, but occupy
  314. an entry in the XArray which can be used to reserve the index for
  315. future use. This is used by allocating XArrays for allocated entries
  316. which are ``NULL``.
  317. Other internal entries may be added in the future. As far as possible, they
  318. will be handled by xas_retry().
  319. Additional functionality
  320. ------------------------
  321. The xas_create_range() function allocates all the necessary memory
  322. to store every entry in a range. It will set ENOMEM in the xa_state if
  323. it cannot allocate memory.
  324. You can use xas_init_marks() to reset the marks on an entry
  325. to their default state. This is usually all marks clear, unless the
  326. XArray is marked with ``XA_FLAGS_TRACK_FREE``, in which case mark 0 is set
  327. and all other marks are clear. Replacing one entry with another using
  328. xas_store() will not reset the marks on that entry; if you want
  329. the marks reset, you should do that explicitly.
  330. The xas_load() will walk the xa_state as close to the entry
  331. as it can. If you know the xa_state has already been walked to the
  332. entry and need to check that the entry hasn't changed, you can use
  333. xas_reload() to save a function call.
  334. If you need to move to a different index in the XArray, call
  335. xas_set(). This resets the cursor to the top of the tree, which
  336. will generally make the next operation walk the cursor to the desired
  337. spot in the tree. If you want to move to the next or previous index,
  338. call xas_next() or xas_prev(). Setting the index does
  339. not walk the cursor around the array so does not require a lock to be
  340. held, while moving to the next or previous index does.
  341. You can search for the next present entry using xas_find(). This
  342. is the equivalent of both xa_find() and xa_find_after();
  343. if the cursor has been walked to an entry, then it will find the next
  344. entry after the one currently referenced. If not, it will return the
  345. entry at the index of the xa_state. Using xas_next_entry() to
  346. move to the next present entry instead of xas_find() will save
  347. a function call in the majority of cases at the expense of emitting more
  348. inline code.
  349. The xas_find_marked() function is similar. If the xa_state has
  350. not been walked, it will return the entry at the index of the xa_state,
  351. if it is marked. Otherwise, it will return the first marked entry after
  352. the entry referenced by the xa_state. The xas_next_marked()
  353. function is the equivalent of xas_next_entry().
  354. When iterating over a range of the XArray using xas_for_each()
  355. or xas_for_each_marked(), it may be necessary to temporarily stop
  356. the iteration. The xas_pause() function exists for this purpose.
  357. After you have done the necessary work and wish to resume, the xa_state
  358. is in an appropriate state to continue the iteration after the entry
  359. you last processed. If you have interrupts disabled while iterating,
  360. then it is good manners to pause the iteration and reenable interrupts
  361. every ``XA_CHECK_SCHED`` entries.
  362. The xas_get_mark(), xas_set_mark() and xas_clear_mark() functions require
  363. the xa_state cursor to have been moved to the appropriate location in the
  364. XArray; they will do nothing if you have called xas_pause() or xas_set()
  365. immediately before.
  366. You can call xas_set_update() to have a callback function
  367. called each time the XArray updates a node. This is used by the page
  368. cache workingset code to maintain its list of nodes which contain only
  369. shadow entries.
  370. Multi-Index Entries
  371. -------------------
  372. The XArray has the ability to tie multiple indices together so that
  373. operations on one index affect all indices. For example, storing into
  374. any index will change the value of the entry retrieved from any index.
  375. Setting or clearing a mark on any index will set or clear the mark
  376. on every index that is tied together. The current implementation
  377. only allows tying ranges which are aligned powers of two together;
  378. eg indices 64-127 may be tied together, but 2-6 may not be. This may
  379. save substantial quantities of memory; for example tying 512 entries
  380. together will save over 4kB.
  381. You can create a multi-index entry by using XA_STATE_ORDER()
  382. or xas_set_order() followed by a call to xas_store().
  383. Calling xas_load() with a multi-index xa_state will walk the
  384. xa_state to the right location in the tree, but the return value is not
  385. meaningful, potentially being an internal entry or ``NULL`` even when there
  386. is an entry stored within the range. Calling xas_find_conflict()
  387. will return the first entry within the range or ``NULL`` if there are no
  388. entries in the range. The xas_for_each_conflict() iterator will
  389. iterate over every entry which overlaps the specified range.
  390. If xas_load() encounters a multi-index entry, the xa_index
  391. in the xa_state will not be changed. When iterating over an XArray
  392. or calling xas_find(), if the initial index is in the middle
  393. of a multi-index entry, it will not be altered. Subsequent calls
  394. or iterations will move the index to the first index in the range.
  395. Each entry will only be returned once, no matter how many indices it
  396. occupies.
  397. Using xas_next() or xas_prev() with a multi-index xa_state is not
  398. supported. Using either of these functions on a multi-index entry will
  399. reveal sibling entries; these should be skipped over by the caller.
  400. Storing ``NULL`` into any index of a multi-index entry will set the
  401. entry at every index to ``NULL`` and dissolve the tie. A multi-index
  402. entry can be split into entries occupying smaller ranges by calling
  403. xas_split_alloc() without the xa_lock held, followed by taking the lock
  404. and calling xas_split().
  405. Functions and structures
  406. ========================
  407. .. kernel-doc:: include/linux/xarray.h
  408. .. kernel-doc:: lib/xarray.c