1 /*
2 * BLIST.C - Bitmap allocator/deallocator, using a radix tree with hinting
3 *
4 * (c)Copyright 1998, Matthew Dillon. Terms for use and redistribution
5 * are covered by the BSD Copyright as found in /usr/src/COPYRIGHT.
6 *
7 * This module implements a general bitmap allocator/deallocator. The
8 * allocator eats around 2 bits per 'block'. The module does not
9 * try to interpret the meaning of a 'block' other then to return
10 * SWAPBLK_NONE on an allocation failure.
11 *
12 * A radix tree is used to maintain the bitmap. Two radix constants are
13 * involved: One for the bitmaps contained in the leaf nodes (typically
14 * 32), and one for the meta nodes (typically 16). Both meta and leaf
15 * nodes have a hint field. This field gives us a hint as to the largest
16 * free contiguous range of blocks under the node. It may contain a
17 * value that is too high, but will never contain a value that is too
18 * low. When the radix tree is searched, allocation failures in subtrees
19 * update the hint.
20 *
21 * The radix tree also implements two collapsed states for meta nodes:
22 * the ALL-ALLOCATED state and the ALL-FREE state. If a meta node is
23 * in either of these two states, all information contained underneath
24 * the node is considered stale. These states are used to optimize
25 * allocation and freeing operations.
26 *
27 * The hinting greatly increases code efficiency for allocations while
28 * the general radix structure optimizes both allocations and frees. The
29 * radix tree should be able to operate well no matter how much
30 * fragmentation there is and no matter how large a bitmap is used.
31 *
32 * Unlike the rlist code, the blist code wires all necessary memory at
33 * creation time. Neither allocations nor frees require interaction with
34 * the memory subsystem. In contrast, the rlist code may allocate memory
35 * on an rlist_free() call. The non-blocking features of the blist code
36 * are used to great advantage in the swap code (vm/nswap_pager.c). The
37 * rlist code uses a little less overall memory then the blist code (but
38 * due to swap interleaving not all that much less), but the blist code
39 * scales much, much better.
40 *
41 * LAYOUT: The radix tree is layed out recursively using a
42 * linear array. Each meta node is immediately followed (layed out
43 * sequentially in memory) by BLIST_META_RADIX lower level nodes. This
44 * is a recursive structure but one that can be easily scanned through
45 * a very simple 'skip' calculation. In order to support large radixes,
46 * portions of the tree may reside outside our memory allocation. We
47 * handle this with an early-termination optimization (when bighint is
48 * set to -1) on the scan. The memory allocation is only large enough
49 * to cover the number of blocks requested at creation time even if it
50 * must be encompassed in larger root-node radix.
51 *
52 * NOTE: the allocator cannot currently allocate more then
53 * BLIST_BMAP_RADIX blocks per call. It will panic with 'allocation too
54 * large' if you try. This is an area that could use improvement. The
55 * radix is large enough that this restriction does not effect the swap
56 * system, though. Currently only the allocation code is effected by
57 * this algorithmic unfeature. The freeing code can handle arbitrary
58 * ranges.
59 *
60 * This code can be compiled stand-alone for debugging.
61 *
62 * $FreeBSD: src/sys/kern/subr_blist.c,v 1.5.2.1 2000/03/17 10:47:29 ps Exp $
63 */
64
65 typedef unsigned int u_daddr_t;
66
67 #include <sys/param.h>
68 #include <sys/systm.h>
69 #include <sys/lock.h>
70 #include <sys/kernel.h>
71 #include "blist.h"
72 #include <sys/malloc.h>
73
74 #if !defined(__APPLE__)
75 #define SWAPBLK_NONE ((daddr_t)-1)
76 #endif
77
78 #define malloc _MALLOC
79 #define free _FREE
80 #define M_SWAP M_TEMP
81
82 /*
83 * static support functions
84 */
85
86 static daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count);
87 static daddr_t blst_meta_alloc(blmeta_t *scan, daddr_t blk,
88 daddr_t count, daddr_t radix, int skip);
89 static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count);
90 static void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count,
91 daddr_t radix, int skip, daddr_t blk);
92 static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
93 daddr_t skip, blist_t dest, daddr_t count);
94 static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix,
95 int skip, daddr_t count);
96
97 /*
98 * blist_create() - create a blist capable of handling up to the specified
99 * number of blocks
100 *
101 * blocks must be greater then 0
102 *
103 * The smallest blist consists of a single leaf node capable of
104 * managing BLIST_BMAP_RADIX blocks.
105 */
106
107 blist_t
blist_create(daddr_t blocks)108 blist_create(daddr_t blocks)
109 {
110 blist_t bl;
111 int radix;
112 int skip = 0;
113
114 /*
115 * Calculate radix and skip field used for scanning.
116 */
117 radix = BLIST_BMAP_RADIX;
118
119 while (radix < blocks) {
120 radix <<= BLIST_META_RADIX_SHIFT;
121 skip = (skip + 1) << BLIST_META_RADIX_SHIFT;
122 }
123
124 bl = kalloc_type(struct blist, Z_ZERO | Z_WAITOK);
125
126 bl->bl_blocks = blocks;
127 bl->bl_radix = radix;
128 bl->bl_skip = skip;
129 bl->bl_rootblks = 1 +
130 blst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks);
131 bl->bl_root = (blmeta_t *)kalloc_data(sizeof(blmeta_t) * bl->bl_rootblks, Z_WAITOK);
132
133 #if defined(BLIST_DEBUG)
134 printf(
135 "BLIST representing %d blocks (%d MB of swap)"
136 ", requiring %dK of ram\n",
137 bl->bl_blocks,
138 bl->bl_blocks * 4 / 1024,
139 (bl->bl_rootblks * sizeof(blmeta_t) + 1023) / 1024
140 );
141 printf("BLIST raw radix tree contains %d records\n", bl->bl_rootblks);
142 #endif
143 blst_radix_init(bl->bl_root, bl->bl_radix, bl->bl_skip, blocks);
144
145 return bl;
146 }
147
148 void
blist_destroy(blist_t bl)149 blist_destroy(blist_t bl)
150 {
151 kfree_data(bl->bl_root, sizeof(blmeta_t) * bl->bl_rootblks);
152 kfree_type(struct blist, bl);
153 }
154
155 /*
156 * blist_alloc() - reserve space in the block bitmap. Return the base
157 * of a contiguous region or SWAPBLK_NONE if space could
158 * not be allocated.
159 */
160
161 daddr_t
blist_alloc(blist_t bl,daddr_t count)162 blist_alloc(blist_t bl, daddr_t count)
163 {
164 daddr_t blk = SWAPBLK_NONE;
165
166 if (bl) {
167 if (bl->bl_radix == BLIST_BMAP_RADIX) {
168 blk = blst_leaf_alloc(bl->bl_root, 0, count);
169 } else {
170 blk = blst_meta_alloc(bl->bl_root, 0, count,
171 bl->bl_radix, bl->bl_skip);
172 }
173 if (blk != SWAPBLK_NONE) {
174 bl->bl_free -= count;
175 }
176 }
177 return blk;
178 }
179
180 /*
181 * blist_free() - free up space in the block bitmap. Return the base
182 * of a contiguous region. Panic if an inconsistancy is
183 * found.
184 */
185
186 void
blist_free(blist_t bl,daddr_t blkno,daddr_t count)187 blist_free(blist_t bl, daddr_t blkno, daddr_t count)
188 {
189 if (bl) {
190 if (bl->bl_radix == BLIST_BMAP_RADIX) {
191 blst_leaf_free(bl->bl_root, blkno, count);
192 } else {
193 blst_meta_free(bl->bl_root, blkno, count,
194 bl->bl_radix, bl->bl_skip, 0);
195 }
196 bl->bl_free += count;
197 }
198 }
199
200 /*
201 * blist_resize() - resize an existing radix tree to handle the
202 * specified number of blocks. This will reallocate
203 * the tree and transfer the previous bitmap to the new
204 * one. When extending the tree you can specify whether
205 * the new blocks are to left allocated or freed.
206 */
207
208 void
blist_resize(blist_t * pbl,daddr_t count,int freenew)209 blist_resize(blist_t *pbl, daddr_t count, int freenew)
210 {
211 blist_t newbl = blist_create(count);
212 blist_t save = *pbl;
213
214 *pbl = newbl;
215 if (count > save->bl_blocks) {
216 count = save->bl_blocks;
217 }
218 blst_copy(save->bl_root, 0, save->bl_radix, save->bl_skip, newbl, count);
219
220 /*
221 * If resizing upwards, should we free the new space or not?
222 */
223 if (freenew && count < newbl->bl_blocks) {
224 blist_free(newbl, count, newbl->bl_blocks - count);
225 }
226 blist_destroy(save);
227 }
228
229 #ifdef BLIST_DEBUG
230
231 /*
232 * blist_print() - dump radix tree
233 */
234
235 void
blist_print(blist_t bl)236 blist_print(blist_t bl)
237 {
238 printf("BLIST {\n");
239 blst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4);
240 printf("}\n");
241 }
242
243 #endif
244
245 /************************************************************************
246 * ALLOCATION SUPPORT FUNCTIONS *
247 ************************************************************************
248 *
249 * These support functions do all the actual work. They may seem
250 * rather longish, but that's because I've commented them up. The
251 * actual code is straight forward.
252 *
253 */
254
255 /*
256 * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap).
257 *
258 * This is the core of the allocator and is optimized for the 1 block
259 * and the BLIST_BMAP_RADIX block allocation cases. Other cases are
260 * somewhat slower. The 1 block allocation case is log2 and extremely
261 * quick.
262 */
263
264 static daddr_t
blst_leaf_alloc(blmeta_t * scan,daddr_t blk,int count)265 blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count)
266 {
267 u_daddr_t orig = scan->u.bmu_bitmap;
268
269 if (orig == 0) {
270 /*
271 * Optimize bitmap all-allocated case. Also, count = 1
272 * case assumes at least 1 bit is free in the bitmap, so
273 * we have to take care of this case here.
274 */
275 scan->bm_bighint = 0;
276 return SWAPBLK_NONE;
277 }
278 if (count == 1) {
279 /*
280 * Optimized code to allocate one bit out of the bitmap
281 */
282 u_daddr_t mask;
283 int j = BLIST_BMAP_RADIX / 2;
284 int r = 0;
285
286 mask = (u_daddr_t)-1 >> (BLIST_BMAP_RADIX / 2);
287
288 while (j) {
289 if ((orig & mask) == 0) {
290 r += j;
291 orig >>= j;
292 }
293 j >>= 1;
294 mask >>= j;
295 }
296 scan->u.bmu_bitmap &= ~(1 << r);
297 return blk + r;
298 }
299 #if !defined(__APPLE__)
300 if (count <= BLIST_BMAP_RADIX) {
301 #else
302 if (count <= (int)BLIST_BMAP_RADIX) {
303 #endif /* __APPLE__ */
304 /*
305 * non-optimized code to allocate N bits out of the bitmap.
306 * The more bits, the faster the code runs. It will run
307 * the slowest allocating 2 bits, but since there aren't any
308 * memory ops in the core loop (or shouldn't be, anyway),
309 * you probably won't notice the difference.
310 */
311 int j;
312 int n = BLIST_BMAP_RADIX - count;
313 u_daddr_t mask;
314
315 mask = (u_daddr_t)-1 >> n;
316
317 for (j = 0; j <= n; ++j) {
318 if ((orig & mask) == mask) {
319 scan->u.bmu_bitmap &= ~mask;
320 return blk + j;
321 }
322 mask = (mask << 1);
323 }
324 }
325 /*
326 * We couldn't allocate count in this subtree, update bighint.
327 */
328 scan->bm_bighint = count - 1;
329 return SWAPBLK_NONE;
330 }
331
332 /*
333 * blist_meta_alloc() - allocate at a meta in the radix tree.
334 *
335 * Attempt to allocate at a meta node. If we can't, we update
336 * bighint and return a failure. Updating bighint optimize future
337 * calls that hit this node. We have to check for our collapse cases
338 * and we have a few optimizations strewn in as well.
339 */
340
341 static daddr_t
342 blst_meta_alloc(blmeta_t *scan, daddr_t blk, daddr_t count, daddr_t radix,
343 int skip)
344 {
345 int i;
346 int next_skip = (skip >> BLIST_META_RADIX_SHIFT);
347
348 if (scan->u.bmu_avail == 0) {
349 /*
350 * ALL-ALLOCATED special case
351 */
352 scan->bm_bighint = count;
353 return SWAPBLK_NONE;
354 }
355
356 if (scan->u.bmu_avail == radix) {
357 radix >>= BLIST_META_RADIX_SHIFT;
358
359 /*
360 * ALL-FREE special case, initialize uninitialize
361 * sublevel.
362 */
363 for (i = 1; i <= skip; i += next_skip) {
364 if (scan[i].bm_bighint == (daddr_t)-1) {
365 break;
366 }
367 if (next_skip == 1) {
368 scan[i].u.bmu_bitmap = (u_daddr_t)-1;
369 scan[i].bm_bighint = BLIST_BMAP_RADIX;
370 } else {
371 scan[i].bm_bighint = radix;
372 scan[i].u.bmu_avail = radix;
373 }
374 }
375 } else {
376 radix >>= BLIST_META_RADIX_SHIFT;
377 }
378
379 for (i = 1; i <= skip; i += next_skip) {
380 if (count <= scan[i].bm_bighint) {
381 /*
382 * count fits in object
383 */
384 daddr_t r;
385 if (next_skip == 1) {
386 r = blst_leaf_alloc(&scan[i], blk, count);
387 } else {
388 r = blst_meta_alloc(&scan[i], blk, count,
389 radix, next_skip - 1);
390 }
391 if (r != SWAPBLK_NONE) {
392 scan->u.bmu_avail -= count;
393 if (scan->bm_bighint > scan->u.bmu_avail) {
394 scan->bm_bighint = scan->u.bmu_avail;
395 }
396 return r;
397 }
398 } else if (scan[i].bm_bighint == (daddr_t)-1) {
399 /*
400 * Terminator
401 */
402 break;
403 } else if (count > radix) {
404 /*
405 * count does not fit in object even if it were
406 * complete free.
407 */
408 panic("blist_meta_alloc: allocation too large");
409 }
410 blk += radix;
411 }
412
413 /*
414 * We couldn't allocate count in this subtree, update bighint.
415 */
416 if (scan->bm_bighint >= count) {
417 scan->bm_bighint = count - 1;
418 }
419 return SWAPBLK_NONE;
420 }
421
422 /*
423 * BLST_LEAF_FREE() - free allocated block from leaf bitmap
424 *
425 */
426
427 static void
428 blst_leaf_free(blmeta_t *scan, daddr_t blk, int count)
429 {
430 /*
431 * free some data in this bitmap
432 *
433 * e.g.
434 * 0000111111111110000
435 * \_________/\__/
436 * v n
437 */
438 int n = blk & (BLIST_BMAP_RADIX - 1);
439 u_daddr_t mask;
440
441 mask = ((u_daddr_t)-1 << n) &
442 ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n));
443
444 if (scan->u.bmu_bitmap & mask) {
445 panic("blst_radix_free: freeing free block");
446 }
447 scan->u.bmu_bitmap |= mask;
448
449 /*
450 * We could probably do a better job here. We are required to make
451 * bighint at least as large as the biggest contiguous block of
452 * data. If we just shoehorn it, a little extra overhead will
453 * be incured on the next allocation (but only that one typically).
454 */
455 scan->bm_bighint = BLIST_BMAP_RADIX;
456 }
457
458 /*
459 * BLST_META_FREE() - free allocated blocks from radix tree meta info
460 *
461 * This support routine frees a range of blocks from the bitmap.
462 * The range must be entirely enclosed by this radix node. If a
463 * meta node, we break the range down recursively to free blocks
464 * in subnodes (which means that this code can free an arbitrary
465 * range whereas the allocation code cannot allocate an arbitrary
466 * range).
467 */
468
469 static void
470 blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, daddr_t radix,
471 int skip, daddr_t blk)
472 {
473 int i;
474 int next_skip = (skip >> BLIST_META_RADIX_SHIFT);
475
476 #if 0
477 printf("FREE (%x,%d) FROM (%x,%d)\n",
478 freeBlk, count,
479 blk, radix
480 );
481 #endif
482
483 if (scan->u.bmu_avail == 0) {
484 /*
485 * ALL-ALLOCATED special case, with possible
486 * shortcut to ALL-FREE special case.
487 */
488 scan->u.bmu_avail = count;
489 scan->bm_bighint = count;
490
491 if (count != radix) {
492 for (i = 1; i <= skip; i += next_skip) {
493 if (scan[i].bm_bighint == (daddr_t)-1) {
494 break;
495 }
496 scan[i].bm_bighint = 0;
497 if (next_skip == 1) {
498 scan[i].u.bmu_bitmap = 0;
499 } else {
500 scan[i].u.bmu_avail = 0;
501 }
502 }
503 /* fall through */
504 }
505 } else {
506 scan->u.bmu_avail += count;
507 /* scan->bm_bighint = radix; */
508 }
509
510 /*
511 * ALL-FREE special case.
512 */
513
514 if (scan->u.bmu_avail == radix) {
515 return;
516 }
517 if (scan->u.bmu_avail > radix) {
518 panic("blst_meta_free: freeing already free blocks (%d) %d/%d", count, scan->u.bmu_avail, radix);
519 }
520
521 /*
522 * Break the free down into its components
523 */
524
525 radix >>= BLIST_META_RADIX_SHIFT;
526
527 i = (freeBlk - blk) / radix;
528 blk += i * radix;
529 i = i * next_skip + 1;
530
531 while (i <= skip && blk < freeBlk + count) {
532 daddr_t v;
533
534 v = blk + radix - freeBlk;
535 if (v > count) {
536 v = count;
537 }
538
539 if (scan->bm_bighint == (daddr_t)-1) {
540 panic("blst_meta_free: freeing unexpected range");
541 }
542
543 if (next_skip == 1) {
544 blst_leaf_free(&scan[i], freeBlk, v);
545 } else {
546 blst_meta_free(&scan[i], freeBlk, v, radix,
547 next_skip - 1, blk);
548 }
549 if (scan->bm_bighint < scan[i].bm_bighint) {
550 scan->bm_bighint = scan[i].bm_bighint;
551 }
552 count -= v;
553 freeBlk += v;
554 blk += radix;
555 i += next_skip;
556 }
557 }
558
559 /*
560 * BLIST_RADIX_COPY() - copy one radix tree to another
561 *
562 * Locates free space in the source tree and frees it in the destination
563 * tree. The space may not already be free in the destination.
564 */
565
566 static void
567 blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix,
568 daddr_t skip, blist_t dest, daddr_t count)
569 {
570 int next_skip;
571 int i;
572
573 /*
574 * Leaf node
575 */
576
577 if (radix == BLIST_BMAP_RADIX) {
578 u_daddr_t v = scan->u.bmu_bitmap;
579
580 if (v == (u_daddr_t)-1) {
581 blist_free(dest, blk, count);
582 } else if (v != 0) {
583 #if !defined(__APPLE__)
584 int i;
585
586 for (i = 0; i < BLIST_BMAP_RADIX && i < count; ++i) {
587 if (v & (1 << i)) {
588 blist_free(dest, blk + i, 1);
589 }
590 }
591 #else
592 int j; /* Avoid shadow warnings */
593
594 for (j = 0; j < (int)BLIST_BMAP_RADIX && j < count; ++j) {
595 if (v & (1 << j)) {
596 blist_free(dest, blk + j, 1);
597 }
598 }
599 #endif /* __APPLE__ */
600 }
601 return;
602 }
603
604 /*
605 * Meta node
606 */
607
608 /*
609 * Source all allocated, leave dest allocated
610 */
611 if (scan->u.bmu_avail == 0) {
612 return;
613 }
614 if (scan->u.bmu_avail == radix) {
615 /*
616 * Source all free, free entire dest
617 */
618 if (count < radix) {
619 blist_free(dest, blk, count);
620 } else {
621 blist_free(dest, blk, radix);
622 }
623 return;
624 }
625
626 radix >>= BLIST_META_RADIX_SHIFT;
627 next_skip = (skip >> BLIST_META_RADIX_SHIFT);
628
629 for (i = 1; count && i <= skip; i += next_skip) {
630 if (scan[i].bm_bighint == (daddr_t)-1) {
631 break;
632 }
633
634 if (count >= radix) {
635 blst_copy(
636 &scan[i],
637 blk,
638 radix,
639 next_skip - 1,
640 dest,
641 radix
642 );
643 count -= radix;
644 } else {
645 if (count) {
646 blst_copy(
647 &scan[i],
648 blk,
649 radix,
650 next_skip - 1,
651 dest,
652 count
653 );
654 }
655 count = 0;
656 }
657 blk += radix;
658 }
659 }
660
661 /*
662 * BLST_RADIX_INIT() - initialize radix tree
663 *
664 * Initialize our meta structures and bitmaps and calculate the exact
665 * amount of space required to manage 'count' blocks - this space may
666 * be considerably less then the calculated radix due to the large
667 * RADIX values we use.
668 */
669
670 static daddr_t
671 blst_radix_init(blmeta_t *scan, daddr_t radix, int skip, daddr_t count)
672 {
673 int i;
674 int next_skip;
675 daddr_t memindex = 0;
676
677 /*
678 * Leaf node
679 */
680
681 if (radix == BLIST_BMAP_RADIX) {
682 if (scan) {
683 scan->bm_bighint = 0;
684 scan->u.bmu_bitmap = 0;
685 }
686 return memindex;
687 }
688
689 /*
690 * Meta node. If allocating the entire object we can special
691 * case it. However, we need to figure out how much memory
692 * is required to manage 'count' blocks, so we continue on anyway.
693 */
694
695 if (scan) {
696 scan->bm_bighint = 0;
697 scan->u.bmu_avail = 0;
698 }
699
700 radix >>= BLIST_META_RADIX_SHIFT;
701 next_skip = (skip >> BLIST_META_RADIX_SHIFT);
702
703 for (i = 1; i <= skip; i += next_skip) {
704 if (count >= radix) {
705 /*
706 * Allocate the entire object
707 */
708 memindex = i + blst_radix_init(
709 ((scan) ? &scan[i] : NULL),
710 radix,
711 next_skip - 1,
712 radix
713 );
714 count -= radix;
715 } else if (count > 0) {
716 /*
717 * Allocate a partial object
718 */
719 memindex = i + blst_radix_init(
720 ((scan) ? &scan[i] : NULL),
721 radix,
722 next_skip - 1,
723 count
724 );
725 count = 0;
726 } else {
727 /*
728 * Add terminator and break out
729 */
730 if (scan) {
731 scan[i].bm_bighint = (daddr_t)-1;
732 }
733 break;
734 }
735 }
736 if (memindex < i) {
737 memindex = i;
738 }
739 return memindex;
740 }
741
742 #ifdef BLIST_DEBUG
743
744 static void
745 blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int skip, int tab)
746 {
747 int i;
748 int next_skip;
749 int lastState = 0;
750
751 if (radix == BLIST_BMAP_RADIX) {
752 printf(
753 "%*.*s(%04x,%d): bitmap %08x big=%d\n",
754 tab, tab, "",
755 blk, radix,
756 scan->u.bmu_bitmap,
757 scan->bm_bighint
758 );
759 return;
760 }
761
762 if (scan->u.bmu_avail == 0) {
763 printf(
764 "%*.*s(%04x,%d) ALL ALLOCATED\n",
765 tab, tab, "",
766 blk,
767 radix
768 );
769 return;
770 }
771 if (scan->u.bmu_avail == radix) {
772 printf(
773 "%*.*s(%04x,%d) ALL FREE\n",
774 tab, tab, "",
775 blk,
776 radix
777 );
778 return;
779 }
780
781 printf(
782 "%*.*s(%04x,%d): subtree (%d/%d) big=%d {\n",
783 tab, tab, "",
784 blk, radix,
785 scan->u.bmu_avail,
786 radix,
787 scan->bm_bighint
788 );
789
790 radix >>= BLIST_META_RADIX_SHIFT;
791 next_skip = (skip >> BLIST_META_RADIX_SHIFT);
792 tab += 4;
793
794 for (i = 1; i <= skip; i += next_skip) {
795 if (scan[i].bm_bighint == (daddr_t)-1) {
796 printf(
797 "%*.*s(%04x,%d): Terminator\n",
798 tab, tab, "",
799 blk, radix
800 );
801 lastState = 0;
802 break;
803 }
804 blst_radix_print(
805 &scan[i],
806 blk,
807 radix,
808 next_skip - 1,
809 tab
810 );
811 blk += radix;
812 }
813 tab -= 4;
814
815 printf(
816 "%*.*s}\n",
817 tab, tab, ""
818 );
819 }
820
821 #endif
822
823 #ifdef BLIST_DEBUG
824
825 int
826 main(int ac, char **av)
827 {
828 int size = 1024;
829 int i;
830 blist_t bl;
831
832 for (i = 1; i < ac; ++i) {
833 const char *ptr = av[i];
834 if (*ptr != '-') {
835 size = strtol(ptr, NULL, 0);
836 continue;
837 }
838 ptr += 2;
839 fprintf(stderr, "Bad option: %s\n", ptr - 2);
840 exit(1);
841 }
842 bl = blist_create(size);
843 blist_free(bl, 0, size);
844
845 for (;;) {
846 char buf[1024];
847 daddr_t da = 0;
848 daddr_t count = 0;
849
850
851 printf("%d/%d/%d> ", bl->bl_free, size, bl->bl_radix);
852 fflush(stdout);
853 if (fgets(buf, sizeof(buf), stdin) == NULL) {
854 break;
855 }
856 switch (buf[0]) {
857 case 'r':
858 if (sscanf(buf + 1, "%d", &count) == 1) {
859 blist_resize(&bl, count, 1);
860 } else {
861 printf("?\n");
862 }
863 case 'p':
864 blist_print(bl);
865 break;
866 case 'a':
867 if (sscanf(buf + 1, "%d", &count) == 1) {
868 daddr_t blk = blist_alloc(bl, count);
869 printf(" R=%04x\n", blk);
870 } else {
871 printf("?\n");
872 }
873 break;
874 case 'f':
875 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) {
876 blist_free(bl, da, count);
877 } else {
878 printf("?\n");
879 }
880 break;
881 case '?':
882 case 'h':
883 puts(
884 "p -print\n"
885 "a %d -allocate\n"
886 "f %x %d -free\n"
887 "r %d -resize\n"
888 "h/? -help"
889 );
890 break;
891 default:
892 printf("?\n");
893 break;
894 }
895 }
896 return 0;
897 }
898
899 void
900 panic(const char *ctl, ...)
901 {
902 va_list va;
903
904 va_start(va, ctl);
905 vfprintf(stderr, ctl, va);
906 fprintf(stderr, "\n");
907 va_end(va);
908 exit(1);
909 }
910
911 #endif
912