sys/libkern/linux_idr.c

   1 /*
   2  * Copyright (c) 2005-2012 The DragonFly Project.
   3  * Copyright (c) 2013 François Tigeot
   4  * Copyright (c) 2013 Matthew Dillon
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The DragonFly Project
   8  * by Jeffrey Hsu.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  *
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in
  18  *    the documentation and/or other materials provided with the
  19  *    distribution.
  20  * 3. Neither the name of The DragonFly Project nor the names of its
  21  *    contributors may be used to endorse or promote products derived
  22  *    from this software without specific, prior written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  25  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  26  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  27  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  28  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  29  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  30  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  31  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  32  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  33  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  34  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  35  * SUCH DAMAGE.
  36  */
  37
  38 #ifdef USERLAND_TEST
  39 /*
  40  * Testing:
  41  *
  42  * cc -I. -DUSERLAND_TEST libkern/linux_idr.c -o /tmp/idr -g
  43  */
  44
  45 #define _KERNEL
  46 #define _KERNEL_STRUCTURES
  47 #define KLD_MODULE
  48 #include <stdio.h>
  49 #include <stdlib.h>
  50 #include <unistd.h>
  51 #include <string.h>
  52 #include <limits.h>
  53 #include <assert.h>
  54 #include <sys/idr.h>
  55 #include <sys/errno.h>
  56
  57 #undef MALLOC_DEFINE
  58 #define MALLOC_DEFINE(a, b, c)
  59 #define lwkt_gettoken(x)
  60 #define lwkt_reltoken(x)
  61 #define kmalloc(bytes, zone, flags)     calloc(bytes, 1)
  62 #define lwkt_token_init(a, b)
  63 #define lwkt_token_uninit(a)
  64 #define kfree(ptr, flags)               free(ptr)
  65 #define KKASSERT(a)
  66 #define panic(str, ...)                 assert(0)
  67 #define min(a, b)       (((a) < (b)) ? (a) : (b))
  68 #define max(a, b)       (((a) > (b)) ? (a) : (b))
  69
  70 int
  71 main(int ac, char **av)
  72 {
  73         char buf[256];
  74         struct idr idr;
  75         intptr_t generation = 0x10000000;
  76         int error;
  77         int id;
  78
  79         idr_init(&idr);
  80
  81         printf("cmd> ");
  82         fflush(stdout);
  83         while (fgets(buf, sizeof(buf), stdin) != NULL) {
  84                 if (sscanf(buf, "a %d", &id) == 1) {
  85                         for (;;) {
  86                                 if (idr_pre_get(&idr, 0) == 0) {
  87                                         fprintf(stderr, "pre_get failed\n");
  88                                         exit(1);
  89                                 }
  90                                 error = idr_get_new_above(&idr,
  91                                                           (void *)generation,
  92                                                           id, &id);
  93                                 if (error == -EAGAIN)
  94                                         continue;
  95                                 if (error) {
  96                                         fprintf(stderr, "get_new err %d\n",
  97                                                 error);
  98                                         exit(1);
  99                                 }
 100                                 printf("allocated %d value %08x\n",
 101                                         id, (int)generation);
 102                                 ++generation;
 103                                 break;
 104                         }
 105                 } else if (sscanf(buf, "f %d", &id) == 1) {
 106                         idr_remove(&idr, id);
 107                 } else if (sscanf(buf, "g %d", &id) == 1) {
 108                         void *res = idr_find(&idr, id);
 109                         printf("find %d res %p\n", id, res);
 110                 }
 111                 printf("cmd> ");
 112                 fflush(stdout);
 113         }
 114         return 0;
 115 }
 116
 117 #else
 118
 119 #include <sys/idr.h>
 120 #include <sys/kernel.h>
 121 #include <sys/libkern.h>
 122 #include <sys/malloc.h>
 123 #include <sys/param.h>
 124 #include <sys/systm.h>
 125 #include <sys/spinlock2.h>
 126 #include <sys/limits.h>
 127
 128 #endif
 129
 130 /* Must be 2^n - 1 */
 131 #define IDR_DEFAULT_SIZE    255
 132
 133 MALLOC_DEFINE(M_IDR, "idr", "Integer ID management");
 134
 135 static void     idr_grow(struct idr *idp, int want);
 136 static void     idr_reserve(struct idr *idp, int id, int incr);
 137 static int      idr_find_free(struct idr *idp, int want, int lim);
 138
 139 /*
 140  * Number of nodes in right subtree, including the root.
 141  */
 142 static __inline int
 143 right_subtree_size(int n)
 144 {
 145         return (n ^ (n | (n + 1)));
 146 }
 147
 148 /*
 149  * Bigger ancestor.
 150  */
 151 static __inline int
 152 right_ancestor(int n)
 153 {
 154         return (n | (n + 1));
 155 }
 156
 157 /*
 158  * Smaller ancestor.
 159  */
 160 static __inline int
 161 left_ancestor(int n)
 162 {
 163         return ((n & (n + 1)) - 1);
 164 }
 165
 166 static __inline void
 167 idrfixup(struct idr *idp, int id)
 168 {
 169         if (id < idp->idr_freeindex) {
 170                 idp->idr_freeindex = id;
 171         }
 172         while (idp->idr_lastindex >= 0 &&
 173                 idp->idr_nodes[idp->idr_lastindex].data == NULL
 174         ) {
 175                 --idp->idr_lastindex;
 176         }
 177 }
 178
 179 static __inline struct idr_node *
 180 idr_get_node(struct idr *idp, int id)
 181 {
 182         struct idr_node *idrnp;
 183         if (id < 0 || id >= idp->idr_count)
 184                 return (NULL);
 185         idrnp = &idp->idr_nodes[id];
 186         if (idrnp->allocated == 0)
 187                 return (NULL);
 188         return (idrnp);
 189 }
 190
 191 static void
 192 idr_reserve(struct idr *idp, int id, int incr)
 193 {
 194         while (id >= 0) {
 195                 idp->idr_nodes[id].allocated += incr;
 196                 KKASSERT(idp->idr_nodes[id].allocated >= 0);
 197                 id = left_ancestor(id);
 198         }
 199 }
 200
 201 static int
 202 idr_find_free(struct idr *idp, int want, int lim)
 203 {
 204         int id, rsum, rsize, node;
 205
 206         /*
 207          * Search for a free descriptor starting at the higher
 208          * of want or fd_freefile.  If that fails, consider
 209          * expanding the ofile array.
 210          *
 211          * NOTE! the 'allocated' field is a cumulative recursive allocation
 212          * count.  If we happen to see a value of 0 then we can shortcut
 213          * our search.  Otherwise we run through through the tree going
 214          * down branches we know have free descriptor(s) until we hit a
 215          * leaf node.  The leaf node will be free but will not necessarily
 216          * have an allocated field of 0.
 217          */
 218
 219         /* move up the tree looking for a subtree with a free node */
 220         for (id = max(want, idp->idr_freeindex); id < min(idp->idr_count, lim);
 221                         id = right_ancestor(id)) {
 222                 if (idp->idr_nodes[id].allocated == 0)
 223                         return (id);
 224
 225                 rsize = right_subtree_size(id);
 226                 if (idp->idr_nodes[id].allocated == rsize)
 227                         continue;       /* right subtree full */
 228
 229                 /*
 230                  * Free fd is in the right subtree of the tree rooted at fd.
 231                  * Call that subtree R.  Look for the smallest (leftmost)
 232                  * subtree of R with an unallocated fd: continue moving
 233                  * down the left branch until encountering a full left
 234                  * subtree, then move to the right.
 235                  */
 236                 for (rsum = 0, rsize /= 2; rsize > 0; rsize /= 2) {
 237                         node = id + rsize;
 238                         rsum += idp->idr_nodes[node].allocated;
 239                         if (idp->idr_nodes[id].allocated == rsum + rsize) {
 240                                 id = node;      /* move to the right */
 241                                 if (idp->idr_nodes[node].allocated == 0)
 242                                         return (id);
 243                                 rsum = 0;
 244                         }
 245                 }
 246                 return (id);
 247         }
 248         return (-1);
 249 }
 250
 251 /*
 252  * Blocking pre-get support, allows callers to use idr_pre_get() in
 253  * combination with idr_get_new_above() such that idr_get_new_above()
 254  * can be called safely with a spinlock held.
 255  *
 256  * Returns 0 on failure, 1 on success.
 257  *
 258  * Caller must hold a blockable lock.
 259  */
 260 int
 261 idr_pre_get(struct idr *idp, __unused unsigned gfp_mask)
 262 {
 263         int want = idp->idr_maxwant;
 264         int lim = INT_MAX;
 265         int result = 1;                         /* success */
 266         int id;
 267
 268         KKASSERT(mycpu->gd_spinlocks == 0);
 269         lwkt_gettoken(&idp->idr_token);
 270         for (;;) {
 271                 /*
 272                  * Grow if necessary (or if forced by the loop)
 273                  */
 274                 if (want >= idp->idr_count)
 275                         idr_grow(idp, want);
 276
 277                 /*
 278                  * Check if a spot is available, break and return 0 if true,
 279                  * unless the available spot is beyond our limit.  It is
 280                  * possible to exceed the limit due to the way array growth
 281                  * works.
 282                  *
 283                  * XXX we assume that the caller uses a consistent <sid> such
 284                  *     that the idr_maxwant field is correct, otherwise we
 285                  *     may believe that a slot is available but the caller then
 286                  *     fails in idr_get_new_above() and loops.
 287                  */
 288                 id = idr_find_free(idp, idp->idr_maxwant, lim);
 289                 if (id != -1) {
 290                         if (id >= lim)
 291                                 result = 0;     /* failure */
 292                         break;
 293                 }
 294
 295                 /*
 296                  * Return ENOSPC if our limit has been reached, otherwise
 297                  * loop and force growth.
 298                  */
 299                 if (idp->idr_count >= lim) {
 300                         result = 0;             /* failure */
 301                         break;
 302                 }
 303                 want = idp->idr_count;
 304         }
 305         lwkt_reltoken(&idp->idr_token);
 306         return result;
 307 }
 308
 309 /*
 310  * Allocate an integer.  If -EAGAIN is returned the caller should loop
 311  * and call idr_pre_get() with no locks held, and then retry the call
 312  * to idr_get_new_above().
 313  *
 314  * Can be safely called with spinlocks held.
 315  */
 316 int
 317 idr_get_new_above(struct idr *idp, void *ptr, int sid, int *id)
 318 {
 319         int resid;
 320
 321         /*
 322          * NOTE! Because the idp is initialized with a non-zero count,
 323          *       sid might be < idp->idr_count but idr_maxwant might not
 324          *       yet be initialized.  So check both cases.
 325          */
 326         lwkt_gettoken(&idp->idr_token);
 327         if (sid >= idp->idr_count || idp->idr_maxwant < sid) {
 328                 idp->idr_maxwant = max(idp->idr_maxwant, sid);
 329                 lwkt_reltoken(&idp->idr_token);
 330                 return -EAGAIN;
 331         }
 332
 333         resid = idr_find_free(idp, sid, INT_MAX);
 334         if (resid == -1) {
 335                 lwkt_reltoken(&idp->idr_token);
 336                 return -EAGAIN;
 337         }
 338
 339         if (resid >= idp->idr_count)
 340                 panic("idr_get_new_above(): illegal resid %d", resid);
 341         if (resid > idp->idr_lastindex)
 342                 idp->idr_lastindex = resid;
 343         if (sid <= idp->idr_freeindex)
 344                 idp->idr_freeindex = resid;
 345         *id = resid;
 346         idr_reserve(idp, resid, 1);
 347         idp->idr_nodes[resid].data = ptr;
 348
 349         lwkt_reltoken(&idp->idr_token);
 350         return (0);
 351 }
 352
 353 /*
 354  * start: minimum id, inclusive
 355  * end:   maximum id, exclusive or INT_MAX if end is negative
 356  */
 357 int
 358 idr_alloc(struct idr *idp, void *ptr, int start, int end, unsigned gfp_mask)
 359 {
 360         int lim = end > 0 ? end - 1 : INT_MAX;
 361         int result, id;
 362
 363         if (start < 0)
 364                 return -EINVAL;
 365
 366         if (lim < start)
 367                 return -ENOSPC;
 368
 369         lwkt_gettoken(&idp->idr_token);
 370
 371         /*
 372          * Grow if necessary (or if forced by the loop)
 373          */
 374         if (start >= idp->idr_count)
 375                 idr_grow(idp, start);
 376
 377         /*
 378          * Check if a spot is available, break and return 0 if true,
 379          * unless the available spot is beyond our limit.  It is
 380          * possible to exceed the limit due to the way array growth
 381          * works.
 382          */
 383         id = idr_find_free(idp, start, lim);
 384         if (id == -1) {
 385                 result = -ENOSPC;
 386                 goto done;
 387         }
 388
 389         if (id >= lim) {
 390                 result = -ENOSPC;
 391                 goto done;
 392         }
 393
 394         if (id >= idp->idr_count)
 395                 panic("idr_get_new_above(): illegal resid %d", id);
 396         if (id > idp->idr_lastindex)
 397                 idp->idr_lastindex = id;
 398         if (start <= idp->idr_freeindex)
 399                 idp->idr_freeindex = id;
 400         result = id;
 401         idr_reserve(idp, id, 1);
 402         idp->idr_nodes[id].data = ptr;
 403
 404 done:
 405         lwkt_reltoken(&idp->idr_token);
 406         return result;
 407 }
 408
 409 int
 410 idr_get_new(struct idr *idp, void *ptr, int *id)
 411 {
 412         return idr_get_new_above(idp, ptr, 0, id);
 413 }
 414
 415 /*
 416  * Grow the file table so it can hold through descriptor (want).
 417  *
 418  * Caller must hold a blockable lock.
 419  */
 420 static void
 421 idr_grow(struct idr *idp, int want)
 422 {
 423         struct idr_node *oldnodes, *newnodes;
 424         int nf;
 425
 426         /* We want 2^n - 1 descriptors */
 427         nf = idp->idr_count;
 428         do {
 429                 nf = 2 * nf + 1;
 430         } while (nf <= want);
 431
 432 #ifdef USERLAND_TEST
 433         printf("idr_grow: %d -> %d\n", idp->idr_count, nf);
 434 #endif
 435
 436         /* Allocate a new zero'ed node array */
 437         newnodes = kmalloc(nf * sizeof(struct idr_node),
 438                            M_IDR, M_ZERO | M_WAITOK);
 439
 440         /* We might race another grow */
 441         if (nf <= idp->idr_count) {
 442                 kfree(newnodes, M_IDR);
 443                 return;
 444         }
 445
 446         /*
 447          * Copy existing nodes to the beginning of the new array
 448          */
 449         oldnodes = idp->idr_nodes;
 450         if (oldnodes) {
 451                 bcopy(oldnodes, newnodes,
 452                       idp->idr_count * sizeof(struct idr_node));
 453         }
 454         idp->idr_nodes = newnodes;
 455         idp->idr_count = nf;
 456
 457         if (oldnodes) {
 458                 kfree(oldnodes, M_IDR);
 459         }
 460         idp->idr_nexpands++;
 461 }
 462
 463 void
 464 idr_remove(struct idr *idp, int id)
 465 {
 466         void *ptr;
 467
 468         lwkt_gettoken(&idp->idr_token);
 469         if (id < 0 || id >= idp->idr_count) {
 470                 lwkt_reltoken(&idp->idr_token);
 471                 return;
 472         }
 473         if ((ptr = idp->idr_nodes[id].data) == NULL) {
 474                 lwkt_reltoken(&idp->idr_token);
 475                 return;
 476         }
 477         idp->idr_nodes[id].data = NULL;
 478         idr_reserve(idp, id, -1);
 479         idrfixup(idp, id);
 480         lwkt_reltoken(&idp->idr_token);
 481 }
 482
 483 /*
 484  * Remove all int allocations, leave array intact.
 485  *
 486  * Caller must hold a blockable lock (or be in a context where holding
 487  * the spinlock is not relevant).
 488  */
 489 void
 490 idr_remove_all(struct idr *idp)
 491 {
 492         lwkt_gettoken(&idp->idr_token);
 493         bzero(idp->idr_nodes, idp->idr_count * sizeof(struct idr_node));
 494         idp->idr_lastindex = -1;
 495         idp->idr_freeindex = 0;
 496         idp->idr_nexpands = 0;
 497         idp->idr_maxwant = 0;
 498         lwkt_reltoken(&idp->idr_token);
 499 }
 500
 501 void
 502 idr_destroy(struct idr *idp)
 503 {
 504         lwkt_token_uninit(&idp->idr_token);
 505         if (idp->idr_nodes) {
 506                 kfree(idp->idr_nodes, M_IDR);
 507                 idp->idr_nodes = NULL;
 508         }
 509         bzero(idp, sizeof(*idp));
 510 }
 511
 512 void *
 513 idr_find(struct idr *idp, int id)
 514 {
 515         void *ret;
 516
 517         if (id < 0 || id >= idp->idr_count) {
 518                 ret = NULL;
 519         } else if (idp->idr_nodes[id].allocated == 0) {
 520                 ret = NULL;
 521         } else {
 522                 ret = idp->idr_nodes[id].data;
 523         }
 524         return ret;
 525 }
 526
 527 int
 528 idr_for_each(struct idr *idp, int (*fn)(int id, void *p, void *data),
 529              void *data)
 530 {
 531         int i, error = 0;
 532         struct idr_node *nodes;
 533
 534         nodes = idp->idr_nodes;
 535         for (i = 0; i < idp->idr_count; i++) {
 536                 if (nodes[i].data != NULL && nodes[i].allocated > 0) {
 537                         error = fn(i, nodes[i].data, data);
 538                         if (error != 0)
 539                                 break;
 540                 }
 541         }
 542         return error;
 543 }
 544
 545 void *
 546 idr_replace(struct idr *idp, void *ptr, int id)
 547 {
 548         struct idr_node *idrnp;
 549         void *ret;
 550
 551         lwkt_gettoken(&idp->idr_token);
 552         idrnp = idr_get_node(idp, id);
 553         if (idrnp == NULL || ptr == NULL) {
 554                 ret = NULL;
 555         } else {
 556                 ret = idrnp->data;
 557                 idrnp->data = ptr;
 558         }
 559         lwkt_reltoken(&idp->idr_token);
 560         return (ret);
 561 }
 562
 563 void
 564 idr_init(struct idr *idp)
 565 {
 566         bzero(idp, sizeof(struct idr));
 567         idp->idr_nodes = kmalloc(IDR_DEFAULT_SIZE * sizeof(struct idr_node),
 568                                                 M_IDR, M_WAITOK | M_ZERO);
 569         idp->idr_count = IDR_DEFAULT_SIZE;
 570         idp->idr_lastindex = -1;
 571         idp->idr_maxwant = 0;
 572         lwkt_token_init(&idp->idr_token, "idr token");
 573 }