1
2#include <linux/export.h>
3#include <linux/generic-radix-tree.h>
4#include <linux/gfp.h>
5
6#define GENRADIX_ARY (PAGE_SIZE / sizeof(struct genradix_node *))
7#define GENRADIX_ARY_SHIFT ilog2(GENRADIX_ARY)
8
9struct genradix_node {
10 union {
11 /* Interior node: */
12 struct genradix_node *children[GENRADIX_ARY];
13
14 /* Leaf: */
15 u8 data[PAGE_SIZE];
16 };
17};
18
19static inline int genradix_depth_shift(unsigned depth)
20{
21 return PAGE_SHIFT + GENRADIX_ARY_SHIFT * depth;
22}
23
24/*
25 * Returns size (of data, in bytes) that a tree of a given depth holds:
26 */
27static inline size_t genradix_depth_size(unsigned depth)
28{
29 return 1UL << genradix_depth_shift(depth);
30}
31
32/* depth that's needed for a genradix that can address up to ULONG_MAX: */
33#define GENRADIX_MAX_DEPTH \
34 DIV_ROUND_UP(BITS_PER_LONG - PAGE_SHIFT, GENRADIX_ARY_SHIFT)
35
36#define GENRADIX_DEPTH_MASK \
37 ((unsigned long) (roundup_pow_of_two(GENRADIX_MAX_DEPTH + 1) - 1))
38
39unsigned genradix_root_to_depth(struct genradix_root *r)
40{
41 return (unsigned long) r & GENRADIX_DEPTH_MASK;
42}
43
44struct genradix_node *genradix_root_to_node(struct genradix_root *r)
45{
46 return (void *) ((unsigned long) r & ~GENRADIX_DEPTH_MASK);
47}
48
49/*
50 * Returns pointer to the specified byte @offset within @radix, or NULL if not
51 * allocated
52 */
53void *__genradix_ptr(struct __genradix *radix, size_t offset)
54{
55 struct genradix_root *r = READ_ONCE(radix->root);
56 struct genradix_node *n = genradix_root_to_node(r);
57 unsigned level = genradix_root_to_depth(r);
58
59 if (ilog2(offset) >= genradix_depth_shift(level))
60 return NULL;
61
62 while (1) {
63 if (!n)
64 return NULL;
65 if (!level)
66 break;
67
68 level--;
69
70 n = n->children[offset >> genradix_depth_shift(level)];
71 offset &= genradix_depth_size(level) - 1;
72 }
73
74 return &n->data[offset];
75}
76EXPORT_SYMBOL(__genradix_ptr);
77
78/*
79 * Returns pointer to the specified byte @offset within @radix, allocating it if
80 * necessary - newly allocated slots are always zeroed out:
81 */
82void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset,
83 gfp_t gfp_mask)
84{
85 struct genradix_root *v = READ_ONCE(radix->root);
86 struct genradix_node *n, *new_node = NULL;
87 unsigned level;
88
89 /* Increase tree depth if necessary: */
90 while (1) {
91 struct genradix_root *r = v, *new_root;
92
93 n = genradix_root_to_node(r);
94 level = genradix_root_to_depth(r);
95
96 if (n && ilog2(offset) < genradix_depth_shift(level))
97 break;
98
99 if (!new_node) {
100 new_node = (void *)
101 __get_free_page(gfp_mask|__GFP_ZERO);
102 if (!new_node)
103 return NULL;
104 }
105
106 new_node->children[0] = n;
107 new_root = ((struct genradix_root *)
108 ((unsigned long) new_node | (n ? level + 1 : 0)));
109
110 if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) {
111 v = new_root;
112 new_node = NULL;
113 }
114 }
115
116 while (level--) {
117 struct genradix_node **p =
118 &n->children[offset >> genradix_depth_shift(level)];
119 offset &= genradix_depth_size(level) - 1;
120
121 n = READ_ONCE(*p);
122 if (!n) {
123 if (!new_node) {
124 new_node = (void *)
125 __get_free_page(gfp_mask|__GFP_ZERO);
126 if (!new_node)
127 return NULL;
128 }
129
130 if (!(n = cmpxchg_release(p, NULL, new_node)))
131 swap(n, new_node);
132 }
133 }
134
135 if (new_node)
136 free_page((unsigned long) new_node);
137
138 return &n->data[offset];
139}
140EXPORT_SYMBOL(__genradix_ptr_alloc);
141
142void *__genradix_iter_peek(struct genradix_iter *iter,
143 struct __genradix *radix,
144 size_t objs_per_page)
145{
146 struct genradix_root *r;
147 struct genradix_node *n;
148 unsigned level, i;
149restart:
150 r = READ_ONCE(radix->root);
151 if (!r)
152 return NULL;
153
154 n = genradix_root_to_node(r);
155 level = genradix_root_to_depth(r);
156
157 if (ilog2(iter->offset) >= genradix_depth_shift(level))
158 return NULL;
159
160 while (level) {
161 level--;
162
163 i = (iter->offset >> genradix_depth_shift(level)) &
164 (GENRADIX_ARY - 1);
165
166 while (!n->children[i]) {
167 i++;
168 iter->offset = round_down(iter->offset +
169 genradix_depth_size(level),
170 genradix_depth_size(level));
171 iter->pos = (iter->offset >> PAGE_SHIFT) *
172 objs_per_page;
173 if (i == GENRADIX_ARY)
174 goto restart;
175 }
176
177 n = n->children[i];
178 }
179
180 return &n->data[iter->offset & (PAGE_SIZE - 1)];
181}
182EXPORT_SYMBOL(__genradix_iter_peek);
183
184static void genradix_free_recurse(struct genradix_node *n, unsigned level)
185{
186 if (level) {
187 unsigned i;
188
189 for (i = 0; i < GENRADIX_ARY; i++)
190 if (n->children[i])
191 genradix_free_recurse(n->children[i], level - 1);
192 }
193
194 free_page((unsigned long) n);
195}
196
197int __genradix_prealloc(struct __genradix *radix, size_t size,
198 gfp_t gfp_mask)
199{
200 size_t offset;
201
202 for (offset = 0; offset < size; offset += PAGE_SIZE)
203 if (!__genradix_ptr_alloc(radix, offset, gfp_mask))
204 return -ENOMEM;
205
206 return 0;
207}
208EXPORT_SYMBOL(__genradix_prealloc);
209
210void __genradix_free(struct __genradix *radix)
211{
212 struct genradix_root *r = xchg(&radix->root, NULL);
213
214 genradix_free_recurse(genradix_root_to_node(r),
215 genradix_root_to_depth(r));
216}
217EXPORT_SYMBOL(__genradix_free);
218