linuxcompressed-devel — Linux Compressed Cache Development Mailing List

Re: [lc-devel] YAY!

[Bob A. <cu...@pb...>]

:) i watch you and i am excited :)

i have two laptops witn 8M ram, X and tight vncviewer, just tell me what i could test :)

On Thu, 16 Oct 2003 13:26:49 -0400 (EDT)
John R Moser <jm...@st...> wrote:

> 
> bluefox@Icechip linux-2.4.20-cc $ cat /proc/comp_cache_stat
> compressed cache - statistics
>  general
>  - (S) swap cache support enabled
>  - (P) page cache support enabled
>  - compressed swap support enabled
>  - maximum used size:   17920 KiB
>  - comp page size:         32 KiB
>  - failed allocations:    136
>  - Default algorithm:  2 (WKdm)
> 
>  algorithm WK4x4
>  - (C) compressed pages:          0  (S:   0% P:   0%)
>  - (D) decompressed pages:        0  (S:   0% P:   0%) D/C:   0%
>  - (R) read pages:                0  (S:   0% P:   0%) R/C:   0%
>  - (W) written pages:             0  (S:   0% P:   0%) W/C:   0%
>    compression ratio:             0% (S:   0% P:   0%)
>  
>  algorithm WKdm
>  - (C) compressed pages:      16130  (S:  90% P:   9%)
>  - (D) decompressed pages:     4096  (S:  93% P:   6%) D/C:  25%
>  - (R) read pages:             2624  (S:  88% P:  11%) R/C:  16%
>  - (W) written pages:          4975  (S: 100% P:   0%) W/C:  30%
>    compression ratio:            50% (S:  48% P:  74%)
>  
>  algorithm LZO
>  - (C) compressed pages:          0  (S:   0% P:   0%)
>  - (D) decompressed pages:        0  (S:   0% P:   0%) D/C:   0%
>  - (R) read pages:                0  (S:   0% P:   0%) R/C:   0%
>  - (W) written pages:             0  (S:   0% P:   0%) W/C:   0%
>    compression ratio:             0% (S:   0% P:   0%)
> bluefox@Icechip linux-2.4.20-cc $
> 
> Any questions?  I'm looking at bobandgeorge.com in firebird; compiling a 
> new kernel; running Gnome2 with a set of applets. . . xscreensavers . . . 
> it's cool.  The registration system works and everything.
> 
> A quick hack is there now (not in my running copy) to NOT load LZO if 
> it's not my default alg.  I'm shakey on its stability.  WKdm is fine.
> 
> I can't see how meta data goes to swap.  Castro, you'll have to rewrite 
> the swap meta data stuff.  Use a meta_data structure (there's one in 
> comp_cache.h) and sizeof() and stuff this time!  I don't want to have to 
> massively hack through the code to change the meta data that goes to 
> swap!
> 
> --Bluefox
> 
> 
> -------------------------------------------------------
> This SF.net email is sponsored by: SF.net Giveback Program.
> SourceForge.net hosts over 70,000 Open Source Projects.
> See the people who have HELPED US provide better services:
> Click here: http://sourceforge.net/supporters.php
> _______________________________________________
> linuxcompressed-devel mailing list
> lin...@li...
> https://lists.sourceforge.net/lists/listinfo/linuxcompressed-devel

[lc-devel] YAY!

[John R M. <jm...@st...>]

bluefox@Icechip linux-2.4.20-cc $ cat /proc/comp_cache_stat
compressed cache - statistics
 general
 - (S) swap cache support enabled
 - (P) page cache support enabled
 - compressed swap support enabled
 - maximum used size:   17920 KiB
 - comp page size:         32 KiB
 - failed allocations:    136
 - Default algorithm:  2 (WKdm)

 algorithm WK4x4
 - (C) compressed pages:          0  (S:   0% P:   0%)
 - (D) decompressed pages:        0  (S:   0% P:   0%) D/C:   0%
 - (R) read pages:                0  (S:   0% P:   0%) R/C:   0%
 - (W) written pages:             0  (S:   0% P:   0%) W/C:   0%
   compression ratio:             0% (S:   0% P:   0%)
 
 algorithm WKdm
 - (C) compressed pages:      16130  (S:  90% P:   9%)
 - (D) decompressed pages:     4096  (S:  93% P:   6%) D/C:  25%
 - (R) read pages:             2624  (S:  88% P:  11%) R/C:  16%
 - (W) written pages:          4975  (S: 100% P:   0%) W/C:  30%
   compression ratio:            50% (S:  48% P:  74%)
 
 algorithm LZO
 - (C) compressed pages:          0  (S:   0% P:   0%)
 - (D) decompressed pages:        0  (S:   0% P:   0%) D/C:   0%
 - (R) read pages:                0  (S:   0% P:   0%) R/C:   0%
 - (W) written pages:             0  (S:   0% P:   0%) W/C:   0%
   compression ratio:             0% (S:   0% P:   0%)
bluefox@Icechip linux-2.4.20-cc $

Any questions?  I'm looking at bobandgeorge.com in firebird; compiling a 
new kernel; running Gnome2 with a set of applets. . . xscreensavers . . . 
it's cool.  The registration system works and everything.

A quick hack is there now (not in my running copy) to NOT load LZO if 
it's not my default alg.  I'm shakey on its stability.  WKdm is fine.

I can't see how meta data goes to swap.  Castro, you'll have to rewrite 
the swap meta data stuff.  Use a meta_data structure (there's one in 
comp_cache.h) and sizeof() and stuff this time!  I don't want to have to 
massively hack through the code to change the meta data that goes to 
swap!

--Bluefox

Re: [lc-devel] Dump of my brain real quick

[Bob A. <cu...@pb...>]

and this is called pagecache compression ?  or you talk about something separate from this?

 
> In my opinion it's not obsolete, because we don't have to remove the
> fragment from the compresse cache and store it in the swap (regardless
> if it's in ramdisk, for example), decreasing variables that account
> for compression success. However, the current vswap code isn't very
> stable and needs improvement, so we should give a second thought if
> the effort is worth its benefit.

Re: [lc-devel] Patch is up

[Rodrigo S. de C. <rc...@im...>]

On Mon, Oct 13, 2003 at 05:28:54PM -0400, John R Moser wrote:
> Yes there's some damage :P I've a few bad hacks, the alg can't be
> changed on the fly, and DON'T use compalg= for now (I'm not sure
> about how well that really works).

That's very simple. You declare "__setup" with the command-line option
and the function which will handle it. For example,

static int __init comp_cache_size(char *str)
{
       unsigned long nr_pages;
       char * endp;

       nr_pages = memparse(str, &endp) >> (PAGE_SHIFT +
       COMP_PAGE_ORDER);

       max_num_comp_pages = nr_pages;
       return 1;
}

__setup("compsize=", comp_cache_size);

In this case, "compsize=" kernel option is setup, and
comp_cache_size() will handle it. The option passed in the
command-line is the parameter to the function.

> I'm running WKdm and there's absolutely no problems.  WKdm is my
> default alg, compiled in, and I'm limited to 128MB RAM via mem=.
> Using 16x pages.
> 
> compressed cache - statistics
>  general
>  - (S) swap cache support enabled
>  - (P) page cache support enabled
>  - compressed swap support enabled
>  - maximum used size:   10112 KiB
>  - comp page size:         64 KiB
>  - failed allocations:    298
>  algorithm WKdm
>  - (C) compressed pages:      19895  (S:  83% P:  16%)
>  - (D) decompressed pages:     6592  (S:  98% P:   1%) D/C:  33%
>  - (R) read pages:             1711  (S:  91% P:   8%) R/C:   8%
>  - (W) written pages:          9276  (S: 100% P:   0%) W/C:  46%
>    compression ratio:            52% (S:  50% P:  62%)
> 
> 
> I'm working on the patch more now, kind of hacking the algorithm
> inits out of proc.c and proc.h.  I'll upload another patch in a few
> days probably, with the registration system in there.  It's going to
> be a simple registration system.  Probably the linked list will be
> as follows:

I guess you will probably keep working on the compression algorithms,
and making them modules. That's great, let me know of your progress.

> struct comp_cache_registered
> {
> 	short	algorithm_idx;
> 	char	*name;
> 	comp_cache_init_function_t	*init;
> 	struct comp_cache_registered	*next;
> }
> 
> on initialization I'll call ->init().  These will be referenced by
> their algorithm_idx, but the sysctl to list available algs will read
> their name.  Also, the default alg will be chosen by name.

I never worked with modules, your solution and implementation for this
registration idea is what most intrigues me now :-)

> I'm also working on making it SMP safe.  Bear in mind I have NO idea
> what this really involves but I'm making it safe to run these side
> by side.  At the same time.  With both CPUs on the exact same
> instruction.  Continuously.  I have class right now so bye.

Basically, that's all about the spinlocks. They protect kernel data
and function, and must be handled carefully, since they are crucial
for making use of the second CPU on a SMP system. Spinlocks don't make
sense when you are running a non-preemptive kernel on an UP system,
since kernel code isn't never forced to relinquish CPU, except for the
most urgent interruption handling. 

I implemented a basic spinlock system in order to be stable in a
kernel with preempt patch, however the concurrency level (which is
sort of "induced") isn't so high as on a SMP system. That's why you
have to test it on a SMP system and start noticing data corruption and
all sort of damages to your system :-), trying then to check where we
have unprotected data or race conditions.

Regards,
-- 
Rodrigo

Re: [lc-devel] About 2.4.21 stability

[Rodrigo S. de C. <rc...@im...>]

Hey Ero,

On Mon, Oct 13, 2003 at 11:24:03PM +0300, Ero Carrera wrote:
> I've notice that some words have been said on stability of the cc path
> on 2.4.21. I have to say that I've been running cc on 2.4.21 in
> production use for months now with no complaints on its stability.

Thanks for you feedback! :-)

> I ported/fixed myself the patch for 2.4.19 (fixed it just so that
> issuing a patch cmd won't give any errors). That version did however
> have some 'fun' with the overcommit feature of the kernel. If a
> hungry process allocated more memory than the system could really
> provide, the whole box went down in a swap storm whenever the kernel
> figured out that it could actually not really satisfy one the memory
> writes to pages allocated but not reserved for the process (after
> all, that's the idea of overcommit).

Great to know that. That's the sort of error I first think it's caused
by CC before trying to test the stock kernel. Any news about this
problem in 2.4.22?

> One "solution" (rather, a low quality fix) was to limit the maximum
> memory per process to (in my case) 196MiB (I have more than that
> physically), with the hope that if a single process wants more than
> that, the kernel won't allocate more.  The problem would still exist
> if several applications would, simultaneously, start behaving like
> that. But is something that has just happened once under extreme
> machine load and could have been prevented with lower memory limits.
>
> I suppose, cc and overcommit don't exactly get along well, because a
> cc 'enabled' kernel will (probably) think that always has memory to
> give away (because of the compression). But this you'll know better
> than me.

We don't change how many pages the system has (in kernel point of
view), therefore it shouldn't be a problem. But that's a very simple
analysis, I am not too aware of overcommit feature.

> To fix the swap storm crashes the maximum process memory setting I
> changed was on the file "include/asm/resource.h", namely the member
> RLIMIT_AS to have a definite value, instead of RLIM_INFINITY.
> 
> I hope this info is of some use to somebody.

It's very useful, mainly when testing CC stability. Thanks.

Regards,
-- 
Rodrigo

Re: [lc-devel] Read the dates on messages.

[Rodrigo S. de C. <rc...@im...>]

On Mon, Oct 13, 2003 at 09:15:06PM -0400, John R Moser wrote:
> Erm, because of my. . . awkward . . . situation, I can't exactly send 
> replies.  I hate butchering the list and breaking the threading but I'm 
> reading mail with Mozilla Thunderbird and sending it by shelling in to 
> the server via ssh and using pine :/  College AIX box won't accept a 
> RELAY request, even with authorization ><.
> 
> Read the dates on the messages.  It seems a few of you are responding to
> my messages in reverse order.
> 
> A quick update as to how things are right now:
> 
> - There's a patch at sf.net/projects/linuxcompressed in patches.  I 
> didn't send it to the mailing list, sorry.  I should have.  I'm a
> little rough to work with since I don't always get proceedure right
> but . . .  erm.  At any rate, it's up there in the patches section.
> RC can take it down if he wants.

I checked the patches sections again, and there is not attached file,
even after logging in. Could you add the patch there or send it to the
list?

> - It works fine, just like the unmodified patch at runtime (except
> for the little sanity check I added when I was having trouble
> tracing the decompression bug).  The bug was an infinite loop I
> introduced.

How have you test stability? What sort of tests, and memory pressure
you forced to check it?

> - LZO IS HOPELESSLY BROKEN.  WKdm is fine.

That's something I am very curious, in particular. What are your
changes that might have broken LZO? It worked find since I first added
it to CC, so I guess a data structure, or a LZO-specific code path
might have been blown it up.

> - Large page sizes (16x for me) will cause a noticable lag in
> high-stress situations, particularly in the fact that spin_lock()
> may occur in 50-200 mS intervals.  I'm trying to buff out the need
> for spin_lock()'s, which will make the lag only be application lag.

Do you have a preemptible kernel? Otherwise, spin_lock()'s don't do
anything, and surely are not the performance bootleneck. How are you
measuring time spent on spinlocks?

Large contiguous pages have a horrible side-effect, which is the
failed allocation attempts. That's awful for us. And it tends to get
worse after some time because memory gets fragmented.

> I haven't confirmed that anything >double has any effect, but I'm
> going to test later with octal and quad. 

That's the same for me. The failed allocations and the inner
management (compaction) have a great cost for the benefits
provided. Another great idea to discuss and implement later consists
of having different page sizes in the CC, so we start allocating, for
example, single pages, and if we detect that the compression ratio
isn't good enough to benefit from compression, we start allocating two
contiguous pages, until we notice it's not useful any longer. (Yes, we
have to discuss it further).

> I'll reflect the results in the Configure.help.  Be aware that
> larger page sizes WILL have an effect for algorithms that are made
> for larger sets of data; my box can do gzip on 256k faster than it
> can read the data from disk, and such higher-intensity algorithms
> will have a better trade-off on higher CPU boxes.  The page size
> should be tailored for the algorithm you intend to use at compile
> time, which for the present is probably going to be WKdm with 2x-8x
> pages.

What's the compression algorithm implemented in gzip? Isn't it an
implementation of Lempel-Ziv?

> - I'm currently doing heavy rewrites of some things in here.  A few
> bad hacks are around in the patch to stave off my breakage of
> things.  They'll probably persist through the next step, but I can
> get some of the things taken care of.

Cool.

Best regards,
-- 
Rodrigo

Re: [lc-devel] Dump of my brain real quick

[Rodrigo S. de C. <rc...@im...>]

On Tue, Oct 14, 2003 at 03:07:36PM +0200, Bob Arctor wrote:
> >   o  Port it a PDA architecture and measure CC benefit on such a
> >      system. This would require improvement of virtual swap
> >      structure to make Linux to swap out pages when we don´t have
> >      swap available.
> > 
> 
> erm, isn't this obsolete?
>
> you can have swap implemented in ramdisk , swapfile on tmpfs , or
> use part of system's memory - or even other system's ram like unused
> video card ram - via mtdblock and slram. i used usused video memory
> of my laptop along with ccache, and it worked great.

In my opinion it's not obsolete, because we don't have to remove the
fragment from the compresse cache and store it in the swap (regardless
if it's in ramdisk, for example), decreasing variables that account
for compression success. However, the current vswap code isn't very
stable and needs improvement, so we should give a second thought if
the effort is worth its benefit.

Regards,
-- 
Rodrigo

Re: [lc-devel] Dump of my brain real quick

[Bob A. <cu...@pb...>]

>=20
>   o  Port it a PDA architecture and measure CC benefit on such a
>      system. This would require improvement of virtual swap structure
>      to make Linux to swap out pages when we don=B4t have swap
>      available.
>=20

erm, isn't this obsolete?
you can have swap implemented in ramdisk , swapfile on tmpfs , or use part =
of system's memory - or even other system's ram like unused video card ram =
- via mtdblock and slram. i used usused video memory of my laptop along wit=
h ccache, and it worked great.

[lc-devel] Read the dates on messages.

[John R M. <jm...@st...>]

Erm, because of my. . . awkward . . . situation, I can't exactly send 
replies.  I hate butchering the list and breaking the threading but I'm 
reading mail with Mozilla Thunderbird and sending it by shelling in to 
the server via ssh and using pine :/  College AIX box won't accept a 
RELAY request, even with authorization ><.

Read the dates on the messages.  It seems a few of you are responding to
my messages in reverse order.

A quick update as to how things are right now:

- There's a patch at sf.net/projects/linuxcompressed in patches.  I 
didn't send it to the mailing list, sorry.  I should have.  I'm a little 
rough to work with since I don't always get proceedure right but . . . 
erm.  At any rate, it's up there in the patches section.  RC can take it 
down if he wants.

- It works fine, just like the unmodified patch at runtime (except for 
the little sanity check I added when I was having trouble tracing the 
decompression bug).  The bug was an infinite loop I introduced.

- LZO IS HOPELESSLY BROKEN.  WKdm is fine.

- Large page sizes (16x for me) will cause a noticable lag in high-stress
situations, particularly in the fact that spin_lock() may occur in 50-200
mS intervals.  I'm trying to buff out the need for spin_lock()'s, which
will make the lag only be application lag.  I haven't confirmed that
anything >double has any effect, but I'm going to test later with octal
and quad.  I'll reflect the results in the Configure.help.  Be aware that
larger page sizes WILL have an effect for algorithms that are made for
larger sets of data; my box can do gzip on 256k faster than it can read
the data from disk, and such higher-intensity algorithms will have a
better trade-off on higher CPU boxes.  The page size should be tailored
for the algorithm you intend to use at compile time, which for the present
is probably going to be WKdm with 2x-8x pages

- I'm currently doing heavy rewrites of some things in here.  A few bad 
hacks are around in the patch to stave off my breakage of things.  
They'll probably persist through the next step, but I can get some of the 
things taken care of.

- other stuff I've forgotten, I'll get to it.

--Bluefox Icy

Re: [lc-devel] My progress thusfar

[Rodrigo S. de C. <rc...@im...>]

On Sat, Oct 11, 2003 at 09:16:20PM -0400, John R Moser wrote:
> Well it's certainly interesting.  I got it to do everything but it
> kinda crashes after decompressing a few pages.  It's annoying.

Well, something seems to be very broken :-)

> I'm not sure now why it's dying, because I've messed with a lot of black 
> magic doing this.  I've changed things I don't understand.  Ah well ^_^;  
> Castro, if you want this patch, wake up and e-mail me.  I probably won't 
> send anything that works right, but it *almost* works.  I'm new at this, 
> and I've done some major hacking.  I'd hope you'd at least look at
> it.

Of course I'd like to look at your patch, send it to the list.

> In its current state it should be able to run more than one alg and
> give stats about it.  If it actually runs. 

You mean, change it on-the-fly, right?

> It runs for about 6 decompresses (you can compress all you want but
> you can't decompress a lot because it blows out fast.  Fix that bug)
> or so.  In the future I want to make each alg register with the
> core, to allow for modular algorithms.

Decompression is all that matters when you are talking about
compression, because it shows if you are handling data
correctly. Probably you store (or read) wrong data when decompressing,
which blows everything. When something like that happens, it's very
likely that the compression alg complains or you get a segfault (in
particular when we decompressed swap data).

Regards,
-- 
Rodrigo

Re: [lc-devel] Re: My progress thusfar (John Moser)

[Rodrigo S. de C. <rc...@im...>]

Hey John,

On Mon, Oct 13, 2003 at 05:21:10PM -0500, john kellar wrote:
> I've been playing with some of this myself, why don't you post your
> changes as a patch to this mailing list and I will download and see
> what I can do.  I agree with you concerning the wkdm initialization
> code and have some e-mails from Scott Kaplan that may explain some
> of this. If you want I can share this with you offline or on-line if
> there is some interest on this list.

Could you share it with us?

Thanks,
-- 
Rodrigo

[lc-devel] Re: My progress thusfar (John Moser)

[john k. <kel...@ho...>]

John,
I've been playing with some of this myself, why don't you post your changes 
as a patch to this mailing list and I will download and see what I can do. I 
agree with you concerning the wkdm initialization code and have some e-mails 
from Scott Kaplan that may explain some of this. If you want I can share 
this with you offline or on-line if there is some interest on this list.
-regards,
john kellar
(kel...@ho...)

_________________________________________________________________
Concerned that messages may bounce because your Hotmail account has exceeded 
its 2MB  storage limit? Get Hotmail Extra Storage!         
http://join.msn.com/?PAGE=features/es

[lc-devel] Patch is up

[John R M. <jm...@st...>]

Yes there's some damage :P  I've a few bad hacks, the alg can't be 
changed on the fly, and DON'T use compalg= for now (I'm not sure about 
how well that really works).

I'm running WKdm and there's absolutely no problems.  WKdm is my default 
alg, compiled in, and I'm limited to 128MB RAM via mem=.  Using 16x pages.

compressed cache - statistics
 general
 - (S) swap cache support enabled
 - (P) page cache support enabled
 - compressed swap support enabled
 - maximum used size:   10112 KiB
 - comp page size:         64 KiB
 - failed allocations:    298
 algorithm WKdm
 - (C) compressed pages:      19895  (S:  83% P:  16%)
 - (D) decompressed pages:     6592  (S:  98% P:   1%) D/C:  33%
 - (R) read pages:             1711  (S:  91% P:   8%) R/C:   8%
 - (W) written pages:          9276  (S: 100% P:   0%) W/C:  46%
   compression ratio:            52% (S:  50% P:  62%)


I'm working on the patch more now, kind of hacking the algorithm inits 
out of proc.c and proc.h.  I'll upload another patch in a few days 
probably, with the registration system in there.  It's going to be a 
simple registration system.  Probably the linked list will be as follows:

struct comp_cache_registered
{
	short	algorithm_idx;
	char	*name;
	comp_cache_init_function_t	*init;
	struct comp_cache_registered	*next;
}

on initialization I'll call ->init().  These will be referenced by their 
algorithm_idx, but the sysctl to list available algs will read their 
name.  Also, the default alg will be chosen by name.

I'm also working on making it SMP safe.  Bear in mind I have NO idea what 
this really involves but I'm making it safe to run these side by side.
At the same time.  With both CPUs on the exact same instruction.  
Continuously.  I have class right now so bye.

--Bluefox Icy

[lc-devel] About 2.4.21 stability

[Ero C. <er...@dk...>]

Hi,

I've notice that some words have been said on stability of the cc path
on 2.4.21. I have to say that I've been running cc on 2.4.21 in
production use for months now with no complaints on its stability.

I ported/fixed myself the patch for 2.4.19 (fixed it just so that
issuing a patch cmd won't give any errors). That version did however
have some 'fun' with the overcommit feature of the kernel. If a hungry
process allocated more memory than the system could really provide, the
whole box went down in a swap storm whenever the kernel figured out that
it could actually not really satisfy one the memory writes to pages
allocated but not reserved for the process (after all, that's the idea
of overcommit).

One "solution" (rather, a low quality fix) was to limit the maximum
memory per process to (in my case) 196MiB (I have more than that
physically), with the hope that if a single process wants more than
that, the kernel won't allocate more.
The problem would still exist if several applications would,
simultaneously, start behaving like that. But is something that has just
happened once under extreme machine load and could have been prevented
with lower memory limits.

I suppose, cc and overcommit don't exactly get along well, because a cc
'enabled' kernel will (probably) think that always has memory to give
away (because of the compression). But this you'll know better than me.

To fix the swap storm crashes the maximum process memory setting I
changed was on the file "include/asm/resource.h", namely the member
RLIMIT_AS to have a definite value, instead of RLIM_INFINITY.

I hope this info is of some use to somebody.

Regards,

--
Ero Carrera

[lc-devel] Brain dump reply

[John R M. <jm...@st...>]

Sorry, i can't send mail from Mozilla . . . my smtp server won't take a 
relay request, so I have to use pine and shell in to the server.  Err.  
Reverse taht.  Shell, then pine.

Anyawy.

All my testing is done with me running.  That's it, no excess workloads 
or stuff.  Although on my laptop i've been testing by passing mem=64M or 
mem=128M (I have more RAM than i can use).  THE PATCH NOW WORKS!! I will 
put it in the patches section.  It's just preliminary separation and 
there's a few crappy hacks, also it seems to occasionally use a random 
algorithm index adn wind up using the compiled-in default instead of what 
compalg= was passed.  I put a simple hack around that in.  FIXME's are 
spewed right before each of these.  YOU WILL SEE IT WHEN CCACHE GETS 
COMPILED.  Guarenteed.  if you're looking at the screen you will see it.

1) 2.4.21 is a bane.  I've never got even the vanilla .21 to run for 24 hours
straight without crashing.  Ccache was no different (no less nor any more
stable).  I've always found .20 to stay up for . ..  well. . . I have to
reboot to take it down.  It won't die by itself.  My laptop is running .20
fine with ccache (WITH my hacks, which now WORK)

2)  Actually I've been using 16x (64KB) pages, and have no problems 
except when I'm under extremely heavy load.  It becomes noticable that 
the system freezes for about 50-100 mS once in a while.  I'll stay away 
from 64x (256KB) pages until I have a 10 Ghz processor ^_~  I use wkdm 
because it gets same or better than wk4x4.  LZO IS CURRENTLY 
UNSTABLE!!!!!!!!!!!!!!!  The box crashes when using LZO.  It can't 
decompress all the time.  Not something I know how to do (maybe something 
I broke, though not likely).

3)  It works.  Unfortunately, there's other bugs that cause a random alg 
to be used once in a while.  I've got bad hacks in to squelch this, and 
there's FIXME's near them, so read the warnings spewed by proc.c at 
compile itme.  Until this is fixed, I can't impliment a sysctl to change 
the alg on the fly, or safely use multiple algs at once.

4)  I've got the preliminaries set up.  It works fine, but there's a bug 
that I've mentioned a ton of times already.  Also I don't know what I'm 
doing much.  I don't know how to store the alg used in the swap page but 
it's TWO BYTES.  You can sacrifice a TWO BYTE overhead.  Yes I'm 
excessive but it's two bytes and you save more than that from the 
compression if you save any (WKDM averages 50% or more, 50% swap and 
70-80% page cache).  You'll have to clean that up behind me.

5)  I'm not implimenting this ^_^;  You can though.  I'd like to see it.

6)  I'm coming closer to that as well.  I've got the stuff divided out a 
bit and i'll put the current patch up (more to guard against a disk crash 
than to show any sort of improvement.  I've added bugs and bad hacks but 
it's stable somehow o.O).  I'm going to next work on dividing out the 
init algs for each algorithm into their source files and headers; and 
creating a registration system.  Ccache will on its own initialization 
request that these 3 default modules register themselves for now.

As for the following:

SMP
spin_lock won't halt other processors?  Hrm.  The problem I see is when 
ccache initializes an algorithm.  Separated data can be used for each 
algorithm easily.  The problem is the linked list I have in there.  
Scanning it should be safe to do twice.  Adding an algorithm to it during 
the scan would be annoying to track, however.  If I was sure that the 
only thing ever initializing algorithms was comp_cache_demand_alg_entry() 
I could probably handle it.  I'm afraid I can't secure it down to a 
single line of code though.  In any case, unless I could halt the other 
CPU from continuing while a function is in use if it calls that function, 
I can't make it perfectly secure.

What I need is a guarentee that two lines of code will be executed only 
once at the same time.  Basicly,

if (alg_registration_entry->enabled)
	return;
alg_registration_entry->enabled = 1;

If that if branches past the return, then I need it to execute the next 
line before any other CPU gets to that exact if statement.  Possibly:

static int skip_out = 0;
if (skip_out)
	return NULL;
skip_out++;
if (alg_registration_entry->enabled || skip_out > 1) {
	skip_out--;
	return NULL;
}
alg_registration_entry->enabled = 1;
<initialize the algorithm>
skip_out--;
return new_alg_entry;

The model illustrated in the above pseudocode may allow me to initialize an
algorithm (i.e.  insert it into the running algorithms list) without needing
a spin_lock and without taking the chance of having the function run twice in
parallel.  Other than that, I can probably set up the compression 
functions to be safe to run multiple times in parallel.  In the event 
that the algorithm can't be initialized (i.e. this skips out), the page 
would simply not be compressed, or would grab a random loaded alg and 
compress with that.

RMAP
UH.  I've just started hacking 2.4 code.  If you're going to go to rmap, 
try to get it stable in 2.4 first, and gimme a week or two to finish the 
modifications I'm doing on the current code.  I'll probably leave a few 
bad hacks and some dirty code around when i'm done so you'll have to 
clean up behind me, but I'll be careful not to do that too much.

PDAs
http://handhelds.org/  I use GPE.  I would love to see WKdm running on 
it, since I have no swap.




That's about it.  My next major step is to separate the init functions 
for lzo, WKdm, and WK4x4 out, set up the registration functions, and have 
ccache's init function request the default set (lzo, wkdm, wk4x4) 
register with it.  Once that's in place, I'll try to rewrite for dynamic 
data allocation and try to make it safe for SMP.  I'm swinging my fists 
blindly here though.  I'll get SOME kind of progress, but it might not go 
all the way.

--Bluefox Icy

Re: [lc-devel] WK4x4

[Rodrigo S. de C. <rc...@im...>]

On Sat, Oct 11, 2003 at 12:33:43PM -0400, John R Moser wrote:
> What the hell?
> 
> I'm trying to rewrite this code and I'm finding that the WK4x4 algorithm 
> doesn't appear to use the data structures allocated in the beginnig in 
> the comp_alg_data * data passed to wk4x4_compress/wk4x4_decompress, or in 
> ANY of the macros in wk4x4.c.  HOWEVER it does get used in wkdm.  Why not 
> NOT allocate the data for WK4x4?

Indeed, it seems to be useless to allocate data for WK4x4. I check the
code and couldn´t find a reference to "data" parameter, and also
downloaded the original WK4x4 code, getting to the same
result. Probably this "data" parameter was introduced in order to make
the interface the same as WKdm.

> I'm going to rewrite the wk4x4 alloc function to not allocate the data, 
> and move that code into the wkdm function.  That should allieviate most 
> of the issues with extremely low ram boxes running out of RAM with wk4x4,
> since the alg allocates 3.6k of RAM (think about 3 meg boxes :P).

It shouldn´t be allocate at all if it isn´t used, not matter if it´s
not that much memory :-)

> Realisticly, at this point there's no way you're running out of RAM, or else
> the box isn't going to boot anyway; But it just annoys me.
> 
> oh, proc.c is pretty much done.  I'm not so sure about the page
> stuff though.  I did modify the page structure,

What page structure? "struct comp_page" to include algorithm
information?

> but I don't know how to make it set the algorithm to -1 on page
> allocation, so when it compreses a page it'll likely either pick a
> random alg that just happens to have the same index as the garbage
> at that point, or pick the default alg.

What exactly are you trying to do? If you added a field to "struct
comp_page", and this page is allocated only when it´s about to be
compressed, you can set it to the chosen alg at that moment.

Regards,
-- 
Rodrigo

Re: [lc-devel] cc on ARM

[Rodrigo S. de C. <rc...@im...>]

Hey Artur,

I am terribly sorry for the delay, this email fell into a black hole
in my mailbox.

On Tue, Sep 02, 2003 at 05:33:05PM +0200, Artur Wisz wrote:
> we are looking for possibilities of optimizing our embedded
> linux-based system, and wondering if we can benefit from using the
> compressed cache.  We don't actually have swap disk in our system,
> but we do a lot of mmaps on a read-only slow memory medium (compact
> flash through USB). About 2/3 of the system memory is used up by our
> programs, and about 1/3 is used by the kernel cache. When the kernel
> needs more memory to satisfy user program requests, it has to remove
> some pages from the cache to free up some memory. Then when that
> data is needed again, it has to be read back from the slow medium. I
> can imagine that the kernel could compress some of the cache to free
> up the space instead of discarding it completely.  Is this what this
> implementation of the compressed cache is about? 

Exactly. We have a code which I named "virtual swap" to enable
compressed cache on swapless systems. And thanks to our page cache
support, you may benefit from compressed cache even without many swap
pages on your system (or even if you didn´t have the "virtual swap"
code).

Talking about its generic behaviour, CC will use part of your memory
to store pages in compressed format, in most cases being of great
utility to the system, which will benefit from avoiding reading these
pages from the backing store (in your case, a compact flash). We have
some policies to help us detect cases where CC is not worthless and
try to minimize its impact.

> And another question: what would be the effort to port this
> compressed cache to the ARM kernel ? We have the kernel 2.4.19.

I guess probably not very much, given that the person has an ARM box
to test it, what I don´t have currently. I may help as much as posible
someone how would like to do this port (having an ARM computer, of
course) or at least would help us testing it.

Please fell free to ask other questions, if you have.

Best regards,
-- 
Rodrigo

Re: [lc-devel] Dump of my brain real quick

[Rodrigo S. de C. <rc...@im...>]

On Fri, Oct 10, 2003 at 08:47:29PM -0400, John R Moser wrote:
> I'm very interested in this project.  Having no job and 256 MB RAM,
> running Gnome2, and a ton of crap, and having lost a 40 gig HDD
> recently, I'm kind of in need of RAM.  At any rate, here's some of
> the stuff I've been thinking:

Great, you have a great motive to help us making this project work.

> 1) I'm not getting the 2.4.20 patch from CVS to actually work right.
> X won't run (I have nvidia kernel module), although it does on
> 2.4.21 with the same setup (which I slammed the .19 patch into by
> hand).

I´ve been told of instability problems with 2.4.20. I would tell you
to try 2.4.21 if you hadn´t already done it.

How stable 2.4.21 is (when CC is enabled)? Are you testing with normal
workload or with specific tests (kernel compilation and so forth)?

> 2) I'm trying to throw in a configure option to select the default
> compression algorithm, and also trying to set up the thing to allow me to 
> select anywhere from single to 64x pages, in steps of powers of 2, for my 
> page size.  Need a working patch to test it though x.x

There is an option to select compression algorithm, but only at boot
time, as you mention below.

I am not sure a CC with 64Kb pages will turn out to have a good
performance, in particular due to fragments (compressed pages)
compaction.

> 3) I've examined the compalg= code and it looks like you actually
> have to enter the algorithm_idx number for the alg :/ I can rewrite
> that to use strcmp against "lzo", "wkdm", and "wk4x4", and go with
> the default if not.  Don't really like having to know the internals
> to use it, especially since the algorithm indexes can change for no
> apparent reason.  For example, you could add "gzip", and I'd rather
> just type "gzip" than "3".

Great idea, I would love to see it implemented.

> 4) It'd be nice to be able to enable/disable compressed page cache while 
> running, and change algorithms.  The innards would need a slight
> modification; each alg would have to be initialized upon first use,
> and each compressed fragment/page would need to have the idx of the
> algorithm it's using stored within it.  I can try to work on this
> but I can't make any guarenteed commitment to the projet.  The
> code's pretty easy to grok though.

I had this feature working a while back, and the implementation was
actually what you mentioned above. I guess I removed it due to the
swap compression, to avoid the overhead of storing the compression alg
within each swap entry. That´s what I think it would be its major
impact on the code. You can check earlier versions of the code to know
how it was implemented, and we may discuss it further.

> 5) Some form of dynamic algorithm choice should be used.  I'm lacking in 
> ideas for this.  The best I can say is the following:
> 
> - When a page is initially compressed, compress it with each algorithm 
> and compare their relative space/speed tradeoffs
> - Get the slope by 'plotting' X as time and Y as percentage saved
> - Order these slopes from greatest to least
> - Find the last slope in the set that is greater than a minimum
> - Use that algorithm initially
> - Every N compresses (make N a large number like 10240) rerun this check 
> against the block (OPTION)
> - Have N adjust for each block dynamically; make sure they're not getting 
> this check more than once within a certain time interval and if they are, 
> grow the number.  (OPTION)  Similarly, if it's getting run less than once 
> every X time intervals, shrink N.  (OPTION)

I don´t think deciding the algorithm only once is a great idea, nor
compress every page with each algorithm. However, doing this analysis
every N compresses (or time interval) is really great, and that´s
exactly I though when you mentioned the first item. :-) In my opinion,
it is worth implementing it.

> 6) Splitting out ccache's algs into modules would be nice.  Particularly, 
> the modules should be rewritten as library functions (like zlib is),
> and ccache should access those.  That way other compression modules
> can be added dynamically.  The ccache dynalg module described in #5
> should be compiled as a module too to facilitate fast testing of new
> algs.

Indeed that should be tried. We could design a way for modules to
registers themselves in the CC, then you can load up as many modules
as you want, and CC wouldn´t have to be aware of them, as long as they
implemented an API. That would be perfect, but it would require quite
a work. Some compression algorithms would have to be rewritten to
avoid depending on some data passed as parameters, and so forth, ie,
make them compliant to a common compression interface for kernel
pages.

> Well that's about it for me.

Some major changes to add to this list:

- Make it SMP-safe

  o You mention something related to the spinlocks in a later email,
    so you probably gave a thought about it. In order to have any
    chance to be more widespread, we must improve its code to be
    SMP-safe in order to make use of higher CPU power SMP systems do
    have.

- Port it to rmap, preferably 2.6

  o  I am not sure it is so hard to do. I had a brief look at 2.6 code
     and I guess we may be able to do that. The challenge here is to
     make use of rmap in order to gather process information and use
     this information to improve CC behaviour.

- PDAs

  o  Port it a PDA architecture and measure CC benefit on such a
     system. This would require improvement of virtual swap structure
     to make Linux to swap out pages when we don´t have swap
     available.


Best regards,
-- 
Rodrigo

[lc-devel] spin_lock() evasion

[John R M. <jm...@st...>]

I'm still wrestling with instability.  I'm pondering trying to remove the 
need for so many spinlocks later (particularly, during compression and 
decompression) by marking algorithms' data as "in use" and attempting to 
allow multiple pages to be compressed/decompressed in parallel.  Here's a 
basic flow:

- Enter compress/decompress function
- Find algorithm entry
- Initialize a data for the algoritm
- compress/decompress the page or fragment
- free the data for the algorithm
- leave the compress/decompress function

This would further be aided by limiting how many data can be allocated at 
one time and queing all requests.  Another method would be to start 
queing requests when available RAM gets too low.

The problem here is that a series of interrupts may cause the retrieval 
of a page to be delayed, or may cause a series of calls to 
decompress/compress pages.  The code can be made to do it and the 
spin_lock()s can be inside an #ifndef though.  It'd be pretty simple to 
code (once the code is actually working the way it is), as would be 
dynamic data allocation.  However, with the static data allocation, 
you're guarenteed the memory needed to decompress/compress a page.

If someone could explain to me why a lot of stuff is where it is it'd be 
helpful :P



By the way, WK4x4 seems to run fine without the initialized data.  At 
least, it runs as fine as it can.  WKdm runs great, but it gets the WK 
data initialization.

--Bluefox Icy

[lc-devel] My progress thusfar

[John R M. <jm...@st...>]

Well it's certainly interesting.  I got it to do everything but it kinda 
crashes after decompressing a few pages.  It's annoying.

I'm not sure now why it's dying, because I've messed with a lot of black 
magic doing this.  I've changed things I don't understand.  Ah well ^_^;  
Castro, if you want this patch, wake up and e-mail me.  I probably won't 
send anything that works right, but it *almost* works.  I'm new at this, 
and I've done some major hacking.  I'd hope you'd at least look at it.

In its current state it should be able to run more than one alg and give
stats about it.  If it actually runs.  It runs for about 6 decompresses
(you can compress all you want but you can't decompress a lot because it
blows out fast.  Fix that bug) or so.  In the future I want to make each
alg register with the core, to allow for modular algorithms.

--Bluefox Icy

[lc-devel] WK4x4

[John R M. <jm...@st...>]

What the hell?

I'm trying to rewrite this code and I'm finding that the WK4x4 algorithm 
doesn't appear to use the data structures allocated in the beginnig in 
the comp_alg_data * data passed to wk4x4_compress/wk4x4_decompress, or in 
ANY of the macros in wk4x4.c.  HOWEVER it does get used in wkdm.  Why not 
NOT allocate the data for WK4x4?

I'm going to rewrite the wk4x4 alloc function to not allocate the data, 
and move that code into the wkdm function.  That should allieviate most 
of the issues with extremely low ram boxes running out of RAM with wk4x4,
since the alg allocates 3.6k of RAM (think about 3 meg boxes :P).

Realisticly, at this point there's no way you're running out of RAM, or else
the box isn't going to boot anyway; But it just annoys me.

oh, proc.c is pretty much done.  I'm not so sure about the page stuff 
though.  I did modify the page structure, but I don't know how to make it 
set the algorithm to -1 on page allocation, so when it compreses a page 
it'll likely either pick a random alg that just happens to have the same 
index as the garbage at that point, or pick the default alg.

-- Bluefox Phoenix Lucid

[lc-devel] Dump of my brain real quick

[John R M. <jm...@st...>]

I'm very interested in this project.  Having no job and 256 MB RAM,
running Gnome2, and a ton of crap, and having lost a 40 gig HDD recently,
I'm kind of in need of RAM.  At any rate, here's some of the stuff I've 
been thinking:

1) I'm not getting the 2.4.20 patch from CVS to actually work right.  X
won't run (I have nvidia kernel module), although it does on 2.4.21 with
the same setup (which I slammed the .19 patch into by hand).

2) I'm trying to throw in a configure option to select the default
compression algorithm, and also trying to set up the thing to allow me to 
select anywhere from single to 64x pages, in steps of powers of 2, for my 
page size.  Need a working patch to test it though x.x

3) I've examined the compalg= code and it looks like you actually have to 
enter the algorithm_idx number for the alg :/  I can rewrite that to use 
strcmp against "lzo", "wkdm", and "wk4x4", and go with the default if 
not.  Don't really like having to know the internals to use it, 
especially since the algorithm indexes can change for no apparent 
reason.  For example, you could add "gzip", and I'd rather just type 
"gzip" than "3".

4) It'd be nice to be able to enable/disable compressed page cache while 
running, and change algorithms.  The innards would need a slight 
modification; each alg would have to be initialized upon first use, and 
each compressed fragment/page would need to have the idx of the algorithm 
it's using stored within it.  I can try to work on this but I can't make 
any guarenteed commitment to the projet.  The code's pretty easy to grok 
though.

5) Some form of dynamic algorithm choice should be used.  I'm lacking in 
ideas for this.  The best I can say is the following:

- When a page is initially compressed, compress it with each algorithm 
and compare their relative space/speed tradeoffs
- Get the slope by 'plotting' X as time and Y as percentage saved
- Order these slopes from greatest to least
- Find the last slope in the set that is greater than a minimum
- Use that algorithm initially
- Every N compresses (make N a large number like 10240) rerun this check 
against the block (OPTION)
- Have N adjust for each block dynamically; make sure they're not getting 
this check more than once within a certain time interval and if they are, 
grow the number.  (OPTION)  Similarly, if it's getting run less than once 
every X time intervals, shrink N.  (OPTION)

6) Splitting out ccache's algs into modules would be nice.  Particularly, 
the modules should be rewritten as library functions (like zlib is), and 
ccache should access those.  That way other compression modules can be 
added dynamically.  The ccache dynalg module described in #5 should be 
compiled as a module too to facilitate fast testing of new algs.

Well that's about it for me.

--Bluefox Phoenix Lucid

[lc-devel] cc on ARM

[Artur W. <wi...@th...>]

Hello,
we are looking for possibilities of optimizing our embedded linux-based 
system, and wondering if we can benefit from using the compressed cache.
We don't actually have swap disk in our system, but we do a lot of mmaps 
on a read-only slow memory medium (compact flash through USB). About 2/3 
of the system memory is used up by our programs, and about 1/3 is used 
by the kernel cache. When the kernel needs more memory to satisfy user 
program requests, it has to remove some pages from the cache to free up 
some memory. Then when that data is needed again, it has to be read back 
from the slow medium. I can imagine that the kernel could compress some 
of the cache to free up the space instead of discarding it completely. 
Is this what this implementation of the compressed cache is about ?
And another question: what would be the effort to port this compressed 
cache to the ARM kernel ? We have the kernel 2.4.19.
Thanks for any help,

Artur Wisz

[lc-devel] 2.4.22rc1 patch

[Bob A. <cu...@pb...>]

sorry, you sent me 2.4.20 patch once... i now have pcmcia network card in my 
laptop, which i forgot to compile in last time, and i have to recompile my 
kernel... i use 2.4.21-openmosix , but it is lot slower for what i need 
(simple thin ssh encrypted vnc client), and swaps a lot... 

i lost your patch because i had disk crash in meanwhile :/ could you send me 
this patch again please?


-- 

Re: [lc-devel] question

[Rodrigo S. de C. <rc...@im...>]

Hi Murali,

Sorry for the delay.

On Mon, Jul 28, 2003 at 10:44:36PM -0400, Murali Vilayannur N wrote:
> Is this a typo in the statistics accounting initialization?
> 
> memset((void *) &compression_algorithm, 0, sizeof(struct stats_summary));
> 
> Should n't it be either
> 
> a) memset((void *) &compression_algorithm.stats, 0, sizeof(struct 
> stats_summary));
> (OR)
> b) memset((void *) &compression_algorithm, 0, sizeof(struct
>    comp_alg));

You are absolutely correct, the above memset wouldn't initialize all
the compression_algorithm structure, since "struct stats_summary" is
only part of it.

> In any case, isn't the memset redundant (since compression algorithm
> is defined as a global variable)?

Agreed, it is a redundant initialization. This code will be removed.

Thanks a lot for your attention and for reporting this bug.

Best regards,
-- 
Rodrigo