xfs: rework near mode extent allocation

Hi all,

Here's v5 of the near mode block allocation rework. This mostly consists of various minor cleanups from v4. The only functional change is to deactivate the cntbt cursor on finding a perfect extent in patch 8. Thoughts, reviews, flames appreciated.

Brian

v5:
- Fix up active logic in patch 1.
- Fix busy_gen type.
- Change ->diff initialization value in proper patch.
- Deactivate cntbt cursor on location of perfect extent.
- Various aesthetic cleanups.
v4: https://lore.kernel.org/linux-xfs/[email protected]/
- Fix up cursor active tracking type usage.
- Fix up cntbt lookup function signature.
- Added high level comment on optimized allocation algorithm.
- Split up series into smaller patches to separate refactoring from functional changes.
v3: https://lore.kernel.org/linux-xfs/[email protected]/
- Drop by-size and exact allocation rework bits.
- Add near mode last block scan.
- Add debug mode patch to randomly toggle near mode algos.
- Refactor cursor setup/lookup logic.
- Refactor minlen reverse scan to be common between near mode algos.
- Fix up logic to consistently prioritize extent size over locality.
- Add more useful tracepoints.
- Miscellaneous bug fixes and code/comment cleanups.
v2: https://marc.info/?l=linux-xfs&m=155854834815400&w=2
- Lift small mode refactoring into separate patch (retained review tag(s).
- Various logic cleanups and refactors.
- Push active flag down into btree cursor private area; eliminate cursor container struct.
- Refactor final allocation code. Fold xfs_alloc_ag_vextent_type() into caller and factor out accounting.
- Fix up tracepoints.
v1: https://marc.info/?l=linux-xfs&m=155742169729590&w=2
- Continued development (various fixes, refinements) on generic bits and near mode implementation.
- Added patches 4-6 to refactor exact, by-size and small allocation modes.
rfcv2: https://marc.info/?l=linux-xfs&m=155197946630582&w=2
- Dropped spurious initial refactoring.
- Added minlen functionality.
- Properly tied into near alloc path.
- General refactoring and cleanups.
rfcv1: https://marc.info/?l=linux-xfs&m=154479089914351&w=2

Brian Foster (11):
xfs: track active state of allocation btree cursors
xfs: introduce allocation cursor data structure
xfs: track allocation busy state in allocation cursor
xfs: track best extent from cntbt lastblock scan in alloc cursor
xfs: refactor cntbt lastblock scan best extent logic into helper
xfs: reuse best extent tracking logic for bnobt scan
xfs: refactor allocation tree fixup code
xfs: refactor and reuse best extent scanning logic
xfs: refactor near mode alloc bnobt scan into separate function
xfs: factor out tree fixup logic into helper
xfs: optimize near mode bnobt scans with concurrent cntbt lookups

 fs/xfs/libxfs/xfs_alloc.c       | 897 ++++++++++++++++++--------------
 fs/xfs/libxfs/xfs_alloc_btree.c |   1 +
 fs/xfs/libxfs/xfs_btree.h       |   3 +
 fs/xfs/xfs_trace.h              |  33 +-
 4 files changed, 547 insertions(+), 387 deletions(-)

2.20.1