1/* $NetBSD: subr_blist.c,v 1.12 2013/12/09 09:35:17 wiz Exp $ */
2
3/*-
4 * Copyright (c) 1998 Matthew Dillon. All Rights Reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 4. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS
18 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
21 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE
23 * GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
24 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
25 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
26 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
27 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29/*
30 * BLIST.C - Bitmap allocator/deallocator, using a radix tree with hinting
31 *
32 * This module implements a general bitmap allocator/deallocator. The
33 * allocator eats around 2 bits per 'block'. The module does not
34 * try to interpret the meaning of a 'block' other than to return
35 * BLIST_NONE on an allocation failure.
36 *
37 * A radix tree is used to maintain the bitmap. Two radix constants are
38 * involved: One for the bitmaps contained in the leaf nodes (typically
39 * 32), and one for the meta nodes (typically 16). Both meta and leaf
40 * nodes have a hint field. This field gives us a hint as to the largest
41 * free contiguous range of blocks under the node. It may contain a
42 * value that is too high, but will never contain a value that is too
43 * low. When the radix tree is searched, allocation failures in subtrees
44 * update the hint.
45 *
46 * The radix tree also implements two collapsed states for meta nodes:
47 * the ALL-ALLOCATED state and the ALL-FREE state. If a meta node is
48 * in either of these two states, all information contained underneath
49 * the node is considered stale. These states are used to optimize
50 * allocation and freeing operations.
51 *
52 * The hinting greatly increases code efficiency for allocations while
53 * the general radix structure optimizes both allocations and frees. The
54 * radix tree should be able to operate well no matter how much
55 * fragmentation there is and no matter how large a bitmap is used.
56 *
57 * Unlike the rlist code, the blist code wires all necessary memory at
58 * creation time. Neither allocations nor frees require interaction with
59 * the memory subsystem. In contrast, the rlist code may allocate memory
60 * on an rlist_free() call. The non-blocking features of the blist code
61 * are used to great advantage in the swap code (vm/nswap_pager.c). The
62 * rlist code uses a little less overall memory than the blist code (but
63 * due to swap interleaving not all that much less), but the blist code
64 * scales much, much better.
65 *
66 * LAYOUT: The radix tree is layed out recursively using a
67 * linear array. Each meta node is immediately followed (layed out
68 * sequentially in memory) by BLIST_META_RADIX lower level nodes. This
69 * is a recursive structure but one that can be easily scanned through
70 * a very simple 'skip' calculation. In order to support large radixes,
71 * portions of the tree may reside outside our memory allocation. We
72 * handle this with an early-termination optimization (when bighint is
73 * set to -1) on the scan. The memory allocation is only large enough
74 * to cover the number of blocks requested at creation time even if it
75 * must be encompassed in larger root-node radix.
76 *
77 * NOTE: the allocator cannot currently allocate more than
78 * BLIST_BMAP_RADIX blocks per call. It will panic with 'allocation too
79 * large' if you try. This is an area that could use improvement. The
80 * radix is large enough that this restriction does not effect the swap
81 * system, though. Currently only the allocation code is effected by
82 * this algorithmic unfeature. The freeing code can handle arbitrary
83 * ranges.
84 *
85 * This code can be compiled stand-alone for debugging.
86 */
87
88#include <sys/cdefs.h>
89__KERNEL_RCSID(0, "$NetBSD: subr_blist.c,v 1.12 2013/12/09 09:35:17 wiz Exp $");
90#if 0
91__FBSDID("$FreeBSD: src/sys/kern/subr_blist.c,v 1.17 2004/06/04 04:03:25 alc Exp $");
92#endif
93
94#ifdef _KERNEL
95
96#include <sys/param.h>
97#include <sys/systm.h>
98#include <sys/blist.h>
99#include <sys/kmem.h>
100
101#else
102
103#ifndef BLIST_NO_DEBUG
104#define BLIST_DEBUG
105#endif
106
107#include <sys/types.h>
108#include <stdio.h>
109#include <string.h>
110#include <stdlib.h>
111#include <stdarg.h>
112#include <inttypes.h>
113
114#define KM_SLEEP 1
115#define kmem_zalloc(a,b,c) calloc(1, (a))
116#define kmem_alloc(a,b,c) malloc(a)
117#define kmem_free(a,b) free(a)
118
119#include "../sys/blist.h"
120
121void panic(const char *ctl, ...) __printflike(1, 2);
122
123#endif
124
125/*
126 * blmeta and bl_bitmap_t MUST be a power of 2 in size.
127 */
128
129typedef struct blmeta {
130 union {
131 blist_blkno_t bmu_avail; /* space available under us */
132 blist_bitmap_t bmu_bitmap; /* bitmap if we are a leaf */
133 } u;
134 blist_blkno_t bm_bighint; /* biggest contiguous block hint*/
135} blmeta_t;
136
137struct blist {
138 blist_blkno_t bl_blocks; /* area of coverage */
139 blist_blkno_t bl_radix; /* coverage radix */
140 blist_blkno_t bl_skip; /* starting skip */
141 blist_blkno_t bl_free; /* number of free blocks */
142 blmeta_t *bl_root; /* root of radix tree */
143 blist_blkno_t bl_rootblks; /* blks allocated for tree */
144};
145
146#define BLIST_META_RADIX 16
147
148/*
149 * static support functions
150 */
151
152static blist_blkno_t blst_leaf_alloc(blmeta_t *scan, blist_blkno_t blk,
153 int count);
154static blist_blkno_t blst_meta_alloc(blmeta_t *scan, blist_blkno_t blk,
155 blist_blkno_t count, blist_blkno_t radix, blist_blkno_t skip);
156static void blst_leaf_free(blmeta_t *scan, blist_blkno_t relblk, int count);
157static void blst_meta_free(blmeta_t *scan, blist_blkno_t freeBlk,
158 blist_blkno_t count, blist_blkno_t radix, blist_blkno_t skip,
159 blist_blkno_t blk);
160static void blst_copy(blmeta_t *scan, blist_blkno_t blk, blist_blkno_t radix,
161 blist_blkno_t skip, blist_t dest, blist_blkno_t count);
162static int blst_leaf_fill(blmeta_t *scan, blist_blkno_t blk, int count);
163static blist_blkno_t blst_meta_fill(blmeta_t *scan, blist_blkno_t allocBlk,
164 blist_blkno_t count, blist_blkno_t radix, blist_blkno_t skip,
165 blist_blkno_t blk);
166static blist_blkno_t blst_radix_init(blmeta_t *scan, blist_blkno_t radix,
167 blist_blkno_t skip, blist_blkno_t count);
168#ifndef _KERNEL
169static void blst_radix_print(blmeta_t *scan, blist_blkno_t blk,
170 blist_blkno_t radix, blist_blkno_t skip, int tab);
171#endif
172
173/*
174 * blist_create() - create a blist capable of handling up to the specified
175 * number of blocks
176 *
177 * blocks must be greater than 0
178 *
179 * The smallest blist consists of a single leaf node capable of
180 * managing BLIST_BMAP_RADIX blocks.
181 */
182
183blist_t
184blist_create(blist_blkno_t blocks)
185{
186 blist_t bl;
187 blist_blkno_t radix;
188 blist_blkno_t skip = 0;
189
190 /*
191 * Calculate radix and skip field used for scanning.
192 *
193 * XXX check overflow
194 */
195 radix = BLIST_BMAP_RADIX;
196
197 while (radix < blocks) {
198 radix *= BLIST_META_RADIX;
199 skip = (skip + 1) * BLIST_META_RADIX;
200 }
201
202 bl = kmem_zalloc(sizeof(struct blist), KM_SLEEP);
203
204 bl->bl_blocks = blocks;
205 bl->bl_radix = radix;
206 bl->bl_skip = skip;
207 bl->bl_rootblks = 1 +
208 blst_radix_init(NULL, bl->bl_radix, bl->bl_skip, blocks);
209 bl->bl_root = kmem_alloc(sizeof(blmeta_t) * bl->bl_rootblks, KM_SLEEP);
210
211#if defined(BLIST_DEBUG)
212 printf(
213 "BLIST representing %" PRIu64 " blocks (%" PRIu64 " MB of swap)"
214 ", requiring %" PRIu64 "K of ram\n",
215 (uint64_t)bl->bl_blocks,
216 (uint64_t)bl->bl_blocks * 4 / 1024,
217 ((uint64_t)bl->bl_rootblks * sizeof(blmeta_t) + 1023) / 1024
218 );
219 printf("BLIST raw radix tree contains %" PRIu64 " records\n",
220 (uint64_t)bl->bl_rootblks);
221#endif
222 blst_radix_init(bl->bl_root, bl->bl_radix, bl->bl_skip, blocks);
223
224 return(bl);
225}
226
227void
228blist_destroy(blist_t bl)
229{
230
231 kmem_free(bl->bl_root, sizeof(blmeta_t) * bl->bl_rootblks);
232 kmem_free(bl, sizeof(struct blist));
233}
234
235/*
236 * blist_alloc() - reserve space in the block bitmap. Return the base
237 * of a contiguous region or BLIST_NONE if space could
238 * not be allocated.
239 */
240
241blist_blkno_t
242blist_alloc(blist_t bl, blist_blkno_t count)
243{
244 blist_blkno_t blk = BLIST_NONE;
245
246 if (bl) {
247 if (bl->bl_radix == BLIST_BMAP_RADIX)
248 blk = blst_leaf_alloc(bl->bl_root, 0, count);
249 else
250 blk = blst_meta_alloc(bl->bl_root, 0, count, bl->bl_radix, bl->bl_skip);
251 if (blk != BLIST_NONE)
252 bl->bl_free -= count;
253 }
254 return(blk);
255}
256
257/*
258 * blist_free() - free up space in the block bitmap. Return the base
259 * of a contiguous region. Panic if an inconsistancy is
260 * found.
261 */
262
263void
264blist_free(blist_t bl, blist_blkno_t blkno, blist_blkno_t count)
265{
266 if (bl) {
267 if (bl->bl_radix == BLIST_BMAP_RADIX)
268 blst_leaf_free(bl->bl_root, blkno, count);
269 else
270 blst_meta_free(bl->bl_root, blkno, count, bl->bl_radix, bl->bl_skip, 0);
271 bl->bl_free += count;
272 }
273}
274
275/*
276 * blist_fill() - mark a region in the block bitmap as off-limits
277 * to the allocator (i.e. allocate it), ignoring any
278 * existing allocations. Return the number of blocks
279 * actually filled that were free before the call.
280 */
281
282blist_blkno_t
283blist_fill(blist_t bl, blist_blkno_t blkno, blist_blkno_t count)
284{
285 blist_blkno_t filled;
286
287 if (bl) {
288 if (bl->bl_radix == BLIST_BMAP_RADIX)
289 filled = blst_leaf_fill(bl->bl_root, blkno, count);
290 else
291 filled = blst_meta_fill(bl->bl_root, blkno, count,
292 bl->bl_radix, bl->bl_skip, 0);
293 bl->bl_free -= filled;
294 return filled;
295 } else
296 return 0;
297}
298
299/*
300 * blist_resize() - resize an existing radix tree to handle the
301 * specified number of blocks. This will reallocate
302 * the tree and transfer the previous bitmap to the new
303 * one. When extending the tree you can specify whether
304 * the new blocks are to left allocated or freed.
305 */
306
307void
308blist_resize(blist_t *pbl, blist_blkno_t count, int freenew)
309{
310 blist_t newbl = blist_create(count);
311 blist_t save = *pbl;
312
313 *pbl = newbl;
314 if (count > save->bl_blocks)
315 count = save->bl_blocks;
316 blst_copy(save->bl_root, 0, save->bl_radix, save->bl_skip, newbl, count);
317
318 /*
319 * If resizing upwards, should we free the new space or not?
320 */
321 if (freenew && count < newbl->bl_blocks) {
322 blist_free(newbl, count, newbl->bl_blocks - count);
323 }
324 blist_destroy(save);
325}
326
327#ifdef BLIST_DEBUG
328
329/*
330 * blist_print() - dump radix tree
331 */
332
333void
334blist_print(blist_t bl)
335{
336 printf("BLIST {\n");
337 blst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4);
338 printf("}\n");
339}
340
341#endif
342
343/************************************************************************
344 * ALLOCATION SUPPORT FUNCTIONS *
345 ************************************************************************
346 *
347 * These support functions do all the actual work. They may seem
348 * rather longish, but that's because I've commented them up. The
349 * actual code is straight forward.
350 *
351 */
352
353/*
354 * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap).
355 *
356 * This is the core of the allocator and is optimized for the 1 block
357 * and the BLIST_BMAP_RADIX block allocation cases. Other cases are
358 * somewhat slower. The 1 block allocation case is log2 and extremely
359 * quick.
360 */
361
362static blist_blkno_t
363blst_leaf_alloc(
364 blmeta_t *scan,
365 blist_blkno_t blk,
366 int count
367) {
368 blist_bitmap_t orig = scan->u.bmu_bitmap;
369
370 if (orig == 0) {
371 /*
372 * Optimize bitmap all-allocated case. Also, count = 1
373 * case assumes at least 1 bit is free in the bitmap, so
374 * we have to take care of this case here.
375 */
376 scan->bm_bighint = 0;
377 return(BLIST_NONE);
378 }
379 if (count == 1) {
380 /*
381 * Optimized code to allocate one bit out of the bitmap
382 */
383 blist_bitmap_t mask;
384 int j = BLIST_BMAP_RADIX/2;
385 int r = 0;
386
387 mask = (blist_bitmap_t)-1 >> (BLIST_BMAP_RADIX/2);
388
389 while (j) {
390 if ((orig & mask) == 0) {
391 r += j;
392 orig >>= j;
393 }
394 j >>= 1;
395 mask >>= j;
396 }
397 scan->u.bmu_bitmap &= ~((blist_bitmap_t)1 << r);
398 return(blk + r);
399 }
400 if (count <= BLIST_BMAP_RADIX) {
401 /*
402 * non-optimized code to allocate N bits out of the bitmap.
403 * The more bits, the faster the code runs. It will run
404 * the slowest allocating 2 bits, but since there aren't any
405 * memory ops in the core loop (or shouldn't be, anyway),
406 * you probably won't notice the difference.
407 */
408 int j;
409 int n = BLIST_BMAP_RADIX - count;
410 blist_bitmap_t mask;
411
412 mask = (blist_bitmap_t)-1 >> n;
413
414 for (j = 0; j <= n; ++j) {
415 if ((orig & mask) == mask) {
416 scan->u.bmu_bitmap &= ~mask;
417 return(blk + j);
418 }
419 mask = (mask << 1);
420 }
421 }
422 /*
423 * We couldn't allocate count in this subtree, update bighint.
424 */
425 scan->bm_bighint = count - 1;
426 return(BLIST_NONE);
427}
428
429/*
430 * blist_meta_alloc() - allocate at a meta in the radix tree.
431 *
432 * Attempt to allocate at a meta node. If we can't, we update
433 * bighint and return a failure. Updating bighint optimize future
434 * calls that hit this node. We have to check for our collapse cases
435 * and we have a few optimizations strewn in as well.
436 */
437
438static blist_blkno_t
439blst_meta_alloc(
440 blmeta_t *scan,
441 blist_blkno_t blk,
442 blist_blkno_t count,
443 blist_blkno_t radix,
444 blist_blkno_t skip
445) {
446 blist_blkno_t i;
447 blist_blkno_t next_skip = (skip / BLIST_META_RADIX);
448
449 if (scan->u.bmu_avail == 0) {
450 /*
451 * ALL-ALLOCATED special case
452 */
453 scan->bm_bighint = count;
454 return(BLIST_NONE);
455 }
456
457 if (scan->u.bmu_avail == radix) {
458 radix /= BLIST_META_RADIX;
459
460 /*
461 * ALL-FREE special case, initialize uninitialize
462 * sublevel.
463 */
464 for (i = 1; i <= skip; i += next_skip) {
465 if (scan[i].bm_bighint == (blist_blkno_t)-1)
466 break;
467 if (next_skip == 1) {
468 scan[i].u.bmu_bitmap = (blist_bitmap_t)-1;
469 scan[i].bm_bighint = BLIST_BMAP_RADIX;
470 } else {
471 scan[i].bm_bighint = radix;
472 scan[i].u.bmu_avail = radix;
473 }
474 }
475 } else {
476 radix /= BLIST_META_RADIX;
477 }
478
479 for (i = 1; i <= skip; i += next_skip) {
480 if (scan[i].bm_bighint == (blist_blkno_t)-1) {
481 /*
482 * Terminator
483 */
484 break;
485 } else if (count <= scan[i].bm_bighint) {
486 /*
487 * count fits in object
488 */
489 blist_blkno_t r;
490 if (next_skip == 1) {
491 r = blst_leaf_alloc(&scan[i], blk, count);
492 } else {
493 r = blst_meta_alloc(&scan[i], blk, count, radix, next_skip - 1);
494 }
495 if (r != BLIST_NONE) {
496 scan->u.bmu_avail -= count;
497 if (scan->bm_bighint > scan->u.bmu_avail)
498 scan->bm_bighint = scan->u.bmu_avail;
499 return(r);
500 }
501 } else if (count > radix) {
502 /*
503 * count does not fit in object even if it were
504 * complete free.
505 */
506 panic("blist_meta_alloc: allocation too large");
507 }
508 blk += radix;
509 }
510
511 /*
512 * We couldn't allocate count in this subtree, update bighint.
513 */
514 if (scan->bm_bighint >= count)
515 scan->bm_bighint = count - 1;
516 return(BLIST_NONE);
517}
518
519/*
520 * BLST_LEAF_FREE() - free allocated block from leaf bitmap
521 *
522 */
523
524static void
525blst_leaf_free(
526 blmeta_t *scan,
527 blist_blkno_t blk,
528 int count
529) {
530 /*
531 * free some data in this bitmap
532 *
533 * e.g.
534 * 0000111111111110000
535 * \_________/\__/
536 * v n
537 */
538 int n = blk & (BLIST_BMAP_RADIX - 1);
539 blist_bitmap_t mask;
540
541 mask = ((blist_bitmap_t)-1 << n) &
542 ((blist_bitmap_t)-1 >> (BLIST_BMAP_RADIX - count - n));
543
544 if (scan->u.bmu_bitmap & mask)
545 panic("blst_radix_free: freeing free block");
546 scan->u.bmu_bitmap |= mask;
547
548 /*
549 * We could probably do a better job here. We are required to make
550 * bighint at least as large as the biggest contiguous block of
551 * data. If we just shoehorn it, a little extra overhead will
552 * be incured on the next allocation (but only that one typically).
553 */
554 scan->bm_bighint = BLIST_BMAP_RADIX;
555}
556
557/*
558 * BLST_META_FREE() - free allocated blocks from radix tree meta info
559 *
560 * This support routine frees a range of blocks from the bitmap.
561 * The range must be entirely enclosed by this radix node. If a
562 * meta node, we break the range down recursively to free blocks
563 * in subnodes (which means that this code can free an arbitrary
564 * range whereas the allocation code cannot allocate an arbitrary
565 * range).
566 */
567
568static void
569blst_meta_free(
570 blmeta_t *scan,
571 blist_blkno_t freeBlk,
572 blist_blkno_t count,
573 blist_blkno_t radix,
574 blist_blkno_t skip,
575 blist_blkno_t blk
576) {
577 blist_blkno_t i;
578 blist_blkno_t next_skip = (skip / BLIST_META_RADIX);
579
580#if 0
581 printf("FREE (%" PRIx64 ",%" PRIu64
582 ") FROM (%" PRIx64 ",%" PRIu64 ")\n",
583 (uint64_t)freeBlk, (uint64_t)count,
584 (uint64_t)blk, (uint64_t)radix
585 );
586#endif
587
588 if (scan->u.bmu_avail == 0) {
589 /*
590 * ALL-ALLOCATED special case, with possible
591 * shortcut to ALL-FREE special case.
592 */
593 scan->u.bmu_avail = count;
594 scan->bm_bighint = count;
595
596 if (count != radix) {
597 for (i = 1; i <= skip; i += next_skip) {
598 if (scan[i].bm_bighint == (blist_blkno_t)-1)
599 break;
600 scan[i].bm_bighint = 0;
601 if (next_skip == 1) {
602 scan[i].u.bmu_bitmap = 0;
603 } else {
604 scan[i].u.bmu_avail = 0;
605 }
606 }
607 /* fall through */
608 }
609 } else {
610 scan->u.bmu_avail += count;
611 /* scan->bm_bighint = radix; */
612 }
613
614 /*
615 * ALL-FREE special case.
616 */
617
618 if (scan->u.bmu_avail == radix)
619 return;
620 if (scan->u.bmu_avail > radix)
621 panic("blst_meta_free: freeing already free blocks (%"
622 PRIu64 ") %" PRIu64 "/%" PRIu64,
623 (uint64_t)count,
624 (uint64_t)scan->u.bmu_avail,
625 (uint64_t)radix);
626
627 /*
628 * Break the free down into its components
629 */
630
631 radix /= BLIST_META_RADIX;
632
633 i = (freeBlk - blk) / radix;
634 blk += i * radix;
635 i = i * next_skip + 1;
636
637 while (i <= skip && blk < freeBlk + count) {
638 blist_blkno_t v;
639
640 v = blk + radix - freeBlk;
641 if (v > count)
642 v = count;
643
644 if (scan->bm_bighint == (blist_blkno_t)-1)
645 panic("blst_meta_free: freeing unexpected range");
646
647 if (next_skip == 1) {
648 blst_leaf_free(&scan[i], freeBlk, v);
649 } else {
650 blst_meta_free(&scan[i], freeBlk, v, radix, next_skip - 1, blk);
651 }
652 if (scan->bm_bighint < scan[i].bm_bighint)
653 scan->bm_bighint = scan[i].bm_bighint;
654 count -= v;
655 freeBlk += v;
656 blk += radix;
657 i += next_skip;
658 }
659}
660
661/*
662 * BLIST_RADIX_COPY() - copy one radix tree to another
663 *
664 * Locates free space in the source tree and frees it in the destination
665 * tree. The space may not already be free in the destination.
666 */
667
668static void blst_copy(
669 blmeta_t *scan,
670 blist_blkno_t blk,
671 blist_blkno_t radix,
672 blist_blkno_t skip,
673 blist_t dest,
674 blist_blkno_t count
675) {
676 blist_blkno_t next_skip;
677 blist_blkno_t i;
678
679 /*
680 * Leaf node
681 */
682
683 if (radix == BLIST_BMAP_RADIX) {
684 blist_bitmap_t v = scan->u.bmu_bitmap;
685
686 if (v == (blist_bitmap_t)-1) {
687 blist_free(dest, blk, count);
688 } else if (v != 0) {
689 int j;
690
691 for (j = 0; j < BLIST_BMAP_RADIX && j < count; ++j) {
692 if (v & (1 << j))
693 blist_free(dest, blk + j, 1);
694 }
695 }
696 return;
697 }
698
699 /*
700 * Meta node
701 */
702
703 if (scan->u.bmu_avail == 0) {
704 /*
705 * Source all allocated, leave dest allocated
706 */
707 return;
708 }
709 if (scan->u.bmu_avail == radix) {
710 /*
711 * Source all free, free entire dest
712 */
713 if (count < radix)
714 blist_free(dest, blk, count);
715 else
716 blist_free(dest, blk, radix);
717 return;
718 }
719
720
721 radix /= BLIST_META_RADIX;
722 next_skip = (skip / BLIST_META_RADIX);
723
724 for (i = 1; count && i <= skip; i += next_skip) {
725 if (scan[i].bm_bighint == (blist_blkno_t)-1)
726 break;
727
728 if (count >= radix) {
729 blst_copy(
730 &scan[i],
731 blk,
732 radix,
733 next_skip - 1,
734 dest,
735 radix
736 );
737 count -= radix;
738 } else {
739 if (count) {
740 blst_copy(
741 &scan[i],
742 blk,
743 radix,
744 next_skip - 1,
745 dest,
746 count
747 );
748 }
749 count = 0;
750 }
751 blk += radix;
752 }
753}
754
755/*
756 * BLST_LEAF_FILL() - allocate specific blocks in leaf bitmap
757 *
758 * This routine allocates all blocks in the specified range
759 * regardless of any existing allocations in that range. Returns
760 * the number of blocks allocated by the call.
761 */
762
763static int
764blst_leaf_fill(blmeta_t *scan, blist_blkno_t blk, int count)
765{
766 int n = blk & (BLIST_BMAP_RADIX - 1);
767 int nblks;
768 blist_bitmap_t mask, bitmap;
769
770 mask = ((blist_bitmap_t)-1 << n) &
771 ((blist_bitmap_t)-1 >> (BLIST_BMAP_RADIX - count - n));
772
773 /* Count the number of blocks we're about to allocate */
774 bitmap = scan->u.bmu_bitmap & mask;
775 for (nblks = 0; bitmap != 0; nblks++)
776 bitmap &= bitmap - 1;
777
778 scan->u.bmu_bitmap &= ~mask;
779 return nblks;
780}
781
782/*
783 * BLIST_META_FILL() - allocate specific blocks at a meta node
784 *
785 * This routine allocates the specified range of blocks,
786 * regardless of any existing allocations in the range. The
787 * range must be within the extent of this node. Returns the
788 * number of blocks allocated by the call.
789 */
790static blist_blkno_t
791blst_meta_fill(
792 blmeta_t *scan,
793 blist_blkno_t allocBlk,
794 blist_blkno_t count,
795 blist_blkno_t radix,
796 blist_blkno_t skip,
797 blist_blkno_t blk
798) {
799 blist_blkno_t i;
800 blist_blkno_t next_skip = (skip / BLIST_META_RADIX);
801 blist_blkno_t nblks = 0;
802
803 if (count == radix || scan->u.bmu_avail == 0) {
804 /*
805 * ALL-ALLOCATED special case
806 */
807 nblks = scan->u.bmu_avail;
808 scan->u.bmu_avail = 0;
809 scan->bm_bighint = count;
810 return nblks;
811 }
812
813 if (count > radix)
814 panic("blist_meta_fill: allocation too large");
815
816 if (scan->u.bmu_avail == radix) {
817 radix /= BLIST_META_RADIX;
818
819 /*
820 * ALL-FREE special case, initialize sublevel
821 */
822 for (i = 1; i <= skip; i += next_skip) {
823 if (scan[i].bm_bighint == (blist_blkno_t)-1)
824 break;
825 if (next_skip == 1) {
826 scan[i].u.bmu_bitmap = (blist_bitmap_t)-1;
827 scan[i].bm_bighint = BLIST_BMAP_RADIX;
828 } else {
829 scan[i].bm_bighint = radix;
830 scan[i].u.bmu_avail = radix;
831 }
832 }
833 } else {
834 radix /= BLIST_META_RADIX;
835 }
836
837 i = (allocBlk - blk) / radix;
838 blk += i * radix;
839 i = i * next_skip + 1;
840
841 while (i <= skip && blk < allocBlk + count) {
842 blist_blkno_t v;
843
844 v = blk + radix - allocBlk;
845 if (v > count)
846 v = count;
847
848 if (scan->bm_bighint == (blist_blkno_t)-1)
849 panic("blst_meta_fill: filling unexpected range");
850
851 if (next_skip == 1) {
852 nblks += blst_leaf_fill(&scan[i], allocBlk, v);
853 } else {
854 nblks += blst_meta_fill(&scan[i], allocBlk, v,
855 radix, next_skip - 1, blk);
856 }
857 count -= v;
858 allocBlk += v;
859 blk += radix;
860 i += next_skip;
861 }
862 scan->u.bmu_avail -= nblks;
863 return nblks;
864}
865
866/*
867 * BLST_RADIX_INIT() - initialize radix tree
868 *
869 * Initialize our meta structures and bitmaps and calculate the exact
870 * amount of space required to manage 'count' blocks - this space may
871 * be considerably less than the calculated radix due to the large
872 * RADIX values we use.
873 */
874
875static blist_blkno_t
876blst_radix_init(blmeta_t *scan, blist_blkno_t radix, blist_blkno_t skip,
877 blist_blkno_t count)
878{
879 blist_blkno_t i;
880 blist_blkno_t next_skip;
881 blist_blkno_t memindex = 0;
882
883 /*
884 * Leaf node
885 */
886
887 if (radix == BLIST_BMAP_RADIX) {
888 if (scan) {
889 scan->bm_bighint = 0;
890 scan->u.bmu_bitmap = 0;
891 }
892 return(memindex);
893 }
894
895 /*
896 * Meta node. If allocating the entire object we can special
897 * case it. However, we need to figure out how much memory
898 * is required to manage 'count' blocks, so we continue on anyway.
899 */
900
901 if (scan) {
902 scan->bm_bighint = 0;
903 scan->u.bmu_avail = 0;
904 }
905
906 radix /= BLIST_META_RADIX;
907 next_skip = (skip / BLIST_META_RADIX);
908
909 for (i = 1; i <= skip; i += next_skip) {
910 if (count >= radix) {
911 /*
912 * Allocate the entire object
913 */
914 memindex = i + blst_radix_init(
915 ((scan) ? &scan[i] : NULL),
916 radix,
917 next_skip - 1,
918 radix
919 );
920 count -= radix;
921 } else if (count > 0) {
922 /*
923 * Allocate a partial object
924 */
925 memindex = i + blst_radix_init(
926 ((scan) ? &scan[i] : NULL),
927 radix,
928 next_skip - 1,
929 count
930 );
931 count = 0;
932 } else {
933 /*
934 * Add terminator and break out
935 */
936 if (scan)
937 scan[i].bm_bighint = (blist_blkno_t)-1;
938 break;
939 }
940 }
941 if (memindex < i)
942 memindex = i;
943 return(memindex);
944}
945
946#ifdef BLIST_DEBUG
947
948static void
949blst_radix_print(blmeta_t *scan, blist_blkno_t blk, blist_blkno_t radix,
950 blist_blkno_t skip, int tab)
951{
952 blist_blkno_t i;
953 blist_blkno_t next_skip;
954 int lastState = 0;
955
956 if (radix == BLIST_BMAP_RADIX) {
957 printf(
958 "%*.*s(%0*" PRIx64 ",%" PRIu64
959 "): bitmap %0*" PRIx64 " big=%" PRIu64 "\n",
960 tab, tab, "",
961 sizeof(blk) * 2,
962 (uint64_t)blk,
963 (uint64_t)radix,
964 sizeof(scan->u.bmu_bitmap) * 2,
965 (uint64_t)scan->u.bmu_bitmap,
966 (uint64_t)scan->bm_bighint
967 );
968 return;
969 }
970
971 if (scan->u.bmu_avail == 0) {
972 printf(
973 "%*.*s(%0*" PRIx64 ",%" PRIu64") ALL ALLOCATED\n",
974 tab, tab, "",
975 sizeof(blk) * 2,
976 (uint64_t)blk,
977 (uint64_t)radix
978 );
979 return;
980 }
981 if (scan->u.bmu_avail == radix) {
982 printf(
983 "%*.*s(%0*" PRIx64 ",%" PRIu64 ") ALL FREE\n",
984 tab, tab, "",
985 sizeof(blk) * 2,
986 (uint64_t)blk,
987 (uint64_t)radix
988 );
989 return;
990 }
991
992 printf(
993 "%*.*s(%0*" PRIx64 ",%" PRIu64 "): subtree (%" PRIu64 "/%"
994 PRIu64 ") big=%" PRIu64 " {\n",
995 tab, tab, "",
996 sizeof(blk) * 2,
997 (uint64_t)blk,
998 (uint64_t)radix,
999 (uint64_t)scan->u.bmu_avail,
1000 (uint64_t)radix,
1001 (uint64_t)scan->bm_bighint
1002 );
1003
1004 radix /= BLIST_META_RADIX;
1005 next_skip = (skip / BLIST_META_RADIX);
1006 tab += 4;
1007
1008 for (i = 1; i <= skip; i += next_skip) {
1009 if (scan[i].bm_bighint == (blist_blkno_t)-1) {
1010 printf(
1011 "%*.*s(%0*" PRIx64 ",%" PRIu64 "): Terminator\n",
1012 tab, tab, "",
1013 sizeof(blk) * 2,
1014 (uint64_t)blk,
1015 (uint64_t)radix
1016 );
1017 lastState = 0;
1018 break;
1019 }
1020 blst_radix_print(
1021 &scan[i],
1022 blk,
1023 radix,
1024 next_skip - 1,
1025 tab
1026 );
1027 blk += radix;
1028 }
1029 tab -= 4;
1030
1031 printf(
1032 "%*.*s}\n",
1033 tab, tab, ""
1034 );
1035}
1036
1037#endif
1038
1039#ifdef BLIST_DEBUG
1040
1041int
1042main(int ac, char **av)
1043{
1044 blist_blkno_t size = 1024;
1045 int i;
1046 blist_t bl;
1047
1048 for (i = 1; i < ac; ++i) {
1049 const char *ptr = av[i];
1050 if (*ptr != '-') {
1051 size = strtol(ptr, NULL, 0);
1052 continue;
1053 }
1054 ptr += 2;
1055 fprintf(stderr, "Bad option: %s\n", ptr - 2);
1056 exit(1);
1057 }
1058 bl = blist_create(size);
1059 blist_free(bl, 0, size);
1060
1061 for (;;) {
1062 char buf[1024];
1063 uint64_t da = 0;
1064 uint64_t count = 0;
1065
1066 printf("%" PRIu64 "/%" PRIu64 "/%" PRIu64 "> ",
1067 (uint64_t)bl->bl_free,
1068 (uint64_t)size,
1069 (uint64_t)bl->bl_radix);
1070 fflush(stdout);
1071 if (fgets(buf, sizeof(buf), stdin) == NULL)
1072 break;
1073 switch(buf[0]) {
1074 case 'r':
1075 if (sscanf(buf + 1, "%" SCNu64, &count) == 1) {
1076 blist_resize(&bl, count, 1);
1077 } else {
1078 printf("?\n");
1079 }
1080 case 'p':
1081 blist_print(bl);
1082 break;
1083 case 'a':
1084 if (sscanf(buf + 1, "%" SCNu64, &count) == 1) {
1085 blist_blkno_t blk = blist_alloc(bl, count);
1086 printf(" R=%0*" PRIx64 "\n",
1087 sizeof(blk) * 2,
1088 (uint64_t)blk);
1089 } else {
1090 printf("?\n");
1091 }
1092 break;
1093 case 'f':
1094 if (sscanf(buf + 1, "%" SCNx64 " %" SCNu64,
1095 &da, &count) == 2) {
1096 blist_free(bl, da, count);
1097 } else {
1098 printf("?\n");
1099 }
1100 break;
1101 case 'l':
1102 if (sscanf(buf + 1, "%" SCNx64 " %" SCNu64,
1103 &da, &count) == 2) {
1104 printf(" n=%" PRIu64 "\n",
1105 (uint64_t)blist_fill(bl, da, count));
1106 } else {
1107 printf("?\n");
1108 }
1109 break;
1110 case '?':
1111 case 'h':
1112 puts(
1113 "p -print\n"
1114 "a %d -allocate\n"
1115 "f %x %d -free\n"
1116 "l %x %d -fill\n"
1117 "r %d -resize\n"
1118 "h/? -help"
1119 );
1120 break;
1121 default:
1122 printf("?\n");
1123 break;
1124 }
1125 }
1126 return(0);
1127}
1128
1129void
1130panic(const char *ctl, ...)
1131{
1132 va_list va;
1133
1134 va_start(va, ctl);
1135 vfprintf(stderr, ctl, va);
1136 fprintf(stderr, "\n");
1137 va_end(va);
1138 exit(1);
1139}
1140
1141#endif
1142
1143