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 void *
 231 idr_get_next(struct idr *idr, int *nextidp)
 232 {
 233         void *res = NULL;
 234         int id = *nextidp;
 235
 236         mtx_lock(&idr->lock);
 237         for (; id <= idr_max(idr); id++) {
 238                 res = idr_find_locked(idr, id);
 239                 if (res == NULL)
 240                         continue;
 241                 *nextidp = id;
 242                 break;
 243         }
 244         mtx_unlock(&idr->lock);
 245         return (res);
 246 }
 247
 248 int
 249 idr_pre_get(struct idr *idr, gfp_t gfp_mask)
 250 {
 251         struct idr_layer *il, *iln;
 252         struct idr_layer *head;
 253         int need;
 254
 255         mtx_lock(&idr->lock);
 256         for (;;) {
 257                 need = idr->layers + 1;
 258                 for (il = idr->free; il != NULL; il = il->ary[0])
 259                         need--;
 260                 mtx_unlock(&idr->lock);
 261                 if (need <= 0)
 262                         break;
 263                 for (head = NULL; need; need--) {
 264                         iln = malloc(sizeof(*il), M_IDR, M_ZERO | gfp_mask);
 265                         if (iln == NULL)
 266                                 break;
 267                         bitmap_fill(&iln->bitmap, IDR_SIZE);
 268                         if (head != NULL) {
 269                                 il->ary[0] = iln;
 270                                 il = iln;
 271                         } else
 272                                 head = il = iln;
 273                 }
 274                 if (head == NULL)
 275                         return (0);
 276                 mtx_lock(&idr->lock);
 277                 il->ary[0] = idr->free;
 278                 idr->free = head;
 279         }
 280         return (1);
 281 }
 282
 283 static inline struct idr_layer *
 284 idr_get(struct idr *idr)
 285 {
 286         struct idr_layer *il;
 287
 288         il = idr->free;
 289         if (il) {
 290                 idr->free = il->ary[0];
 291                 il->ary[0] = NULL;
 292                 return (il);
 293         }
 294         il = malloc(sizeof(*il), M_IDR, M_ZERO | M_NOWAIT);
 295         bitmap_fill(&il->bitmap, IDR_SIZE);
 296         return (il);
 297 }
 298
 299 /*
 300  * Could be implemented as get_new_above(idr, ptr, 0, idp) but written
 301  * first for simplicity sake.
 302  */
 303 static int
 304 idr_get_new_locked(struct idr *idr, void *ptr, int *idp)
 305 {
 306         struct idr_layer *stack[MAX_LEVEL];
 307         struct idr_layer *il;
 308         int error;
 309         int layer;
 310         int idx;
 311         int id;
 312
 313         mtx_assert(&idr->lock, MA_OWNED);
 314
 315         error = -EAGAIN;
 316         /*
 317          * Expand the tree until there is free space.
 318          */
 319         if (idr->top == NULL || idr->top->bitmap == 0) {
 320                 if (idr->layers == MAX_LEVEL + 1) {
 321                         error = -ENOSPC;
 322                         goto out;
 323                 }
 324                 il = idr_get(idr);
 325                 if (il == NULL)
 326                         goto out;
 327                 il->ary[0] = idr->top;
 328                 if (idr->top)
 329                         il->bitmap &= ~1;
 330                 idr->top = il;
 331                 idr->layers++;
 332         }
 333         il = idr->top;
 334         id = 0;
 335         /*
 336          * Walk the tree following free bitmaps, record our path.
 337          */
 338         for (layer = idr->layers - 1;; layer--) {
 339                 stack[layer] = il;
 340                 idx = ffsl(il->bitmap);
 341                 if (idx == 0)
 342                         panic("idr_get_new: Invalid leaf state (%p, %p)\n",
 343                             idr, il);
 344                 idx--;
 345                 id |= idx << (layer * IDR_BITS);
 346                 if (layer == 0)
 347                         break;
 348                 if (il->ary[idx] == NULL) {
 349                         il->ary[idx] = idr_get(idr);
 350                         if (il->ary[idx] == NULL)
 351                                 goto out;
 352                 }
 353                 il = il->ary[idx];
 354         }
 355         /*
 356          * Allocate the leaf to the consumer.
 357          */
 358         il->bitmap &= ~(1 << idx);
 359         il->ary[idx] = ptr;
 360         *idp = id;
 361         /*
 362          * Clear bitmaps potentially up to the root.
 363          */
 364         while (il->bitmap == 0 && ++layer < idr->layers) {
 365                 il = stack[layer];
 366                 il->bitmap &= ~(1 << idr_pos(id, layer));
 367         }
 368         error = 0;
 369 out:
 370 #ifdef INVARIANTS
 371         if (error == 0 && idr_find_locked(idr, id) != ptr) {
 372                 panic("idr_get_new: Failed for idr %p, id %d, ptr %p\n",
 373                     idr, id, ptr);
 374         }
 375 #endif
 376         return (error);
 377 }
 378
 379 int
 380 idr_get_new(struct idr *idr, void *ptr, int *idp)
 381 {
 382         int retval;
 383
 384         mtx_lock(&idr->lock);
 385         retval = idr_get_new_locked(idr, ptr, idp);
 386         mtx_unlock(&idr->lock);
 387         return (retval);
 388 }
 389
 390 static int
 391 idr_get_new_above_locked(struct idr *idr, void *ptr, int starting_id, int *idp)
 392 {
 393         struct idr_layer *stack[MAX_LEVEL];
 394         struct idr_layer *il;
 395         int error;
 396         int layer;
 397         int idx, sidx;
 398         int id;
 399
 400         mtx_assert(&idr->lock, MA_OWNED);
 401
 402         error = -EAGAIN;
 403         /*
 404          * Compute the layers required to support starting_id and the mask
 405          * at the top layer.
 406          */
 407 restart:
 408         idx = starting_id;
 409         layer = 0;
 410         while (idx & ~IDR_MASK) {
 411                 layer++;
 412                 idx >>= IDR_BITS;
 413         }
 414         if (layer == MAX_LEVEL + 1) {
 415                 error = -ENOSPC;
 416                 goto out;
 417         }
 418         /*
 419          * Expand the tree until there is free space at or beyond starting_id.
 420          */
 421         while (idr->layers <= layer ||
 422             idr->top->bitmap < (1 << idr_pos(starting_id, idr->layers - 1))) {
 423                 if (idr->layers == MAX_LEVEL + 1) {
 424                         error = -ENOSPC;
 425                         goto out;
 426                 }
 427                 il = idr_get(idr);
 428                 if (il == NULL)
 429                         goto out;
 430                 il->ary[0] = idr->top;
 431                 if (idr->top && idr->top->bitmap == 0)
 432                         il->bitmap &= ~1;
 433                 idr->top = il;
 434                 idr->layers++;
 435         }
 436         il = idr->top;
 437         id = 0;
 438         /*
 439          * Walk the tree following free bitmaps, record our path.
 440          */
 441         for (layer = idr->layers - 1;; layer--) {
 442                 stack[layer] = il;
 443                 sidx = idr_pos(starting_id, layer);
 444                 /* Returns index numbered from 0 or size if none exists. */
 445                 idx = find_next_bit(&il->bitmap, IDR_SIZE, sidx);
 446                 if (idx == IDR_SIZE && sidx == 0)
 447                         panic("idr_get_new: Invalid leaf state (%p, %p)\n",
 448                             idr, il);
 449                 /*
 450                  * We may have walked a path where there was a free bit but
 451                  * it was lower than what we wanted.  Restart the search with
 452                  * a larger starting id.  id contains the progress we made so
 453                  * far.  Search the leaf one above this level.  This may
 454                  * restart as many as MAX_LEVEL times but that is expected
 455                  * to be rare.
 456                  */
 457                 if (idx == IDR_SIZE) {
 458                         starting_id = id + (1 << ((layer + 1) * IDR_BITS));
 459                         goto restart;
 460                 }
 461                 if (idx > sidx)
 462                         starting_id = 0;        /* Search the whole subtree. */
 463                 id |= idx << (layer * IDR_BITS);
 464                 if (layer == 0)
 465                         break;
 466                 if (il->ary[idx] == NULL) {
 467                         il->ary[idx] = idr_get(idr);
 468                         if (il->ary[idx] == NULL)
 469                                 goto out;
 470                 }
 471                 il = il->ary[idx];
 472         }
 473         /*
 474          * Allocate the leaf to the consumer.
 475          */
 476         il->bitmap &= ~(1 << idx);
 477         il->ary[idx] = ptr;
 478         *idp = id;
 479         /*
 480          * Clear bitmaps potentially up to the root.
 481          */
 482         while (il->bitmap == 0 && ++layer < idr->layers) {
 483                 il = stack[layer];
 484                 il->bitmap &= ~(1 << idr_pos(id, layer));
 485         }
 486         error = 0;
 487 out:
 488 #ifdef INVARIANTS
 489         if (error == 0 && idr_find_locked(idr, id) != ptr) {
 490                 panic("idr_get_new_above: Failed for idr %p, id %d, ptr %p\n",
 491                     idr, id, ptr);
 492         }
 493 #endif
 494         return (error);
 495 }
 496
 497 int
 498 idr_get_new_above(struct idr *idr, void *ptr, int starting_id, int *idp)
 499 {
 500         int retval;
 501
 502         mtx_lock(&idr->lock);
 503         retval = idr_get_new_above_locked(idr, ptr, starting_id, idp);
 504         mtx_unlock(&idr->lock);
 505         return (retval);
 506 }
 507
 508 int
 509 ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
 510 {
 511         return (idr_get_new_above(&ida->idr, NULL, starting_id, p_id));
 512 }
 513
 514 static int
 515 idr_alloc_locked(struct idr *idr, void *ptr, int start, int end)
 516 {
 517         int max = end > 0 ? end - 1 : INT_MAX;
 518         int error;
 519         int id;
 520
 521         mtx_assert(&idr->lock, MA_OWNED);
 522
 523         if (unlikely(start < 0))
 524                 return (-EINVAL);
 525         if (unlikely(max < start))
 526                 return (-ENOSPC);
 527
 528         if (start == 0)
 529                 error = idr_get_new_locked(idr, ptr, &id);
 530         else
 531                 error = idr_get_new_above_locked(idr, ptr, start, &id);
 532
 533         if (unlikely(error < 0))
 534                 return (error);
 535         if (unlikely(id > max)) {
 536                 idr_remove_locked(idr, id);
 537                 return (-ENOSPC);
 538         }
 539         return (id);
 540 }
 541
 542 int
 543 idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
 544 {
 545         int retval;
 546
 547         mtx_lock(&idr->lock);
 548         retval = idr_alloc_locked(idr, ptr, start, end);
 549         mtx_unlock(&idr->lock);
 550         return (retval);
 551 }
 552
 553 int
 554 idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
 555 {
 556         int retval;
 557
 558         mtx_lock(&idr->lock);
 559         retval = idr_alloc_locked(idr, ptr, max(start, idr->next_cyclic_id), end);
 560         if (unlikely(retval == -ENOSPC))
 561                 retval = idr_alloc_locked(idr, ptr, start, end);
 562         if (likely(retval >= 0))
 563                 idr->next_cyclic_id = retval + 1;
 564         mtx_unlock(&idr->lock);
 565         return (retval);
 566 }
 567
 568 static int
 569 idr_for_each_layer(struct idr_layer *il, int layer,
 570     int (*f)(int id, void *p, void *data), void *data)
 571 {
 572         int i, err;
 573
 574         if (il == NULL)
 575                 return (0);
 576         if (layer == 0) {
 577                 for (i = 0; i < IDR_SIZE; i++) {
 578                         if (il->ary[i] == NULL)
 579                                 continue;
 580                         err = f(i, il->ary[i],  data);
 581                         if (err)
 582                                 return (err);
 583                 }
 584                 return (0);
 585         }
 586         for (i = 0; i < IDR_SIZE; i++) {
 587                 if (il->ary[i] == NULL)
 588                         continue;
 589                 err = idr_for_each_layer(il->ary[i], layer - 1, f, data);
 590                 if (err)
 591                         return (err);
 592         }
 593         return (0);
 594 }
 595
 596 /* NOTE: It is not allowed to modify the IDR tree while it is being iterated */
 597 int
 598 idr_for_each(struct idr *idp, int (*f)(int id, void *p, void *data), void *data)
 599 {
 600         return (idr_for_each_layer(idp->top, idp->layers - 1, f, data));
 601 }
 602
 603 int
 604 ida_pre_get(struct ida *ida, gfp_t flags)
 605 {
 606         if (idr_pre_get(&ida->idr, flags) == 0)
 607                 return (0);
 608
 609         if (ida->free_bitmap == NULL) {
 610                 ida->free_bitmap =
 611                     malloc(sizeof(struct ida_bitmap), M_IDR, flags);
 612         }
 613         return (ida->free_bitmap != NULL);
 614 }
 615
 616 int
 617 ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
 618     gfp_t flags)
 619 {
 620         int ret, id;
 621         unsigned int max;
 622
 623         MPASS((int)start >= 0);
 624         MPASS((int)end >= 0);
 625
 626         if (end == 0)
 627                 max = 0x80000000;
 628         else {
 629                 MPASS(end > start);
 630                 max = end - 1;
 631         }
 632 again:
 633         if (!ida_pre_get(ida, flags))
 634                 return (-ENOMEM);
 635
 636         if ((ret = ida_get_new_above(ida, start, &id)) == 0) {
 637                 if (id > max) {
 638                         ida_remove(ida, id);
 639                         ret = -ENOSPC;
 640                 } else {
 641                         ret = id;
 642                 }
 643         }
 644         if (__predict_false(ret == -EAGAIN))
 645                 goto again;
 646
 647         return (ret);
 648 }
 649
 650 void
 651 ida_simple_remove(struct ida *ida, unsigned int id)
 652 {
 653         idr_remove(&ida->idr, id);
 654 }
 655
 656 void
 657 ida_remove(struct ida *ida, int id)
 658 {
 659         idr_remove(&ida->idr, id);
 660 }
 661
 662 void
 663 ida_init(struct ida *ida)
 664 {
 665         idr_init(&ida->idr);
 666 }
 667
 668 void
 669 ida_destroy(struct ida *ida)
 670 {
 671         idr_destroy(&ida->idr);
 672         free(ida->free_bitmap, M_IDR);
 673 }