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
Date: Wed, 26 Oct 2016 19:09:51 +0100 [thread overview]
Message-ID: <20161026180951.GG15216@arm.com> (raw)
In-Reply-To: <1477420604-28918-1-git-send-email-danielmentz@google.com>
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
next prev parent reply other threads:[~2016-10-26 18:09 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-10-25 1:58 [PATCH] lib/genalloc.c: Start search from start of chunk Daniel Mentz
2016-10-25 12:29 ` Mathieu Desnoyers
2016-10-25 18:36 ` Daniel Mentz
2016-10-26 18:09 ` Will Deacon [this message]
2016-10-26 19:39 ` Andrew Morton
2016-10-26 22:24 ` Daniel Mentz
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20161026180951.GG15216@arm.com \
--to=will.deacon@arm.com \
--cc=ak@linux.intel.com \
--cc=akpm@linux-foundation.org \
--cc=arnd@arndb.de \
--cc=broonie@kernel.org \
--cc=cascardo@linux.vnet.ibm.com \
--cc=catalin.marinas@arm.com \
--cc=dan.j.williams@intel.com \
--cc=danielmentz@google.com \
--cc=davidriley@chromium.org \
--cc=eric.y.miao@gmail.com \
--cc=grant.likely@linaro.org \
--cc=gregkh@linuxfoundation.org \
--cc=haojian.zhuang@gmail.com \
--cc=khilman@deeprootsystems.com \
--cc=lauraa@codeaurora.org \
--cc=lgirdwood@gmail.com \
--cc=linux-kernel@vger.kernel.org \
--cc=linux@arm.linux.org.uk \
--cc=m.chehab@samsung.com \
--cc=mathieu.desnoyers@efficios.com \
--cc=nsekhar@ti.com \
--cc=olof@lixom.net \
--cc=perex@perex.cz \
--cc=ritesh.harjani@gmail.com \
--cc=thierry.reding@gmail.com \
--cc=tiwai@suse.de \
--cc=vinod.koul@intel.com \
--cc=vladimir_zapolskiy@mentor.com \
--cc=ying.huang@intel.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).