Re: testing/pre-7 and do_poll()

Re: testing/pre-7 and do_poll()

[Colin Plumb]

Chip Salzenberg wrote:
> Well, I forgot the (unsigned long) cast, as someone else noted:

>	timeout = ROUND_UP((unsigned long) timeout, 1000/HZ);

>
> Otherwise, the code is Just Right.

Um, this works perfectly when HZ == 100, but consider what happens when
HZ == 1024.  1000/HZ == 0, and then computing (x+0-1)/0 doesn't work so well.

If you want accuracy with no danger of overflow, try the following trick:

	ticks = (msec/1000)*HZ + (msec%1000)*HZ/1000.

To make this more efficient, use that only on large values of msec,
and the simpler (msec*HZ)/1000.  In thhe HZ > 1000 case, you also lose
the guarantee that every legal msec value corresponds to a 

(C experts will note that none of the parens are necessary, but I though
it was clearer to include them.)

So, for perfection, you want:

unsigned long msec_to_ticks(unsigned long msec)
{
	if (msec <= ULONG_MAX/HZ)
		return msec*HZ/1000;
#if HZ > 1000
	/* Wups, can overflow - saturate return value */
	if (msec > (ULONG_MAX/HZ)*1000 + (ULONG_MAX % HZ)*1000/HZ)
		return ULONG_MAX
#endif
	return (msec/1000)*HZ + (msec%1000)*HZ/1000;
}

Um... this is the rounding-down case, and also saturates at ULONG_MAX
instead of MAX_SCHEDULE_TIMEOUT (LONG_MAX).  Let me adjust the boundary
cases a bit...

#if MAX_SCHEDULE_TIMEOUT != LONG_MAX
#error Adjust this code - it assumes identical input and output ranges
#endif
unsigned long msec_to_ticks(unsigned long msec)
{
	if (msec < ULONG_MAX/HZ - 999)
		return (msec+999)*HZ/1000;
	msec--;	/* Following code rounds up and adds one */
#if HZ > 1000
	/* Wups, can overflow - saturate return value */
	if (msec >= (ULONG_MAX/HZ)*1000 + (ULONG_MAX % HZ)*1000/HZ)
		return MAX_SCHEDULE_TIMEOUT;
#endif
	return (msec/1000)*HZ + (msec%1000)*HZ/1000 + 1;
}
-- 
	-Colin
--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: testing/pre-7 and do_poll()

[Shawn Leas]

On Mon, 11 Jan 1999 estafford@ixl.com wrote:

> 
> On 11-Jan-99 Linus Torvalds wrote:
> > 
> > 
> > On Mon, 11 Jan 1999, Shawn Leas wrote:
> > 
> >> On Sun, 10 Jan 1999, Linus Torvalds wrote:
> >> 
> >> > things. So far, megahertz are still far in the future, but maybe I some
> >> > day will have to remove even that assumption. Unlikely to be a problem in
> >> > my lifetime, but hey, I can hope (whether due to a long life or really
> >> > fast CPU's, I don't care ;) 
> >> 
> >> Well, they've made a photonic chip, so we may be thinking about this
> >> sooner than you think... Think 200GHz processors.
> > 
> > Hey, I want to see the memory subsystems for it..
> > 
> >               Linus
> 
> Got any links to such technology?  I've been working on it for a while, but
> making transistors from glass are not quite as easy as I would think.. Lemme
> know.

Take a lewk at this! And yes, it aint digital logic, it's
quantum logic.  It used to be that photonic computers were not
really processors as we know them.  This is the real deal.

http://www.nbnn.com/pubNews/123239.html

-Shawn
<=========== America Held Hostage ===========>
   Day 2183 for the poor and the middle class. 
   Day 2202 for the rich and the dead.
   739 days remaining in the Raw Deal.
<============================================> 

--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: testing/pre-7 and do_poll()

[Gregory Maxwell]

On Mon, 11 Jan 1999, Linus Torvalds wrote:

> Hey, I want to see the memory subsystems for it..
> 
> 		Linus

Actually, I would imagine that such a processor could use a very long
nano-manufactured fiber loop as memory. Sorta like mercury tube storage...

But.. You'd be the one to know about fancy processor dohickies wouldn't
you? :)


--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: testing/pre-7 and do_poll()

[estafford]

On 11-Jan-99 Linus Torvalds wrote:
> 
> 
> On Mon, 11 Jan 1999, Shawn Leas wrote:
> 
>> On Sun, 10 Jan 1999, Linus Torvalds wrote:
>> 
>> > things. So far, megahertz are still far in the future, but maybe I some
>> > day will have to remove even that assumption. Unlikely to be a problem in
>> > my lifetime, but hey, I can hope (whether due to a long life or really
>> > fast CPU's, I don't care ;) 
>> 
>> Well, they've made a photonic chip, so we may be thinking about this
>> sooner than you think... Think 200GHz processors.
> 
> Hey, I want to see the memory subsystems for it..
> 
>               Linus

Got any links to such technology?  I've been working on it for a while, but
making transistors from glass are not quite as easy as I would think.. Lemme
know.

----------------------------------------
Ed Stafford            Of. (901)348-3487
iXL Hosting            Fx. (901)345-9992      
Programming Engineer   estafford@ixl.com
----------------------------------------

--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: testing/pre-7 and do_poll()

[Linus Torvalds]

On Mon, 11 Jan 1999, Shawn Leas wrote:

> On Sun, 10 Jan 1999, Linus Torvalds wrote:
> 
> > things. So far, megahertz are still far in the future, but maybe I some
> > day will have to remove even that assumption. Unlikely to be a problem in
> > my lifetime, but hey, I can hope (whether due to a long life or really
> > fast CPU's, I don't care ;) 
> 
> Well, they've made a photonic chip, so we may be thinking about this
> sooner than you think... Think 200GHz processors.

Hey, I want to see the memory subsystems for it..

		Linus

--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: testing/pre-7 and do_poll()

[Shawn Leas]

On Sun, 10 Jan 1999, Linus Torvalds wrote:

> things. So far, megahertz are still far in the future, but maybe I some
> day will have to remove even that assumption. Unlikely to be a problem in
> my lifetime, but hey, I can hope (whether due to a long life or really
> fast CPU's, I don't care ;) 

Well, they've made a photonic chip, so we may be thinking about this
sooner than you think... Think 200GHz processors.

-Shawn
<=========== America Held Hostage ===========>
   Day 2182 for the poor and the middle class. 
   Day 2201 for the rich and the dead.
   740 days remaining in the Raw Deal.
<============================================> 

--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: testing/pre-7 and do_poll()

[Adam Heath]

On Sun, 10 Jan 1999, Chip Salzenberg wrote:

> According to Linus Torvalds:
> > There's a "pre-7.gz" on ftp.kernel.org in testing, anybody interested?
> 
> Got it, like it -- *except* the fix for overflow in do_poll() is a
> little bit off.  Quoting testing/pre-7:
> 
> 	if (timeout) {
> 		/* Carefula about overflow in the intermediate values */
> 		if ((unsigned long) timeout < MAX_SCHEDULE_TIMEOUT / HZ)
> 			timeout = (timeout*HZ+999)/1000+1;
> 		else /* Negative or overflow */
> 			timeout = MAX_SCHEDULE_TIMEOUT;
> 	}
> 
> However, the maximum legal millisecond timeout isn't (as shown)
> MAX_SCHEDULE_TIMEOUT/HZ, but rather MAX_SCHEDULE_TIMEOUT/(1000/HZ).
> So this code will turn some large timeouts into MAX_SCHEDULE_TIMEOUT
> unnecessarily.

A/(B/C) = A * (C / B) = A / B * C (done this way to eliminate overflow)

MAX_SCHEDULE_TIMEOUT / 1000 * HZ

Adam


--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: testing/pre-7 and do_poll()

[Linus Torvalds]

On Mon, 11 Jan 1999, Chip Salzenberg wrote:
> > 
> > Hint: HZ is a define - not 100.
> > You just ended up dividing by zero on certain architectures.
> 
> I didn't think HZ ranged over 1000 in practice, else of course I would
> not have written the above.

I made the same assumption wrt usecs (notice how I myself would divide by
zero on any architecture where HZ is over 1000000).

Right now, HZ is 100 on most architectures, with alpha being the exception
at 1024. Some of the PC speaker patches used to have HZ at 8192 even on a
PC, although later versions scaled it down (and just internally used a
timer tick happening at 8kHz, leaving HZ at 100).

With modern machines, 100Hz is just peanuts, and a HZ in the kilohertz
certainly makes sense - and allows for nicer granularity for a lot of
things. So far, megahertz are still far in the future, but maybe I some
day will have to remove even that assumption. Unlikely to be a problem in
my lifetime, but hey, I can hope (whether due to a long life or really
fast CPU's, I don't care ;) 

		Linus

--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: testing/pre-7 and do_poll()

[Chip Salzenberg]

According to Linus Torvalds:
> On Mon, 11 Jan 1999, Chip Salzenberg wrote:
> > Well, I forgot the (unsigned long) cast, as someone else noted:
> > 	timeout = ROUND_UP((unsigned long) timeout, 1000/HZ);
> > Otherwise, the code is Just Right.
> 
> Hint: HZ is a define - not 100.
> You just ended up dividing by zero on certain architectures.

I didn't think HZ ranged over 1000 in practice, else of course I would
not have written the above.
-- 
Chip Salzenberg      - a.k.a. -      <chip@perlsupport.com>
      "When do you work?"   "Whenever I'm not busy."
--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: testing/pre-7 and do_poll()

[Linus Torvalds]

On Mon, 11 Jan 1999, Chip Salzenberg wrote:
> 
> Well, I forgot the (unsigned long) cast, as someone else noted:
> 
> 	timeout = ROUND_UP((unsigned long) timeout, 1000/HZ);
> 
> Otherwise, the code is Just Right.

Duh?

The above code is basically just completely wrong.

Hint: HZ is a define - not 100.

You just ended up dividing by zero on certain architectures.

		Linus

--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: testing/pre-7 and do_poll()

[Chip Salzenberg]

According to Linus Torvalds:
> On Sun, 10 Jan 1999, Chip Salzenberg wrote:
> > However, the maximum legal millisecond timeout isn't (as shown)
> > MAX_SCHEDULE_TIMEOUT/HZ, but rather MAX_SCHEDULE_TIMEOUT/(1000/HZ).
> > So this code will turn some large timeouts into MAX_SCHEDULE_TIMEOUT
> > unnecessarily.
> 
> Note the comment (and do NOT look at the speeling).  In particular,
> we need to make sure the _intermediate_ value doesn' toverflow.

Of course; that's obvious.  What's perhaps less obvious is that I'm
suggesting a change in the calculation of timeout -- a change which
avoids the creation of unnecessarily large _intermediate_ values.

> > ! 	if (timeout < 0)
> > ! 		timeout = MAX_SCHEDULE_TIMEOUT;
> > ! 	else if (timeout)
> > ! 		timeout = ROUND_UP(timeout, 1000/HZ);
> 
> Eh? And re-introduce the original bug?

Well, I forgot the (unsigned long) cast, as someone else noted:

	timeout = ROUND_UP((unsigned long) timeout, 1000/HZ);

Otherwise, the code is Just Right.
-- 
Chip Salzenberg      - a.k.a. -      <chip@perlsupport.com>
      "When do you work?"   "Whenever I'm not busy."
--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

Re: testing/pre-7 and do_poll()

[Linus Torvalds]

On Sun, 10 Jan 1999, Chip Salzenberg wrote:
> 
> Got it, like it -- *except* the fix for overflow in do_poll() is a
> little bit off.  Quoting testing/pre-7:
> 
> 	if (timeout) {
> 		/* Carefula about overflow in the intermediate values */
> 		if ((unsigned long) timeout < MAX_SCHEDULE_TIMEOUT / HZ)
> 			timeout = (timeout*HZ+999)/1000+1;
> 		else /* Negative or overflow */
> 			timeout = MAX_SCHEDULE_TIMEOUT;
> 	}
> 
> However, the maximum legal millisecond timeout isn't (as shown)
> MAX_SCHEDULE_TIMEOUT/HZ, but rather MAX_SCHEDULE_TIMEOUT/(1000/HZ).
> So this code will turn some large timeouts into MAX_SCHEDULE_TIMEOUT
> unnecessarily.

Note the comment (and do NOT look at the speeling).

In particular, we need to make sure the _intermediate_ value doesn'
toverflow. We could do that by using 64-bit arithmetic, but let's not.

> ! 	if (timeout < 0)
> ! 		timeout = MAX_SCHEDULE_TIMEOUT;
> ! 	else if (timeout)
> ! 		timeout = ROUND_UP(timeout, 1000/HZ);

Eh? And re-introduce the original bug?

		Linus

--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org

testing/pre-7 and do_poll()

[Chip Salzenberg]

According to Linus Torvalds:
> There's a "pre-7.gz" on ftp.kernel.org in testing, anybody interested?

Got it, like it -- *except* the fix for overflow in do_poll() is a
little bit off.  Quoting testing/pre-7:

	if (timeout) {
		/* Carefula about overflow in the intermediate values */
		if ((unsigned long) timeout < MAX_SCHEDULE_TIMEOUT / HZ)
			timeout = (timeout*HZ+999)/1000+1;
		else /* Negative or overflow */
			timeout = MAX_SCHEDULE_TIMEOUT;
	}

However, the maximum legal millisecond timeout isn't (as shown)
MAX_SCHEDULE_TIMEOUT/HZ, but rather MAX_SCHEDULE_TIMEOUT/(1000/HZ).
So this code will turn some large timeouts into MAX_SCHEDULE_TIMEOUT
unnecessarily.

Therefore, I suggest this patch:

Index: fs/select.c
*************** asmlinkage int sys_poll(struct pollfd * 
*** 336,346 ****
  		goto out;
  
! 	if (timeout) {
! 		/* Carefula about overflow in the intermediate values */
! 		if ((unsigned long) timeout < MAX_SCHEDULE_TIMEOUT / HZ)
! 			timeout = (timeout*HZ+999)/1000+1;
! 		else /* Negative or overflow */
! 			timeout = MAX_SCHEDULE_TIMEOUT;
! 	}
  
  	err = -ENOMEM;
--- 336,343 ----
  		goto out;
  
! 	if (timeout < 0)
! 		timeout = MAX_SCHEDULE_TIMEOUT;
! 	else if (timeout)
! 		timeout = ROUND_UP(timeout, 1000/HZ);
  
  	err = -ENOMEM;


-- 
Chip Salzenberg      - a.k.a. -      <chip@perlsupport.com>
      "When do you work?"   "Whenever I'm not busy."
--
This is a majordomo managed list.  To unsubscribe, send a message with
the body 'unsubscribe linux-mm me@address' to: majordomo@kvack.org