generic-radix-tree.c 5.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237
  1. #include <linux/export.h>
  2. #include <linux/generic-radix-tree.h>
  3. #include <linux/gfp.h>
  4. #include <linux/kmemleak.h>
  5. #define GENRADIX_ARY (PAGE_SIZE / sizeof(struct genradix_node *))
  6. #define GENRADIX_ARY_SHIFT ilog2(GENRADIX_ARY)
  7. struct genradix_node {
  8. union {
  9. /* Interior node: */
  10. struct genradix_node *children[GENRADIX_ARY];
  11. /* Leaf: */
  12. u8 data[PAGE_SIZE];
  13. };
  14. };
  15. static inline int genradix_depth_shift(unsigned depth)
  16. {
  17. return PAGE_SHIFT + GENRADIX_ARY_SHIFT * depth;
  18. }
  19. /*
  20. * Returns size (of data, in bytes) that a tree of a given depth holds:
  21. */
  22. static inline size_t genradix_depth_size(unsigned depth)
  23. {
  24. return 1UL << genradix_depth_shift(depth);
  25. }
  26. /* depth that's needed for a genradix that can address up to ULONG_MAX: */
  27. #define GENRADIX_MAX_DEPTH \
  28. DIV_ROUND_UP(BITS_PER_LONG - PAGE_SHIFT, GENRADIX_ARY_SHIFT)
  29. #define GENRADIX_DEPTH_MASK \
  30. ((unsigned long) (roundup_pow_of_two(GENRADIX_MAX_DEPTH + 1) - 1))
  31. static inline unsigned genradix_root_to_depth(struct genradix_root *r)
  32. {
  33. return (unsigned long) r & GENRADIX_DEPTH_MASK;
  34. }
  35. static inline struct genradix_node *genradix_root_to_node(struct genradix_root *r)
  36. {
  37. return (void *) ((unsigned long) r & ~GENRADIX_DEPTH_MASK);
  38. }
  39. /*
  40. * Returns pointer to the specified byte @offset within @radix, or NULL if not
  41. * allocated
  42. */
  43. void *__genradix_ptr(struct __genradix *radix, size_t offset)
  44. {
  45. struct genradix_root *r = READ_ONCE(radix->root);
  46. struct genradix_node *n = genradix_root_to_node(r);
  47. unsigned level = genradix_root_to_depth(r);
  48. if (ilog2(offset) >= genradix_depth_shift(level))
  49. return NULL;
  50. while (1) {
  51. if (!n)
  52. return NULL;
  53. if (!level)
  54. break;
  55. level--;
  56. n = n->children[offset >> genradix_depth_shift(level)];
  57. offset &= genradix_depth_size(level) - 1;
  58. }
  59. return &n->data[offset];
  60. }
  61. EXPORT_SYMBOL(__genradix_ptr);
  62. static inline struct genradix_node *genradix_alloc_node(gfp_t gfp_mask)
  63. {
  64. struct genradix_node *node;
  65. node = (struct genradix_node *)__get_free_page(gfp_mask|__GFP_ZERO);
  66. /*
  67. * We're using pages (not slab allocations) directly for kernel data
  68. * structures, so we need to explicitly inform kmemleak of them in order
  69. * to avoid false positive memory leak reports.
  70. */
  71. kmemleak_alloc(node, PAGE_SIZE, 1, gfp_mask);
  72. return node;
  73. }
  74. static inline void genradix_free_node(struct genradix_node *node)
  75. {
  76. kmemleak_free(node);
  77. free_page((unsigned long)node);
  78. }
  79. /*
  80. * Returns pointer to the specified byte @offset within @radix, allocating it if
  81. * necessary - newly allocated slots are always zeroed out:
  82. */
  83. void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset,
  84. gfp_t gfp_mask)
  85. {
  86. struct genradix_root *v = READ_ONCE(radix->root);
  87. struct genradix_node *n, *new_node = NULL;
  88. unsigned level;
  89. /* Increase tree depth if necessary: */
  90. while (1) {
  91. struct genradix_root *r = v, *new_root;
  92. n = genradix_root_to_node(r);
  93. level = genradix_root_to_depth(r);
  94. if (n && ilog2(offset) < genradix_depth_shift(level))
  95. break;
  96. if (!new_node) {
  97. new_node = genradix_alloc_node(gfp_mask);
  98. if (!new_node)
  99. return NULL;
  100. }
  101. new_node->children[0] = n;
  102. new_root = ((struct genradix_root *)
  103. ((unsigned long) new_node | (n ? level + 1 : 0)));
  104. if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) {
  105. v = new_root;
  106. new_node = NULL;
  107. }
  108. }
  109. while (level--) {
  110. struct genradix_node **p =
  111. &n->children[offset >> genradix_depth_shift(level)];
  112. offset &= genradix_depth_size(level) - 1;
  113. n = READ_ONCE(*p);
  114. if (!n) {
  115. if (!new_node) {
  116. new_node = genradix_alloc_node(gfp_mask);
  117. if (!new_node)
  118. return NULL;
  119. }
  120. if (!(n = cmpxchg_release(p, NULL, new_node)))
  121. swap(n, new_node);
  122. }
  123. }
  124. if (new_node)
  125. genradix_free_node(new_node);
  126. return &n->data[offset];
  127. }
  128. EXPORT_SYMBOL(__genradix_ptr_alloc);
  129. void *__genradix_iter_peek(struct genradix_iter *iter,
  130. struct __genradix *radix,
  131. size_t objs_per_page)
  132. {
  133. struct genradix_root *r;
  134. struct genradix_node *n;
  135. unsigned level, i;
  136. restart:
  137. r = READ_ONCE(radix->root);
  138. if (!r)
  139. return NULL;
  140. n = genradix_root_to_node(r);
  141. level = genradix_root_to_depth(r);
  142. if (ilog2(iter->offset) >= genradix_depth_shift(level))
  143. return NULL;
  144. while (level) {
  145. level--;
  146. i = (iter->offset >> genradix_depth_shift(level)) &
  147. (GENRADIX_ARY - 1);
  148. while (!n->children[i]) {
  149. i++;
  150. iter->offset = round_down(iter->offset +
  151. genradix_depth_size(level),
  152. genradix_depth_size(level));
  153. iter->pos = (iter->offset >> PAGE_SHIFT) *
  154. objs_per_page;
  155. if (i == GENRADIX_ARY)
  156. goto restart;
  157. }
  158. n = n->children[i];
  159. }
  160. return &n->data[iter->offset & (PAGE_SIZE - 1)];
  161. }
  162. EXPORT_SYMBOL(__genradix_iter_peek);
  163. static void genradix_free_recurse(struct genradix_node *n, unsigned level)
  164. {
  165. if (level) {
  166. unsigned i;
  167. for (i = 0; i < GENRADIX_ARY; i++)
  168. if (n->children[i])
  169. genradix_free_recurse(n->children[i], level - 1);
  170. }
  171. genradix_free_node(n);
  172. }
  173. int __genradix_prealloc(struct __genradix *radix, size_t size,
  174. gfp_t gfp_mask)
  175. {
  176. size_t offset;
  177. for (offset = 0; offset < size; offset += PAGE_SIZE)
  178. if (!__genradix_ptr_alloc(radix, offset, gfp_mask))
  179. return -ENOMEM;
  180. return 0;
  181. }
  182. EXPORT_SYMBOL(__genradix_prealloc);
  183. void __genradix_free(struct __genradix *radix)
  184. {
  185. struct genradix_root *r = xchg(&radix->root, NULL);
  186. genradix_free_recurse(genradix_root_to_node(r),
  187. genradix_root_to_depth(r));
  188. }
  189. EXPORT_SYMBOL(__genradix_free);