i don't understand why we should not update the *cursor here. since AvlAllocator was inspired by zfs's dynamic fit block allocator. i am looking into its implementation. see https://github.com/openzfs/zfs/blob/60ffc1c460e4cdf3c3ca12c8840fd0675a98ed0d/module/zfs/metaslab.c#L1666 . IIUC, lbas[cbits(align) - 1] should be the end of the allocated extent to ease the search of the extent of the same alignment next time.

also, probably we can consolidate the code (not tested) like

  uint64_t *cursor = &lbas[cbits(align) - 1];
  const int free_pct = num_free * 100 / device_size;
  uint64_t start = 0;
  if (force_range_size_alloc ||
      max_size < range_size_alloc_threshold ||
      free_pct < range_size_alloc_free_pct) {
    /*
     * If we're running low on space switch to using the size
     * sorted AVL tree (best-fit).
     */
    start = -1ULL;
  } else {
    start = _block_picker(range_tree, cursor, size, unit);
  }
  if (start == -1ULL) {
    do {
      start = _block_picker(range_size_tree, cursor, size, unit);
      if (start != -1ULL) {
        break;
      }
      // try to collect smaller extents as we could fail to retrieve
      // that large block due to misaligned extents
      size = p2align(size >> 1, unit);
      align = size & -size;
      cursor = &lbas[cbits(align) - 1];
    } while (size >= unit);
  }

what do you think?

@tchaikov I agree that preserving cursor behavior is important. I do not fully grasp how adherence to cursor hints reflects on fragmentation behavior, but I can clearly see that there is some emerging anti-fragmentation properties that make avl fragment very little, while stupid did a lot.

I would suggest full synchronization between best and first fit:

bool best_fit = force_range_size_alloc ||
                  max_size < range_size_alloc_threshold ||
	          free_pct < range_size_alloc_free_pct;
  /*
   * If we're running low on space switch to using the size
   * sorted AVL tree (best-fit).
   */
  do {
    if (best_fit) {
      start = _block_picker(range_size_tree, cursor, size, unit);
    } else {
      start = _block_picker(range_tree, cursor, size, unit);
    }
    if (start != -1ULL) {
      break;
    }
    // try to collect smaller extents as we could fail to retrieve
    // that large block due to misaligned extents
    size = p2align(size >> 1, unit);
  } while (size >= unit);

i don't understand why we should not update the *cursor here. since AvlAllocator was inspired by zfs's dynamic fit block allocator. i am looking into its implementation. see https://github.com/openzfs/zfs/blob/60ffc1c460e4cdf3c3ca12c8840fd0675a98ed0d/module/zfs/metaslab.c#L1666 . IIUC, lbas[cbits(align) - 1] should be the end of the allocated extent to ease the search of the extent of the same alignment next time.
...
what do you think?

IMO cursor makes sense in first-fit mode only when we use range_tree (ordered by offset) to lookup the proper chunk. In that case preserving the cursor and using it as a hint for the next "similar-sized" lookup allows to allocate the nearest chunk. IIUC this might be beneficial from fragmentation point of view since similarly sized chunks tend to have better "geographic" locality. It's actually an open question whether we should increase cursor on each allocation to get better geo locality then. Not to mention that one might want to start with different initial cursor positions (e.g. choose them randomly on allocator's init or use some fixed but DIFFERENT positions for all of them. And preserve this info between reboots!).
I think the above improvements would provide better geo locality. But definitely that's unrelated to this PR.

Additionally cursor usage (and geo locality) might also improve spinning drive write performance when a bunch of similarly(!) sized writes is processed. But again IMO it's an open question whether this is good when handling a mixture of writes with different block sizes - high chances to get fragmented resulting write which isn't good for a spinning drive.

On the other hand in best-fit mode block picker runs through range_size_tree which is sorted by size only. Chunk offset isn't used for the selection during the lookup at all and hence no much sense in preserving the cursor - it's only the next "first-fit"(!) request which would benefit from that. Which is very unlikely to happen soon enough (as more space to be released to turn this mode back in the allocator) and hence no one would benefit from that cursor update.

Although it's rather a secondary question it seemed preferable to me to show that cursor isn't used in best-fit mode this way.
Given the above - would you prefer this to be reverted?

@ifed01 best-fit mode sorts by size (first priority) and offset (second priority). So although limited, cursor pointing to location still play a role.

I agree that for allocators dedicated for spinners we should actively promote locality.

@ifed01 best-fit mode sorts by size (first priority) and offset (second priority). So although limited, cursor pointing to location still play a role.

Yeah, missed that. Thanks!

I agree that for allocators dedicated for spinners we should actively promote locality.

i agree that the cursor is not likely to help with the locality of allocation requests of the same alignment. but just one thing, i think what the cursor tries to do is to clump the write requests with the same alignment to the same region not with the similar size.

Additionally cursor usage (and geo locality) might also improve spinning drive write performance when a bunch of similarly(!) sized writes is processed.

i was reading the document, source code and watching the speaks by ZFS authors. they helped to convince me that it's designed to combine the large amount of write request at block level or at the device level to a large one for better performance. it is specifically designed to improve the performance of spindle, but it could also benefit the SSD. as a sequential write is more performant than a bunch of random small writes.