Re: [autofs] [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.
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 100 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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.
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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [autofs] [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.
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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.
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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.
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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.
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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.
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. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.
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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.
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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
[PATCH 1/4] fs/autofs: Use time_before, time_before_eq, etc.
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/) // @ 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 @ no_include depends on !include && change_compare_np @ @@ #include + #include // 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.0 +0100 +++ linuxcopy/fs/autofs/dirhash.c 2007-12-25 20:53:48.0 +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); -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/