lkml.org 
[lkml]   [2005]   [Sep]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[PATCH 3/7] CART - an advanced page replacement policy
    The flesh of the CART implementation. Again comments in the file should be
    clear.

    Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>

    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(-)

    Index: linux-2.6-git/mm/cart.c
    ===================================================================
    --- /dev/null
    +++ linux-2.6-git/mm/cart.c
    @@ -0,0 +1,639 @@
    +/*
    + * mm/cart.c
    + *
    + * Written by Peter Zijlstra <a.p.zijlstra@chello.nl>
    + * 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;
    + }
    +}
    Index: linux-2.6-git/include/linux/mm_inline.h
    ===================================================================
    --- linux-2.6-git.orig/include/linux/mm_inline.h
    +++ linux-2.6-git/include/linux/mm_inline.h
    @@ -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--;
    + }
    }
    Index: linux-2.6-git/include/linux/mmzone.h
    ===================================================================
    --- linux-2.6-git.orig/include/linux/mmzone.h
    +++ linux-2.6-git/include/linux/mmzone.h
    @@ -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 */

    Index: linux-2.6-git/include/linux/page-flags.h
    ===================================================================
    --- linux-2.6-git.orig/include/linux/page-flags.h
    +++ linux-2.6-git/include/linux/page-flags.h
    @@ -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);
    Index: linux-2.6-git/include/linux/swap.h
    ===================================================================
    --- linux-2.6-git.orig/include/linux/swap.h
    +++ linux-2.6-git/include/linux/swap.h
    @@ -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(in
    extern 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;
    Index: linux-2.6-git/init/main.c
    ===================================================================
    --- linux-2.6-git.orig/init/main.c
    +++ linux-2.6-git/init/main.c
    @@ -497,6 +497,7 @@ asmlinkage void __init start_kernel(void
    vfs_caches_init_early();
    nonresident_init();
    mem_init();
    + cart_init();
    kmem_cache_init();
    setup_per_cpu_pageset();
    numa_policy_init();
    Index: linux-2.6-git/mm/Makefile
    ===================================================================
    --- linux-2.6-git.orig/mm/Makefile
    +++ linux-2.6-git/mm/Makefile
    @@ -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 from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2005-09-29 20:21    [W:8.795 / U:0.044 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site