[lc-devel] Re: Compressed cache status

[Nitin G. <nit...@gm...>]

Hi Rodrigo,
We need not think about handling 4M pages. I fortunately had a talk
with HugeTLB Filesystem maintainer himself at #kernelnewbies! This is
what he told: Huge pages are never paged out. They are just paged in
on demand (lazy mmap()'ing).

Also, 2.6 kernels have a thrashing protection algorithm implemented
(mm/thrash.c) (based on http://www.cs.wm.edu/~sjiang/token.pdf). This
should significantly improve compressed cache performance as it will
reduce no. of "false LRU pages" (as paper calls them) reaching
compressed cache and hence lesser no. of unnecessary
compression/decompressions.

Just when everything was ready - latest vanilla kernel with all
debugging turned on, my End-Term exams have struck. They are now
dangerously close (3 Dec). So, I am sorry to tell you that I may not
be able to work on it till 25 Dec.

So, I think CVS branch can then be started for real work :)
(my sf user: nitin_sf)

Anyway, I will try reading more of existing code and keep up with
relevant kernel updates and keep you informed.


Best Regards,

Nitin


On 11/27/05, Rodrigo S de Castro <ro...@te...> wrote:
> 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 hav=
e
> 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 branc=
h,
> 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 an=
d
> 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 o=
n
> 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 proj=
ect
> 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...]
> 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 cach=
e
> > development. In the next two or three weeks I will have a decision abou=
t
> > this.
> >
> > Concerning compressed cache structure, the fragmentation is in the cell=
s
> (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 ha=
ve
> > (some benchmark results would back this statement). What is interesting=
 in
> > this metadata is that we don't have much overhead with the fragmentatio=
n
> 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 looku=
p.
> > Moving data is expensive, but it is less expensive than eviction or a n=
ew
> > 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 c=
ost
> > 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 woul=
d
> 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 prim=
ary
> > goal).
> >
> > I went through the 2.6 memory code recently, but very briefly. I had th=
e
> > impression that it does not have substantial changes in the eviction pa=
th,
> > 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 th=
e
> > 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 consideratio=
n
> the
> > design decisions I took in this work. They are very important and are a=
ll
> > 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 syste=
m
> is
> > very much sensitive to any changes in it (mainly reduction of memory fo=
r
> > 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
> >
> >
> >
> >
>
>
>
>