2 * Copyright (c) 2004 Poul-Henning Kamp
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
29 * Unit number allocation functions.
31 * These functions implement a mixed run-length/bitmap management of unit
32 * number spaces in a very memory efficient manner.
34 * Allocation policy is always lowest free number first.
36 * A return value of -1 signals that no more unit numbers are available.
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.
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()).
47 * The allocation function alloc_unr{l}() never sleeps (but it may block on
48 * the mutex of course).
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.
53 * A userland test program is included.
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.
70 #include <sys/types.h>
71 #include <sys/bitstring.h>
72 #include <sys/_unrhdr.h>
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>
82 #include <sys/mutex.h>
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.
90 static MALLOC_DEFINE(M_UNIT
, "Unitno", "Unit number allocation");
92 #define Malloc(foo) malloc(foo, M_UNIT, M_WAITOK | M_ZERO)
93 #define Free(foo) free(foo, M_UNIT)
95 static struct mtx unitmtx
;
97 MTX_SYSINIT(unit
, &unitmtx
, "unit# allocation", MTX_DEF
);
99 #else /* ...USERLAND */
105 #define KASSERT(cond, arg) \
114 #define Malloc(foo) _Malloc(foo, __LINE__)
116 _Malloc(size_t foo
, int line
)
119 KASSERT(no_alloc
== 0, ("malloc in wrong place() line %d", line
));
120 return (calloc(foo
, 1));
122 #define Free(foo) free(foo)
132 mtx_lock(struct mtx
*mp
)
134 KASSERT(mp
->state
== 0, ("mutex already locked"));
139 mtx_unlock(struct mtx
*mp
)
141 KASSERT(mp
->state
== 1, ("mutex not locked"));
148 mtx_assert(struct mtx
*mp
, int flag
)
150 if (flag
== MA_OWNED
) {
151 KASSERT(mp
->state
== 1, ("mtx_assert(MA_OWNED) not true"));
155 #define CTASSERT(foo)
156 #define WITNESS_WARN(flags, lock, fmt, ...) (void)0
158 #endif /* USERLAND */
161 * This is our basic building block.
163 * It can be used in three different ways depending on the value of the ptr
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.
169 * For runs the len field is the length of the run.
170 * For bitmaps the len field represents the number of allocated items.
172 * The bitmap is the same size as struct unr to optimize memory management.
175 TAILQ_ENTRY(unr
) list
;
182 bitstr_t map
[sizeof(struct unr
) - 1];
185 CTASSERT(sizeof(struct unr
) == sizeof(struct unrb
));
187 /* Number of bits in the bitmap */
188 #define NBITS ((int)sizeof(((struct unrb *)NULL)->map) * 8)
190 #if defined(DIAGNOSTIC) || !defined(_KERNEL)
192 * Consistency check function.
194 * Checks the internal consistency as well as we can.
196 * Called at all boundaries of this API.
199 check_unrhdr(struct unrhdr
*uh
, int line
)
207 TAILQ_FOREACH(up
, &uh
->head
, list
) {
209 if (up
->ptr
!= uh
&& up
->ptr
!= NULL
) {
211 KASSERT (up
->len
<= NBITS
,
212 ("UNR inconsistency: len %u max %d (line %d)\n",
213 up
->len
, NBITS
, line
));
216 for (x
= 0; x
< up
->len
; x
++)
217 if (bit_test(ub
->map
, x
))
219 KASSERT (w
== ub
->busy
,
220 ("UNR inconsistency: busy %u found %u (line %d)\n",
223 } else if (up
->ptr
!= NULL
)
226 KASSERT (y
== uh
->busy
,
227 ("UNR inconsistency: items %u found %u (line %d)\n",
229 KASSERT (z
== uh
->alloc
,
230 ("UNR inconsistency: chunks %u found %u (line %d)\n",
231 uh
->alloc
, z
, line
));
237 check_unrhdr(struct unrhdr
*uh
, int line
)
246 * Userland memory management. Just use calloc and keep track of how
247 * many elements we have allocated for check_unrhdr().
250 static __inline
void *
251 new_unr(struct unrhdr
*uh
, void **p1
, void **p2
)
256 KASSERT(*p1
!= NULL
|| *p2
!= NULL
, ("Out of cached memory"));
269 delete_unr(struct unrhdr
*uh
, void *ptr
)
275 TAILQ_INSERT_TAIL(&uh
->ppfree
, up
, list
);
279 clean_unrhdrl(struct unrhdr
*uh
)
283 mtx_assert(uh
->mtx
, MA_OWNED
);
284 while ((up
= TAILQ_FIRST(&uh
->ppfree
)) != NULL
) {
285 TAILQ_REMOVE(&uh
->ppfree
, up
, list
);
294 clean_unrhdr(struct unrhdr
*uh
)
303 init_unrhdr(struct unrhdr
*uh
, int low
, int high
, struct mtx
*mutex
)
306 KASSERT(low
>= 0 && low
<= high
,
307 ("UNR: use error: new_unrhdr(%d, %d)", low
, high
));
312 TAILQ_INIT(&uh
->head
);
313 TAILQ_INIT(&uh
->ppfree
);
317 uh
->last
= 1 + (high
- low
);
318 check_unrhdr(uh
, __LINE__
);
322 * Allocate a new unrheader set.
324 * Highest and lowest valid values given as parameters.
328 new_unrhdr(int low
, int high
, struct mtx
*mutex
)
332 uh
= Malloc(sizeof *uh
);
333 init_unrhdr(uh
, low
, high
, mutex
);
338 delete_unrhdr(struct unrhdr
*uh
)
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"));
350 is_bitmap(struct unrhdr
*uh
, struct unr
*up
)
352 return (up
->ptr
!= uh
&& up
->ptr
!= NULL
);
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.
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.
362 * NB: called from alloc_unr(), no new memory allocation allowed.
365 optimize_unr(struct unrhdr
*uh
)
367 struct unr
*up
, *uf
, *us
;
368 struct unrb
*ub
, *ubf
;
372 * Look for the run of items (if any) which when collapsed into
373 * a bitmap would save most memory.
377 TAILQ_FOREACH(uf
, &uh
->head
, list
) {
378 if (uf
->len
>= NBITS
)
381 if (is_bitmap(uh
, uf
))
386 up
= TAILQ_NEXT(up
, list
);
389 if ((up
->len
+ l
) > NBITS
)
392 if (is_bitmap(uh
, up
))
405 * If the first element is not a bitmap, make it one.
406 * Trying to do so without allocating more memory complicates things
409 if (!is_bitmap(uh
, us
)) {
410 uf
= TAILQ_NEXT(us
, list
);
411 TAILQ_REMOVE(&uh
->head
, us
, list
);
413 l
= us
->ptr
== uh
? 1 : 0;
417 bit_nset(ub
->map
, 0, a
);
420 bit_nclear(ub
->map
, 0, a
);
422 if (!is_bitmap(uh
, uf
)) {
423 if (uf
->ptr
== NULL
) {
424 bit_nclear(ub
->map
, a
, a
+ uf
->len
- 1);
426 bit_nset(ub
->map
, a
, a
+ uf
->len
- 1);
434 for (l
= 0; l
< uf
->len
; l
++, a
++) {
435 if (bit_test(ubf
->map
, l
)) {
439 bit_clear(ub
->map
, a
);
443 delete_unr(uh
, uf
->ptr
);
450 uf
= TAILQ_NEXT(us
, list
);
453 if (uf
->len
+ us
->len
> NBITS
)
455 if (uf
->ptr
== NULL
) {
456 bit_nclear(ub
->map
, us
->len
, us
->len
+ uf
->len
- 1);
458 TAILQ_REMOVE(&uh
->head
, uf
, list
);
460 } else if (uf
->ptr
== uh
) {
461 bit_nset(ub
->map
, us
->len
, us
->len
+ uf
->len
- 1);
464 TAILQ_REMOVE(&uh
->head
, uf
, list
);
468 for (l
= 0; l
< uf
->len
; l
++, us
->len
++) {
469 if (bit_test(ubf
->map
, l
)) {
470 bit_set(ub
->map
, us
->len
);
473 bit_clear(ub
->map
, us
->len
);
476 TAILQ_REMOVE(&uh
->head
, uf
, list
);
484 * See if a given unr should be collapsed with a neighbor.
486 * NB: called from alloc_unr(), no new memory allocation allowed.
489 collapse_unr(struct unrhdr
*uh
, struct unr
*up
)
494 /* If bitmap is all set or clear, change it to runlength */
495 if (is_bitmap(uh
, up
)) {
497 if (ub
->busy
== up
->len
) {
498 delete_unr(uh
, up
->ptr
);
500 } else if (ub
->busy
== 0) {
501 delete_unr(uh
, up
->ptr
);
506 /* If nothing left in runlength, delete it */
508 upp
= TAILQ_PREV(up
, unrhd
, list
);
510 upp
= TAILQ_NEXT(up
, list
);
511 TAILQ_REMOVE(&uh
->head
, up
, list
);
516 /* If we have "hot-spot" still, merge with neighbor if possible */
518 upp
= TAILQ_PREV(up
, unrhd
, list
);
519 if (upp
!= NULL
&& up
->ptr
== upp
->ptr
) {
521 TAILQ_REMOVE(&uh
->head
, upp
, list
);
524 upp
= TAILQ_NEXT(up
, list
);
525 if (upp
!= NULL
&& up
->ptr
== upp
->ptr
) {
527 TAILQ_REMOVE(&uh
->head
, upp
, list
);
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
);
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
);
552 /* Try to make bitmaps */
553 while (optimize_unr(uh
))
558 * Allocate a free unr.
561 alloc_unrl(struct unrhdr
*uh
)
568 mtx_assert(uh
->mtx
, MA_OWNED
);
569 check_unrhdr(uh
, __LINE__
);
570 x
= uh
->low
+ uh
->first
;
572 up
= TAILQ_FIRST(&uh
->head
);
575 * If we have an ideal split, just adjust the first+last
577 if (up
== NULL
&& uh
->last
> 0) {
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.
591 KASSERT(up
->ptr
!= uh
, ("UNR first element is allocated"));
593 if (up
->ptr
== NULL
) { /* free run */
596 } else { /* bitmap */
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."));
606 collapse_unr(uh
, up
);
611 alloc_unr(struct unrhdr
*uh
)
623 alloc_unr_specificl(struct unrhdr
*uh
, u_int item
, void **p1
, void **p2
)
625 struct unr
*up
, *upn
;
629 mtx_assert(uh
->mtx
, MA_OWNED
);
631 if (item
< uh
->low
+ uh
->first
|| item
> uh
->high
)
634 up
= TAILQ_FIRST(&uh
->head
);
636 if (up
== NULL
&& item
- uh
->low
== uh
->first
) {
640 check_unrhdr(uh
, __LINE__
);
644 i
= item
- uh
->low
- uh
->first
;
647 up
= new_unr(uh
, p1
, p2
);
650 TAILQ_INSERT_TAIL(&uh
->head
, up
, list
);
651 up
= new_unr(uh
, p1
, p2
);
654 TAILQ_INSERT_TAIL(&uh
->head
, up
, list
);
655 uh
->last
= uh
->high
- uh
->low
- i
;
657 check_unrhdr(uh
, __LINE__
);
660 /* Find the item which contains the unit we want to allocate. */
661 TAILQ_FOREACH(up
, &uh
->head
, list
) {
670 up
= new_unr(uh
, p1
, p2
);
673 TAILQ_INSERT_TAIL(&uh
->head
, up
, list
);
675 up
= new_unr(uh
, p1
, p2
);
678 TAILQ_INSERT_TAIL(&uh
->head
, up
, list
);
682 if (is_bitmap(uh
, up
)) {
684 if (bit_test(ub
->map
, i
) == 0) {
690 } else if (up
->ptr
== uh
)
693 KASSERT(up
->ptr
== NULL
,
694 ("alloc_unr_specificl: up->ptr != NULL (up=%p)", up
));
696 /* Split off the tail end, if any. */
697 tl
= up
->len
- (1 + i
);
699 upn
= new_unr(uh
, p1
, p2
);
702 TAILQ_INSERT_AFTER(&uh
->head
, up
, upn
, list
);
705 /* Split off head end, if any */
707 upn
= new_unr(uh
, p1
, p2
);
710 TAILQ_INSERT_BEFORE(up
, upn
, list
);
716 last
= uh
->high
- uh
->low
- (item
- uh
->low
);
720 collapse_unr(uh
, up
);
721 check_unrhdr(uh
, __LINE__
);
726 alloc_unr_specific(struct unrhdr
*uh
, u_int item
)
731 WITNESS_WARN(WARN_GIANTOK
| WARN_SLEEPOK
, NULL
, "alloc_unr_specific");
733 p1
= Malloc(sizeof(struct unr
));
734 p2
= Malloc(sizeof(struct unr
));
737 i
= alloc_unr_specificl(uh
, item
, &p1
, &p2
);
751 * If we can save unrs by using a bitmap, do so.
754 free_unrl(struct unrhdr
*uh
, u_int item
, void **p1
, void **p2
)
756 struct unr
*up
, *upp
, *upn
;
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__
);
765 upp
= TAILQ_FIRST(&uh
->head
);
767 * Freeing in the ideal split case
769 if (item
+ 1 == uh
->first
&& upp
== NULL
) {
773 check_unrhdr(uh
, __LINE__
);
777 * Freeing in the ->first section. Create a run starting at the
778 * freed item. The code below will subdivide it.
780 if (item
< uh
->first
) {
781 up
= new_unr(uh
, p1
, p2
);
783 up
->len
= uh
->first
- item
;
784 TAILQ_INSERT_HEAD(&uh
->head
, up
, list
);
785 uh
->first
-= up
->len
;
790 /* Find the item which contains the unit we want to free */
791 TAILQ_FOREACH(up
, &uh
->head
, list
) {
797 /* Handle bitmap items */
798 if (is_bitmap(uh
, up
)) {
801 KASSERT(bit_test(ub
->map
, item
) != 0,
802 ("UNR: Freeing free item %d (bitmap)\n", item
));
803 bit_clear(ub
->map
, item
);
806 collapse_unr(uh
, up
);
810 KASSERT(up
->ptr
== uh
, ("UNR Freeing free item %d (run))\n", item
));
812 /* Just this one left, reap it */
816 collapse_unr(uh
, up
);
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
) {
826 collapse_unr(uh
, up
);
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
) {
836 collapse_unr(uh
, up
);
840 /* Split off the tail end, if any. */
841 pl
= up
->len
- (1 + item
);
843 upp
= new_unr(uh
, p1
, p2
);
846 TAILQ_INSERT_AFTER(&uh
->head
, up
, upp
, list
);
849 /* Split off head end, if any */
851 upp
= new_unr(uh
, p1
, p2
);
854 TAILQ_INSERT_BEFORE(up
, upp
, list
);
859 collapse_unr(uh
, up
);
863 free_unr(struct unrhdr
*uh
, u_int item
)
867 WITNESS_WARN(WARN_GIANTOK
| WARN_SLEEPOK
, NULL
, "free_unr");
868 p1
= Malloc(sizeof(struct unr
));
869 p2
= Malloc(sizeof(struct unr
));
871 free_unrl(uh
, item
, &p1
, &p2
);
880 #ifndef _KERNEL /* USERLAND test driver */
883 * Simple stochastic test driver for the above functions
887 print_unr(struct unrhdr
*uh
, struct unr
*up
)
892 printf(" %p len = %5u ", up
, up
->len
);
895 else if (up
->ptr
== uh
)
899 printf("bitmap(%d) [", ub
->busy
);
900 for (x
= 0; x
< up
->len
; x
++) {
901 if (bit_test(ub
->map
, x
))
911 print_unrhdr(struct unrhdr
*uh
)
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
);
923 if (up
->ptr
== NULL
|| up
->ptr
== uh
)
931 test_alloc_unr(struct unrhdr
*uh
, u_int i
, char a
[])
951 test_alloc_unr_specific(struct unrhdr
*uh
, u_int i
, char a
[])
955 j
= alloc_unr_specific(uh
, i
);
966 /* Number of unrs to test */
970 main(int argc __unused
, const char **argv __unused
)
976 setbuf(stdout
, NULL
);
977 uh
= new_unrhdr(0, NN
- 1, NULL
);
980 memset(a
, 0, sizeof a
);
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
);
988 for (m
= 0; m
< NN
* 100; m
++) {
995 if ((random() & 1) != 0)
996 test_alloc_unr(uh
, i
, a
);
998 test_alloc_unr_specific(uh
, i
, a
);
1000 if (1) /* XXX: change this for detailed debug printout */
1002 check_unrhdr(uh
, __LINE__
);
1004 for (i
= 0; i
< NN
; i
++) {
1006 printf("C %u\n", i
);