Skip to contentSkip to conversation

block, mempool, percpu: implement percpu mempool and fix blkcg percpu alloc deadlock

PATCH In review Tejun Heo 4 participants 51 messages Dec 22, 2011 – Feb 15, 2012

Subsystems (6)
lore
Share & tools
lore

Tejun Heo

author maintainer
#0 lore raw

PATCH 1/1 block, mempool, percpu: implement percpu mempool and fix blkcg percpu alloc deadlock

Hello, guys.

This patchset implements mempool for percpu memory and use it to solve allocation deadlock problem in block cgroup paths. Percpu memory allocator can't be called from memory reclaim path, mostly because its on-demand chunk filling hooks into vmalloc area management, which in turn hooks into arch pagetable code.

This usually isn't a problem but block cgroup code wants to do opportunistic percpu allocation to track statistics in IO issue path. Currently, it directly calls alloc_percpu() from IO path triggering lockdep warning and falling into deadlocks under the right conditions.

This patchset adds percpu mempool which supports async refilling and uses that as allocation buffer to solve the above problem. It solves the problem for the next merge window but I'm not sure about what to do about this window and -stable. The mempool updates seems a bit too invasive. Maybe implement a stripped down allocation buffer in block-cgroup?

This patchset contains the following seven patches.

0001-mempool-fix-and-document-synchronization-and-memory-.patch 0002-mempool-drop-unnecessary-and-incorrect-BUG_ON-from-m.patch 0003-mempool-fix-first-round-failure-behavior.patch 0004-mempool-factor-out-mempool_fill.patch 0005-mempool-separate-out-__mempool_create.patch 0006-mempool-percpu-implement-percpu-mempool.patch 0007-block-fix-deadlock-through-percpu-allocation-in-blk-.patch

0001-0003 are general mempool updates and already in -mm. Note that Oleg has an alternative patch for 0003 which seems better to me.

0004-0006 prepare for and implement percpu mempool.

0007 uses it in block cgroup to fix the deadlock problem.

This patchset is on top of block/for-3.3/core but applies on mainline too.

If people agree with this approach, it would probably be easier to route everything through block, I think. Andrew, Jens, how do you guys want to route these?

Oleg, if you can send patch with proper description and SOB, I'll replace 0003 with yours.

The patchset is also available in the following git branch.

git://git.kernel.org/pub/scm/linux/kernel/git/tj/misc.git block-blkcg-pcpu-fix

and contains the following changes.

 block/blk-cgroup.c      |   37 +++++
 block/blk-cgroup.h      |    2 
 block/blk-throttle.c    |    2 
 block/cfq-iosched.c     |    2 
 include/linux/mempool.h |   80 ++++++++++++
 mm/mempool.c            |  310 +++++++++++++++++++++++++++++++++++++-----------
 6 files changed, 363 insertions(+), 70 deletions(-)

Thanks.

--
tejun

author maintainer
#1 lore raw

PATCH 1/7 mempool: fix and document synchronization and memory barrier usage

mempool_alloc/free() use undocumented smp_mb()'s. The code is slightly broken and misleading.

The lockless part is in mempool_free(). It wants to determine whether the item being freed needs to be returned to the pool or backing allocator without grabbing pool->lock. Two things need to be guaranteed for correct operation.

1. pool->curr_nr + #allocated should never dip below pool->min_nr.
2. Waiters shouldn't be left dangling.

For #1, The only necessary condition is that curr_nr visible at free is from after the allocation of the element being freed (details in the comment). For most cases, this is true without any barrier but there can be fringe cases where the allocated pointer is passed to the freeing task without going through memory barriers. To cover this case, wmb is necessary before returning from allocation and rmb is necessary before reading curr_nr. IOW,

	ALLOCATING TASK			FREEING TASK

	update pool state after alloc;
	wmb();
	pass pointer to freeing task;
					read pointer;
					rmb();
					read pool state to free;

The current code doesn't have wmb after pool update during allocation and may theoretically, on machines where unlock doesn't behave as full wmb, lead to pool depletion and deadlock. smp_wmb() needs to be added after successful allocation from reserved elements and smp_mb() in mempool_free() can be replaced with smp_rmb().

For #2, the waiter needs to add itself to waitqueue and then check the wait condition and the waker needs to update the wait condition and then wake up. Because waitqueue operations always go through full spinlock synchronization, there is no need for extra memory barriers.

Furthermore, mempool_alloc() is already holding pool->lock when it decides that it needs to wait. There is no reason to do unlock - add waitqueue - test condition again. It can simply add itself to waitqueue while holding pool->lock and then unlock and sleep.

This patch adds smp_wmb() after successful allocation from reserved pool, replaces smp_mb() in mempool_free() with smp_rmb() and extend pool->lock over waitqueue addition. More importantly, it explains what memory barriers do and how the lockless testing is correct.

-v2: Oleg pointed out that unlock doesn't imply wmb. Added explicit
smp_wmb() after successful allocation from reserved pool and updated comments accordingly.

Cc Oleg Nesterov <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc "Paul E. McKenney" <[email protected]>
Cc David Howells <[email protected]>
---
 mm/mempool.c |   61 +++++++++++++++++++++++++++++++++++++++++++++------------
 1 files changed, 48 insertions(+), 13 deletions(-)
mm/mempool.c +48 -13
index e73641b..11f0d0a 100644
@@ -224,28 +224,31 @@ repeat_alloc:
 	if (likely(pool->curr_nr)) {
 		element = remove_element(pool);
 		spin_unlock_irqrestore(&pool->lock, flags);
+		/* paired with rmb in mempool_free(), read comment there */
+		smp_wmb();
 		return element;
 	}
-	spin_unlock_irqrestore(&pool->lock, flags);
 
 	/* We must not sleep in the GFP_ATOMIC case */
-	if (!(gfp_mask & __GFP_WAIT))
+	if (!(gfp_mask & __GFP_WAIT)) {
+		spin_unlock_irqrestore(&pool->lock, flags);
 		return NULL;
+	}
 
-	/* Now start performing page reclaim */
+	/* Let's wait for someone else to return an element to @pool */
 	gfp_temp = gfp_mask;
 	init_wait(&wait);
 	prepare_to_wait(&pool->wait, &wait, TASK_UNINTERRUPTIBLE);
-	smp_mb();
-	if (!pool->curr_nr) {
-		/*
-		 * FIXME: this should be io_schedule().  The timeout is there
-		 * as a workaround for some DM problems in 2.6.18.
-		 */
-		io_schedule_timeout(5*HZ);
-	}
-	finish_wait(&pool->wait, &wait);
 
+	spin_unlock_irqrestore(&pool->lock, flags);
+
+	/*
+	 * FIXME: this should be io_schedule().  The timeout is there as a
+	 * workaround for some DM problems in 2.6.18.
+	 */
+	io_schedule_timeout(5*HZ);
+
+	finish_wait(&pool->wait, &wait);
 	goto repeat_alloc;
 }
 EXPORT_SYMBOL(mempool_alloc);
@@ -265,7 +268,39 @@ void mempool_free(void *element, mempool_t *pool)
 	if (unlikely(element == NULL))
 		return;
 
-	smp_mb();
+	/*
+	 * Paired with the wmb in mempool_alloc().  The preceding read is
+	 * for @element and the following @pool->curr_nr.  This ensures
+	 * that the visible value of @pool->curr_nr is from after the
+	 * allocation of @element.  This is necessary for fringe cases
+	 * where @element was passed to this task without going through
+	 * barriers.
+	 *
+	 * For example, assume @p is %NULL at the beginning and one task
+	 * performs "p = mempool_alloc(...);" while another task is doing
+	 * "while (!p) cpu_relax(); mempool_free(p, ...);".  This function
+	 * may end up using curr_nr value which is from before allocation
+	 * of @p without the following rmb.
+	 */
+	smp_rmb();
+
+	/*
+	 * For correctness, we need a test which is guaranteed to trigger
+	 * if curr_nr + #allocated == min_nr.  Testing curr_nr < min_nr
+	 * without locking achieves that and refilling as soon as possible
+	 * is desirable.
+	 *
+	 * Because curr_nr visible here is always a value after the
+	 * allocation of @element, any task which decremented curr_nr below
+	 * min_nr is guaranteed to see curr_nr < min_nr unless curr_nr gets
+	 * incremented to min_nr afterwards.  If curr_nr gets incremented
+	 * to min_nr after the allocation of @element, the elements
+	 * allocated after that are subject to the same guarantee.
+	 *
+	 * Waiters happen iff curr_nr is 0 and the above guarantee also
+	 * ensures that there will be frees which return elements to the
+	 * pool waking up the waiters.
+	 */
 	if (pool->curr_nr < pool->min_nr) {
 		spin_lock_irqsave(&pool->lock, flags);
 		if (pool->curr_nr < pool->min_nr) {
Signature · 1 line
1.7.3.1
author maintainer
#3 lore raw

PATCH 3/7 mempool: fix first round failure behavior

In reply to Tejun Heo

mempool modifies gfp_mask so that the backing allocator doesn't try too hard or trigger warning message when there's pool to fall back on. In addition, for the first try, it removes __GFP_WAIT and IO, so that it doesn't trigger reclaim or wait when allocation can be fulfilled from pool; however, when that allocation fails and pool is empty too, it waits for the pool to be replenished before retrying.

Allocation which could have succeeded after a bit of reclaim has to wait on the reserved items and it's not like mempool doesn't retry with __GFP_WAIT and IO. It just does that *after* someone returns an element, pointlessly delaying things.

Fix it by retrying immediately if the first round of allocation attempts w/o __GFP_WAIT and IO fails.

Cc Andrew Morton <[email protected]>
---
 mm/mempool.c |   13 +++++++++++--
 1 files changed, 11 insertions(+), 2 deletions(-)
mm/mempool.c +11 -2
index e3a802a..6326cc6 100644
@@ -221,14 +221,23 @@ repeat_alloc:
 		return element;
 	}
 
-	/* We must not sleep in the GFP_ATOMIC case */
+	/*
+	 * We use gfp mask w/o __GFP_WAIT or IO for the first round.  If
+	 * alloc failed with that and @pool was empty, retry immediately.
+	 */
+	if (gfp_temp != gfp_mask) {
+		gfp_temp = gfp_mask;
+		spin_unlock_irqrestore(&pool->lock, flags);
+		goto repeat_alloc;
+	}
+
+	/* We must not sleep if !__GFP_WAIT */
 	if (!(gfp_mask & __GFP_WAIT)) {
 		spin_unlock_irqrestore(&pool->lock, flags);
 		return NULL;
 	}
 
 	/* Let's wait for someone else to return an element to @pool */
-	gfp_temp = gfp_mask;
 	init_wait(&wait);
 	prepare_to_wait(&pool->wait, &wait, TASK_UNINTERRUPTIBLE);
 
Signature · 1 line
1.7.3.1
author maintainer
#4 lore raw

PATCH 4/7 mempool: factor out mempool_fill()

In reply to Tejun Heo

Factor out mempool_fill() from mempool_create() and mempool_resize(). When called, it fills the reservoir upto the configured min_nr elements.

After the change, gotos in mempool_resize() exit paths don't make whole lot of sense, unlock and return directly.

Note that mempool_create() repeatedly locks and unlocks pool->lock while filling the pool initially and mempool_resize() may go through one extra locking cycle. This shouldn't result in noticeable difference.

Cc Andrew Morton <[email protected]>
Cc Oleg Nesterov <[email protected]>
---
 mm/mempool.c |   75 ++++++++++++++++++++++++++++++++++++---------------------
 1 files changed, 47 insertions(+), 28 deletions(-)
mm/mempool.c +47 -28
index 6326cc6..4747283 100644
@@ -47,6 +47,43 @@ void mempool_destroy(mempool_t *pool)
 EXPORT_SYMBOL(mempool_destroy);
 
 /**
+ * mempool_fill - fill a memory pool
+ * @pool:	memory pool to fill
+ * @gfp_mask:	allocation mask to use
+ *
+ * Allocate new elements with @gfp_mask and fill @pool so that it has
+ * @pool->min_nr elements.  Returns 0 on success, -errno on failure.
+ */
+static int mempool_fill(mempool_t *pool, gfp_t gfp_mask)
+{
+	/*
+	 * If curr_nr == min_nr is visible, we're correct regardless of
+	 * locking.
+	 */
+	while (pool->curr_nr < pool->min_nr) {
+		void *elem;
+		unsigned long flags;
+
+		elem = pool->alloc(gfp_mask, pool->pool_data);
+		if (unlikely(!elem))
+			return -ENOMEM;
+
+		spin_lock_irqsave(&pool->lock, flags);
+		if (pool->curr_nr < pool->min_nr) {
+			add_element(pool, elem);
+			elem = NULL;
+		}
+		spin_unlock_irqrestore(&pool->lock, flags);
+
+		if (elem) {
+			pool->free(elem, pool->pool_data);
+			return 0;
+		}
+	}
+	return 0;
+}
+
+/**
  * mempool_create - create a memory pool
  * @min_nr:    the minimum number of elements guaranteed to be
  *             allocated for this pool.
@@ -90,16 +127,11 @@ mempool_t *mempool_create_node(int min_nr, mempool_alloc_t *alloc_fn,
 	/*
 	 * First pre-allocate the guaranteed number of buffers.
 	 */
-	while (pool->curr_nr < pool->min_nr) {
-		void *element;
-
-		element = pool->alloc(GFP_KERNEL, pool->pool_data);
-		if (unlikely(!element)) {
-			mempool_destroy(pool);
-			return NULL;
-		}
-		add_element(pool, element);
+	if (mempool_fill(pool, GFP_KERNEL)) {
+		mempool_destroy(pool);
+		return NULL;
 	}
+
 	return pool;
 }
 EXPORT_SYMBOL(mempool_create_node);
@@ -137,7 +169,8 @@ int mempool_resize(mempool_t *pool, int new_min_nr, gfp_t gfp_mask)
 			spin_lock_irqsave(&pool->lock, flags);
 		}
 		pool->min_nr = new_min_nr;
-		goto out_unlock;
+		spin_unlock_irqrestore(&pool->lock, flags);
+		return 0;
 	}
 	spin_unlock_irqrestore(&pool->lock, flags);
 
@@ -151,31 +184,17 @@ int mempool_resize(mempool_t *pool, int new_min_nr, gfp_t gfp_mask)
 		/* Raced, other resize will do our work */
 		spin_unlock_irqrestore(&pool->lock, flags);
 		kfree(new_elements);
-		goto out;
+		return 0;
 	}
 	memcpy(new_elements, pool->elements,
 			pool->curr_nr * sizeof(*new_elements));
 	kfree(pool->elements);
 	pool->elements = new_elements;
 	pool->min_nr = new_min_nr;
-
-	while (pool->curr_nr < pool->min_nr) {
-		spin_unlock_irqrestore(&pool->lock, flags);
-		element = pool->alloc(gfp_mask, pool->pool_data);
-		if (!element)
-			goto out;
-		spin_lock_irqsave(&pool->lock, flags);
-		if (pool->curr_nr < pool->min_nr) {
-			add_element(pool, element);
-		} else {
-			spin_unlock_irqrestore(&pool->lock, flags);
-			pool->free(element, pool->pool_data);	/* Raced */
-			goto out;
-		}
-	}
-out_unlock:
 	spin_unlock_irqrestore(&pool->lock, flags);
-out:
+
+	mempool_fill(pool, gfp_mask);
+
 	return 0;
 }
 EXPORT_SYMBOL(mempool_resize);
Signature · 1 line
1.7.3.1
author maintainer
#2 lore raw

PATCH 2/7 mempool: drop unnecessary and incorrect BUG_ON() from mempool_destroy()

In reply to Tejun Heo

mempool_destroy() is a thin wrapper around free_pool(). The only thing it adds is BUG_ON(pool->curr_nr != pool->min_nr). The intention seems to be to enforce that all allocated elements are freed; however, the BUG_ON() can't achieve that (it doesn't know anything about objects above min_nr) and incorrect as mempool_resize() is allowed to leave the pool extended but not filled. Furthermore, panicking is way worse than any memory leak and there are better debug tools to track memory leaks.

Drop the BUG_ON() from mempool_destory() and as that leaves the function identical to free_pool(), replace it.

Cc Andrew Morton <[email protected]>
---
 mm/mempool.c |   30 +++++++++++-------------------
 1 files changed, 11 insertions(+), 19 deletions(-)
mm/mempool.c +11 -19
index 11f0d0a..e3a802a 100644
@@ -27,7 +27,15 @@ static void *remove_element(mempool_t *pool)
 	return pool->elements[--pool->curr_nr];
 }
 
-static void free_pool(mempool_t *pool)
+/**
+ * mempool_destroy - deallocate a memory pool
+ * @pool:      pointer to the memory pool which was allocated via
+ *             mempool_create().
+ *
+ * Free all reserved elements in @pool and @pool itself.  This function
+ * only sleeps if the free_fn() function sleeps.
+ */
+void mempool_destroy(mempool_t *pool)
 {
 	while (pool->curr_nr) {
 		void *element = remove_element(pool);
@@ -36,6 +44,7 @@ static void free_pool(mempool_t *pool)
 	kfree(pool->elements);
 	kfree(pool);
 }
+EXPORT_SYMBOL(mempool_destroy);
 
 /**
  * mempool_create - create a memory pool
@@ -86,7 +95,7 @@ mempool_t *mempool_create_node(int min_nr, mempool_alloc_t *alloc_fn,
 
 		element = pool->alloc(GFP_KERNEL, pool->pool_data);
 		if (unlikely(!element)) {
-			free_pool(pool);
+			mempool_destroy(pool);
 			return NULL;
 		}
 		add_element(pool, element);
@@ -172,23 +181,6 @@ out:
 EXPORT_SYMBOL(mempool_resize);
 
 /**
- * mempool_destroy - deallocate a memory pool
- * @pool:      pointer to the memory pool which was allocated via
- *             mempool_create().
- *
- * this function only sleeps if the free_fn() function sleeps. The caller
- * has to guarantee that all elements have been returned to the pool (ie:
- * freed) prior to calling mempool_destroy().
- */
-void mempool_destroy(mempool_t *pool)
-{
-	/* Check for outstanding elements */
-	BUG_ON(pool->curr_nr != pool->min_nr);
-	free_pool(pool);
-}
-EXPORT_SYMBOL(mempool_destroy);
-
-/**
  * mempool_alloc - allocate an element from a specific memory pool
  * @pool:      pointer to the memory pool which was allocated via
  *             mempool_create().
Signature · 1 line
1.7.3.1
author maintainer
#6 lore raw

PATCH 6/7 mempool, percpu: implement percpu mempool

In reply to Tejun Heo

This patch implements mempool for percpu memory areas. Percpu mempool is mostly identical to regular mempool and shares most of code but has some peculiarities.

Percpu memory allocator requires %GFP_KERNEL during allocation, which comes from its on-demand nature and vmalloc area usage. In most cases, it's not a good idea to allocate percpu memory from more constricted context and this doesn't cause a problem; however, there are rare cases where opportunistic allocation from NOIO path makes sense.

To ease such use cases, percpu mempool comes with refill mechanism which can behave both synchronously and asynchronously depending on the specified gfp mask.

Cc Christoph Lameter <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Oleg Nesterov <[email protected]>
Cc Jens Axboe <[email protected]>
Cc Vivek Goyal <[email protected]>
---
 include/linux/mempool.h |   80 ++++++++++++++++++++++++++++++++++
 mm/mempool.c            |  111 +++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 191 insertions(+), 0 deletions(-)
include/linux/mempool.h +80 -0
index 7c08052..129acbe 100644
@@ -5,6 +5,7 @@
 #define _LINUX_MEMPOOL_H
 
 #include <linux/wait.h>
+#include <linux/workqueue.h>
 
 struct kmem_cache;
 
@@ -70,4 +71,83 @@ static inline mempool_t *mempool_create_page_pool(int min_nr, int order)
 			      (void *)(long)order);
 }
 
+/*
+ * Percpu mempool - mempool backed by percpu memory allocator.
+ *
+ * Along with the usual mempool role, because percpu allocator doesn't
+ * support NOIO allocations, percpu mempool is useful as allocation buffer
+ * which is filled from IO context and consumed from atomic or non-IO one.
+ * To help this usage, percpu_mempool has built-in mechanism to refill the
+ * pool which supports both sync and async operations.  Refer to
+ * percpu_mempool_refill() for details.
+ */
+struct percpu_mempool {
+	mempool_t		pool;
+	size_t			size;		/* size of elements */
+	size_t			align;		/* align of elements */
+	struct work_struct	refill_work;	/* work item for async refill */
+};
+
+struct percpu_mempool *percpu_mempool_create(int min_nr, size_t size,
+					     size_t align);
+int percpu_mempool_refill(struct percpu_mempool *pcpu_pool, gfp_t gfp_mask);
+void percpu_mempool_destroy(struct percpu_mempool *pcpu_pool);
+
+/**
+ * percpu_mempool_resize - resize an existing percpu mempool
+ * @pcpu_pool:	percpu mempool to resize
+ * @new_min_nr:	new minimum number of elements guaranteed to be allocated
+ * @gfp_mask:	allocation mask to use
+ *
+ * Counterpart of mempool_resize().  If @gfp_mask doesn't contain
+ * %__GFP_IO, resizing itself may succeed but the implied filling (if
+ * necessary) will fail.
+ */
+static inline int percpu_mempool_resize(struct percpu_mempool *pcpu_pool,
+					int new_min_nr, gfp_t gfp_mask)
+{
+	return mempool_resize(&pcpu_pool->pool, new_min_nr, gfp_mask);
+}
+
+/**
+ * percpu_mempool_alloc - allocate an element from a percpu mempool
+ * @pcpu_pool:	percpu mempool to allocate from
+ * @gfp_mask:	allocation mask to use
+ *
+ * Counterpart of mempool_alloc().  If @gfp_mask doesn't contain %__GFP_IO,
+ * allocation is always from the reserved pool.
+ */
+static inline void __percpu *
+percpu_mempool_alloc(struct percpu_mempool *pcpu_pool, gfp_t gfp_mask)
+{
+	void *p = mempool_alloc(&pcpu_pool->pool, gfp_mask);
+
+	return (void __percpu __force *)p;
+}
+
+/**
+ * percpu_mempool_free - free an element to a percpu mempool
+ * @elem:	element being freed
+ * @pcpu_pool:	percpu mempool to free to
+ */
+static inline void percpu_mempool_free(void __percpu *elem,
+				       struct percpu_mempool *pcpu_pool)
+{
+	void *p = (void __kernel __force *)elem;
+
+	mempool_free(p, &pcpu_pool->pool);
+}
+
+/**
+ * percpu_mempool_nr_elems - return nr of reserved elems in a percpu mempool
+ * @pcpu_pool:	percpu mempool of interest
+ *
+ * Returns the number of reserved elements in @pcpu_pool.  Mostly useful
+ * for deciding when to refill.
+ */
+static inline int percpu_mempool_nr_elems(struct percpu_mempool *pcpu_pool)
+{
+	return pcpu_pool->pool.curr_nr;
+}
+
 #endif /* _LINUX_MEMPOOL_H */
mm/mempool.c +111 -0

120 lines not on this page · raw message

Signature · 1 line
1.7.3.1
author maintainer
#7 lore raw

PATCH 7/7 block: fix deadlock through percpu allocation in blk-cgroup

In reply to Tejun Heo

Percpu allocator depends on %GFP_KERNEL allocation and can't be used for NOIO or NOFS allocations; unfortunately, blk-cgroup allocates percpu stats structure in the IO path, which triggers the following lockdep warning and also leads to actual deadlocks under certain conditions.

inconsistent {RECLAIM_FS-ON-W} -> {IN-RECLAIM_FS-W} usage. qemu-kvm/8774 [HC0[0]:SC0[0]:HE1:SE1] takes:
(pcpu_alloc_mutex){+.+.?.}, at: [<ffffffff8110c8be>] pcpu_alloc+0x6f/0x835
{RECLAIM_FS-ON-W} state was registered at:

   [<ffffffff8108f85a>] mark_held_locks+0x6d/0x95
   [<ffffffff8108fe69>] lockdep_trace_alloc+0x9f/0xc2
   [<ffffffff8112d781>] slab_pre_alloc_hook+0x1e/0x54
   [<ffffffff8112fcf9>] __kmalloc+0x64/0x10c
   [<ffffffff8110bec8>] pcpu_mem_alloc+0x5e/0x67
   [<ffffffff8110c169>] pcpu_extend_area_map+0x2b/0xd4
   [<ffffffff8110ca0d>] pcpu_alloc+0x1be/0x835
   [<ffffffff8110d094>] __alloc_percpu+0x10/0x12
   [<ffffffff8113167a>] kmem_cache_open+0x2cc/0x2d6
   [<ffffffff8113185d>] kmem_cache_create+0x1d9/0x281
   [<ffffffff812971a5>] acpi_os_create_cache+0x1d/0x2d
   [<ffffffff812bf742>] acpi_ut_create_caches+0x26/0xb0
   [<ffffffff812c2106>] acpi_ut_init_globals+0xe/0x244
   [<ffffffff81d82ca9>] acpi_initialize_subsystem+0x35/0xae
   [<ffffffff81d819c2>] acpi_early_init+0x5c/0xf7
   [<ffffffff81d51be9>] start_kernel+0x3ce/0x3ea
   [<ffffffff81d512c4>] x86_64_start_reservations+0xaf/0xb3
   [<ffffffff81d51412>] x86_64_start_kernel+0x14a/0x159
 irq event stamp: 48683649
 hardirqs last  enabled at (48683649): [<ffffffff814fd547>] __slab_alloc+0x413/0x434
 hardirqs last disabled at (48683648): [<ffffffff814fd17c>] __slab_alloc+0x48/0x434
 softirqs last  enabled at (48683630): [<ffffffff810630bf>] __do_softirq+0x200/0x25a
 softirqs last disabled at (48683625): [<ffffffff8150debc>] call_softirq+0x1c/0x30

other info that might help us debug this:

  Possible unsafe locking scenario:
        CPU0
        ----
   lock(pcpu_alloc_mutex);
   <Interrupt>
     lock(pcpu_alloc_mutex);

*** DEADLOCK ***

3 locks held by qemu-kvm/8774:

  #0:  (&vcpu->mutex){+.+.+.}, at: [<ffffffffa005d979>] vcpu_load+0x1d/0x90 [kvm]
  #1:  (&kvm->srcu){.+.+.+}, at: [<ffffffffa00663f7>] srcu_read_lock+0x0/0x49 [kvm]
  #2:  (&mm->mmap_sem){++++++}, at: [<ffffffffa005ee6f>] hva_to_pfn+0xbb/0x2d1 [kvm]
 stack backtrace:
 Pid: 8774, comm: qemu-kvm Not tainted 3.1.4 #2
 Call Trace:
  [<ffffffff814fa906>] print_usage_bug+0x1e7/0x1f8
  [<ffffffff8108e232>] mark_lock+0x106/0x220
  [<ffffffff8108e6ee>] __lock_acquire+0x3a2/0xd0c
  [<ffffffff8108f55b>] lock_acquire+0xf3/0x13e
  [<ffffffff815030ad>] __mutex_lock_common+0x5d/0x39a
  [<ffffffff815034f9>] mutex_lock_nested+0x40/0x45
  [<ffffffff8110c8be>] pcpu_alloc+0x6f/0x835
  [<ffffffff8110d094>] __alloc_percpu+0x10/0x12
  [<ffffffff8123d64c>] blkio_alloc_blkg_stats+0x1d/0x31
  [<ffffffff8123ed87>] throtl_alloc_tg+0x3a/0xdf
  [<ffffffff8123f79f>] blk_throtl_bio+0x154/0x39c
  [<ffffffff81231c52>] generic_make_request+0x2e4/0x415
  [<ffffffff81231e61>] submit_bio+0xde/0xfd
  [<ffffffff8111e15d>] swap_writepage+0x94/0x9f
  [<ffffffff811041d1>] shmem_writepage+0x192/0x1d8
  [<ffffffff8110167b>] shrink_page_list+0x402/0x79a
  [<ffffffff81101e1a>] shrink_inactive_list+0x22c/0x3df
  [<ffffffff811026b2>] shrink_zone+0x43f/0x582
  [<ffffffff81102b5e>] do_try_to_free_pages+0x107/0x318
  [<ffffffff811030a6>] try_to_free_pages+0xd5/0x175
  [<ffffffff810f9021>] __alloc_pages_nodemask+0x535/0x7eb
  [<ffffffff81127f02>] alloc_pages_vma+0xf5/0xfa
  [<ffffffff81136bfb>] do_huge_pmd_anonymous_page+0xb3/0x274
  [<ffffffff811112f2>] handle_mm_fault+0xfd/0x1b8
  [<ffffffff8111173c>] __get_user_pages+0x2fa/0x465
  [<ffffffffa005edb2>] get_user_page_nowait+0x37/0x39 [kvm]
  [<ffffffffa005ee8a>] hva_to_pfn+0xd6/0x2d1 [kvm]
  [<ffffffffa005f108>] __gfn_to_pfn+0x83/0x8c [kvm]
  [<ffffffffa005f1c9>] gfn_to_pfn_async+0x1a/0x1c [kvm]
  [<ffffffffa007799e>] try_async_pf+0x3f/0x248 [kvm]
  [<ffffffffa0079140>] tdp_page_fault+0xe8/0x1a5 [kvm]
  [<ffffffffa0077c83>] kvm_mmu_page_fault+0x2b/0x83 [kvm]
  [<ffffffffa00cda71>] handle_ept_violation+0xe1/0xea [kvm_intel]
  [<ffffffffa00d2129>] vmx_handle_exit+0x5ee/0x638 [kvm_intel]
  [<ffffffffa007153f>] kvm_arch_vcpu_ioctl_run+0xb30/0xe00 [kvm]
  [<ffffffffa005db4f>] kvm_vcpu_ioctl+0x120/0x59c [kvm]
  [<ffffffff811502a5>] do_vfs_ioctl+0x472/0x4b3
  [<ffffffff8115033c>] sys_ioctl+0x56/0x7a
  [<ffffffff8150bbc2>] system_call_fastpath+0x16/0x1b

For more details, please refer to the following thread.

http://thread.gmane.org/gmane.comp.emulators.kvm.devel/82755

This patch fixes the bug by using percpu_mempool to allocate blkg percpu stats. As the allocations are only per cgroup - request_queue pair, they aren't expected to be frequent. Use smallish pool of 8 elements which is refilled once half is consumed.

Cc Christoph Lameter <[email protected]>
Cc Andrew Morton <[email protected]>
Cc Oleg Nesterov <[email protected]>
Cc Jens Axboe <[email protected]>
Cc Vivek Goyal <[email protected]>
---
 block/blk-cgroup.c   |   37 +++++++++++++++++++++++++++++++++++--
 block/blk-cgroup.h   |    2 ++
 block/blk-throttle.c |    2 +-
 block/cfq-iosched.c  |    2 +-
 4 files changed, 39 insertions(+), 4 deletions(-)
block/blk-cgroup.c +35 -2
index 2788693..43bf5e8 100644
@@ -17,17 +17,33 @@
 #include <linux/err.h>
 #include <linux/blkdev.h>
 #include <linux/slab.h>
+#include <linux/mempool.h>
 #include "blk-cgroup.h"
 #include <linux/genhd.h>
 
 #define MAX_KEY_LEN 100
 
+/*
+ * blkg_stats_cpu_pool parameters.  These allocations aren't frequent, can
+ * be opportunistic and percpu memory is expensive.
+ */
+#define BLKG_STATS_CPU_POOL_SIZE	8
+#define BLKG_STATS_CPU_POOL_REFILL	4
+
 static DEFINE_SPINLOCK(blkio_list_lock);
 static LIST_HEAD(blkio_list);
 
 struct blkio_cgroup blkio_root_cgroup = { .weight = 2*BLKIO_WEIGHT_DEFAULT };
 EXPORT_SYMBOL_GPL(blkio_root_cgroup);
 
+/*
+ * Percpu mempool for blkgio_group_stats_cpu which are allocated on-demand
+ * on IO path.  As percpu doesn't support NOIO allocations, we need to
+ * buffer them through mempool.
+ */
+struct percpu_mempool *blkg_stats_cpu_pool;
+EXPORT_SYMBOL_GPL(blkg_stats_cpu_pool);
+
 static struct cgroup_subsys_state *blkiocg_create(struct cgroup_subsys *,
 						  struct cgroup *);
 static int blkiocg_can_attach_task(struct cgroup *, struct task_struct *);
@@ -469,8 +485,13 @@ EXPORT_SYMBOL_GPL(blkiocg_update_io_merged_stats);
  */
 int blkio_alloc_blkg_stats(struct blkio_group *blkg)
 {
+	/* Schedule refill if necessary */
+	if (percpu_mempool_nr_elems(blkg_stats_cpu_pool) <=
+	    BLKG_STATS_CPU_POOL_REFILL)
+		percpu_mempool_refill(blkg_stats_cpu_pool, GFP_NOWAIT);
+
 	/* Allocate memory for per cpu stats */
-	blkg->stats_cpu = alloc_percpu(struct blkio_group_stats_cpu);
+	blkg->stats_cpu = percpu_mempool_alloc(blkg_stats_cpu_pool, GFP_NOWAIT);
 	if (!blkg->stats_cpu)
 		return -ENOMEM;
 	return 0;
@@ -1671,12 +1692,24 @@ EXPORT_SYMBOL_GPL(blkio_policy_unregister);
 
 static int __init init_cgroup_blkio(void)
 {
-	return cgroup_load_subsys(&blkio_subsys);
+	int ret;
+
+	blkg_stats_cpu_pool = percpu_mempool_create(BLKG_STATS_CPU_POOL_SIZE,
+				sizeof(struct blkio_group_stats_cpu),
+				__alignof__(struct blkio_group_stats_cpu));
+	if (!blkg_stats_cpu_pool)
+		return -ENOMEM;
+
+	ret = cgroup_load_subsys(&blkio_subsys);
+	if (ret)
+		percpu_mempool_destroy(blkg_stats_cpu_pool);
+	return ret;
 }
 
 static void __exit exit_cgroup_blkio(void)
 {
 	cgroup_unload_subsys(&blkio_subsys);
+	percpu_mempool_destroy(blkg_stats_cpu_pool);
 }
 
 module_init(init_cgroup_blkio);
block/blk-cgroup.h +2 -0
index 6f3ace7..7659564 100644
@@ -32,6 +32,8 @@ extern struct cgroup_subsys blkio_subsys;
 #define blkio_subsys_id blkio_subsys.subsys_id
 #endif
 
+extern struct percpu_mempool *blkg_stats_cpu_pool;
+
 enum stat_type {
 	/* Total time spent (in ns) between request dispatch to the driver and
 	 * request completion for IOs doen by this cgroup. This may not be
block/blk-throttle.c +1 -1
index 5eed6a7..0f0805e 100644
@@ -159,7 +159,7 @@ static void throtl_free_tg(struct rcu_head *head)
 	struct throtl_grp *tg;
 
 	tg = container_of(head, struct throtl_grp, rcu_head);
-	free_percpu(tg->blkg.stats_cpu);
+	percpu_mempool_free(tg->blkg.stats_cpu, blkg_stats_cpu_pool);
 	kfree(tg);
 }
 
block/cfq-iosched.c +1 -1
index 163263d..44d374a 100644
@@ -1204,7 +1204,7 @@ static void cfq_put_cfqg(struct cfq_group *cfqg)
 		return;
 	for_each_cfqg_st(cfqg, i, j, st)
 		BUG_ON(!RB_EMPTY_ROOT(&st->rb));
-	free_percpu(cfqg->blkg.stats_cpu);
+	percpu_mempool_free(cfqg->blkg.stats_cpu, blkg_stats_cpu_pool);
 	kfree(cfqg);
 }
 
Signature · 1 line
1.7.3.1
author maintainer
#5 lore raw

PATCH 5/7 mempool: separate out __mempool_create()

In reply to Tejun Heo

Separate out __mempool_create(), which handles creation of the mempool without filling it, from mempool_create_node(). This will be used to implemen percpu_mempool.

Cc Andrew Morton <[email protected]>
Cc Oleg Nesterov <[email protected]>
---
 mm/mempool.c |   24 ++++++++++++++++++------
 1 files changed, 18 insertions(+), 6 deletions(-)
mm/mempool.c +18 -6
index 4747283..85e2c28 100644
@@ -104,11 +104,13 @@ mempool_t *mempool_create(int min_nr, mempool_alloc_t *alloc_fn,
 }
 EXPORT_SYMBOL(mempool_create);
 
-mempool_t *mempool_create_node(int min_nr, mempool_alloc_t *alloc_fn,
-			mempool_free_t *free_fn, void *pool_data, int node_id)
+static mempool_t *__mempool_create(int min_nr, mempool_alloc_t *alloc_fn,
+				   mempool_free_t *free_fn, void *pool_data,
+				   int node_id, size_t mempool_bytes)
 {
 	mempool_t *pool;
-	pool = kmalloc_node(sizeof(*pool), GFP_KERNEL | __GFP_ZERO, node_id);
+
+	pool = kmalloc_node(mempool_bytes, GFP_KERNEL | __GFP_ZERO, node_id);
 	if (!pool)
 		return NULL;
 	pool->elements = kmalloc_node(min_nr * sizeof(void *),
@@ -124,9 +126,19 @@ mempool_t *mempool_create_node(int min_nr, mempool_alloc_t *alloc_fn,
 	pool->alloc = alloc_fn;
 	pool->free = free_fn;
 
-	/*
-	 * First pre-allocate the guaranteed number of buffers.
-	 */
+	return pool;
+}
+
+mempool_t *mempool_create_node(int min_nr, mempool_alloc_t *alloc_fn,
+			       mempool_free_t *free_fn, void *pool_data,
+			       int node_id)
+{
+	mempool_t *pool;
+
+	pool = __mempool_create(min_nr, alloc_fn, free_fn, pool_data, node_id,
+				sizeof(*pool));
+
+	/* Pre-allocate the guaranteed number of buffers */
 	if (mempool_fill(pool, GFP_KERNEL)) {
 		mempool_destroy(pool);
 		return NULL;
Signature · 1 line
1.7.3.1
maintainer
#10 lore raw
In reply to Tejun Heo
Quoted 11 lines · On Thu, 22 Dec 2011 13:45:19 -0800 Tejun Heo <[email protected]> wrote:

This patchset implements mempool for percpu memory and use it to solve allocation deadlock problem in block cgroup paths. Percpu memory allocator can't be called from memory reclaim path, mostly because its on-demand chunk filling hooks into vmalloc area management, which in turn hooks into arch pagetable code.

This usually isn't a problem but block cgroup code wants to do opportunistic percpu allocation to track statistics in IO issue path. Currently, it directly calls alloc_percpu() from IO path triggering lockdep warning and falling into deadlocks under the right conditions.

Quoted 6 lines

This patchset adds percpu mempool which supports async refilling and uses that as allocation buffer to solve the above problem. It solves the problem for the next merge window but I'm not sure about what to do about this window and -stable. The mempool updates seems a bit too invasive. Maybe implement a stripped down allocation buffer in block-cgroup?

This is taking the kernel in exactly the wrong direction. More code, more complexity. Let's think of an alternative which takes us in the right direction.

How about we just delete those statistics and then this patchset?

Or how about we change those statistics to not do percpu allocations, then delete this patchset?

Or how about we fix the percpu memory allocation code so that it propagates the gfp flags, then delete this patchset?

All of those things would simplify and/or improve the kernel. Whereas this patchset complicates the kernel while working around known shortcomings.

author maintainer
#11 lore raw

Hello,

Quoted 4 lines · Andrew Morton

How about we just delete those statistics and then this patchset?

Or how about we change those statistics to not do percpu allocations, then delete this patchset?

I'm not against above both but apparently those percpu stats reduced CPU overhead significantly.

Quoted 2 lines

Or how about we fix the percpu memory allocation code so that it propagates the gfp flags, then delete this patchset?

Oh, no, this is gonna make things *way* more complex. I tried. If we're gonna have many more NOIO percpu users, which I don't think we would or should, that might make sense but, for fringe cases, extending mempool to cover percpu is a much better sized solution.

Thanks.

Signature · 1 line
tejun
maintainer
#12 lore raw
Quoted 9 lines · On Thu, 22 Dec 2011 14:09:11 -0800 Tejun Heo <[email protected]> wrote:

Hello,

Quoted 4 lines · Andrew Morton

How about we just delete those statistics and then this patchset?

Or how about we change those statistics to not do percpu allocations, then delete this patchset?

I'm not against above both

Don't just consider my suggestions - please try to come up with your own alternatives too! If all else fails then this patch is a last resort.

Quoted 2 lines

but apparently those percpu stats reduced
CPU overhead significantly.

Deleting them would save even more CPU.

Or make them runtime or compile-time configurable, so only the developers see the impact.

Some specifics on which counters are causing the problems would help here.

Quoted 4 lines
Quoted 2 lines

Or how about we fix the percpu memory allocation code so that it propagates the gfp flags, then delete this patchset?

Oh, no, this is gonna make things *way* more complex. I tried.

But there's a difference between fixing a problem and working around it.

Quoted 4 lines

If
we're gonna have many more NOIO percpu users, which I don't think we would or should, that might make sense but, for fringe cases, extending mempool to cover percpu is a much better sized solution.

I've long felt that we goofed with the gfp_flags thing and that it should be a field in the task_struct. Now *that* would be a large patch!

author maintainer
#13 lore raw

Hello, Andrew.

Quoted 2 lines · Andrew Morton

Don't just consider my suggestions - please try to come up with your own alternatives too! If all else fails then this patch is a last resort.

Umm... this is my alternative.

Quoted 9 lines
Quoted 2 lines

but apparently those percpu stats reduced
CPU overhead significantly.

Deleting them would save even more CPU.

Or make them runtime or compile-time configurable, so only the developers see the impact.

Some specifics on which counters are causing the problems would help here.

These stats are userland visible and quite useful ones if blkcg is in use. I don't really see how these can be removed.

Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

Or how about we fix the percpu memory allocation code so that it propagates the gfp flags, then delete this patchset?

Oh, no, this is gonna make things *way* more complex. I tried.

But there's a difference between fixing a problem and working around it.

Yeah, that was my first direction too. The reason why percpu can't do NOIO is the same one why vmalloc can't do it. It reaches pretty deep into page table code and I don't think doing all that churning is worthwhile or even desirable. An altnernative approach would be implementing transparent front buffer to percpu allocator, which I *might* do if there really are more of these users, but I think keeping percpu allocator painful to use from reclaim context isn't such a bad idea.

There have been multiple requests for atomic allocation and they all have been successfully pushed back, but IMHO this is a valid one and I don't see a better way around the problem, so while I agree using mempool for this is a workaround, I think it is a right choice, for now, anyway.

Quoted 8 lines
Quoted 4 lines

If we're gonna have many more NOIO percpu users, which I don't think we would or should, that might make sense but, for fringe cases, extending mempool to cover percpu is a much better sized solution.

I've long felt that we goofed with the gfp_flags thing and that it should be a field in the task_struct. Now *that* would be a large patch!

Yeah, some of PF_* flags already carry related role information. I'm not too sure how much pushing the whole thing into task_struct would change tho. We would need push/popping. It could be simpler in some cases but in essence wouldn't we have just relocated the position of parameter?

Thanks.

Signature · 1 line
tejun
maintainer
#14 lore raw
Quoted 7 lines · On Thu, 22 Dec 2011 14:41:17 -0800 Tejun Heo <[email protected]> wrote:

Hello, Andrew.

Quoted 2 lines · Andrew Morton

Don't just consider my suggestions - please try to come up with your own alternatives too! If all else fails then this patch is a last resort.

Umm... this is my alternative.

We're beyond the point where aany additional kernel complexity should be considered a regression.

Quoted 5 lines
Quoted 5 lines
Quoted 2 lines

but apparently those percpu stats reduced
CPU overhead significantly.

Deleting them would save even more CPU.

Quoted 7 lines
Quoted 4 lines

Or make them runtime or compile-time configurable, so only the developers see the impact.

Some specifics on which counters are causing the problems would help here.

These stats are userland visible and quite useful ones if blkcg is in use. I don't really see how these can be removed.

What stats?

And why are we doing percpu *allocation* so deep in the code? You mean we're *creating* stats counters on an IO path? Sounds odd. Where is this code?

Quoted 16 lines
Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

Or how about we fix the percpu memory allocation code so that it propagates the gfp flags, then delete this patchset?

Oh, no, this is gonna make things *way* more complex. I tried.

But there's a difference between fixing a problem and working around it.

Yeah, that was my first direction too. The reason why percpu can't do NOIO is the same one why vmalloc can't do it. It reaches pretty deep into page table code and I don't think doing all that churning is worthwhile or even desirable. An altnernative approach would be implementing transparent front buffer to percpu allocator, which I *might* do if there really are more of these users, but I think keeping percpu allocator painful to use from reclaim context isn't such a bad idea.

Quoted 5 lines

There have been multiple requests for atomic allocation and they all have been successfully pushed back, but IMHO this is a valid one and I don't see a better way around the problem, so while I agree using mempool for this is a workaround, I think it is a right choice, for now, anyway.

For starters, doing pagetable allocation on the I/O path sounds nutty.

Secondly, GFP_NOIO is a *weaker* allocation mode than GFP_KERNEL. By permitting it with this patchset, we have a kernel which is more likely to get oom failures. Fixing the kernel to not perform GFP_NOIO allocations for these counters will result in a more robust kernel. This is a good thing, which improves the kernel while avoiding adding more compexity elsewhere.

This patchset is the worst option and we should try much harder to avoid applying it!

Quoted 9 lines
Quoted 8 lines
Quoted 4 lines

If we're gonna have many more NOIO percpu users, which I don't think we would or should, that might make sense but, for fringe cases, extending mempool to cover percpu is a much better sized solution.

I've long felt that we goofed with the gfp_flags thing and that it should be a field in the task_struct. Now *that* would be a large patch!

Quoted 5 lines

Yeah, some of PF_* flags already carry related role information. I'm not too sure how much pushing the whole thing into task_struct would change tho. We would need push/popping. It could be simpler in some cases but in essence wouldn't we have just relocated the position of parameter?

The code would get considerably simpler. The big benefit comes when you have deep call stacks - we're presently passing a gfp_t down five layers of function call while none of the intermediate functions even use the thing - they just pass it on to the next guy. Pass it via the task_struct and all that goes away. It would make maintenance a lot easier - at present if you want to add a new kmalloc() to a leaf function you need to edit all five layers of caller functions.

author maintainer
#15 lore raw

Hello, Andrew.

Quoted 4 lines · Andrew Morton
Quoted 2 lines

These stats are userland visible and quite useful ones if blkcg is in use. I don't really see how these can be removed.

What stats?

The ones allocated in the last patch. blk_group_cpu_stats.

Quoted 3 lines

And why are we doing percpu *allocation* so deep in the code? You mean we're *creating* stats counters on an IO path? Sounds odd. Where is this code?

Please read below.

Quoted 31 lines
Quoted 16 lines
Quoted 6 lines
Quoted 4 lines
Quoted 2 lines

Or how about we fix the percpu memory allocation code so that it propagates the gfp flags, then delete this patchset?

Oh, no, this is gonna make things *way* more complex. I tried.

But there's a difference between fixing a problem and working around it.

Yeah, that was my first direction too. The reason why percpu can't do NOIO is the same one why vmalloc can't do it. It reaches pretty deep into page table code and I don't think doing all that churning is worthwhile or even desirable. An altnernative approach would be implementing transparent front buffer to percpu allocator, which I *might* do if there really are more of these users, but I think keeping percpu allocator painful to use from reclaim context isn't such a bad idea.

Quoted 5 lines

There have been multiple requests for atomic allocation and they all have been successfully pushed back, but IMHO this is a valid one and I don't see a better way around the problem, so while I agree using mempool for this is a workaround, I think it is a right choice, for now, anyway.

For starters, doing pagetable allocation on the I/O path sounds nutty.

Secondly, GFP_NOIO is a *weaker* allocation mode than GFP_KERNEL. By permitting it with this patchset, we have a kernel which is more likely to get oom failures. Fixing the kernel to not perform GFP_NOIO allocations for these counters will result in a more robust kernel. This is a good thing, which improves the kernel while avoiding adding more compexity elsewhere.

Quoted 2 lines

This patchset is the worst option and we should try much harder to avoid applying it!

The stats are per cgroup - request_queue pair. We don't want to allocate for all of them for each combination as there are configurations with stupid number of request_queues and silly many cgroups and #cgroups * #request_queue * #cpus can be huge. So, we want on-demand allocation. While the stats are important, they are not critical and allocations can be opportunistic. If the allocation fails this time, we can try it for the next time.

So, yeah, the suggested solution fits the problem. If you have a better idea, please don't be shy.

Quoted 6 lines
Quoted 5 lines

Yeah, some of PF_* flags already carry related role information. I'm not too sure how much pushing the whole thing into task_struct would change tho. We would need push/popping. It could be simpler in some cases but in essence wouldn't we have just relocated the position of parameter?

Quoted 7 lines

The code would get considerably simpler. The big benefit comes when you have deep call stacks - we're presently passing a gfp_t down five layers of function call while none of the intermediate functions even use the thing - they just pass it on to the next guy. Pass it via the task_struct and all that goes away. It would make maintenance a lot easier - at present if you want to add a new kmalloc() to a leaf function you need to edit all five layers of caller functions.

Hmmm... yeah, the relocation could save a lot of hassle, I suppose.

Thanks.

Signature · 1 line
tejun
maintainer
#16 lore raw
Quoted 9 lines · On Thu, 22 Dec 2011 15:00:47 -0800 Tejun Heo <[email protected]> wrote:

Hello, Andrew.

Quoted 4 lines · Andrew Morton
Quoted 2 lines

These stats are userland visible and quite useful ones if blkcg is in use. I don't really see how these can be removed.

What stats?

The ones allocated in the last patch. blk_group_cpu_stats.

What last patch.

I can find no occurence of "blk_group_cpu_stats" on linux-kernel or in the kernel tree.

Quoted 12 lines
Quoted 11 lines

For starters, doing pagetable allocation on the I/O path sounds nutty.

Secondly, GFP_NOIO is a *weaker* allocation mode than GFP_KERNEL. By permitting it with this patchset, we have a kernel which is more likely to get oom failures. Fixing the kernel to not perform GFP_NOIO allocations for these counters will result in a more robust kernel. This is a good thing, which improves the kernel while avoiding adding more compexity elsewhere.

This patchset is the worst option and we should try much harder to avoid applying it!

Quoted 7 lines

The stats are per cgroup - request_queue pair. We don't want to allocate for all of them for each combination as there are configurations with stupid number of request_queues and silly many cgroups and #cgroups * #request_queue * #cpus can be huge. So, we want on-demand allocation. While the stats are important, they are not critical and allocations can be opportunistic. If the allocation fails this time, we can try it for the next time.

Without code to look at I am at a loss.

request_queues are allocated in blk_alloc_queue_node(), which uses GFP_KERNEL (and also mysteriously takes a gfp_t arg).

Quoted 2 lines

So, yeah, the suggested solution fits the problem. If you have a better idea, please don't be shy.

Unsure which solution you're referring to here.

author maintainer
#17 lore raw

Hello,

Quoted 6 lines · Andrew Morton
Quoted 1 line

The ones allocated in the last patch. blk_group_cpu_stats.

What last patch.

I can find no occurence of "blk_group_cpu_stats" on linux-kernel or in the kernel tree.

Sorry it's blkio_group_stats_cpu. It's in the seventh path in this series.

Quoted 9 lines
Quoted 7 lines

The stats are per cgroup - request_queue pair. We don't want to allocate for all of them for each combination as there are configurations with stupid number of request_queues and silly many cgroups and #cgroups * #request_queue * #cpus can be huge. So, we want on-demand allocation. While the stats are important, they are not critical and allocations can be opportunistic. If the allocation fails this time, we can try it for the next time.

Without code to look at I am at a loss.

block/blk-cgroup.c blk-throttle.c cfq-iosched.c. Have fun.

Quoted 2 lines

request_queues are allocated in blk_alloc_queue_node(), which uses GFP_KERNEL (and also mysteriously takes a gfp_t arg).

Yeah, sure, we *can* allocate everything for every combination when either request_queue or cgroup comes up. That's the thing I tried to explain in the above quoted paragraph.

Thanks.

Signature · 1 line
tejun
maintainer
#18 lore raw
Quoted 23 lines · On Thu, 22 Dec 2011 15:24:33 -0800 Tejun Heo <[email protected]> wrote:

Hello,

Quoted 6 lines · Andrew Morton
Quoted 1 line

The ones allocated in the last patch. blk_group_cpu_stats.

What last patch.

I can find no occurence of "blk_group_cpu_stats" on linux-kernel or in the kernel tree.

Sorry it's blkio_group_stats_cpu. It's in the seventh path in this series.

Quoted 9 lines
Quoted 7 lines

The stats are per cgroup - request_queue pair. We don't want to allocate for all of them for each combination as there are configurations with stupid number of request_queues and silly many cgroups and #cgroups * #request_queue * #cpus can be huge. So, we want on-demand allocation. While the stats are important, they are not critical and allocations can be opportunistic. If the allocation fails this time, we can try it for the next time.

Without code to look at I am at a loss.

Quoted 9 lines

block/blk-cgroup.c blk-throttle.c cfq-iosched.c. Have fun.

Quoted 2 lines

request_queues are allocated in blk_alloc_queue_node(), which uses GFP_KERNEL (and also mysteriously takes a gfp_t arg).

Yeah, sure, we *can* allocate everything for every combination when either request_queue or cgroup comes up. That's the thing I tried to explain in the above quoted paragraph.

All the code I'm looking at assumes that blkio_group.stats_cpu is non-zero. Won't the kerenl just go splat if that allocation failed?

If the code *does* correctly handle ->stats_cpu == NULL then we have options.

a) Give userspace a new procfs/debugfs file to start stats gathering on a particular cgroup/request_queue pair. Allocate the stats memory in that.

b) Or allocate stats_cpu on the first call to blkio_read_stat_cpu() and return zeroes for this first call.

c) Or change the low-level code to do blkio_group.want_stats_cpu=true, then test that at the top level after we've determined that blkio_group.stats_cpu is NULL.

d) Or, worse, punt the allocation into a workqueue thread.

Note that all these option will permit us to use GFP_KERNEL, which is better.

Note that a) and b) means that users get control over whether these stats are accumulated at all, so many won't incur needless memory and CPU consumption.

I think I like b). Fix the code so it doesn't oops when ->stats_cpu is NULL, then turn on stats gathering the first time someone tries to read the stats.

(Someone appears to have misspelled "throttle" as "throtl" for no apparent reason about 1000 times. Sigh.)

author maintainer
#19 lore raw

Hello,

Quoted 5 lines · Andrew Morton

All the code I'm looking at assumes that blkio_group.stats_cpu is non-zero. Won't the kerenl just go splat if that allocation failed?

If the code *does* correctly handle ->stats_cpu == NULL then we have options.

I think it's supposed to just skip creating whole blk_group if percpu allocation fails, so ->stats_cpu of existing groups are guaranteed to be !%NULL.

Quoted 6 lines

a) Give userspace a new procfs/debugfs file to start stats gathering on a particular cgroup/request_queue pair. Allocate the stats memory in that.

b) Or allocate stats_cpu on the first call to blkio_read_stat_cpu() and return zeroes for this first call.

Hmmm... IIRC, the stats aren't exported per cgroup-request_queue pair, so reads are issued per cgroup. We can't tell which request_queues userland is actually interested in.

Quoted 3 lines

c) Or change the low-level code to do blkio_group.want_stats_cpu=true, then test that at the top level after we've determined that blkio_group.stats_cpu is NULL.

Not following. Where's the "top level"?

Quoted 1 line

d) Or, worse, punt the allocation into a workqueue thread.

I would much prefer using mempool to this. They are essentially the same approach.

Thanks.

Signature · 1 line
tejun
#8 lore raw

Re: [PATCH 7/7] block: fix deadlock through percpu allocation in blk-cgroup

In reply to Tejun Heo

On Thu, Dec 22, 2011 at 01:45:26PM -0800, Tejun Heo wrote:

[..]

block/blk-cgroup.c line 46

Quoted 8 lines
block/blk-cgroup.c +8 -0
+/*
+ * Percpu mempool for blkgio_group_stats_cpu which are allocated on-demand
+ * on IO path.  As percpu doesn't support NOIO allocations, we need to
+ * buffer them through mempool.
+ */
+struct percpu_mempool *blkg_stats_cpu_pool;
+EXPORT_SYMBOL_GPL(blkg_stats_cpu_pool);
+

Thanks for this work Tejun.

So this pool is global and shared by all devices (both by CFQ and throttling logic). I am not sure if there are any advantages of having this pool per queue. In one of the mails you mentioned that dm is having one pool across many devices which defeats the purpose of having mempool.

**********************************************************************
It seemed the problem was dm sharing the same pool from multiple devices (which defeats the purpose of using mempool BTW)
*********************************************************************

Not sure why devices sharing a mempool is a bad idea. Having a global pool definitely simplifies the implementation a lot in this case.

Thanks
Vivek

maintainer
#20 lore raw
In reply to Tejun Heo
Quoted 6 lines · On Thu, 22 Dec 2011 15:54:55 -0800 Tejun Heo <[email protected]> wrote:

Hello,

Quoted 3 lines · Andrew Morton

All the code I'm looking at assumes that blkio_group.stats_cpu is non-zero. Won't the kerenl just go splat if that allocation failed?

Quoted 6 lines
Quoted 2 lines

If the code *does* correctly handle ->stats_cpu == NULL then we have options.

I think it's supposed to just skip creating whole blk_group if percpu allocation fails, so ->stats_cpu of existing groups are guaranteed to be !%NULL.

What is the role of ->elevator_set_req_fn()? And when is it called?

It seems that we allocate the blkio_group within the elevator_set_req_fn() context?

(Your stack trace in the "block: fix deadlock through percpu allocation in blk-cgroup" changelog is some unuseful ACPI thing. It would be better if it were to show the offending trace into the block code).

Quoted 10 lines
Quoted 6 lines

a) Give userspace a new procfs/debugfs file to start stats gathering on a particular cgroup/request_queue pair. Allocate the stats memory in that.

b) Or allocate stats_cpu on the first call to blkio_read_stat_cpu() and return zeroes for this first call.

Hmmm... IIRC, the stats aren't exported per cgroup-request_queue pair, so reads are issued per cgroup. We can't tell which request_queues userland is actually interested in.

Doesn't matter. The stats are allocated on a per-blkio_group basis. blkio_read_stat_cpu() is passed the blkio_group. Populate ->stats_cpu there.

Advantages:

- performs allocation with the more reliable GPF_KERNEL

- avoids burdening users with the space and CPU overhead when they're not using the stats

- avoids adding more code into the mempool code.

Quoted 5 lines
Quoted 3 lines

c) Or change the low-level code to do blkio_group.want_stats_cpu=true, then test that at the top level after we've determined that blkio_group.stats_cpu is NULL.

Not following. Where's the "top level"?

Somewhere appropriate where we can use GFP_KERNEL. ie: the correct context for percpu_alloc().

Separately...

Mixing mempools and percpu_alloc() in the proposed fashion seems a pretty poor fit. mempools are for high-frequency low-level allocations which have key characteristics: there are typically a finite number of elements in flight and we *know* that elements are being freed in a timely manner.

This doesn't fit with percpu_alloc(), which is a very heavyweight operation requiring GFP_KERNEL and it doesn't fit with blkio_group_stats_cpu because blkio_group_stats_cpu does not have the "freed in a timely manner" behaviour.

To resolve these things you've added the workqueue to keep the pool populated, which turns percpu_mempool into a quite different concept which happens to borrow some mempool code (not necessarily a bad thing). This will result in some memory wastage, keeping that pool full.

More significantly, it's pretty unreliable: if the allocations outpace the kernel thread's ability to refill the pool, all we can do is to wait for the kernel thread to do some work. But we're holding low-level locks while doing that wait, which will block the kernel thread. Deadlock.

#27 lore raw
In reply to Andrew Morton
Quoted 31 lines · Andrew Morton
Quoted 28 lines · On Thu, 22 Dec 2011 15:24:33 -0800 Tejun Heo <[email protected]> wrote:

Hello,

Quoted 6 lines · Andrew Morton
Quoted 1 line

The ones allocated in the last patch. blk_group_cpu_stats.

What last patch.

I can find no occurence of "blk_group_cpu_stats" on linux-kernel or in the kernel tree.

Sorry it's blkio_group_stats_cpu. It's in the seventh path in this series.

Quoted 9 lines
Quoted 7 lines

The stats are per cgroup - request_queue pair. We don't want to allocate for all of them for each combination as there are configurations with stupid number of request_queues and silly many cgroups and #cgroups * #request_queue * #cpus can be huge. So, we want on-demand allocation. While the stats are important, they are not critical and allocations can be opportunistic. If the allocation fails this time, we can try it for the next time.

Without code to look at I am at a loss.

block/blk-cgroup.c blk-throttle.c cfq-iosched.c. Have fun.

Quoted 2 lines

request_queues are allocated in blk_alloc_queue_node(), which uses GFP_KERNEL (and also mysteriously takes a gfp_t arg).

Quoted 7 lines
Quoted 4 lines

Yeah, sure, we *can* allocate everything for every combination when either request_queue or cgroup comes up. That's the thing I tried to explain in the above quoted paragraph.

All the code I'm looking at assumes that blkio_group.stats_cpu is non-zero. Won't the kerenl just go splat if that allocation failed?

If per cpu stat allocation fails, we fail the whole group allocation and IO is accounted to root group and is tried again when new IO request comes in.

Look at throtl_alloc_tg() in block/blk-throttle.c

Quoted 10 lines

If the code *does* correctly handle ->stats_cpu == NULL then we have options.

a) Give userspace a new procfs/debugfs file to start stats gathering on a particular cgroup/request_queue pair. Allocate the stats memory in that.

b) Or allocate stats_cpu on the first call to blkio_read_stat_cpu() and return zeroes for this first call.

But the purpose of stats is that they are gathered even if somebody has not read them even once? So if I create a cgroup and put some task into it which does some IO, I think stat collection should start immediately without user taking any action. Forcing the user to first read a stat before the collection starts is kind of odd to me.

Quoted 6 lines

c) Or change the low-level code to do blkio_group.want_stats_cpu=true, then test that at the top level after we've determined that blkio_group.stats_cpu is NULL.

d) Or, worse, punt the allocation into a workqueue thread.

I implemented a patch to punt the allocation using a worker thread. Tejun did not like it. I personally think that it is less intrusive to fix this specific problem.

https://lkml.org/lkml/2011/12/19/291

Quoted 8 lines

Note that all these option will permit us to use GFP_KERNEL, which is better.

Note that a) and b) means that users get control over whether these stats are accumulated at all, so many won't incur needless memory and CPU consumption.

Quoted 6 lines

I think I like b). Fix the code so it doesn't oops when ->stats_cpu is NULL, then turn on stats gathering the first time someone tries to read the stats.

(Someone appears to have misspelled "throttle" as "throtl" for no apparent reason about 1000 times. Sigh.)

That someone would be me. I thought that throtl communicates the meaning and keeps the length of all the strings relatively short. But if it does not look good, I can change it.

Thanks
Vivek

maintainer
#28 lore raw
Quoted 9 lines · On Thu, 22 Dec 2011 20:21:12 -0500 Vivek Goyal <[email protected]> wrote:
Quoted 8 lines · Andrew Morton

If the code *does* correctly handle ->stats_cpu == NULL then we have options.

a) Give userspace a new procfs/debugfs file to start stats gathering on a particular cgroup/request_queue pair. Allocate the stats memory in that.

Quoted 5 lines
Quoted 2 lines

b) Or allocate stats_cpu on the first call to blkio_read_stat_cpu() and return zeroes for this first call.

But the purpose of stats is that they are gathered even if somebody has not read them even once?

That's not a useful way of using stats. The normal usage would be to record the stats then start the workload then monitor how the stats have changed as work proceeds.

Quoted 3 lines

So if I create a cgroup and put some
task into it which does some IO, I think stat collection should start immediately without user taking any action.

If you really want to know the stats since cgroup creation then trigger the stats initialisation from userspace when creating the blkio_cgroup.

Quoted 2 lines

Forcing the user to first
read a stat before the collection starts is kind of odd to me.

Well one could add a separate stats_enable knob. Doing it automatically from read() would be for approximate-back-compatibility with existing behaviour.

Plus (again) this way we also avoid burdening non-stats-users with the overhead of stats.

Quoted 5 lines
Quoted 5 lines

c) Or change the low-level code to do blkio_group.want_stats_cpu=true, then test that at the top level after we've determined that blkio_group.stats_cpu is NULL.

Quoted 7 lines
Quoted 1 line

d) Or, worse, punt the allocation into a workqueue thread.

I implemented a patch to punt the allocation using a worker thread. Tejun did not like it. I personally think that it is less intrusive to fix this specific problem.

https://lkml.org/lkml/2011/12/19/291

hm.

Look, the basic problem here is a highish-level design one. We're attempting to do a high-level heavyweight intialization operation in a low-level place. How do we fix that *properly*? It has to be by performing the heavyweight operation in an appropriate place.

Quoted 12 lines
Quoted 12 lines

Note that all these option will permit us to use GFP_KERNEL, which is better.

Note that a) and b) means that users get control over whether these stats are accumulated at all, so many won't incur needless memory and CPU consumption.

I think I like b). Fix the code so it doesn't oops when ->stats_cpu is NULL, then turn on stats gathering the first time someone tries to read the stats.

Quoted 6 lines
Quoted 2 lines

(Someone appears to have misspelled "throttle" as "throtl" for no apparent reason about 1000 times. Sigh.)

That someone would be me. I thought that throtl communicates the meaning and keeps the length of all the strings relatively short. But if it does not look good, I can change it.

It's unconventional. We do usually avoid the odd abbreviations and just spell the whole thing out.

#37 lore raw
In reply to Andrew Morton
Quoted 21 lines · Andrew Morton
Quoted 9 lines · On Thu, 22 Dec 2011 14:09:11 -0800 Tejun Heo <[email protected]> wrote:

Hello,

Quoted 4 lines · Andrew Morton

How about we just delete those statistics and then this patchset?

Or how about we change those statistics to not do percpu allocations, then delete this patchset?

I'm not against above both

Don't just consider my suggestions - please try to come up with your own alternatives too! If all else fails then this patch is a last resort.

Quoted 2 lines

but apparently those percpu stats reduced
CPU overhead significantly.

Deleting them would save even more CPU.

[..]

Quoted 2 lines

Or make them runtime or compile-time configurable, so only the developers see the impact.

Some of the stats are already under debug option (DEBUG_BLK_CGROUP). But rest seem to be useful ones to be put under debug option.

Making them run time configuration is an option. I am assuming that would be a global option and not per cgroup per device option. If yes, then again you have same problem where after enabling the stat, any new group creation or new device creation will require allocation of per cpu stat.

So I think we need to figure out a way to be able to allocation per cpu stat dynamically.

Quoted 2 lines

Some specifics on which counters are causing the problems would help here.

Various kind of stats are collected. Current per cpu stats are.

- Number of sectors transferred.
- Number of bytes transferred.
- Number of IOs transferred.
- Number of IOs merged

If a user has not put any throttling rules in the cgroup, then we do want to collect the stats but don't want to take any locks. Otherwise on fast devices, ex PCI-E based flash, it becomes a bottleneck.

So far we were taking request queue lock. I guess if we fall back to non-per cpu stats, we should be able to get away with group's stat lock (blkg->stats_lock) and access the group under rcu. So this will be an improvement as lock will be per group and not per device but I think it is still a problem for most of the users because most contended group is root group.

Distributions are now shipping throttling logic enabled and by default all IO goes through root group and for every IO submission we don't want to take blkg->stats lock just to collect the stats.

That's why the need of per cpu data structures to make stat collection lockless.

Thanks
Vivek

maintainer
#38 lore raw
Quoted 2 lines · On Thu, 22 Dec 2011 20:40:43 -0500 Vivek Goyal <[email protected]> wrote:

That's why the need of per cpu data structures to make stat collection lockless.

btw, (and this is a common refrain): was there any reason for avoiding using percpu_counters here?

afacit these stats don't have the transient-negative-number problem because they're purely upcounters, but percpu_counters would be helpful when num_online_cpus is much less than num_possible_cpus. Plus it would avoid implementing yet another hand-coded percpu_counter...

#29 lore raw
In reply to Andrew Morton
Quoted 14 lines · Andrew Morton
Quoted 12 lines · On Thu, 22 Dec 2011 20:21:12 -0500 Vivek Goyal <[email protected]> wrote:
Quoted 10 lines · Andrew Morton

If the code *does* correctly handle ->stats_cpu == NULL then we have options.

a) Give userspace a new procfs/debugfs file to start stats gathering on a particular cgroup/request_queue pair. Allocate the stats memory in that.

b) Or allocate stats_cpu on the first call to blkio_read_stat_cpu() and return zeroes for this first call.

Quoted 6 lines
Quoted 2 lines

But the purpose of stats is that they are gathered even if somebody has not read them even once?

That's not a useful way of using stats. The normal usage would be to record the stats then start the workload then monitor how the stats have changed as work proceeds.

I have atleast one example "iostat" which does not follow this. Its first report shows the total stats since the system boot and each subsequent report covers time since previous report. With stats being available since the cgroup creation time, one can think of extending iostat tool to display per IO cgroup stats too.

Also we have a knob "reset_stats" to reset all the stats to zero. So one can first reset stats, starts workload and then monitor it (if one does not like stats since the cgroup creation time).

Quoted 7 lines
Quoted 4 lines

So if I create a cgroup and put some
task into it which does some IO, I think stat collection should start immediately without user taking any action.

If you really want to know the stats since cgroup creation then trigger the stats initialisation from userspace when creating the blkio_cgroup.

These per cpu stats are per cgroup per device. So if a workload in a cgroup is doing IO to 4 devices, we allocate 4 percpu stat areas for stats. So at cgroup creation time we just don't know how many of these to create and also it does not cover the case of device hotplug after cgroup creation.

Quoted 10 lines
Quoted 3 lines

Forcing the user to first
read a stat before the collection starts is kind of odd to me.

Well one could add a separate stats_enable knob. Doing it automatically from read() would be for approximate-back-compatibility with existing behaviour.

Plus (again) this way we also avoid burdening non-stats-users with the overhead of stats.

Even if we do that we have the problem with hoplugged device. Assume a cgroup created, stats enabled now a new devices shows up and some task in the group does IO on that device. Now we need to create percpu data area for that cgroup-device pair dynamically in IO path and we are back to the same problem.

Thanks
Vivek

#39 lore raw
In reply to Andrew Morton
Quoted 7 lines · Andrew Morton
Quoted 2 lines · On Thu, 22 Dec 2011 20:40:43 -0500 Vivek Goyal <[email protected]> wrote:

That's why the need of per cpu data structures to make stat collection lockless.

btw, (and this is a common refrain): was there any reason for avoiding using percpu_counters here?

Frankly speaking I did not consider that. I will look into it (/me needs to read up a bit on per cpu counter and look at code examples).

Thanks
Vivek

maintainer
#30 lore raw
In reply to Vivek Goyal
Quoted 22 lines · On Thu, 22 Dec 2011 21:54:11 -0500 Vivek Goyal <[email protected]> wrote:
Quoted 14 lines · Andrew Morton
Quoted 12 lines · On Thu, 22 Dec 2011 20:21:12 -0500 Vivek Goyal <[email protected]> wrote:
Quoted 10 lines · Andrew Morton

If the code *does* correctly handle ->stats_cpu == NULL then we have options.

a) Give userspace a new procfs/debugfs file to start stats gathering on a particular cgroup/request_queue pair. Allocate the stats memory in that.

b) Or allocate stats_cpu on the first call to blkio_read_stat_cpu() and return zeroes for this first call.

Quoted 6 lines
Quoted 2 lines

But the purpose of stats is that they are gathered even if somebody has not read them even once?

That's not a useful way of using stats. The normal usage would be to record the stats then start the workload then monitor how the stats have changed as work proceeds.

Quoted 5 lines

I have atleast one example "iostat" which does not follow this. Its first report shows the total stats since the system boot and each subsequent report covers time since previous report. With stats being available since the cgroup creation time, one can think of extending iostat tool to display per IO cgroup stats too.

If that's useful (dubious) then it can be addressed by creating the stats when a device is bound to the cgroup (below).

Quoted 9 lines

Also we have a knob "reset_stats" to reset all the stats to zero. So one can first reset stats, starts workload and then monitor it (if one does not like stats since the cgroup creation time).

Quoted 5 lines
Quoted 4 lines

So if I create a cgroup and put some
task into it which does some IO, I think stat collection should start immediately without user taking any action.

Quoted 8 lines
Quoted 2 lines

If you really want to know the stats since cgroup creation then trigger the stats initialisation from userspace when creating the blkio_cgroup.

These per cpu stats are per cgroup per device. So if a workload in a cgroup is doing IO to 4 devices, we allocate 4 percpu stat areas for stats. So at cgroup creation time we just don't know how many of these to create and also it does not cover the case of device hotplug after cgroup creation.

Mark the cgroup as "needing stats" then allocate the stats (if needed) when a device is bound to the cgroup. Rather than on first I/O.

Quoted 8 lines
Quoted 8 lines
Quoted 3 lines

Forcing the user to first
read a stat before the collection starts is kind of odd to me.

Well one could add a separate stats_enable knob. Doing it automatically from read() would be for approximate-back-compatibility with existing behaviour.

Quoted 8 lines
Quoted 2 lines

Plus (again) this way we also avoid burdening non-stats-users with the overhead of stats.

Even if we do that we have the problem with hoplugged device. Assume a cgroup created, stats enabled now a new devices shows up and some task in the group does IO on that device. Now we need to create percpu data area for that cgroup-device pair dynamically in IO path and we are back to the same problem.

Why do the allocation during I/O? Can't it be done in the hotplug handler?

Please, don't expend brain cells thinking of reasons why this all can't be done. Instead expend them on finding a way in which it *can* be done!

Maybe doing all this cgroups stuff within ->elevator_set_req_fn() was the wrong design decision.

#50 lore raw
In reply to Andrew Morton
Quoted 7 lines · Andrew Morton
Quoted 2 lines · On Thu, 22 Dec 2011 20:40:43 -0500 Vivek Goyal <[email protected]> wrote:

That's why the need of per cpu data structures to make stat collection lockless.

btw, (and this is a common refrain): was there any reason for avoiding using percpu_counters here?

IIUC, per cpu counters also call alloc_percpu() during initialization.

int __percpu_counter_init(struct percpu_counter *fbc, s64 amount,
struct lock_class_key *key)

{
        raw_spin_lock_init(&fbc->lock);
        lockdep_set_class(&fbc->lock, key);
        fbc->count = amount;
        fbc->counters = alloc_percpu(s32);

....
....
}

So they are no good either for allocation and initialization in IO path.

Thanks
Vivek

#31 lore raw
In reply to Andrew Morton
Quoted 45 lines · Andrew Morton
Quoted 22 lines · On Thu, 22 Dec 2011 21:54:11 -0500 Vivek Goyal <[email protected]> wrote:
Quoted 14 lines · Andrew Morton
Quoted 12 lines · On Thu, 22 Dec 2011 20:21:12 -0500 Vivek Goyal <[email protected]> wrote:
Quoted 10 lines · Andrew Morton

If the code *does* correctly handle ->stats_cpu == NULL then we have options.

a) Give userspace a new procfs/debugfs file to start stats gathering on a particular cgroup/request_queue pair. Allocate the stats memory in that.

b) Or allocate stats_cpu on the first call to blkio_read_stat_cpu() and return zeroes for this first call.

Quoted 6 lines
Quoted 2 lines

But the purpose of stats is that they are gathered even if somebody has not read them even once?

That's not a useful way of using stats. The normal usage would be to record the stats then start the workload then monitor how the stats have changed as work proceeds.

Quoted 5 lines

I have atleast one example "iostat" which does not follow this. Its first report shows the total stats since the system boot and each subsequent report covers time since previous report. With stats being available since the cgroup creation time, one can think of extending iostat tool to display per IO cgroup stats too.

If that's useful (dubious) then it can be addressed by creating the stats when a device is bound to the cgroup (below).

Quoted 12 lines

Also we have a knob "reset_stats" to reset all the stats to zero. So one can first reset stats, starts workload and then monitor it (if one does not like stats since the cgroup creation time).

Quoted 7 lines
Quoted 4 lines

So if I create a cgroup and put some
task into it which does some IO, I think stat collection should start immediately without user taking any action.

If you really want to know the stats since cgroup creation then trigger the stats initialisation from userspace when creating the blkio_cgroup.

Quoted 8 lines
Quoted 5 lines

These per cpu stats are per cgroup per device. So if a workload in a cgroup is doing IO to 4 devices, we allocate 4 percpu stat areas for stats. So at cgroup creation time we just don't know how many of these to create and also it does not cover the case of device hotplug after cgroup creation.

Mark the cgroup as "needing stats" then allocate the stats (if needed) when a device is bound to the cgroup. Rather than on first I/O.

This will work for the throttling case where a user has to specifically put throttling rules for each device and that can be considered as binding device to the cgroup. In that case we will not be collecting the stats for which there are no rules for the device. I guess I can live with that.

But it still does not work for the case of CFQ where there might not be any user initiated device binding to cgroup. User might just specify a cgroup weight (like task ioprio) and binding to device is automatically created on first IO to the device from the cgroup. User does not initiate any specific binding.

Quoted 12 lines
Quoted 12 lines
Quoted 11 lines
Quoted 4 lines

Forcing the user to first
read a stat before the collection starts is kind of odd to me.

Well one could add a separate stats_enable knob. Doing it automatically from read() would be for approximate-back-compatibility with existing behaviour.

Plus (again) this way we also avoid burdening non-stats-users with the overhead of stats.

Quoted 8 lines
Quoted 5 lines

Even if we do that we have the problem with hoplugged device. Assume a cgroup created, stats enabled now a new devices shows up and some task in the group does IO on that device. Now we need to create percpu data area for that cgroup-device pair dynamically in IO path and we are back to the same problem.

Why do the allocation during I/O? Can't it be done in the hotplug handler?

Even if we can do it in hotplug handler it will be very wasteful of memory. So if there are 100 IO cgroups in the system, upon every block device hotplug, we will allocate per cpu memory for all the 100 cgroups, irrespective of the fact whether they are doing IO to the device or not.

Now expand this to a system with 100 cgroups and 100 Luns. 10000 allocations for no reason. (Even if we do it for cgroups needing stats, does not help much). Current scheme allocates memory for the group only if a sepcific cgroup is doing IO to a specific block device.

Thanks
Vivek

#21 lore raw
In reply to Andrew Morton

On Thu, Dec 22, 2011 at 05:14:32PM -0800, Andrew Morton wrote:

[..]

Quoted 13 lines

Separately...

Mixing mempools and percpu_alloc() in the proposed fashion seems a pretty poor fit. mempools are for high-frequency low-level allocations which have key characteristics: there are typically a finite number of elements in flight and we *know* that elements are being freed in a timely manner.

This doesn't fit with percpu_alloc(), which is a very heavyweight operation requiring GFP_KERNEL and it doesn't fit with blkio_group_stats_cpu because blkio_group_stats_cpu does not have the "freed in a timely manner" behaviour.

Quoted 4 lines

To resolve these things you've added the workqueue to keep the pool populated, which turns percpu_mempool into a quite different concept which happens to borrow some mempool code (not necessarily a bad thing). This will result in some memory wastage, keeping that pool full.

Tejun seems to have created one global pool for all the device with minimum number of objects at 8. So keeping just 8 objects aside for the whole system is not a significant memory wastage, IMHO. This is much better then creating all the possible cgroup, device pair cgroup irrespective of the fact whether IO is happening on that pair or not.

Quoted 6 lines

More significantly, it's pretty unreliable: if the allocations outpace the kernel thread's ability to refill the pool, all we can do is to wait for the kernel thread to do some work. But we're holding low-level locks while doing that wait, which will block the kernel thread. Deadlock.

Sorry, I did not understand this point. In the IO path we don't wait for kernel thread to do some work. If there are no elements in the pool, we will simply return and not create the group and IO will be accounted to root group. Once the new IO comes in, it will try again and if by that time worker thread succeeded in filling the pool, we will allocate the group.

So in tight memory situation we will not account the IO to actual cgroup but to root cgroup. Once the memory situation eases, IO will be acccounted to right cgroup.

Can't see any deadlock happening. Did I miss something?

Thanks
Vivek

author maintainer
#9 lore raw

Re: [PATCH 7/7] block: fix deadlock through percpu allocation in blk-cgroup

In reply to Vivek Goyal

Hello,

Quoted 5 lines · Vivek Goyal

So this pool is global and shared by all devices (both by CFQ and throttling logic). I am not sure if there are any advantages of having this pool per queue. In one of the mails you mentioned that dm is having one pool across many devices which defeats the purpose of having mempool.

Quoted 7 lines

**********************************************************************
It seemed the problem was dm sharing the same pool from multiple devices (which defeats the purpose of using mempool BTW)
*********************************************************************

Not sure why devices sharing a mempool is a bad idea. Having a global pool definitely simplifies the implementation a lot in this case.

Ooh, sharing breaks the forward progress guarantee by mempool. blkcg isn't using mempool for that. It's just using it as allocation buffer so it isn't relevant.

Thanks.

Signature · 1 line
tejun
#40 lore raw
In reply to Vivek Goyal
Quoted 12 lines · On Thu, 22 Dec 2011 21:56:29 -0500 Vivek Goyal <[email protected]> wrote:
Quoted 7 lines · Andrew Morton
Quoted 2 lines · On Thu, 22 Dec 2011 20:40:43 -0500 Vivek Goyal <[email protected]> wrote:

That's why the need of per cpu data structures to make stat collection lockless.

btw, (and this is a common refrain): was there any reason for avoiding using percpu_counters here?

Frankly speaking I did not consider that. I will look into it (/me needs to read up a bit on per cpu counter and look at code examples).

Hm, how about this kind of delayed initialization ?

== this patch is untested. just for sharing idea ==

Quoted 1 line

From 433b56fd5644d4b1e695bc16bbf8dd78842999fd Mon Sep 17 00:00:00 2001

From: KAMEZAWA Hiroyuki <[email protected]>
Date: Mon, 26 Dec 2011 15:06:21 +0900
Subject: [PATCH] percpu_counter: add lazy init

percpu_counter calls alloc_percpu(). This means percpu_counter_init() assumes GFP_KERNEL context. This may call vmalloc() in percpu_counter allocation and will have locks.

If a caller doesn't want to assume GFP_KERNEL, we need some tricks. This patch adds percpu_counter_init_lazy().

At lazy allocation, the function leaves fbc->counters as NULL and init fbc->counters by workqueue. This work item handling is done by fbc->list, so, the struct size of 'fbc' will not increase if a user configs CONFIG_HOTPLUG_CPU.

---
 include/linux/percpu_counter.h |   32 +++++++-----
 lib/percpu_counter.c           |  110 +++++++++++++++++++++++++++++----------
 2 files changed, 100 insertions(+), 42 deletions(-)
include/linux/percpu_counter.h +18 -14
index b9df9ed..1ab6d9a 100644
@@ -18,22 +18,31 @@
 struct percpu_counter {
 	raw_spinlock_t lock;
 	s64 count;
-#ifdef CONFIG_HOTPLUG_CPU
 	struct list_head list;	/* All percpu_counters are on a list */
-#endif
 	s32 __percpu *counters;
 };
 
 extern int percpu_counter_batch;
 
 int __percpu_counter_init(struct percpu_counter *fbc, s64 amount,
-			  struct lock_class_key *key);
+			  bool lazy, struct lock_class_key *key);
 
+/* percpu_counter_init() requires GFP_KERNEL context. */
 #define percpu_counter_init(fbc, value)					\
 	({								\
 		static struct lock_class_key __key;			\
 									\
-		__percpu_counter_init(fbc, value, &__key);		\
+		__percpu_counter_init(fbc, value, false, &__key);	\
+	})
+/*
+ * percpu_counter_lazy_init() doesn't requires GFP_KERNEL but cannot be
+ * called in interrupt context. This function may sleep.
+ */
+#define percpu_couneter_lazy_init(fbc, value)				\
+	({								\
+		static struct lock_class_key __key;			\
+									\
+		__percpu_counter_lazy_init(fbc, value, true, &_key);	\
 	})
 
 void percpu_counter_destroy(struct percpu_counter *fbc);
@@ -78,11 +87,6 @@ static inline s64 percpu_counter_read_positive(struct percpu_counter *fbc)
 	return 0;
 }
 
-static inline int percpu_counter_initialized(struct percpu_counter *fbc)
-{
-	return (fbc->counters != NULL);
-}
-
 #else
 
 struct percpu_counter {
@@ -94,6 +98,11 @@ static inline int percpu_counter_init(struct percpu_counter *fbc, s64 amount)
 	fbc->count = amount;
 	return 0;
 }
+static inline int
+percpu_counter_lazy_init(struct percpu_counter *fbc, s64 amount)
+{
+	return percpu_counter_init(fbc, amount);
+}
 
 static inline void percpu_counter_destroy(struct percpu_counter *fbc)
 {
@@ -152,11 +161,6 @@ static inline s64 percpu_counter_sum(struct percpu_counter *fbc)
 	return percpu_counter_read(fbc);
 }
 
-static inline int percpu_counter_initialized(struct percpu_counter *fbc)
-{
-	return 1;
-}
-
 #endif	/* CONFIG_SMP */
 
 static inline void percpu_counter_inc(struct percpu_counter *fbc)
lib/percpu_counter.c +82 -28

164 lines not on this page · raw message

Signature · 1 line
1.7.4.1
author maintainer
#41 lore raw

Hello, KAMEZAWA.

Quoted 9 lines · KAMEZAWA Hiroyuki

From 433b56fd5644d4b1e695bc16bbf8dd78842999fd Mon Sep 17 00:00:00 2001
From: KAMEZAWA Hiroyuki <[email protected]>
Date: Mon, 26 Dec 2011 15:06:21 +0900
Subject: [PATCH] percpu_counter: add lazy init

percpu_counter calls alloc_percpu(). This means percpu_counter_init() assumes GFP_KERNEL context. This may call vmalloc() in percpu_counter allocation and will have locks.

Quoted 7 lines

If a caller doesn't want to assume GFP_KERNEL, we need some tricks. This patch adds percpu_counter_init_lazy().

At lazy allocation, the function leaves fbc->counters as NULL and init fbc->counters by workqueue. This work item handling is done by fbc->list, so, the struct size of 'fbc' will not increase if a user configs CONFIG_HOTPLUG_CPU.

This is essentially more specialized form of the mempool approach. It doesn't seem any simpler to me while being less generic. I don't see what the upside would be.

Thanks.

Signature · 1 line
tejun
author maintainer
#22 lore raw
In reply to Andrew Morton

(cc'ing Jens)

Hello, Andrew.

Quoted 8 lines · Andrew Morton
Quoted 6 lines · On Thu, 22 Dec 2011 15:54:55 -0800 Tejun Heo <[email protected]> wrote:

Hello,

Quoted 3 lines · Andrew Morton

All the code I'm looking at assumes that blkio_group.stats_cpu is non-zero. Won't the kerenl just go splat if that allocation failed?

Quoted 8 lines
Quoted 6 lines
Quoted 2 lines

If the code *does* correctly handle ->stats_cpu == NULL then we have options.

I think it's supposed to just skip creating whole blk_group if percpu allocation fails, so ->stats_cpu of existing groups are guaranteed to be !%NULL.

What is the role of ->elevator_set_req_fn()? And when is it called?

It allocates elevator specific data for a request and is called during request construction, IOW, on IO issue path.

Quoted 2 lines

It seems that we allocate the blkio_group within the elevator_set_req_fn() context?

The allocation may happen through any subsystem which implements blkcg policy - at the moment, either blk-throttle or cfq-iosched. elevator_set_req_fn() is for cfq-iosched. In most cases, the user is expected to be in IO submission path as that's the only place we can identify active blkcg - request_queue pairs and we don't want to create blk_group for all possible combinations.

Quoted 7 lines
Quoted 3 lines

Hmmm... IIRC, the stats aren't exported per cgroup-request_queue pair, so reads are issued per cgroup. We can't tell which request_queues userland is actually interested in.

Doesn't matter. The stats are allocated on a per-blkio_group basis. blkio_read_stat_cpu() is passed the blkio_group. Populate ->stats_cpu there.

Hmmm.... so you wanna break up blkg and its per-cpu stats allocation.

One problem I see is that there's no reliable way to tell when the stats for specific pair has started. ie. Reading the stats file from userland shouldn't create blkg for all matching combinations. It should only walk the blkgs which are created by actual IOs. So, blkg stat counting would start on the first stats read after IOs happen for that specific pair and there wouldn't be any way for userland to discover whether stat gathering is in progress or not. Ugh... that's just nasty. Jens, what do you think?

Quoted 8 lines
Quoted 5 lines
Quoted 3 lines

c) Or change the low-level code to do blkio_group.want_stats_cpu=true, then test that at the top level after we've determined that blkio_group.stats_cpu is NULL.

Not following. Where's the "top level"?

Somewhere appropriate where we can use GFP_KERNEL. ie: the correct context for percpu_alloc().

There's no natural "top level" for block layer. It either has to hook off from userland access as you suggested above or we should explicitly defer to work item. That of course is possible but that is worse than making use of existing infrastructure to solve the problem. Note that explicitly deferring to wq is basically more specialized version of using wq backed mempool and would take more code.

Quoted 7 lines

Separately...

Mixing mempools and percpu_alloc() in the proposed fashion seems a pretty poor fit. mempools are for high-frequency low-level allocations which have key characteristics: there are typically a finite number of elements in flight and we *know* that elements are being freed in a timely manner.

mempool is a pool of memory allocations. Nothing more, nothing less.

Quoted 4 lines

This doesn't fit with percpu_alloc(), which is a very heavyweight operation requiring GFP_KERNEL and it doesn't fit with blkio_group_stats_cpu because blkio_group_stats_cpu does not have the "freed in a timely manner" behaviour.

And, yes, it is a different usage of the same mechanism. Nothing changes for the mechanism itself (other than the silly GFP_WAIT behavior which is buggy anyway).

Quoted 4 lines

To resolve these things you've added the workqueue to keep the pool populated, which turns percpu_mempool into a quite different concept which happens to borrow some mempool code (not necessarily a bad thing). This will result in some memory wastage, keeping that pool full.

The wq thing can be moved into block layer if that's the bothering part, but given this mode of usage would be the prevalent one for percpu mempool, I think it would be better to put it there for obvious reasons.

It's the same pool of allocations. If you don't have inter-item dependency and allocated items are guaranteed to be returned in finite amount of time, it guarantees allocation attempts would succeed in finite amount of time. If you put in items in a context and take it out in a different one, it serves as allocation buffer.

Quoted 5 lines

More significantly, it's pretty unreliable: if the allocations outpace the kernel thread's ability to refill the pool, all we can do is to wait for the kernel thread to do some work. But we're holding low-level locks while doing that wait, which will block the kernel thread. Deadlock.

Ummm... if you try to allocate with GFP_KERNEL from IO path, deadlock of course is possible. That's the *whole* reason why allocation buffering is used there. It's filled from GFP_KERNEL context and consumed from GFO_NOIO and as pointed out multiple times the allocaion there is infrequent and can be opportunistic. Sans the use of small buffering items, this isn't any different from deferring allocation to different context. There's no guarantee when that allocation would happen but in practice both will be reliable enough for the given use case.

I don't necessarily insist on using mempool here but all the given objections seem bogus to me. The amount of code added is minimal and straight-forward. It doesn't change what mempool is or what it does at all and the usage fits the problem to be solved. I can't really understand what the objection is about.

Thanks.

Signature · 1 line
tejun
maintainer
#23 lore raw
Quoted 9 lines · On Tue, 27 Dec 2011 10:34:02 -0800 Tejun Heo <[email protected]> wrote:
Quoted 7 lines

Separately...

Mixing mempools and percpu_alloc() in the proposed fashion seems a pretty poor fit. mempools are for high-frequency low-level allocations which have key characteristics: there are typically a finite number of elements in flight and we *know* that elements are being freed in a timely manner.

mempool is a pool of memory allocations. Nothing more, nothing less.

No, there is more. An important concept in mempool is that it is safe to indefinitely wait for items because it is guaranteed that the in-flight ones will be returned in a timely fashion.

Quoted 8 lines
Quoted 5 lines

More significantly, it's pretty unreliable: if the allocations outpace the kernel thread's ability to refill the pool, all we can do is to wait for the kernel thread to do some work. But we're holding low-level locks while doing that wait, which will block the kernel thread. Deadlock.

Ummm... if you try to allocate with GFP_KERNEL from IO path, deadlock of course is possible.

It is deadlockable when used with GFP_NOFS, or GFP_NOIO. Anything with __GFP_WAIT.

The only "safe" usage of the proposed interface is when the caller performs the per-cpu allocation with !__GFP_WAIT (ie: GFP_ATOMIC) and when the caller is prepared to repeatedly poll until the allocation succeeds.

That's a narrow and rare calling pattern which doesn't merit being formalised into a core kernel API. It is one which encourages poor code in callers, which should instead be reworked to use GFP_KERNEL, in which case the interface isn't needed.

It's also a dangerous API because people could call it with GFP_NOIO (for example) and risk deadlocks. Waiting for a kernel thread to perform a GFP_KERNEL allocation is equivalent to directly performing that allocation, with GFP_KERNEL. The only real effect of handing over to a kernel thread to do the work is to hide your bug from lockdep.

Quoted 8 lines

That's the *whole* reason why allocation
buffering is used there. It's filled from GFP_KERNEL context and consumed from GFO_NOIO and as pointed out multiple times the allocaion there is infrequent and can be opportunistic. Sans the use of small buffering items, this isn't any different from deferring allocation to different context. There's no guarantee when that allocation would happen but in practice both will be reliable enough for the given use case.

"reliable enough" is not the standard to which we aspire.

Look, the core problem here is that this block code is trying to allocate from an inappropriate context. Rather than hacking around adding stuff to make this work most-of-the-time, how about fixing the block code to perform the allocation from the correct context?

Quoted 5 lines

I don't necessarily insist on using mempool here but all the given objections seem bogus to me. The amount of code added is minimal and straight-forward. It doesn't change what mempool is or what it does at all and the usage fits the problem to be solved. I can't really understand what the objection is about.

It's adding complexity to core kernel. It's adding a weak and dangerous interface which will encourage poor code in callers.

And why are we doing all of this? So we can continue to use what is now poor code at one particular site in the block layer! If the block code wants to run alloc_percpu() (which requires GFP_KERNEL context) then it should be reworked to do so from GFP_KERNEL context. For that is the *best* solution, no?

maintainer
#32 lore raw
In reply to Vivek Goyal
Quoted 8 lines · On Fri, 23 Dec 2011 09:58:56 -0500 Vivek Goyal <[email protected]> wrote:
Quoted 2 lines

Why do the allocation during I/O? Can't it be done in the hotplug handler?

Even if we can do it in hotplug handler it will be very wasteful of memory. So if there are 100 IO cgroups in the system, upon every block device hotplug, we will allocate per cpu memory for all the 100 cgroups, irrespective of the fact whether they are doing IO to the device or not.

Quoted 4 lines

Now expand this to a system with 100 cgroups and 100 Luns. 10000 allocations for no reason. (Even if we do it for cgroups needing stats, does not help much). Current scheme allocates memory for the group only if a sepcific cgroup is doing IO to a specific block device.

umm, we've already declared that it is OK to completely waste this memory for the users (probably a majority) who will not be using these stats.

Also, has this stuff been tested at that scale? I fear to think what 10000 allocations will do to fragmetnation of the vmalloc() arena.

author maintainer
#24 lore raw
In reply to Andrew Morton

Hello, Andrew.

Quoted 9 lines · Andrew Morton
Quoted 8 lines

That's the *whole* reason why allocation
buffering is used there. It's filled from GFP_KERNEL context and consumed from GFO_NOIO and as pointed out multiple times the allocaion there is infrequent and can be opportunistic. Sans the use of small buffering items, this isn't any different from deferring allocation to different context. There's no guarantee when that allocation would happen but in practice both will be reliable enough for the given use case.

Quoted 6 lines

"reliable enough" is not the standard to which we aspire.

Look, the core problem here is that this block code is trying to allocate from an inappropriate context. Rather than hacking around adding stuff to make this work most-of-the-time, how about fixing the block code to perform the allocation from the correct context?

Yeah, sure, that would be nice. I'm just not convinced that would be possible in a way which would be in the end better than buffering memory allocations some way. For better or for worse, the whole blkcg / ioc / request_queue association mechanism is based on essentially opportunistic allocation on the expectation that the number of used combinations would be low and allocation frequency would be low too.

Quoted 6 lines
Quoted 5 lines

I don't necessarily insist on using mempool here but all the given objections seem bogus to me. The amount of code added is minimal and straight-forward. It doesn't change what mempool is or what it does at all and the usage fits the problem to be solved. I can't really understand what the objection is about.

Quoted 8 lines

It's adding complexity to core kernel. It's adding a weak and dangerous interface which will encourage poor code in callers.

And why are we doing all of this? So we can continue to use what is now poor code at one particular site in the block layer! If the block code wants to run alloc_percpu() (which requires GFP_KERNEL context) then it should be reworked to do so from GFP_KERNEL context. For that is the *best* solution, no?

Ummm... I'm not arguing this is the best solution in the world.

I'm not convinced trying to put this into GFP_KERNEL context would work. Short of that, the next best thing would be making percpu allocator useable from memory reclaim path, right? But that would involved a lot more churn and complexity without much added benefit, given that this type of use cases aren't expected to be common - and I'm fairly sure it isn't given track record of past few years.

IMHO, core code is there to help its users. In this case, if we choose to buffer allocation somehow, we sure can add that to block layer, but that would be pretty silly thing to do. It's not keeping anything simple. It's just hiding things.

Anyways, let's stop this abstract discussion. I think the crux of disagreement is about whether this can be moved into GFP_KERNEL context or not. Let's continue with Vivek's subthread.

Thanks.

Signature · 1 line
tejun
maintainer
#25 lore raw
Quoted 3 lines · On Tue, 27 Dec 2011 13:44:21 -0800 Tejun Heo <[email protected]> wrote:

I'm not convinced trying to put this into GFP_KERNEL context would work. Short of that, the next best thing would be making percpu allocator useable from memory reclaim path, right?

Well.. All allocations which are weaker than GFP_KERNEL are to be discouraged. That being said...

Quoted 4 lines

But that would
involved a lot more churn and complexity without much added benefit, given that this type of use cases aren't expected to be common - and I'm fairly sure it isn't given track record of past few years.

I don't think it would be too hard to add an alloc_percpu_gfp(). Add the gfp_t to a small number of functions (two or three?) then change pcpu_mem_zalloc() to always use kzalloc() if (flags & GFP_KERNEL != GFP_KERNEL). And that's it?

But the question is: is this a *good* thing to do? It would be nice if kernel developers understood that GFP_KERNEL is strongly preferred and that they should put in effort to use it. But there's a strong tendency for people to get themselves into a sticky corner then take the easy way out, resulting in less robust code. Maybe calling the function alloc_percpu_i_really_suck() would convey the hint.

author maintainer
#33 lore raw
In reply to Andrew Morton

Hello,

Quoted 3 lines · Andrew Morton

umm, we've already declared that it is OK to completely waste this memory for the users (probably a majority) who will not be using these stats.

We're talking about combinatorial combinations where only small subset is usually expected to be used and, in addition to the absolute usage, there's big advantage in showing behavior which users would expect. If 1000 cgroups are doing IOs to 1000 devices, it's expected to consume some amount of resource.

The whole io_context / blk_cgroup - request_queue association mechanism is based on opportunistic allocation. It might not be the prettiest thing in the world but given the circumstances IMHO the approach fits the constraints defined by the problem.

Given the restricted nature of percpu allocation, it would be nice to punt it to GFP_KERNEL context *somewhere* and for block layer that somewhere probably can only be userland access. I just don't see that fitting better here. The suggested alternative seems much nastier with userland visible side effects and possibility for combinatorial increase in memory usage for something as benign as single cat of stat files.

Also, such erratic userland visible behavior is deviation from the current one and at the same time we would be bound to the idiosyncracies later when we can improve the implementation.

I can't see how that can be a better tradeoff. It shifts the problem to even more cumbersome corner.

Quoted 2 lines

Also, has this stuff been tested at that scale? I fear to think what 10000 allocations will do to fragmetnation of the vmalloc() arena.

Percpu allocator doesn't use vmalloc directly. It maps address ranges (which is at least 32k and usually much larger) from vmalloc space and allocate it using simplistic extent allocator.

Thanks.

Signature · 1 line
tejun
maintainer
#34 lore raw
Quoted 7 lines · On Tue, 27 Dec 2011 14:07:53 -0800 Tejun Heo <[email protected]> wrote:

Hello,

Quoted 3 lines · Andrew Morton

umm, we've already declared that it is OK to completely waste this memory for the users (probably a majority) who will not be using these stats.

Quoted 5 lines

We're talking about combinatorial combinations where only small subset is usually expected to be used and, in addition to the absolute usage, there's big advantage in showing behavior which users would expect. If 1000 cgroups are doing IOs to 1000 devices, it's expected to consume some amount of resource.

<autorepeat>For those users who don't want the stats, stats shouldn't consume any resources at all.

And I bet that the majority of the minority who want stats simply want to know "how much IO is this cgroup doing", and don't need per-cgroup, per-device accounting.

And it could be that the minority of the minority who want per-device, per-cgroup stats only want those for a minority of the time.

IOW, what happens if we give 'em atomic_add() and be done with it?

author maintainer
#26 lore raw
In reply to Andrew Morton

Hello, Andrew.

Quoted 9 lines · Andrew Morton
Quoted 4 lines

But that would
involved a lot more churn and complexity without much added benefit, given that this type of use cases aren't expected to be common - and I'm fairly sure it isn't given track record of past few years.

I don't think it would be too hard to add an alloc_percpu_gfp(). Add the gfp_t to a small number of functions (two or three?) then change pcpu_mem_zalloc() to always use kzalloc() if (flags & GFP_KERNEL != GFP_KERNEL). And that's it?

Hmmm... What do you mean "always use kzalloc()"? Percpu memory can't be served by kzalloc(). They need to be congruent.

Currently, percpu allocation happens in two stages. The first stage is locating congruent address areas in vmalloc space (so that static percpu offsets among different CPUs can be maintained for dynamic percpu areas). The second stage is actually allocating pages and populating those areas. Because percpu memory is expensive, the allocator keeps both steps on demand. When it runs out of address space, it gets some and the addresses are filled only when the memory areas are actually handed out.

Unfortunately, both steps involve vmalloc machinery and GFP_KERNEL assumption reaches into arch specific code for page table allocation. So, making all those steps reclaim path friendly would be quite a churn.

*If* we're gonna solve this at the allocator level, we'll probably end up with front buffer in percpu allocator, which buffers populated percpu areas to give out for reclaim path allocations, which is doable, would involve a lot more complexity and would probably need to keep more percpu memory reserved to stay generic.

Quoted 6 lines

But the question is: is this a *good* thing to do? It would be nice if kernel developers understood that GFP_KERNEL is strongly preferred and that they should put in effort to use it. But there's a strong tendency for people to get themselves into a sticky corner then take the easy way out, resulting in less robust code. Maybe calling the function alloc_percpu_i_really_suck() would convey the hint.

I fully agree and have been pushing back pretty hard against people trying to allocate percpu memory from !GFP_KERNEL context and I want to keep it that way. But, to me, this one seems like a valid use case. If we want to track dynamic associations in IO path, short of allocating for all combinatorial combinations, we can't avoid performing NOIO allocations. Of course, the code path should be careful so that it's not too demanding on the allocator and must be able to degrade operation gracefully on allocation failures. It's a special case but a valid one at that.

Thanks.

Signature · 1 line
tejun
author maintainer
#35 lore raw
In reply to Andrew Morton

Hello, Andrew.

Quoted 2 lines · Andrew Morton

<autorepeat>For those users who don't want the stats, stats shouldn't consume any resources at all.

Hmmm.... For common use cases - a few cgroups doing IOs to most likely single physical device and maybe a couple virtual ones, I don't think this would show up anywhere both in terms of memory and process overhead. While avoding it would be nice, I don't think that should be the focus of optimization or design decisions.

Quoted 8 lines

And I bet that the majority of the minority who want stats simply want to know "how much IO is this cgroup doing", and don't need per-cgroup, per-device accounting.

And it could be that the minority of the minority who want per-device, per-cgroup stats only want those for a minority of the time.

IOW, what happens if we give 'em atomic_add() and be done with it?

I really don't know. That surely is an enticing idea tho. Jens, Vivek, can you guys chime in? Is gutting out (or drastically simplifying) cgroup-dev stats an option? Are there users who are actually interested in this stuff?

Thanks.

Signature · 1 line
tejun
#42 lore raw
In reply to Tejun Heo
Quoted 15 lines · On Tue, 27 Dec 2011 09:52:49 -0800 Tejun Heo <[email protected]> wrote:

Hello, KAMEZAWA.

Quoted 12 lines · KAMEZAWA Hiroyuki

From 433b56fd5644d4b1e695bc16bbf8dd78842999fd Mon Sep 17 00:00:00 2001
From: KAMEZAWA Hiroyuki <[email protected]>
Date: Mon, 26 Dec 2011 15:06:21 +0900
Subject: [PATCH] percpu_counter: add lazy init

percpu_counter calls alloc_percpu(). This means percpu_counter_init() assumes GFP_KERNEL context. This may call vmalloc() in percpu_counter allocation and will have locks.

If a caller doesn't want to assume GFP_KERNEL, we need some tricks. This patch adds percpu_counter_init_lazy().

Quoted 9 lines
Quoted 4 lines

At lazy allocation, the function leaves fbc->counters as NULL and init fbc->counters by workqueue. This work item handling is done by fbc->list, so, the struct size of 'fbc' will not increase if a user configs CONFIG_HOTPLUG_CPU.

This is essentially more specialized form of the mempool approach. It doesn't seem any simpler to me while being less generic. I don't see what the upside would be.

Hm, but this never causes -ENOMEM error, at all.

Thanks,
-Kame

author maintainer
#43 lore raw

Hello,

Quoted 5 lines · KAMEZAWA Hiroyuki
Quoted 3 lines

This is essentially more specialized form of the mempool approach. It doesn't seem any simpler to me while being less generic. I don't see what the upside would be.

Hm, but this never causes -ENOMEM error, at all.

Ooh, I missed the part it falls back to the global counter if percpu counters aren't allocated yet. Yeah, this is an interesting approach. I'll think more about it.

Thanks.

Signature · 1 line
tejun
author maintainer
#44 lore raw
Quoted 7 lines · Tejun Heo

Hello,

Quoted 4 lines · KAMEZAWA Hiroyuki
Quoted 3 lines

This is essentially more specialized form of the mempool approach. It doesn't seem any simpler to me while being less generic. I don't see what the upside would be.

Quoted 5 lines
Quoted 1 line

Hm, but this never causes -ENOMEM error, at all.

Ooh, I missed the part it falls back to the global counter if percpu counters aren't allocated yet. Yeah, this is an interesting approach. I'll think more about it.

I've been staring at the blkcg stats code and commit logs and am wondering whether we can just scrap percpu counters there. It seems the reason why it was introduced in the first place is to avoid stats->lock, which BTW is extremely heavy handed for gathering stats, overhead in fast paths and I think there can be easier ways to avoid stats->lock.

Thanks.

Signature · 1 line
tejun
#36 lore raw
In reply to Tejun Heo
Quoted 19 lines · Tejun Heo

Hello, Andrew.

Quoted 2 lines · Andrew Morton

<autorepeat>For those users who don't want the stats, stats shouldn't consume any resources at all.

Hmmm.... For common use cases - a few cgroups doing IOs to most likely single physical device and maybe a couple virtual ones, I don't think this would show up anywhere both in terms of memory and process overhead. While avoding it would be nice, I don't think that should be the focus of optimization or design decisions.

Quoted 7 lines

And I bet that the majority of the minority who want stats simply want to know "how much IO is this cgroup doing", and don't need per-cgroup, per-device accounting.

And it could be that the minority of the minority who want per-device, per-cgroup stats only want those for a minority of the time.

Quoted 6 lines
Quoted 1 line

IOW, what happens if we give 'em atomic_add() and be done with it?

I really don't know. That surely is an enticing idea tho. Jens, Vivek, can you guys chime in? Is gutting out (or drastically simplifying) cgroup-dev stats an option? Are there users who are actually interested in this stuff?

Ok, I am back after a break of 3 weeks. So time to restart the discussion.

So we seem to be talking of two things.

- Use atomic_add() for stats.
- Do not keep stats per cgroup/per device instead just keep gloabl per cgroup stat.

For the first point, is atomic operation really that cheap then taking spin lock. The whole point of introducing per cpu data structure was to make fast path lockless. My understanding is that atomic operation on IO submission path is expensive so to me it really does not solve the overhead problem?

Initially google folks (Divyesh Shah) introduced additional files to display additional stats which per per cgroup per device. I am assuming they are making use of it. To me knowing how IO is distributed to different devies from a cgroup is a good thing to know.

Keeping the stats per device also helps that aggregation of stats happens from process context and we reduce the contention on stat update from various devices. So to me it is good thing to keep stats per device and then display these as user find them useful (Either per cgroup or per cgroup per device).

So to me none of the above options are really solving the issue of reducing the cost/overhead of atomic operation in IO submission path. Please correct me if missed something here.

Thanks
Vivek

#45 lore raw
In reply to Tejun Heo
Quoted 14 lines · Tejun Heo
Quoted 7 lines · Tejun Heo

Hello,

Quoted 4 lines · KAMEZAWA Hiroyuki
Quoted 3 lines

This is essentially more specialized form of the mempool approach. It doesn't seem any simpler to me while being less generic. I don't see what the upside would be.

Quoted 5 lines
Quoted 1 line

Hm, but this never causes -ENOMEM error, at all.

Ooh, I missed the part it falls back to the global counter if percpu counters aren't allocated yet. Yeah, this is an interesting approach. I'll think more about it.

Quoted 6 lines

I've been staring at the blkcg stats code and commit logs and am wondering whether we can just scrap percpu counters there. It seems the reason why it was introduced in the first place is to avoid stats->lock, which BTW is extremely heavy handed for gathering stats, overhead in fast paths and I think there can be easier ways to avoid stats->lock.

Tejun,

If you get rid of stats->lock, and also don't use per cpu data strucutres how would we avoid races in case of concurrent update (IO submission?).

Thanks
Vivek

author maintainer
#46 lore raw
In reply to Tejun Heo

Hello, guys.

Quoted 14 lines · Tejun Heo
Quoted 7 lines · Tejun Heo

Hello,

Quoted 4 lines · KAMEZAWA Hiroyuki
Quoted 3 lines

This is essentially more specialized form of the mempool approach. It doesn't seem any simpler to me while being less generic. I don't see what the upside would be.

Quoted 5 lines
Quoted 1 line

Hm, but this never causes -ENOMEM error, at all.

Ooh, I missed the part it falls back to the global counter if percpu counters aren't allocated yet. Yeah, this is an interesting approach. I'll think more about it.

Quoted 6 lines

I've been staring at the blkcg stats code and commit logs and am wondering whether we can just scrap percpu counters there. It seems the reason why it was introduced in the first place is to avoid stats->lock, which BTW is extremely heavy handed for gathering stats, overhead in fast paths and I think there can be easier ways to avoid stats->lock.

I could remove stats_lock without much trouble but couldn't get blk-throtl fast path stat working. :(

I think I'll try to get KAMEZAWA's percpu counter working. Any objections?

Thanks.

Signature · 1 line
tejun
#47 lore raw
Quoted 24 lines · Tejun Heo

Hello, guys.

Quoted 14 lines · Tejun Heo
Quoted 7 lines · Tejun Heo

Hello,

Quoted 4 lines · KAMEZAWA Hiroyuki
Quoted 3 lines

This is essentially more specialized form of the mempool approach. It doesn't seem any simpler to me while being less generic. I don't see what the upside would be.

Quoted 5 lines
Quoted 1 line

Hm, but this never causes -ENOMEM error, at all.

Ooh, I missed the part it falls back to the global counter if percpu counters aren't allocated yet. Yeah, this is an interesting approach. I'll think more about it.

Quoted 6 lines

I've been staring at the blkcg stats code and commit logs and am wondering whether we can just scrap percpu counters there. It seems the reason why it was introduced in the first place is to avoid stats->lock, which BTW is extremely heavy handed for gathering stats, overhead in fast paths and I think there can be easier ways to avoid stats->lock.

Quoted 5 lines

I could remove stats_lock without much trouble but couldn't get blk-throtl fast path stat working. :(

I think I'll try to get KAMEZAWA's percpu counter working. Any objections?

So IIUC, that patch essentially does the same thing which my patch was doing for blk-throttle.c and cfq-iosched.c. That is do the allocation of counters from worker thread and till allocation does not happen we do not record the stats.

The only difference is that by putting this logic in per cpu counters, we make it somewhat generic so that other users who can't do GFP_KERNEL allocation of per cpu data, can use it. I can live with that.

Ideally I would have thought that if passing gfp_flag to alloc_percpu() is a need, then we need to fix that instead of trying to create generic infrastructure around that. For the code which is broken currently like blkcg, we can fix them by doing allocation from worker context so that this workaround is limited to a specific piece of code and not generic enough that other subsystems latch on to it.

But if you don't think that fixing alloc_percpu() is possible in long term and users should use per cpu counters for any kind of non GFP_KERNEL needs, then it probably is find to continue to develop this patch.

Personally, I liked my old patch of restricting worker thread allocation logic to blk-throttle.c and cfq-iosched.c. If you don't have objection to that approach, I can brush it up, fix a pending issue and post it?

Thanks
Vivek

author maintainer
#48 lore raw

Hello, Vivek.

Quoted 3 lines · Vivek Goyal

The only difference is that by putting this logic in per cpu counters, we make it somewhat generic so that other users who can't do GFP_KERNEL allocation of per cpu data, can use it. I can live with that.

Also, it has fallback mechanism while percpu data isn't there, so the counts are guaranteed to be right. Probably doesn't matter all that much for blkcg stats.

Quoted 3 lines

But if you don't think that fixing alloc_percpu() is possible in long term and users should use per cpu counters for any kind of non GFP_KERNEL needs, then it probably is find to continue to develop this patch.

Updating alloc_percpu() to support full @gfp_mask is rather complex and likely to generate a lot of churn and fragility.

Quoted 3 lines

Personally, I liked my old patch of restricting worker thread allocation logic to blk-throttle.c and cfq-iosched.c. If you don't have objection to that approach, I can brush it up, fix a pending issue and post it?

I don't know. If we're gonna do that, I think doing that in mempool is better. Andrew, are you still dead against using mempool for percpu pooling? That logic is going somewhere and it probably is better to put it somewhere common rather than shoving it in block cgroup code.

Thanks.

Signature · 1 line
tejun
#49 lore raw
Quoted 10 lines · Tejun Heo

Hello, Vivek.

Quoted 3 lines · Vivek Goyal

The only difference is that by putting this logic in per cpu counters, we make it somewhat generic so that other users who can't do GFP_KERNEL allocation of per cpu data, can use it. I can live with that.

Also, it has fallback mechanism while percpu data isn't there, so the counts are guaranteed to be right. Probably doesn't matter all that much for blkcg stats.

Ok, I had missed that part. Nice.

I have no objections to making this lazy allocation in per cpu counter idea work and migrate blkcg per cpu stats to use per cpu counters. If this patchset is not too intrusive, it might even be backportable to stable kernels.

Andrew does not seem to like mempool idea, so instead of not making any progress, it is better to go with this idea. We need to fix this issue. More poeple might run into this.

Thanks
Vivek