Patch "lib/genalloc.c: start search from start of chunk" has been added to the 4.4-stable tree

This is a note to let you know that I've just added the patch titled

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

to the 4.4-stable tree which can be found at:
http://www.kernel.org/git/?p=linux/kernel/git/stable/stable-queue.git;a=summary

The filename of the patch is:
lib-genalloc.c-start-search-from-start-of-chunk.patch
and it can be found in the queue-4.4 subdirectory.

If you, or anyone else, feels it should not be added to the stable tree, please let <[email protected]> know about it.

From: Daniel Mentz <[email protected]>
Date: Thu, 27 Oct 2016 17:46:59 -0700
Subject: lib/genalloc.c: start search from start of chunk

From: Daniel Mentz <[email protected]>

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.

---
 lib/genalloc.c |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

@@ -273,7 +273,7 @@ unsigned long gen_pool_alloc(struct gen_
 	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());

@@ -288,6 +288,7 @@ unsigned long gen_pool_alloc(struct gen_
 		if (size > atomic_read(&chunk->avail))
 			continue;
 
+		start_bit = 0;
 		end_bit = chunk_size(chunk) >> order;
 retry:
 		start_bit = pool->algo(chunk->bits, end_bit, start_bit, nbits,

Patches currently in stable-queue which might be from [email protected] are

queue-4.4/lib-genalloc.c-start-search-from-start-of-chunk.patch