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 int
 354 idr_get_new(struct idr *idp, void *ptr, int *id)
 355 {
 356         return idr_get_new_above(idp, ptr, 0, id);
 357 }
 358
 359 /*
 360  * Grow the file table so it can hold through descriptor (want).
 361  *
 362  * Caller must hold a blockable lock.
 363  */
 364 static void
 365 idr_grow(struct idr *idp, int want)
 366 {
 367         struct idr_node *oldnodes, *newnodes;
 368         int nf;
 369
 370         /* We want 2^n - 1 descriptors */
 371         nf = idp->idr_count;
 372         do {
 373                 nf = 2 * nf + 1;
 374         } while (nf <= want);
 375
 376 #ifdef USERLAND_TEST
 377         printf("idr_grow: %d -> %d\n", idp->idr_count, nf);
 378 #endif
 379
 380         /* Allocate a new zero'ed node array */
 381         newnodes = kmalloc(nf * sizeof(struct idr_node),
 382                            M_IDR, M_ZERO | M_WAITOK);
 383
 384         /* We might race another grow */
 385         if (nf <= idp->idr_count) {
 386                 kfree(newnodes, M_IDR);
 387                 return;
 388         }
 389
 390         /*
 391          * Copy existing nodes to the beginning of the new array
 392          */
 393         oldnodes = idp->idr_nodes;
 394         if (oldnodes) {
 395                 bcopy(oldnodes, newnodes,
 396                       idp->idr_count * sizeof(struct idr_node));
 397         }
 398         idp->idr_nodes = newnodes;
 399         idp->idr_count = nf;
 400
 401         if (oldnodes) {
 402                 kfree(oldnodes, M_IDR);
 403         }
 404         idp->idr_nexpands++;
 405 }
 406
 407 void
 408 idr_remove(struct idr *idp, int id)
 409 {
 410         void *ptr;
 411
 412         lwkt_gettoken(&idp->idr_token);
 413         if (id < 0 || id >= idp->idr_count) {
 414                 lwkt_reltoken(&idp->idr_token);
 415                 return;
 416         }
 417         if ((ptr = idp->idr_nodes[id].data) == NULL) {
 418                 lwkt_reltoken(&idp->idr_token);
 419                 return;
 420         }
 421         idp->idr_nodes[id].data = NULL;
 422         idr_reserve(idp, id, -1);
 423         idrfixup(idp, id);
 424         lwkt_reltoken(&idp->idr_token);
 425 }
 426
 427 /*
 428  * Remove all int allocations, leave array intact.
 429  *
 430  * Caller must hold a blockable lock (or be in a context where holding
 431  * the spinlock is not relevant).
 432  */
 433 void
 434 idr_remove_all(struct idr *idp)
 435 {
 436         lwkt_gettoken(&idp->idr_token);
 437         bzero(idp->idr_nodes, idp->idr_count * sizeof(struct idr_node));
 438         idp->idr_lastindex = -1;
 439         idp->idr_freeindex = 0;
 440         idp->idr_nexpands = 0;
 441         idp->idr_maxwant = 0;
 442         lwkt_reltoken(&idp->idr_token);
 443 }
 444
 445 void
 446 idr_destroy(struct idr *idp)
 447 {
 448         lwkt_token_uninit(&idp->idr_token);
 449         if (idp->idr_nodes) {
 450                 kfree(idp->idr_nodes, M_IDR);
 451                 idp->idr_nodes = NULL;
 452         }
 453         bzero(idp, sizeof(*idp));
 454 }
 455
 456 void *
 457 idr_find(struct idr *idp, int id)
 458 {
 459         void *ret;
 460
 461         if (id < 0 || id >= idp->idr_count) {
 462                 ret = NULL;
 463         } else if (idp->idr_nodes[id].allocated == 0) {
 464                 ret = NULL;
 465         } else {
 466                 ret = idp->idr_nodes[id].data;
 467         }
 468         return ret;
 469 }
 470
 471 int
 472 idr_for_each(struct idr *idp, int (*fn)(int id, void *p, void *data),
 473              void *data)
 474 {
 475         int i, error = 0;
 476         struct idr_node *nodes;
 477
 478         nodes = idp->idr_nodes;
 479         for (i = 0; i < idp->idr_count; i++) {
 480                 if (nodes[i].data != NULL && nodes[i].allocated > 0) {
 481                         error = fn(i, nodes[i].data, data);
 482                         if (error != 0)
 483                                 break;
 484                 }
 485         }
 486         return error;
 487 }
 488
 489 void *
 490 idr_replace(struct idr *idp, void *ptr, int id)
 491 {
 492         struct idr_node *idrnp;
 493         void *ret;
 494
 495         lwkt_gettoken(&idp->idr_token);
 496         idrnp = idr_get_node(idp, id);
 497         if (idrnp == NULL || ptr == NULL) {
 498                 ret = NULL;
 499         } else {
 500                 ret = idrnp->data;
 501                 idrnp->data = ptr;
 502         }
 503         lwkt_reltoken(&idp->idr_token);
 504         return (ret);
 505 }
 506
 507 void
 508 idr_init(struct idr *idp)
 509 {
 510         bzero(idp, sizeof(struct idr));
 511         idp->idr_nodes = kmalloc(IDR_DEFAULT_SIZE * sizeof(struct idr_node),
 512                                                 M_IDR, M_WAITOK | M_ZERO);
 513         idp->idr_count = IDR_DEFAULT_SIZE;
 514         idp->idr_lastindex = -1;
 515         idp->idr_maxwant = 0;
 516         lwkt_token_init(&idp->idr_token, "idr token");
 517 }