[lkml]   [2016]   [Oct]   [25]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
Patch in this message
Subject[PATCH] lib/genalloc.c: Start search from start of chunk
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))

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 <>
Fixes: 7f184275aa30 ("lib, Make gen_pool memory allocator lockless")
Cc: Andi Kleen <>
Cc: Andrew Morton <>
Cc: Arnd Bergmann <>
Cc: Catalin Marinas <>
Cc: Dan Williams <>
Cc: David Riley <>
Cc: Eric Miao <>
Cc: Grant Likely <>
Cc: Greg Kroah-Hartman <>
Cc: Haojian Zhuang <>
Cc: Huang Ying <>
Cc: Jaroslav Kysela <>
Cc: Kevin Hilman <>
Cc: Laura Abbott <>
Cc: Liam Girdwood <>
Cc: Mark Brown <>
Cc: Mathieu Desnoyers <>
Cc: Mauro Carvalho Chehab <>
Cc: Olof Johansson <>
Cc: Ritesh Harjain <>
Cc: Russell King <>
Cc: Sekhar Nori <>
Cc: Takashi Iwai <>
Cc: Thadeu Lima de Souza Cascardo <>
Cc: Thierry Reding <>
Cc: Vinod Koul <>
Cc: Vladimir Zapolskiy <>
Cc: Will Deacon <>
Signed-off-by: Daniel Mentz <>
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;

@@ -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,
 \ /
  Last update: 2016-10-25 20:37    [W:0.069 / U:2.380 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site