kernel - Correct unaligned results in alist_free_info()
[dragonfly.git] / sys / kern / subr_alist.c
CommitLineData
3ae3b454
MD
1/*
2 * ALIST.C - Bitmap allocator/deallocator, using a radix tree with hinting.
3 * Unlimited-size allocations, power-of-2 only, power-of-2
4 * aligned results only.
5 *
6 * Copyright (c) 2007 The DragonFly Project. All rights reserved.
7 *
8 * This code is derived from software contributed to The DragonFly Project
9 * by Matthew Dillon <dillon@backplane.com>
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 *
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in
19 * the documentation and/or other materials provided with the
20 * distribution.
21 * 3. Neither the name of The DragonFly Project nor the names of its
22 * contributors may be used to endorse or promote products derived
23 * from this software without specific, prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
28 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
29 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
30 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
31 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
32 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
33 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
34 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
35 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
36 * SUCH DAMAGE.
3ae3b454
MD
37 */
38/*
39 * This module has been adapted from the BLIST module, which was written
40 * by Matthew Dillon many years ago.
41 *
42 * This module implements a general power-of-2 bitmap allocator/deallocator.
43 * All allocations must be in powers of 2 and will return similarly aligned
44 * results. The module does not try to interpret the meaning of a 'block'
45 * other then to return ALIST_BLOCK_NONE on an allocation failure.
46 *
47 * A maximum of 2 billion blocks is supported so, for example, if one block
48 * represented 64 bytes a maximally sized ALIST would represent
49 * 128 gigabytes.
50 *
51 * A radix tree is used to maintain the bitmap and layed out in a manner
52 * similar to the blist code. Meta nodes use a radix of 16 and 2 bits per
53 * block while leaf nodes use a radix of 32 and 1 bit per block (stored in
54 * a 32 bit bitmap field). Both meta and leaf nodes have a hint field.
55 * This field gives us a hint as to the largest free contiguous range of
56 * blocks under the node. It may contain a value that is too high, but
57 * will never contain a value that is too low. When the radix tree is
58 * searched, allocation failures in subtrees update the hint.
59 *
60 * The radix tree is layed out recursively using a linear array. Each meta
61 * node is immediately followed (layed out sequentially in memory) by
62 * ALIST_META_RADIX lower level nodes. This is a recursive structure but one
63 * that can be easily scanned through a very simple 'skip' calculation. In
64 * order to support large radixes, portions of the tree may reside outside our
65 * memory allocation. We handle this with an early-terminate optimization
66 * in the meta-node. The memory allocation is only large enough to cover
67 * the number of blocks requested at creation time even if it must be
68 * encompassed in larger root-node radix.
69 *
70 * This code can be compiled stand-alone for debugging.
71 */
72
73#ifdef _KERNEL
74
75#include <sys/param.h>
76#include <sys/systm.h>
77#include <sys/lock.h>
78#include <sys/kernel.h>
79#include <sys/alist.h>
80#include <sys/malloc.h>
81#include <vm/vm.h>
82#include <vm/vm_object.h>
83#include <vm/vm_kern.h>
84#include <vm/vm_extern.h>
85#include <vm/vm_page.h>
86
87#else
88
89#ifndef ALIST_NO_DEBUG
90#define ALIST_DEBUG
91#endif
92
93#include <sys/types.h>
94#include <stdio.h>
95#include <assert.h>
96#include <string.h>
97#include <stdlib.h>
98#include <stdarg.h>
99
100#define kmalloc(a,b,c) malloc(a)
101#define kfree(a,b) free(a)
102#define kprintf printf
103#define KKASSERT(exp) assert(exp)
104struct malloc_type;
105
3ae3b454
MD
106#include <sys/alist.h>
107
108void panic(const char *ctl, ...);
109
110#endif
111
112/*
113 * static support functions
114 */
115
7552e9ee
MD
116static alist_blk_t alst_leaf_alloc(almeta_t *scan, alist_blk_t blk,
117 alist_blk_t start, alist_blk_t count);
118static alist_blk_t alst_meta_alloc(almeta_t *scan, alist_blk_t blk,
119 alist_blk_t start, alist_blk_t count,
120 alist_blk_t radix, alist_blk_t skip);
121static void alst_leaf_free(almeta_t *scan, alist_blk_t relblk,
122 alist_blk_t count);
123static void alst_meta_free(almeta_t *scan, alist_blk_t freeBlk,
124 alist_blk_t count, alist_blk_t radix,
125 alist_blk_t skip, alist_blk_t blk);
126static alist_blk_t alst_radix_init(almeta_t *scan, alist_blk_t blk,
127 alist_blk_t radix, alist_blk_t skip,
128 alist_blk_t count);
3ae3b454 129#ifndef _KERNEL
7552e9ee
MD
130static void alst_radix_print(almeta_t *scan, alist_blk_t blk,
131 alist_blk_t radix, alist_blk_t skip,
132 int tab);
3ae3b454
MD
133#endif
134
135/*
7552e9ee
MD
136 * Create a alist capable of handling up to the specified number of blocks.
137 * Blocks must be greater then 0 but does not have to be a power of 2.
3ae3b454 138 *
7552e9ee
MD
139 * The smallest alist consists of a single leaf node capable of
140 * managing ALIST_BMAP_RADIX blocks.
3ae3b454 141 */
3ae3b454 142alist_t
7552e9ee 143alist_create(alist_blk_t blocks, struct malloc_type *mtype)
3ae3b454
MD
144{
145 alist_t bl;
7552e9ee
MD
146 alist_blk_t radix;
147 alist_blk_t skip = 0;
3ae3b454
MD
148
149 /*
150 * Calculate radix and skip field used for scanning.
151 */
152 radix = ALIST_BMAP_RADIX;
153
154 while (radix < blocks) {
155 radix *= ALIST_META_RADIX;
156 skip = (skip + 1) * ALIST_META_RADIX;
157 }
158
0c374e73 159 bl = kmalloc(sizeof(struct alist), mtype, M_WAITOK | M_ZERO);
3ae3b454
MD
160
161 bl->bl_blocks = blocks;
162 bl->bl_radix = radix;
163 bl->bl_skip = skip;
7552e9ee
MD
164 bl->bl_rootblks = 1 + alst_radix_init(NULL, 0, bl->bl_radix,
165 bl->bl_skip, blocks);
166 bl->bl_root = kmalloc(sizeof(almeta_t) * bl->bl_rootblks,
167 mtype, M_WAITOK);
3ae3b454
MD
168
169#if defined(ALIST_DEBUG)
170 kprintf(
171 "ALIST representing %d blocks (%d MB of swap)"
463a6bdd 172 ", requiring %dK (%d bytes) of ram\n",
3ae3b454
MD
173 bl->bl_blocks,
174 bl->bl_blocks * 4 / 1024,
463a6bdd
MD
175 (bl->bl_rootblks * sizeof(almeta_t) + 1023) / 1024,
176 (bl->bl_rootblks * sizeof(almeta_t))
3ae3b454
MD
177 );
178 kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
179#endif
7552e9ee 180 alst_radix_init(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, blocks);
3ae3b454
MD
181
182 return(bl);
183}
184
7552e9ee
MD
185void
186alist_init(alist_t bl, alist_blk_t blocks,
187 almeta_t *records, alist_blk_t nrecords)
188{
189 alist_blk_t radix;
190 alist_blk_t skip = 0;
191
192 /*
193 * Calculate radix and skip field used for scanning.
194 */
195 radix = ALIST_BMAP_RADIX;
196
197 while (radix < blocks) {
198 radix *= ALIST_META_RADIX;
199 skip = (skip + 1) * ALIST_META_RADIX;
200 }
201 bzero(bl, sizeof(*bl));
202
203 bl->bl_blocks = blocks;
204 bl->bl_radix = radix;
205 bl->bl_skip = skip;
206 bl->bl_rootblks = 1 + alst_radix_init(NULL, 0, bl->bl_radix,
207 bl->bl_skip, blocks);
208 KKASSERT(bl->bl_rootblks <= nrecords);
209 bl->bl_root = records;
210
211#if defined(ALIST_DEBUG)
212 kprintf(
213 "ALIST representing %d blocks (%d MB of swap)"
214 ", requiring %dK (%d bytes) of ram\n",
215 bl->bl_blocks,
216 bl->bl_blocks * 4 / 1024,
217 (bl->bl_rootblks * sizeof(almeta_t) + 1023) / 1024,
218 (bl->bl_rootblks * sizeof(almeta_t))
219 );
220 kprintf("ALIST raw radix tree contains %d records\n", bl->bl_rootblks);
221#endif
222 alst_radix_init(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, blocks);
223}
224
3ae3b454
MD
225void
226alist_destroy(alist_t bl, struct malloc_type *mtype)
227{
228 kfree(bl->bl_root, mtype);
229 kfree(bl, mtype);
230}
231
232/*
7552e9ee
MD
233 * Reserve space in the block bitmap. Return the base of a contiguous
234 * region or ALIST_BLOCK_NONE if space could not be allocated.
235 *
236 * This nominally allocates a power-of-2 number of blocks. However,
237 * non-powers of 2 are accepted and implemented by first allocating
238 * the nearest power of 2 and then freeing the remainder.
3ae3b454 239 */
7552e9ee
MD
240alist_blk_t
241alist_alloc(alist_t bl, alist_blk_t start, alist_blk_t count)
3ae3b454 242{
7552e9ee 243 alist_blk_t blk = ALIST_BLOCK_NONE;
3ae3b454 244
7552e9ee
MD
245 /*
246 * Check non power-of-2
247 */
248 KKASSERT(count);
249 if ((count | (count - 1)) != (count << 1) - 1) {
250 alist_blk_t ncount = (count < 256) ? 1 : 256;
251 while (ncount < count)
252 ncount <<= 1;
253 blk = alist_alloc(bl, start, ncount);
254 if (blk != ALIST_BLOCK_NONE)
255 alist_free(bl, blk + count, ncount - count);
256 return (blk);
257 }
3ae3b454 258
7552e9ee
MD
259 /*
260 * Power of 2
261 */
3ae3b454 262 if (bl && count < bl->bl_radix) {
7552e9ee
MD
263 if (bl->bl_radix == ALIST_BMAP_RADIX) {
264 blk = alst_leaf_alloc(bl->bl_root, 0, start, count);
265 } else {
266 blk = alst_meta_alloc(bl->bl_root, 0, start, count,
267 bl->bl_radix, bl->bl_skip);
268 }
3ae3b454
MD
269 if (blk != ALIST_BLOCK_NONE)
270 bl->bl_free -= count;
271 }
272 return(blk);
273}
274
275/*
7552e9ee
MD
276 * Free up space in the block bitmap. The starting block and count do not
277 * need to be power-of-2 aligned. The related blocks must be in an allocated
278 * state.
3ae3b454 279 */
3ae3b454 280void
7552e9ee 281alist_free(alist_t bl, alist_blk_t blkno, alist_blk_t count)
3ae3b454
MD
282{
283 if (bl) {
284 KKASSERT(blkno + count <= bl->bl_blocks);
7552e9ee 285 if (bl->bl_radix == ALIST_BMAP_RADIX) {
3ae3b454 286 alst_leaf_free(bl->bl_root, blkno, count);
7552e9ee
MD
287 } else {
288 alst_meta_free(bl->bl_root, blkno, count,
289 bl->bl_radix, bl->bl_skip, 0);
290 }
3ae3b454
MD
291 bl->bl_free += count;
292 }
293}
294
7552e9ee
MD
295/*
296 * Returns the current total number of free blocks and the
297 * approximate trailing largest contiguous free block available.
298 */
299alist_blk_t
300alist_free_info(alist_t bl, alist_blk_t *startp, alist_blk_t *countp)
301{
302 alist_blk_t radix = bl->bl_radix;
303 alist_blk_t skip = bl->bl_skip;
304 alist_blk_t next_skip;
305 alist_blk_t i;
7552e9ee
MD
306 alist_bmap_t mask;
307 almeta_t *scan = bl->bl_root;
308
309 *startp = 0;
310 *countp = 0;
311
312 while (radix != ALIST_BMAP_RADIX) {
313 radix /= ALIST_META_RADIX;
314 next_skip = skip / ALIST_META_RADIX;
315
316 /*
317 * Find the biggest fully allocated chunk.
318 */
319 for (i = ALIST_META_RADIX - 1; i != ALIST_BLOCK_NONE; --i) {
320 mask = (scan->bm_bitmap >> (i * 2)) & 3;
321 if (mask == 0) {
322 /*
323 * All allocated, continue the loop
324 */
325 continue;
326 }
327 if (mask == 1) {
328 /*
329 * Partially allocated, push into this guy
330 */
331 break;
332 }
333 if (mask == 2) {
334 /*
335 * Unknown state
336 */
337 return(bl->bl_free);
338 }
339 /*
340 * All free, we can return the chunk.
341 */
342 *startp += i * radix;
343 *countp = radix;
344 return(bl->bl_free);
345 }
346
347 /*
348 * If we failed to find anything stop here, otherwise push
349 * in.
350 */
351 if (i == ALIST_BLOCK_NONE)
352 return(bl->bl_free);
353 *startp += i * radix;
354 scan += 1 + next_skip * i;
355 skip = next_skip - 1;
356 }
28efdceb
MD
357
358 /*
359 * If we got all the way down to a leaf node locate the last block,
360 * power-of-2 aligned and power-of-2 sized. Well, the easiest way
361 * to deal with this is to just return 1 block.
362 */
7552e9ee
MD
363 if (radix == ALIST_BMAP_RADIX) {
364 mask = scan->bm_bitmap;
365 for (i = ALIST_BMAP_RADIX - 1; i != ALIST_BLOCK_NONE; --i) {
366 if ((mask & ((alist_bmap_t)1U << i)))
367 break;
368 }
369
370 /*
371 * did not find free entry
372 */
28efdceb 373 if (i == ALIST_BLOCK_NONE)
7552e9ee 374 return(bl->bl_free);
7552e9ee
MD
375
376 /*
28efdceb 377 * Return one block.
7552e9ee 378 */
28efdceb
MD
379 *startp += i;
380 *countp = 1;
7552e9ee
MD
381 return(bl->bl_free);
382 }
383 return(bl->bl_free);
384}
385
3ae3b454
MD
386#ifdef ALIST_DEBUG
387
388/*
389 * alist_print() - dump radix tree
390 */
391
392void
393alist_print(alist_t bl)
394{
395 kprintf("ALIST {\n");
396 alst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4);
397 kprintf("}\n");
398}
399
400#endif
401
402/************************************************************************
403 * ALLOCATION SUPPORT FUNCTIONS *
404 ************************************************************************
405 *
406 * These support functions do all the actual work. They may seem
407 * rather longish, but that's because I've commented them up. The
408 * actual code is straight forward.
409 *
410 */
411
412/*
413 * alist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap).
414 *
415 * This is the core of the allocator and is optimized for the 1 block
416 * and the ALIST_BMAP_RADIX block allocation cases. Other cases are
417 * somewhat slower. The 1 block allocation case is log2 and extremely
418 * quick.
7552e9ee
MD
419 *
420 * mask bit is 0 allocated, not available
421 * mask bit is 1 free, available for allocation
3ae3b454
MD
422 */
423
7552e9ee
MD
424static alist_blk_t
425alst_leaf_alloc(almeta_t *scan, alist_blk_t blk, alist_blk_t start,
426 alist_blk_t count)
427{
428 alist_bmap_t orig = scan->bm_bitmap;
429
430 /*
431 * Allocate only beyond the start point. Mask to 0 the low bits
432 * below start. If start == blk no bits get cleared so don't
433 * bother.
434 */
435 if (start >= blk + ALIST_BMAP_RADIX)
436 return(ALIST_BLOCK_NONE);
437
438 if (start > blk && start < blk + ALIST_BMAP_RADIX)
439 orig &= ~(((alist_bmap_t)1U << (start - blk)) - 1);
440
441 start &= ALIST_BMAP_RADIX - 1;
3ae3b454
MD
442
443 /*
444 * Optimize bitmap all-allocated case. Also, count = 1
445 * case assumes at least 1 bit is free in the bitmap, so
446 * we have to take care of this case here.
447 */
448 if (orig == 0) {
7552e9ee
MD
449 if (start <= blk)
450 scan->bm_bighint = 0;
3ae3b454
MD
451 return(ALIST_BLOCK_NONE);
452 }
453
454 /*
455 * Optimized code to allocate one bit out of the bitmap
456 */
457 if (count == 1) {
7552e9ee
MD
458 alist_bmap_t mask;
459 alist_blk_t j = ALIST_BMAP_RADIX/2;
460 alist_blk_t r = 0;
3ae3b454 461
7552e9ee 462 mask = (alist_bmap_t)-1 >> (ALIST_BMAP_RADIX/2);
3ae3b454
MD
463
464 while (j) {
465 if ((orig & mask) == 0) {
466 r += j;
467 orig >>= j;
468 }
469 j >>= 1;
470 mask >>= j;
471 }
472 scan->bm_bitmap &= ~(1 << r);
473 return(blk + r);
474 }
475
476 /*
477 * non-optimized code to allocate N bits out of the bitmap.
478 * The more bits, the faster the code runs. It will run
479 * the slowest allocating 2 bits, but since there aren't any
480 * memory ops in the core loop (or shouldn't be, anyway),
481 * you probably won't notice the difference.
482 *
483 * Similar to the blist case, the alist code also requires
484 * allocations to be power-of-2 sized and aligned to the
485 * size of the allocation, which simplifies the algorithm.
486 */
487 {
7552e9ee
MD
488 alist_blk_t j;
489 alist_blk_t n = ALIST_BMAP_RADIX - count;
490 alist_bmap_t mask;
3ae3b454 491
7552e9ee 492 mask = (alist_bmap_t)-1 >> n;
3ae3b454
MD
493
494 for (j = 0; j <= n; j += count) {
495 if ((orig & mask) == mask) {
496 scan->bm_bitmap &= ~mask;
497 return(blk + j);
498 }
499 mask = mask << count;
500 }
501 }
502
503 /*
7552e9ee
MD
504 * We couldn't allocate count in this subtree, update bighint
505 * if we were able to check the entire node.
3ae3b454 506 */
7552e9ee
MD
507 if (start <= blk)
508 scan->bm_bighint = count - 1;
3ae3b454
MD
509 return(ALIST_BLOCK_NONE);
510}
511
512/*
7552e9ee
MD
513 * Attempt to allocate at a meta node. If we can't, we update
514 * bighint and return a failure. Updating bighint optimize future
515 * calls that hit this node. We have to check for our collapse cases
516 * and we have a few optimizations strewn in as well.
3ae3b454 517 */
7552e9ee
MD
518static alist_blk_t
519alst_meta_alloc(almeta_t *scan, alist_blk_t blk, alist_blk_t start,
520 alist_blk_t count, alist_blk_t radix, alist_blk_t skip)
521{
522 alist_blk_t i;
523 alist_bmap_t mask;
524 alist_bmap_t pmask;
525 alist_blk_t next_skip = ((u_int)skip / ALIST_META_RADIX);
526 alist_blk_t orig_blk;
3ae3b454
MD
527
528 /*
529 * ALL-ALLOCATED special case
530 */
531 if (scan->bm_bitmap == 0) {
532 scan->bm_bighint = 0;
533 return(ALIST_BLOCK_NONE);
534 }
535
536 radix /= ALIST_META_RADIX;
537
538 /*
539 * Radix now represents each bitmap entry for this meta node. If
540 * the number of blocks being allocated can be fully represented,
541 * we allocate directly out of this meta node.
542 *
543 * Meta node bitmaps use 2 bits per block.
544 *
545 * 00 ALL-ALLOCATED
546 * 01 PARTIALLY-FREE/PARTIALLY-ALLOCATED
547 * 10 (RESERVED)
548 * 11 ALL-FREE
549 */
550 if (count >= radix) {
7552e9ee
MD
551 alist_blk_t n = count / radix * 2; /* number of bits */
552 alist_blk_t j;
3ae3b454 553
7552e9ee 554 mask = (alist_bmap_t)-1 >> (ALIST_BMAP_RADIX - n);
3ae3b454 555 for (j = 0; j < ALIST_META_RADIX; j += n / 2) {
7552e9ee
MD
556 if ((scan->bm_bitmap & mask) == mask &&
557 blk + j * radix >= start) {
3ae3b454 558 scan->bm_bitmap &= ~mask;
a03c3701 559 return(blk + j * radix);
3ae3b454
MD
560 }
561 mask <<= n;
562 }
7552e9ee 563 if (scan->bm_bighint >= count && start <= blk)
3ae3b454
MD
564 scan->bm_bighint = count >> 1;
565 return(ALIST_BLOCK_NONE);
566 }
567
568 /*
569 * If not we have to recurse.
570 */
571 mask = 0x00000003;
572 pmask = 0x00000001;
7552e9ee 573 orig_blk = blk;
3ae3b454 574 for (i = 1; i <= skip; i += next_skip) {
7552e9ee 575 if (scan[i].bm_bighint == (alist_blk_t)-1) {
3ae3b454
MD
576 /*
577 * Terminator
578 */
579 break;
580 }
4b25f870
MD
581
582 /*
583 * If the element is marked completely free (11), initialize
584 * the recursion.
585 */
3ae3b454 586 if ((scan->bm_bitmap & mask) == mask) {
7552e9ee 587 scan[i].bm_bitmap = (alist_bmap_t)-1;
3ae3b454 588 scan[i].bm_bighint = radix;
4b25f870 589 }
3ae3b454 590
4b25f870
MD
591 if ((scan->bm_bitmap & mask) == 0) {
592 /*
593 * Object marked completely allocated, recursion
594 * contains garbage.
595 */
596 /* Skip it */
7552e9ee
MD
597 } else if (blk + radix <= start) {
598 /*
599 * Object does not contain or is not beyond our
600 * start point.
601 */
602 /* Skip it */
4b25f870 603 } else if (count <= scan[i].bm_bighint) {
3ae3b454 604 /*
7552e9ee
MD
605 * count fits in object. If successful and the
606 * deeper level becomes all allocated, mark our
607 * level as all-allocated.
3ae3b454 608 */
7552e9ee 609 alist_blk_t r;
3ae3b454 610 if (next_skip == 1) {
7552e9ee
MD
611 r = alst_leaf_alloc(&scan[i], blk, start,
612 count);
3ae3b454 613 } else {
7552e9ee
MD
614 r = alst_meta_alloc(&scan[i], blk, start,
615 count,
616 radix, next_skip - 1);
3ae3b454
MD
617 }
618 if (r != ALIST_BLOCK_NONE) {
619 if (scan[i].bm_bitmap == 0) {
620 scan->bm_bitmap &= ~mask;
621 } else {
622 scan->bm_bitmap &= ~mask;
623 scan->bm_bitmap |= pmask;
624 }
625 return(r);
626 }
4b25f870 627 }
3ae3b454
MD
628 blk += radix;
629 mask <<= 2;
630 pmask <<= 2;
631 }
632
633 /*
7552e9ee
MD
634 * We couldn't allocate count in this subtree, update bighint
635 * if we were able to check the entire node.
3ae3b454 636 */
7552e9ee 637 if (scan->bm_bighint >= count && start <= orig_blk)
3ae3b454
MD
638 scan->bm_bighint = count >> 1;
639 return(ALIST_BLOCK_NONE);
640}
641
642/*
7552e9ee 643 * Free allocated block from leaf bitmap
3ae3b454
MD
644 */
645static void
7552e9ee
MD
646alst_leaf_free(almeta_t *scan, alist_blk_t blk, alist_blk_t count)
647{
3ae3b454
MD
648 /*
649 * free some data in this bitmap
650 *
651 * e.g.
652 * 0000111111111110000
653 * \_________/\__/
654 * v n
655 */
7552e9ee
MD
656 alist_blk_t n = blk & (ALIST_BMAP_RADIX - 1);
657 alist_bmap_t mask;
3ae3b454 658
7552e9ee
MD
659 mask = ((alist_bmap_t)-1 << n) &
660 ((alist_bmap_t)-1 >> (ALIST_BMAP_RADIX - count - n));
3ae3b454
MD
661
662 if (scan->bm_bitmap & mask)
663 panic("alst_radix_free: freeing free block");
664 scan->bm_bitmap |= mask;
665
666 /*
667 * We could probably do a better job here. We are required to make
668 * bighint at least as large as the biggest contiguous block of
669 * data. If we just shoehorn it, a little extra overhead will
670 * be incured on the next allocation (but only that one typically).
671 */
672 scan->bm_bighint = ALIST_BMAP_RADIX;
673}
674
675/*
7552e9ee
MD
676 * Free allocated blocks from radix tree meta info. This support routine
677 * frees a range of blocks from the bitmap. The range must be entirely
678 * enclosed by this radix node. If a meta node, we break the range down
679 * recursively to free blocks in subnodes (which means that this code
680 * can free an arbitrary range whereas the allocation code cannot allocate
681 * an arbitrary range).
3ae3b454 682 */
3ae3b454 683static void
7552e9ee
MD
684alst_meta_free(almeta_t *scan, alist_blk_t freeBlk, alist_blk_t count,
685 alist_blk_t radix, alist_blk_t skip, alist_blk_t blk)
686{
687 alist_blk_t next_skip = ((u_int)skip / ALIST_META_RADIX);
688 alist_bmap_t mask;
689 alist_bmap_t pmask;
690 alist_blk_t i;
3ae3b454
MD
691
692 /*
693 * Break the free down into its components. Because it is so easy
694 * to implement, frees are not limited to power-of-2 sizes.
695 *
696 * Each block in a meta-node bitmap takes two bits.
697 */
698 radix /= ALIST_META_RADIX;
699
700 i = (freeBlk - blk) / radix;
701 blk += i * radix;
702 mask = 0x00000003 << (i * 2);
703 pmask = 0x00000001 << (i * 2);
704
705 i = i * next_skip + 1;
706
707 while (i <= skip && blk < freeBlk + count) {
7552e9ee 708 alist_blk_t v;
3ae3b454
MD
709
710 v = blk + radix - freeBlk;
711 if (v > count)
712 v = count;
713
7552e9ee 714 if (scan->bm_bighint == (alist_blk_t)-1)
3ae3b454
MD
715 panic("alst_meta_free: freeing unexpected range");
716
7552e9ee
MD
717 /*
718 * WARNING on bighint updates. When we free an element in
719 * a chunk if the chunk becomes wholely free it is possible
720 * that the whole node is now free, so bighint must be set
721 * to cover the whole node. Otherwise address-specific
722 * allocations may fail.
723 *
724 * We don't bother figuring out how much of the node is
725 * actually free in this case.
726 */
3ae3b454
MD
727 if (freeBlk == blk && count >= radix) {
728 /*
7552e9ee
MD
729 * The area being freed covers the entire block,
730 * assert that we are marked all-allocated and
731 * then mark it all-free.
3ae3b454 732 */
7552e9ee 733 KKASSERT((scan->bm_bitmap & mask) == 0);
3ae3b454 734 scan->bm_bitmap |= mask;
7552e9ee 735 scan->bm_bighint = radix * ALIST_META_RADIX;
3ae3b454 736 } else {
4b25f870
MD
737 /*
738 * If we were previously marked all-allocated, fix-up
739 * the next layer so we can recurse down into it.
740 */
741 if ((scan->bm_bitmap & mask) == 0) {
7552e9ee 742 scan[i].bm_bitmap = (alist_bmap_t)0;
4b25f870
MD
743 scan[i].bm_bighint = 0;
744 }
745
3ae3b454 746 /*
7552e9ee
MD
747 * Recursion case, then either mark all-free or
748 * partially free.
3ae3b454 749 */
7552e9ee 750 if (next_skip == 1) {
3ae3b454 751 alst_leaf_free(&scan[i], freeBlk, v);
7552e9ee
MD
752 } else {
753 alst_meta_free(&scan[i], freeBlk, v,
754 radix, next_skip - 1, blk);
755 }
756 if (scan[i].bm_bitmap == (alist_bmap_t)-1) {
3ae3b454 757 scan->bm_bitmap |= mask;
7552e9ee
MD
758 scan->bm_bighint = radix * ALIST_META_RADIX;
759 } else {
760 scan->bm_bitmap &= ~mask;
3ae3b454 761 scan->bm_bitmap |= pmask;
7552e9ee
MD
762 if (scan->bm_bighint < scan[i].bm_bighint)
763 scan->bm_bighint = scan[i].bm_bighint;
764 }
3ae3b454
MD
765 }
766 mask <<= 2;
767 pmask <<= 2;
768 count -= v;
769 freeBlk += v;
770 blk += radix;
771 i += next_skip;
772 }
773}
774
775/*
7552e9ee
MD
776 * Initialize our meta structures and bitmaps and calculate the exact
777 * amount of space required to manage 'count' blocks - this space may
778 * be considerably less then the calculated radix due to the large
779 * RADIX values we use.
3ae3b454 780 */
7552e9ee
MD
781static alist_blk_t
782alst_radix_init(almeta_t *scan, alist_blk_t blk, alist_blk_t radix,
783 alist_blk_t skip, alist_blk_t count)
3ae3b454 784{
7552e9ee
MD
785 alist_blk_t i;
786 alist_blk_t next_skip;
787 alist_bmap_t mask;
788 alist_bmap_t pmask;
789 alist_blk_t memindex;
3ae3b454
MD
790
791 /*
792 * Leaf node
793 */
794 if (radix == ALIST_BMAP_RADIX) {
795 if (scan) {
796 scan->bm_bighint = 0;
797 scan->bm_bitmap = 0;
798 }
7552e9ee 799 return(0);
3ae3b454
MD
800 }
801
802 /*
803 * Meta node. If allocating the entire object we can special
804 * case it. However, we need to figure out how much memory
805 * is required to manage 'count' blocks, so we continue on anyway.
806 */
3ae3b454
MD
807 if (scan) {
808 scan->bm_bighint = 0;
809 scan->bm_bitmap = 0;
810 }
7552e9ee 811 memindex = 0;
3ae3b454
MD
812
813 radix /= ALIST_META_RADIX;
7552e9ee 814 next_skip = skip / ALIST_META_RADIX;
3ae3b454
MD
815 mask = 0x00000003;
816 pmask = 0x00000001;
817
818 for (i = 1; i <= skip; i += next_skip) {
7552e9ee 819 if (count >= blk + radix) {
3ae3b454
MD
820 /*
821 * Allocate the entire object
822 */
7552e9ee
MD
823 memindex += alst_radix_init(((scan) ? &scan[i] : NULL),
824 blk, radix,
825 next_skip - 1, count);
3ae3b454 826 /* already marked as wholely allocated */
7552e9ee 827 } else if (count > blk) {
3ae3b454 828 /*
7552e9ee
MD
829 * Allocate a partial object, well it's really
830 * all-allocated, we just aren't allowed to
831 * free the whole thing.
3ae3b454 832 */
7552e9ee
MD
833 memindex += alst_radix_init(((scan) ? &scan[i] : NULL),
834 blk, radix,
835 next_skip - 1, count);
836 /* already marked as wholely allocated */
3ae3b454
MD
837 } else {
838 /*
7552e9ee
MD
839 * Add terminator but continue the loop. Populate
840 * all terminators.
3ae3b454 841 */
7552e9ee
MD
842 if (scan) {
843 scan[i].bm_bighint = (alist_blk_t)-1;
844 scan[i].bm_bitmap = 0;
845 }
3ae3b454 846 /* already marked as wholely allocated */
3ae3b454
MD
847 }
848 mask <<= 2;
849 pmask <<= 2;
7552e9ee 850 blk += radix;
3ae3b454 851 }
7552e9ee 852 memindex += ALIST_META_RADIX;
3ae3b454
MD
853 return(memindex);
854}
855
856#ifdef ALIST_DEBUG
857
858static void
7552e9ee
MD
859alst_radix_print(almeta_t *scan, alist_blk_t blk, alist_blk_t radix,
860 alist_blk_t skip, int tab)
3ae3b454 861{
7552e9ee
MD
862 alist_blk_t i;
863 alist_blk_t next_skip;
864 alist_bmap_t mask;
3ae3b454 865 int lastState = 0;
3ae3b454
MD
866
867 if (radix == ALIST_BMAP_RADIX) {
868 kprintf(
869 "%*.*s(%04x,%d): bitmap %08x big=%d\n",
870 tab, tab, "",
871 blk, radix,
872 scan->bm_bitmap,
873 scan->bm_bighint
874 );
875 return;
876 }
877
878 if (scan->bm_bitmap == 0) {
879 kprintf(
880 "%*.*s(%04x,%d) ALL ALLOCATED\n",
881 tab, tab, "",
882 blk,
883 radix
884 );
885 return;
886 }
7552e9ee 887 if (scan->bm_bitmap == (alist_bmap_t)-1) {
3ae3b454
MD
888 kprintf(
889 "%*.*s(%04x,%d) ALL FREE\n",
890 tab, tab, "",
891 blk,
892 radix
893 );
894 return;
895 }
896
897 kprintf(
898 "%*.*s(%04x,%d): subtree (%d) bitmap=%08x big=%d {\n",
899 tab, tab, "",
900 blk, radix,
901 radix,
902 scan->bm_bitmap,
903 scan->bm_bighint
904 );
905
906 radix /= ALIST_META_RADIX;
7552e9ee 907 next_skip = skip / ALIST_META_RADIX;
3ae3b454
MD
908 tab += 4;
909 mask = 0x00000003;
910
911 for (i = 1; i <= skip; i += next_skip) {
7552e9ee 912 if (scan[i].bm_bighint == (alist_blk_t)-1) {
3ae3b454
MD
913 kprintf(
914 "%*.*s(%04x,%d): Terminator\n",
915 tab, tab, "",
916 blk, radix
917 );
918 lastState = 0;
919 break;
920 }
921 if ((scan->bm_bitmap & mask) == mask) {
922 kprintf(
923 "%*.*s(%04x,%d): ALL FREE\n",
924 tab, tab, "",
925 blk, radix
926 );
927 } else if ((scan->bm_bitmap & mask) == 0) {
928 kprintf(
929 "%*.*s(%04x,%d): ALL ALLOCATED\n",
930 tab, tab, "",
931 blk, radix
932 );
933 } else {
934 alst_radix_print(
935 &scan[i],
936 blk,
937 radix,
938 next_skip - 1,
939 tab
940 );
941 }
942 blk += radix;
943 mask <<= 2;
944 }
945 tab -= 4;
946
7552e9ee 947 kprintf("%*.*s}\n", tab, tab, "");
3ae3b454
MD
948}
949
950#endif
951
952#ifdef ALIST_DEBUG
953
954int
955main(int ac, char **av)
956{
7552e9ee
MD
957 alist_blk_t size = 1024;
958 alist_blk_t da = 0;
959 alist_blk_t count = 0;
3ae3b454 960 alist_t bl;
7552e9ee 961 int i;
3ae3b454
MD
962
963 for (i = 1; i < ac; ++i) {
964 const char *ptr = av[i];
965 if (*ptr != '-') {
966 size = strtol(ptr, NULL, 0);
967 continue;
968 }
969 ptr += 2;
970 fprintf(stderr, "Bad option: %s\n", ptr - 2);
971 exit(1);
972 }
973 bl = alist_create(size, NULL);
974 alist_free(bl, 0, size);
975
976 for (;;) {
977 char buf[1024];
7552e9ee 978 alist_blk_t bfree;
3ae3b454
MD
979
980
981 kprintf("%d/%d/%d> ", bl->bl_free, size, bl->bl_radix);
982 fflush(stdout);
983 if (fgets(buf, sizeof(buf), stdin) == NULL)
984 break;
985 switch(buf[0]) {
986 case 'p':
987 alist_print(bl);
988 break;
989 case 'a':
7552e9ee
MD
990 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) {
991 da = alist_alloc(bl, da, count);
992 kprintf(" R=%04x\n", da);
993 } else if (sscanf(buf + 1, "%d", &count) == 1) {
994 da = alist_alloc(bl, 0, count);
995 kprintf(" R=%04x\n", da);
996 } else if (count) {
997 kprintf("alloc 0x%04x/%d\n", da, count);
998 alist_blk_t blk = alist_alloc(bl, da, count);
3ae3b454
MD
999 kprintf(" R=%04x\n", blk);
1000 } else {
1001 kprintf("?\n");
1002 }
1003 break;
1004 case 'f':
1005 if (sscanf(buf + 1, "%x %d", &da, &count) == 2) {
1006 alist_free(bl, da, count);
7552e9ee
MD
1007 } else if (count) {
1008 kprintf("free 0x%04x/%d\n", da, count);
1009 alist_free(bl, da, count);
3ae3b454
MD
1010 } else {
1011 kprintf("?\n");
1012 }
1013 break;
1014 case '?':
1015 case 'h':
7552e9ee
MD
1016 puts("p -print\n"
1017 "a %d -allocate\n"
1018 "f %x %d -free\n"
1019 "h/? -help");
1020 break;
1021 case 'i':
1022 bfree = alist_free_info(bl, &da, &count);
1023 kprintf("info: %d free trailing: 0x%04x/%d\n",
1024 bfree, da, count);
3ae3b454
MD
1025 break;
1026 default:
1027 kprintf("?\n");
1028 break;
1029 }
1030 }
1031 return(0);
1032}
1033
1034void
1035panic(const char *ctl, ...)
1036{
1037 __va_list va;
1038
1039 __va_start(va, ctl);
1040 vfprintf(stderr, ctl, va);
1041 fprintf(stderr, "\n");
1042 __va_end(va);
1043 exit(1);
1044}
1045
1046#endif