Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755648AbcJZSJ4 (ORCPT ); Wed, 26 Oct 2016 14:09:56 -0400 Received: from foss.arm.com ([217.140.101.70]:49618 "EHLO foss.arm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754385AbcJZSJx (ORCPT ); Wed, 26 Oct 2016 14:09:53 -0400 Date: Wed, 26 Oct 2016 19:09:51 +0100 From: Will Deacon To: Daniel Mentz Cc: linux-kernel@vger.kernel.org, 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 Subject: Re: [PATCH] lib/genalloc.c: Start search from start of chunk Message-ID: <20161026180951.GG15216@arm.com> References: <325247067.2674.1477398550882.JavaMail.zimbra@efficios.com> <1477420604-28918-1-git-send-email-danielmentz@google.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1477420604-28918-1-git-send-email-danielmentz@google.com> User-Agent: Mutt/1.5.23 (2014-03-12) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Length: 1383 Lines: 34 On Tue, Oct 25, 2016 at 11:36:44AM -0700, Daniel Mentz wrote: > 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. Please add a CC stable. With that: Acked-by: Will Deacon Will