8158afd682062efa76c54b825d51bf110ea657ec
[dragonfly.git] / sys / kern / subr_blist.c
1
2 /*
3  * BLIST.C -    Bitmap allocator/deallocator, using a radix tree with hinting
4  *
5  *      (c)Copyright 1998, Matthew Dillon.  Terms for use and redistribution
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 $
64  * $DragonFly: src/sys/kern/subr_blist.c,v 1.3 2003/11/09 02:22:36 dillon Exp $
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
98 typedef unsigned int u_daddr_t;
99
100 #include <sys/blist.h>
101
102 void panic(const char *ctl, ...);
103
104 #endif
105
106 /*
107  * static support functions
108  */
109
110 static daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count);
111 static daddr_t blst_meta_alloc(blmeta_t *scan, daddr_t blk, 
112                                 daddr_t count, daddr_t radix, int skip);
113 static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count);
114 static void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, 
115                                         daddr_t radix, int skip, daddr_t blk);
116 static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, 
117                                 daddr_t skip, blist_t dest, daddr_t count);
118 static daddr_t  blst_radix_init(blmeta_t *scan, daddr_t radix, 
119                                                 int skip, daddr_t count);
120 #ifndef _KERNEL
121 static void     blst_radix_print(blmeta_t *scan, daddr_t blk, 
122                                         daddr_t radix, int skip, int tab);
123 #endif
124
125 #ifdef _KERNEL
126 static 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
139 blist_t 
140 blist_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
182 void 
183 blist_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
195 daddr_t 
196 blist_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
217 void 
218 blist_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
237 void
238 blist_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
263 void
264 blist_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
292 static daddr_t
293 blst_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
368 static daddr_t
369 blst_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
454 static void
455 blst_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
498 static void 
499 blst_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
593 static 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
689 static daddr_t  
690 blst_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
761 static void     
762 blst_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
842 int
843 main(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
915 void
916 panic(const char *ctl, ...)
917 {
918         __va_list va;
919
920         __va_start(va, ctl);
921         vfprintf(stderr, ctl, va);
922         fprintf(stderr, "\n");
923         __va_end(va);
924         exit(1);
925 }
926
927 #endif
928