1ba20ba2eSKent Overstreet
2ba20ba2eSKent Overstreet #include <linux/export.h>
3ba20ba2eSKent Overstreet #include <linux/generic-radix-tree.h>
4ba20ba2eSKent Overstreet #include <linux/gfp.h>
53c52b0afSEric Biggers #include <linux/kmemleak.h>
6ba20ba2eSKent Overstreet
7ba20ba2eSKent Overstreet #define GENRADIX_ARY (PAGE_SIZE / sizeof(struct genradix_node *))
8ba20ba2eSKent Overstreet #define GENRADIX_ARY_SHIFT ilog2(GENRADIX_ARY)
9ba20ba2eSKent Overstreet
10ba20ba2eSKent Overstreet struct genradix_node {
11ba20ba2eSKent Overstreet union {
12ba20ba2eSKent Overstreet /* Interior node: */
13ba20ba2eSKent Overstreet struct genradix_node *children[GENRADIX_ARY];
14ba20ba2eSKent Overstreet
15ba20ba2eSKent Overstreet /* Leaf: */
16ba20ba2eSKent Overstreet u8 data[PAGE_SIZE];
17ba20ba2eSKent Overstreet };
18ba20ba2eSKent Overstreet };
19ba20ba2eSKent Overstreet
genradix_depth_shift(unsigned depth)20ba20ba2eSKent Overstreet static inline int genradix_depth_shift(unsigned depth)
21ba20ba2eSKent Overstreet {
22ba20ba2eSKent Overstreet return PAGE_SHIFT + GENRADIX_ARY_SHIFT * depth;
23ba20ba2eSKent Overstreet }
24ba20ba2eSKent Overstreet
25ba20ba2eSKent Overstreet /*
26ba20ba2eSKent Overstreet * Returns size (of data, in bytes) that a tree of a given depth holds:
27ba20ba2eSKent Overstreet */
genradix_depth_size(unsigned depth)28ba20ba2eSKent Overstreet static inline size_t genradix_depth_size(unsigned depth)
29ba20ba2eSKent Overstreet {
30ba20ba2eSKent Overstreet return 1UL << genradix_depth_shift(depth);
31ba20ba2eSKent Overstreet }
32ba20ba2eSKent Overstreet
33ba20ba2eSKent Overstreet /* depth that's needed for a genradix that can address up to ULONG_MAX: */
34ba20ba2eSKent Overstreet #define GENRADIX_MAX_DEPTH \
35ba20ba2eSKent Overstreet DIV_ROUND_UP(BITS_PER_LONG - PAGE_SHIFT, GENRADIX_ARY_SHIFT)
36ba20ba2eSKent Overstreet
37ba20ba2eSKent Overstreet #define GENRADIX_DEPTH_MASK \
38ba20ba2eSKent Overstreet ((unsigned long) (roundup_pow_of_two(GENRADIX_MAX_DEPTH + 1) - 1))
39ba20ba2eSKent Overstreet
genradix_root_to_depth(struct genradix_root * r)40e3f4faa4SValdis Kletnieks static inline unsigned genradix_root_to_depth(struct genradix_root *r)
41ba20ba2eSKent Overstreet {
42ba20ba2eSKent Overstreet return (unsigned long) r & GENRADIX_DEPTH_MASK;
43ba20ba2eSKent Overstreet }
44ba20ba2eSKent Overstreet
genradix_root_to_node(struct genradix_root * r)45e3f4faa4SValdis Kletnieks static inline struct genradix_node *genradix_root_to_node(struct genradix_root *r)
46ba20ba2eSKent Overstreet {
47ba20ba2eSKent Overstreet return (void *) ((unsigned long) r & ~GENRADIX_DEPTH_MASK);
48ba20ba2eSKent Overstreet }
49ba20ba2eSKent Overstreet
50ba20ba2eSKent Overstreet /*
51ba20ba2eSKent Overstreet * Returns pointer to the specified byte @offset within @radix, or NULL if not
52ba20ba2eSKent Overstreet * allocated
53ba20ba2eSKent Overstreet */
__genradix_ptr(struct __genradix * radix,size_t offset)54ba20ba2eSKent Overstreet void *__genradix_ptr(struct __genradix *radix, size_t offset)
55ba20ba2eSKent Overstreet {
56ba20ba2eSKent Overstreet struct genradix_root *r = READ_ONCE(radix->root);
57ba20ba2eSKent Overstreet struct genradix_node *n = genradix_root_to_node(r);
58ba20ba2eSKent Overstreet unsigned level = genradix_root_to_depth(r);
59ba20ba2eSKent Overstreet
60ba20ba2eSKent Overstreet if (ilog2(offset) >= genradix_depth_shift(level))
61ba20ba2eSKent Overstreet return NULL;
62ba20ba2eSKent Overstreet
63ba20ba2eSKent Overstreet while (1) {
64ba20ba2eSKent Overstreet if (!n)
65ba20ba2eSKent Overstreet return NULL;
66ba20ba2eSKent Overstreet if (!level)
67ba20ba2eSKent Overstreet break;
68ba20ba2eSKent Overstreet
69ba20ba2eSKent Overstreet level--;
70ba20ba2eSKent Overstreet
71ba20ba2eSKent Overstreet n = n->children[offset >> genradix_depth_shift(level)];
72ba20ba2eSKent Overstreet offset &= genradix_depth_size(level) - 1;
73ba20ba2eSKent Overstreet }
74ba20ba2eSKent Overstreet
75ba20ba2eSKent Overstreet return &n->data[offset];
76ba20ba2eSKent Overstreet }
77ba20ba2eSKent Overstreet EXPORT_SYMBOL(__genradix_ptr);
78ba20ba2eSKent Overstreet
genradix_alloc_node(gfp_t gfp_mask)793c52b0afSEric Biggers static inline struct genradix_node *genradix_alloc_node(gfp_t gfp_mask)
803c52b0afSEric Biggers {
813c52b0afSEric Biggers struct genradix_node *node;
823c52b0afSEric Biggers
833c52b0afSEric Biggers node = (struct genradix_node *)__get_free_page(gfp_mask|__GFP_ZERO);
843c52b0afSEric Biggers
853c52b0afSEric Biggers /*
863c52b0afSEric Biggers * We're using pages (not slab allocations) directly for kernel data
873c52b0afSEric Biggers * structures, so we need to explicitly inform kmemleak of them in order
883c52b0afSEric Biggers * to avoid false positive memory leak reports.
893c52b0afSEric Biggers */
903c52b0afSEric Biggers kmemleak_alloc(node, PAGE_SIZE, 1, gfp_mask);
913c52b0afSEric Biggers return node;
923c52b0afSEric Biggers }
933c52b0afSEric Biggers
genradix_free_node(struct genradix_node * node)943c52b0afSEric Biggers static inline void genradix_free_node(struct genradix_node *node)
953c52b0afSEric Biggers {
963c52b0afSEric Biggers kmemleak_free(node);
973c52b0afSEric Biggers free_page((unsigned long)node);
983c52b0afSEric Biggers }
993c52b0afSEric Biggers
100ba20ba2eSKent Overstreet /*
101ba20ba2eSKent Overstreet * Returns pointer to the specified byte @offset within @radix, allocating it if
102ba20ba2eSKent Overstreet * necessary - newly allocated slots are always zeroed out:
103ba20ba2eSKent Overstreet */
__genradix_ptr_alloc(struct __genradix * radix,size_t offset,gfp_t gfp_mask)104ba20ba2eSKent Overstreet void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset,
105ba20ba2eSKent Overstreet gfp_t gfp_mask)
106ba20ba2eSKent Overstreet {
107ba20ba2eSKent Overstreet struct genradix_root *v = READ_ONCE(radix->root);
108ba20ba2eSKent Overstreet struct genradix_node *n, *new_node = NULL;
109ba20ba2eSKent Overstreet unsigned level;
110ba20ba2eSKent Overstreet
111ba20ba2eSKent Overstreet /* Increase tree depth if necessary: */
112ba20ba2eSKent Overstreet while (1) {
113ba20ba2eSKent Overstreet struct genradix_root *r = v, *new_root;
114ba20ba2eSKent Overstreet
115ba20ba2eSKent Overstreet n = genradix_root_to_node(r);
116ba20ba2eSKent Overstreet level = genradix_root_to_depth(r);
117ba20ba2eSKent Overstreet
118ba20ba2eSKent Overstreet if (n && ilog2(offset) < genradix_depth_shift(level))
119ba20ba2eSKent Overstreet break;
120ba20ba2eSKent Overstreet
121ba20ba2eSKent Overstreet if (!new_node) {
1223c52b0afSEric Biggers new_node = genradix_alloc_node(gfp_mask);
123ba20ba2eSKent Overstreet if (!new_node)
124ba20ba2eSKent Overstreet return NULL;
125ba20ba2eSKent Overstreet }
126ba20ba2eSKent Overstreet
127ba20ba2eSKent Overstreet new_node->children[0] = n;
128ba20ba2eSKent Overstreet new_root = ((struct genradix_root *)
129ba20ba2eSKent Overstreet ((unsigned long) new_node | (n ? level + 1 : 0)));
130ba20ba2eSKent Overstreet
131ba20ba2eSKent Overstreet if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) {
132ba20ba2eSKent Overstreet v = new_root;
133ba20ba2eSKent Overstreet new_node = NULL;
134ba20ba2eSKent Overstreet }
135ba20ba2eSKent Overstreet }
136ba20ba2eSKent Overstreet
137ba20ba2eSKent Overstreet while (level--) {
138ba20ba2eSKent Overstreet struct genradix_node **p =
139ba20ba2eSKent Overstreet &n->children[offset >> genradix_depth_shift(level)];
140ba20ba2eSKent Overstreet offset &= genradix_depth_size(level) - 1;
141ba20ba2eSKent Overstreet
142ba20ba2eSKent Overstreet n = READ_ONCE(*p);
143ba20ba2eSKent Overstreet if (!n) {
144ba20ba2eSKent Overstreet if (!new_node) {
1453c52b0afSEric Biggers new_node = genradix_alloc_node(gfp_mask);
146ba20ba2eSKent Overstreet if (!new_node)
147ba20ba2eSKent Overstreet return NULL;
148ba20ba2eSKent Overstreet }
149ba20ba2eSKent Overstreet
150ba20ba2eSKent Overstreet if (!(n = cmpxchg_release(p, NULL, new_node)))
151ba20ba2eSKent Overstreet swap(n, new_node);
152ba20ba2eSKent Overstreet }
153ba20ba2eSKent Overstreet }
154ba20ba2eSKent Overstreet
155ba20ba2eSKent Overstreet if (new_node)
1563c52b0afSEric Biggers genradix_free_node(new_node);
157ba20ba2eSKent Overstreet
158ba20ba2eSKent Overstreet return &n->data[offset];
159ba20ba2eSKent Overstreet }
160ba20ba2eSKent Overstreet EXPORT_SYMBOL(__genradix_ptr_alloc);
161ba20ba2eSKent Overstreet
__genradix_iter_peek(struct genradix_iter * iter,struct __genradix * radix,size_t objs_per_page)162ba20ba2eSKent Overstreet void *__genradix_iter_peek(struct genradix_iter *iter,
163ba20ba2eSKent Overstreet struct __genradix *radix,
164ba20ba2eSKent Overstreet size_t objs_per_page)
165ba20ba2eSKent Overstreet {
166ba20ba2eSKent Overstreet struct genradix_root *r;
167ba20ba2eSKent Overstreet struct genradix_node *n;
168ba20ba2eSKent Overstreet unsigned level, i;
169*aa7f1827SKent Overstreet
170*aa7f1827SKent Overstreet if (iter->offset == SIZE_MAX)
171*aa7f1827SKent Overstreet return NULL;
172*aa7f1827SKent Overstreet
173ba20ba2eSKent Overstreet restart:
174ba20ba2eSKent Overstreet r = READ_ONCE(radix->root);
175ba20ba2eSKent Overstreet if (!r)
176ba20ba2eSKent Overstreet return NULL;
177ba20ba2eSKent Overstreet
178ba20ba2eSKent Overstreet n = genradix_root_to_node(r);
179ba20ba2eSKent Overstreet level = genradix_root_to_depth(r);
180ba20ba2eSKent Overstreet
181ba20ba2eSKent Overstreet if (ilog2(iter->offset) >= genradix_depth_shift(level))
182ba20ba2eSKent Overstreet return NULL;
183ba20ba2eSKent Overstreet
184ba20ba2eSKent Overstreet while (level) {
185ba20ba2eSKent Overstreet level--;
186ba20ba2eSKent Overstreet
187ba20ba2eSKent Overstreet i = (iter->offset >> genradix_depth_shift(level)) &
188ba20ba2eSKent Overstreet (GENRADIX_ARY - 1);
189ba20ba2eSKent Overstreet
190ba20ba2eSKent Overstreet while (!n->children[i]) {
191*aa7f1827SKent Overstreet size_t objs_per_ptr = genradix_depth_size(level);
192*aa7f1827SKent Overstreet
193*aa7f1827SKent Overstreet if (iter->offset + objs_per_ptr < iter->offset) {
194*aa7f1827SKent Overstreet iter->offset = SIZE_MAX;
195*aa7f1827SKent Overstreet iter->pos = SIZE_MAX;
196*aa7f1827SKent Overstreet return NULL;
197*aa7f1827SKent Overstreet }
198*aa7f1827SKent Overstreet
199ba20ba2eSKent Overstreet i++;
200*aa7f1827SKent Overstreet iter->offset = round_down(iter->offset + objs_per_ptr,
201*aa7f1827SKent Overstreet objs_per_ptr);
202ba20ba2eSKent Overstreet iter->pos = (iter->offset >> PAGE_SHIFT) *
203ba20ba2eSKent Overstreet objs_per_page;
204ba20ba2eSKent Overstreet if (i == GENRADIX_ARY)
205ba20ba2eSKent Overstreet goto restart;
206ba20ba2eSKent Overstreet }
207ba20ba2eSKent Overstreet
208ba20ba2eSKent Overstreet n = n->children[i];
209ba20ba2eSKent Overstreet }
210ba20ba2eSKent Overstreet
211ba20ba2eSKent Overstreet return &n->data[iter->offset & (PAGE_SIZE - 1)];
212ba20ba2eSKent Overstreet }
213ba20ba2eSKent Overstreet EXPORT_SYMBOL(__genradix_iter_peek);
214ba20ba2eSKent Overstreet
genradix_free_recurse(struct genradix_node * n,unsigned level)215ba20ba2eSKent Overstreet static void genradix_free_recurse(struct genradix_node *n, unsigned level)
216ba20ba2eSKent Overstreet {
217ba20ba2eSKent Overstreet if (level) {
218ba20ba2eSKent Overstreet unsigned i;
219ba20ba2eSKent Overstreet
220ba20ba2eSKent Overstreet for (i = 0; i < GENRADIX_ARY; i++)
221ba20ba2eSKent Overstreet if (n->children[i])
222ba20ba2eSKent Overstreet genradix_free_recurse(n->children[i], level - 1);
223ba20ba2eSKent Overstreet }
224ba20ba2eSKent Overstreet
2253c52b0afSEric Biggers genradix_free_node(n);
226ba20ba2eSKent Overstreet }
227ba20ba2eSKent Overstreet
__genradix_prealloc(struct __genradix * radix,size_t size,gfp_t gfp_mask)228ba20ba2eSKent Overstreet int __genradix_prealloc(struct __genradix *radix, size_t size,
229ba20ba2eSKent Overstreet gfp_t gfp_mask)
230ba20ba2eSKent Overstreet {
231ba20ba2eSKent Overstreet size_t offset;
232ba20ba2eSKent Overstreet
233ba20ba2eSKent Overstreet for (offset = 0; offset < size; offset += PAGE_SIZE)
234ba20ba2eSKent Overstreet if (!__genradix_ptr_alloc(radix, offset, gfp_mask))
235ba20ba2eSKent Overstreet return -ENOMEM;
236ba20ba2eSKent Overstreet
237ba20ba2eSKent Overstreet return 0;
238ba20ba2eSKent Overstreet }
239ba20ba2eSKent Overstreet EXPORT_SYMBOL(__genradix_prealloc);
240ba20ba2eSKent Overstreet
__genradix_free(struct __genradix * radix)241ba20ba2eSKent Overstreet void __genradix_free(struct __genradix *radix)
242ba20ba2eSKent Overstreet {
243ba20ba2eSKent Overstreet struct genradix_root *r = xchg(&radix->root, NULL);
244ba20ba2eSKent Overstreet
245ba20ba2eSKent Overstreet genradix_free_recurse(genradix_root_to_node(r),
246ba20ba2eSKent Overstreet genradix_root_to_depth(r));
247ba20ba2eSKent Overstreet }
248ba20ba2eSKent Overstreet EXPORT_SYMBOL(__genradix_free);
249