[lc-devel] RE: Compressed cache status

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

Hi Nitin,

I am very sorry for the delay. I had restricted internet access this =
week
and couldn't answer your email earlier.

If we are going to do a new implementation, I agree with the static
compressed cache approach. This was the first step of the current 2.4
implementation and I think it was very useful. Actually, even if we were =
to
port the current code, I think that disabling adaptivity would be very
useful to make it work stably initially and then we add and improve the
adaptivity heuristic.

Concerning the kernel version, I would go with the latest vanilla =
version
and would update for every release, since I don't think that it would =
have
many differences in -ac/-mm branches that could justify the effort of
keeping updated with them. In the past, during 2.4 version =
implementation,
we achieved a point that some people asked to keep updated with -ac =
branch,
but it was already somewhat stable and people were using it. Therefore, =
I
think your approach would work.

This week I discussed a little bit about compressed cache in Linux 2.6 =
and
there is something that we must think when implementing this new =
version. In
2.6 there is support for huge pages (4Mb pages instead of 4Kb, at least =
on
i386). We didn't have that in 2.4 and we must devise a way to handle =
them.

Finally, great to hear about taking compressed cache as your final
university project. I really hope we can work together on this.

PS: Tell me your sourceforge user so I can add as a developer in the =
project
if you are about to start coding. Let's manage the CVS repository with
directories or branches for each implementation (2.4/2.6).

Best regards,

Rodrigo

-----Original Message-----
From: Nitin Gupta [mailto:nit...@gm...]=20
Sent: ter=E7a-feira, 22 de novembro de 2005 08:36
To: Rodrigo S de Castro
Cc: lin...@li...
Subject: Re: Compressed cache status

Hi Rodrigo,

I think the coding can now start from next week.

For the compressed structure, I think the 2-page cell structure would
be best as you have done a lot of research here and my guess-work will
not help here.

For the implementation, I think first getting static compressed cache
implemented for 2.6 kernel would be very useful. I think, by actually
working on VM code will give us a clear understanding of all the
relevant recent kernel changes. Although you have a lot of experience
working on VM code but for me, it would be very difficult to
practically come-up with a good heuristic now and go on with
implementing a dynamic compressed cache. Also, this will allow us to
parallelize the work on heuristic without delaying the work.

Also, I think working on a new implementation instead of just trying
to port your previous work would be better since older bugs may become
very hard to trace down and this will also give more flexibility in
implementation.

To start with the implementation should we start with the latest
vanilla kernel or -ac/-mm?
In my previous work I went with the latest vanilla and updated it
(about) every 3 weeks to keep the work current. Do you think this
approach will work here?

I have also taken-up this as my final year university project and as
an entry for a competition sponsored by Red Hat
(http://ekalavya.iitb.ac.in/rhs/ - Group RHS051032). So, it will be
great to have you as mentor!


Best Regards,

Nitin



On 11/20/05, Rodrigo S de Castro <ro...@te...> wrote:
> 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
>
>
>
>