Re: Linux VM design

Re: Linux VM design

[VDA]

Hi VM folks,

I'd like your comments on this (rather simplistic) hypothetic
VM description. If you know what's wrong with it, please tell me.


Ram page can be:

free
        Not used by anything.

clean non-backed
        Initially allocated page. All such pages share
        global zero-filled readonly page. On write COW magic
        is making a dirty non-backed copy
        
dirty non-backed
        This ram page have copy neither in swap nor in fs.
        Under light i/o load page laundering machinery
        _may_ allocate swap for it and write it back.
        Only after a timeout. No point in writing back
        too early/too often. This laundering can be
        turned off completely without much harm.

clean swap-backed
        This ram page has a copy on swap. It is not modified
        (either swapped in or is already laundered)
        Note: as soon as it gets dirty, it becomes
        dirty *non-backed* and swap page is freed
        
dirty swap-backed
        This ram page was modified some time ago, become
        dirty non-backed, and is being written back right now
        to newly allocated swap page (laundering or
        (evicting LRU ram page under memory pressure)).
        A temporary stage. Turns clean swap-backed
        as soon as write completes.

clean fs-backed
        This ram page is mmapped from a file and is not modified
        or already written back
        
dirty fs-backed
        This ram page is mmapped from a file and is modified.
        It needs to be written back within reasonable timeout
        to keep fs data consistent


How LRU works
        
All non-free ram pages are in LRU list. Top ram page on the list
is the most recently accessed one. Bottom one is least recently
accessed one.

VM periodically scans all process pte's looking for 'accessed'
and 'dirty' bits, resets those bits, modifies page status:

Accessed bit set: Move ram page to top of LRU list.
Dirty bit set:
    clean non-backed  -  can't happen (global zero page is RO)
    dirty non-backed  -> dirty non-backed
    clean swap-backed -> dirty non-backed (note: swap page freed!)
    dirty swap-backed -> dirty non-backed (note: complicated case. See below)
    clean fs-backed   -> dirty fs-backed
    dirty fs-backed   -> dirty fs-backed

Complicated case:
We are writing ram page to swap either due to:
1) Evicting LRU ram page under memory pressure
2) Laundering ram page under light io load
and page gets accessed/dirtied by some process.
In first case we are in deep trouble. To prevent this we must
unmap ram page from all processes before evicting.
In second case we are fine, however, laundering io is wasted.
Ram page should become dirty non-backed again and moved
to top of LRU list, swap page freed.


Ram page eviction

We evict ram pages when we have no free ram pages and
we have a memory request:
1) a process accesses not-present (swapped out) page
2) a process accesses not-present page mmaped to a file
3) a process writes to clean non-backed ram page and COW needs
   new ram page to make a copy

Rate of such evictions is a good measure of mem pressure.

We evict ram page from the bottom of LRU list by unmapping it from
all processes, writing back to fs or allocating swap and writing back
to swap if it is dirty and using freed ram page to fulfill memory
request.
-- 
Best regards, VDA
mailto:VDA@port.imtp.ilyichevsk.odessa.ua

Re: Linux VM design

[Rik van Riel]

On Tue, 25 Sep 2001, VDA wrote:

> I'd like your comments on this (rather simplistic) hypothetic
> VM description. If you know what's wrong with it, please tell me.

It's a nice start, but not quite accurate. You may want to
read my freenix paper and some of the documents on the
linux-mm page:

	http://linux-mm.org/
	http://www.surriel.com/lectures/

cheers,

Rik
-- 
IA64: a worthy successor to i860.

http://www.surriel.com/		http://distro.conectiva.com/

Send all your spam to aardvark@nl.linux.org (spam digging piggy)

Re: Linux VM design

[bill davidsen]

In article <20010924182948Z16175-2757+1593@humbolt.nl.linux.org> phillips@bonn-fries.net wrote:

| You might want to have a look at this:
| 
|    http://archi.snu.ac.kr/jhkim/seminar/96-004.ps
|    (lrfu algorithm)
| 
| To tell the truth, I don't really see why the frequency information is all
| that useful either.  Rik suggested it's good for streaming IO but we already 
| have effective means of dealing with that that don't rely on any frequency 
| information.

  A count which may actually be useful is a count of how many time the
page has been swapped in (after being swapped out) as a predictor that
it will be a good page to keep. The problem is that there are many
things which help, and I don't think we have the balance quite right
yet. I suspect that there need to be some hysteresis and runtime tuning
over seconds to get optimal performance. Of course systems with really
odd loads will still need to have hand tuning, and the /proc/sys
interface should include sensible ways to do this.

| So the list of reasons why aging is good is looking really short.

  The primary reason on my list is that under some load conditions it
produces much better response. Note that I didn't say all conditions
before you rush to disagree with me. Sometimes people will trade a
little steady state performance to avoid a really bad worst case.

  How the problem is solved really isn't the issue, but responsiveness
is important. Right now it seems some people are reporting that their
loads work better with aging.

-- 
bill davidsen <davidsen@tmr.com>
 "If I were a diplomat, in the best case I'd go hungry.  In the worst
  case, people would die."
		-- Robert Lipe

Re: Linux VM design

[VDA]

Hello Dan,
Monday, September 24, 2001, 10:11:08 PM, you wrote:

DM> I hope this isn't the wrong place to ask this but,  wouldn't it be better to
DM> increase ram size and decrease swap size as memory requirements grow?  For
DM> instance, say I have a lightly loaded machine, that has 192MB of ram.  From
DM> everything I've heard in the past, I'd use roughly 192MB of swap with this
DM> machine.  The problem I would imagine is that if all 192MB got used wouldn't
DM> it be terribly slow to read/write that much data back in?  Would less swap,
DM> say 32 MB make the kernel more restrictive with it's available memory and
DM> make the box more responsive when it's heavily using swap?

If you want everything to be fast, buy more RAM and use no swap whatsoever.

Swap is useful if your total memory requirements are big but working
set is significantly smaller. You need RAM to cover working set
and RAM+swap to cover total memory requirements.

As you can see, amount of RAM and swap thus *application dependent*.
-- 
Best regards, VDA
mailto:VDA@port.imtp.ilyichevsk.odessa.ua

Re: Linux VM design

[Daniel Phillips]

On September 24, 2001 09:32 pm, Rik van Riel wrote:
> On Mon, 24 Sep 2001, Daniel Phillips wrote:
> > To tell the truth, I don't really see why the frequency
> > information is all that useful either.
> 
> > So the list of reasons why aging is good is looking really short.
> 
> Ummmm, that _you_ can't see it doesn't mean suddenly all
> VM research from the last 15 years has been invalidated.

Did you have some more reasons to add to the list?

--
Daniel

Re: Linux VM design

[Rik van Riel]

On Mon, 24 Sep 2001, Rob Landley wrote:

> Out of morbid curiosity, how much of that research either said
> or assumed that microkernels were a good idea?

*grin*

None that I can remember even dealt with this. The
page replacement research I've read was both generic
OS and database page replacement, maybe 50 to 100
papers total...

cheers,

Rik
--
IA64: a worthy successor to the i860.

		http://www.surriel.com/
http://www.conectiva.com/	http://distro.conectiva.com/

Re: Linux VM design

[Rik van Riel]

On Mon, 24 Sep 2001, Daniel Phillips wrote:

> To tell the truth, I don't really see why the frequency
> information is all that useful either.

> So the list of reasons why aging is good is looking really short.

Ummmm, that _you_ can't see it doesn't mean suddenly all
VM research from the last 15 years has been invalidated.

cheers,

Rik
--
IA64: a worthy successor to the i860.

		http://www.surriel.com/
http://www.conectiva.com/	http://distro.conectiva.com/

Re: Linux VM design

[Daniel Phillips]

On September 24, 2001 08:46 pm, Jonathan Morton wrote:
> >  > DP> The arguments in support of aging over LRU that I'm aware of are:
> >>
> >>  DP>   - incrementing an age is more efficient than resetting several LRU
> >>  DP>     list links
> >>  DP>   - also captures some frequency-of-use information
> >>
> >>  Of what use this info can be? If one page is accessed 100 times/second
> >>  and other one once in 10 seconds, they both have to stay in RAM.
> >>  VM should take 'time since last access' into account whan deciding
> >>  which page to swap out, not how often it was referenced.
> >
> >You might want to have a look at this:
> >
> >    http://archi.snu.ac.kr/jhkim/seminar/96-004.ps
> >    (lrfu algorithm)
> >
> >To tell the truth, I don't really see why the frequency information is all
> >that useful either.  Rik suggested it's good for streaming IO but we 
already
> >have effective means of dealing with that that don't rely on any frequency
> >information.
> >
> >So the list of reasons why aging is good is looking really short.
> 
> It's not really frequency information.  If a page is accessed 1000 
> times during a single schedule cycle, that will count as a single 
> increment in the age come the time.  However, *macro* frequency 
> information of this type *is* useful in the case where thrashing is 
> taking place.  You want to swap out the page that is accessed only 
> once every other schedule cycle, before the one accessed every cycle. 

But this happens naturally with LRU.  Think how it works: to get evicted a 
page has to progress all the way from the head to the tail of the LRU list.  
Any page that's accessed frequently is going to keep being put back at the 
head of the list, and only infrequently accessed pages will drop off the tail.

> This is of course moot if one process is being suspended (as it 
> probably should), but the criteria for suspension might include this 
> access information.

OK, that does get at something you can do with aging that you can't do with 
an LRU list: look at the weightings of random pages.  You can't do that with 
the LRU list because there's no efficient way to determine which position a 
page holds in the list.

One application where you would want to know the weightings of random pages 
is defragmentation.  That might become important in the future but we're not 
doing it now.

A little contemplation will probably turn up other uses for this special 
property.

--
Daniel

Re: Linux VM design

[Dan Mann]

I hope this isn't the wrong place to ask this but,  wouldn't it be better to
increase ram size and decrease swap size as memory requirements grow?  For
instance, say I have a lightly loaded machine, that has 192MB of ram.  From
everything I've heard in the past, I'd use roughly 192MB of swap with this
machine.  The problem I would imagine is that if all 192MB got used wouldn't
it be terribly slow to read/write that much data back in?  Would less swap,
say 32 MB make the kernel more restrictive with it's available memory and
make the box more responsive when it's heavily using swap?

Or am I way off and just smoking crack?  (which I may very well be)

This damn mailing list is addictive.  Now I read it at work.

Dan

Re: Linux VM design

[Jonathan Morton]

>  > DP> The arguments in support of aging over LRU that I'm aware of are:
>>
>>  DP>   - incrementing an age is more efficient than resetting several LRU
>>  DP>     list links
>>  DP>   - also captures some frequency-of-use information
>>
>>  Of what use this info can be? If one page is accessed 100 times/second
>>  and other one once in 10 seconds, they both have to stay in RAM.
>>  VM should take 'time since last access' into account whan deciding
>>  which page to swap out, not how often it was referenced.
>
>You might want to have a look at this:
>
>    http://archi.snu.ac.kr/jhkim/seminar/96-004.ps
>    (lrfu algorithm)
>
>To tell the truth, I don't really see why the frequency information is all
>that useful either.  Rik suggested it's good for streaming IO but we already
>have effective means of dealing with that that don't rely on any frequency
>information.
>
>So the list of reasons why aging is good is looking really short.

It's not really frequency information.  If a page is accessed 1000 
times during a single schedule cycle, that will count as a single 
increment in the age come the time.  However, *macro* frequency 
information of this type *is* useful in the case where thrashing is 
taking place.  You want to swap out the page that is accessed only 
once every other schedule cycle, before the one accessed every cycle. 
This is of course moot if one process is being suspended (as it 
probably should), but the criteria for suspension might include this 
access information.

-- 
--------------------------------------------------------------
from:     Jonathan "Chromatix" Morton
mail:     chromi@cyberspace.org  (not for attachments)
website:  http://www.chromatix.uklinux.net/vnc/
geekcode: GCS$/E dpu(!) s:- a20 C+++ UL++ P L+++ E W+ N- o? K? w--- O-- M++$
           V? PS PE- Y+ PGP++ t- 5- X- R !tv b++ DI+++ D G e+ h+ r++ y+(*)
tagline:  The key to knowledge is not to rely on people to teach you it.

Re: Linux VM design

[Daniel Phillips]

On September 24, 2001 11:36 am, VDA wrote:
> Daniel Phillips <phillips@bonn-fries.net> wrote:
> DP> The arguments in support of aging over LRU that I'm aware of are:
> 
> DP>   - incrementing an age is more efficient than resetting several LRU 
> DP>     list links
> DP>   - also captures some frequency-of-use information
> 
> Of what use this info can be? If one page is accessed 100 times/second
> and other one once in 10 seconds, they both have to stay in RAM.
> VM should take 'time since last access' into account whan deciding
> which page to swap out, not how often it was referenced.

You might want to have a look at this:

   http://archi.snu.ac.kr/jhkim/seminar/96-004.ps
   (lrfu algorithm)

To tell the truth, I don't really see why the frequency information is all
that useful either.  Rik suggested it's good for streaming IO but we already 
have effective means of dealing with that that don't rely on any frequency 
information.

So the list of reasons why aging is good is looking really short.

--
Daniel

Re: Linux VM design

[Rob Landley]

On Monday 24 September 2001 15:32, Rik van Riel wrote:
> On Mon, 24 Sep 2001, Daniel Phillips wrote:
> > To tell the truth, I don't really see why the frequency
> > information is all that useful either.
> >
> > So the list of reasons why aging is good is looking really short.
>
> Ummmm, that _you_ can't see it doesn't mean suddenly all
> VM research from the last 15 years has been invalidated.

Out of morbid curiosity, how much of that research either said or assumed 
that microkernels were a good idea?

Rob

Re: Linux VM design

[Rik van Riel]

[grrrrr, the dog was sitting against my arm and I pressed the
wrong key ;)]

On Mon, 24 Sep 2001, VDA wrote:

> >Virtual Memory Management Policy
> >--------------------------------
> >The basic principle of the Linux VM system is page aging.

> is better than plain simple LRU?

All research I've seen indicates that it's better to take
frequency into account as well instead of only access
recency.

Plain LRU just breaks down under sequential IO, LRU with
a large enough inactive list should hold up decently under
streaming IO, but only a replacement strategy which keeps
access frequency into account too will be able to make
proper decisions as to which pages to keep in memory and
which pages to throw out.

Note that it's not me making this up, it's simply the info
I've seen everywhere ... I don't like reinventing the wheel ;)

> We definitely need VM FAQ to have these questions answered once per VM
> design, not once per week :-)

Go ahead, make on on the Linux-MM wiki:

	http://linux-mm.org/wiki/

(note that for some reason the thing gives an internal
server error once in a while ... I haven't yet been able
to find a pattern to it, so I it's not fixed yet)

regards,

Rik
-- 
IA64: a worthy successor to i860.

http://www.surriel.com/		http://distro.conectiva.com/

Send all your spam to aardvark@nl.linux.org (spam digging piggy)

Re: Linux VM design

[Rik van Riel]

On Mon, 24 Sep 2001, VDA wrote:

> RvR> http://linux-mm.org/
>
> I was there today. Good. Can this stuff be placed as
> Doc/mv/vm2.4rik
> to prevent it from being outdated in 2-3 months?

Putting documents in the kernel tree has never worked
as a means of keeping them up to date.

Unless, of course, you're volunteering to keep them
up to date ;)

> Also I'd like to be enlightened why this:
>
> >Virtual Memory Management Policy
> >--------------------------------
> >The basic principle of the Linux VM system is page aging.

> is better than plain simple LRU?
>
> We definitely need VM FAQ to have these questions answered once per VM
> design, not once per week :-)



> RvR> The only thing missing is an explanation of Andrea's
> RvR> VM, but knowing Andrea's enthusiasm at documentation
> RvR> I wouldn't really count on that any time soon ;)
>
> :-)
>
> --
> Best regards, VDA
> mailto:VDA@port.imtp.ilyichevsk.odessa.ua
>
>

Rik
-- 
IA64: a worthy successor to i860.

http://www.surriel.com/		http://distro.conectiva.com/

Send all your spam to aardvark@nl.linux.org (spam digging piggy)

Re: Linux VM design

[VDA]

Hello Rik,
Monday, September 24, 2001, 4:29:46 PM, you wrote:

>> Since we reached some kind of stability with 2.4, maybe
>> Andrea, Rik and whoever else is considering himself VM geek
>> would tell us not-so-clever lkml readers how VM works and put it in
>> vm-2.4andrea, vm-2.4rik or whatever in Doc/vm/*,
>> I will be unbelievably happy. Matt Dillon's post belongs there too.

RvR> http://linux-mm.org/

I was there today. Good. Can this stuff be placed as
Doc/mv/vm2.4rik
to prevent it from being outdated in 2-3 months?
Linus?

Also I'd like to be enlightened why this:

>Virtual Memory Management Policy
>--------------------------------
>The basic principle of the Linux VM system is page aging. We've seen
>that refill_inactive_scan() is invoked periodically to try to
>deactivate pages, and that it ages pages down as it does so,
>deactivating them when their age reaches 0. We've also seen that
>swap_out() will age referenced page frames up while scanning process
>memory maps. This is the fundamental mechanism for VM resource
>balancing in Linux: pages are aged down at a more-or-less steady rate,
>and deactivated when they become sufficiently old; but processes can
>keep pages "young" by referencing them frequently.

is better than plain simple LRU?

We definitely need VM FAQ to have these questions answered once per VM
design, not once per week :-)

RvR> The only thing missing is an explanation of Andrea's
RvR> VM, but knowing Andrea's enthusiasm at documentation
RvR> I wouldn't really count on that any time soon ;)

:-)

-- 
Best regards, VDA
mailto:VDA@port.imtp.ilyichevsk.odessa.ua

Re: Linux VM design

[Rik van Riel]

On Mon, 24 Sep 2001, VDA wrote:

> I'd like to understand Linux VM but there's not much in
> Documentation/vm/* on the subject.

http://linux-mm.org/ has some stuff and I wrote a freenix
paper on the subject as well http://www.surriel.com/lectures/.

> Since we reached some kind of stability with 2.4, maybe
> Andrea, Rik and whoever else is considering himself VM geek
> would tell us not-so-clever lkml readers how VM works and put it in
> vm-2.4andrea, vm-2.4rik or whatever in Doc/vm/*,
> I will be unbelievably happy. Matt Dillon's post belongs there too.

http://linux-mm.org/

The only thing missing is an explanation of Andrea's
VM, but knowing Andrea's enthusiasm at documentation
I wouldn't really count on that any time soon ;)

cheers,

Rik
-- 
IA64: a worthy successor to i860.

http://www.surriel.com/		http://distro.conectiva.com/

Send all your spam to aardvark@nl.linux.org (spam digging piggy)

Re: Linux VM design

[Kirill Ratkin]

--- Dave Jones <davej@suse.de> wrote:
> On Mon, 24 Sep 2001, VDA wrote:
> 
> > I'd like to understand Linux VM but there's not
> much in
> > Documentation/vm/* on the subject. I understand
> that with current
> > frantic development pace it is hard to maintain
> such docs.
> 
> In case you're not aware of it,
> http://linux-mm.org/wiki/moin.cgi
> is starting to fill out with documentation/ideas/etc
> on VM strategies
> past, present and future.
> 
> regards,
> 
> Dave.
> 
> -- 
> | Dave Jones.        http://www.suse.de/~davej
> | SuSE Labs
> 

And here:
http://home.earthlink.net/~jknapka/linux-mm/vmoutline.html

> -
> To unsubscribe from this list: send the line
> "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at 
> http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/


__________________________________________________
Do You Yahoo!?
Get email alerts & NEW webcam video instant messaging with Yahoo! Messenger. http://im.yahoo.com

Re: Linux VM design

[Dave Jones]

On Mon, 24 Sep 2001, VDA wrote:

> I'd like to understand Linux VM but there's not much in
> Documentation/vm/* on the subject. I understand that with current
> frantic development pace it is hard to maintain such docs.

In case you're not aware of it, http://linux-mm.org/wiki/moin.cgi
is starting to fill out with documentation/ideas/etc on VM strategies
past, present and future.

regards,

Dave.

-- 
| Dave Jones.        http://www.suse.de/~davej
| SuSE Labs

Linux VM design

[VDA]

[-- Attachment #1: Type: text/plain, Size: 3776 bytes --]

Hi VM folks,

I'd like to understand Linux VM but there's not much in
Documentation/vm/* on the subject. I understand that with current
frantic development pace it is hard to maintain such docs.

However, with only a handful of people really understading how VM
works we risk ending in a situation when nobody will know how to fix
it (does recent Andrea's VM rewrite just replaced large part of hardly
maintenable, not-quite-right VM in 2.4.10?)

When I have a stalled problem to solve, I sometimes catch
unsuspecting victim and start explainig what I am trying to do and
how I'm doing that. Often, in the middle of my explanation, I realize
myself what I did wrong. There is an old teacher's joke:
"My pupils are dumb! I explained them this theme once, then twice, I
finally myself understood it, and they still don't".
        ^^^^^^^^^^^^^^^^^^^^
Since we reached some kind of stability with 2.4, maybe
Andrea, Rik and whoever else is considering himself VM geek
would tell us not-so-clever lkml readers how VM works and put it in
vm-2.4andrea, vm-2.4rik or whatever in Doc/vm/*,
I will be unbelievably happy. Matt Dillon's post belongs there too.

I have an example how I would describe VM if I knew anything about it.
I am putting it in the zip attachment just to reduce number of
people laughing on how stupid I am :-). Most lkml readers won't open
it, I hope :-).

If VM geeks are disagreeing with each other on some VM inner workings,
they can describe their views in those separate files, giving readers
ability to compare their VM designs. Maybe these files will evolve in
VM FAQs.

Saturday, September 22, 2001, 2:01:02 PM,
Daniel Phillips <phillips@bonn-fries.net> wrote:
DP> The arguments in support of aging over LRU that I'm aware of are:

DP>   - incrementing an age is more efficient than resetting several LRU list links
DP>   - also captures some frequency-of-use information

Of what use this info can be? If one page is accessed 100 times/second
and other one once in 10 seconds, they both have to stay in RAM.
VM should take 'time since last access' into account whan deciding
which page to swap out, not how often it was referenced.

DP>   - it can be implemented in hardware (not that that matters much)
DP>   - allows more scope for tuning/balancing (and also rope to hang oneself)

DP> The big problem with aging is that unless it's entirely correctly balanced its
DP> just not going to work very well.  To balance it well requires knowing a lot
DP> about rates of list scanning and so on.  Matt Dillon perfected this art in BSD,
DP> but we never did, being preoccupied with things like just getting the mm
DP> scanners to activate when required, and sorting out our special complexities
DP> like zones and highmem buffers.  Probably another few months of working on it
DP> would let us get past the remaining structural problems and actually start
DP> tuning it, but we've already made people wait way too long for a stable 2.4.
DP> A more robust strategy makes a lot of sense right now.  We can still play with
DP> stronger magic in 2.5, and of course Rik's aging strategy will continue to be
DP> developed in Alan's tree while Andrea's is still going through the test of
DP> fire.
DP> </musings>

DP> I'll keep reading Andrea's code and maybe I'll be able to shed some more light
DP> on the algorithms he's using, since he doesn't seem to be in a big hurry to
DP> do that himself.  (Hi Andrea ;-)

DP> --
DP> Daniel
DP> -
DP> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
DP> the body of a message to majordomo@vger.kernel.org
DP> More majordomo info at  http://vger.kernel.org/majordomo-info.html
DP> Please read the FAQ at  http://www.tux.org/lkml/




-- 
Best regards, VDA
mailto:VDA@port.imtp.ilyichevsk.odessa.ua

[-- Attachment #2: Vm-dumb.zip --]
[-- Type: application/x-zip-compressed, Size: 2006 bytes --]