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: Results: pre6 vs pre6+zlatko's_patch vs pre5 vs arcavm13

[Steve Bergman]

Linus Torvalds wrote:

> The logic for that would be something like the attached patch to
> page_alloc.c..


I tried the patch in the 'image test' and it helped little if any.  Still a lot
of swapping in and the numbers are close enough that I'm not sure it helped at
all.  This was a comparison between vanilla pre6 and vanilla
pre6+page_alloc_patch with no other patches applied.

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

Re: Results: pre6 vs pre6+zlatko's_patch vs pre5 vs arcavm13

[Linus Torvalds]

On Sun, 10 Jan 1999, Steve Bergman wrote:
> 
> I tried the patch in the 'image test' and it helped little if any.  Still a lot
> of swapping in and the numbers are close enough that I'm not sure it helped at
> all.  This was a comparison between vanilla pre6 and vanilla
> pre6+page_alloc_patch with no other patches applied.

Ok, I think I now know why pre-6 looks so unbalanced. It's two issues. 

Basically, trying to swap out a large number of pages from one process
context is just doomed. It bascially sucks, because

 - it has bad latency. This is further excerberated by the per-process
   "thrashing_memory" flag, which means that if we were unlucky enough to
   be selected to be the process that frees up memory, we'll probably be
   stuck with it for a long time. That can make it extremely unfair under
   some circumstances - other processes may allocate the pages we free'd
   up, so that we keep on being counted as a memory trasher even if we
   really aren't. 

   Note that this shows most under "moderate" load - the problem doesn't
   tend to show itself if you have some process that is _really_
   allocating a lot of pages, because then that process will be correctly
   found by the trashing logic. But if you have lots of "normal load"
   processes, some of those can get really badly hurt by this.

   In particular, the worst case you have a number of processes that all
   allocate memory, but not very quickly - certainly not more quickly than
   we can page things out. What happens is that under these circumstances
   one of them gets marked as a "scapegoat", and once that happens all the
   others will just live off the pages that the scapegoat frees up, while
   the scapegoat itself doesn't make much progress at all because it is
   always just freeing memory for others. 

   The really bad behaviour tends to go away reasonably quickly, but while
   it happens it's _really_ unfair.

 - try_to_free_pages() just goes overboard, and starts paging stuff out
   without getting back to the nice balanced behaviour. This is what
   Andrea noticed.

   Essentially, once it starts failing the shrink_mmap() tests, it will
   just page things out crazily. Normally this is avoided by just always
   starting from shrink_mmap(), but if you ask try_to_free_pages() to try
   to free up a ton of pages, the balancing that it does is basically
   bypassed.

So basically pre-6 works _really_ well for the kind of stress-me stuff
that it was designed for: a few processes that are extremely memory
hungry. It gets close to perfect swap-out behaviour, simply because it is
optimized for getting into a paging rut. 

That makes for nice benchmarks, but it also explains why (a) sometimes
it's just not very nice for interactive behaviour and (b) why it under
normal load can easily swap much too eagerly.

Anyway, the first problem is fixed by making "trashing" be a global flag
rather than a per-process flag. Being per-process is really nice when it
finds the right process, but it's really unfair under a lot of other
circumstances. I'd rather be fair than get the best possible page-out
speed. 

Note that even a global flag helps: it still clusters the write-outs, and
means that processes that allocate more pages tend to be more likely to be
hit by it, so it still does a large part of what the per-process flag did
- without the unfairness (but admittedly being unfair sometimes gets you
better performance - you just have to be _very_ careful whom you target
with the unfairness, and that's the hard part). 

The second problem actually goes away by simply just not asking
try_to_free_pages() to free too many pages - and having the global
trashing flag makes it unnecessary to do so anyway because the flag will
essentially cluster the page-outs even without asking for them to be all
done in one large chunk (and now it's not just one process that gets hit
any more).

There's a "pre-7.gz" on ftp.kernel.org in testing, anybody interested? 
It's not the real thing, as I haven't done the write semaphore deadlock
thing yet, but that one will not affect normal users anyway so for
performance testing this should be equivalent. 

			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

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

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 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 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:
> > 
> > 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()

[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()

[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()

[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()

[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()

[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