[lc-devel] RE: Compressed cache status

[Rodrigo S de C. <ro...@te...>]

Hi Nitin,

As I mentioned, there is a possibility that I return to compressed cache
development. In the next two or three weeks I will have a decision about
this.

Concerning compressed cache structure, the fragmentation is in the cells (ie
contiguous pages), and some metadata keep track of the fragmented space in
the cell. Of course there is a small memory space overhead to keep this data
and a performance penalty, but it is negligible given the benefit we have
(some benchmark results would back this statement). What is interesting in
this metadata is that we don't have much overhead with the fragmentation and
the compaction. If it is worth to compact a cell rather than allocate a new
one or evict a compressed page, we do it after a quick hash table lookup.
Moving data is expensive, but it is less expensive than eviction or a new
page allocation (remember we are always under memory pressure).

In case of too much fragmentation in the compressed cache (and we don't have
any single cell whose compaction would result in enough free space), a
scheme to perform compaction moving compressed pages from a cell to another
could improve a lot the allocated memory space, but I am not sure the cost
would be affordable. Moreover, I am not sure this is a common case, anyway,
but it is very simple to keep track of the overall free space to have a
feeling of it after some tests.

Your ideas for the use of compressed cache are very interesting. I would say
that its usage in PDA/Cell phones is also something that may be interesting
(even though, in this case, performance improvement may not be the primary
goal).

I went through the 2.6 memory code recently, but very briefly. I had the
impression that it does not have substantial changes in the eviction path,
except the inclusion of rmap. We could figure out how knowing the processing
mapping a page could help us. Another research topic would be checking
kVMTrace developed by Scott Kaplan. Maybe it could help us improving the
heuristic to avoid maladaptivity, but still I don't know much about it to
advance our discussion at this moment.

As a general guideline, I would suggest that you take into consideration the
design decisions I took in this work. They are very important and are all
the lessons I learned during the implementation and my research:

- Cells composed of 2 contiguous pages
- Page cache (not only swap cache)
- Heuristic to try to disable compressed cache when it is not useful
- Virtual swap address
- Page order
- Possibility of swap compression
- Idea behind profit and cost lists in the heuristic
- Scheduling impact
- Buffer/IO operations impact
- Adjustment of Linux watermarks

Having all these points in mind will let us to start a port or new
implementation far ahead. In summary, the main lesson is that the system is
very much sensitive to any changes in it (mainly reduction of memory for
other caches).

Let's keep in touch. As soon as I have a decision about the possibility of
working with you on this, I will let you know.

Best regards,

Rodrigo

-----Original Message-----
From: Nitin Gupta [mailto:nit...@gm...] 
Sent: quarta-feira, 16 de novembro de 2005 12:47
To: ro...@te...
Cc: lin...@li...
Subject: Compressed cache status

Hi Rodrigo,

    It was great to see your reply!
    I've been working on compressed cache port to 2.6 for about 2
months whenever I can take out the time. Currently not a single line
of code has been written. Since I was new to VMM subsystem, the
initial study took too much time. The details seemed overwhelming but
after a lot of work the picture is much clearer now.
    So, the current status is that I have read a lot on VMM and your
paper on adaptive compressed caching. Now, I'm looking for the most
recent changes in kernel that can help compressed cache design.
    Since, I've done some kernel patches (for CIFS vfs) before, which
involved lot of concurrency issues, I have a general feel of kernel
programming. So, I think once a complete "roadmap" is prepared, work
can really speed up.

    So, before I go hunting for the right kernel hooks, I wanted to
have following on paper:

- Compressed cache structure - currently the cell based design (2-4
pages taken as unit) has problem of fragmentation and relies on
compaction as last resort to free-up memory before starting to
swap-out to disks. Although, fragmentation cannot be eliminated but I
think a different design (for which I am looking for) can surely
reduce it.
	Also, it needs to be addressable storage (kernel asks for page in
swap at xxxxx where is this in compressed cache?). Although you have
implemented this but I couldn't get it.

- Adaptivity heuristic - I've read your current heuristic method but
as you mentioned that rmap and other recent developments in 2.6 can be
really helpful here. So, I'm now reading more on recent developments.
Heuristic quality will be very significant and can determine success
of this work. As you have shown setting up just the right static cache
size for a particular workload is so good for performance while the
wrong choice produces significant slowdown.

- Compression algorithm - these can simply be reused from your
implementation.

With these in hand, I can then proceed with implementation: find the
right kernel hooks, implement a "dummy" compressed cache (not really
do anything but just to make sure I've the right entry points), and
then gradually implement all the parts (from static to dynamic cache).

Also, I'm particularly looking forward to its use in:
- LiveCD environment - swap in not available and CD-ROM read speed is
exceptionally slow.
- Virtualized environment - hard-disk is a file backed on host OS. So,
RAM and disc speed gap is even greater here (many more +ve factors
here).

In general i'm not very busy and can spare a lot of time for this
work. But, unfortunately my semester exams are due to start early
december and last for about 3 weeks. However, I'm extremely interested
in this project and it would be great if I can get your help.


Best regards,

Nitin