dm-crypt-sort-requests.patch

   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
  16 Index: linux-3.10.4-fast/drivers/md/dm-crypt.c
  17 ===================================================================
  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
  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;
  46 @@ -1011,7 +1012,7 @@ static int dmcrypt_write(void *data)
  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);
  55 @@ -1019,7 +1020,7 @@ static int dmcrypt_write(void *data)
  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);
  64 @@ -1041,20 +1042,23 @@ continue_locked:
  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;
  97 @@ -1065,6 +1069,8 @@ static void kcryptd_crypt_write_io_submi
  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);
 106 @@ -1079,7 +1085,21 @@ static void kcryptd_crypt_write_io_submi
 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  }
 129 @@ -1639,7 +1659,7 @@ static int crypt_ctr(struct dm_target *t
 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)) {