K 10 svn:author V 5 markj K 8 svn:date V 27 2018-11-13T18:40:01.234870Z K 7 svn:log V 1496 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 Reviewed by: alc MFC after: 1 month Differential Revision: https://reviews.freebsd.org/D12635 END