[PATCH 01/77] idr: fix a subtle bug in idr_get_next()

[PATCH 01/77] idr: fix a subtle bug in idr_get_next()

[Tejun Heo]

The iteration logic of idr_get_next() is borrowed mostly verbatim from
idr_for_each().  It walks down the tree looking for the slot matching
the current ID.  If the matching slot is not found, the ID is
incremented by the distance of single slot at the given level and
repeats.

The implementation assumes that during the whole iteration id is
aligned to the layer boundaries of the level closest to the leaf,
which is true for all iterations starting from zero or an existing
element and thus is fine for idr_for_each().

However, idr_get_next() may be given any point and if the starting id
hits in the middle of a non-existent layer, increment to the next
layer will end up skipping the same offset into it.  For example, an
IDR with IDs filled between [64, 127] would look like the following.

          [  0  64 ... ]
       /----/   |
       |        |
      NULL    [ 64 ... 127 ]

If idr_get_next() is called with 63 as the starting point, it will try
to follow down the pointer from 0.  As it is NULL, it will then try to
proceed to the next slot in the same level by adding the slot distance
at that level which is 64 - making the next try 127.  It goes around
the loop and finds and returns 127 skipping [64, 126].

Note that this bug also triggers in idr_for_each_entry() loop which
deletes during iteration as deletions can make layers go away leaving
the iteration with unaligned ID into missing layers.

Fix it by ensuring proceeding to the next slot doesn't carry over the
unaligned offset - ie. use round_up(id + 1, slot_distance) instead of
id += slot_distance.

Signed-off-by: Tejun Heo <tj@kernel.org>
Reported-by: David Teigland <teigland@redhat.com>
Cc: KAMEZAWA Hiroyuki <kamezawa.hiroyu@jp.fujitsu.com>
Cc: stable@vger.kernel.org
---
 lib/idr.c | 9 ++++++++-
 1 file changed, 8 insertions(+), 1 deletion(-)

diff --git a/lib/idr.c b/lib/idr.c
index 6482390..ca5aa00 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -625,7 +625,14 @@ void *idr_get_next(struct idr *idp, int *nextidp)
 			return p;
 		}
 
-		id += 1 << n;
+		/*
+		 * Proceed to the next layer at the current level.  Unlike
+		 * idr_for_each(), @id isn't guaranteed to be aligned to
+		 * layer boundary at this point and adding 1 << n may
+		 * incorrectly skip IDs.  Make sure we jump to the
+		 * beginning of the next layer using round_up().
+		 */
+		id = round_up(id + 1, 1 << n);
 		while (n < fls(id)) {
 			n += IDR_BITS;
 			p = *--paa;
-- 
1.8.1

[PATCH 21/77] block: fix synchronization and limit check in blk_alloc_devt()

[Tejun Heo]

idr allocation in blk_alloc_devt() wasn't synchronized against lookup
and removal, and its limit check was off by one - 1 << MINORBITS is
the number of minors allowed, not the maximum allowed minor.

Add locking and rename MAX_EXT_DEVT to NR_EXT_DEVT and fix limit
checking.

Signed-off-by: Tejun Heo <tj@kernel.org>
Acked-by: Jens Axboe <axboe@kernel.dk>
Cc: stable@vger.kernel.org
---
 block/genhd.c | 13 +++++++------
 1 file changed, 7 insertions(+), 6 deletions(-)

diff --git a/block/genhd.c b/block/genhd.c
index 2eb64a3..b1f34d0 100644
--- a/block/genhd.c
+++ b/block/genhd.c
@@ -26,7 +26,7 @@ static DEFINE_MUTEX(block_class_lock);
 struct kobject *block_depr;
 
 /* for extended dynamic devt allocation, currently only one major is used */
-#define MAX_EXT_DEVT		(1 << MINORBITS)
+#define NR_EXT_DEVT		(1 << MINORBITS)
 
 /* For extended devt allocation.  ext_devt_mutex prevents look up
  * results from going away underneath its user.
@@ -423,17 +423,18 @@ int blk_alloc_devt(struct hd_struct *part, dev_t *devt)
 	do {
 		if (!idr_pre_get(&ext_devt_idr, GFP_KERNEL))
 			return -ENOMEM;
+		mutex_lock(&ext_devt_mutex);
 		rc = idr_get_new(&ext_devt_idr, part, &idx);
+		if (!rc && idx >= NR_EXT_DEVT) {
+			idr_remove(&ext_devt_idr, idx);
+			rc = -EBUSY;
+		}
+		mutex_unlock(&ext_devt_mutex);
 	} while (rc == -EAGAIN);
 
 	if (rc)
 		return rc;
 
-	if (idx > MAX_EXT_DEVT) {
-		idr_remove(&ext_devt_idr, idx);
-		return -EBUSY;
-	}
-
 	*devt = MKDEV(BLOCK_EXT_MAJOR, blk_mangle_minor(idx));
 	return 0;
 }
-- 
1.8.1

[PATCH 28/77] firewire: add minor number range check to fw_device_init()

[Tejun Heo]

fw_device_init() didn't check whether the allocated minor number isn't
too large.  Fail if it goes overflows MINORBITS.

Signed-off-by: Tejun Heo <tj@kernel.org>
Suggested-by: Stefan Richter <stefanr@s5r6.in-berlin.de>
Acked-by: Stefan Richter <stefanr@s5r6.in-berlin.de>
Cc: stable@vger.kernel.org
---
 drivers/firewire/core-device.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/drivers/firewire/core-device.c b/drivers/firewire/core-device.c
index 3873d53..af3e8aa 100644
--- a/drivers/firewire/core-device.c
+++ b/drivers/firewire/core-device.c
@@ -1020,6 +1020,10 @@ static void fw_device_init(struct work_struct *work)
 	ret = idr_pre_get(&fw_device_idr, GFP_KERNEL) ?
 	      idr_get_new(&fw_device_idr, device, &minor) :
 	      -ENOMEM;
+	if (minor >= 1 << MINORBITS) {
+		idr_remove(&fw_device_idr, minor);
+		minor = -ENOSPC;
+	}
 	up_write(&fw_device_rwsem);
 
 	if (ret < 0)
-- 
1.8.1

Re: [PATCH 21/77] block: fix synchronization and limit check in blk_alloc_devt()

[Andrew Morton]

On Wed,  6 Feb 2013 11:39:53 -0800
Tejun Heo <tj@kernel.org> wrote:

> idr allocation in blk_alloc_devt() wasn't synchronized against lookup
> and removal, and its limit check was off by one - 1 << MINORBITS is
> the number of minors allowed, not the maximum allowed minor.
> 
> Add locking and rename MAX_EXT_DEVT to NR_EXT_DEVT and fix limit
> checking.
> 
> ...
>
> --- a/block/genhd.c
> +++ b/block/genhd.c
> @@ -26,7 +26,7 @@ static DEFINE_MUTEX(block_class_lock);
>  struct kobject *block_depr;
>  
>  /* for extended dynamic devt allocation, currently only one major is used */
> -#define MAX_EXT_DEVT		(1 << MINORBITS)
> +#define NR_EXT_DEVT		(1 << MINORBITS)
>  
>  /* For extended devt allocation.  ext_devt_mutex prevents look up
>   * results from going away underneath its user.
> @@ -423,17 +423,18 @@ int blk_alloc_devt(struct hd_struct *part, dev_t *devt)
>  	do {
>  		if (!idr_pre_get(&ext_devt_idr, GFP_KERNEL))
>  			return -ENOMEM;
> +		mutex_lock(&ext_devt_mutex);
>  		rc = idr_get_new(&ext_devt_idr, part, &idx);
> +		if (!rc && idx >= NR_EXT_DEVT) {
> +			idr_remove(&ext_devt_idr, idx);
> +			rc = -EBUSY;
> +		}
> +		mutex_unlock(&ext_devt_mutex);
>  	} while (rc == -EAGAIN);
>  
>  	if (rc)
>  		return rc;
>  
> -	if (idx > MAX_EXT_DEVT) {
> -		idr_remove(&ext_devt_idr, idx);
> -		return -EBUSY;
> -	}
> -
>  	*devt = MKDEV(BLOCK_EXT_MAJOR, blk_mangle_minor(idx));
>  	return 0;
>  }

This gets all tangled up with
http://ozlabs.org/~akpm/mmotm/broken-out/block-fix-ext_devt_idr-handling.patch,
which appears to solve the same issue.

What to do?

Re: [PATCH 21/77] block: fix synchronization and limit check in blk_alloc_devt()

[Tejun Heo]

Hello, Andrew.

On Wed, Feb 06, 2013 at 02:24:22PM -0800, Andrew Morton wrote:
> This gets all tangled up with
> http://ozlabs.org/~akpm/mmotm/broken-out/block-fix-ext_devt_idr-handling.patch,
> which appears to solve the same issue.
> 
> What to do?

Can you please drop 21 and 22?  Everything else shouldn't be affected
and we can sort these out later.  The actual deprecation patch is held
off for now anyway.

Thanks.

-- 
tejun

Re: [PATCH 21/77] block: fix synchronization and limit check in blk_alloc_devt()

[Andrew Morton]

On Wed, 6 Feb 2013 14:27:55 -0800
Tejun Heo <tj@kernel.org> wrote:

> Hello, Andrew.
> 
> On Wed, Feb 06, 2013 at 02:24:22PM -0800, Andrew Morton wrote:
> > This gets all tangled up with
> > http://ozlabs.org/~akpm/mmotm/broken-out/block-fix-ext_devt_idr-handling.patch,
> > which appears to solve the same issue.
> > 
> > What to do?
> 
> Can you please drop 21 and 22?  Everything else shouldn't be affected
> and we can sort these out later.  The actual deprecation patch is held
> off for now anyway.

hm, I could.  Instead I merged your patch on top of Tomas's and marked
Tomas's patch for -stable as well.  Sound OK?

Re: [PATCH 21/77] block: fix synchronization and limit check in blk_alloc_devt()

[Tejun Heo]

Hello,

On Wed, Feb 6, 2013 at 2:32 PM, Andrew Morton <akpm@linux-foundation.org> wrote:
>> Can you please drop 21 and 22?  Everything else shouldn't be affected
>> and we can sort these out later.  The actual deprecation patch is held
>> off for now anyway.
>
> hm, I could.  Instead I merged your patch on top of Tomas's and marked
> Tomas's patch for -stable as well.  Sound OK?

Sure, less work for me. :)

-- 
tejun