generic-radix-tree.h 6.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231
  1. #ifndef _LINUX_GENERIC_RADIX_TREE_H
  2. #define _LINUX_GENERIC_RADIX_TREE_H
  3. /**
  4. * DOC: Generic radix trees/sparse arrays
  5. *
  6. * Very simple and minimalistic, supporting arbitrary size entries up to
  7. * PAGE_SIZE.
  8. *
  9. * A genradix is defined with the type it will store, like so:
  10. *
  11. * static GENRADIX(struct foo) foo_genradix;
  12. *
  13. * The main operations are:
  14. *
  15. * - genradix_init(radix) - initialize an empty genradix
  16. *
  17. * - genradix_free(radix) - free all memory owned by the genradix and
  18. * reinitialize it
  19. *
  20. * - genradix_ptr(radix, idx) - gets a pointer to the entry at idx, returning
  21. * NULL if that entry does not exist
  22. *
  23. * - genradix_ptr_alloc(radix, idx, gfp) - gets a pointer to an entry,
  24. * allocating it if necessary
  25. *
  26. * - genradix_for_each(radix, iter, p) - iterate over each entry in a genradix
  27. *
  28. * The radix tree allocates one page of entries at a time, so entries may exist
  29. * that were never explicitly allocated - they will be initialized to all
  30. * zeroes.
  31. *
  32. * Internally, a genradix is just a radix tree of pages, and indexing works in
  33. * terms of byte offsets. The wrappers in this header file use sizeof on the
  34. * type the radix contains to calculate a byte offset from the index - see
  35. * __idx_to_offset.
  36. */
  37. #include <asm/page.h>
  38. #include <linux/bug.h>
  39. #include <linux/kernel.h>
  40. #include <linux/log2.h>
  41. struct genradix_root;
  42. struct __genradix {
  43. struct genradix_root *root;
  44. };
  45. /*
  46. * NOTE: currently, sizeof(_type) must not be larger than PAGE_SIZE:
  47. */
  48. #define __GENRADIX_INITIALIZER \
  49. { \
  50. .tree = { \
  51. .root = NULL, \
  52. } \
  53. }
  54. /*
  55. * We use a 0 size array to stash the type we're storing without taking any
  56. * space at runtime - then the various accessor macros can use typeof() to get
  57. * to it for casts/sizeof - we also force the alignment so that storing a type
  58. * with a ridiculous alignment doesn't blow up the alignment or size of the
  59. * genradix.
  60. */
  61. #define GENRADIX(_type) \
  62. struct { \
  63. struct __genradix tree; \
  64. _type type[0] __aligned(1); \
  65. }
  66. #define DEFINE_GENRADIX(_name, _type) \
  67. GENRADIX(_type) _name = __GENRADIX_INITIALIZER
  68. /**
  69. * genradix_init - initialize a genradix
  70. * @_radix: genradix to initialize
  71. *
  72. * Does not fail
  73. */
  74. #define genradix_init(_radix) \
  75. do { \
  76. *(_radix) = (typeof(*_radix)) __GENRADIX_INITIALIZER; \
  77. } while (0)
  78. void __genradix_free(struct __genradix *);
  79. /**
  80. * genradix_free: free all memory owned by a genradix
  81. * @_radix: the genradix to free
  82. *
  83. * After freeing, @_radix will be reinitialized and empty
  84. */
  85. #define genradix_free(_radix) __genradix_free(&(_radix)->tree)
  86. static inline size_t __idx_to_offset(size_t idx, size_t obj_size)
  87. {
  88. if (__builtin_constant_p(obj_size))
  89. BUILD_BUG_ON(obj_size > PAGE_SIZE);
  90. else
  91. BUG_ON(obj_size > PAGE_SIZE);
  92. if (!is_power_of_2(obj_size)) {
  93. size_t objs_per_page = PAGE_SIZE / obj_size;
  94. return (idx / objs_per_page) * PAGE_SIZE +
  95. (idx % objs_per_page) * obj_size;
  96. } else {
  97. return idx * obj_size;
  98. }
  99. }
  100. #define __genradix_cast(_radix) (typeof((_radix)->type[0]) *)
  101. #define __genradix_obj_size(_radix) sizeof((_radix)->type[0])
  102. #define __genradix_idx_to_offset(_radix, _idx) \
  103. __idx_to_offset(_idx, __genradix_obj_size(_radix))
  104. void *__genradix_ptr(struct __genradix *, size_t);
  105. /**
  106. * genradix_ptr - get a pointer to a genradix entry
  107. * @_radix: genradix to access
  108. * @_idx: index to fetch
  109. *
  110. * Returns a pointer to entry at @_idx, or NULL if that entry does not exist.
  111. */
  112. #define genradix_ptr(_radix, _idx) \
  113. (__genradix_cast(_radix) \
  114. __genradix_ptr(&(_radix)->tree, \
  115. __genradix_idx_to_offset(_radix, _idx)))
  116. void *__genradix_ptr_alloc(struct __genradix *, size_t, gfp_t);
  117. /**
  118. * genradix_ptr_alloc - get a pointer to a genradix entry, allocating it
  119. * if necessary
  120. * @_radix: genradix to access
  121. * @_idx: index to fetch
  122. * @_gfp: gfp mask
  123. *
  124. * Returns a pointer to entry at @_idx, or NULL on allocation failure
  125. */
  126. #define genradix_ptr_alloc(_radix, _idx, _gfp) \
  127. (__genradix_cast(_radix) \
  128. __genradix_ptr_alloc(&(_radix)->tree, \
  129. __genradix_idx_to_offset(_radix, _idx), \
  130. _gfp))
  131. struct genradix_iter {
  132. size_t offset;
  133. size_t pos;
  134. };
  135. /**
  136. * genradix_iter_init - initialize a genradix_iter
  137. * @_radix: genradix that will be iterated over
  138. * @_idx: index to start iterating from
  139. */
  140. #define genradix_iter_init(_radix, _idx) \
  141. ((struct genradix_iter) { \
  142. .pos = (_idx), \
  143. .offset = __genradix_idx_to_offset((_radix), (_idx)),\
  144. })
  145. void *__genradix_iter_peek(struct genradix_iter *, struct __genradix *, size_t);
  146. /**
  147. * genradix_iter_peek - get first entry at or above iterator's current
  148. * position
  149. * @_iter: a genradix_iter
  150. * @_radix: genradix being iterated over
  151. *
  152. * If no more entries exist at or above @_iter's current position, returns NULL
  153. */
  154. #define genradix_iter_peek(_iter, _radix) \
  155. (__genradix_cast(_radix) \
  156. __genradix_iter_peek(_iter, &(_radix)->tree, \
  157. PAGE_SIZE / __genradix_obj_size(_radix)))
  158. static inline void __genradix_iter_advance(struct genradix_iter *iter,
  159. size_t obj_size)
  160. {
  161. iter->offset += obj_size;
  162. if (!is_power_of_2(obj_size) &&
  163. (iter->offset & (PAGE_SIZE - 1)) + obj_size > PAGE_SIZE)
  164. iter->offset = round_up(iter->offset, PAGE_SIZE);
  165. iter->pos++;
  166. }
  167. #define genradix_iter_advance(_iter, _radix) \
  168. __genradix_iter_advance(_iter, __genradix_obj_size(_radix))
  169. #define genradix_for_each_from(_radix, _iter, _p, _start) \
  170. for (_iter = genradix_iter_init(_radix, _start); \
  171. (_p = genradix_iter_peek(&_iter, _radix)) != NULL; \
  172. genradix_iter_advance(&_iter, _radix))
  173. /**
  174. * genradix_for_each - iterate over entry in a genradix
  175. * @_radix: genradix to iterate over
  176. * @_iter: a genradix_iter to track current position
  177. * @_p: pointer to genradix entry type
  178. *
  179. * On every iteration, @_p will point to the current entry, and @_iter.pos
  180. * will be the current entry's index.
  181. */
  182. #define genradix_for_each(_radix, _iter, _p) \
  183. genradix_for_each_from(_radix, _iter, _p, 0)
  184. int __genradix_prealloc(struct __genradix *, size_t, gfp_t);
  185. /**
  186. * genradix_prealloc - preallocate entries in a generic radix tree
  187. * @_radix: genradix to preallocate
  188. * @_nr: number of entries to preallocate
  189. * @_gfp: gfp mask
  190. *
  191. * Returns 0 on success, -ENOMEM on failure
  192. */
  193. #define genradix_prealloc(_radix, _nr, _gfp) \
  194. __genradix_prealloc(&(_radix)->tree, \
  195. __genradix_idx_to_offset(_radix, _nr + 1),\
  196. _gfp)
  197. #endif /* _LINUX_GENERIC_RADIX_TREE_H */