[PATCH] genalloc: make possible to use a custom allocation algorithm

[PATCH] genalloc: make possible to use a custom allocation algorithm

[Benjamin Gaignard]

From: Benjamin Gaignard <benjamin.gaignard@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.gaignard@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();
+
+	pool->algo = algo;
+	if (!pool->algo)
+		pool->algo = gen_pool_first_fit;
+
+	pool->data = data;
+
+	rcu_read_unlock();
+}
+EXPORT_SYMBOL(gen_pool_set_algo);
+
+/**
+ * gen_pool_first_fit - find the first available region
+ * of memory macthing the size requirement (no alignment constraint)
+ * @map: The address to base the search on
+ * @size: The bitmap size in bits
+ * @start: The bitnumber to start searching at
+ * @nr: The number of zeroed bits we're looking for
+ * @data: additional data - unused
+ */
+unsigned long gen_pool_first_fit(unsigned long *map, unsigned long size,
+		unsigned long start, unsigned int nr, void *data)
+{
+	return bitmap_find_next_zero_area(map, size, start, nr, 0);
+}
+EXPORT_SYMBOL(gen_pool_first_fit);
+
+/**
+ * gen_pool_best_fit - find the best fiting region of memory
+ * macthing the size requirement (no alignment constraint)
+ * @map: The address to base the search on
+ * @size: The bitmap size in bits
+ * @start: The bitnumber to start searching at
+ * @nr: The number of zeroed bits we're looking for
+ * @data: additional data - unused
+ *
+ * Iterate over the bitmap to find the smaller region where
+ * allocate the memory.
+ */
+unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size,
+		unsigned long start, unsigned int nr, void *data)
+{
+	unsigned long start_bit = size;
+	unsigned long len = size + 1;
+	unsigned long index;
+
+	index = bitmap_find_next_zero_area(map, size, start, nr, 0);
+
+	while (index < size) {
+		int next_bit = find_next_bit(map, size, index + nr);
+		if ((next_bit - index) < len) {
+			len = next_bit - index;
+			start_bit = index;
+			if (len == nr)
+				return start_bit;
+		}
+		index = bitmap_find_next_zero_area(map, size,
+						   next_bit + 1, nr, 0);
+	}
+
+	return start_bit;
+}
+EXPORT_SYMBOL(gen_pool_best_fit);
-- 
1.7.10

Re: [PATCH] genalloc: make possible to use a custom allocation algorithm

[Linus Walleij]

On Fri, Sep 7, 2012 at 11:16 AM, Benjamin Gaignard
<benjamin.gaignard@linaro.org> wrote:

> From: Benjamin Gaignard <benjamin.gaignard@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.gaignard@stericsson.com>

We really need this to manage our on-chip RAM
(ESRAM) which is a scarce resource, so:
Acked-by: Linus Walleij <linus.walleij@linaro.org>

Yours,
Linus Walleij

Re: [PATCH] genalloc: make possible to use a custom allocation algorithm

[Andrew Morton]

On Fri,  7 Sep 2012 11:16:33 +0200
Benjamin Gaignard <benjamin.gaignard@linaro.org> wrote:

> From: Benjamin Gaignard <benjamin.gaignard@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.

hm, OK.  What kernel subsystem are you referring to here?  Where do I
find this "ESRAM shared by multiple hardware"?

> --- 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();
> +
> +	pool->algo = algo;
> +	if (!pool->algo)
> +		pool->algo = gen_pool_first_fit;
> +
> +	pool->data = data;
> +
> +	rcu_read_unlock();
> +}
> +EXPORT_SYMBOL(gen_pool_set_algo);

It's sometimes nice to make such a function return the old value.  But
there's hopefully little point in doing that here, and there are two
"old values" anyway.

And what's up with `data'?  If the caller is passing algo==NULL then
that caller has no business specifying gen_pool_first_fit's "data"!

Presumably, the requirement is that data==NULL if algo==NULL?  If so,
let's document that.

Also the kerneldoc is quite wrong - fields are misnamed and fields are
missing altogether.

> +EXPORT_SYMBOL(gen_pool_first_fit);

Why is gen_pool_first_fit exported?  gen_pool_set_algo() can reference
gen_pool_first_fit() by passing in NULL, hence no need for the export? 
gen_pool_first_fit() can be made static to this file?

> +
> +/**
> + * gen_pool_best_fit - find the best fiting region of memory
> + * macthing the size requirement (no alignment constraint)
> + * @map: The address to base the search on
> + * @size: The bitmap size in bits
> + * @start: The bitnumber to start searching at
> + * @nr: The number of zeroed bits we're looking for
> + * @data: additional data - unused
> + *
> + * Iterate over the bitmap to find the smaller region where
> + * allocate the memory.

"to find the smallest free region from which we can allcoate the memory"

> + */
> +unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size,
> +		unsigned long start, unsigned int nr, void *data)
> +{
> +	unsigned long start_bit = size;
> +	unsigned long len = size + 1;
> +	unsigned long index;
> +
> +	index = bitmap_find_next_zero_area(map, size, start, nr, 0);
> +
> +	while (index < size) {
> +		int next_bit = find_next_bit(map, size, index + nr);
> +		if ((next_bit - index) < len) {
> +			len = next_bit - index;
> +			start_bit = index;
> +			if (len == nr)
> +				return start_bit;
> +		}
> +		index = bitmap_find_next_zero_area(map, size,
> +						   next_bit + 1, nr, 0);
> +	}
> +
> +	return start_bit;
> +}
> +EXPORT_SYMBOL(gen_pool_best_fit);

`data' continues to be unused and it is unobvious what its use is.  Can
we just remove it?


There's a potential reference counting issue here.  Each time a genpool
is created to reference a particular algorithm function, it in effects
takes a reference on that algorithm function.  What this means is that
strictly speaking, gen_pool_set_algo() should do a
module_get()/module_put() to track how many genpools are referring to
that module's text.  So that the module cannot be unloaded while any
genpools are still referring to its algorithm function.

But we can probably get away without this, for now: the module will
keep track of all its genpools and will destroy them all before
permitting itself to be unloaded.

Re: [PATCH] genalloc: make possible to use a custom allocation algorithm

[Linus Walleij]

On Fri, Sep 7, 2012 at 11:27 PM, Andrew Morton
<akpm@linux-foundation.org> wrote:
> On Fri,  7 Sep 2012 11:16:33 +0200
> Benjamin Gaignard <benjamin.gaignard@linaro.org> wrote:

> hm, OK.  What kernel subsystem are you referring to here?  Where do I
> find this "ESRAM shared by multiple hardware"?

This is on the Ux500 in the ARM tree. We have defined the bases
for this memory down there:

cd arch/arm/mach-ux500 && grep -r ESRAM .
./include/mach/db8500-regs.h:/* Base address and bank offsets for ESRAM */
./include/mach/db8500-regs.h:#define U8500_ESRAM_BASE	0x40000000
./include/mach/db8500-regs.h:#define U8500_ESRAM_BANK_SIZE	0x00020000
./include/mach/db8500-regs.h:#define U8500_ESRAM_BANK0	U8500_ESRAM_BASE
./include/mach/db8500-regs.h:#define
U8500_ESRAM_BANK1	(U8500_ESRAM_BASE + U8500_ESRAM_BANK_SIZE)
./include/mach/db8500-regs.h:#define
U8500_ESRAM_BANK2	(U8500_ESRAM_BANK1 + U8500_ESRAM_BANK_SIZE)
./include/mach/db8500-regs.h:#define
U8500_ESRAM_BANK3	(U8500_ESRAM_BANK2 + U8500_ESRAM_BANK_SIZE)
./include/mach/db8500-regs.h:#define
U8500_ESRAM_BANK4	(U8500_ESRAM_BANK3 + U8500_ESRAM_BANK_SIZE)
./include/mach/db8500-regs.h:#define U8500_ESRAM_DMA_LCPA_OFFSET     0x10000
./include/mach/db8500-regs.h:#define U8500_DMA_LCPA_BASE
(U8500_ESRAM_BANK0 + U8500_ESRAM_DMA_LCPA_OFFSET)
./include/mach/db8500-regs.h:#define U8500_DMA_LCLA_BASE	U8500_ESRAM_BANK4

So 5 banks of on-chip (fast!) RAM of 128 KB each. (And my
Commodore 128 had 128 kB in total ... sob.)

As you can see the last three defines start to do something that
will grow unmaintainable: use static allocations in that ESRAM.
In this case to hold linked lists for DMA transfers.

Needless to say, a few high-performance use cases will really
benefit from using this high-speed RAM. Typically DMA
linked lists, graphics accelerators, encoders/decoders,
SETI@Home work units, you name it.

So we need to chop up this memory using a real allocator.
So we've tried to use genalloc and it turns out it works fine
until we run into allocation issues as those described by
Benjamin, and it becomes a chicken-and-egg problem
that we need fixing genalloc first to get to use the resource
in a good way before we can submit code using the
allocator.

(The rest of the review comments I think Benjamin can
answer way better than me...)

Yours,
Linus Walleij

Re: [PATCH] genalloc: make possible to use a custom allocation algorithm

[Huang Ying]

On Fri, 2012-09-07 at 11:16 +0200, Benjamin Gaignard wrote:
> From: Benjamin Gaignard <benjamin.gaignard@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.gaignard@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

Re: [PATCH] genalloc: make possible to use a custom allocation algorithm

[Benjamin Gaignard]

In my mind 'data' is for custom algorithms that could need additional
data to perform the allocation (it is very similar to what is done in
gen_pool_for_each_chunk function).

In gen_pool_set_algo function I have test 'algo' just be sure that we
alway have a valid algorithm function.
gen_pool_alloc doesn't take pool->lock, only rcu_lock, and I want to
avoid changing allocation function while gen_pool_alloc use it, so I
have only protect pool->algo with rcu_lock.
I need to export gen_pool_best_fit so I have do the same for gen_pool_first_fit.

I will add more detail about that in kerneldoc and fix the other
mistakes before send a new version of this patch.

Regards,
Benjamin Gaignard

Re: [PATCH] genalloc: make possible to use a custom allocation algorithm

[Benjamin Gaignard]

>From e790af0773193c3c7e5950ab74fa5e1e29204ad5 Mon Sep 17 00:00:00 2001
From: Benjamin Gaignard <benjamin.gaignard@stericsson.com>
Date: Mon, 10 Sep 2012 10:11:05 +0200
Subject: [PATCH] genalloc: make possible to use a custom allocation algorithm

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.gaignard@stericsson.com>
---
 include/linux/genalloc.h |   15 ++++++++
 lib/genalloc.c           |   90 +++++++++++++++++++++++++++++++++++++++++++---
 2 files changed, 101 insertions(+), 4 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 5e98eeb..f72a0a0 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..9583dae 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,82 @@ 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
+ * @algo: custom algorithm function
+ * @data: additional data used by @algo
+ *
+ * Call @algo for each memory allocation in the pool.
+ * If @algo is NULL use gen_pool_first_fit as default
+ * memory allocation 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();
+
+	pool->algo = algo;
+	if (!pool->algo)
+		pool->algo = gen_pool_first_fit;
+
+	pool->data = data;
+
+	rcu_read_unlock();
+}
+EXPORT_SYMBOL(gen_pool_set_algo);
+
+/**
+ * gen_pool_first_fit - find the first available region
+ * of memory macthing the size requirement (no alignment constraint)
+ * @map: The address to base the search on
+ * @size: The bitmap size in bits
+ * @start: The bitnumber to start searching at
+ * @nr: The number of zeroed bits we're looking for
+ * @data: additional data - unused
+ */
+unsigned long gen_pool_first_fit(unsigned long *map, unsigned long size,
+		unsigned long start, unsigned int nr, void *data)
+{
+	return bitmap_find_next_zero_area(map, size, start, nr, 0);
+}
+EXPORT_SYMBOL(gen_pool_first_fit);
+
+/**
+ * gen_pool_best_fit - find the best fiting region of memory
+ * macthing the size requirement (no alignment constraint)
+ * @map: The address to base the search on
+ * @size: The bitmap size in bits
+ * @start: The bitnumber to start searching at
+ * @nr: The number of zeroed bits we're looking for
+ * @data: additional data - unused
+ *
+ * Iterate over the bitmap to find the smallest free region
+ * which we can allocate the memory.
+ */
+unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size,
+		unsigned long start, unsigned int nr, void *data)
+{
+	unsigned long start_bit = size;
+	unsigned long len = size + 1;
+	unsigned long index;
+
+	index = bitmap_find_next_zero_area(map, size, start, nr, 0);
+
+	while (index < size) {
+		int next_bit = find_next_bit(map, size, index + nr);
+		if ((next_bit - index) < len) {
+			len = next_bit - index;
+			start_bit = index;
+			if (len == nr)
+				return start_bit;
+		}
+		index = bitmap_find_next_zero_area(map, size,
+						   next_bit + 1, nr, 0);
+	}
+
+	return start_bit;
+}
+EXPORT_SYMBOL(gen_pool_best_fit);
-- 
1.7.10

Re: [PATCH] genalloc: make possible to use a custom allocation algorithm

[Andrew Morton]

On Mon, 10 Sep 2012 10:46:43 +0200
Benjamin Gaignard <benjamin.gaignard@linaro.org> wrote:

> >From e790af0773193c3c7e5950ab74fa5e1e29204ad5 Mon Sep 17 00:00:00 2001
> From: Benjamin Gaignard <benjamin.gaignard@stericsson.com>
> Date: Mon, 10 Sep 2012 10:11:05 +0200
> Subject: [PATCH] genalloc: make possible to use a custom allocation algorithm
> 
> 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.

I still don't understand why this "data" argument is there.  Please
describe this fully in the changelog.  A usage example might help.

> This new algorithm help to solve fragmentation issues on ESRAM shared
> by multiple
> hardware IP allocating and freeing dynamically memory region of various sizes.

I earlier asked what the above meant, and someone provided a useful
reply.  Please get that reply into the changelog so that others don't
wonder the same thing.

Generally, any reviewer question should be taken as a sign that the
changelog or code commenting was inadequate.

> --- 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 *);

I think it is better to include the names of the arguments.  The above
is pretty unreadable without this.

I suggest you create a typedef for this thing:

typedef unsigned long (*genpool_algo_t)(unsigned long *name1,
					unsigned long name2,
					unsigned long name3,
					unsigned int name4,
					void *data);

(with name[1-4] appropriately chosen) and use that throughout the patch.

typedefs are generally frowned upon, but this particular case is an
exception.

> +	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 *);

The patch is wordwrapped.  Please fix up your email client.

>  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 *);

Ditto.  Yes, the current code leaves the names out, but that doesn't
mean it's a good thing to do.

>  #endif /* __GENALLOC_H__ */
> diff --git a/lib/genalloc.c b/lib/genalloc.c
> index 6bc04aa..9583dae 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,82 @@ 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
> + * @algo: custom algorithm function
> + * @data: additional data used by @algo
> + *
> + * Call @algo for each memory allocation in the pool.
> + * If @algo is NULL use gen_pool_first_fit as default
> + * memory allocation 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();
> +
> +	pool->algo = algo;
> +	if (!pool->algo)
> +		pool->algo = gen_pool_first_fit;
> +
> +	pool->data = data;
> +
> +	rcu_read_unlock();
> +}
> +EXPORT_SYMBOL(gen_pool_set_algo);
> +
> +/**
> + * gen_pool_first_fit - find the first available region
> + * of memory macthing the size requirement (no alignment constraint)

"matching"

> + * @map: The address to base the search on
> + * @size: The bitmap size in bits
> + * @start: The bitnumber to start searching at
> + * @nr: The number of zeroed bits we're looking for
> + * @data: additional data - unused
> + */
> +unsigned long gen_pool_first_fit(unsigned long *map, unsigned long size,
> +		unsigned long start, unsigned int nr, void *data)
> +{
> +	return bitmap_find_next_zero_area(map, size, start, nr, 0);
> +}
> +EXPORT_SYMBOL(gen_pool_first_fit);
> +
> +/**
> + * gen_pool_best_fit - find the best fiting region of memory

"fitting"

> + * macthing the size requirement (no alignment constraint)

"matching"

> + * @map: The address to base the search on
> + * @size: The bitmap size in bits
> + * @start: The bitnumber to start searching at
> + * @nr: The number of zeroed bits we're looking for
> + * @data: additional data - unused
> + *
> + * Iterate over the bitmap to find the smallest free region
> + * which we can allocate the memory.
> + */
> +unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size,
> +		unsigned long start, unsigned int nr, void *data)
> +{
> +	unsigned long start_bit = size;
> +	unsigned long len = size + 1;
> +	unsigned long index;
> +
> +	index = bitmap_find_next_zero_area(map, size, start, nr, 0);
> +
> +	while (index < size) {
> +		int next_bit = find_next_bit(map, size, index + nr);
> +		if ((next_bit - index) < len) {
> +			len = next_bit - index;
> +			start_bit = index;
> +			if (len == nr)
> +				return start_bit;
> +		}
> +		index = bitmap_find_next_zero_area(map, size,
> +						   next_bit + 1, nr, 0);
> +	}
> +
> +	return start_bit;
> +}
> +EXPORT_SYMBOL(gen_pool_best_fit);

Re: [PATCH] genalloc: make possible to use a custom allocation algorithm

[Benjamin Gaignard]

>From b78b2fea3899c5170b780f5ff138490ac6cf4cb7 Mon Sep 17 00:00:00 2001
From: Benjamin Gaignard <benjamin.gaignard@stericsson.com>
Date: Thu, 13 Sep 2012 11:29:03 +0200
Subject: [PATCH] genalloc: make possible to use a custom allocation algorithm

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.
As I can't predict all the possible requirements/needs for all allocation
uses cases, I add a "free" field 'void *data' to pass any needed information
to the allocation function. For example 'data' could be used to handle
a structure
where you store the alignment, the expected memory bank, the requester
device, or any information that could influence the allocation algorithm.

An usage example may look like this:
struct my_pool_constraints {
	int align;
	int bank;
	...
};

unsigned long my_custom_algo(unsigned long *map, unsigned long size,
		unsigned long start, unsigned int nr, void *data)
{
	struct my_pool_constraints *constraints = data;
	...
	deal with allocation contraints
	...
	return the index in bitmap where perform the allocation
}

void create_my_pool()
{
	struct my_pool_constraints c;
	struct gen_pool *pool = gen_pool_create(...);
	gen_pool_add(pool, ...);
	gen_pool_set_algo(pool, my_custom_algo, &c);
}

Add of best-fit algorithm function:
most of the time best-fit is slower then first-fit but memory fragmentation
is lower. The random buffer allocation/free tests don't show any arithmetic
relation between the allocation time and fragmentation but the
best-fit algorithm
is sometime able to perform the allocation when the first-fit can't.

This new algorithm help to remove static allocations on ESRAM, a small but
fast on-chip RAM of few KB, used for high-performance uses cases like DMA
linked lists, graphic accelerators, encoders/decoders. On the Ux500
(in the ARM tree) we have define 5 ESRAM banks of 128 KB each and use of
static allocations becomes unmaintainable:
cd arch/arm/mach-ux500 && grep -r ESRAM .
./include/mach/db8500-regs.h:/* Base address and bank offsets for ESRAM */
./include/mach/db8500-regs.h:#define U8500_ESRAM_BASE   0x40000000
./include/mach/db8500-regs.h:#define U8500_ESRAM_BANK_SIZE      0x00020000
./include/mach/db8500-regs.h:#define U8500_ESRAM_BANK0  U8500_ESRAM_BASE
./include/mach/db8500-regs.h:#define
U8500_ESRAM_BANK1       (U8500_ESRAM_BASE + U8500_ESRAM_BANK_SIZE)
./include/mach/db8500-regs.h:#define
U8500_ESRAM_BANK2       (U8500_ESRAM_BANK1 + U8500_ESRAM_BANK_SIZE)
./include/mach/db8500-regs.h:#define
U8500_ESRAM_BANK3       (U8500_ESRAM_BANK2 + U8500_ESRAM_BANK_SIZE)
./include/mach/db8500-regs.h:#define
U8500_ESRAM_BANK4       (U8500_ESRAM_BANK3 + U8500_ESRAM_BANK_SIZE)
./include/mach/db8500-regs.h:#define U8500_ESRAM_DMA_LCPA_OFFSET     0x10000
./include/mach/db8500-regs.h:#define U8500_DMA_LCPA_BASE
(U8500_ESRAM_BANK0 + U8500_ESRAM_DMA_LCPA_OFFSET)
./include/mach/db8500-regs.h:#define U8500_DMA_LCLA_BASE U8500_ESRAM_BANK4

I want to use genalloc to do dynamic allocations but I need to be able to
fine tune the allocation algorithm. I my case best-fit algorithm give
better results than first-fit, but it will not be true for every use case.

Signed-off-by: Benjamin Gaignard <benjamin.gaignard@stericsson.com>
---
 include/linux/genalloc.h |   27 ++++++++++++++
 lib/genalloc.c           |   88 +++++++++++++++++++++++++++++++++++++++++++---
 2 files changed, 111 insertions(+), 4 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 5e98eeb..dd7c569 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -29,6 +29,20 @@

 #ifndef __GENALLOC_H__
 #define __GENALLOC_H__
+/**
+ * Allocation callback function type definition
+ * @map: Pointer to bitmap
+ * @size: The bitmap size in bits
+ * @start: The bitnumber to start searching at
+ * @nr: The number of zeroed bits we're looking for
+ * @data: optional additional data used by @genpool_algo_t
+ */
+typedef unsigned long (*genpool_algo_t)(unsigned long *map,
+			unsigned long size,
+			unsigned long start,
+			unsigned int nr,
+			void *data);
+
 /*
  *  General purpose special memory pool descriptor.
  */
@@ -36,6 +50,9 @@ struct gen_pool {
 	spinlock_t lock;
 	struct list_head chunks;	/* list of chunks in this pool */
 	int min_alloc_order;		/* minimum allocation order */
+
+	genpool_algo_t algo;		/* allocation function */
+	void *data;
 };

 /*
@@ -78,4 +95,14 @@ 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 *pool, genpool_algo_t algo,
+		void *data);
+
+extern unsigned long gen_pool_first_fit(unsigned long *map, unsigned long size,
+		unsigned long start, unsigned int nr, void *data);
+
+extern unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size,
+		unsigned long start, unsigned int nr, void *data);
+
 #endif /* __GENALLOC_H__ */
diff --git a/lib/genalloc.c b/lib/genalloc.c
index 6bc04aa..ca208a9 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,80 @@ 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
+ * @algo: custom algorithm function
+ * @data: additional data used by @algo
+ *
+ * Call @algo for each memory allocation in the pool.
+ * If @algo is NULL use gen_pool_first_fit as default
+ * memory allocation function.
+ */
+void gen_pool_set_algo(struct gen_pool *pool, genpool_algo_t algo, void *data)
+{
+	rcu_read_lock();
+
+	pool->algo = algo;
+	if (!pool->algo)
+		pool->algo = gen_pool_first_fit;
+
+	pool->data = data;
+
+	rcu_read_unlock();
+}
+EXPORT_SYMBOL(gen_pool_set_algo);
+
+/**
+ * gen_pool_first_fit - find the first available region
+ * of memory matching the size requirement (no alignment constraint)
+ * @map: The address to base the search on
+ * @size: The bitmap size in bits
+ * @start: The bitnumber to start searching at
+ * @nr: The number of zeroed bits we're looking for
+ * @data: additional data - unused
+ */
+unsigned long gen_pool_first_fit(unsigned long *map, unsigned long size,
+		unsigned long start, unsigned int nr, void *data)
+{
+	return bitmap_find_next_zero_area(map, size, start, nr, 0);
+}
+EXPORT_SYMBOL(gen_pool_first_fit);
+
+/**
+ * gen_pool_best_fit - find the best fitting region of memory
+ * macthing the size requirement (no alignment constraint)
+ * @map: The address to base the search on
+ * @size: The bitmap size in bits
+ * @start: The bitnumber to start searching at
+ * @nr: The number of zeroed bits we're looking for
+ * @data: additional data - unused
+ *
+ * Iterate over the bitmap to find the smallest free region
+ * which we can allocate the memory.
+ */
+unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size,
+		unsigned long start, unsigned int nr, void *data)
+{
+	unsigned long start_bit = size;
+	unsigned long len = size + 1;
+	unsigned long index;
+
+	index = bitmap_find_next_zero_area(map, size, start, nr, 0);
+
+	while (index < size) {
+		int next_bit = find_next_bit(map, size, index + nr);
+		if ((next_bit - index) < len) {
+			len = next_bit - index;
+			start_bit = index;
+			if (len == nr)
+				return start_bit;
+		}
+		index = bitmap_find_next_zero_area(map, size,
+						   next_bit + 1, nr, 0);
+	}
+
+	return start_bit;
+}
+EXPORT_SYMBOL(gen_pool_best_fit);
-- 
1.7.10