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 if (il != NULL)
271 bitmap_fill(&il->bitmap, IDR_SIZE);
272 return (il);
273 }
274
275 /*
276 * Could be implemented as get_new_above(idr, ptr, 0, idp) but written
277 * first for simplicity sake.
278 */
279 int
idr_get_new(struct idr * idr,void * ptr,int * idp)280 idr_get_new(struct idr *idr, void *ptr, int *idp)
281 {
282 struct idr_layer *stack[MAX_LEVEL];
283 struct idr_layer *il;
284 int error;
285 int layer;
286 int idx;
287 int id;
288
289 error = -EAGAIN;
290 mtx_lock(&idr->lock);
291 /*
292 * Expand the tree until there is free space.
293 */
294 if (idr->top == NULL || idr->top->bitmap == 0) {
295 if (idr->layers == MAX_LEVEL + 1) {
296 error = -ENOSPC;
297 goto out;
298 }
299 il = idr_get(idr);
300 if (il == NULL)
301 goto out;
302 il->ary[0] = idr->top;
303 if (idr->top)
304 il->bitmap &= ~1;
305 idr->top = il;
306 idr->layers++;
307 }
308 il = idr->top;
309 id = 0;
310 /*
311 * Walk the tree following free bitmaps, record our path.
312 */
313 for (layer = idr->layers - 1;; layer--) {
314 stack[layer] = il;
315 idx = ffsl(il->bitmap);
316 if (idx == 0)
317 panic("idr_get_new: Invalid leaf state (%p, %p)\n",
318 idr, il);
319 idx--;
320 id |= idx << (layer * IDR_BITS);
321 if (layer == 0)
322 break;
323 if (il->ary[idx] == NULL) {
324 il->ary[idx] = idr_get(idr);
325 if (il->ary[idx] == NULL)
326 goto out;
327 }
328 il = il->ary[idx];
329 }
330 /*
331 * Allocate the leaf to the consumer.
332 */
333 il->bitmap &= ~(1 << idx);
334 il->ary[idx] = ptr;
335 *idp = id;
336 /*
337 * Clear bitmaps potentially up to the root.
338 */
339 while (il->bitmap == 0 && ++layer < idr->layers) {
340 il = stack[layer];
341 il->bitmap &= ~(1 << idr_pos(id, layer));
342 }
343 error = 0;
344 out:
345 #ifdef INVARIANTS
346 if (error == 0 && idr_find_locked(idr, id) != ptr) {
347 panic("idr_get_new: Failed for idr %p, id %d, ptr %p\n",
348 idr, id, ptr);
349 }
350 #endif
351 mtx_unlock(&idr->lock);
352 return (error);
353 }
354
355 int
idr_get_new_above(struct idr * idr,void * ptr,int starting_id,int * idp)356 idr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp)
357 {
358 struct idr_layer *stack[MAX_LEVEL];
359 struct idr_layer *il;
360 int error;
361 int layer;
362 int idx, sidx;
363 int id;
364
365 error = -EAGAIN;
366 mtx_lock(&idr->lock);
367 /*
368 * Compute the layers required to support starting_id and the mask
369 * at the top layer.
370 */
371 restart:
372 idx = starting_id;
373 layer = 0;
374 while (idx & ~IDR_MASK) {
375 layer++;
376 idx >>= IDR_BITS;
377 }
378 if (layer == MAX_LEVEL + 1) {
379 error = -ENOSPC;
380 goto out;
381 }
382 /*
383 * Expand the tree until there is free space at or beyond starting_id.
384 */
385 while (idr->layers <= layer ||
386 idr->top->bitmap < (1 << idr_pos(starting_id, idr->layers - 1))) {
387 if (idr->layers == MAX_LEVEL + 1) {
388 error = -ENOSPC;
389 goto out;
390 }
391 il = idr_get(idr);
392 if (il == NULL)
393 goto out;
394 il->ary[0] = idr->top;
395 if (idr->top && idr->top->bitmap == 0)
396 il->bitmap &= ~1;
397 idr->top = il;
398 idr->layers++;
399 }
400 il = idr->top;
401 id = 0;
402 /*
403 * Walk the tree following free bitmaps, record our path.
404 */
405 for (layer = idr->layers - 1;; layer--) {
406 stack[layer] = il;
407 sidx = idr_pos(starting_id, layer);
408 /* Returns index numbered from 0 or size if none exists. */
409 idx = find_next_bit(&il->bitmap, IDR_SIZE, sidx);
410 if (idx == IDR_SIZE && sidx == 0)
411 panic("idr_get_new: Invalid leaf state (%p, %p)\n",
412 idr, il);
413 /*
414 * We may have walked a path where there was a free bit but
415 * it was lower than what we wanted. Restart the search with
416 * a larger starting id. id contains the progress we made so
417 * far. Search the leaf one above this level. This may
418 * restart as many as MAX_LEVEL times but that is expected
419 * to be rare.
420 */
421 if (idx == IDR_SIZE) {
422 starting_id = id + (1 << ((layer + 1) * IDR_BITS));
423 goto restart;
424 }
425 if (idx > sidx)
426 starting_id = 0; /* Search the whole subtree. */
427 id |= idx << (layer * IDR_BITS);
428 if (layer == 0)
429 break;
430 if (il->ary[idx] == NULL) {
431 il->ary[idx] = idr_get(idr);
432 if (il->ary[idx] == NULL)
433 goto out;
434 }
435 il = il->ary[idx];
436 }
437 /*
438 * Allocate the leaf to the consumer.
439 */
440 il->bitmap &= ~(1 << idx);
441 il->ary[idx] = ptr;
442 *idp = id;
443 /*
444 * Clear bitmaps potentially up to the root.
445 */
446 while (il->bitmap == 0 && ++layer < idr->layers) {
447 il = stack[layer];
448 il->bitmap &= ~(1 << idr_pos(id, layer));
449 }
450 error = 0;
451 out:
452 #ifdef INVARIANTS
453 if (error == 0 && idr_find_locked(idr, id) != ptr) {
454 panic("idr_get_new_above: Failed for idr %p, id %d, ptr %p\n",
455 idr, id, ptr);
456 }
457 #endif
458 mtx_unlock(&idr->lock);
459 return (error);
460 }
461