Bug #14981


zfs: Several B-tree optimizations

Added by Toomas Soome 10 days ago. Updated 10 days ago.

In Progress
zfs - Zettabyte File System
Start date:
Due date:
% Done:


Estimated time:
Gerrit CR:
External Bug:


Update from OpenZFS:

- Introduce first element offset within a leaf. It allows to reduce
by ~50% average memmove() size when adding/removing elements. If the
added/removed element is in the first half of the leaf, we may shift
elements before it and adjust the bth_first instead of moving more
elements after it.
- Use memcpy() instead of memmove() when we know there is no overlap.
- Switch from uint64_t to uint32_t. It does not limit anything,
but 32-bit arches should appreciate it greatly in hot paths.
- Store leaf capacity in struct btree to avoid 64-bit divisions.
- Adjust zfs_btree_insert_into_leaf() to always result in balanced
leaves after splitting, no matter where the new element was inserted.
Not that we care about it much, but it should also allow B-trees with
as little as two elements per leaf instead of 4 previously.

When scrubbing pool of 12 SSDs, storing 1.5TB of 4KB zvol blocks this
reduces amount of time spent in memmove() inside the scan thread from
13.7% to 5.7% and total scrub time by ~15 seconds out of 9 minutes.
It should also reduce spacemaps load time, but I haven't measured it.

Reviewed-by: Paul Dagnelie <>
Signed-off-by: Alexander Motin <>
Sponsored-By: iXsystems, Inc.
Closes #13582

Testing done: build/install/boot. Have been using it since the beginning of July.

Related issues

Precedes illumos gate - Bug #14982: zfs: Fix use-after-free in btree codeIn ProgressToomas Soome

Actions #1

Updated by Toomas Soome 10 days ago

  • Related to Bug #14982: zfs: Fix use-after-free in btree code added
Actions #2

Updated by Electric Monk 10 days ago

  • Gerrit CR set to 2356
Actions #3

Updated by Dan McDonald 7 days ago

  • Related to deleted (Bug #14982: zfs: Fix use-after-free in btree code)
Actions #4

Updated by Dan McDonald 7 days ago

  • Precedes Bug #14982: zfs: Fix use-after-free in btree code added

Also available in: Atom PDF