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  * 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$
   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 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 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 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/queue.h>
   72 #include <sys/bitstring.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 
  157 #endif /* USERLAND */
  158 
  159 /*
  160  * This is our basic building block.
  161  *
  162  * It can be used in three different ways depending on the value of the ptr
  163  * element:
  164  *     If ptr is NULL, it represents a run of free items.
  165  *     If ptr points to the unrhdr it represents a run of allocated items.
  166  *     Otherwise it points to an bitstring of allocated items.
  167  *
  168  * For runs the len field is the length of the run.
  169  * For bitmaps the len field represents the number of allocated items.
  170  *
  171  * The bitmap is the same size as struct unr to optimize memory management.
  172  */
  173 struct unr {
  174         TAILQ_ENTRY(unr)        list;
  175         u_int                   len;
  176         void                    *ptr;
  177 };
  178 
  179 struct unrb {
  180         u_char                  busy;
  181         bitstr_t                map[sizeof(struct unr) - 1];
  182 };
  183 
  184 CTASSERT(sizeof(struct unr) == sizeof(struct unrb));
  185 
  186 /* Number of bits in the bitmap */
  187 #define NBITS   ((int)sizeof(((struct unrb *)NULL)->map) * 8)
  188 
  189 /* Header element for a unr number space. */
  190 
  191 struct unrhdr {
  192         TAILQ_HEAD(unrhd,unr)   head;
  193         u_int                   low;    /* Lowest item */
  194         u_int                   high;   /* Highest item */
  195         u_int                   busy;   /* Count of allocated items */
  196         u_int                   alloc;  /* Count of memory allocations */
  197         u_int                   first;  /* items in allocated from start */
  198         u_int                   last;   /* items free at end */
  199         struct mtx              *mtx;
  200         TAILQ_HEAD(unrfr,unr)   ppfree; /* Items to be freed after mtx
  201                                            lock dropped */
  202 };
  203 
  204 
  205 #if defined(DIAGNOSTIC) || !defined(_KERNEL)
  206 /*
  207  * Consistency check function.
  208  *
  209  * Checks the internal consistency as well as we can.
  210  * 
  211  * Called at all boundaries of this API.
  212  */
  213 static void
  214 check_unrhdr(struct unrhdr *uh, int line)
  215 {
  216         struct unr *up;
  217         struct unrb *ub;
  218         u_int x, y, z, w;
  219 
  220         y = uh->first;
  221         z = 0;
  222         TAILQ_FOREACH(up, &uh->head, list) {
  223                 z++;
  224                 if (up->ptr != uh && up->ptr != NULL) {
  225                         ub = up->ptr;
  226                         KASSERT (up->len <= NBITS,
  227                             ("UNR inconsistency: len %u max %d (line %d)\n",
  228                             up->len, NBITS, line));
  229                         z++;
  230                         w = 0;
  231                         for (x = 0; x < up->len; x++)
  232                                 if (bit_test(ub->map, x))
  233                                         w++;
  234                         KASSERT (w == ub->busy,
  235                             ("UNR inconsistency: busy %u found %u (line %d)\n",
  236                             ub->busy, w, line));
  237                         y += w;
  238                 } else if (up->ptr != NULL) 
  239                         y += up->len;
  240         }
  241         KASSERT (y == uh->busy,
  242             ("UNR inconsistency: items %u found %u (line %d)\n",
  243             uh->busy, y, line));
  244         KASSERT (z == uh->alloc,
  245             ("UNR inconsistency: chunks %u found %u (line %d)\n",
  246             uh->alloc, z, line));
  247 }
  248 
  249 #else
  250 
  251 static __inline void
  252 check_unrhdr(struct unrhdr *uh, int line)
  253 {
  254 
  255 }
  256 
  257 #endif
  258 
  259 
  260 /*
  261  * Userland memory management.  Just use calloc and keep track of how
  262  * many elements we have allocated for check_unrhdr().
  263  */
  264 
  265 static __inline void *
  266 new_unr(struct unrhdr *uh, void **p1, void **p2)
  267 {
  268         void *p;
  269 
  270         uh->alloc++;
  271         KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory"));
  272         if (*p1 != NULL) {
  273                 p = *p1;
  274                 *p1 = NULL;
  275                 return (p);
  276         } else {
  277                 p = *p2;
  278                 *p2 = NULL;
  279                 return (p);
  280         }
  281 }
  282 
  283 static __inline void
  284 delete_unr(struct unrhdr *uh, void *ptr)
  285 {
  286         struct unr *up;
  287 
  288         uh->alloc--;
  289         up = ptr;
  290         TAILQ_INSERT_TAIL(&uh->ppfree, up, list);
  291 }
  292 
  293 void
  294 clean_unrhdrl(struct unrhdr *uh)
  295 {
  296         struct unr *up;
  297 
  298         mtx_assert(uh->mtx, MA_OWNED);
  299         while ((up = TAILQ_FIRST(&uh->ppfree)) != NULL) {
  300                 TAILQ_REMOVE(&uh->ppfree, up, list);
  301                 mtx_unlock(uh->mtx);
  302                 Free(up);
  303                 mtx_lock(uh->mtx);
  304         }
  305 
  306 }
  307 
  308 void
  309 clean_unrhdr(struct unrhdr *uh)
  310 {
  311 
  312         mtx_lock(uh->mtx);
  313         clean_unrhdrl(uh);
  314         mtx_unlock(uh->mtx);
  315 }
  316 
  317 /*
  318  * Allocate a new unrheader set.
  319  *
  320  * Highest and lowest valid values given as paramters.
  321  */
  322 
  323 struct unrhdr *
  324 new_unrhdr(int low, int high, struct mtx *mutex)
  325 {
  326         struct unrhdr *uh;
  327 
  328         KASSERT(low <= high,
  329             ("UNR: use error: new_unrhdr(%u, %u)", low, high));
  330         uh = Malloc(sizeof *uh);
  331         if (mutex != NULL)
  332                 uh->mtx = mutex;
  333         else
  334                 uh->mtx = &unitmtx;
  335         TAILQ_INIT(&uh->head);
  336         TAILQ_INIT(&uh->ppfree);
  337         uh->low = low;
  338         uh->high = high;
  339         uh->first = 0;
  340         uh->last = 1 + (high - low);
  341         check_unrhdr(uh, __LINE__);
  342         return (uh);
  343 }
  344 
  345 void
  346 delete_unrhdr(struct unrhdr *uh)
  347 {
  348 
  349         check_unrhdr(uh, __LINE__);
  350         KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
  351         KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
  352         KASSERT(TAILQ_FIRST(&uh->ppfree) == NULL,
  353             ("unrhdr has postponed item for free"));
  354         Free(uh);
  355 }
  356 
  357 static __inline int
  358 is_bitmap(struct unrhdr *uh, struct unr *up)
  359 {
  360         return (up->ptr != uh && up->ptr != NULL);
  361 }
  362 
  363 /*
  364  * Look for sequence of items which can be combined into a bitmap, if
  365  * multiple are present, take the one which saves most memory.
  366  * 
  367  * Return (1) if a sequence was found to indicate that another call
  368  * might be able to do more.  Return (0) if we found no suitable sequence.
  369  *
  370  * NB: called from alloc_unr(), no new memory allocation allowed.
  371  */
  372 static int
  373 optimize_unr(struct unrhdr *uh)
  374 {
  375         struct unr *up, *uf, *us;
  376         struct unrb *ub, *ubf;
  377         u_int a, l, ba;
  378 
  379         /*
  380          * Look for the run of items (if any) which when collapsed into
  381          * a bitmap would save most memory.
  382          */
  383         us = NULL;
  384         ba = 0;
  385         TAILQ_FOREACH(uf, &uh->head, list) {
  386                 if (uf->len >= NBITS)
  387                         continue;
  388                 a = 1;
  389                 if (is_bitmap(uh, uf))
  390                         a++;
  391                 l = uf->len;
  392                 up = uf;
  393                 while (1) {
  394                         up = TAILQ_NEXT(up, list);
  395                         if (up == NULL)
  396                                 break;
  397                         if ((up->len + l) > NBITS)
  398                                 break;
  399                         a++;
  400                         if (is_bitmap(uh, up))
  401                                 a++;
  402                         l += up->len;
  403                 }
  404                 if (a > ba) {
  405                         ba = a;
  406                         us = uf;
  407                 }
  408         }
  409         if (ba < 3)
  410                 return (0);
  411 
  412         /*
  413          * If the first element is not a bitmap, make it one.
  414          * Trying to do so without allocating more memory complicates things
  415          * a bit
  416          */
  417         if (!is_bitmap(uh, us)) {
  418                 uf = TAILQ_NEXT(us, list);
  419                 TAILQ_REMOVE(&uh->head, us, list);
  420                 a = us->len;
  421                 l = us->ptr == uh ? 1 : 0;
  422                 ub = (void *)us;
  423                 ub->busy = 0;
  424                 if (l) {
  425                         bit_nset(ub->map, 0, a);
  426                         ub->busy += a;
  427                 } else {
  428                         bit_nclear(ub->map, 0, a);
  429                 }
  430                 if (!is_bitmap(uh, uf)) {
  431                         if (uf->ptr == NULL) {
  432                                 bit_nclear(ub->map, a, a + uf->len - 1);
  433                         } else {
  434                                 bit_nset(ub->map, a, a + uf->len - 1);
  435                                 ub->busy += uf->len;
  436                         }
  437                         uf->ptr = ub;
  438                         uf->len += a;
  439                         us = uf;
  440                 } else {
  441                         ubf = uf->ptr;
  442                         for (l = 0; l < uf->len; l++, a++) {
  443                                 if (bit_test(ubf->map, l)) {
  444                                         bit_set(ub->map, a);
  445                                         ub->busy++;
  446                                 } else {
  447                                         bit_clear(ub->map, a);
  448                                 }
  449                         }
  450                         uf->len = a;
  451                         delete_unr(uh, uf->ptr);
  452                         uf->ptr = ub;
  453                         us = uf;
  454                 }
  455         }
  456         ub = us->ptr;
  457         while (1) {
  458                 uf = TAILQ_NEXT(us, list);
  459                 if (uf == NULL)
  460                         return (1);
  461                 if (uf->len + us->len > NBITS)
  462                         return (1);
  463                 if (uf->ptr == NULL) {
  464                         bit_nclear(ub->map, us->len, us->len + uf->len - 1);
  465                         us->len += uf->len;
  466                         TAILQ_REMOVE(&uh->head, uf, list);
  467                         delete_unr(uh, uf);
  468                 } else if (uf->ptr == uh) {
  469                         bit_nset(ub->map, us->len, us->len + uf->len - 1);
  470                         ub->busy += uf->len;
  471                         us->len += uf->len;
  472                         TAILQ_REMOVE(&uh->head, uf, list);
  473                         delete_unr(uh, uf);
  474                 } else {
  475                         ubf = uf->ptr;
  476                         for (l = 0; l < uf->len; l++, us->len++) {
  477                                 if (bit_test(ubf->map, l)) {
  478                                         bit_set(ub->map, us->len);
  479                                         ub->busy++;
  480                                 } else {
  481                                         bit_clear(ub->map, us->len);
  482                                 }
  483                         }
  484                         TAILQ_REMOVE(&uh->head, uf, list);
  485                         delete_unr(uh, ubf);
  486                         delete_unr(uh, uf);
  487                 }
  488         }
  489 }
  490 
  491 /*
  492  * See if a given unr should be collapsed with a neighbor.
  493  *
  494  * NB: called from alloc_unr(), no new memory allocation allowed.
  495  */
  496 static void
  497 collapse_unr(struct unrhdr *uh, struct unr *up)
  498 {
  499         struct unr *upp;
  500         struct unrb *ub;
  501 
  502         /* If bitmap is all set or clear, change it to runlength */
  503         if (is_bitmap(uh, up)) {
  504                 ub = up->ptr;
  505                 if (ub->busy == up->len) {
  506                         delete_unr(uh, up->ptr);
  507                         up->ptr = uh;
  508                 } else if (ub->busy == 0) {
  509                         delete_unr(uh, up->ptr);
  510                         up->ptr = NULL;
  511                 }
  512         }
  513 
  514         /* If nothing left in runlength, delete it */
  515         if (up->len == 0) {
  516                 upp = TAILQ_PREV(up, unrhd, list);
  517                 if (upp == NULL)
  518                         upp = TAILQ_NEXT(up, list);
  519                 TAILQ_REMOVE(&uh->head, up, list);
  520                 delete_unr(uh, up);
  521                 up = upp;
  522         }
  523 
  524         /* If we have "hot-spot" still, merge with neighbor if possible */
  525         if (up != NULL) {
  526                 upp = TAILQ_PREV(up, unrhd, list);
  527                 if (upp != NULL && up->ptr == upp->ptr) {
  528                         up->len += upp->len;
  529                         TAILQ_REMOVE(&uh->head, upp, list);
  530                         delete_unr(uh, upp);
  531                         }
  532                 upp = TAILQ_NEXT(up, list);
  533                 if (upp != NULL && up->ptr == upp->ptr) {
  534                         up->len += upp->len;
  535                         TAILQ_REMOVE(&uh->head, upp, list);
  536                         delete_unr(uh, upp);
  537                 }
  538         }
  539 
  540         /* Merge into ->first if possible */
  541         upp = TAILQ_FIRST(&uh->head);
  542         if (upp != NULL && upp->ptr == uh) {
  543                 uh->first += upp->len;
  544                 TAILQ_REMOVE(&uh->head, upp, list);
  545                 delete_unr(uh, upp);
  546                 if (up == upp)
  547                         up = NULL;
  548         }
  549 
  550         /* Merge into ->last if possible */
  551         upp = TAILQ_LAST(&uh->head, unrhd);
  552         if (upp != NULL && upp->ptr == NULL) {
  553                 uh->last += upp->len;
  554                 TAILQ_REMOVE(&uh->head, upp, list);
  555                 delete_unr(uh, upp);
  556                 if (up == upp)
  557                         up = NULL;
  558         }
  559 
  560         /* Try to make bitmaps */
  561         while (optimize_unr(uh))
  562                 continue;
  563 }
  564 
  565 /*
  566  * Allocate a free unr.
  567  */
  568 int
  569 alloc_unrl(struct unrhdr *uh)
  570 {
  571         struct unr *up;
  572         struct unrb *ub;
  573         u_int x;
  574         int y;
  575 
  576         mtx_assert(uh->mtx, MA_OWNED);
  577         check_unrhdr(uh, __LINE__);
  578         x = uh->low + uh->first;
  579 
  580         up = TAILQ_FIRST(&uh->head);
  581 
  582         /*
  583          * If we have an ideal split, just adjust the first+last
  584          */
  585         if (up == NULL && uh->last > 0) {
  586                 uh->first++;
  587                 uh->last--;
  588                 uh->busy++;
  589                 return (x);
  590         }
  591 
  592         /*
  593          * We can always allocate from the first list element, so if we have 
  594          * nothing on the list, we must have run out of unit numbers.
  595          */
  596         if (up == NULL)
  597                 return (-1);
  598 
  599         KASSERT(up->ptr != uh, ("UNR first element is allocated"));
  600 
  601         if (up->ptr == NULL) {  /* free run */
  602                 uh->first++;
  603                 up->len--;
  604         } else {                /* bitmap */
  605                 ub = up->ptr;
  606                 KASSERT(ub->busy < up->len, ("UNR bitmap confusion"));
  607                 bit_ffc(ub->map, up->len, &y);
  608                 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
  609                 bit_set(ub->map, y);
  610                 ub->busy++;
  611                 x += y;
  612         }
  613         uh->busy++;
  614         collapse_unr(uh, up);
  615         return (x);
  616 }
  617 
  618 int
  619 alloc_unr(struct unrhdr *uh)
  620 {
  621         int i;
  622 
  623         mtx_lock(uh->mtx);
  624         i = alloc_unrl(uh);
  625         clean_unrhdrl(uh);
  626         mtx_unlock(uh->mtx);
  627         return (i);
  628 }
  629 
  630 /*
  631  * Free a unr.
  632  *
  633  * If we can save unrs by using a bitmap, do so.
  634  */
  635 static void
  636 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
  637 {
  638         struct unr *up, *upp, *upn;
  639         struct unrb *ub;
  640         u_int pl;
  641 
  642         KASSERT(item >= uh->low && item <= uh->high,
  643             ("UNR: free_unr(%u) out of range [%u...%u]",
  644              item, uh->low, uh->high));
  645         check_unrhdr(uh, __LINE__);
  646         item -= uh->low;
  647         upp = TAILQ_FIRST(&uh->head);
  648         /*
  649          * Freeing in the ideal split case
  650          */
  651         if (item + 1 == uh->first && upp == NULL) {
  652                 uh->last++;
  653                 uh->first--;
  654                 uh->busy--;
  655                 check_unrhdr(uh, __LINE__);
  656                 return;
  657         }
  658         /*
  659          * Freeing in the ->first section.  Create a run starting at the
  660          * freed item.  The code below will subdivide it.
  661          */
  662         if (item < uh->first) {
  663                 up = new_unr(uh, p1, p2);
  664                 up->ptr = uh;
  665                 up->len = uh->first - item;
  666                 TAILQ_INSERT_HEAD(&uh->head, up, list);
  667                 uh->first -= up->len;
  668         }
  669 
  670         item -= uh->first;
  671 
  672         /* Find the item which contains the unit we want to free */
  673         TAILQ_FOREACH(up, &uh->head, list) {
  674                 if (up->len > item)
  675                         break;
  676                 item -= up->len;
  677         }
  678 
  679         /* Handle bitmap items */
  680         if (is_bitmap(uh, up)) {
  681                 ub = up->ptr;
  682                 
  683                 KASSERT(bit_test(ub->map, item) != 0,
  684                     ("UNR: Freeing free item %d (bitmap)\n", item));
  685                 bit_clear(ub->map, item);
  686                 uh->busy--;
  687                 ub->busy--;
  688                 collapse_unr(uh, up);
  689                 return;
  690         }
  691 
  692         KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
  693 
  694         /* Just this one left, reap it */
  695         if (up->len == 1) {
  696                 up->ptr = NULL;
  697                 uh->busy--;
  698                 collapse_unr(uh, up);
  699                 return;
  700         }
  701 
  702         /* Check if we can shift the item into the previous 'free' run */
  703         upp = TAILQ_PREV(up, unrhd, list);
  704         if (item == 0 && upp != NULL && upp->ptr == NULL) {
  705                 upp->len++;
  706                 up->len--;
  707                 uh->busy--;
  708                 collapse_unr(uh, up);
  709                 return;
  710         }
  711 
  712         /* Check if we can shift the item to the next 'free' run */
  713         upn = TAILQ_NEXT(up, list);
  714         if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
  715                 upn->len++;
  716                 up->len--;
  717                 uh->busy--;
  718                 collapse_unr(uh, up);
  719                 return;
  720         }
  721 
  722         /* Split off the tail end, if any. */
  723         pl = up->len - (1 + item);
  724         if (pl > 0) {
  725                 upp = new_unr(uh, p1, p2);
  726                 upp->ptr = uh;
  727                 upp->len = pl;
  728                 TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
  729         }
  730 
  731         /* Split off head end, if any */
  732         if (item > 0) {
  733                 upp = new_unr(uh, p1, p2);
  734                 upp->len = item;
  735                 upp->ptr = uh;
  736                 TAILQ_INSERT_BEFORE(up, upp, list);
  737         }
  738         up->len = 1;
  739         up->ptr = NULL;
  740         uh->busy--;
  741         collapse_unr(uh, up);
  742 }
  743 
  744 void
  745 free_unr(struct unrhdr *uh, u_int item)
  746 {
  747         void *p1, *p2;
  748 
  749         WITNESS_WARN(WARN_GIANTOK | WARN_SLEEPOK, NULL, "free_unr");
  750         p1 = Malloc(sizeof(struct unr));
  751         p2 = Malloc(sizeof(struct unr));
  752         mtx_lock(uh->mtx);
  753         free_unrl(uh, item, &p1, &p2);
  754         clean_unrhdrl(uh);
  755         mtx_unlock(uh->mtx);
  756         if (p1 != NULL)
  757                 Free(p1);
  758         if (p2 != NULL)
  759                 Free(p2);
  760 }
  761 
  762 #ifndef _KERNEL /* USERLAND test driver */
  763 
  764 /*
  765  * Simple stochastic test driver for the above functions
  766  */
  767 
  768 static void
  769 print_unr(struct unrhdr *uh, struct unr *up)
  770 {
  771         u_int x;
  772         struct unrb *ub;
  773 
  774         printf("  %p len = %5u ", up, up->len);
  775         if (up->ptr == NULL)
  776                 printf("free\n");
  777         else if (up->ptr == uh)
  778                 printf("alloc\n");
  779         else {
  780                 ub = up->ptr;
  781                 printf("bitmap(%d) [", ub->busy);
  782                 for (x = 0; x < up->len; x++) {
  783                         if (bit_test(ub->map, x))
  784                                 printf("#");
  785                         else 
  786                                 printf(" ");
  787                 }
  788                 printf("]\n");
  789         }
  790 }
  791 
  792 static void
  793 print_unrhdr(struct unrhdr *uh)
  794 {
  795         struct unr *up;
  796         u_int x;
  797 
  798         printf(
  799             "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n",
  800             uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
  801         x = uh->low + uh->first;
  802         TAILQ_FOREACH(up, &uh->head, list) {
  803                 printf("  from = %5u", x);
  804                 print_unr(uh, up);
  805                 if (up->ptr == NULL || up->ptr == uh)
  806                         x += up->len;
  807                 else
  808                         x += NBITS;
  809         }
  810 }
  811 
  812 /* Number of unrs to test */
  813 #define NN      10000
  814 
  815 int
  816 main(int argc __unused, const char **argv __unused)
  817 {
  818         struct unrhdr *uh;
  819         u_int i, x, m, j;
  820         char a[NN];
  821 
  822         setbuf(stdout, NULL);
  823         uh = new_unrhdr(0, NN - 1, NULL);
  824         print_unrhdr(uh);
  825 
  826         memset(a, 0, sizeof a);
  827 
  828         fprintf(stderr, "sizeof(struct unr) %d\n", sizeof (struct unr));
  829         fprintf(stderr, "sizeof(struct unrb) %d\n", sizeof (struct unrb));
  830         fprintf(stderr, "sizeof(struct unrhdr) %d\n", sizeof (struct unrhdr));
  831         fprintf(stderr, "NBITS %d\n", NBITS);
  832         x = 1;
  833         for (m = 0; m < NN * 100; m++) {
  834                 j = random();
  835                 i = (j >> 1) % NN;
  836 #if 0
  837                 if (a[i] && (j & 1))
  838                         continue;
  839 #endif
  840                 if (a[i]) {
  841                         printf("F %u\n", i);
  842                         free_unr(uh, i);
  843                         a[i] = 0;
  844                 } else {
  845                         no_alloc = 1;
  846                         i = alloc_unr(uh);
  847                         if (i != -1) {
  848                                 a[i] = 1;
  849                                 printf("A %u\n", i);
  850                         }
  851                         no_alloc = 0;
  852                 }
  853                 if (1)  /* XXX: change this for detailed debug printout */
  854                         print_unrhdr(uh);
  855                 check_unrhdr(uh, __LINE__);
  856         }
  857         for (i = 0; i < NN; i++) {
  858                 if (a[i]) {
  859                         printf("C %u\n", i);
  860                         free_unr(uh, i);
  861                         print_unrhdr(uh);
  862                 }
  863         }
  864         print_unrhdr(uh);
  865         delete_unrhdr(uh);
  866         return (0);
  867 }
  868 #endif

Cache object: 7fe1c3b61fc40ea272f1bf68e37de1a0


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