[linux-mm-cc] Hi All

[Nitin Gupta]

Hi All,


On 9/14/07, Anderson Briglia <anderson.briglia at indt.org.br> wrote:
>
> Hi all,
>
> ext Sanket Somnath Hase wrote:
> > Hi All,
> >
> > We are graduate students at Carnegie Mellon University. We are enrolled
> in a course (Operating systems practicum http://www.cs.cmu.edu/~412/ )
> which involves hands-on experience with operating-system code as it is
> developed and deployed in the real world.
> >
> > We are interested in contributing to project :Compressed caching on
> Linux
> >
> > We have already taken an operating system design and implementation
> class
> > (http://www.cs.cmu.edu/~410/ ) before where we developed a UNIX like
> kernel from scratch. We have fair experience in reading-coding-debugging
> kernel code. All three of us interned at core systems group at companies
> like Google and Oracle in the past summer.
> >
> > Our team can invest 50 hours per week, for a period of 13 weeks of this
> Fall
> > semester. Nitin has already given us some pointers towards current to-do
> list.
> >
> > We are interested in knowing the current stage of the project. Could you
> refer us to the latest documentation and/or code-base of the project?
> Anything else which you think we should look at ?
>
> I suspect that you can get this information from Nitin. Actually, I
> believe we need more tests on latest Ikeda's patches
> which implemented a shrink operation to CCache. You can find this mail
> thread here:
> http://lists.laptop.org/pipermail/linux-mm-cc/2007-July/000165.html


There are few reasons why I am not very much willing to extend/improve
existing 2.6.x patches:

1) Existing approach has big metadata overhead. Ikeda's patches increases it
further (though, I think, it was necessary for his dynamic ccache resizing
work).
2)  It compresses both page-cache and swap-cache pages. Anderson and co.
have shown in paper (link below) that for embedded devices only swap-cache
pages need to be compressed. This can result in significant simplifications
in existing code. Also, I think ccahing is mainly useful for embedded
devices only and not much for desktop/server systems.
3) Its storage structure for compressed pages has some problems (large
metada, poor locality for compressed data chunks, etc.)
4) It decompresses page in context where we cannot sleep in general (like in
find_get_page() and friends). This is a serious drawback since we need to
allocate some temporary memory in decompression path also which we cannot
allow to sleep and thus has very high chances of failing - If decompression
path fails, we loose data and what not!

That's why I was working on new design that will at least solve all above
problems and might also result in much simplified code.
Also, I was looking for an approach that does not require any kernel
patching - everything should be done as external kernel modules. This will
make it more likely for this work to get included in mainline. Existing
patches for 2.6.x are very intrusive.

So, my new plan is:
1) Implement new allocator "VStore": this will have no ccache specific
knowledge - it will be a separate kernel module.
2) De/compression algos: LZO is in mainline - just use that since it is
tested on nearly all Linux supported archs, its fast and has good code
quality. Drop support for WKdm, WK4x4 algos till we can get them to mainline
too.
3) With (1) and (2) in hand, all work is now ccache specific logic which
includes:
    a) Implement a pseudo block device which will act as swap device for
ccache.
    b) LRU like eviction scheme from ccache in case it reaches its size
limit or out heurstic suggests compression is hurting system or we are out
of memory - this I thought can be done by storing {ObjectID, mapping} for
all compressed pages in LRU like fashion (ObjectIDs are from VStore when you
store a compressed page).
    c) Heuristic to determine if compressing pages is hurting perf. - we can
take this from Rodrigo's work. (In cases of swapless systems, this part is
not necessary since we plan to compress anon pages only).

I tried developing experimental code for 3(a) but could not stabilize that.
Also had problems handing curious cases like user trying to create
partitions on this pseudo block devices. This approach also looks a bit
inefficient since lot of unnecessary I/O sched code is executed - this can
be painful for speed as well as energy use on embedded systems.
So, if 3(a) turns out to be bad, we have to go with approach that involves
kernel patches --- while making sure we don't re-introduce problem (4) in
de/compression paths.


I've worked with CCache focused on embedded devices, mainly Nokia devices:
> N770 and N800. I did a presentation at Linux
> Symposium 2007, you can find the article here:
> https://ols2006.108.redhat.com/2007/Reprints/briglia-Reprint.pdf
>
> I did not have time to continue this work after OLS, but I'll continue
> this month yet, since it's part of my Master's
> course. :)
>
> Nitin, do you have any news about that CCache allocator?


see http://linux-mm.org/VStore - I have not yet started its implementation.
Though in initial fits of excitement I did open a separate project page for
this :)   http://code.google.com/p/vstore2



Cheers,
Nitin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.laptop.org/pipermail/linux-mm-cc/attachments/20070914/00015439/attachment.htm