15-412, CART for Linux

This is the home of the "CART for Linux" project.

Introduction

Paging algorithms are key to achieving performance from many Operating Systems. Traditionally, operating systems have used LRU based algorithms for page replacement. LRU approximations such as CLOCK are often used. Linux currently uses an active pages/inactive pages list approach which also works like clock. More on the current eviction scheme can be found in the references section. However, the reader is warned that the MM system in Linux is a candidate for frequent upheavals and often the information is dated and sometimes inaccurate.

The mid 1990s spawned research in the page replacement area. Algorithms such as Clock Pro, ARC and CART were proposed. All these algorithms have one feature in common - they all use a cache directory that consists not only of the resident pages, but also information on non resident pages in the system.

My Work

The problem of representing non resident pages is an interesting one as it is essential that the storage overhead for this be low. However, speed of lookup and LRU property maintenance also pose additional restrictions. My work in this area led to two patches which are available in the "Patches" section.

Once this framework was in place, I implemented the CART algorithm proposed by Modha et al. at IBM. The first patch implements the algorithm exactly as it is mentioned in the paper. However, in the second patch, I retain the active/inactive lists, however, I use CART to select candidates for replacement from the active list.

Patches

The third CART patch is available here. This fixes a few bugs that Marcelo Tosatti pointed out. As with the v2 patch, this too applies on the 2.6.12-rc5 kernel. This patch upgrades from the v2 patch. If you are using Rik van Riel's patches for non resident page management, use this patch.

The second CART patch is available here. It applies on a vanilla 2.6.12-rc5 kernel. This changes the standard CART implementation to use CART only on the active list rather than making the 4 CART lists into the page cache.

The first CART Patch is available here. It applies on a vanilla 2.6.11 kernel.

Kindly note that ARC and CART are under patents held by IBM Corporation. However, as per Nick Donofrio's speech at the Linuxworld conference and expo, IBM has pledged not to "assert its patent portfolio against the Linux kernel". The link to the news story is here. However, if you are going to use this code for commercial purposes, it is recommended that you contact IBM.

Current Status

Currently, this project is a part of an experimental excursion into advanced page replacement technologies coordinated by Rik van Riel. I have been running this code on my laptop on a regular basis, and have found no issues in normal operation. However, I do know that there is a case where the kernel runs out of memory while allocating a node representing a non-resident page. This issue showed up in my test suite. The latest info on the project can be found at the Advanced Page Replacement Wiki.

Reference material

• Advanced Page Replacement
  • Advanced Page Replacement Wiki
• CART
  • The CART Paper
• Linux Memory Management
  • Understanding the Linux Memory Manager
  • Code Commentary on the Linux Virtual Memory Manager
  • Towards an O(1) VM
  • Page Replacement in Linux 2.4
• Linux Kernel Source
  • The Linux Kernel Sources
  • An Easy way to Browse the kernel sources

Presentations

• CART for Linux Presentation (2/10/05)

• The Story of a Page (2/23/05)

• CART Implementation (3/14/05)

[Last modified Thursday September 01, 2005]