diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/Kconfig | 6 | ||||
| -rw-r--r-- | lib/Makefile | 2 | ||||
| -rw-r--r-- | lib/genalloc.c | 188 | ||||
| -rw-r--r-- | lib/idr.c | 2 | ||||
| -rw-r--r-- | lib/kernel_lock.c | 55 | ||||
| -rw-r--r-- | lib/smp_processor_id.c | 55 |
6 files changed, 252 insertions, 56 deletions
diff --git a/lib/Kconfig b/lib/Kconfig index eeb45225248f..2d4d4e3bc4aa 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -40,6 +40,12 @@ config ZLIB_DEFLATE tristate # +# Generic allocator support is selected if needed +# +config GENERIC_ALLOCATOR + boolean + +# # reed solomon support is select'ed if needed # config REED_SOLOMON diff --git a/lib/Makefile b/lib/Makefile index 9eccea9429a7..dcb4231916e2 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -20,6 +20,7 @@ lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o +obj-$(CONFIG_DEBUG_PREEMPT) += smp_processor_id.o ifneq ($(CONFIG_HAVE_DEC_LOCK),y) lib-y += dec_and_lock.o @@ -29,6 +30,7 @@ obj-$(CONFIG_CRC_CCITT) += crc-ccitt.o obj-$(CONFIG_CRC32) += crc32.o obj-$(CONFIG_LIBCRC32C) += libcrc32c.o obj-$(CONFIG_GENERIC_IOMAP) += iomap.o +obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o obj-$(CONFIG_ZLIB_INFLATE) += zlib_inflate/ obj-$(CONFIG_ZLIB_DEFLATE) += zlib_deflate/ diff --git a/lib/genalloc.c b/lib/genalloc.c new file mode 100644 index 000000000000..d6d30d2e7166 --- /dev/null +++ b/lib/genalloc.c @@ -0,0 +1,188 @@ +/* + * Basic general purpose allocator for managing special purpose memory + * not managed by the regular kmalloc/kfree interface. + * Uses for this includes on-device special memory, uncached memory + * etc. + * + * This code is based on the buddy allocator found in the sym53c8xx_2 + * driver Copyright (C) 1999-2001 Gerard Roudier <groudier@free.fr>, + * and adapted for general purpose use. + * + * Copyright 2005 (C) Jes Sorensen <jes@trained-monkey.org> + * + * This source code is licensed under the GNU General Public License, + * Version 2. See the file COPYING for more details. + */ + +#include <linux/module.h> +#include <linux/stddef.h> +#include <linux/kernel.h> +#include <linux/string.h> +#include <linux/slab.h> +#include <linux/init.h> +#include <linux/mm.h> +#include <linux/spinlock.h> +#include <linux/genalloc.h> + +#include <asm/page.h> + + +struct gen_pool *gen_pool_create(int nr_chunks, int max_chunk_shift, + unsigned long (*fp)(struct gen_pool *), + unsigned long data) +{ + struct gen_pool *poolp; + unsigned long tmp; + int i; + + /* + * This is really an arbitrary limit, +10 is enough for + * IA64_GRANULE_SHIFT, aka 16MB. If anyone needs a large limit + * this can be increased without problems. + */ + if ((max_chunk_shift > (PAGE_SHIFT + 10)) || + ((max_chunk_shift < ALLOC_MIN_SHIFT) && max_chunk_shift)) + return NULL; + + if (!max_chunk_shift) + max_chunk_shift = PAGE_SHIFT; + + poolp = kmalloc(sizeof(struct gen_pool), GFP_KERNEL); + if (!poolp) + return NULL; + memset(poolp, 0, sizeof(struct gen_pool)); + poolp->h = kmalloc(sizeof(struct gen_pool_link) * + (max_chunk_shift - ALLOC_MIN_SHIFT + 1), + GFP_KERNEL); + if (!poolp->h) { + printk(KERN_WARNING "gen_pool_alloc() failed to allocate\n"); + kfree(poolp); + return NULL; + } + memset(poolp->h, 0, sizeof(struct gen_pool_link) * + (max_chunk_shift - ALLOC_MIN_SHIFT + 1)); + + spin_lock_init(&poolp->lock); + poolp->get_new_chunk = fp; + poolp->max_chunk_shift = max_chunk_shift; + poolp->private = data; + + for (i = 0; i < nr_chunks; i++) { + tmp = poolp->get_new_chunk(poolp); + printk(KERN_INFO "allocated %lx\n", tmp); + if (!tmp) + break; + gen_pool_free(poolp, tmp, (1 << poolp->max_chunk_shift)); + } + + return poolp; +} +EXPORT_SYMBOL(gen_pool_create); + + +/* + * Simple power of two buddy-like generic allocator. + * Provides naturally aligned memory chunks. + */ +unsigned long gen_pool_alloc(struct gen_pool *poolp, int size) +{ + int j, i, s, max_chunk_size; + unsigned long a, flags; + struct gen_pool_link *h = poolp->h; + + max_chunk_size = 1 << poolp->max_chunk_shift; + + if (size > max_chunk_size) + return 0; + + i = 0; + + size = max(size, 1 << ALLOC_MIN_SHIFT); + s = roundup_pow_of_two(size); + + j = i; + + spin_lock_irqsave(&poolp->lock, flags); + while (!h[j].next) { + if (s == max_chunk_size) { + struct gen_pool_link *ptr; + spin_unlock_irqrestore(&poolp->lock, flags); + ptr = (struct gen_pool_link *)poolp->get_new_chunk(poolp); + spin_lock_irqsave(&poolp->lock, flags); + h[j].next = ptr; + if (h[j].next) + h[j].next->next = NULL; + break; + } + j++; + s <<= 1; + } + a = (unsigned long) h[j].next; + if (a) { + h[j].next = h[j].next->next; + /* + * This should be split into a seperate function doing + * the chunk split in order to support custom + * handling memory not physically accessible by host + */ + while (j > i) { + j -= 1; + s >>= 1; + h[j].next = (struct gen_pool_link *) (a + s); + h[j].next->next = NULL; + } + } + spin_unlock_irqrestore(&poolp->lock, flags); + return a; +} +EXPORT_SYMBOL(gen_pool_alloc); + + +/* + * Counter-part of the generic allocator. + */ +void gen_pool_free(struct gen_pool *poolp, unsigned long ptr, int size) +{ + struct gen_pool_link *q; + struct gen_pool_link *h = poolp->h; + unsigned long a, b, flags; + int i, s, max_chunk_size; + + max_chunk_size = 1 << poolp->max_chunk_shift; + + if (size > max_chunk_size) + return; + + i = 0; + + size = max(size, 1 << ALLOC_MIN_SHIFT); + s = roundup_pow_of_two(size); + + a = ptr; + + spin_lock_irqsave(&poolp->lock, flags); + while (1) { + if (s == max_chunk_size) { + ((struct gen_pool_link *)a)->next = h[i].next; + h[i].next = (struct gen_pool_link *)a; + break; + } + b = a ^ s; + q = &h[i]; + + while (q->next && q->next != (struct gen_pool_link *)b) + q = q->next; + + if (!q->next) { + ((struct gen_pool_link *)a)->next = h[i].next; + h[i].next = (struct gen_pool_link *)a; + break; + } + q->next = q->next->next; + a = a & b; + s <<= 1; + i++; + } + spin_unlock_irqrestore(&poolp->lock, flags); +} +EXPORT_SYMBOL(gen_pool_free); diff --git a/lib/idr.c b/lib/idr.c index 81fc430602ee..c5be889de449 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -175,7 +175,7 @@ build_up: * Add a new layer to the top of the tree if the requested * id is larger than the currently allocated space. */ - while ((layers < MAX_LEVEL) && (id >= (1 << (layers*IDR_BITS)))) { + while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) { layers++; if (!p->count) continue; diff --git a/lib/kernel_lock.c b/lib/kernel_lock.c index 99b0ae3d51dd..bd2bc5d887b8 100644 --- a/lib/kernel_lock.c +++ b/lib/kernel_lock.c @@ -9,61 +9,6 @@ #include <linux/module.h> #include <linux/kallsyms.h> -#if defined(CONFIG_PREEMPT) && defined(__smp_processor_id) && \ - defined(CONFIG_DEBUG_PREEMPT) - -/* - * Debugging check. - */ -unsigned int smp_processor_id(void) -{ - unsigned long preempt_count = preempt_count(); - int this_cpu = __smp_processor_id(); - cpumask_t this_mask; - - if (likely(preempt_count)) - goto out; - - if (irqs_disabled()) - goto out; - - /* - * Kernel threads bound to a single CPU can safely use - * smp_processor_id(): - */ - this_mask = cpumask_of_cpu(this_cpu); - - if (cpus_equal(current->cpus_allowed, this_mask)) - goto out; - - /* - * It is valid to assume CPU-locality during early bootup: - */ - if (system_state != SYSTEM_RUNNING) - goto out; - - /* - * Avoid recursion: - */ - preempt_disable(); - - if (!printk_ratelimit()) - goto out_enable; - - printk(KERN_ERR "BUG: using smp_processor_id() in preemptible [%08x] code: %s/%d\n", preempt_count(), current->comm, current->pid); - print_symbol("caller is %s\n", (long)__builtin_return_address(0)); - dump_stack(); - -out_enable: - preempt_enable_no_resched(); -out: - return this_cpu; -} - -EXPORT_SYMBOL(smp_processor_id); - -#endif /* PREEMPT && __smp_processor_id && DEBUG_PREEMPT */ - #ifdef CONFIG_PREEMPT_BKL /* * The 'big kernel semaphore' diff --git a/lib/smp_processor_id.c b/lib/smp_processor_id.c new file mode 100644 index 000000000000..42c08ef828c5 --- /dev/null +++ b/lib/smp_processor_id.c @@ -0,0 +1,55 @@ +/* + * lib/smp_processor_id.c + * + * DEBUG_PREEMPT variant of smp_processor_id(). + */ +#include <linux/module.h> +#include <linux/kallsyms.h> + +unsigned int debug_smp_processor_id(void) +{ + unsigned long preempt_count = preempt_count(); + int this_cpu = raw_smp_processor_id(); + cpumask_t this_mask; + + if (likely(preempt_count)) + goto out; + + if (irqs_disabled()) + goto out; + + /* + * Kernel threads bound to a single CPU can safely use + * smp_processor_id(): + */ + this_mask = cpumask_of_cpu(this_cpu); + + if (cpus_equal(current->cpus_allowed, this_mask)) + goto out; + + /* + * It is valid to assume CPU-locality during early bootup: + */ + if (system_state != SYSTEM_RUNNING) + goto out; + + /* + * Avoid recursion: + */ + preempt_disable(); + + if (!printk_ratelimit()) + goto out_enable; + + printk(KERN_ERR "BUG: using smp_processor_id() in preemptible [%08x] code: %s/%d\n", preempt_count(), current->comm, current->pid); + print_symbol("caller is %s\n", (long)__builtin_return_address(0)); + dump_stack(); + +out_enable: + preempt_enable_no_resched(); +out: + return this_cpu; +} + +EXPORT_SYMBOL(debug_smp_processor_id); + |