FreeBSD/Linux Kernel Cross Reference
sys/kern/subr_unit.c
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/8.0/sys/kern/subr_unit.c 171202 2007-07-04 06:56:58Z kib $
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: 782a5276b62edeffe9176a338acb47fd
|