Skip to content

CART - an advanced page replacement policy

Peter Zijlstra linux-mm lkml 1 version In review

Get series with b4
b4 am 20050929180845.910895444@twins

Versions newest first

  1. v1 Latest7 patches 6 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/7CART - an advanced page replacement policyinclude/linux/swap.h init/main.c mm/Makefile +1 more+402 -10 replies
2/7CART - an advanced page replacement policyfs/proc/proc_misc.c mm/nonresident.c+95 -00 replies
3/7CART - an advanced page replacement policyinclude/linux/mm_inline.h include/linux/mmzone.h include/linux/page-flags.h +4 more+681 -353 replies
4/7CART - an advanced page replacement policyinclude/linux/mmzone.h mm/cart.c+41 -40 replies
5/7CART - an advanced page replacement policyfs/proc/proc_misc.c mm/cart.c+108 -00 replies
6/7CART - an advanced page replacement policymm/filemap.c mm/shmem.c mm/swap.c +2 more+8 -650 replies
7/7CART - an advanced page replacement policyfs/exec.c include/linux/swap.h mm/memory.c +3 more+38 -3060 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [PATCH 0/7] CART - an advanced page replacement policy

Multiple memory zone CART implementation for Linux. An advanced page replacement policy.

http://www.almaden.ibm.com/cs/people/dmodha/clockfast.pdf
(IBM does hold patent rights to the base algorithm ARC)

My ideas are based on the initial cart patch by Rahul Iyer and the non-resident code of Rik van Riel.

For a zoned page replacement algorithm we have per zone resident list(s) and global non-resident list(s). CART specific we would have a T1_i and T2_i, where 0 <= i <= nr_zones, and global B1 and B2 lists.

Because B1 and B2 are variable size and the B1_i target size q_i is zone specific we need some tricks. However since |B1| + |B2| = c we could get away with a single hash_table of c entries if we can manage to balance the entries within.

Let us denote the buckets with the subscript j: |B1_j| + |B2_j| = c_j.

We need to balance the per zone values:
T1_i, T2_i, |T1_i|, |T2_i|
p_i, Ns_i, Nl_i

|B1_i|, |B2_i|, q_i

against the per bucket values:
B1_j, B2_j.

and global values:
|B1|, |B2|

This can be done with two simple modifications to the algorithm:

- explicitly keep |B1_i| and |B2_i| - needed for the p,q targets; rebalance with the global |B1|, |B2| before a batch replace.

- merge the history replacement (lines 6-10) in the replace (lines 36-40) code so that: adding the new MRU page and removing the old LRU page becomes one action.

This will keep:

|B1_j| |B1| |B1_i|
-------- ~ ------ ~ --------
|B2_j| |B2| |B2_i|

I implemented my ideas in the following 4 patches:

[1/7] cart-nonresident.patch
[3/7] cart-cart.patch
[6/7] cart-use-once.patch
[7/7] cart-use-cart.patch

1. contains the hashed nonresident page management
3. contains the CART implementation proper
6. removes the current use-once logic
7. replace the current page replacement logic with cart

I also improved upon CART in the following patch:

[5/7] cart-cart-r.patch

And some debugging /proc stats for both the nonresident and cart code:

[2/7] cart-nonresident-stats.patch
[4/7] cart-cart-stats.patch

The code seems stable on my SMP box (thanks to the wonderfull lock debugging found in the -rt tree) hence this first post outside of linux-mm.

All feedback, comments and test results are welcome. I hope for inclusion in -mm and if blessed in -linus one day.

Kind regards,

Peter Zijlstra

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>