Improve hint maintenance on allocation

[alc]

Summary

Reduce the frequency of hint updates without incurring additional allocation overhead. Previously, blst_meta_alloc() updated the hint after every successful allocation. However, these "eager" hint updates are of no actual benefit if, instead, the "lazy" hint update at the start of blst_meta_alloc() is generalized to handle all cases where the number of available blocks is less than the requested allocation. Previously, the lazy hint update at the start of blst_meta_alloc() only handled the ALL-FULL case. I would also note that this change provides consistency between blist_alloc() and blist_fill() in that their hint maintenance is now entirely lazy.

Eliminate unnecessary checks for terminators in blst_meta_alloc() and blst_meta_fill() when handling ALL-FREE meta nodes.

Eliminate the field "bl_free" from struct blist. It is redundant. Unless the entire radix tree is a single leaf, the count of free blocks is stored in the root node. Add a trivial function, blist_avail(), for obtaining the count of free blocks.

In blst_meta_alloc(), perform a sanity check on the allocation once rather than repeating it in a loop.

Use the optimized bitcount*() function instead of a loop.

Add or improve several comments.

Address some nearby style errors.

[kib]

kern/subr_blist.c

427 ↗

(On Diff #29467)

Why is this correct ? Could it be that some other node under this meta contains larger contig chunk ?

[alc]

kern/subr_blist.c

427 ↗

(On Diff #29467)

u.bmu_avail is the total number of free blocks in the subtree. Unlike the hint, it is always accurate.

In this case, the allocation is asking for more blocks than are free in this subtree, so the allocation cannot possibly be satisfied. Also, there cannot possibly be a contiguous free range in the subtree that is larger than u.bmu_avail. Finally, all callers check the hint before making a call into this function, so the hint must have been no less than count and should be reduced.

[alc]

I'd like to add something else to this patch. Specifically, I'd like to remove the field "bl_free" from struct blmeta. While it is correctly maintained, it is never used. Moreover, unless the entire tree is a single leaf, the field "u.bmu_avail" at the root provides the count of free blocks in the tree.

Does that make sense?

[kib]

In D11146#230856, @alc wrote:

I'd like to add something else to this patch. Specifically, I'd like to remove the field "bl_free" from struct blmeta. While it is correctly maintained, it is never used. Moreover, unless the entire tree is a single leaf, the field "u.bmu_avail" at the root provides the count of free blocks in the tree.

You mean, bl_free from struct blist. Indeed, it is not used.

[alc]

In D11146#230884, @kib wrote:

In D11146#230856, @alc wrote:

I'd like to add something else to this patch. Specifically, I'd like to remove the field "bl_free" from struct blmeta. While it is correctly maintained, it is never used. Moreover, unless the entire tree is a single leaf, the field "u.bmu_avail" at the root provides the count of free blocks in the tree.

You mean, bl_free from struct blist. Indeed, it is not used.

Yes.

[alc]

Eliminate the field "bl_free" from struct blist. It is redundant. Unless the entire radix tree is a single leaf, the count of free blocks is stored in the root node.

Add a trivial function, blist_avail(), for obtaining the count of free blocks.

Use the optimized bitcount*() function instead of a loop.

[kib]

kern/subr_blist.c

242 ↗

(On Diff #29530)

'else' is not needed.

[alc]

kern/subr_blist.c

242 ↗

(On Diff #29530)

I wrote it this way so that the structure of the code parallels the nearby functions.