1 /*-
2 * Copyright (c) 2010 Isilon Systems, Inc.
3 * Copyright (c) 2010 iX Systems, Inc.
4 * Copyright (c) 2010 Panasas, Inc.
5 * Copyright (c) 2013, 2014 Mellanox Technologies, Ltd.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 * 1. Redistributions of source code must retain the above copyright
12 * notice unmodified, this list of conditions, and the following
13 * disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30 #include <sys/param.h>
31 #include <sys/systm.h>
32 #include <sys/malloc.h>
33 #include <sys/kernel.h>
34 #include <sys/sysctl.h>
35 #include <sys/lock.h>
36 #include <sys/mutex.h>
37
38 #include <machine/stdarg.h>
39
40 #include <linux/bitops.h>
41 #include <linux/kobject.h>
42 #include <linux/slab.h>
43 #include <linux/idr.h>
44 #include <linux/err.h>
45
46 /*
47 * IDR Implementation.
48 *
49 * This is quick and dirty and not as re-entrant as the linux version
50 * however it should be fairly fast. It is basically a radix tree with
51 * a builtin bitmap for allocation.
52 */
53 static MALLOC_DEFINE(M_IDR, "idr", "Linux IDR compat");
54
55 static inline int
idr_max(struct idr * idr)56 idr_max(struct idr *idr)
57 {
58 return (1 << (idr->layers * IDR_BITS)) - 1;
59 }
60
61 static inline int
idr_pos(int id,int layer)62 idr_pos(int id, int layer)
63 {
64 return (id >> (IDR_BITS * layer)) & IDR_MASK;
65 }
66
67 void
idr_init(struct idr * idr)68 idr_init(struct idr *idr)
69 {
70 bzero(idr, sizeof(*idr));
71 mtx_init(&idr->lock, "idr", NULL, MTX_DEF);
72 }
73
74 /* Only frees cached pages. */
75 void
idr_destroy(struct idr * idr)76 idr_destroy(struct idr *idr)
77 {
78 struct idr_layer *il, *iln;
79
80 idr_remove_all(idr);
81 mtx_lock(&idr->lock);
82 for (il = idr->free; il != NULL; il = iln) {
83 iln = il->ary[0];
84 free(il, M_IDR);
85 }
86 mtx_unlock(&idr->lock);
87 }
88
89 static void
idr_remove_layer(struct idr_layer * il,int layer)90 idr_remove_layer(struct idr_layer *il, int layer)
91 {
92 int i;
93
94 if (il == NULL)
95 return;
96 if (layer == 0) {
97 free(il, M_IDR);
98 return;
99 }
100 for (i = 0; i < IDR_SIZE; i++)
101 if (il->ary[i])
102 idr_remove_layer(il->ary[i], layer - 1);
103 }
104
105 void
idr_remove_all(struct idr * idr)106 idr_remove_all(struct idr *idr)
107 {
108
109 mtx_lock(&idr->lock);
110 idr_remove_layer(idr->top, idr->layers - 1);
111 idr->top = NULL;
112 idr->layers = 0;
113 mtx_unlock(&idr->lock);
114 }
115
116 void
idr_remove(struct idr * idr,int id)117 idr_remove(struct idr *idr, int id)
118 {
119 struct idr_layer *il;
120 int layer;
121 int idx;
122
123 id &= MAX_ID_MASK;
124 mtx_lock(&idr->lock);
125 il = idr->top;
126 layer = idr->layers - 1;
127 if (il == NULL || id > idr_max(idr)) {
128 mtx_unlock(&idr->lock);
129 return;
130 }
131 /*
132 * Walk down the tree to this item setting bitmaps along the way
133 * as we know at least one item will be free along this path.
134 */
135 while (layer && il) {
136 idx = idr_pos(id, layer);
137 il->bitmap |= 1 << idx;
138 il = il->ary[idx];
139 layer--;
140 }
141 idx = id & IDR_MASK;
142 /*
143 * At this point we've set free space bitmaps up the whole tree.
144 * We could make this non-fatal and unwind but linux dumps a stack
145 * and a warning so I don't think it's necessary.
146 */
147 if (il == NULL || (il->bitmap & (1 << idx)) != 0)
148 panic("idr_remove: Item %d not allocated (%p, %p)\n",
149 id, idr, il);
150 il->ary[idx] = NULL;
151 il->bitmap |= 1 << idx;
152 mtx_unlock(&idr->lock);
153 return;
154 }
155
156 void *
idr_replace(struct idr * idr,void * ptr,int id)157 idr_replace(struct idr *idr, void *ptr, int id)
158 {
159 struct idr_layer *il;
160 void *res;
161 int layer;
162 int idx;
163
164 res = ERR_PTR(-EINVAL);
165 id &= MAX_ID_MASK;
166 mtx_lock(&idr->lock);
167 il = idr->top;
168 layer = idr->layers - 1;
169 if (il == NULL || id > idr_max(idr))
170 goto out;
171 while (layer && il) {
172 il = il->ary[idr_pos(id, layer)];
173 layer--;
174 }
175 idx = id & IDR_MASK;
176 /*
177 * Replace still returns an error if the item was not allocated.
178 */
179 if (il != NULL && (il->bitmap & (1 << idx)) != 0) {
180 res = il->ary[idx];
181 il->ary[idx] = ptr;
182 }
183 out:
184 mtx_unlock(&idr->lock);
185 return (res);
186 }
187
188 static inline void *
idr_find_locked(struct idr * idr,int id)189 idr_find_locked(struct idr *idr, int id)
190 {
191 struct idr_layer *il;
192 void *res;
193 int layer;
194
195 mtx_assert(&idr->lock, MA_OWNED);
196
197 id &= MAX_ID_MASK;
198 res = NULL;
199 il = idr->top;
200 layer = idr->layers - 1;
201 if (il == NULL || id > idr_max(idr))
202 return (NULL);
203 while (layer && il) {
204 il = il->ary[idr_pos(id, layer)];
205 layer--;
206 }
207 if (il != NULL)
208 res = il->ary[id & IDR_MASK];
209 return (res);
210 }
211
212 void *
idr_find(struct idr * idr,int id)213 idr_find(struct idr *idr, int id)
214 {
215 void *res;
216
217 mtx_lock(&idr->lock);
218 res = idr_find_locked(idr, id);
219 mtx_unlock(&idr->lock);
220 return (res);
221 }
222
223 int
idr_pre_get(struct idr * idr,gfp_t gfp_mask)224 idr_pre_get(struct idr *idr, gfp_t gfp_mask)
225 {
226 struct idr_layer *il, *iln;
227 struct idr_layer *head;
228 int need;
229
230 mtx_lock(&idr->lock);
231 for (;;) {
232 need = idr->layers + 1;
233 for (il = idr->free; il != NULL; il = il->ary[0])
234 need--;
235 mtx_unlock(&idr->lock);
236 if (need == 0)
237 break;
238 for (head = NULL; need; need--) {
239 iln = malloc(sizeof(*il), M_IDR, M_ZERO | gfp_mask);
240 if (iln == NULL)
241 break;
242 bitmap_fill(&iln->bitmap, IDR_SIZE);
243 if (head != NULL) {
244 il->ary[0] = iln;
245 il = iln;
246 } else
247 head = il = iln;
248 }
249 if (head == NULL)
250 return (0);
251 mtx_lock(&idr->lock);
252 il->ary[0] = idr->free;
253 idr->free = head;
254 }
255 return (1);
256 }
257
258 static inline struct idr_layer *
idr_get(struct idr * idr)259 idr_get(struct idr *idr)
260 {
261 struct idr_layer *il;
262
263 il = idr->free;
264 if (il) {
265 idr->free = il->ary[0];
266 il->ary[0] = NULL;
267 return (il);
268 }
269 il = malloc(sizeof(*il), M_IDR, M_ZERO | M_NOWAIT);
270 bitmap_fill(&il->bitmap, IDR_SIZE);
271 return (il);
272 }
273
274 /*
275 * Could be implemented as get_new_above(idr, ptr, 0, idp) but written
276 * first for simplicity sake.
277 */
278 int
idr_get_new(struct idr * idr,void * ptr,int * idp)279 idr_get_new(struct idr *idr, void *ptr, int *idp)
280 {
281 struct idr_layer *stack[MAX_LEVEL];
282 struct idr_layer *il;
283 int error;
284 int layer;
285 int idx;
286 int id;
287
288 error = -EAGAIN;
289 mtx_lock(&idr->lock);
290 /*
291 * Expand the tree until there is free space.
292 */
293 if (idr->top == NULL || idr->top->bitmap == 0) {
294 if (idr->layers == MAX_LEVEL + 1) {
295 error = -ENOSPC;
296 goto out;
297 }
298 il = idr_get(idr);
299 if (il == NULL)
300 goto out;
301 il->ary[0] = idr->top;
302 if (idr->top)
303 il->bitmap &= ~1;
304 idr->top = il;
305 idr->layers++;
306 }
307 il = idr->top;
308 id = 0;
309 /*
310 * Walk the tree following free bitmaps, record our path.
311 */
312 for (layer = idr->layers - 1;; layer--) {
313 stack[layer] = il;
314 idx = ffsl(il->bitmap);
315 if (idx == 0)
316 panic("idr_get_new: Invalid leaf state (%p, %p)\n",
317 idr, il);
318 idx--;
319 id |= idx << (layer * IDR_BITS);
320 if (layer == 0)
321 break;
322 if (il->ary[idx] == NULL) {
323 il->ary[idx] = idr_get(idr);
324 if (il->ary[idx] == NULL)
325 goto out;
326 }
327 il = il->ary[idx];
328 }
329 /*
330 * Allocate the leaf to the consumer.
331 */
332 il->bitmap &= ~(1 << idx);
333 il->ary[idx] = ptr;
334 *idp = id;
335 /*
336 * Clear bitmaps potentially up to the root.
337 */
338 while (il->bitmap == 0 && ++layer < idr->layers) {
339 il = stack[layer];
340 il->bitmap &= ~(1 << idr_pos(id, layer));
341 }
342 error = 0;
343 out:
344 #ifdef INVARIANTS
345 if (error == 0 && idr_find_locked(idr, id) != ptr) {
346 panic("idr_get_new: Failed for idr %p, id %d, ptr %p\n",
347 idr, id, ptr);
348 }
349 #endif
350 mtx_unlock(&idr->lock);
351 return (error);
352 }
353
354 int
idr_get_new_above(struct idr * idr,void * ptr,int starting_id,int * idp)355 idr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp)
356 {
357 struct idr_layer *stack[MAX_LEVEL];
358 struct idr_layer *il;
359 int error;
360 int layer;
361 int idx, sidx;
362 int id;
363
364 error = -EAGAIN;
365 mtx_lock(&idr->lock);
366 /*
367 * Compute the layers required to support starting_id and the mask
368 * at the top layer.
369 */
370 restart:
371 idx = starting_id;
372 layer = 0;
373 while (idx & ~IDR_MASK) {
374 layer++;
375 idx >>= IDR_BITS;
376 }
377 if (layer == MAX_LEVEL + 1) {
378 error = -ENOSPC;
379 goto out;
380 }
381 /*
382 * Expand the tree until there is free space at or beyond starting_id.
383 */
384 while (idr->layers <= layer ||
385 idr->top->bitmap < (1 << idr_pos(starting_id, idr->layers - 1))) {
386 if (idr->layers == MAX_LEVEL + 1) {
387 error = -ENOSPC;
388 goto out;
389 }
390 il = idr_get(idr);
391 if (il == NULL)
392 goto out;
393 il->ary[0] = idr->top;
394 if (idr->top && idr->top->bitmap == 0)
395 il->bitmap &= ~1;
396 idr->top = il;
397 idr->layers++;
398 }
399 il = idr->top;
400 id = 0;
401 /*
402 * Walk the tree following free bitmaps, record our path.
403 */
404 for (layer = idr->layers - 1;; layer--) {
405 stack[layer] = il;
406 sidx = idr_pos(starting_id, layer);
407 /* Returns index numbered from 0 or size if none exists. */
408 idx = find_next_bit(&il->bitmap, IDR_SIZE, sidx);
409 if (idx == IDR_SIZE && sidx == 0)
410 panic("idr_get_new: Invalid leaf state (%p, %p)\n",
411 idr, il);
412 /*
413 * We may have walked a path where there was a free bit but
414 * it was lower than what we wanted. Restart the search with
415 * a larger starting id. id contains the progress we made so
416 * far. Search the leaf one above this level. This may
417 * restart as many as MAX_LEVEL times but that is expected
418 * to be rare.
419 */
420 if (idx == IDR_SIZE) {
421 starting_id = id + (1 << (layer+1 * IDR_BITS));
422 goto restart;
423 }
424 if (idx > sidx)
425 starting_id = 0; /* Search the whole subtree. */
426 id |= idx << (layer * IDR_BITS);
427 if (layer == 0)
428 break;
429 if (il->ary[idx] == NULL) {
430 il->ary[idx] = idr_get(idr);
431 if (il->ary[idx] == NULL)
432 goto out;
433 }
434 il = il->ary[idx];
435 }
436 /*
437 * Allocate the leaf to the consumer.
438 */
439 il->bitmap &= ~(1 << idx);
440 il->ary[idx] = ptr;
441 *idp = id;
442 /*
443 * Clear bitmaps potentially up to the root.
444 */
445 while (il->bitmap == 0 && ++layer < idr->layers) {
446 il = stack[layer];
447 il->bitmap &= ~(1 << idr_pos(id, layer));
448 }
449 error = 0;
450 out:
451 #ifdef INVARIANTS
452 if (error == 0 && idr_find_locked(idr, id) != ptr) {
453 panic("idr_get_new_above: Failed for idr %p, id %d, ptr %p\n",
454 idr, id, ptr);
455 }
456 #endif
457 mtx_unlock(&idr->lock);
458 return (error);
459 }
460