compressed caching
linux virtual memory


standard and new memory hierarchy

Compressed caching is the introduction of a new level into the virtual memory hierarchy. Specifically, RAM is used to store both an uncompressed cache of pages in their 'natural' encoding, and a compressed cache of pages in some compressed format. By using RAM to store some number of compressed pages, the effective size of RAM is increased, and so the number of page faults that must be serviced by very slow hard disks is decreased. Our aim is to improve system performance. When that is not possible, our goal is to introduce none (or a minimum overhead) when compressed caching is enabled in the system.

Born as an undergraduate research project, it is now being developed mainly by Rodrigo S. de Castro (rcastro at ime.usp.br). It was part of his master's thesis (soon avaliable) at Universidade de São Paulo (University of Sao Paulo, or USP), under the supervision of Alair Pereira do Lago, PhD, Professor at USP, Dilma Menezes da Silva, PhD, Researcher at IBM TJ Watson Research Center and Fábio Kon, PhD, also Professor at USP. Until March 2003, this research was supported by FAPESP (under contract 01/01432-4) and CNPq (under contract 465901, headed by Prof. Imre Simon, PhD). Currently, it is done mostly in Rodrigo's spare time.

The main goal was, based on prelimary studies by Scott F. Kaplan (see our references section), to implement this compressed caching in Linux 2.4. This step has been successfully accomplished and now we aim to improve its performance and implement it into Linux 2.5/2.6.

Compressed cache patch has already been included into: kernel patchset by Con Kolivas and WOLK project by Marc-Christian Petersen. It has been tested on preempted kernels. Although the infrastructure for SMP systems is implemented, it was never tested and we assume it is not safe. Moreover, our development architecture is i386, so we are unable to tell whether it works on other architectures or not (in spite of that it does not have much arch-dependent code).

Thanks for your interest in compressed caching implementation. In case you want more information, have any troubles or suggestion, or even want to join us in this effort, get in touch.


News

you can also check Rodrigo's diary

(Jun 10th 2003) New statistics

New performance statistics are available, namely:

Soon I will add some info about problems with Sort, PostMark and Contest that made us implement some features like clean page suspension, or even made us realize that there were some scheduling effect when using compressed caching.

(Jun 08th 2003) Dissertation defense

The defense of the master's dissertation on compressed caching took place on Jun 06th at Jacy Monteiro Amphitheater of University of Sao Paulo, at 2PM BRT. The audience wasn't very large, but it was composed of high quality people :-). I guess the presentation was pretty fine, but it took a little longer than I expected. The questions about the project were clever, but no surprise. All the committee members liked the dissertation and my master was approved. After the defense, some close friends and I celebrated it going to a pizzeria, where we ate a lot. Now I have to fix some mistakes and check some suggestions in order to deliver the final version of my text.

(May 05th 2003) Project is alive and moves on.

Much water has passed under the bridge since our laste news about the project. I couldn't work on the project for a long time due to my dissertation and two papers that I wrote about this project. Nevertheless, the project is still alive and I want to keep working on it, since I do have some ideas that may be implemented, now that I finally finished writing my master's dissertation. I also think porting it to 2.5/2.6 will be really cool. However, the only difference is that, from now on, I will not be working on it full-time, since my scholarship is over and I got a job. Anyway, if you want to help out in some way, feel free to drop me a note.

(Nov 22th 2002) Patch 2.4.1{8,9}-0.24pre5 (news)

Finally a new patch is out for both 2.4.18 and 2.4.19 kernels. This patch features the clean page adaptability, which disables clean page compression when necessary. It also has some bug fixes and cleanups, as always.

(Sep 14th 2002) Home Page Updated (news)

Finally the home page was updated. Now the directions to install the compressed cache patch matches the options available in the last version. Cache design section has been marked as outdated (and the excerpt on the home page removed). There are links to the patchset that include compressed cache.


Docs


How to apply the Patches

All the patches released may not be suitable for use on a production box. Use at your own risk.

Compressed Cache Patches are done for the newest versions of Linux Kernel development tree. Currently, we have patches for 2.4.X and for 2.4.X-acY versions of Linux Kernel.


Resources

Cache Design (outdated)

Mailing Lists

IRC: Join #linux-mm-cc channel on irc.oftc.net to discuss about the project.

Patches

CVS Repository

ToDo List

Compression Statistics


General Information

Linux 2.4 Virtual Memory Overview

80x86 instruction set


Acknoledgements

Everyone that helped, in some way, this project so far. Alair P. do Lago, Dilma M. da Silva, Fabio Kon, Livio B. Soares, Caetano J. Carezzato, Scott F. Kaplan, Paolo Ciarrocchi, Marc-Christian Petersen, Con Kolivas, Rik van Riel, Marcelo Tosatti, Jeff Dike.


References

The Case for Compressed Caching in Virtual Memory Systems

Paul R. Wilson, Scott F. Kaplan, and Yannis Smaragdakis, USENIX '99. (postscript)

Compressed Caching and Modern Virtual Memory Simulation

Scott F. Kaplan, Ph.D. Dissertation. (postscript)

Improving Application Performance through Swap Compression

R. Cervera, T. Cortes, and Y. Becerra, , USENIX '99. (postscript)
Their Compressed Swap Cache for Linux page (html)

The Compression Cache: Using On-Line Compression to Extend Physical Memory

Fred Douglis, paper. (postscript)

Operating System Support for Fast Hardware Compression of Main Memory Contents

Bulent Abali and Hubertus Franke, IBM T.J. Watson Research Center, paper. (pdf)

Unix Internals

Uresh Vahalia, Prentice Hall, 1995, book.

Understanding the Linux Kernel

Daniel P. Bovet and Marco Cesati, O'Reilly, 2001, book.

The Linux Kernel

David A Rusling, book. (postscript)

Too little, too slow; memory management

Rik van Riel, lecture. (html)

Page replacement in Linux 2.4 memory management

Rik van Riel, paper FREENIX 2001. (pdf)

The Memory Management Glossary (html)

UVM, the new Virtual Memory system (html)

The Design and Implementation of the UVM Virtual Memory System

Charles Cranor (postscript)

The Slab Allocator: An Object-Caching Kernel Memory Allocator

Jeff Bonwick, presented at the USENIX '94. (postscript)

User-Mode-Linux

Jeff Dike (html)

Linux Kernel Debugging

Andrea Arcangeli, talk in San José. (tar.gz)

Open Source Development with CVS

Karl Fogel, online book. (web site)

Monografia do Trabalho de Formatura

Rodrigo S. de Castro, technical activities report (summary), in Portuguese. (postscript)

Valid HTML 4.01! Valid CSS! SourceForge.net Logo

Page last updated on "Thu Jul 10 17:12:49 2003"
Send feedback to Rodrigo S. de Castro <rcastro@users.sourceforge.net>