Re: [PATCH] lib/genalloc.c: Start search from start of chunk

From: Andrew Morton <akpm@linux-foundation.org>
To: Will Deacon <will.deacon@arm.com>
Cc: Daniel Mentz <danielmentz@google.com>,
	linux-kernel@vger.kernel.org, Andi Kleen <ak@linux.intel.com>,
	Arnd Bergmann <arnd@arndb.de>,
	Catalin Marinas <catalin.marinas@arm.com>,
	Dan Williams <dan.j.williams@intel.com>,
	David Riley <davidriley@chromium.org>,
	Eric Miao <eric.y.miao@gmail.com>,
	Grant Likely <grant.likely@linaro.org>,
	Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
	Haojian Zhuang <haojian.zhuang@gmail.com>,
	Huang Ying <ying.huang@intel.com>,
	Jaroslav Kysela <perex@perex.cz>,
	Kevin Hilman <khilman@deeprootsystems.com>,
	Laura Abbott <lauraa@codeaurora.org>,
	Liam Girdwood <lgirdwood@gmail.com>,
	Mark Brown <broonie@kernel.org>,
	Mathieu Desnoyers <mathieu.desnoyers@efficios.com>,
	Mauro Carvalho Chehab <m.chehab@samsung.com>,
	Olof Johansson <olof@lixom.net>,
	Ritesh Harjain <ritesh.harjani@gmail.com>,
	Russell King <linux@arm.linux.org.uk>,
	Sekhar Nori <nsekhar@ti.com>, Takashi Iwai <tiwai@suse.de>,
	Thadeu Lima de Souza Cascardo <cascardo@linux.vnet.ibm.com>,
	Thierry Reding <thierry.reding@gmail.com>,
	Vinod Koul <vinod.koul@intel.com>,
	Vladimir Zapolskiy <vladimir_zapolskiy@mentor.com>
Subject: Re: [PATCH] lib/genalloc.c: Start search from start of chunk
Date: Wed, 26 Oct 2016 12:39:45 -0700	[thread overview]
Message-ID: <20161026123945.9341e2a2c1f3a9f95ef41cce@linux-foundation.org> (raw)
In-Reply-To: <20161026180951.GG15216@arm.com>

On Wed, 26 Oct 2016 19:09:51 +0100 Will Deacon <will.deacon@arm.com> wrote:

> 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.

You sure?  The changelog doesn't describe the end-user impacts very
well (it should always do so, please) but I'm thinking "little impact"?

> With that:
> 
> Acked-by: Will Deacon <will.deacon@arm.com>
> 
> Will