d469c1b1112b2b957266eae694fff3599df2d427
[dragonfly.git] / sys / vfs / hammer / hammer_alist.c
1 /*
2  * HAMMER_ALIST.C -
3  *
4  * Bitmap allocator/deallocator, using a radix tree with hinting.
5  * Unlimited-size allocations, power-of-2 only, power-of-2 aligned results
6  * only.  This module has been separated from the generic kernel module and
7  * written specifically for embedding in HAMMER storage structures.
8  * 
9  * Copyright (c) 2007 The DragonFly Project.  All rights reserved.
10  * 
11  * This code is derived from software contributed to The DragonFly Project
12  * by Matthew Dillon <dillon@backplane.com>
13  * 
14  * Redistribution and use in source and binary forms, with or without
15  * modification, are permitted provided that the following conditions
16  * are met:
17  * 
18  * 1. Redistributions of source code must retain the above copyright
19  *    notice, this list of conditions and the following disclaimer.
20  * 2. Redistributions in binary form must reproduce the above copyright
21  *    notice, this list of conditions and the following disclaimer in
22  *    the documentation and/or other materials provided with the
23  *    distribution.
24  * 3. Neither the name of The DragonFly Project nor the names of its
25  *    contributors may be used to endorse or promote products derived
26  *    from this software without specific, prior written permission.
27  * 
28  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
31  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
32  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
33  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
34  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
35  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
36  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
37  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
38  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
39  * SUCH DAMAGE.
40  *
41  * $DragonFly: src/sys/vfs/hammer/Attic/hammer_alist.c,v 1.1 2007/10/10 19:37:25 dillon Exp $
42  */
43 /*
44  * This module implements a generic allocator through the use of a hinted
45  * radix tree.  All allocations must be in powers of 2 and will return
46  * similarly aligned results.  The radix tree typically recurses within
47  * a memory buffer and then continues its recursion by chaining to other
48  * memory buffers, creating a seemless whole capable of managing any amount
49  * of storage.
50  *
51  * The radix tree is layed out recursively using a linear array.  Each meta
52  * node is immediately followed (layed out sequentially in memory) by
53  * HAMMER_ALIST_META_RADIX lower level nodes.  This is a recursive structure
54  * but one that can be easily scanned through a very simple 'skip'
55  * calculation.
56  *
57  * The radix tree supports an early-termination optimization which
58  * effectively allows us to efficiently mix large and small allocations
59  * with a single abstraction.  The address space can be partitioned
60  * arbitrarily without adding much in the way of additional meta-storage
61  * for the allocator.
62  *
63  * This code can be compiled stand-alone for debugging.
64  */
65
66 #ifdef _KERNEL
67
68 #include <sys/param.h>
69 #include <sys/systm.h>
70 #include <sys/lock.h>
71 #include <sys/kernel.h>
72 #include <sys/malloc.h>
73 #include <vm/vm.h>
74 #include <vm/vm_object.h>
75 #include <vm/vm_kern.h>
76 #include <vm/vm_extern.h>
77 #include <vm/vm_page.h>
78
79 #include "hammerfs.h"
80
81 #else
82
83 #ifndef ALIST_NO_DEBUG
84 #define ALIST_DEBUG
85 #endif
86
87 #include <sys/types.h>
88 #include <stdio.h>
89 #include <assert.h>
90 #include <string.h>
91 #include <stdlib.h>
92 #include <stdarg.h>
93
94 #define kmalloc(a,b,c)  malloc(a)
95 #define kfree(a,b)      free(a)
96 #define kprintf         printf
97 #define KKASSERT(exp)   assert(exp)
98 struct malloc_type;
99
100 #include "hammerfs.h"
101
102 void panic(const char *ctl, ...);
103
104 #endif
105
106 /*
107  * static support functions
108  */
109
110 static int32_t hammer_alst_leaf_alloc_fwd(hammer_almeta_t *scan,
111                                         int32_t blk, int count);
112 static int32_t hammer_alst_meta_alloc_fwd(hammer_almeta_t *scan,
113                                         int32_t blk, int32_t count,
114                                         int32_t radix, int skip);
115 static int32_t hammer_alst_leaf_alloc_rev(hammer_almeta_t *scan,
116                                         int32_t blk, int count);
117 static int32_t hammer_alst_meta_alloc_rev(hammer_almeta_t *scan,
118                                         int32_t blk, int32_t count,
119                                         int32_t radix, int skip);
120 static void hammer_alst_leaf_free(hammer_almeta_t *scan,
121                                         int32_t relblk, int count);
122 static void hammer_alst_meta_free(hammer_almeta_t *scan,
123                                         int32_t freeBlk, int32_t count, 
124                                         int32_t radix, int skip, int32_t blk);
125 static int32_t  hammer_alst_radix_init(hammer_almeta_t *scan,
126                                         int32_t radix, int skip, int32_t count);
127 #ifdef ALIST_DEBUG
128 static void     hammer_alst_radix_print(hammer_almeta_t *scan,
129                                         int32_t blk,
130                                         int32_t radix, int skip, int tab);
131 #endif
132
133 /*
134  * Initialize an alist for use.  The alist will initially be marked
135  * all-allocated so the caller must free the portion it wishes to manage.
136  */
137 void
138 hammer_alist_template(hammer_alist_t bl, int blocks, int maxmeta)
139 {
140         int radix;
141         int skip = 0;
142
143         /*
144          * Calculate radix and skip field used for scanning.
145          */
146         radix = HAMMER_ALIST_BMAP_RADIX;
147
148         while (radix < blocks) {
149                 radix *= HAMMER_ALIST_META_RADIX;
150                 skip = (skip + 1) * HAMMER_ALIST_META_RADIX;
151         }
152
153         bzero(bl, sizeof(*bl));
154
155         bl->bl_blocks = blocks;
156         bl->bl_radix = radix;
157         bl->bl_skip = skip;
158         bl->bl_rootblks = 1 +
159             hammer_alst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks);
160         KKASSERT(bl->bl_rootblks <= maxmeta);
161
162 #if defined(ALIST_DEBUG)
163         kprintf(
164                 "ALIST representing %d blocks (%d MB of swap)"
165                 ", requiring %dK (%d bytes) of ram\n",
166                 bl->bl_blocks,
167                 bl->bl_blocks * 4 / 1024,
168                 (bl->bl_rootblks * sizeof(hammer_almeta_t) + 1023) / 1024,
169                 (bl->bl_rootblks * sizeof(hammer_almeta_t))
170         );
171         kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
172 #endif
173 }
174
175 void
176 hammer_alist_init(hammer_alist_t bl, hammer_almeta_t *meta)
177 {
178         hammer_alst_radix_init(meta, bl->bl_radix, bl->bl_skip, bl->bl_blocks);
179 }
180
181 #if !defined(_KERNEL) && defined(ALIST_DEBUG)
182
183 /*
184  * hammer_alist_create()        (userland only)
185  *
186  *      create a alist capable of handling up to the specified number of
187  *      blocks.  blocks must be greater then 0
188  *
189  *      The smallest alist consists of a single leaf node capable of 
190  *      managing HAMMER_ALIST_BMAP_RADIX blocks.
191  */
192
193 hammer_alist_t 
194 hammer_alist_create(int32_t blocks, struct malloc_type *mtype,
195                     hammer_almeta_t **metap)
196 {
197         hammer_alist_t bl;
198         hammer_almeta_t *meta;
199         int radix;
200         int skip = 0;
201         int rootblks;
202         size_t metasize;
203
204         /*
205          * Calculate radix and skip field used for scanning.
206          */
207         radix = HAMMER_ALIST_BMAP_RADIX;
208
209         while (radix < blocks) {
210                 radix *= HAMMER_ALIST_META_RADIX;
211                 skip = (skip + 1) * HAMMER_ALIST_META_RADIX;
212         }
213
214         rootblks = 1 + hammer_alst_radix_init(NULL, radix, skip, blocks);
215         metasize = sizeof(struct hammer_almeta) * rootblks;
216         bl = kmalloc(sizeof(struct hammer_alist), mtype, M_WAITOK);
217         meta = kmalloc(metasize, mtype, M_WAITOK);
218
219         bzero(bl, sizeof(*bl));
220         bzero(meta, metasize);
221
222         bl->bl_blocks = blocks;
223         bl->bl_radix = radix;
224         bl->bl_skip = skip;
225         bl->bl_rootblks = rootblks;
226
227 #if defined(ALIST_DEBUG)
228         kprintf(
229                 "ALIST representing %d blocks (%d MB of swap)"
230                 ", requiring %dK (%d bytes) of ram\n",
231                 bl->bl_blocks,
232                 bl->bl_blocks * 4 / 1024,
233                 (bl->bl_rootblks * sizeof(hammer_almeta_t) + 1023) / 1024,
234                 (bl->bl_rootblks * sizeof(hammer_almeta_t))
235         );
236         kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
237 #endif
238         hammer_alst_radix_init(meta, bl->bl_radix, bl->bl_skip, blocks);
239
240         *metap = meta;
241         return(bl);
242 }
243
244 void
245 hammer_alist_destroy(hammer_alist_t bl, struct malloc_type *mtype)
246 {
247         kfree(bl, mtype);
248 }
249
250 #endif
251
252 /*
253  * hammer_alist_alloc()
254  *
255  *      Reserve space in the block bitmap.  Return the base of a contiguous
256  *      region or HAMMER_ALIST_BLOCK_NONE if space could not be allocated.
257  */
258
259 int32_t 
260 hammer_alist_alloc(hammer_alist_t bl, hammer_almeta_t *meta, int32_t count)
261 {
262         int32_t blk = HAMMER_ALIST_BLOCK_NONE;
263
264         KKASSERT((count | (count - 1)) == (count << 1) - 1);
265
266         if (bl && count < bl->bl_radix) {
267                 if (bl->bl_radix == HAMMER_ALIST_BMAP_RADIX) {
268                         blk = hammer_alst_leaf_alloc_fwd(meta, 0, count);
269                 } else {
270                         blk = hammer_alst_meta_alloc_fwd(
271                                     meta, 0, count, bl->bl_radix, bl->bl_skip);
272                 }
273                 if (blk != HAMMER_ALIST_BLOCK_NONE)
274                         bl->bl_free -= count;
275         }
276         return(blk);
277 }
278
279 int32_t 
280 hammer_alist_alloc_rev(hammer_alist_t bl, hammer_almeta_t *meta, int32_t count)
281 {
282         int32_t blk = HAMMER_ALIST_BLOCK_NONE;
283
284         KKASSERT((count | (count - 1)) == (count << 1) - 1);
285
286         if (bl && count < bl->bl_radix) {
287                 if (bl->bl_radix == HAMMER_ALIST_BMAP_RADIX) {
288                         blk = hammer_alst_leaf_alloc_rev(meta, 0, count);
289                 } else {
290                         blk = hammer_alst_meta_alloc_rev(
291                                     meta, 0, count, bl->bl_radix, bl->bl_skip);
292                 }
293                 if (blk != HAMMER_ALIST_BLOCK_NONE)
294                         bl->bl_free -= count;
295         }
296         return(blk);
297 }
298
299 #if 0
300
301 /*
302  * hammer_alist_alloc_from()
303  *
304  *      An extended version of hammer_alist_alloc() which locates free space
305  *      starting at the specified block either forwards or backwards.
306  *      HAMMER_ALIST_BLOCK_NONE is returned if space could not be allocated.
307  *
308  *      Note: when allocating from a particular point forwards space is never
309  *      allocated behind that start point, and similarly when going backwards.
310  */
311 int32_t 
312 hammer_alist_alloc_from(hammer_alist_t bl, hammer_almeta_t *meta,
313                         int32_t count, int32_t start, int flags)
314
315 {
316 }
317
318 #endif
319
320 /*
321  * alist_free()
322  *
323  *      Free up space in the block bitmap.  Return the base of a contiguous
324  *      region.  Panic if an inconsistancy is found.
325  *
326  *      Unlike allocations, there are no alignment requirements for blkno or
327  *      count when freeing blocks.
328  */
329
330 void 
331 hammer_alist_free(hammer_alist_t bl, hammer_almeta_t *meta,
332                   int32_t blkno, int32_t count)
333 {
334         if (bl) {
335                 KKASSERT(blkno + count <= bl->bl_blocks);
336                 if (bl->bl_radix == HAMMER_ALIST_BMAP_RADIX)
337                         hammer_alst_leaf_free(meta, blkno, count);
338                 else
339                         hammer_alst_meta_free(meta, blkno, count,
340                                               bl->bl_radix, bl->bl_skip, 0);
341                 bl->bl_free += count;
342         }
343 }
344
345 #ifdef ALIST_DEBUG
346
347 /*
348  * alist_print()    - dump radix tree
349  */
350
351 void
352 hammer_alist_print(hammer_alist_t bl, hammer_almeta_t *meta)
353 {
354         kprintf("ALIST {\n");
355         hammer_alst_radix_print(meta, 0, bl->bl_radix, bl->bl_skip, 4);
356         kprintf("}\n");
357 }
358
359 #endif
360
361 /************************************************************************
362  *                        ALLOCATION SUPPORT FUNCTIONS                  *
363  ************************************************************************
364  *
365  *      These support functions do all the actual work.  They may seem 
366  *      rather longish, but that's because I've commented them up.  The
367  *      actual code is straight forward.
368  *
369  */
370
371 /*
372  * hammer_alist_leaf_alloc_fwd()
373  *
374  *      Allocate at a leaf in the radix tree (a bitmap).
375  *
376  *      This is the core of the allocator and is optimized for the 1 block
377  *      and the HAMMER_ALIST_BMAP_RADIX block allocation cases.  Other cases
378  *      are somewhat slower.  The 1 block allocation case is log2 and extremely
379  *      quick.
380  */
381
382 static int32_t
383 hammer_alst_leaf_alloc_fwd(hammer_almeta_t *scan, int32_t blk, int count)
384 {
385         u_int32_t orig = scan->bm_bitmap;
386
387         /*
388          * Optimize bitmap all-allocated case.  Also, count = 1
389          * case assumes at least 1 bit is free in the bitmap, so
390          * we have to take care of this case here.
391          */
392         if (orig == 0) {
393                 scan->bm_bighint = 0;
394                 return(HAMMER_ALIST_BLOCK_NONE);
395         }
396
397         /*
398          * Optimized code to allocate one bit out of the bitmap
399          */
400         if (count == 1) {
401                 u_int32_t mask;
402                 int j = HAMMER_ALIST_BMAP_RADIX/2;
403                 int r = 0;
404
405                 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX/2);
406
407                 while (j) {
408                         if ((orig & mask) == 0) {
409                             r += j;
410                             orig >>= j;
411                         }
412                         j >>= 1;
413                         mask >>= j;
414                 }
415                 scan->bm_bitmap &= ~(1 << r);
416                 return(blk + r);
417         }
418
419         /*
420          * non-optimized code to allocate N bits out of the bitmap.
421          * The more bits, the faster the code runs.  It will run
422          * the slowest allocating 2 bits, but since there aren't any
423          * memory ops in the core loop (or shouldn't be, anyway),
424          * you probably won't notice the difference.
425          *
426          * Similar to the blist case, the alist code also requires
427          * allocations to be power-of-2 sized and aligned to the
428          * size of the allocation, which simplifies the algorithm.
429          */
430         {
431                 int j;
432                 int n = HAMMER_ALIST_BMAP_RADIX - count;
433                 u_int32_t mask;
434
435                 mask = (u_int32_t)-1 >> n;
436
437                 for (j = 0; j <= n; j += count) {
438                         if ((orig & mask) == mask) {
439                                 scan->bm_bitmap &= ~mask;
440                                 return(blk + j);
441                         }
442                         mask = mask << count;
443                 }
444         }
445
446         /*
447          * We couldn't allocate count in this subtree, update bighint.
448          */
449         scan->bm_bighint = count - 1;
450         return(HAMMER_ALIST_BLOCK_NONE);
451 }
452
453 /*
454  * This version allocates blocks in the reverse direction.
455  */
456 static int32_t
457 hammer_alst_leaf_alloc_rev(hammer_almeta_t *scan, int32_t blk, int count)
458 {
459         u_int32_t orig = scan->bm_bitmap;
460
461         /*
462          * Optimize bitmap all-allocated case.  Also, count = 1
463          * case assumes at least 1 bit is free in the bitmap, so
464          * we have to take care of this case here.
465          */
466         if (orig == 0) {
467                 scan->bm_bighint = 0;
468                 return(HAMMER_ALIST_BLOCK_NONE);
469         }
470
471         /*
472          * Optimized code to allocate one bit out of the bitmap
473          */
474         if (count == 1) {
475                 u_int32_t mask;
476                 int j = HAMMER_ALIST_BMAP_RADIX/2;
477                 int r = HAMMER_ALIST_BMAP_RADIX - 1;
478
479                 mask = ~((u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX/2));
480
481                 while (j) {
482                         if ((orig & mask) == 0) {
483                             r -= j;
484                             orig <<= j;
485                         }
486                         j >>= 1;
487                         mask <<= j;
488                 }
489                 scan->bm_bitmap &= ~(1 << r);
490                 return(blk + r);
491         }
492
493         /*
494          * non-optimized code to allocate N bits out of the bitmap.
495          * The more bits, the faster the code runs.  It will run
496          * the slowest allocating 2 bits, but since there aren't any
497          * memory ops in the core loop (or shouldn't be, anyway),
498          * you probably won't notice the difference.
499          *
500          * Similar to the blist case, the alist code also requires
501          * allocations to be power-of-2 sized and aligned to the
502          * size of the allocation, which simplifies the algorithm.
503          *
504          * initial mask if count == 2:  1100....0000
505          */
506         {
507                 int j;
508                 int n = HAMMER_ALIST_BMAP_RADIX - count;
509                 u_int32_t mask;
510
511                 mask = ((u_int32_t)-1 >> n) << n;
512
513                 for (j = n; j >= 0; j -= count) {
514                         if ((orig & mask) == mask) {
515                                 scan->bm_bitmap &= ~mask;
516                                 return(blk + j);
517                         }
518                         mask = mask >> count;
519                 }
520         }
521
522         /*
523          * We couldn't allocate count in this subtree, update bighint.
524          */
525         scan->bm_bighint = count - 1;
526         return(HAMMER_ALIST_BLOCK_NONE);
527 }
528
529 /*
530  * hammer_alist_meta_alloc_fwd()
531  *
532  *      Allocate at a meta in the radix tree.
533  *
534  *      Attempt to allocate at a meta node.  If we can't, we update
535  *      bighint and return a failure.  Updating bighint optimize future
536  *      calls that hit this node.  We have to check for our collapse cases
537  *      and we have a few optimizations strewn in as well.
538  */
539 static int32_t
540 hammer_alst_meta_alloc_fwd(hammer_almeta_t *scan, int32_t blk, int32_t count,
541                            int32_t radix, int skip
542 ) {
543         int i;
544         u_int32_t mask;
545         u_int32_t pmask;
546         int next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
547
548         /*
549          * ALL-ALLOCATED special case
550          */
551         if (scan->bm_bitmap == 0)  {
552                 scan->bm_bighint = 0;
553                 return(HAMMER_ALIST_BLOCK_NONE);
554         }
555
556         radix /= HAMMER_ALIST_META_RADIX;
557
558         /*
559          * Radix now represents each bitmap entry for this meta node.  If
560          * the number of blocks being allocated can be fully represented,
561          * we allocate directly out of this meta node.
562          *
563          * Meta node bitmaps use 2 bits per block.
564          *
565          *      00      ALL-ALLOCATED
566          *      01      PARTIALLY-FREE/PARTIALLY-ALLOCATED
567          *      10      (RESERVED)
568          *      11      ALL-FREE
569          */
570         if (count >= radix) {
571                 int n = count / radix * 2;      /* number of bits */
572                 int j;
573
574                 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - n);
575                 for (j = 0; j < HAMMER_ALIST_META_RADIX; j += n / 2) {
576                         if ((scan->bm_bitmap & mask) == mask) {
577                                 scan->bm_bitmap &= ~mask;
578                                 return(blk + j * radix);
579                         }
580                         mask <<= n;
581                 }
582                 if (scan->bm_bighint >= count)
583                         scan->bm_bighint = count >> 1;
584                 return(HAMMER_ALIST_BLOCK_NONE);
585         }
586
587         /*
588          * If not we have to recurse.
589          */
590         mask = 0x00000003;
591         pmask = 0x00000001;
592         for (i = 1; i <= skip; i += next_skip) {
593                 if (scan[i].bm_bighint == (int32_t)-1) {
594                         /* 
595                          * Terminator
596                          */
597                         break;
598                 }
599                 if ((scan->bm_bitmap & mask) == mask) {
600                         scan[i].bm_bitmap = (u_int32_t)-1;
601                         scan[i].bm_bighint = radix;
602                 }
603
604                 if (count <= scan[i].bm_bighint) {
605                         /*
606                          * count fits in object
607                          */
608                         int32_t r;
609                         if (next_skip == 1) {
610                                 r = hammer_alst_leaf_alloc_fwd(
611                                         &scan[i], blk, count);
612                         } else {
613                                 r = hammer_alst_meta_alloc_fwd(
614                                         &scan[i], blk, count,
615                                         radix, next_skip - 1);
616                         }
617                         if (r != HAMMER_ALIST_BLOCK_NONE) {
618                                 if (scan[i].bm_bitmap == 0) {
619                                         scan->bm_bitmap &= ~mask;
620                                 } else {
621                                         scan->bm_bitmap &= ~mask;
622                                         scan->bm_bitmap |= pmask;
623                                 }
624                                 return(r);
625                         }
626                 } else if (count > radix) {
627                         /*
628                          * count does not fit in object even if it were
629                          * completely free.
630                          */
631                         break;
632                 }
633                 blk += radix;
634                 mask <<= 2;
635                 pmask <<= 2;
636         }
637
638         /*
639          * We couldn't allocate count in this subtree, update bighint.
640          */
641         if (scan->bm_bighint >= count)
642                 scan->bm_bighint = count >> 1;
643         return(HAMMER_ALIST_BLOCK_NONE);
644 }
645
646 /*
647  * This version allocates blocks in the reverse direction.
648  */
649 static int32_t
650 hammer_alst_meta_alloc_rev(hammer_almeta_t *scan, int32_t blk, int32_t count,
651                            int32_t radix, int skip
652 ) {
653         int i;
654         int j;
655         u_int32_t mask;
656         u_int32_t pmask;
657         int next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
658
659         /*
660          * ALL-ALLOCATED special case
661          */
662         if (scan->bm_bitmap == 0)  {
663                 scan->bm_bighint = 0;
664                 return(HAMMER_ALIST_BLOCK_NONE);
665         }
666
667         radix /= HAMMER_ALIST_META_RADIX;
668
669         /*
670          * Radix now represents each bitmap entry for this meta node.  If
671          * the number of blocks being allocated can be fully represented,
672          * we allocate directly out of this meta node.
673          *
674          * Meta node bitmaps use 2 bits per block.
675          *
676          *      00      ALL-ALLOCATED
677          *      01      PARTIALLY-FREE/PARTIALLY-ALLOCATED
678          *      10      (RESERVED)
679          *      11      ALL-FREE
680          */
681         if (count >= radix) {
682                 int n = count / radix * 2;      /* number of bits */
683                 int j;
684
685                 /*
686                  * Initial mask if e.g. n == 2:  1100....0000
687                  */
688                 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - n) <<
689                         (HAMMER_ALIST_BMAP_RADIX - n);
690                 for (j = HAMMER_ALIST_META_RADIX - n / 2; j >= 0; j -= n / 2) {
691                         if ((scan->bm_bitmap & mask) == mask) {
692                                 scan->bm_bitmap &= ~mask;
693                                 return(blk + j * radix);
694                         }
695                         mask >>= n;
696                 }
697                 if (scan->bm_bighint >= count)
698                         scan->bm_bighint = count >> 1;
699                 return(HAMMER_ALIST_BLOCK_NONE);
700         }
701
702         /*
703          * If not we have to recurse.  Since we are going in the reverse
704          * direction we need an extra loop to determine if there is a
705          * terminator, then run backwards.
706          *
707          * This is a little weird but we do not want to overflow the
708          * mask/pmask in the loop.
709          */
710         j = 0;
711         for (i = 1; i <= skip; i += next_skip) {
712                 if (scan[i].bm_bighint == (int32_t)-1)
713                         break;
714                 blk += radix;
715                 j += 2;
716         }
717         blk -= radix;
718         j -= 2;
719         mask = 0x00000003 << j;
720         pmask = 0x00000001 << j;
721         i -= next_skip;
722
723         while (i >= 1) {
724                 /*
725                  * Initialize the bitmap in the child if allocating from
726                  * the all-free case.
727                  */
728                 if ((scan->bm_bitmap & mask) == mask) {
729                         scan[i].bm_bitmap = (u_int32_t)-1;
730                         scan[i].bm_bighint = radix;
731                 }
732
733                 /*
734                  * Handle various count cases.  Bighint may be too large but
735                  * is never too small.
736                  */
737                 if (count <= scan[i].bm_bighint) {
738                         /*
739                          * count fits in object
740                          */
741                         int32_t r;
742                         if (next_skip == 1) {
743                                 r = hammer_alst_leaf_alloc_rev(
744                                         &scan[i], blk, count);
745                         } else {
746                                 r = hammer_alst_meta_alloc_rev(
747                                         &scan[i], blk, count,
748                                         radix, next_skip - 1);
749                         }
750                         if (r != HAMMER_ALIST_BLOCK_NONE) {
751                                 if (scan[i].bm_bitmap == 0) {
752                                         scan->bm_bitmap &= ~mask;
753                                 } else {
754                                         scan->bm_bitmap &= ~mask;
755                                         scan->bm_bitmap |= pmask;
756                                 }
757                                 return(r);
758                         }
759                 } else if (count > radix) {
760                         /*
761                          * count does not fit in object even if it were
762                          * completely free.
763                          */
764                         break;
765                 }
766                 blk -= radix;
767                 mask >>= 2;
768                 pmask >>= 2;
769                 i -= next_skip;
770         }
771
772         /*
773          * We couldn't allocate count in this subtree, update bighint.
774          */
775         if (scan->bm_bighint >= count)
776                 scan->bm_bighint = count >> 1;
777         return(HAMMER_ALIST_BLOCK_NONE);
778 }
779
780 /*
781  * BLST_LEAF_FREE()
782  *
783  *      Free allocated blocks from leaf bitmap.  The allocation code is
784  *      restricted to powers of 2, the freeing code is not.
785  */
786 static void
787 hammer_alst_leaf_free(
788         hammer_almeta_t *scan,
789         int32_t blk,
790         int count
791 ) {
792         /*
793          * free some data in this bitmap
794          *
795          * e.g.
796          *      0000111111111110000
797          *          \_________/\__/
798          *              v        n
799          */
800         int n = blk & (HAMMER_ALIST_BMAP_RADIX - 1);
801         u_int32_t mask;
802
803         mask = ((u_int32_t)-1 << n) &
804             ((u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - count - n));
805
806         if (scan->bm_bitmap & mask)
807                 panic("hammer_alst_radix_free: freeing free block");
808         scan->bm_bitmap |= mask;
809
810         /*
811          * We could probably do a better job here.  We are required to make
812          * bighint at least as large as the biggest contiguous block of 
813          * data.  If we just shoehorn it, a little extra overhead will
814          * be incured on the next allocation (but only that one typically).
815          */
816         scan->bm_bighint = HAMMER_ALIST_BMAP_RADIX;
817 }
818
819 /*
820  * BLST_META_FREE()
821  *
822  *      Free allocated blocks from radix tree meta info.
823  *
824  *      This support routine frees a range of blocks from the bitmap.
825  *      The range must be entirely enclosed by this radix node.  If a
826  *      meta node, we break the range down recursively to free blocks
827  *      in subnodes (which means that this code can free an arbitrary
828  *      range whereas the allocation code cannot allocate an arbitrary
829  *      range).
830  */
831
832 static void 
833 hammer_alst_meta_free(
834         hammer_almeta_t *scan, 
835         int32_t freeBlk,
836         int32_t count,
837         int32_t radix, 
838         int skip,
839         int32_t blk
840 ) {
841         int next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
842         u_int32_t mask;
843         u_int32_t pmask;
844         int i;
845
846         /*
847          * Break the free down into its components.  Because it is so easy
848          * to implement, frees are not limited to power-of-2 sizes.
849          *
850          * Each block in a meta-node bitmap takes two bits.
851          */
852         radix /= HAMMER_ALIST_META_RADIX;
853
854         i = (freeBlk - blk) / radix;
855         blk += i * radix;
856         mask = 0x00000003 << (i * 2);
857         pmask = 0x00000001 << (i * 2);
858
859         i = i * next_skip + 1;
860
861         while (i <= skip && blk < freeBlk + count) {
862                 int32_t v;
863
864                 v = blk + radix - freeBlk;
865                 if (v > count)
866                         v = count;
867
868                 if (scan->bm_bighint == (int32_t)-1)
869                         panic("hammer_alst_meta_free: freeing unexpected range");
870
871                 if (freeBlk == blk && count >= radix) {
872                         /*
873                          * All-free case, no need to update sub-tree
874                          */
875                         scan->bm_bitmap |= mask;
876                         scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
877                         /*XXX*/
878                 } else {
879                         /*
880                          * Recursion case
881                          */
882                         if (next_skip == 1)
883                                 hammer_alst_leaf_free(&scan[i], freeBlk, v);
884                         else
885                                 hammer_alst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk);
886                         if (scan[i].bm_bitmap == (u_int32_t)-1)
887                                 scan->bm_bitmap |= mask;
888                         else
889                                 scan->bm_bitmap |= pmask;
890                         if (scan->bm_bighint < scan[i].bm_bighint)
891                             scan->bm_bighint = scan[i].bm_bighint;
892                 }
893                 mask <<= 2;
894                 pmask <<= 2;
895                 count -= v;
896                 freeBlk += v;
897                 blk += radix;
898                 i += next_skip;
899         }
900 }
901
902 /*
903  * BLST_RADIX_INIT()
904  *
905  *      Initialize our meta structures and bitmaps and calculate the exact
906  *      amount of space required to manage 'count' blocks - this space may
907  *      be considerably less then the calculated radix due to the large
908  *      RADIX values we use.
909  */
910
911 static int32_t  
912 hammer_alst_radix_init(hammer_almeta_t *scan, int32_t radix,
913                        int skip, int32_t count)
914 {
915         int i;
916         int next_skip;
917         int32_t memindex = 0;
918         u_int32_t mask;
919         u_int32_t pmask;
920
921         /*
922          * Leaf node
923          */
924         if (radix == HAMMER_ALIST_BMAP_RADIX) {
925                 if (scan) {
926                         scan->bm_bighint = 0;
927                         scan->bm_bitmap = 0;
928                 }
929                 return(memindex);
930         }
931
932         /*
933          * Meta node.  If allocating the entire object we can special
934          * case it.  However, we need to figure out how much memory
935          * is required to manage 'count' blocks, so we continue on anyway.
936          */
937
938         if (scan) {
939                 scan->bm_bighint = 0;
940                 scan->bm_bitmap = 0;
941         }
942
943         radix /= HAMMER_ALIST_META_RADIX;
944         next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
945         mask = 0x00000003;
946         pmask = 0x00000001;
947
948         for (i = 1; i <= skip; i += next_skip) {
949                 if (count >= radix) {
950                         /*
951                          * Allocate the entire object
952                          */
953                         memindex = i + hammer_alst_radix_init(
954                             ((scan) ? &scan[i] : NULL),
955                             radix,
956                             next_skip - 1,
957                             radix
958                         );
959                         count -= radix;
960                         /* already marked as wholely allocated */
961                 } else if (count > 0) {
962                         /*
963                          * Allocate a partial object
964                          */
965                         memindex = i + hammer_alst_radix_init(
966                             ((scan) ? &scan[i] : NULL),
967                             radix,
968                             next_skip - 1,
969                             count
970                         );
971                         count = 0;
972
973                         /*
974                          * Mark as partially allocated
975                          */
976                         if (scan)
977                                 scan->bm_bitmap |= pmask;
978                 } else {
979                         /*
980                          * Add terminator and break out
981                          */
982                         if (scan)
983                                 scan[i].bm_bighint = (int32_t)-1;
984                         /* already marked as wholely allocated */
985                         break;
986                 }
987                 mask <<= 2;
988                 pmask <<= 2;
989         }
990         if (memindex < i)
991                 memindex = i;
992         return(memindex);
993 }
994
995 #ifdef ALIST_DEBUG
996
997 static void     
998 hammer_alst_radix_print(hammer_almeta_t *scan, int32_t blk,
999                         int32_t radix, int skip, int tab)
1000 {
1001         int i;
1002         int next_skip;
1003         int lastState = 0;
1004         u_int32_t mask;
1005
1006         if (radix == HAMMER_ALIST_BMAP_RADIX) {
1007                 kprintf(
1008                     "%*.*s(%04x,%d): bitmap %08x big=%d\n", 
1009                     tab, tab, "",
1010                     blk, radix,
1011                     scan->bm_bitmap,
1012                     scan->bm_bighint
1013                 );
1014                 return;
1015         }
1016
1017         if (scan->bm_bitmap == 0) {
1018                 kprintf(
1019                     "%*.*s(%04x,%d) ALL ALLOCATED\n",
1020                     tab, tab, "",
1021                     blk,
1022                     radix
1023                 );
1024                 return;
1025         }
1026         if (scan->bm_bitmap == (u_int32_t)-1) {
1027                 kprintf(
1028                     "%*.*s(%04x,%d) ALL FREE\n",
1029                     tab, tab, "",
1030                     blk,
1031                     radix
1032                 );
1033                 return;
1034         }
1035
1036         kprintf(
1037             "%*.*s(%04x,%d): subtree (%d) bitmap=%08x big=%d {\n",
1038             tab, tab, "",
1039             blk, radix,
1040             radix,
1041             scan->bm_bitmap,
1042             scan->bm_bighint
1043         );
1044
1045         radix /= HAMMER_ALIST_META_RADIX;
1046         next_skip = ((u_int)skip / HAMMER_ALIST_META_RADIX);
1047         tab += 4;
1048         mask = 0x00000003;
1049
1050         for (i = 1; i <= skip; i += next_skip) {
1051                 if (scan[i].bm_bighint == (int32_t)-1) {
1052                         kprintf(
1053                             "%*.*s(%04x,%d): Terminator\n",
1054                             tab, tab, "",
1055                             blk, radix
1056                         );
1057                         lastState = 0;
1058                         break;
1059                 }
1060                 if ((scan->bm_bitmap & mask) == mask) {
1061                         kprintf(
1062                             "%*.*s(%04x,%d): ALL FREE\n",
1063                             tab, tab, "",
1064                             blk, radix
1065                         );
1066                 } else if ((scan->bm_bitmap & mask) == 0) {
1067                         kprintf(
1068                             "%*.*s(%04x,%d): ALL ALLOCATED\n",
1069                             tab, tab, "",
1070                             blk, radix
1071                         );
1072                 } else {
1073                         hammer_alst_radix_print(
1074                             &scan[i],
1075                             blk,
1076                             radix,
1077                             next_skip - 1,
1078                             tab
1079                         );
1080                 }
1081                 blk += radix;
1082                 mask <<= 2;
1083         }
1084         tab -= 4;
1085
1086         kprintf(
1087             "%*.*s}\n",
1088             tab, tab, ""
1089         );
1090 }
1091
1092 #endif
1093
1094 #ifdef ALIST_DEBUG
1095
1096 int
1097 main(int ac, char **av)
1098 {
1099         int size = 1024;
1100         int i;
1101         hammer_alist_t bl;
1102         hammer_almeta_t *meta = NULL;
1103
1104         for (i = 1; i < ac; ++i) {
1105                 const char *ptr = av[i];
1106                 if (*ptr != '-') {
1107                         size = strtol(ptr, NULL, 0);
1108                         continue;
1109                 }
1110                 ptr += 2;
1111                 fprintf(stderr, "Bad option: %s\n", ptr - 2);
1112                 exit(1);
1113         }
1114         bl = hammer_alist_create(size, NULL, &meta);
1115         hammer_alist_free(bl, meta, 0, size);
1116
1117         for (;;) {
1118                 char buf[1024];
1119                 int32_t da = 0;
1120                 int32_t count = 0;
1121                 int32_t blk;
1122
1123                 kprintf("%d/%d/%d> ", bl->bl_free, size, bl->bl_radix);
1124                 fflush(stdout);
1125                 if (fgets(buf, sizeof(buf), stdin) == NULL)
1126                         break;
1127                 switch(buf[0]) {
1128                 case 'p':
1129                         hammer_alist_print(bl, meta);
1130                         break;
1131                 case 'a':
1132                         if (sscanf(buf + 1, "%d", &count) == 1) {
1133                                 blk = hammer_alist_alloc(bl, meta, count);
1134                                 kprintf("    R=%04x\n", blk);
1135                         } else {
1136                                 kprintf("?\n");
1137                         }
1138                         break;
1139                 case 'r':
1140                         if (sscanf(buf + 1, "%d", &count) == 1) {
1141                                 blk = hammer_alist_alloc_rev(bl, meta, count);
1142                                 kprintf("    R=%04x\n", blk);
1143                         } else {
1144                                 kprintf("?\n");
1145                         }
1146                         break;
1147                 case 'f':
1148                         if (sscanf(buf + 1, "%x %d", &da, &count) == 2) {
1149                                 hammer_alist_free(bl, meta, da, count);
1150                         } else {
1151                                 kprintf("?\n");
1152                         }
1153                         break;
1154                 case '?':
1155                 case 'h':
1156                         puts(
1157                             "p          -print\n"
1158                             "a %d       -allocate\n"
1159                             "r %d       -allocate reverse\n"
1160                             "f %x %d    -free\n"
1161                             "h/?        -help"
1162                         );
1163                         break;
1164                 default:
1165                         kprintf("?\n");
1166                         break;
1167                 }
1168         }
1169         return(0);
1170 }
1171
1172 void
1173 panic(const char *ctl, ...)
1174 {
1175         __va_list va;
1176
1177         __va_start(va, ctl);
1178         vfprintf(stderr, ctl, va);
1179         fprintf(stderr, "\n");
1180         __va_end(va);
1181         exit(1);
1182 }
1183
1184 #endif
1185