On Mar 1, 2021, at 6:53 PM, harshad shirwadkar [off-list ref] wrote:

Thanks for the review! Some comments inlined:

On Mon, Mar 1, 2021 at 2:22 PM Andreas Dilger [off-list ref] wrote:

quoted

On Feb 26, 2021, at 12:36 PM, Harshad Shirwadkar [off-list ref] wrote:

quoted

Instead of traversing through groups linearly, scan groups in specific
orders at cr 0 and cr 1. At cr 0, we want to find groups that have the
largest free order >= the order of the request. So, with this patch,
we maintain lists for each possible order and insert each group into a
list based on the largest free order in its buddy bitmap. During cr 0
allocation, we traverse these lists in the increasing order of largest
free orders. This allows us to find a group with the best available cr
0 match in constant time. If nothing can be found, we fallback to cr 1
immediately.

Thanks for the updated patch, I think it looks pretty good, with a
few suggestions.

Two other things that I wanted to mention in my previous email:

- whether this code should be enabled by default?  I think yes, because
  it is very unlikely that normal users will know this optimization
  exists, and the code will be dead for them, as they continue to suffer
  with long scan times.  If we think it is not a win to use with smaller
  filesystems, then MB_DEFAULT_LINEAR_LIMIT could be increased to where
  it *is* a win (e.g. 1TB = 8192 groups).
- rather than having mb_optimize_scan disabled for small filesystems at
  compile time, it would make more sense to allow mb_optimze_scan=N as
  a mount option to specify whether the feature is enabled or not.  If
  unset, then filesystems over MB_DEFAULT_LINEAR_SCAN_THRESHOLD would
  be enabled by default, but if =0 it is disabled, and =1 it is enabled
  (regardless of filesystem size).

Cheers, Andreas