Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Krishna Kumar]

Hi Linus,

> >
> > In short: It is wrong to do
> >
> >          if (jiffies <= start+HZ)
> >
> > and it is _right_ to do
> >
> >          if (jiffies - start <= HZ)
>
> Actually this last part is wrong, isn't it ? jiffies <= start + HZ is
also
> a correct way to do it, since start+HZ will overflow to the current value
> of jiffies when HZ time elapses. So the above two statements are
IDENTICAL.
>
> No.
>
> Try it out with a few examples. You'll see.
>
>                    Linus

I am sorry, but I still don't see the difference. I wrote a small program
with different
cases, but the values still come same irrespective of the input arguments
to the
checks. Could you tell under what conditions the checks wuold fail ? The
2's
complement  works the same for addition and subtraction. I have included
the
test program below.

Thanks,

- KK

---------------------------------------------------------------------------------------------
/*
     if (jiffies <= start+HZ)
     if (jiffies - start <= HZ)
*/

#define HZ 100

main()
{
     unsigned long start, jiffies;

     /* Case 1 */
     start = ((unsigned long) -1);
     jiffies = start + HZ;
     if (jiffies <= start + HZ) {
           printf("Less Case 1\n");
     }
     if (jiffies - start <= HZ) {
           printf("Less Case 2\n");
     }

     /* Case 2 */
     start = ((unsigned long) -10);
     jiffies = start + HZ + 1;
     if (jiffies <= start + HZ) {
           printf("Less Case 3\n");
     }
     if (jiffies - start <= HZ) {
           printf("Less Case 4\n");
     }

     /* Case 3 */
     start = ((unsigned long) -10);
     jiffies = start + HZ - 1;
     if (jiffies <= start + HZ) {
           printf("Less Case 5\n");
     }
     if (jiffies - start <= HZ) {
           printf("Less Case 6\n");
     }
}

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Linus Torvalds]

On Thu, 8 Nov 2001, Krishna Kumar wrote:
> > >
> > > In short: It is wrong to do
> > >
> > >          if (jiffies <= start+HZ)
> > >
> > > and it is _right_ to do
> > >
> > >          if (jiffies - start <= HZ)
>
> I am sorry, but I still don't see the difference. I wrote a small
> program with different cases, but the values still come same
> irrespective of the input arguments to the checks. Could you tell
> under what conditions the checks wuold fail ? The 2's complement works
> the same for addition and subtraction. I have included the test
> program below.

Ok.

Let's give an example. HZ is 100, and we started just before jiffies
wrapped, and we want to check that we're within one second.

So "start" equals 0xfffffff0, and "jiffies" equals 0xfffffff5.

The first if-statement will say

	if (0xfffffff5 <= 0xfffffff0+100)

which is the same as

	if (0xfffffff5 <= 0x54)

which is

	if (0)

in short, the first statement will say that jiffies is _not_ within 100
ticks of "start", which is obviously wrong. Jiffies _is_ within 100 ticks,
it is in fact just 5 ticks after "start".

The second statement will say

	if (0xfffffff5 - 0xfffffff0 <= 100)

which is

	if (5 <= 100)

which is

	if (1)

which is _correct_. We _are_ within 100 ticks.

See?

Ok, that was wrap-around one way: the "+HZ" wrapped. Let's see the other
case, which is that "jiffies" has wrapped: start is still 0xfffffff0, but
jiffies has wrapped around and is 0x00000001.

The first if-statement will say

	if (0x00000001 <= 0xfffffff0+100)

which is

	if (0x00000001 <= 0x54)

which is

	if (1)

which is correct. The second one will say

	if (0x00000001 - 0xfffffff0 <= 100)

which is

	if (11 <= 100)

which is

	if (1)

which is correct.

In short, the _correct_ one ALWAYS gets the right answer. Even when the
subtraction overflows.

While the first (and incorrect one) gets the wrong answer when the
addition overflows.

Do you see the difference now?

		Linus

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Andreas Dilger]

On Nov 08, 2001  08:55 -0800, Krishna Kumar wrote:
> > > In short: It is wrong to do
> > >
> > >          if (jiffies <= start+HZ)
> > >
> > > and it is _right_ to do
> > >
> > >          if (jiffies - start <= HZ)
> >
> > Actually this last part is wrong, isn't it ? jiffies <= start + HZ is
> > also a correct way to do it, since start+HZ will overflow to the current
> > value of jiffies when HZ time elapses. So the above two statements are
> > IDENTICAL.
> 
> I am sorry, but I still don't see the difference. I wrote a small program
> with different cases, but the values still come same irrespective of the
> input arguments to the checks. Could you tell under what conditions the
> checks wuold fail ? The 2's complement  works the same for addition and
> subtraction. I have included the test program below.

There are several cases where jiffies comparisons can be incorrect:

	unsigned long start = jiffies;		/* say 0xfffffff8 */
	unsigned long delta = 16;
	unsigned long end = jiffies + delta;	/* wraps to 0x00000008 */

a)	while (jiffies < end) { do something }

If jiffies is near wrap when calculating end, end will wrap and your loop
will never be executed, because 0xfffffff9 is greater than 0x00000008.

b)	while (jiffies - end < 0) { do something }

Fails because both jiffies and end are unsigned, and the difference can
never be negative.

c)	while ((long)jiffies - (long)end < 0) { do something }

Correct.  Hmm, this is just like

	while(time_before(jiffies, end)) { do something }

d) 	while (jiffies - start < delta) { do something }

This will also work because of modulo arithmetic, as long as we know in
advance that "start" is always less than "jiffies".


e)	if (jiffies > end) { fail because of timeout }

Incorrect for the same reason as (a) above, 0xfffffff9 > 0x00000008, where
we really want to wait until 0x00000009 to timeout.

f)	if (jiffies - end > 0) { fail because of timeout }

Fails for the same reason as (b) - both jiffies and end are unsigned, and
the difference can never be negative.

g)	if ((long)jiffies - (long)end > 0) { fail because of timeout }

Correct, which is just like:

	if (time_after(jiffies, end)) { fail because of timeout }


h)	if (jiffies - start > delta) { fail because of timeout }

Correct because of modulo arithmetic, as long as we know in advance that
"start" is less than "jiffies".


So it appears there are lots of ways to get it wrong that appear to be
correct.  This is why I'm pushing for the use of the macros, so that
there is no question about whether the comparison is right or wrong.

This is just the same as Linus' pedantic min() and max() macros - sure
people can get it right by themselves, but sometimes they get it wrong,
and it is easier to just make sure they don't get it wrong.

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Vino Thomas]

Hello Krishna,

In 'Case 3' Change the line

	jiffies = start + HZ - 1;
to
	jiffies = start + HZ - 91;

and see the difference.

Regards,
Vino.

On Thu, 8 Nov 2001, Krishna Kumar wrote:

> 
> Hi Linus,
> 
> > >
> > > In short: It is wrong to do
> > >
> > >          if (jiffies <= start+HZ)
> > >
> > > and it is _right_ to do
> > >
> > >          if (jiffies - start <= HZ)
> >
> > Actually this last part is wrong, isn't it ? jiffies <= start + HZ is
> also
> > a correct way to do it, since start+HZ will overflow to the current value
> > of jiffies when HZ time elapses. So the above two statements are
> IDENTICAL.
> >
> > No.
> >
> > Try it out with a few examples. You'll see.
> >
> >                    Linus
> 
> I am sorry, but I still don't see the difference. I wrote a small program
> with different
> cases, but the values still come same irrespective of the input arguments
> to the
> checks. Could you tell under what conditions the checks wuold fail ? The
> 2's
> complement  works the same for addition and subtraction. I have included
> the
> test program below.
> 
> Thanks,
> 
> - KK
> 
> ---------------------------------------------------------------------------------------------
> /*
>      if (jiffies <= start+HZ)
>      if (jiffies - start <= HZ)
> */
> 
> #define HZ 100
> 
> main()
> {
>      unsigned long start, jiffies;
> 
>      /* Case 1 */
>      start = ((unsigned long) -1);
>      jiffies = start + HZ;
>      if (jiffies <= start + HZ) {
>            printf("Less Case 1\n");
>      }
>      if (jiffies - start <= HZ) {
>            printf("Less Case 2\n");
>      }
> 
>      /* Case 2 */
>      start = ((unsigned long) -10);
>      jiffies = start + HZ + 1;
>      if (jiffies <= start + HZ) {
>            printf("Less Case 3\n");
>      }
>      if (jiffies - start <= HZ) {
>            printf("Less Case 4\n");
>      }
> 
>      /* Case 3 */
>      start = ((unsigned long) -10);
>      jiffies = start + HZ - 1;
>      if (jiffies <= start + HZ) {
>            printf("Less Case 5\n");
>      }
>      if (jiffies - start <= HZ) {
>            printf("Less Case 6\n");
>      }
> }
> 
> 
> 

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Krishna Kumar]

Hi Linus,

Thanks for your clarification, it does make sense. I did only
the jiffies overflowing case, and missed the case where it
does not overflow.

Thanks,

- KK
-----------------------------------------------------------------------------

Ok.

Let's give an example. HZ is 100, and we started just before jiffies
wrapped, and we want to check that we're within one second.

So "start" equals 0xfffffff0, and "jiffies" equals 0xfffffff5.

The first if-statement will say

           if (0xfffffff5 <= 0xfffffff0+100)

which is the same as

           if (0xfffffff5 <= 0x54)

which is

           if (0)

in short, the first statement will say that jiffies is _not_ within 100
ticks of "start", which is obviously wrong. Jiffies _is_ within 100 ticks,
it is in fact just 5 ticks after "start".

The second statement will say

           if (0xfffffff5 - 0xfffffff0 <= 100)

which is

           if (5 <= 100)

which is

           if (1)

which is _correct_. We _are_ within 100 ticks.

See?

Ok, that was wrap-around one way: the "+HZ" wrapped. Let's see the other
case, which is that "jiffies" has wrapped: start is still 0xfffffff0, but
jiffies has wrapped around and is 0x00000001.

The first if-statement will say

           if (0x00000001 <= 0xfffffff0+100)

which is

           if (0x00000001 <= 0x54)

which is

           if (1)

which is correct. The second one will say

           if (0x00000001 - 0xfffffff0 <= 100)

which is

           if (11 <= 100)

which is

           if (1)

which is correct.

In short, the _correct_ one ALWAYS gets the right answer. Even when the
subtraction overflows.

While the first (and incorrect one) gets the wrong answer when the
addition overflows.

Do you see the difference now?

                     Linus

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Krishna Kumar]

> Unsigned arithmetic is fine. The _correct_ way to test whether something
> is in within
>
>          [ start , start+HZ ]
>
> is to do
>
>          if (jiffies - start <= HZ)
>
> try it. The C language guarantees that unsigned arithmetic works in a
> "modulo power of two" fashion, which means that it _is_ ok to do
> arithmetic on unsigned longs, and jiffy wrapping does not matter. No need
> to cast to "signed" or anything else.
>
> In short: It is wrong to do
>
>          if (jiffies <= start+HZ)
>
> and it is _right_ to do
>
>          if (jiffies - start <= HZ)

Actually this last part is wrong, isn't it ? jiffies <= start + HZ is also
a correct way to do it, since start+HZ will overflow to the current value
of
jiffies when HZ time elapses. So the above two statements are IDENTICAL. I
agree with the rest of the statements, and especially that you don't need
to worry about wrapping using unsigned numbers.

Regards,

- KK

> (as long as "start" is "unsigned long" like jiffies).
>
>                    Linus

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Linus Torvalds]

On Wed, 7 Nov 2001, Krishna Kumar wrote:
> >
> > In short: It is wrong to do
> >
> >          if (jiffies <= start+HZ)
> >
> > and it is _right_ to do
> >
> >          if (jiffies - start <= HZ)
>
> Actually this last part is wrong, isn't it ? jiffies <= start + HZ is also
> a correct way to do it, since start+HZ will overflow to the current value
> of jiffies when HZ time elapses. So the above two statements are IDENTICAL.

No.

Try it out with a few examples. You'll see.

		Linus

[PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Tim Schmielau]

Hi all,

jiffies cleanup patch of the day follows. Mostly boring changes of jiffies
comparisons to use time_{before,after} in order to handle jiffies
wraparound correctly.

However, two interesting points:

 - deciding on whether or not it is a problem on 64 bit platforms to
   declare the jiffies argument to ic_bootp_send_if as u32.
   Result: It's probably not a big deal to impose the condition on alphas,
   that DHCP/BOOTP must succeed within 48 days. On the other hand, it
   doesn't hurt to change it to unsigned long either, so I did that.

 - syn_flood_warning. No big deal that it did not warn within
   the first 60 seconds after boot. However, it also turns of
   warnings after 248 days on 32 bit platforms.
   While pretty much any other event may safely be assumed to happen more
   often than that, less than one synflood attack per year seems totally
   reasonable (desirable, in fact).

   I did not do anything about that yet. When I have submitted the patch
   to supply a get_jiffies64() routine, we should probably reexamine
   whether or not a call to a locking get_jiffies64() is acceptable
   in this place.

Extra measures taken this time to not again loose a compiler message ;-)

Tim



--- linux-2.4.14/net/core/neighbour.c	Mon Oct  1 18:19:56 2001
+++ linux-2.4.14-jiffies64/net/core/neighbour.c	Wed Nov  7 23:37:36 2001
@@ -136,7 +136,7 @@
 			if (atomic_read(&n->refcnt) == 1 &&
 			    !(n->nud_state&NUD_PERMANENT) &&
 			    (n->nud_state != NUD_INCOMPLETE ||
-			     jiffies - n->used > n->parms->retrans_time)) {
+			     time_after(jiffies, n->used + n->parms->retrans_time))) {
 				*np = n->next;
 				n->dead = 1;
 				shrunk = 1;
@@ -234,7 +234,7 @@

 	if (tbl->entries > tbl->gc_thresh3 ||
 	    (tbl->entries > tbl->gc_thresh2 &&
-	     now - tbl->last_flush > 5*HZ)) {
+	     time_after(now, tbl->last_flush + 5*HZ))) {
 		if (neigh_forced_gc(tbl) == 0 &&
 		    tbl->entries > tbl->gc_thresh3)
 			return NULL;
@@ -533,12 +533,12 @@
 	if (state&(NUD_NOARP|NUD_PERMANENT))
 		return;
 	if (state&NUD_REACHABLE) {
-		if (now - n->confirmed > n->parms->reachable_time) {
+		if (time_after(now, n->confirmed + n->parms->reachable_time)) {
 			n->nud_state = NUD_STALE;
 			neigh_suspect(n);
 		}
 	} else if (state&NUD_VALID) {
-		if (now - n->confirmed < n->parms->reachable_time) {
+		if (time_before(now, n->confirmed + n->parms->reachable_time)) {
 			neigh_del_timer(n);
 			n->nud_state = NUD_REACHABLE;
 			neigh_connect(n);
@@ -559,7 +559,7 @@
 	 *	periodicly recompute ReachableTime from random function
 	 */

-	if (now - tbl->last_rand > 300*HZ) {
+	if (time_after(now, tbl->last_rand + 300*HZ)) {
 		struct neigh_parms *p;
 		tbl->last_rand = now;
 		for (p=&tbl->parms; p; p = p->next)
@@ -585,7 +585,7 @@
 				n->used = n->confirmed;

 			if (atomic_read(&n->refcnt) == 1 &&
-			    (state == NUD_FAILED || now - n->used > n->parms->gc_staletime)) {
+			    (state == NUD_FAILED || time_after(now, n->used + n->parms->gc_staletime))) {
 				*np = n->next;
 				n->dead = 1;
 				write_unlock(&n->lock);
@@ -594,7 +594,7 @@
 			}

 			if (n->nud_state&NUD_REACHABLE &&
-			    now - n->confirmed > n->parms->reachable_time) {
+			    time_after(now, n->confirmed + n->parms->reachable_time)) {
 				n->nud_state = NUD_STALE;
 				neigh_suspect(n);
 			}
@@ -646,7 +646,7 @@
 	}

 	if ((state&NUD_VALID) &&
-	    now - neigh->confirmed < neigh->parms->reachable_time) {
+	    time_before(now, neigh->confirmed + neigh->parms->reachable_time)) {
 		neigh->nud_state = NUD_REACHABLE;
 		NEIGH_PRINTK2("neigh %p is still alive.\n", neigh);
 		neigh_connect(neigh);
--- linux-2.4.14/net/ipv4/arp.c	Fri Sep  7 20:01:20 2001
+++ linux-2.4.14-jiffies64/net/ipv4/arp.c	Wed Nov  7 22:35:19 2001
@@ -811,7 +811,7 @@
 		   agents are active. Taking the first reply prevents
 		   arp trashing and chooses the fastest router.
 		 */
-		if (jiffies - n->updated >= n->parms->locktime)
+		if (time_after_eq(jiffies, n->updated + n->parms->locktime))
 			override = 1;

 		/* Broadcast replies and request packets
--- linux-2.4.14/net/ipv4/route.c	Wed Oct 31 00:08:12 2001
+++ linux-2.4.14-jiffies64/net/ipv4/route.c	Wed Nov  7 22:51:23 2001
@@ -346,7 +346,7 @@
 		goto out;

 	ret = 1;
-	if (rth->u.dst.expires && (long)(rth->u.dst.expires - jiffies) <= 0)
+	if (rth->u.dst.expires && time_after_eq(jiffies, rth->u.dst.expires))
 		goto out;

 	age = jiffies - rth->u.dst.lastuse;
@@ -377,7 +377,7 @@
 		while ((rth = *rthp) != NULL) {
 			if (rth->u.dst.expires) {
 				/* Entry is expired even if it is in use */
-				if ((long)(now - rth->u.dst.expires) <= 0) {
+				if (time_before_eq(now, rth->u.dst.expires)) {
 					tmo >>= 1;
 					rthp = &rth->u.rt_next;
 					continue;
@@ -395,7 +395,7 @@
 		write_unlock(&rt_hash_table[i].lock);

 		/* Fallback loop breaker. */
-		if ((jiffies - now) > 0)
+		if (time_after(jiffies, now))
 			break;
 	}
 	rover = i;
@@ -499,7 +499,7 @@
 	 * Garbage collection is pretty expensive,
 	 * do not make it too frequently.
 	 */
-	if (now - last_gc < ip_rt_gc_min_interval &&
+	if (time_before(now, last_gc + ip_rt_gc_min_interval) &&
 	    atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
 		goto out;

@@ -522,7 +522,7 @@
 		equilibrium = atomic_read(&ipv4_dst_ops.entries) - goal;
 	}

-	if (now - last_gc >= ip_rt_gc_min_interval)
+	if (time_after_eq(now, last_gc + ip_rt_gc_min_interval))
 		last_gc = now;

 	if (goal <= 0) {
@@ -578,7 +578,7 @@

 		if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
 			goto out;
-	} while (!in_softirq() && jiffies - now < 1);
+	} while (!in_softirq() && !time_after(jiffies, now));

 	if (atomic_read(&ipv4_dst_ops.entries) < ip_rt_max_size)
 		goto out;
@@ -949,8 +949,8 @@
 	/* Check for load limit; set rate_last to the latest sent
 	 * redirect.
 	 */
-	if (jiffies - rt->u.dst.rate_last >
-	    (ip_rt_redirect_load << rt->u.dst.rate_tokens)) {
+	if (time_after(jiffies, rt->u.dst.rate_last +
+	                        (ip_rt_redirect_load << rt->u.dst.rate_tokens))) {
 		icmp_send(skb, ICMP_REDIRECT, ICMP_REDIR_HOST, rt->rt_gateway);
 		rt->u.dst.rate_last = jiffies;
 		++rt->u.dst.rate_tokens;
--- linux-2.4.14/net/ipv4/igmp.c	Sat Jul 28 21:12:38 2001
+++ linux-2.4.14-jiffies64/net/ipv4/igmp.c	Wed Nov  7 22:55:00 2001
@@ -121,7 +121,7 @@
  * contradict to specs provided this delay is small enough.
  */

-#define IGMP_V1_SEEN(in_dev) ((in_dev)->mr_v1_seen && (long)(jiffies - (in_dev)->mr_v1_seen) < 0)
+#define IGMP_V1_SEEN(in_dev) ((in_dev)->mr_v1_seen && time_before(jiffies, (in_dev)->mr_v1_seen))

 #endif

@@ -165,7 +165,7 @@
 	spin_lock_bh(&im->lock);
 	im->unsolicit_count = 0;
 	if (del_timer(&im->timer)) {
-		if ((long)(im->timer.expires-jiffies) < max_delay) {
+		if (time_before(im->timer.expires, jiffies + max_delay)) {
 			add_timer(&im->timer);
 			im->tm_running=1;
 			spin_unlock_bh(&im->lock);
--- linux-2.4.14/net/ipv4/ip_gre.c	Wed Oct 31 00:08:12 2001
+++ linux-2.4.14-jiffies64/net/ipv4/ip_gre.c	Wed Nov  7 22:56:37 2001
@@ -390,7 +390,7 @@
 	if (t->parms.iph.ttl == 0 && type == ICMP_TIME_EXCEEDED)
 		goto out;

-	if (jiffies - t->err_time < IPTUNNEL_ERR_TIMEO)
+	if (time_before(jiffies, t->err_time + IPTUNNEL_ERR_TIMEO))
 		t->err_count++;
 	else
 		t->err_count = 1;
@@ -796,7 +796,7 @@
 #endif

 	if (tunnel->err_count > 0) {
-		if (jiffies - tunnel->err_time < IPTUNNEL_ERR_TIMEO) {
+		if (time_before(jiffies, tunnel->err_time + IPTUNNEL_ERR_TIMEO)) {
 			tunnel->err_count--;

 			dst_link_failure(skb);
--- linux-2.4.14/net/ipv4/ipmr.c	Thu Sep 20 23:12:56 2001
+++ linux-2.4.14-jiffies64/net/ipv4/ipmr.c	Wed Nov  7 22:58:00 2001
@@ -1268,7 +1268,7 @@
 		       large chunk of pimd to kernel. Ough... --ANK
 		     */
 		    (mroute_do_pim || cache->mfc_un.res.ttls[true_vifi] < 255) &&
-		    jiffies - cache->mfc_un.res.last_assert > MFC_ASSERT_THRESH) {
+		    time_after(jiffies, cache->mfc_un.res.last_assert + MFC_ASSERT_THRESH)) {
 			cache->mfc_un.res.last_assert = jiffies;
 			ipmr_cache_report(skb, true_vifi, IGMPMSG_WRONGVIF);
 		}
--- linux-2.4.14/net/ipv4/tcp_timer.c	Mon Oct  1 18:19:57 2001
+++ linux-2.4.14-jiffies64/net/ipv4/tcp_timer.c	Wed Nov  7 23:01:23 2001
@@ -227,7 +227,7 @@
 	if (sk->state == TCP_CLOSE || !(tp->ack.pending&TCP_ACK_TIMER))
 		goto out;

-	if ((long)(tp->ack.timeout - jiffies) > 0) {
+	if (time_before(jiffies, tp->ack.timeout)) {
 		if (!mod_timer(&tp->delack_timer, tp->ack.timeout))
 			sock_hold(sk);
 		goto out;
@@ -429,7 +429,7 @@
 	if (sk->state == TCP_CLOSE || !tp->pending)
 		goto out;

-	if ((long)(tp->timeout - jiffies) > 0) {
+	if (time_before(jiffies, tp->timeout)) {
 		if (!mod_timer(&tp->retransmit_timer, tp->timeout))
 			sock_hold(sk);
 		goto out;
@@ -509,7 +509,7 @@
 	do {
 		reqp=&lopt->syn_table[i];
 		while ((req = *reqp) != NULL) {
-			if ((long)(now - req->expires) >= 0) {
+			if (time_after_eq(now, req->expires)) {
 				if ((req->retrans < thresh ||
 				     (req->acked && req->retrans < max_retries))
 				    && !req->class->rtx_syn_ack(sk, req, NULL)) {
--- linux-2.4.14/net/ipv4/tcp_ipv4.c	Mon Nov  5 18:46:12 2001
+++ linux-2.4.14-jiffies64/net/ipv4/tcp_ipv4.c	Wed Nov  7 23:10:21 2001
@@ -1213,10 +1213,10 @@

 static inline void syn_flood_warning(struct sk_buff *skb)
 {
-	static unsigned long warntime;
+	static unsigned long next_warntime;

-	if (jiffies - warntime > HZ*60) {
-		warntime = jiffies;
+	if (time_after(jiffies, next_warntime)) {
+		next_warntime = jiffies + 60*HZ;
 		printk(KERN_INFO
 		       "possible SYN flooding on port %d. Sending cookies.\n",
 		       ntohs(skb->h.th->dest));
--- linux-2.4.14/net/ipv4/ipconfig.c	Wed Oct 31 00:08:12 2001
+++ linux-2.4.14-jiffies64/net/ipv4/ipconfig.c	Wed Nov  7 23:28:47 2001
@@ -630,7 +630,7 @@
 /*
  *  Send DHCP/BOOTP request to single interface.
  */
-static void __init ic_bootp_send_if(struct ic_device *d, u32 jiffies)
+static void __init ic_bootp_send_if(struct ic_device *d, unsigned long jiffies)
 {
 	struct net_device *dev = d->dev;
 	struct sk_buff *skb;
@@ -1000,7 +1000,7 @@
 #endif

 		jiff = jiffies + (d->next ? CONF_INTER_TIMEOUT : timeout);
-		while (jiffies < jiff && !ic_got_reply)
+		while (time_before(jiffies, jiff) && !ic_got_reply)
 			barrier();
 #ifdef IPCONFIG_DHCP
 		/* DHCP isn't done until we get a DHCPACK. */
@@ -1113,7 +1113,7 @@
  try_try_again:
 	/* Give hardware a chance to settle */
 	jiff = jiffies + CONF_PRE_OPEN;
-	while (jiffies < jiff)
+	while (time_before(jiffies, jiff))
 		;

 	/* Setup all network devices */
@@ -1122,7 +1122,7 @@

 	/* Give drivers a chance to settle */
 	jiff = jiffies + CONF_POST_OPEN;
-	while (jiffies < jiff)
+	while (time_before(jiffies, jiff))
 			;

 	/*
--- linux-2.4.14/net/ipv4/tcp_minisocks.c	Mon Oct  1 18:19:57 2001
+++ linux-2.4.14-jiffies64/net/ipv4/tcp_minisocks.c	Thu Nov  8 00:40:37 2001
@@ -562,7 +562,7 @@
 			tcp_twcal_timer.expires = tcp_twcal_jiffie + (slot<<TCP_TW_RECYCLE_TICK);
 			add_timer(&tcp_twcal_timer);
 		} else {
-			if ((long)(tcp_twcal_timer.expires - jiffies) > (slot<<TCP_TW_RECYCLE_TICK))
+			if (time_after(tcp_twcal_timer.expires, jiffies + (slot<<TCP_TW_RECYCLE_TICK)))
 				mod_timer(&tcp_twcal_timer, jiffies + (slot<<TCP_TW_RECYCLE_TICK));
 			slot = (tcp_twcal_hand + slot)&(TCP_TW_RECYCLE_SLOTS-1);
 		}
@@ -595,7 +595,7 @@
 	j = tcp_twcal_jiffie;

 	for (n=0; n<TCP_TW_RECYCLE_SLOTS; n++) {
-		if ((long)(j - now) <= 0) {
+		if (time_before(j, now)) {
 			struct tcp_tw_bucket *tw;

 			while((tw = tcp_twcal_row[slot]) != NULL) {

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[David S. Miller]

   From: Tim Schmielau <tim@physik3.uni-rostock.de>
   Date: Thu, 8 Nov 2001 01:00:24 +0100 (CET)

   jiffies cleanup patch of the day follows. Mostly boring changes of jiffies
   comparisons to use time_{before,after} in order to handle jiffies
   wraparound correctly.

These cases handle wraparound correctly!!!!

Please stop sending these changes, start thinking about what the
code is doing.

It is comparing a "DIFFERRENCE" not raw jiffy values with each other.
It works just fine.

Franks a lot,
David S. Miller
davem@redhat.com

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Andreas Dilger]

On Nov 07, 2001  16:09 -0800, David S. Miller wrote:
>    From: Tim Schmielau <tim@physik3.uni-rostock.de>
> 
>    jiffies cleanup patch of the day follows. Mostly boring changes of jiffies
>    comparisons to use time_{before,after} in order to handle jiffies
>    wraparound correctly.
> 
> These cases handle wraparound correctly!!!!
> 
> Please stop sending these changes, start thinking about what the
> code is doing.
> 
> It is comparing a "DIFFERRENCE" not raw jiffy values with each other.
> It works just fine.

No, only a limited number of them cast to a signed value, which means
that a large number of them get the comparison wrong in the case of
jiffies wrap (where the difference is a large unsigned value, and not
a small negative number).


This is not just idle change.  Tim has problems when jiffies is
initialized to a pre-wrap value at boot, and changing everything to
use time_{before,after} is the only easy way to audit all of the code
(and know that it is done).

As I sent to Alan privately (and he agreed), there are three reasons to
change this code (even if it is correct) to using time_{before,after}:

1) because it is non-obvious what "correct" is when dealing with jiffies wrap
   (some of the changes that Alan previously complained about as being already
   correct were in fact broken, and if _he_ can't get it right, who can?)
2) so that people see it more and are more likely to get it correct, instead
   of always adding in code that only breaks after 497 days of uptime
3) to isolate code from any changes if jiffies moves to a 64-bit value (where
   casts to "(long)" may not be appropriate anymore)

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[David S. Miller]

   From: Andreas Dilger <adilger@turbolabs.com>
   Date: Wed, 7 Nov 2001 17:36:27 -0700

   No, only a limited number of them cast to a signed value, which means
   that a large number of them get the comparison wrong in the case of
   jiffies wrap (where the difference is a large unsigned value, and not
   a small negative number).
   
Why do they these cases that are actually in the code need to cast to
a signed value to get a correct answer?  They are not like your
example.

Almost all of these cases are:

	(jiffies - SOME_VALUE_KNOWN_TO_BE_IN_THE_PAST) > 5 * HZ

So you say if we don't cast to signed, this won't get it right on
wrap-around?  I disagree, let's say "long" is 32-bits and jiffies
wrapped around to "0x2" and SOME_VALUE... is 0xfffffff8.  The
subtraction above yields 10, and that is what we want.

Please show me a bad case where casting to signed is necessary.

I actually ran through the tree the other night myself starting to
convert these things, then I noticed that I couldn't even convince
myself that the code was incorrect.

Franks a lot,
David S. Miller
davem@redhat.com

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Tim Schmielau]

> Why do they these cases that are actually in the code need to cast to
> a signed value to get a correct answer?  They are not like your
> example.
>
> Almost all of these cases are:
>
> 	(jiffies - SOME_VALUE_KNOWN_TO_BE_IN_THE_PAST) > 5 * HZ
>
> So you say if we don't cast to signed, this won't get it right on
> wrap-around?  I disagree, let's say "long" is 32-bits and jiffies
> wrapped around to "0x2" and SOME_VALUE... is 0xfffffff8.  The
> subtraction above yields 10, and that is what we want.
>
> Please show me a bad case where casting to signed is necessary.
>
> I actually ran through the tree the other night myself starting to
> convert these things, then I noticed that I couldn't even convince
> myself that the code was incorrect.
>


Please consider to change the appended ones.

Tim


--- linux-2.4.14/net/ipv4/route.c	Wed Oct 31 00:08:12 2001
+++ linux-2.4.14-jiffies64/net/ipv4/route.c	Wed Nov  7 22:51:23 2001
@@ -395,7 +395,7 @@
 		write_unlock(&rt_hash_table[i].lock);

 		/* Fallback loop breaker. */
-		if ((jiffies - now) > 0)
+		if ((long)(jiffies - now) > 0)
 			break;
 	}
 	rover = i;
--- linux-2.4.14/net/ipv4/ipconfig.c	Wed Oct 31 00:08:12 2001
+++ linux-2.4.14-jiffies64/net/ipv4/ipconfig.c	Wed Nov  7 23:28:47 2001
@@ -1000,7 +1000,7 @@
 #endif

 		jiff = jiffies + (d->next ? CONF_INTER_TIMEOUT : timeout);
-		while (jiffies < jiff && !ic_got_reply)
+		while ((long)(jiffies - jiff) < 0 && !ic_got_reply)
 			barrier();
 #ifdef IPCONFIG_DHCP
 		/* DHCP isn't done until we get a DHCPACK. */
@@ -1113,7 +1113,7 @@
  try_try_again:
 	/* Give hardware a chance to settle */
 	jiff = jiffies + CONF_PRE_OPEN;
-	while (jiffies < jiff)
+	while ((long)(jiffies - jiff) < 0)
 		;

 	/* Setup all network devices */
@@ -1122,7 +1122,7 @@

 	/* Give drivers a chance to settle */
 	jiff = jiffies + CONF_POST_OPEN;
-	while (jiffies < jiff)
+	while ((long)(jiffies - jiff) < 0)
 			;

 	/*

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[David S. Miller]

   From: Tim Schmielau <tim@physik3.uni-rostock.de>
   Date: Thu, 8 Nov 2001 01:58:45 +0100 (CET)

   Please consider to change the appended ones.
   
   --- linux-2.4.14/net/ipv4/route.c	Wed Oct 31 00:08:12 2001
   +++ linux-2.4.14-jiffies64/net/ipv4/route.c	Wed Nov  7 22:51:23 2001
   @@ -395,7 +395,7 @@
    		write_unlock(&rt_hash_table[i].lock);
   
    		/* Fallback loop breaker. */
   -		if ((jiffies - now) > 0)
   +		if ((long)(jiffies - now) > 0)
    			break;
    	}
    	rover = i;

Nothing is wrong with this case.  Jiffies is guarenteed to be greater
than or equal to "now".  There is no need to cast it to a signed type.

Let me say this again, in another way :-)

	SOME_WRAPPED_AROUND_SMALL_VALUE

	MINUS

	SOME_HUGE_ABOUT_TO_WRAP_AROUND_VALUE

will have the same result, signed or not.  Check this out!

(gdb) p (long)0x2 - (long)0xfffffff8
$1 = 10
(gdb) p (unsigned long)0x2 - (unsigned long)0xfffffff8
$2 = 10

It's math and the computer comfirms it! :-)))

Please show me a failure case for this statement if you disagree
with me.

   --- linux-2.4.14/net/ipv4/ipconfig.c	Wed Oct 31 00:08:12 2001
   +++ linux-2.4.14-jiffies64/net/ipv4/ipconfig.c	Wed Nov  7 23:28:47 2001

These cases are indeed buggy.  I'd rather fix these ones with
time_{after,before}() though.  And again, your "signed" casts
are totally superfluous.

Franks a lot,
David S. Miller
davem@redhat.com

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Tim Schmielau]

>
>    --- linux-2.4.14/net/ipv4/ipconfig.c	Wed Oct 31 00:08:12 2001
>    +++ linux-2.4.14-jiffies64/net/ipv4/ipconfig.c	Wed Nov  7 23:28:47 2001
>
> These cases are indeed buggy.  I'd rather fix these ones with
> time_{after,before}() though.  And again, your "signed" casts
> are totally superfluous.
>

They actually are necessary as unsigned values can never become less than
zero.

Tim

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[David S. Miller]

   From: Tim Schmielau <tim@physik3.uni-rostock.de>
   Date: Thu, 8 Nov 2001 02:20:02 +0100 (CET)
   
   They actually are necessary as unsigned values can never become less than
   zero.

I definitely stand corrected.

Franks a lot,
David S. Miller
davem@redhat.com

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Andreas Dilger]

On Nov 07, 2001  16:44 -0800, David S. Miller wrote:
> Why do they these cases that are actually in the code need to cast to
> a signed value to get a correct answer?  They are not like your
> example.
> 
> Almost all of these cases are:
> 
> 	(jiffies - SOME_VALUE_KNOWN_TO_BE_IN_THE_PAST) > 5 * HZ
> 
> So you say if we don't cast to signed, this won't get it right on
> wrap-around?  I disagree, let's say "long" is 32-bits and jiffies
> wrapped around to "0x2" and SOME_VALUE... is 0xfffffff8.  The
> subtraction above yields 10, and that is what we want.

OK, in this code it mostly appears that the wraparound is correct, but
in some cases it is very hard to say without specific knowledge of the code:

	neigh->confirmed = jiffies - (n->parms->base_reachable_time<<1);
	.
	.
	.
	if ((state&NUD_VALID) &&
	    now - neigh->confirmed < neigh->parms->reachable_time) {

How are we to know that the above calculation won't be wrong because of
jiffies wrap?

> Please show me a bad case where casting to signed is necessary.

I don't know enough about the net code to say for sure, but for example
in drivers/sound/sb_common.c:

	limit = jiffies + HZ / 10;      /* Timeout */

	for (i = 0; i < 500000 && (limit-jiffies)>0; i++)

Since limit and jiffies are both unsigned, the value will always be > 0,
unless they are equal.

> I actually ran through the tree the other night myself starting to
> convert these things, then I noticed that I couldn't even convince
> myself that the code was incorrect.

I don't disagree that it is possible to make correct code without the
macros, but it is easier to guarantee that it IS correct with the macros.
Rather than evaluate each jiffies usage on a case-by-case basis, it is
much easier to do a code audit and fix all comparisons.  I don't see that
it harms anything to use the macros instead.

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[David S. Miller]

   From: Andreas Dilger <adilger@turbolabs.com>
   Date: Wed, 7 Nov 2001 21:32:18 -0700

   I don't see that it harms anything to use the macros instead.

Maybe if this code were literally etched into the back your skull like
it is for some of us, you'd understand what a detriment it is to make
changes like this when it isn't necessary :-)

Franks a lot,
David S. Miller
davem@redhat.com

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Linus Torvalds]

On Wed, 7 Nov 2001, Andreas Dilger wrote:
>
> No, only a limited number of them cast to a signed value, which means
> that a large number of them get the comparison wrong in the case of
> jiffies wrap (where the difference is a large unsigned value, and not
> a small negative number).

No.

Unsigned arithmetic is fine. The _correct_ way to test whether something
is in within

	[ start , start+HZ ]

is to do

	if (jiffies - start <= HZ)

try it. The C language guarantees that unsigned arithmetic works in a
"modulo power of two" fashion, which means that it _is_ ok to do
arithmetic on unsigned longs, and jiffy wrapping does not matter. No need
to cast to "signed" or anything else.

In short: It is wrong to do

	if (jiffies <= start+HZ)

and it is _right_ to do

	if (jiffies - start <= HZ)

(as long as "start" is "unsigned long" like jiffies).

		Linus

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[kuznet]

Hello!

>    jiffies cleanup patch of the day follows. Mostly boring changes of jiffies
>    comparisons to use time_{before,after} in order to handle jiffies
>    wraparound correctly.

I want to _ask_ one thing people working on these changes.
_Please_, defer this edit to 2.5. The changes are very good,
but time for them is very bad.

When I wrote this code the macros did not exist. However, this code is right,
take my word. Hence, it is pure maintanance problem and as soon as
main reader of this code is me, I would be glad to see the changes,
but only having no deadlines.

Anyway, if someone want to try to define jiffies as somewhat
different of "unsigned long", all code needs real checking rather
than syntax changes.

Alexey

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Tim Schmielau]

> >    jiffies cleanup patch of the day follows. Mostly boring changes of jiffies
> >    comparisons to use time_{before,after} in order to handle jiffies
> >    wraparound correctly.
>
> I want to _ask_ one thing people working on these changes.
> _Please_, defer this edit to 2.5. The changes are very good,
> but time for them is very bad.
>

Agreed. For now I will only post patches for code that really _is_ broken.
I've already learned that from the discussion with David Miller.
This way I might miss some places getting the comparison wrong, but
changes will be less intrusive.

However, I definitely want to see a 2.4.x someday that is able to run
for more that 497 days.


Tim

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[Andreas Dilger]

On Nov 08, 2001  20:54 +0300, kuznet@ms2.inr.ac.ru wrote:
> I want to _ask_ one thing people working on these changes.
> _Please_, defer this edit to 2.5. The changes are very good,
> but time for them is very bad.
> 
> When I wrote this code the macros did not exist.

Well, Alan said the same thing, and I went and checked - the macros existed
since 2.1.106, probably the last time there was a "jiffies wrap" effort.  It
is more likely that nobody knows about them, because nobody uses them, 
because nobody knows about them, etc.

> However, this code is right, take my word. Hence, it is pure maintanance
> problem and as soon as main reader of this code is me, I would be glad to
> see the changes, but only having no deadlines.

If people don't want to see them, that is fine with me - they will stop.

Tim and I were only trying to fix instability that he noticed when
initializing jiffies to some large pre-wrap value.  If people are OK
with 2.4 Linux boxes hanging after 497 days, that is fine with me.

The only box I have that could stay up that long is my router (486/33),
and it does not have a UPS so it is not likely to actually make it
(record is 6 months or so).

Cheers, Andreas
--
Andreas Dilger
http://sourceforge.net/projects/ext2resize/
http://www-mddsp.enel.ucalgary.ca/People/adilger/

Re: [PATCH] net/ipv4/*, net/core/neighbour.c jiffies cleanup

[kuznet]

Hello!

> is more likely that nobody knows about them, because nobody uses them, 
> because nobody knows about them, etc.

Yes, it is thing which usually happens with good macros. :-)


> If people don't want to see them, that is fine with me - they will stop.

I talk only about neighbour.c. It is pretty hairy to bring it to
brain cache fastly enough. And I am afraid (remember) that in the past
I did some silly tricks, sort of using the fact that large positive
now - mark means that mark is in future. Mostly likely killed together
with another hacks, but I am not sure.

Another places are trivial as rule and can be edited any time.

Alexey