sys/libkern/idr.c

   1 /*
   2  * Copyright (c) 2005-2012 The DragonFly Project.
   3  * Copyright (c) 2013 François Tigeot
   4  * All rights reserved.
   5  *
   6  * This code is derived from software contributed to The DragonFly Project
   7  * by Jeffrey Hsu.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  *
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in
  17  *    the documentation and/or other materials provided with the
  18  *    distribution.
  19  * 3. Neither the name of The DragonFly Project nor the names of its
  20  *    contributors may be used to endorse or promote products derived
  21  *    from this software without specific, prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  26  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  27  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  28  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  29  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  30  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  31  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  32  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  33  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34  * SUCH DAMAGE.
  35  *
  36  */
  37
  38 #include <sys/idr.h>
  39 #include <sys/kernel.h>
  40 #include <sys/libkern.h>
  41 #include <sys/malloc.h>
  42 #include <sys/param.h>
  43 #include <sys/systm.h>
  44 #include <sys/spinlock2.h>
  45 #include <sys/limits.h>
  46
  47 #define IDR_DEFAULT_SIZE    256
  48
  49 MALLOC_DEFINE(M_IDR, "idr", "Integer ID management");
  50
  51 static void     idr_grow(struct idr *idp, int want);
  52 static void     idr_reserve(struct idr *idp, int id, int incr);
  53 static void     idr_set(struct idr *idp, int id, void *ptr);
  54 static int      idr_find_free(struct idr *idp, int want, int lim);
  55 static int      idr_pre_get1(struct idr *idp, int want, int lim);
  56
  57 /*
  58  * Number of nodes in right subtree, including the root.
  59  */
  60 static __inline int
  61 right_subtree_size(int n)
  62 {
  63         return (n ^ (n | (n + 1)));
  64 }
  65
  66 /*
  67  * Bigger ancestor.
  68  */
  69 static __inline int
  70 right_ancestor(int n)
  71 {
  72         return (n | (n + 1));
  73 }
  74
  75 /*
  76  * Smaller ancestor.
  77  */
  78 static __inline int
  79 left_ancestor(int n)
  80 {
  81         return ((n & (n + 1)) - 1);
  82 }
  83
  84 static __inline void
  85 idrfixup(struct idr *idp, int id)
  86 {
  87         if (id < idp->idr_freeindex) {
  88                 idp->idr_freeindex = id;
  89         }
  90         while (idp->idr_lastindex >= 0 &&
  91                 idp->idr_nodes[idp->idr_lastindex].data == NULL &&
  92                 idp->idr_nodes[idp->idr_lastindex].reserved == 0
  93         ) {
  94                 --idp->idr_lastindex;
  95         }
  96 }
  97
  98 static __inline struct idr_node *
  99 idr_get_node(struct idr *idp, int id)
 100 {
 101         struct idr_node *idrnp;
 102         if (id >= idp->idr_count)
 103                 return (NULL);
 104         idrnp = &idp->idr_nodes[id];
 105         if (idrnp->allocated == 0)
 106                 return (NULL);
 107         return (idrnp);
 108 }
 109
 110 static void
 111 idr_reserve(struct idr *idp, int id, int incr)
 112 {
 113         while (id >= 0) {
 114                 idp->idr_nodes[id].allocated += incr;
 115                 KKASSERT(idp->idr_nodes[id].allocated >= 0);
 116                 id = left_ancestor(id);
 117         }
 118 }
 119
 120 static int
 121 idr_find_free(struct idr *idp, int want, int lim)
 122 {
 123         int id, rsum, rsize, node;
 124
 125         /*
 126          * Search for a free descriptor starting at the higher
 127          * of want or fd_freefile.  If that fails, consider
 128          * expanding the ofile array.
 129          *
 130          * NOTE! the 'allocated' field is a cumulative recursive allocation
 131          * count.  If we happen to see a value of 0 then we can shortcut
 132          * our search.  Otherwise we run through through the tree going
 133          * down branches we know have free descriptor(s) until we hit a
 134          * leaf node.  The leaf node will be free but will not necessarily
 135          * have an allocated field of 0.
 136          */
 137
 138         /* move up the tree looking for a subtree with a free node */
 139         for (id = max(want, idp->idr_freeindex); id < min(idp->idr_count, lim);
 140                         id = right_ancestor(id)) {
 141                 if (idp->idr_nodes[id].allocated == 0)
 142                         return (id);
 143
 144                 rsize = right_subtree_size(id);
 145                 if (idp->idr_nodes[id].allocated == rsize)
 146                         continue;       /* right subtree full */
 147
 148                 /*
 149                  * Free fd is in the right subtree of the tree rooted at fd.
 150                  * Call that subtree R.  Look for the smallest (leftmost)
 151                  * subtree of R with an unallocated fd: continue moving
 152                  * down the left branch until encountering a full left
 153                  * subtree, then move to the right.
 154                  */
 155                 for (rsum = 0, rsize /= 2; rsize > 0; rsize /= 2) {
 156                         node = id + rsize;
 157                         rsum += idp->idr_nodes[node].allocated;
 158                         if (idp->idr_nodes[id].allocated == rsum + rsize) {
 159                                 id = node;      /* move to the right */
 160                                 if (idp->idr_nodes[node].allocated == 0)
 161                                         return (id);
 162                                 rsum = 0;
 163                         }
 164                 }
 165                 return (id);
 166         }
 167         return (-1);
 168 }
 169
 170 static int
 171 idr_pre_get1(struct idr *idp, int want, int lim)
 172 {
 173         int id;
 174
 175         if (want >= idp->idr_count)
 176                 idr_grow(idp, want);
 177
 178 retry:
 179         id = idr_find_free(idp, want, lim);
 180         if (id > -1)
 181                 goto found;
 182
 183         /*
 184          * No space in current array.  Expand?
 185          */
 186         if (idp->idr_count >= lim) {
 187                 return (ENOSPC);
 188         }
 189         idr_grow(idp, want);
 190         goto retry;
 191
 192 found:
 193         return (0);
 194 }
 195
 196 int
 197 idr_pre_get(struct idr *idp)
 198 {
 199         lwkt_gettoken(&idp->idr_token);
 200         int error = idr_pre_get1(idp, idp->idr_maxwant, INT_MAX);
 201         lwkt_reltoken(&idp->idr_token);
 202         return (error == 0);
 203 }
 204
 205 int
 206 idr_get_new(struct idr *idp, void *ptr, int *id)
 207 {
 208         int resid;
 209
 210         if (ptr == NULL)
 211                 return (EINVAL);
 212
 213         lwkt_gettoken(&idp->idr_token);
 214         resid = idr_find_free(idp, 0, INT_MAX);
 215         if (resid == -1) {
 216                 lwkt_reltoken(&idp->idr_token);
 217                 return (EAGAIN);
 218         }
 219
 220         if (resid > idp->idr_lastindex)
 221                 idp->idr_lastindex = resid;
 222         idp->idr_freeindex = resid;
 223         *id = resid;
 224         KKASSERT(idp->idr_nodes[resid].reserved == 0);
 225         idp->idr_nodes[resid].reserved = 1;
 226         idr_reserve(idp, resid, 1);
 227         idr_set(idp, resid, ptr);
 228
 229         lwkt_reltoken(&idp->idr_token);
 230         return (0);
 231 }
 232
 233 int
 234 idr_get_new_above(struct idr *idp, void *ptr, int sid, int *id)
 235 {
 236         int resid;
 237
 238         if (ptr == NULL)
 239                 return (EINVAL);
 240
 241         lwkt_gettoken(&idp->idr_token);
 242         if (sid >= idp->idr_count) {
 243                 idp->idr_maxwant = max(idp->idr_maxwant, sid);
 244                 lwkt_reltoken(&idp->idr_token);
 245                 return (EAGAIN);
 246         }
 247
 248         resid = idr_find_free(idp, sid, INT_MAX);
 249         if (resid == -1) {
 250                 lwkt_reltoken(&idp->idr_token);
 251                 return (EAGAIN);
 252         }
 253
 254         if (resid >= idp->idr_count)
 255                 idr_grow(idp, resid);
 256         if (resid > idp->idr_lastindex)
 257                 idp->idr_lastindex = resid;
 258         if (sid <= idp->idr_freeindex)
 259                 idp->idr_freeindex = resid;
 260         *id = resid;
 261         KKASSERT(idp->idr_nodes[resid].reserved == 0);
 262         idp->idr_nodes[resid].reserved = 1;
 263         idr_reserve(idp, resid, 1);
 264         idr_set(idp, resid, ptr);
 265
 266         lwkt_reltoken(&idp->idr_token);
 267         return (0);
 268 }
 269
 270 /*
 271  * Grow the file table so it can hold through descriptor (want).
 272  */
 273 static void
 274 idr_grow(struct idr *idp, int want)
 275 {
 276         struct idr_node *newnodes;
 277         struct idr_node *oldnodes;
 278         int nf, extra;
 279
 280         nf = idp->idr_count;
 281         do {
 282                 /* nf has to be of the form 2^n - 1 */
 283                 nf = 2 * nf + 1;
 284         } while (nf <= want);
 285
 286         newnodes = kmalloc(nf * sizeof(struct idr_node), M_IDR, M_WAITOK);
 287
 288         /*
 289          * Copy the existing ofile and ofileflags arrays
 290          * and zero the new portion of each array.
 291          */
 292         extra = nf - idp->idr_count;
 293         if (idp->idr_nodes != NULL)
 294                 bcopy(idp->idr_nodes, newnodes, idp->idr_count * sizeof(struct idr_node));
 295         bzero(&newnodes[idp->idr_count], extra * sizeof(struct idr_node));
 296
 297         oldnodes = idp->idr_nodes;
 298         idp->idr_nodes = newnodes;
 299         idp->idr_count = nf;
 300
 301         if (oldnodes != NULL) {
 302                 kfree(oldnodes, M_IDR);
 303         }
 304
 305         idp->idr_nexpands++;
 306 }
 307
 308 void
 309 idr_remove(struct idr *idp, int id)
 310 {
 311         void *ptr;
 312
 313         lwkt_gettoken(&idp->idr_token);
 314
 315         if (id >= idp->idr_count)
 316                 goto out;
 317         if ((ptr = idp->idr_nodes[id].data) == NULL)
 318                 goto out;
 319         idp->idr_nodes[id].data = NULL;
 320
 321         idr_reserve(idp, id, -1);
 322         idrfixup(idp, id);
 323
 324 out:
 325         lwkt_reltoken(&idp->idr_token);
 326 }
 327
 328 void
 329 idr_remove_all(struct idr *idp)
 330 {
 331         kfree(idp->idr_nodes, M_IDR);
 332         idp->idr_nodes = kmalloc(idp->idr_count * sizeof *idp, M_IDR, M_WAITOK | M_ZERO);
 333         idp->idr_lastindex = -1;
 334         idp->idr_freeindex = 0;
 335         idp->idr_nexpands = 0;
 336         idp->idr_maxwant = 0;
 337 }
 338
 339 void
 340 idr_destroy(struct idr *idp)
 341 {
 342         lwkt_token_uninit(&idp->idr_token);
 343         kfree(idp->idr_nodes, M_IDR);
 344         memset(idp, 0, sizeof(struct idr));
 345 }
 346
 347 void *
 348 idr_find(struct idr *idp, int id)
 349 {
 350         void * ret = NULL;
 351
 352         lwkt_gettoken(&idp->idr_token);
 353
 354         if (id > idp->idr_count) {
 355                 goto out;
 356         } else if (idp->idr_nodes[id].allocated == 0) {
 357                 goto out;
 358         }
 359         KKASSERT(idp->idr_nodes[id].data != NULL);
 360         ret = idp->idr_nodes[id].data;
 361
 362 out:
 363         lwkt_reltoken(&idp->idr_token);
 364         return ret;
 365 }
 366
 367 static void
 368 idr_set(struct idr *idp, int id, void *ptr)
 369 {
 370         KKASSERT(id < idp->idr_count);
 371         KKASSERT(idp->idr_nodes[id].reserved != 0);
 372         if (ptr) {
 373                 idp->idr_nodes[id].data = ptr;
 374                 idp->idr_nodes[id].reserved = 0;
 375         } else {
 376                 idp->idr_nodes[id].reserved = 0;
 377                 idr_reserve(idp, id, -1);
 378                 idrfixup(idp, id);
 379         }
 380 }
 381
 382 int
 383 idr_for_each(struct idr *idp, int (*fn)(int id, void *p, void *data), void *data)
 384 {
 385         int i, error = 0;
 386         struct idr_node *nodes = idp->idr_nodes;
 387
 388         lwkt_gettoken(&idp->idr_token);
 389         for (i = 0; i < idp->idr_count; i++) {
 390                 if (nodes[i].data != NULL && nodes[i].allocated > 0) {
 391                         error = fn(i, nodes[i].data, data);
 392                         if (error != 0)
 393                                 goto out;
 394                 }
 395         }
 396 out:
 397         lwkt_reltoken(&idp->idr_token);
 398         return error;
 399 }
 400
 401 void *
 402 idr_replace(struct idr *idp, void *ptr, int id)
 403 {
 404         struct idr_node *idrnp;
 405         void *ret = NULL;
 406
 407         lwkt_gettoken(&idp->idr_token);
 408
 409         idrnp = idr_get_node(idp, id);
 410         if (idrnp == NULL || ptr == NULL)
 411                 goto out;
 412
 413         ret = idrnp->data;
 414         idrnp->data = ptr;
 415
 416 out:
 417         lwkt_reltoken(&idp->idr_token);
 418         return (ret);
 419 }
 420
 421 void
 422 idr_init(struct idr *idp)
 423 {
 424         bzero(idp, sizeof(struct idr));
 425         idp->idr_nodes = kmalloc(IDR_DEFAULT_SIZE * sizeof(*idp),
 426                                                 M_IDR, M_WAITOK | M_ZERO);
 427         idp->idr_count = IDR_DEFAULT_SIZE;
 428         idp->idr_lastindex = -1;
 429         idp->idr_maxwant = 0;
 430         lwkt_token_init(&idp->idr_token, "idr token");
 431 }