mm anon rmap: replace same_anon_vma linked list with an interval tree.

[deliverable/linux.git] / mm / rmap.c

diff --git a/mm/rmap.c b/mm/rmap.c
index 8cbd62fde0f18528a1eb7e15486bbc8995c70670..9c61bf387fd1bc369638a3c33b5457f4bedb5ec0 100644 (file)
--- a/mm/rmap.c
+++ b/mm/rmap.c
@@ -127,12 +127,7 @@ static void anon_vma_chain_link(struct vm_area_struct *vma,
        avc->vma = vma;
        avc->anon_vma = anon_vma;
        list_add(&avc->same_vma, &vma->anon_vma_chain);
-
-       /*
-        * It's critical to add new vmas to the tail of the anon_vma,
-        * see comment in huge_memory.c:__split_huge_page().
-        */
-       list_add_tail(&avc->same_anon_vma, &anon_vma->head);
+       anon_vma_interval_tree_insert(avc, &anon_vma->rb_root);
 }
 
 /**
@@ -336,13 +331,13 @@ void unlink_anon_vmas(struct vm_area_struct *vma)
                struct anon_vma *anon_vma = avc->anon_vma;
 
                root = lock_anon_vma_root(root, anon_vma);
-               list_del(&avc->same_anon_vma);
+               anon_vma_interval_tree_remove(avc, &anon_vma->rb_root);
 
                /*
                 * Leave empty anon_vmas on the list - we'll need
                 * to free them outside the lock.
                 */
-               if (list_empty(&anon_vma->head))
+               if (RB_EMPTY_ROOT(&anon_vma->rb_root))
                        continue;
 
                list_del(&avc->same_vma);
@@ -371,7 +366,7 @@ static void anon_vma_ctor(void *data)
 
        mutex_init(&anon_vma->mutex);
        atomic_set(&anon_vma->refcount, 0);
-       INIT_LIST_HEAD(&anon_vma->head);
+       anon_vma->rb_root = RB_ROOT;
 }
 
 void __init anon_vma_init(void)
@@ -724,6 +719,7 @@ static int page_referenced_anon(struct page *page,
 {
        unsigned int mapcount;
        struct anon_vma *anon_vma;
+       pgoff_t pgoff;
        struct anon_vma_chain *avc;
        int referenced = 0;
 
@@ -732,7 +728,8 @@ static int page_referenced_anon(struct page *page,
                return referenced;
 
        mapcount = page_mapcount(page);
-       list_for_each_entry(avc, &anon_vma->head, same_anon_vma) {
+       pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
+       anon_vma_interval_tree_foreach(avc, &anon_vma->rb_root, pgoff, pgoff) {
                struct vm_area_struct *vma = avc->vma;
                unsigned long address = vma_address(page, vma);
                if (address == -EFAULT)
@@ -1445,6 +1442,7 @@ bool is_vma_temporary_stack(struct vm_area_struct *vma)
 static int try_to_unmap_anon(struct page *page, enum ttu_flags flags)
 {
        struct anon_vma *anon_vma;
+       pgoff_t pgoff;
        struct anon_vma_chain *avc;
        int ret = SWAP_AGAIN;
 
@@ -1452,7 +1450,8 @@ static int try_to_unmap_anon(struct page *page, enum ttu_flags flags)
        if (!anon_vma)
                return ret;
 
-       list_for_each_entry(avc, &anon_vma->head, same_anon_vma) {
+       pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
+       anon_vma_interval_tree_foreach(avc, &anon_vma->rb_root, pgoff, pgoff) {
                struct vm_area_struct *vma = avc->vma;
                unsigned long address;
 
@@ -1668,6 +1667,7 @@ static int rmap_walk_anon(struct page *page, int (*rmap_one)(struct page *,
                struct vm_area_struct *, unsigned long, void *), void *arg)
 {
        struct anon_vma *anon_vma;
+       pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
        struct anon_vma_chain *avc;
        int ret = SWAP_AGAIN;
 
@@ -1681,7 +1681,7 @@ static int rmap_walk_anon(struct page *page, int (*rmap_one)(struct page *,
        if (!anon_vma)
                return ret;
        anon_vma_lock(anon_vma);
-       list_for_each_entry(avc, &anon_vma->head, same_anon_vma) {
+       anon_vma_interval_tree_foreach(avc, &anon_vma->rb_root, pgoff, pgoff) {
                struct vm_area_struct *vma = avc->vma;
                unsigned long address = vma_address(page, vma);
                if (address == -EFAULT)