summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorKent Overstreet <koverstreet@google.com>2013-06-14 15:55:11 -0700
committerKent Overstreet <koverstreet@google.com>2013-06-14 15:58:31 -0700
commit01657040f46132eb1300172eccae9b89850be780 (patch)
treed347a9797354796f4006054c8a356b594e93f35b
parent37afdfd7ecbb4d07b176b61f7f80502ae475f3ad (diff)
use bitmap tree for percpu tagsidr-array-alloc
-rw-r--r--include/linux/percpu-tags.h11
-rw-r--r--lib/percpu-tags.c47
2 files changed, 21 insertions, 37 deletions
diff --git a/include/linux/percpu-tags.h b/include/linux/percpu-tags.h
index 0f1e7b31d421..39b7020dff9b 100644
--- a/include/linux/percpu-tags.h
+++ b/include/linux/percpu-tags.h
@@ -28,6 +28,7 @@
#ifndef _LINUX_TAGS_H
#define _LINUX_TAGS_H
+#include <linux/bitmap-tree.h>
#include <linux/spinlock_types.h>
#include <linux/wait.h>
@@ -62,15 +63,11 @@ struct percpu_tag_pool {
*/
unsigned cpu_last_stolen;
- /*
- * Global freelist - it's a stack where nr_free points to the
- * top
- */
- unsigned nr_free;
- unsigned *freelist;
-
/* For sleeping on allocation failure */
wait_queue_head_t wait;
+
+ /* Global freelist */
+ struct bitmap_tree map;
} ____cacheline_aligned_in_smp;
};
diff --git a/lib/percpu-tags.c b/lib/percpu-tags.c
index 2c5d55e3c69e..f41f23194846 100644
--- a/lib/percpu-tags.c
+++ b/lib/percpu-tags.c
@@ -7,9 +7,8 @@
#include <asm/cmpxchg.h>
#include <linux/bitmap.h>
-#include <linux/freezer.h>
+#include <linux/export.h>
#include <linux/gfp.h>
-#include <linux/module.h>
#include <linux/percpu.h>
#include <linux/sched.h>
#include <linux/slab.h>
@@ -114,14 +113,15 @@ static inline bool steal_tags(struct percpu_tag_pool *pool,
static inline bool alloc_global_tags(struct percpu_tag_pool *pool,
struct percpu_tag_cpu *tags)
{
- if (pool->nr_free) {
- move_tags(tags->freelist, &tags->nr_free,
- pool->freelist, &pool->nr_free,
- min(pool->nr_free, TAG_CPU_BATCH_MOVE));
- return true;
- }
+ int nr_free = bitmap_tree_find_set_bits(&pool->map,
+ tags->freelist,
+ TAG_CPU_BATCH_MOVE);
- return false;
+ if (nr_free <= 0)
+ return false;
+
+ tags->nr_free = nr_free;
+ return true;
}
static inline unsigned alloc_local_tag(struct percpu_tag_pool *pool,
@@ -211,7 +211,6 @@ unsigned percpu_tag_alloc(struct percpu_tag_pool *pool, gfp_t gfp)
break;
schedule();
- try_to_freeze();
local_irq_save(flags);
this_cpu = smp_processor_id();
@@ -272,14 +271,12 @@ void percpu_tag_free(struct percpu_tag_pool *pool, unsigned tag)
if (new == TAG_CPU_SIZE) {
spin_lock(&pool->lock);
- /* Might have had our tags stolen before we took global lock */
- if (tags->nr_free == TAG_CPU_SIZE) {
- move_tags(pool->freelist, &pool->nr_free,
- tags->freelist, &tags->nr_free,
- TAG_CPU_BATCH_MOVE);
- wake_up(&pool->wait);
- }
+ while (tags->nr_free > TAG_CPU_SIZE - TAG_CPU_BATCH_MOVE)
+ bitmap_tree_clear_bit(&pool->map,
+ tags->freelist[--tags->nr_free]);
+
+ wake_up(&pool->wait);
spin_unlock(&pool->lock);
}
@@ -297,8 +294,7 @@ void percpu_tag_pool_free(struct percpu_tag_pool *pool)
{
free_percpu(pool->tag_cpu);
kfree(pool->cpus_have_tags);
- free_pages((unsigned long) pool->freelist,
- get_order(pool->nr_tags * sizeof(unsigned)));
+ bitmap_tree_free(&pool->map);
}
EXPORT_SYMBOL_GPL(percpu_tag_pool_free);
@@ -316,8 +312,6 @@ EXPORT_SYMBOL_GPL(percpu_tag_pool_free);
*/
int percpu_tag_pool_init(struct percpu_tag_pool *pool, unsigned long nr_tags)
{
- unsigned i, order;
-
memset(pool, 0, sizeof(*pool));
spin_lock_init(&pool->lock);
@@ -330,15 +324,8 @@ int percpu_tag_pool_init(struct percpu_tag_pool *pool, unsigned long nr_tags)
return -EINVAL;
}
- order = get_order(nr_tags * sizeof(unsigned));
- pool->freelist = (void *) __get_free_pages(GFP_KERNEL, order);
- if (!pool->freelist)
- goto err;
-
- for (i = 0; i < nr_tags; i++)
- pool->freelist[i] = i;
-
- pool->nr_free = nr_tags;
+ if (bitmap_tree_init(&pool->map, nr_tags))
+ return -ENOMEM;
pool->cpus_have_tags = kzalloc(BITS_TO_LONGS(nr_cpu_ids) *
sizeof(unsigned long), GFP_KERNEL);