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
26 * $FreeBSD: src/sys/kern/subr_unit.c,v 1.7 2005/03/14 06:51:29 phk Exp $
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 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 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.
70 #include <sys/types.h>
71 #include <sys/queue.h>
72 #include <sys/bitstring.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>
86 * In theory it would be smarter to allocate the individual blocks
87 * with the zone allocator, but at this time the expectation is that
88 * there will typically not even be enough allocations to fill a single
89 * page, so we stick with malloc for now.
91 static MALLOC_DEFINE(M_UNIT, "Unitno", "Unit number allocation");
93 #define Malloc(foo) kmalloc(foo, M_UNIT, M_WAITOK | M_ZERO)
94 #define Free(foo) kfree(foo, M_UNIT)
96 static struct lock unit_lock;
98 LOCK_SYSINIT(unit, &unit_lock, "unit# allocation", LK_CANRECURSE);
100 #else /* ...USERLAND */
102 /* No unit allocation on DragonFly's userland */
104 #endif /* USERLAND */
107 * This is our basic building block.
109 * It can be used in three different ways depending on the value of the ptr
111 * If ptr is NULL, it represents a run of free items.
112 * If ptr points to the unrhdr it represents a run of allocated items.
113 * Otherwise it points to an bitstring of allocated items.
115 * For runs the len field is the length of the run.
116 * For bitmaps the len field represents the number of allocated items.
118 * The bitmap is the same size as struct unr to optimize memory management.
121 TAILQ_ENTRY(unr) list;
128 bitstr_t map[sizeof(struct unr) - 1];
131 CTASSERT(sizeof(struct unr) == sizeof(struct unrb));
133 /* Number of bits in the bitmap */
134 #define NBITS ((int)sizeof(((struct unrb *)NULL)->map) * 8)
136 /* Header element for a unr number space. */
139 TAILQ_HEAD(unrhd,unr) head;
140 u_int low; /* Lowest item */
141 u_int high; /* Highest item */
142 u_int busy; /* Count of allocated items */
143 u_int alloc; /* Count of memory allocations */
144 u_int first; /* items in allocated from start */
145 u_int last; /* items free at end */
150 #if defined(DIAGNOSTIC) || !defined(_KERNEL)
152 * Consistency check function.
154 * Checks the internal consistency as well as we can.
156 * Called at all boundaries of this API.
159 check_unrhdr(struct unrhdr *uh, int line)
167 TAILQ_FOREACH(up, &uh->head, list) {
169 if (up->ptr != uh && up->ptr != NULL) {
171 KASSERT (up->len <= NBITS,
172 ("UNR inconsistency: len %u max %d (line %d)\n",
173 up->len, NBITS, line));
176 for (x = 0; x < up->len; x++)
177 if (bit_test(ub->map, x))
179 KASSERT (w == ub->busy,
180 ("UNR inconsistency: busy %u found %u (line %d)\n",
183 } else if (up->ptr != NULL)
186 KASSERT (y == uh->busy,
187 ("UNR inconsistency: items %u found %u (line %d)\n",
189 KASSERT (z == uh->alloc,
190 ("UNR inconsistency: chunks %u found %u (line %d)\n",
191 uh->alloc, z, line));
197 check_unrhdr(struct unrhdr *uh, int line)
206 * Userland memory management. Just use calloc and keep track of how
207 * many elements we have allocated for check_unrhdr().
210 static __inline void *
211 new_unr(struct unrhdr *uh, void **p1, void **p2)
216 KASSERT(*p1 != NULL || *p2 != NULL, ("Out of cached memory"));
229 delete_unr(struct unrhdr *uh, void *ptr)
237 * Allocate a new unrheader set.
239 * Highest and lowest valid values given as paramters.
243 new_unrhdr(int low, int high, struct lock *lock)
248 ("UNR: use error: new_unrhdr(%u, %u)", low, high));
249 uh = Malloc(sizeof *uh);
253 uh->lock = &unit_lock;
254 TAILQ_INIT(&uh->head);
258 uh->last = 1 + (high - low);
259 check_unrhdr(uh, __LINE__);
264 delete_unrhdr(struct unrhdr *uh)
267 check_unrhdr(uh, __LINE__);
268 KASSERT(uh->busy == 0, ("unrhdr has %u allocations", uh->busy));
269 KASSERT(uh->alloc == 0, ("UNR memory leak in delete_unrhdr"));
274 is_bitmap(struct unrhdr *uh, struct unr *up)
276 return (up->ptr != uh && up->ptr != NULL);
280 * Look for sequence of items which can be combined into a bitmap, if
281 * multiple are present, take the one which saves most memory.
283 * Return (1) if a sequence was found to indicate that another call
284 * might be able to do more. Return (0) if we found no suitable sequence.
286 * NB: called from alloc_unr(), no new memory allocation allowed.
289 optimize_unr(struct unrhdr *uh)
291 struct unr *up, *uf, *us;
292 struct unrb *ub, *ubf;
296 * Look for the run of items (if any) which when collapsed into
297 * a bitmap would save most memory.
301 TAILQ_FOREACH(uf, &uh->head, list) {
302 if (uf->len >= NBITS)
305 if (is_bitmap(uh, uf))
310 up = TAILQ_NEXT(up, list);
313 if ((up->len + l) > NBITS)
316 if (is_bitmap(uh, up))
329 * If the first element is not a bitmap, make it one.
330 * Trying to do so without allocating more memory complicates things
333 if (!is_bitmap(uh, us)) {
334 uf = TAILQ_NEXT(us, list);
335 TAILQ_REMOVE(&uh->head, us, list);
337 l = us->ptr == uh ? 1 : 0;
341 bit_nset(ub->map, 0, a);
344 bit_nclear(ub->map, 0, a);
346 if (!is_bitmap(uh, uf)) {
347 if (uf->ptr == NULL) {
348 bit_nclear(ub->map, a, a + uf->len - 1);
350 bit_nset(ub->map, a, a + uf->len - 1);
358 for (l = 0; l < uf->len; l++, a++) {
359 if (bit_test(ubf->map, l)) {
363 bit_clear(ub->map, a);
367 delete_unr(uh, uf->ptr);
374 uf = TAILQ_NEXT(us, list);
377 if (uf->len + us->len > NBITS)
379 if (uf->ptr == NULL) {
380 bit_nclear(ub->map, us->len, us->len + uf->len - 1);
382 TAILQ_REMOVE(&uh->head, uf, list);
384 } else if (uf->ptr == uh) {
385 bit_nset(ub->map, us->len, us->len + uf->len - 1);
388 TAILQ_REMOVE(&uh->head, uf, list);
392 for (l = 0; l < uf->len; l++, us->len++) {
393 if (bit_test(ubf->map, l)) {
394 bit_set(ub->map, us->len);
397 bit_clear(ub->map, us->len);
400 TAILQ_REMOVE(&uh->head, uf, list);
408 * See if a given unr should be collapsed with a neighbor.
410 * NB: called from alloc_unr(), no new memory allocation allowed.
413 collapse_unr(struct unrhdr *uh, struct unr *up)
418 /* If bitmap is all set or clear, change it to runlength */
419 if (is_bitmap(uh, up)) {
421 if (ub->busy == up->len) {
422 delete_unr(uh, up->ptr);
424 } else if (ub->busy == 0) {
425 delete_unr(uh, up->ptr);
430 /* If nothing left in runlength, delete it */
432 upp = TAILQ_PREV(up, unrhd, list);
434 upp = TAILQ_NEXT(up, list);
435 TAILQ_REMOVE(&uh->head, up, list);
440 /* If we have "hot-spot" still, merge with neighbor if possible */
442 upp = TAILQ_PREV(up, unrhd, list);
443 if (upp != NULL && up->ptr == upp->ptr) {
445 TAILQ_REMOVE(&uh->head, upp, list);
448 upp = TAILQ_NEXT(up, list);
449 if (upp != NULL && up->ptr == upp->ptr) {
451 TAILQ_REMOVE(&uh->head, upp, list);
456 /* Merge into ->first if possible */
457 upp = TAILQ_FIRST(&uh->head);
458 if (upp != NULL && upp->ptr == uh) {
459 uh->first += upp->len;
460 TAILQ_REMOVE(&uh->head, upp, list);
466 /* Merge into ->last if possible */
467 upp = TAILQ_LAST(&uh->head, unrhd);
468 if (upp != NULL && upp->ptr == NULL) {
469 uh->last += upp->len;
470 TAILQ_REMOVE(&uh->head, upp, list);
476 /* Try to make bitmaps */
477 while (optimize_unr(uh))
482 * Allocate a free unr.
485 alloc_unrl(struct unrhdr *uh)
491 struct lock *ml __debugvar = uh->lock;
492 struct thread *td __debugvar = curthread;
494 KKASSERT(lockstatus(ml, td) != 0);
495 check_unrhdr(uh, __LINE__);
496 x = uh->low + uh->first;
498 up = TAILQ_FIRST(&uh->head);
501 * If we have an ideal split, just adjust the first+last
503 if (up == NULL && uh->last > 0) {
511 * We can always allocate from the first list element, so if we have
512 * nothing on the list, we must have run out of unit numbers.
517 KASSERT(up->ptr != uh, ("UNR first element is allocated"));
519 if (up->ptr == NULL) { /* free run */
522 } else { /* bitmap */
524 KASSERT(ub->busy < up->len, ("UNR bitmap confusion"));
525 bit_ffc(ub->map, up->len, &y);
526 KASSERT(y != -1, ("UNR corruption: No clear bit in bitmap."));
532 collapse_unr(uh, up);
537 alloc_unr(struct unrhdr *uh)
541 lockmgr(uh->lock, LK_EXCLUSIVE);
543 lockmgr(uh->lock, LK_RELEASE);
550 * If we can save unrs by using a bitmap, do so.
553 free_unrl(struct unrhdr *uh, u_int item, void **p1, void **p2)
555 struct unr *up, *upp, *upn;
559 KASSERT(item >= uh->low && item <= uh->high,
560 ("UNR: free_unr(%u) out of range [%u...%u]",
561 item, uh->low, uh->high));
562 check_unrhdr(uh, __LINE__);
564 upp = TAILQ_FIRST(&uh->head);
566 * Freeing in the ideal split case
568 if (item + 1 == uh->first && upp == NULL) {
572 check_unrhdr(uh, __LINE__);
576 * Freeing in the ->first section. Create a run starting at the
577 * freed item. The code below will subdivide it.
579 if (item < uh->first) {
580 up = new_unr(uh, p1, p2);
582 up->len = uh->first - item;
583 TAILQ_INSERT_HEAD(&uh->head, up, list);
584 uh->first -= up->len;
589 /* Find the item which contains the unit we want to free */
590 TAILQ_FOREACH(up, &uh->head, list) {
596 /* Handle bitmap items */
597 if (is_bitmap(uh, up)) {
600 KASSERT(bit_test(ub->map, item) != 0,
601 ("UNR: Freeing free item %d (bitmap)\n", item));
602 bit_clear(ub->map, item);
605 collapse_unr(uh, up);
609 KASSERT(up->ptr == uh, ("UNR Freeing free item %d (run))\n", item));
611 /* Just this one left, reap it */
615 collapse_unr(uh, up);
619 /* Check if we can shift the item into the previous 'free' run */
620 upp = TAILQ_PREV(up, unrhd, list);
621 if (item == 0 && upp != NULL && upp->ptr == NULL) {
625 collapse_unr(uh, up);
629 /* Check if we can shift the item to the next 'free' run */
630 upn = TAILQ_NEXT(up, list);
631 if (item == up->len - 1 && upn != NULL && upn->ptr == NULL) {
635 collapse_unr(uh, up);
639 /* Split off the tail end, if any. */
640 pl = up->len - (1 + item);
642 upp = new_unr(uh, p1, p2);
645 TAILQ_INSERT_AFTER(&uh->head, up, upp, list);
648 /* Split off head end, if any */
650 upp = new_unr(uh, p1, p2);
653 TAILQ_INSERT_BEFORE(up, upp, list);
658 collapse_unr(uh, up);
662 free_unr(struct unrhdr *uh, u_int item)
666 p1 = Malloc(sizeof(struct unr));
667 p2 = Malloc(sizeof(struct unr));
668 lockmgr(uh->lock, LK_EXCLUSIVE);
669 free_unrl(uh, item, &p1, &p2);
670 lockmgr(uh->lock, LK_RELEASE);
677 #ifndef _KERNEL /* USERLAND test driver */
680 * Simple stochastic test driver for the above functions
684 print_unr(struct unrhdr *uh, struct unr *up)
689 printf(" %p len = %5u ", up, up->len);
692 else if (up->ptr == uh)
696 printf("bitmap(%d) [", ub->busy);
697 for (x = 0; x < up->len; x++) {
698 if (bit_test(ub->map, x))
708 print_unrhdr(struct unrhdr *uh)
714 "%p low = %u high = %u first = %u last = %u busy %u chunks = %u\n",
715 uh, uh->low, uh->high, uh->first, uh->last, uh->busy, uh->alloc);
716 x = uh->low + uh->first;
717 TAILQ_FOREACH(up, &uh->head, list) {
718 printf(" from = %5u", x);
720 if (up->ptr == NULL || up->ptr == uh)
727 /* Number of unrs to test */
731 main(int argc __unused, const char **argv __unused)
737 setbuf(stdout, NULL);
738 uh = new_unrhdr(0, NN - 1, NULL);
741 memset(a, 0, sizeof a);
743 fprintf(stderr, "sizeof(struct unr) %d\n", sizeof (struct unr));
744 fprintf(stderr, "sizeof(struct unrb) %d\n", sizeof (struct unrb));
745 fprintf(stderr, "sizeof(struct unrhdr) %d\n", sizeof (struct unrhdr));
746 fprintf(stderr, "NBITS %d\n", NBITS);
748 for (m = 0; m < NN * 100; m++) {
768 if (1) /* XXX: change this for detailed debug printout */
770 check_unrhdr(uh, __LINE__);
772 for (i = 0; i < NN; i++) {