]>
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 | |
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 |
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)) { |