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-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-2  -  FREEBSD-11-1  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-4  -  FREEBSD-10-3  -  FREEBSD-10-2  -  FREEBSD-10-1  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-3  -  FREEBSD-9-2  -  FREEBSD-9-1  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-4  -  FREEBSD-8-3  -  FREEBSD-8-2  -  FREEBSD-8-1  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-4  -  FREEBSD-7-3  -  FREEBSD-7-2  -  FREEBSD-7-1  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-4  -  FREEBSD-6-3  -  FREEBSD-6-2  -  FREEBSD-6-1  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-5  -  FREEBSD-5-4  -  FREEBSD-5-3  -  FREEBSD-5-2  -  FREEBSD-5-1  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  linux-2.6  -  linux-2.4.22  -  MK83  -  MK84  -  PLAN9  -  DFBSD  -  NETBSD  -  NETBSD5  -  NETBSD4  -  NETBSD3  -  NETBSD20  -  OPENBSD  -  xnu-517  -  xnu-792  -  xnu-792.6.70  -  xnu-1228  -  xnu-1456.1.26  -  xnu-1699.24.8  -  xnu-2050.18.24  -  OPENSOLARIS  -  minix-3-1-1 
SearchContext: -  none  -  3  -  10 

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

Cache object: 86180dbf73870d5bcef58cb8a3a32e10


[ 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.