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