diff options
authorDaniel Mentz <>2016-10-27 17:46:59 -0700
committerGreg Kroah-Hartman <>2016-11-18 10:51:51 +0100
commitc1a2ada73dacd528a9a76936cfa1496981f0ea64 (patch)
parent06bb5ebedbb4da6236e1ffb57031c01088127444 (diff)
lib/genalloc.c: start search from start of chunk
commit 62e931fac45b17c2a42549389879411572f75804 upstream. 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. Fixes: 7f184275aa30 ("lib, Make gen_pool memory allocator lockless") Link: Signed-off-by: Daniel Mentz <> Reviewed-by: Mathieu Desnoyers <> Acked-by: Will Deacon <> Signed-off-by: Andrew Morton <> Signed-off-by: Linus Torvalds <> Signed-off-by: Greg Kroah-Hartman <>
1 files changed, 2 insertions, 1 deletions
diff --git a/lib/genalloc.c b/lib/genalloc.c
index 0a1139644d32..144fe6b1a03e 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;
@@ -307,6 +307,7 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size,
if (size > atomic_read(&chunk->avail))
+ start_bit = 0;
end_bit = chunk_size(chunk) >> order;
start_bit = algo(chunk->bits, end_bit, start_bit,