]>
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 | ||
39348b5e | 16 | Index: linux-3.10.4-fast/drivers/md/dm-crypt.c |
101a7448 | 17 | =================================================================== |
39348b5e ŁK |
18 | --- linux-3.10.4-fast.orig/drivers/md/dm-crypt.c 2013-07-31 17:03:27.000000000 +0200 |
19 | +++ linux-3.10.4-fast/drivers/md/dm-crypt.c 2013-07-31 17:03:30.000000000 +0200 | |
101a7448 ŁK |
20 | @@ -21,6 +21,7 @@ |
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> | |
28 | @@ -61,7 +62,7 @@ struct dm_crypt_io { | |
29 | int error; | |
30 | sector_t sector; | |
31 | ||
32 | - struct list_head list; | |
33 | + struct rb_node rb_node; | |
34 | }; | |
35 | ||
36 | struct dm_crypt_request { | |
37 | @@ -128,7 +129,7 @@ struct crypt_config { | |
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; | |
39348b5e | 46 | @@ -1011,7 +1012,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); | |
39348b5e | 55 | @@ -1019,7 +1020,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); | |
39348b5e | 64 | @@ -1041,20 +1042,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; | |
39348b5e | 97 | @@ -1065,6 +1069,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); | |
39348b5e | 106 | @@ -1079,7 +1085,21 @@ static void kcryptd_crypt_write_io_submi |
101a7448 ŁK |
107 | clone->bi_sector = cc->start + io->sector; |
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 | } | |
39348b5e | 129 | @@ -1639,7 +1659,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)) { |