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_lastindex)
 255                 idp->idr_lastindex = resid;
 256         if (sid <= idp->idr_freeindex)
 257                 idp->idr_freeindex = resid;
 258         *id = resid;
 259         KKASSERT(idp->idr_nodes[resid].reserved == 0);
 260         idp->idr_nodes[resid].reserved = 1;
 261         idr_reserve(idp, resid, 1);
 262         idr_set(idp, resid, ptr);
 263
 264         lwkt_reltoken(&idp->idr_token);
 265         return (0);
 266 }
 267
 268 /*
 269  * Grow the file table so it can hold through descriptor (want).
 270  */
 271 static void
 272 idr_grow(struct idr *idp, int want)
 273 {
 274         struct idr_node *newnodes;
 275         struct idr_node *oldnodes;
 276         int nf, extra;
 277
 278         nf = idp->idr_count;
 279         do {
 280                 /* nf has to be of the form 2^n - 1 */
 281                 nf = 2 * nf + 1;
 282         } while (nf <= want);
 283
 284         newnodes = kmalloc(nf * sizeof(struct idr_node), M_IDR, M_WAITOK);
 285
 286         /*
 287          * Copy the existing ofile and ofileflags arrays
 288          * and zero the new portion of each array.
 289          */
 290         extra = nf - idp->idr_count;
 291         if (idp->idr_nodes != NULL)
 292                 bcopy(idp->idr_nodes, newnodes, idp->idr_count * sizeof(struct idr_node));
 293         bzero(&newnodes[idp->idr_count], extra * sizeof(struct idr_node));
 294
 295         oldnodes = idp->idr_nodes;
 296         idp->idr_nodes = newnodes;
 297         idp->idr_count = nf;
 298
 299         if (oldnodes != NULL) {
 300                 kfree(oldnodes, M_IDR);
 301         }
 302
 303         idp->idr_nexpands++;
 304 }
 305
 306 void
 307 idr_remove(struct idr *idp, int id)
 308 {
 309         void *ptr;
 310
 311         lwkt_gettoken(&idp->idr_token);
 312
 313         if (id >= idp->idr_count)
 314                 goto out;
 315         if ((ptr = idp->idr_nodes[id].data) == NULL)
 316                 goto out;
 317         idp->idr_nodes[id].data = NULL;
 318
 319         idr_reserve(idp, id, -1);
 320         idrfixup(idp, id);
 321
 322 out:
 323         lwkt_reltoken(&idp->idr_token);
 324 }
 325
 326 void
 327 idr_remove_all(struct idr *idp)
 328 {
 329         kfree(idp->idr_nodes, M_IDR);
 330         idp->idr_nodes = kmalloc(idp->idr_count * sizeof *idp, M_IDR, M_WAITOK | M_ZERO);
 331         idp->idr_lastindex = -1;
 332         idp->idr_freeindex = 0;
 333         idp->idr_nexpands = 0;
 334         idp->idr_maxwant = 0;
 335 }
 336
 337 void
 338 idr_destroy(struct idr *idp)
 339 {
 340         lwkt_token_uninit(&idp->idr_token);
 341         kfree(idp->idr_nodes, M_IDR);
 342         memset(idp, 0, sizeof(struct idr));
 343 }
 344
 345 void *
 346 idr_find(struct idr *idp, int id)
 347 {
 348         void * ret = NULL;
 349
 350         lwkt_gettoken(&idp->idr_token);
 351
 352         if (id > idp->idr_count) {
 353                 goto out;
 354         } else if (idp->idr_nodes[id].allocated == 0) {
 355                 goto out;
 356         }
 357         KKASSERT(idp->idr_nodes[id].data != NULL);
 358         ret = idp->idr_nodes[id].data;
 359
 360 out:
 361         lwkt_reltoken(&idp->idr_token);
 362         return ret;
 363 }
 364
 365 static void
 366 idr_set(struct idr *idp, int id, void *ptr)
 367 {
 368         KKASSERT(id < idp->idr_count);
 369         KKASSERT(idp->idr_nodes[id].reserved != 0);
 370         if (ptr) {
 371                 idp->idr_nodes[id].data = ptr;
 372                 idp->idr_nodes[id].reserved = 0;
 373         } else {
 374                 idp->idr_nodes[id].reserved = 0;
 375                 idr_reserve(idp, id, -1);
 376                 idrfixup(idp, id);
 377         }
 378 }
 379
 380 int
 381 idr_for_each(struct idr *idp, int (*fn)(int id, void *p, void *data), void *data)
 382 {
 383         int i, error = 0;
 384         struct idr_node *nodes = idp->idr_nodes;
 385
 386         lwkt_gettoken(&idp->idr_token);
 387         for (i = 0; i < idp->idr_count; i++) {
 388                 if (nodes[i].data != NULL && nodes[i].allocated > 0) {
 389                         error = fn(i, nodes[i].data, data);
 390                         if (error != 0)
 391                                 goto out;
 392                 }
 393         }
 394 out:
 395         lwkt_reltoken(&idp->idr_token);
 396         return error;
 397 }
 398
 399 void *
 400 idr_replace(struct idr *idp, void *ptr, int id)
 401 {
 402         struct idr_node *idrnp;
 403         void *ret = NULL;
 404
 405         lwkt_gettoken(&idp->idr_token);
 406
 407         idrnp = idr_get_node(idp, id);
 408         if (idrnp == NULL || ptr == NULL)
 409                 goto out;
 410
 411         ret = idrnp->data;
 412         idrnp->data = ptr;
 413
 414 out:
 415         lwkt_reltoken(&idp->idr_token);
 416         return (ret);
 417 }
 418
 419 void
 420 idr_init(struct idr *idp)
 421 {
 422         bzero(idp, sizeof(struct idr));
 423         idp->idr_nodes = kmalloc(IDR_DEFAULT_SIZE * sizeof(*idp),
 424                                                 M_IDR, M_WAITOK | M_ZERO);
 425         idp->idr_count = IDR_DEFAULT_SIZE;
 426         idp->idr_lastindex = -1;
 427         idp->idr_maxwant = 0;
 428         lwkt_token_init(&idp->idr_token, "idr token");
 429 }