[PATCH 3/7] dm-crypt: avoid deadlock in mempools

[PATCH 3/7] dm-crypt: avoid deadlock in mempools

[Mikulas Patocka]

This patch fixes a theoretical deadlock introduced in the previous patch.

The function crypt_alloc_buffer may be called concurrently. If we allocate
from the mempool concurrently, there is a possibility of deadlock.
For example, if we have mempool of 256 pages, two processes, each wanting 256,
pages allocate from the mempool concurrently, it may deadlock in a situation
where both processes have allocated 128 pages and the mempool is exhausted.

In order to avoid this scenarios, we allocate the pages under a mutex.

In order to not degrade performance with excessive locking, we try
non-blocking allocations without a mutex first and if it fails, we fallback
to a blocking allocation with a mutex.

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

---
 drivers/md/dm-crypt.c |   41 ++++++++++++++++++++++++++++++++++++-----
 1 file changed, 36 insertions(+), 5 deletions(-)

Index: linux-3.18-rc1/drivers/md/dm-crypt.c
===================================================================
--- linux-3.18-rc1.orig/drivers/md/dm-crypt.c	2014-10-21 00:49:31.000000000 +0200
+++ linux-3.18-rc1/drivers/md/dm-crypt.c	2014-10-21 00:49:34.000000000 +0200
@@ -124,6 +124,7 @@ struct crypt_config {
 	mempool_t *req_pool;
 	mempool_t *page_pool;
 	struct bio_set *bs;
+	struct mutex bio_alloc_lock;
 
 	struct workqueue_struct *io_queue;
 	struct workqueue_struct *crypt_queue;
@@ -949,27 +950,51 @@ static void crypt_free_buffer_pages(stru
 /*
  * Generate a new unfragmented bio with the given size
  * This should never violate the device limitations
+ *
+ * This function may be called concurrently. If we allocate from the mempool
+ * concurrently, there is a possibility of deadlock. For example, if we have
+ * mempool of 256 pages, two processes, each wanting 256, pages allocate from
+ * the mempool concurrently, it may deadlock in a situation where both processes
+ * have allocated 128 pages and the mempool is exhausted.
+ *
+ * In order to avoid this scenarios, we allocate the pages under a mutex.
+ *
+ * In order to not degrade performance with excessive locking, we try
+ * non-blocking allocations without a mutex first and if it fails, we fallback
+ * to a blocking allocation with a mutex.
  */
 static struct bio *crypt_alloc_buffer(struct dm_crypt_io *io, unsigned size)
 {
 	struct crypt_config *cc = io->cc;
 	struct bio *clone;
 	unsigned int nr_iovecs = (size + PAGE_SIZE - 1) >> PAGE_SHIFT;
-	gfp_t gfp_mask = GFP_NOIO | __GFP_HIGHMEM;
-	unsigned i, len;
+	gfp_t gfp_mask = GFP_NOWAIT | __GFP_HIGHMEM;
+	unsigned i, len, remaining_size;
 	struct page *page;
 	struct bio_vec *bvec;
 
+retry:
+	if (unlikely(gfp_mask & __GFP_WAIT))
+		mutex_lock(&cc->bio_alloc_lock);
+
 	clone = bio_alloc_bioset(GFP_NOIO, nr_iovecs, cc->bs);
 	if (!clone)
-		return NULL;
+		goto return_clone;
 
 	clone_init(io, clone);
 
+	remaining_size = size;
+
 	for (i = 0; i < nr_iovecs; i++) {
 		page = mempool_alloc(cc->page_pool, gfp_mask);
+		if (!page) {
+			crypt_free_buffer_pages(cc, clone);
+			bio_put(clone);
+			gfp_mask |= __GFP_WAIT;
+			goto retry;
+		}
 
-		len = (size > PAGE_SIZE) ? PAGE_SIZE : size;
+		len = (remaining_size > PAGE_SIZE) ? PAGE_SIZE : remaining_size;
 
 		bvec = &clone->bi_io_vec[clone->bi_vcnt++];
 		bvec->bv_page = page;
@@ -978,9 +1003,13 @@ static struct bio *crypt_alloc_buffer(st
 
 		clone->bi_iter.bi_size += len;
 
-		size -= len;
+		remaining_size -= len;
 	}
 
+return_clone:
+	if (unlikely(gfp_mask & __GFP_WAIT))
+		mutex_unlock(&cc->bio_alloc_lock);
+
 	return clone;
 }
 
@@ -1679,6 +1708,8 @@ static int crypt_ctr(struct dm_target *t
 		goto bad;
 	}
 
+	mutex_init(&cc->bio_alloc_lock);
+
 	ret = -EINVAL;
 	if (sscanf(argv[2], "%llu%c", &tmpll, &dummy) != 1) {
 		ti->error = "Invalid iv_offset sector";

Re: [PATCH 3/7] dm-crypt: avoid deadlock in mempools

[Mike Snitzer]

On Fri, Feb 13 2015 at  8:24P -0500,
Mikulas Patocka <mpatocka@redhat.com> wrote:

> This patch fixes a theoretical deadlock introduced in the previous patch.
> 
> The function crypt_alloc_buffer may be called concurrently. If we allocate
> from the mempool concurrently, there is a possibility of deadlock.
> For example, if we have mempool of 256 pages, two processes, each wanting 256,
> pages allocate from the mempool concurrently, it may deadlock in a situation
> where both processes have allocated 128 pages and the mempool is exhausted.
> 
> In order to avoid this scenarios, we allocate the pages under a mutex.
> 
> In order to not degrade performance with excessive locking, we try
> non-blocking allocations without a mutex first and if it fails, we fallback
> to a blocking allocation with a mutex.
> 
> Signed-off-by: Mikulas Patocka <mpatocka@redhat.com>
> 
> ---
>  drivers/md/dm-crypt.c |   41 ++++++++++++++++++++++++++++++++++++-----
>  1 file changed, 36 insertions(+), 5 deletions(-)
> 
> Index: linux-3.18-rc1/drivers/md/dm-crypt.c
> ===================================================================
> --- linux-3.18-rc1.orig/drivers/md/dm-crypt.c	2014-10-21 00:49:31.000000000 +0200
> +++ linux-3.18-rc1/drivers/md/dm-crypt.c	2014-10-21 00:49:34.000000000 +0200
> @@ -124,6 +124,7 @@ struct crypt_config {
>  	mempool_t *req_pool;
>  	mempool_t *page_pool;
>  	struct bio_set *bs;
> +	struct mutex bio_alloc_lock;
>  
>  	struct workqueue_struct *io_queue;
>  	struct workqueue_struct *crypt_queue;
> @@ -949,27 +950,51 @@ static void crypt_free_buffer_pages(stru
>  /*
>   * Generate a new unfragmented bio with the given size
>   * This should never violate the device limitations
> + *
> + * This function may be called concurrently. If we allocate from the mempool
> + * concurrently, there is a possibility of deadlock. For example, if we have
> + * mempool of 256 pages, two processes, each wanting 256, pages allocate from
> + * the mempool concurrently, it may deadlock in a situation where both processes
> + * have allocated 128 pages and the mempool is exhausted.
> + *
> + * In order to avoid this scenarios, we allocate the pages under a mutex.
> + *
> + * In order to not degrade performance with excessive locking, we try
> + * non-blocking allocations without a mutex first and if it fails, we fallback
> + * to a blocking allocation with a mutex.
>   */

I folded this in:

diff --git a/drivers/md/dm-crypt.c b/drivers/md/dm-crypt.c
index cb075a7..6fc655d 100644
--- a/drivers/md/dm-crypt.c
+++ b/drivers/md/dm-crypt.c
@@ -968,10 +968,10 @@ static void crypt_free_buffer_pages(struct crypt_config *cc, struct bio *clone);
  * the mempool concurrently, it may deadlock in a situation where both processes
  * have allocated 128 pages and the mempool is exhausted.
  *
- * In order to avoid this scenarios, we allocate the pages under a mutex.
+ * In order to avoid this scenario we allocate the pages under a mutex.
  *
  * In order to not degrade performance with excessive locking, we try
- * non-blocking allocations without a mutex first and if it fails, we fallback
+ * non-blocking allocation without a mutex first and if it fails, we fallback
  * to a blocking allocation with a mutex.
  */
 static struct bio *crypt_alloc_buffer(struct dm_crypt_io *io, unsigned size)

Re: [PATCH 3/7] dm-crypt: avoid deadlock in mempools

[Mikulas Patocka]

On Fri, 13 Feb 2015, Mike Snitzer wrote:

>   * In order to not degrade performance with excessive locking, we try
> - * non-blocking allocations without a mutex first and if it fails, we fallback
> + * non-blocking allocation without a mutex first and if it fails, we fallback
>   * to a blocking allocation with a mutex.
>   */
>  static struct bio *crypt_alloc_buffer(struct dm_crypt_io *io, unsigned size)

There are multiple allocations, so I would leave plural there.

Mikulas

Re: [PATCH 3/7] dm-crypt: avoid deadlock in mempools

[Mike Snitzer]

On Fri, Feb 13 2015 at  5:09P -0500,
Mikulas Patocka <mpatocka@redhat.com> wrote:

> 
> 
> On Fri, 13 Feb 2015, Mike Snitzer wrote:
> 
> >   * In order to not degrade performance with excessive locking, we try
> > - * non-blocking allocations without a mutex first and if it fails, we fallback
> > + * non-blocking allocation without a mutex first and if it fails, we fallback
> >   * to a blocking allocation with a mutex.
> >   */
> >  static struct bio *crypt_alloc_buffer(struct dm_crypt_io *io, unsigned size)
> 
> There are multiple allocations, so I would leave plural there.

Fixed, and tweaked the headers (already did that last time around so
nothing new, you just didn't pick up my headers for your v2).  I pushed
your patchset to linux-next (for 3.21), see:
https://git.kernel.org/cgit/linux/kernel/git/device-mapper/linux-dm.git/log/?h=for-next

Ondrej and Milan, please let us know if you hit any problems with this
patchset and/or branch.

Re: [PATCH 3/7] dm-crypt: avoid deadlock in mempools

[Milan Broz]

On 02/14/2015 02:14 AM, Mike Snitzer wrote:
> On Fri, Feb 13 2015 at  5:09P -0500,
> Mikulas Patocka <mpatocka@redhat.com> wrote:
> 
>>
>>
>> On Fri, 13 Feb 2015, Mike Snitzer wrote:
>>
>>>   * In order to not degrade performance with excessive locking, we try
>>> - * non-blocking allocations without a mutex first and if it fails, we fallback
>>> + * non-blocking allocation without a mutex first and if it fails, we fallback
>>>   * to a blocking allocation with a mutex.
>>>   */
>>>  static struct bio *crypt_alloc_buffer(struct dm_crypt_io *io, unsigned size)
>>
>> There are multiple allocations, so I would leave plural there.
> 
> Fixed, and tweaked the headers (already did that last time around so
> nothing new, you just didn't pick up my headers for your v2).  I pushed
> your patchset to linux-next (for 3.21), see:
> https://git.kernel.org/cgit/linux/kernel/git/device-mapper/linux-dm.git/log/?h=for-next
> 
> Ondrej and Milan, please let us know if you hit any problems with this
> patchset and/or branch.

Will try to test it soon on some strange configurations :)

Just to be sure - nothing of this patchset is planned for 3.20?

(TBH I would like to see it upstream asap but too late for 3.20 here I guess...)

Thanks,
Milan

Re: [PATCH 3/7] dm-crypt: avoid deadlock in mempools

[Mike Snitzer]

On Mon, Feb 16 2015 at  4:31am -0500,
Milan Broz <mbroz@redhat.com> wrote:

> On 02/14/2015 02:14 AM, Mike Snitzer wrote:
> > On Fri, Feb 13 2015 at  5:09P -0500,
> > Mikulas Patocka <mpatocka@redhat.com> wrote:
> > 
> >>
> >>
> >> On Fri, 13 Feb 2015, Mike Snitzer wrote:
> >>
> >>>   * In order to not degrade performance with excessive locking, we try
> >>> - * non-blocking allocations without a mutex first and if it fails, we fallback
> >>> + * non-blocking allocation without a mutex first and if it fails, we fallback
> >>>   * to a blocking allocation with a mutex.
> >>>   */
> >>>  static struct bio *crypt_alloc_buffer(struct dm_crypt_io *io, unsigned size)
> >>
> >> There are multiple allocations, so I would leave plural there.
> > 
> > Fixed, and tweaked the headers (already did that last time around so
> > nothing new, you just didn't pick up my headers for your v2).  I pushed
> > your patchset to linux-next (for 3.21), see:
> > https://git.kernel.org/cgit/linux/kernel/git/device-mapper/linux-dm.git/log/?h=for-next
> > 
> > Ondrej and Milan, please let us know if you hit any problems with this
> > patchset and/or branch.
> 
> Will try to test it soon on some strange configurations :)

OK, see if you and Ondrej can re-test with urgency over the next few
days.
 
> Just to be sure - nothing of this patchset is planned for 3.20?
> 
> (TBH I would like to see it upstream asap but too late for 3.20 here I guess...)

I'm not opposed to sending them for the current merge (we still have a
week) purely because this code has been around for quite a long time
and is overdue for landing upstream.  Mikulas' recent change is
localized to adding the knob to shutoff offloading write bios to a
separate thread -- so nothing that should invalidate prior testing, etc.

Let me know what you guys think and please share results.  If we have
the results ideally we can decide by end of day Thursday.

I will rebase real quick to get these changes at the front of the
dm-for-3.20 followon work.

Mike

Re: [PATCH 3/7] dm-crypt: avoid deadlock in mempools

[Ondrej Kozina]

On 02/16/2015 02:58 PM, Mike Snitzer wrote:
> On Mon, Feb 16 2015 at  4:31am -0500,
> Milan Broz <mbroz@redhat.com> wrote:
>
>> On 02/14/2015 02:14 AM, Mike Snitzer wrote:
>>> On Fri, Feb 13 2015 at  5:09P -0500,
>>> Mikulas Patocka <mpatocka@redhat.com> wrote:
>>>
>>>>
>>>>
>>>> On Fri, 13 Feb 2015, Mike Snitzer wrote:
>>>>
>>>>>    * In order to not degrade performance with excessive locking, we try
>>>>> - * non-blocking allocations without a mutex first and if it fails, we fallback
>>>>> + * non-blocking allocation without a mutex first and if it fails, we fallback
>>>>>    * to a blocking allocation with a mutex.
>>>>>    */
>>>>>   static struct bio *crypt_alloc_buffer(struct dm_crypt_io *io, unsigned size)
>>>>
>>>> There are multiple allocations, so I would leave plural there.
>>>
>>> Fixed, and tweaked the headers (already did that last time around so
>>> nothing new, you just didn't pick up my headers for your v2).  I pushed
>>> your patchset to linux-next (for 3.21), see:
>>> https://git.kernel.org/cgit/linux/kernel/git/device-mapper/linux-dm.git/log/?h=for-next
>>>
>>> Ondrej and Milan, please let us know if you hit any problems with this
>>> patchset and/or branch.
>>
>> Will try to test it soon on some strange configurations :)
>
> OK, see if you and Ondrej can re-test with urgency over the next few
> days.
>

I'll post summary of results as a reply to the top post, including short 
commentary on why we decided to implement the switch for dmtable.

For anyone interested I'll also give links to full test results.

AFAIK the only thing that should be tested again at the moment is the 
switch itself.

O.

Re: [PATCH 3/7] dm-crypt: avoid deadlock in mempools

[Mike Snitzer]

On Mon, Feb 16 2015 at  9:11am -0500,
Ondrej Kozina <okozina@redhat.com> wrote:

> On 02/16/2015 02:58 PM, Mike Snitzer wrote:
> >On Mon, Feb 16 2015 at  4:31am -0500,
> >Milan Broz <mbroz@redhat.com> wrote:
> >
> >>On 02/14/2015 02:14 AM, Mike Snitzer wrote:
> >>>On Fri, Feb 13 2015 at  5:09P -0500,
> >>>Mikulas Patocka <mpatocka@redhat.com> wrote:
> >>>
> >>>>
> >>>>
> >>>>On Fri, 13 Feb 2015, Mike Snitzer wrote:
> >>>>
> >>>>>   * In order to not degrade performance with excessive locking, we try
> >>>>>- * non-blocking allocations without a mutex first and if it fails, we fallback
> >>>>>+ * non-blocking allocation without a mutex first and if it fails, we fallback
> >>>>>   * to a blocking allocation with a mutex.
> >>>>>   */
> >>>>>  static struct bio *crypt_alloc_buffer(struct dm_crypt_io *io, unsigned size)
> >>>>
> >>>>There are multiple allocations, so I would leave plural there.
> >>>
> >>>Fixed, and tweaked the headers (already did that last time around so
> >>>nothing new, you just didn't pick up my headers for your v2).  I pushed
> >>>your patchset to linux-next (for 3.21), see:
> >>>https://git.kernel.org/cgit/linux/kernel/git/device-mapper/linux-dm.git/log/?h=for-next
> >>>
> >>>Ondrej and Milan, please let us know if you hit any problems with this
> >>>patchset and/or branch.
> >>
> >>Will try to test it soon on some strange configurations :)
> >
> >OK, see if you and Ondrej can re-test with urgency over the next few
> >days.
> >
> 
> I'll post summary of results as a reply to the top post, including
> short commentary on why we decided to implement the switch for
> dmtable.
> 
> For anyone interested I'll also give links to full test results.
> 
> AFAIK the only thing that should be tested again at the moment is
> the switch itself.

There are now 2 switches.  But in order to test these switches you'll
need to re-establish the baseline without any patches.

See:
1) same_cpu_crypt
https://git.kernel.org/cgit/linux/kernel/git/device-mapper/linux-dm.git/commit/?h=dm-for-3.20&id=a3a0e3e8b98d9ada663023937eaddd7e54961a7d
2) submit_from_crypt_cpus
https://git.kernel.org/cgit/linux/kernel/git/device-mapper/linux-dm.git/commit/?h=dm-for-3.20&id=0f5d8e6ee758f7023e4353cca75d785b2d4f6abe

Please make sure you're using latest rebased dm-for-3.20 branch (tip is
commit b3c5fd3052492f1b8d060799d4f18be5a5438add).

Please test the 4 different permutations these flags can enable (so it
looks like it'd be runs against 5 different dm-cryot.ko permutations).

Thanks!