bcachefs: Fragmentation LRU
authorKent Overstreet <kent.overstreet@linux.dev>
Mon, 5 Dec 2022 15:24:19 +0000 (10:24 -0500)
committerKent Overstreet <kent.overstreet@linux.dev>
Sun, 22 Oct 2023 21:09:53 +0000 (17:09 -0400)
commit80c33085783656617d0d07e1bc9fba70a592ce5c
tree2f2a6b43a3b6caab092c4f74df9f5a582e1a60b0
parent1b30ed5fd87828b5e29647510eefb18a363e4d19
bcachefs: Fragmentation LRU

Now that we have much more efficient updates to the LRU btree, this
patch adds a new LRU that indexes buckets by fragmentation.

This means copygc no longer has to scan every bucket to find buckets
that need to be evacuated.

Changes:
 - A new field in bch_alloc_v4, fragmentation_lru - this corresponds to
   the bucket's position in the fragmentation LRU. We add a new field
   for this instead of calculating it as needed because we may make the
   fragmentation LRU optional; this field indicates whether a bucket is
   on the fragmentation LRU.

   Also, zoned devices will introduce variable bucket sizes; explicitly
   recording the LRU position will be safer for them.

 - A new copygc path for using the fragmentation LRU instead of
   scanning every bucket and building up an in-memory heap.

Signed-off-by: Kent Overstreet <kent.overstreet@linux.dev>
13 files changed:
fs/bcachefs/alloc_background.c
fs/bcachefs/alloc_background.h
fs/bcachefs/bcachefs.h
fs/bcachefs/bcachefs_format.h
fs/bcachefs/buckets_types.h
fs/bcachefs/lru.c
fs/bcachefs/lru.h
fs/bcachefs/move.c
fs/bcachefs/move.h
fs/bcachefs/movinggc.c
fs/bcachefs/recovery.c
fs/bcachefs/super.c
fs/bcachefs/trace.h