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 KO |
7 | |
8 | #define GENRADIX_ARY (PAGE_SIZE / sizeof(struct genradix_node *)) | |
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: */ | |
17 | u8 data[PAGE_SIZE]; | |
18 | }; | |
19 | }; | |
20 | ||
21 | static inline int genradix_depth_shift(unsigned depth) | |
22 | { | |
23 | return PAGE_SHIFT + GENRADIX_ARY_SHIFT * depth; | |
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 \ | |
36 | DIV_ROUND_UP(BITS_PER_LONG - PAGE_SHIFT, GENRADIX_ARY_SHIFT) | |
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 | { | |
82 | struct genradix_node *node; | |
83 | ||
84 | node = (struct genradix_node *)__get_free_page(gfp_mask|__GFP_ZERO); | |
85 | ||
86 | /* | |
87 | * We're using pages (not slab allocations) directly for kernel data | |
88 | * structures, so we need to explicitly inform kmemleak of them in order | |
89 | * to avoid false positive memory leak reports. | |
90 | */ | |
91 | kmemleak_alloc(node, PAGE_SIZE, 1, gfp_mask); | |
92 | return node; | |
93 | } | |
94 | ||
95 | static inline void genradix_free_node(struct genradix_node *node) | |
96 | { | |
97 | kmemleak_free(node); | |
98 | free_page((unsigned long)node); | |
99 | } | |
100 | ||
ba20ba2e KO |
101 | /* |
102 | * Returns pointer to the specified byte @offset within @radix, allocating it if | |
103 | * necessary - newly allocated slots are always zeroed out: | |
104 | */ | |
105 | void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset, | |
106 | gfp_t gfp_mask) | |
107 | { | |
108 | struct genradix_root *v = READ_ONCE(radix->root); | |
109 | struct genradix_node *n, *new_node = NULL; | |
110 | unsigned level; | |
111 | ||
112 | /* Increase tree depth if necessary: */ | |
113 | while (1) { | |
114 | struct genradix_root *r = v, *new_root; | |
115 | ||
116 | n = genradix_root_to_node(r); | |
117 | level = genradix_root_to_depth(r); | |
118 | ||
119 | if (n && ilog2(offset) < genradix_depth_shift(level)) | |
120 | break; | |
121 | ||
122 | if (!new_node) { | |
3c52b0af | 123 | new_node = genradix_alloc_node(gfp_mask); |
ba20ba2e KO |
124 | if (!new_node) |
125 | return NULL; | |
126 | } | |
127 | ||
128 | new_node->children[0] = n; | |
129 | new_root = ((struct genradix_root *) | |
130 | ((unsigned long) new_node | (n ? level + 1 : 0))); | |
131 | ||
132 | if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) { | |
133 | v = new_root; | |
134 | new_node = NULL; | |
135 | } | |
136 | } | |
137 | ||
138 | while (level--) { | |
139 | struct genradix_node **p = | |
140 | &n->children[offset >> genradix_depth_shift(level)]; | |
141 | offset &= genradix_depth_size(level) - 1; | |
142 | ||
143 | n = READ_ONCE(*p); | |
144 | if (!n) { | |
145 | if (!new_node) { | |
3c52b0af | 146 | new_node = genradix_alloc_node(gfp_mask); |
ba20ba2e KO |
147 | if (!new_node) |
148 | return NULL; | |
149 | } | |
150 | ||
151 | if (!(n = cmpxchg_release(p, NULL, new_node))) | |
152 | swap(n, new_node); | |
153 | } | |
154 | } | |
155 | ||
156 | if (new_node) | |
3c52b0af | 157 | genradix_free_node(new_node); |
ba20ba2e KO |
158 | |
159 | return &n->data[offset]; | |
160 | } | |
161 | EXPORT_SYMBOL(__genradix_ptr_alloc); | |
162 | ||
163 | void *__genradix_iter_peek(struct genradix_iter *iter, | |
164 | struct __genradix *radix, | |
165 | size_t objs_per_page) | |
166 | { | |
167 | struct genradix_root *r; | |
168 | struct genradix_node *n; | |
169 | unsigned level, i; | |
9492261f KO |
170 | |
171 | if (iter->offset == SIZE_MAX) | |
172 | return NULL; | |
173 | ||
ba20ba2e KO |
174 | restart: |
175 | r = READ_ONCE(radix->root); | |
176 | if (!r) | |
177 | return NULL; | |
178 | ||
179 | n = genradix_root_to_node(r); | |
180 | level = genradix_root_to_depth(r); | |
181 | ||
182 | if (ilog2(iter->offset) >= genradix_depth_shift(level)) | |
183 | return NULL; | |
184 | ||
185 | while (level) { | |
186 | level--; | |
187 | ||
188 | i = (iter->offset >> genradix_depth_shift(level)) & | |
189 | (GENRADIX_ARY - 1); | |
190 | ||
191 | while (!n->children[i]) { | |
9492261f KO |
192 | size_t objs_per_ptr = genradix_depth_size(level); |
193 | ||
194 | if (iter->offset + objs_per_ptr < iter->offset) { | |
195 | iter->offset = SIZE_MAX; | |
196 | iter->pos = SIZE_MAX; | |
197 | return NULL; | |
198 | } | |
199 | ||
ba20ba2e | 200 | i++; |
9492261f KO |
201 | iter->offset = round_down(iter->offset + objs_per_ptr, |
202 | objs_per_ptr); | |
ba20ba2e KO |
203 | iter->pos = (iter->offset >> PAGE_SHIFT) * |
204 | objs_per_page; | |
205 | if (i == GENRADIX_ARY) | |
206 | goto restart; | |
207 | } | |
208 | ||
209 | n = n->children[i]; | |
210 | } | |
211 | ||
212 | return &n->data[iter->offset & (PAGE_SIZE - 1)]; | |
213 | } | |
214 | EXPORT_SYMBOL(__genradix_iter_peek); | |
215 | ||
73badee4 KO |
216 | void *__genradix_iter_peek_prev(struct genradix_iter *iter, |
217 | struct __genradix *radix, | |
218 | size_t objs_per_page, | |
219 | size_t obj_size_plus_page_remainder) | |
220 | { | |
221 | struct genradix_root *r; | |
222 | struct genradix_node *n; | |
223 | unsigned level, i; | |
224 | ||
225 | if (iter->offset == SIZE_MAX) | |
226 | return NULL; | |
227 | ||
228 | restart: | |
229 | r = READ_ONCE(radix->root); | |
230 | if (!r) | |
231 | return NULL; | |
232 | ||
233 | n = genradix_root_to_node(r); | |
234 | level = genradix_root_to_depth(r); | |
235 | ||
236 | if (ilog2(iter->offset) >= genradix_depth_shift(level)) { | |
237 | iter->offset = genradix_depth_size(level); | |
238 | iter->pos = (iter->offset >> PAGE_SHIFT) * objs_per_page; | |
239 | ||
240 | iter->offset -= obj_size_plus_page_remainder; | |
241 | iter->pos--; | |
242 | } | |
243 | ||
244 | while (level) { | |
245 | level--; | |
246 | ||
247 | i = (iter->offset >> genradix_depth_shift(level)) & | |
248 | (GENRADIX_ARY - 1); | |
249 | ||
250 | while (!n->children[i]) { | |
251 | size_t objs_per_ptr = genradix_depth_size(level); | |
252 | ||
253 | iter->offset = round_down(iter->offset, objs_per_ptr); | |
254 | iter->pos = (iter->offset >> PAGE_SHIFT) * objs_per_page; | |
255 | ||
256 | if (!iter->offset) | |
257 | return NULL; | |
258 | ||
259 | iter->offset -= obj_size_plus_page_remainder; | |
260 | iter->pos--; | |
261 | ||
262 | if (!i) | |
263 | goto restart; | |
264 | --i; | |
265 | } | |
266 | ||
267 | n = n->children[i]; | |
268 | } | |
269 | ||
270 | return &n->data[iter->offset & (PAGE_SIZE - 1)]; | |
271 | } | |
272 | EXPORT_SYMBOL(__genradix_iter_peek_prev); | |
273 | ||
ba20ba2e KO |
274 | static void genradix_free_recurse(struct genradix_node *n, unsigned level) |
275 | { | |
276 | if (level) { | |
277 | unsigned i; | |
278 | ||
279 | for (i = 0; i < GENRADIX_ARY; i++) | |
280 | if (n->children[i]) | |
281 | genradix_free_recurse(n->children[i], level - 1); | |
282 | } | |
283 | ||
3c52b0af | 284 | genradix_free_node(n); |
ba20ba2e KO |
285 | } |
286 | ||
287 | int __genradix_prealloc(struct __genradix *radix, size_t size, | |
288 | gfp_t gfp_mask) | |
289 | { | |
290 | size_t offset; | |
291 | ||
292 | for (offset = 0; offset < size; offset += PAGE_SIZE) | |
293 | if (!__genradix_ptr_alloc(radix, offset, gfp_mask)) | |
294 | return -ENOMEM; | |
295 | ||
296 | return 0; | |
297 | } | |
298 | EXPORT_SYMBOL(__genradix_prealloc); | |
299 | ||
300 | void __genradix_free(struct __genradix *radix) | |
301 | { | |
302 | struct genradix_root *r = xchg(&radix->root, NULL); | |
303 | ||
304 | genradix_free_recurse(genradix_root_to_node(r), | |
305 | genradix_root_to_depth(r)); | |
306 | } | |
307 | EXPORT_SYMBOL(__genradix_free); |