1 | #ifndef _LINUX_GENERIC_RADIX_TREE_H |
---|---|

2 | #define _LINUX_GENERIC_RADIX_TREE_H |

3 | |

4 | /** |

5 | * DOC: Generic radix trees/sparse arrays: |

6 | * |

7 | * Very simple and minimalistic, supporting arbitrary size entries up to |

8 | * PAGE_SIZE. |

9 | * |

10 | * A genradix is defined with the type it will store, like so: |

11 | * |

12 | * static GENRADIX(struct foo) foo_genradix; |

13 | * |

14 | * The main operations are: |

15 | * |

16 | * - genradix_init(radix) - initialize an empty genradix |

17 | * |

18 | * - genradix_free(radix) - free all memory owned by the genradix and |

19 | * reinitialize it |

20 | * |

21 | * - genradix_ptr(radix, idx) - gets a pointer to the entry at idx, returning |

22 | * NULL if that entry does not exist |

23 | * |

24 | * - genradix_ptr_alloc(radix, idx, gfp) - gets a pointer to an entry, |

25 | * allocating it if necessary |

26 | * |

27 | * - genradix_for_each(radix, iter, p) - iterate over each entry in a genradix |

28 | * |

29 | * The radix tree allocates one page of entries at a time, so entries may exist |

30 | * that were never explicitly allocated - they will be initialized to all |

31 | * zeroes. |

32 | * |

33 | * Internally, a genradix is just a radix tree of pages, and indexing works in |

34 | * terms of byte offsets. The wrappers in this header file use sizeof on the |

35 | * type the radix contains to calculate a byte offset from the index - see |

36 | * __idx_to_offset. |

37 | */ |

38 | |

39 | #include <asm/page.h> |

40 | #include <linux/bug.h> |

41 | #include <linux/kernel.h> |

42 | #include <linux/log2.h> |

43 | |

44 | struct genradix_root; |

45 | |

46 | struct __genradix { |

47 | struct genradix_root __rcu *root; |

48 | }; |

49 | |

50 | /* |

51 | * NOTE: currently, sizeof(_type) must not be larger than PAGE_SIZE: |

52 | */ |

53 | |

54 | #define __GENRADIX_INITIALIZER \ |

55 | { \ |

56 | .tree = { \ |

57 | .root = NULL, \ |

58 | } \ |

59 | } |

60 | |

61 | /* |

62 | * We use a 0 size array to stash the type we're storing without taking any |

63 | * space at runtime - then the various accessor macros can use typeof() to get |

64 | * to it for casts/sizeof - we also force the alignment so that storing a type |

65 | * with a ridiculous alignment doesn't blow up the alignment or size of the |

66 | * genradix. |

67 | */ |

68 | |

69 | #define GENRADIX(_type) \ |

70 | struct { \ |

71 | struct __genradix tree; \ |

72 | _type type[0] __aligned(1); \ |

73 | } |

74 | |

75 | #define DEFINE_GENRADIX(_name, _type) \ |

76 | GENRADIX(_type) _name = __GENRADIX_INITIALIZER |

77 | |

78 | /** |

79 | * genradix_init - initialize a genradix |

80 | * @_radix: genradix to initialize |

81 | * |

82 | * Does not fail |

83 | */ |

84 | #define genradix_init(_radix) \ |

85 | do { \ |

86 | *(_radix) = (typeof(*_radix)) __GENRADIX_INITIALIZER; \ |

87 | } while (0) |

88 | |

89 | void __genradix_free(struct __genradix *); |

90 | |

91 | /** |

92 | * genradix_free: free all memory owned by a genradix |

93 | * @_radix: the genradix to free |

94 | * |

95 | * After freeing, @_radix will be reinitialized and empty |

96 | */ |

97 | #define genradix_free(_radix) __genradix_free(&(_radix)->tree) |

98 | |

99 | static inline size_t __idx_to_offset(size_t idx, size_t obj_size) |

100 | { |

101 | if (__builtin_constant_p(obj_size)) |

102 | BUILD_BUG_ON(obj_size > PAGE_SIZE); |

103 | else |

104 | BUG_ON(obj_size > PAGE_SIZE); |

105 | |

106 | if (!is_power_of_2(obj_size)) { |

107 | size_t objs_per_page = PAGE_SIZE / obj_size; |

108 | |

109 | return (idx / objs_per_page) * PAGE_SIZE + |

110 | (idx % objs_per_page) * obj_size; |

111 | } else { |

112 | return idx * obj_size; |

113 | } |

114 | } |

115 | |

116 | #define __genradix_cast(_radix) (typeof((_radix)->type[0]) *) |

117 | #define __genradix_obj_size(_radix) sizeof((_radix)->type[0]) |

118 | #define __genradix_idx_to_offset(_radix, _idx) \ |

119 | __idx_to_offset(_idx, __genradix_obj_size(_radix)) |

120 | |

121 | void *__genradix_ptr(struct __genradix *, size_t); |

122 | |

123 | /** |

124 | * genradix_ptr - get a pointer to a genradix entry |

125 | * @_radix: genradix to access |

126 | * @_idx: index to fetch |

127 | * |

128 | * Returns a pointer to entry at @_idx, or NULL if that entry does not exist. |

129 | */ |

130 | #define genradix_ptr(_radix, _idx) \ |

131 | (__genradix_cast(_radix) \ |

132 | __genradix_ptr(&(_radix)->tree, \ |

133 | __genradix_idx_to_offset(_radix, _idx))) |

134 | |

135 | void *__genradix_ptr_alloc(struct __genradix *, size_t, gfp_t); |

136 | |

137 | /** |

138 | * genradix_ptr_alloc - get a pointer to a genradix entry, allocating it |

139 | * if necessary |

140 | * @_radix: genradix to access |

141 | * @_idx: index to fetch |

142 | * @_gfp: gfp mask |

143 | * |

144 | * Returns a pointer to entry at @_idx, or NULL on allocation failure |

145 | */ |

146 | #define genradix_ptr_alloc(_radix, _idx, _gfp) \ |

147 | (__genradix_cast(_radix) \ |

148 | __genradix_ptr_alloc(&(_radix)->tree, \ |

149 | __genradix_idx_to_offset(_radix, _idx), \ |

150 | _gfp)) |

151 | |

152 | struct genradix_iter { |

153 | size_t offset; |

154 | size_t pos; |

155 | }; |

156 | |

157 | /** |

158 | * genradix_iter_init - initialize a genradix_iter |

159 | * @_radix: genradix that will be iterated over |

160 | * @_idx: index to start iterating from |

161 | */ |

162 | #define genradix_iter_init(_radix, _idx) \ |

163 | ((struct genradix_iter) { \ |

164 | .pos = (_idx), \ |

165 | .offset = __genradix_idx_to_offset((_radix), (_idx)),\ |

166 | }) |

167 | |

168 | void *__genradix_iter_peek(struct genradix_iter *, struct __genradix *, size_t); |

169 | |

170 | /** |

171 | * genradix_iter_peek - get first entry at or above iterator's current |

172 | * position |

173 | * @_iter: a genradix_iter |

174 | * @_radix: genradix being iterated over |

175 | * |

176 | * If no more entries exist at or above @_iter's current position, returns NULL |

177 | */ |

178 | #define genradix_iter_peek(_iter, _radix) \ |

179 | (__genradix_cast(_radix) \ |

180 | __genradix_iter_peek(_iter, &(_radix)->tree, \ |

181 | PAGE_SIZE / __genradix_obj_size(_radix))) |

182 | |

183 | static inline void __genradix_iter_advance(struct genradix_iter *iter, |

184 | size_t obj_size) |

185 | { |

186 | iter->offset += obj_size; |

187 | |

188 | if (!is_power_of_2(obj_size) && |

189 | (iter->offset & (PAGE_SIZE - 1)) + obj_size > PAGE_SIZE) |

190 | iter->offset = round_up(iter->offset, PAGE_SIZE); |

191 | |

192 | iter->pos++; |

193 | } |

194 | |

195 | #define genradix_iter_advance(_iter, _radix) \ |

196 | __genradix_iter_advance(_iter, __genradix_obj_size(_radix)) |

197 | |

198 | #define genradix_for_each_from(_radix, _iter, _p, _start) \ |

199 | for (_iter = genradix_iter_init(_radix, _start); \ |

200 | (_p = genradix_iter_peek(&_iter, _radix)) != NULL; \ |

201 | genradix_iter_advance(&_iter, _radix)) |

202 | |

203 | /** |

204 | * genradix_for_each - iterate over entry in a genradix |

205 | * @_radix: genradix to iterate over |

206 | * @_iter: a genradix_iter to track current position |

207 | * @_p: pointer to genradix entry type |

208 | * |

209 | * On every iteration, @_p will point to the current entry, and @_iter.pos |

210 | * will be the current entry's index. |

211 | */ |

212 | #define genradix_for_each(_radix, _iter, _p) \ |

213 | genradix_for_each_from(_radix, _iter, _p, 0) |

214 | |

215 | int __genradix_prealloc(struct __genradix *, size_t, gfp_t); |

216 | |

217 | /** |

218 | * genradix_prealloc - preallocate entries in a generic radix tree |

219 | * @_radix: genradix to preallocate |

220 | * @_nr: number of entries to preallocate |

221 | * @_gfp: gfp mask |

222 | * |

223 | * Returns 0 on success, -ENOMEM on failure |

224 | */ |

225 | #define genradix_prealloc(_radix, _nr, _gfp) \ |

226 | __genradix_prealloc(&(_radix)->tree, \ |

227 | __genradix_idx_to_offset(_radix, _nr + 1),\ |

228 | _gfp) |

229 | |

230 | |

231 | #endif /* _LINUX_GENERIC_RADIX_TREE_H */ |

232 |