[PATCH] idr: prevent NULL deref on lookups before insertions

[PATCH] idr: prevent NULL deref on lookups before insertions

[Sasha Levin]

'hint' will be NULL if we're looking up before adding anything
to the IDR.

Signed-off-by: Sasha Levin <sasha.levin@oracle.com>
---
 include/linux/idr.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index aed2a0c..a6f38b5 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -113,7 +113,7 @@ static inline void *idr_find(struct idr *idr, int id)
 {
 	struct idr_layer *hint = rcu_dereference_raw(idr->hint);
 
-	if ((id & ~IDR_MASK) == hint->prefix)
+	if (hint && (id & ~IDR_MASK) == hint->prefix)
 		return rcu_dereference_raw(hint->ary[id & IDR_MASK]);
 
 	return idr_find_slowpath(idr, id);
-- 
1.8.1.2

Re: [PATCH] idr: prevent NULL deref on lookups before insertions

[Tejun Heo]

Hello, Sasha.

On Wed, Feb 20, 2013 at 10:44 AM, Sasha Levin <sasha.levin@oracle.com> wrote:
> 'hint' will be NULL if we're looking up before adding anything
> to the IDR.
>
> Signed-off-by: Sasha Levin <sasha.levin@oracle.com>

Andy Shevchenko	already posted fix (and free_layer() needs an update too).

Thanks.

-- 
tejun

Re: [PATCH] idr: prevent NULL deref on lookups before insertions

[Sasha Levin]

On 02/20/2013 01:45 PM, Tejun Heo wrote:
> Hello, Sasha.
> 
> On Wed, Feb 20, 2013 at 10:44 AM, Sasha Levin <sasha.levin@oracle.com> wrote:
>> 'hint' will be NULL if we're looking up before adding anything
>> to the IDR.
>>
>> Signed-off-by: Sasha Levin <sasha.levin@oracle.com>
> 
> Andy Shevchenko	already posted fix (and free_layer() needs an update too).

Sorry about that, didn't see one on lkml so I've sent mine.

What about a patch that deals with:

[   67.992946] ------------[ cut here ]------------
[   67.994133] WARNING: at lib/idr.c:669 idr_find_slowpath+0x36/0x170()
[   67.999650] Modules linked in:
[   68.000469] Pid: 7156, comm: trinity Tainted: G        W    3.8.0-next-20130220-sasha-00006-g3d6f01c-dirty #6
[   68.005136] Call Trace:
[   68.005719]  [<ffffffff8110c96b>] warn_slowpath_common+0x8b/0xc0
[   68.011168]  [<ffffffff8110c9b5>] warn_slowpath_null+0x15/0x20
[   68.012488]  [<ffffffff81a23506>] idr_find_slowpath+0x36/0x170
[   68.013805]  [<ffffffff8113bbcf>] __lock_timer+0x12f/0x240
[   68.015686]  [<ffffffff8113baa0>] ? posix_timer_fn+0xd0/0xd0
[   68.016946]  [<ffffffff8113c64c>] sys_timer_delete+0x2c/0x180
[   68.018478]  [<ffffffff83dab0f5>] ? tracesys+0x7e/0xe6
[   68.019647]  [<ffffffff83dab158>] tracesys+0xe1/0xe6
[   68.020941] ---[ end trace 6d02b1896fa2505b ]---


Thanks,
Sasha

[PATCH] posix-timer: don't call idr_find() w/ negative ID

[Tejun Heo]

Recent idr updates make idr_find() trigger WARN_ON_ONCE() before
returning NULL when a negative ID is specified.  Apparently,
posix-timer::__lock_timer() was depending on idr_find() returning NULL
on negative ID, thus triggering the new WARN_ON_ONCE().  Make
__lock_timer() first check whether @timer_id is negative and return
NULL without invoking idr_find() if so.

Note that the previous code was theoretically broken.  idr_find()
masked off the sign bit before performing lookup and if the matching
IDs were in use, it would have returned pointer for the incorrect
entry.

Signed-off-by: Tejun Heo <tj@kernel.org>
Reported-by: Sasha Levin <sasha.levin@oracle.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
---
Sasha, can you please test whether this makes the warning go away?

Thanks.

 kernel/posix-timers.c |    3 +++
 1 file changed, 3 insertions(+)

diff --git a/kernel/posix-timers.c b/kernel/posix-timers.c
index b51bb08..92465f9 100644
--- a/kernel/posix-timers.c
+++ b/kernel/posix-timers.c
@@ -637,6 +637,9 @@ static struct k_itimer *__lock_timer(timer_t timer_id, unsigned long *flags)
 {
 	struct k_itimer *timr;
 
+	if ((int)timer_id < 0)
+		return NULL;
+
 	rcu_read_lock();
 	timr = idr_find(&posix_timers_id, (int)timer_id);
 	if (timr) {

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Andrew Morton]

On Wed, 20 Feb 2013 13:01:16 -0800
Tejun Heo <tj@kernel.org> wrote:

> Recent idr updates make idr_find() trigger WARN_ON_ONCE() before
> returning NULL when a negative ID is specified.  Apparently,
> posix-timer::__lock_timer() was depending on idr_find() returning NULL
> on negative ID, thus triggering the new WARN_ON_ONCE().  Make
> __lock_timer() first check whether @timer_id is negative and return
> NULL without invoking idr_find() if so.
> 
> Note that the previous code was theoretically broken.  idr_find()
> masked off the sign bit before performing lookup and if the matching
> IDs were in use, it would have returned pointer for the incorrect
> entry.
> 
> ...
>
> --- a/kernel/posix-timers.c
> +++ b/kernel/posix-timers.c
> @@ -637,6 +637,9 @@ static struct k_itimer *__lock_timer(timer_t timer_id, unsigned long *flags)
>  {
>  	struct k_itimer *timr;
>  
> +	if ((int)timer_id < 0)
> +		return NULL;
> +
>  	rcu_read_lock();
>  	timr = idr_find(&posix_timers_id, (int)timer_id);
>  	if (timr) {

This is a bit risky - if some arch defines timer_t to be a u64 then we
will incorrectly treat 0x0000 0001 ffff ffff as a negative number. 
(That's a lot of timers!)

A fancy way of avoiding this is

	if (timer_id & ((typeof timer_id)1 << (sizeof(timer_id) - 1)))

(approximately ;))

But I think casting to (long) should be good enough?

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Sasha Levin]

On 02/20/2013 04:01 PM, Tejun Heo wrote:
> Recent idr updates make idr_find() trigger WARN_ON_ONCE() before
> returning NULL when a negative ID is specified.  Apparently,
> posix-timer::__lock_timer() was depending on idr_find() returning NULL
> on negative ID, thus triggering the new WARN_ON_ONCE().  Make
> __lock_timer() first check whether @timer_id is negative and return
> NULL without invoking idr_find() if so.
> 
> Note that the previous code was theoretically broken.  idr_find()
> masked off the sign bit before performing lookup and if the matching
> IDs were in use, it would have returned pointer for the incorrect
> entry.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>
> Reported-by: Sasha Levin <sasha.levin@oracle.com>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> ---
> Sasha, can you please test whether this makes the warning go away?

Looks like it did.


Thanks,
Sasha

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Tejun Heo]

Hello, Andrew.

On Wed, Feb 20, 2013 at 01:23:00PM -0800, Andrew Morton wrote:
> > @@ -637,6 +637,9 @@ static struct k_itimer *__lock_timer(timer_t timer_id, unsigned long *flags)
> >  {
> >  	struct k_itimer *timr;
> >  
> > +	if ((int)timer_id < 0)
> > +		return NULL;
> > +
> >  	rcu_read_lock();
> >  	timr = idr_find(&posix_timers_id, (int)timer_id);
> >  	if (timr) {
> 
> This is a bit risky - if some arch defines timer_t to be a u64 then we
> will incorrectly treat 0x0000 0001 ffff ffff as a negative number. 
> (That's a lot of timers!)
> 
> A fancy way of avoiding this is
> 
> 	if (timer_id & ((typeof timer_id)1 << (sizeof(timer_id) - 1)))
> 
> (approximately ;))
> 
> But I think casting to (long) should be good enough?

Sans WARN_ON_ONCE(), the code would behave the same as before, which
in turn, from what I can tell, is the behavior the code intended to
implement before idr_alloc() conversion.

If timer_id is being allocated from idr, a valid id can never go over
INT_MAX and returning NULL for any ID above that is the correct
behavior, I think.  If timer_t is larger than int, both (int) and
(long) castings wouldn't be useful.  Both will miss (1LU << 33) + 1
and idr_find() will end up looking for 1.

If we want to be strict, we would have to do, I think,

	if ((unsigned long long)timer_t > INT_MAX)

hopefully with some comments.  That said, if I'm grepping it right,
all archs define timer_t as int, so maybe we're just being paranoid.

Thanks.

-- 
tejun

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Thomas Gleixner]

On Wed, 20 Feb 2013, Tejun Heo wrote:

> Recent idr updates make idr_find() trigger WARN_ON_ONCE() before
> returning NULL when a negative ID is specified.  Apparently,
> posix-timer::__lock_timer() was depending on idr_find() returning NULL
> on negative ID, thus triggering the new WARN_ON_ONCE().  Make
> __lock_timer() first check whether @timer_id is negative and return
> NULL without invoking idr_find() if so.

I can grumpily accept the patch below as a quick hack fix, which can
go to stable as well, but not with such a patently misleading
changelog.

The changelog wants to document, that this is not a proper fix at all
and just a quick hack which can be nonintrusively applied to stable.

> Note that the previous code was theoretically broken.  idr_find()
> masked off the sign bit before performing lookup and if the matching
> IDs were in use, it would have returned pointer for the incorrect
> entry.

Brilliant code that. What's the purpose of having the idr id as an
"int" and then masking off the sign bit instead of simply refusing
negative id values in the idr code itself or simply making the id
"unsigned int" ?

Just look at the various f*ckedup users of MAX_IDR_MASK. Example:

drivers/pps/pps.c:

        err = idr_get_new(&pps_idr, pps, &pps->id);
        mutex_unlock(&pps_idr_lock);

        if (err < 0)
                return err;

        pps->id &= MAX_IDR_MASK;

Why the heck is that necessary? Either we get an error code and we
don't care about pps->id or idr_get_new() sets pps->id to a valid idr
id. If the idr code really returns a _valid_ id with the sign bit set,
then the idr code is broken beyond repair and needs to be fixed
instead of propagating that insanity all over the users.

Thanks,

	tglx

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Tejun Heo]

Hey, Thomas.

On Wed, Feb 20, 2013 at 10:38:36PM +0100, Thomas Gleixner wrote:
> I can grumpily accept the patch below as a quick hack fix, which can
> go to stable as well, but not with such a patently misleading
> changelog.
> 
> The changelog wants to document, that this is not a proper fix at all
> and just a quick hack which can be nonintrusively applied to stable.

I'm not sure about what type timer_t can be but if it can actually be
u64 as Andrew suggests, we probably want a different test guarding it.

> > Note that the previous code was theoretically broken.  idr_find()
> > masked off the sign bit before performing lookup and if the matching
> > IDs were in use, it would have returned pointer for the incorrect
> > entry.
> 
> Brilliant code that. What's the purpose of having the idr id as an
> "int" and then masking off the sign bit instead of simply refusing
> negative id values in the idr code itself or simply making the id
> "unsigned int" ?

Beats me.  The code has been like that since the beginning.  One of
the many oddities of idr implementation.  Patch to remove MAX_IDR_MASK
is already queued in -mm w/ other idr updates.

Thanks.

-- 
tejun

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Thomas Gleixner]

On Wed, 20 Feb 2013, Tejun Heo wrote:

> Hey, Thomas.
> 
> On Wed, Feb 20, 2013 at 10:38:36PM +0100, Thomas Gleixner wrote:
> > I can grumpily accept the patch below as a quick hack fix, which can
> > go to stable as well, but not with such a patently misleading
> > changelog.
> > 
> > The changelog wants to document, that this is not a proper fix at all
> > and just a quick hack which can be nonintrusively applied to stable.
> 
> I'm not sure about what type timer_t can be but if it can actually be
> u64 as Andrew suggests, we probably want a different test guarding it.
> 
> > > Note that the previous code was theoretically broken.  idr_find()
> > > masked off the sign bit before performing lookup and if the matching
> > > IDs were in use, it would have returned pointer for the incorrect
> > > entry.
> > 
> > Brilliant code that. What's the purpose of having the idr id as an
> > "int" and then masking off the sign bit instead of simply refusing
> > negative id values in the idr code itself or simply making the id
> > "unsigned int" ?
> 
> Beats me.  The code has been like that since the beginning.  One of
> the many oddities of idr implementation.  Patch to remove MAX_IDR_MASK
> is already queued in -mm w/ other idr updates.

Missed that, but good to know that this insanity is going to be gone
soon.

Thanks,

	tglx

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Tejun Heo]

On Wed, Feb 20, 2013 at 10:47:12PM +0100, Thomas Gleixner wrote:
> Missed that, but good to know that this insanity is going to be gone
> soon.

Yeah, idr at least shouldn't be insane interface-wise.  Its
implementation still makes me want to drive pencils into my eyes and
ida still needs some love tho.  Some other time, hopefully.

-- 
tejun

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Andrew Morton]

On Wed, 20 Feb 2013 13:37:01 -0800
Tejun Heo <tj@kernel.org> wrote:

> Hello, Andrew.
> 
> On Wed, Feb 20, 2013 at 01:23:00PM -0800, Andrew Morton wrote:
> > > @@ -637,6 +637,9 @@ static struct k_itimer *__lock_timer(timer_t timer_id, unsigned long *flags)
> > >  {
> > >  	struct k_itimer *timr;
> > >  
> > > +	if ((int)timer_id < 0)
> > > +		return NULL;
> > > +
> > >  	rcu_read_lock();
> > >  	timr = idr_find(&posix_timers_id, (int)timer_id);
> > >  	if (timr) {
> > 
> > This is a bit risky - if some arch defines timer_t to be a u64 then we
> > will incorrectly treat 0x0000 0001 ffff ffff as a negative number. 
> > (That's a lot of timers!)
> > 
> > A fancy way of avoiding this is
> > 
> > 	if (timer_id & ((typeof timer_id)1 << (sizeof(timer_id) - 1)))
> > 
> > (approximately ;))
> > 
> > But I think casting to (long) should be good enough?
> 
> Sans WARN_ON_ONCE(), the code would behave the same as before, which
> in turn, from what I can tell, is the behavior the code intended to
> implement before idr_alloc() conversion.
> 
> If timer_id is being allocated from idr, a valid id can never go over
> INT_MAX and returning NULL for any ID above that is the correct
> behavior, I think.  If timer_t is larger than int, both (int) and
> (long) castings wouldn't be useful.  Both will miss (1LU << 33) + 1
> and idr_find() will end up looking for 1.
> 
> If we want to be strict, we would have to do, I think,
> 
> 	if ((unsigned long long)timer_t > INT_MAX)
> 
> hopefully with some comments.  That said, if I'm grepping it right,
> all archs define timer_t as int, so maybe we're just being paranoid.
> 

Sure, it's unlikely to cause a problem in practice.  Maybe five years
from now, after idr has been cleaned up and switched to 64-bit, we've
left a little hand grenade for someone.  It would be good to
future-safe it in some fashion.

I wonder if we should add some generic facility to handle this:

/*
 * Query whether an unsigned type is `negative' when we don't know its size
 */
#define msb_is_set(v)	{ implementation goes here ;) }

Maybe not justified, dunno...

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Tejun Heo]

On Wed, Feb 20, 2013 at 02:05:51PM -0800, Andrew Morton wrote:
> Sure, it's unlikely to cause a problem in practice.  Maybe five years
> from now, after idr has been cleaned up and switched to 64-bit, we've
> left a little hand grenade for someone.  It would be good to
> future-safe it in some fashion.
> 
> I wonder if we should add some generic facility to handle this:
> 
> /*
>  * Query whether an unsigned type is `negative' when we don't know its size
>  */
> #define msb_is_set(v)	{ implementation goes here ;) }
> 
> Maybe not justified, dunno...

The thing is it's not only about MSB.  Any bits beyond 1 << 31 are
problematic, so we want a range test.

Thanks.

-- 
tejun

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Sasha Levin]

On 02/20/2013 05:05 PM, Andrew Morton wrote:
> I wonder if we should add some generic facility to handle this:
> 
> /*
>  * Query whether an unsigned type is `negative' when we don't know its size
>  */
> #define msb_is_set(v)	{ implementation goes here ;) }
> 
> Maybe not justified, dunno...

I do think that if you have to resort to using something like that there's
something terribly wrong with the code somewhere else, and that other thing
should be fixed first.

Maybe digging into the timers code and seeing why this is needed there will
prove me wrong...


Thanks,
Sasha

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Tejun Heo]

On Wed, Feb 20, 2013 at 2:10 PM, Sasha Levin <sasha.levin@oracle.com> wrote:
> I do think that if you have to resort to using something like that there's
> something terribly wrong with the code somewhere else, and that other thing
> should be fixed first.
>
> Maybe digging into the timers code and seeing why this is needed there will
> prove me wrong...

The problem is that userland can feed us any timer_t which makes it
necessary to properly sanitize the value before using it.

Thanks.

-- 
tejun

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Sasha Levin]

On 02/20/2013 05:12 PM, Tejun Heo wrote:
> On Wed, Feb 20, 2013 at 2:10 PM, Sasha Levin <sasha.levin@oracle.com> wrote:
>> I do think that if you have to resort to using something like that there's
>> something terribly wrong with the code somewhere else, and that other thing
>> should be fixed first.
>>
>> Maybe digging into the timers code and seeing why this is needed there will
>> prove me wrong...
> 
> The problem is that userland can feed us any timer_t which makes it
> necessary to properly sanitize the value before using it.

Why can the timer be negative in the first place though? Why isn't the timer
defined as an 'unsigned int' instead of an 'int' so that all values of timer
would be legitimate?


Thanks,
sasha

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Tejun Heo]

On Wed, Feb 20, 2013 at 2:15 PM, Sasha Levin <sasha.levin@oracle.com> wrote:
> Why can the timer be negative in the first place though? Why isn't the timer
> defined as an 'unsigned int' instead of an 'int' so that all values of timer
> would be legitimate?

No idea but it's userland visible thing. No point in arguing about it.

Thanks.

-- 
tejun

[PATCH] posix-timer: don't call idr_find() w/ out-of-range ID

[Tejun Heo]

When idr_find() is fed a negative ID, it used to look up the ID
ignoring the sign bit before recent ("idr: remove MAX_IDR_MASK and
move left MAX_IDR_* into idr.c") patch, and triggers WARN_ON_ONCE()
after it.

__lock_timer() feeds timer_id from userland directly to idr_find()
without sanitizing it which can trigger the above malfunctions.  Add a
range check on @timer_id before invoking idr_find() in __lock_timer().

While timer_t is defined as int by all archs at the moment, Andrew
worries that it may be defined as a larger type later on.  Make the
test cover larger integers too so that it at least is guaranteed to
not return the wrong timer.

Signed-off-by: Tejun Heo <tj@kernel.org>
Reported-by: Sasha Levin <sasha.levin@oracle.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: stable@vger.kernel.org
---
 kernel/posix-timers.c |    7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/kernel/posix-timers.c b/kernel/posix-timers.c
index b51bb08..6edbb2c 100644
--- a/kernel/posix-timers.c
+++ b/kernel/posix-timers.c
@@ -637,6 +637,13 @@ static struct k_itimer *__lock_timer(timer_t timer_id, unsigned long *flags)
 {
 	struct k_itimer *timr;
 
+	/*
+	 * timer_t could be any type >= int and we want to make sure any
+	 * @timer_id outside positive int range fails lookup.
+	 */
+	if ((unsigned long long)timer_id > INT_MAX)
+		return NULL;
+
 	rcu_read_lock();
 	timr = idr_find(&posix_timers_id, (int)timer_id);
 	if (timr) {

Re: [PATCH] posix-timer: don't call idr_find() w/ out-of-range ID

[Thomas Gleixner]

On Wed, 20 Feb 2013, Tejun Heo wrote:

> When idr_find() is fed a negative ID, it used to look up the ID
> ignoring the sign bit before recent ("idr: remove MAX_IDR_MASK and
> move left MAX_IDR_* into idr.c") patch, and triggers WARN_ON_ONCE()
> after it.
> 
> __lock_timer() feeds timer_id from userland directly to idr_find()
> without sanitizing it which can trigger the above malfunctions.  Add a
> range check on @timer_id before invoking idr_find() in __lock_timer().
> 
> While timer_t is defined as int by all archs at the moment, Andrew
> worries that it may be defined as a larger type later on.  Make the
> test cover larger integers too so that it at least is guaranteed to
> not return the wrong timer.

Again. I totaly agree with that for stable, but I disagree that this
is the real fix.

idr_find() should simply return NULL, if "id < 0". Is it that hard?
 
Thanks,

	tglx

Re: [PATCH] posix-timer: don't call idr_find() w/ out-of-range ID

[Tejun Heo]

Hello, Thomas.

On Thu, Feb 21, 2013 at 12:01:07AM +0100, Thomas Gleixner wrote:
> idr_find() should simply return NULL, if "id < 0". Is it that hard?

It already does but w/ WARN_ON_ONCE().  The WARN_ON_ONCE() is there
mostly as a transitional precaution.  As the previous idr_find()
behavior was extremely weird, just in case someone was depending on
ignoring the msb for example, it would be nice to be able to identify
the ones which are passing in negative ids, at least for a release
cycle or two.

Thanks.

-- 
tejun

Re: [PATCH] posix-timer: don't call idr_find() w/ negative ID

[Thomas Gleixner]

On Wed, 20 Feb 2013, Andrew Morton wrote:
> On Wed, 20 Feb 2013 13:37:01 -0800
> Tejun Heo <tj@kernel.org> wrote:
> > hopefully with some comments.  That said, if I'm grepping it right,
> > all archs define timer_t as int, so maybe we're just being paranoid.
> > 
> 
> Sure, it's unlikely to cause a problem in practice.  Maybe five years
> from now, after idr has been cleaned up and switched to 64-bit, we've
> left a little hand grenade for someone.  It would be good to
> future-safe it in some fashion.
> 
> I wonder if we should add some generic facility to handle this:
> 
> /*
>  * Query whether an unsigned type is `negative' when we don't know its size
>  */
> #define msb_is_set(v)	{ implementation goes here ;) }
> 
> Maybe not justified, dunno...

First of all the compiler should warn you about the truncation. And
aside of that:

+ BUILD_BUG_ON(sizeof(timer_t) != sizeof(int));

and then we can worry about that esoteric architecture when that thing
triggers?

Aside of that, due to the pending checkpoint/restore stuff this user
might be gone in the near future.

Thanks,

	tglx

Re: [PATCH] posix-timer: don't call idr_find() w/ out-of-range ID

[Thomas Gleixner]

On Wed, 20 Feb 2013, Tejun Heo wrote:

> Hello, Thomas.
> 
> On Thu, Feb 21, 2013 at 12:01:07AM +0100, Thomas Gleixner wrote:
> > idr_find() should simply return NULL, if "id < 0". Is it that hard?
> 
> It already does but w/ WARN_ON_ONCE().  The WARN_ON_ONCE() is there
> mostly as a transitional precaution.  As the previous idr_find()
> behavior was extremely weird, just in case someone was depending on
> ignoring the msb for example, it would be nice to be able to identify
> the ones which are passing in negative ids, at least for a release
> cycle or two.

No objection, but please add this to the changelog and the comment.

Thanks,

	tglx

[PATCH UPDATED] posix-timer: don't call idr_find() w/ out-of-range ID

[Tejun Heo]

When idr_find() is fed a negative ID, it used to look up the ID
ignoring the sign bit before recent ("idr: remove MAX_IDR_MASK and
move left MAX_IDR_* into idr.c") patch, and triggers WARN_ON_ONCE()
after it.

__lock_timer() feeds timer_id from userland directly to idr_find()
without sanitizing it which can trigger the above malfunctions.  Add a
range check on @timer_id before invoking idr_find() in __lock_timer().

While timer_t is defined as int by all archs at the moment, Andrew
worries that it may be defined as a larger type later on.  Make the
test cover larger integers too so that it at least is guaranteed to
not return the wrong timer.

Note that WARN_ON_ONCE() in idr_find() on id < 0 is transitional
precaution while moving away from ignoring MSB.  Once it's gone we can
remove the guard as long as timer_t isn't larger than int.

Signed-off-by: Tejun Heo <tj@kernel.org>nnn
Reported-by: Sasha Levin <sasha.levin@oracle.com>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: stable@vger.kernel.org
---
Given that larger timer_t is possible, at least theoretically, it
probably is better to keep the guard even if idr_find() is later
updated, so not marking the guard as to be removed.

Will send a separate patch to add comment on top of WARN_ON_ONCE() in
idr_find().

Thanks.

 kernel/posix-timers.c |    7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/kernel/posix-timers.c b/kernel/posix-timers.c
index b51bb08..6edbb2c 100644
--- a/kernel/posix-timers.c
+++ b/kernel/posix-timers.c
@@ -637,6 +637,13 @@ static struct k_itimer *__lock_timer(timer_t timer_id, unsigned long *flags)
 {
 	struct k_itimer *timr;
 
+	/*
+	 * timer_t could be any type >= int and we want to make sure any
+	 * @timer_id outside positive int range fails lookup.
+	 */
+	if ((unsigned long long)timer_id > INT_MAX)
+		return NULL;
+
 	rcu_read_lock();
 	timr = idr_find(&posix_timers_id, (int)timer_id);
 	if (timr) {

[PATCH] idr: explain WARN_ON_ONCE() on negative IDs out-of-range ID

[Tejun Heo]

Until recently, when an negative ID is specified, idr functions used
to ignore the sign bit and proceeded with the operation with the rest
of bits, which is bizarre and error-prone.  The behavior recently got
changed so that negative IDs are treated as invalid but we're
triggering WARN_ON_ONCE() on negative IDs just in case somebody was
depending on the sign bit being ignored, so that those can be detected
and fixed easily.

We only need this for a while.  Explain why WARN_ON_ONCE()s are there
and that they can be removed later.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
---
 lib/idr.c |   10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/lib/idr.c b/lib/idr.c
index 5c772dc..134a61a 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -569,6 +569,7 @@ void idr_remove(struct idr *idp, int id)
 	struct idr_layer *p;
 	struct idr_layer *to_free;
 
+	/* see comment in idr_find_slowpath() */
 	if (WARN_ON_ONCE(id < 0))
 		return;
 
@@ -666,6 +667,14 @@ void *idr_find_slowpath(struct idr *idp, int id)
 	int n;
 	struct idr_layer *p;
 
+	/*
+	 * If @id is negative, idr_find() used to ignore the sign bit and
+	 * performed lookup with the rest of bits, which is weird and can
+	 * lead to very obscure bugs.  We're now returning NULL for all
+	 * negative IDs but just in case somebody was depending on the sign
+	 * bit being ignored, let's trigger WARN_ON_ONCE() so that they can
+	 * be detected and fixed.  WARN_ON_ONCE() can later be removed.
+	 */
 	if (WARN_ON_ONCE(id < 0))
 		return NULL;
 
@@ -815,6 +824,7 @@ void *idr_replace(struct idr *idp, void *ptr, int id)
 	int n;
 	struct idr_layer *p, *old_p;
 
+	/* see comment in idr_find_slowpath() */
 	if (WARN_ON_ONCE(id < 0))
 		return ERR_PTR(-EINVAL);
 

Re: [PATCH] idr: explain WARN_ON_ONCE() on negative IDs out-of-range ID

[Thomas Gleixner]

On Wed, 20 Feb 2013, Tejun Heo wrote:

> Until recently, when an negative ID is specified, idr functions used
> to ignore the sign bit and proceeded with the operation with the rest
> of bits, which is bizarre and error-prone.  The behavior recently got
> changed so that negative IDs are treated as invalid but we're
> triggering WARN_ON_ONCE() on negative IDs just in case somebody was
> depending on the sign bit being ignored, so that those can be detected
> and fixed easily.
> 
> We only need this for a while.  Explain why WARN_ON_ONCE()s are there
> and that they can be removed later.
> 
> Signed-off-by: Tejun Heo <tj@kernel.org>

Acked-by : Thomas Gleixner <tglx@linutronix.de>

[tip:timers/urgent] posix-timer: Don't call idr_find() with out-of-range ID

[tip-bot for Tejun Heo]

Commit-ID:  e182bb38d7db7494fa5dcd82da17fe0dedf60ecf
Gitweb:     http://git.kernel.org/tip/e182bb38d7db7494fa5dcd82da17fe0dedf60ecf
Author:     Tejun Heo <tj@kernel.org>
AuthorDate: Wed, 20 Feb 2013 15:24:12 -0800
Committer:  Thomas Gleixner <tglx@linutronix.de>
CommitDate: Thu, 21 Feb 2013 17:28:29 +0100

posix-timer: Don't call idr_find() with out-of-range ID

When idr_find() was fed a negative ID, it used to look up the ID
ignoring the sign bit before recent ("idr: remove MAX_IDR_MASK and
move left MAX_IDR_* into idr.c") patch. Now a negative ID triggers
a WARN_ON_ONCE().

__lock_timer() feeds timer_id from userland directly to idr_find()
without sanitizing it which can trigger the above malfunctions.  Add a
range check on @timer_id before invoking idr_find() in __lock_timer().

While timer_t is defined as int by all archs at the moment, Andrew
worries that it may be defined as a larger type later on.  Make the
test cover larger integers too so that it at least is guaranteed to
not return the wrong timer.

Note that WARN_ON_ONCE() in idr_find() on id < 0 is transitional
precaution while moving away from ignoring MSB.  Once it's gone we can
remove the guard as long as timer_t isn't larger than int.

Signed-off-by: Tejun Heo <tj@kernel.org>nnn
Reported-by: Sasha Levin <sasha.levin@oracle.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: stable@vger.kernel.org
Link: http://lkml.kernel.org/r/20130220232412.GL3570@htj.dyndns.org
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 kernel/posix-timers.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/kernel/posix-timers.c b/kernel/posix-timers.c
index 10349d5..7edfe4b 100644
--- a/kernel/posix-timers.c
+++ b/kernel/posix-timers.c
@@ -639,6 +639,13 @@ static struct k_itimer *__lock_timer(timer_t timer_id, unsigned long *flags)
 {
 	struct k_itimer *timr;
 
+	/*
+	 * timer_t could be any type >= int and we want to make sure any
+	 * @timer_id outside positive int range fails lookup.
+	 */
+	if ((unsigned long long)timer_id > INT_MAX)
+		return NULL;
+
 	rcu_read_lock();
 	timr = idr_find(&posix_timers_id, (int)timer_id);
 	if (timr) {