]> CyberLeo.Net >> Repos - FreeBSD/FreeBSD.git/commit
Allow allocations across meta boundaries.
authormarkj <markj@FreeBSD.org>
Tue, 13 Nov 2018 18:40:01 +0000 (18:40 +0000)
committermarkj <markj@FreeBSD.org>
Tue, 13 Nov 2018 18:40:01 +0000 (18:40 +0000)
commit3ce6f385ad8da2fa1f4e227fe897b7ceada138b2
tree57107da3874dd565eddffcf3d9d2d018470ed0ab
parentae8238d65ba5677350d41333373148f012e4e993
Allow allocations across meta boundaries.

Remove restrictions that prevent allocation requests to cross the
boundary between two meta nodes.

Replace the bmu_avail field in meta nodes with a bitmap that identifies
which subtrees have some free memory, and iterate over the nonempty
subtrees only in blst_meta_alloc.  If free memory is scarce, this should
make searching for it faster.

Put the code for handling the next-leaf allocation in a separate
function.  When taking blocks from the next leaf empties the leaf, be
sure to clear the appropriate bit in its parent, and so on, up to the
least-common ancestor of this leaf and the next.

Eliminate special terminator nodes, and rely instead on the fact that
there is a 0-bit at the end of the bitmask at the root of the tree that
will stop a meta_alloc search, or a next-leaf search, before the search
falls off the end of the tree. Make sure that the tree is big enough to
have space for that 0-bit.

Eliminate special all-free indicators.  Lazy initialization of subtrees
stands in the way of having an allocation span a meta-node boundary, so
a subtree of all free blocks is not treated specially.  Subtrees of
all-allocated blocks are still recognized by looking at the bitmask at
the root and finding 0.

Don't print all-allocated subtrees.  Do print the bitmasks for meta
nodes, when tree-printing.

Submitted by: Doug Moore <dougm@rice.edu>
Reviewed by: alc
MFC after: 1 month
Differential Revision: https://reviews.freebsd.org/D12635
sys/kern/subr_blist.c
sys/sys/blist.h