[lc-devel] Re: Compressed cache status

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

Hi Nitin,

On Monday 28 November 2005 18:36, Nitin Gupta wrote:
> 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).

Great that you talked to him. Is the maintaner William Irwin (wli), as in t=
he=20
maintainers file? He is very well-known in kernel world.

If huge pages are not page out, we must find out the impact on them by usin=
g a=20
portion of the memory for compressed cache. In the first implementations,=20
when I was only compressing swap pages, the impact on the other page cache=
=20
pages was severe. Also on buffers, that ended up being written much more=20
often. We must understand his implementation better to know if there is a=20
chance that we introduce a negative impact on applications that may use hug=
e=20
pages.

> 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.

Oh, I read this paper. Sometime ago, I thought about implementing it after =
Rik=20
van Riel mentioned that to me, but unfortunately things changed and I=20
couldn't spend more time on kernel development at that time.

I agree that it may help compressed cache. However, perhaps some changes to=
=20
the amount of time that an application holds the swap token may happen=20
depending on the compressed cache size and on how this value is initially=20
defined in the implementation (I didn't read the code yet).

> 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.

=46irst finish all your exams, then you will be free to work intensively :-=
)=20
Good luck with them!

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

You are now a developer in the SF project.

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

Excellent. I will try to find more about huge pages and swap token impact a=
nd=20
will let you know too.

Best Regards

> 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 we=
ek
> > 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 ve=
ry
> > 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 versi=
on
> > 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 reposito=
ry
> > 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
> > > 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 spa=
ce
> > > 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 abo=
ut
> > > 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 possibili=
ty
> > > 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 ha=
ve
> > > 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