Changeset View
Changeset View
Standalone View
Standalone View
sys/kern/subr_blist.c
Context not available. | |||||
u_daddr_t radix); | u_daddr_t radix); | ||||
static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, | static void blst_copy(blmeta_t *scan, daddr_t blk, daddr_t radix, | ||||
blist_t dest, daddr_t count); | blist_t dest, daddr_t count); | ||||
static daddr_t blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count); | |||||
static daddr_t blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, | |||||
u_daddr_t radix); | |||||
static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t count); | static daddr_t blst_radix_init(blmeta_t *scan, daddr_t radix, daddr_t count); | ||||
#ifndef _KERNEL | #ifndef _KERNEL | ||||
static void blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, | static void blst_radix_print(blmeta_t *scan, daddr_t blk, daddr_t radix, | ||||
Context not available. | |||||
} | } | ||||
/* | /* | ||||
* blist_fill() - mark a region in the block bitmap as off-limits | * blist_alloc_all() - mark all blocks allocated. | ||||
* to the allocator (i.e. allocate it), ignoring any | |||||
* existing allocations. Return the number of blocks | |||||
* actually filled that were free before the call. | |||||
*/ | */ | ||||
daddr_t | void | ||||
blist_fill(blist_t bl, daddr_t blkno, daddr_t count) | blist_alloc_all(blist_t bl) | ||||
{ | { | ||||
return (blst_meta_fill(bl->bl_root, blkno, count, bl->bl_radix)); | if (bl->bl_radix == BLIST_BMAP_RADIX) | ||||
bl->bl_root->u.bmu_bitmap = 0; | |||||
else | |||||
bl->bl_root->u.bmu_avail = 0; | |||||
} | } | ||||
/* | /* | ||||
Context not available. | |||||
} | } | ||||
/* | /* | ||||
* BLST_LEAF_FILL() - allocate specific blocks in leaf bitmap | |||||
* | |||||
* This routine allocates all blocks in the specified range | |||||
* regardless of any existing allocations in that range. Returns | |||||
* the number of blocks allocated by the call. | |||||
*/ | |||||
static daddr_t | |||||
blst_leaf_fill(blmeta_t *scan, daddr_t blk, int count) | |||||
{ | |||||
daddr_t nblks; | |||||
u_daddr_t mask; | |||||
int n; | |||||
n = blk & BLIST_BMAP_MASK; | |||||
mask = ((u_daddr_t)-1 << n) & | |||||
((u_daddr_t)-1 >> (BLIST_BMAP_RADIX - count - n)); | |||||
/* Count the number of blocks that we are allocating. */ | |||||
nblks = bitcount64(scan->u.bmu_bitmap & mask); | |||||
scan->u.bmu_bitmap &= ~mask; | |||||
return (nblks); | |||||
} | |||||
/* | |||||
* BLIST_META_FILL() - allocate specific blocks at a meta node | |||||
* | |||||
* This routine allocates the specified range of blocks, | |||||
* regardless of any existing allocations in the range. The | |||||
* range must be within the extent of this node. Returns the | |||||
* number of blocks allocated by the call. | |||||
*/ | |||||
static daddr_t | |||||
blst_meta_fill(blmeta_t *scan, daddr_t allocBlk, daddr_t count, u_daddr_t radix) | |||||
{ | |||||
daddr_t blk, i, nblks, next_skip, skip, v; | |||||
int child; | |||||
if (scan->bm_bighint == (daddr_t)-1) | |||||
panic("filling invalid range"); | |||||
if (count > radix) { | |||||
/* | |||||
* The allocation exceeds the number of blocks that are | |||||
* managed by this node. | |||||
*/ | |||||
panic("fill too large"); | |||||
} | |||||
if (radix == BLIST_BMAP_RADIX) | |||||
return (blst_leaf_fill(scan, allocBlk, count)); | |||||
if (count == radix || scan->u.bmu_avail == 0) { | |||||
/* | |||||
* ALL-ALLOCATED special case | |||||
*/ | |||||
nblks = scan->u.bmu_avail; | |||||
scan->u.bmu_avail = 0; | |||||
scan->bm_bighint = 0; | |||||
return (nblks); | |||||
} | |||||
skip = radix_to_skip(radix); | |||||
next_skip = skip / BLIST_META_RADIX; | |||||
blk = allocBlk & -radix; | |||||
/* | |||||
* An ALL-FREE meta node requires special handling before allocating | |||||
* any of its blocks. | |||||
*/ | |||||
if (scan->u.bmu_avail == radix) { | |||||
radix /= BLIST_META_RADIX; | |||||
/* | |||||
* Reinitialize each of the meta node's children. An ALL-FREE | |||||
* meta node cannot have a terminator in any subtree. | |||||
*/ | |||||
for (i = 1; i < skip; i += next_skip) { | |||||
if (next_skip == 1) | |||||
scan[i].u.bmu_bitmap = (u_daddr_t)-1; | |||||
else | |||||
scan[i].u.bmu_avail = radix; | |||||
scan[i].bm_bighint = radix; | |||||
} | |||||
} else { | |||||
radix /= BLIST_META_RADIX; | |||||
} | |||||
nblks = 0; | |||||
child = (allocBlk - blk) / radix; | |||||
blk += child * radix; | |||||
i = 1 + child * next_skip; | |||||
while (i < skip && blk < allocBlk + count) { | |||||
v = blk + radix - allocBlk; | |||||
if (v > count) | |||||
v = count; | |||||
nblks += blst_meta_fill(&scan[i], allocBlk, v, radix); | |||||
count -= v; | |||||
allocBlk += v; | |||||
blk += radix; | |||||
i += next_skip; | |||||
} | |||||
scan->u.bmu_avail -= nblks; | |||||
return (nblks); | |||||
} | |||||
/* | |||||
* BLST_RADIX_INIT() - initialize radix tree | * BLST_RADIX_INIT() - initialize radix tree | ||||
* | * | ||||
* Initialize our meta structures and bitmaps and calculate the exact | * Initialize our meta structures and bitmaps and calculate the exact | ||||
Context not available. | |||||
printf("?\n"); | printf("?\n"); | ||||
} | } | ||||
break; | break; | ||||
case 'A': | |||||
blist_alloc_all(bl); | |||||
break; | |||||
case 'f': | case 'f': | ||||
if (sscanf(buf + 1, "%llx %lld", &da, &count) == 2) { | if (sscanf(buf + 1, "%llx %lld", &da, &count) == 2) { | ||||
blist_free(bl, da, count); | blist_free(bl, da, count); | ||||
Context not available. | |||||
printf("?\n"); | printf("?\n"); | ||||
} | } | ||||
break; | break; | ||||
case 'l': | |||||
if (sscanf(buf + 1, "%llx %lld", &da, &count) == 2) { | |||||
printf(" n=%jd\n", | |||||
(intmax_t)blist_fill(bl, da, count)); | |||||
} else { | |||||
printf("?\n"); | |||||
} | |||||
break; | |||||
case '?': | case '?': | ||||
case 'h': | case 'h': | ||||
puts( | puts( | ||||
"p -print\n" | "p -print\n" | ||||
"s -stats\n" | "s -stats\n" | ||||
"a %d -allocate\n" | "a %d -allocate\n" | ||||
"A -allocate all\n" | |||||
"f %x %d -free\n" | "f %x %d -free\n" | ||||
"l %x %d -fill\n" | |||||
"r %d -resize\n" | "r %d -resize\n" | ||||
"h/? -help" | "h/? -help" | ||||
); | ); | ||||
Context not available. |