HAMMER 15/many - user utility infrastructure, refactor alists, misc
[dragonfly.git] / sys / vfs / hammer / hammer_alist.c
CommitLineData
8750964d
MD
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 *
61aeeb33 41 * $DragonFly: src/sys/vfs/hammer/Attic/hammer_alist.c,v 1.6 2008/01/03 06:48:49 dillon Exp $
8750964d
MD
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 *
c60bb2c5
MD
63 * The radix tree supports allocator layering. By supplying a base_radix > 1
64 * the allocator will issue callbacks to recurse into lower layers once
61aeeb33
MD
65 * higher layers have been exhausted.
66 *
67 * ALLOCATIONS IN MULTIPLES OF base_radix WILL BE ENTIRELY RETAINED IN THE
68 * HIGHER LEVEL ALLOCATOR AND NEVER RECURSE. This means the init function
69 * will never be called and the A-list will consider the underlying zone
70 * as being uninitialized. If you then do a partial free, the A-list will
71 * call the init function before freeing. Most users of this API, including
72 * HAMMER, only allocate and free whole zones, or only allocate and free
73 * partial zones, and never mix their metaphors.
c60bb2c5 74 *
8750964d
MD
75 * This code can be compiled stand-alone for debugging.
76 */
77
78#ifdef _KERNEL
79
80#include <sys/param.h>
81#include <sys/systm.h>
82#include <sys/lock.h>
83#include <sys/kernel.h>
84#include <sys/malloc.h>
85#include <vm/vm.h>
86#include <vm/vm_object.h>
87#include <vm/vm_kern.h>
88#include <vm/vm_extern.h>
89#include <vm/vm_page.h>
90
427e5fc6 91#include "hammer_alist.h"
c60bb2c5 92#include "hammer_disk.h"
8750964d
MD
93
94#else
95
96#ifndef ALIST_NO_DEBUG
97#define ALIST_DEBUG
98#endif
99
100#include <sys/types.h>
101#include <stdio.h>
102#include <assert.h>
103#include <string.h>
104#include <stdlib.h>
105#include <stdarg.h>
106
107#define kmalloc(a,b,c) malloc(a)
108#define kfree(a,b) free(a)
109#define kprintf printf
110#define KKASSERT(exp) assert(exp)
111struct malloc_type;
112
c60bb2c5 113#include "hammer_alist.h"
8750964d
MD
114
115void panic(const char *ctl, ...);
116
117#endif
118
119/*
120 * static support functions
121 */
122
c60bb2c5 123static int32_t hammer_alst_leaf_alloc_fwd(hammer_almeta_t scan,
9775c955 124 int32_t blk, int count, int32_t atblk);
c60bb2c5
MD
125static int32_t hammer_alst_meta_alloc_fwd(hammer_alist_t live,
126 hammer_almeta_t scan,
8750964d 127 int32_t blk, int32_t count,
9775c955 128 int32_t radix, int skip, int32_t atblk);
c60bb2c5 129static int32_t hammer_alst_leaf_alloc_rev(hammer_almeta_t scan,
9775c955 130 int32_t blk, int count, int32_t atblk);
c60bb2c5
MD
131static int32_t hammer_alst_meta_alloc_rev(hammer_alist_t live,
132 hammer_almeta_t scan,
8750964d 133 int32_t blk, int32_t count,
9775c955 134 int32_t radix, int skip, int32_t atblk);
61aeeb33
MD
135static void hammer_alst_leaf_free(hammer_almeta_t scan, int32_t relblk,
136 int count);
c60bb2c5 137static void hammer_alst_meta_free(hammer_alist_t live, hammer_almeta_t scan,
8750964d
MD
138 int32_t freeBlk, int32_t count,
139 int32_t radix, int skip, int32_t blk);
c60bb2c5 140static int32_t hammer_alst_radix_init(hammer_almeta_t scan,
8750964d
MD
141 int32_t radix, int skip, int32_t count);
142#ifdef ALIST_DEBUG
c60bb2c5
MD
143static void hammer_alst_radix_print(hammer_alist_t live,
144 hammer_almeta_t scan, int32_t blk,
8750964d
MD
145 int32_t radix, int skip, int tab);
146#endif
147
148/*
c60bb2c5
MD
149 * Initialize an a-list config structure for use. The config structure
150 * describes the basic structure of an a-list's topology and may be
151 * shared by any number of a-lists which have the same topology.
152 *
153 * blocks is the total number of blocks, that is the number of blocks
154 * handled at this layer multiplied by the base radix.
155 *
156 * When base_radix != 1 the A-list has only meta elements and does not have
157 * any leaves, in order to be able to track partial allocations.
8750964d
MD
158 */
159void
c60bb2c5
MD
160hammer_alist_template(hammer_alist_config_t bl, int32_t blocks,
161 int32_t base_radix, int32_t maxmeta)
8750964d
MD
162{
163 int radix;
c60bb2c5 164 int skip;
8750964d
MD
165
166 /*
c60bb2c5
MD
167 * Calculate radix and skip field used for scanning. The leaf nodes
168 * in our tree are either BMAP or META nodes depending on whether
169 * we chain to a lower level allocation layer or not.
8750964d 170 */
c60bb2c5
MD
171 if (base_radix == 1)
172 radix = HAMMER_ALIST_BMAP_RADIX;
173 else
174 radix = HAMMER_ALIST_META_RADIX;
175 skip = 1;
8750964d 176
c60bb2c5 177 while (radix < blocks / base_radix) {
8750964d 178 radix *= HAMMER_ALIST_META_RADIX;
c60bb2c5 179 skip = skip * HAMMER_ALIST_META_RADIX + 1;
8750964d
MD
180 }
181
c60bb2c5
MD
182 /*
183 * Increase the radix based on the number of blocks a lower level
184 * allocator is able to handle at the 'base' of our allocator.
185 * If base_radix != 1 the caller will have to initialize the callback
186 * fields to implement the lower level allocator.
187 */
7f7c1f84 188 KKASSERT((int64_t)radix * (int64_t)base_radix < 0x80000000LL);
c60bb2c5
MD
189 radix *= base_radix;
190
8750964d
MD
191 bzero(bl, sizeof(*bl));
192
193 bl->bl_blocks = blocks;
c60bb2c5 194 bl->bl_base_radix = base_radix;
8750964d
MD
195 bl->bl_radix = radix;
196 bl->bl_skip = skip;
c60bb2c5
MD
197 bl->bl_rootblks = hammer_alst_radix_init(NULL, bl->bl_radix,
198 bl->bl_skip, blocks);
199 ++bl->bl_rootblks; /* one more for freeblks header */
200 if (base_radix == 1)
201 bl->bl_terminal = 1;
202 KKASSERT(maxmeta == 0 || bl->bl_rootblks <= maxmeta);
8750964d
MD
203
204#if defined(ALIST_DEBUG)
205 kprintf(
c60bb2c5 206 "PRIMARY ALIST LAYER manages %d blocks"
8750964d 207 ", requiring %dK (%d bytes) of ram\n",
c60bb2c5
MD
208 bl->bl_blocks / bl->bl_base_radix,
209 (bl->bl_rootblks * sizeof(struct hammer_almeta) + 1023) / 1024,
210 (bl->bl_rootblks * sizeof(struct hammer_almeta))
8750964d
MD
211 );
212 kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
213#endif
214}
215
216void
61aeeb33
MD
217hammer_alist_init(hammer_alist_t live, int32_t start, int32_t count,
218 enum hammer_alloc_state state)
8750964d 219{
c60bb2c5
MD
220 hammer_alist_config_t bl = live->config;
221
c60bb2c5 222 live->meta->bm_alist_freeblks = 0;
61aeeb33 223 live->meta->bm_alist_base_freeblks = count;
c60bb2c5
MD
224 hammer_alst_radix_init(live->meta + 1, bl->bl_radix,
225 bl->bl_skip, bl->bl_blocks);
61aeeb33
MD
226 if (count && state == HAMMER_ASTATE_FREE)
227 hammer_alist_free(live, start, count);
8750964d
MD
228}
229
230#if !defined(_KERNEL) && defined(ALIST_DEBUG)
231
232/*
233 * hammer_alist_create() (userland only)
234 *
235 * create a alist capable of handling up to the specified number of
236 * blocks. blocks must be greater then 0
237 *
238 * The smallest alist consists of a single leaf node capable of
c60bb2c5
MD
239 * managing HAMMER_ALIST_BMAP_RADIX blocks, or (if base_radix != 1)
240 * a single meta node capable of managing HAMMER_ALIST_META_RADIX
241 * blocks which recurses into other storage layers for a total
242 * handling capability of (HAMMER_ALIST_META_RADIX * base_radix) blocks.
243 *
244 * Larger a-list's increase their capability exponentially by
245 * HAMMER_ALIST_META_RADIX.
246 *
247 * The block count is the total number of blocks inclusive of any
248 * layering. blocks can be less then base_radix and will result in
249 * a radix tree with a single leaf node which then chains down.
8750964d
MD
250 */
251
252hammer_alist_t
c60bb2c5 253hammer_alist_create(int32_t blocks, int32_t base_radix,
61aeeb33 254 struct malloc_type *mtype, enum hammer_alloc_state state)
8750964d 255{
c60bb2c5
MD
256 hammer_alist_t live;
257 hammer_alist_config_t bl;
8750964d
MD
258 size_t metasize;
259
c60bb2c5
MD
260 live = kmalloc(sizeof(*live), mtype, M_WAITOK);
261 live->config = bl = kmalloc(sizeof(*bl), mtype, M_WAITOK);
262 hammer_alist_template(bl, blocks, base_radix, 0);
8750964d 263
c60bb2c5
MD
264 metasize = sizeof(*live->meta) * bl->bl_rootblks;
265 live->meta = kmalloc(metasize, mtype, M_WAITOK);
266 bzero(live->meta, metasize);
8750964d
MD
267
268#if defined(ALIST_DEBUG)
269 kprintf(
270 "ALIST representing %d blocks (%d MB of swap)"
271 ", requiring %dK (%d bytes) of ram\n",
272 bl->bl_blocks,
273 bl->bl_blocks * 4 / 1024,
c60bb2c5
MD
274 (bl->bl_rootblks * sizeof(*live->meta) + 1023) / 1024,
275 (bl->bl_rootblks * sizeof(*live->meta))
8750964d 276 );
c60bb2c5
MD
277 if (base_radix != 1) {
278 kprintf("ALIST recurses when it reaches a base_radix of %d\n",
279 base_radix);
280 }
8750964d
MD
281 kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
282#endif
61aeeb33 283 hammer_alist_init(live, 0, blocks, state);
c60bb2c5 284 return(live);
8750964d
MD
285}
286
287void
c60bb2c5 288hammer_alist_destroy(hammer_alist_t live, struct malloc_type *mtype)
8750964d 289{
c60bb2c5
MD
290 kfree(live->config, mtype);
291 kfree(live->meta, mtype);
292 live->config = NULL;
293 live->meta = NULL;
294 kfree(live, mtype);
8750964d
MD
295}
296
297#endif
298
299/*
300 * hammer_alist_alloc()
301 *
302 * Reserve space in the block bitmap. Return the base of a contiguous
303 * region or HAMMER_ALIST_BLOCK_NONE if space could not be allocated.
304 */
305
306int32_t
c60bb2c5 307hammer_alist_alloc(hammer_alist_t live, int32_t count)
8750964d
MD
308{
309 int32_t blk = HAMMER_ALIST_BLOCK_NONE;
c60bb2c5 310 hammer_alist_config_t bl = live->config;
8750964d
MD
311
312 KKASSERT((count | (count - 1)) == (count << 1) - 1);
313
c60bb2c5
MD
314 if (bl && count <= bl->bl_radix) {
315 /*
316 * When skip is 1 we are at a leaf. If we are the terminal
317 * allocator we use our native leaf functions and radix will
318 * be HAMMER_ALIST_BMAP_RADIX. Otherwise we are a meta node
319 * which will chain to another allocator.
320 */
321 if (bl->bl_skip == 1 && bl->bl_terminal) {
322#ifndef _KERNEL
323 KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
324#endif
325 blk = hammer_alst_leaf_alloc_fwd(
9775c955 326 live->meta + 1, 0, count, 0);
8750964d
MD
327 } else {
328 blk = hammer_alst_meta_alloc_fwd(
c60bb2c5 329 live, live->meta + 1,
9775c955 330 0, count, bl->bl_radix, bl->bl_skip, 0);
8750964d
MD
331 }
332 if (blk != HAMMER_ALIST_BLOCK_NONE)
c60bb2c5 333 live->meta->bm_alist_freeblks -= count;
8750964d
MD
334 }
335 return(blk);
336}
337
338int32_t
9775c955 339hammer_alist_alloc_fwd(hammer_alist_t live, int32_t count, int32_t atblk)
8750964d
MD
340{
341 int32_t blk = HAMMER_ALIST_BLOCK_NONE;
9775c955 342 hammer_alist_config_t bl = live->config;
8750964d
MD
343
344 KKASSERT((count | (count - 1)) == (count << 1) - 1);
345
9775c955
MD
346 if (bl && count <= bl->bl_radix) {
347 /*
348 * When skip is 1 we are at a leaf. If we are the terminal
349 * allocator we use our native leaf functions and radix will
350 * be HAMMER_ALIST_BMAP_RADIX. Otherwise we are a meta node
351 * which will chain to another allocator.
352 */
c60bb2c5
MD
353 if (bl->bl_skip == 1 && bl->bl_terminal) {
354#ifndef _KERNEL
355 KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
356#endif
9775c955
MD
357 blk = hammer_alst_leaf_alloc_fwd(
358 live->meta + 1, 0, count, atblk);
8750964d 359 } else {
9775c955 360 blk = hammer_alst_meta_alloc_fwd(
c60bb2c5 361 live, live->meta + 1,
9775c955 362 0, count, bl->bl_radix, bl->bl_skip, atblk);
8750964d
MD
363 }
364 if (blk != HAMMER_ALIST_BLOCK_NONE)
c60bb2c5 365 live->meta->bm_alist_freeblks -= count;
8750964d
MD
366 }
367 return(blk);
368}
369
8750964d 370int32_t
9775c955 371hammer_alist_alloc_rev(hammer_alist_t live, int32_t count, int32_t atblk)
8750964d 372{
9775c955
MD
373 hammer_alist_config_t bl = live->config;
374 int32_t blk = HAMMER_ALIST_BLOCK_NONE;
375
376 KKASSERT((count | (count - 1)) == (count << 1) - 1);
8750964d 377
9775c955
MD
378 if (bl && count < bl->bl_radix) {
379 if (bl->bl_skip == 1 && bl->bl_terminal) {
380#ifndef _KERNEL
381 KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
8750964d 382#endif
9775c955
MD
383 blk = hammer_alst_leaf_alloc_rev(
384 live->meta + 1, 0, count, atblk);
385 } else {
386 blk = hammer_alst_meta_alloc_rev(
387 live, live->meta + 1,
388 0, count, bl->bl_radix, bl->bl_skip, atblk);
389 }
390 if (blk != HAMMER_ALIST_BLOCK_NONE)
391 live->meta->bm_alist_freeblks -= count;
392 }
393 return(blk);
394}
8750964d
MD
395
396/*
397 * alist_free()
398 *
399 * Free up space in the block bitmap. Return the base of a contiguous
400 * region. Panic if an inconsistancy is found.
401 *
402 * Unlike allocations, there are no alignment requirements for blkno or
403 * count when freeing blocks.
404 */
405
406void
c60bb2c5 407hammer_alist_free(hammer_alist_t live, int32_t blkno, int32_t count)
8750964d 408{
c60bb2c5
MD
409 hammer_alist_config_t bl = live->config;
410
411 KKASSERT(blkno + count <= bl->bl_blocks);
412 if (bl->bl_skip == 1 && bl->bl_terminal) {
413#ifndef _KERNEL
414 KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
415#endif
416 hammer_alst_leaf_free(live->meta + 1, blkno, count);
417 } else {
418 hammer_alst_meta_free(live, live->meta + 1,
419 blkno, count,
420 bl->bl_radix, bl->bl_skip, 0);
8750964d 421 }
c60bb2c5 422 live->meta->bm_alist_freeblks += count;
8750964d
MD
423}
424
9775c955
MD
425int
426hammer_alist_isfull(hammer_alist_t live)
427{
428 return(live->meta->bm_alist_freeblks == 0);
429}
430
431int
432hammer_alist_isempty(hammer_alist_t live)
433{
61aeeb33
MD
434 return((int)live->meta->bm_alist_freeblks ==
435 live->meta->bm_alist_base_freeblks);
9775c955
MD
436}
437
8750964d
MD
438#ifdef ALIST_DEBUG
439
440/*
441 * alist_print() - dump radix tree
442 */
443
444void
c60bb2c5 445hammer_alist_print(hammer_alist_t live, int tab)
8750964d 446{
c60bb2c5
MD
447 hammer_alist_config_t bl = live->config;
448
449 kprintf("%*.*sALIST (%d free blocks) {\n",
450 tab, tab, "", live->meta->bm_alist_freeblks);
451 hammer_alst_radix_print(live, live->meta + 1, 0,
452 bl->bl_radix, bl->bl_skip, tab + 4);
453 kprintf("%*.*s}\n", tab, tab, "");
8750964d
MD
454}
455
456#endif
457
458/************************************************************************
459 * ALLOCATION SUPPORT FUNCTIONS *
460 ************************************************************************
461 *
462 * These support functions do all the actual work. They may seem
463 * rather longish, but that's because I've commented them up. The
464 * actual code is straight forward.
465 *
466 */
467
468/*
469 * hammer_alist_leaf_alloc_fwd()
470 *
471 * Allocate at a leaf in the radix tree (a bitmap).
472 *
473 * This is the core of the allocator and is optimized for the 1 block
474 * and the HAMMER_ALIST_BMAP_RADIX block allocation cases. Other cases
475 * are somewhat slower. The 1 block allocation case is log2 and extremely
476 * quick.
477 */
478
479static int32_t
9775c955
MD
480hammer_alst_leaf_alloc_fwd(hammer_almeta_t scan, int32_t blk,
481 int count, int32_t atblk)
8750964d
MD
482{
483 u_int32_t orig = scan->bm_bitmap;
9775c955 484 int32_t saveblk = blk;
8750964d
MD
485
486 /*
487 * Optimize bitmap all-allocated case. Also, count = 1
488 * case assumes at least 1 bit is free in the bitmap, so
489 * we have to take care of this case here.
490 */
491 if (orig == 0) {
492 scan->bm_bighint = 0;
493 return(HAMMER_ALIST_BLOCK_NONE);
494 }
495
9775c955 496#if 0
8750964d
MD
497 /*
498 * Optimized code to allocate one bit out of the bitmap
9775c955
MD
499 *
500 * mask iterates e.g. 00001111 00000011 00000001
501 *
502 * mask starts at 00001111
8750964d
MD
503 */
504 if (count == 1) {
505 u_int32_t mask;
506 int j = HAMMER_ALIST_BMAP_RADIX/2;
507 int r = 0;
508
509 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX/2);
510
511 while (j) {
512 if ((orig & mask) == 0) {
513 r += j;
514 orig >>= j;
515 }
516 j >>= 1;
517 mask >>= j;
518 }
519 scan->bm_bitmap &= ~(1 << r);
520 return(blk + r);
521 }
9775c955 522#endif
8750964d
MD
523
524 /*
525 * non-optimized code to allocate N bits out of the bitmap.
526 * The more bits, the faster the code runs. It will run
527 * the slowest allocating 2 bits, but since there aren't any
528 * memory ops in the core loop (or shouldn't be, anyway),
529 * you probably won't notice the difference.
530 *
531 * Similar to the blist case, the alist code also requires
532 * allocations to be power-of-2 sized and aligned to the
533 * size of the allocation, which simplifies the algorithm.
534 */
535 {
536 int j;
537 int n = HAMMER_ALIST_BMAP_RADIX - count;
538 u_int32_t mask;
539
540 mask = (u_int32_t)-1 >> n;
541
542 for (j = 0; j <= n; j += count) {
9775c955 543 if ((orig & mask) == mask && blk >= atblk) {
8750964d 544 scan->bm_bitmap &= ~mask;
9775c955 545 return(blk);
8750964d
MD
546 }
547 mask = mask << count;
9775c955 548 blk += count;
8750964d
MD
549 }
550 }
551
552 /*
9775c955
MD
553 * We couldn't allocate count in this subtree, update bighint if
554 * atblk didn't interfere with the hinting mechanism.
8750964d 555 */
9775c955
MD
556 if (saveblk >= atblk)
557 scan->bm_bighint = count - 1;
8750964d
MD
558 return(HAMMER_ALIST_BLOCK_NONE);
559}
560
561/*
562 * This version allocates blocks in the reverse direction.
563 */
564static int32_t
9775c955
MD
565hammer_alst_leaf_alloc_rev(hammer_almeta_t scan, int32_t blk,
566 int count, int32_t atblk)
8750964d
MD
567{
568 u_int32_t orig = scan->bm_bitmap;
9775c955 569 int32_t saveblk;
8750964d
MD
570
571 /*
572 * Optimize bitmap all-allocated case. Also, count = 1
573 * case assumes at least 1 bit is free in the bitmap, so
574 * we have to take care of this case here.
575 */
576 if (orig == 0) {
577 scan->bm_bighint = 0;
578 return(HAMMER_ALIST_BLOCK_NONE);
579 }
580
9775c955 581#if 0
8750964d
MD
582 /*
583 * Optimized code to allocate one bit out of the bitmap
584 */
585 if (count == 1) {
586 u_int32_t mask;
587 int j = HAMMER_ALIST_BMAP_RADIX/2;
588 int r = HAMMER_ALIST_BMAP_RADIX - 1;
589
590 mask = ~((u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX/2));
591
592 while (j) {
593 if ((orig & mask) == 0) {
594 r -= j;
595 orig <<= j;
596 }
597 j >>= 1;
598 mask <<= j;
599 }
600 scan->bm_bitmap &= ~(1 << r);
601 return(blk + r);
602 }
9775c955 603#endif
8750964d
MD
604
605 /*
606 * non-optimized code to allocate N bits out of the bitmap.
607 * The more bits, the faster the code runs. It will run
608 * the slowest allocating 2 bits, but since there aren't any
609 * memory ops in the core loop (or shouldn't be, anyway),
610 * you probably won't notice the difference.
611 *
612 * Similar to the blist case, the alist code also requires
613 * allocations to be power-of-2 sized and aligned to the
614 * size of the allocation, which simplifies the algorithm.
615 *
616 * initial mask if count == 2: 1100....0000
617 */
618 {
619 int j;
620 int n = HAMMER_ALIST_BMAP_RADIX - count;
621 u_int32_t mask;
622
623 mask = ((u_int32_t)-1 >> n) << n;
9775c955
MD
624 blk += n;
625 saveblk = blk;
8750964d
MD
626
627 for (j = n; j >= 0; j -= count) {
9775c955 628 if ((orig & mask) == mask && blk <= atblk) {
8750964d 629 scan->bm_bitmap &= ~mask;
9775c955 630 return(blk);
8750964d
MD
631 }
632 mask = mask >> count;
9775c955 633 blk -= count;
8750964d
MD
634 }
635 }
636
637 /*
9775c955
MD
638 * We couldn't allocate count in this subtree, update bighint if
639 * atblk didn't interfere with it.
8750964d 640 */
9775c955
MD
641 if (saveblk <= atblk)
642 scan->bm_bighint = count - 1;
8750964d
MD
643 return(HAMMER_ALIST_BLOCK_NONE);
644}
645
646/*
647 * hammer_alist_meta_alloc_fwd()
648 *
649 * Allocate at a meta in the radix tree.
650 *
651 * Attempt to allocate at a meta node. If we can't, we update
652 * bighint and return a failure. Updating bighint optimize future
653 * calls that hit this node. We have to check for our collapse cases
654 * and we have a few optimizations strewn in as well.
655 */
656static int32_t
c60bb2c5
MD
657hammer_alst_meta_alloc_fwd(hammer_alist_t live, hammer_almeta_t scan,
658 int32_t blk, int32_t count,
9775c955 659 int32_t radix, int skip, int32_t atblk
8750964d 660) {
c60bb2c5 661 hammer_alist_config_t bl;
8750964d
MD
662 u_int32_t mask;
663 u_int32_t pmask;
9775c955 664 int32_t saveblk;
c60bb2c5 665 int next_skip;
9775c955 666 int i;
8750964d
MD
667
668 /*
669 * ALL-ALLOCATED special case
670 */
671 if (scan->bm_bitmap == 0) {
672 scan->bm_bighint = 0;
673 return(HAMMER_ALIST_BLOCK_NONE);
674 }
675
676 radix /= HAMMER_ALIST_META_RADIX;
c60bb2c5 677 bl = live->config;
8750964d
MD
678
679 /*
680 * Radix now represents each bitmap entry for this meta node. If
681 * the number of blocks being allocated can be fully represented,
682 * we allocate directly out of this meta node.
683 *
684 * Meta node bitmaps use 2 bits per block.
685 *
61aeeb33 686 * 00 ALL-ALLOCATED - UNINITIALIZED
8750964d 687 * 01 PARTIALLY-FREE/PARTIALLY-ALLOCATED
61aeeb33
MD
688 * 10 ALL-ALLOCATED - INITIALIZED
689 * 11 ALL-FREE - UNINITIALIZED
8750964d
MD
690 */
691 if (count >= radix) {
692 int n = count / radix * 2; /* number of bits */
9775c955 693 int nd2 = n / 2;
8750964d
MD
694 int j;
695
696 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - n);
9775c955 697 saveblk = blk;
61aeeb33 698 for (j = 0; j < (int)HAMMER_ALIST_META_RADIX; j += nd2) {
9775c955 699 if ((scan->bm_bitmap & mask) == mask && blk >= atblk) {
61aeeb33
MD
700 /*
701 * NOTE: Marked all-allocate/uninitialized
702 * rather then all-allocated/initialized.
703 * See the warning at the top of the file.
704 */
8750964d 705 scan->bm_bitmap &= ~mask;
9775c955 706 return(blk);
8750964d
MD
707 }
708 mask <<= n;
9775c955 709 blk += radix * nd2;
8750964d 710 }
9775c955 711 if (scan->bm_bighint >= count && saveblk >= atblk)
8750964d
MD
712 scan->bm_bighint = count >> 1;
713 return(HAMMER_ALIST_BLOCK_NONE);
714 }
715
c60bb2c5
MD
716 /*
717 * If the count is too big we couldn't allocate anything from a
718 * recursion even if the sub-tree were entirely free.
719 */
9775c955 720 saveblk = blk;
c60bb2c5
MD
721 if (count > radix)
722 goto failed;
723
8750964d
MD
724 /*
725 * If not we have to recurse.
726 */
727 mask = 0x00000003;
728 pmask = 0x00000001;
8750964d 729
c60bb2c5
MD
730 if (skip == 1) {
731 /*
732 * If skip is 1 we are a meta leaf node, which means there
733 * is another allocation layer we have to dive down into.
734 */
61aeeb33 735 for (i = 0; i < (int)HAMMER_ALIST_META_RADIX; ++i) {
8750964d 736 /*
c60bb2c5 737 * If the next layer is completely free then call
61aeeb33 738 * its init function to initialize it.
8750964d 739 */
9775c955
MD
740 if ((scan->bm_bitmap & mask) == mask &&
741 blk + radix > atblk) {
61aeeb33
MD
742 if (bl->bl_radix_init(live->info, blk, radix, HAMMER_ASTATE_FREE) == 0) {
743 /*
744 * NOTE: Marked all-allocate/uninit-
745 * ialized rather then all-allocated/
746 * initialized. See the warning at
747 * the top of the file.
748 */
8750964d
MD
749 scan->bm_bitmap &= ~mask;
750 scan->bm_bitmap |= pmask;
751 }
8750964d 752 }
c60bb2c5 753
8750964d 754 /*
c60bb2c5
MD
755 * If there may be some free blocks try to allocate
756 * out of the layer. If the layer indicates that
757 * it is completely full then clear both bits to
758 * propogate the condition.
8750964d 759 */
9775c955
MD
760 if ((scan->bm_bitmap & mask) == pmask &&
761 blk + radix > atblk) {
c60bb2c5
MD
762 int32_t r;
763 int32_t full;
764
765 r = bl->bl_radix_alloc_fwd(live->info, blk,
9775c955
MD
766 radix, count, atblk,
767 &full);
c60bb2c5 768 if (r != HAMMER_ALIST_BLOCK_NONE) {
61aeeb33 769 if (full)
c60bb2c5
MD
770 scan->bm_bitmap &= ~mask;
771 return(r);
772 }
773 }
774 blk += radix;
775 mask <<= 2;
776 pmask <<= 2;
777 }
778 } else {
779 /*
780 * Otherwise there are sub-records in the current a-list
781 * layer. We can also peek into the sub-layers to get
782 * more accurate size hints.
783 */
784 next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
7f7c1f84 785 for (i = 1; i < skip; i += next_skip) {
c60bb2c5
MD
786 if (scan[i].bm_bighint == (int32_t)-1) {
787 /*
788 * Terminator
789 */
790 break;
791 }
9775c955
MD
792
793 /*
794 * Initialize bitmap if allocating from the all-free
795 * case.
796 */
c60bb2c5
MD
797 if ((scan->bm_bitmap & mask) == mask) {
798 scan[i].bm_bitmap = (u_int32_t)-1;
799 scan[i].bm_bighint = radix;
800 }
801
9775c955
MD
802 if (count <= scan[i].bm_bighint &&
803 blk + radix > atblk) {
c60bb2c5
MD
804 /*
805 * count fits in object, recurse into the
806 * next layer. If the next_skip is 1 it
807 * will be either a normal leaf or a meta
808 * leaf.
809 */
810 int32_t r;
811
812 if (next_skip == 1 && bl->bl_terminal) {
813 r = hammer_alst_leaf_alloc_fwd(
9775c955 814 &scan[i], blk, count, atblk);
c60bb2c5
MD
815 } else {
816 r = hammer_alst_meta_alloc_fwd(
817 live, &scan[i],
818 blk, count,
9775c955 819 radix, next_skip, atblk);
c60bb2c5
MD
820 }
821 if (r != HAMMER_ALIST_BLOCK_NONE) {
822 if (scan[i].bm_bitmap == 0) {
823 scan->bm_bitmap &= ~mask;
824 } else {
825 scan->bm_bitmap &= ~mask;
826 scan->bm_bitmap |= pmask;
827 }
828 return(r);
829 }
830 }
831 blk += radix;
832 mask <<= 2;
833 pmask <<= 2;
8750964d 834 }
8750964d
MD
835 }
836
c60bb2c5 837failed:
8750964d
MD
838 /*
839 * We couldn't allocate count in this subtree, update bighint.
840 */
9775c955 841 if (scan->bm_bighint >= count && saveblk >= atblk)
8750964d
MD
842 scan->bm_bighint = count >> 1;
843 return(HAMMER_ALIST_BLOCK_NONE);
844}
845
846/*
847 * This version allocates blocks in the reverse direction.
848 */
849static int32_t
c60bb2c5
MD
850hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
851 int32_t blk, int32_t count,
9775c955 852 int32_t radix, int skip, int32_t atblk
8750964d 853) {
c60bb2c5 854 hammer_alist_config_t bl;
8750964d
MD
855 int i;
856 int j;
857 u_int32_t mask;
858 u_int32_t pmask;
9775c955 859 int32_t saveblk;
c60bb2c5 860 int next_skip;
8750964d
MD
861
862 /*
863 * ALL-ALLOCATED special case
864 */
865 if (scan->bm_bitmap == 0) {
866 scan->bm_bighint = 0;
867 return(HAMMER_ALIST_BLOCK_NONE);
868 }
869
870 radix /= HAMMER_ALIST_META_RADIX;
c60bb2c5 871 bl = live->config;
8750964d
MD
872
873 /*
874 * Radix now represents each bitmap entry for this meta node. If
875 * the number of blocks being allocated can be fully represented,
876 * we allocate directly out of this meta node.
877 *
878 * Meta node bitmaps use 2 bits per block.
879 *
61aeeb33 880 * 00 ALL-ALLOCATED (uninitialized)
8750964d 881 * 01 PARTIALLY-FREE/PARTIALLY-ALLOCATED
61aeeb33 882 * 10 ALL-ALLOCATED (initialized)
8750964d
MD
883 * 11 ALL-FREE
884 */
885 if (count >= radix) {
886 int n = count / radix * 2; /* number of bits */
9775c955 887 int nd2 = n / 2; /* number of radi */
8750964d
MD
888
889 /*
890 * Initial mask if e.g. n == 2: 1100....0000
891 */
892 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - n) <<
893 (HAMMER_ALIST_BMAP_RADIX - n);
9775c955
MD
894 blk += (HAMMER_ALIST_META_RADIX - nd2) * radix;
895 saveblk = blk;
896 for (j = HAMMER_ALIST_META_RADIX - nd2; j >= 0; j -= nd2) {
897 if ((scan->bm_bitmap & mask) == mask && blk <= atblk) {
8750964d 898 scan->bm_bitmap &= ~mask;
9775c955 899 return(blk);
8750964d
MD
900 }
901 mask >>= n;
9775c955 902 blk -= nd2 * radix;
8750964d 903 }
9775c955 904 if (scan->bm_bighint >= count && saveblk <= atblk)
8750964d
MD
905 scan->bm_bighint = count >> 1;
906 return(HAMMER_ALIST_BLOCK_NONE);
907 }
908
909 /*
c60bb2c5
MD
910 * If the count is too big we couldn't allocate anything from a
911 * recursion even if the sub-tree were entirely free.
8750964d 912 */
9775c955
MD
913 if (count > radix) {
914 saveblk = atblk; /* make it work for the conditional */
915 goto failed; /* at the failed label */
916 }
8750964d 917
c60bb2c5 918 if (skip == 1) {
8750964d 919 /*
c60bb2c5
MD
920 * We need the recurse but we are at a meta node leaf, which
921 * means there is another layer under us.
8750964d 922 */
c60bb2c5
MD
923 mask = 0xC0000000;
924 pmask = 0x40000000;
925 blk += radix * HAMMER_ALIST_META_RADIX - radix;
9775c955 926 saveblk = blk;
8750964d 927
61aeeb33 928 for (i = 0; i < (int)HAMMER_ALIST_META_RADIX; ++i) {
8750964d 929 /*
c60bb2c5 930 * If the next layer is completely free then call
61aeeb33
MD
931 * its init function to initialize it. The init
932 * function is responsible for the initial freeing.
8750964d 933 */
9775c955 934 if ((scan->bm_bitmap & mask) == mask && blk <= atblk) {
61aeeb33 935 if (bl->bl_radix_init(live->info, blk, radix, HAMMER_ASTATE_FREE) == 0) {
8750964d
MD
936 scan->bm_bitmap &= ~mask;
937 scan->bm_bitmap |= pmask;
938 }
8750964d 939 }
c60bb2c5 940
8750964d 941 /*
c60bb2c5
MD
942 * If there may be some free blocks try to allocate
943 * out of the layer. If the layer indicates that
944 * it is completely full then clear both bits to
945 * propogate the condition.
8750964d 946 */
9775c955 947 if ((scan->bm_bitmap & mask) == pmask && blk <= atblk) {
c60bb2c5
MD
948 int32_t r;
949 int32_t full;
950
951 r = bl->bl_radix_alloc_rev(live->info, blk,
9775c955
MD
952 radix, count,
953 atblk, &full);
c60bb2c5 954 if (r != HAMMER_ALIST_BLOCK_NONE) {
61aeeb33 955 if (full)
c60bb2c5
MD
956 scan->bm_bitmap &= ~mask;
957 return(r);
958 }
959 }
960 mask >>= 2;
961 pmask >>= 2;
962 blk -= radix;
963 }
964 } else {
965 /*
966 * Since we are going in the reverse direction we need an
967 * extra loop to determine if there is a terminator, then
968 * run backwards.
969 *
970 * This is a little weird but we do not want to overflow the
971 * mask/pmask in the loop.
972 */
973 next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
974 j = 0;
9775c955
MD
975 for (i = 1; i < skip; i += next_skip) {
976 if (scan[i].bm_bighint == (int32_t)-1) {
977 KKASSERT(j != 0);
c60bb2c5 978 break;
9775c955 979 }
c60bb2c5
MD
980 blk += radix;
981 j += 2;
8750964d
MD
982 }
983 blk -= radix;
c60bb2c5
MD
984 j -= 2;
985 mask = 0x00000003 << j;
986 pmask = 0x00000001 << j;
8750964d 987 i -= next_skip;
9775c955 988 saveblk = blk;
c60bb2c5
MD
989
990 while (i >= 1) {
991 /*
992 * Initialize the bitmap in the child if allocating
993 * from the all-free case.
994 */
995 if ((scan->bm_bitmap & mask) == mask) {
996 scan[i].bm_bitmap = (u_int32_t)-1;
997 scan[i].bm_bighint = radix;
998 }
999
1000 /*
1001 * Handle various count cases. Bighint may be too
1002 * large but is never too small.
1003 */
9775c955 1004 if (count <= scan[i].bm_bighint && blk <= atblk) {
c60bb2c5
MD
1005 /*
1006 * count fits in object
1007 */
1008 int32_t r;
1009 if (next_skip == 1 && bl->bl_terminal) {
1010 r = hammer_alst_leaf_alloc_rev(
9775c955 1011 &scan[i], blk, count, atblk);
c60bb2c5
MD
1012 } else {
1013 r = hammer_alst_meta_alloc_rev(
1014 live, &scan[i],
1015 blk, count,
9775c955 1016 radix, next_skip, atblk);
c60bb2c5
MD
1017 }
1018 if (r != HAMMER_ALIST_BLOCK_NONE) {
1019 if (scan[i].bm_bitmap == 0) {
1020 scan->bm_bitmap &= ~mask;
1021 } else {
1022 scan->bm_bitmap &= ~mask;
1023 scan->bm_bitmap |= pmask;
1024 }
1025 return(r);
1026 }
c60bb2c5
MD
1027 }
1028 blk -= radix;
1029 mask >>= 2;
1030 pmask >>= 2;
1031 i -= next_skip;
1032 }
8750964d
MD
1033 }
1034
c60bb2c5 1035failed:
8750964d
MD
1036 /*
1037 * We couldn't allocate count in this subtree, update bighint.
c60bb2c5
MD
1038 * Since we are restricted to powers of 2, the next highest count
1039 * we might be able to allocate is (count >> 1).
8750964d 1040 */
9775c955 1041 if (scan->bm_bighint >= count && saveblk <= atblk)
8750964d
MD
1042 scan->bm_bighint = count >> 1;
1043 return(HAMMER_ALIST_BLOCK_NONE);
1044}
1045
1046/*
1047 * BLST_LEAF_FREE()
1048 *
1049 * Free allocated blocks from leaf bitmap. The allocation code is
1050 * restricted to powers of 2, the freeing code is not.
1051 */
1052static void
c60bb2c5 1053hammer_alst_leaf_free(hammer_almeta_t scan, int32_t blk, int count) {
8750964d
MD
1054 /*
1055 * free some data in this bitmap
1056 *
1057 * e.g.
1058 * 0000111111111110000
1059 * \_________/\__/
1060 * v n
1061 */
1062 int n = blk & (HAMMER_ALIST_BMAP_RADIX - 1);
1063 u_int32_t mask;
1064
1065 mask = ((u_int32_t)-1 << n) &
1066 ((u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - count - n));
1067
1068 if (scan->bm_bitmap & mask)
1069 panic("hammer_alst_radix_free: freeing free block");
1070 scan->bm_bitmap |= mask;
1071
1072 /*
1073 * We could probably do a better job here. We are required to make
1074 * bighint at least as large as the biggest contiguous block of
1075 * data. If we just shoehorn it, a little extra overhead will
1076 * be incured on the next allocation (but only that one typically).
1077 */
1078 scan->bm_bighint = HAMMER_ALIST_BMAP_RADIX;
1079}
1080
1081/*
1082 * BLST_META_FREE()
1083 *
1084 * Free allocated blocks from radix tree meta info.
1085 *
1086 * This support routine frees a range of blocks from the bitmap.
1087 * The range must be entirely enclosed by this radix node. If a
1088 * meta node, we break the range down recursively to free blocks
1089 * in subnodes (which means that this code can free an arbitrary
1090 * range whereas the allocation code cannot allocate an arbitrary
1091 * range).
1092 */
1093
1094static void
c60bb2c5
MD
1095hammer_alst_meta_free(hammer_alist_t live, hammer_almeta_t scan,
1096 int32_t freeBlk, int32_t count,
1097 int32_t radix, int skip, int32_t blk
8750964d 1098) {
c60bb2c5
MD
1099 hammer_alist_config_t bl;
1100 int next_skip;
8750964d
MD
1101 u_int32_t mask;
1102 u_int32_t pmask;
1103 int i;
1104
1105 /*
1106 * Break the free down into its components. Because it is so easy
1107 * to implement, frees are not limited to power-of-2 sizes.
1108 *
1109 * Each block in a meta-node bitmap takes two bits.
1110 */
1111 radix /= HAMMER_ALIST_META_RADIX;
c60bb2c5 1112 bl = live->config;
8750964d
MD
1113
1114 i = (freeBlk - blk) / radix;
1115 blk += i * radix;
1116 mask = 0x00000003 << (i * 2);
1117 pmask = 0x00000001 << (i * 2);
1118
c60bb2c5
MD
1119 if (skip == 1) {
1120 /*
1121 * Our meta node is a leaf node, which means it must recurse
1122 * into another allocator.
1123 */
61aeeb33
MD
1124 while (i < (int)HAMMER_ALIST_META_RADIX &&
1125 blk < freeBlk + count) {
c60bb2c5 1126 int32_t v;
8750964d 1127
c60bb2c5
MD
1128 v = blk + radix - freeBlk;
1129 if (v > count)
1130 v = count;
8750964d 1131
c60bb2c5
MD
1132 if (scan->bm_bighint == (int32_t)-1)
1133 panic("hammer_alst_meta_free: freeing unexpected range");
61aeeb33 1134 KKASSERT((scan->bm_bitmap & mask) != mask);
8750964d 1135
c60bb2c5
MD
1136 if (freeBlk == blk && count >= radix) {
1137 /*
61aeeb33
MD
1138 * Freeing an entire zone. Only recurse if
1139 * the zone was initialized. A 00 state means
1140 * that the zone is marked all-allocated,
1141 * but was never initialized.
1142 *
1143 * Then set the zone to the all-free state (11).
c60bb2c5 1144 */
9775c955
MD
1145 int32_t empty;
1146
61aeeb33 1147 if (scan->bm_bitmap & mask) {
9775c955
MD
1148 bl->bl_radix_free(live->info, blk, radix,
1149 freeBlk - blk, v, &empty);
61aeeb33 1150 KKASSERT(empty);
9775c955
MD
1151 bl->bl_radix_destroy(live->info, blk, radix);
1152 }
c60bb2c5
MD
1153 scan->bm_bitmap |= mask;
1154 scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
1155 /* XXX bighint not being set properly */
1156 } else {
1157 /*
61aeeb33
MD
1158 * Recursion case, partial free. If 00 the
1159 * zone is marked all allocated but has never
1160 * been initialized, so we init it.
c60bb2c5
MD
1161 */
1162 int32_t empty;
1163
9775c955 1164 if ((scan->bm_bitmap & mask) == 0)
61aeeb33 1165 bl->bl_radix_init(live->info, blk, radix, HAMMER_ASTATE_ALLOC);
9775c955
MD
1166 bl->bl_radix_free(live->info, blk, radix,
1167 freeBlk - blk, v, &empty);
c60bb2c5
MD
1168 if (empty) {
1169 scan->bm_bitmap |= mask;
1170 scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
9775c955 1171 bl->bl_radix_destroy(live->info, blk, radix);
c60bb2c5
MD
1172 /* XXX bighint not being set properly */
1173 } else {
1174 scan->bm_bitmap |= pmask;
1175 if (scan->bm_bighint < radix / 2)
1176 scan->bm_bighint = radix / 2;
1177 /* XXX bighint not being set properly */
1178 }
1179 }
1180 ++i;
1181 mask <<= 2;
1182 pmask <<= 2;
1183 count -= v;
1184 freeBlk += v;
1185 blk += radix;
1186 }
1187 } else {
1188 next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
1189 i = 1 + i * next_skip;
8750964d 1190
c60bb2c5
MD
1191 while (i <= skip && blk < freeBlk + count) {
1192 int32_t v;
1193
7f7c1f84
MD
1194 KKASSERT(mask != 0);
1195
c60bb2c5
MD
1196 v = blk + radix - freeBlk;
1197 if (v > count)
1198 v = count;
1199
1200 if (scan->bm_bighint == (int32_t)-1)
1201 panic("hammer_alst_meta_free: freeing unexpected range");
1202
1203 if (freeBlk == blk && count >= radix) {
1204 /*
1205 * All-free case, no need to update sub-tree
1206 */
8750964d 1207 scan->bm_bitmap |= mask;
c60bb2c5
MD
1208 scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
1209 /* XXX bighint not being set properly */
1210 } else {
1211 /*
1212 * Recursion case
1213 */
1214 if (next_skip == 1 && bl->bl_terminal) {
1215 hammer_alst_leaf_free(&scan[i], freeBlk, v);
1216 } else {
1217 hammer_alst_meta_free(live, &scan[i],
1218 freeBlk, v,
1219 radix, next_skip,
1220 blk);
1221 }
1222 if (scan[i].bm_bitmap == (u_int32_t)-1)
1223 scan->bm_bitmap |= mask;
1224 else
1225 scan->bm_bitmap |= pmask;
1226 if (scan->bm_bighint < scan[i].bm_bighint)
1227 scan->bm_bighint = scan[i].bm_bighint;
1228 }
1229 mask <<= 2;
1230 pmask <<= 2;
1231 count -= v;
1232 freeBlk += v;
1233 blk += radix;
1234 i += next_skip;
8750964d 1235 }
8750964d
MD
1236 }
1237}
1238
1239/*
c60bb2c5 1240 * hammer_alst_radix_init()
8750964d
MD
1241 *
1242 * Initialize our meta structures and bitmaps and calculate the exact
c60bb2c5
MD
1243 * number of meta-nodes required to manage 'count' blocks.
1244 *
1245 * The required space may be truncated due to early termination records.
8750964d 1246 */
8750964d 1247static int32_t
c60bb2c5 1248hammer_alst_radix_init(hammer_almeta_t scan, int32_t radix,
8750964d
MD
1249 int skip, int32_t count)
1250{
1251 int i;
1252 int next_skip;
c60bb2c5 1253 int32_t memindex = 1;
8750964d
MD
1254 u_int32_t mask;
1255 u_int32_t pmask;
1256
1257 /*
61aeeb33
MD
1258 * Basic initialization of the almeta for meta or leaf nodes. This
1259 * marks the element as all-allocated.
8750964d 1260 */
c60bb2c5
MD
1261 if (scan) {
1262 scan->bm_bighint = 0;
1263 scan->bm_bitmap = 0;
8750964d
MD
1264 }
1265
c60bb2c5
MD
1266 /*
1267 * We are at a leaf, we only eat one meta element.
1268 */
1269 if (skip == 1)
1270 return(memindex);
1271
8750964d
MD
1272 /*
1273 * Meta node. If allocating the entire object we can special
1274 * case it. However, we need to figure out how much memory
1275 * is required to manage 'count' blocks, so we continue on anyway.
1276 */
8750964d 1277 radix /= HAMMER_ALIST_META_RADIX;
c60bb2c5 1278 next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
8750964d
MD
1279 mask = 0x00000003;
1280 pmask = 0x00000001;
1281
7f7c1f84 1282 for (i = 1; i < skip; i += next_skip) {
c60bb2c5
MD
1283 /*
1284 * We eat up to this record
1285 */
1286 memindex = i;
1287
7f7c1f84
MD
1288 KKASSERT(mask != 0);
1289
8750964d
MD
1290 if (count >= radix) {
1291 /*
1292 * Allocate the entire object
1293 */
c60bb2c5 1294 memindex += hammer_alst_radix_init(
8750964d
MD
1295 ((scan) ? &scan[i] : NULL),
1296 radix,
c60bb2c5 1297 next_skip,
8750964d
MD
1298 radix
1299 );
1300 count -= radix;
1301 /* already marked as wholely allocated */
1302 } else if (count > 0) {
1303 /*
1304 * Allocate a partial object
1305 */
c60bb2c5 1306 memindex += hammer_alst_radix_init(
8750964d
MD
1307 ((scan) ? &scan[i] : NULL),
1308 radix,
c60bb2c5 1309 next_skip,
8750964d
MD
1310 count
1311 );
1312 count = 0;
1313
1314 /*
1315 * Mark as partially allocated
1316 */
1317 if (scan)
1318 scan->bm_bitmap |= pmask;
1319 } else {
1320 /*
c60bb2c5
MD
1321 * Add terminator and break out. The terminal
1322 * eats the meta node at scan[i].
8750964d 1323 */
c60bb2c5 1324 ++memindex;
8750964d
MD
1325 if (scan)
1326 scan[i].bm_bighint = (int32_t)-1;
1327 /* already marked as wholely allocated */
1328 break;
1329 }
1330 mask <<= 2;
1331 pmask <<= 2;
1332 }
8750964d
MD
1333 return(memindex);
1334}
1335
1336#ifdef ALIST_DEBUG
1337
1338static void
c60bb2c5
MD
1339hammer_alst_radix_print(hammer_alist_t live, hammer_almeta_t scan,
1340 int32_t blk, int32_t radix, int skip, int tab)
8750964d
MD
1341{
1342 int i;
1343 int next_skip;
1344 int lastState = 0;
1345 u_int32_t mask;
1346
c60bb2c5 1347 if (skip == 1 && live->config->bl_terminal) {
8750964d
MD
1348 kprintf(
1349 "%*.*s(%04x,%d): bitmap %08x big=%d\n",
1350 tab, tab, "",
1351 blk, radix,
1352 scan->bm_bitmap,
1353 scan->bm_bighint
1354 );
1355 return;
1356 }
1357
1358 if (scan->bm_bitmap == 0) {
1359 kprintf(
1360 "%*.*s(%04x,%d) ALL ALLOCATED\n",
1361 tab, tab, "",
1362 blk,
1363 radix
1364 );
1365 return;
1366 }
1367 if (scan->bm_bitmap == (u_int32_t)-1) {
1368 kprintf(
1369 "%*.*s(%04x,%d) ALL FREE\n",
1370 tab, tab, "",
1371 blk,
1372 radix
1373 );
1374 return;
1375 }
1376
1377 kprintf(
c60bb2c5 1378 "%*.*s(%04x,%d): %s (%d) bitmap=%08x big=%d {\n",
8750964d
MD
1379 tab, tab, "",
1380 blk, radix,
c60bb2c5 1381 (skip == 1 ? "LAYER" : "subtree"),
8750964d
MD
1382 radix,
1383 scan->bm_bitmap,
1384 scan->bm_bighint
1385 );
1386
1387 radix /= HAMMER_ALIST_META_RADIX;
8750964d
MD
1388 tab += 4;
1389 mask = 0x00000003;
1390
c60bb2c5
MD
1391 if (skip == 1) {
1392 for (i = 0; i < HAMMER_ALIST_META_RADIX; ++i) {
1393 if ((scan->bm_bitmap & mask) == mask) {
1394 kprintf(
1395 "%*.*s(%04x,%d): ALL FREE\n",
1396 tab, tab, "",
1397 blk, radix
1398 );
1399 } else if ((scan->bm_bitmap & mask) == 0) {
1400 kprintf(
1401 "%*.*s(%04x,%d): ALL ALLOCATED\n",
1402 tab, tab, "",
1403 blk, radix
1404 );
1405 } else {
1406 live->config->bl_radix_print(
1407 live->info, blk, radix, tab);
1408 }
1409 blk += radix;
1410 mask <<= 2;
8750964d 1411 }
c60bb2c5 1412 } else {
7f7c1f84 1413 next_skip = ((u_int)(skip - 1) / HAMMER_ALIST_META_RADIX);
c60bb2c5 1414
7f7c1f84
MD
1415 for (i = 1; i < skip; i += next_skip) {
1416 KKASSERT(mask != 0);
c60bb2c5
MD
1417 if (scan[i].bm_bighint == (int32_t)-1) {
1418 kprintf(
1419 "%*.*s(%04x,%d): Terminator\n",
1420 tab, tab, "",
1421 blk, radix
1422 );
1423 lastState = 0;
1424 break;
1425 }
1426 if ((scan->bm_bitmap & mask) == mask) {
1427 kprintf(
1428 "%*.*s(%04x,%d): ALL FREE\n",
1429 tab, tab, "",
1430 blk, radix
1431 );
1432 } else if ((scan->bm_bitmap & mask) == 0) {
1433 kprintf(
1434 "%*.*s(%04x,%d): ALL ALLOCATED\n",
1435 tab, tab, "",
1436 blk, radix
1437 );
1438 } else {
1439 hammer_alst_radix_print(
1440 live,
1441 &scan[i],
1442 blk,
1443 radix,
7f7c1f84 1444 next_skip,
c60bb2c5
MD
1445 tab
1446 );
1447 }
1448 blk += radix;
1449 mask <<= 2;
8750964d 1450 }
8750964d
MD
1451 }
1452 tab -= 4;
1453
1454 kprintf(
1455 "%*.*s}\n",
1456 tab, tab, ""
1457 );
1458}
1459
1460#endif
1461
1462#ifdef ALIST_DEBUG
1463
c60bb2c5
MD
1464static struct hammer_alist_live **layers; /* initialized by main */
1465static int32_t layer_radix = -1;
1466
61aeeb33
MD
1467/*
1468 * Initialize a zone.
1469 *
1470 * If allocating is non-zero this init is being called when transitioning out
1471 * of an all-free state. Allocate the zone and mark the whole mess as being
1472 * free so the caller can then allocate out of this zone.
1473 *
1474 * If freeing this init is being called when transitioning out of an
1475 * initial all-allocated (00) state. Allocate the zone but leave the whole
1476 * mess left all-allocated. The caller will then free the appropriate range.
1477 */
c60bb2c5
MD
1478static
1479int
61aeeb33
MD
1480debug_radix_init(void *info, int32_t blk, int32_t radix,
1481 enum hammer_alloc_state state)
c60bb2c5
MD
1482{
1483 hammer_alist_t layer;
1484 int layer_no = blk / layer_radix;
1485
61aeeb33
MD
1486 printf("lower layer: init (%04x,%d) layer_radix=%d\n",
1487 blk, radix, layer_radix);
1488 KKASSERT(layer_radix == radix);
c60bb2c5 1489 KKASSERT(layers[layer_no] == NULL);
61aeeb33 1490 layer = layers[layer_no] = hammer_alist_create(radix, 1, NULL, state);
9775c955
MD
1491 return(0);
1492}
1493
61aeeb33
MD
1494/*
1495 * This is called when a zone becomes entirely free, typically after a
1496 * call to debug_radix_free() has indicated that the entire zone is now
1497 * free.
1498 */
9775c955
MD
1499static
1500int
1501debug_radix_destroy(void *info, int32_t blk, int32_t radix)
1502{
1503 hammer_alist_t layer;
1504 int layer_no = blk / layer_radix;
1505
1506 printf("lower layer: destroy (%04x,%d)\n", blk, radix);
1507 layer = layers[layer_no];
1508 KKASSERT(layer != NULL);
1509 hammer_alist_destroy(layer, NULL);
1510 layers[layer_no] = NULL;
c60bb2c5
MD
1511 return(0);
1512}
1513
9775c955 1514
c60bb2c5
MD
1515static
1516int32_t
1517debug_radix_alloc_fwd(void *info, int32_t blk, int32_t radix,
9775c955 1518 int32_t count, int32_t atblk, int32_t *fullp)
c60bb2c5
MD
1519{
1520 hammer_alist_t layer = layers[blk / layer_radix];
9775c955 1521 int32_t r;
c60bb2c5 1522
9775c955 1523 r = hammer_alist_alloc_fwd(layer, count, atblk - blk);
61aeeb33 1524 *fullp = hammer_alist_isfull(layer);
9775c955
MD
1525 if (r != HAMMER_ALIST_BLOCK_NONE)
1526 r += blk;
1527 return(r);
c60bb2c5
MD
1528}
1529
1530static
1531int32_t
1532debug_radix_alloc_rev(void *info, int32_t blk, int32_t radix,
9775c955 1533 int32_t count, int32_t atblk, int32_t *fullp)
c60bb2c5
MD
1534{
1535 hammer_alist_t layer = layers[blk / layer_radix];
9775c955 1536 int32_t r;
c60bb2c5 1537
9775c955 1538 r = hammer_alist_alloc_rev(layer, count, atblk - blk);
61aeeb33 1539 *fullp = hammer_alist_isfull(layer);
9775c955
MD
1540 if (r != HAMMER_ALIST_BLOCK_NONE)
1541 r += blk;
1542 return(r);
c60bb2c5
MD
1543}
1544
1545static
1546void
9775c955
MD
1547debug_radix_free(void *info, int32_t blk, int32_t radix,
1548 int32_t base_blk, int32_t count, int32_t *emptyp)
c60bb2c5
MD
1549{
1550 int layer_no = blk / layer_radix;
1551 hammer_alist_t layer = layers[layer_no];
1552
61aeeb33 1553 KKASSERT(layer);
9775c955 1554 hammer_alist_free(layer, base_blk, count);
61aeeb33 1555 *emptyp = hammer_alist_isempty(layer);
c60bb2c5
MD
1556}
1557
1558static
1559void
1560debug_radix_print(void *info, int32_t blk, int32_t radix, int tab)
1561{
1562 hammer_alist_t layer = layers[blk / layer_radix];
1563
1564 hammer_alist_print(layer, tab);
1565}
1566
8750964d
MD
1567int
1568main(int ac, char **av)
1569{
c60bb2c5 1570 int32_t size = -1;
8750964d 1571 int i;
c60bb2c5
MD
1572 hammer_alist_t live;
1573 hammer_almeta_t meta = NULL;
8750964d
MD
1574
1575 for (i = 1; i < ac; ++i) {
1576 const char *ptr = av[i];
1577 if (*ptr != '-') {
c60bb2c5
MD
1578 if (size == -1)
1579 size = strtol(ptr, NULL, 0);
1580 else if (layer_radix == -1)
1581 layer_radix = strtol(ptr, NULL, 0);
1582 else
1583 ;
8750964d
MD
1584 continue;
1585 }
1586 ptr += 2;
1587 fprintf(stderr, "Bad option: %s\n", ptr - 2);
1588 exit(1);
1589 }
c60bb2c5
MD
1590 if (size == -1)
1591 size = 1024;
1592 if (layer_radix == -1)
1593 layer_radix = 1; /* no second storage layer */
1594 if ((size ^ (size - 1)) != (size << 1) - 1) {
1595 fprintf(stderr, "size must be a power of 2\n");
1596 exit(1);
1597 }
1598 if ((layer_radix ^ (layer_radix - 1)) != (layer_radix << 1) - 1) {
1599 fprintf(stderr, "the second layer radix must be a power of 2\n");
1600 exit(1);
1601 }
1602
61aeeb33
MD
1603 live = hammer_alist_create(size, layer_radix, NULL,
1604 HAMMER_ASTATE_ALLOC);
c60bb2c5
MD
1605 layers = calloc(size, sizeof(hammer_alist_t));
1606
1607 printf("A-LIST TEST %d blocks, first-layer radix %d, "
1608 "second-layer radix %d\n",
1609 size, live->config->bl_radix / layer_radix, layer_radix);
1610
1611 live->config->bl_radix_init = debug_radix_init;
9775c955 1612 live->config->bl_radix_destroy = debug_radix_destroy;
c60bb2c5
MD
1613 live->config->bl_radix_alloc_fwd = debug_radix_alloc_fwd;
1614 live->config->bl_radix_alloc_rev = debug_radix_alloc_rev;
1615 live->config->bl_radix_free = debug_radix_free;
1616 live->config->bl_radix_print = debug_radix_print;
1617
1618 hammer_alist_free(live, 0, size);
8750964d
MD
1619
1620 for (;;) {
1621 char buf[1024];
1622 int32_t da = 0;
1623 int32_t count = 0;
9775c955 1624 int32_t atblk;
8750964d
MD
1625 int32_t blk;
1626
c60bb2c5
MD
1627 kprintf("%d/%d> ",
1628 live->meta->bm_alist_freeblks, size);
8750964d
MD
1629 fflush(stdout);
1630 if (fgets(buf, sizeof(buf), stdin) == NULL)
1631 break;
1632 switch(buf[0]) {
1633 case 'p':
c60bb2c5 1634 hammer_alist_print(live, 0);
8750964d
MD
1635 break;
1636 case 'a':
7f7c1f84 1637 atblk = 0;
9775c955
MD
1638 if (sscanf(buf + 1, "%d %d", &count, &atblk) >= 1) {
1639 blk = hammer_alist_alloc_fwd(live, count, atblk);
8750964d
MD
1640 kprintf(" R=%04x\n", blk);
1641 } else {
1642 kprintf("?\n");
1643 }
1644 break;
1645 case 'r':
9775c955
MD
1646 atblk = HAMMER_ALIST_BLOCK_MAX;
1647 if (sscanf(buf + 1, "%d %d", &count, &atblk) >= 1) {
1648 blk = hammer_alist_alloc_rev(live, count, atblk);
8750964d
MD
1649 kprintf(" R=%04x\n", blk);
1650 } else {
1651 kprintf("?\n");
1652 }
1653 break;
1654 case 'f':
1655 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) {
c60bb2c5 1656 hammer_alist_free(live, da, count);
61aeeb33
MD
1657 if (hammer_alist_isempty(live))
1658 kprintf("a-list is now 100%% empty\n");
8750964d
MD
1659 } else {
1660 kprintf("?\n");
1661 }
1662 break;
1663 case '?':
1664 case 'h':
1665 puts(
1666 "p -print\n"
1667 "a %d -allocate\n"
1668 "r %d -allocate reverse\n"
1669 "f %x %d -free\n"
1670 "h/? -help"
1671 );
1672 break;
1673 default:
1674 kprintf("?\n");
1675 break;
1676 }
1677 }
1678 return(0);
1679}
1680
1681void
1682panic(const char *ctl, ...)
1683{
1684 __va_list va;
1685
1686 __va_start(va, ctl);
1687 vfprintf(stderr, ctl, va);
1688 fprintf(stderr, "\n");
1689 __va_end(va);
1690 exit(1);
1691}
1692
1693#endif
1694