[PATCH] 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(-)

diff --git a/drivers/md/bcache/bcache.h b/drivers/md/bcache/bcache.h
index d43fcccf297c..88fb9bb69ce9 100644
--- a/drivers/md/bcache/bcache.h
+++ b/drivers/md/bcache/bcache.h
@@ -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;
 	/*
diff --git a/drivers/md/bcache/util.h b/drivers/md/bcache/util.h
index f61ab1bada6c..3f5f85bdeafe 100644
--- a/drivers/md/bcache/util.h
+++ b/drivers/md/bcache/util.h
@@ -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);						\
diff --git a/drivers/md/bcache/writeback.c b/drivers/md/bcache/writeback.c
index 302e75f1fc4b..4f0e47c841aa 100644
--- a/drivers/md/bcache/writeback.c
+++ b/drivers/md/bcache/writeback.c
@@ -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.
-			 */
-			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;
 
 			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;
diff --git a/drivers/md/bcache/writeback.h b/drivers/md/bcache/writeback.h
index 31df716951f6..7e6b75768cad 100644
--- a/drivers/md/bcache/writeback.h
+++ b/drivers/md/bcache/writeback.h
@@ -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