HomeFreeBSD

Change blst_leaf_alloc() to handle a cursor argument, and to improve

Description

Change blst_leaf_alloc() to handle a cursor argument, and to improve
performance.

To find in the leaf bitmap all ranges of sufficient length, use a doubling
strategy with shift-and-and until each bit still set represents a bit
sequence of length 'count', or until the bitmask is zero. In the latter
case, update the hint based on the first bit sequence length not found to
be available. For example, seeking an interval of length 12, the set bits
of the bitmap would represent intervals of length 1, then 2, then 3, then
6, then 12. If no bits are set at the point when each bit represents an
interval of length 6, then the hint can be updated to 5 and the search
terminated.

If long-enough intervals are found, discard those before the cursor. If
any remain, use binary search to find the position of the first of them,
and allocate that interval.

Submitted by: Doug Moore <dougm@rice.edu>
Reviewed by: kib, markj
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D11426

Details

Provenance
alcAuthored on
Reviewer
kib
Differential Revision
D11426: revise leaf allocator for faster allocation, with cursors
Parents
rS320526: MFC r320316:
Branches
Unknown
Tags
Unknown