linuxcompressed-devel

[lc-devel] Compressed cache status

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

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.
=09Also, 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 implementati=
on.

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

[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

[lc-devel] Re: Compressed cache status

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

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 i=
n
> the cell. Of course there is a small memory space overhead to keep this d=
ata
> and a performance penalty, but it is negligible given the benefit we have
> (some benchmark results would back this statement). What is interesting i=
n
> 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 n=
ew
> 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 h=
ave
> any single cell whose compaction would result in enough free space), a
> scheme to perform compaction moving compressed pages from a cell to anoth=
er
> could improve a lot the allocated memory space, but I am not sure the cos=
t
> would be affordable. Moreover, I am not sure this is a common case, anywa=
y,
> 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 interesti=
ng
> (even though, in this case, performance improvement may not be the primar=
y
> 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 process=
ing
> 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 o=
f
> 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
>
>
>
>

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

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

[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

[lc-devel] Compressed cache and large pages

[Dilma D. <di...@wa...>]

In my opinion, the implementation for proper support of large pages
(in Linux and other operating systems) is in its infancy; in order to
allow applications to really take advantage of large pages (e.g. the
reduced number TLB entries) the support in Linux will have to advance
(and in my opinion it will, as developers see the need for it). I
think it makes sense to take large pages into consideration as the
design for compressed caches is revisited now; I don't suggest to
address it on an implementation now, but to think about it enough so
that the many issues (such as the relevance of memory fragmentation,
the potential need to promote and demote memory areas from/to
large/small pages) can be worked out later if needed.

dilma

[lc-devel] Re: Compressed cache status

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

Hi Rodrigo,

As mail from Dilma DaSilva suggests, the huge pages support can
undergo many changes in (near) future. So, apart from studying impact
of compressed cache on applications using huge pages, we should also
work out cache structure for actually storing these 4M pages. Although
we may not implement it now but it will be useful to have a way to
handle them without affecting existing cell structure too much so that
it is easier to incorporate it later if need be.

Before I talked to wli (yes, he was William Irwin (wli), as in the
maintainers file :) ), I thought of a simple way of handling 4M pages:

Simply store them separately and also maintain the corresponding
metadata separately. When a huge page comes to be swapped out,
compress it page-by-page, allocating no. of single (4K) pages as
required. When another huge page comes, start by allocating a new page
and do not touch space left over from storing previous huge page i.e.
let the space in last page be wasted (I think, this will not be that
costly and will greatly simplify design).
When a huge page is to be taken out, simple decompress it and free the
associated pages in compressed cache.

One immediate problem I could see here is that while compressing huge
page, pages have to be allocated on-demand. If a huge page is being
swapped out, the system must be really tight on memory and while it is
not completely compressed it just cannot be freed. But once it is
completely compressed system will not only gain with saved space but
also from larger contiguous space availability. This "design" also
eliminates need for compaction and is completely separated from cache
for normal 4K pages.

This is just an initial idea. I haven't though it out in detail but
just wanted to tell you this before I go invisible for few weeks :)

Best Regards,

Nitin


On 11/30/05, Rodrigo S de Castro <ro...@te...> wrote:
> 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=
 the
> 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 us=
ing a
> portion of the memory for compressed cache. In the first implementations,
> when I was only compressing swap pages, the impact on the other page cach=
e
> pages was severe. Also on buffers, that ended up being written much more
> often. We must understand his implementation better to know if there is a
> chance that we introduce a negative impact on applications that may use h=
uge
> 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 afte=
r Rik
> van Riel mentioned that to me, but unfortunately things changed and I
> couldn't spend more time on kernel development at that time.
>
> I agree that it may help compressed cache. However, perhaps some changes =
to
> the amount of time that an application holds the swap token may happen
> depending on the compressed cache size and on how this value is initially
> 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.
>
> First finish all your exams, then you will be free to work intensively :-=
)
> 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=
 and
> 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 =
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 w=
ere
> > > 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 t=
he
> > > adaptivity heuristic.
> > >
> > > Concerning the kernel version, I would go with the latest vanilla ver=
sion
> > > 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 effo=
rt
> > > 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 peopl=
e
> > > 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 reposi=
tory
> > > 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 wil=
l
> > > 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 becom=
e
> > > 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 s=
pace
> > > > in the cell. Of course there is a small memory space overhead to ke=
ep
> > > > this
> > >
> > > data
> > >
> > > > and a performance penalty, but it is negligible given the benefit w=
e
> > > > have (some benchmark results would back this statement). What is
> > > > interesting in this metadata is that we don't have much overhead wi=
th
> > > > the fragmentation
> > >
> > > and
> > >
> > > > the compaction. If it is worth to compact a cell rather than alloca=
te 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 mem=
ory
> > > > pressure).
> > > >
> > > > In case of too much fragmentation in the compressed cache (and we d=
on'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 t=
he
> > > > 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 ha=
ve 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 ha=
d
> > > > the impression that it does not have substantial changes in the
> > > > eviction path, except the inclusion of rmap. We could figure out ho=
w
> > > > knowing the
> > >
> > > processing
> > >
> > > > mapping a page could help us. Another research topic would be check=
ing
> > > > kVMTrace developed by Scott Kaplan. Maybe it could help us improvin=
g
> > > > the heuristic to avoid maladaptivity, but still I don't know much a=
bout
> > > > 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 a=
re
> > > > 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 usefu=
l
> > > > - 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 memor=
y
> > > > for other caches).
> > > >
> > > > Let's keep in touch. As soon as I have a decision about the possibi=
lity
> > > > 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 lin=
e
> > > > of code has been written. Since I was new to VMM subsystem, the
> > > > initial study took too much time. The details seemed overwhelming b=
ut
> > > > 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 you=
r
> > > > 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, whi=
ch
> > > > involved lot of concurrency issues, I have a general feel of kernel
> > > > programming. So, I think once a complete "roadmap" is prepared, wor=
k
> > > > 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 p=
age
> > > > 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 bu=
t
> > > > 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 development=
s.
> > > > Heuristic quality will be very significant and can determine succes=
s
> > > > of this work. As you have shown setting up just the right static ca=
che
> > > > 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 th=
e
> > > > right kernel hooks, implement a "dummy" compressed cache (not reall=
y
> > > > do anything but just to make sure I've the right entry points), and
> > > > then gradually implement all the parts (from static to dynamic cach=
e).
> > > >
> > > > 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 interes=
ted
> > > > in this project and it would be great if I can get your help.
> > > >
> > > >
> > > > Best regards,
> > > >
> > > > Nitin
>
>