Hi all, Here is v4 of the near mode allocation rework. The primary difference in v4 is that I've split up the one big rework patch from previous versions into smaller patches that separate most of the functional changes from the larger amount of refactoring required to hopefully facilitate review. Since the previous versions were basically a rewrite of the existing algorithm, this approach of evolving the current code to the combined bnobt+cnbtbt algorithm ends up with slightly different code from the previous version. For example, some changes to how minlen is handled and tweaks to the best extent selection logic are lost in favor of preservation of the existing logic. The debug mode patch is no longer necessary because the existing equivalent code is preserved. I think these differences are mostly harmless and essentially just artifacts of the difference in how this patch series is constructed. Some of these tweaks may be reintroduced as independent fixups or to ultimately support the other allocation modes, but they are not required to fix the fundamental problem of pathological worst case bnobt scanning behavior. That said, I can't rule out some quirks that might have been introduced through the process of taking the previous version apart and reintroducing it in smaller increments, so review for that would be useful. I've run this through a series of tests mostly to verify that there haven't been any regressions since v3. This survives fstests from a functional perspective, maintains relative performance on clean and pre-fragmented filesystems and maintains the same level of locality effectiveness described by the previous version. It provides the same significant speedup to the highly (free space) fragmented metadump image provided by Mao Cheng that originally exhibited this problem. Thoughts, reviews, flames appreciated. Brian v4: - 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/20190815125538.49570-1-bfoster@xxxxxxxxxx/ - 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 | 887 ++++++++++++++++++-------------- fs/xfs/libxfs/xfs_alloc_btree.c | 1 + fs/xfs/libxfs/xfs_btree.h | 3 + fs/xfs/xfs_trace.h | 32 +- 4 files changed, 537 insertions(+), 386 deletions(-) -- 2.20.1
