Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1524309

[PATCH 4.4 31/38] lib/genalloc.c: start search from start of chunk

Show all headers | View raw

4.4-stable review patch.  If anyone has any objections, please let me know.

------------------

From: Daniel Mentz <danielmentz@google.com>

commit 62e931fac45b17c2a42549389879411572f75804 upstream.

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.

Fixes: 7f184275aa30 ("lib, Make gen_pool memory allocator lockless")
Link: http://lkml.kernel.org/r/1477420604-28918-1-git-send-email-danielmentz@google.com
Signed-off-by: Daniel Mentz <danielmentz@google.com>
Reviewed-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Acked-by: Will Deacon <will.deacon@arm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>

---
 lib/genalloc.c |    3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

--- a/lib/genalloc.c
+++ b/lib/genalloc.c
@@ -273,7 +273,7 @@ unsigned long gen_pool_alloc(struct gen_
 	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());
@@ -288,6 +288,7 @@ unsigned long gen_pool_alloc(struct gen_
 		if (size > atomic_read(&chunk->avail))
 			continue;
 
+		start_bit = 0;
 		end_bit = chunk_size(chunk) >> order;
 retry:
 		start_bit = pool->algo(chunk->bits, end_bit, start_bit, nbits,

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[PATCH 4.4 00/38] 4.4.33-stable review Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:40 +0100
  [PATCH 4.4 10/38] pinctrl: cherryview: Prevent possible interrupt storm on resume Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 06/38] coredump: fix unfreezable coredumping task Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 30/38] mei: bus: fix received data size check in NFC fixup Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 05/38] swapfile: fix memory corruption via malformed swapfile Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 33/38] i40e: fix call of ndo_dflt_bridge_getlink() Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 11/38] staging: iio: ad5933: avoid uninitialized variable in error case Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 29/38] iommu/vt-d: Fix dead-locks in disable_dmar_iommu() path Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 18/38] toshiba-wmi: Fix loading the driver on non Toshiba laptops Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 28/38] iommu/amd: Free domain id when free a domain of struct dma_ops_domain Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 31/38] lib/genalloc.c: start search from start of chunk Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 32/38] hwrng: core - Dont use a stack buffer in add_early_randomness() Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 22/38] scsi: qla2xxx: Fix scsi scan hang triggered if adapter fails during init Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 36/38] mmc: mxs: Initialize the spinlock prior to using it Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 38/38] netfilter: fix namespace handling in nf_log_proc_dostring Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
    Re: [PATCH 4.4 38/38] netfilter: fix namespace handling in  nf_log_proc_dostring Pablo Neira Ayuso <pablo@netfilter.org> - 2016-11-17 12:10 +0100
      Re: [PATCH 4.4 38/38] netfilter: fix namespace handling in  nf_log_proc_dostring Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 13:10 +0100
  [PATCH 4.4 35/38] ASoC: sun4i-codec: return error code instead of NULL when create_card fails Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 20/38] iio: hid-sensors: Increase the precision of scale to fix wrong reading interpretation. Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 13/38] Revert "staging: nvec: ps2: change serio type to passthrough" Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 17/38] drbd: Fix kernel_sendmsg() usage - potential NULL deref Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 37/38] btrfs: qgroup: Prevent qgroup->reserved from going subzero Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 34/38] ACPI / APEI: Fix incorrect return value of ghes_proc() Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 12/38] drivers: staging: nvec: remove bogus reset command for PS/2 interface Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 14/38] staging: nvec: remove managed resource from PS2 driver Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 26/38] dmaengine: at_xdmac: fix spurious flag status for mem2mem transfers Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 15/38] USB: cdc-acm: fix TIOCMIWAIT Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 09/38] pinctrl: cherryview: Serialize register access in suspend/resume Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 11:50 +0100
  [PATCH 4.4 01/38] ALSA: info: Return error for invalid read/write Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 12:00 +0100
  [PATCH 4.4 03/38] ASoC: cs4270: fix DAPM stream name mismatch Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2016-11-17 12:00 +0100
  Re: [PATCH 4.4 00/38] 4.4.33-stable review Guenter Roeck <linux@roeck-us.net> - 2016-11-17 23:30 +0100

csiph-web