?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
acxcontrol(8) is gone.
[dragonfly.git] / sys / vfs / hammer / hammer_alist.c
bloba865432b611c736955fd220b135582b060359102
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.11 2008/01/24 02:14:45 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 * The radix tree supports allocator layering. By supplying a base_radix > 1
64 * the allocator will issue callbacks to recurse into lower layers once
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.
74 *
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
91 #include "hammer_alist.h"
92 #include "hammer_disk.h"
93
94 #else
95
96 #ifndef ALIST_NO_DEBUG
97 #define ALIST_DEBUG
98 #endif
99
100 #include <sys/types.h>
101 #include <sys/errno.h>
102 #include <stdio.h>
103 #include <assert.h>
104 #include <string.h>
105 #include <stdlib.h>
106 #include <stdarg.h>
107
108 #define kmalloc(a,b,c) malloc(a)
109 #define kfree(a,b) free(a)
110 #define kprintf printf
111 #define KKASSERT(exp) assert(exp)
112 struct malloc_type;
113
114 #include "hammer_alist.h"
115
116 void panic(const char *ctl, ...);
117
118 #endif
119
120 /*
121 * static support functions
122 */
123 static int32_t hammer_alst_leaf_alloc_fwd(hammer_almeta_t scan,
124 int32_t blk, int count, int32_t atblk);
125 static int32_t hammer_alst_meta_alloc_fwd(hammer_alist_t live,
126 hammer_almeta_t scan,
127 int32_t blk, int32_t count,
128 int32_t radix, int skip, int32_t atblk);
129 static int32_t hammer_alst_leaf_alloc_rev(hammer_almeta_t scan,
130 int32_t blk, int count, int32_t atblk);
131 static int32_t hammer_alst_meta_alloc_rev(hammer_alist_t live,
132 hammer_almeta_t scan,
133 int32_t blk, int32_t count,
134 int32_t radix, int skip, int32_t atblk);
135 static int32_t hammer_alst_find(hammer_alist_t live, hammer_almeta_t scan,
136 int32_t blk, int32_t radix,
137 int32_t skip, int32_t atblk, int flags);
138 static void hammer_alst_leaf_free(hammer_almeta_t scan, int32_t relblk,
139 int count);
140 static void hammer_alst_meta_free(hammer_alist_t live, hammer_almeta_t scan,
141 int32_t freeBlk, int32_t count,
142 int32_t radix, int skip, int32_t blk);
143 static int32_t hammer_alst_radix_init(hammer_almeta_t scan,
144 int32_t radix, int skip, int32_t count);
145 static void hammer_alst_radix_recover(hammer_alist_recover_t info,
146 hammer_almeta_t scan, int32_t blk,
147 int32_t radix, int skip, int32_t count,
148 int32_t a_beg, int32_t a_end);
149 #ifdef ALIST_DEBUG
150 static void hammer_alst_radix_print(hammer_alist_t live,
151 hammer_almeta_t scan, int32_t blk,
152 int32_t radix, int skip, int tab);
153 #endif
154
155 /*
156 * Initialize an a-list config structure for use. The config structure
157 * describes the basic structure of an a-list's topology and may be
158 * shared by any number of a-lists which have the same topology.
159 *
160 * blocks is the total number of blocks, that is the number of blocks
161 * handled at this layer multiplied by the base radix.
162 *
163 * When base_radix != 1 the A-list has only meta elements and does not have
164 * any leaves, in order to be able to track partial allocations.
165 */
166 void
167 hammer_alist_template(hammer_alist_config_t bl, int32_t blocks,
168 int32_t base_radix, int32_t maxmeta, int inverted)
169 {
170 int radix;
171 int skip;
172
173 /*
174 * Calculate radix and skip field used for scanning. The leaf nodes
175 * in our tree are either BMAP or META nodes depending on whether
176 * we chain to a lower level allocation layer or not.
177 */
178 if (base_radix == 1)
179 radix = HAMMER_ALIST_BMAP_RADIX;
180 else
181 radix = HAMMER_ALIST_META_RADIX;
182 skip = 1;
183
184 while (radix < blocks / base_radix) {
185 radix *= HAMMER_ALIST_META_RADIX;
186 skip = skip * HAMMER_ALIST_META_RADIX + 1;
187 }
188
189 /*
190 * Increase the radix based on the number of blocks a lower level
191 * allocator is able to handle at the 'base' of our allocator.
192 * If base_radix != 1 the caller will have to initialize the callback
193 * fields to implement the lower level allocator.
194 */
195 KKASSERT((int64_t)radix * (int64_t)base_radix < 0x80000000LL);
196 radix *= base_radix;
197
198 bzero(bl, sizeof(*bl));
199
200 bl->bl_blocks = blocks;
201 bl->bl_base_radix = base_radix;
202 bl->bl_radix = radix;
203 bl->bl_skip = skip;
204 bl->bl_rootblks = hammer_alst_radix_init(NULL, bl->bl_radix,
205 bl->bl_skip, blocks);
206 bl->bl_inverted = inverted;
207 ++bl->bl_rootblks; /* one more for freeblks header */
208 if (base_radix == 1)
209 bl->bl_terminal = 1;
210 KKASSERT(maxmeta == 0 || bl->bl_rootblks <= maxmeta);
211
212 #if defined(ALIST_DEBUG)
213 kprintf(
214 "PRIMARY ALIST LAYER manages %d blocks"
215 ", requiring %dK (%d bytes) of ram\n",
216 bl->bl_blocks / bl->bl_base_radix,
217 (bl->bl_rootblks * sizeof(struct hammer_almeta) + 1023) / 1024,
218 (bl->bl_rootblks * sizeof(struct hammer_almeta))
219 );
220 kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
221 #endif
222 }
223
224 /*
225 * Initialize a new A-list
226 */
227 void
228 hammer_alist_init(hammer_alist_t live, int32_t start, int32_t count,
229 enum hammer_alloc_state state)
230 {
231 hammer_alist_config_t bl = live->config;
232
233 /*
234 * Note: base_freeblks is a count, not a block number limit.
235 */
236 live->meta->bm_alist_freeblks = 0;
237 live->meta->bm_alist_base_freeblks = count;
238 hammer_alst_radix_init(live->meta + 1, bl->bl_radix,
239 bl->bl_skip, bl->bl_blocks);
240 if (count && state == HAMMER_ASTATE_FREE)
241 hammer_alist_free(live, start, count);
242 }
243
244 #if !defined(_KERNEL) && defined(ALIST_DEBUG)
245
246 /*
247 * hammer_alist_create() (userland only)
248 *
249 * create a alist capable of handling up to the specified number of
250 * blocks. blocks must be greater then 0
251 *
252 * The smallest alist consists of a single leaf node capable of
253 * managing HAMMER_ALIST_BMAP_RADIX blocks, or (if base_radix != 1)
254 * a single meta node capable of managing HAMMER_ALIST_META_RADIX
255 * blocks which recurses into other storage layers for a total
256 * handling capability of (HAMMER_ALIST_META_RADIX * base_radix) blocks.
257 *
258 * Larger a-list's increase their capability exponentially by
259 * HAMMER_ALIST_META_RADIX.
260 *
261 * The block count is the total number of blocks inclusive of any
262 * layering. blocks can be less then base_radix and will result in
263 * a radix tree with a single leaf node which then chains down.
264 */
265
266 hammer_alist_t
267 hammer_alist_create(int32_t blocks, int32_t base_radix,
268 struct malloc_type *mtype, enum hammer_alloc_state state)
269 {
270 hammer_alist_t live;
271 hammer_alist_config_t bl;
272 size_t metasize;
273
274 live = kmalloc(sizeof(*live), mtype, M_WAITOK);
275 live->config = bl = kmalloc(sizeof(*bl), mtype, M_WAITOK);
276 hammer_alist_template(bl, blocks, base_radix, 0, 0);
277
278 metasize = sizeof(*live->meta) * bl->bl_rootblks;
279 live->meta = kmalloc(metasize, mtype, M_WAITOK);
280 bzero(live->meta, metasize);
281
282 #if defined(ALIST_DEBUG)
283 kprintf(
284 "ALIST representing %d blocks (%d MB of swap)"
285 ", requiring %dK (%d bytes) of ram\n",
286 bl->bl_blocks,
287 bl->bl_blocks * 4 / 1024,
288 (bl->bl_rootblks * sizeof(*live->meta) + 1023) / 1024,
289 (bl->bl_rootblks * sizeof(*live->meta))
290 );
291 if (base_radix != 1) {
292 kprintf("ALIST recurses when it reaches a base_radix of %d\n",
293 base_radix);
294 }
295 kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
296 #endif
297 hammer_alist_init(live, 0, blocks, state);
298 return(live);
299 }
300
301 void
302 hammer_alist_destroy(hammer_alist_t live, struct malloc_type *mtype)
303 {
304 kfree(live->config, mtype);
305 kfree(live->meta, mtype);
306 live->config = NULL;
307 live->meta = NULL;
308 kfree(live, mtype);
309 }
310
311 #endif
312
313 /*
314 * hammer_alist_alloc()
315 *
316 * Reserve space in the block bitmap. Return the base of a contiguous
317 * region or HAMMER_ALIST_BLOCK_NONE if space could not be allocated.
318 */
319
320 int32_t
321 hammer_alist_alloc(hammer_alist_t live, int32_t count)
322 {
323 int32_t blk = HAMMER_ALIST_BLOCK_NONE;
324 hammer_alist_config_t bl = live->config;
325
326 KKASSERT((count | (count - 1)) == (count << 1) - 1);
327
328 if (bl && count <= bl->bl_radix) {
329 /*
330 * When skip is 1 we are at a leaf. If we are the terminal
331 * allocator we use our native leaf functions and radix will
332 * be HAMMER_ALIST_BMAP_RADIX. Otherwise we are a meta node
333 * which will chain to another allocator.
334 */
335 if (bl->bl_skip == 1 && bl->bl_terminal) {
336 #ifndef _KERNEL
337 KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
338 #endif
339 blk = hammer_alst_leaf_alloc_fwd(
340 live->meta + 1, 0, count, 0);
341 } else {
342 blk = hammer_alst_meta_alloc_fwd(
343 live, live->meta + 1,
344 0, count, bl->bl_radix, bl->bl_skip, 0);
345 }
346 if (blk != HAMMER_ALIST_BLOCK_NONE)
347 live->meta->bm_alist_freeblks -= count;
348 }
349 return(blk);
350 }
351
352 int32_t
353 hammer_alist_alloc_fwd(hammer_alist_t live, int32_t count, int32_t atblk)
354 {
355 int32_t blk = HAMMER_ALIST_BLOCK_NONE;
356 hammer_alist_config_t bl = live->config;
357
358 KKASSERT((count | (count - 1)) == (count << 1) - 1);
359
360 if (bl && count <= bl->bl_radix) {
361 /*
362 * When skip is 1 we are at a leaf. If we are the terminal
363 * allocator we use our native leaf functions and radix will
364 * be HAMMER_ALIST_BMAP_RADIX. Otherwise we are a meta node
365 * which will chain to another allocator.
366 */
367 if (bl->bl_skip == 1 && bl->bl_terminal) {
368 #ifndef _KERNEL
369 KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
370 #endif
371 blk = hammer_alst_leaf_alloc_fwd(
372 live->meta + 1, 0, count, atblk);
373 } else {
374 blk = hammer_alst_meta_alloc_fwd(
375 live, live->meta + 1,
376 0, count, bl->bl_radix, bl->bl_skip, atblk);
377 }
378 if (blk != HAMMER_ALIST_BLOCK_NONE)
379 live->meta->bm_alist_freeblks -= count;
380 }
381 return(blk);
382 }
383
384 int32_t
385 hammer_alist_alloc_rev(hammer_alist_t live, int32_t count, int32_t atblk)
386 {
387 hammer_alist_config_t bl = live->config;
388 int32_t blk = HAMMER_ALIST_BLOCK_NONE;
389
390 KKASSERT((count | (count - 1)) == (count << 1) - 1);
391
392 if (bl && count < bl->bl_radix) {
393 if (bl->bl_skip == 1 && bl->bl_terminal) {
394 #ifndef _KERNEL
395 KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
396 #endif
397 blk = hammer_alst_leaf_alloc_rev(
398 live->meta + 1, 0, count, atblk);
399 } else {
400 blk = hammer_alst_meta_alloc_rev(
401 live, live->meta + 1,
402 0, count, bl->bl_radix, bl->bl_skip, atblk);
403 }
404 if (blk != HAMMER_ALIST_BLOCK_NONE)
405 live->meta->bm_alist_freeblks -= count;
406 }
407 return(blk);
408 }
409
410 /*
411 * hammer_alist_find()
412 *
413 * Locate the first block >= atblk and < maxblk marked as allocated
414 * in the A-list and return it. Return HAMMER_ALIST_BLOCK_NONE if
415 * no block could be found.
416 *
417 * HAMMER_ALIST_FIND_NOSTACK - A special search mode which returns
418 * all initialized blocks (whether allocated or free) on bl_base_radix
419 * boundaries. The all-free (11) state is treated as initialized only
420 * if bl_inverted is set.
421 *
422 * HAMMER_ALIST_FIND_INITONLY - only initialized blocks are returned.
423 * Blocks belonging to the all-allocated/uninitialized state are not
424 * returned.
425 */
426 int32_t
427 hammer_alist_find(hammer_alist_t live, int32_t atblk, int32_t maxblk, int flags)
428 {
429 hammer_alist_config_t bl = live->config;
430 KKASSERT(live->config != NULL);
431 KKASSERT(atblk >= 0);
432 atblk = hammer_alst_find(live, live->meta + 1, 0, bl->bl_radix,
433 bl->bl_skip, atblk, flags);
434 if (atblk >= maxblk)
435 atblk = HAMMER_ALIST_BLOCK_NONE;
436 return(atblk);
437 }
438
439 /*
440 * hammer_alist_free()
441 *
442 * Free up space in the block bitmap. Return the base of a contiguous
443 * region. Panic if an inconsistancy is found.
444 *
445 * Unlike allocations, there are no alignment requirements for blkno or
446 * count when freeing blocks.
447 */
448
449 void
450 hammer_alist_free(hammer_alist_t live, int32_t blkno, int32_t count)
451 {
452 hammer_alist_config_t bl = live->config;
453
454 KKASSERT(blkno + count <= bl->bl_blocks);
455 if (bl->bl_skip == 1 && bl->bl_terminal) {
456 #ifndef _KERNEL
457 KKASSERT(bl->bl_radix == HAMMER_ALIST_BMAP_RADIX);
458 #endif
459 hammer_alst_leaf_free(live->meta + 1, blkno, count);
460 } else {
461 hammer_alst_meta_free(live, live->meta + 1,
462 blkno, count,
463 bl->bl_radix, bl->bl_skip, 0);
464 }
465 live->meta->bm_alist_freeblks += count;
466 }
467
468 /*
469 * Recover an A-list. This will dive down to the leaves and regenerate
470 * the hints and the freeblks count. This function will also recurse
471 * through any stacked A-lists. > 0 is returned on success, a negative
472 * error code on failure.
473 *
474 * Since A-lists have no pointers the only thing that can prevent recovery
475 * is an I/O error in e.g. a stacked A-list. This doesn't mean the recovered
476 * map will be meaningful, however.
477 *
478 * blk is usually passed as 0 at the top level and is adjusted as the recovery
479 * code scans the A-list. It is only used when recursing down a stacked
480 * A-list.
481 *
482 * (start,count) describes the region of the A-list which is allowed to contain
483 * free blocks. Any region to the left or right will be marked as allocated.
484 */
485 int
486 hammer_alist_recover(hammer_alist_t live, int32_t blk, int32_t start,
487 int32_t count)
488 {
489 hammer_alist_config_t bl = live->config;
490 struct hammer_alist_recover info;
491
492 info.live = live;
493 info.error = 0;
494
495 live->meta->bm_alist_freeblks = 0;
496 live->meta->bm_alist_base_freeblks = count;
497 hammer_alst_radix_recover(&info, live->meta + 1, blk, bl->bl_radix,
498 bl->bl_skip, bl->bl_blocks,
499 start, start + count);
500 if (info.error)
501 return(info.error);
502 return(live->meta->bm_alist_freeblks);
503 }
504
505 int
506 hammer_alist_isfull(hammer_alist_t live)
507 {
508 return(live->meta->bm_alist_freeblks == 0);
509 }
510
511 int
512 hammer_alist_isempty(hammer_alist_t live)
513 {
514 return((int)live->meta->bm_alist_freeblks ==
515 live->meta->bm_alist_base_freeblks);
516 }
517
518 #ifdef ALIST_DEBUG
519
520 /*
521 * alist_print() - dump radix tree
522 */
523
524 void
525 hammer_alist_print(hammer_alist_t live, int tab)
526 {
527 hammer_alist_config_t bl = live->config;
528
529 kprintf("%*.*sALIST (%d/%d free blocks) {\n",
530 tab, tab, "",
531 live->meta->bm_alist_freeblks,
532 live->meta->bm_alist_base_freeblks);
533 hammer_alst_radix_print(live, live->meta + 1, 0,
534 bl->bl_radix, bl->bl_skip, tab + 4);
535 kprintf("%*.*s}\n", tab, tab, "");
536 }
537
538 #endif
539
540 /************************************************************************
541 * ALLOCATION SUPPORT FUNCTIONS *
542 ************************************************************************
543 *
544 * These support functions do all the actual work. They may seem
545 * rather longish, but that's because I've commented them up. The
546 * actual code is straight forward.
547 *
548 */
549
550 /*
551 * hammer_alist_leaf_alloc_fwd()
552 *
553 * Allocate at a leaf in the radix tree (a bitmap).
554 *
555 * This is the core of the allocator and is optimized for the 1 block
556 * and the HAMMER_ALIST_BMAP_RADIX block allocation cases. Other cases
557 * are somewhat slower. The 1 block allocation case is log2 and extremely
558 * quick.
559 */
560
561 static int32_t
562 hammer_alst_leaf_alloc_fwd(hammer_almeta_t scan, int32_t blk,
563 int count, int32_t atblk)
564 {
565 u_int32_t orig = scan->bm_bitmap;
566 int32_t saveblk = blk;
567
568 /*
569 * Optimize bitmap all-allocated case. Also, count = 1
570 * case assumes at least 1 bit is free in the bitmap, so
571 * we have to take care of this case here.
572 */
573 if (orig == 0) {
574 scan->bm_bighint = 0;
575 return(HAMMER_ALIST_BLOCK_NONE);
576 }
577
578 #if 0
579 /*
580 * Optimized code to allocate one bit out of the bitmap
581 *
582 * mask iterates e.g. 00001111 00000011 00000001
583 *
584 * mask starts at 00001111
585 */
586 if (count == 1) {
587 u_int32_t mask;
588 int j = HAMMER_ALIST_BMAP_RADIX/2;
589 int r = 0;
590
591 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX/2);
592
593 while (j) {
594 if ((orig & mask) == 0) {
595 r += j;
596 orig >>= j;
597 }
598 j >>= 1;
599 mask >>= j;
600 }
601 scan->bm_bitmap &= ~(1 << r);
602 return(blk + r);
603 }
604 #endif
605
606 /*
607 * non-optimized code to allocate N bits out of the bitmap.
608 * The more bits, the faster the code runs. It will run
609 * the slowest allocating 2 bits, but since there aren't any
610 * memory ops in the core loop (or shouldn't be, anyway),
611 * you probably won't notice the difference.
612 *
613 * Similar to the blist case, the alist code also requires
614 * allocations to be power-of-2 sized and aligned to the
615 * size of the allocation, which simplifies the algorithm.
616 */
617 {
618 int j;
619 int n = HAMMER_ALIST_BMAP_RADIX - count;
620 u_int32_t mask;
621
622 mask = (u_int32_t)-1 >> n;
623
624 for (j = 0; j <= n; j += count) {
625 if ((orig & mask) == mask && blk >= atblk) {
626 scan->bm_bitmap &= ~mask;
627 return(blk);
628 }
629 mask = mask << count;
630 blk += count;
631 }
632 }
633
634 /*
635 * We couldn't allocate count in this subtree, update bighint if
636 * atblk didn't interfere with the hinting mechanism.
637 */
638 if (saveblk >= atblk)
639 scan->bm_bighint = count - 1;
640 return(HAMMER_ALIST_BLOCK_NONE);
641 }
642
643 /*
644 * This version allocates blocks in the reverse direction.
645 */
646 static int32_t
647 hammer_alst_leaf_alloc_rev(hammer_almeta_t scan, int32_t blk,
648 int count, int32_t atblk)
649 {
650 u_int32_t orig = scan->bm_bitmap;
651 int32_t saveblk;
652
653 /*
654 * Optimize bitmap all-allocated case. Also, count = 1
655 * case assumes at least 1 bit is free in the bitmap, so
656 * we have to take care of this case here.
657 */
658 if (orig == 0) {
659 scan->bm_bighint = 0;
660 return(HAMMER_ALIST_BLOCK_NONE);
661 }
662
663 #if 0
664 /*
665 * Optimized code to allocate one bit out of the bitmap
666 */
667 if (count == 1) {
668 u_int32_t mask;
669 int j = HAMMER_ALIST_BMAP_RADIX/2;
670 int r = HAMMER_ALIST_BMAP_RADIX - 1;
671
672 mask = ~((u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX/2));
673
674 while (j) {
675 if ((orig & mask) == 0) {
676 r -= j;
677 orig <<= j;
678 }
679 j >>= 1;
680 mask <<= j;
681 }
682 scan->bm_bitmap &= ~(1 << r);
683 return(blk + r);
684 }
685 #endif
686
687 /*
688 * non-optimized code to allocate N bits out of the bitmap.
689 * The more bits, the faster the code runs. It will run
690 * the slowest allocating 2 bits, but since there aren't any
691 * memory ops in the core loop (or shouldn't be, anyway),
692 * you probably won't notice the difference.
693 *
694 * Similar to the blist case, the alist code also requires
695 * allocations to be power-of-2 sized and aligned to the
696 * size of the allocation, which simplifies the algorithm.
697 *
698 * initial mask if count == 2: 1100....0000
699 */
700 {
701 int j;
702 int n = HAMMER_ALIST_BMAP_RADIX - count;
703 u_int32_t mask;
704
705 mask = ((u_int32_t)-1 >> n) << n;
706 blk += n;
707 saveblk = blk;
708
709 for (j = n; j >= 0; j -= count) {
710 if ((orig & mask) == mask && blk <= atblk) {
711 scan->bm_bitmap &= ~mask;
712 return(blk);
713 }
714 mask = mask >> count;
715 blk -= count;
716 }
717 }
718
719 /*
720 * We couldn't allocate count in this subtree, update bighint if
721 * atblk didn't interfere with it.
722 */
723 if (saveblk <= atblk)
724 scan->bm_bighint = count - 1;
725 return(HAMMER_ALIST_BLOCK_NONE);
726 }
727
728 /*
729 * hammer_alist_meta_alloc_fwd()
730 *
731 * Allocate at a meta in the radix tree.
732 *
733 * Attempt to allocate at a meta node. If we can't, we update
734 * bighint and return a failure. Updating bighint optimize future
735 * calls that hit this node. We have to check for our collapse cases
736 * and we have a few optimizations strewn in as well.
737 */
738 static int32_t
739 hammer_alst_meta_alloc_fwd(hammer_alist_t live, hammer_almeta_t scan,
740 int32_t blk, int32_t count,
741 int32_t radix, int skip, int32_t atblk
742 ) {
743 hammer_alist_config_t bl;
744 u_int32_t mask;
745 u_int32_t pmask;
746 int32_t saveblk;
747 int next_skip;
748 int i;
749
750 /*
751 * ALL-ALLOCATED special case
752 */
753 if (scan->bm_bitmap == 0 || scan->bm_bitmap == 0xAAAAAAAAU) {
754 scan->bm_bighint = 0;
755 return(HAMMER_ALIST_BLOCK_NONE);
756 }
757
758 radix /= HAMMER_ALIST_META_RADIX;
759 bl = live->config;
760
761 /*
762 * Radix now represents each bitmap entry for this meta node. If
763 * the number of blocks being allocated can be fully represented,
764 * we allocate directly out of this meta node.
765 *
766 * Meta node bitmaps use 2 bits per block.
767 *
768 * 00 ALL-ALLOCATED - UNINITIALIZED
769 * 01 PARTIALLY-FREE/PARTIALLY-ALLOCATED
770 * 10 ALL-ALLOCATED - INITIALIZED
771 * 11 ALL-FREE - UNINITIALIZED
772 */
773 if (count >= radix) {
774 int n = count / radix * 2; /* number of bits */
775 int nd2 = n / 2;
776 int j;
777
778 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - n);
779 saveblk = blk;
780 for (j = 0; j < (int)HAMMER_ALIST_META_RADIX; j += nd2) {
781 if ((scan->bm_bitmap & mask) == mask && blk >= atblk) {
782 /*
783 * NOTE: Marked all-allocate/uninitialized
784 * rather then all-allocated/initialized.
785 * See the warning at the top of the file.
786 */
787 scan->bm_bitmap &= ~mask;
788 return(blk);
789 }
790 mask <<= n;
791 blk += radix * nd2;
792 }
793 if (scan->bm_bighint >= count && saveblk >= atblk)
794 scan->bm_bighint = count >> 1;
795 return(HAMMER_ALIST_BLOCK_NONE);
796 }
797
798 /*
799 * If the count is too big we couldn't allocate anything from a
800 * recursion even if the sub-tree were entirely free.
801 */
802 saveblk = blk;
803 if (count > radix)
804 goto failed;
805
806 /*
807 * If not we have to recurse.
808 */
809 mask = 0x00000003;
810 pmask = 0x00000001;
811
812 if (skip == 1) {
813 /*
814 * If skip is 1 we are a meta leaf node, which means there
815 * is another allocation layer we have to dive down into.
816 */
817 for (i = 0; i < (int)HAMMER_ALIST_META_RADIX; ++i) {
818 /*
819 * If the next layer is completely free then call
820 * its init function to initialize it.
821 */
822 if ((scan->bm_bitmap & mask) == mask &&
823 blk + radix > atblk) {
824 if (bl->bl_radix_init(live->info, blk, radix, HAMMER_ASTATE_FREE) == 0) {
825 /*
826 * NOTE: Marked all-allocate/uninit-
827 * ialized rather then all-allocated/
828 * initialized. See the warning at
829 * the top of the file.
830 */
831 scan->bm_bitmap &= ~mask;
832 scan->bm_bitmap |= pmask;
833 }
834 }
835
836 /*
837 * If there may be some free blocks try to allocate
838 * out of the layer. If the layer indicates that
839 * it is completely full then clear both bits to
840 * propogate the condition.
841 */
842 if ((scan->bm_bitmap & mask) == pmask &&
843 blk + radix > atblk) {
844 int32_t r;
845 int32_t full;
846
847 r = bl->bl_radix_alloc_fwd(live->info, blk,
848 radix, count,
849 atblk, &full);
850 if (full) {
851 scan->bm_bitmap &= ~mask;
852 scan->bm_bitmap |= pmask << 1;
853 }
854 if (r != HAMMER_ALIST_BLOCK_NONE)
855 return(r);
856 }
857 blk += radix;
858 mask <<= 2;
859 pmask <<= 2;
860 }
861 } else {
862 /*
863 * Otherwise there are sub-records in the current a-list
864 * layer. We can also peek into the sub-layers to get
865 * more accurate size hints.
866 */
867 next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
868 for (i = 1; i < skip; i += next_skip) {
869 if (scan[i].bm_bighint == (int32_t)-1) {
870 /*
871 * Terminator
872 */
873 break;
874 }
875
876 /*
877 * Initialize bitmap if allocating from the all-free
878 * case.
879 */
880 if ((scan->bm_bitmap & mask) == mask) {
881 scan[i].bm_bitmap = (u_int32_t)-1;
882 scan[i].bm_bighint = radix;
883 }
884
885 if (count <= scan[i].bm_bighint &&
886 blk + radix > atblk) {
887 /*
888 * count fits in object, recurse into the
889 * next layer. If the next_skip is 1 it
890 * will be either a normal leaf or a meta
891 * leaf.
892 */
893 int32_t r;
894
895 if (next_skip == 1 && bl->bl_terminal) {
896 r = hammer_alst_leaf_alloc_fwd(
897 &scan[i], blk, count, atblk);
898 } else {
899 r = hammer_alst_meta_alloc_fwd(
900 live, &scan[i],
901 blk, count,
902 radix, next_skip, atblk);
903 }
904 if (r != HAMMER_ALIST_BLOCK_NONE) {
905 if (scan[i].bm_bitmap == 0) {
906 scan->bm_bitmap &= ~mask;
907 } else if (scan[i].bm_bitmap == 0xAAAAAAAAU) {
908 scan->bm_bitmap &= ~mask;
909 scan->bm_bitmap |= pmask << 1;
910 } else {
911 scan->bm_bitmap &= ~mask;
912 scan->bm_bitmap |= pmask;
913 }
914 return(r);
915 }
916 }
917 blk += radix;
918 mask <<= 2;
919 pmask <<= 2;
920 }
921 }
922
923 failed:
924 /*
925 * We couldn't allocate count in this subtree, update bighint.
926 */
927 if (scan->bm_bighint >= count && saveblk >= atblk)
928 scan->bm_bighint = count >> 1;
929 return(HAMMER_ALIST_BLOCK_NONE);
930 }
931
932 /*
933 * This version allocates blocks in the reverse direction.
934 *
935 * This is really nasty code
936 */
937 static int32_t
938 hammer_alst_meta_alloc_rev(hammer_alist_t live, hammer_almeta_t scan,
939 int32_t blk, int32_t count,
940 int32_t radix, int skip, int32_t atblk
941 ) {
942 hammer_alist_config_t bl;
943 int i;
944 int j;
945 u_int32_t mask;
946 u_int32_t pmask;
947 int32_t saveblk;
948 int next_skip;
949
950 /*
951 * ALL-ALLOCATED special case
952 */
953 if (scan->bm_bitmap == 0 || scan->bm_bitmap == 0xAAAAAAAAU) {
954 scan->bm_bighint = 0;
955 return(HAMMER_ALIST_BLOCK_NONE);
956 }
957
958 radix /= HAMMER_ALIST_META_RADIX;
959 bl = live->config;
960
961 /*
962 * Radix now represents each bitmap entry for this meta node. If
963 * the number of blocks being allocated can be fully represented,
964 * we allocate directly out of this meta node.
965 *
966 * Meta node bitmaps use 2 bits per block.
967 *
968 * 00 ALL-ALLOCATED (uninitialized)
969 * 01 PARTIALLY-FREE/PARTIALLY-ALLOCATED
970 * 10 ALL-ALLOCATED (initialized)
971 * 11 ALL-FREE
972 */
973 if (count >= radix) {
974 int n = count / radix * 2; /* number of bits */
975 int nd2 = n / 2; /* number of radi */
976
977 /*
978 * Initial mask if e.g. n == 2: 1100....0000
979 */
980 mask = (u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - n) <<
981 (HAMMER_ALIST_BMAP_RADIX - n);
982 blk += (HAMMER_ALIST_META_RADIX - nd2) * radix;
983 saveblk = blk;
984 for (j = HAMMER_ALIST_META_RADIX - nd2; j >= 0; j -= nd2) {
985 if ((scan->bm_bitmap & mask) == mask && blk <= atblk) {
986 scan->bm_bitmap &= ~mask;
987 return(blk);
988 }
989 mask >>= n;
990 blk -= nd2 * radix;
991 }
992 if (scan->bm_bighint >= count && saveblk <= atblk)
993 scan->bm_bighint = count >> 1;
994 return(HAMMER_ALIST_BLOCK_NONE);
995 }
996
997 /*
998 * NOTE: saveblk must represent the entire layer, not the base blk
999 * of the last element. Otherwise an atblk that is inside the
1000 * last element can cause bighint to be updated for a failed
1001 * allocation when we didn't actually test all available blocks.
1002 */
1003
1004 if (skip == 1) {
1005 /*
1006 * We need the recurse but we are at a meta node leaf, which
1007 * means there is another layer under us.
1008 */
1009 mask = 0xC0000000;
1010 pmask = 0x40000000;
1011 blk += radix * HAMMER_ALIST_META_RADIX;
1012
1013 saveblk = blk;
1014 blk -= radix;
1015
1016 for (i = 0; i < (int)HAMMER_ALIST_META_RADIX; ++i) {
1017 /*
1018 * If the next layer is completely free then call
1019 * its init function to initialize it. The init
1020 * function is responsible for the initial freeing.
1021 */
1022 if ((scan->bm_bitmap & mask) == mask && blk <= atblk) {
1023 if (bl->bl_radix_init(live->info, blk, radix, HAMMER_ASTATE_FREE) == 0) {
1024 scan->bm_bitmap &= ~mask;
1025 scan->bm_bitmap |= pmask;
1026 }
1027 }
1028
1029 /*
1030 * If there may be some free blocks try to allocate
1031 * out of the layer. If the layer indicates that
1032 * it is completely full then clear both bits to
1033 * propogate the condition.
1034 */
1035 if ((scan->bm_bitmap & mask) == pmask && blk <= atblk) {
1036 int32_t r;
1037 int32_t full;
1038
1039 r = bl->bl_radix_alloc_rev(live->info, blk,
1040 radix, count,
1041 atblk, &full);
1042 if (full) {
1043 scan->bm_bitmap &= ~mask;
1044 scan->bm_bitmap |= pmask << 1;
1045 }
1046 if (r != HAMMER_ALIST_BLOCK_NONE)
1047 return(r);
1048 }
1049 mask >>= 2;
1050 pmask >>= 2;
1051 blk -= radix;
1052 }
1053 } else {
1054 /*
1055 * Since we are going in the reverse direction we need an
1056 * extra loop to determine if there is a terminator, then
1057 * run backwards.
1058 *
1059 * This is a little weird but we do not want to overflow the
1060 * mask/pmask in the loop.
1061 */
1062 next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
1063 j = 0;
1064 for (i = 1; i < skip; i += next_skip) {
1065 if (scan[i].bm_bighint == (int32_t)-1) {
1066 KKASSERT(j != 0);
1067 break;
1068 }
1069 blk += radix;
1070 j += 2;
1071 }
1072
1073 saveblk = blk;
1074 blk -= radix;
1075 j -= 2;
1076 mask = 0x00000003 << j;
1077 pmask = 0x00000001 << j;
1078 i -= next_skip;
1079
1080 while (i >= 1) {
1081 /*
1082 * Initialize the bitmap in the child if allocating
1083 * from the all-free case.
1084 */
1085 if ((scan->bm_bitmap & mask) == mask) {
1086 scan[i].bm_bitmap = (u_int32_t)-1;
1087 scan[i].bm_bighint = radix;
1088 }
1089
1090 /*
1091 * Handle various count cases. Bighint may be too
1092 * large but is never too small.
1093 */
1094 if (count <= scan[i].bm_bighint && blk <= atblk) {
1095 /*
1096 * count fits in object
1097 */
1098 int32_t r;
1099 if (next_skip == 1 && bl->bl_terminal) {
1100 r = hammer_alst_leaf_alloc_rev(
1101 &scan[i], blk, count, atblk);
1102 } else {
1103 r = hammer_alst_meta_alloc_rev(
1104 live, &scan[i],
1105 blk, count,
1106 radix, next_skip, atblk);
1107 }
1108 if (r != HAMMER_ALIST_BLOCK_NONE) {
1109 if (scan[i].bm_bitmap == 0) {
1110 scan->bm_bitmap &= ~mask;
1111 } else if (scan[i].bm_bitmap == 0xAAAAAAAAU) {
1112 scan->bm_bitmap &= ~mask;
1113 scan->bm_bitmap |= pmask << 1;
1114 } else {
1115 scan->bm_bitmap &= ~mask;
1116 scan->bm_bitmap |= pmask;
1117 }
1118 return(r);
1119 }
1120 }
1121 blk -= radix;
1122 mask >>= 2;
1123 pmask >>= 2;
1124 i -= next_skip;
1125 }
1126 }
1127
1128 /*
1129 * We couldn't allocate count in this subtree, update bighint.
1130 * Since we are restricted to powers of 2, the next highest count
1131 * we might be able to allocate is (count >> 1).
1132 */
1133 if (scan->bm_bighint >= count && saveblk <= atblk)
1134 scan->bm_bighint = count >> 1;
1135 return(HAMMER_ALIST_BLOCK_NONE);
1136 }
1137
1138 /*
1139 * HAMMER_ALST_FIND()
1140 *
1141 * Locate the first allocated block greater or equal to atblk.
1142 */
1143 static int32_t
1144 hammer_alst_find(hammer_alist_t live, hammer_almeta_t scan, int32_t blk,
1145 int32_t radix, int32_t skip, int32_t atblk, int flags)
1146 {
1147 u_int32_t mask;
1148 u_int32_t pmask;
1149 int32_t next_skip;
1150 int32_t tmpblk;
1151 int nostack = flags & HAMMER_ALIST_FIND_NOSTACK;
1152 int initonly = flags & HAMMER_ALIST_FIND_INITONLY;
1153 int i;
1154 int j;
1155
1156 /*
1157 * Leaf node (currently hammer_alist_find() only works on terminal
1158 * a-list's and the case is asserted in hammer_alist_find()).
1159 */
1160 if (skip == 1 && live->config->bl_terminal) {
1161 if (scan->bm_bitmap == (u_int32_t)-1)
1162 return(HAMMER_ALIST_BLOCK_NONE);
1163 for (i = 0; i < (int)HAMMER_ALIST_BMAP_RADIX; ++i) {
1164 if (blk + i < atblk)
1165 continue;
1166 if ((scan->bm_bitmap & (1 << i)) == 0)
1167 return(blk + i);
1168 }
1169 return(HAMMER_ALIST_BLOCK_NONE);
1170 }
1171
1172 /*
1173 * Meta
1174 */
1175 radix /= HAMMER_ALIST_META_RADIX;
1176 next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
1177 mask = 0x00000003;
1178 pmask = 0x00000001;
1179 for (j = 0, i = 1; j < (int)HAMMER_ALIST_META_RADIX;
1180 (i += next_skip), ++j) {
1181 /*
1182 * Check Terminator
1183 */
1184 if (scan[i].bm_bighint == (int32_t)-1) {
1185 break;
1186 }
1187
1188 /*
1189 * Recurse if this meta might contain a desired block.
1190 */
1191 if (blk + radix > atblk) {
1192 if (next_skip == 0 && nostack) {
1193 /*
1194 * At base_radix and nostack was specified.
1195 */
1196 if ((scan->bm_bitmap & mask) == 0) {
1197 /*
1198 * 00 - all-allocated, uninitalized
1199 */
1200 if (initonly == 0) {
1201 if (atblk <= blk)
1202 return(blk);
1203 }
1204 } else if ((scan->bm_bitmap & mask) != mask) {
1205 /*
1206 * 01 or 10 - partially allocated
1207 * or all-allocated/initialized.
1208 */
1209 if (atblk <= blk)
1210 return(blk);
1211 } else if ((scan->bm_bitmap & mask) == mask) {
1212 /*
1213 * 11 - all free. If inverted it is
1214 * initialized, however, and must be
1215 * returned for the no-stack case.
1216 */
1217 if (live->config->bl_inverted) {
1218 if (atblk <= blk)
1219 return(blk);
1220 }
1221 }
1222 } else if ((scan->bm_bitmap & mask) == 0) {
1223 /*
1224 * 00 - all-allocated, uninitialized
1225 */
1226 if (initonly == 0) {
1227 goto return_all_meta;
1228 }
1229 /* else skip */
1230 } else if ((scan->bm_bitmap & mask) == (pmask << 1)) {
1231 /*
1232 * 10 - all-allocated, initialized
1233 */
1234 goto return_all_meta;
1235 } else if ((scan->bm_bitmap & mask) == mask) {
1236 /*
1237 * 11 - all-free (skip if not inverted)
1238 *
1239 * If nostack and inverted we must return
1240 * blocks on the base radix boundary.
1241 */
1242 if (nostack && live->config->bl_inverted) {
1243 int32_t bradix;
1244
1245 return_all_meta:
1246 bradix = live->config->bl_base_radix;
1247 if (atblk <= blk)
1248 return(blk);
1249 atblk = (atblk + bradix - 1) &
1250 ~(bradix - 1);
1251 if (atblk < blk + radix)
1252 return(atblk);
1253 }
1254 } else if (next_skip == 0) {
1255 /*
1256 * Partially allocated but we have to recurse
1257 * into a stacked A-list.
1258 *
1259 * If no-stack is set the caller just wants
1260 * to know if the
1261 */
1262 if (atblk < blk)
1263 atblk = blk;
1264 tmpblk = live->config->bl_radix_find(
1265 live->info, blk, radix,
1266 atblk, flags);
1267 if (tmpblk != HAMMER_ALIST_BLOCK_NONE)
1268 return(tmpblk);
1269 /* else skip */
1270 } else if ((scan->bm_bitmap & mask) == pmask) {
1271 /*
1272 * 01 - partially-allocated
1273 */
1274 if (atblk < blk)
1275 atblk = blk;
1276 tmpblk = hammer_alst_find(live, &scan[i],
1277 blk, radix,
1278 next_skip, atblk,
1279 flags);
1280 if (tmpblk != HAMMER_ALIST_BLOCK_NONE)
1281 return(tmpblk);
1282 }
1283 }
1284 mask <<= 2;
1285 pmask <<= 2;
1286 blk += radix;
1287 }
1288 return(HAMMER_ALIST_BLOCK_NONE);
1289 }
1290
1291 /*
1292 * HAMMER_ALST_LEAF_FREE()
1293 *
1294 * Free allocated blocks from leaf bitmap. The allocation code is
1295 * restricted to powers of 2, the freeing code is not.
1296 */
1297 static void
1298 hammer_alst_leaf_free(hammer_almeta_t scan, int32_t blk, int count) {
1299 /*
1300 * free some data in this bitmap
1301 *
1302 * e.g.
1303 * 0000111111111110000
1304 * \_________/\__/
1305 * v n
1306 */
1307 int n = blk & (HAMMER_ALIST_BMAP_RADIX - 1);
1308 u_int32_t mask;
1309
1310 mask = ((u_int32_t)-1 << n) &
1311 ((u_int32_t)-1 >> (HAMMER_ALIST_BMAP_RADIX - count - n));
1312
1313 if (scan->bm_bitmap & mask)
1314 panic("hammer_alst_radix_free: freeing free block");
1315 scan->bm_bitmap |= mask;
1316
1317 /*
1318 * We could probably do a better job here. We are required to make
1319 * bighint at least as large as the biggest contiguous block of
1320 * data. If we just shoehorn it, a little extra overhead will
1321 * be incured on the next allocation (but only that one typically).
1322 */
1323 scan->bm_bighint = HAMMER_ALIST_BMAP_RADIX;
1324 }
1325
1326 /*
1327 * BLST_META_FREE()
1328 *
1329 * Free allocated blocks from radix tree meta info.
1330 *
1331 * This support routine frees a range of blocks from the bitmap.
1332 * The range must be entirely enclosed by this radix node. If a
1333 * meta node, we break the range down recursively to free blocks
1334 * in subnodes (which means that this code can free an arbitrary
1335 * range whereas the allocation code cannot allocate an arbitrary
1336 * range).
1337 */
1338
1339 static void
1340 hammer_alst_meta_free(hammer_alist_t live, hammer_almeta_t scan,
1341 int32_t freeBlk, int32_t count,
1342 int32_t radix, int skip, int32_t blk
1343 ) {
1344 hammer_alist_config_t bl;
1345 int next_skip;
1346 u_int32_t mask;
1347 u_int32_t pmask;
1348 int i;
1349
1350 /*
1351 * Break the free down into its components. Because it is so easy
1352 * to implement, frees are not limited to power-of-2 sizes.
1353 *
1354 * Each block in a meta-node bitmap takes two bits.
1355 */
1356 radix /= HAMMER_ALIST_META_RADIX;
1357 bl = live->config;
1358
1359 i = (freeBlk - blk) / radix;
1360 blk += i * radix;
1361 mask = 0x00000003 << (i * 2);
1362 pmask = 0x00000001 << (i * 2);
1363
1364 if (skip == 1) {
1365 /*
1366 * Our meta node is a leaf node, which means it must recurse
1367 * into another allocator.
1368 */
1369 while (i < (int)HAMMER_ALIST_META_RADIX &&
1370 blk < freeBlk + count) {
1371 int32_t v;
1372
1373 v = blk + radix - freeBlk;
1374 if (v > count)
1375 v = count;
1376
1377 if (scan->bm_bighint == (int32_t)-1)
1378 panic("hammer_alst_meta_free: freeing unexpected range");
1379 KKASSERT((scan->bm_bitmap & mask) != mask);
1380
1381 if (freeBlk == blk && count >= radix) {
1382 /*
1383 * Freeing an entire zone. Only recurse if
1384 * the zone was initialized. A 00 state means
1385 * that the zone is marked all-allocated,
1386 * but was never initialized.
1387 *
1388 * Then set the zone to the all-free state (11).
1389 */
1390 int32_t empty;
1391
1392 if (scan->bm_bitmap & mask) {
1393 bl->bl_radix_free(live->info, blk, radix,
1394 freeBlk - blk, v, &empty);
1395 KKASSERT(empty);
1396 bl->bl_radix_destroy(live->info, blk, radix);
1397 }
1398 scan->bm_bitmap |= mask;
1399 scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
1400 /* XXX bighint not being set properly */
1401 } else {
1402 /*
1403 * Recursion case, partial free. If 00 the
1404 * zone is marked all allocated but has never
1405 * been initialized, so we init it.
1406 */
1407 int32_t empty;
1408
1409 if ((scan->bm_bitmap & mask) == 0)
1410 bl->bl_radix_init(live->info, blk, radix, HAMMER_ASTATE_ALLOC);
1411 bl->bl_radix_free(live->info, blk, radix,
1412 freeBlk - blk, v, &empty);
1413 if (empty) {
1414 if (scan->bm_bitmap & mask)
1415 bl->bl_radix_destroy(live->info, blk, radix);
1416 scan->bm_bitmap |= mask;
1417 scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
1418 /* XXX bighint not being set properly */
1419 } else {
1420 scan->bm_bitmap &= ~mask;
1421 scan->bm_bitmap |= pmask;
1422 if (scan->bm_bighint < radix / 2)
1423 scan->bm_bighint = radix / 2;
1424 /* XXX bighint not being set properly */
1425 }
1426 }
1427 ++i;
1428 mask <<= 2;
1429 pmask <<= 2;
1430 count -= v;
1431 freeBlk += v;
1432 blk += radix;
1433 }
1434 } else {
1435 next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
1436 i = 1 + i * next_skip;
1437
1438 while (i <= skip && blk < freeBlk + count) {
1439 int32_t v;
1440
1441 KKASSERT(mask != 0);
1442 KKASSERT(count != 0);
1443
1444 v = blk + radix - freeBlk;
1445 if (v > count)
1446 v = count;
1447
1448 if (scan->bm_bighint == (int32_t)-1)
1449 panic("hammer_alst_meta_free: freeing unexpected range");
1450
1451 if (freeBlk == blk && count >= radix) {
1452 /*
1453 * All-free case, no need to update sub-tree
1454 */
1455 scan->bm_bitmap |= mask;
1456 scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
1457 /* XXX bighint not being set properly */
1458 } else {
1459 /*
1460 * Recursion case
1461 */
1462 if (next_skip == 1 && bl->bl_terminal) {
1463 hammer_alst_leaf_free(&scan[i], freeBlk, v);
1464 } else {
1465 hammer_alst_meta_free(live, &scan[i],
1466 freeBlk, v,
1467 radix, next_skip,
1468 blk);
1469 }
1470 if (scan[i].bm_bitmap == (u_int32_t)-1) {
1471 scan->bm_bitmap |= mask;
1472 /* XXX bighint not set properly */
1473 scan->bm_bighint = radix * HAMMER_ALIST_META_RADIX;
1474 } else {
1475 scan->bm_bitmap &= ~mask;
1476 scan->bm_bitmap |= pmask;
1477 /* XXX bighint not set properly */
1478 if (scan->bm_bighint < scan[i].bm_bighint)
1479 scan->bm_bighint = scan[i].bm_bighint;
1480 }
1481 }
1482 mask <<= 2;
1483 pmask <<= 2;
1484 count -= v;
1485 freeBlk += v;
1486 blk += radix;
1487 i += next_skip;
1488 }
1489 }
1490 }
1491
1492 /*
1493 * hammer_alst_radix_init()
1494 *
1495 * Initialize our meta structures and bitmaps and calculate the exact
1496 * number of meta-nodes required to manage 'count' blocks.
1497 *
1498 * The required space may be truncated due to early termination records.
1499 */
1500 static int32_t
1501 hammer_alst_radix_init(hammer_almeta_t scan, int32_t radix,
1502 int skip, int32_t count)
1503 {
1504 int i;
1505 int next_skip;
1506 int32_t memindex = 1;
1507 u_int32_t mask;
1508 u_int32_t pmask;
1509
1510 /*
1511 * Basic initialization of the almeta for meta or leaf nodes. This
1512 * marks the element as all-allocated.
1513 */
1514 if (scan) {
1515 scan->bm_bighint = 0;
1516 scan->bm_bitmap = 0;
1517 }
1518
1519 /*
1520 * We are at a terminal node, we only eat one meta element. If
1521 * live->config->bl_terminal is set this is a leaf node, otherwise
1522 * it is a meta node for a stacked A-list. We do NOT recurse into
1523 * stacked A-lists but simply mark the entire stack as all-free using
1524 * code 00 (meaning all-free & uninitialized).
1525 */
1526 if (skip == 1)
1527 return(memindex);
1528
1529 /*
1530 * Meta node. If allocating the entire object we can special
1531 * case it. However, we need to figure out how much memory
1532 * is required to manage 'count' blocks, so we continue on anyway.
1533 */
1534 radix /= HAMMER_ALIST_META_RADIX;
1535 next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
1536 mask = 0x00000003;
1537 pmask = 0x00000001;
1538
1539 for (i = 1; i < skip; i += next_skip) {
1540 /*
1541 * We eat up to this record
1542 */
1543 memindex = i;
1544
1545 KKASSERT(mask != 0);
1546
1547 if (count >= radix) {
1548 /*
1549 * Allocate the entire object
1550 */
1551 memindex += hammer_alst_radix_init(
1552 ((scan) ? &scan[i] : NULL),
1553 radix,
1554 next_skip,
1555 radix
1556 );
1557 count -= radix;
1558 /* already marked as wholely allocated */
1559 } else if (count > 0) {
1560 /*
1561 * Allocate a partial object
1562 */
1563 memindex += hammer_alst_radix_init(
1564 ((scan) ? &scan[i] : NULL),
1565 radix,
1566 next_skip,
1567 count
1568 );
1569 count = 0;
1570
1571 /*
1572 * Mark as partially allocated
1573 */
1574 if (scan) {
1575 scan->bm_bitmap &= ~mask;
1576 scan->bm_bitmap |= pmask;
1577 }
1578 } else {
1579 /*
1580 * Add terminator and break out. The terminal
1581 * eats the meta node at scan[i].
1582 */
1583 ++memindex;
1584 if (scan)
1585 scan[i].bm_bighint = (int32_t)-1;
1586 /* already marked as wholely allocated */
1587 break;
1588 }
1589 mask <<= 2;
1590 pmask <<= 2;
1591 }
1592 return(memindex);
1593 }
1594
1595 /*
1596 * hammer_alst_radix_recover()
1597 *
1598 * This code is basically a duplicate of hammer_alst_radix_init()
1599 * except it recovers the a-list instead of initializes it.
1600 *
1601 * (a_beg,a_end) specifies the global allocatable range within
1602 * the radix tree. The recovery code guarentees that blocks
1603 * within the tree but outside this range are marked as being
1604 * allocated to prevent them from being allocated.
1605 *
1606 *
1607 */
1608 static void
1609 hammer_alst_radix_recover(hammer_alist_recover_t info, hammer_almeta_t scan,
1610 int32_t blk, int32_t radix, int skip, int32_t count,
1611 int32_t a_beg, int32_t a_end)
1612 {
1613 hammer_alist_t live = info->live;
1614 u_int32_t mask;
1615 u_int32_t pmask;
1616 int next_skip;
1617 int i;
1618 int j;
1619 int n;
1620
1621 /*
1622 * Don't try to recover bighint, just set it to its maximum
1623 * value and let the A-list allocations reoptimize it. XXX
1624 */
1625 scan->bm_bighint = radix;
1626
1627 /*
1628 * If we are at a terminal node (i.e. not stacked on top of another
1629 * A-list), just count the free blocks.
1630 */
1631 if (skip == 1 && live->config->bl_terminal) {
1632 for (i = 0; i < (int)HAMMER_ALIST_BMAP_RADIX; ++i) {
1633 if (blk + i < a_beg || blk + i >= a_end)
1634 scan->bm_bitmap &= ~(1 << i);
1635 if (scan->bm_bitmap & (1 << i))
1636 ++info->live->meta->bm_alist_freeblks;
1637 }
1638 return;
1639 }
1640
1641 /*
1642 * Recursive meta node (next_skip != 0) or terminal meta
1643 * node (next_skip == 0).
1644 */
1645 radix /= HAMMER_ALIST_META_RADIX;
1646 next_skip = (skip - 1) / HAMMER_ALIST_META_RADIX;
1647 mask = 0x00000003;
1648 pmask = 0x00000001;
1649
1650 for (i = 1, j = 0; j < (int)HAMMER_ALIST_META_RADIX;
1651 ++j, (i += next_skip)) {
1652 /*
1653 * Check mask:
1654 *
1655 * 00 ALL-ALLOCATED - UNINITIALIZED
1656 * 01 PARTIALLY-FREE/PARTIALLY-ALLOCATED
1657 * 10 ALL-ALLOCATED - INITIALIZED
1658 * 11 ALL-FREE - UNINITIALIZED (INITIALIZED
1659 * IF CONFIG SAYS INVERTED)
1660 */
1661 KKASSERT(mask);
1662
1663 /*
1664 * Adjust the bitmap for out of bounds or partially out of
1665 * bounds elements. If we are completely out of bounds
1666 * mark as all-allocated. If we are partially out of
1667 * bounds do not allow the area to be marked all-free.
1668 */
1669 if (blk + radix <= a_beg || blk >= a_end) {
1670 scan->bm_bitmap &= ~mask;
1671 } else if (blk < a_beg || blk + radix > a_end) {
1672 if ((scan->bm_bitmap & mask) == mask) {
1673 scan->bm_bitmap &= ~mask;
1674 scan->bm_bitmap |= pmask;
1675 }
1676 }
1677
1678 if (count >= radix) {
1679 /*
1680 * Recover the entire object
1681 */
1682 if ((scan->bm_bitmap & mask) == 0) {
1683 /*
1684 * All-allocated (uninited), do nothing
1685 */
1686 } else if ((scan->bm_bitmap & mask) == mask &&
1687 live->config->bl_inverted == 0) {
1688 /*
1689 * All-free (uninited), do nothing.
1690 *
1691 * (if inverted all-free is initialized and
1692 * must be recovered).
1693 */
1694 live->meta->bm_alist_freeblks += radix;
1695 } else if (next_skip) {
1696 if ((scan->bm_bitmap & mask) == mask) {
1697 /*
1698 * This is a special case. If we
1699 * are inverted but in an all-free
1700 * state, it's actually initialized
1701 * (sorta) and we still have to dive
1702 * through to any stacked nodes so
1703 * we can call bl_radix_recover().
1704 */
1705 scan[i].bm_bitmap = (u_int32_t)-1;
1706 }
1707 /*
1708 * Normal meta node, initialized. Recover and
1709 * adjust to the proper state.
1710 */
1711 hammer_alst_radix_recover(
1712 info,
1713 &scan[i],
1714 blk, radix,
1715 next_skip, radix,
1716 a_beg, a_end
1717 );
1718 if (scan[i].bm_bitmap == 0) {
1719 scan->bm_bitmap &= ~mask;
1720 } else if (scan[i].bm_bitmap == 0xAAAAAAAAU) {
1721 scan->bm_bitmap &= ~mask;
1722 scan->bm_bitmap |= pmask << 1;
1723 } else if (scan[i].bm_bitmap == (u_int32_t)-1) {
1724 scan->bm_bitmap |= mask;
1725 } else {
1726 scan->bm_bitmap &= ~mask;
1727 scan->bm_bitmap |= pmask;
1728 }
1729 } else {
1730 /*
1731 * Stacked meta node, recurse.
1732 *
1733 * If no free blocks are present mark the
1734 * meta node as all-allocated/initialized.
1735 * A return code of -EDOM will mark the
1736 * meta node as all-allocated/uninitialized.
1737 *
1738 * This can be really confusing. bl_inverted
1739 * has no function here because we are
1740 * ALREADY known to be in an initialized
1741 * state.
1742 */
1743 n = live->config->bl_radix_recover(
1744 live->info,
1745 blk, radix, radix);
1746 if (n == -EDOM) {
1747 scan->bm_bitmap &= ~mask;
1748 } else if (n >= 0) {
1749 live->meta->bm_alist_freeblks += n;
1750 if (n == 0) {
1751 scan->bm_bitmap =
1752 (scan->bm_bitmap & ~mask) |
1753 (pmask << 1);
1754 } else if (n == radix) {
1755 scan->bm_bitmap |= mask;
1756 } else {
1757 scan->bm_bitmap =
1758 (scan->bm_bitmap & ~mask) |
1759 pmask;
1760 }
1761 } else {
1762 info->error = n;
1763 }
1764 }
1765 count -= radix;
1766 } else if (count > 0) {
1767 /*
1768 * Recover a partial object. The object can become
1769 * wholely allocated but never wholely free.
1770 */
1771 if (next_skip) {
1772 hammer_alst_radix_recover(
1773 info,
1774 &scan[i],
1775 blk, radix,
1776 next_skip, count,
1777 a_beg, a_end
1778 );
1779 if (scan[i].bm_bitmap == 0) {
1780 scan->bm_bitmap &= ~mask;
1781 } else if (scan[i].bm_bitmap == 0xAAAAAAAAU) {
1782 scan->bm_bitmap &= ~mask;
1783 scan->bm_bitmap |= pmask << 1;
1784 } else {
1785 scan->bm_bitmap &= ~mask;
1786 scan->bm_bitmap |= pmask;
1787 }
1788 } else {
1789 /*
1790 * If no free blocks are present mark the
1791 * meta node as all-allocated/initialized.
1792 * A return code of -EDOM will mark the
1793 * meta node as all-allocated/uninitialized.
1794 *
1795 * This can be really confusing. bl_inverted
1796 * has no function here because we are
1797 * ALREADY known to be in an initialized
1798 */
1799 n = live->config->bl_radix_recover(
1800 live->info,
1801 blk, radix, count);
1802 if (n == -EDOM) {
1803 scan->bm_bitmap &= ~mask;
1804 } else if (n >= 0) {
1805 live->meta->bm_alist_freeblks += n;
1806 if (n == 0) {
1807 scan->bm_bitmap &= ~mask;
1808 scan->bm_bitmap |= pmask << 1;
1809 } else {
1810 scan->bm_bitmap &= ~mask;
1811 scan->bm_bitmap |= pmask;
1812 }
1813 } else {
1814 info->error = n;
1815 }
1816 }
1817 count = 0;
1818 } else if (next_skip) {
1819 /*
1820 * Add terminator. The terminator eats the meta
1821 * node at scan[i]. There is only ONE terminator,
1822 * make sure we don't write out any more (set count to
1823 * -1) or we may overflow our allocation.
1824 */
1825 if (count == 0) {
1826 scan[i].bm_bighint = (int32_t)-1;
1827 count = -1;
1828 }
1829 scan->bm_bitmap &= ~mask; /* all-allocated/uni */
1830 } else {
1831 scan->bm_bitmap &= ~mask; /* all-allocated/uni */
1832 }
1833 mask <<= 2;
1834 pmask <<= 2;
1835 blk += radix;
1836 }
1837 }
1838
1839 #ifdef ALIST_DEBUG
1840
1841 static void
1842 hammer_alst_radix_print(hammer_alist_t live, hammer_almeta_t scan,
1843 int32_t blk, int32_t radix, int skip, int tab)
1844 {
1845 int i;
1846 int next_skip;
1847 int lastState = 0;
1848 u_int32_t mask;
1849
1850 if (skip == 1 && live->config->bl_terminal) {
1851 kprintf(
1852 "%*.*s(%04x,%d): bitmap %08x big=%d\n",
1853 tab, tab, "",
1854 blk, radix,
1855 scan->bm_bitmap,
1856 scan->bm_bighint
1857 );
1858 return;
1859 }
1860
1861 if (scan->bm_bitmap == 0) {
1862 kprintf(
1863 "%*.*s(%04x,%d) ALL ALLOCATED\n",
1864 tab, tab, "",
1865 blk,
1866 radix
1867 );
1868 return;
1869 }
1870 if (scan->bm_bitmap == (u_int32_t)-1) {
1871 kprintf(
1872 "%*.*s(%04x,%d) ALL FREE\n",
1873 tab, tab, "",
1874 blk,
1875 radix
1876 );
1877 return;
1878 }
1879
1880 kprintf(
1881 "%*.*s(%04x,%d): %s (%d) bitmap=%08x big=%d {\n",
1882 tab, tab, "",
1883 blk, radix,
1884 (skip == 1 ? "LAYER" : "subtree"),
1885 radix,
1886 scan->bm_bitmap,
1887 scan->bm_bighint
1888 );
1889
1890 radix /= HAMMER_ALIST_META_RADIX;
1891 tab += 4;
1892 mask = 0x00000003;
1893
1894 if (skip == 1) {
1895 for (i = 0; i < HAMMER_ALIST_META_RADIX; ++i) {
1896 if ((scan->bm_bitmap & mask) == mask) {
1897 kprintf(
1898 "%*.*s(%04x,%d): ALL FREE\n",
1899 tab, tab, "",
1900 blk, radix
1901 );
1902 } else if ((scan->bm_bitmap & mask) == 0) {
1903 kprintf(
1904 "%*.*s(%04x,%d): ALL ALLOCATED\n",
1905 tab, tab, "",
1906 blk, radix
1907 );
1908 } else {
1909 live->config->bl_radix_print(
1910 live->info, blk, radix, tab);
1911 }
1912 blk += radix;
1913 mask <<= 2;
1914 }
1915 } else {
1916 next_skip = ((u_int)(skip - 1) / HAMMER_ALIST_META_RADIX);
1917
1918 for (i = 1; i < skip; i += next_skip) {
1919 KKASSERT(mask != 0);
1920 if (scan[i].bm_bighint == (int32_t)-1) {
1921 kprintf(
1922 "%*.*s(%04x,%d): Terminator\n",
1923 tab, tab, "",
1924 blk, radix
1925 );
1926 lastState = 0;
1927 break;
1928 }
1929 if ((scan->bm_bitmap & mask) == mask) {
1930 kprintf(
1931 "%*.*s(%04x,%d): ALL FREE\n",
1932 tab, tab, "",
1933 blk, radix
1934 );
1935 } else if ((scan->bm_bitmap & mask) == 0) {
1936 kprintf(
1937 "%*.*s(%04x,%d): ALL ALLOCATED\n",
1938 tab, tab, "",
1939 blk, radix
1940 );
1941 } else {
1942 hammer_alst_radix_print(
1943 live,
1944 &scan[i],
1945 blk,
1946 radix,
1947 next_skip,
1948 tab
1949 );
1950 }
1951 blk += radix;
1952 mask <<= 2;
1953 }
1954 }
1955 tab -= 4;
1956
1957 kprintf(
1958 "%*.*s}\n",
1959 tab, tab, ""
1960 );
1961 }
1962
1963 #endif
1964
1965 #ifdef ALIST_DEBUG
1966
1967 static struct hammer_alist_live **layers; /* initialized by main */
1968 static int32_t layer_radix = -1;
1969
1970 /*
1971 * Initialize a zone.
1972 *
1973 * If allocating is non-zero this init is being called when transitioning out
1974 * of an all-free state. Allocate the zone and mark the whole mess as being
1975 * free so the caller can then allocate out of this zone.
1976 *
1977 * If freeing this init is being called when transitioning out of an
1978 * initial all-allocated (00) state. Allocate the zone but leave the whole
1979 * mess left all-allocated. The caller will then free the appropriate range.
1980 */
1981 static
1982 int
1983 debug_radix_init(void *info, int32_t blk, int32_t radix,
1984 enum hammer_alloc_state state)
1985 {
1986 hammer_alist_t layer;
1987 int layer_no = blk / layer_radix;
1988
1989 printf("lower layer: init (%04x,%d) layer_radix=%d\n",
1990 blk, radix, layer_radix);
1991 KKASSERT(layer_radix == radix);
1992 KKASSERT(layers[layer_no] == NULL);
1993 layer = layers[layer_no] = hammer_alist_create(radix, 1, NULL, state);
1994 return(0);
1995 }
1996
1997 static
1998 int32_t
1999 debug_radix_recover(void *info, int32_t blk, int32_t radix, int32_t count)
2000 {
2001 hammer_alist_t layer;
2002 int layer_no = blk / layer_radix;
2003 int32_t n;
2004
2005 KKASSERT(layer_radix == radix);
2006 KKASSERT(layers[layer_no] != NULL);
2007 layer = layers[layer_no];
2008 n = hammer_alist_recover(layer, blk, 0, count);
2009 printf("Recover layer %d blk %d result %d/%d\n",
2010 layer_no, blk, n, count);
2011 return(n);
2012 }
2013
2014 static
2015 int32_t
2016 debug_radix_find(void *info, int32_t blk, int32_t radix, int32_t atblk,
2017 int flags)
2018 {
2019 hammer_alist_t layer;
2020 int layer_no = blk / layer_radix;
2021 int32_t res;
2022
2023 KKASSERT(layer_radix == radix);
2024 KKASSERT(layers[layer_no] != NULL);
2025 layer = layers[layer_no];
2026 res = hammer_alist_find(layer, atblk - blk, radix, flags);
2027 if (res != HAMMER_ALIST_BLOCK_NONE)
2028 res += blk;
2029 return(res);
2030 }
2031
2032 /*
2033 * This is called when a zone becomes entirely free, typically after a
2034 * call to debug_radix_free() has indicated that the entire zone is now
2035 * free.
2036 */
2037 static
2038 int
2039 debug_radix_destroy(void *info, int32_t blk, int32_t radix)
2040 {
2041 hammer_alist_t layer;
2042 int layer_no = blk / layer_radix;
2043
2044 printf("lower layer: destroy (%04x,%d)\n", blk, radix);
2045 layer = layers[layer_no];
2046 KKASSERT(layer != NULL);
2047 hammer_alist_destroy(layer, NULL);
2048 layers[layer_no] = NULL;
2049 return(0);
2050 }
2051
2052
2053 static
2054 int32_t
2055 debug_radix_alloc_fwd(void *info, int32_t blk, int32_t radix,
2056 int32_t count, int32_t atblk, int32_t *fullp)
2057 {
2058 hammer_alist_t layer = layers[blk / layer_radix];
2059 int32_t r;
2060
2061 r = hammer_alist_alloc_fwd(layer, count, atblk - blk);
2062 *fullp = hammer_alist_isfull(layer);
2063 if (r != HAMMER_ALIST_BLOCK_NONE)
2064 r += blk;
2065 return(r);
2066 }
2067
2068 static
2069 int32_t
2070 debug_radix_alloc_rev(void *info, int32_t blk, int32_t radix,
2071 int32_t count, int32_t atblk, int32_t *fullp)
2072 {
2073 hammer_alist_t layer = layers[blk / layer_radix];
2074 int32_t r;
2075
2076 r = hammer_alist_alloc_rev(layer, count, atblk - blk);
2077 *fullp = hammer_alist_isfull(layer);
2078 if (r != HAMMER_ALIST_BLOCK_NONE)
2079 r += blk;
2080 return(r);
2081 }
2082
2083 static
2084 void
2085 debug_radix_free(void *info, int32_t blk, int32_t radix,
2086 int32_t base_blk, int32_t count, int32_t *emptyp)
2087 {
2088 int layer_no = blk / layer_radix;
2089 hammer_alist_t layer = layers[layer_no];
2090
2091 KKASSERT(layer);
2092 hammer_alist_free(layer, base_blk, count);
2093 *emptyp = hammer_alist_isempty(layer);
2094 }
2095
2096 static
2097 void
2098 debug_radix_print(void *info, int32_t blk, int32_t radix, int tab)
2099 {
2100 hammer_alist_t layer = layers[blk / layer_radix];
2101
2102 hammer_alist_print(layer, tab);
2103 }
2104
2105 int
2106 main(int ac, char **av)
2107 {
2108 int32_t size = -1;
2109 int i;
2110 hammer_alist_t live;
2111 hammer_almeta_t meta = NULL;
2112
2113 for (i = 1; i < ac; ++i) {
2114 const char *ptr = av[i];
2115 if (*ptr != '-') {
2116 if (size == -1)
2117 size = strtol(ptr, NULL, 0);
2118 else if (layer_radix == -1)
2119 layer_radix = strtol(ptr, NULL, 0);
2120 else
2121 ;
2122 continue;
2123 }
2124 ptr += 2;
2125 fprintf(stderr, "Bad option: %s\n", ptr - 2);
2126 exit(1);
2127 }
2128 if (size == -1)
2129 size = 1024;
2130 if (layer_radix == -1)
2131 layer_radix = 1; /* no second storage layer */
2132 if ((size ^ (size - 1)) != (size << 1) - 1) {
2133 fprintf(stderr, "size must be a power of 2\n");
2134 exit(1);
2135 }
2136 if ((layer_radix ^ (layer_radix - 1)) != (layer_radix << 1) - 1) {
2137 fprintf(stderr, "the second layer radix must be a power of 2\n");
2138 exit(1);
2139 }
2140
2141 live = hammer_alist_create(size, layer_radix, NULL,
2142 HAMMER_ASTATE_ALLOC);
2143 layers = calloc(size, sizeof(hammer_alist_t));
2144
2145 printf("A-LIST TEST %d blocks, first-layer radix %d, "
2146 "second-layer radix %d\n",
2147 size, live->config->bl_radix / layer_radix, layer_radix);
2148
2149 live->config->bl_radix_init = debug_radix_init;
2150 live->config->bl_radix_recover = debug_radix_recover;
2151 live->config->bl_radix_find = debug_radix_find;
2152 live->config->bl_radix_destroy = debug_radix_destroy;
2153 live->config->bl_radix_alloc_fwd = debug_radix_alloc_fwd;
2154 live->config->bl_radix_alloc_rev = debug_radix_alloc_rev;
2155 live->config->bl_radix_free = debug_radix_free;
2156 live->config->bl_radix_print = debug_radix_print;
2157
2158 hammer_alist_free(live, 0, size);
2159
2160 for (;;) {
2161 char buf[1024];
2162 int32_t da = 0;
2163 int32_t count = 0;
2164 int32_t atblk;
2165 int32_t blk;
2166 int flags;
2167
2168 kprintf("%d/%d> ",
2169 live->meta->bm_alist_freeblks, size);
2170 fflush(stdout);
2171 if (fgets(buf, sizeof(buf), stdin) == NULL)
2172 break;
2173 switch(buf[0]) {
2174 case 'p':
2175 hammer_alist_print(live, 0);
2176
2177 flags = 0;
2178 if (buf[1] == 'i' || (buf[1] && buf[2] == 'i'))
2179 flags |= HAMMER_ALIST_FIND_INITONLY;
2180 if (buf[1] == 'm' || (buf[1] && buf[2] == 'm'))
2181 flags |= HAMMER_ALIST_FIND_NOSTACK;
2182 atblk = 0;
2183 kprintf("allocated: ");
2184 while ((atblk = hammer_alist_find(live, atblk, size, flags)) != HAMMER_ALIST_BLOCK_NONE) {
2185 kprintf(" %d", atblk);
2186 ++atblk;
2187 }
2188 kprintf("\n");
2189 break;
2190 case 'a':
2191 atblk = 0;
2192 if (sscanf(buf + 1, "%d %d", &count, &atblk) >= 1) {
2193 blk = hammer_alist_alloc_fwd(live, count, atblk);
2194 kprintf(" R=%04x\n", blk);
2195 } else {
2196 kprintf("?\n");
2197 }
2198 break;
2199 case 'r':
2200 atblk = HAMMER_ALIST_BLOCK_MAX;
2201 if (sscanf(buf + 1, "%d %d", &count, &atblk) >= 1) {
2202 blk = hammer_alist_alloc_rev(live, count, atblk);
2203 kprintf(" R=%04x\n", blk);
2204 } else {
2205 kprintf("?\n");
2206 }
2207 break;
2208 case 'f':
2209 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) {
2210 hammer_alist_free(live, da, count);
2211 if (hammer_alist_isempty(live))
2212 kprintf("a-list is now 100%% empty\n");
2213 } else {
2214 kprintf("?\n");
2215 }
2216 break;
2217 case 'R':
2218 {
2219 int n;
2220
2221 n = hammer_alist_recover(live, 0, 0,
2222 live->meta->bm_alist_base_freeblks);
2223 if (n < 0)
2224 kprintf("recover: error %d\n", -n);
2225 else
2226 kprintf("recover: %d free\n", n);
2227 }
2228 break;
2229 case '?':
2230 case 'h':
2231 puts(
2232 "p[i][m] -print (initialized only) (meta-only)\n"
2233 "a %d -allocate\n"
2234 "r %d -allocate reverse\n"
2235 "f %x %d -free\n"
2236 "R -recovery a-list\n"
2237 "h/? -help"
2238 );
2239 break;
2240 default:
2241 kprintf("?\n");
2242 break;
2243 }
2244 }
2245 return(0);
2246 }
2247
2248 void
2249 panic(const char *ctl, ...)
2250 {
2251 __va_list va;
2252
2253 __va_start(va, ctl);
2254 vfprintf(stderr, ctl, va);
2255 fprintf(stderr, "\n");
2256 __va_end(va);
2257 exit(1);
2258 }
2259
2260 #endif
2261
DragonFly BSD