lkml.org 
[lkml]   [2008]   [Oct]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[PATCH] mm: use a radix-tree to make do_move_pages() complexity linear
    Add a radix-tree in do_move_pages() to associate each page with
    the struct page_to_node that describes its migration.
    new_page_node() can now easily find out the page_to_node of the
    given page instead of traversing the whole page_to_node array.
    So the overall complexity is linear instead of quadratic.

    We still need the page_to_node array since it is allocated by the
    caller (sys_move_page()) and used by do_pages_stat() when no target
    nodes are given by the application. And we need room to store all
    these page_to_node entries for do_move_pages() as well anyway.

    If a page is given twice by the application, the old code would
    return -EBUSY (failure from the second isolate_lru_page()). Now,
    radix_tree_insert() will return -EEXIST, and we convert it back
    to -EBUSY to keep the user-space ABI.

    The radix-tree is emptied at the end of do_move_pages() since
    new_page_node() doesn't know when an entry is used for the last
    time (unmap_and_move() could try another pass later).
    Marking pp->page as ZERO_PAGE(0) was actually never used. We now
    set it to NULL when pp is not in the radix-tree. It is faster
    than doing a loop of radix_tree_lookup_gang()+delete().

    Signed-off-by: Brice Goglin <Brice.Goglin@inria.fr>
    Signed-off-by: Nathalie Furmento <Nathalie.Furmento@labri.fr>

    --- a/mm/migrate.c
    +++ b/mm/migrate.c
    @@ -31,6 +31,7 @@
    #include <linux/security.h>
    #include <linux/memcontrol.h>
    #include <linux/syscalls.h>
    +#include <linux/radix-tree.h>

    #include "internal.h"

    @@ -840,12 +841,10 @@ struct page_to_node {
    static struct page *new_page_node(struct page *p, unsigned long private,
    int **result)
    {
    - struct page_to_node *pm = (struct page_to_node *)private;
    + struct radix_tree_root *root = (struct radix_tree_root *) private;
    + struct page_to_node *pm = (struct page_to_node *) radix_tree_lookup(root, (unsigned long) p);

    - while (pm->node != MAX_NUMNODES && pm->page != p)
    - pm++;
    -
    - if (pm->node == MAX_NUMNODES)
    + if (!pm)
    return NULL;

    *result = &pm->status;
    @@ -865,6 +864,7 @@ static int do_move_pages(struct mm_struct *mm, struct page_to_node *pm,
    int err;
    struct page_to_node *pp;
    LIST_HEAD(pagelist);
    + RADIX_TREE(pmroot, GFP_KERNEL);

    down_read(&mm->mmap_sem);

    @@ -876,11 +876,8 @@ static int do_move_pages(struct mm_struct *mm, struct page_to_node *pm,
    struct vm_area_struct *vma;
    struct page *page;

    - /*
    - * A valid page pointer that will not match any of the
    - * pages that will be moved.
    - */
    - pp->page = ZERO_PAGE(0);
    + /* set to NULL as long as pp is not in the radix-tree */
    + pp->page = NULL;

    err = -EFAULT;
    vma = find_vma(mm, pp->addr);
    @@ -900,9 +897,7 @@ static int do_move_pages(struct mm_struct *mm, struct page_to_node *pm,
    if (PageReserved(page)) /* Check for zero page */
    goto put_and_set;

    - pp->page = page;
    err = page_to_nid(page);
    -
    if (err == pp->node)
    /*
    * Node already in the right place
    @@ -914,6 +909,23 @@ static int do_move_pages(struct mm_struct *mm, struct page_to_node *pm,
    !migrate_all)
    goto put_and_set;

    + /*
    + * Insert pp in the radix-tree so that new_page_node() can find it
    + * while only knowing the page.
    + * There cannot be any duplicate since isolate_lru_page() would fail
    + * below anyway.
    + */
    + err = radix_tree_insert(&pmroot, (unsigned long) page, pp);
    + if (err < 0) {
    + if (err == -EEXIST)
    + /* the page cannot be migrated twice */
    + err = -EBUSY;
    + goto put_and_set;
    + }
    +
    + /* set pp->page for real now that pp is in the radix-tree */
    + pp->page = page;
    +
    err = isolate_lru_page(page, &pagelist);
    put_and_set:
    /*
    @@ -927,12 +939,17 @@ set_status:
    }

    if (!list_empty(&pagelist))
    - err = migrate_pages(&pagelist, new_page_node,
    - (unsigned long)pm);
    + err = migrate_pages(&pagelist, new_page_node, (unsigned long) &pmroot);
    else
    err = -ENOENT;

    up_read(&mm->mmap_sem);
    +
    + /* empty the radix-tree now that new_page_node() will not be called anymore */
    + for(pp = pm; pp->node != MAX_NUMNODES; pp++)
    + if (pp->page)
    + radix_tree_delete(&pmroot, (unsigned long) pp->page);
    +
    return err;
    }




    \
     
     \ /
      Last update: 2008-10-09 14:33    [W:0.027 / U:32.736 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site