[PATCH] lib/genalloc.c: Start search from start of chunk

[PATCH] lib/genalloc.c: Start search from start of chunk

[Daniel Mentz]

gen_pool_alloc_algo() iterates over all chunks of a pool trying to find
a contiguous block of memory that satisfies the allocation request.
The search should start at address zero of every chunk. However, as the
code stands today, this is only true for the first chunk. Due to a bug,
the search of subsequent chunks starts somewhere else:

The variables start_bit and end_bit are meant to describe the range that
should be searched and should be reset for every chunk that is searched.
Today, the code fails to reset start_bit to 0.

Fixes: 7f184275aa30 ("lib, Make gen_pool memory allocator lockless")
Cc: Andi Kleen <ak@linux.intel.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: Dan Williams <dan.j.williams@intel.com>
Cc: David Riley <davidriley@chromium.org>
Cc: Eric Miao <eric.y.miao@gmail.com>
Cc: Grant Likely <grant.likely@linaro.org>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc: Haojian Zhuang <haojian.zhuang@gmail.com>
Cc: Huang Ying <ying.huang@intel.com>
Cc: Jaroslav Kysela <perex@perex.cz>
Cc: Kevin Hilman <khilman@deeprootsystems.com>
Cc: Laura Abbott <lauraa@codeaurora.org>
Cc: Liam Girdwood <lgirdwood@gmail.com>
Cc: Mark Brown <broonie@kernel.org>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Mauro Carvalho Chehab <m.chehab@samsung.com>
Cc: Olof Johansson <olof@lixom.net>
Cc: Ritesh Harjain <ritesh.harjani@gmail.com>
Cc: Rob Herring <rob.herring@calxeda.com>
Cc: Russell King <linux@arm.linux.org.uk>
Cc: Sekhar Nori <nsekhar@ti.com>
Cc: Takashi Iwai <tiwai@suse.de>
Cc: Thadeu Lima de Souza Cascardo <cascardo@linux.vnet.ibm.com>
Cc: Thierry Reding <thierry.reding@gmail.com>
Cc: Vinod Koul <vinod.koul@intel.com>
Cc: Vladimir Zapolskiy <vladimir_zapolskiy@mentor.com>
Cc: Will Deacon <will.deacon@arm.com>
Signed-off-by: Daniel Mentz <danielmentz@google.com>
---
 lib/genalloc.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/genalloc.c b/lib/genalloc.c
index 0a11396..144fe6b 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -292,7 +292,7 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size,
 	struct gen_pool_chunk *chunk;
 	unsigned long addr = 0;
 	int order = pool->min_alloc_order;
-	int nbits, start_bit = 0, end_bit, remain;
+	int nbits, start_bit, end_bit, remain;
 
 #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
 	BUG_ON(in_nmi());
@@ -307,6 +307,7 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size,
 		if (size > atomic_read(&chunk->avail))
 			continue;
 
+		start_bit = 0;
 		end_bit = chunk_size(chunk) >> order;
 retry:
 		start_bit = algo(chunk->bits, end_bit, start_bit,
-- 
2.8.0.rc3.226.g39d4020

Re: [PATCH] lib/genalloc.c: Start search from start of chunk

[Mathieu Desnoyers]

----- On Oct 24, 2016, at 9:58 PM, Daniel Mentz danielmentz@google.com wrote:

> gen_pool_alloc_algo() iterates over all chunks of a pool trying to find
> a contiguous block of memory that satisfies the allocation request.
> The search should start at address zero of every chunk. However, as the
> code stands today, this is only true for the first chunk. Due to a bug,
> the search of subsequent chunks starts somewhere else:

So in a situation where a chunk has enough bytes left to fulfill the
request, but they are not contiguous, the check:

                if (size > atomic_read(&chunk->avail))
                        continue;

would not trigger, and we'd end up setting start_bit to the value end_bit
after returning from the algo() call.

So if the following chunks have the same size as the nearly full chunk,
we end up failing memory allocation for all following chunks even
though there is plenty of room left.

I would be tempted to add a bit of explanation on the failure
modes to the commit message (e.g. scenario above).

Other than that:

Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>

Thanks!

Mathieu

> 
> The variables start_bit and end_bit are meant to describe the range that
> should be searched and should be reset for every chunk that is searched.
> Today, the code fails to reset start_bit to 0.
> 
> Fixes: 7f184275aa30 ("lib, Make gen_pool memory allocator lockless")
> Cc: Andi Kleen <ak@linux.intel.com>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Cc: Arnd Bergmann <arnd@arndb.de>
> Cc: Catalin Marinas <catalin.marinas@arm.com>
> Cc: Dan Williams <dan.j.williams@intel.com>
> Cc: David Riley <davidriley@chromium.org>
> Cc: Eric Miao <eric.y.miao@gmail.com>
> Cc: Grant Likely <grant.likely@linaro.org>
> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
> Cc: Haojian Zhuang <haojian.zhuang@gmail.com>
> Cc: Huang Ying <ying.huang@intel.com>
> Cc: Jaroslav Kysela <perex@perex.cz>
> Cc: Kevin Hilman <khilman@deeprootsystems.com>
> Cc: Laura Abbott <lauraa@codeaurora.org>
> Cc: Liam Girdwood <lgirdwood@gmail.com>
> Cc: Mark Brown <broonie@kernel.org>
> Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
> Cc: Mauro Carvalho Chehab <m.chehab@samsung.com>
> Cc: Olof Johansson <olof@lixom.net>
> Cc: Ritesh Harjain <ritesh.harjani@gmail.com>
> Cc: Rob Herring <rob.herring@calxeda.com>
> Cc: Russell King <linux@arm.linux.org.uk>
> Cc: Sekhar Nori <nsekhar@ti.com>
> Cc: Takashi Iwai <tiwai@suse.de>
> Cc: Thadeu Lima de Souza Cascardo <cascardo@linux.vnet.ibm.com>
> Cc: Thierry Reding <thierry.reding@gmail.com>
> Cc: Vinod Koul <vinod.koul@intel.com>
> Cc: Vladimir Zapolskiy <vladimir_zapolskiy@mentor.com>
> Cc: Will Deacon <will.deacon@arm.com>
> Signed-off-by: Daniel Mentz <danielmentz@google.com>
> ---
> lib/genalloc.c | 3 ++-
> 1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/lib/genalloc.c b/lib/genalloc.c
> index 0a11396..144fe6b 100644
> --- a/lib/genalloc.c
> +++ b/lib/genalloc.c
> @@ -292,7 +292,7 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool,
> size_t size,
> 	struct gen_pool_chunk *chunk;
> 	unsigned long addr = 0;
> 	int order = pool->min_alloc_order;
> -	int nbits, start_bit = 0, end_bit, remain;
> +	int nbits, start_bit, end_bit, remain;
> 
> #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
> 	BUG_ON(in_nmi());
> @@ -307,6 +307,7 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool,
> size_t size,
> 		if (size > atomic_read(&chunk->avail))
> 			continue;
> 
> +		start_bit = 0;
> 		end_bit = chunk_size(chunk) >> order;
> retry:
> 		start_bit = algo(chunk->bits, end_bit, start_bit,
> --
> 2.8.0.rc3.226.g39d4020

-- 
Mathieu Desnoyers
EfficiOS Inc.
http://www.efficios.com

[PATCH] lib/genalloc.c: Start search from start of chunk

[Daniel Mentz]

gen_pool_alloc_algo() iterates over the chunks of a pool trying to find
a contiguous block of memory that satisfies the allocation request.

The shortcut

	if (size > atomic_read(&chunk->avail))
		continue;

makes the loop skip over chunks that do not have enough bytes left to
fulfill the request. There are two situations, though, where an
allocation might still fail:

(1) The available memory is not contiguous, i.e. the request cannot be
fulfilled due to external fragmentation.

(2) A race condition. Another thread runs the same code concurrently and
is quicker to grab the available memory.

In those situations, the loop calls pool->algo() to search the entire
chunk, and pool->algo() returns some value that is >= end_bit to
indicate that the search failed.  This return value is then assigned to
start_bit. The variables start_bit and end_bit describe the range that
should be searched, and this range should be reset for every chunk that
is searched.  Today, the code fails to reset start_bit to 0.  As a
result, prefixes of subsequent chunks are ignored. Memory allocations
might fail even though there is plenty of room left in these prefixes of
those other chunks.

Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Fixes: 7f184275aa30 ("lib, Make gen_pool memory allocator lockless")
Cc: Andi Kleen <ak@linux.intel.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Arnd Bergmann <arnd@arndb.de>
Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: Dan Williams <dan.j.williams@intel.com>
Cc: David Riley <davidriley@chromium.org>
Cc: Eric Miao <eric.y.miao@gmail.com>
Cc: Grant Likely <grant.likely@linaro.org>
Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Cc: Haojian Zhuang <haojian.zhuang@gmail.com>
Cc: Huang Ying <ying.huang@intel.com>
Cc: Jaroslav Kysela <perex@perex.cz>
Cc: Kevin Hilman <khilman@deeprootsystems.com>
Cc: Laura Abbott <lauraa@codeaurora.org>
Cc: Liam Girdwood <lgirdwood@gmail.com>
Cc: Mark Brown <broonie@kernel.org>
Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Mauro Carvalho Chehab <m.chehab@samsung.com>
Cc: Olof Johansson <olof@lixom.net>
Cc: Ritesh Harjain <ritesh.harjani@gmail.com>
Cc: Russell King <linux@arm.linux.org.uk>
Cc: Sekhar Nori <nsekhar@ti.com>
Cc: Takashi Iwai <tiwai@suse.de>
Cc: Thadeu Lima de Souza Cascardo <cascardo@linux.vnet.ibm.com>
Cc: Thierry Reding <thierry.reding@gmail.com>
Cc: Vinod Koul <vinod.koul@intel.com>
Cc: Vladimir Zapolskiy <vladimir_zapolskiy@mentor.com>
Cc: Will Deacon <will.deacon@arm.com>
Signed-off-by: Daniel Mentz <danielmentz@google.com>
---
 lib/genalloc.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/genalloc.c b/lib/genalloc.c
index 0a11396..144fe6b 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -292,7 +292,7 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size,
 	struct gen_pool_chunk *chunk;
 	unsigned long addr = 0;
 	int order = pool->min_alloc_order;
-	int nbits, start_bit = 0, end_bit, remain;
+	int nbits, start_bit, end_bit, remain;
 
 #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
 	BUG_ON(in_nmi());
@@ -307,6 +307,7 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size,
 		if (size > atomic_read(&chunk->avail))
 			continue;
 
+		start_bit = 0;
 		end_bit = chunk_size(chunk) >> order;
 retry:
 		start_bit = algo(chunk->bits, end_bit, start_bit,
-- 
2.8.0.rc3.226.g39d4020

Re: [PATCH] lib/genalloc.c: Start search from start of chunk

[Will Deacon]

On Tue, Oct 25, 2016 at 11:36:44AM -0700, Daniel Mentz wrote:
> gen_pool_alloc_algo() iterates over the chunks of a pool trying to find
> a contiguous block of memory that satisfies the allocation request.
> 
> The shortcut
> 
> 	if (size > atomic_read(&chunk->avail))
> 		continue;
> 
> makes the loop skip over chunks that do not have enough bytes left to
> fulfill the request. There are two situations, though, where an
> allocation might still fail:
> 
> (1) The available memory is not contiguous, i.e. the request cannot be
> fulfilled due to external fragmentation.
> 
> (2) A race condition. Another thread runs the same code concurrently and
> is quicker to grab the available memory.
> 
> In those situations, the loop calls pool->algo() to search the entire
> chunk, and pool->algo() returns some value that is >= end_bit to
> indicate that the search failed.  This return value is then assigned to
> start_bit. The variables start_bit and end_bit describe the range that
> should be searched, and this range should be reset for every chunk that
> is searched.  Today, the code fails to reset start_bit to 0.  As a
> result, prefixes of subsequent chunks are ignored. Memory allocations
> might fail even though there is plenty of room left in these prefixes of
> those other chunks.

Please add a CC stable. With that:

Acked-by: Will Deacon <will.deacon@arm.com>

Will

Re: [PATCH] lib/genalloc.c: Start search from start of chunk

[Andrew Morton]

On Wed, 26 Oct 2016 19:09:51 +0100 Will Deacon <will.deacon@arm.com> wrote:

> On Tue, Oct 25, 2016 at 11:36:44AM -0700, Daniel Mentz wrote:
> > gen_pool_alloc_algo() iterates over the chunks of a pool trying to find
> > a contiguous block of memory that satisfies the allocation request.
> > 
> > The shortcut
> > 
> > 	if (size > atomic_read(&chunk->avail))
> > 		continue;
> > 
> > makes the loop skip over chunks that do not have enough bytes left to
> > fulfill the request. There are two situations, though, where an
> > allocation might still fail:
> > 
> > (1) The available memory is not contiguous, i.e. the request cannot be
> > fulfilled due to external fragmentation.
> > 
> > (2) A race condition. Another thread runs the same code concurrently and
> > is quicker to grab the available memory.
> > 
> > In those situations, the loop calls pool->algo() to search the entire
> > chunk, and pool->algo() returns some value that is >= end_bit to
> > indicate that the search failed.  This return value is then assigned to
> > start_bit. The variables start_bit and end_bit describe the range that
> > should be searched, and this range should be reset for every chunk that
> > is searched.  Today, the code fails to reset start_bit to 0.  As a
> > result, prefixes of subsequent chunks are ignored. Memory allocations
> > might fail even though there is plenty of room left in these prefixes of
> > those other chunks.
> 
> Please add a CC stable.

You sure?  The changelog doesn't describe the end-user impacts very
well (it should always do so, please) but I'm thinking "little impact"?

> With that:
> 
> Acked-by: Will Deacon <will.deacon@arm.com>
> 
> Will

Re: [PATCH] lib/genalloc.c: Start search from start of chunk

[Daniel Mentz]

On Wed, Oct 26, 2016 at 12:39 PM, Andrew Morton
<akpm@linux-foundation.org> wrote:
> On Wed, 26 Oct 2016 19:09:51 +0100 Will Deacon <will.deacon@arm.com> wrote:
>
>> On Tue, Oct 25, 2016 at 11:36:44AM -0700, Daniel Mentz wrote:
>> > gen_pool_alloc_algo() iterates over the chunks of a pool trying to find
>> > a contiguous block of memory that satisfies the allocation request.
>> >
>> > The shortcut
>> >
>> >     if (size > atomic_read(&chunk->avail))
>> >             continue;
>> >
>> > makes the loop skip over chunks that do not have enough bytes left to
>> > fulfill the request. There are two situations, though, where an
>> > allocation might still fail:
>> >
>> > (1) The available memory is not contiguous, i.e. the request cannot be
>> > fulfilled due to external fragmentation.
>> >
>> > (2) A race condition. Another thread runs the same code concurrently and
>> > is quicker to grab the available memory.
>> >
>> > In those situations, the loop calls pool->algo() to search the entire
>> > chunk, and pool->algo() returns some value that is >= end_bit to
>> > indicate that the search failed.  This return value is then assigned to
>> > start_bit. The variables start_bit and end_bit describe the range that
>> > should be searched, and this range should be reset for every chunk that
>> > is searched.  Today, the code fails to reset start_bit to 0.  As a
>> > result, prefixes of subsequent chunks are ignored. Memory allocations
>> > might fail even though there is plenty of room left in these prefixes of
>> > those other chunks.
>>
>> Please add a CC stable.
>
> You sure?  The changelog doesn't describe the end-user impacts very
> well (it should always do so, please) but I'm thinking "little impact"?

Sorry for not describing the end-user impact. This bug does actually
not affect our specific application since we are using genalloc with
only a single chunk (through arch/arm/mm/dma-mapping.c). I found this
bug by coincident while reviewing the code for a different reason.

While trying to determine the user impact, I found some places where
people add multiple chunks. Whether or not these users hit this bug
depends on the patterns in which they allocate memory through genalloc
and whether an allocation request can't be fulfilled due to external
fragmentation.

I'd say it's unlikely for end-users to hit this bug but if they do,
the user impact is probably significant.