1 | /* |
2 | * BLIST.C - Bitmap allocator/deallocator, using a radix tree with hinting |
3 | * |
4 | * (c)Copyright 1998, Matthew Dillon. Terms for use and redistribution |
5 | * are covered by the BSD Copyright as found in /usr/src/COPYRIGHT. |
6 | * |
7 | * This module implements a general bitmap allocator/deallocator. The |
8 | * allocator eats around 2 bits per 'block'. The module does not |
9 | * try to interpret the meaning of a 'block' other then to return |
10 | * SWAPBLK_NONE on an allocation failure. |
11 | * |
12 | * A radix tree is used to maintain the bitmap. Two radix constants are |
13 | * involved: One for the bitmaps contained in the leaf nodes (typically |
14 | * 32), and one for the meta nodes (typically 16). Both meta and leaf |
15 | * nodes have a hint field. This field gives us a hint as to the largest |
16 | * free contiguous range of blocks under the node. It may contain a |
17 | * value that is too high, but will never contain a value that is too |
18 | * low. When the radix tree is searched, allocation failures in subtrees |
19 | * update the hint. |
20 | * |
21 | * The radix tree also implements two collapsed states for meta nodes: |
22 | * the ALL-ALLOCATED state and the ALL-FREE state. If a meta node is |
23 | * in either of these two states, all information contained underneath |
24 | * the node is considered stale. These states are used to optimize |
25 | * allocation and freeing operations. |
26 | * |
27 | * The hinting greatly increases code efficiency for allocations while |
28 | * the general radix structure optimizes both allocations and frees. The |
29 | * radix tree should be able to operate well no matter how much |
30 | * fragmentation there is and no matter how large a bitmap is used. |
31 | * |
32 | * Unlike the rlist code, the blist code wires all necessary memory at |
33 | * creation time. Neither allocations nor frees require interaction with |
34 | * the memory subsystem. In contrast, the rlist code may allocate memory |
35 | * on an rlist_free() call. The non-blocking features of the blist code |
36 | * are used to great advantage in the swap code (vm/nswap_pager.c). The |
37 | * rlist code uses a little less overall memory then the blist code (but |
38 | * due to swap interleaving not all that much less), but the blist code |
39 | * scales much, much better. |
40 | * |
41 | * LAYOUT: The radix tree is layed out recursively using a |
42 | * linear array. Each meta node is immediately followed (layed out |
43 | * sequentially in memory) by BLIST_META_RADIX lower level nodes. This |
44 | * is a recursive structure but one that can be easily scanned through |
45 | * a very simple 'skip' calculation. In order to support large radixes, |
46 | * portions of the tree may reside outside our memory allocation. We |
47 | * handle this with an early-termination optimization (when bighint is |
48 | * set to -1) on the scan. The memory allocation is only large enough |
49 | * to cover the number of blocks requested at creation time even if it |
50 | * must be encompassed in larger root-node radix. |
51 | * |
52 | * NOTE: the allocator cannot currently allocate more then |
53 | * BLIST_BMAP_RADIX blocks per call. It will panic with 'allocation too |
54 | * large' if you try. This is an area that could use improvement. The |
55 | * radix is large enough that this restriction does not effect the swap |
56 | * system, though. Currently only the allocation code is effected by |
57 | * this algorithmic unfeature. The freeing code can handle arbitrary |
58 | * ranges. |
59 | * |
60 | * This code can be compiled stand-alone for debugging. |
61 | * |
62 | * $FreeBSD: src/sys/kern/subr_blist.c,v 1.5.2.1 2000/03/17 10:47:29 ps Exp $ |
63 | */ |
64 | |
65 | typedef unsigned int u_daddr_t; |
66 | |
67 | #include <sys/param.h> |
68 | #include <sys/systm.h> |
69 | #include <sys/lock.h> |
70 | #include <sys/kernel.h> |
71 | #include "blist.h" |
72 | #include <sys/malloc.h> |
73 | |
74 | #if !defined(__APPLE__) |
75 | #define SWAPBLK_NONE ((daddr_t)-1) |
76 | #endif |
77 | |
78 | /* |
79 | * static support functions |
80 | */ |
81 | |
82 | static daddr_t blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count); |
83 | static daddr_t blst_meta_alloc(blmeta_t *scan, daddr_t blk, |
84 | daddr_t count, daddr_t radix, int skip); |
85 | static void blst_leaf_free(blmeta_t *scan, daddr_t relblk, int count); |
86 | static void blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, |
87 | daddr_t radix, int skip, daddr_t blk); |
88 | static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, |
89 | daddr_t skip, blist_t dest, daddr_t count); |
90 | static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, |
91 | int skip, daddr_t count); |
92 | |
93 | /* |
94 | * blist_create() - create a blist capable of handling up to the specified |
95 | * number of blocks |
96 | * |
97 | * blocks must be greater then 0 |
98 | * |
99 | * The smallest blist consists of a single leaf node capable of |
100 | * managing BLIST_BMAP_RADIX blocks. |
101 | */ |
102 | |
103 | blist_t |
104 | blist_create(daddr_t blocks) |
105 | { |
106 | blist_t bl; |
107 | int radix; |
108 | int skip = 0; |
109 | |
110 | /* |
111 | * Calculate radix and skip field used for scanning. |
112 | */ |
113 | radix = BLIST_BMAP_RADIX; |
114 | |
115 | while (radix < blocks) { |
116 | radix <<= BLIST_META_RADIX_SHIFT; |
117 | skip = (skip + 1) << BLIST_META_RADIX_SHIFT; |
118 | } |
119 | |
120 | bl = kalloc_type(struct blist, Z_ZERO | Z_WAITOK); |
121 | |
122 | bl->bl_blocks = blocks; |
123 | bl->bl_radix = radix; |
124 | bl->bl_skip = skip; |
125 | bl->bl_rootblks = 1 + |
126 | blst_radix_init(NULL, radix: bl->bl_radix, skip: bl->bl_skip, count: blocks); |
127 | bl->bl_root = (blmeta_t *)kalloc_data(sizeof(blmeta_t) * bl->bl_rootblks, Z_WAITOK); |
128 | |
129 | #if defined(BLIST_DEBUG) |
130 | printf( |
131 | "BLIST representing %d blocks (%d MB of swap)" |
132 | ", requiring %dK of ram\n" , |
133 | bl->bl_blocks, |
134 | bl->bl_blocks * 4 / 1024, |
135 | (bl->bl_rootblks * sizeof(blmeta_t) + 1023) / 1024 |
136 | ); |
137 | printf("BLIST raw radix tree contains %d records\n" , bl->bl_rootblks); |
138 | #endif |
139 | blst_radix_init(scan: bl->bl_root, radix: bl->bl_radix, skip: bl->bl_skip, count: blocks); |
140 | |
141 | return bl; |
142 | } |
143 | |
144 | void |
145 | blist_destroy(blist_t bl) |
146 | { |
147 | kfree_data(bl->bl_root, sizeof(blmeta_t) * bl->bl_rootblks); |
148 | kfree_type(struct blist, bl); |
149 | } |
150 | |
151 | /* |
152 | * blist_alloc() - reserve space in the block bitmap. Return the base |
153 | * of a contiguous region or SWAPBLK_NONE if space could |
154 | * not be allocated. |
155 | */ |
156 | |
157 | daddr_t |
158 | blist_alloc(blist_t bl, daddr_t count) |
159 | { |
160 | daddr_t blk = SWAPBLK_NONE; |
161 | |
162 | if (bl) { |
163 | if (bl->bl_radix == BLIST_BMAP_RADIX) { |
164 | blk = blst_leaf_alloc(scan: bl->bl_root, blk: 0, count); |
165 | } else { |
166 | blk = blst_meta_alloc(scan: bl->bl_root, blk: 0, count, |
167 | radix: bl->bl_radix, skip: bl->bl_skip); |
168 | } |
169 | if (blk != SWAPBLK_NONE) { |
170 | bl->bl_free -= count; |
171 | } |
172 | } |
173 | return blk; |
174 | } |
175 | |
176 | /* |
177 | * blist_free() - free up space in the block bitmap. Return the base |
178 | * of a contiguous region. Panic if an inconsistancy is |
179 | * found. |
180 | */ |
181 | |
182 | void |
183 | blist_free(blist_t bl, daddr_t blkno, daddr_t count) |
184 | { |
185 | if (bl) { |
186 | if (bl->bl_radix == BLIST_BMAP_RADIX) { |
187 | blst_leaf_free(scan: bl->bl_root, relblk: blkno, count); |
188 | } else { |
189 | blst_meta_free(scan: bl->bl_root, freeBlk: blkno, count, |
190 | radix: bl->bl_radix, skip: bl->bl_skip, blk: 0); |
191 | } |
192 | bl->bl_free += count; |
193 | } |
194 | } |
195 | |
196 | /* |
197 | * blist_resize() - resize an existing radix tree to handle the |
198 | * specified number of blocks. This will reallocate |
199 | * the tree and transfer the previous bitmap to the new |
200 | * one. When extending the tree you can specify whether |
201 | * the new blocks are to left allocated or freed. |
202 | */ |
203 | |
204 | void |
205 | blist_resize(blist_t *pbl, daddr_t count, int freenew) |
206 | { |
207 | blist_t newbl = blist_create(blocks: count); |
208 | blist_t save = *pbl; |
209 | |
210 | *pbl = newbl; |
211 | if (count > save->bl_blocks) { |
212 | count = save->bl_blocks; |
213 | } |
214 | blst_copy(scan: save->bl_root, blk: 0, radix: save->bl_radix, skip: save->bl_skip, dest: newbl, count); |
215 | |
216 | /* |
217 | * If resizing upwards, should we free the new space or not? |
218 | */ |
219 | if (freenew && count < newbl->bl_blocks) { |
220 | blist_free(bl: newbl, blkno: count, count: newbl->bl_blocks - count); |
221 | } |
222 | blist_destroy(bl: save); |
223 | } |
224 | |
225 | #ifdef BLIST_DEBUG |
226 | |
227 | /* |
228 | * blist_print() - dump radix tree |
229 | */ |
230 | |
231 | void |
232 | blist_print(blist_t bl) |
233 | { |
234 | printf("BLIST {\n" ); |
235 | blst_radix_print(bl->bl_root, 0, bl->bl_radix, bl->bl_skip, 4); |
236 | printf("}\n" ); |
237 | } |
238 | |
239 | #endif |
240 | |
241 | /************************************************************************ |
242 | * ALLOCATION SUPPORT FUNCTIONS * |
243 | ************************************************************************ |
244 | * |
245 | * These support functions do all the actual work. They may seem |
246 | * rather longish, but that's because I've commented them up. The |
247 | * actual code is straight forward. |
248 | * |
249 | */ |
250 | |
251 | /* |
252 | * blist_leaf_alloc() - allocate at a leaf in the radix tree (a bitmap). |
253 | * |
254 | * This is the core of the allocator and is optimized for the 1 block |
255 | * and the BLIST_BMAP_RADIX block allocation cases. Other cases are |
256 | * somewhat slower. The 1 block allocation case is log2 and extremely |
257 | * quick. |
258 | */ |
259 | |
260 | static daddr_t |
261 | blst_leaf_alloc(blmeta_t *scan, daddr_t blk, int count) |
262 | { |
263 | u_daddr_t orig = scan->u.bmu_bitmap; |
264 | |
265 | if (orig == 0) { |
266 | /* |
267 | * Optimize bitmap all-allocated case. Also, count = 1 |
268 | * case assumes at least 1 bit is free in the bitmap, so |
269 | * we have to take care of this case here. |
270 | */ |
271 | scan->bm_bighint = 0; |
272 | return SWAPBLK_NONE; |
273 | } |
274 | if (count == 1) { |
275 | /* |
276 | * Optimized code to allocate one bit out of the bitmap |
277 | */ |
278 | u_daddr_t mask; |
279 | int j = BLIST_BMAP_RADIX / 2; |
280 | int r = 0; |
281 | |
282 | mask = (u_daddr_t)-1 >> (BLIST_BMAP_RADIX / 2); |
283 | |
284 | while (j) { |
285 | if ((orig & mask) == 0) { |
286 | r += j; |
287 | orig >>= j; |
288 | } |
289 | j >>= 1; |
290 | mask >>= j; |
291 | } |
292 | scan->u.bmu_bitmap &= ~(1 << r); |
293 | return blk + r; |
294 | } |
295 | #if !defined(__APPLE__) |
296 | if (count <= BLIST_BMAP_RADIX) { |
297 | #else |
298 | if (count <= (int)BLIST_BMAP_RADIX) { |
299 | #endif /* __APPLE__ */ |
300 | /* |
301 | * non-optimized code to allocate N bits out of the bitmap. |
302 | * The more bits, the faster the code runs. It will run |
303 | * the slowest allocating 2 bits, but since there aren't any |
304 | * memory ops in the core loop (or shouldn't be, anyway), |
305 | * you probably won't notice the difference. |
306 | */ |
307 | int j; |
308 | int n = BLIST_BMAP_RADIX - count; |
309 | u_daddr_t mask; |
310 | |
311 | mask = (u_daddr_t)-1 >> n; |
312 | |
313 | for (j = 0; j <= n; ++j) { |
314 | if ((orig & mask) == mask) { |
315 | scan->u.bmu_bitmap &= ~mask; |
316 | return blk + j; |
317 | } |
318 | mask = (mask << 1); |
319 | } |
320 | } |
321 | /* |
322 | * We couldn't allocate count in this subtree, update bighint. |
323 | */ |
324 | scan->bm_bighint = count - 1; |
325 | return SWAPBLK_NONE; |
326 | } |
327 | |
328 | /* |
329 | * blist_meta_alloc() - allocate at a meta in the radix tree. |
330 | * |
331 | * Attempt to allocate at a meta node. If we can't, we update |
332 | * bighint and return a failure. Updating bighint optimize future |
333 | * calls that hit this node. We have to check for our collapse cases |
334 | * and we have a few optimizations strewn in as well. |
335 | */ |
336 | |
337 | static daddr_t |
338 | blst_meta_alloc(blmeta_t *scan, daddr_t blk, daddr_t count, daddr_t radix, |
339 | int skip) |
340 | { |
341 | int i; |
342 | int next_skip = (skip >> BLIST_META_RADIX_SHIFT); |
343 | |
344 | if (scan->u.bmu_avail == 0) { |
345 | /* |
346 | * ALL-ALLOCATED special case |
347 | */ |
348 | scan->bm_bighint = count; |
349 | return SWAPBLK_NONE; |
350 | } |
351 | |
352 | if (scan->u.bmu_avail == radix) { |
353 | radix >>= BLIST_META_RADIX_SHIFT; |
354 | |
355 | /* |
356 | * ALL-FREE special case, initialize uninitialize |
357 | * sublevel. |
358 | */ |
359 | for (i = 1; i <= skip; i += next_skip) { |
360 | if (scan[i].bm_bighint == (daddr_t)-1) { |
361 | break; |
362 | } |
363 | if (next_skip == 1) { |
364 | scan[i].u.bmu_bitmap = (u_daddr_t)-1; |
365 | scan[i].bm_bighint = BLIST_BMAP_RADIX; |
366 | } else { |
367 | scan[i].bm_bighint = radix; |
368 | scan[i].u.bmu_avail = radix; |
369 | } |
370 | } |
371 | } else { |
372 | radix >>= BLIST_META_RADIX_SHIFT; |
373 | } |
374 | |
375 | for (i = 1; i <= skip; i += next_skip) { |
376 | if (count <= scan[i].bm_bighint) { |
377 | /* |
378 | * count fits in object |
379 | */ |
380 | daddr_t r; |
381 | if (next_skip == 1) { |
382 | r = blst_leaf_alloc(scan: &scan[i], blk, count); |
383 | } else { |
384 | r = blst_meta_alloc(scan: &scan[i], blk, count, |
385 | radix, skip: next_skip - 1); |
386 | } |
387 | if (r != SWAPBLK_NONE) { |
388 | scan->u.bmu_avail -= count; |
389 | if (scan->bm_bighint > scan->u.bmu_avail) { |
390 | scan->bm_bighint = scan->u.bmu_avail; |
391 | } |
392 | return r; |
393 | } |
394 | } else if (scan[i].bm_bighint == (daddr_t)-1) { |
395 | /* |
396 | * Terminator |
397 | */ |
398 | break; |
399 | } else if (count > radix) { |
400 | /* |
401 | * count does not fit in object even if it were |
402 | * complete free. |
403 | */ |
404 | panic("blist_meta_alloc: allocation too large" ); |
405 | } |
406 | blk += radix; |
407 | } |
408 | |
409 | /* |
410 | * We couldn't allocate count in this subtree, update bighint. |
411 | */ |
412 | if (scan->bm_bighint >= count) { |
413 | scan->bm_bighint = count - 1; |
414 | } |
415 | return SWAPBLK_NONE; |
416 | } |
417 | |
418 | /* |
419 | * BLST_LEAF_FREE() - free allocated block from leaf bitmap |
420 | * |
421 | */ |
422 | |
423 | static void |
424 | blst_leaf_free(blmeta_t *scan, daddr_t blk, int count) |
425 | { |
426 | /* |
427 | * free some data in this bitmap |
428 | * |
429 | * e.g. |
430 | * 0000111111111110000 |
431 | * \_________/\__/ |
432 | * v n |
433 | */ |
434 | int n = blk & (BLIST_BMAP_RADIX - 1); |
435 | u_daddr_t mask; |
436 | |
437 | mask = ((u_daddr_t)-1 << n) & |
438 | ((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n)); |
439 | |
440 | if (scan->u.bmu_bitmap & mask) { |
441 | panic("blst_radix_free: freeing free block" ); |
442 | } |
443 | scan->u.bmu_bitmap |= mask; |
444 | |
445 | /* |
446 | * We could probably do a better job here. We are required to make |
447 | * bighint at least as large as the biggest contiguous block of |
448 | * data. If we just shoehorn it, a little extra overhead will |
449 | * be incured on the next allocation (but only that one typically). |
450 | */ |
451 | scan->bm_bighint = BLIST_BMAP_RADIX; |
452 | } |
453 | |
454 | /* |
455 | * BLST_META_FREE() - free allocated blocks from radix tree meta info |
456 | * |
457 | * This support routine frees a range of blocks from the bitmap. |
458 | * The range must be entirely enclosed by this radix node. If a |
459 | * meta node, we break the range down recursively to free blocks |
460 | * in subnodes (which means that this code can free an arbitrary |
461 | * range whereas the allocation code cannot allocate an arbitrary |
462 | * range). |
463 | */ |
464 | |
465 | static void |
466 | blst_meta_free(blmeta_t *scan, daddr_t freeBlk, daddr_t count, daddr_t radix, |
467 | int skip, daddr_t blk) |
468 | { |
469 | int i; |
470 | int next_skip = (skip >> BLIST_META_RADIX_SHIFT); |
471 | |
472 | #if 0 |
473 | printf("FREE (%x,%d) FROM (%x,%d)\n" , |
474 | freeBlk, count, |
475 | blk, radix |
476 | ); |
477 | #endif |
478 | |
479 | if (scan->u.bmu_avail == 0) { |
480 | /* |
481 | * ALL-ALLOCATED special case, with possible |
482 | * shortcut to ALL-FREE special case. |
483 | */ |
484 | scan->u.bmu_avail = count; |
485 | scan->bm_bighint = count; |
486 | |
487 | if (count != radix) { |
488 | for (i = 1; i <= skip; i += next_skip) { |
489 | if (scan[i].bm_bighint == (daddr_t)-1) { |
490 | break; |
491 | } |
492 | scan[i].bm_bighint = 0; |
493 | if (next_skip == 1) { |
494 | scan[i].u.bmu_bitmap = 0; |
495 | } else { |
496 | scan[i].u.bmu_avail = 0; |
497 | } |
498 | } |
499 | /* fall through */ |
500 | } |
501 | } else { |
502 | scan->u.bmu_avail += count; |
503 | /* scan->bm_bighint = radix; */ |
504 | } |
505 | |
506 | /* |
507 | * ALL-FREE special case. |
508 | */ |
509 | |
510 | if (scan->u.bmu_avail == radix) { |
511 | return; |
512 | } |
513 | if (scan->u.bmu_avail > radix) { |
514 | panic("blst_meta_free: freeing already free blocks (%d) %d/%d" , count, scan->u.bmu_avail, radix); |
515 | } |
516 | |
517 | /* |
518 | * Break the free down into its components |
519 | */ |
520 | |
521 | radix >>= BLIST_META_RADIX_SHIFT; |
522 | |
523 | i = (freeBlk - blk) / radix; |
524 | blk += i * radix; |
525 | i = i * next_skip + 1; |
526 | |
527 | while (i <= skip && blk < freeBlk + count) { |
528 | daddr_t v; |
529 | |
530 | v = blk + radix - freeBlk; |
531 | if (v > count) { |
532 | v = count; |
533 | } |
534 | |
535 | if (scan->bm_bighint == (daddr_t)-1) { |
536 | panic("blst_meta_free: freeing unexpected range" ); |
537 | } |
538 | |
539 | if (next_skip == 1) { |
540 | blst_leaf_free(scan: &scan[i], blk: freeBlk, count: v); |
541 | } else { |
542 | blst_meta_free(scan: &scan[i], freeBlk, count: v, radix, |
543 | skip: next_skip - 1, blk); |
544 | } |
545 | if (scan->bm_bighint < scan[i].bm_bighint) { |
546 | scan->bm_bighint = scan[i].bm_bighint; |
547 | } |
548 | count -= v; |
549 | freeBlk += v; |
550 | blk += radix; |
551 | i += next_skip; |
552 | } |
553 | } |
554 | |
555 | /* |
556 | * BLIST_RADIX_COPY() - copy one radix tree to another |
557 | * |
558 | * Locates free space in the source tree and frees it in the destination |
559 | * tree. The space may not already be free in the destination. |
560 | */ |
561 | |
562 | static void |
563 | blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, |
564 | daddr_t skip, blist_t dest, daddr_t count) |
565 | { |
566 | int next_skip; |
567 | int i; |
568 | |
569 | /* |
570 | * Leaf node |
571 | */ |
572 | |
573 | if (radix == BLIST_BMAP_RADIX) { |
574 | u_daddr_t v = scan->u.bmu_bitmap; |
575 | |
576 | if (v == (u_daddr_t)-1) { |
577 | blist_free(bl: dest, blkno: blk, count); |
578 | } else if (v != 0) { |
579 | #if !defined(__APPLE__) |
580 | int i; |
581 | |
582 | for (i = 0; i < BLIST_BMAP_RADIX && i < count; ++i) { |
583 | if (v & (1 << i)) { |
584 | blist_free(dest, blk + i, 1); |
585 | } |
586 | } |
587 | #else |
588 | int j; /* Avoid shadow warnings */ |
589 | |
590 | for (j = 0; j < (int)BLIST_BMAP_RADIX && j < count; ++j) { |
591 | if (v & (1 << j)) { |
592 | blist_free(bl: dest, blkno: blk + j, count: 1); |
593 | } |
594 | } |
595 | #endif /* __APPLE__ */ |
596 | } |
597 | return; |
598 | } |
599 | |
600 | /* |
601 | * Meta node |
602 | */ |
603 | |
604 | /* |
605 | * Source all allocated, leave dest allocated |
606 | */ |
607 | if (scan->u.bmu_avail == 0) { |
608 | return; |
609 | } |
610 | if (scan->u.bmu_avail == radix) { |
611 | /* |
612 | * Source all free, free entire dest |
613 | */ |
614 | if (count < radix) { |
615 | blist_free(bl: dest, blkno: blk, count); |
616 | } else { |
617 | blist_free(bl: dest, blkno: blk, count: radix); |
618 | } |
619 | return; |
620 | } |
621 | |
622 | radix >>= BLIST_META_RADIX_SHIFT; |
623 | next_skip = (skip >> BLIST_META_RADIX_SHIFT); |
624 | |
625 | for (i = 1; count && i <= skip; i += next_skip) { |
626 | if (scan[i].bm_bighint == (daddr_t)-1) { |
627 | break; |
628 | } |
629 | |
630 | if (count >= radix) { |
631 | blst_copy( |
632 | scan: &scan[i], |
633 | blk, |
634 | radix, |
635 | skip: next_skip - 1, |
636 | dest, |
637 | count: radix |
638 | ); |
639 | count -= radix; |
640 | } else { |
641 | if (count) { |
642 | blst_copy( |
643 | scan: &scan[i], |
644 | blk, |
645 | radix, |
646 | skip: next_skip - 1, |
647 | dest, |
648 | count |
649 | ); |
650 | } |
651 | count = 0; |
652 | } |
653 | blk += radix; |
654 | } |
655 | } |
656 | |
657 | /* |
658 | * BLST_RADIX_INIT() - initialize radix tree |
659 | * |
660 | * Initialize our meta structures and bitmaps and calculate the exact |
661 | * amount of space required to manage 'count' blocks - this space may |
662 | * be considerably less then the calculated radix due to the large |
663 | * RADIX values we use. |
664 | */ |
665 | |
666 | static daddr_t |
667 | blst_radix_init(blmeta_t *scan, daddr_t radix, int skip, daddr_t count) |
668 | { |
669 | int i; |
670 | int next_skip; |
671 | daddr_t memindex = 0; |
672 | |
673 | /* |
674 | * Leaf node |
675 | */ |
676 | |
677 | if (radix == BLIST_BMAP_RADIX) { |
678 | if (scan) { |
679 | scan->bm_bighint = 0; |
680 | scan->u.bmu_bitmap = 0; |
681 | } |
682 | return memindex; |
683 | } |
684 | |
685 | /* |
686 | * Meta node. If allocating the entire object we can special |
687 | * case it. However, we need to figure out how much memory |
688 | * is required to manage 'count' blocks, so we continue on anyway. |
689 | */ |
690 | |
691 | if (scan) { |
692 | scan->bm_bighint = 0; |
693 | scan->u.bmu_avail = 0; |
694 | } |
695 | |
696 | radix >>= BLIST_META_RADIX_SHIFT; |
697 | next_skip = (skip >> BLIST_META_RADIX_SHIFT); |
698 | |
699 | for (i = 1; i <= skip; i += next_skip) { |
700 | if (count >= radix) { |
701 | /* |
702 | * Allocate the entire object |
703 | */ |
704 | memindex = i + blst_radix_init( |
705 | scan: ((scan) ? &scan[i] : NULL), |
706 | radix, |
707 | skip: next_skip - 1, |
708 | count: radix |
709 | ); |
710 | count -= radix; |
711 | } else if (count > 0) { |
712 | /* |
713 | * Allocate a partial object |
714 | */ |
715 | memindex = i + blst_radix_init( |
716 | scan: ((scan) ? &scan[i] : NULL), |
717 | radix, |
718 | skip: next_skip - 1, |
719 | count |
720 | ); |
721 | count = 0; |
722 | } else { |
723 | /* |
724 | * Add terminator and break out |
725 | */ |
726 | if (scan) { |
727 | scan[i].bm_bighint = (daddr_t)-1; |
728 | } |
729 | break; |
730 | } |
731 | } |
732 | if (memindex < i) { |
733 | memindex = i; |
734 | } |
735 | return memindex; |
736 | } |
737 | |
738 | #ifdef BLIST_DEBUG |
739 | |
740 | static void |
741 | blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, int skip, int tab) |
742 | { |
743 | int i; |
744 | int next_skip; |
745 | int lastState = 0; |
746 | |
747 | if (radix == BLIST_BMAP_RADIX) { |
748 | printf( |
749 | "%*.*s(%04x,%d): bitmap %08x big=%d\n" , |
750 | tab, tab, "" , |
751 | blk, radix, |
752 | scan->u.bmu_bitmap, |
753 | scan->bm_bighint |
754 | ); |
755 | return; |
756 | } |
757 | |
758 | if (scan->u.bmu_avail == 0) { |
759 | printf( |
760 | "%*.*s(%04x,%d) ALL ALLOCATED\n" , |
761 | tab, tab, "" , |
762 | blk, |
763 | radix |
764 | ); |
765 | return; |
766 | } |
767 | if (scan->u.bmu_avail == radix) { |
768 | printf( |
769 | "%*.*s(%04x,%d) ALL FREE\n" , |
770 | tab, tab, "" , |
771 | blk, |
772 | radix |
773 | ); |
774 | return; |
775 | } |
776 | |
777 | printf( |
778 | "%*.*s(%04x,%d): subtree (%d/%d) big=%d {\n" , |
779 | tab, tab, "" , |
780 | blk, radix, |
781 | scan->u.bmu_avail, |
782 | radix, |
783 | scan->bm_bighint |
784 | ); |
785 | |
786 | radix >>= BLIST_META_RADIX_SHIFT; |
787 | next_skip = (skip >> BLIST_META_RADIX_SHIFT); |
788 | tab += 4; |
789 | |
790 | for (i = 1; i <= skip; i += next_skip) { |
791 | if (scan[i].bm_bighint == (daddr_t)-1) { |
792 | printf( |
793 | "%*.*s(%04x,%d): Terminator\n" , |
794 | tab, tab, "" , |
795 | blk, radix |
796 | ); |
797 | lastState = 0; |
798 | break; |
799 | } |
800 | blst_radix_print( |
801 | &scan[i], |
802 | blk, |
803 | radix, |
804 | next_skip - 1, |
805 | tab |
806 | ); |
807 | blk += radix; |
808 | } |
809 | tab -= 4; |
810 | |
811 | printf( |
812 | "%*.*s}\n" , |
813 | tab, tab, "" |
814 | ); |
815 | } |
816 | |
817 | #endif |
818 | |
819 | #ifdef BLIST_DEBUG |
820 | |
821 | int |
822 | main(int ac, char **av) |
823 | { |
824 | int size = 1024; |
825 | int i; |
826 | blist_t bl; |
827 | |
828 | for (i = 1; i < ac; ++i) { |
829 | const char *ptr = av[i]; |
830 | if (*ptr != '-') { |
831 | size = strtol(ptr, NULL, 0); |
832 | continue; |
833 | } |
834 | ptr += 2; |
835 | fprintf(stderr, "Bad option: %s\n" , ptr - 2); |
836 | exit(1); |
837 | } |
838 | bl = blist_create(size); |
839 | blist_free(bl, 0, size); |
840 | |
841 | for (;;) { |
842 | char buf[1024]; |
843 | daddr_t da = 0; |
844 | daddr_t count = 0; |
845 | |
846 | |
847 | printf("%d/%d/%d> " , bl->bl_free, size, bl->bl_radix); |
848 | fflush(stdout); |
849 | if (fgets(buf, sizeof(buf), stdin) == NULL) { |
850 | break; |
851 | } |
852 | switch (buf[0]) { |
853 | case 'r': |
854 | if (sscanf(buf + 1, "%d" , &count) == 1) { |
855 | blist_resize(&bl, count, 1); |
856 | } else { |
857 | printf("?\n" ); |
858 | } |
859 | case 'p': |
860 | blist_print(bl); |
861 | break; |
862 | case 'a': |
863 | if (sscanf(buf + 1, "%d" , &count) == 1) { |
864 | daddr_t blk = blist_alloc(bl, count); |
865 | printf(" R=%04x\n" , blk); |
866 | } else { |
867 | printf("?\n" ); |
868 | } |
869 | break; |
870 | case 'f': |
871 | if (sscanf(buf + 1, "%x %d" , &da, &count) == 2) { |
872 | blist_free(bl, da, count); |
873 | } else { |
874 | printf("?\n" ); |
875 | } |
876 | break; |
877 | case '?': |
878 | case 'h': |
879 | puts( |
880 | "p -print\n" |
881 | "a %d -allocate\n" |
882 | "f %x %d -free\n" |
883 | "r %d -resize\n" |
884 | "h/? -help" |
885 | ); |
886 | break; |
887 | default: |
888 | printf("?\n" ); |
889 | break; |
890 | } |
891 | } |
892 | return 0; |
893 | } |
894 | |
895 | void |
896 | panic(const char *ctl, ...) |
897 | { |
898 | va_list va; |
899 | |
900 | va_start(va, ctl); |
901 | vfprintf(stderr, ctl, va); |
902 | fprintf(stderr, "\n" ); |
903 | va_end(va); |
904 | exit(1); |
905 | } |
906 | |
907 | #endif |
908 | |