radix-tree.c 25 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026
  1. /*
  2. * Copyright (C) 2001 Momchil Velikov
  3. * Portions Copyright (C) 2001 Christoph Hellwig
  4. * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com>
  5. * Copyright (C) 2006 Nick Piggin
  6. *
  7. * This program is free software; you can redistribute it and/or
  8. * modify it under the terms of the GNU General Public License as
  9. * published by the Free Software Foundation; either version 2, or (at
  10. * your option) any later version.
  11. *
  12. * This program is distributed in the hope that it will be useful, but
  13. * WITHOUT ANY WARRANTY; without even the implied warranty of
  14. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15. * General Public License for more details.
  16. *
  17. * You should have received a copy of the GNU General Public License
  18. * along with this program; if not, write to the Free Software
  19. * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  20. */
  21. #include <linux/errno.h>
  22. #include <linux/init.h>
  23. #include <linux/kernel.h>
  24. #include <linux/module.h>
  25. #include <linux/radix-tree.h>
  26. #include <linux/percpu.h>
  27. #include <linux/slab.h>
  28. #include <linux/notifier.h>
  29. #include <linux/cpu.h>
  30. #include <linux/gfp.h>
  31. #include <linux/string.h>
  32. #include <linux/bitops.h>
  33. #include <linux/rcupdate.h>
  34. #ifdef __KERNEL__
  35. #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
  36. #else
  37. #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */
  38. #endif
  39. #define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
  40. #define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
  41. #define RADIX_TREE_TAG_LONGS \
  42. ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
  43. struct radix_tree_node {
  44. unsigned int height; /* Height from the bottom */
  45. unsigned int count;
  46. struct rcu_head rcu_head;
  47. void *slots[RADIX_TREE_MAP_SIZE];
  48. unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
  49. };
  50. struct radix_tree_path {
  51. struct radix_tree_node *node;
  52. int offset;
  53. };
  54. #define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
  55. #define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)
  56. static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly;
  57. /*
  58. * Radix tree node cache.
  59. */
  60. static struct kmem_cache *radix_tree_node_cachep;
  61. /*
  62. * Per-cpu pool of preloaded nodes
  63. */
  64. struct radix_tree_preload {
  65. int nr;
  66. struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH];
  67. };
  68. DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
  69. static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
  70. {
  71. return root->gfp_mask & __GFP_BITS_MASK;
  72. }
  73. /*
  74. * This assumes that the caller has performed appropriate preallocation, and
  75. * that the caller has pinned this thread of control to the current CPU.
  76. */
  77. static struct radix_tree_node *
  78. radix_tree_node_alloc(struct radix_tree_root *root)
  79. {
  80. struct radix_tree_node *ret;
  81. gfp_t gfp_mask = root_gfp_mask(root);
  82. ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
  83. if (ret == NULL && !(gfp_mask & __GFP_WAIT)) {
  84. struct radix_tree_preload *rtp;
  85. rtp = &__get_cpu_var(radix_tree_preloads);
  86. if (rtp->nr) {
  87. ret = rtp->nodes[rtp->nr - 1];
  88. rtp->nodes[rtp->nr - 1] = NULL;
  89. rtp->nr--;
  90. }
  91. }
  92. BUG_ON(radix_tree_is_direct_ptr(ret));
  93. return ret;
  94. }
  95. static void radix_tree_node_rcu_free(struct rcu_head *head)
  96. {
  97. struct radix_tree_node *node =
  98. container_of(head, struct radix_tree_node, rcu_head);
  99. kmem_cache_free(radix_tree_node_cachep, node);
  100. }
  101. static inline void
  102. radix_tree_node_free(struct radix_tree_node *node)
  103. {
  104. call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
  105. }
  106. /*
  107. * Load up this CPU's radix_tree_node buffer with sufficient objects to
  108. * ensure that the addition of a single element in the tree cannot fail. On
  109. * success, return zero, with preemption disabled. On error, return -ENOMEM
  110. * with preemption not disabled.
  111. */
  112. int radix_tree_preload(gfp_t gfp_mask)
  113. {
  114. struct radix_tree_preload *rtp;
  115. struct radix_tree_node *node;
  116. int ret = -ENOMEM;
  117. preempt_disable();
  118. rtp = &__get_cpu_var(radix_tree_preloads);
  119. while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
  120. preempt_enable();
  121. node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
  122. if (node == NULL)
  123. goto out;
  124. preempt_disable();
  125. rtp = &__get_cpu_var(radix_tree_preloads);
  126. if (rtp->nr < ARRAY_SIZE(rtp->nodes))
  127. rtp->nodes[rtp->nr++] = node;
  128. else
  129. kmem_cache_free(radix_tree_node_cachep, node);
  130. }
  131. ret = 0;
  132. out:
  133. return ret;
  134. }
  135. static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
  136. int offset)
  137. {
  138. __set_bit(offset, node->tags[tag]);
  139. }
  140. static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
  141. int offset)
  142. {
  143. __clear_bit(offset, node->tags[tag]);
  144. }
  145. static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
  146. int offset)
  147. {
  148. return test_bit(offset, node->tags[tag]);
  149. }
  150. static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
  151. {
  152. root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));
  153. }
  154. static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
  155. {
  156. root->gfp_mask &= (__force gfp_t)~(1 << (tag + __GFP_BITS_SHIFT));
  157. }
  158. static inline void root_tag_clear_all(struct radix_tree_root *root)
  159. {
  160. root->gfp_mask &= __GFP_BITS_MASK;
  161. }
  162. static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
  163. {
  164. return (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
  165. }
  166. /*
  167. * Returns 1 if any slot in the node has this tag set.
  168. * Otherwise returns 0.
  169. */
  170. static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
  171. {
  172. int idx;
  173. for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
  174. if (node->tags[tag][idx])
  175. return 1;
  176. }
  177. return 0;
  178. }
  179. /*
  180. * Return the maximum key which can be store into a
  181. * radix tree with height HEIGHT.
  182. */
  183. static inline unsigned long radix_tree_maxindex(unsigned int height)
  184. {
  185. return height_to_maxindex[height];
  186. }
  187. /*
  188. * Extend a radix tree so it can store key @index.
  189. */
  190. static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
  191. {
  192. struct radix_tree_node *node;
  193. unsigned int height;
  194. int tag;
  195. /* Figure out what the height should be. */
  196. height = root->height + 1;
  197. while (index > radix_tree_maxindex(height))
  198. height++;
  199. if (root->rnode == NULL) {
  200. root->height = height;
  201. goto out;
  202. }
  203. do {
  204. unsigned int newheight;
  205. if (!(node = radix_tree_node_alloc(root)))
  206. return -ENOMEM;
  207. /* Increase the height. */
  208. node->slots[0] = radix_tree_direct_to_ptr(root->rnode);
  209. /* Propagate the aggregated tag info into the new root */
  210. for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
  211. if (root_tag_get(root, tag))
  212. tag_set(node, tag, 0);
  213. }
  214. newheight = root->height+1;
  215. node->height = newheight;
  216. node->count = 1;
  217. rcu_assign_pointer(root->rnode, node);
  218. root->height = newheight;
  219. } while (height > root->height);
  220. out:
  221. return 0;
  222. }
  223. /**
  224. * radix_tree_insert - insert into a radix tree
  225. * @root: radix tree root
  226. * @index: index key
  227. * @item: item to insert
  228. *
  229. * Insert an item into the radix tree at position @index.
  230. */
  231. int radix_tree_insert(struct radix_tree_root *root,
  232. unsigned long index, void *item)
  233. {
  234. struct radix_tree_node *node = NULL, *slot;
  235. unsigned int height, shift;
  236. int offset;
  237. int error;
  238. BUG_ON(radix_tree_is_direct_ptr(item));
  239. /* Make sure the tree is high enough. */
  240. if (index > radix_tree_maxindex(root->height)) {
  241. error = radix_tree_extend(root, index);
  242. if (error)
  243. return error;
  244. }
  245. slot = root->rnode;
  246. height = root->height;
  247. shift = (height-1) * RADIX_TREE_MAP_SHIFT;
  248. offset = 0; /* uninitialised var warning */
  249. while (height > 0) {
  250. if (slot == NULL) {
  251. /* Have to add a child node. */
  252. if (!(slot = radix_tree_node_alloc(root)))
  253. return -ENOMEM;
  254. slot->height = height;
  255. if (node) {
  256. rcu_assign_pointer(node->slots[offset], slot);
  257. node->count++;
  258. } else
  259. rcu_assign_pointer(root->rnode, slot);
  260. }
  261. /* Go a level down */
  262. offset = (index >> shift) & RADIX_TREE_MAP_MASK;
  263. node = slot;
  264. slot = node->slots[offset];
  265. shift -= RADIX_TREE_MAP_SHIFT;
  266. height--;
  267. }
  268. if (slot != NULL)
  269. return -EEXIST;
  270. if (node) {
  271. node->count++;
  272. rcu_assign_pointer(node->slots[offset], item);
  273. BUG_ON(tag_get(node, 0, offset));
  274. BUG_ON(tag_get(node, 1, offset));
  275. } else {
  276. rcu_assign_pointer(root->rnode, radix_tree_ptr_to_direct(item));
  277. BUG_ON(root_tag_get(root, 0));
  278. BUG_ON(root_tag_get(root, 1));
  279. }
  280. return 0;
  281. }
  282. EXPORT_SYMBOL(radix_tree_insert);
  283. /**
  284. * radix_tree_lookup_slot - lookup a slot in a radix tree
  285. * @root: radix tree root
  286. * @index: index key
  287. *
  288. * Returns: the slot corresponding to the position @index in the
  289. * radix tree @root. This is useful for update-if-exists operations.
  290. *
  291. * This function cannot be called under rcu_read_lock, it must be
  292. * excluded from writers, as must the returned slot for subsequent
  293. * use by radix_tree_deref_slot() and radix_tree_replace slot.
  294. * Caller must hold tree write locked across slot lookup and
  295. * replace.
  296. */
  297. void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
  298. {
  299. unsigned int height, shift;
  300. struct radix_tree_node *node, **slot;
  301. node = root->rnode;
  302. if (node == NULL)
  303. return NULL;
  304. if (radix_tree_is_direct_ptr(node)) {
  305. if (index > 0)
  306. return NULL;
  307. return (void **)&root->rnode;
  308. }
  309. height = node->height;
  310. if (index > radix_tree_maxindex(height))
  311. return NULL;
  312. shift = (height-1) * RADIX_TREE_MAP_SHIFT;
  313. do {
  314. slot = (struct radix_tree_node **)
  315. (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
  316. node = *slot;
  317. if (node == NULL)
  318. return NULL;
  319. shift -= RADIX_TREE_MAP_SHIFT;
  320. height--;
  321. } while (height > 0);
  322. return (void **)slot;
  323. }
  324. EXPORT_SYMBOL(radix_tree_lookup_slot);
  325. /**
  326. * radix_tree_lookup - perform lookup operation on a radix tree
  327. * @root: radix tree root
  328. * @index: index key
  329. *
  330. * Lookup the item at the position @index in the radix tree @root.
  331. *
  332. * This function can be called under rcu_read_lock, however the caller
  333. * must manage lifetimes of leaf nodes (eg. RCU may also be used to free
  334. * them safely). No RCU barriers are required to access or modify the
  335. * returned item, however.
  336. */
  337. void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
  338. {
  339. unsigned int height, shift;
  340. struct radix_tree_node *node, **slot;
  341. node = rcu_dereference(root->rnode);
  342. if (node == NULL)
  343. return NULL;
  344. if (radix_tree_is_direct_ptr(node)) {
  345. if (index > 0)
  346. return NULL;
  347. return radix_tree_direct_to_ptr(node);
  348. }
  349. height = node->height;
  350. if (index > radix_tree_maxindex(height))
  351. return NULL;
  352. shift = (height-1) * RADIX_TREE_MAP_SHIFT;
  353. do {
  354. slot = (struct radix_tree_node **)
  355. (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
  356. node = rcu_dereference(*slot);
  357. if (node == NULL)
  358. return NULL;
  359. shift -= RADIX_TREE_MAP_SHIFT;
  360. height--;
  361. } while (height > 0);
  362. return node;
  363. }
  364. EXPORT_SYMBOL(radix_tree_lookup);
  365. /**
  366. * radix_tree_tag_set - set a tag on a radix tree node
  367. * @root: radix tree root
  368. * @index: index key
  369. * @tag: tag index
  370. *
  371. * Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
  372. * corresponding to @index in the radix tree. From
  373. * the root all the way down to the leaf node.
  374. *
  375. * Returns the address of the tagged item. Setting a tag on a not-present
  376. * item is a bug.
  377. */
  378. void *radix_tree_tag_set(struct radix_tree_root *root,
  379. unsigned long index, unsigned int tag)
  380. {
  381. unsigned int height, shift;
  382. struct radix_tree_node *slot;
  383. height = root->height;
  384. BUG_ON(index > radix_tree_maxindex(height));
  385. slot = root->rnode;
  386. shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
  387. while (height > 0) {
  388. int offset;
  389. offset = (index >> shift) & RADIX_TREE_MAP_MASK;
  390. if (!tag_get(slot, tag, offset))
  391. tag_set(slot, tag, offset);
  392. slot = slot->slots[offset];
  393. BUG_ON(slot == NULL);
  394. shift -= RADIX_TREE_MAP_SHIFT;
  395. height--;
  396. }
  397. /* set the root's tag bit */
  398. if (slot && !root_tag_get(root, tag))
  399. root_tag_set(root, tag);
  400. return slot;
  401. }
  402. EXPORT_SYMBOL(radix_tree_tag_set);
  403. /**
  404. * radix_tree_tag_clear - clear a tag on a radix tree node
  405. * @root: radix tree root
  406. * @index: index key
  407. * @tag: tag index
  408. *
  409. * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
  410. * corresponding to @index in the radix tree. If
  411. * this causes the leaf node to have no tags set then clear the tag in the
  412. * next-to-leaf node, etc.
  413. *
  414. * Returns the address of the tagged item on success, else NULL. ie:
  415. * has the same return value and semantics as radix_tree_lookup().
  416. */
  417. void *radix_tree_tag_clear(struct radix_tree_root *root,
  418. unsigned long index, unsigned int tag)
  419. {
  420. struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
  421. struct radix_tree_node *slot = NULL;
  422. unsigned int height, shift;
  423. height = root->height;
  424. if (index > radix_tree_maxindex(height))
  425. goto out;
  426. shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
  427. pathp->node = NULL;
  428. slot = root->rnode;
  429. while (height > 0) {
  430. int offset;
  431. if (slot == NULL)
  432. goto out;
  433. offset = (index >> shift) & RADIX_TREE_MAP_MASK;
  434. pathp[1].offset = offset;
  435. pathp[1].node = slot;
  436. slot = slot->slots[offset];
  437. pathp++;
  438. shift -= RADIX_TREE_MAP_SHIFT;
  439. height--;
  440. }
  441. if (slot == NULL)
  442. goto out;
  443. while (pathp->node) {
  444. if (!tag_get(pathp->node, tag, pathp->offset))
  445. goto out;
  446. tag_clear(pathp->node, tag, pathp->offset);
  447. if (any_tag_set(pathp->node, tag))
  448. goto out;
  449. pathp--;
  450. }
  451. /* clear the root's tag bit */
  452. if (root_tag_get(root, tag))
  453. root_tag_clear(root, tag);
  454. out:
  455. return slot;
  456. }
  457. EXPORT_SYMBOL(radix_tree_tag_clear);
  458. #ifndef __KERNEL__ /* Only the test harness uses this at present */
  459. /**
  460. * radix_tree_tag_get - get a tag on a radix tree node
  461. * @root: radix tree root
  462. * @index: index key
  463. * @tag: tag index (< RADIX_TREE_MAX_TAGS)
  464. *
  465. * Return values:
  466. *
  467. * 0: tag not present or not set
  468. * 1: tag set
  469. */
  470. int radix_tree_tag_get(struct radix_tree_root *root,
  471. unsigned long index, unsigned int tag)
  472. {
  473. unsigned int height, shift;
  474. struct radix_tree_node *node;
  475. int saw_unset_tag = 0;
  476. /* check the root's tag bit */
  477. if (!root_tag_get(root, tag))
  478. return 0;
  479. node = rcu_dereference(root->rnode);
  480. if (node == NULL)
  481. return 0;
  482. if (radix_tree_is_direct_ptr(node))
  483. return (index == 0);
  484. height = node->height;
  485. if (index > radix_tree_maxindex(height))
  486. return 0;
  487. shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
  488. for ( ; ; ) {
  489. int offset;
  490. if (node == NULL)
  491. return 0;
  492. offset = (index >> shift) & RADIX_TREE_MAP_MASK;
  493. /*
  494. * This is just a debug check. Later, we can bale as soon as
  495. * we see an unset tag.
  496. */
  497. if (!tag_get(node, tag, offset))
  498. saw_unset_tag = 1;
  499. if (height == 1) {
  500. int ret = tag_get(node, tag, offset);
  501. BUG_ON(ret && saw_unset_tag);
  502. return !!ret;
  503. }
  504. node = rcu_dereference(node->slots[offset]);
  505. shift -= RADIX_TREE_MAP_SHIFT;
  506. height--;
  507. }
  508. }
  509. EXPORT_SYMBOL(radix_tree_tag_get);
  510. #endif
  511. static unsigned int
  512. __lookup(struct radix_tree_node *slot, void **results, unsigned long index,
  513. unsigned int max_items, unsigned long *next_index)
  514. {
  515. unsigned int nr_found = 0;
  516. unsigned int shift, height;
  517. unsigned long i;
  518. height = slot->height;
  519. if (height == 0)
  520. goto out;
  521. shift = (height-1) * RADIX_TREE_MAP_SHIFT;
  522. for ( ; height > 1; height--) {
  523. i = (index >> shift) & RADIX_TREE_MAP_MASK;
  524. for (;;) {
  525. if (slot->slots[i] != NULL)
  526. break;
  527. index &= ~((1UL << shift) - 1);
  528. index += 1UL << shift;
  529. if (index == 0)
  530. goto out; /* 32-bit wraparound */
  531. i++;
  532. if (i == RADIX_TREE_MAP_SIZE)
  533. goto out;
  534. }
  535. shift -= RADIX_TREE_MAP_SHIFT;
  536. slot = rcu_dereference(slot->slots[i]);
  537. if (slot == NULL)
  538. goto out;
  539. }
  540. /* Bottom level: grab some items */
  541. for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
  542. struct radix_tree_node *node;
  543. index++;
  544. node = slot->slots[i];
  545. if (node) {
  546. results[nr_found++] = rcu_dereference(node);
  547. if (nr_found == max_items)
  548. goto out;
  549. }
  550. }
  551. out:
  552. *next_index = index;
  553. return nr_found;
  554. }
  555. /**
  556. * radix_tree_gang_lookup - perform multiple lookup on a radix tree
  557. * @root: radix tree root
  558. * @results: where the results of the lookup are placed
  559. * @first_index: start the lookup from this key
  560. * @max_items: place up to this many items at *results
  561. *
  562. * Performs an index-ascending scan of the tree for present items. Places
  563. * them at *@results and returns the number of items which were placed at
  564. * *@results.
  565. *
  566. * The implementation is naive.
  567. *
  568. * Like radix_tree_lookup, radix_tree_gang_lookup may be called under
  569. * rcu_read_lock. In this case, rather than the returned results being
  570. * an atomic snapshot of the tree at a single point in time, the semantics
  571. * of an RCU protected gang lookup are as though multiple radix_tree_lookups
  572. * have been issued in individual locks, and results stored in 'results'.
  573. */
  574. unsigned int
  575. radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
  576. unsigned long first_index, unsigned int max_items)
  577. {
  578. unsigned long max_index;
  579. struct radix_tree_node *node;
  580. unsigned long cur_index = first_index;
  581. unsigned int ret;
  582. node = rcu_dereference(root->rnode);
  583. if (!node)
  584. return 0;
  585. if (radix_tree_is_direct_ptr(node)) {
  586. if (first_index > 0)
  587. return 0;
  588. node = radix_tree_direct_to_ptr(node);
  589. results[0] = rcu_dereference(node);
  590. return 1;
  591. }
  592. max_index = radix_tree_maxindex(node->height);
  593. ret = 0;
  594. while (ret < max_items) {
  595. unsigned int nr_found;
  596. unsigned long next_index; /* Index of next search */
  597. if (cur_index > max_index)
  598. break;
  599. nr_found = __lookup(node, results + ret, cur_index,
  600. max_items - ret, &next_index);
  601. ret += nr_found;
  602. if (next_index == 0)
  603. break;
  604. cur_index = next_index;
  605. }
  606. return ret;
  607. }
  608. EXPORT_SYMBOL(radix_tree_gang_lookup);
  609. /*
  610. * FIXME: the two tag_get()s here should use find_next_bit() instead of
  611. * open-coding the search.
  612. */
  613. static unsigned int
  614. __lookup_tag(struct radix_tree_node *slot, void **results, unsigned long index,
  615. unsigned int max_items, unsigned long *next_index, unsigned int tag)
  616. {
  617. unsigned int nr_found = 0;
  618. unsigned int shift, height;
  619. height = slot->height;
  620. if (height == 0)
  621. goto out;
  622. shift = (height-1) * RADIX_TREE_MAP_SHIFT;
  623. while (height > 0) {
  624. unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK ;
  625. for (;;) {
  626. if (tag_get(slot, tag, i))
  627. break;
  628. index &= ~((1UL << shift) - 1);
  629. index += 1UL << shift;
  630. if (index == 0)
  631. goto out; /* 32-bit wraparound */
  632. i++;
  633. if (i == RADIX_TREE_MAP_SIZE)
  634. goto out;
  635. }
  636. height--;
  637. if (height == 0) { /* Bottom level: grab some items */
  638. unsigned long j = index & RADIX_TREE_MAP_MASK;
  639. for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
  640. struct radix_tree_node *node;
  641. index++;
  642. if (!tag_get(slot, tag, j))
  643. continue;
  644. node = slot->slots[j];
  645. /*
  646. * Even though the tag was found set, we need to
  647. * recheck that we have a non-NULL node, because
  648. * if this lookup is lockless, it may have been
  649. * subsequently deleted.
  650. *
  651. * Similar care must be taken in any place that
  652. * lookup ->slots[x] without a lock (ie. can't
  653. * rely on its value remaining the same).
  654. */
  655. if (node) {
  656. node = rcu_dereference(node);
  657. results[nr_found++] = node;
  658. if (nr_found == max_items)
  659. goto out;
  660. }
  661. }
  662. }
  663. shift -= RADIX_TREE_MAP_SHIFT;
  664. slot = rcu_dereference(slot->slots[i]);
  665. if (slot == NULL)
  666. break;
  667. }
  668. out:
  669. *next_index = index;
  670. return nr_found;
  671. }
  672. /**
  673. * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
  674. * based on a tag
  675. * @root: radix tree root
  676. * @results: where the results of the lookup are placed
  677. * @first_index: start the lookup from this key
  678. * @max_items: place up to this many items at *results
  679. * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
  680. *
  681. * Performs an index-ascending scan of the tree for present items which
  682. * have the tag indexed by @tag set. Places the items at *@results and
  683. * returns the number of items which were placed at *@results.
  684. */
  685. unsigned int
  686. radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
  687. unsigned long first_index, unsigned int max_items,
  688. unsigned int tag)
  689. {
  690. struct radix_tree_node *node;
  691. unsigned long max_index;
  692. unsigned long cur_index = first_index;
  693. unsigned int ret;
  694. /* check the root's tag bit */
  695. if (!root_tag_get(root, tag))
  696. return 0;
  697. node = rcu_dereference(root->rnode);
  698. if (!node)
  699. return 0;
  700. if (radix_tree_is_direct_ptr(node)) {
  701. if (first_index > 0)
  702. return 0;
  703. node = radix_tree_direct_to_ptr(node);
  704. results[0] = rcu_dereference(node);
  705. return 1;
  706. }
  707. max_index = radix_tree_maxindex(node->height);
  708. ret = 0;
  709. while (ret < max_items) {
  710. unsigned int nr_found;
  711. unsigned long next_index; /* Index of next search */
  712. if (cur_index > max_index)
  713. break;
  714. nr_found = __lookup_tag(node, results + ret, cur_index,
  715. max_items - ret, &next_index, tag);
  716. ret += nr_found;
  717. if (next_index == 0)
  718. break;
  719. cur_index = next_index;
  720. }
  721. return ret;
  722. }
  723. EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
  724. /**
  725. * radix_tree_shrink - shrink height of a radix tree to minimal
  726. * @root radix tree root
  727. */
  728. static inline void radix_tree_shrink(struct radix_tree_root *root)
  729. {
  730. /* try to shrink tree height */
  731. while (root->height > 0 &&
  732. root->rnode->count == 1 &&
  733. root->rnode->slots[0]) {
  734. struct radix_tree_node *to_free = root->rnode;
  735. void *newptr;
  736. /*
  737. * We don't need rcu_assign_pointer(), since we are simply
  738. * moving the node from one part of the tree to another. If
  739. * it was safe to dereference the old pointer to it
  740. * (to_free->slots[0]), it will be safe to dereference the new
  741. * one (root->rnode).
  742. */
  743. newptr = to_free->slots[0];
  744. if (root->height == 1)
  745. newptr = radix_tree_ptr_to_direct(newptr);
  746. root->rnode = newptr;
  747. root->height--;
  748. /* must only free zeroed nodes into the slab */
  749. tag_clear(to_free, 0, 0);
  750. tag_clear(to_free, 1, 0);
  751. to_free->slots[0] = NULL;
  752. to_free->count = 0;
  753. radix_tree_node_free(to_free);
  754. }
  755. }
  756. /**
  757. * radix_tree_delete - delete an item from a radix tree
  758. * @root: radix tree root
  759. * @index: index key
  760. *
  761. * Remove the item at @index from the radix tree rooted at @root.
  762. *
  763. * Returns the address of the deleted item, or NULL if it was not present.
  764. */
  765. void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
  766. {
  767. struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
  768. struct radix_tree_node *slot = NULL;
  769. struct radix_tree_node *to_free;
  770. unsigned int height, shift;
  771. int tag;
  772. int offset;
  773. height = root->height;
  774. if (index > radix_tree_maxindex(height))
  775. goto out;
  776. slot = root->rnode;
  777. if (height == 0 && root->rnode) {
  778. slot = radix_tree_direct_to_ptr(slot);
  779. root_tag_clear_all(root);
  780. root->rnode = NULL;
  781. goto out;
  782. }
  783. shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
  784. pathp->node = NULL;
  785. do {
  786. if (slot == NULL)
  787. goto out;
  788. pathp++;
  789. offset = (index >> shift) & RADIX_TREE_MAP_MASK;
  790. pathp->offset = offset;
  791. pathp->node = slot;
  792. slot = slot->slots[offset];
  793. shift -= RADIX_TREE_MAP_SHIFT;
  794. height--;
  795. } while (height > 0);
  796. if (slot == NULL)
  797. goto out;
  798. /*
  799. * Clear all tags associated with the just-deleted item
  800. */
  801. for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
  802. if (tag_get(pathp->node, tag, pathp->offset))
  803. radix_tree_tag_clear(root, index, tag);
  804. }
  805. to_free = NULL;
  806. /* Now free the nodes we do not need anymore */
  807. while (pathp->node) {
  808. pathp->node->slots[pathp->offset] = NULL;
  809. pathp->node->count--;
  810. /*
  811. * Queue the node for deferred freeing after the
  812. * last reference to it disappears (set NULL, above).
  813. */
  814. if (to_free)
  815. radix_tree_node_free(to_free);
  816. if (pathp->node->count) {
  817. if (pathp->node == root->rnode)
  818. radix_tree_shrink(root);
  819. goto out;
  820. }
  821. /* Node with zero slots in use so free it */
  822. to_free = pathp->node;
  823. pathp--;
  824. }
  825. root_tag_clear_all(root);
  826. root->height = 0;
  827. root->rnode = NULL;
  828. if (to_free)
  829. radix_tree_node_free(to_free);
  830. out:
  831. return slot;
  832. }
  833. EXPORT_SYMBOL(radix_tree_delete);
  834. /**
  835. * radix_tree_tagged - test whether any items in the tree are tagged
  836. * @root: radix tree root
  837. * @tag: tag to test
  838. */
  839. int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
  840. {
  841. return root_tag_get(root, tag);
  842. }
  843. EXPORT_SYMBOL(radix_tree_tagged);
  844. static void
  845. radix_tree_node_ctor(void *node, struct kmem_cache *cachep, unsigned long flags)
  846. {
  847. memset(node, 0, sizeof(struct radix_tree_node));
  848. }
  849. static __init unsigned long __maxindex(unsigned int height)
  850. {
  851. unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
  852. unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
  853. if (tmp >= RADIX_TREE_INDEX_BITS)
  854. index = ~0UL;
  855. return index;
  856. }
  857. static __init void radix_tree_init_maxindex(void)
  858. {
  859. unsigned int i;
  860. for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
  861. height_to_maxindex[i] = __maxindex(i);
  862. }
  863. static int radix_tree_callback(struct notifier_block *nfb,
  864. unsigned long action,
  865. void *hcpu)
  866. {
  867. int cpu = (long)hcpu;
  868. struct radix_tree_preload *rtp;
  869. /* Free per-cpu pool of perloaded nodes */
  870. if (action == CPU_DEAD) {
  871. rtp = &per_cpu(radix_tree_preloads, cpu);
  872. while (rtp->nr) {
  873. kmem_cache_free(radix_tree_node_cachep,
  874. rtp->nodes[rtp->nr-1]);
  875. rtp->nodes[rtp->nr-1] = NULL;
  876. rtp->nr--;
  877. }
  878. }
  879. return NOTIFY_OK;
  880. }
  881. void __init radix_tree_init(void)
  882. {
  883. radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
  884. sizeof(struct radix_tree_node), 0,
  885. SLAB_PANIC, radix_tree_node_ctor, NULL);
  886. radix_tree_init_maxindex();
  887. hotcpu_notifier(radix_tree_callback, 0);
  888. }