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