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 static inline void *
 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 *
 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
 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 *
 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
 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
 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 }