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  * 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
  56 idr_max(struct idr *idr)
  57 {
  58         return (1 << (idr->layers * IDR_BITS)) - 1;
  59 }
  60
  61 static inline int
  62 idr_pos(int id, int layer)
  63 {
  64         return (id >> (IDR_BITS * layer)) & IDR_MASK;
  65 }
  66
  67 void
  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
  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
  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
 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
 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 *
 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 void *
 189 idr_find(struct idr *idr, int id)
 190 {
 191         struct idr_layer *il;
 192         void *res;
 193         int layer;
 194
 195         res = NULL;
 196         id &= MAX_ID_MASK;
 197         mtx_lock(&idr->lock);
 198         il = idr->top;
 199         layer = idr->layers - 1;
 200         if (il == NULL || id > idr_max(idr))
 201                 goto out;
 202         while (layer && il) {
 203                 il = il->ary[idr_pos(id, layer)];
 204                 layer--;
 205         }
 206         if (il != NULL)
 207                 res = il->ary[id & IDR_MASK];
 208 out:
 209         mtx_unlock(&idr->lock);
 210         return (res);
 211 }
 212
 213 int
 214 idr_pre_get(struct idr *idr, gfp_t gfp_mask)
 215 {
 216         struct idr_layer *il, *iln;
 217         struct idr_layer *head;
 218         int need;
 219
 220         mtx_lock(&idr->lock);
 221         for (;;) {
 222                 need = idr->layers + 1;
 223                 for (il = idr->free; il != NULL; il = il->ary[0])
 224                         need--;
 225                 mtx_unlock(&idr->lock);
 226                 if (need == 0)
 227                         break;
 228                 for (head = NULL; need; need--) {
 229                         iln = malloc(sizeof(*il), M_IDR, M_ZERO | gfp_mask);
 230                         if (iln == NULL)
 231                                 break;
 232                         bitmap_fill(&iln->bitmap, IDR_SIZE);
 233                         if (head != NULL) {
 234                                 il->ary[0] = iln;
 235                                 il = iln;
 236                         } else
 237                                 head = il = iln;
 238                 }
 239                 if (head == NULL)
 240                         return (0);
 241                 mtx_lock(&idr->lock);
 242                 il->ary[0] = idr->free;
 243                 idr->free = head;
 244         }
 245         return (1);
 246 }
 247
 248 static inline struct idr_layer *
 249 idr_get(struct idr *idr)
 250 {
 251         struct idr_layer *il;
 252
 253         il = idr->free;
 254         if (il) {
 255                 idr->free = il->ary[0];
 256                 il->ary[0] = NULL;
 257                 return (il);
 258         }
 259         il = malloc(sizeof(*il), M_IDR, M_ZERO | M_NOWAIT);
 260         bitmap_fill(&il->bitmap, IDR_SIZE);
 261         return (il);
 262 }
 263
 264 /*
 265  * Could be implemented as get_new_above(idr, ptr, 0, idp) but written
 266  * first for simplicity sake.
 267  */
 268 int
 269 idr_get_new(struct idr *idr, void *ptr, int *idp)
 270 {
 271         struct idr_layer *stack[MAX_LEVEL];
 272         struct idr_layer *il;
 273         int error;
 274         int layer;
 275         int idx;
 276         int id;
 277
 278         error = -EAGAIN;
 279         mtx_lock(&idr->lock);
 280         /*
 281          * Expand the tree until there is free space.
 282          */
 283         if (idr->top == NULL || idr->top->bitmap == 0) {
 284                 if (idr->layers == MAX_LEVEL + 1) {
 285                         error = -ENOSPC;
 286                         goto out;
 287                 }
 288                 il = idr_get(idr);
 289                 if (il == NULL)
 290                         goto out;
 291                 il->ary[0] = idr->top;
 292                 if (idr->top)
 293                         il->bitmap &= ~1;
 294                 idr->top = il;
 295                 idr->layers++;
 296         }
 297         il = idr->top;
 298         id = 0;
 299         /*
 300          * Walk the tree following free bitmaps, record our path.
 301          */
 302         for (layer = idr->layers - 1;; layer--) {
 303                 stack[layer] = il;
 304                 idx = ffsl(il->bitmap);
 305                 if (idx == 0)
 306                         panic("idr_get_new: Invalid leaf state (%p, %p)\n",
 307                             idr, il);
 308                 idx--;
 309                 id |= idx << (layer * IDR_BITS);
 310                 if (layer == 0)
 311                         break;
 312                 if (il->ary[idx] == NULL) {
 313                         il->ary[idx] = idr_get(idr);
 314                         if (il->ary[idx] == NULL)
 315                                 goto out;
 316                 }
 317                 il = il->ary[idx];
 318         }
 319         /*
 320          * Allocate the leaf to the consumer.
 321          */
 322         il->bitmap &= ~(1 << idx);
 323         il->ary[idx] = ptr;
 324         *idp = id;
 325         /*
 326          * Clear bitmaps potentially up to the root.
 327          */
 328         while (il->bitmap == 0 && ++layer < idr->layers) {
 329                 il = stack[layer];
 330                 il->bitmap &= ~(1 << idr_pos(id, layer));
 331         }
 332         error = 0;
 333 out:
 334         mtx_unlock(&idr->lock);
 335 #ifdef INVARIANTS
 336         if (error == 0 && idr_find(idr, id) != ptr) {
 337                 panic("idr_get_new: Failed for idr %p, id %d, ptr %p\n",
 338                     idr, id, ptr);
 339         }
 340 #endif
 341         return (error);
 342 }
 343
 344 int
 345 idr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp)
 346 {
 347         struct idr_layer *stack[MAX_LEVEL];
 348         struct idr_layer *il;
 349         int error;
 350         int layer;
 351         int idx, sidx;
 352         int id;
 353
 354         error = -EAGAIN;
 355         mtx_lock(&idr->lock);
 356         /*
 357          * Compute the layers required to support starting_id and the mask
 358          * at the top layer.
 359          */
 360 restart:
 361         idx = starting_id;
 362         layer = 0;
 363         while (idx & ~IDR_MASK) {
 364                 layer++;
 365                 idx >>= IDR_BITS;
 366         }
 367         if (layer == MAX_LEVEL + 1) {
 368                 error = -ENOSPC;
 369                 goto out;
 370         }
 371         /*
 372          * Expand the tree until there is free space at or beyond starting_id.
 373          */
 374         while (idr->layers <= layer ||
 375             idr->top->bitmap < (1 << idr_pos(starting_id, idr->layers - 1))) {
 376                 if (idr->layers == MAX_LEVEL + 1) {
 377                         error = -ENOSPC;
 378                         goto out;
 379                 }
 380                 il = idr_get(idr);
 381                 if (il == NULL)
 382                         goto out;
 383                 il->ary[0] = idr->top;
 384                 if (idr->top && idr->top->bitmap == 0)
 385                         il->bitmap &= ~1;
 386                 idr->top = il;
 387                 idr->layers++;
 388         }
 389         il = idr->top;
 390         id = 0;
 391         /*
 392          * Walk the tree following free bitmaps, record our path.
 393          */
 394         for (layer = idr->layers - 1;; layer--) {
 395                 stack[layer] = il;
 396                 sidx = idr_pos(starting_id, layer);
 397                 /* Returns index numbered from 0 or size if none exists. */
 398                 idx = find_next_bit(&il->bitmap, IDR_SIZE, sidx);
 399                 if (idx == IDR_SIZE && sidx == 0)
 400                         panic("idr_get_new: Invalid leaf state (%p, %p)\n",
 401                             idr, il);
 402                 /*
 403                  * We may have walked a path where there was a free bit but
 404                  * it was lower than what we wanted.  Restart the search with
 405                  * a larger starting id.  id contains the progress we made so
 406                  * far.  Search the leaf one above this level.  This may
 407                  * restart as many as MAX_LEVEL times but that is expected
 408                  * to be rare.
 409                  */
 410                 if (idx == IDR_SIZE) {
 411                         starting_id = id + (1 << (layer+1 * IDR_BITS));
 412                         goto restart;
 413                 }
 414                 if (idx > sidx)
 415                         starting_id = 0;        /* Search the whole subtree. */
 416                 id |= idx << (layer * IDR_BITS);
 417                 if (layer == 0)
 418                         break;
 419                 if (il->ary[idx] == NULL) {
 420                         il->ary[idx] = idr_get(idr);
 421                         if (il->ary[idx] == NULL)
 422                                 goto out;
 423                 }
 424                 il = il->ary[idx];
 425         }
 426         /*
 427          * Allocate the leaf to the consumer.
 428          */
 429         il->bitmap &= ~(1 << idx);
 430         il->ary[idx] = ptr;
 431         *idp = id;
 432         /*
 433          * Clear bitmaps potentially up to the root.
 434          */
 435         while (il->bitmap == 0 && ++layer < idr->layers) {
 436                 il = stack[layer];
 437                 il->bitmap &= ~(1 << idr_pos(id, layer));
 438         }
 439         error = 0;
 440 out:
 441         mtx_unlock(&idr->lock);
 442 #ifdef INVARIANTS
 443         if (error == 0 && idr_find(idr, id) != ptr) {
 444                 panic("idr_get_new_above: Failed for idr %p, id %d, ptr %p\n",
 445                     idr, id, ptr);
 446         }
 447 #endif
 448         return (error);
 449 }