From: Julia Lawall <[email protected]>
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 <[email protected]>
---
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);
Julia Lawall wrote:
> From: Julia Lawall <[email protected]>
>
> 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
On Wed, 26 Dec 2007, H. Peter Anvin wrote:
> Julia Lawall wrote:
> > From: Julia Lawall <[email protected]>
> >
> > 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
On Dec 26, 2007 7:21 AM, Julia Lawall <[email protected]> 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.
Ray Lee wrote:
> On Dec 26, 2007 7:21 AM, Julia Lawall <[email protected]> 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
On Wed, 26 Dec 2007, H. Peter Anvin wrote:
> Ray Lee wrote:
> > On Dec 26, 2007 7:21 AM, Julia Lawall <[email protected]> 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
In article <[email protected]> (at Thu, 27 Dec 2007 08:08:53 +0100 (CET)), Julia Lawall <[email protected]> says:
> On Wed, 26 Dec 2007, H. Peter Anvin wrote:
>
> > Ray Lee wrote:
> > > On Dec 26, 2007 7:21 AM, Julia Lawall <[email protected]> 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
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 <[email protected]> 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
On Wed, 26 Dec 2007, H. Peter Anvin wrote:
> Ray Lee wrote:
> > On Dec 26, 2007 7:21 AM, Julia Lawall <[email protected]> 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
On Wed, Dec 26, 2007 at 11:58:56AM -0800, Ray Lee wrote:
>
> On Dec 26, 2007 7:21 AM, Julia Lawall <[email protected]> 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