On Fri, 2012-09-07 at 11:16 +0200, Benjamin Gaignard wrote:
> From: Benjamin Gaignard <benjamin.gaign...@stericsson.com>
>
> This patch allow to use another algorithm than the default first-fit one.
> For example a custom algorithm could be used to manage alignment requirements.
>
> Add of best-fit algorithm function:
> most of the time best-fit is slower then first-fit but memory fragmentation
> is lower.
> Random buffer allocation/free tests don't show any arithmetic relation between
> allocation time and fragmentation but best-fit algorithm is sometime able to
> perform the allocation when first-fit can't.
>
> This new algorithm help to solve fragmentation issues on ESRAM shared by
> multiple
> hardware IP allocating and freeing dynamically memory region of various sizes.
>
> Signed-off-by: Benjamin Gaignard <benjamin.gaign...@stericsson.com>
> ---
> include/linux/genalloc.h | 15 ++++++++
> lib/genalloc.c | 86
> +++++++++++++++++++++++++++++++++++++++++++---
> 2 files changed, 97 insertions(+), 4 deletions(-)
>
> diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
> index 5e98eeb..b8570a7 100644
> --- a/include/linux/genalloc.h
> +++ b/include/linux/genalloc.h
> @@ -36,6 +36,10 @@ struct gen_pool {
> spinlock_t lock;
> struct list_head chunks; /* list of chunks in this pool */
> int min_alloc_order; /* minimum allocation order */
> +
> + unsigned long (*algo)(unsigned long *, unsigned long,
> + unsigned long, unsigned int, void *);
> + void *data;
> };
>
> /*
> @@ -78,4 +82,15 @@ extern void gen_pool_for_each_chunk(struct gen_pool *,
> void (*)(struct gen_pool *, struct gen_pool_chunk *, void *), void *);
> extern size_t gen_pool_avail(struct gen_pool *);
> extern size_t gen_pool_size(struct gen_pool *);
> +
> +extern void gen_pool_set_algo(struct gen_pool *,
> + unsigned long (*)(unsigned long *, unsigned long, unsigned long,
> + unsigned int, void *), void *);
> +
> +extern unsigned long gen_pool_first_fit(unsigned long *, unsigned long,
> + unsigned long, unsigned int, void *);
> +
> +extern unsigned long gen_pool_best_fit(unsigned long *, unsigned long,
> + unsigned long, unsigned int, void *);
> +
> #endif /* __GENALLOC_H__ */
> diff --git a/lib/genalloc.c b/lib/genalloc.c
> index 6bc04aa..a0d73c8 100644
> --- a/lib/genalloc.c
> +++ b/lib/genalloc.c
> @@ -152,6 +152,8 @@ struct gen_pool *gen_pool_create(int min_alloc_order, int
> nid)
> spin_lock_init(&pool->lock);
> INIT_LIST_HEAD(&pool->chunks);
> pool->min_alloc_order = min_alloc_order;
> + pool->algo = gen_pool_first_fit;
> + pool->data = NULL;
> }
> return pool;
> }
> @@ -255,8 +257,9 @@ EXPORT_SYMBOL(gen_pool_destroy);
> * @size: number of bytes to allocate from the pool
> *
> * Allocate the requested number of bytes from the specified pool.
> - * Uses a first-fit algorithm. Can not be used in NMI handler on
> - * architectures without NMI-safe cmpxchg implementation.
> + * Uses the pool allocation function (with first-fit algorithm by default).
> + * Can not be used in NMI handler on architectures without
> + * NMI-safe cmpxchg implementation.
> */
> unsigned long gen_pool_alloc(struct gen_pool *pool, size_t size)
> {
> @@ -280,8 +283,8 @@ unsigned long gen_pool_alloc(struct gen_pool *pool,
> size_t size)
>
> end_bit = (chunk->end_addr - chunk->start_addr) >> order;
> retry:
> - start_bit = bitmap_find_next_zero_area(chunk->bits, end_bit,
> - start_bit, nbits, 0);
> + start_bit = pool->algo(chunk->bits, end_bit, start_bit, nbits,
> + pool->data);
> if (start_bit >= end_bit)
> continue;
> remain = bitmap_set_ll(chunk->bits, start_bit, nbits);
> @@ -400,3 +403,78 @@ size_t gen_pool_size(struct gen_pool *pool)
> return size;
> }
> EXPORT_SYMBOL_GPL(gen_pool_size);
> +
> +/**
> + * gen_pool_set_algo - set the allocation algorithm
> + * @pool: pool to change allocation algorithm
> + * @priv: private data to be pass to algorithm function
> + * @algo: custom algorithm function
> + */
> +void gen_pool_set_algo(struct gen_pool *pool,
> + unsigned long (*algo)(unsigned long *map, unsigned long size,
> + unsigned long start, unsigned int nr, void *data), void *data)
> +{
> + rcu_read_lock();
IMHO, you can use pool->lock here. _set_algo need not to be lock-less.
> +
> + pool->algo = algo;
> + if (!pool->algo)
> + pool->algo = gen_pool_first_fit;
Why not check input parameter algo?
> +
> + pool->data = data;
> +
> + rcu_read_unlock();
> +}
> +EXPORT_SYMBOL(gen_pool_set_algo);
[snip]
Best Regards,
Huang Ying
--
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/
