]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/blob - sys/compat/linuxkpi/common/src/linux_idr.c
Factor out common code into "idr_find_layer_locked()" and fix inverted
[FreeBSD/FreeBSD.git] / sys / compat / linuxkpi / common / src / linux_idr.c
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-2016 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/cdefs.h>
31 __FBSDID("$FreeBSD$");
32
33 #include <sys/param.h>
34 #include <sys/systm.h>
35 #include <sys/malloc.h>
36 #include <sys/kernel.h>
37 #include <sys/sysctl.h>
38 #include <sys/lock.h>
39 #include <sys/mutex.h>
40
41 #include <machine/stdarg.h>
42
43 #include <linux/bitops.h>
44 #include <linux/kobject.h>
45 #include <linux/slab.h>
46 #include <linux/idr.h>
47 #include <linux/err.h>
48
49 /*
50  * IDR Implementation.
51  *
52  * This is quick and dirty and not as re-entrant as the linux version
53  * however it should be fairly fast.  It is basically a radix tree with
54  * a builtin bitmap for allocation.
55  */
56 static MALLOC_DEFINE(M_IDR, "idr", "Linux IDR compat");
57
58 static inline int
59 idr_max(struct idr *idr)
60 {
61         return (1 << (idr->layers * IDR_BITS)) - 1;
62 }
63
64 static inline int
65 idr_pos(int id, int layer)
66 {
67         return (id >> (IDR_BITS * layer)) & IDR_MASK;
68 }
69
70 void
71 idr_init(struct idr *idr)
72 {
73         bzero(idr, sizeof(*idr));
74         mtx_init(&idr->lock, "idr", NULL, MTX_DEF);
75 }
76
77 /* Only frees cached pages. */
78 void
79 idr_destroy(struct idr *idr)
80 {
81         struct idr_layer *il, *iln;
82
83         idr_remove_all(idr);
84         mtx_lock(&idr->lock);
85         for (il = idr->free; il != NULL; il = iln) {
86                 iln = il->ary[0];
87                 free(il, M_IDR);
88         }
89         mtx_unlock(&idr->lock);
90         mtx_destroy(&idr->lock);
91 }
92
93 static void
94 idr_remove_layer(struct idr_layer *il, int layer)
95 {
96         int i;
97
98         if (il == NULL)
99                 return;
100         if (layer == 0) {
101                 free(il, M_IDR);
102                 return;
103         }
104         for (i = 0; i < IDR_SIZE; i++)
105                 if (il->ary[i])
106                         idr_remove_layer(il->ary[i], layer - 1);
107 }
108
109 void
110 idr_remove_all(struct idr *idr)
111 {
112
113         mtx_lock(&idr->lock);
114         idr_remove_layer(idr->top, idr->layers - 1);
115         idr->top = NULL;
116         idr->layers = 0;
117         mtx_unlock(&idr->lock);
118 }
119
120 static void
121 idr_remove_locked(struct idr *idr, int id)
122 {
123         struct idr_layer *il;
124         int layer;
125         int idx;
126
127         id &= MAX_ID_MASK;
128         il = idr->top;
129         layer = idr->layers - 1;
130         if (il == NULL || id > idr_max(idr))
131                 return;
132         /*
133          * Walk down the tree to this item setting bitmaps along the way
134          * as we know at least one item will be free along this path.
135          */
136         while (layer && il) {
137                 idx = idr_pos(id, layer);
138                 il->bitmap |= 1 << idx;
139                 il = il->ary[idx];
140                 layer--;
141         }
142         idx = id & IDR_MASK;
143         /*
144          * At this point we've set free space bitmaps up the whole tree.
145          * We could make this non-fatal and unwind but linux dumps a stack
146          * and a warning so I don't think it's necessary.
147          */
148         if (il == NULL || (il->bitmap & (1 << idx)) != 0)
149                 panic("idr_remove: Item %d not allocated (%p, %p)\n",
150                     id, idr, il);
151         il->ary[idx] = NULL;
152         il->bitmap |= 1 << idx;
153 }
154
155 void
156 idr_remove(struct idr *idr, int id)
157 {
158         mtx_lock(&idr->lock);
159         idr_remove_locked(idr, id);
160         mtx_unlock(&idr->lock);
161 }
162
163
164 static inline struct idr_layer *
165 idr_find_layer_locked(struct idr *idr, int id)
166 {
167         struct idr_layer *il;
168         int layer;
169
170         id &= MAX_ID_MASK;
171         il = idr->top;
172         layer = idr->layers - 1;
173         if (il == NULL || id > idr_max(idr))
174                 return (NULL);
175         while (layer && il) {
176                 il = il->ary[idr_pos(id, layer)];
177                 layer--;
178         }
179         return (il);
180 }
181
182 void *
183 idr_replace(struct idr *idr, void *ptr, int id)
184 {
185         struct idr_layer *il;
186         void *res;
187         int idx;
188
189         mtx_lock(&idr->lock);
190         il = idr_find_layer_locked(idr, id);
191         idx = id & IDR_MASK;
192
193         /* Replace still returns an error if the item was not allocated. */
194         if (il == NULL || (il->bitmap & (1 << idx))) {
195                 res = ERR_PTR(-ENOENT);
196         } else {
197                 res = il->ary[idx];
198                 il->ary[idx] = ptr;
199         }
200         mtx_unlock(&idr->lock);
201         return (res);
202 }
203
204 static inline void *
205 idr_find_locked(struct idr *idr, int id)
206 {
207         struct idr_layer *il;
208         void *res;
209
210         mtx_assert(&idr->lock, MA_OWNED);
211         il = idr_find_layer_locked(idr, id);
212         if (il != NULL)
213                 res = il->ary[id & IDR_MASK];
214         else
215                 res = NULL;
216         return (res);
217 }
218
219 void *
220 idr_find(struct idr *idr, int id)
221 {
222         void *res;
223
224         mtx_lock(&idr->lock);
225         res = idr_find_locked(idr, id);
226         mtx_unlock(&idr->lock);
227         return (res);
228 }
229
230 int
231 idr_pre_get(struct idr *idr, gfp_t gfp_mask)
232 {
233         struct idr_layer *il, *iln;
234         struct idr_layer *head;
235         int need;
236
237         mtx_lock(&idr->lock);
238         for (;;) {
239                 need = idr->layers + 1;
240                 for (il = idr->free; il != NULL; il = il->ary[0])
241                         need--;
242                 mtx_unlock(&idr->lock);
243                 if (need <= 0)
244                         break;
245                 for (head = NULL; need; need--) {
246                         iln = malloc(sizeof(*il), M_IDR, M_ZERO | gfp_mask);
247                         if (iln == NULL)
248                                 break;
249                         bitmap_fill(&iln->bitmap, IDR_SIZE);
250                         if (head != NULL) {
251                                 il->ary[0] = iln;
252                                 il = iln;
253                         } else
254                                 head = il = iln;
255                 }
256                 if (head == NULL)
257                         return (0);
258                 mtx_lock(&idr->lock);
259                 il->ary[0] = idr->free;
260                 idr->free = head;
261         }
262         return (1);
263 }
264
265 static inline struct idr_layer *
266 idr_get(struct idr *idr)
267 {
268         struct idr_layer *il;
269
270         il = idr->free;
271         if (il) {
272                 idr->free = il->ary[0];
273                 il->ary[0] = NULL;
274                 return (il);
275         }
276         il = malloc(sizeof(*il), M_IDR, M_ZERO | M_NOWAIT);
277         bitmap_fill(&il->bitmap, IDR_SIZE);
278         return (il);
279 }
280
281 /*
282  * Could be implemented as get_new_above(idr, ptr, 0, idp) but written
283  * first for simplicity sake.
284  */
285 static int
286 idr_get_new_locked(struct idr *idr, void *ptr, int *idp)
287 {
288         struct idr_layer *stack[MAX_LEVEL];
289         struct idr_layer *il;
290         int error;
291         int layer;
292         int idx;
293         int id;
294
295         mtx_assert(&idr->lock, MA_OWNED);
296
297         error = -EAGAIN;
298         /*
299          * Expand the tree until there is free space.
300          */
301         if (idr->top == NULL || idr->top->bitmap == 0) {
302                 if (idr->layers == MAX_LEVEL + 1) {
303                         error = -ENOSPC;
304                         goto out;
305                 }
306                 il = idr_get(idr);
307                 if (il == NULL)
308                         goto out;
309                 il->ary[0] = idr->top;
310                 if (idr->top)
311                         il->bitmap &= ~1;
312                 idr->top = il;
313                 idr->layers++;
314         }
315         il = idr->top;
316         id = 0;
317         /*
318          * Walk the tree following free bitmaps, record our path.
319          */
320         for (layer = idr->layers - 1;; layer--) {
321                 stack[layer] = il;
322                 idx = ffsl(il->bitmap);
323                 if (idx == 0)
324                         panic("idr_get_new: Invalid leaf state (%p, %p)\n",
325                             idr, il);
326                 idx--;
327                 id |= idx << (layer * IDR_BITS);
328                 if (layer == 0)
329                         break;
330                 if (il->ary[idx] == NULL) {
331                         il->ary[idx] = idr_get(idr);
332                         if (il->ary[idx] == NULL)
333                                 goto out;
334                 }
335                 il = il->ary[idx];
336         }
337         /*
338          * Allocate the leaf to the consumer.
339          */
340         il->bitmap &= ~(1 << idx);
341         il->ary[idx] = ptr;
342         *idp = id;
343         /*
344          * Clear bitmaps potentially up to the root.
345          */
346         while (il->bitmap == 0 && ++layer < idr->layers) {
347                 il = stack[layer];
348                 il->bitmap &= ~(1 << idr_pos(id, layer));
349         }
350         error = 0;
351 out:
352 #ifdef INVARIANTS
353         if (error == 0 && idr_find_locked(idr, id) != ptr) {
354                 panic("idr_get_new: Failed for idr %p, id %d, ptr %p\n",
355                     idr, id, ptr);
356         }
357 #endif
358         return (error);
359 }
360
361 int
362 idr_get_new(struct idr *idr, void *ptr, int *idp)
363 {
364         int retval;
365
366         mtx_lock(&idr->lock);
367         retval = idr_get_new_locked(idr, ptr, idp);
368         mtx_unlock(&idr->lock);
369         return (retval);
370 }
371
372 static int
373 idr_get_new_above_locked(struct idr *idr, void *ptr, int starting_id, int *idp)
374 {
375         struct idr_layer *stack[MAX_LEVEL];
376         struct idr_layer *il;
377         int error;
378         int layer;
379         int idx, sidx;
380         int id;
381
382         mtx_assert(&idr->lock, MA_OWNED);
383
384         error = -EAGAIN;
385         /*
386          * Compute the layers required to support starting_id and the mask
387          * at the top layer.
388          */
389 restart:
390         idx = starting_id;
391         layer = 0;
392         while (idx & ~IDR_MASK) {
393                 layer++;
394                 idx >>= IDR_BITS;
395         }
396         if (layer == MAX_LEVEL + 1) {
397                 error = -ENOSPC;
398                 goto out;
399         }
400         /*
401          * Expand the tree until there is free space at or beyond starting_id.
402          */
403         while (idr->layers <= layer ||
404             idr->top->bitmap < (1 << idr_pos(starting_id, idr->layers - 1))) {
405                 if (idr->layers == MAX_LEVEL + 1) {
406                         error = -ENOSPC;
407                         goto out;
408                 }
409                 il = idr_get(idr);
410                 if (il == NULL)
411                         goto out;
412                 il->ary[0] = idr->top;
413                 if (idr->top && idr->top->bitmap == 0)
414                         il->bitmap &= ~1;
415                 idr->top = il;
416                 idr->layers++;
417         }
418         il = idr->top;
419         id = 0;
420         /*
421          * Walk the tree following free bitmaps, record our path.
422          */
423         for (layer = idr->layers - 1;; layer--) {
424                 stack[layer] = il;
425                 sidx = idr_pos(starting_id, layer);
426                 /* Returns index numbered from 0 or size if none exists. */
427                 idx = find_next_bit(&il->bitmap, IDR_SIZE, sidx);
428                 if (idx == IDR_SIZE && sidx == 0)
429                         panic("idr_get_new: Invalid leaf state (%p, %p)\n",
430                             idr, il);
431                 /*
432                  * We may have walked a path where there was a free bit but
433                  * it was lower than what we wanted.  Restart the search with
434                  * a larger starting id.  id contains the progress we made so
435                  * far.  Search the leaf one above this level.  This may
436                  * restart as many as MAX_LEVEL times but that is expected
437                  * to be rare.
438                  */
439                 if (idx == IDR_SIZE) {
440                         starting_id = id + (1 << ((layer + 1) * IDR_BITS));
441                         goto restart;
442                 }
443                 if (idx > sidx)
444                         starting_id = 0;        /* Search the whole subtree. */
445                 id |= idx << (layer * IDR_BITS);
446                 if (layer == 0)
447                         break;
448                 if (il->ary[idx] == NULL) {
449                         il->ary[idx] = idr_get(idr);
450                         if (il->ary[idx] == NULL)
451                                 goto out;
452                 }
453                 il = il->ary[idx];
454         }
455         /*
456          * Allocate the leaf to the consumer.
457          */
458         il->bitmap &= ~(1 << idx);
459         il->ary[idx] = ptr;
460         *idp = id;
461         /*
462          * Clear bitmaps potentially up to the root.
463          */
464         while (il->bitmap == 0 && ++layer < idr->layers) {
465                 il = stack[layer];
466                 il->bitmap &= ~(1 << idr_pos(id, layer));
467         }
468         error = 0;
469 out:
470 #ifdef INVARIANTS
471         if (error == 0 && idr_find_locked(idr, id) != ptr) {
472                 panic("idr_get_new_above: Failed for idr %p, id %d, ptr %p\n",
473                     idr, id, ptr);
474         }
475 #endif
476         return (error);
477 }
478
479 int
480 idr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp)
481 {
482         int retval;
483
484         mtx_lock(&idr->lock);
485         retval = idr_get_new_above_locked(idr, ptr, starting_id, idp);
486         mtx_unlock(&idr->lock);
487         return (retval);
488 }
489
490 static int
491 idr_alloc_locked(struct idr *idr, void *ptr, int start, int end)
492 {
493         int max = end > 0 ? end - 1 : INT_MAX;
494         int error;
495         int id;
496
497         mtx_assert(&idr->lock, MA_OWNED);
498
499         if (unlikely(start < 0))
500                 return (-EINVAL);
501         if (unlikely(max < start))
502                 return (-ENOSPC);
503
504         if (start == 0)
505                 error = idr_get_new_locked(idr, ptr, &id);
506         else
507                 error = idr_get_new_above_locked(idr, ptr, start, &id);
508
509         if (unlikely(error < 0))
510                 return (error);
511         if (unlikely(id > max)) {
512                 idr_remove_locked(idr, id);
513                 return (-ENOSPC);
514         }
515         return (id);
516 }
517
518 int
519 idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
520 {
521         int retval;
522
523         mtx_lock(&idr->lock);
524         retval = idr_alloc_locked(idr, ptr, start, end);
525         mtx_unlock(&idr->lock);
526         return (retval);
527 }
528
529 int
530 idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
531 {
532         int retval;
533
534         mtx_lock(&idr->lock);
535         retval = idr_alloc_locked(idr, ptr, max(start, idr->next_cyclic_id), end);
536         if (unlikely(retval == -ENOSPC))
537                 retval = idr_alloc_locked(idr, ptr, start, end);
538         if (likely(retval >= 0))
539                 idr->next_cyclic_id = retval + 1;
540         mtx_unlock(&idr->lock);
541         return (retval);
542 }