The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_unit.c

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    1 /*-
    2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
    3  *
    4  * Copyright (c) 2004 Poul-Henning Kamp
    5  * All rights reserved.
    6  *
    7  * Redistribution and use in source and binary forms, with or without
    8  * modification, are permitted provided that the following conditions
    9  * are met:
   10  * 1. Redistributions of source code must retain the above copyright
   11  *    notice, this list of conditions and the following disclaimer.
   12  * 2. Redistributions in binary form must reproduce the above copyright
   13  *    notice, this list of conditions and the following disclaimer in the
   14  *    documentation and/or other materials provided with the distribution.
   15  *
   16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
   17  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   19  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
   20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   22  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   23  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   24  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   25  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   26  * SUCH DAMAGE.
   27  *
   28  * $FreeBSD$
   29  *
   30  *
   31  * Unit number allocation functions.
   32  *
   33  * These functions implement a mixed run-length/bitmap management of unit
   34  * number spaces in a very memory efficient manner.
   35  *
   36  * Allocation policy is always lowest free number first.
   37  *
   38  * A return value of -1 signals that no more unit numbers are available.
   39  *
   40  * There is no cost associated with the range of unitnumbers, so unless
   41  * the resource really is finite, specify INT_MAX to new_unrhdr() and
   42  * forget about checking the return value.
   43  *
   44  * If a mutex is not provided when the unit number space is created, a
   45  * default global mutex is used.  The advantage to passing a mutex in, is
   46  * that the alloc_unrl() function can be called with the mutex already
   47  * held (it will not be released by alloc_unrl()).
   48  *
   49  * The allocation function alloc_unr{l}() never sleeps (but it may block on
   50  * the mutex of course).
   51  *
   52  * Freeing a unit number may require allocating memory, and can therefore
   53  * sleep so the free_unr() function does not come in a pre-locked variant.
   54  *
   55  * A userland test program is included.
   56  *
   57  * Memory usage is a very complex function of the exact allocation
   58  * pattern, but always very compact:
   59  *    * For the very typical case where a single unbroken run of unit
   60  *      numbers are allocated 44 bytes are used on i386.
   61  *    * For a unit number space of 1000 units and the random pattern
   62  *      in the usermode test program included, the worst case usage
   63  *      was 252 bytes on i386 for 500 allocated and 500 free units.
   64  *    * For a unit number space of 10000 units and the random pattern
   65  *      in the usermode test program included, the worst case usage
   66  *      was 798 bytes on i386 for 5000 allocated and 5000 free units.
   67  *    * The worst case is where every other unit number is allocated and
   68  *      the rest are free.  In that case 44 + N/4 bytes are used where
   69  *      N is the number of the highest unit allocated.
   70  */
   71 
   72 #include <sys/param.h>
   73 #include <sys/types.h>
   74 #include <sys/_unrhdr.h>
   75 
   76 #ifdef _KERNEL
   77 
   78 #include <sys/bitstring.h>
   79 #include <sys/malloc.h>
   80 #include <sys/kernel.h>
   81 #include <sys/systm.h>
   82 #include <sys/limits.h>
   83 #include <sys/lock.h>
   84 #include <sys/mutex.h>
   85 
   86 /*
   87  * In theory it would be smarter to allocate the individual blocks
   88  * with the zone allocator, but at this time the expectation is that
   89  * there will typically not even be enough allocations to fill a single
   90  * page, so we stick with malloc for now.
   91  */
   92 static MALLOC_DEFINE(M_UNIT, "Unitno", "Unit number allocation");
   93 
   94 #define Malloc(foo) malloc(foo, M_UNIT, M_WAITOK | M_ZERO)
   95 #define Free(foo) free(foo, M_UNIT)
   96 
   97 static struct mtx unitmtx;
   98 
   99 MTX_SYSINIT(unit, &unitmtx, "unit# allocation", MTX_DEF);
  100 
  101 #ifdef UNR64_LOCKED
  102 uint64_t
  103 alloc_unr64(struct unrhdr64 *unr64)
  104 {
  105         uint64_t item;
  106 
  107         mtx_lock(&unitmtx);
  108         item = unr64->counter++;
  109         mtx_unlock(&unitmtx);
  110         return (item);
  111 }
  112 #endif
  113 
  114 #else /* ...USERLAND */
  115 
  116 #include <bitstring.h>
  117 #include <err.h>
  118 #include <errno.h>
  119 #include <getopt.h>
  120 #include <stdbool.h>
  121 #include <stdio.h>
  122 #include <stdlib.h>
  123 #include <string.h>
  124 
  125 #define KASSERT(cond, arg) \
  126         do { \
  127                 if (!(cond)) { \
  128                         printf arg; \
  129                         abort(); \
  130                 } \
  131         } while (0)
  132 
  133 static int no_alloc;
  134 #define Malloc(foo) _Malloc(foo, __LINE__)
  135 static void *
  136 _Malloc(size_t foo, int line)
  137 {
  138 
  139         KASSERT(no_alloc == 0, ("malloc in wrong place() line %d", line));
  140         return (calloc(foo, 1));
  141 }
  142 #define Free(foo) free(foo)
  143 
  144 struct unrhdr;
  145 
  146 
  147 struct mtx {
  148         int     state;
  149 } unitmtx;
  150 
  151 static void
  152 mtx_lock(struct mtx *mp)
  153 {
  154         KASSERT(mp->state == 0, ("mutex already locked"));
  155         mp->state = 1;
  156 }
  157 
  158 static void
  159 mtx_unlock(struct mtx *mp)
  160 {
  161         KASSERT(mp->state == 1, ("mutex not locked"));
  162         mp->state = 0;
  163 }
  164 
  165 #define MA_OWNED        9
  166 
  167 static void
  168 mtx_assert(struct mtx *mp, int flag)
  169 {
  170         if (flag == MA_OWNED) {
  171                 KASSERT(mp->state == 1, ("mtx_assert(MA_OWNED) not true"));
  172         }
  173 }
  174 
  175 #define CTASSERT(foo)
  176 #define WITNESS_WARN(flags, lock, fmt, ...)     (void)0
  177 
  178 #endif /* USERLAND */
  179 
  180 /*
  181  * This is our basic building block.
  182  *
  183  * It can be used in three different ways depending on the value of the ptr
  184  * element:
  185  *     If ptr is NULL, it represents a run of free items.
  186  *     If ptr points to the unrhdr it represents a run of allocated items.
  187  *     Otherwise it points to a bitstring of allocated items.
  188  *
  189  * For runs the len field is the length of the run.
  190  * For bitmaps the len field represents the number of allocated items.
  191  *
  192  * The bitmap is the same size as struct unr to optimize memory management.
  193  */
  194 struct unr {
  195         TAILQ_ENTRY(unr)        list;
  196         u_int                   len;
  197         void                    *ptr;
  198 };
  199 
  200 struct unrb {
  201         bitstr_t                map[sizeof(struct unr) / sizeof(bitstr_t)];
  202 };
  203 
  204 CTASSERT((sizeof(struct unr) % sizeof(bitstr_t)) == 0);
  205 
  206 /* Number of bits we can store in the bitmap */
  207 #define NBITS (8 * sizeof(((struct unrb*)NULL)->map))
  208 
  209 /* Is the unrb empty in at least the first len bits? */
  210 static inline bool
  211 ub_empty(struct unrb *ub, int len) {
  212         int first_set;
  213 
  214         bit_ffs(ub->map, len, &first_set);
  215         return (first_set == -1);
  216 }
  217 
  218 /* Is the unrb full?  That is, is the number of set elements equal to len? */
  219 static inline bool
  220 ub_full(struct unrb *ub, int len)
  221 {
  222         int first_clear;
  223 
  224         bit_ffc(ub->map, len, &first_clear);
  225         return (first_clear == -1);
  226 }
  227 
  228 
  229 #if defined(DIAGNOSTIC) || !defined(_KERNEL)
  230 /*
  231  * Consistency check function.
  232  *
  233  * Checks the internal consistency as well as we can.
  234  *
  235  * Called at all boundaries of this API.
  236  */
  237 static void
  238 check_unrhdr(struct unrhdr *uh, int line)
  239 {
  240         struct unr *up;
  241         struct unrb *ub;
  242         int w;
  243         u_int y, z;
  244 
  245         y = uh->first;
  246         z = 0;
  247         TAILQ_FOREACH(up, &uh->head, list) {
  248                 z++;
  249                 if (up->ptr != uh && up->ptr != NULL) {
  250                         ub = up->ptr;
  251                         KASSERT (up->len <= NBITS,
  252                             ("UNR inconsistency: len %u max %zd (line %d)\n",
  253                             up->len, NBITS, line));
  254                         z++;
  255                         w = 0;
  256                         bit_count(ub->map, 0, up->len, &w);
  257                         y += w;
  258                 } else if (up->ptr != NULL)
  259                         y += up->len;
  260         }
  261         KASSERT (y == uh->busy,
  262             ("UNR inconsistency: items %u found %u (line %d)\n",
  263             uh->busy, y, line));
  264         KASSERT (z == uh->alloc,
  265             ("UNR inconsistency: chunks %u found %u (line %d)\n",
  266             uh->alloc, z, line));
  267 }
  268 
  269 #else
  270 
  271 static __inline void
  272 check_unrhdr(struct unrhdr *uh __unused, int line __unused)
  273 {
  274 
  275 }
  276 
  277 #endif
  278 
  279 
  280 /*
  281  * Userland memory management.  Just use calloc and keep track of how
  282  * many elements we have allocated for check_unrhdr().
  283  */
  284 
  285 static __inline void *
  286 new_unr(struct unrhdr *uh, void **p1, void **p2)
  287 {
  288         void *p;
  289 
  290         uh->alloc++;
  291         KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory"));
  292         if (*p1 != NULL) {
  293                 p = *p1;
  294                 *p1 = NULL;
  295                 return (p);
  296         } else {
  297                 p = *p2;
  298                 *p2 = NULL;
  299                 return (p);
  300         }
  301 }
  302 
  303 static __inline void
  304 delete_unr(struct unrhdr *uh, void *ptr)
  305 {
  306         struct unr *up;
  307 
  308         uh->alloc--;
  309         up = ptr;
  310         TAILQ_INSERT_TAIL(&uh->ppfree, up, list);
  311 }
  312 
  313 void
  314 clean_unrhdrl(struct unrhdr *uh)
  315 {
  316         struct unr *up;
  317 
  318         mtx_assert(uh->mtx, MA_OWNED);
  319         while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {
  320                 TAILQ_REMOVE(&uh->ppfree, up, list);
  321                 mtx_unlock(uh->mtx);
  322                 Free(up);
  323                 mtx_lock(uh->mtx);
  324         }
  325 
  326 }
  327 
  328 void
  329 clean_unrhdr(struct unrhdr *uh)
  330 {
  331 
  332         mtx_lock(uh->mtx);
  333         clean_unrhdrl(uh);
  334         mtx_unlock(uh->mtx);
  335 }
  336 
  337 void
  338 init_unrhdr(struct unrhdr *uh, int low, int high, struct mtx *mutex)
  339 {
  340 
  341         KASSERT(low >= 0 && low <= high,
  342             ("UNR: use error: new_unrhdr(%d, %d)", low, high));
  343         if (mutex != NULL)
  344                 uh->mtx = mutex;
  345         else
  346                 uh->mtx = &unitmtx;
  347         TAILQ_INIT(&uh->head);
  348         TAILQ_INIT(&uh->ppfree);
  349         uh->low = low;
  350         uh->high = high;
  351         uh->first = 0;
  352         uh->last = 1 + (high - low);
  353         check_unrhdr(uh, __LINE__);
  354 }
  355 
  356 /*
  357  * Allocate a new unrheader set.
  358  *
  359  * Highest and lowest valid values given as parameters.
  360  */
  361 
  362 struct unrhdr *
  363 new_unrhdr(int low, int high, struct mtx *mutex)
  364 {
  365         struct unrhdr *uh;
  366 
  367         uh = Malloc(sizeof *uh);
  368         init_unrhdr(uh, low, high, mutex);
  369         return (uh);
  370 }
  371 
  372 void
  373 delete_unrhdr(struct unrhdr *uh)
  374 {
  375 
  376         check_unrhdr(uh, __LINE__);
  377         KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
  378         KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
  379         KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,
  380             ("unrhdr has postponed item for free"));
  381         Free(uh);
  382 }
  383 
  384 void
  385 clear_unrhdr(struct unrhdr *uh)
  386 {
  387         struct unr *up, *uq;
  388 
  389         KASSERT(TAILQ_EMPTY(&uh->ppfree),
  390             ("unrhdr has postponed item for free"));
  391         TAILQ_FOREACH_SAFE(up, &uh->head, list, uq) {
  392                 if (up->ptr != uh) {
  393                         Free(up->ptr);
  394                 }
  395                 Free(up);
  396         }
  397         uh->busy = 0;
  398         uh->alloc = 0;
  399         init_unrhdr(uh, uh->low, uh->high, uh->mtx);
  400 
  401         check_unrhdr(uh, __LINE__);
  402 }
  403 
  404 static __inline int
  405 is_bitmap(struct unrhdr *uh, struct unr *up)
  406 {
  407         return (up->ptr != uh && up->ptr != NULL);
  408 }
  409 
  410 /*
  411  * Look for sequence of items which can be combined into a bitmap, if
  412  * multiple are present, take the one which saves most memory.
  413  *
  414  * Return (1) if a sequence was found to indicate that another call
  415  * might be able to do more.  Return (0) if we found no suitable sequence.
  416  *
  417  * NB: called from alloc_unr(), no new memory allocation allowed.
  418  */
  419 static int
  420 optimize_unr(struct unrhdr *uh)
  421 {
  422         struct unr *up, *uf, *us;
  423         struct unrb *ub, *ubf;
  424         u_int a, l, ba;
  425 
  426         /*
  427          * Look for the run of items (if any) which when collapsed into
  428          * a bitmap would save most memory.
  429          */
  430         us = NULL;
  431         ba = 0;
  432         TAILQ_FOREACH(uf, &uh->head, list) {
  433                 if (uf->len >= NBITS)
  434                         continue;
  435                 a = 1;
  436                 if (is_bitmap(uh, uf))
  437                         a++;
  438                 l = uf->len;
  439                 up = uf;
  440                 while (1) {
  441                         up = TAILQ_NEXT(up, list);
  442                         if (up == NULL)
  443                                 break;
  444                         if ((up->len + l) > NBITS)
  445                                 break;
  446                         a++;
  447                         if (is_bitmap(uh, up))
  448                                 a++;
  449                         l += up->len;
  450                 }
  451                 if (a > ba) {
  452                         ba = a;
  453                         us = uf;
  454                 }
  455         }
  456         if (ba < 3)
  457                 return (0);
  458 
  459         /*
  460          * If the first element is not a bitmap, make it one.
  461          * Trying to do so without allocating more memory complicates things
  462          * a bit
  463          */
  464         if (!is_bitmap(uh, us)) {
  465                 uf = TAILQ_NEXT(us, list);
  466                 TAILQ_REMOVE(&uh->head, us, list);
  467                 a = us->len;
  468                 l = us->ptr == uh ? 1 : 0;
  469                 ub = (void *)us;
  470                 bit_nclear(ub->map, 0, NBITS - 1);
  471                 if (l)
  472                         bit_nset(ub->map, 0, a);
  473                 if (!is_bitmap(uh, uf)) {
  474                         if (uf->ptr == NULL)
  475                                 bit_nclear(ub->map, a, a + uf->len - 1);
  476                         else
  477                                 bit_nset(ub->map, a, a + uf->len - 1);
  478                         uf->ptr = ub;
  479                         uf->len += a;
  480                         us = uf;
  481                 } else {
  482                         ubf = uf->ptr;
  483                         for (l = 0; l < uf->len; l++, a++) {
  484                                 if (bit_test(ubf->map, l))
  485                                         bit_set(ub->map, a);
  486                                 else
  487                                         bit_clear(ub->map, a);
  488                         }
  489                         uf->len = a;
  490                         delete_unr(uh, uf->ptr);
  491                         uf->ptr = ub;
  492                         us = uf;
  493                 }
  494         }
  495         ub = us->ptr;
  496         while (1) {
  497                 uf = TAILQ_NEXT(us, list);
  498                 if (uf == NULL)
  499                         return (1);
  500                 if (uf->len + us->len > NBITS)
  501                         return (1);
  502                 if (uf->ptr == NULL) {
  503                         bit_nclear(ub->map, us->len, us->len + uf->len - 1);
  504                         us->len += uf->len;
  505                         TAILQ_REMOVE(&uh->head, uf, list);
  506                         delete_unr(uh, uf);
  507                 } else if (uf->ptr == uh) {
  508                         bit_nset(ub->map, us->len, us->len + uf->len - 1);
  509                         us->len += uf->len;
  510                         TAILQ_REMOVE(&uh->head, uf, list);
  511                         delete_unr(uh, uf);
  512                 } else {
  513                         ubf = uf->ptr;
  514                         for (l = 0; l < uf->len; l++, us->len++) {
  515                                 if (bit_test(ubf->map, l))
  516                                         bit_set(ub->map, us->len);
  517                                 else
  518                                         bit_clear(ub->map, us->len);
  519                         }
  520                         TAILQ_REMOVE(&uh->head, uf, list);
  521                         delete_unr(uh, ubf);
  522                         delete_unr(uh, uf);
  523                 }
  524         }
  525 }
  526 
  527 /*
  528  * See if a given unr should be collapsed with a neighbor.
  529  *
  530  * NB: called from alloc_unr(), no new memory allocation allowed.
  531  */
  532 static void
  533 collapse_unr(struct unrhdr *uh, struct unr *up)
  534 {
  535         struct unr *upp;
  536         struct unrb *ub;
  537 
  538         /* If bitmap is all set or clear, change it to runlength */
  539         if (is_bitmap(uh, up)) {
  540                 ub = up->ptr;
  541                 if (ub_full(ub, up->len)) {
  542                         delete_unr(uh, up->ptr);
  543                         up->ptr = uh;
  544                 } else if (ub_empty(ub, up->len)) {
  545                         delete_unr(uh, up->ptr);
  546                         up->ptr = NULL;
  547                 }
  548         }
  549 
  550         /* If nothing left in runlength, delete it */
  551         if (up->len == 0) {
  552                 upp = TAILQ_PREV(up, unrhd, list);
  553                 if (upp == NULL)
  554                         upp = TAILQ_NEXT(up, list);
  555                 TAILQ_REMOVE(&uh->head, up, list);
  556                 delete_unr(uh, up);
  557                 up = upp;
  558         }
  559 
  560         /* If we have "hot-spot" still, merge with neighbor if possible */
  561         if (up != NULL) {
  562                 upp = TAILQ_PREV(up, unrhd, list);
  563                 if (upp != NULL && up->ptr == upp->ptr) {
  564                         up->len += upp->len;
  565                         TAILQ_REMOVE(&uh->head, upp, list);
  566                         delete_unr(uh, upp);
  567                         }
  568                 upp = TAILQ_NEXT(up, list);
  569                 if (upp != NULL && up->ptr == upp->ptr) {
  570                         up->len += upp->len;
  571                         TAILQ_REMOVE(&uh->head, upp, list);
  572                         delete_unr(uh, upp);
  573                 }
  574         }
  575 
  576         /* Merge into ->first if possible */
  577         upp = TAILQ_FIRST(&uh->head);
  578         if (upp != NULL && upp->ptr == uh) {
  579                 uh->first += upp->len;
  580                 TAILQ_REMOVE(&uh->head, upp, list);
  581                 delete_unr(uh, upp);
  582                 if (up == upp)
  583                         up = NULL;
  584         }
  585 
  586         /* Merge into ->last if possible */
  587         upp = TAILQ_LAST(&uh->head, unrhd);
  588         if (upp != NULL && upp->ptr == NULL) {
  589                 uh->last += upp->len;
  590                 TAILQ_REMOVE(&uh->head, upp, list);
  591                 delete_unr(uh, upp);
  592                 if (up == upp)
  593                         up = NULL;
  594         }
  595 
  596         /* Try to make bitmaps */
  597         while (optimize_unr(uh))
  598                 continue;
  599 }
  600 
  601 /*
  602  * Allocate a free unr.
  603  */
  604 int
  605 alloc_unrl(struct unrhdr *uh)
  606 {
  607         struct unr *up;
  608         struct unrb *ub;
  609         u_int x;
  610         int y;
  611 
  612         mtx_assert(uh->mtx, MA_OWNED);
  613         check_unrhdr(uh, __LINE__);
  614         x = uh->low + uh->first;
  615 
  616         up = TAILQ_FIRST(&uh->head);
  617 
  618         /*
  619          * If we have an ideal split, just adjust the first+last
  620          */
  621         if (up == NULL && uh->last > 0) {
  622                 uh->first++;
  623                 uh->last--;
  624                 uh->busy++;
  625                 return (x);
  626         }
  627 
  628         /*
  629          * We can always allocate from the first list element, so if we have
  630          * nothing on the list, we must have run out of unit numbers.
  631          */
  632         if (up == NULL)
  633                 return (-1);
  634 
  635         KASSERT(up->ptr != uh, ("UNR first element is allocated"));
  636 
  637         if (up->ptr == NULL) {  /* free run */
  638                 uh->first++;
  639                 up->len--;
  640         } else {                /* bitmap */
  641                 ub = up->ptr;
  642                 bit_ffc(ub->map, up->len, &y);
  643                 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
  644                 bit_set(ub->map, y);
  645                 x += y;
  646         }
  647         uh->busy++;
  648         collapse_unr(uh, up);
  649         return (x);
  650 }
  651 
  652 int
  653 alloc_unr(struct unrhdr *uh)
  654 {
  655         int i;
  656 
  657         mtx_lock(uh->mtx);
  658         i = alloc_unrl(uh);
  659         clean_unrhdrl(uh);
  660         mtx_unlock(uh->mtx);
  661         return (i);
  662 }
  663 
  664 static int
  665 alloc_unr_specificl(struct unrhdr *uh, u_int item, void **p1, void **p2)
  666 {
  667         struct unr *up, *upn;
  668         struct unrb *ub;
  669         u_int i, last, tl;
  670 
  671         mtx_assert(uh->mtx, MA_OWNED);
  672 
  673         if (item < uh->low + uh->first || item > uh->high)
  674                 return (-1);
  675 
  676         up = TAILQ_FIRST(&uh->head);
  677         /* Ideal split. */
  678         if (up == NULL && item - uh->low == uh->first) {
  679                 uh->first++;
  680                 uh->last--;
  681                 uh->busy++;
  682                 check_unrhdr(uh, __LINE__);
  683                 return (item);
  684         }
  685 
  686         i = item - uh->low - uh->first;
  687 
  688         if (up == NULL) {
  689                 up = new_unr(uh, p1, p2);
  690                 up->ptr = NULL;
  691                 up->len = i;
  692                 TAILQ_INSERT_TAIL(&uh->head, up, list);
  693                 up = new_unr(uh, p1, p2);
  694                 up->ptr = uh;
  695                 up->len = 1;
  696                 TAILQ_INSERT_TAIL(&uh->head, up, list);
  697                 uh->last = uh->high - uh->low - i;
  698                 uh->busy++;
  699                 check_unrhdr(uh, __LINE__);
  700                 return (item);
  701         } else {
  702                 /* Find the item which contains the unit we want to allocate. */
  703                 TAILQ_FOREACH(up, &uh->head, list) {
  704                         if (up->len > i)
  705                                 break;
  706                         i -= up->len;
  707                 }
  708         }
  709 
  710         if (up == NULL) {
  711                 if (i > 0) {
  712                         up = new_unr(uh, p1, p2);
  713                         up->ptr = NULL;
  714                         up->len = i;
  715                         TAILQ_INSERT_TAIL(&uh->head, up, list);
  716                 }
  717                 up = new_unr(uh, p1, p2);
  718                 up->ptr = uh;
  719                 up->len = 1;
  720                 TAILQ_INSERT_TAIL(&uh->head, up, list);
  721                 goto done;
  722         }
  723 
  724         if (is_bitmap(uh, up)) {
  725                 ub = up->ptr;
  726                 if (bit_test(ub->map, i) == 0) {
  727                         bit_set(ub->map, i);
  728                         goto done;
  729                 } else
  730                         return (-1);
  731         } else if (up->ptr == uh)
  732                 return (-1);
  733 
  734         KASSERT(up->ptr == NULL,
  735             ("alloc_unr_specificl: up->ptr != NULL (up=%p)", up));
  736 
  737         /* Split off the tail end, if any. */
  738         tl = up->len - (1 + i);
  739         if (tl > 0) {
  740                 upn = new_unr(uh, p1, p2);
  741                 upn->ptr = NULL;
  742                 upn->len = tl;
  743                 TAILQ_INSERT_AFTER(&uh->head, up, upn, list);
  744         }
  745 
  746         /* Split off head end, if any */
  747         if (i > 0) {
  748                 upn = new_unr(uh, p1, p2);
  749                 upn->len = i;
  750                 upn->ptr = NULL;
  751                 TAILQ_INSERT_BEFORE(up, upn, list);
  752         }
  753         up->len = 1;
  754         up->ptr = uh;
  755 
  756 done:
  757         last = uh->high - uh->low - (item - uh->low);
  758         if (uh->last > last)
  759                 uh->last = last;
  760         uh->busy++;
  761         collapse_unr(uh, up);
  762         check_unrhdr(uh, __LINE__);
  763         return (item);
  764 }
  765 
  766 int
  767 alloc_unr_specific(struct unrhdr *uh, u_int item)
  768 {
  769         void *p1, *p2;
  770         int i;
  771 
  772         WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "alloc_unr_specific");
  773 
  774         p1 = Malloc(sizeof(struct unr));
  775         p2 = Malloc(sizeof(struct unr));
  776 
  777         mtx_lock(uh->mtx);
  778         i = alloc_unr_specificl(uh, item, &p1, &p2);
  779         mtx_unlock(uh->mtx);
  780 
  781         if (p1 != NULL)
  782                 Free(p1);
  783         if (p2 != NULL)
  784                 Free(p2);
  785 
  786         return (i);
  787 }
  788 
  789 /*
  790  * Free a unr.
  791  *
  792  * If we can save unrs by using a bitmap, do so.
  793  */
  794 static void
  795 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
  796 {
  797         struct unr *up, *upp, *upn;
  798         struct unrb *ub;
  799         u_int pl;
  800 
  801         KASSERT(item >= uh->low && item <= uh->high,
  802             ("UNR: free_unr(%u) out of range [%u...%u]",
  803              item, uh->low, uh->high));
  804         check_unrhdr(uh, __LINE__);
  805         item -= uh->low;
  806         upp = TAILQ_FIRST(&uh->head);
  807         /*
  808          * Freeing in the ideal split case
  809          */
  810         if (item + 1 == uh->first && upp == NULL) {
  811                 uh->last++;
  812                 uh->first--;
  813                 uh->busy--;
  814                 check_unrhdr(uh, __LINE__);
  815                 return;
  816         }
  817         /*
  818          * Freeing in the ->first section.  Create a run starting at the
  819          * freed item.  The code below will subdivide it.
  820          */
  821         if (item < uh->first) {
  822                 up = new_unr(uh, p1, p2);
  823                 up->ptr = uh;
  824                 up->len = uh->first - item;
  825                 TAILQ_INSERT_HEAD(&uh->head, up, list);
  826                 uh->first -= up->len;
  827         }
  828 
  829         item -= uh->first;
  830 
  831         /* Find the item which contains the unit we want to free */
  832         TAILQ_FOREACH(up, &uh->head, list) {
  833                 if (up->len > item)
  834                         break;
  835                 item -= up->len;
  836         }
  837 
  838         /* Handle bitmap items */
  839         if (is_bitmap(uh, up)) {
  840                 ub = up->ptr;
  841 
  842                 KASSERT(bit_test(ub->map, item) != 0,
  843                     ("UNR: Freeing free item %d (bitmap)\n", item));
  844                 bit_clear(ub->map, item);
  845                 uh->busy--;
  846                 collapse_unr(uh, up);
  847                 return;
  848         }
  849 
  850         KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
  851 
  852         /* Just this one left, reap it */
  853         if (up->len == 1) {
  854                 up->ptr = NULL;
  855                 uh->busy--;
  856                 collapse_unr(uh, up);
  857                 return;
  858         }
  859 
  860         /* Check if we can shift the item into the previous 'free' run */
  861         upp = TAILQ_PREV(up, unrhd, list);
  862         if (item == 0 && upp != NULL && upp->ptr == NULL) {
  863                 upp->len++;
  864                 up->len--;
  865                 uh->busy--;
  866                 collapse_unr(uh, up);
  867                 return;
  868         }
  869 
  870         /* Check if we can shift the item to the next 'free' run */
  871         upn = TAILQ_NEXT(up, list);
  872         if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
  873                 upn->len++;
  874                 up->len--;
  875                 uh->busy--;
  876                 collapse_unr(uh, up);
  877                 return;
  878         }
  879 
  880         /* Split off the tail end, if any. */
  881         pl = up->len - (1 + item);
  882         if (pl > 0) {
  883                 upp = new_unr(uh, p1, p2);
  884                 upp->ptr = uh;
  885                 upp->len = pl;
  886                 TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
  887         }
  888 
  889         /* Split off head end, if any */
  890         if (item > 0) {
  891                 upp = new_unr(uh, p1, p2);
  892                 upp->len = item;
  893                 upp->ptr = uh;
  894                 TAILQ_INSERT_BEFORE(up, upp, list);
  895         }
  896         up->len = 1;
  897         up->ptr = NULL;
  898         uh->busy--;
  899         collapse_unr(uh, up);
  900 }
  901 
  902 void
  903 free_unr(struct unrhdr *uh, u_int item)
  904 {
  905         void *p1, *p2;
  906 
  907         WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr");
  908         p1 = Malloc(sizeof(struct unr));
  909         p2 = Malloc(sizeof(struct unr));
  910         mtx_lock(uh->mtx);
  911         free_unrl(uh, item, &p1, &p2);
  912         clean_unrhdrl(uh);
  913         mtx_unlock(uh->mtx);
  914         if (p1 != NULL)
  915                 Free(p1);
  916         if (p2 != NULL)
  917                 Free(p2);
  918 }
  919 
  920 #ifndef _KERNEL /* USERLAND test driver */
  921 
  922 /*
  923  * Simple stochastic test driver for the above functions.  The code resides
  924  * here so that it can access static functions and structures.
  925  */
  926 
  927 static bool verbose;
  928 #define VPRINTF(...)    {if (verbose) printf(__VA_ARGS__);}
  929 
  930 static void
  931 print_unr(struct unrhdr *uh, struct unr *up)
  932 {
  933         u_int x;
  934         struct unrb *ub;
  935 
  936         printf("  %p len = %5u ", up, up->len);
  937         if (up->ptr == NULL)
  938                 printf("free\n");
  939         else if (up->ptr == uh)
  940                 printf("alloc\n");
  941         else {
  942                 ub = up->ptr;
  943                 printf("bitmap [");
  944                 for (x = 0; x < up->len; x++) {
  945                         if (bit_test(ub->map, x))
  946                                 printf("#");
  947                         else
  948                                 printf(" ");
  949                 }
  950                 printf("]\n");
  951         }
  952 }
  953 
  954 static void
  955 print_unrhdr(struct unrhdr *uh)
  956 {
  957         struct unr *up;
  958         u_int x;
  959 
  960         printf(
  961             "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n",
  962             uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
  963         x = uh->low + uh->first;
  964         TAILQ_FOREACH(up, &uh->head, list) {
  965                 printf("  from = %5u", x);
  966                 print_unr(uh, up);
  967                 if (up->ptr == NULL || up->ptr == uh)
  968                         x += up->len;
  969                 else
  970                         x += NBITS;
  971         }
  972 }
  973 
  974 static void
  975 test_alloc_unr(struct unrhdr *uh, u_int i, char a[])
  976 {
  977         int j;
  978 
  979         if (a[i]) {
  980                 VPRINTF("F %u\n", i);
  981                 free_unr(uh, i);
  982                 a[i] = 0;
  983         } else {
  984                 no_alloc = 1;
  985                 j = alloc_unr(uh);
  986                 if (j != -1) {
  987                         a[j] = 1;
  988                         VPRINTF("A %d\n", j);
  989                 }
  990                 no_alloc = 0;
  991         }
  992 }
  993 
  994 static void
  995 test_alloc_unr_specific(struct unrhdr *uh, u_int i, char a[])
  996 {
  997         int j;
  998 
  999         j = alloc_unr_specific(uh, i);
 1000         if (j == -1) {
 1001                 VPRINTF("F %u\n", i);
 1002                 a[i] = 0;
 1003                 free_unr(uh, i);
 1004         } else {
 1005                 a[i] = 1;
 1006                 VPRINTF("A %d\n", j);
 1007         }
 1008 }
 1009 
 1010 static void
 1011 usage(char** argv)
 1012 {
 1013         printf("%s [-h] [-r REPETITIONS] [-v]\n", argv[0]);
 1014 }
 1015 
 1016 int
 1017 main(int argc, char **argv)
 1018 {
 1019         struct unrhdr *uh;
 1020         char *a;
 1021         long count = 10000;     /* Number of unrs to test */
 1022         long reps = 1, m;
 1023         int ch;
 1024         u_int i, j;
 1025 
 1026         verbose = false;
 1027 
 1028         while ((ch = getopt(argc, argv, "hr:v")) != -1) {
 1029                 switch (ch) {
 1030                 case 'r':
 1031                         errno = 0;
 1032                         reps = strtol(optarg, NULL, 0);
 1033                         if (errno == ERANGE || errno == EINVAL) {
 1034                                 usage(argv);
 1035                                 exit(2);
 1036                         }
 1037 
 1038                         break;
 1039                 case 'v':
 1040                         verbose = true;
 1041                         break;
 1042                 case 'h':
 1043                 default:
 1044                         usage(argv);
 1045                         exit(2);
 1046                 }
 1047 
 1048 
 1049         }
 1050 
 1051         setbuf(stdout, NULL);
 1052         uh = new_unrhdr(0, count - 1, NULL);
 1053         print_unrhdr(uh);
 1054 
 1055         a = calloc(count, sizeof(char));
 1056         if (a == NULL)
 1057                 err(1, "calloc failed");
 1058         srandomdev();
 1059 
 1060         printf("sizeof(struct unr) %zu\n", sizeof(struct unr));
 1061         printf("sizeof(struct unrb) %zu\n", sizeof(struct unrb));
 1062         printf("sizeof(struct unrhdr) %zu\n", sizeof(struct unrhdr));
 1063         printf("NBITS %lu\n", (unsigned long)NBITS);
 1064         for (m = 0; m < count * reps; m++) {
 1065                 j = random();
 1066                 i = (j >> 1) % count;
 1067 #if 0
 1068                 if (a[i] && (j & 1))
 1069                         continue;
 1070 #endif
 1071                 if ((random() & 1) != 0)
 1072                         test_alloc_unr(uh, i, a);
 1073                 else
 1074                         test_alloc_unr_specific(uh, i, a);
 1075 
 1076                 if (verbose)
 1077                         print_unrhdr(uh);
 1078                 check_unrhdr(uh, __LINE__);
 1079         }
 1080         for (i = 0; i < (u_int)count; i++) {
 1081                 if (a[i]) {
 1082                         if (verbose) {
 1083                                 printf("C %u\n", i);
 1084                                 print_unrhdr(uh);
 1085                         }
 1086                         free_unr(uh, i);
 1087                 }
 1088         }
 1089         print_unrhdr(uh);
 1090         delete_unrhdr(uh);
 1091         free(a);
 1092         return (0);
 1093 }
 1094 #endif

Cache object: dd9904da46819f65f9d33ad1227f78ee


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.