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