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

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 <[email protected]>

Cc Andrew Morton <[email protected]>

Cc Arnd Bergmann <[email protected]>

Cc Catalin Marinas <[email protected]>

Cc Dan Williams <[email protected]>

Cc David Riley <[email protected]>

Cc Eric Miao <[email protected]>

Cc Grant Likely <[email protected]>

Cc Greg Kroah-Hartman <[email protected]>

Cc Haojian Zhuang <[email protected]>

Cc Huang Ying <[email protected]>

Cc Jaroslav Kysela <[email protected]>

Cc Kevin Hilman <[email protected]>

Cc Laura Abbott <[email protected]>

Cc Liam Girdwood <[email protected]>

Cc Mark Brown <[email protected]>

Cc Mathieu Desnoyers <[email protected]>

Cc Mauro Carvalho Chehab <[email protected]>

Cc Olof Johansson <[email protected]>

Cc Ritesh Harjain <[email protected]>

Cc Rob Herring <[email protected]>

Cc Russell King <[email protected]>

Cc Sekhar Nori <[email protected]>

Cc Takashi Iwai <[email protected]>

Cc Thadeu Lima de Souza Cascardo <[email protected]>

Cc Thierry Reding <[email protected]>

Cc Vinod Koul <[email protected]>

Cc Vladimir Zapolskiy <[email protected]>

Cc Will Deacon <[email protected]>

Signed-off-by Daniel Mentz <[email protected]>

---
lib/genalloc.c | 3 ++-

1 file changed, 2 insertions(+), 1 deletion(-)

lib/genalloc.c +1 -1

index 0a11396..144fe6b 100644
@@ -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());

lib/genalloc.c +1 -0

@@ -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

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.

Quoted 18 lines · 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.

Quoted 9 lines

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 <[email protected]>

Will

Quoted 29 lines · On Wed, 26 Oct 2016 19:09:51 +0100 Will Deacon <[email protected]> wrote:

Quoted 27 lines · 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.

Quoted 1 line

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"?