[PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.

[PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.

[Julia Lawall]

From: Julia Lawall <julia@diku.dk>

The functions time_before, time_before_eq, time_after, and time_after_eq
are more robust for comparing jiffies against other values.

A simplified version of the semantic patch making this change is as follows:
(http://www.emn.fr/x-info/coccinelle/)

// <smpl>
@ change_compare_np @
expression E;
@@

(
- jiffies <= E
+ time_before_eq(jiffies,E)
|
- jiffies >= E
+ time_after_eq(jiffies,E)
|
- jiffies < E
+ time_before(jiffies,E)
|
- jiffies > E
+ time_after(jiffies,E)
)

@ include depends on change_compare_np @
@@

#include <linux/jiffies.h>

@ no_include depends on !include && change_compare_np @
@@

  #include <linux/...>
+ #include <linux/jiffies.h>
// </smpl>

Signed-off-by: Julia Lawall <julia@diku.dk>
---

diff -u -p linux-2.6/fs/autofs/dirhash.c linuxcopy/fs/autofs/dirhash.c
--- linux-2.6/fs/autofs/dirhash.c	2006-11-30 19:05:26.000000000 +0100
+++ linuxcopy/fs/autofs/dirhash.c	2007-12-25 20:53:48.000000000 +0100
@@ -47,7 +47,7 @@ struct autofs_dir_ent *autofs_expire(str
 			return NULL;	/* No entries */
 		/* We keep the list sorted by last_usage and want old stuff */
 		ent = list_entry(dh->expiry_head.next, struct autofs_dir_ent, exp);
-		if (jiffies - ent->last_usage < timeout)
+		if (time_before(jiffies, ent->last_usage + timeout))
 			break;
 		/* Move to end of list in case expiry isn't desirable */
 		autofs_update_usage(dh, ent);

Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.

[H. Peter Anvin]

Julia Lawall wrote:
> From: Julia Lawall <julia@diku.dk>
> 
> The functions time_before, time_before_eq, time_after, and time_after_eq
> are more robust for comparing jiffies against other values.
> 

More robust, how?  You already almost introduced a bug here...

	-hpa

Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.

[Julia Lawall]

On Wed, 26 Dec 2007, H. Peter Anvin wrote:

> Julia Lawall wrote:
> > From: Julia Lawall <julia@diku.dk>
> > 
> > The functions time_before, time_before_eq, time_after, and time_after_eq
> > are more robust for comparing jiffies against other values.
> > 
> 
> More robust, how?  You already almost introduced a bug here...

I'm just summarizing the comment that goes with the definition of the 
time_after etc functions:

include/linux/jiffies.h:88
/*
 *	These inlines deal with timer wrapping correctly. You are 
 *	strongly encouraged to use them
 *	1. Because people otherwise forget
 *	2. Because if the timer wrap changes in future you won't have to
 *	   alter your driver code.
 *

julia

Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.

[Ray Lee]

On Dec 26, 2007 7:21 AM, Julia Lawall <julia@diku.dk> wrote:
> -               if (jiffies - ent->last_usage < timeout)
> +               if (time_before(jiffies, ent->last_usage + timeout))

I don't think this is a safe change? subtraction is always safe (if
you think about it as 'distance'), addition isn't always safe unless
you know the range. The time_before macro will expand that out to
(effectively):

  if ( (long)(ent->last_usage + timeout) - (long)(jiffies) < 0 )

which seems to introduce an overflow condition in the first term.

Dunno, I may be wrong (happens often), but at the very least what
you've transformed it into is no longer obviously correct, and so it's
not a great change.

Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.

[H. Peter Anvin]

Ray Lee wrote:
> On Dec 26, 2007 7:21 AM, Julia Lawall <julia@diku.dk> wrote:
>> -               if (jiffies - ent->last_usage < timeout)
>> +               if (time_before(jiffies, ent->last_usage + timeout))
> 
> I don't think this is a safe change? subtraction is always safe (if
> you think about it as 'distance'), addition isn't always safe unless
> you know the range. The time_before macro will expand that out to
> (effectively):
> 
>   if ( (long)(ent->last_usage + timeout) - (long)(jiffies) < 0 )
> 
> which seems to introduce an overflow condition in the first term.
> 
> Dunno, I may be wrong (happens often), but at the very least what
> you've transformed it into is no longer obviously correct, and so it's
> not a great change.

Indeed.  The bottom form will have overflow issues at time 
jiffies_wraparound/2, whereas the top form will have overflow issues 
only near jiffies_wraparound/1.

	-hpa

Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.

[Julia Lawall]

On Wed, 26 Dec 2007, H. Peter Anvin wrote:

> Ray Lee wrote:
> > On Dec 26, 2007 7:21 AM, Julia Lawall <julia@diku.dk> wrote:
> > > -               if (jiffies - ent->last_usage < timeout)
> > > +               if (time_before(jiffies, ent->last_usage + timeout))
> > 
> > I don't think this is a safe change? subtraction is always safe (if
> > you think about it as 'distance'), addition isn't always safe unless
> > you know the range. The time_before macro will expand that out to
> > (effectively):
> > 
> >   if ( (long)(ent->last_usage + timeout) - (long)(jiffies) < 0 )
> > 
> > which seems to introduce an overflow condition in the first term.
> > 
> > Dunno, I may be wrong (happens often), but at the very least what
> > you've transformed it into is no longer obviously correct, and so it's
> > not a great change.
> 
> Indeed.  The bottom form will have overflow issues at time
> jiffies_wraparound/2, whereas the top form will have overflow issues only near
> jiffies_wraparound/1.

OK, so it seems like it is not such a good idea.

There are, however, over 200 files that contain calls to the various time 
functions that follow this pattern, eg:

arch/arm/kernel/ecard.c:563
if (!last || time_after(jiffies, last + 5*HZ)) {

Perhaps they should be coverted to use a subtraction as well?

julia

Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.

[YOSHIFUJI Hideaki / 吉藤英明]

In article <Pine.LNX.4.64.0712270805370.6952@ask.diku.dk> (at Thu, 27 Dec 2007 08:08:53 +0100 (CET)), Julia Lawall <julia@diku.dk> says:

> On Wed, 26 Dec 2007, H. Peter Anvin wrote:
> 
> > Ray Lee wrote:
> > > On Dec 26, 2007 7:21 AM, Julia Lawall <julia@diku.dk> wrote:
> > > > -               if (jiffies - ent->last_usage < timeout)
> > > > +               if (time_before(jiffies, ent->last_usage + timeout))
> > > 
> > > I don't think this is a safe change? subtraction is always safe (if
> > > you think about it as 'distance'), addition isn't always safe unless
> > > you know the range. The time_before macro will expand that out to
> > > (effectively):
> > > 
> > >   if ( (long)(ent->last_usage + timeout) - (long)(jiffies) < 0 )
> > > 
> > > which seems to introduce an overflow condition in the first term.
> > > 
> > > Dunno, I may be wrong (happens often), but at the very least what
> > > you've transformed it into is no longer obviously correct, and so it's
> > > not a great change.
> > 
> > Indeed.  The bottom form will have overflow issues at time
> > jiffies_wraparound/2, whereas the top form will have overflow issues only near
> > jiffies_wraparound/1.
> 
> OK, so it seems like it is not such a good idea.
> 
> There are, however, over 200 files that contain calls to the various time 
> functions that follow this pattern, eg:
> 
> arch/arm/kernel/ecard.c:563
> if (!last || time_after(jiffies, last + 5*HZ)) {
> 
> Perhaps they should be coverted to use a subtraction as well?

No, use time_after() etc., unless you have very good reason not using them.
And above is not a good reason at all.
Frequency is not a problem.  If we have longer timeout which could
result in wrap-around, we must use another method, e.g. 64bit jiffies,
anyway.

--yoshfuji

Re: [autofs] [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.

[Ian Kent]

On Thu, 2007-12-27 at 08:08 +0100, Julia Lawall wrote:
> On Wed, 26 Dec 2007, H. Peter Anvin wrote:
> 
> > Ray Lee wrote:
> > > On Dec 26, 2007 7:21 AM, Julia Lawall <julia@diku.dk> wrote:
> > > > -               if (jiffies - ent->last_usage < timeout)
> > > > +               if (time_before(jiffies, ent->last_usage + timeout))
> > > 
> > > I don't think this is a safe change? subtraction is always safe (if
> > > you think about it as 'distance'), addition isn't always safe unless
> > > you know the range. The time_before macro will expand that out to
> > > (effectively):

I don't see how subtraction is any different in this case as that could
just as easily underflow leading to the same issue.

> > > 
> > >   if ( (long)(ent->last_usage + timeout) - (long)(jiffies) < 0 )
> > > 
> > > which seems to introduce an overflow condition in the first term.
> > > 
> > > Dunno, I may be wrong (happens often), but at the very least what
> > > you've transformed it into is no longer obviously correct, and so it's
> > > not a great change.
> > 
> > Indeed.  The bottom form will have overflow issues at time
> > jiffies_wraparound/2, whereas the top form will have overflow issues only near
> > jiffies_wraparound/1.
> 
> OK, so it seems like it is not such a good idea.
> 
> There are, however, over 200 files that contain calls to the various time 
> functions that follow this pattern, eg:
> 
> arch/arm/kernel/ecard.c:563
> if (!last || time_after(jiffies, last + 5*HZ)) {

Including autofs4.

> 
> Perhaps they should be coverted to use a subtraction as well?

Thinking about the cases involved always makes my head ache.

Ian

Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.

[Julia Lawall]

On Wed, 26 Dec 2007, H. Peter Anvin wrote:

> Ray Lee wrote:
> > On Dec 26, 2007 7:21 AM, Julia Lawall <julia@diku.dk> wrote:
> > > -               if (jiffies - ent->last_usage < timeout)
> > > +               if (time_before(jiffies, ent->last_usage + timeout))
> > 
> > I don't think this is a safe change? subtraction is always safe (if
> > you think about it as 'distance'), addition isn't always safe unless
> > you know the range. The time_before macro will expand that out to
> > (effectively):
> > 
> >   if ( (long)(ent->last_usage + timeout) - (long)(jiffies) < 0 )
> > 
> > which seems to introduce an overflow condition in the first term.
> > 
> > Dunno, I may be wrong (happens often), but at the very least what
> > you've transformed it into is no longer obviously correct, and so it's
> > not a great change.
> 
> Indeed.  The bottom form will have overflow issues at time
> jiffies_wraparound/2, whereas the top form will have overflow issues only near
> jiffies_wraparound/1.

Isn't this only the case if timeout is a potentially large number? In this 
case, timeout may ultimately depend on a value that come from the user 
level, so I don't know what ranges are expected, but in many other cases 
one of the summands is a constant multiplied by HZ.  If the constant is 
small, then I guess that the likelihood that jiffies overflows and the 
likelihood that the sum overflows are essentially the same.  One then has 
to consider whether:

overflowed - correct </>/<=/>= small constant

is more or less desirable than

time_before/after/before_eq/after_eq(correct, overflowed_by_small_constant)

julia

Re: [autofs] [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.

[Fabio Olive Leite]

On Wed, Dec 26, 2007 at 11:58:56AM -0800, Ray Lee wrote:
> 
> On Dec 26, 2007 7:21 AM, Julia Lawall <julia@diku.dk> wrote:
> > -               if (jiffies - ent->last_usage < timeout)
> > +               if (time_before(jiffies, ent->last_usage + timeout))
> 
> I don't think this is a safe change? subtraction is always safe (if
> you think about it as 'distance'), addition isn't always safe unless
> you know the range.

This thinking is wrong, and is exactly the kind of wrong thinking that
led to the time_{before,after}{,_eq} macros. If jiffies just wrapped,
your safe subtraction will underflow, and you'll be comparing very
different unsigned values.

This is only a concern for 32bit architectures, of course. With 64bit
jiffies, even if HZ is set to 1000000 in the far future, this
civilization will still not outlive the jiffies counter (insert
shocking soundtrack!) as it will wrap in half a million years.

Sadly with 32bit jiffies it currently wraps every 50 days, and the
sign (if cast to signed) changes every 25 days.

> The time_before macro will expand that out to
> (effectively):
> 
>   if ( (long)(ent->last_usage + timeout) - (long)(jiffies) < 0 )

After contemplating this for a very long time (for an NFS fix at the
time) I _think_ the magic is in the casts to signed. The construct
manages to compare correctly any given jiffie values within 2^31 of
each other (on 32bit arches) even with wraps, assuming you really have
timestamps where the second one is taken less than 2^31 jiffies after
the first.

Of course, if the highest jiffies bit wraps twice between the first
and second timestamps, you'll be comparing apples and oranges. If the
timing is right this can happen if you compare two timestamps i.e. 26
days from each other, but I think only NFS is wicked enough to produce
such long living (and stale) kernel data structures.

So in summary: don't question time_after and friends. Not without a
very good analysis and testing with a matrix of timestamps. :)

Cheers!
Fábio Olivé
-- 
ex sed lex awk yacc, e pluribus unix, amem