percpu: speed alloc_pcpu_area() up

If we know that first N areas are all in use, we can obviously skip
them when searching for a free one.  And that kind of hint is very
easy to maintain.

Signed-off-by: Al Viro <viro@zeniv.linux.org.uk>
Signed-off-by: Tejun Heo <tj@kernel.org>

1 files changed, 17 insertions, 1 deletions

diff --git a/mm/percpu.c b/mm/percpu.c
index 49dfccf9169c..c7206d06f8de 100644
--- a/mm/percpu.c
+++ b/mm/percpu.c
@@ -106,6 +106,7 @@ struct pcpu_chunk {
         int                     map_alloc;      /* # of map entries allocated */
         int                     *map;           /* allocation map */
         void                    *data;          /* chunk data */
+        int                     first_free;     /* no free below this */
         bool                    immutable;      /* no [de]population allowed */
         unsigned long           populated[];    /* populated bitmap */
 };
@@ -441,9 +442,10 @@ static int pcpu_alloc_area(struct pcpu_chunk *chunk, int size, int align)
         int oslot = pcpu_chunk_slot(chunk);
         int max_contig = 0;
         int i, off;
+        bool seen_free = false;
         int *p;
 
-        for (i = 0, p = chunk->map; i < chunk->map_used; i++, p++) {
+        for (i = chunk->first_free, p = chunk->map + i; i < chunk->map_used; i++, p++) {
                 int head, tail;
                 int this_size;
 
@@ -456,6 +458,10 @@ static int pcpu_alloc_area(struct pcpu_chunk *chunk, int size, int align)
 
                 this_size = (p[1] & ~1) - off;
                 if (this_size < head + size) {
+                        if (!seen_free) {
+                                chunk->first_free = i;
+                                seen_free = true;
+                        }
                         max_contig = max(this_size, max_contig);
                         continue;
                 }
@@ -491,6 +497,10 @@ static int pcpu_alloc_area(struct pcpu_chunk *chunk, int size, int align)
                         chunk->map_used += nr_extra;
 
                         if (head) {
+                                if (!seen_free) {
+                                        chunk->first_free = i;
+                                        seen_free = true;
+                                }
                                 *++p = off += head;
                                 ++i;
                                 max_contig = max(head, max_contig);
@@ -501,6 +511,9 @@ static int pcpu_alloc_area(struct pcpu_chunk *chunk, int size, int align)
                         }
                 }
 
+                if (!seen_free)
+                        chunk->first_free = i + 1;
+
                 /* update hint and mark allocated */
                 if (i + 1 == chunk->map_used)
                         chunk->contig_hint = max_contig; /* fully scanned */
@@ -558,6 +571,9 @@ static void pcpu_free_area(struct pcpu_chunk *chunk, int freeme)
         }
         BUG_ON(off != freeme);
 
+        if (i < chunk->first_free)
+                chunk->first_free = i;
+
         p = chunk->map + i;
         *p = off &= ~1;
         chunk->free_size += (p[1] & ~1) - off;