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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <20161026180951.GG15216@arm.com>
Date:   Wed, 26 Oct 2016 19:09:51 +0100
From:   Will Deacon <will.deacon@....com>
To:     Daniel Mentz <danielmentz@...gle.com>
Cc:     linux-kernel@...r.kernel.org, Andi Kleen <ak@...ux.intel.com>,
        Andrew Morton <akpm@...ux-foundation.org>,
        Arnd Bergmann <arnd@...db.de>,
        Catalin Marinas <catalin.marinas@....com>,
        Dan Williams <dan.j.williams@...el.com>,
        David Riley <davidriley@...omium.org>,
        Eric Miao <eric.y.miao@...il.com>,
        Grant Likely <grant.likely@...aro.org>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        Haojian Zhuang <haojian.zhuang@...il.com>,
        Huang Ying <ying.huang@...el.com>,
        Jaroslav Kysela <perex@...ex.cz>,
        Kevin Hilman <khilman@...prootsystems.com>,
        Laura Abbott <lauraa@...eaurora.org>,
        Liam Girdwood <lgirdwood@...il.com>,
        Mark Brown <broonie@...nel.org>,
        Mathieu Desnoyers <mathieu.desnoyers@...icios.com>,
        Mauro Carvalho Chehab <m.chehab@...sung.com>,
        Olof Johansson <olof@...om.net>,
        Ritesh Harjain <ritesh.harjani@...il.com>,
        Russell King <linux@....linux.org.uk>,
        Sekhar Nori <nsekhar@...com>, Takashi Iwai <tiwai@...e.de>,
        Thadeu Lima de Souza Cascardo <cascardo@...ux.vnet.ibm.com>,
        Thierry Reding <thierry.reding@...il.com>,
        Vinod Koul <vinod.koul@...el.com>,
        Vladimir Zapolskiy <vladimir_zapolskiy@...tor.com>
Subject: Re: [PATCH] lib/genalloc.c: Start search from start of chunk

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

Will