Re: [RFC 6/8] In order putback lru core

From: Minchan Kim
Date: Wed Apr 27 2011 - 00:20:10 EST

Next message: Minchan Kim: "Re: [RFC 8/8] compaction: make compaction use in-order putback"
Previous message: Jidong Xiao: "Re: How to export information larger than PROC_BLOCK_SIZE via /procfile system?"
In reply to: Minchan Kim: "[RFC 6/8] In order putback lru core"
Next in thread: KAMEZAWA Hiroyuki: "Re: [RFC 6/8] In order putback lru core"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

On Wed, Apr 27, 2011 at 1:25 AM, Minchan Kim <minchan.kim@xxxxxxxxx> wrote:
> This patch defines new APIs to putback the page into previous position of LRU.
> The idea is simple.
>
> When we try to putback the page into lru list and if friends(prev, next) of the pages
> still is nearest neighbor, we can insert isolated page into prev's next instead of
> head of LRU list. So it keeps LRU history without losing the LRU information.
>
> Before :
> Â Â Â ÂLRU POV : H - P1 - P2 - P3 - P4 -T
>
> Isolate P3 :
> Â Â Â ÂLRU POV : H - P1 - P2 - P4 - T
>
> Putback P3 :
> Â Â Â Âif (P2->next == P4)
> Â Â Â Â Â Â Â Âputback(P3, P2);
> Â Â Â ÂSo,
> Â Â Â ÂLRU POV : H - P1 - P2 - P3 - P4 -T
>
> For implement, we defines new structure pages_lru which remebers
> both lru friend pages of isolated one and handling functions.
>
> But this approach has a problem on contiguous pages.
> In this case, my idea can not work since friend pages are isolated, too.
> It means prev_page->next == next_page always is false and both pages are not
> LRU any more at that time. It's pointed out by Rik at LSF/MM summit.
> So for solving the problem, I can change the idea.
> I think we don't need both friend(prev, next) pages relation but
> just consider either prev or next page that it is still same LRU.
> Worset case in this approach, prev or next page is free and allocate new
> so it's in head of LRU and our isolated page is located on next of head.
> But it's almost same situation with current problem. So it doesn't make worse
> than now and it would be rare. But in this version, I implement based on idea
> discussed at LSF/MM. If my new idea makes sense, I will change it.
>
> Any comment?
>
> Cc: KOSAKI Motohiro <kosaki.motohiro@xxxxxxxxxxxxxx>
> Cc: Mel Gorman <mgorman@xxxxxxx>
> Cc: Rik van Riel <riel@xxxxxxxxxx>
> Cc: Andrea Arcangeli <aarcange@xxxxxxxxxx>
> Signed-off-by: Minchan Kim <minchan.kim@xxxxxxxxx>
> ---
> Âinclude/linux/migrate.h Â| Â Â2 +
> Âinclude/linux/mm_types.h | Â Â7 ++++
> Âinclude/linux/swap.h Â Â | Â Â4 ++-
> Âmm/compaction.c Â Â Â Â Â| Â Â3 +-
> Âmm/internal.h Â Â Â Â Â Â| Â Â2 +
> Âmm/memcontrol.c Â Â Â Â Â| Â Â2 +-
> Âmm/migrate.c Â Â Â Â Â Â | Â 36 +++++++++++++++++++++
> Âmm/swap.c Â Â Â Â Â Â Â Â| Â Â2 +-
> Âmm/vmscan.c Â Â Â Â Â Â Â| Â 79 +++++++++++++++++++++++++++++++++++++++++++--
> Â9 files changed, 129 insertions(+), 8 deletions(-)
>
> diff --git a/include/linux/migrate.h b/include/linux/migrate.h
> index e39aeec..3aa5ab6 100644
> --- a/include/linux/migrate.h
> +++ b/include/linux/migrate.h
> @@ -9,6 +9,7 @@ typedef struct page *new_page_t(struct page *, unsigned long private, int **);
> Â#ifdef CONFIG_MIGRATION
> Â#define PAGE_MIGRATION 1
>
> +extern void putback_pages_lru(struct list_head *l);
> Âextern void putback_lru_pages(struct list_head *l);
> Âextern int migrate_page(struct address_space *,
> Â Â Â Â Â Â Â Â Â Â Â Âstruct page *, struct page *);
> @@ -33,6 +34,7 @@ extern int migrate_huge_page_move_mapping(struct address_space *mapping,
> Â#else
> Â#define PAGE_MIGRATION 0
>
> +static inline void putback_pages_lru(struct list_head *l) {}
> Âstatic inline void putback_lru_pages(struct list_head *l) {}
> Âstatic inline int migrate_pages(struct list_head *l, new_page_t x,
> Â Â Â Â Â Â Â Âunsigned long private, bool offlining,
> diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h
> index ca01ab2..35e80fb 100644
> --- a/include/linux/mm_types.h
> +++ b/include/linux/mm_types.h
> @@ -102,6 +102,13 @@ struct page {
> Â#endif
> Â};
>
> +/* This structure is used for keeping LRU ordering of isolated page */
> +struct pages_lru {
> + Â Â Â Âstruct page *page; Â Â Â/* isolated page */
> + Â Â Â Âstruct page *prev_page; /* previous page of isolate page as LRU order */
> + Â Â Â Âstruct page *next_page; /* next page of isolate page as LRU order */
> + Â Â Â Âstruct list_head lru;
> +};
> Â/*
> Â* A region containing a mapping of a non-memory backed file under NOMMU
> Â* conditions. ÂThese are held in a global tree and are pinned by the VMAs that
> diff --git a/include/linux/swap.h b/include/linux/swap.h
> index baef4ad..4ad0a0c 100644
> --- a/include/linux/swap.h
> +++ b/include/linux/swap.h
> @@ -227,6 +227,8 @@ extern void rotate_reclaimable_page(struct page *page);
> Âextern void deactivate_page(struct page *page);
> Âextern void swap_setup(void);
>
> +extern void update_page_reclaim_stat(struct zone *zone, struct page *page,
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Âint file, int rotated);
> Âextern void add_page_to_unevictable_list(struct page *page);
>
> Â/**
> @@ -260,7 +262,7 @@ extern unsigned long mem_cgroup_shrink_node_zone(struct mem_cgroup *mem,
> Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Âstruct zone *zone,
> Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Âunsigned long *nr_scanned);
> Âextern int __isolate_lru_page(struct page *page, int mode, int file,
> - Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â int not_dirty, int not_mapped);
> + Â Â Â Â Â Â Â int not_dirty, int not_mapped, struct pages_lru *pages_lru);
> Âextern unsigned long shrink_all_memory(unsigned long nr_pages);
> Âextern int vm_swappiness;
> Âextern int remove_mapping(struct address_space *mapping, struct page *page);
> diff --git a/mm/compaction.c b/mm/compaction.c
> index 653b02b..c453000 100644
> --- a/mm/compaction.c
> +++ b/mm/compaction.c
> @@ -335,7 +335,8 @@ static unsigned long isolate_migratepages(struct zone *zone,
> Â Â Â Â Â Â Â Â}
>
> Â Â Â Â Â Â Â Â/* Try isolate the page */
> - Â Â Â Â Â Â Â if (__isolate_lru_page(page, ISOLATE_BOTH, 0, !cc->sync, 0) != 0)
> + Â Â Â Â Â Â Â if (__isolate_lru_page(page, ISOLATE_BOTH, 0,
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â !cc->sync, 0, NULL) != 0)
> Â Â Â Â Â Â Â Â Â Â Â Âcontinue;
>
> Â Â Â Â Â Â Â ÂVM_BUG_ON(PageTransCompound(page));
> diff --git a/mm/internal.h b/mm/internal.h
> index d071d38..3c8182c 100644
> --- a/mm/internal.h
> +++ b/mm/internal.h
> @@ -43,6 +43,8 @@ extern unsigned long highest_memmap_pfn;
> Â* in mm/vmscan.c:
> Â*/
> Âextern int isolate_lru_page(struct page *page);
> +extern bool keep_lru_order(struct pages_lru *pages_lru);
> +extern void putback_page_to_lru(struct page *page, struct list_head *head);
> Âextern void putback_lru_page(struct page *page);
>
> Â/*
> diff --git a/mm/memcontrol.c b/mm/memcontrol.c
> index 471e7fd..92a9046 100644
> --- a/mm/memcontrol.c
> +++ b/mm/memcontrol.c
> @@ -1193,7 +1193,7 @@ unsigned long mem_cgroup_isolate_pages(unsigned long nr_to_scan,
> Â Â Â Â Â Â Â Â Â Â Â Âcontinue;
>
> Â Â Â Â Â Â Â Âscan++;
> - Â Â Â Â Â Â Â ret = __isolate_lru_page(page, mode, file, 0, 0);
> + Â Â Â Â Â Â Â ret = __isolate_lru_page(page, mode, file, 0, 0, NULL);
> Â Â Â Â Â Â Â Âswitch (ret) {
> Â Â Â Â Â Â Â Âcase 0:
> Â Â Â Â Â Â Â Â Â Â Â Âlist_move(&page->lru, dst);
> diff --git a/mm/migrate.c b/mm/migrate.c
> index 819d233..9cfb63b 100644
> --- a/mm/migrate.c
> +++ b/mm/migrate.c
> @@ -85,6 +85,42 @@ void putback_lru_pages(struct list_head *l)
> Â}
>
> Â/*
> + * This function is almost same iwth putback_lru_pages.
> + * The difference is that function receives struct pages_lru list
> + * and if possible, we add pages into original position of LRU
> + * instead of LRU's head.
> + */
> +void putback_pages_lru(struct list_head *l)
> +{
> + Â Â Â Âstruct pages_lru *isolated_page;
> + Â Â Â Âstruct pages_lru *isolated_page2;
> + Â Â Â Âstruct page *page;
> +
> + Â Â Â Âlist_for_each_entry_safe(isolated_page, isolated_page2, l, lru) {
> + Â Â Â Â Â Â Â Âstruct zone *zone;
> + Â Â Â Â Â Â Â Âpage = isolated_page->page;
> + Â Â Â Â Â Â Â Âlist_del(&isolated_page->lru);
> +
> + Â Â Â Â Â Â Â Âdec_zone_page_state(page, NR_ISOLATED_ANON +
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Âpage_is_file_cache(page));
> +
> + Â Â Â Â Â Â Â Âzone = page_zone(page);
> + Â Â Â Â Â Â Â Âspin_lock_irq(&zone->lru_lock);
> + Â Â Â Â Â Â Â Âif (keep_lru_order(isolated_page)) {
> + Â Â Â Â Â Â Â Â Â Â Â Âputback_page_to_lru(page, &isolated_page->prev_page->lru);
> + Â Â Â Â Â Â Â Â Â Â Â Âspin_unlock_irq(&zone->lru_lock);
> + Â Â Â Â Â Â Â Â}
> + Â Â Â Â Â Â Â Âelse {
> + Â Â Â Â Â Â Â Â Â Â Â Âspin_unlock_irq(&zone->lru_lock);
> + Â Â Â Â Â Â Â Â Â Â Â Âputback_lru_page(page);
> + Â Â Â Â Â Â Â Â}
> +
> + Â Â Â Â Â Â Â Âkfree(isolated_page);
> + Â Â Â Â}
> +}
> +
> +
> +/*
> Â* Restore a potential migration pte to a working pte entry
> Â*/
> Âstatic int remove_migration_pte(struct page *new, struct vm_area_struct *vma,
> diff --git a/mm/swap.c b/mm/swap.c
> index a83ec5a..0cb15b7 100644
> --- a/mm/swap.c
> +++ b/mm/swap.c
> @@ -252,7 +252,7 @@ void rotate_reclaimable_page(struct page *page)
> Â Â Â Â}
> Â}
>
> -static void update_page_reclaim_stat(struct zone *zone, struct page *page,
> +void update_page_reclaim_stat(struct zone *zone, struct page *page,
> Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â int file, int rotated)
> Â{
> Â Â Â Âstruct zone_reclaim_stat *reclaim_stat = &zone->reclaim_stat;
> diff --git a/mm/vmscan.c b/mm/vmscan.c
> index 5196f0c..06a7c9b 100644
> --- a/mm/vmscan.c
> +++ b/mm/vmscan.c
> @@ -550,6 +550,58 @@ int remove_mapping(struct address_space *mapping, struct page *page)
> Â Â Â Âreturn 0;
> Â}
>
> +/* zone->lru_lock must be hold */
> +bool keep_lru_order(struct pages_lru *pages_lru)
> +{
> + Â Â Â Âbool ret = false;
> + Â Â Â Âstruct page *prev, *next;
> +
> + Â Â Â Âif (!pages_lru->prev_page)
> + Â Â Â Â Â Â Â Âreturn ret;
> +
> + Â Â Â Âprev = pages_lru->prev_page;
> + Â Â Â Ânext = pages_lru->next_page;
> +
> + Â Â Â Âif (!PageLRU(prev) || !PageLRU(next))
> + Â Â Â Â Â Â Â Âreturn ret;
> +
> + Â Â Â Âif (prev->lru.next == &next->lru)
> + Â Â Â Â Â Â Â Âret = true;
> +
> + Â Â Â if (unlikely(PageUnevictable(prev)))
> + Â Â Â Â Â Â Â ret = false;
> +
> + Â Â Â Âreturn ret;
> +}
> +
> +/**
> + * putback_page_to_lru - put isolated @page onto @head
> + * @page: page to be put back to appropriate lru list
> + * @head: lru position to be put back
> + *
> + * Insert previously isolated @page to appropriate position of lru list
> + * zone->lru_lock must be hold.
> + */
> +void putback_page_to_lru(struct page *page, struct list_head *head)
> +{
> + Â Â Â Âint lru, active, file;
> + Â Â Â Âstruct zone *zone = page_zone(page);
> + Â Â Â Âstruct page *prev_page = container_of(head, struct page, lru);
> +
> + Â Â Â Âlru = page_lru(prev_page);
> + Â Â Â Âactive = is_active_lru(lru);
> + Â Â Â Âfile = is_file_lru(lru);
> +
> + Â Â Â Âif (active)
> + Â Â Â Â Â Â Â ÂSetPageActive(page);
> + Â Â Â else
> + Â Â Â Â Â Â Â ClearPageActive(page);
> +
> + Â Â Â Âupdate_page_reclaim_stat(zone, page, file, active);
> + Â Â Â ÂSetPageLRU(page);
> + Â Â Â Â__add_page_to_lru_list(zone, page, lru, head);
> +}
> +
> Â/**
> Â* putback_lru_page - put previously isolated page onto appropriate LRU list's head
> Â* @page: page to be put back to appropriate lru list
> @@ -959,8 +1011,8 @@ keep_lumpy:
> Â* not_mapped: page should be not mapped
> Â* returns 0 on success, -ve errno on failure.
> Â*/
> -int __isolate_lru_page(struct page *page, int mode, int file,
> - Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â int not_dirty, int not_mapped)
> +int __isolate_lru_page(struct page *page, int mode, int file, int not_dirty,
> + Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â int not_mapped, struct pages_lru *pages_lru)
> Â{
> Â Â Â Âint ret = -EINVAL;
>
> @@ -996,12 +1048,31 @@ int __isolate_lru_page(struct page *page, int mode, int file,
> Â Â Â Âret = -EBUSY;
>
> Â Â Â Âif (likely(get_page_unless_zero(page))) {
> + Â Â Â Â Â Â Â struct zone *zone = page_zone(page);
> + Â Â Â Â Â Â Â enum lru_list l = page_lru(page);
> Â Â Â Â Â Â Â Â/*
> Â Â Â Â Â Â Â Â * Be careful not to clear PageLRU until after we're
> Â Â Â Â Â Â Â Â * sure the page is not being freed elsewhere -- the
> Â Â Â Â Â Â Â Â * page release code relies on it.
> Â Â Â Â Â Â Â Â */
> Â Â Â Â Â Â Â ÂClearPageLRU(page);
> +
> + Â Â Â Â Â Â Â if (!pages_lru)
> + Â Â Â Â Â Â Â Â Â Â Â goto skip;
> +
> + Â Â Â Â Â Â Â pages_lru->page = page;
> + Â Â Â Â Â Â Â if (&zone->lru[l].list == pages_lru->lru.prev ||
> + Â Â Â Â Â Â Â Â Â Â Â &zone->lru[l].list == pages_lru->lru.next) {
> + Â Â Â Â Â Â Â Â Â Â Â pages_lru->prev_page = NULL;
> + Â Â Â Â Â Â Â Â Â Â Â pages_lru->next_page = NULL;
> + Â Â Â Â Â Â Â Â Â Â Â goto skip;
> + Â Â Â Â Â Â Â }

While I was refactoring the code, I might got sleep.
It should be following as,

@@ -1071,8 +1072,8 @@ int __isolate_lru_page(struct page *page, int
mode, int file, int not_dirty,
goto skip;

pages_lru->page = page;
- if (&zone->lru[l].list == pages_lru->lru.prev ||
- &zone->lru[l].list == pages_lru->lru.next) {
+ if (&zone->lru[l].list == page->lru.prev ||
+ &zone->lru[l].list == page->lru.next) {
pages_lru->prev_page = NULL;
pages_lru->next_page = NULL;
goto skip;

--
Kind regards,
Minchan Kim
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Next message: Minchan Kim: "Re: [RFC 8/8] compaction: make compaction use in-order putback"
Previous message: Jidong Xiao: "Re: How to export information larger than PROC_BLOCK_SIZE via /procfile system?"
In reply to: Minchan Kim: "[RFC 6/8] In order putback lru core"
Next in thread: KAMEZAWA Hiroyuki: "Re: [RFC 6/8] In order putback lru core"
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]