[PATCH] lib/genaloc: Fix allocation of aligned buffer from non-aligned chunk

[PATCH] lib/genaloc: Fix allocation of aligned buffer from non-aligned chunk

[Alexey Skidanov]

On success, gen_pool_first_fit_align() returns the bit number such that
chunk_start_addr + (bit << order) is properly aligned. On failure,
the bitmap size parameter is returned.

When the chunk_start_addr isn't aligned properly, the
chunk_start_addr + (bit << order) isn't aligned too.

To fix this, gen_pool_first_fit_align() takes into account
the chunk_start_addr alignment and returns the bit value such that
chunk_start_addr + (bit << order) is properly aligned
(exactly as it done in CMA).

Link: https://lkml.kernel.org/lkml/a170cf65-6884-3592-1de9-4c235888cc8a@intel.com
Signed-off-by: Alexey Skidanov <alexey.skidanov@intel.com>
---
 include/linux/genalloc.h | 13 +++++++------
 lib/genalloc.c           | 20 ++++++++++++--------
 2 files changed, 19 insertions(+), 14 deletions(-)

diff --git a/include/linux/genalloc.h b/include/linux/genalloc.h
index 872f930..dd0a452 100644
--- a/include/linux/genalloc.h
+++ b/include/linux/genalloc.h
@@ -51,7 +51,8 @@ typedef unsigned long (*genpool_algo_t)(unsigned long *map,
 			unsigned long size,
 			unsigned long start,
 			unsigned int nr,
-			void *data, struct gen_pool *pool);
+			void *data, struct gen_pool *pool,
+			unsigned long start_addr);
 
 /*
  *  General purpose special memory pool descriptor.
@@ -131,24 +132,24 @@ extern void gen_pool_set_algo(struct gen_pool *pool, genpool_algo_t algo,
 
 extern unsigned long gen_pool_first_fit(unsigned long *map, unsigned long size,
 		unsigned long start, unsigned int nr, void *data,
-		struct gen_pool *pool);
+		struct gen_pool *pool, unsigned long start_addr);
 
 extern unsigned long gen_pool_fixed_alloc(unsigned long *map,
 		unsigned long size, unsigned long start, unsigned int nr,
-		void *data, struct gen_pool *pool);
+		void *data, struct gen_pool *pool, unsigned long start_addr);
 
 extern unsigned long gen_pool_first_fit_align(unsigned long *map,
 		unsigned long size, unsigned long start, unsigned int nr,
-		void *data, struct gen_pool *pool);
+		void *data, struct gen_pool *pool, unsigned long start_addr);
 
 
 extern unsigned long gen_pool_first_fit_order_align(unsigned long *map,
 		unsigned long size, unsigned long start, unsigned int nr,
-		void *data, struct gen_pool *pool);
+		void *data, struct gen_pool *pool, unsigned long start_addr);
 
 extern unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size,
 		unsigned long start, unsigned int nr, void *data,
-		struct gen_pool *pool);
+		struct gen_pool *pool, unsigned long start_addr);
 
 
 extern struct gen_pool *devm_gen_pool_create(struct device *dev,
diff --git a/lib/genalloc.c b/lib/genalloc.c
index ca06adc..033817a 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -311,7 +311,7 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size,
 		end_bit = chunk_size(chunk) >> order;
 retry:
 		start_bit = algo(chunk->bits, end_bit, start_bit,
-				 nbits, data, pool);
+				 nbits, data, pool, chunk->start_addr);
 		if (start_bit >= end_bit)
 			continue;
 		remain = bitmap_set_ll(chunk->bits, start_bit, nbits);
@@ -525,7 +525,7 @@ EXPORT_SYMBOL(gen_pool_set_algo);
  */
 unsigned long gen_pool_first_fit(unsigned long *map, unsigned long size,
 		unsigned long start, unsigned int nr, void *data,
-		struct gen_pool *pool)
+		struct gen_pool *pool, unsigned long start_add)
 {
 	return bitmap_find_next_zero_area(map, size, start, nr, 0);
 }
@@ -543,16 +543,19 @@ EXPORT_SYMBOL(gen_pool_first_fit);
  */
 unsigned long gen_pool_first_fit_align(unsigned long *map, unsigned long size,
 		unsigned long start, unsigned int nr, void *data,
-		struct gen_pool *pool)
+		struct gen_pool *pool, unsigned long start_addr)
 {
 	struct genpool_data_align *alignment;
-	unsigned long align_mask;
+	unsigned long align_mask, align_off;
 	int order;
 
 	alignment = data;
 	order = pool->min_alloc_order;
 	align_mask = ((alignment->align + (1UL << order) - 1) >> order) - 1;
-	return bitmap_find_next_zero_area(map, size, start, nr, align_mask);
+	align_off = (start_addr & (alignment->align - 1)) >> order;
+
+	return bitmap_find_next_zero_area_off(map, size, start, nr,
+					      align_mask, align_off);
 }
 EXPORT_SYMBOL(gen_pool_first_fit_align);
 
@@ -567,7 +570,7 @@ EXPORT_SYMBOL(gen_pool_first_fit_align);
  */
 unsigned long gen_pool_fixed_alloc(unsigned long *map, unsigned long size,
 		unsigned long start, unsigned int nr, void *data,
-		struct gen_pool *pool)
+		struct gen_pool *pool, unsigned long start_add)
 {
 	struct genpool_data_fixed *fixed_data;
 	int order;
@@ -601,7 +604,8 @@ EXPORT_SYMBOL(gen_pool_fixed_alloc);
  */
 unsigned long gen_pool_first_fit_order_align(unsigned long *map,
 		unsigned long size, unsigned long start,
-		unsigned int nr, void *data, struct gen_pool *pool)
+		unsigned int nr, void *data, struct gen_pool *pool,
+		unsigned long start_addr)
 {
 	unsigned long align_mask = roundup_pow_of_two(nr) - 1;
 
@@ -624,7 +628,7 @@ EXPORT_SYMBOL(gen_pool_first_fit_order_align);
  */
 unsigned long gen_pool_best_fit(unsigned long *map, unsigned long size,
 		unsigned long start, unsigned int nr, void *data,
-		struct gen_pool *pool)
+		struct gen_pool *pool, unsigned long start_add)
 {
 	unsigned long start_bit = size;
 	unsigned long len = size + 1;
-- 
2.7.4

Re: [PATCH] lib/genaloc: Fix allocation of aligned buffer from non-aligned chunk

[Andrew Morton]

On Tue,  6 Nov 2018 14:20:53 +0200 Alexey Skidanov <alexey.skidanov@intel.com> wrote:

> On success, gen_pool_first_fit_align() returns the bit number such that
> chunk_start_addr + (bit << order) is properly aligned. On failure,
> the bitmap size parameter is returned.
> 
> When the chunk_start_addr isn't aligned properly, the
> chunk_start_addr + (bit << order) isn't aligned too.
> 
> To fix this, gen_pool_first_fit_align() takes into account
> the chunk_start_addr alignment and returns the bit value such that
> chunk_start_addr + (bit << order) is properly aligned
> (exactly as it done in CMA).

Why does this need "fixing"?  Are there current callers which can
misalign chunk_start_addr?  Or is there a requirement that future
callers can misalign chunk_start_addr?

Re: [PATCH] lib/genaloc: Fix allocation of aligned buffer from non-aligned chunk

[Andrew Morton]

On Tue,  6 Nov 2018 14:20:53 +0200 Alexey Skidanov <alexey.skidanov@intel.com> wrote:

> On success, gen_pool_first_fit_align() returns the bit number such that
> chunk_start_addr + (bit << order) is properly aligned. On failure,
> the bitmap size parameter is returned.
> 
> When the chunk_start_addr isn't aligned properly, the
> chunk_start_addr + (bit << order) isn't aligned too.
> 
> To fix this, gen_pool_first_fit_align() takes into account
> the chunk_start_addr alignment and returns the bit value such that
> chunk_start_addr + (bit << order) is properly aligned
> (exactly as it done in CMA).
> 
> ...
>
> --- a/include/linux/genalloc.h
> +++ b/include/linux/genalloc.h
>
> ...
>
> +		struct gen_pool *pool, unsigned long start_add)
>
> ...
>
> +		struct gen_pool *pool, unsigned long start_add)
>
> ...
>
> +		struct gen_pool *pool, unsigned long start_add)
>
> ...
>

We have three typos here.  Which makes me wonder why we're passing the
new argument and then not using it?

Re: [PATCH] lib/genaloc: Fix allocation of aligned buffer from non-aligned chunk

[Alexey Skidanov]

On 11/7/18 12:11 AM, Andrew Morton wrote:
> On Tue,  6 Nov 2018 14:20:53 +0200 Alexey Skidanov <alexey.skidanov@intel.com> wrote:
> 
>> On success, gen_pool_first_fit_align() returns the bit number such that
>> chunk_start_addr + (bit << order) is properly aligned. On failure,
>> the bitmap size parameter is returned.
>>
>> When the chunk_start_addr isn't aligned properly, the
>> chunk_start_addr + (bit << order) isn't aligned too.
>>
>> To fix this, gen_pool_first_fit_align() takes into account
>> the chunk_start_addr alignment and returns the bit value such that
>> chunk_start_addr + (bit << order) is properly aligned
>> (exactly as it done in CMA).
> 
> Why does this need "fixing"?  Are there current callers which can
> misalign chunk_start_addr?  Or is there a requirement that future
> callers can misalign chunk_start_addr?
> 
I work on adding aligned allocation support for ION heaps
(https://www.spinics.net/lists/linux-driver-devel/msg118754.html). Two
of these heaps use genpool internally.

If you want to have an ability to allocate buffers aligned on different
boundaries (for example, 4K, 1MB, ...), this fix actually removes the
requirement for chunk_start_addr to be aligned on the max possible
alignment.

Thanks,
Alexey

Re: [PATCH] lib/genaloc: Fix allocation of aligned buffer from non-aligned chunk

[Alexey Skidanov]

On 11/7/18 12:15 AM, Andrew Morton wrote:
> On Tue,  6 Nov 2018 14:20:53 +0200 Alexey Skidanov <alexey.skidanov@intel.com> wrote:
> 
>> On success, gen_pool_first_fit_align() returns the bit number such that
>> chunk_start_addr + (bit << order) is properly aligned. On failure,
>> the bitmap size parameter is returned.
>>
>> When the chunk_start_addr isn't aligned properly, the
>> chunk_start_addr + (bit << order) isn't aligned too.
>>
>> To fix this, gen_pool_first_fit_align() takes into account
>> the chunk_start_addr alignment and returns the bit value such that
>> chunk_start_addr + (bit << order) is properly aligned
>> (exactly as it done in CMA).
>>
>> ...
>>
>> --- a/include/linux/genalloc.h
>> +++ b/include/linux/genalloc.h
>>
>> ...
>>
>> +		struct gen_pool *pool, unsigned long start_add)
>>
>> ...
>>
>> +		struct gen_pool *pool, unsigned long start_add)
>>
>> ...
>>
>> +		struct gen_pool *pool, unsigned long start_add)
>>
>> ...
>>
> 
> We have three typos here.  Which makes me wonder why we're passing the
> new argument and then not using it?
> 
genpool uses allocation callbacks function that implement some
allocation strategy - bes fit, first fit, ... All of them has the same
type. The added chunk start_addr is used only in one of them -
gen_pool_first_fit_align()

Thanks,
Alexey

Re: [PATCH] lib/genaloc: Fix allocation of aligned buffer from non-aligned chunk

[Andrew Morton]

On Wed, 7 Nov 2018 08:27:31 +0200 Alexey Skidanov <alexey.skidanov@intel.com> wrote:

> 
> 
> On 11/7/18 12:15 AM, Andrew Morton wrote:
> > On Tue,  6 Nov 2018 14:20:53 +0200 Alexey Skidanov <alexey.skidanov@intel.com> wrote:
> > 
> >> On success, gen_pool_first_fit_align() returns the bit number such that
> >> chunk_start_addr + (bit << order) is properly aligned. On failure,
> >> the bitmap size parameter is returned.
> >>
> >> When the chunk_start_addr isn't aligned properly, the
> >> chunk_start_addr + (bit << order) isn't aligned too.
> >>
> >> To fix this, gen_pool_first_fit_align() takes into account
> >> the chunk_start_addr alignment and returns the bit value such that
> >> chunk_start_addr + (bit << order) is properly aligned
> >> (exactly as it done in CMA).
> >>
> >> ...
> >>
> >> --- a/include/linux/genalloc.h
> >> +++ b/include/linux/genalloc.h
> >>
> >> ...
> >>
> >> +		struct gen_pool *pool, unsigned long start_add)
> >>
> >> ...
> >>
> >> +		struct gen_pool *pool, unsigned long start_add)
> >>
> >> ...
> >>
> >> +		struct gen_pool *pool, unsigned long start_add)
> >>
> >> ...
> >>
> > 
> > We have three typos here.  Which makes me wonder why we're passing the
> > new argument and then not using it?
> > 
> genpool uses allocation callbacks function that implement some
> allocation strategy - bes fit, first fit, ... All of them has the same
> type. The added chunk start_addr is used only in one of them -
> gen_pool_first_fit_align()

OK, but the argument name here is start_add, not start_addr.

Re: [PATCH] lib/genaloc: Fix allocation of aligned buffer from non-aligned chunk

[Andrew Morton]

On Wed, 7 Nov 2018 08:21:07 +0200 Alexey Skidanov <alexey.skidanov@intel.com> wrote:

> > Why does this need "fixing"?  Are there current callers which can
> > misalign chunk_start_addr?  Or is there a requirement that future
> > callers can misalign chunk_start_addr?
> > 
> I work on adding aligned allocation support for ION heaps
> (https://www.spinics.net/lists/linux-driver-devel/msg118754.html). Two
> of these heaps use genpool internally.
> 
> If you want to have an ability to allocate buffers aligned on different
> boundaries (for example, 4K, 1MB, ...), this fix actually removes the
> requirement for chunk_start_addr to be aligned on the max possible
> alignment.

OK.  This sort of information should be in the changelog, please.  In
much detail.

Re: [PATCH] lib/genaloc: Fix allocation of aligned buffer from non-aligned chunk

[Alexey Skidanov]

On 11/8/18 00:12, Andrew Morton wrote:
> On Wed, 7 Nov 2018 08:27:31 +0200 Alexey Skidanov <alexey.skidanov@intel.com> wrote:
> 
>>
>>
>> On 11/7/18 12:15 AM, Andrew Morton wrote:
>>> On Tue,  6 Nov 2018 14:20:53 +0200 Alexey Skidanov <alexey.skidanov@intel.com> wrote:
>>>
>>>> On success, gen_pool_first_fit_align() returns the bit number such that
>>>> chunk_start_addr + (bit << order) is properly aligned. On failure,
>>>> the bitmap size parameter is returned.
>>>>
>>>> When the chunk_start_addr isn't aligned properly, the
>>>> chunk_start_addr + (bit << order) isn't aligned too.
>>>>
>>>> To fix this, gen_pool_first_fit_align() takes into account
>>>> the chunk_start_addr alignment and returns the bit value such that
>>>> chunk_start_addr + (bit << order) is properly aligned
>>>> (exactly as it done in CMA).
>>>>
>>>> ...
>>>>
>>>> --- a/include/linux/genalloc.h
>>>> +++ b/include/linux/genalloc.h
>>>>
>>>> ...
>>>>
>>>> +		struct gen_pool *pool, unsigned long start_add)
>>>>
>>>> ...
>>>>
>>>> +		struct gen_pool *pool, unsigned long start_add)
>>>>
>>>> ...
>>>>
>>>> +		struct gen_pool *pool, unsigned long start_add)
>>>>
>>>> ...
>>>>
>>>
>>> We have three typos here.  Which makes me wonder why we're passing the
>>> new argument and then not using it?
>>>
>> genpool uses allocation callbacks function that implement some
>> allocation strategy - bes fit, first fit, ... All of them has the same
>> type. The added chunk start_addr is used only in one of them -
>> gen_pool_first_fit_align()
> 
> OK, but the argument name here is start_add, not start_addr.
> 
Sure, I'll fix.

Re: [PATCH] lib/genaloc: Fix allocation of aligned buffer from non-aligned chunk

[Alexey Skidanov]

On 11/8/18 00:14, Andrew Morton wrote:
> On Wed, 7 Nov 2018 08:21:07 +0200 Alexey Skidanov <alexey.skidanov@intel.com> wrote:
> 
>>> Why does this need "fixing"?  Are there current callers which can
>>> misalign chunk_start_addr?  Or is there a requirement that future
>>> callers can misalign chunk_start_addr?
>>>
>> I work on adding aligned allocation support for ION heaps
>> (https://www.spinics.net/lists/linux-driver-devel/msg118754.html). Two
>> of these heaps use genpool internally.
>>
>> If you want to have an ability to allocate buffers aligned on different
>> boundaries (for example, 4K, 1MB, ...), this fix actually removes the
>> requirement for chunk_start_addr to be aligned on the max possible
>> alignment.
> 
> OK.  This sort of information should be in the changelog, please.  In
> much detail.
> 
Sure, I'll add this information and resend the patch.

Thanks,
Alexey