CART - an advanced page replacement policy
Subsystems (10)
cover 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>
PATCH 1/7 CART - an advanced page replacement policy
Originally started by Rik van Riel, I heavily modified the code to suit my needs. Comments in the file should be clear.
include/linux/swap.h | 23 +++ init/main.c | 2 mm/Makefile | 3 mm/nonresident.c | 372 +++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 399 insertions(+), 1 deletion(-)
mm/nonresident.c new file +375 -0
@@ -0,0 +1,375 @@ +/* +* mm/nonresident.c +* (C) 2004,2005 Red Hat, Inc +* Written by Rik van Riel <[email protected]> +* Released under the GPL, see the file COPYING for details. +* Adapted by Peter Zijlstra <[email protected]> for use by ARC +* like algorithms. +* +* Keeps track of whether a non-resident page was recently evicted +* and should be immediately promoted to the active list. This also +* helps automatically tune the inactive target. +* +* The pageout code stores a recently evicted page in this cache +* by calling nonresident_put(mapping/mm, index/vaddr) +* and can look it up in the cache by calling nonresident_find() +* with the same arguments. +* +* Note that there is no way to invalidate pages after eg. truncate +* or exit, we let the pages fall out of the non-resident set through +* normal replacement. +* +* +* Modified to work with ARC like algorithms who: +* - need to balance two FIFOs; |b1| + |b2| = c, +* +* The bucket contains four single linked cyclic lists (CLOCKS) and each +* clock has a tail hand. By selecting a victim clock upon insertion it +* is possible to balance them. +* +* The first two lists are used for B1/B2 and a third for a free slot list. +* The fourth list is unused. +* +* The slot looks like this: +* struct slot_t { +* u32 cookie : 24; // LSB +* u32 index : 6; +* u32 listid : 2; +* }; +* +* The bucket is guarded by a spinlock. +*/ +#include <linux/swap.h> +#include <linux/mm.h> +#include <linux/cache.h> +#include <linux/spinlock.h> +#include <linux/bootmem.h> +#include <linux/hash.h> +#include <linux/prefetch.h> +#include <linux/kernel.h> + +#define TARGET_SLOTS 64 +#define NR_CACHELINES (TARGET_SLOTS*sizeof(u32) / L1_CACHE_BYTES) +#define NR_SLOTS (((NR_CACHELINES * L1_CACHE_BYTES) - sizeof(spinlock_t) - 2*sizeof(u16)) / sizeof(u32)) +#if 0 +#if NR_SLOTS < (TARGET_SLOTS /2 ) +#warning very small slot size +#if NR_SLOTS <=0 +#error no room for slots left +#endif +#endif +#endif + +#define BUILD_MASK (bits, shift) (((1 << (bits)) - 1) << (shift)) + +#define LISTID_BITS 2 +#define LISTID_SHIFT (sizeof(u32)*8 - LISTID_BITS) +#define LISTID_MASK BUILD_MASK(LISTID_BITS, LISTID_SHIFT) + +#define SET_LISTID (x, flg) ((x) = ((x) & ~LISTID_MASK) | ((flg) << LISTID_SHIFT)) +#define GET_LISTID (x) (((x) & LISTID_MASK) >> LISTID_SHIFT) + +#define INDEX_BITS 6/* ceil(log2(NR_SLOTS)) */ +#define INDEX_SHIFT (LISTID_SHIFT - INDEX_BITS) +#define INDEX_MASK BUILD_MASK(INDEX_BITS, INDEX_SHIFT) + +#define SET_INDEX (x, idx) ((x) = ((x) & ~INDEX_MASK) | ((idx) << INDEX_SHIFT)) +#define GET_INDEX (x) (((x) & INDEX_MASK) >> INDEX_SHIFT) + +#define COOKIE_MASK BUILD_MASK(sizeof(u32)*8 - LISTID_BITS - INDEX_BITS, 0) + +struct nr_bucket +{ +spinlock_t lock; +u8 hand[4 ]; +u32 slot[NR_SLOTS ]; +}____cacheline_aligned ; + +/* The non-resident page hash table. */ +static struct nr_bucket * nonres_table; +static unsigned int nonres_shift; +static unsigned int nonres_mask; + +/* hash the address into a bucket */ +static struct nr_bucket *nr_hash (void * mapping,unsigned long index) +{ +unsigned long bucket; +unsigned long hash; + + hash = (unsigned long )mapping +37 * index; + bucket =hash_long (hash, nonres_shift); + +return nonres_table + bucket; +} + +/* hash the address and inode into a cookie */ +static u32 nr_cookie (struct address_space * mapping,unsigned long index) +{ +unsigned long hash; + + hash =37 * (unsigned long )mapping + index; + +if (mapping && mapping->host) + hash =37 * hash + mapping->host->i_ino; + +return hash_long (hash,sizeof (u32)*8 -LISTID_BITS -INDEX_BITS ); +} + +static DEFINE_PER_CPU(unsigned int[4], nonres_count); + +/* +* remove current (b from 'abc'): +* +* initial swap(2,3) +* +* 1: -> [2],a 1: -> [2],a +* * 2: -> [3],b 2: -> [1],c +* 3: -> [1],c * 3: -> [3],b +* +* 3 is now free for use. +* +* @nr_bucket: bucket to operate in +* @listid: list that the deletee belongs to +* @pos: slot position of deletee +* @slot: possible pointer to slot +* +* returns pointer to removed slot, NULL when list empty. +*/ +static u32 *__nonresident_del (struct nr_bucket *nr_bucket,int listid,u8 pos,u32 *slot) +{ +int next_pos; +u32 *next; + +if (slot ==NULL ) { + slot = &nr_bucket->slot[pos]; +if (GET_LISTID (*slot) != listid) +return NULL ; + } + + --__get_cpu_var (nonres_count[listid]); + + next_pos =GET_INDEX (*slot); +if (pos == next_pos) { + next = slot; + goto out; + } + + next = &nr_bucket->slot[next_pos]; + *next =xchg (slot, *next); + +if (next_pos == nr_bucket->hand[listid]) + nr_bucket->hand[listid] = pos; +out: +BUG_ON (GET_INDEX (*next) != next_pos); +return next; +} + +static inline u32 *__nonresident_pop (struct nr_bucket *nr_bucket,int listid) +{ +return __nonresident_del (nr_bucket, listid, nr_bucket->hand[listid],NULL ); +} + +/* +* insert before (d before b in 'abc') +* +* initial set 4 swap(2,4) +* +* 1: -> [2],a 1: -> [2],a 1: -> [2],a +* * 2: -> [3],b 2: -> [3],b 2: -> [4],d +* 3: -> [1],c 3: -> [1],c 3: -> [1],c +* 4: -> [4],nil 4: -> [4],d * 4: -> [3],b +* +* leaving us with 'adbc'. +* +* @nr_bucket: bucket to operator in +* @listid: list to insert into +* @pos: position to insert before +* @slot: slot to insert +*/ +static void __nonresident_insert (struct nr_bucket *nr_bucket,int listid,u8 *pos,u32 *slot) +{ +u32 *head; + +SET_LISTID (*slot, listid); + + head = &nr_bucket->slot[*pos]; + + *pos =GET_INDEX (*slot); +if (GET_LISTID (*head) == listid) + *slot =xchg (head, *slot); + + ++__get_cpu_var (nonres_count[listid]); +} + +static inline void __nonresident_push (struct nr_bucket *nr_bucket,int listid,u32 *slot) +{ +__nonresident_insert (nr_bucket, listid, &nr_bucket->hand[listid], slot); +} + +/* +* Remembers a page by putting a hash-cookie on the @listid list. +* +* @mapping: page_mapping() +* @index: page_index() +* @listid: list to put the page on (NR_b1, NR_b2 and NR_free). +* @listid_evict: list to get a free page from when NR_free is empty. +* +* returns the list an empty page was taken from. +*/ +int nonresident_put (struct address_space * mapping,unsigned long index,int listid,int listid_evict) +{ +struct nr_bucket *nr_bucket; +u32 cookie; +unsigned long flags; +u32 *slot; +int evict = NR_free; + +prefetch (mapping->host); + nr_bucket =nr_hash (mapping, index); + +spin_lock_prefetch (nr_bucket);// prefetchw_range(nr_bucket, NR_CACHELINES); + cookie =nr_cookie (mapping, index); + +spin_lock_irqsave (&nr_bucket->lock, flags); + slot =__nonresident_pop (nr_bucket, evict); +if (!slot) { + evict = listid_evict; + slot =__nonresident_pop (nr_bucket, evict); +if (!slot) { + evict ^=1 ; + slot =__nonresident_pop (nr_bucket, evict); + } + } +BUG_ON (!slot); +SET_INDEX (cookie,GET_INDEX (*slot)); + cookie =xchg (slot, cookie); +__nonresident_push (nr_bucket, listid, slot); +spin_unlock_irqrestore (&nr_bucket->lock, flags); + +return evict; +} + +/* +* Searches a page on the first two lists, and places it on the free list. +* +* @mapping: page_mapping() +* @index: page_index() +* +* returns listid of the list the item was found on with NR_found set if found. +*/ +int nonresident_find (struct address_space * mapping,unsigned long index) +{ +struct nr_bucket * nr_bucket; +u32 wanted; +int j; +u8 i; +unsigned long flags; +int ret =0 ; + +if (mapping) +prefetch (mapping->host); + nr_bucket =nr_hash (mapping, index); + +spin_lock_prefetch (nr_bucket);// prefetch_range(nr_bucket, NR_CACHELINES); + wanted =nr_cookie (mapping, index) &COOKIE_MASK ; + +spin_lock_irqsave (&nr_bucket->lock, flags); +for (i =0 ; i <2 ; ++i) { + j = nr_bucket->hand[i]; +do { +u32 *slot = &nr_bucket->slot[j]; +if (GET_LISTID (*slot) != i) +break ; + +if ((*slot &COOKIE_MASK ) == wanted) { + slot =__nonresident_del (nr_bucket, i, j, slot); +__nonresident_push (nr_bucket, NR_free, slot); + ret = i | NR_found; + goto out; + } + + j =GET_INDEX (*slot); + }while (j != nr_bucket->hand[i]); + } +out: +spin_unlock_irqrestore (&nr_bucket->lock, flags); + +return ret; +} + +unsigned int nonresident_count (int listid) +{ +unsigned int ret =0 ; +int cpu; + +preempt_disable (); +for_each_cpu (cpu) { + ret +=per_cpu (nonres_count[listid], cpu); + } +preempt_enable (); + +return ret; +} + +unsigned int nonresident_total (void ) +{ +return (1 << nonres_shift) *NR_SLOTS ; +} + +/* +* For interactive workloads, we remember about as many non-resident pages +* as we have actual memory pages. For server workloads with large inter- +* reference distances we could benefit from remembering more. +*/ +static __initdata unsigned long nonresident_factor =1 ; +void __init nonresident_init (void ) +{ +int target; +int i, j; + +/* +* Calculate the non-resident hash bucket target. Use a power of +* two for the division because alloc_large_system_hash rounds up. +*/ + target = nr_all_pages * nonresident_factor; + target /= (sizeof (struct nr_bucket ) /sizeof (u32)); + + nonres_table =alloc_large_system_hash ("Non-resident page tracking" , +sizeof (struct nr_bucket ), + target, +0 , +HASH_EARLY |HASH_HIGHMEM , + &nonres_shift, + &nonres_mask, +0 ); + +for (i =0 ; i < (1 << nonres_shift); i++) { +spin_lock_init (&nonres_table[i].lock); +for (j =0 ; j <4 ; ++j) + nonres_table[i].hand[j] =0 ; + +for (j =0 ; j <NR_SLOTS ; ++j) { + nonres_table[i].slot[j] =0 ; +SET_LISTID (nonres_table[i].slot[j], NR_free); +if (j <NR_SLOTS -1 ) +SET_INDEX (nonres_table[i].slot[j], j+1 ); +else /* j == NR_SLOTS - 1 */ +SET_INDEX (nonres_table[i].slot[j],0 ); + } + } + +for_each_cpu (i) { +for (j=0 ; j<4 ; ++j) +per_cpu (nonres_count[j], i) =0 ; + } +} + +static int __init set_nonresident_factor (char * str) +{ +if (!str) +return 0 ; + nonresident_factor =simple_strtoul (str, &str,0 ); +return 1 ; +} + +__setup ("nonresident_factor=" , set_nonresident_factor);
include/linux/swap.h +23 -0
@@ -154,6 +154,22 @@ extern void out_of_memory(unsigned int _/* linux/mm/memory.c */ extern void swapin_readahead (swp_entry_t ,unsigned long ,struct vm_area_struct *); +/* linux/mm/nonresident.c */ +#define NR_b1 0 +#define NR_b2 1 +#define NR_free 2 +#define NR_lost 3 + +#define NR_listid 3 +#define NR_found 0x80000000 + + +extern int nonresident_put (struct address_space *,unsigned long ,int ,int ); +extern int nonresident_find (struct address_space *,unsigned long ); +extern unsigned int nonresident_count (int ); +extern unsigned int nonresident_total (void ); +extern void nonresident_init (void ); +/* linux/mm/page_alloc.c */ extern unsigned long totalram_pages;extern unsigned long totalhigh_pages;
@@ -292,6 +308,13 @@ static inline swp_entry_t get_swap_page(#define grab_swap_token () do { } while(0)#define has_swap_token (x) 0 +/* linux/mm/nonresident.c */ +#define nonresident_put (w,x,y,z) 0 +#define nonresident_find (x,y) 0 +#define nonresident_count (x) 0 +#define nonresident_total () 0 +#define nonresident_init () do { } while (0) +#endif /* CONFIG_SWAP */ #endif /* __KERNEL__*/ #endif /* _LINUX_SWAP_H */
init/main.c +2 -0
@@ -47,6 +47,7 @@#include <linux/rmap.h> #include <linux/mempolicy.h> #include <linux/key.h> +#include <linux/swap.h> #include <asm/io.h> #include <asm/bugs.h>
@@ -494,6 +495,7 @@ asmlinkage void __init start_kernel(void }#endif vfs_caches_init_early (); +nonresident_init ();mem_init ();kmem_cache_init ();setup_per_cpu_pageset ();
mm/Makefile +2 -1
@@ -12,7 +12,8 @@ obj-y := bootmem.o filemap.o mempool.o readahead.o slab.o swap.o truncate.o vmscan.o \ prio_tree.o $(mmu-y) -obj-$(CONFIG_SWAP) += page_io.o swap_state.o swapfile.o thrash.o +obj-$(CONFIG_SWAP) += page_io.o swap_state.o swapfile.o thrash.o \ + nonresident.o obj-$(CONFIG_HUGETLBFS) += hugetlb.o obj-$(CONFIG_NUMA) += mempolicy.o obj-$(CONFIG_SPARSEMEM) += sparse.o
--
--
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>
PATCH 2/7 CART - an advanced page replacement policy
In reply to Peter ZijlstraAdds some /proc debugging output to the nonresident code.
fs/proc/proc_misc.c | 15 +++++++++ mm/nonresident.c | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 95 insertions(+)
fs/proc/proc_misc.c +15 -0
@@ -233,6 +233,20 @@ static struct file_operations proc_zonei .release = seq_release, }; +extern struct seq_operations nonresident_op; +static int nonresident_open (struct inode *inode,struct file *file) +{ + (void )inode; +return seq_open (file, &nonresident_op); +} + +static struct file_operations nonresident_file_operations = { + .open = nonresident_open, + .read = seq_read, + .llseek = seq_lseek, + .release = seq_release, +}; +static int version_read_proc (char *page,char **start,off_t off,int count,int *eof,void *data) {
@@ -602,6 +616,7 @@ void __init proc_misc_init(void)create_seq_entry ("interrupts" ,0 , &proc_interrupts_operations);create_seq_entry ("slabinfo" ,S_IWUSR |S_IRUGO ,&proc_slabinfo_operations);create_seq_entry ("buddyinfo" ,S_IRUGO , &fragmentation_file_operations); +create_seq_entry ("nonresident" ,S_IRUGO , &nonresident_file_operations);create_seq_entry ("vmstat" ,S_IRUGO , &proc_vmstat_file_operations);create_seq_entry ("zoneinfo" ,S_IRUGO , &proc_zoneinfo_file_operations);create_seq_entry ("diskstats" ,0 , &proc_diskstats_operations);
mm/nonresident.c +80 -0
83 lines not on this page · raw message
--
--
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>
PATCH 3/7 CART - an advanced page replacement policy
In reply to Peter ZijlstraThe flesh of the CART implementation. Again comments in the file should be clear.
include/linux/mm_inline.h | 37 -- include/linux/mmzone.h | 11 include/linux/page-flags.h | 15 + include/linux/swap.h | 20 + init/main.c | 1 mm/Makefile | 2 mm/cart.c | 631 +++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 682 insertions(+), 35 deletions(-)
mm/cart.c new file +639 -0
@@ -0,0 +1,639 @@ +/* +* mm/cart.c +* +* Written by Peter Zijlstra <[email protected]> +* Released under the GPL, see the file COPYING for details. +* +* This file contains a Page Replacement Algorithm based on CART +* Please refer to the CART paper here - +* http://www.almaden.ibm.com/cs/people/dmodha/clockfast.pdf +* +* T1 -> active_list |T1| -> nr_active +* T2 -> inactive_list |T2| -> nr_inactive +* filter bit -> PG_longterm +* +* The algorithm was adapted to work for linux which poses the following +* extra constraints: +* - multiple memory zones, +* - async pageout (PG_writeback), +* - fault before reference. +* +* The multiple memory zones are handled by decoupling the T lists from the +* B lists, keeping T lists per zone while having global B lists. See +* mm/nonresident.c for the B list implementation. List sizes are scaled on +* comparison. +* +* The asynchronous pageout makes for the problem of pages that are selected +* for eviction but can not (yet) be freed. And since they are not evicted +* they could be referenced again, so we have to keep them on the resident +* lists. Handling this issue gives rise to the PG_writeback checks in +* cart_rebalance_T[12] and the cart_reinsert and cart_rotate_reclaimable +* functions. +* +* The paper seems to assume we insert after/on the first reference, we +* actually insert before the first reference. In order to give 'S' pages +* a chance we will not mark them 'L' on their first cycle (PG_new). +* +* Also for efficiency's sake the replace operation is batched. This to +* avoid holding the much contended zone->lru_lock while calling the +* possibly slow page_referenced(). +* +* +* All functions that are prefixed with '__' assume that zone->lru_lock is taken. +*/ + +#include <linux/swap.h> +#include <linux/mm.h> +#include <linux/page-flags.h> +#include <linux/mm_inline.h> +#include <linux/rmap.h> +#include <linux/buffer_head.h> +#include <linux/pagevec.h> + +#define cart_cT ((zone)->nr_active + (zone)->nr_inactive + (zone)->free_pages) +#define cart_cB ((zone)->present_pages) + +#define T2B (x) (((x) * cart_cB) / cart_cT) +#define B2T (x) (((x) * cart_cT) / cart_cB) + +#define size_T1 ((zone)->nr_active) +#define size_T2 ((zone)->nr_inactive) + +#define list_T1 (&(zone)->active_list) +#define list_T2 (&(zone)->inactive_list) + +#define cart_p ((zone)->nr_p) +#define cart_q ((zone)->nr_q) + +#define size_B1 ((zone)->nr_evicted_active) +#define size_B2 ((zone)->nr_evicted_inactive) + +#define nr_Ns ((zone)->nr_shortterm) +#define nr_Nl (size_T1 + size_T2 - nr_Ns) + +/* Called from init/main.c to initialize the cart parameters */ +void __init cart_init (void ) +{ +struct zone *zone; +for_each_zone (zone) { + zone->nr_evicted_active =0 ; + zone->nr_evicted_inactive =0 ; + zone->nr_shortterm =0 ; + zone->nr_p =0 ; + zone->nr_q =0 ; + } +} + +static inline void __cart_q_inc (struct zone *zone,unsigned long dq) +{ +/* if (|T2| + |B2| + |T1| - ns >= c) q = min(q + 1, 2c - |T1|) */ +/* |B2| + nl >= c */ +if (B2T (size_B2) + nr_Nl >= cart_cT) + cart_q =min (cart_q + dq,2 *cart_cB -T2B (size_T1)); +} + +static inline void __cart_q_dec (struct zone *zone,unsigned long dq) +{ +/* q = max(q - 1, c - |T1|) */ +unsigned long target = cart_cB -T2B (size_T1); +if (cart_q <= target) + cart_q = target; +else if (cart_q >= dq) + cart_q -= dq; +else + cart_q =0 ; +} + +/* +* Insert page into @zones CART and update adaptive parameters. +* +* @zone: target zone. +* @page: new page. +*/ +void __cart_insert (struct zone *zone,struct page *page) +{ +unsigned int rflags; +unsigned long ratio; + +/* +* Note: we could give hints to the insertion process using the LRU +* specific PG_flags like: PG_active, PG_longterm and PG_referenced. +*/ + + rflags =nonresident_find (page_mapping (page),page_index (page)); + +if (rflags & NR_found) { + rflags &= NR_listid; +if (rflags == NR_b1) { +if (likely (size_B1)) --size_B1; + +/* p = min(p + max(1, ns/|B1|), c) */ + ratio = (nr_Ns / (B2T (size_B1) +1 )) ?:1UL ; + cart_p += ratio; +if (unlikely (cart_p > cart_cT)) + cart_p = cart_cT; + +SetPageLongTerm (page); + }else if (rflags == NR_b2) { +if (likely (size_B2)) --size_B2; + +/* p = max(p - max(1, nl/|B2|), 0) */ + ratio = (nr_Nl / (B2T (size_B2) +1 )) ?:1UL ; +if (cart_p >= ratio) + cart_p -= ratio; +else + cart_p =0UL ; + +SetPageLongTerm (page); +__cart_q_inc (zone,1 ); + } +/* ++nr_Nl; */ + }else { +ClearPageLongTerm (page); + ++nr_Ns; + } + +SetPageNew (page); +ClearPageReferenced (page); +SetPageActive (page); +list_add_tail (&page->lru, list_T1); + ++size_T1; +BUG_ON (!PageLRU (page)); +} + +#define head_to_page (list) list_entry((list)->next, struct page, lru) +#define tail_to_page (list) list_entry((list)->prev, struct page, lru) + +#ifdef ARCH_HAS_PREFETCH +#define prefetch_next_lru_page (_page, _base, _field) \ + do { \ + if ((_page)->lru.next != _base) { \ + struct page *next; \ + \ + next = head_to_page(&(_page->lru)); \ + prefetch(&next->_field); \ + } \ + } while (0) + +#define prefetch_prev_lru_page (_page, _base, _field) \ + do { \ + if ((_page)->lru.prev != _base) { \ + struct page *prev; \ + \ + prev = tail_to_page(&(_page->lru)); \ + prefetch(&prev->_field); \ + } \ + } while (0) +#else +#define prefetch_next_lru_page (_page, _base, _field) do { } while (0) +#define prefetch_prev_lru_page (_page, _base, _field) do { } while (0) +#endif + +#ifdef ARCH_HAS_PREFETCHW +#define prefetchw_next_lru_page (_page, _base, _field) \ + do { \ + if ((_page)->lru.next != _base) { \ + struct page *next; \ + \ + next = head_to_page(&(_page->lru)); \ + prefetchw(&next->_field); \ + } \ + } while (0) + +#define prefetchw_prev_lru_page (_page, _base, _field) \ + do { \ + if ((_page)->lru.prev != _base) { \ + struct page *prev; \ + \ + prev = tail_to_page(&(_page->lru)); \ + prefetchw(&prev->_field); \ + } \ + } while (0) +#else +#define prefetchw_next_lru_page (_page, _base, _field) do { } while (0) +#define prefetchw_prev_lru_page (_page, _base, _field) do { } while (0) +#endif + +/* +* Try to grab a specified number of pages of a list head. +* Ups the refcount on the grabbed pages. +* +* @zone: zone to take pages from. +* @dst: temp list to hold pages. +* @src: list to take pages from. +* @nr_dst: target number of pages to grab. +* @nr_scanned: counter that keeps the number of pages touched. +* +* returns how many pages were moved to @dst. +*/ +static unsigned long cart_isolate (struct zone *zone,struct list_head *dst, +struct list_head *src,unsigned long nr_dst, +unsigned long *nr_scanned) +{ +struct page *page; +unsigned long nr_taken =0 , scan =0 ; + +spin_lock_irq (&zone->lru_lock); +while (scan++ < nr_dst && !list_empty (src)) { + page =head_to_page (src); +if (!get_page_testone (page)) { +list_move_tail (&page->lru, dst); + ++nr_taken; + }else { +list_move_tail (&page->lru, src); +__put_page (page); + } + } +spin_unlock_irq (&zone->lru_lock); + + *nr_scanned += scan; +return nr_taken; +} + +/* +* Add page to a release pagevec, temp. drop zone lock to release pagevec if full. +* +* @zone: @pages zone. +* @page: page to be released. +* @pvec: pagevec to collect pages in. +*/ +static void __cart_page_release (struct zone *zone,struct page *page, +struct pagevec *pvec) +{ +if (!pagevec_add (pvec, page)) { +spin_unlock_irq (&zone->lru_lock); +if (buffer_heads_over_limit) +pagevec_strip (pvec); +__pagevec_release (pvec); +spin_lock_irq (&zone->lru_lock); + } +} + +/* +* Append list to head and releases pages. +* +* @zone: zone of pages. +* @list: temp list of pages (1 ref). +* @head: zone pagelist. +* @pvec: pagevec for release. +*/ +static void __cart_list_splice_tail_release (struct zone *zone,struct list_head *list, +struct list_head *head,struct pagevec *pvec) +{ +while (!list_empty (list)) {/* head = { head, list } */ +struct page *page =head_to_page (list); +list_move_tail (&page->lru, head); +__cart_page_release (zone, page, pvec); + } +} + +static void __cart_list_splice_release (struct zone *zone,struct list_head *list, +struct list_head *head,struct pagevec *pvec) +{ +while (!list_empty (list)) {/* head = { list, head } */ +struct page *page =tail_to_page (list); +list_move (&page->lru, head); +__cart_page_release (zone, page, pvec); + } +} + +/* +* Rebalance the T2 list: +* move referenced pages to T1s' tail, +* take unreffed pages for reclaim. +* +* @zone: target zone. +* @l_t2_head: temp list of reclaimable pages (1 ref). +* @nr_dst: quantum of pages. +* @nr_scanned: counter that keeps the number of pages touched. +* @pvec: pagevec used to release pages. +* @ignore_token: ignore the swap-token when checking for page_reference(). +* +* returns if we encountered more PG_writeback pages than reclaimable pages. +*/ +static int cart_rebalance_T2 (struct zone *zone,struct list_head *l_t2_head, +unsigned long nr_dst,unsigned long *nr_scanned, +struct pagevec *pvec,int ignore_token) +{ +struct page *page; +LIST_HEAD (l_hold); +LIST_HEAD (l_t1); +unsigned long nr, dq; +unsigned long nr_reclaim =0 , nr_writeback =0 ; + +do { + nr =cart_isolate (zone, &l_hold, list_T2, nr_dst, nr_scanned); +if (!nr) +break ; + + dq =0 ; +while (!list_empty (&l_hold)) { + page =head_to_page (&l_hold); +prefetchw_next_lru_page (page, &l_hold, flags); + +if (page_referenced (page,0 , ignore_token) || + (PageWriteback (page) && ++nr_writeback)) { +list_move_tail (&page->lru, &l_t1); +SetPageActive (page); + ++dq; + }else { +list_move_tail (&page->lru, l_t2_head); + ++nr_reclaim; + } + } + +spin_lock_irq (&zone->lru_lock); +__cart_list_splice_tail_release (zone, &l_t1, list_T1, pvec); + size_T2 -= dq; + size_T1 += dq; +__cart_q_inc (zone, dq); +spin_unlock_irq (&zone->lru_lock); + }while (list_empty (l_t2_head) && nr_writeback < nr_reclaim); + +return nr_writeback >= nr_reclaim; +} + +/* +* Rebalance the T1 list: +* move referenced pages to tail and possibly mark 'L', +* move unreffed 'L' pages to tail T2, +* take unreffed 'S' pages for reclaim. +* +* @zone: target zone. +* @l_t1_head: temp list of reclaimable pages (1 ref). +* @nr_dst: quantum of pages. +* @nr_scanned: counter that keeps the number of pages touched. +* @pvec: pagevec used to release pages. +* @ignore_token: ignore the swap-token when checking for page_reference(). +* +* returns if we encountered more PG_writeback pages than reclaimable pages. +*/ +static int cart_rebalance_T1 (struct zone *zone,struct list_head *l_t1_head, +unsigned long nr_dst,unsigned long *nr_scanned, +struct pagevec *pvec,int ignore_token) +{ +struct page *page; +LIST_HEAD (l_hold); +LIST_HEAD (l_t1); +LIST_HEAD (l_t2); +unsigned long nr, dq, dsl; +unsigned long nr_reclaim =0 , nr_writeback =0 ; +int new, referenced; + +do { + nr =cart_isolate (zone, &l_hold, list_T1, nr_dst, nr_scanned); +if (!nr) +break ; + + dq =0 ; + dsl =0 ; +while (!list_empty (&l_hold)) { + page =head_to_page (&l_hold); +prefetchw_next_lru_page (page, &l_hold, flags); + + referenced =page_referenced (page,0 , ignore_token); + new =TestClearPageNew (page); + +if (referenced || + (PageWriteback (page) && ++nr_writeback)) { +list_move_tail (&page->lru, &l_t1); + +/* ( |T1| >= min(p + 1, |B1|) ) and ( filter = 'S' ) */ +if (referenced && !PageLongTerm (page) && !new && + (size_T1 - dq) >=min (cart_p +1 ,B2T (size_B1))) { +SetPageLongTerm (page); + ++dsl; + } + }else if (PageLongTerm (page)) { +list_move_tail (&page->lru, &l_t2); +ClearPageActive (page); + ++dq; + }else { +list_move_tail (&page->lru, l_t1_head); + ++nr_reclaim; + } + } + +spin_lock_irq (&zone->lru_lock); +__cart_list_splice_tail_release (zone, &l_t2, list_T2, pvec); +__cart_list_splice_tail_release (zone, &l_t1, list_T1, pvec); + nr_Ns -= dsl; +/* nr_Nl += dsl; */ + size_T1 -= dq; + size_T2 += dq; +__cart_q_dec (zone, dq); +spin_unlock_irq (&zone->lru_lock); + }while (list_empty (l_t1_head) && nr_writeback < nr_reclaim); + +return nr_writeback >= nr_reclaim; +} + +/* +* Try to reclaim a specified number of pages. +* +* Clears PG_lru of reclaimed pages, but does take 1 reference. +* +* @zone: target zone to reclaim pages from. +* @dst: temp list of reclaimable pages (1 ref). +* @nr_dst: target number of pages to reclaim. +* @nr_scanned: counter that keeps the number of pages touched. +* @ignore_token: ignore the swap-token when checking for page_reference(). +* +* returns number of pages on @dst. +*/ +unsigned long cart_replace (struct zone *zone,struct list_head *dst, +unsigned long nr_dst,unsigned long *nr_scanned, +int ignore_token) +{ +struct page *page; +LIST_HEAD (l_t1); +LIST_HEAD (l_t2); +struct pagevec pvec; +unsigned long nr; +unsigned int nonres_total; +int wr1 =0 , wr2 =0 ; + +pagevec_init (&pvec,1 ); + +/* +* Rebalance nonresident lists to zone size +*/ + nonres_total =nonresident_total (); + +spin_lock_irq (&zone->lru_lock); + size_B1 = (nonresident_count (NR_b1) * cart_cB) / nonres_total; + size_B2 = (nonresident_count (NR_b2) * cart_cB) / nonres_total; +spin_unlock_irq (&zone->lru_lock); + +for (nr =0 ; nr < nr_dst;) { +if (list_empty (&l_t2)) + wr2 =cart_rebalance_T2 (zone, &l_t2, nr_dst/2 , nr_scanned, + &pvec, ignore_token); +if (list_empty (&l_t1)) + wr1 =cart_rebalance_T1 (zone, &l_t1, nr_dst/2 , nr_scanned, + &pvec, ignore_token); + +if (list_empty (&l_t1) &&list_empty (&l_t2)) +break ; + +spin_lock_irq (&zone->lru_lock); +while (!list_empty (&l_t1) && + (size_T1 > cart_p || !size_T2 || wr2) && nr < nr_dst) { + page =head_to_page (&l_t1); +prefetchw_next_lru_page (page, &l_t1, flags); + +if (!TestClearPageLRU (page)) +BUG (); +if (PageLongTerm (page)) +BUG (); + --nr_Ns; + --size_T1; + ++nr; +list_move (&page->lru, dst); + } +while (!list_empty (&l_t2) && + (size_T1 <= cart_p || wr1) && nr < nr_dst) { + page =head_to_page (&l_t2); +prefetchw_next_lru_page (page, &l_t2, flags); + +if (!TestClearPageLRU (page)) +BUG (); +if (!PageLongTerm (page)) +BUG (); +/* --nr_Nl; */ + --size_T2; + ++nr; +list_move (&page->lru, dst); + } +spin_unlock_irq (&zone->lru_lock); + +cond_resched (); + } + +spin_lock_irq (&zone->lru_lock); +__cart_list_splice_release (zone, &l_t1, list_T1, &pvec); +__cart_list_splice_release (zone, &l_t2, list_T2, &pvec); +spin_unlock_irq (&zone->lru_lock); +pagevec_release (&pvec); + +return nr; +} + +/* +* Re-insert pages that were elected for replacement but could not be freed, +* writeback has started agains them. Rotate as referenced to let the relaim +* path make progress. +* +* Assumes PG_lru is clear and will set for re-inserted pages. +* Assumes the pages have 1 reference taken and will return it. +* +* @zone: target zone for re-insertion. +* @list: list of left over pages. +*/ +void cart_reinsert (struct zone *zone,struct list_head *list) +{ +struct pagevec pvec; + +pagevec_init (&pvec,1 ); +spin_lock_irq (&zone->lru_lock); +while (!list_empty (list)) + { +struct page *page =tail_to_page (list); +prefetchw_prev_lru_page (page, list, flags); + +if (TestSetPageLRU (page)) +BUG (); +if (!PageActive (page)) {/* T2 */ +if (!PageLongTerm (page)) +BUG (); + +SetPageActive (page); +list_move_tail (&page->lru, list_T1); + ++size_T1; + +__cart_q_inc (zone,1 ); + }else {/* T1 */ +if (!PageLongTerm (page)) + ++nr_Ns; +/* else ++nr_Nl; */ + +list_move_tail (&page->lru, list_T1); + ++size_T1; + +/* ( |T1| >= min(p + 1, |B1| ) and ( filter = 'S' ) */ +/* +* Don't modify page state; it wasn't actually referenced +*/ + } +__cart_page_release (zone, page, &pvec); + } +spin_unlock_irq (&zone->lru_lock); +pagevec_release (&pvec); +} + +/* +* Make page available for direct reclaim. +* +* @zone: page's zone. +* @page: page. +*/ +void __cart_rotate_reclaimable (struct zone *zone,struct page *page) +{ +if (PageLongTerm (page)) { +if (TestClearPageActive (page)) { + --size_T1; + ++size_T2; +__cart_q_dec (zone,1 ); + } +list_move (&page->lru, list_T2); + }else { +if (!PageActive (page)) +BUG (); +list_move (&page->lru, list_T1); + } +} + +/* +* Puts pages on the non-resident lists on swap-out +* XXX: lose the reliance on zone->lru_lock !!! +* +* @zone: dead pages zone. +* @page: dead page. +*/ +void __cart_remember (struct zone *zone,struct page *page) +{ +int listid; +int listid_evict; + +if (PageActive (page)) { + listid = NR_b1; + ++size_B1; + }else { + listid = NR_b2; + ++size_B2; + } + +/* +* Assume |B1| + |B2| == c + 1, since |B1_j| + |B2_j| := c_j. +* The list_empty check is done on the Bn_j side. +*/ +/* |B1| > max(0, q) */ +if (size_B1 > cart_q) + listid_evict = NR_b1; +else + listid_evict = NR_b2; + + listid_evict =nonresident_put (page_mapping (page), +page_index (page), + listid, listid_evict); + +switch (listid_evict) { +case NR_b1: +if (likely (size_B1)) --size_B1; +break ; + +case NR_b2: +if (likely (size_B2)) --size_B2; +break ; + } +}
include/linux/mm_inline.h +6 -31
@@ -1,40 +1,15 @@ - -static inline void -add_page_to_active_list (struct zone *zone,struct page *page) -{ -list_add (&page->lru, &zone->active_list); - zone->nr_active++; -} - -static inline void -add_page_to_inactive_list (struct zone *zone,struct page *page) -{ -list_add (&page->lru, &zone->inactive_list); - zone->nr_inactive++; -} - -static inline void -del_page_from_active_list (struct zone *zone,struct page *page) -{ -list_del (&page->lru); - zone->nr_active--; -} - -static inline void -del_page_from_inactive_list (struct zone *zone,struct page *page) -{ -list_del (&page->lru); - zone->nr_inactive--; -} -static inline void del_page_from_lru (struct zone *zone,struct page *page) {list_del (&page->lru); -if (PageActive (page)) { -ClearPageActive (page); +if (TestClearPageActive (page)) { zone->nr_active--; }else { zone->nr_inactive--; } +if (TestClearPageLongTerm (page)) { +/* zone->nr_longterm--; */ + }else { + zone->nr_shortterm--; + } }
include/linux/mmzone.h +8 -3
@@ -143,13 +143,18 @@ struct zone {ZONE_PADDING (_pad1_)/* Fields commonly accessed by the page reclaim scanner */ - spinlock_t lru_lock; -struct list_head active_list; -struct list_head inactive_list; + spinlock_t lru_lock; +struct list_head active_list;/* The T1 list of CART */ +struct list_head inactive_list;/* The T2 list of CART */ unsigned long nr_scan_active;unsigned long nr_scan_inactive;unsigned long nr_active;unsigned long nr_inactive; +unsigned long nr_evicted_active; +unsigned long nr_evicted_inactive; +unsigned long nr_shortterm;/* number of short term pages */ +unsigned long nr_p;/* p from the CART paper */ +unsigned long nr_q;/* q from the cart paper */ unsigned long pages_scanned;/* since last reclaim */ int all_unreclaimable;/* All pages pinned */
include/linux/page-flags.h +15 -0
@@ -76,6 +76,9 @@#define PG_nosave_free 18/* Free, should not be written */ #define PG_uncached 19/* Page has been mapped as uncached */ +#define PG_longterm 20/* Filter bit for CART see mm/cart.c */ +#define PG_new 21/* New page, skip first reference */ +/* * Global page accounting. One instance per CPU. Only unsigned longs are * allowed.
@@ -305,6 +308,18 @@ extern void __mod_page_state(unsigned lo#define SetPageUncached (page) set_bit(PG_uncached, &(page)->flags)#define ClearPageUncached (page) clear_bit(PG_uncached, &(page)->flags) +#define PageLongTerm (page) test_bit(PG_longterm, &(page)->flags) +#define SetPageLongTerm (page) set_bit(PG_longterm, &(page)->flags) +#define TestSetPageLongTerm (page) test_and_set_bit(PG_longterm, &(page)->flags) +#define ClearPageLongTerm (page) clear_bit(PG_longterm, &(page)->flags) +#define TestClearPageLongTerm (page) test_and_clear_bit(PG_longterm, &(page)->flags) + +#define PageNew (page) test_bit(PG_new, &(page)->flags) +#define SetPageNew (page) set_bit(PG_new, &(page)->flags) +#define TestSetPageNew (page) test_and_set_bit(PG_new, &(page)->flags) +#define ClearPageNew (page) clear_bit(PG_new, &(page)->flags) +#define TestClearPageNew (page) test_and_clear_bit(PG_new, &(page)->flags) +struct page ;/* forward declaration */ int test_clear_page_dirty (struct page *page);
include/linux/swap.h +11 -0
@@ -7,6 +7,7 @@#include <linux/mmzone.h> #include <linux/list.h> #include <linux/sched.h> +#include <linux/mm.h> #include <asm/atomic.h> #include <asm/page.h>
@@ -170,6 +171,16 @@ extern unsigned int nonresident_count(inextern unsigned int nonresident_total (void );extern void nonresident_init (void ); +/* linux/mm/cart.c */ +extern void cart_init (void ); +extern void __cart_insert (struct zone *,struct page *); +extern unsigned long cart_replace (struct zone *,struct list_head *, +unsigned long ,unsigned long *, +int ); +extern void cart_reinsert (struct zone *,struct list_head *); +extern void __cart_rotate_reclaimable (struct zone *,struct page *); +extern void __cart_remember (struct zone *,struct page *); +/* linux/mm/page_alloc.c */ extern unsigned long totalram_pages;extern unsigned long totalhigh_pages;
init/main.c +1 -0
@@ -497,6 +497,7 @@ asmlinkage void __init start_kernel(voidvfs_caches_init_early ();nonresident_init ();mem_init (); +cart_init ();kmem_cache_init ();setup_per_cpu_pageset ();numa_policy_init ();
mm/Makefile +1 -1
@@ -13,7 +13,7 @@ obj-y := bootmem.o filemap.o mempool.o prio_tree.o $(mmu-y) obj-$(CONFIG_SWAP) += page_io.o swap_state.o swapfile.o thrash.o \ - nonresident.o + nonresident.o cart.o obj-$(CONFIG_HUGETLBFS) += hugetlb.o obj-$(CONFIG_NUMA) += mempolicy.o obj-$(CONFIG_SPARSEMEM) += sparse.o
--
--
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>
Hi Peter,
Quoted 2 lines · Peter Zijlstra
The flesh of the CART implementation. Again comments in the file should be clear.
Having per-zone "B1" target accounted at fault-time instead of a global target strikes me.
The ARC algorithm adjusts the B1 target based on the fact that being-faulted-pages were removed from the same memory region where such pages will reside.
The per-zone "B1" target as you implement it means that the B1 target accounting happens for the zone in which the page for the faulting data has been allocated, _not_ on the zone from which the data has been evicted. Seems quite unfair.
So for example, if a page gets removed from the HighMem zone while in the B1 list, and the same data gets faulted in later on a page from the normal zone, Normal will have its "B1" target erroneously increased.
A global inactive target scaled to the zone size would get rid of that problem.
Another issue is testing: You had some very interesting numbers before, how are things now?
Quoted 10 lines
Signed-off-by Peter Zijlstra <[email protected]>mm/cart.c | 631 +++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 682 insertions(+), 35 deletions(-)Index:
linux-2.6-git/mm/cart.c
===================================================================mm/cart.c new file +0
-0@@ -0,0 +1,639 @@
<snip>
Quoted 10 lines
mm/cart.c new file +10
-0+#define cart_cT ((zone)->nr_active + (zone)->nr_inactive + (zone)->free_pages) +#define cart_cB ((zone)->present_pages) + +#define T2B (x) (((x) * cart_cB) / cart_cT) +#define B2T (x) (((x) * cart_cT) / cart_cB) + +#define size_T1 ((zone)->nr_active) +#define size_T2 ((zone)->nr_inactive) + +#define list_T1 (&(zone)->active_list)
mm/cart.c line 72
Quoted 10 lines
mm/cart.c new file +10
-0+#define list_T2 (&(zone)->inactive_list) + +#define cart_p ((zone)->nr_p) +#define cart_q ((zone)->nr_q) + +#define size_B1 ((zone)->nr_evicted_active) +#define size_B2 ((zone)->nr_evicted_inactive) + +#define nr_Ns ((zone)->nr_shortterm) +#define nr_Nl (size_T1 + size_T2 - nr_Ns)
These defines are not not easy to read inside the code which uses them, I personally think that "zone->nr_.." explicitly is much clearer.
--
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>
Quoted 16 lines · Marcelo
Hi Peter,
Quoted 2 lines · Peter Zijlstra
The flesh of the CART implementation. Again comments in the file should be clear.
Having per-zone "B1" target accounted at fault-time instead of a global target strikes me.
The ARC algorithm adjusts the B1 target based on the fact that being-faulted-pages were removed from the same memory region where such pages will reside.
The per-zone "B1" target as you implement it means that the B1 target accounting happens for the zone in which the page for the faulting data has been allocated, _not_ on the zone from which the data has been evicted. Seems quite unfair.
Quoted 5 lines
So for example, if a page gets removed from the HighMem zone while in the B1 list, and the same data gets faulted in later on a page from the normal zone, Normal will have its "B1" target erroneously increased.
A global inactive target scaled to the zone size would get rid of that problem.
Good, good, I'll think this though, this probably means the other
targets: 'p' and 'r' would similarly benefit.
Quoted 2 lines
Another issue is testing: You had some very interesting numbers before, how are things now?
I managed to reproduce that 10% gain on the kernel build time once more, however it seems very unstable, I generally get only 2-3%.
Quoted 29 lines
Quoted 10 lines
Signed-off-by Peter Zijlstra <[email protected]>mm/cart.c | 631 +++++++++++++++++++++++++++++++++++++++++++++ 7 files changed, 682 insertions(+), 35 deletions(-)Index:
linux-2.6-git/mm/cart.c
===================================================================mm/cart.c new file +0
-0@@ -0,0 +1,639 @@<snip>
Quoted 16 lines
mm/cart.c new file +16
-0+#define cart_cT ((zone)->nr_active + (zone)->nr_inactive + (zone)->free_pages) +#define cart_cB ((zone)->present_pages) + +#define T2B (x) (((x) * cart_cB) / cart_cT) +#define B2T (x) (((x) * cart_cT) / cart_cB) + +#define size_T1 ((zone)->nr_active) +#define size_T2 ((zone)->nr_inactive) + +#define list_T1 (&(zone)->active_list) +#define list_T2 (&(zone)->inactive_list) + +#define cart_p ((zone)->nr_p) +#define cart_q ((zone)->nr_q) + +#define size_B1 ((zone)->nr_evicted_active)
Quoted 8 lines
mm/cart.c line 72
Quoted 4 lines
mm/cart.c new file +4
-0+#define size_B2 ((zone)->nr_evicted_inactive) + +#define nr_Ns ((zone)->nr_shortterm) +#define nr_Nl (size_T1 + size_T2 - nr_Ns)These defines are not not easy to read inside the code which uses them, I personally think that "
zone->nr_.." explicitly is much clearer.
Yes, I plan to replace them by explicit referenced, however they were handy while playing with the definitions. And since nobody outside of the cart code still refers to them I plan to rename the struct zone members to match these names; zone->nr_active to zone->size_T1 and zone->active_list to zone->list_T1.
Signature · 7 lines
Peter Zijlstra <[email protected]> -- 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>
Quoted 17 lines · Peter Zijlstra
Quoted 16 lines · Marcelo
Hi Peter,
Quoted 2 lines · Peter Zijlstra
The flesh of the CART implementation. Again comments in the file should be clear.
Having per-zone "B1" target accounted at fault-time instead of a global target strikes me.
The ARC algorithm adjusts the B1 target based on the fact that being-faulted-pages were removed from the same memory region where such pages will reside.
The per-zone "B1" target as you implement it means that the B1 target accounting happens for the zone in which the page for the faulting data has been allocated, _not_ on the zone from which the data has been evicted. Seems quite unfair.
Quoted 8 lines
Quoted 5 lines
So for example, if a page gets removed from the HighMem zone while in the B1 list, and the same data gets faulted in later on a page from the normal zone, Normal will have its "B1" target erroneously increased.
A global inactive target scaled to the zone size would get rid of that problem.
Good, good, I'll think this though, this probably means the other
targets: 'p' and 'r' would similarly benefit.
I'm not thinking straigt, I should get back on my feet before I start touching that code.
Thanks for the feedsback.
Peter
Signature · 7 lines
Peter Zijlstra <[email protected]> -- 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>
PATCH 4/7 CART - an advanced page replacement policy
In reply to Peter ZijlstraAn improvement to CART.
This patch introduces yet another adaptive parameter: 'r'. 'r' measures the influx of fresh pages in ns/nl space; ie. those pages not in: T1 u T2 u B1 u B2.
When 'r' drops below nl we start reclaiming 'new' 'L' pages (from T1).
This elevates the typical scan problem of eating your own tail.
One possible improvement on this scheme: when it is found that we start reclaiming 'new' pages too soon ('p' > |T1|) we can give referenced 'new' 'L' pages one extra cycle and promote them to regular 'L' pages instead of reclaiming them when they are again referenced.
include/linux/mmzone.h | 1 + mm/cart.c | 41 ++++++++++++++++++++++++++++++++++++++--- 2 files changed, 39 insertions(+), 3 deletions(-)
mm/cart.c +40 -4
@@ -64,6 +64,7 @@#define cart_p ((zone)->nr_p)#define cart_q ((zone)->nr_q) +#define cart_r ((zone)->nr_r)#define size_B1 ((zone)->nr_evicted_active)#define size_B2 ((zone)->nr_evicted_inactive)
@@ -81,6 +82,7 @@ void __init cart_init(void) zone->nr_shortterm =0 ; zone->nr_p =0 ; zone->nr_q =0 ; + zone->nr_r =0 ; } }
@@ -123,6 +125,12 @@ void __cart_insert(struct zone *zone, st rflags =nonresident_find (page_mapping (page),page_index (page));if (rflags & NR_found) { + ratio = (nr_Nl / (nr_Ns +1 )) ?:1 ; +if (cart_r > ratio) + cart_r -= ratio; +else + cart_r =0UL ; + rflags &= NR_listid;if (rflags == NR_b1) {if (likely (size_B1)) --size_B1;
@@ -149,6 +157,11 @@ void __cart_insert(struct zone *zone, st }/* ++nr_Nl; */ }else { + ratio = (nr_Ns / (nr_Nl +1 )) ?:1 ; + cart_r += ratio; +if (cart_r > cart_cT) + cart_r = cart_cT; +ClearPageLongTerm (page); ++nr_Ns; }
@@ -355,12 +368,14 @@ static int cart_rebalance_T2(struct zone/* * Rebalance the T1 list: +* take 'new' 'L' pages for reclaim when r < nl, * move referenced pages to tail and possibly mark 'L', * move unreffed 'L' pages to tail T2, * take unreffed 'S' pages for reclaim. * * @zone: target zone. * @l_t1_head: temp list of reclaimable pages (1 ref). +* @l_new: temp list of 'new' pages. * @nr_dst: quantum of pages. * @nr_scanned: counter that keeps the number of pages touched. * @pvec: pagevec used to release pages.
@@ -369,6 +384,7 @@ static int cart_rebalance_T2(struct zone* returns if we encountered more PG_writeback pages than reclaimable pages. */ static int cart_rebalance_T1 (struct zone *zone,struct list_head *l_t1_head, +struct list_head *l_new,unsigned long nr_dst,unsigned long *nr_scanned,struct pagevec *pvec,int ignore_token) {
@@ -394,8 +410,13 @@ static int cart_rebalance_T1(struct zone referenced =page_referenced (page,0 , ignore_token); new =TestClearPageNew (page); -if (referenced || - (PageWriteback (page) && ++nr_writeback)) { +if (cart_r < (nr_Nl + dsl) &&PageLongTerm (page) && new) { +list_move_tail (&page->lru, l_new); +ClearPageActive (page); + ++dq; + ++nr_reclaim; + }else if (referenced || + (PageWriteback (page) && ++nr_writeback)) {list_move_tail (&page->lru, &l_t1);// XXX: we race a bit here;
@@ -432,6 +453,7 @@ static int cart_rebalance_T1(struct zone/* * Try to reclaim a specified number of pages. +* Prefer 'new' pages when available, otherwise let p be the judge. * * Clears PG_lru of reclaimed pages, but does take 1 reference. *
@@ -448,6 +470,7 @@ unsigned long cart_replace(struct zone * int ignore_token) {struct page *page; +LIST_HEAD (l_new);LIST_HEAD (l_t1);LIST_HEAD (l_t2);struct pagevec pvec;
@@ -472,13 +495,26 @@ unsigned long cart_replace(struct zone * wr2 =cart_rebalance_T2 (zone, &l_t2, nr_dst/2 , nr_scanned, &pvec, ignore_token);if (list_empty (&l_t1)) - wr1 =cart_rebalance_T1 (zone, &l_t1, nr_dst/2 , nr_scanned, + wr1 =cart_rebalance_T1 (zone, &l_t1, &l_new, nr_dst/2 , nr_scanned, &pvec, ignore_token);if (list_empty (&l_t1) &&list_empty (&l_t2))break ;spin_lock_irq (&zone->lru_lock); +while (!list_empty (&l_new) && nr < nr_dst) { + page =head_to_page (&l_new); +prefetchw_next_lru_page (page, &l_new, flags); + +if (!TestClearPageLRU (page)) +BUG (); +if (!PageLongTerm (page)) +BUG (); +/* --nr_Nl; */ + --size_T2; + ++nr; +list_move (&page->lru, dst); + }while (!list_empty (&l_t1) && (size_T1 > cart_p || !size_T2 || wr2) && nr < nr_dst) { page =head_to_page (&l_t1);
@@ -515,6 +551,7 @@ unsigned long cart_replace(struct zone *spin_lock_irq (&zone->lru_lock);__cart_list_splice_release (zone, &l_t1, list_T1, &pvec);__cart_list_splice_release (zone, &l_t2, list_T2, &pvec); +__cart_list_splice_release (zone, &l_new, list_T2, &pvec);spin_unlock_irq (&zone->lru_lock);pagevec_release (&pvec);
@@ -562,7 +599,6 @@ void cart_reinsert(struct zone *zone, stlist_move_tail (&page->lru, list_T1); ++size_T1; -/* ( |T1| >= min(p + 1, |B1| ) and ( filter = 'S' ) */ /* * Don't modify page state; it wasn't actually referenced */
include/linux/mmzone.h +1 -0
@@ -155,6 +155,7 @@ struct zone {unsigned long nr_shortterm;/* number of short term pages */ unsigned long nr_p;/* p from the CART paper */ unsigned long nr_q;/* q from the cart paper */ +unsigned long nr_r;unsigned long pages_scanned;/* since last reclaim */ int all_unreclaimable;/* All pages pinned */
--
--
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>
PATCH 5/7 CART - an advanced page replacement policy
In reply to Peter ZijlstraAdds some /proc debugging information to the CART patch.
fs/proc/proc_misc.c | 15 ++++++++ mm/cart.c | 93 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 108 insertions(+)
fs/proc/proc_misc.c +15 -0
@@ -233,6 +233,20 @@ static struct file_operations proc_zonei .release = seq_release, }; +extern struct seq_operations cart_op; +static int cart_open (struct inode *inode,struct file *file) +{ + (void )inode; +return seq_open (file, &cart_op); +} + +static struct file_operations cart_file_operations = { + .open = cart_open, + .read = seq_read, + .llseek = seq_lseek, + .release = seq_release, +}; +extern struct seq_operations nonresident_op;static int nonresident_open (struct inode *inode,struct file *file) {
@@ -616,6 +630,7 @@ void __init proc_misc_init(void)create_seq_entry ("interrupts" ,0 , &proc_interrupts_operations);create_seq_entry ("slabinfo" ,S_IWUSR |S_IRUGO ,&proc_slabinfo_operations);create_seq_entry ("buddyinfo" ,S_IRUGO , &fragmentation_file_operations); +create_seq_entry ("cart" ,S_IRUGO , &cart_file_operations);create_seq_entry ("nonresident" ,S_IRUGO , &nonresident_file_operations);create_seq_entry ("vmstat" ,S_IRUGO , &proc_vmstat_file_operations);create_seq_entry ("zoneinfo" ,S_IRUGO , &proc_zoneinfo_file_operations);
mm/cart.c +93 -0
96 lines not on this page · raw message
--
--
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>
PATCH 6/7 CART - an advanced page replacement policy
In reply to Peter ZijlstraThis patch started live as a rework of the use-once code by Rik van Riel. I (ab)used it to remove the use-once code.
mm/filemap.c | 10 +--------- mm/shmem.c | 7 ++----- mm/swap.c | 27 +-------------------------- mm/swapfile.c | 4 ++-- mm/vmscan.c | 25 ++----------------------- 5 files changed, 8 insertions(+), 65 deletions(-)
mm/filemap.c +1 -9
@@ -723,7 +723,6 @@ void do_generic_mapping_read(struct addrunsigned long offset;unsigned long last_index;unsigned long next_index; -unsigned long prev_index;loff_t isize;struct page *cached_page;int error;
@@ -732,7 +731,6 @@ void do_generic_mapping_read(struct addr cached_page =NULL ; index = *ppos >>PAGE_CACHE_SHIFT ; next_index = index; - prev_index = ra.prev_page; last_index = (*ppos + desc->count +PAGE_CACHE_SIZE -1 ) >>PAGE_CACHE_SHIFT ; offset = *ppos & ~PAGE_CACHE_MASK ;
@@ -779,13 +777,7 @@ page_ok:if (mapping_writably_mapped (mapping))flush_dcache_page (page); -/* -* When (part of) the same page is read multiple times -* in succession, only mark it as accessed the first time. -*/ -if (prev_index != index) -mark_page_accessed (page); - prev_index = index; +mark_page_accessed (page);/* * Ok, we have the page, and it's up-to-date, so
mm/shmem.c +2 -5
@@ -1500,11 +1500,8 @@ static void do_shmem_file_read(struct fi*/ if (mapping_writably_mapped (mapping))flush_dcache_page (page); -/* -* Mark the page accessed if we read the beginning. -*/ -if (!offset) -mark_page_accessed (page); + +mark_page_accessed (page); }else page =ZERO_PAGE (0 );
mm/swap.c +1 -26
@@ -97,37 +97,12 @@ int rotate_reclaimable_page(struct page }/* -* FIXME: speed this up? -*/ -void fastcall activate_page(struct page *page) -{ -struct zone *zone =page_zone (page); - -spin_lock_irq (&zone->lru_lock); -if (PageLRU (page) && !PageActive (page)) { -del_page_from_inactive_list (zone, page); -SetPageActive (page); -add_page_to_active_list (zone, page); -inc_page_state (pgactivate); - } -spin_unlock_irq (&zone->lru_lock); -} - -/* * Mark a page as having seen activity. -* -* inactive,unreferenced -> inactive,referenced -* inactive,referenced -> active,unreferenced -* active,unreferenced -> active,referenced */ void fastcall mark_page_accessed(struct page *page) { -if (!PageActive (page) &&PageReferenced (page) &&PageLRU (page)) { -activate_page (page); -ClearPageReferenced (page); - }else if (!PageReferenced (page)) { +if (!PageReferenced (page))SetPageReferenced (page); - } }EXPORT_SYMBOL (mark_page_accessed);
mm/swapfile.c +2 -2
@@ -408,7 +408,7 @@ static void unuse_pte(struct vm_area_str* Move the page to the active list so it is not * immediately swapped out again after swapon. */ -activate_page (page); +SetPageReferenced (page); } static int unuse_pte_range(struct vm_area_struct *vma, pmd_t *pmd,
@@ -508,7 +508,7 @@ static int unuse_mm(struct mm_struct *mm* Activate page so shrink_cache is unlikely to unmap its * ptes while lock is dropped, so swapoff can make progress. */ -activate_page (page); +SetPageReferenced (page);unlock_page (page);down_read (&mm->mmap_sem);lock_page (page);
mm/vmscan.c +2 -23
@@ -235,27 +235,6 @@ static int shrink_slab(unsigned long scareturn ret; } -/* Called without lock on whether page is mapped, so answer is unstable */ -static inline int page_mapping_inuse (struct page *page) -{ -struct address_space *mapping; - -/* Page is in somebody's page tables. */ -if (page_mapped (page)) -return 1 ; - -/* Be more reluctant to reclaim swapcache than pagecache */ -if (PageSwapCache (page)) -return 1 ; - - mapping =page_mapping (page); -if (!mapping) -return 0 ; - -/* File is mmap'd by somebody? */ -return mapping_mapped (mapping); -} -static inline int is_page_cache_freeable (struct page *page) {return page_count (page) - !!PagePrivate (page) ==2 ;
@@ -408,8 +387,8 @@ static int shrink_list(struct list_head goto keep_locked; referenced =page_referenced (page,1 , sc->priority <=0 ); -/* In active use or really unfreeable? Activate it. */ -if (referenced &&page_mapping_inuse (page)) + +if (referenced) goto activate_locked;#ifdef CONFIG_SWAP
--
--
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>
PATCH 7/7 CART - an advanced page replacement policy
In reply to Peter ZijlstraRemove most of the current page replacement code and make use of the new CART code.
fs/exec.c | 2 include/linux/swap.h | 2 mm/memory.c | 7 - mm/swap.c | 55 ---------- mm/swap_state.c | 2 mm/vmscan.c | 262 +++------------------------------------------------ 6 files changed, 28 insertions(+), 302 deletions(-)
fs/exec.c +1 -1
@@ -331,7 +331,7 @@ void install_arg_page(struct vm_area_str goto out; }inc_mm_counter (mm, rss); -lru_cache_add_active (page); +lru_cache_add (page);set_pte_at (mm, address, pte,pte_mkdirty (pte_mkwrite (mk_pte ( page, vma->vm_page_prot))));page_add_anon_rmap (page, vma, address);
include/linux/swap.h +0 -2
@@ -201,8 +201,6 @@ extern unsigned int nr_free_pagecache_pa/* linux/mm/swap.c */ extern void FASTCALL (lru_cache_add (struct page *)); -extern void FASTCALL (lru_cache_add_active (struct page *)); -extern void FASTCALL (activate_page (struct page *));extern void FASTCALL (mark_page_accessed (struct page *));extern void lru_add_drain (void );extern int rotate_reclaimable_page (struct page *page);
mm/memory.c +3 -4
@@ -1304,7 +1304,7 @@ static int do_wp_page(struct mm_struct *page_remove_rmap (old_page);flush_cache_page (vma, address, pfn);break_cow (vma, new_page, address, page_table); -lru_cache_add_active (new_page); +lru_cache_add (new_page);page_add_anon_rmap (new_page, vma, address);/* Free the old page.. */
@@ -1782,8 +1782,7 @@ do_anonymous_page(struct mm_struct *mm, entry =maybe_mkwrite (pte_mkdirty (mk_pte (page, vma->vm_page_prot)), vma); -lru_cache_add_active (page); -SetPageReferenced (page); +lru_cache_add (page);page_add_anon_rmap (page, vma, addr); }
@@ -1903,7 +1902,7 @@ retry: entry =maybe_mkwrite (pte_mkdirty (entry), vma);set_pte_at (mm, address, page_table, entry);if (anon) { -lru_cache_add_active (new_page); +lru_cache_add (new_page);page_add_anon_rmap (new_page, vma, address); }else page_add_file_rmap (new_page);
mm/swap.c +5 -50
102 lines not on this page · raw message
mm/swap_state.c +1 -1
@@ -359,7 +359,7 @@ struct page *read_swap_cache_async(swp_e/* * Initiate read into locked page and return. */ -lru_cache_add_active (new_page); +lru_cache_add (new_page);swap_readpage (NULL , new_page);return new_page; }
mm/vmscan.c +28 -248
375 lines not on this page · raw message
--
--
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>
Quoted 5 lines · Peter Zijlstra
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)
Peter, this is a large patch, perhaps you could describe what configs benefit, how much, and what the right to use status of the patent might be. In other words, why would a reader of LKML put in this patch and try it?
The description of how it works is clear, but the problem solved isn't.
Signature · 3 lines
-bill davidsen ([email protected]) "The secret to procrastination is to put things off until the last possible moment - but no longer" -me
Quoted 9 lines · Bill Davidsen
Quoted 5 lines · Peter Zijlstra
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)Peter, this is a large patch, perhaps you could describe what configs benefit,
All those that use swap. Those that exploit the weak side of LRU more than others.
CART is an adaptive algorithm that will act like LFU on one side and LRU on the other, capturing both behaviours. Therefore it is also scan proof, eg. 'use once' scans should not flush the full cache.
Hence people with LFU friendly applications will see an improvement while those who have an LRU friendly application should see no decrease in swap performance.
Non of the algorithms handle cyclic access very well, that is what patch 5 tries to tackle.
Quoted 1 line
how much,
In the cyclic case (n+a: a << n) I've seen speedups of over 300%. Other cases much less. However I've yet to encounter a case where it gives worse performance.
I'm still constructing some corner case tests to give more hard numbers.
Quoted 2 lines
and what the right to use status of the patent might be.
AFAIK IBM allows Linux implementation of their patents.
See: http://news.com.com/IBM+pledges+no+patent+attacks+against+Linux/2100-7344_3-5296787.html
Quoted 2 lines
In other words, why would a reader of LKML put in this patch and try it? The description of how it works is clear, but the problem solved isn't.
I hope to have answered these questions. If any questions still remain, please let me know.
Kind regards,
Peter Zijlstra
Signature · 7 lines
Peter Zijlstra <[email protected]> -- 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>
Quoted 54 lines · Peter Zijlstra
Quoted 13 lines · Bill Davidsen
Quoted 7 lines · Peter Zijlstra
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)Peter, this is a large patch, perhaps you could describe what configs benefit,
All those that use swap. Those that exploit the weak side of LRU more than others.
CART is an adaptive algorithm that will act like LFU on one side and LRU on the other, capturing both behaviours. Therefore it is also scan proof, eg. 'use once' scans should not flush the full cache.
Hence people with LFU friendly applications will see an improvement while those who have an LRU friendly application should see no decrease in swap performance.
Non of the algorithms handle cyclic access very well, that is what patch 5 tries to tackle.
Quoted 3 lines
how much,
In the cyclic case (n+a: a << n) I've seen speedups of over 300%. Other cases much less. However I've yet to encounter a case where it gives worse performance.
I'm still constructing some corner case tests to give more hard numbers.
Quoted 3 lines
and what the right to use status of the patent might be.
AFAIK IBM allows Linux implementation of their patents.
See: http://news.com.com/IBM+pledges+no+patent+attacks+against+Linux/2100-7344_3-5296787.html
Quoted 8 lines
Quoted 4 lines
In other words, why would a reader of LKML put in this patch and try it? The description of how it works is clear, but the problem solved isn't.
I hope to have answered these questions. If any questions still remain, please let me know.
Thanks, you have cleared up all of the issues which I felt were unclear.
Signature · 3 lines
bill davidsen <[email protected]> CTO TMR Associates, Inc Doing interesting things with small computers since 1979