From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail.linuxfoundation.org ([140.211.169.12]:37414 "EHLO mail.linuxfoundation.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932309AbcKQIg5 (ORCPT ); Thu, 17 Nov 2016 03:36:57 -0500 Subject: Patch "lib/genalloc.c: start search from start of chunk" has been added to the 4.4-stable tree To: danielmentz@google.com, akpm@linux-foundation.org, gregkh@linuxfoundation.org, mathieu.desnoyers@efficios.com, torvalds@linux-foundation.org, will.deacon@arm.com Cc: , From: Date: Thu, 17 Nov 2016 09:36:57 +0100 Message-ID: <147937181723339@kroah.com> MIME-Version: 1.0 Content-Type: text/plain; charset=ANSI_X3.4-1968 Content-Transfer-Encoding: 8bit Sender: stable-owner@vger.kernel.org List-ID: 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 know about it. >>From 62e931fac45b17c2a42549389879411572f75804 Mon Sep 17 00:00:00 2001 From: Daniel Mentz Date: Thu, 27 Oct 2016 17:46:59 -0700 Subject: lib/genalloc.c: start search from start of chunk From: Daniel Mentz 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: http://lkml.kernel.org/r/1477420604-28918-1-git-send-email-danielmentz@google.com 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 --- lib/genalloc.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) --- a/lib/genalloc.c +++ b/lib/genalloc.c @@ -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 danielmentz@google.com are queue-4.4/lib-genalloc.c-start-search-from-start-of-chunk.patch