From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <linux-kernel-owner@vger.kernel.org>
Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand
        id S1755648AbcJZSJ4 (ORCPT <rfc822;w@1wt.eu>);
        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 <rfc822;linux-kernel@vger.kernel.org>);
        Wed, 26 Oct 2016 14:09:53 -0400
Date: Wed, 26 Oct 2016 19:09:51 +0100
From: Will Deacon <will.deacon@arm.com>
To: Daniel Mentz <danielmentz@google.com>
Cc: linux-kernel@vger.kernel.org, Andi Kleen <ak@linux.intel.com>,
        Andrew Morton <akpm@linux-foundation.org>,
        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
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: <linux-kernel.vger.kernel.org>
X-Mailing-List: linux-kernel@vger.kernel.org

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.deacon@arm.com>

Will