3 Write requests are sorted in a red-black tree structure and are submitted
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.
10 Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
13 drivers/md/dm-crypt.c | 50 +++++++++++++++++++++++++++++++++++---------------
14 1 file changed, 35 insertions(+), 15 deletions(-)
16 Index: linux-3.14/drivers/md/dm-crypt.c
17 ===================================================================
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
21 #include <linux/backing-dev.h>
22 #include <linux/atomic.h>
23 #include <linux/scatterlist.h>
24 +#include <linux/rbtree.h>
26 #include <asm/unaligned.h>
27 #include <crypto/hash.h>
28 @@ -60,7 +61,7 @@ struct dm_crypt_io {
32 - struct list_head list;
33 + struct rb_node rb_node;
34 } CRYPTO_MINALIGN_ATTR;
36 struct dm_crypt_request {
37 @@ -133,7 +134,7 @@ struct crypt_config {
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;
46 @@ -1177,7 +1178,7 @@ static int dmcrypt_write(void *data)
48 struct crypt_config *cc = data;
50 - struct list_head local_list;
51 + struct rb_root write_tree;
54 DECLARE_WAITQUEUE(wait, current);
55 @@ -1185,7 +1186,7 @@ static int dmcrypt_write(void *data)
56 spin_lock_irq(&cc->write_thread_wait.lock);
59 - if (!list_empty(&cc->write_thread_list))
60 + if (!RB_EMPTY_ROOT(&cc->write_tree))
63 __set_current_state(TASK_INTERRUPTIBLE);
64 @@ -1207,20 +1208,23 @@ continue_locked:
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);
73 + write_tree = cc->write_tree;
74 + cc->write_tree = RB_ROOT;
75 spin_unlock_irq(&cc->write_thread_wait.lock);
77 + BUG_ON(rb_parent(write_tree.rb_node));
80 + * Note: we cannot walk the tree here with rb_next because
81 + * the structures may be freed when kcryptd_io_write is called.
83 blk_start_plug(&plug);
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);
92 - } while (!list_empty(&local_list));
93 + } while (!RB_EMPTY_ROOT(&write_tree));
94 blk_finish_plug(&plug);
97 @@ -1231,6 +1235,8 @@ static void kcryptd_crypt_write_io_submi
98 struct bio *clone = io->ctx.bio_out;
99 struct crypt_config *cc = io->cc;
102 + struct rb_node **p, *parent;
104 if (unlikely(io->error < 0)) {
105 crypt_free_buffer_pages(cc, clone);
106 @@ -1245,7 +1251,21 @@ static void kcryptd_crypt_write_io_submi
107 clone->bi_iter.bi_sector = cc->start + io->sector;
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;
113 + sector = io->sector;
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;
120 + p = &io_node->rb_node.rb_right;
123 + rb_link_node(&io->rb_node, parent, p);
124 + rb_insert_color(&io->rb_node, &cc->write_tree);
126 wake_up_locked(&cc->write_thread_wait);
127 spin_unlock_irqrestore(&cc->write_thread_wait.lock, flags);
129 @@ -1808,7 +1828,7 @@ static int crypt_ctr(struct dm_target *t
132 init_waitqueue_head(&cc->write_thread_wait);
133 - INIT_LIST_HEAD(&cc->write_thread_list);
134 + cc->write_tree = RB_ROOT;
136 cc->write_thread = kthread_create(dmcrypt_write, cc, "dmcrypt_write");
137 if (IS_ERR(cc->write_thread)) {