bcache: improve writeback throughput when frontend I/O is idle

Currently in order to write dirty blocks to backend device in LBA order for better performance, inside write_dirty() the I/O is issued only when its sequence matches current expected sequence. Otherwise the kworker will repeat check-wait-woken loop until the sequence number matches.

When frontend I/O is idle, the writeback rate is set to INT_MAX, but the writeback thoughput doesn't increase much. There are two reasons,
- The check-wait-woken loop is inefficient.
- I/O depth on backing device is every low.

To improve the writeback throughput, this patch continues to use LBA re- order idea, but improves it by the following means,
- Do the reorder from write_dirty() to read_dirty().
Inside read_dirty(), use a min_heap to order all the to-be-writebacked keys, and read dirty blocks in LBA order. Although each read requests are not completed in issue order, there is no check-wait-woken loop so that the dirty blocks are issued in a small time range and they can be ordered by I/O schedulers efficiently.

- Read more dirty keys when frontend I/O is idle
Define WRITEBACKS_IN_PASS (5), MAX_WRITEBACKS_IN_PASS (80) for write- back dirty keys in each pass, and define WRITESIZE_IN_PASS (5000) and MAX_WRITESIZE_IN_PASS (80000) for total writeback data size in each pass. When frontend I/O is idle, new values MAX_WRITEBACKS_IN_PASS and MAX_WRITESIZE_IN_PASS are used to read more dirty keys and data size from cache deice, then more dirty blocks will be written to backend device in almost LBA order.

By this effort, when there is frontend I/O, the IOPS and latency almost has no difference observed, identical from previous read_dirty() and write_dirty() implementation. When frontend I/O is idle, with this patch the average queue size increases from 2.5 to 21, writeback thoughput on backing device increases from 12MiB/s to 20MiB/s.

Writeback throughput increases around 67% when frontend I/O is idle.

Signed-off-by Coly Li <[email protected]>

---
 drivers/md/bcache/bcache.h    |  1 +
 drivers/md/bcache/util.h      |  8 ++++
 drivers/md/bcache/writeback.c | 82 +++++++++++++++++------------------
 drivers/md/bcache/writeback.h |  6 ++-
 4 files changed, 52 insertions(+), 45 deletions(-)

drivers/md/bcache/bcache.h +1 -0

index d43fcccf297c..88fb9bb69ce9 100644
@@ -345,6 +345,7 @@ struct cached_dev {
        struct workqueue_struct *writeback_write_wq;
 
        struct keybuf           writeback_keys;
+       DECLARE_HEAP(struct keybuf_key *, read_dirty_heap);
 
        struct task_struct      *status_update_thread;
        /*

drivers/md/bcache/util.h +8 -0

index f61ab1bada6c..3f5f85bdeafe 100644
@@ -46,6 +46,14 @@ struct closure;
        (heap)->data;                                                   \
 })
 
+#define reset_heap(heap)                                               \
+({                                                                     \
+       size_t _bytes;                                                  \
+       _bytes = (heap)->size * sizeof(*(heap)->data);                  \
+       memset((heap)->data, 0, _bytes);                                \
+       (heap)->used = 0;                                               \
+})
+
 #define free_heap(heap)                                                        \
 do {                                                                   \
        kvfree((heap)->data);                                           \

drivers/md/bcache/writeback.c +26 -32

index 302e75f1fc4b..4f0e47c841aa 100644
@@ -406,26 +406,6 @@ static CLOSURE_CALLBACK(write_dirty)
        struct keybuf_key *w = io->bio.bi_private;
        struct cached_dev *dc = io->dc;
 
-       uint16_t next_sequence;
-
-       if (atomic_read(&dc->writeback_sequence_next) != io->sequence) {
-               /* Not our turn to write; wait for a write to complete */
-               closure_wait(&dc->writeback_ordering_wait, cl);
-
-               if (atomic_read(&dc->writeback_sequence_next) == io->sequence) {
-                       /*
-                        * Edge case-- it happened in indeterminate order
-                        * relative to when we were added to wait list..
-                        */
-                       closure_wake_up(&dc->writeback_ordering_wait);
-               }
-
-               continue_at(cl, write_dirty, io->dc->writeback_write_wq);
-               return;
-       }
-
-       next_sequence = io->sequence + 1;
-
        /*
         * IO errors are signalled using the dirty bit on the key.
         * If we failed to read, we should not attempt to write to the

@@ -443,7 +423,6 @@ static CLOSURE_CALLBACK(write_dirty)
                closure_bio_submit(io->dc->disk.c, &io->bio, cl);
        }
 
-       atomic_set(&dc->writeback_sequence_next, next_sequence);
        closure_wake_up(&dc->writeback_ordering_wait);
 
        continue_at(cl, write_dirty_finish, io->dc->writeback_write_wq);

@@ -471,18 +450,25 @@ static CLOSURE_CALLBACK(read_dirty_submit)
        continue_at(cl, write_dirty, io->dc->writeback_write_wq);
 }
 
+static uint64_t keybuf_key_cmp(const struct keybuf_key *l,
+                              const struct keybuf_key *r)
+{
+       if (unlikely((KEY_INODE(&l->key) != KEY_INODE(&r->key))))
+               return KEY_INODE(&l->key) > KEY_INODE(&r->key);
+       else
+               return KEY_OFFSET(&l->key) > KEY_OFFSET(&r->key);
+}
+
 static void read_dirty(struct cached_dev *dc)
 {
        unsigned int delay = 0;
-       struct keybuf_key *next, *keys[MAX_WRITEBACKS_IN_PASS], *w;
-       size_t size;
-       int nk, i;
+       struct keybuf_key *next, *w;
        struct dirty_io *io;
        struct closure cl;
-       uint16_t sequence = 0;
+       size_t size;
+       int nk, i;
 
        BUG_ON(!llist_empty(&dc->writeback_ordering_wait.list));
-       atomic_set(&dc->writeback_sequence_next, sequence);
        closure_init_stack(&cl);
 
        /*

@@ -495,46 +481,49 @@ static void read_dirty(struct cached_dev *dc)
        while (!kthread_should_stop() &&
               !test_bit(CACHE_SET_IO_DISABLE, &dc->disk.c->flags) &&
               next) {
+               size_t max_size_in_pass;
+               int max_writebacks_in_pass;
+
                size = 0;
                nk = 0;
+               reset_heap(&dc->read_dirty_heap);
 
                do {
                        BUG_ON(ptr_stale(dc->disk.c, &next->key, 0));
 
+                       if (atomic_read(&dc->disk.c->at_max_writeback_rate)) {
+                               max_writebacks_in_pass = MAX_WRITEBACKS_IN_PASS;
+                               max_size_in_pass = MAX_WRITESIZE_IN_PASS;
+                       } else {
+                               max_writebacks_in_pass = WRITEBACKS_IN_PASS;
+                               max_size_in_pass = WRITESIZE_IN_PASS;
+                       }
+
                        /*
                         * Don't combine too many operations, even if they
                         * are all small.
                         */
-                       if (nk >= MAX_WRITEBACKS_IN_PASS)
+                       if (nk >= max_writebacks_in_pass)
                                break;
 
                        /*
                         * If the current operation is very large, don't
                         * further combine operations.
                         */
-                       if (size >= MAX_WRITESIZE_IN_PASS)
+                       if (size >= max_size_in_pass)
                                break;
 
-                       /*
-                        * Operations are only eligible to be combined
-                        * if they are contiguous.
-                        *

drivers/md/bcache/writeback.c +11 -4

                        size += KEY_SIZE(&next->key);
-                       keys[nk++] = next;
+                       nk++;
                } while ((next = bch_keybuf_next(&dc->writeback_keys)));
 
                /* Now we have gathered a set of 1..5 keys to write back. */
                for (i = 0; i < nk; i++) {
-                       w = keys[i];
+                       heap_pop(&dc->read_dirty_heap, w, keybuf_key_cmp);
 
                        io = kzalloc(struct_size(io, bio.bi_inline_vecs,
                                                DIV_ROUND_UP(KEY_SIZE(&w->key), PAGE_SECTORS)),

@@ -544,7 +533,6 @@ static void read_dirty(struct cached_dev *dc)
 
                        w->private      = io;
                        io->dc          = dc;
-                       io->sequence    = sequence++;
 
                        dirty_init(w);
                        io->bio.bi_opf = REQ_OP_READ;

@@ -835,6 +823,7 @@ static int bch_writeback_thread(void *arg)
        if (dc->writeback_write_wq)
                destroy_workqueue(dc->writeback_write_wq);
 
+       free_heap(&dc->read_dirty_heap);
        cached_dev_put(dc);
        wait_for_kthread_stop();
 

@@ -1080,12 +1069,19 @@ int bch_cached_dev_writeback_start(struct cached_dev *dc)
        if (!dc->writeback_write_wq)
                return -ENOMEM;
 
+       if (!init_heap(&dc->read_dirty_heap, MAX_WRITEBACKS_IN_PASS,
+                      GFP_KERNEL)) {
+               destroy_workqueue(dc->writeback_write_wq);
+               return -ENOMEM;
+       }
+
        cached_dev_get(dc);
        dc->writeback_thread = kthread_create(bch_writeback_thread, dc,
                                              "bcache_writeback");
        if (IS_ERR(dc->writeback_thread)) {
-               cached_dev_put(dc);
                destroy_workqueue(dc->writeback_write_wq);
+               free_heap(&dc->read_dirty_heap);
+               cached_dev_put(dc);
                return PTR_ERR(dc->writeback_thread);
        }
        dc->writeback_running = true;

drivers/md/bcache/writeback.h +4 -3

index 31df716951f6..7e6b75768cad 100644
@@ -8,8 +8,10 @@
 #define CUTOFF_WRITEBACK_MAX           70
 #define CUTOFF_WRITEBACK_SYNC_MAX      90
 
-#define MAX_WRITEBACKS_IN_PASS  5
-#define MAX_WRITESIZE_IN_PASS   5000   /* *512b */
+#define WRITEBACKS_IN_PASS             5
+#define MAX_WRITEBACKS_IN_PASS         80
+#define WRITESIZE_IN_PASS              5000  /* *512b */
+#define MAX_WRITESIZE_IN_PASS          80000 /* *512b */
 
 #define WRITEBACK_RATE_UPDATE_SECS_MAX         60
 #define WRITEBACK_RATE_UPDATE_SECS_DEFAULT     5
--

2.47.2

Quoted 193 lines · On Fri, 29 Aug 2025 at 00:20, <[email protected]> wrote:

Currently in order to write dirty blocks to backend device in LBA order for better performance, inside write_dirty() the I/O is issued only when its sequence matches current expected sequence. Otherwise the kworker will repeat check-wait-woken loop until the sequence number matches.

When frontend I/O is idle, the writeback rate is set to INT_MAX, but the writeback thoughput doesn't increase much. There are two reasons,
- The check-wait-woken loop is inefficient.
- I/O depth on backing device is every low.

To improve the writeback throughput, this patch continues to use LBA re- order idea, but improves it by the following means,
- Do the reorder from write_dirty() to read_dirty().
Inside read_dirty(), use a min_heap to order all the to-be-writebacked keys, and read dirty blocks in LBA order. Although each read requests are not completed in issue order, there is no check-wait-woken loop so that the dirty blocks are issued in a small time range and they can be ordered by I/O schedulers efficiently.

- Read more dirty keys when frontend I/O is idle
Define WRITEBACKS_IN_PASS (5), MAX_WRITEBACKS_IN_PASS (80) for write- back dirty keys in each pass, and define WRITESIZE_IN_PASS (5000) and MAX_WRITESIZE_IN_PASS (80000) for total writeback data size in each pass. When frontend I/O is idle, new values MAX_WRITEBACKS_IN_PASS and MAX_WRITESIZE_IN_PASS are used to read more dirty keys and data size from cache deice, then more dirty blocks will be written to backend device in almost LBA order.

By this effort, when there is frontend I/O, the IOPS and latency almost has no difference observed, identical from previous read_dirty() and write_dirty() implementation. When frontend I/O is idle, with this patch the average queue size increases from 2.5 to 21, writeback thoughput on backing device increases from 12MiB/s to 20MiB/s.

Writeback throughput increases around 67% when frontend I/O is idle.

Signed-off-by Coly Li <[email protected]>

---
 drivers/md/bcache/bcache.h    |  1 +
 drivers/md/bcache/util.h      |  8 ++++
 drivers/md/bcache/writeback.c | 82 +++++++++++++++++------------------
 drivers/md/bcache/writeback.h |  6 ++-
 4 files changed, 52 insertions(+), 45 deletions(-)

drivers/md/bcache/bcache.h +1 -0

index d43fcccf297c..88fb9bb69ce9 100644
@@ -345,6 +345,7 @@ struct cached_dev {
        struct workqueue_struct *writeback_write_wq;
 
        struct keybuf           writeback_keys;
+       DECLARE_HEAP(struct keybuf_key *, read_dirty_heap);
 
        struct task_struct      *status_update_thread;
        /*

drivers/md/bcache/util.h +8 -0

index f61ab1bada6c..3f5f85bdeafe 100644
@@ -46,6 +46,14 @@ struct closure;
        (heap)->data;                                                   \
 })
 
+#define reset_heap(heap)                                               \
+({                                                                     \
+       size_t _bytes;                                                  \
+       _bytes = (heap)->size * sizeof(*(heap)->data);                  \
+       memset((heap)->data, 0, _bytes);                                \
+       (heap)->used = 0;                                               \
+})
+
 #define free_heap(heap)                                                        \
 do {                                                                   \
        kvfree((heap)->data);                                           \

drivers/md/bcache/writeback.c +26 -37

index 302e75f1fc4b..4f0e47c841aa 100644
@@ -406,26 +406,6 @@ static CLOSURE_CALLBACK(write_dirty)
        struct keybuf_key *w = io->bio.bi_private;
        struct cached_dev *dc = io->dc;
 
-       uint16_t next_sequence;
-
-       if (atomic_read(&dc->writeback_sequence_next) != io->sequence) {
-               /* Not our turn to write; wait for a write to complete */
-               closure_wait(&dc->writeback_ordering_wait, cl);
-
-               if (atomic_read(&dc->writeback_sequence_next) == io->sequence) {
-                       /*
-                        * Edge case-- it happened in indeterminate order
-                        * relative to when we were added to wait list..
-                        */
-                       closure_wake_up(&dc->writeback_ordering_wait);
-               }
-
-               continue_at(cl, write_dirty, io->dc->writeback_write_wq);
-               return;
-       }
-
-       next_sequence = io->sequence + 1;
-
        /*
         * IO errors are signalled using the dirty bit on the key.
         * If we failed to read, we should not attempt to write to the

@@ -443,7 +423,6 @@ static CLOSURE_CALLBACK(write_dirty)
                closure_bio_submit(io->dc->disk.c, &io->bio, cl);
        }
 
-       atomic_set(&dc->writeback_sequence_next, next_sequence);
        closure_wake_up(&dc->writeback_ordering_wait);
 
        continue_at(cl, write_dirty_finish, io->dc->writeback_write_wq);

@@ -471,18 +450,25 @@ static CLOSURE_CALLBACK(read_dirty_submit)
        continue_at(cl, write_dirty, io->dc->writeback_write_wq);
 }
 
+static uint64_t keybuf_key_cmp(const struct keybuf_key *l,
+                              const struct keybuf_key *r)
+{
+       if (unlikely((KEY_INODE(&l->key) != KEY_INODE(&r->key))))
+               return KEY_INODE(&l->key) > KEY_INODE(&r->key);
+       else
+               return KEY_OFFSET(&l->key) > KEY_OFFSET(&r->key);
+}
+
 static void read_dirty(struct cached_dev *dc)
 {
        unsigned int delay = 0;
-       struct keybuf_key *next, *keys[MAX_WRITEBACKS_IN_PASS], *w;
-       size_t size;
-       int nk, i;
+       struct keybuf_key *next, *w;
        struct dirty_io *io;
        struct closure cl;
-       uint16_t sequence = 0;
+       size_t size;
+       int nk, i;
 
        BUG_ON(!llist_empty(&dc->writeback_ordering_wait.list));
-       atomic_set(&dc->writeback_sequence_next, sequence);
        closure_init_stack(&cl);
 
        /*

@@ -495,46 +481,49 @@ static void read_dirty(struct cached_dev *dc)
        while (!kthread_should_stop() &&
               !test_bit(CACHE_SET_IO_DISABLE, &dc->disk.c->flags) &&
               next) {
+               size_t max_size_in_pass;
+               int max_writebacks_in_pass;
+
                size = 0;
                nk = 0;
+               reset_heap(&dc->read_dirty_heap);
 
                do {
                        BUG_ON(ptr_stale(dc->disk.c, &next->key, 0));
 
+                       if (atomic_read(&dc->disk.c->at_max_writeback_rate)) {
+                               max_writebacks_in_pass = MAX_WRITEBACKS_IN_PASS;
+                               max_size_in_pass = MAX_WRITESIZE_IN_PASS;
+                       } else {
+                               max_writebacks_in_pass = WRITEBACKS_IN_PASS;
+                               max_size_in_pass = WRITESIZE_IN_PASS;
+                       }
+
                        /*
                         * Don't combine too many operations, even if they
                         * are all small.
                         */
-                       if (nk >= MAX_WRITEBACKS_IN_PASS)
+                       if (nk >= max_writebacks_in_pass)
                                break;
 
                        /*
                         * If the current operation is very large, don't
                         * further combine operations.
                         */
-                       if (size >= MAX_WRITESIZE_IN_PASS)
+                       if (size >= max_size_in_pass)
                                break;
 
-                       /*
-                        * Operations are only eligible to be combined
-                        * if they are contiguous.
-                        *
-                        * TODO: add a heuristic willing to fire a
-                        * certain amount of non-contiguous IO per pass,
-                        * so that we can benefit from backing device
-                        * command queueing.
-                        */

drivers/md/bcache/writeback.c static void read_dirty(struct cached_dev *dc) · line 518

Quoted 5 lines

drivers/md/bcache/writeback.c +2 -2

-                       if ((nk != 0) && bkey_cmp(&keys[nk-1]->key,
-                                               &START_KEY(&next->key)))
+                       if (!heap_add(&dc->read_dirty_heap, next,
+                                     keybuf_key_cmp))
                                break;

The bkeys retrieved from the dc->writeback_keys rbtree are in a specific order. Can the heap sorting here be omitted?

Quoted 46 lines · jifeng zhou

Quoted 45 lines · On Fri, 29 Aug 2025 at 00:20, <[email protected]> wrote:

Currently in order to write dirty blocks to backend device in LBA order for better performance, inside write_dirty() the I/O is issued only when its sequence matches current expected sequence. Otherwise the kworker will repeat check-wait-woken loop until the sequence number matches.

When frontend I/O is idle, the writeback rate is set to INT_MAX, but the writeback thoughput doesn't increase much. There are two reasons,
- The check-wait-woken loop is inefficient.
- I/O depth on backing device is every low.

To improve the writeback throughput, this patch continues to use LBA re- order idea, but improves it by the following means,
- Do the reorder from write_dirty() to read_dirty().
Inside read_dirty(), use a min_heap to order all the to-be-writebacked keys, and read dirty blocks in LBA order. Although each read requests are not completed in issue order, there is no check-wait-woken loop so that the dirty blocks are issued in a small time range and they can be ordered by I/O schedulers efficiently.

- Read more dirty keys when frontend I/O is idle
Define WRITEBACKS_IN_PASS (5), MAX_WRITEBACKS_IN_PASS (80) for write- back dirty keys in each pass, and define WRITESIZE_IN_PASS (5000) and MAX_WRITESIZE_IN_PASS (80000) for total writeback data size in each pass. When frontend I/O is idle, new values MAX_WRITEBACKS_IN_PASS and MAX_WRITESIZE_IN_PASS are used to read more dirty keys and data size from cache deice, then more dirty blocks will be written to backend device in almost LBA order.

By this effort, when there is frontend I/O, the IOPS and latency almost has no difference observed, identical from previous read_dirty() and write_dirty() implementation. When frontend I/O is idle, with this patch the average queue size increases from 2.5 to 21, writeback thoughput on backing device increases from 12MiB/s to 20MiB/s.

Writeback throughput increases around 67% when frontend I/O is idle.

Signed-off-by Coly Li <[email protected]>

---

drivers/md/bcache/bcache.h    |  1 +
drivers/md/bcache/util.h      |  8 ++++
drivers/md/bcache/writeback.c | 82 +++++++++++++++++------------------
drivers/md/bcache/writeback.h |  6 ++-
4 files changed, 52 insertions(+), 45 deletions(-)

Quoted 65 lines

Quoted 65 lines

static void read_dirty(struct cached_dev *dc)

{
       unsigned int delay = 0;

drivers/md/bcache/writeback.c +17 -16

-       struct keybuf_key *next, *keys[MAX_WRITEBACKS_IN_PASS], *w;
-       size_t size;
-       int nk, i;
+       struct keybuf_key *next, *w;
       struct dirty_io *io;
       struct closure cl;
-       uint16_t sequence = 0;
+       size_t size;
+       int nk, i;
 
       BUG_ON(!llist_empty(&dc->writeback_ordering_wait.list));
-       atomic_set(&dc->writeback_sequence_next, sequence);
       closure_init_stack(&cl);
 
       /*

@@ -495,46 +481,49 @@ static void read_dirty(struct cached_dev *dc)
       while (!kthread_should_stop() &&
              !test_bit(CACHE_SET_IO_DISABLE, &dc->disk.c->flags) &&
              next) {
+               size_t max_size_in_pass;
+               int max_writebacks_in_pass;
+
               size = 0;
               nk = 0;
+               reset_heap(&dc->read_dirty_heap);
 
               do {
                       BUG_ON(ptr_stale(dc->disk.c, &next->key, 0));
 
+                       if (atomic_read(&dc->disk.c->at_max_writeback_rate)) {
+                               max_writebacks_in_pass = MAX_WRITEBACKS_IN_PASS;
+                               max_size_in_pass = MAX_WRITESIZE_IN_PASS;
+                       } else {
+                               max_writebacks_in_pass = WRITEBACKS_IN_PASS;
+                               max_size_in_pass = WRITESIZE_IN_PASS;
+                       }
+
                       /*
                        * Don't combine too many operations, even if they
                        * are all small.
                        */
-                       if (nk >= MAX_WRITEBACKS_IN_PASS)
+                       if (nk >= max_writebacks_in_pass)
                               break;
 
                       /*
                        * If the current operation is very large, don't
                        * further combine operations.
                        */
-                       if (size >= MAX_WRITESIZE_IN_PASS)
+                       if (size >= max_size_in_pass)
                               break;
 
-                       /*
-                        * Operations are only eligible to be combined
-                        * if they are contiguous.
-                        *
-                        * TODO: add a heuristic willing to fire a
-                        * certain amount of non-contiguous IO per pass,
-                        * so that we can benefit from backing device
-                        * command queueing.
-                        */

Quoted 8 lines

drivers/md/bcache/writeback.c static void read_dirty(struct cached_dev *dc) · line 518

Quoted 5 lines

drivers/md/bcache/writeback.c +2 -2

-                       if ((nk != 0) && bkey_cmp(&keys[nk-1]->key,
-                                               &START_KEY(&next->key)))
+                       if (!heap_add(&dc->read_dirty_heap, next,
+                                     keybuf_key_cmp))
                               break;

The bkeys retrieved from the dc->writeback_keys rbtree are in a specific order. Can the heap sorting here be omitted?

Indeed the keys in dc->writeback_keys are not in a specific order, yes they are in the order from oldest to newest, but there is *NO* overlap betwen any two keys in dc->writeback_keys. See RB_INSERT() inside refill_keybuf_fn().

Because there is no overlap inside keys of dc->writeback_keys, re-order them by LBA incremental order won't make trouble here.