[packages/kernel.git] / dm-crypt-sort-requests.patch

dm-crypt: sort writes

Write requests are sorted in a red-black tree structure and are submitted
in the sorted order.

In theory the sorting should be performed by the underlying disk scheduler,
however, in practice the disk scheduler accepts and sorts only 128 requests.
In order to sort more requests, we need to implement our own sorting.

Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>

---
 drivers/md/dm-crypt.c |   50 +++++++++++++++++++++++++++++++++++---------------
 1 file changed, 35 insertions(+), 15 deletions(-)

Index: linux-3.14/drivers/md/dm-crypt.c
===================================================================
--- linux-3.14.orig/drivers/md/dm-crypt.c	2014-04-04 21:06:22.000000000 +0200
+++ linux-3.14/drivers/md/dm-crypt.c	2014-04-04 21:06:55.000000000 +0200
@@ -22,6 +22,7 @@
 #include <linux/backing-dev.h>
 #include <linux/atomic.h>
 #include <linux/scatterlist.h>
+#include <linux/rbtree.h>
 #include <asm/page.h>
 #include <asm/unaligned.h>
 #include <crypto/hash.h>
@@ -60,7 +61,7 @@ struct dm_crypt_io {
 	int error;
 	sector_t sector;
 
-	struct list_head list;
+	struct rb_node rb_node;
 } CRYPTO_MINALIGN_ATTR;
 
 struct dm_crypt_request {
@@ -133,7 +134,7 @@ struct crypt_config {
 
 	struct task_struct *write_thread;
 	wait_queue_head_t write_thread_wait;
-	struct list_head write_thread_list;
+	struct rb_root write_tree;
 
 	char *cipher;
 	char *cipher_string;
@@ -1177,7 +1178,7 @@ static int dmcrypt_write(void *data)
 {
 	struct crypt_config *cc = data;
 	while (1) {
-		struct list_head local_list;
+		struct rb_root write_tree;
 		struct blk_plug plug;
 
 		DECLARE_WAITQUEUE(wait, current);
@@ -1185,7 +1186,7 @@ static int dmcrypt_write(void *data)
 		spin_lock_irq(&cc->write_thread_wait.lock);
 continue_locked:
 
-		if (!list_empty(&cc->write_thread_list))
+		if (!RB_EMPTY_ROOT(&cc->write_tree))
 			goto pop_from_list;
 
 		__set_current_state(TASK_INTERRUPTIBLE);
@@ -1207,20 +1208,23 @@ continue_locked:
 		goto continue_locked;
 
 pop_from_list:
-		local_list = cc->write_thread_list;
-		local_list.next->prev = &local_list;
-		local_list.prev->next = &local_list;
-		INIT_LIST_HEAD(&cc->write_thread_list);
-
+		write_tree = cc->write_tree;
+		cc->write_tree = RB_ROOT;
 		spin_unlock_irq(&cc->write_thread_wait.lock);
 
+		BUG_ON(rb_parent(write_tree.rb_node));
+
+		/*
+		 * Note: we cannot walk the tree here with rb_next because
+		 * the structures may be freed when kcryptd_io_write is called.
+		 */
 		blk_start_plug(&plug);
 		do {
-			struct dm_crypt_io *io = container_of(local_list.next,
-						struct dm_crypt_io, list);
-			list_del(&io->list);
+			struct dm_crypt_io *io = rb_entry(rb_first(&write_tree),
+						struct dm_crypt_io, rb_node);
+			rb_erase(&io->rb_node, &write_tree);
 			kcryptd_io_write(io);
-		} while (!list_empty(&local_list));
+		} while (!RB_EMPTY_ROOT(&write_tree));
 		blk_finish_plug(&plug);
 	}
 	return 0;
@@ -1231,6 +1235,8 @@ static void kcryptd_crypt_write_io_submi
 	struct bio *clone = io->ctx.bio_out;
 	struct crypt_config *cc = io->cc;
 	unsigned long flags;
+	sector_t sector;
+	struct rb_node **p, *parent;
 
 	if (unlikely(io->error < 0)) {
 		crypt_free_buffer_pages(cc, clone);
@@ -1245,7 +1251,21 @@ static void kcryptd_crypt_write_io_submi
 	clone->bi_iter.bi_sector = cc->start + io->sector;
 
 	spin_lock_irqsave(&cc->write_thread_wait.lock, flags);
-	list_add_tail(&io->list, &cc->write_thread_list);
+	p = &cc->write_tree.rb_node;
+	parent = NULL;
+	sector = io->sector;
+	while (*p) {
+		parent = *p;
+#define io_node rb_entry(parent, struct dm_crypt_io, rb_node)
+		if (sector < io_node->sector)
+			p = &io_node->rb_node.rb_left;
+		else
+			p = &io_node->rb_node.rb_right;
+#undef io_node
+	}
+	rb_link_node(&io->rb_node, parent, p);
+	rb_insert_color(&io->rb_node, &cc->write_tree);
+
 	wake_up_locked(&cc->write_thread_wait);
 	spin_unlock_irqrestore(&cc->write_thread_wait.lock, flags);
 }
@@ -1808,7 +1828,7 @@ static int crypt_ctr(struct dm_target *t
 	}
 
 	init_waitqueue_head(&cc->write_thread_wait);
-	INIT_LIST_HEAD(&cc->write_thread_list);
+	cc->write_tree = RB_ROOT;
 
 	cc->write_thread = kthread_create(dmcrypt_write, cc, "dmcrypt_write");
 	if (IS_ERR(cc->write_thread)) {
Commit	Line	Data
101a7448 ŁK	1	dm-crypt: sort writes
	2
	3	Write requests are sorted in a red-black tree structure and are submitted
	4	in the sorted order.
	5
	6	In theory the sorting should be performed by the underlying disk scheduler,
	7	however, in practice the disk scheduler accepts and sorts only 128 requests.
	8	In order to sort more requests, we need to implement our own sorting.
	9
	10	Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
	11
	12	---
	13	drivers/md/dm-crypt.c \| 50 +++++++++++++++++++++++++++++++++++---------------
	14	1 file changed, 35 insertions(+), 15 deletions(-)
	15
0a2e4279	16	Index: linux-3.14/drivers/md/dm-crypt.c
101a7448	17	===================================================================
0a2e4279 ŁK	18	--- linux-3.14.orig/drivers/md/dm-crypt.c 2014-04-04 21:06:22.000000000 +0200
	19	+++ linux-3.14/drivers/md/dm-crypt.c 2014-04-04 21:06:55.000000000 +0200
	20	@@ -22,6 +22,7 @@
101a7448 ŁK	21	#include <linux/backing-dev.h>
	22	#include <linux/atomic.h>
	23	#include <linux/scatterlist.h>
	24	+#include <linux/rbtree.h>
	25	#include <asm/page.h>
	26	#include <asm/unaligned.h>
	27	#include <crypto/hash.h>
0a2e4279	28	@@ -60,7 +61,7 @@ struct dm_crypt_io {
101a7448 ŁK	29	int error;
	30	sector_t sector;
	31
	32	- struct list_head list;
	33	+ struct rb_node rb_node;
0a2e4279	34	} CRYPTO_MINALIGN_ATTR;
101a7448 ŁK	35
101a7448 ŁK	36	struct dm_crypt_request {
0a2e4279	37	@@ -133,7 +134,7 @@ struct crypt_config {
101a7448 ŁK	38
	39	struct task_struct *write_thread;
	40	wait_queue_head_t write_thread_wait;
	41	- struct list_head write_thread_list;
	42	+ struct rb_root write_tree;
	43
	44	char *cipher;
	45	char *cipher_string;
0a2e4279	46	@@ -1177,7 +1178,7 @@ static int dmcrypt_write(void *data)
101a7448 ŁK	47	{
	48	struct crypt_config *cc = data;
	49	while (1) {
	50	- struct list_head local_list;
	51	+ struct rb_root write_tree;
	52	struct blk_plug plug;
	53
	54	DECLARE_WAITQUEUE(wait, current);
0a2e4279	55	@@ -1185,7 +1186,7 @@ static int dmcrypt_write(void *data)
101a7448 ŁK	56	spin_lock_irq(&cc->write_thread_wait.lock);
	57	continue_locked:
	58
	59	- if (!list_empty(&cc->write_thread_list))
	60	+ if (!RB_EMPTY_ROOT(&cc->write_tree))
	61	goto pop_from_list;
	62
	63	__set_current_state(TASK_INTERRUPTIBLE);
0a2e4279	64	@@ -1207,20 +1208,23 @@ continue_locked:
101a7448 ŁK	65	goto continue_locked;
	66
	67	pop_from_list:
	68	- local_list = cc->write_thread_list;
	69	- local_list.next->prev = &local_list;
	70	- local_list.prev->next = &local_list;
	71	- INIT_LIST_HEAD(&cc->write_thread_list);
	72	-
	73	+ write_tree = cc->write_tree;
	74	+ cc->write_tree = RB_ROOT;
	75	spin_unlock_irq(&cc->write_thread_wait.lock);
	76
	77	+ BUG_ON(rb_parent(write_tree.rb_node));
	78	+
	79	+ /*
	80	+ * Note: we cannot walk the tree here with rb_next because
	81	+ * the structures may be freed when kcryptd_io_write is called.
	82	+ */
	83	blk_start_plug(&plug);
	84	do {
	85	- struct dm_crypt_io *io = container_of(local_list.next,
	86	- struct dm_crypt_io, list);
	87	- list_del(&io->list);
	88	+ struct dm_crypt_io *io = rb_entry(rb_first(&write_tree),
	89	+ struct dm_crypt_io, rb_node);
	90	+ rb_erase(&io->rb_node, &write_tree);
	91	kcryptd_io_write(io);
	92	- } while (!list_empty(&local_list));
	93	+ } while (!RB_EMPTY_ROOT(&write_tree));
	94	blk_finish_plug(&plug);
	95	}
	96	return 0;
0a2e4279	97	@@ -1231,6 +1235,8 @@ static void kcryptd_crypt_write_io_submi
101a7448 ŁK	98	struct bio *clone = io->ctx.bio_out;
	99	struct crypt_config *cc = io->cc;
	100	unsigned long flags;
	101	+ sector_t sector;
	102	+ struct rb_node *p, parent;
	103
	104	if (unlikely(io->error < 0)) {
	105	crypt_free_buffer_pages(cc, clone);
0a2e4279 ŁK	106	@@ -1245,7 +1251,21 @@ static void kcryptd_crypt_write_io_submi
0a2e4279 ŁK	107	clone->bi_iter.bi_sector = cc->start + io->sector;
101a7448 ŁK	108
	109	spin_lock_irqsave(&cc->write_thread_wait.lock, flags);
	110	- list_add_tail(&io->list, &cc->write_thread_list);
	111	+ p = &cc->write_tree.rb_node;
	112	+ parent = NULL;
	113	+ sector = io->sector;
	114	+ while (*p) {
	115	+ parent = *p;
	116	+#define io_node rb_entry(parent, struct dm_crypt_io, rb_node)
	117	+ if (sector < io_node->sector)
	118	+ p = &io_node->rb_node.rb_left;
	119	+ else
	120	+ p = &io_node->rb_node.rb_right;
	121	+#undef io_node
	122	+ }
	123	+ rb_link_node(&io->rb_node, parent, p);
	124	+ rb_insert_color(&io->rb_node, &cc->write_tree);
	125	+
	126	wake_up_locked(&cc->write_thread_wait);
	127	spin_unlock_irqrestore(&cc->write_thread_wait.lock, flags);
	128	}
0a2e4279	129	@@ -1808,7 +1828,7 @@ static int crypt_ctr(struct dm_target *t
101a7448 ŁK	130	}
	131
	132	init_waitqueue_head(&cc->write_thread_wait);
	133	- INIT_LIST_HEAD(&cc->write_thread_list);
	134	+ cc->write_tree = RB_ROOT;
	135
	136	cc->write_thread = kthread_create(dmcrypt_write, cc, "dmcrypt_write");
	137	if (IS_ERR(cc->write_thread)) {