1 | |
2 | #include <linux/atomic.h> |
3 | #include <linux/export.h> |
4 | #include <linux/generic-radix-tree.h> |
5 | #include <linux/gfp.h> |
6 | #include <linux/kmemleak.h> |
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 | |
41 | static inline unsigned genradix_root_to_depth(struct genradix_root *r) |
42 | { |
43 | return (unsigned long) r & GENRADIX_DEPTH_MASK; |
44 | } |
45 | |
46 | static inline struct genradix_node *genradix_root_to_node(struct genradix_root *r) |
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(depth: 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(depth: level)]; |
73 | offset &= genradix_depth_size(depth: level) - 1; |
74 | } |
75 | |
76 | return &n->data[offset]; |
77 | } |
78 | EXPORT_SYMBOL(__genradix_ptr); |
79 | |
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(ptr: node, PAGE_SIZE, min_count: 1, gfp: gfp_mask); |
92 | return node; |
93 | } |
94 | |
95 | static inline void genradix_free_node(struct genradix_node *node) |
96 | { |
97 | kmemleak_free(ptr: node); |
98 | free_page((unsigned long)node); |
99 | } |
100 | |
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(depth: level)) |
120 | break; |
121 | |
122 | if (!new_node) { |
123 | new_node = genradix_alloc_node(gfp_mask); |
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(depth: level)]; |
141 | offset &= genradix_depth_size(depth: level) - 1; |
142 | |
143 | n = READ_ONCE(*p); |
144 | if (!n) { |
145 | if (!new_node) { |
146 | new_node = genradix_alloc_node(gfp_mask); |
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) |
157 | genradix_free_node(node: new_node); |
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; |
170 | |
171 | if (iter->offset == SIZE_MAX) |
172 | return NULL; |
173 | |
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(depth: level)) |
183 | return NULL; |
184 | |
185 | while (level) { |
186 | level--; |
187 | |
188 | i = (iter->offset >> genradix_depth_shift(depth: level)) & |
189 | (GENRADIX_ARY - 1); |
190 | |
191 | while (!n->children[i]) { |
192 | size_t objs_per_ptr = genradix_depth_size(depth: 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 | |
200 | i++; |
201 | iter->offset = round_down(iter->offset + objs_per_ptr, |
202 | objs_per_ptr); |
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 | |
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(depth: level)) { |
237 | iter->offset = genradix_depth_size(depth: 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(depth: level)) & |
248 | (GENRADIX_ARY - 1); |
249 | |
250 | while (!n->children[i]) { |
251 | size_t objs_per_ptr = genradix_depth_size(depth: 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 | |
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: n->children[i], level: level - 1); |
282 | } |
283 | |
284 | genradix_free_node(node: n); |
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(n: genradix_root_to_node(r), |
305 | level: genradix_root_to_depth(r)); |
306 | } |
307 | EXPORT_SYMBOL(__genradix_free); |
308 | |