Re: [PATCH] Bug in mm/thrash.c function grab_swap_token()

Re: [PATCH] Bug in mm/thrash.c function grab_swap_token()

[Andrew Morton]

On Thu, 10 May 2007 15:24:00 +0300
Mika Kukkonen <mikukkon@miku.homelinux.net> wrote:

> Following bug was uncovered by compiling with '-W' flag:
> 
>   CC      mm/thrash.o
> mm/thrash.c: In function a??grab_swap_tokena??:
> mm/thrash.c:52: warning: comparison of unsigned expression < 0 is always false
> 
> Variable token_priority is unsigned, so decrementing first and then
> checking the result does not work; fixed by reversing the test, patch
> attached (compile tested only). 
> 
> I am not sure if likely() makes much sense in this new situation, but
> I'll let somebody else to make a decision on that.
> 
> Signed-off-by: Mika Kukkonen <mikukkon@iki.fi>
> 
> diff --git a/mm/thrash.c b/mm/thrash.c
> index 9ef9071..c4c5205 100644
> --- a/mm/thrash.c
> +++ b/mm/thrash.c
> @@ -48,9 +48,8 @@ void grab_swap_token(void)
>  		if (current_interval < current->mm->last_interval)
>  			current->mm->token_priority++;
>  		else {
> -			current->mm->token_priority--;
> -			if (unlikely(current->mm->token_priority < 0))
> -				current->mm->token_priority = 0;
> +			if (likely(current->mm->token_priority > 0))
> +				current->mm->token_priority--;
>  		}
>  		/* Check if we deserve the token */
>  		if (current->mm->token_priority >

argh.

This has potential to cause large changes in system performance.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] Bug in mm/thrash.c function grab_swap_token()

[Ashwin Chaugule]

On Thu, 2007-05-10 at 15:29 -0700, Andrew Morton wrote:
> On Thu, 10 May 2007 15:24:00 +0300
> Mika Kukkonen <mikukkon@miku.homelinux.net> wrote:
> 
> > Following bug was uncovered by compiling with '-W' flag:
> > 
> >   CC      mm/thrash.o
> > mm/thrash.c: In function A?AcAcA?A!A?A?grab_swap_tokenA?AcAcA?A!AcA?Ac:
> > mm/thrash.c:52: warning: comparison of unsigned expression < 0 is always false
> > 
> > Variable token_priority is unsigned, so decrementing first and then
> > checking the result does not work; fixed by reversing the test, patch
> > attached (compile tested only). 
> > 
> > I am not sure if likely() makes much sense in this new situation, but
> > I'll let somebody else to make a decision on that.
> > 
> > Signed-off-by: Mika Kukkonen <mikukkon@iki.fi>
> > 
> > diff --git a/mm/thrash.c b/mm/thrash.c
> > index 9ef9071..c4c5205 100644
> > --- a/mm/thrash.c
> > +++ b/mm/thrash.c
> > @@ -48,9 +48,8 @@ void grab_swap_token(void)
> >  		if (current_interval < current->mm->last_interval)
> >  			current->mm->token_priority++;
> >  		else {
> > -			current->mm->token_priority--;
> > -			if (unlikely(current->mm->token_priority < 0))
> > -				current->mm->token_priority = 0;
> > +			if (likely(current->mm->token_priority > 0))
> > +				current->mm->token_priority--;
> >  		}
> >  		/* Check if we deserve the token */
> >  		if (current->mm->token_priority >
> 
> argh.
> 
> This has potential to cause large changes in system performance.

I'm not sure how. Although, I think the logic still remains the same.
IOW, if the prio decrements to zero, it will remain zero until it
contends for token rapidly. 

The likely part is unnecessary.

Thanks Mika. Let me submit this patch, coz I'd like to change my email
address in thrash.c



--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] Bug in mm/thrash.c function grab_swap_token()

[ashwin chaugule]

This patch fixes a bug discovered by Mika Kukkonen in the swap token
code. An unsigned int was being decremented and then checked for < 0.

Signed-off-by: Ashwin Chaugule <ashwin.chaugule@gmail.com>

diff --git a/mm/thrash.c b/mm/thrash.c
index 9ef9071..60f3344 100644
--- a/mm/thrash.c
+++ b/mm/thrash.c
@@ -8,7 +8,7 @@
  * Simple token based thrashing protection, using the algorithm
  * described in:  http://www.cs.wm.edu/~sjiang/token.pdf
  *
- * Sep 2006, Ashwin Chaugule <ashwin.chaugule@celunite.com>
+ * Sep 2006, Ashwin Chaugule <ashwin.chaugule@gmail.com>
  * Improved algorithm to pass token:
  * Each task has a priority which is incremented if it contended
  * for the token in an interval less than its previous attempt.
@@ -48,9 +48,8 @@ void grab_swap_token(void)
                if (current_interval < current->mm->last_interval)
                        current->mm->token_priority++;
                else {
-                       current->mm->token_priority--;
-                       if (unlikely(current->mm->token_priority < 0))
-                               current->mm->token_priority = 0;
+                       if (current->mm->token_priority > 0)
+                               current->mm->token_priority--;
                }
                /* Check if we deserve the token */
                if (current->mm->token_priority >

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] Bug in mm/thrash.c function grab_swap_token()

[Rik van Riel]

Ashwin Chaugule wrote:
> On Thu, 2007-05-10 at 15:29 -0700, Andrew Morton wrote:
>> On Thu, 10 May 2007 15:24:00 +0300
>> Mika Kukkonen <mikukkon@miku.homelinux.net> wrote:
>>
>>> Following bug was uncovered by compiling with '-W' flag:
>>>
>>>   CC      mm/thrash.o
>>> mm/thrash.c: In function A?AcAcA?A!A?A?grab_swap_tokenA?AcAcA?A!AcA?Ac:
>>> mm/thrash.c:52: warning: comparison of unsigned expression < 0 is always false
>>>
>>> Variable token_priority is unsigned, so decrementing first and then
>>> checking the result does not work; fixed by reversing the test, patch
>>> attached (compile tested only). 
>>>
>>> I am not sure if likely() makes much sense in this new situation, but
>>> I'll let somebody else to make a decision on that.
>>>
>>> Signed-off-by: Mika Kukkonen <mikukkon@iki.fi>
>>>
>>> diff --git a/mm/thrash.c b/mm/thrash.c
>>> index 9ef9071..c4c5205 100644
>>> --- a/mm/thrash.c
>>> +++ b/mm/thrash.c
>>> @@ -48,9 +48,8 @@ void grab_swap_token(void)
>>>  		if (current_interval < current->mm->last_interval)
>>>  			current->mm->token_priority++;
>>>  		else {
>>> -			current->mm->token_priority--;
>>> -			if (unlikely(current->mm->token_priority < 0))
>>> -				current->mm->token_priority = 0;
>>> +			if (likely(current->mm->token_priority > 0))
>>> +				current->mm->token_priority--;
>>>  		}
>>>  		/* Check if we deserve the token */
>>>  		if (current->mm->token_priority >
>> argh.
>>
>> This has potential to cause large changes in system performance.
> 
> I'm not sure how. Although, I think the logic still remains the same.
> IOW, if the prio decrements to zero, it will remain zero until it
> contends for token rapidly. 

The problem is that the original code would decrement an
unsigned variable beyond zero, underflowing to a number
just under 2^32...

That would make the process basically a permanent owner
of the swap token.

-- 
Politics is the struggle between those who want to make their country
the best in the world, and those who believe it already is.  Each group
calls the other unpatriotic.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: [PATCH] Bug in mm/thrash.c function grab_swap_token()

[ashwin chaugule]

> >>> @@ -48,9 +48,8 @@ void grab_swap_token(void)
> >>>             if (current_interval < current->mm->last_interval)
> >>>                     current->mm->token_priority++;
> >>>             else {
> >>> -                   current->mm->token_priority--;
> >>> -                   if (unlikely(current->mm->token_priority < 0))
> >>> -                           current->mm->token_priority = 0;
> >>> +                   if (likely(current->mm->token_priority > 0))
> >>> +                           current->mm->token_priority--;
> >>>             }
> >>>             /* Check if we deserve the token */
> >>>             if (current->mm->token_priority >
> >> argh.
> >>
> >> This has potential to cause large changes in system performance.
> >
> > I'm not sure how. Although, I think the logic still remains the same.
> > IOW, if the prio decrements to zero, it will remain zero until it
> > contends for token rapidly.
>
> The problem is that the original code would decrement an
> unsigned variable beyond zero, underflowing to a number
> just under 2^32...
>
> That would make the process basically a permanent owner
> of the swap token.


Hm. Although, the probability of token_prio going below zero in the
previous code was quite small. Nevertheless, I shall run the new fix
through some tests and post the results asap.

Cheers,
Ashwin

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>