linux-kernel - [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 for Android: free password hash cracker in your pocket

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

Message-Id: <1477420604-28918-1-git-send-email-danielmentz@google.com>
Date:   Tue, 25 Oct 2016 11:36:44 -0700
From:   Daniel Mentz <danielmentz@...gle.com>
To:     linux-kernel@...r.kernel.org
Cc:     Daniel Mentz <danielmentz@...gle.com>,
        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>,
        Will Deacon <will.deacon@....com>
Subject: [PATCH] lib/genalloc.c: Start search from start of chunk

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.

Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Fixes: 7f184275aa30 ("lib, Make gen_pool memory allocator lockless")
Cc: Andi Kleen <ak@...ux.intel.com>
Cc: Andrew Morton <akpm@...ux-foundation.org>
Cc: Arnd Bergmann <arnd@...db.de>
Cc: Catalin Marinas <catalin.marinas@....com>
Cc: Dan Williams <dan.j.williams@...el.com>
Cc: David Riley <davidriley@...omium.org>
Cc: Eric Miao <eric.y.miao@...il.com>
Cc: Grant Likely <grant.likely@...aro.org>
Cc: Greg Kroah-Hartman <gregkh@...uxfoundation.org>
Cc: Haojian Zhuang <haojian.zhuang@...il.com>
Cc: Huang Ying <ying.huang@...el.com>
Cc: Jaroslav Kysela <perex@...ex.cz>
Cc: Kevin Hilman <khilman@...prootsystems.com>
Cc: Laura Abbott <lauraa@...eaurora.org>
Cc: Liam Girdwood <lgirdwood@...il.com>
Cc: Mark Brown <broonie@...nel.org>
Cc: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Cc: Mauro Carvalho Chehab <m.chehab@...sung.com>
Cc: Olof Johansson <olof@...om.net>
Cc: Ritesh Harjain <ritesh.harjani@...il.com>
Cc: Russell King <linux@....linux.org.uk>
Cc: Sekhar Nori <nsekhar@...com>
Cc: Takashi Iwai <tiwai@...e.de>
Cc: Thadeu Lima de Souza Cascardo <cascardo@...ux.vnet.ibm.com>
Cc: Thierry Reding <thierry.reding@...il.com>
Cc: Vinod Koul <vinod.koul@...el.com>
Cc: Vladimir Zapolskiy <vladimir_zapolskiy@...tor.com>
Cc: Will Deacon <will.deacon@....com>
Signed-off-by: Daniel Mentz <danielmentz@...gle.com>
---
 lib/genalloc.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/lib/genalloc.c b/lib/genalloc.c
index 0a11396..144fe6b 100644
--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -292,7 +292,7 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size,
 	struct gen_pool_chunk *chunk;
 	unsigned long addr = 0;
 	int order = pool->min_alloc_order;
-	int nbits, start_bit = 0, end_bit, remain;
+	int nbits, start_bit, end_bit, remain;
 
 #ifndef CONFIG_ARCH_HAVE_NMI_SAFE_CMPXCHG
 	BUG_ON(in_nmi());
@@ -307,6 +307,7 @@ unsigned long gen_pool_alloc_algo(struct gen_pool *pool, size_t size,
 		if (size > atomic_read(&chunk->avail))
 			continue;
 
+		start_bit = 0;
 		end_bit = chunk_size(chunk) >> order;
 retry:
 		start_bit = algo(chunk->bits, end_bit, start_bit,
-- 
2.8.0.rc3.226.g39d4020