Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1759295AbcJYShN (ORCPT ); Tue, 25 Oct 2016 14:37:13 -0400 Received: from mail-pf0-f172.google.com ([209.85.192.172]:34699 "EHLO mail-pf0-f172.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751039AbcJYShK (ORCPT ); Tue, 25 Oct 2016 14:37:10 -0400 From: Daniel Mentz To: linux-kernel@vger.kernel.org Cc: Daniel Mentz , Andi Kleen , Andrew Morton , Arnd Bergmann , Catalin Marinas , Dan Williams , David Riley , Eric Miao , Grant Likely , Greg Kroah-Hartman , Haojian Zhuang , Huang Ying , Jaroslav Kysela , Kevin Hilman , Laura Abbott , Liam Girdwood , Mark Brown , Mathieu Desnoyers , Mauro Carvalho Chehab , Olof Johansson , Ritesh Harjain , Russell King , Sekhar Nori , Takashi Iwai , Thadeu Lima de Souza Cascardo , Thierry Reding , Vinod Koul , Vladimir Zapolskiy , Will Deacon Subject: [PATCH] lib/genalloc.c: Start search from start of chunk Date: Tue, 25 Oct 2016 11:36:44 -0700 Message-Id: <1477420604-28918-1-git-send-email-danielmentz@google.com> X-Mailer: git-send-email 2.8.0.rc3.226.g39d4020 In-Reply-To: <325247067.2674.1477398550882.JavaMail.zimbra@efficios.com> References: <325247067.2674.1477398550882.JavaMail.zimbra@efficios.com> Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3393 Lines: 86 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. 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; #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG BUG_ON(in_nmi()); @@ -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