1 files changed, 104 insertions, 52 deletions

diff --git a/mm/vmalloc.c b/mm/vmalloc.c
index f9b166732e70..fc77adabb5e3 100644
--- a/mm/vmalloc.c
+++ b/mm/vmalloc.c
@@ -261,8 +261,15 @@ struct vmap_area {
 };
 
 static DEFINE_SPINLOCK(vmap_area_lock);
-static struct rb_root vmap_area_root = RB_ROOT;
 static LIST_HEAD(vmap_area_list);
+static struct rb_root vmap_area_root = RB_ROOT;
+
+/* The vmap cache globals are protected by vmap_area_lock */
+static struct rb_node *free_vmap_cache;
+static unsigned long cached_hole_size;
+static unsigned long cached_vstart;
+static unsigned long cached_align;
+
 static unsigned long vmap_area_pcpu_hole;
 
 static struct vmap_area *__find_vmap_area(unsigned long addr)
@@ -331,9 +338,11 @@ static struct vmap_area *alloc_vmap_area(unsigned long size,
         struct rb_node *n;
         unsigned long addr;
         int purged = 0;
+        struct vmap_area *first;
 
         BUG_ON(!size);
         BUG_ON(size & ~PAGE_MASK);
+        BUG_ON(!is_power_of_2(align));
 
         va = kmalloc_node(sizeof(struct vmap_area),
                         gfp_mask & GFP_RECLAIM_MASK, node);
@@ -341,79 +350,106 @@ static struct vmap_area *alloc_vmap_area(unsigned long size,
                 return ERR_PTR(-ENOMEM);
 
 retry:
-        addr = ALIGN(vstart, align);
-
         spin_lock(&vmap_area_lock);
-        if (addr + size - 1 < addr)
-                goto overflow;
+        /*
+         * Invalidate cache if we have more permissive parameters.
+         * cached_hole_size notes the largest hole noticed _below_
+         * the vmap_area cached in free_vmap_cache: if size fits
+         * into that hole, we want to scan from vstart to reuse
+         * the hole instead of allocating above free_vmap_cache.
+         * Note that __free_vmap_area may update free_vmap_cache
+         * without updating cached_hole_size or cached_align.
+         */
+        if (!free_vmap_cache ||
+                        size < cached_hole_size ||
+                        vstart < cached_vstart ||
+                        align < cached_align) {
+nocache:
+                cached_hole_size = 0;
+                free_vmap_cache = NULL;
+        }
+        /* record if we encounter less permissive parameters */
+        cached_vstart = vstart;
+        cached_align = align;
+
+        /* find starting point for our search */
+        if (free_vmap_cache) {
+                first = rb_entry(free_vmap_cache, struct vmap_area, rb_node);
+                addr = ALIGN(first->va_end + PAGE_SIZE, align);
+                if (addr < vstart)
+                        goto nocache;
+                if (addr + size - 1 < addr)
+                        goto overflow;
+
+        } else {
+                addr = ALIGN(vstart, align);
+                if (addr + size - 1 < addr)
+                        goto overflow;
 
-        /* XXX: could have a last_hole cache */
-        n = vmap_area_root.rb_node;
-        if (n) {
-                struct vmap_area *first = NULL;
+                n = vmap_area_root.rb_node;
+                first = NULL;
 
-                do {
+                while (n) {
                         struct vmap_area *tmp;
                         tmp = rb_entry(n, struct vmap_area, rb_node);
                         if (tmp->va_end >= addr) {
-                                if (!first && tmp->va_start < addr + size)
-                                        first = tmp;
-                                n = n->rb_left;
-                        } else {
                                 first = tmp;
+                                if (tmp->va_start <= addr)
+                                        break;
+                                n = n->rb_left;
+                        } else
                                 n = n->rb_right;
-                        }
-                } while (n);
+                }
 
                 if (!first)
                         goto found;
-
-                if (first->va_end < addr) {
-                        n = rb_next(&first->rb_node);
-                        if (n)
-                                first = rb_entry(n, struct vmap_area, rb_node);
-                        else
-                                goto found;
-                }
-
-                while (addr + size > first->va_start && addr + size <= vend) {
-                        addr = ALIGN(first->va_end + PAGE_SIZE, align);
-                        if (addr + size - 1 < addr)
-                                goto overflow;
-
-                        n = rb_next(&first->rb_node);
-                        if (n)
-                                first = rb_entry(n, struct vmap_area, rb_node);
-                        else
-                                goto found;
-                }
         }
-found:
-        if (addr + size > vend) {
-overflow:
-                spin_unlock(&vmap_area_lock);
-                if (!purged) {
-                        purge_vmap_area_lazy();
-                        purged = 1;
-                        goto retry;
-                }
-                if (printk_ratelimit())
-                        printk(KERN_WARNING
-                                "vmap allocation for size %lu failed: "
-                                "use vmalloc=<size> to increase size.\n", size);
-                kfree(va);
-                return ERR_PTR(-EBUSY);
+
+        /* from the starting point, walk areas until a suitable hole is found */
+        while (addr + size >= first->va_start && addr + size <= vend) {
+                if (addr + cached_hole_size < first->va_start)
+                        cached_hole_size = first->va_start - addr;
+                addr = ALIGN(first->va_end + PAGE_SIZE, align);
+                if (addr + size - 1 < addr)
+                        goto overflow;
+
+                n = rb_next(&first->rb_node);
+                if (n)
+                        first = rb_entry(n, struct vmap_area, rb_node);
+                else
+                        goto found;
         }
 
-        BUG_ON(addr & (align-1));
+found:
+        if (addr + size > vend)
+                goto overflow;
 
         va->va_start = addr;
         va->va_end = addr + size;
         va->flags = 0;
         __insert_vmap_area(va);
+        free_vmap_cache = &va->rb_node;
         spin_unlock(&vmap_area_lock);
 
+        BUG_ON(va->va_start & (align-1));
+        BUG_ON(va->va_start < vstart);
+        BUG_ON(va->va_end > vend);
+
         return va;
+
+overflow:
+        spin_unlock(&vmap_area_lock);
+        if (!purged) {
+                purge_vmap_area_lazy();
+                purged = 1;
+                goto retry;
+        }
+        if (printk_ratelimit())
+                printk(KERN_WARNING
+                        "vmap allocation for size %lu failed: "
+                        "use vmalloc=<size> to increase size.\n", size);
+        kfree(va);
+        return ERR_PTR(-EBUSY);
 }
 
 static void rcu_free_va(struct rcu_head *head)
@@ -426,6 +462,22 @@ static void rcu_free_va(struct rcu_head *head)
 static void __free_vmap_area(struct vmap_area *va)
 {
         BUG_ON(RB_EMPTY_NODE(&va->rb_node));
+
+        if (free_vmap_cache) {
+                if (va->va_end < cached_vstart) {
+                        free_vmap_cache = NULL;
+                } else {
+                        struct vmap_area *cache;
+                        cache = rb_entry(free_vmap_cache, struct vmap_area, rb_node);
+                        if (va->va_start <= cache->va_start) {
+                                free_vmap_cache = rb_prev(&va->rb_node);
+                                /*
+                                 * We don't try to update cached_hole_size or
+                                 * cached_align, but it won't go very wrong.
+                                 */
+                        }
+                }
+        }
         rb_erase(&va->rb_node, &vmap_area_root);
         RB_CLEAR_NODE(&va->rb_node);
         list_del_rcu(&va->list);