Page MenuHomeFreeBSD

revise leaf allocator for faster allocation, with cursors
ClosedPublic

Authored by dougm on Jun 30 2017, 3:39 PM.
Tags
None
Referenced Files
Unknown Object (File)
Sun, Apr 21, 11:15 PM
Unknown Object (File)
Sun, Apr 21, 10:33 PM
Unknown Object (File)
Jan 31 2024, 2:30 PM
Unknown Object (File)
Jan 2 2024, 12:03 AM
Unknown Object (File)
Dec 23 2023, 10:58 AM
Unknown Object (File)
Nov 13 2023, 5:59 PM
Unknown Object (File)
Nov 7 2023, 8:51 PM
Unknown Object (File)
Oct 20 2023, 8:00 PM
Subscribers
None

Details

Summary

Change blist_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.

Diff Detail

Repository
rS FreeBSD src repository - subversion
Lint
Lint Not Applicable
Unit
Tests Not Applicable

Event Timeline

This revision is now accepted and ready to land.Jun 30 2017, 3:53 PM
sys/kern/subr_blist.c
422 ↗(On Diff #30259)

Shouldn't it be the "last set bit", i.e., the most significant set bit?

423 ↗(On Diff #30259)

"sufficient"

512 ↗(On Diff #30259)

The second line should have an indent of four spaces.

sys/kern/subr_blist.c
422 ↗(On Diff #30259)

I believe it should be the least significant set bit. I can add 'significant' to the comment.

sys/kern/subr_blist.c
422 ↗(On Diff #30259)

Oops, right. If I understand correctly, the most significant bit marks the start of the *last* available range of sufficient size.

I think it would help a bit to add "significant."

dougm edited edge metadata.

Accept suggestions on spelling, comment clarity and code formatting.

This revision now requires review to proceed.Jun 30 2017, 9:20 PM

This is cool. I had thought it was odd that the previous code took care to optimize single-bit allocations, since those ought to be fairly rare with the swap pager (the main consumer of this code).

This revision is now accepted and ready to land.Jun 30 2017, 10:26 PM
This revision was automatically updated to reflect the committed changes.