Allocates integers out of a predefined range - for use by e.g. a driver
to allocate tags for communicating with the device.
Signed-off-by: Kent Overstreet <koverstr...@google.com>
Cc: Tejun Heo <t...@kernel.org>
Cc: Oleg Nesterov <o...@redhat.com>
Cc: Christoph Lameter <c...@linux-foundation.org>
Cc: Ingo Molnar <mi...@redhat.com>
---
include/linux/tags.h | 38 ++++++++++++
lib/Kconfig | 3 +
lib/Makefile | 2 +-
lib/tags.c | 167 +++++++++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 209 insertions(+), 1 deletion(-)
create mode 100644 include/linux/tags.h
create mode 100644 lib/tags.c
diff --git a/include/linux/tags.h b/include/linux/tags.h
new file mode 100644
index 0000000..1b8cfca
--- /dev/null
+++ b/include/linux/tags.h
@@ -0,0 +1,38 @@
+/*
+ * Copyright 2012 Google Inc. All Rights Reserved.
+ * Author: koverstr...@google.com (Kent Overstreet)
+ *
+ * Per cpu tag allocator.
+ */
+
+#ifndef _LINUX_TAGS_H
+#define _LINUX_TAGS_H
+
+#include <linux/list.h>
+#include <linux/spinlock.h>
+
+struct tag_cpu_freelist;
+
+struct tag_pool {
+ unsigned watermark;
+ unsigned nr_tags;
+
+ struct tag_cpu_freelist *tag_cpu;
+
+ struct {
+ /* Global freelist */
+ unsigned nr_free;
+ unsigned *free;
+ spinlock_t lock;
+ struct list_head wait;
+ } ____cacheline_aligned;
+};
+
+unsigned tag_alloc(struct tag_pool *pool, bool wait);
+void tag_free(struct tag_pool *pool, unsigned tag);
+
+void tag_pool_free(struct tag_pool *pool);
+int tag_pool_init(struct tag_pool *pool, unsigned long nr_tags);
+
+
+#endif
diff --git a/lib/Kconfig b/lib/Kconfig
index fe01d41..fa77e31 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -407,4 +407,7 @@ config OID_REGISTRY
config UCS2_STRING
tristate
+config PERCPU_TAG
+ bool
+
endmenu
diff --git a/lib/Makefile b/lib/Makefile
index 25a0ce1..c622107 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -13,7 +13,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
proportions.o flex_proportions.o prio_heap.o ratelimit.o show_mem.o \
is_single_threaded.o plist.o decompress.o kobject_uevent.o \
- earlycpio.o percpu-refcount.o
+ earlycpio.o percpu-refcount.o tags.o
obj-$(CONFIG_ARCH_HAS_DEBUG_STRICT_USER_COPY_CHECKS) += usercopy.o
lib-$(CONFIG_MMU) += ioremap.o
diff --git a/lib/tags.c b/lib/tags.c
new file mode 100644
index 0000000..5c3de28
--- /dev/null
+++ b/lib/tags.c
@@ -0,0 +1,167 @@
+/*
+ * Copyright 2012 Google Inc. All Rights Reserved.
+ * Author: koverstr...@google.com (Kent Overstreet)
+ *
+ * Per cpu tag allocator.
+ */
+
+#include <linux/gfp.h>
+#include <linux/module.h>
+#include <linux/sched.h>
+#include <linux/tags.h>
+
+struct tag_cpu_freelist {
+ unsigned nr_free;
+ unsigned free[];
+};
+
+struct tag_waiter {
+ struct list_head list;
+ struct task_struct *task;
+};
+
+static inline void move_tags(unsigned *dst, unsigned *dst_nr,
+ unsigned *src, unsigned *src_nr,
+ unsigned nr)
+{
+ *src_nr -= nr;
+ memcpy(dst + *dst_nr, src + *src_nr, sizeof(unsigned) * nr);
+ *dst_nr += nr;
+}
+
+unsigned tag_alloc(struct tag_pool *pool, bool wait)
+{
+ struct tag_cpu_freelist *tags;
+ unsigned long flags;
+ unsigned ret;
+retry:
+ preempt_disable();
+ local_irq_save(flags);
+ tags = this_cpu_ptr(pool->tag_cpu);
+
+ while (!tags->nr_free) {
+ spin_lock(&pool->lock);
+
+ if (pool->nr_free)
+ move_tags(tags->free, &tags->nr_free,
+ pool->free, &pool->nr_free,
+ min(pool->nr_free, pool->watermark));
+ else if (wait) {
+ struct tag_waiter wait = { .task = current };
+
+ __set_current_state(TASK_UNINTERRUPTIBLE);
+ list_add(&wait.list, &pool->wait);
+
+ spin_unlock(&pool->lock);
+ local_irq_restore(flags);
+ preempt_enable();
+
+ schedule();
+ __set_current_state(TASK_RUNNING);
+
+ if (!list_empty_careful(&wait.list)) {
+ spin_lock_irqsave(&pool->lock, flags);
+ list_del_init(&wait.list);
+ spin_unlock_irqrestore(&pool->lock, flags);
+ }
+
+ goto retry;
+ } else
+ goto fail;
+
+ spin_unlock(&pool->lock);
+ }
+
+ ret = tags->free[--tags->nr_free];
+
+ local_irq_restore(flags);
+ preempt_enable();
+
+ return ret;
+fail:
+ local_irq_restore(flags);
+ preempt_enable();
+ return 0;
+}
+EXPORT_SYMBOL_GPL(tag_alloc);
+
+void tag_free(struct tag_pool *pool, unsigned tag)
+{
+ struct tag_cpu_freelist *tags;
+ unsigned long flags;
+
+ preempt_disable();
+ local_irq_save(flags);
+ tags = this_cpu_ptr(pool->tag_cpu);
+
+ tags->free[tags->nr_free++] = tag;
+
+ if (tags->nr_free == pool->watermark * 2) {
+ spin_lock(&pool->lock);
+
+ move_tags(pool->free, &pool->nr_free,
+ tags->free, &tags->nr_free,
+ pool->watermark);
+
+ while (!list_empty(&pool->wait)) {
+ struct tag_waiter *wait;
+ wait = list_first_entry(&pool->wait,
+ struct tag_waiter, list);
+ list_del_init(&wait->list);
+ wake_up_process(wait->task);
+ }
+
+ spin_unlock(&pool->lock);
+ }
+
+ local_irq_restore(flags);
+ preempt_enable();
+}
+EXPORT_SYMBOL_GPL(tag_free);
+
+void tag_pool_free(struct tag_pool *pool)
+{
+ free_percpu(pool->tag_cpu);
+
+ free_pages((unsigned long) pool->free,
+ get_order(pool->nr_tags * sizeof(unsigned)));
+}
+EXPORT_SYMBOL_GPL(tag_pool_free);
+
+int tag_pool_init(struct tag_pool *pool, unsigned long nr_tags)
+{
+ unsigned i, order;
+
+ spin_lock_init(&pool->lock);
+ INIT_LIST_HEAD(&pool->wait);
+ pool->nr_tags = nr_tags;
+
+ /* Guard against overflow */
+ if (nr_tags > UINT_MAX)
+ return -ENOMEM;
+
+ order = get_order(nr_tags * sizeof(unsigned));
+ pool->free = (void *) __get_free_pages(GFP_KERNEL, order);
+ if (!pool->free)
+ return -ENOMEM;
+
+ for (i = 1; i < nr_tags; i++)
+ pool->free[pool->nr_free++] = i;
+
+ /* nr_possible_cpus would be more correct */
+ pool->watermark = nr_tags / (num_possible_cpus() * 4);
+
+ pool->watermark = min(pool->watermark, 128);
+
+ if (pool->watermark > 64)
+ pool->watermark = round_down(pool->watermark, 32);
+
+ pool->tag_cpu = __alloc_percpu(sizeof(struct tag_cpu_freelist) +
+ pool->watermark * 2 * sizeof(unsigned),
+ sizeof(unsigned));
+ if (!pool->tag_cpu)
+ return -ENOMEM;
+
+ return 0;
+}
+EXPORT_SYMBOL_GPL(tag_pool_init);
--
1.8.2.1
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
