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

Cache object: 5a92e8ac68ce07b29c92be9a0aaa6b54


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