Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S941579AbcJYM3U (ORCPT ); Tue, 25 Oct 2016 08:29:20 -0400 Received: from mail.efficios.com ([167.114.142.141]:45497 "EHLO mail.efficios.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933920AbcJYM3P (ORCPT ); Tue, 25 Oct 2016 08:29:15 -0400 Date: Tue, 25 Oct 2016 12:29:10 +0000 (UTC) From: Mathieu Desnoyers To: Daniel Mentz Cc: linux-kernel , 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 , Mauro Carvalho Chehab , Olof Johansson , Ritesh Harjain , Rob Herring , Russell King , Sekhar Nori , Takashi Iwai , Thadeu Lima de Souza Cascardo , Thierry Reding , Vinod Koul , Vladimir Zapolskiy , Will Deacon Message-ID: <325247067.2674.1477398550882.JavaMail.zimbra@efficios.com> In-Reply-To: <1477360693-17645-1-git-send-email-danielmentz@google.com> References: <1477360693-17645-1-git-send-email-danielmentz@google.com> Subject: Re: [PATCH] lib/genalloc.c: Start search from start of chunk MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-Originating-IP: [167.114.142.141] X-Mailer: Zimbra 8.7.0_GA_1659 (ZimbraWebClient - FF49 (Linux)/8.7.0_GA_1659) Thread-Topic: lib/genalloc.c: Start search from start of chunk Thread-Index: NpMy+cyqpuo7G8OHRq5HoAQf33CvGg== Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 3703 Lines: 102 ----- On Oct 24, 2016, at 9:58 PM, Daniel Mentz danielmentz@google.com wrote: > gen_pool_alloc_algo() iterates over all chunks of a pool trying to find > a contiguous block of memory that satisfies the allocation request. > The search should start at address zero of every chunk. However, as the > code stands today, this is only true for the first chunk. Due to a bug, > the search of subsequent chunks starts somewhere else: So in a situation where a chunk has enough bytes left to fulfill the request, but they are not contiguous, the check: if (size > atomic_read(&chunk->avail)) continue; would not trigger, and we'd end up setting start_bit to the value end_bit after returning from the algo() call. So if the following chunks have the same size as the nearly full chunk, we end up failing memory allocation for all following chunks even though there is plenty of room left. I would be tempted to add a bit of explanation on the failure modes to the commit message (e.g. scenario above). Other than that: Reviewed-by: Mathieu Desnoyers Thanks! Mathieu > > The variables start_bit and end_bit are meant to describe the range that > should be searched and should be reset for every chunk that is searched. > Today, the code fails to reset start_bit to 0. > > 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: Rob Herring > 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 -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com