Memory compression (again). . help?

Memory compression (again). . help?

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I'm not quite sure what I'm doing or when I have time, but I'm looking
into writing in some hooks and a compression routine to manage
compressed memory.  I have the following considerations:

 - Compressed memory should become "Swap."  This means the kernel would
   report memory used for compressed storage as used swap.  At boot it
   would reflect 0K swap; when there are 1024KiB of pages compressed in
   memory, 1024KiB of additional "swap" is reported, all used.
 - I need to stop the kernel when it's about to swap.  This should be
   done when it's decided that either invalidating disk cache or
   swapping is the best course of action, and what to do with what.  At
   this point I'll have to be able to see what the kernel wants to swap
   out and tell it that it's taken care of.
 - I need to catch invalid pagefaults that look for swap, as well as the
   disk cache mechanism.  I'll be adding stuff to compress disk cache,
   so disk cache might need to be "swapped in" effectively.

Can anyone recommend what functions I should look at modifying?  I'm
planning on using Rodrigo Castro's WK4x4 or WKdm algorithms, as they
worked great in his proof of concept.  32KiB blocks will be used because
I got about a 40% reduction with those, and that was where I reached
asymptotic growth (larger blocks did not compress much more, smaller
blocks compressed much less).

Compressed memory is great for things like LiveCDs and huge database
servers, as well as just giving almost-but-not-quite free memory in general.

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                                     -- Evil alien overlord from Blasto
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.1 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFEA6FKhDd4aOud5P8RAnGyAJ9kFbdxA5+DroHFOZS7oM4uzYhN1gCfbVa+
rHPUYKjXjekcwLnHN+e12IE=
=K/bw
-----END PGP SIGNATURE-----

Re: Memory compression (again). . help?

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1


Hmm, I can't see where the kernel checks to see which pages are least
used. . . . anyone good with the VM can point me in the right direction?

- -
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/


- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                                     -- Evil alien overlord from Blasto
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.1 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFEA8MJhDd4aOud5P8RAtxpAJwJ0nGSykXgSmMWkrpjtg5HWPdlqACfWQQZ
yUay/1CZdoKceqiteMdDcC0=
=F1ac
-----END PGP SIGNATURE-----

Re: Memory compression (again). . help?

[Magnus Damm]

On 2/28/06, John Richard Moser <nigelenki@comcast.net> wrote:
> Hmm, I can't see where the kernel checks to see which pages are least
> used. . . . anyone good with the VM can point me in the right direction?

The page reclaim code responsible for shrinking the LRUs code be found
in mm/vmscan.c. That file contains a lot of code, my recommendation to
you is to have a look at shrink_zone() which is responsible for
rotating and shrinking the active and inactive lists.

Also, If you want to compress pages that normally would be swapped
out, then I recommend you to have a look at the functions in
mm/swap_state.c and see how swap space gets allocated and freed.

If you need to know more about the Linux VM then I recommend you to
buy the excellent book "Understanding the Linux Virtual Memory
Manager" written by Mel Gorman, ISBN 0-13-145348-3. My copy of that
book covers Linux-2.4 and has some comments about 2.6 too.

/ magnus

Re: Memory compression (again). . help?

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Magnus Damm wrote:
> On 2/28/06, John Richard Moser <nigelenki@comcast.net> wrote:
>> Hmm, I can't see where the kernel checks to see which pages are least
>> used. . . . anyone good with the VM can point me in the right direction?
> 
> The page reclaim code responsible for shrinking the LRUs code be found
> in mm/vmscan.c. That file contains a lot of code, my recommendation to
> you is to have a look at shrink_zone() which is responsible for
> rotating and shrinking the active and inactive lists.
> 

Thanks, I'll take a look.

> Also, If you want to compress pages that normally would be swapped
> out, then I recommend you to have a look at the functions in
> mm/swap_state.c and see how swap space gets allocated and freed.
> 

Mm.  Ok.

> If you need to know more about the Linux VM then I recommend you to
> buy the excellent book "Understanding the Linux Virtual Memory
> Manager" written by Mel Gorman, ISBN 0-13-145348-3. My copy of that
> book covers Linux-2.4 and has some comments about 2.6 too.
> 

I'll shoot from the hip, my foot grows back.

> / magnus
> 

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                                     -- Evil alien overlord from Blasto
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.1 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFEBDzdhDd4aOud5P8RApCXAKCASRwqJqXD/8rHh84x3tzkntC6jQCeMeqS
9B7IgG3aCEJOOXrOsxSMp3o=
=ZLh3
-----END PGP SIGNATURE-----

Re: Memory compression (again). . help?

[Rik van Riel]

On Mon, 27 Feb 2006, John Richard Moser wrote:

> Hmm, I can't see where the kernel checks to see which pages are least
> used. . . . anyone good with the VM can point me in the right direction?

Not completely written yet, but take a look at:

	http://linux-mm.org/PageOutKswapd


-- 
All Rights Reversed

Re: Memory compression (again). . help?

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Rik van Riel wrote:
> On Mon, 27 Feb 2006, John Richard Moser wrote:
> 
>> Hmm, I can't see where the kernel checks to see which pages are least
>> used. . . . anyone good with the VM can point me in the right direction?
> 
> Not completely written yet, but take a look at:
> 
> 	http://linux-mm.org/PageOutKswapd
> 

Wow nice.  Confusing, but nice.

I'm currently peeking around vmscan.c, though I can't seem to tell quite
how the kernel knows what's hot and cold.  I heard somewhere that when a
process doesn't use memory for like 5 days, the kernel knows better to
swap that instead of something it used 10 minutes ago.  I'm not sure how
though, I don't think the kernel debugs memory access.  My best guess is
when the page falls out of process TLB, the kernel is notified about it
and keeps these in order; and when it's faulted back into TLB, the
kernel is notified and moves it up to more recently used.  Of course,
this would mean the kernel never invalidates stuff in the process' TLB
(working set), which doesn't make sense.  Either way the inner workings
don't matter much to me; what I'm worried about is where it accounts for
this and more importantly what APIs it provides to query this information.

> 

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                                     -- Evil alien overlord from Blasto
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.1 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFEBIIQhDd4aOud5P8RAnxaAKCOreOPFYNokQzECFPpSAOCbzJsQgCggWav
AIZ+oU4AMRkdMGjp62xdqP0=
=TkEA
-----END PGP SIGNATURE-----

Re: Memory compression (again). . help?

[Alexander E. Patrakov]

John Richard Moser wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> I'm not quite sure what I'm doing or when I have time, but I'm looking
> into writing in some hooks and a compression routine to manage
> compressed memory.  I have the following considerations:
> 
>  - Compressed memory should become "Swap."  This means the kernel would
>    report memory used for compressed storage as used swap.  At boot it
>    would reflect 0K swap; when there are 1024KiB of pages compressed in
>    memory, 1024KiB of additional "swap" is reported, all used.
>  - I need to stop the kernel when it's about to swap.  This should be
>    done when it's decided that either invalidating disk cache or
>    swapping is the best course of action, and what to do with what.  At
>    this point I'll have to be able to see what the kernel wants to swap
>    out and tell it that it's taken care of.
>  - I need to catch invalid pagefaults that look for swap, as well as the
>    disk cache mechanism.  I'll be adding stuff to compress disk cache,
>    so disk cache might need to be "swapped in" effectively.

If you are OK with using a ery old 2.4.18 kernel, look at 
http://linuxcompressed.sourceforge.net/

-- 
Alexander E. Patrakov

Re: Memory compression (again). . help?

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Alexander E. Patrakov wrote:
> John Richard Moser wrote:
>> -----BEGIN PGP SIGNED MESSAGE-----
>> Hash: SHA1
>>
>> I'm not quite sure what I'm doing or when I have time, but I'm looking
>> into writing in some hooks and a compression routine to manage
>> compressed memory.  I have the following considerations:
>>
>>  - Compressed memory should become "Swap."  This means the kernel would
>>    report memory used for compressed storage as used swap.  At boot it
>>    would reflect 0K swap; when there are 1024KiB of pages compressed in
>>    memory, 1024KiB of additional "swap" is reported, all used.
>>  - I need to stop the kernel when it's about to swap.  This should be
>>    done when it's decided that either invalidating disk cache or
>>    swapping is the best course of action, and what to do with what.  At
>>    this point I'll have to be able to see what the kernel wants to swap
>>    out and tell it that it's taken care of.
>>  - I need to catch invalid pagefaults that look for swap, as well as the
>>    disk cache mechanism.  I'll be adding stuff to compress disk cache,
>>    so disk cache might need to be "swapped in" effectively.
> 
> If you are OK with using a ery old 2.4.18 kernel, look at
> http://linuxcompressed.sourceforge.net/
> 

I'm actually looking to submit to mainline in the end ;P  It'd be a very
good permenant feature.  RAM is cheap, but CPU is even cheaper; if I buy
a gig of RAM and get 200M free, woohoo?

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                                     -- Evil alien overlord from Blasto
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.1 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFEBD+KhDd4aOud5P8RAmAjAJ9RvbX1WxtHNDWWJy2LD33ll2JuyQCfefQ/
DbvWtgSk5sE2Uhuge1jvB5M=
=Gbdm
-----END PGP SIGNATURE-----

Re: Memory compression (again). . help?

[Asbjørn Sannes]

John Richard Moser wrote:
> >>> I'm not quite sure what I'm doing or when I have time, but I'm looking
> >>> into writing in some hooks and a compression routine to manage
> >>> compressed memory.
<snip>
> I'm actually looking to submit to mainline in the end ;P  It'd be a very
> good permenant feature.  RAM is cheap, but CPU is even cheaper; if I buy
> a gig of RAM and get 200M free, woohoo?

Nitin Gupta and myself has already started working on a implementation
for 2.6, you are of course welcome to join our effort. Nitin has already
made some code available where you can clearly see where such things
could be done. I can recommend "Understanding the Linux kernel (3rd
Edition)" by Daniel P. Bovet & Marco Cesati. Also, you could take a look
at http://www.kernelnewbies.org/ under recommended books.


Mvh,
Asbjørn Sannes

Re: Memory compression (again). . help?

[John Richard Moser]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Asbjørn Sannes wrote:
> John Richard Moser wrote:
>>>>> I'm not quite sure what I'm doing or when I have time, but I'm looking
>>>>> into writing in some hooks and a compression routine to manage
>>>>> compressed memory.
> <snip>
>> I'm actually looking to submit to mainline in the end ;P  It'd be a very
>> good permenant feature.  RAM is cheap, but CPU is even cheaper; if I buy
>> a gig of RAM and get 200M free, woohoo?
> 
> Nitin Gupta and myself has already started working on a implementation
> for 2.6, you are of course welcome to join our effort. Nitin has already
> made some code available where you can clearly see where such things
> could be done. I can recommend "Understanding the Linux kernel (3rd
> Edition)" by Daniel P. Bovet & Marco Cesati. Also, you could take a look
> at http://www.kernelnewbies.org/ under recommended books.
> 

That's cool.  How are you designing it?  I was planning on structuring
it such that I made the swapping system interruptible via hooks, and
wrote all the code in mm/compress.c; the swapping and vmscan code would
be only slightly touched to allow me to break out of it into compress.c,
where accounting of compressed pages would take place.  I had also
considered that I would need hooks in the disk cache system for it to
make an assumption that disk cache "may be in swap" or similar, as I
want to compress disk cache as well.

I considered that I would have to account my compressed pages to be
"Persistent" (program memory, anonymous memory) and "Transient" (disk
cache, can be freed when memory is low); this would allow for
"Transient" pages to be recognized and simply invalidated when memory
pressure is far too high, effectively allowing for the freeing of disk
cache after it's compressed without decompressing it.  This would of
course require "Transient" pages be designated a destructor so that when
freed they can alert the corresponding system to the action (i.e. tell
disk cache it can no longer access these "swapped" (compressed) pages).

Which compression algorithms are you using?  I did tests with Castro's
patch on 2.4, tweaking it up to 128K pages.  I found that efficiency
increased significantly at each binary step (4K, 8K, 16K...) up to 32K
blocks; beyond that, the gains were minimal.  I recommend WKdm or WK4x4
from Castro's patch, working on sets of 8 pages (32KiB) by default.  In
any case, compressed data should be tailed together; if it uses 9KiB
compressed, then there should be 2 full pages and one page with 3KiB
left, and that 3KiB should be used to store more compressed data.

The algorithm should be in a separate source file and register itself
with the compression system; it should be called indirectly via hook in
the compression code through the registration system.  This will allow
new compression venues to be used; for example heavier systems where the
processor is several orders of magnitude faster than disk may be able to
benefit from future LZMA compression on 64 blocks.

The {algorithm,blocksize} pair should be somehow derivable from the
accounting information to allow for algorithmic changes at runtime
including switching the algorithms used and the block size.  This would
allow for best-size-searching, where in a pinch the system can be
allowed to compress with heavier algorithms or even use multiple
algorithms to determine the best gains.

I had also considered what to do during extreme memory pressure.  My
original thoughts were to set soft and hard limits on how much memory is
used for compressed storage.  When the system encounters memory
pressure, it then attempts to compress memory and keep it in ram until
it hits the soft limit; then it starts swapping (preferably, swapping
the pages holding compressed data out).  If it reaches memory and swap
pressure (i.e. no swap file), it then begins to approach the hard limit.
 This means that if you have a 4M swap file and allow 25% soft limit and
90% hard limit, then you'll use 25% of RAM for compressed store until
the swap file fills; approach 90% of RAM holding a compressed store; and
then freak out and start OOM killing things because too much memory
pressure is happening.

At least, those are my thoughts.  How are you guys doing it?  Is there a
project page I can look into?

> 
> Mvh,
> Asbjørn Sannes
> 
> -
> 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/
> 

- --
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

    Creative brains are a valuable, limited resource. They shouldn't be
    wasted on re-inventing the wheel when there are so many fascinating
    new problems waiting out there.
                                                 -- Eric Steven Raymond

    We will enslave their women, eat their children and rape their
    cattle!
                                     -- Evil alien overlord from Blasto
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2.1 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFEBHTrhDd4aOud5P8RAupLAJ4tS3t12gGqpSzNKtrgGoVwH3dRQgCcCAbe
D+T30PxooDojPXdJzuebC9U=
=8cPZ
-----END PGP SIGNATURE-----