]>
Commit | Line | Data |
---|---|---|
ba20ba2e | 1 | |
73badee4 | 2 | #include <linux/atomic.h> |
ba20ba2e KO |
3 | #include <linux/export.h> |
4 | #include <linux/generic-radix-tree.h> | |
5 | #include <linux/gfp.h> | |
3c52b0af | 6 | #include <linux/kmemleak.h> |
ba20ba2e | 7 | |
3a319a24 | 8 | #define GENRADIX_ARY (GENRADIX_NODE_SIZE / sizeof(struct genradix_node *)) |
ba20ba2e KO |
9 | #define GENRADIX_ARY_SHIFT ilog2(GENRADIX_ARY) |
10 | ||
11 | struct genradix_node { | |
12 | union { | |
13 | /* Interior node: */ | |
14 | struct genradix_node *children[GENRADIX_ARY]; | |
15 | ||
16 | /* Leaf: */ | |
3a319a24 | 17 | u8 data[GENRADIX_NODE_SIZE]; |
ba20ba2e KO |
18 | }; |
19 | }; | |
20 | ||
21 | static inline int genradix_depth_shift(unsigned depth) | |
22 | { | |
3a319a24 | 23 | return GENRADIX_NODE_SHIFT + GENRADIX_ARY_SHIFT * depth; |
ba20ba2e KO |
24 | } |
25 | ||
26 | /* | |
27 | * Returns size (of data, in bytes) that a tree of a given depth holds: | |
28 | */ | |
29 | static inline size_t genradix_depth_size(unsigned depth) | |
30 | { | |
31 | return 1UL << genradix_depth_shift(depth); | |
32 | } | |
33 | ||
34 | /* depth that's needed for a genradix that can address up to ULONG_MAX: */ | |
35 | #define GENRADIX_MAX_DEPTH \ | |
3a319a24 | 36 | DIV_ROUND_UP(BITS_PER_LONG - GENRADIX_NODE_SHIFT, GENRADIX_ARY_SHIFT) |
ba20ba2e KO |
37 | |
38 | #define GENRADIX_DEPTH_MASK \ | |
39 | ((unsigned long) (roundup_pow_of_two(GENRADIX_MAX_DEPTH + 1) - 1)) | |
40 | ||
e3f4faa4 | 41 | static inline unsigned genradix_root_to_depth(struct genradix_root *r) |
ba20ba2e KO |
42 | { |
43 | return (unsigned long) r & GENRADIX_DEPTH_MASK; | |
44 | } | |
45 | ||
e3f4faa4 | 46 | static inline struct genradix_node *genradix_root_to_node(struct genradix_root *r) |
ba20ba2e KO |
47 | { |
48 | return (void *) ((unsigned long) r & ~GENRADIX_DEPTH_MASK); | |
49 | } | |
50 | ||
51 | /* | |
52 | * Returns pointer to the specified byte @offset within @radix, or NULL if not | |
53 | * allocated | |
54 | */ | |
55 | void *__genradix_ptr(struct __genradix *radix, size_t offset) | |
56 | { | |
57 | struct genradix_root *r = READ_ONCE(radix->root); | |
58 | struct genradix_node *n = genradix_root_to_node(r); | |
59 | unsigned level = genradix_root_to_depth(r); | |
60 | ||
61 | if (ilog2(offset) >= genradix_depth_shift(level)) | |
62 | return NULL; | |
63 | ||
64 | while (1) { | |
65 | if (!n) | |
66 | return NULL; | |
67 | if (!level) | |
68 | break; | |
69 | ||
70 | level--; | |
71 | ||
72 | n = n->children[offset >> genradix_depth_shift(level)]; | |
73 | offset &= genradix_depth_size(level) - 1; | |
74 | } | |
75 | ||
76 | return &n->data[offset]; | |
77 | } | |
78 | EXPORT_SYMBOL(__genradix_ptr); | |
79 | ||
3c52b0af EB |
80 | static inline struct genradix_node *genradix_alloc_node(gfp_t gfp_mask) |
81 | { | |
3a319a24 | 82 | return kzalloc(GENRADIX_NODE_SIZE, gfp_mask); |
3c52b0af EB |
83 | } |
84 | ||
85 | static inline void genradix_free_node(struct genradix_node *node) | |
86 | { | |
3a319a24 | 87 | kfree(node); |
3c52b0af EB |
88 | } |
89 | ||
ba20ba2e KO |
90 | /* |
91 | * Returns pointer to the specified byte @offset within @radix, allocating it if | |
92 | * necessary - newly allocated slots are always zeroed out: | |
93 | */ | |
94 | void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset, | |
95 | gfp_t gfp_mask) | |
96 | { | |
97 | struct genradix_root *v = READ_ONCE(radix->root); | |
98 | struct genradix_node *n, *new_node = NULL; | |
99 | unsigned level; | |
100 | ||
101 | /* Increase tree depth if necessary: */ | |
102 | while (1) { | |
103 | struct genradix_root *r = v, *new_root; | |
104 | ||
105 | n = genradix_root_to_node(r); | |
106 | level = genradix_root_to_depth(r); | |
107 | ||
108 | if (n && ilog2(offset) < genradix_depth_shift(level)) | |
109 | break; | |
110 | ||
111 | if (!new_node) { | |
3c52b0af | 112 | new_node = genradix_alloc_node(gfp_mask); |
ba20ba2e KO |
113 | if (!new_node) |
114 | return NULL; | |
115 | } | |
116 | ||
117 | new_node->children[0] = n; | |
118 | new_root = ((struct genradix_root *) | |
119 | ((unsigned long) new_node | (n ? level + 1 : 0))); | |
120 | ||
121 | if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) { | |
122 | v = new_root; | |
123 | new_node = NULL; | |
124 | } | |
125 | } | |
126 | ||
127 | while (level--) { | |
128 | struct genradix_node **p = | |
129 | &n->children[offset >> genradix_depth_shift(level)]; | |
130 | offset &= genradix_depth_size(level) - 1; | |
131 | ||
132 | n = READ_ONCE(*p); | |
133 | if (!n) { | |
134 | if (!new_node) { | |
3c52b0af | 135 | new_node = genradix_alloc_node(gfp_mask); |
ba20ba2e KO |
136 | if (!new_node) |
137 | return NULL; | |
138 | } | |
139 | ||
140 | if (!(n = cmpxchg_release(p, NULL, new_node))) | |
141 | swap(n, new_node); | |
142 | } | |
143 | } | |
144 | ||
145 | if (new_node) | |
3c52b0af | 146 | genradix_free_node(new_node); |
ba20ba2e KO |
147 | |
148 | return &n->data[offset]; | |
149 | } | |
150 | EXPORT_SYMBOL(__genradix_ptr_alloc); | |
151 | ||
152 | void *__genradix_iter_peek(struct genradix_iter *iter, | |
153 | struct __genradix *radix, | |
154 | size_t objs_per_page) | |
155 | { | |
156 | struct genradix_root *r; | |
157 | struct genradix_node *n; | |
158 | unsigned level, i; | |
9492261f KO |
159 | |
160 | if (iter->offset == SIZE_MAX) | |
161 | return NULL; | |
162 | ||
ba20ba2e KO |
163 | restart: |
164 | r = READ_ONCE(radix->root); | |
165 | if (!r) | |
166 | return NULL; | |
167 | ||
168 | n = genradix_root_to_node(r); | |
169 | level = genradix_root_to_depth(r); | |
170 | ||
171 | if (ilog2(iter->offset) >= genradix_depth_shift(level)) | |
172 | return NULL; | |
173 | ||
174 | while (level) { | |
175 | level--; | |
176 | ||
177 | i = (iter->offset >> genradix_depth_shift(level)) & | |
178 | (GENRADIX_ARY - 1); | |
179 | ||
180 | while (!n->children[i]) { | |
9492261f KO |
181 | size_t objs_per_ptr = genradix_depth_size(level); |
182 | ||
183 | if (iter->offset + objs_per_ptr < iter->offset) { | |
184 | iter->offset = SIZE_MAX; | |
185 | iter->pos = SIZE_MAX; | |
186 | return NULL; | |
187 | } | |
188 | ||
ba20ba2e | 189 | i++; |
9492261f KO |
190 | iter->offset = round_down(iter->offset + objs_per_ptr, |
191 | objs_per_ptr); | |
3a319a24 | 192 | iter->pos = (iter->offset >> GENRADIX_NODE_SHIFT) * |
ba20ba2e KO |
193 | objs_per_page; |
194 | if (i == GENRADIX_ARY) | |
195 | goto restart; | |
196 | } | |
197 | ||
198 | n = n->children[i]; | |
199 | } | |
200 | ||
3a319a24 | 201 | return &n->data[iter->offset & (GENRADIX_NODE_SIZE - 1)]; |
ba20ba2e KO |
202 | } |
203 | EXPORT_SYMBOL(__genradix_iter_peek); | |
204 | ||
73badee4 KO |
205 | void *__genradix_iter_peek_prev(struct genradix_iter *iter, |
206 | struct __genradix *radix, | |
207 | size_t objs_per_page, | |
208 | size_t obj_size_plus_page_remainder) | |
209 | { | |
210 | struct genradix_root *r; | |
211 | struct genradix_node *n; | |
212 | unsigned level, i; | |
213 | ||
214 | if (iter->offset == SIZE_MAX) | |
215 | return NULL; | |
216 | ||
217 | restart: | |
218 | r = READ_ONCE(radix->root); | |
219 | if (!r) | |
220 | return NULL; | |
221 | ||
222 | n = genradix_root_to_node(r); | |
223 | level = genradix_root_to_depth(r); | |
224 | ||
225 | if (ilog2(iter->offset) >= genradix_depth_shift(level)) { | |
226 | iter->offset = genradix_depth_size(level); | |
3a319a24 | 227 | iter->pos = (iter->offset >> GENRADIX_NODE_SHIFT) * objs_per_page; |
73badee4 KO |
228 | |
229 | iter->offset -= obj_size_plus_page_remainder; | |
230 | iter->pos--; | |
231 | } | |
232 | ||
233 | while (level) { | |
234 | level--; | |
235 | ||
236 | i = (iter->offset >> genradix_depth_shift(level)) & | |
237 | (GENRADIX_ARY - 1); | |
238 | ||
239 | while (!n->children[i]) { | |
240 | size_t objs_per_ptr = genradix_depth_size(level); | |
241 | ||
242 | iter->offset = round_down(iter->offset, objs_per_ptr); | |
3a319a24 | 243 | iter->pos = (iter->offset >> GENRADIX_NODE_SHIFT) * objs_per_page; |
73badee4 KO |
244 | |
245 | if (!iter->offset) | |
246 | return NULL; | |
247 | ||
248 | iter->offset -= obj_size_plus_page_remainder; | |
249 | iter->pos--; | |
250 | ||
251 | if (!i) | |
252 | goto restart; | |
253 | --i; | |
254 | } | |
255 | ||
256 | n = n->children[i]; | |
257 | } | |
258 | ||
3a319a24 | 259 | return &n->data[iter->offset & (GENRADIX_NODE_SIZE - 1)]; |
73badee4 KO |
260 | } |
261 | EXPORT_SYMBOL(__genradix_iter_peek_prev); | |
262 | ||
ba20ba2e KO |
263 | static void genradix_free_recurse(struct genradix_node *n, unsigned level) |
264 | { | |
265 | if (level) { | |
266 | unsigned i; | |
267 | ||
268 | for (i = 0; i < GENRADIX_ARY; i++) | |
269 | if (n->children[i]) | |
270 | genradix_free_recurse(n->children[i], level - 1); | |
271 | } | |
272 | ||
3c52b0af | 273 | genradix_free_node(n); |
ba20ba2e KO |
274 | } |
275 | ||
276 | int __genradix_prealloc(struct __genradix *radix, size_t size, | |
277 | gfp_t gfp_mask) | |
278 | { | |
279 | size_t offset; | |
280 | ||
3a319a24 | 281 | for (offset = 0; offset < size; offset += GENRADIX_NODE_SIZE) |
ba20ba2e KO |
282 | if (!__genradix_ptr_alloc(radix, offset, gfp_mask)) |
283 | return -ENOMEM; | |
284 | ||
285 | return 0; | |
286 | } | |
287 | EXPORT_SYMBOL(__genradix_prealloc); | |
288 | ||
289 | void __genradix_free(struct __genradix *radix) | |
290 | { | |
291 | struct genradix_root *r = xchg(&radix->root, NULL); | |
292 | ||
293 | genradix_free_recurse(genradix_root_to_node(r), | |
294 | genradix_root_to_depth(r)); | |
295 | } | |
296 | EXPORT_SYMBOL(__genradix_free); |