radix-tree.h 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470
  1. /* SPDX-License-Identifier: GPL-2.0-or-later */
  2. /*
  3. * Copyright (C) 2001 Momchil Velikov
  4. * Portions Copyright (C) 2001 Christoph Hellwig
  5. * Copyright (C) 2006 Nick Piggin
  6. * Copyright (C) 2012 Konstantin Khlebnikov
  7. */
  8. #ifndef _LINUX_RADIX_TREE_H
  9. #define _LINUX_RADIX_TREE_H
  10. #include <linux/bitops.h>
  11. #include <linux/kernel.h>
  12. #include <linux/list.h>
  13. #include <linux/percpu.h>
  14. #include <linux/preempt.h>
  15. #include <linux/rcupdate.h>
  16. #include <linux/spinlock.h>
  17. #include <linux/types.h>
  18. #include <linux/xarray.h>
  19. #include <linux/local_lock.h>
  20. /* Keep unconverted code working */
  21. #define radix_tree_root xarray
  22. #define radix_tree_node xa_node
  23. struct radix_tree_preload {
  24. local_lock_t lock;
  25. unsigned nr;
  26. /* nodes->parent points to next preallocated node */
  27. struct radix_tree_node *nodes;
  28. };
  29. DECLARE_PER_CPU(struct radix_tree_preload, radix_tree_preloads);
  30. /*
  31. * The bottom two bits of the slot determine how the remaining bits in the
  32. * slot are interpreted:
  33. *
  34. * 00 - data pointer
  35. * 10 - internal entry
  36. * x1 - value entry
  37. *
  38. * The internal entry may be a pointer to the next level in the tree, a
  39. * sibling entry, or an indicator that the entry in this slot has been moved
  40. * to another location in the tree and the lookup should be restarted. While
  41. * NULL fits the 'data pointer' pattern, it means that there is no entry in
  42. * the tree for this index (no matter what level of the tree it is found at).
  43. * This means that storing a NULL entry in the tree is the same as deleting
  44. * the entry from the tree.
  45. */
  46. #define RADIX_TREE_ENTRY_MASK 3UL
  47. #define RADIX_TREE_INTERNAL_NODE 2UL
  48. static inline bool radix_tree_is_internal_node(void *ptr)
  49. {
  50. return ((unsigned long)ptr & RADIX_TREE_ENTRY_MASK) ==
  51. RADIX_TREE_INTERNAL_NODE;
  52. }
  53. /*** radix-tree API starts here ***/
  54. #define RADIX_TREE_MAP_SHIFT XA_CHUNK_SHIFT
  55. #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
  56. #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
  57. #define RADIX_TREE_MAX_TAGS XA_MAX_MARKS
  58. #define RADIX_TREE_TAG_LONGS XA_MARK_LONGS
  59. #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
  60. #define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
  61. RADIX_TREE_MAP_SHIFT))
  62. /* The IDR tag is stored in the low bits of xa_flags */
  63. #define ROOT_IS_IDR ((__force gfp_t)4)
  64. /* The top bits of xa_flags are used to store the root tags */
  65. #define ROOT_TAG_SHIFT (__GFP_BITS_SHIFT)
  66. #define RADIX_TREE_INIT(name, mask) XARRAY_INIT(name, mask)
  67. #define RADIX_TREE(name, mask) \
  68. struct radix_tree_root name = RADIX_TREE_INIT(name, mask)
  69. #define INIT_RADIX_TREE(root, mask) xa_init_flags(root, mask)
  70. static inline bool radix_tree_empty(const struct radix_tree_root *root)
  71. {
  72. return root->xa_head == NULL;
  73. }
  74. /**
  75. * struct radix_tree_iter - radix tree iterator state
  76. *
  77. * @index: index of current slot
  78. * @next_index: one beyond the last index for this chunk
  79. * @tags: bit-mask for tag-iterating
  80. * @node: node that contains current slot
  81. *
  82. * This radix tree iterator works in terms of "chunks" of slots. A chunk is a
  83. * subinterval of slots contained within one radix tree leaf node. It is
  84. * described by a pointer to its first slot and a struct radix_tree_iter
  85. * which holds the chunk's position in the tree and its size. For tagged
  86. * iteration radix_tree_iter also holds the slots' bit-mask for one chosen
  87. * radix tree tag.
  88. */
  89. struct radix_tree_iter {
  90. unsigned long index;
  91. unsigned long next_index;
  92. unsigned long tags;
  93. struct radix_tree_node *node;
  94. };
  95. /**
  96. * Radix-tree synchronization
  97. *
  98. * The radix-tree API requires that users provide all synchronisation (with
  99. * specific exceptions, noted below).
  100. *
  101. * Synchronization of access to the data items being stored in the tree, and
  102. * management of their lifetimes must be completely managed by API users.
  103. *
  104. * For API usage, in general,
  105. * - any function _modifying_ the tree or tags (inserting or deleting
  106. * items, setting or clearing tags) must exclude other modifications, and
  107. * exclude any functions reading the tree.
  108. * - any function _reading_ the tree or tags (looking up items or tags,
  109. * gang lookups) must exclude modifications to the tree, but may occur
  110. * concurrently with other readers.
  111. *
  112. * The notable exceptions to this rule are the following functions:
  113. * __radix_tree_lookup
  114. * radix_tree_lookup
  115. * radix_tree_lookup_slot
  116. * radix_tree_tag_get
  117. * radix_tree_gang_lookup
  118. * radix_tree_gang_lookup_tag
  119. * radix_tree_gang_lookup_tag_slot
  120. * radix_tree_tagged
  121. *
  122. * The first 7 functions are able to be called locklessly, using RCU. The
  123. * caller must ensure calls to these functions are made within rcu_read_lock()
  124. * regions. Other readers (lock-free or otherwise) and modifications may be
  125. * running concurrently.
  126. *
  127. * It is still required that the caller manage the synchronization and lifetimes
  128. * of the items. So if RCU lock-free lookups are used, typically this would mean
  129. * that the items have their own locks, or are amenable to lock-free access; and
  130. * that the items are freed by RCU (or only freed after having been deleted from
  131. * the radix tree *and* a synchronize_rcu() grace period).
  132. *
  133. * (Note, rcu_assign_pointer and rcu_dereference are not needed to control
  134. * access to data items when inserting into or looking up from the radix tree)
  135. *
  136. * Note that the value returned by radix_tree_tag_get() may not be relied upon
  137. * if only the RCU read lock is held. Functions to set/clear tags and to
  138. * delete nodes running concurrently with it may affect its result such that
  139. * two consecutive reads in the same locked section may return different
  140. * values. If reliability is required, modification functions must also be
  141. * excluded from concurrency.
  142. *
  143. * radix_tree_tagged is able to be called without locking or RCU.
  144. */
  145. /**
  146. * radix_tree_deref_slot - dereference a slot
  147. * @slot: slot pointer, returned by radix_tree_lookup_slot
  148. *
  149. * For use with radix_tree_lookup_slot(). Caller must hold tree at least read
  150. * locked across slot lookup and dereference. Not required if write lock is
  151. * held (ie. items cannot be concurrently inserted).
  152. *
  153. * radix_tree_deref_retry must be used to confirm validity of the pointer if
  154. * only the read lock is held.
  155. *
  156. * Return: entry stored in that slot.
  157. */
  158. static inline void *radix_tree_deref_slot(void __rcu **slot)
  159. {
  160. return rcu_dereference(*slot);
  161. }
  162. /**
  163. * radix_tree_deref_slot_protected - dereference a slot with tree lock held
  164. * @slot: slot pointer, returned by radix_tree_lookup_slot
  165. *
  166. * Similar to radix_tree_deref_slot. The caller does not hold the RCU read
  167. * lock but it must hold the tree lock to prevent parallel updates.
  168. *
  169. * Return: entry stored in that slot.
  170. */
  171. static inline void *radix_tree_deref_slot_protected(void __rcu **slot,
  172. spinlock_t *treelock)
  173. {
  174. return rcu_dereference_protected(*slot, lockdep_is_held(treelock));
  175. }
  176. /**
  177. * radix_tree_deref_retry - check radix_tree_deref_slot
  178. * @arg: pointer returned by radix_tree_deref_slot
  179. * Returns: 0 if retry is not required, otherwise retry is required
  180. *
  181. * radix_tree_deref_retry must be used with radix_tree_deref_slot.
  182. */
  183. static inline int radix_tree_deref_retry(void *arg)
  184. {
  185. return unlikely(radix_tree_is_internal_node(arg));
  186. }
  187. /**
  188. * radix_tree_exception - radix_tree_deref_slot returned either exception?
  189. * @arg: value returned by radix_tree_deref_slot
  190. * Returns: 0 if well-aligned pointer, non-0 if either kind of exception.
  191. */
  192. static inline int radix_tree_exception(void *arg)
  193. {
  194. return unlikely((unsigned long)arg & RADIX_TREE_ENTRY_MASK);
  195. }
  196. int radix_tree_insert(struct radix_tree_root *, unsigned long index,
  197. void *);
  198. void *__radix_tree_lookup(const struct radix_tree_root *, unsigned long index,
  199. struct radix_tree_node **nodep, void __rcu ***slotp);
  200. void *radix_tree_lookup(const struct radix_tree_root *, unsigned long);
  201. void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *,
  202. unsigned long index);
  203. void __radix_tree_replace(struct radix_tree_root *, struct radix_tree_node *,
  204. void __rcu **slot, void *entry);
  205. void radix_tree_iter_replace(struct radix_tree_root *,
  206. const struct radix_tree_iter *, void __rcu **slot, void *entry);
  207. void radix_tree_replace_slot(struct radix_tree_root *,
  208. void __rcu **slot, void *entry);
  209. void radix_tree_iter_delete(struct radix_tree_root *,
  210. struct radix_tree_iter *iter, void __rcu **slot);
  211. void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *);
  212. void *radix_tree_delete(struct radix_tree_root *, unsigned long);
  213. unsigned int radix_tree_gang_lookup(const struct radix_tree_root *,
  214. void **results, unsigned long first_index,
  215. unsigned int max_items);
  216. int radix_tree_preload(gfp_t gfp_mask);
  217. int radix_tree_maybe_preload(gfp_t gfp_mask);
  218. void radix_tree_init(void);
  219. void *radix_tree_tag_set(struct radix_tree_root *,
  220. unsigned long index, unsigned int tag);
  221. void *radix_tree_tag_clear(struct radix_tree_root *,
  222. unsigned long index, unsigned int tag);
  223. int radix_tree_tag_get(const struct radix_tree_root *,
  224. unsigned long index, unsigned int tag);
  225. void radix_tree_iter_tag_clear(struct radix_tree_root *,
  226. const struct radix_tree_iter *iter, unsigned int tag);
  227. unsigned int radix_tree_gang_lookup_tag(const struct radix_tree_root *,
  228. void **results, unsigned long first_index,
  229. unsigned int max_items, unsigned int tag);
  230. unsigned int radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *,
  231. void __rcu ***results, unsigned long first_index,
  232. unsigned int max_items, unsigned int tag);
  233. int radix_tree_tagged(const struct radix_tree_root *, unsigned int tag);
  234. static inline void radix_tree_preload_end(void)
  235. {
  236. local_unlock(&radix_tree_preloads.lock);
  237. }
  238. void __rcu **idr_get_free(struct radix_tree_root *root,
  239. struct radix_tree_iter *iter, gfp_t gfp,
  240. unsigned long max);
  241. enum {
  242. RADIX_TREE_ITER_TAG_MASK = 0x0f, /* tag index in lower nybble */
  243. RADIX_TREE_ITER_TAGGED = 0x10, /* lookup tagged slots */
  244. RADIX_TREE_ITER_CONTIG = 0x20, /* stop at first hole */
  245. };
  246. /**
  247. * radix_tree_iter_init - initialize radix tree iterator
  248. *
  249. * @iter: pointer to iterator state
  250. * @start: iteration starting index
  251. * Returns: NULL
  252. */
  253. static __always_inline void __rcu **
  254. radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
  255. {
  256. /*
  257. * Leave iter->tags uninitialized. radix_tree_next_chunk() will fill it
  258. * in the case of a successful tagged chunk lookup. If the lookup was
  259. * unsuccessful or non-tagged then nobody cares about ->tags.
  260. *
  261. * Set index to zero to bypass next_index overflow protection.
  262. * See the comment in radix_tree_next_chunk() for details.
  263. */
  264. iter->index = 0;
  265. iter->next_index = start;
  266. return NULL;
  267. }
  268. /**
  269. * radix_tree_next_chunk - find next chunk of slots for iteration
  270. *
  271. * @root: radix tree root
  272. * @iter: iterator state
  273. * @flags: RADIX_TREE_ITER_* flags and tag index
  274. * Returns: pointer to chunk first slot, or NULL if there no more left
  275. *
  276. * This function looks up the next chunk in the radix tree starting from
  277. * @iter->next_index. It returns a pointer to the chunk's first slot.
  278. * Also it fills @iter with data about chunk: position in the tree (index),
  279. * its end (next_index), and constructs a bit mask for tagged iterating (tags).
  280. */
  281. void __rcu **radix_tree_next_chunk(const struct radix_tree_root *,
  282. struct radix_tree_iter *iter, unsigned flags);
  283. /**
  284. * radix_tree_iter_lookup - look up an index in the radix tree
  285. * @root: radix tree root
  286. * @iter: iterator state
  287. * @index: key to look up
  288. *
  289. * If @index is present in the radix tree, this function returns the slot
  290. * containing it and updates @iter to describe the entry. If @index is not
  291. * present, it returns NULL.
  292. */
  293. static inline void __rcu **
  294. radix_tree_iter_lookup(const struct radix_tree_root *root,
  295. struct radix_tree_iter *iter, unsigned long index)
  296. {
  297. radix_tree_iter_init(iter, index);
  298. return radix_tree_next_chunk(root, iter, RADIX_TREE_ITER_CONTIG);
  299. }
  300. /**
  301. * radix_tree_iter_retry - retry this chunk of the iteration
  302. * @iter: iterator state
  303. *
  304. * If we iterate over a tree protected only by the RCU lock, a race
  305. * against deletion or creation may result in seeing a slot for which
  306. * radix_tree_deref_retry() returns true. If so, call this function
  307. * and continue the iteration.
  308. */
  309. static inline __must_check
  310. void __rcu **radix_tree_iter_retry(struct radix_tree_iter *iter)
  311. {
  312. iter->next_index = iter->index;
  313. iter->tags = 0;
  314. return NULL;
  315. }
  316. static inline unsigned long
  317. __radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots)
  318. {
  319. return iter->index + slots;
  320. }
  321. /**
  322. * radix_tree_iter_resume - resume iterating when the chunk may be invalid
  323. * @slot: pointer to current slot
  324. * @iter: iterator state
  325. * Returns: New slot pointer
  326. *
  327. * If the iterator needs to release then reacquire a lock, the chunk may
  328. * have been invalidated by an insertion or deletion. Call this function
  329. * before releasing the lock to continue the iteration from the next index.
  330. */
  331. void __rcu **__must_check radix_tree_iter_resume(void __rcu **slot,
  332. struct radix_tree_iter *iter);
  333. /**
  334. * radix_tree_chunk_size - get current chunk size
  335. *
  336. * @iter: pointer to radix tree iterator
  337. * Returns: current chunk size
  338. */
  339. static __always_inline long
  340. radix_tree_chunk_size(struct radix_tree_iter *iter)
  341. {
  342. return iter->next_index - iter->index;
  343. }
  344. /**
  345. * radix_tree_next_slot - find next slot in chunk
  346. *
  347. * @slot: pointer to current slot
  348. * @iter: pointer to iterator state
  349. * @flags: RADIX_TREE_ITER_*, should be constant
  350. * Returns: pointer to next slot, or NULL if there no more left
  351. *
  352. * This function updates @iter->index in the case of a successful lookup.
  353. * For tagged lookup it also eats @iter->tags.
  354. *
  355. * There are several cases where 'slot' can be passed in as NULL to this
  356. * function. These cases result from the use of radix_tree_iter_resume() or
  357. * radix_tree_iter_retry(). In these cases we don't end up dereferencing
  358. * 'slot' because either:
  359. * a) we are doing tagged iteration and iter->tags has been set to 0, or
  360. * b) we are doing non-tagged iteration, and iter->index and iter->next_index
  361. * have been set up so that radix_tree_chunk_size() returns 1 or 0.
  362. */
  363. static __always_inline void __rcu **radix_tree_next_slot(void __rcu **slot,
  364. struct radix_tree_iter *iter, unsigned flags)
  365. {
  366. if (flags & RADIX_TREE_ITER_TAGGED) {
  367. iter->tags >>= 1;
  368. if (unlikely(!iter->tags))
  369. return NULL;
  370. if (likely(iter->tags & 1ul)) {
  371. iter->index = __radix_tree_iter_add(iter, 1);
  372. slot++;
  373. goto found;
  374. }
  375. if (!(flags & RADIX_TREE_ITER_CONTIG)) {
  376. unsigned offset = __ffs(iter->tags);
  377. iter->tags >>= offset++;
  378. iter->index = __radix_tree_iter_add(iter, offset);
  379. slot += offset;
  380. goto found;
  381. }
  382. } else {
  383. long count = radix_tree_chunk_size(iter);
  384. while (--count > 0) {
  385. slot++;
  386. iter->index = __radix_tree_iter_add(iter, 1);
  387. if (likely(*slot))
  388. goto found;
  389. if (flags & RADIX_TREE_ITER_CONTIG) {
  390. /* forbid switching to the next chunk */
  391. iter->next_index = 0;
  392. break;
  393. }
  394. }
  395. }
  396. return NULL;
  397. found:
  398. return slot;
  399. }
  400. /**
  401. * radix_tree_for_each_slot - iterate over non-empty slots
  402. *
  403. * @slot: the void** variable for pointer to slot
  404. * @root: the struct radix_tree_root pointer
  405. * @iter: the struct radix_tree_iter pointer
  406. * @start: iteration starting index
  407. *
  408. * @slot points to radix tree slot, @iter->index contains its index.
  409. */
  410. #define radix_tree_for_each_slot(slot, root, iter, start) \
  411. for (slot = radix_tree_iter_init(iter, start) ; \
  412. slot || (slot = radix_tree_next_chunk(root, iter, 0)) ; \
  413. slot = radix_tree_next_slot(slot, iter, 0))
  414. /**
  415. * radix_tree_for_each_tagged - iterate over tagged slots
  416. *
  417. * @slot: the void** variable for pointer to slot
  418. * @root: the struct radix_tree_root pointer
  419. * @iter: the struct radix_tree_iter pointer
  420. * @start: iteration starting index
  421. * @tag: tag index
  422. *
  423. * @slot points to radix tree slot, @iter->index contains its index.
  424. */
  425. #define radix_tree_for_each_tagged(slot, root, iter, start, tag) \
  426. for (slot = radix_tree_iter_init(iter, start) ; \
  427. slot || (slot = radix_tree_next_chunk(root, iter, \
  428. RADIX_TREE_ITER_TAGGED | tag)) ; \
  429. slot = radix_tree_next_slot(slot, iter, \
  430. RADIX_TREE_ITER_TAGGED | tag))
  431. #endif /* _LINUX_RADIX_TREE_H */