[PATCH 00/10] workqueue: restructure flush_workqueue() and start all flusher at the same time

[PATCH 00/10] workqueue: restructure flush_workqueue() and start all flusher at the same time

[Lai Jiangshan]

The core patch is patch6, it makes all flusher can start and the same time
and allow us do more cleanup.

Only patch1 and patch6 change the behavior of the code.
All other patches do not change any behavior.

Lai Jiangshan (10):
  workqueue: always pass flush responsibility to next
  workqueue: remove unneeded check
  workqueue: remove while(true)
  workqueue: use nr_cwqs_to_flush array
  workqueue: add wq_dec_flusher_ref()
  workqueue: start all flusher at the same time
  workqueue: simplify flush_workqueue_prep_cwqs()
  workqueue: assign overflowed flushers's flush color when queued
  workqueue: remove flusher_overflow
  workqueue: remove wq->flush_color

 kernel/workqueue.c |  243 +++++++++++++++++++--------------------------------
 1 files changed, 91 insertions(+), 152 deletions(-)

-- 
1.7.4.4

[PATCH 01/10] workqueue: always pass flush responsibility to next

[Lai Jiangshan]

depriving the responsibility make the code complex, we pass it to the next
unconditionally.

After this change, we don't need to go back to repeat cascading, so we use
"break" to exit the loop.

The loop will be remove in later patch.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/workqueue.c |   11 ++---------
 1 files changed, 2 insertions(+), 9 deletions(-)

diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index a59171a..360b7e2 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -2740,15 +2740,8 @@ void flush_workqueue(struct workqueue_struct *wq)
 
 		list_del_init(&next->list);
 		wq->first_flusher = next;
-
-		if (flush_workqueue_prep_cwqs(wq, wq->flush_color, -1))
-			break;
-
-		/*
-		 * Meh... this color is already done, clear first
-		 * flusher and repeat cascading.
-		 */
-		wq->first_flusher = NULL;
+		flush_workqueue_prep_cwqs(wq, wq->flush_color, -1);
+		break;
 	}
 
 out_unlock:
-- 
1.7.4.4

[PATCH 02/10] workqueue: remove unneeded check

[Lai Jiangshan]

Since we always pass flush responsibility to next, we will not deprive it,
now the ->first_flusher can only be changed by the first_flusher, no one
can change it, no race as 4ce48b37 said.

Remove the check introduced by 4ce48b37, use BUG_ON() instead.

Also move "wq->first_flusher = NULL;" later.

This patch doesn't make any functional difference.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/workqueue.c |    8 ++------
 1 files changed, 2 insertions(+), 6 deletions(-)

diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index 360b7e2..acd9e2f 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -2682,12 +2682,7 @@ void flush_workqueue(struct workqueue_struct *wq)
 
 	mutex_lock(&wq->flush_mutex);
 
-	/* we might have raced, check again with mutex held */
-	if (wq->first_flusher != &this_flusher)
-		goto out_unlock;
-
-	wq->first_flusher = NULL;
-
+	BUG_ON(wq->first_flusher != &this_flusher);
 	BUG_ON(!list_empty(&this_flusher.list));
 	BUG_ON(wq->flush_color != this_flusher.flush_color);
 
@@ -2728,6 +2723,7 @@ void flush_workqueue(struct workqueue_struct *wq)
 
 		if (list_empty(&wq->flusher_queue)) {
 			BUG_ON(wq->flush_color != wq->work_color);
+			wq->first_flusher = NULL;
 			break;
 		}
 
-- 
1.7.4.4

[PATCH 03/10] workqueue: remove while(true)

[Lai Jiangshan]

The loop count is always=1, remove the "while(true)" and fix the indent.

This patch doesn't make any functional difference.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/workqueue.c |   86 +++++++++++++++++++++++++---------------------------
 1 files changed, 41 insertions(+), 45 deletions(-)

diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index acd9e2f..5439fb6 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -2617,6 +2617,7 @@ void flush_workqueue(struct workqueue_struct *wq)
 		.flush_color = -1,
 		.done = COMPLETION_INITIALIZER_ONSTACK(this_flusher.done),
 	};
+	struct wq_flusher *next, *tmp;
 	int next_color;
 
 	lock_map_acquire(&wq->lockdep_map);
@@ -2686,59 +2687,54 @@ void flush_workqueue(struct workqueue_struct *wq)
 	BUG_ON(!list_empty(&this_flusher.list));
 	BUG_ON(wq->flush_color != this_flusher.flush_color);
 
-	while (true) {
-		struct wq_flusher *next, *tmp;
-
-		/* complete all the flushers sharing the current flush color */
-		list_for_each_entry_safe(next, tmp, &wq->flusher_queue, list) {
-			if (next->flush_color != wq->flush_color)
-				break;
-			list_del_init(&next->list);
-			complete(&next->done);
-		}
+	/* complete all the flushers sharing the current flush color */
+	list_for_each_entry_safe(next, tmp, &wq->flusher_queue, list) {
+		if (next->flush_color != wq->flush_color)
+			break;
+		list_del_init(&next->list);
+		complete(&next->done);
+	}
 
-		BUG_ON(!list_empty(&wq->flusher_overflow) &&
-		       wq->flush_color != work_next_color(wq->work_color));
+	BUG_ON(!list_empty(&wq->flusher_overflow) &&
+	       wq->flush_color != work_next_color(wq->work_color));
 
-		/* this flush_color is finished, advance by one */
-		wq->flush_color = work_next_color(wq->flush_color);
+	/* this flush_color is finished, advance by one */
+	wq->flush_color = work_next_color(wq->flush_color);
 
-		/* one color has been freed, handle overflow queue */
-		if (!list_empty(&wq->flusher_overflow)) {
-			/*
-			 * Assign the same color to all overflowed
-			 * flushers, advance work_color and append to
-			 * flusher_queue.  This is the start-to-wait
-			 * phase for these overflowed flushers.
-			 */
-			list_for_each_entry(tmp, &wq->flusher_overflow, list)
-				tmp->flush_color = wq->work_color;
+	/* one color has been freed, handle overflow queue */
+	if (!list_empty(&wq->flusher_overflow)) {
+		/*
+		 * Assign the same color to all overflowed
+		 * flushers, advance work_color and append to
+		 * flusher_queue.  This is the start-to-wait
+		 * phase for these overflowed flushers.
+		 */
+		list_for_each_entry(tmp, &wq->flusher_overflow, list)
+			tmp->flush_color = wq->work_color;
 
-			wq->work_color = work_next_color(wq->work_color);
+		wq->work_color = work_next_color(wq->work_color);
 
-			list_splice_tail_init(&wq->flusher_overflow,
-					      &wq->flusher_queue);
-			flush_workqueue_prep_cwqs(wq, -1, wq->work_color);
-		}
+		list_splice_tail_init(&wq->flusher_overflow,
+				      &wq->flusher_queue);
+		flush_workqueue_prep_cwqs(wq, -1, wq->work_color);
+	}
 
-		if (list_empty(&wq->flusher_queue)) {
-			BUG_ON(wq->flush_color != wq->work_color);
-			wq->first_flusher = NULL;
-			break;
-		}
+	if (list_empty(&wq->flusher_queue)) {
+		BUG_ON(wq->flush_color != wq->work_color);
+		wq->first_flusher = NULL;
+		goto out_unlock;
+	}
 
-		/*
-		 * Need to flush more colors.  Make the next flusher
-		 * the new first flusher and arm cwqs.
-		 */
-		BUG_ON(wq->flush_color == wq->work_color);
-		BUG_ON(wq->flush_color != next->flush_color);
+	/*
+	 * Need to flush more colors.  Make the next flusher
+	 * the new first flusher and arm cwqs.
+	 */
+	BUG_ON(wq->flush_color == wq->work_color);
+	BUG_ON(wq->flush_color != next->flush_color);
 
-		list_del_init(&next->list);
-		wq->first_flusher = next;
-		flush_workqueue_prep_cwqs(wq, wq->flush_color, -1);
-		break;
-	}
+	list_del_init(&next->list);
+	wq->first_flusher = next;
+	flush_workqueue_prep_cwqs(wq, wq->flush_color, -1);
 
 out_unlock:
 	mutex_unlock(&wq->flush_mutex);
-- 
1.7.4.4

[PATCH 04/10] workqueue: use nr_cwqs_to_flush array

[Lai Jiangshan]

Each color uses its own nr_cwqs_to_flush[color].

This patch doesn't make any functional difference.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/workqueue.c |   21 ++++++++++++---------
 1 files changed, 12 insertions(+), 9 deletions(-)

diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index 5439fb6..861b4c7 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -250,7 +250,7 @@ struct workqueue_struct {
 	struct mutex		flush_mutex;	/* protects wq flushing */
 	int			work_color;	/* F: current work color */
 	int			flush_color;	/* F: current flush color */
-	atomic_t		nr_cwqs_to_flush; /* flush in progress */
+	atomic_t		nr_cwqs_to_flush[WORK_NR_COLORS];
 	struct wq_flusher	*first_flusher;	/* F: first flusher */
 	struct list_head	flusher_queue;	/* F: flush waiters */
 	struct list_head	flusher_overflow; /* F: flush overflow list */
@@ -1036,7 +1036,7 @@ static void cwq_dec_nr_in_flight(struct cpu_workqueue_struct *cwq, int color)
 	 * If this was the last cwq, wake up the first flusher.  It
 	 * will handle the rest.
 	 */
-	if (atomic_dec_and_test(&cwq->wq->nr_cwqs_to_flush))
+	if (atomic_dec_and_test(&cwq->wq->nr_cwqs_to_flush[color]))
 		complete(&cwq->wq->first_flusher->done);
 }
 
@@ -2540,8 +2540,8 @@ static void insert_wq_barrier(struct cpu_workqueue_struct *cwq,
  * -1.  If no cwq has in-flight commands at the specified color, all
  * cwq->flush_color's stay at -1 and %false is returned.  If any cwq
  * has in flight commands, its cwq->flush_color is set to
- * @flush_color, @wq->nr_cwqs_to_flush is updated accordingly, cwq
- * wakeup logic is armed and %true is returned.
+ * @flush_color, @wq->nr_cwqs_to_flush[flush_color] is updated accordingly,
+ * cwq wakeup logic is armed and %true is returned.
  *
  * The caller should have initialized @wq->first_flusher prior to
  * calling this function with non-negative @flush_color.  If
@@ -2566,8 +2566,8 @@ static bool flush_workqueue_prep_cwqs(struct workqueue_struct *wq,
 	unsigned int cpu;
 
 	if (flush_color >= 0) {
-		BUG_ON(atomic_read(&wq->nr_cwqs_to_flush));
-		atomic_set(&wq->nr_cwqs_to_flush, 1);
+		BUG_ON(atomic_read(&wq->nr_cwqs_to_flush[flush_color]));
+		atomic_set(&wq->nr_cwqs_to_flush[flush_color], 1);
 	}
 
 	for_each_cwq_cpu(cpu, wq) {
@@ -2581,7 +2581,7 @@ static bool flush_workqueue_prep_cwqs(struct workqueue_struct *wq,
 
 			if (cwq->nr_in_flight[flush_color]) {
 				cwq->flush_color = flush_color;
-				atomic_inc(&wq->nr_cwqs_to_flush);
+				atomic_inc(&wq->nr_cwqs_to_flush[flush_color]);
 				wait = true;
 			}
 		}
@@ -2594,7 +2594,8 @@ static bool flush_workqueue_prep_cwqs(struct workqueue_struct *wq,
 		spin_unlock_irq(&gcwq->lock);
 	}
 
-	if (flush_color >= 0 && atomic_dec_and_test(&wq->nr_cwqs_to_flush))
+	if (flush_color >= 0 &&
+	    atomic_dec_and_test(&wq->nr_cwqs_to_flush[flush_color]))
 		complete(&wq->first_flusher->done);
 
 	return wait;
@@ -3211,6 +3212,7 @@ struct workqueue_struct *__alloc_workqueue_key(const char *fmt,
 	struct workqueue_struct *wq;
 	unsigned int cpu;
 	size_t namelen;
+	int color;
 
 	/* determine namelen, allocate wq and format name */
 	va_start(args, lock_name);
@@ -3239,7 +3241,8 @@ struct workqueue_struct *__alloc_workqueue_key(const char *fmt,
 	wq->flags = flags;
 	wq->saved_max_active = max_active;
 	mutex_init(&wq->flush_mutex);
-	atomic_set(&wq->nr_cwqs_to_flush, 0);
+	for (color = 0; color < WORK_NR_COLORS; color++)
+		atomic_set(&wq->nr_cwqs_to_flush[color], 0);
 	INIT_LIST_HEAD(&wq->flusher_queue);
 	INIT_LIST_HEAD(&wq->flusher_overflow);
 
-- 
1.7.4.4

[PATCH 05/10] workqueue: add wq_dec_flusher_ref()

[Lai Jiangshan]

it is a helper to relase reference.

This patch doesn't make any functional difference.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/workqueue.c |   22 +++++++++++++---------
 1 files changed, 13 insertions(+), 9 deletions(-)

diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index 861b4c7..e5ba08c 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -995,6 +995,16 @@ static void cwq_activate_first_delayed(struct cpu_workqueue_struct *cwq)
 	cwq_activate_delayed_work(work);
 }
 
+static void wq_dec_flusher_ref(struct workqueue_struct *wq, int color)
+{
+	/*
+	 * If this was the last reference, wake up the first flusher.
+	 * It will handle the rest.
+	 */
+	if (atomic_dec_and_test(&wq->nr_cwqs_to_flush[color]))
+		complete(&wq->first_flusher->done);
+}
+
 /**
  * cwq_dec_nr_in_flight - decrement cwq's nr_in_flight
  * @cwq: cwq of interest
@@ -1032,12 +1042,7 @@ static void cwq_dec_nr_in_flight(struct cpu_workqueue_struct *cwq, int color)
 	/* this cwq is done, clear flush_color */
 	cwq->flush_color = -1;
 
-	/*
-	 * If this was the last cwq, wake up the first flusher.  It
-	 * will handle the rest.
-	 */
-	if (atomic_dec_and_test(&cwq->wq->nr_cwqs_to_flush[color]))
-		complete(&cwq->wq->first_flusher->done);
+	wq_dec_flusher_ref(cwq->wq, color);
 }
 
 /**
@@ -2594,9 +2599,8 @@ static bool flush_workqueue_prep_cwqs(struct workqueue_struct *wq,
 		spin_unlock_irq(&gcwq->lock);
 	}
 
-	if (flush_color >= 0 &&
-	    atomic_dec_and_test(&wq->nr_cwqs_to_flush[flush_color]))
-		complete(&wq->first_flusher->done);
+	if (flush_color >= 0)
+		wq_dec_flusher_ref(wq, flush_color);
 
 	return wait;
 }
-- 
1.7.4.4

[PATCH 06/10] workqueue: start all flusher at the same time

[Lai Jiangshan]

Start all flusher at the same time(except the overflowed flushers).

Since we have nr_cwqs_to_flush array for each color, any flush
color can start the same time, every color don't interfere
each other. The progress of flushing for any color is the same
as the old code.

A little different is that: the later color can't finished
until the previous color finished. So the top flusher of
previous color always hold a reference of the later color.
These is done by flush_workqueue_prep_cwqs() get a ref of
the just starting flush color, and it does not release it,
this ref's owner is assigned to the first flusher.
(so wq_dec_flusher_ref() is removed out from flush_workqueue_prep_cwqs()).

When the first flusher finished its flushing, it will release the ref
of the next color, and then the next color can finish.

All flush color can start and the same time, cwq_dec_nr_in_flight() must
decrease ref of any color, so cwq_dec_nr_in_flight() can't use cwq->flush_color,
it must use "cwq->work_color == color" to detect the @color is started to flush.
cwq->work_color is not used any more, remove it.

For any flush color, flush_workqueue_prep_cwqs() is called only one time.
(old code may call twice) it saves a big loop(when we have many CPUs)
and avoid to touch all gcwq again.

Wake-up-and-cascade phase become simpler and return quickly.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/workqueue.c |   46 ++++++++++++++++++----------------------------
 1 files changed, 18 insertions(+), 28 deletions(-)

diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index e5ba08c..803a22c 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -196,7 +196,6 @@ struct cpu_workqueue_struct {
 	struct worker_pool	*pool;		/* I: the associated pool */
 	struct workqueue_struct *wq;		/* I: the owning workqueue */
 	int			work_color;	/* L: current color */
-	int			flush_color;	/* L: flushing color */
 	int			nr_in_flight[WORK_NR_COLORS];
 						/* L: nr of in_flight works */
 	int			nr_active;	/* L: nr of active works */
@@ -1031,17 +1030,15 @@ static void cwq_dec_nr_in_flight(struct cpu_workqueue_struct *cwq, int color)
 			cwq_activate_first_delayed(cwq);
 	}
 
-	/* is flush in progress and are we at the flushing tip? */
-	if (likely(cwq->flush_color != color))
+	/* is flush in progress? */
+	if (likely(cwq->work_color == color))
 		return;
 
 	/* are there still in-flight works? */
 	if (cwq->nr_in_flight[color])
 		return;
 
-	/* this cwq is done, clear flush_color */
-	cwq->flush_color = -1;
-
+	/* this cwq is done, release the flusher ref of the color */
 	wq_dec_flusher_ref(cwq->wq, color);
 }
 
@@ -2541,13 +2538,6 @@ static void insert_wq_barrier(struct cpu_workqueue_struct *cwq,
  *
  * Prepare cwqs for workqueue flushing.
  *
- * If @flush_color is non-negative, flush_color on all cwqs should be
- * -1.  If no cwq has in-flight commands at the specified color, all
- * cwq->flush_color's stay at -1 and %false is returned.  If any cwq
- * has in flight commands, its cwq->flush_color is set to
- * @flush_color, @wq->nr_cwqs_to_flush[flush_color] is updated accordingly,
- * cwq wakeup logic is armed and %true is returned.
- *
  * The caller should have initialized @wq->first_flusher prior to
  * calling this function with non-negative @flush_color.  If
  * @flush_color is negative, no flush color update is done and %false
@@ -2572,6 +2562,7 @@ static bool flush_workqueue_prep_cwqs(struct workqueue_struct *wq,
 
 	if (flush_color >= 0) {
 		BUG_ON(atomic_read(&wq->nr_cwqs_to_flush[flush_color]));
+		/* this ref is held by first flusher */
 		atomic_set(&wq->nr_cwqs_to_flush[flush_color], 1);
 	}
 
@@ -2582,10 +2573,7 @@ static bool flush_workqueue_prep_cwqs(struct workqueue_struct *wq,
 		spin_lock_irq(&gcwq->lock);
 
 		if (flush_color >= 0) {
-			BUG_ON(cwq->flush_color != -1);
-
 			if (cwq->nr_in_flight[flush_color]) {
-				cwq->flush_color = flush_color;
 				atomic_inc(&wq->nr_cwqs_to_flush[flush_color]);
 				wait = true;
 			}
@@ -2599,9 +2587,6 @@ static bool flush_workqueue_prep_cwqs(struct workqueue_struct *wq,
 		spin_unlock_irq(&gcwq->lock);
 	}
 
-	if (flush_color >= 0)
-		wq_dec_flusher_ref(wq, flush_color);
-
 	return wait;
 }
 
@@ -2623,7 +2608,7 @@ void flush_workqueue(struct workqueue_struct *wq)
 		.done = COMPLETION_INITIALIZER_ONSTACK(this_flusher.done),
 	};
 	struct wq_flusher *next, *tmp;
-	int next_color;
+	int flush_color, next_color;
 
 	lock_map_acquire(&wq->lockdep_map);
 	lock_map_release(&wq->lockdep_map);
@@ -2633,6 +2618,7 @@ void flush_workqueue(struct workqueue_struct *wq)
 	/*
 	 * Start-to-wait phase
 	 */
+	flush_color = wq->work_color;
 	next_color = work_next_color(wq->work_color);
 
 	if (next_color != wq->flush_color) {
@@ -2642,27 +2628,31 @@ void flush_workqueue(struct workqueue_struct *wq)
 		 * by one.
 		 */
 		BUG_ON(!list_empty(&wq->flusher_overflow));
-		this_flusher.flush_color = wq->work_color;
+		this_flusher.flush_color = flush_color;
 		wq->work_color = next_color;
 
 		if (!wq->first_flusher) {
 			/* no flush in progress, become the first flusher */
-			BUG_ON(wq->flush_color != this_flusher.flush_color);
+			BUG_ON(wq->flush_color != flush_color);
 
 			wq->first_flusher = &this_flusher;
 
-			if (!flush_workqueue_prep_cwqs(wq, wq->flush_color,
+			if (!flush_workqueue_prep_cwqs(wq, flush_color,
 						       wq->work_color)) {
 				/* nothing to flush, done */
+				wq_dec_flusher_ref(wq, flush_color);
 				wq->flush_color = next_color;
 				wq->first_flusher = NULL;
 				goto out_unlock;
 			}
+
+			wq_dec_flusher_ref(wq, flush_color);
 		} else {
 			/* wait in queue */
 			BUG_ON(wq->flush_color == this_flusher.flush_color);
 			list_add_tail(&this_flusher.list, &wq->flusher_queue);
-			flush_workqueue_prep_cwqs(wq, -1, wq->work_color);
+			flush_workqueue_prep_cwqs(wq, flush_color,
+						  wq->work_color);
 		}
 	} else {
 		/*
@@ -2717,11 +2707,12 @@ void flush_workqueue(struct workqueue_struct *wq)
 		list_for_each_entry(tmp, &wq->flusher_overflow, list)
 			tmp->flush_color = wq->work_color;
 
+		flush_color = wq->work_color;
 		wq->work_color = work_next_color(wq->work_color);
 
 		list_splice_tail_init(&wq->flusher_overflow,
 				      &wq->flusher_queue);
-		flush_workqueue_prep_cwqs(wq, -1, wq->work_color);
+		flush_workqueue_prep_cwqs(wq, flush_color, wq->work_color);
 	}
 
 	if (list_empty(&wq->flusher_queue)) {
@@ -2732,14 +2723,14 @@ void flush_workqueue(struct workqueue_struct *wq)
 
 	/*
 	 * Need to flush more colors.  Make the next flusher
-	 * the new first flusher and arm cwqs.
+	 * the new first flusher and arm it.
 	 */
 	BUG_ON(wq->flush_color == wq->work_color);
 	BUG_ON(wq->flush_color != next->flush_color);
 
 	list_del_init(&next->list);
 	wq->first_flusher = next;
-	flush_workqueue_prep_cwqs(wq, wq->flush_color, -1);
+	wq_dec_flusher_ref(wq, wq->flush_color);
 
 out_unlock:
 	mutex_unlock(&wq->flush_mutex);
@@ -3264,7 +3255,6 @@ struct workqueue_struct *__alloc_workqueue_key(const char *fmt,
 		BUG_ON((unsigned long)cwq & WORK_STRUCT_FLAG_MASK);
 		cwq->pool = &gcwq->pools[pool_idx];
 		cwq->wq = wq;
-		cwq->flush_color = -1;
 		cwq->max_active = max_active;
 		INIT_LIST_HEAD(&cwq->delayed_works);
 	}
-- 
1.7.4.4

[PATCH 07/10] workqueue: simplify flush_workqueue_prep_cwqs()

[Lai Jiangshan]

Move the advance of wq->work_color into flush_workqueue_prep_cwqs()
and rename flush_workqueue_prep_cwqs() to workqueue_start_flush(),
It will simplify the caller.

Since the @flush_color and @work_color can't be -1, so we remove
the test in workqueue_start_flush() and fix the indent.

Since the @flush_color is always equals to wq->work_color(before advance),
so we remove the @flush_color argument. @flush_color becomes a
local variable.

Since the @work_color is always equals to work_next_color(flush_color),
so we remove the @work_color argument. @work_color is renamed to
@next_color and becomes a local variable

This patch doesn't make any functional difference.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/workqueue.c |   69 +++++++++++++++++++--------------------------------
 1 files changed, 26 insertions(+), 43 deletions(-)

diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index 803a22c..be407e1 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -2531,40 +2531,37 @@ static void insert_wq_barrier(struct cpu_workqueue_struct *cwq,
 }
 
 /**
- * flush_workqueue_prep_cwqs - prepare cwqs for workqueue flushing
+ * workqueue_start_flush - start workqueue flushing
  * @wq: workqueue being flushed
- * @flush_color: new flush color, < 0 for no-op
- * @work_color: new work color, < 0 for no-op
  *
- * Prepare cwqs for workqueue flushing.
+ * Start a new flush color and prepare cwqs for workqueue flushing.
  *
- * The caller should have initialized @wq->first_flusher prior to
- * calling this function with non-negative @flush_color.  If
- * @flush_color is negative, no flush color update is done and %false
- * is returned.
+ * Called with color space is not full.  The current work_color
+ * becomes new flush_color and work_color is advanced by one.
+ * All cwq's work_color are set to new work_color(advanced by one).
  *
- * If @work_color is non-negative, all cwqs should have the same
- * work_color which is previous to @work_color and all will be
- * advanced to @work_color.
+ * The caller should have initialized @wq->first_flusher prior to
+ * calling this function.
  *
  * CONTEXT:
  * mutex_lock(wq->flush_mutex).
  *
  * RETURNS:
- * %true if @flush_color >= 0 and there's something to flush.  %false
- * otherwise.
+ * %true if there's some cwqs to flush.  %false otherwise.
  */
-static bool flush_workqueue_prep_cwqs(struct workqueue_struct *wq,
-				      int flush_color, int work_color)
+static bool workqueue_start_flush(struct workqueue_struct *wq)
 {
+	int flush_color = wq->work_color;
+	int next_color = work_next_color(wq->work_color);
 	bool wait = false;
 	unsigned int cpu;
 
-	if (flush_color >= 0) {
-		BUG_ON(atomic_read(&wq->nr_cwqs_to_flush[flush_color]));
-		/* this ref is held by first flusher */
-		atomic_set(&wq->nr_cwqs_to_flush[flush_color], 1);
-	}
+	BUG_ON(next_color == wq->flush_color);
+	wq->work_color = next_color;
+
+	BUG_ON(atomic_read(&wq->nr_cwqs_to_flush[flush_color]));
+	/* this ref is held by first flusher */
+	atomic_set(&wq->nr_cwqs_to_flush[flush_color], 1);
 
 	for_each_cwq_cpu(cpu, wq) {
 		struct cpu_workqueue_struct *cwq = get_cwq(cpu, wq);
@@ -2572,17 +2569,13 @@ static bool flush_workqueue_prep_cwqs(struct workqueue_struct *wq,
 
 		spin_lock_irq(&gcwq->lock);
 
-		if (flush_color >= 0) {
-			if (cwq->nr_in_flight[flush_color]) {
-				atomic_inc(&wq->nr_cwqs_to_flush[flush_color]);
-				wait = true;
-			}
+		if (cwq->nr_in_flight[flush_color]) {
+			atomic_inc(&wq->nr_cwqs_to_flush[flush_color]);
+			wait = true;
 		}
 
-		if (work_color >= 0) {
-			BUG_ON(work_color != work_next_color(cwq->work_color));
-			cwq->work_color = work_color;
-		}
+		BUG_ON(next_color != work_next_color(cwq->work_color));
+		cwq->work_color = next_color;
 
 		spin_unlock_irq(&gcwq->lock);
 	}
@@ -2622,14 +2615,9 @@ void flush_workqueue(struct workqueue_struct *wq)
 	next_color = work_next_color(wq->work_color);
 
 	if (next_color != wq->flush_color) {
-		/*
-		 * Color space is not full.  The current work_color
-		 * becomes our flush_color and work_color is advanced
-		 * by one.
-		 */
+		/* Color space is not full */
 		BUG_ON(!list_empty(&wq->flusher_overflow));
 		this_flusher.flush_color = flush_color;
-		wq->work_color = next_color;
 
 		if (!wq->first_flusher) {
 			/* no flush in progress, become the first flusher */
@@ -2637,8 +2625,7 @@ void flush_workqueue(struct workqueue_struct *wq)
 
 			wq->first_flusher = &this_flusher;
 
-			if (!flush_workqueue_prep_cwqs(wq, flush_color,
-						       wq->work_color)) {
+			if (!workqueue_start_flush(wq)) {
 				/* nothing to flush, done */
 				wq_dec_flusher_ref(wq, flush_color);
 				wq->flush_color = next_color;
@@ -2651,8 +2638,7 @@ void flush_workqueue(struct workqueue_struct *wq)
 			/* wait in queue */
 			BUG_ON(wq->flush_color == this_flusher.flush_color);
 			list_add_tail(&this_flusher.list, &wq->flusher_queue);
-			flush_workqueue_prep_cwqs(wq, flush_color,
-						  wq->work_color);
+			workqueue_start_flush(wq);
 		}
 	} else {
 		/*
@@ -2707,12 +2693,9 @@ void flush_workqueue(struct workqueue_struct *wq)
 		list_for_each_entry(tmp, &wq->flusher_overflow, list)
 			tmp->flush_color = wq->work_color;
 
-		flush_color = wq->work_color;
-		wq->work_color = work_next_color(wq->work_color);
-
 		list_splice_tail_init(&wq->flusher_overflow,
 				      &wq->flusher_queue);
-		flush_workqueue_prep_cwqs(wq, flush_color, wq->work_color);
+		workqueue_start_flush(wq);
 	}
 
 	if (list_empty(&wq->flusher_queue)) {
-- 
1.7.4.4

[PATCH 08/10] workqueue: assign overflowed flushers's flush color when queued

[Lai Jiangshan]

wq->work_color is unchanged between overflowed flusher queued on
 ->flusher_overflow and requeued on ->flusher_queue.

So we can assign overflowed flushers's flush color when they are queued
on ->flusher_overflow.

This patch makes the flusher's flush color more clear:
	flusher's flush color is the work color of the WQ
	when flush_workqueue() starts.

Remove an unneeded loop.

This patch doesn't make any functional difference.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/workqueue.c |   19 +++++++++----------
 1 files changed, 9 insertions(+), 10 deletions(-)

diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index be407e1..f687893 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -2613,11 +2613,11 @@ void flush_workqueue(struct workqueue_struct *wq)
 	 */
 	flush_color = wq->work_color;
 	next_color = work_next_color(wq->work_color);
+	this_flusher.flush_color = flush_color;
 
 	if (next_color != wq->flush_color) {
 		/* Color space is not full */
 		BUG_ON(!list_empty(&wq->flusher_overflow));
-		this_flusher.flush_color = flush_color;
 
 		if (!wq->first_flusher) {
 			/* no flush in progress, become the first flusher */
@@ -2643,8 +2643,8 @@ void flush_workqueue(struct workqueue_struct *wq)
 	} else {
 		/*
 		 * Oops, color space is full, wait on overflow queue.
-		 * The next flush completion will assign us
-		 * flush_color and transfer to flusher_queue.
+		 * The next flush completion will start flush for us
+		 * with freed flush color and transfer us to flusher_queue.
 		 */
 		list_add_tail(&this_flusher.list, &wq->flusher_overflow);
 	}
@@ -2684,15 +2684,14 @@ void flush_workqueue(struct workqueue_struct *wq)
 
 	/* one color has been freed, handle overflow queue */
 	if (!list_empty(&wq->flusher_overflow)) {
+		BUG_ON(list_first_entry(&wq->flusher_overflow,
+					struct wq_flusher,
+					list)->flush_color
+		       != wq->work_color);
 		/*
-		 * Assign the same color to all overflowed
-		 * flushers, advance work_color and append to
-		 * flusher_queue.  This is the start-to-wait
-		 * phase for these overflowed flushers.
+		 * start flush with the freed color and append
+		 * overflowed flushers to the flusher_queue.
 		 */
-		list_for_each_entry(tmp, &wq->flusher_overflow, list)
-			tmp->flush_color = wq->work_color;
-
 		list_splice_tail_init(&wq->flusher_overflow,
 				      &wq->flusher_queue);
 		workqueue_start_flush(wq);
-- 
1.7.4.4

[PATCH 09/10] workqueue: remove flusher_overflow

[Lai Jiangshan]

We can detect whether a flusher is started by comparing its
flush_color VS wq->work_color.

We move all overflowed flusher to flusher_queue, and then we
start flush for them when there is freed color. we detect it
by the color of the last flusher of the flusher_queue.

This patch doesn't make any functional difference.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/workqueue.c |   39 +++++++++++++--------------------------
 1 files changed, 13 insertions(+), 26 deletions(-)

diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index f687893..d78fe08 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -252,7 +252,6 @@ struct workqueue_struct {
 	atomic_t		nr_cwqs_to_flush[WORK_NR_COLORS];
 	struct wq_flusher	*first_flusher;	/* F: first flusher */
 	struct list_head	flusher_queue;	/* F: flush waiters */
-	struct list_head	flusher_overflow; /* F: flush overflow list */
 
 	mayday_mask_t		mayday_mask;	/* cpus requesting rescue */
 	struct worker		*rescuer;	/* I: rescue worker */
@@ -2600,7 +2599,7 @@ void flush_workqueue(struct workqueue_struct *wq)
 		.flush_color = -1,
 		.done = COMPLETION_INITIALIZER_ONSTACK(this_flusher.done),
 	};
-	struct wq_flusher *next, *tmp;
+	struct wq_flusher *next, *tmp, *last;
 	int flush_color, next_color;
 
 	lock_map_acquire(&wq->lockdep_map);
@@ -2617,8 +2616,6 @@ void flush_workqueue(struct workqueue_struct *wq)
 
 	if (next_color != wq->flush_color) {
 		/* Color space is not full */
-		BUG_ON(!list_empty(&wq->flusher_overflow));
-
 		if (!wq->first_flusher) {
 			/* no flush in progress, become the first flusher */
 			BUG_ON(wq->flush_color != flush_color);
@@ -2642,11 +2639,11 @@ void flush_workqueue(struct workqueue_struct *wq)
 		}
 	} else {
 		/*
-		 * Oops, color space is full, wait on overflow queue.
+		 * Oops, color space is full, queue it without starting flush.
 		 * The next flush completion will start flush for us
-		 * with freed flush color and transfer us to flusher_queue.
+		 * with freed flush color.
 		 */
-		list_add_tail(&this_flusher.list, &wq->flusher_overflow);
+		list_add_tail(&this_flusher.list, &wq->flusher_queue);
 	}
 
 	mutex_unlock(&wq->flush_mutex);
@@ -2676,27 +2673,9 @@ void flush_workqueue(struct workqueue_struct *wq)
 		complete(&next->done);
 	}
 
-	BUG_ON(!list_empty(&wq->flusher_overflow) &&
-	       wq->flush_color != work_next_color(wq->work_color));
-
 	/* this flush_color is finished, advance by one */
 	wq->flush_color = work_next_color(wq->flush_color);
 
-	/* one color has been freed, handle overflow queue */
-	if (!list_empty(&wq->flusher_overflow)) {
-		BUG_ON(list_first_entry(&wq->flusher_overflow,
-					struct wq_flusher,
-					list)->flush_color
-		       != wq->work_color);
-		/*
-		 * start flush with the freed color and append
-		 * overflowed flushers to the flusher_queue.
-		 */
-		list_splice_tail_init(&wq->flusher_overflow,
-				      &wq->flusher_queue);
-		workqueue_start_flush(wq);
-	}
-
 	if (list_empty(&wq->flusher_queue)) {
 		BUG_ON(wq->flush_color != wq->work_color);
 		wq->first_flusher = NULL;
@@ -2710,8 +2689,17 @@ void flush_workqueue(struct workqueue_struct *wq)
 	BUG_ON(wq->flush_color == wq->work_color);
 	BUG_ON(wq->flush_color != next->flush_color);
 
+	last = list_entry(wq->flusher_queue.prev, struct wq_flusher, list);
 	list_del_init(&next->list);
 	wq->first_flusher = next;
+
+	/* if have unstarted flushers appended, start flush for them */
+	if (last->flush_color == wq->work_color)
+		workqueue_start_flush(wq);
+
+	BUG_ON(work_next_color(last->flush_color) != wq->work_color);
+
+	/* arm new first flusher */
 	wq_dec_flusher_ref(wq, wq->flush_color);
 
 out_unlock:
@@ -3221,7 +3209,6 @@ struct workqueue_struct *__alloc_workqueue_key(const char *fmt,
 	for (color = 0; color < WORK_NR_COLORS; color++)
 		atomic_set(&wq->nr_cwqs_to_flush[color], 0);
 	INIT_LIST_HEAD(&wq->flusher_queue);
-	INIT_LIST_HEAD(&wq->flusher_overflow);
 
 	lockdep_init_map(&wq->lockdep_map, lock_name, key, 0);
 	INIT_LIST_HEAD(&wq->list);
-- 
1.7.4.4

[PATCH 10/10] workqueue: remove wq->flush_color

[Lai Jiangshan]

Use wq->first_flusher->flush_color instead.

If current task is the first_flusher, we use @flush_color
or work_next_color(flush_color) directly.

This patch doesn't make any functional difference.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 kernel/workqueue.c |   52 ++++++++++++++++++++--------------------------------
 1 files changed, 20 insertions(+), 32 deletions(-)

diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index d78fe08..e703659 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -248,7 +248,6 @@ struct workqueue_struct {
 
 	struct mutex		flush_mutex;	/* protects wq flushing */
 	int			work_color;	/* F: current work color */
-	int			flush_color;	/* F: current flush color */
 	atomic_t		nr_cwqs_to_flush[WORK_NR_COLORS];
 	struct wq_flusher	*first_flusher;	/* F: first flusher */
 	struct list_head	flusher_queue;	/* F: flush waiters */
@@ -2555,7 +2554,7 @@ static bool workqueue_start_flush(struct workqueue_struct *wq)
 	bool wait = false;
 	unsigned int cpu;
 
-	BUG_ON(next_color == wq->flush_color);
+	BUG_ON(next_color == wq->first_flusher->flush_color);
 	wq->work_color = next_color;
 
 	BUG_ON(atomic_read(&wq->nr_cwqs_to_flush[flush_color]));
@@ -2614,29 +2613,23 @@ void flush_workqueue(struct workqueue_struct *wq)
 	next_color = work_next_color(wq->work_color);
 	this_flusher.flush_color = flush_color;
 
-	if (next_color != wq->flush_color) {
-		/* Color space is not full */
-		if (!wq->first_flusher) {
-			/* no flush in progress, become the first flusher */
-			BUG_ON(wq->flush_color != flush_color);
-
-			wq->first_flusher = &this_flusher;
-
-			if (!workqueue_start_flush(wq)) {
-				/* nothing to flush, done */
-				wq_dec_flusher_ref(wq, flush_color);
-				wq->flush_color = next_color;
-				wq->first_flusher = NULL;
-				goto out_unlock;
-			}
+	if (!wq->first_flusher) {
+		/* no flush in progress, become the first flusher */
+		wq->first_flusher = &this_flusher;
 
+		if (!workqueue_start_flush(wq)) {
+			/* nothing to flush, done */
 			wq_dec_flusher_ref(wq, flush_color);
-		} else {
-			/* wait in queue */
-			BUG_ON(wq->flush_color == this_flusher.flush_color);
-			list_add_tail(&this_flusher.list, &wq->flusher_queue);
-			workqueue_start_flush(wq);
+			wq->first_flusher = NULL;
+			goto out_unlock;
 		}
+
+		wq_dec_flusher_ref(wq, flush_color);
+	} else if (next_color != wq->first_flusher->flush_color) {
+		/* Color space is not full, wait in queue */
+		BUG_ON(wq->first_flusher->flush_color == flush_color);
+		list_add_tail(&this_flusher.list, &wq->flusher_queue);
+		workqueue_start_flush(wq);
 	} else {
 		/*
 		 * Oops, color space is full, queue it without starting flush.
@@ -2663,21 +2656,17 @@ void flush_workqueue(struct workqueue_struct *wq)
 
 	BUG_ON(wq->first_flusher != &this_flusher);
 	BUG_ON(!list_empty(&this_flusher.list));
-	BUG_ON(wq->flush_color != this_flusher.flush_color);
 
 	/* complete all the flushers sharing the current flush color */
 	list_for_each_entry_safe(next, tmp, &wq->flusher_queue, list) {
-		if (next->flush_color != wq->flush_color)
+		if (next->flush_color != flush_color)
 			break;
 		list_del_init(&next->list);
 		complete(&next->done);
 	}
 
-	/* this flush_color is finished, advance by one */
-	wq->flush_color = work_next_color(wq->flush_color);
-
 	if (list_empty(&wq->flusher_queue)) {
-		BUG_ON(wq->flush_color != wq->work_color);
+		BUG_ON(work_next_color(flush_color) != wq->work_color);
 		wq->first_flusher = NULL;
 		goto out_unlock;
 	}
@@ -2686,9 +2675,6 @@ void flush_workqueue(struct workqueue_struct *wq)
 	 * Need to flush more colors.  Make the next flusher
 	 * the new first flusher and arm it.
 	 */
-	BUG_ON(wq->flush_color == wq->work_color);
-	BUG_ON(wq->flush_color != next->flush_color);
-
 	last = list_entry(wq->flusher_queue.prev, struct wq_flusher, list);
 	list_del_init(&next->list);
 	wq->first_flusher = next;
@@ -2698,9 +2684,11 @@ void flush_workqueue(struct workqueue_struct *wq)
 		workqueue_start_flush(wq);
 
 	BUG_ON(work_next_color(last->flush_color) != wq->work_color);
+	BUG_ON(work_next_color(flush_color) != next->flush_color);
+	BUG_ON(next->flush_color == wq->work_color);
 
 	/* arm new first flusher */
-	wq_dec_flusher_ref(wq, wq->flush_color);
+	wq_dec_flusher_ref(wq, next->flush_color);
 
 out_unlock:
 	mutex_unlock(&wq->flush_mutex);
-- 
1.7.4.4

Re: [PATCH 00/10] workqueue: restructure flush_workqueue() and start all flusher at the same time

[Tejun Heo]

Hello, Lai.

On Mon, Sep 24, 2012 at 06:07:02PM +0800, Lai Jiangshan wrote:
> The core patch is patch6, it makes all flusher can start and the same time
> and allow us do more cleanup.
> 
> Only patch1 and patch6 change the behavior of the code.
> All other patches do not change any behavior.

It would have been nice if you described what this patchset tries to
achieve how in the head message.

I don't see anything wrong with the patchset but flush_workqueue() is
quite hairy before this patchset and I'm not sure the situation
improves a lot afterwards.  The current code is known / verified to
work for quite some time and I'd *much* prefer to keep it stable
unless it can be vastly simpler.

I do like the removal of explicit cascading and would have gone that
direction if this code is just being implemented but I'm quite
skeptical whether changing over to that now is justifiable.  Flush
bugs tend to be nasty and often difficult to track down.

I'll think more about it.  How confident are you about the change?
How did you test them?  For changes like this, it usually helps a lot
to describe how things were tested as part of head and/or commit
messages.

Thanks.

-- 
tejun

Re: [PATCH 00/10] workqueue: restructure flush_workqueue() and start all flusher at the same time

[Lai Jiangshan]

On 09/25/2012 04:39 AM, Tejun Heo wrote:
> Hello, Lai.
> 
> On Mon, Sep 24, 2012 at 06:07:02PM +0800, Lai Jiangshan wrote:
>> The core patch is patch6, it makes all flusher can start and the same time
>> and allow us do more cleanup.
>>
>> Only patch1 and patch6 change the behavior of the code.
>> All other patches do not change any behavior.
> 
> It would have been nice if you described what this patchset tries to
> achieve how in the head message.
> 
> I don't see anything wrong with the patchset but flush_workqueue() is
> quite hairy before this patchset and I'm not sure the situation
> improves a lot afterwards.  The current code is known / verified to
> work for quite some time and I'd *much* prefer to keep it stable
> unless it can be vastly simpler.

Hi, Tejun

I know your attitude, it is OK if you reject it.

I found the flush_workqueue() is not nature for me, especially
the usage of the colors and flush_workqueue_prep_cwqs().
so I try to improve it without change too much things/behavior.

(These patchset delay other simple patches, I think I should
send simple patches at first.)

> 
> I do like the removal of explicit cascading and would have gone that
> direction if this code is just being implemented but I'm quite
> skeptical whether changing over to that now is justifiable.  Flush
> bugs tend to be nasty and often difficult to track down.
> 
> I'll think more about it.  How confident are you about the change?
> How did you test them?  For changes like this, it usually helps a lot
> to describe how things were tested as part of head and/or commit
> messages.
> 

I always check the code by hard reviewing the code. I always try to image
there are many thread run in my brain orderless and I write all possible
transitions in paper. This progress is the most important, no test can
replace it.

Human brain can wrong, the attached patch is my testing code.
It verify flush_workqueue() by cookie number.

type "make test" to start the test.
type "Ctrl" and "c" to stop the test.

I also need your testing code for workqueue. ^_^

Thanks,
Lai

diff --git a/workqueue_flush_test/Makefile b/workqueue_flush_test/Makefile
new file mode 100644
index 0000000..3ecc7aa
--- /dev/null
+++ b/workqueue_flush_test/Makefile
@@ -0,0 +1,10 @@
+obj-m += wflush.o
+
+all:
+	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules
+
+clean:
+	make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean
+
+test: all
+	bash ./test.sh
diff --git a/workqueue_flush_test/test.sh b/workqueue_flush_test/test.sh
new file mode 100644
index 0000000..a9d2d6a
--- /dev/null
+++ b/workqueue_flush_test/test.sh
@@ -0,0 +1,12 @@
+#/bin/bash
+
+make
+sync
+sync
+echo testing...
+trap 'echo interrupt test' INT
+sudo insmod wflush.ko
+sleep 60000
+sudo rmmod wflush.ko
+echo test done
+
diff --git a/workqueue_flush_test/wflush.c b/workqueue_flush_test/wflush.c
new file mode 100644
index 0000000..971e73d
--- /dev/null
+++ b/workqueue_flush_test/wflush.c
@@ -0,0 +1,129 @@
+#include <linux/module.h>
+#include <linux/kthread.h>
+#include <linux/workqueue.h>
+#include <linux/delay.h>
+#include <linux/mutex.h>
+#include <linux/list.h>
+#include <linux/random.h>
+
+struct cookie_struct {
+	struct list_head head;
+	unsigned long cookie;
+};
+
+static DEFINE_MUTEX(cookie_lock);
+static unsigned long test_cookie;
+static LIST_HEAD(cookie_head);
+
+static unsigned long last_cookie(void)
+{
+	unsigned long cookie;
+
+	mutex_lock(&cookie_lock);
+	cookie = test_cookie - 1; /* c->cookie = test_cookie++; */
+	mutex_unlock(&cookie_lock);
+
+	return cookie;
+}
+
+static unsigned long tip_cookie(void)
+{
+	unsigned long cookie;
+
+	mutex_lock(&cookie_lock);
+	if (list_empty(&cookie_head))
+		cookie = test_cookie;
+	else
+		cookie = list_first_entry(&cookie_head, struct cookie_struct, head)->cookie;
+	mutex_unlock(&cookie_lock);
+
+	return cookie;
+}
+
+struct test_work {
+	struct work_struct w;
+	struct cookie_struct c;
+};
+
+static void add_test_work(struct test_work *t)
+{
+	struct cookie_struct *c = &t->c;
+
+	mutex_lock(&cookie_lock);
+	c->cookie = test_cookie++;
+	BUG_ON(!list_empty(&c->head));
+	list_add_tail(&c->head, &cookie_head);
+	schedule_work(&t->w);
+	mutex_unlock(&cookie_lock);
+
+	udelay(1+random32()%50);
+}
+
+static void test_work_fn(struct work_struct *w)
+{
+	struct test_work *t = container_of(w, struct test_work, w);
+
+	mutex_lock(&cookie_lock);
+	list_del_init(&t->c.head);
+	mutex_unlock(&cookie_lock);
+
+	udelay(1+random32()%50);
+}
+
+static int test_thread(void *arg)
+{
+	unsigned long lcookie, tcookie;
+	struct test_work t[10];
+	int i;
+
+	for (i = 0; i < ARRAY_SIZE(t); i++) {
+		INIT_WORK_ONSTACK(&t[i].w, test_work_fn);
+		INIT_LIST_HEAD(&t[i].c.head);
+	}
+
+	do {
+		for (i = 0; i < ARRAY_SIZE(t); i++) {
+			add_test_work(t+i);
+		}
+
+		lcookie = last_cookie();
+		flush_scheduled_work();
+		tcookie = tip_cookie();
+		BUG_ON((long)(tcookie - lcookie) <= 0);
+	} while (!kthread_should_stop());
+	return 0;
+}
+
+static struct task_struct *test_tasks[100];
+
+static int test_init(void)
+{
+	int i;
+
+	printk(KERN_ERR "wflush test start\n");
+	for (i = 0; i < ARRAY_SIZE(test_tasks); i++) {
+		test_tasks[i] = kthread_run(test_thread, NULL, "wflush");
+		if (!test_tasks[i]) {
+			printk(KERN_ERR "wflush create fail %d\n", i);
+			break;
+		}
+	}
+
+	return 0;
+}
+module_init(test_init);
+
+static void test_exit(void)
+{
+	int i;
+
+	printk(KERN_ERR "wflush test stopping\n");
+	for (i = 0; i < ARRAY_SIZE(test_tasks); i++) {
+		if (test_tasks[i])
+			kthread_stop(test_tasks[i]);
+	}
+	printk(KERN_ERR "wflush test stopped\n");
+}
+module_exit(test_exit);
+
+MODULE_LICENSE("GPL");

Re: [PATCH 00/10] workqueue: restructure flush_workqueue() and start all flusher at the same time

[Lai Jiangshan]

On 09/25/2012 04:39 AM, Tejun Heo wrote:
> 
> I do like the removal of explicit cascading and would have gone that
> direction if this code is just being implemented but I'm quite
> skeptical whether changing over to that now is justifiable.  Flush
> bugs tend to be nasty and often difficult to track down.
> 

Hi, Tejun

I know your attitude, it is OK if you reject it.

It is not possible to remove cascading. If cascading code is
not in flush_workqueue(), it must be in some where else.

If you force overflow to wait for freed color before do flush(which also
force only one flusher for one color), and force the sole flush_workqueue()
to grab ->flush_mutex twice, we can simplify the flush_workqueue().
(see the attached patch, it remove 100 LOC, and the cascading code becomes
only 3 LOC). But these two forcing slow down the caller a little.

(And if you allow to use SRCU(which is only TWO colors), you can remove another
150 LOC. flush_workqueue() will become single line. But it will add some more overhead
in flush_workqueue() because SRCU's readsite is lockless)

Thanks,
Lai

This patch is applied on top of patch7. it replaces patch8~10

 workqueue.c |  168 ++++++++++--------------------------------------------------
 1 file changed, 30 insertions(+), 138 deletions(-)
diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index be407e1..bff0ae0 100644
--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -204,15 +204,6 @@ struct cpu_workqueue_struct {
 };
 
 /*
- * Structure used to wait for workqueue flush.
- */
-struct wq_flusher {
-	struct list_head	list;		/* F: list of flushers */
-	int			flush_color;	/* F: flush color waiting for */
-	struct completion	done;		/* flush completion */
-};
-
-/*
  * All cpumasks are assumed to be always set on UP and thus can't be
  * used to determine whether there's something to be done.
  */
@@ -250,9 +241,8 @@ struct workqueue_struct {
 	int			work_color;	/* F: current work color */
 	int			flush_color;	/* F: current flush color */
 	atomic_t		nr_cwqs_to_flush[WORK_NR_COLORS];
-	struct wq_flusher	*first_flusher;	/* F: first flusher */
-	struct list_head	flusher_queue;	/* F: flush waiters */
-	struct list_head	flusher_overflow; /* F: flush overflow list */
+	struct completion	*flusher[WORK_NR_COLORS]; /* F: flusers */
+	wait_queue_head_t	flusher_overflow; /* flush overflow queue */
 
 	mayday_mask_t		mayday_mask;	/* cpus requesting rescue */
 	struct worker		*rescuer;	/* I: rescue worker */
@@ -1001,7 +991,7 @@ static void wq_dec_flusher_ref(struct workqueue_struct *wq, int color)
 	 * It will handle the rest.
 	 */
 	if (atomic_dec_and_test(&wq->nr_cwqs_to_flush[color]))
-		complete(&wq->first_flusher->done);
+		complete(wq->flusher[color]);
 }
 
 /**
@@ -2540,27 +2530,20 @@ static void insert_wq_barrier(struct cpu_workqueue_struct *cwq,
  * becomes new flush_color and work_color is advanced by one.
  * All cwq's work_color are set to new work_color(advanced by one).
  *
- * The caller should have initialized @wq->first_flusher prior to
- * calling this function.
- *
  * CONTEXT:
  * mutex_lock(wq->flush_mutex).
- *
- * RETURNS:
- * %true if there's some cwqs to flush.  %false otherwise.
  */
-static bool workqueue_start_flush(struct workqueue_struct *wq)
+static void workqueue_start_flush(struct workqueue_struct *wq)
 {
 	int flush_color = wq->work_color;
 	int next_color = work_next_color(wq->work_color);
-	bool wait = false;
 	unsigned int cpu;
 
 	BUG_ON(next_color == wq->flush_color);
 	wq->work_color = next_color;
 
 	BUG_ON(atomic_read(&wq->nr_cwqs_to_flush[flush_color]));
-	/* this ref is held by first flusher */
+	/* this ref is held by previous flusher */
 	atomic_set(&wq->nr_cwqs_to_flush[flush_color], 1);
 
 	for_each_cwq_cpu(cpu, wq) {
@@ -2569,18 +2552,14 @@ static bool workqueue_start_flush(struct workqueue_struct *wq)
 
 		spin_lock_irq(&gcwq->lock);
 
-		if (cwq->nr_in_flight[flush_color]) {
+		if (cwq->nr_in_flight[flush_color])
 			atomic_inc(&wq->nr_cwqs_to_flush[flush_color]);
-			wait = true;
-		}
 
 		BUG_ON(next_color != work_next_color(cwq->work_color));
 		cwq->work_color = next_color;
 
 		spin_unlock_irq(&gcwq->lock);
 	}
-
-	return wait;
 }
 
 /**
@@ -2595,127 +2574,41 @@ static bool workqueue_start_flush(struct workqueue_struct *wq)
  */
 void flush_workqueue(struct workqueue_struct *wq)
 {
-	struct wq_flusher this_flusher = {
-		.list = LIST_HEAD_INIT(this_flusher.list),
-		.flush_color = -1,
-		.done = COMPLETION_INITIALIZER_ONSTACK(this_flusher.done),
-	};
-	struct wq_flusher *next, *tmp;
-	int flush_color, next_color;
+	DECLARE_COMPLETION(this_flusher);
+	int flush_color;
 
 	lock_map_acquire(&wq->lockdep_map);
 	lock_map_release(&wq->lockdep_map);
 
+overflow:
+	/* handle overflow*/
+	wait_event(wq->flusher_overflow,
+		   work_next_color(wq->work_color) != wq->flush_color);
 	mutex_lock(&wq->flush_mutex);
-
-	/*
-	 * Start-to-wait phase
-	 */
-	flush_color = wq->work_color;
-	next_color = work_next_color(wq->work_color);
-
-	if (next_color != wq->flush_color) {
-		/* Color space is not full */
-		BUG_ON(!list_empty(&wq->flusher_overflow));
-		this_flusher.flush_color = flush_color;
-
-		if (!wq->first_flusher) {
-			/* no flush in progress, become the first flusher */
-			BUG_ON(wq->flush_color != flush_color);
-
-			wq->first_flusher = &this_flusher;
-
-			if (!workqueue_start_flush(wq)) {
-				/* nothing to flush, done */
-				wq_dec_flusher_ref(wq, flush_color);
-				wq->flush_color = next_color;
-				wq->first_flusher = NULL;
-				goto out_unlock;
-			}
-
-			wq_dec_flusher_ref(wq, flush_color);
-		} else {
-			/* wait in queue */
-			BUG_ON(wq->flush_color == this_flusher.flush_color);
-			list_add_tail(&this_flusher.list, &wq->flusher_queue);
-			workqueue_start_flush(wq);
-		}
-	} else {
-		/*
-		 * Oops, color space is full, wait on overflow queue.
-		 * The next flush completion will assign us
-		 * flush_color and transfer to flusher_queue.
-		 */
-		list_add_tail(&this_flusher.list, &wq->flusher_overflow);
+	if (work_next_color(wq->work_color) == wq->flush_color) {
+		mutex_unlock(&wq->flush_mutex);
+		goto overflow;
 	}
 
+	/* start flush */
+	flush_color = wq->work_color;
+	wq->flusher[flush_color] = &this_flusher;
+	workqueue_start_flush(wq);
+	if (flush_color == wq->flush_color)
+		wq_dec_flusher_ref(wq, flush_color);
 	mutex_unlock(&wq->flush_mutex);
 
-	wait_for_completion(&this_flusher.done);
-
-	/*
-	 * Wake-up-and-cascade phase
-	 *
-	 * First flushers are responsible for cascading flushes and
-	 * handling overflow.  Non-first flushers can simply return.
-	 */
-	if (wq->first_flusher != &this_flusher)
-		return;
+	wait_for_completion(&this_flusher);
 
+	/* finish flush */
 	mutex_lock(&wq->flush_mutex);
-
-	BUG_ON(wq->first_flusher != &this_flusher);
-	BUG_ON(!list_empty(&this_flusher.list));
-	BUG_ON(wq->flush_color != this_flusher.flush_color);
-
-	/* complete all the flushers sharing the current flush color */
-	list_for_each_entry_safe(next, tmp, &wq->flusher_queue, list) {
-		if (next->flush_color != wq->flush_color)
-			break;
-		list_del_init(&next->list);
-		complete(&next->done);
-	}
-
-	BUG_ON(!list_empty(&wq->flusher_overflow) &&
-	       wq->flush_color != work_next_color(wq->work_color));
-
-	/* this flush_color is finished, advance by one */
+	BUG_ON(flush_color != wq->flush_color);
+	BUG_ON(wq->flusher[flush_color] != &this_flusher);
+	wq->flusher[flush_color] = NULL;
 	wq->flush_color = work_next_color(wq->flush_color);
-
-	/* one color has been freed, handle overflow queue */
-	if (!list_empty(&wq->flusher_overflow)) {
-		/*
-		 * Assign the same color to all overflowed
-		 * flushers, advance work_color and append to
-		 * flusher_queue.  This is the start-to-wait
-		 * phase for these overflowed flushers.
-		 */
-		list_for_each_entry(tmp, &wq->flusher_overflow, list)
-			tmp->flush_color = wq->work_color;
-
-		list_splice_tail_init(&wq->flusher_overflow,
-				      &wq->flusher_queue);
-		workqueue_start_flush(wq);
-	}
-
-	if (list_empty(&wq->flusher_queue)) {
-		BUG_ON(wq->flush_color != wq->work_color);
-		wq->first_flusher = NULL;
-		goto out_unlock;
-	}
-
-	/*
-	 * Need to flush more colors.  Make the next flusher
-	 * the new first flusher and arm it.
-	 */
-	BUG_ON(wq->flush_color == wq->work_color);
-	BUG_ON(wq->flush_color != next->flush_color);
-
-	list_del_init(&next->list);
-	wq->first_flusher = next;
-	wq_dec_flusher_ref(wq, wq->flush_color);
-
-out_unlock:
+	if (wq->work_color != wq->flush_color)
+		 wq_dec_flusher_ref(wq, wq->flush_color);
+	wake_up(&wq->flusher_overflow);
 	mutex_unlock(&wq->flush_mutex);
 }
 EXPORT_SYMBOL_GPL(flush_workqueue);
@@ -3221,8 +3114,7 @@ struct workqueue_struct *__alloc_workqueue_key(const char *fmt,
 	mutex_init(&wq->flush_mutex);
 	for (color = 0; color < WORK_NR_COLORS; color++)
 		atomic_set(&wq->nr_cwqs_to_flush[color], 0);
-	INIT_LIST_HEAD(&wq->flusher_queue);
-	INIT_LIST_HEAD(&wq->flusher_overflow);
+	init_waitqueue_head(&wq->flusher_overflow);
 
 	lockdep_init_map(&wq->lockdep_map, lock_name, key, 0);
 	INIT_LIST_HEAD(&wq->list);

Re: [PATCH 00/10] workqueue: restructure flush_workqueue() and start all flusher at the same time

[Tejun Heo]

[-- Attachment #1: Type: text/plain, Size: 1391 bytes --]

Hello, Lai.

On Tue, Sep 25, 2012 at 05:02:31PM +0800, Lai Jiangshan wrote:
> I found the flush_workqueue() is not nature for me, especially

I don't think it's natural for anybody.  I'm not a big fan of that
code either.

> the usage of the colors and flush_workqueue_prep_cwqs().
> so I try to improve it without change too much things/behavior.
> 
> (These patchset delay other simple patches, I think I should
> send simple patches at first.)

Yes, please do so.

> I always check the code by hard reviewing the code. I always try to image
> there are many thread run in my brain orderless and I write all possible
> transitions in paper. This progress is the most important, no test can
> replace it.
> 
> Human brain can wrong, the attached patch is my testing code.
> It verify flush_workqueue() by cookie number.

Sure, nothing beats careful reviews but then again it's difficult to
have any level of confidence without actually excercising and
verifying each possible code path.  For tricky changes, it helps a lot
if you describe how the code was verified and why and how much you
feel confident about the change.

> I also need your testing code for workqueue. ^_^

Heh, you asked for it.  Attached.  It's a scenario based thing and I
use different scenarios usually in combination with some debug printks
to verify things are behaving as I think they should.

Thanks.

-- 
tejun

[-- Attachment #2: test-wq.c --]
[-- Type: text/x-csrc, Size: 36402 bytes --]

#include <linux/module.h>
#include <linux/workqueue.h>
#include <linux/jiffies.h>
#include <linux/delay.h>
#include <linux/sched.h>
#include <linux/wait.h>
#include <linux/cpu.h>
#include <linux/kthread.h>

#define MAX_WQ_NAME		64
#define MAX_WQS			64
#define MAX_WORKS		64

struct wq_spec {
	int			id;	/* -1 terminates */
	unsigned int		max_active;
	unsigned int		flags;
};

enum action {
	ACT_TERM,			/* end */
	ACT_LOG,			/* const char * */
	ACT_BURN,			/* ulong duration_msecs */
	ACT_SLEEP,			/* ulong duration_msecs */
	ACT_WAKEUP,			/* ulong work_id */
	ACT_REQUEUE,			/* ulong delay_msecs, ulong cpu */
	ACT_FLUSH,			/* ulong work_id */
	ACT_FLUSH_WQ,			/* ulong workqueue_id */
	ACT_CANCEL,			/* ulong work_id */
};

struct work_action {
	enum action		action;	/* ACT_TERM terminates */
	union {
		unsigned long	v;
		const char	*s;
	};
	unsigned long		v1;
};

struct work_spec {
	int			id;		/* -1 terminates */
	int			wq_id;
	int			requeue_cnt;
	unsigned int		cpu;
	unsigned long		initial_delay;	/* msecs */

	const struct work_action *actions;
};

struct test_scenario {
	const struct wq_spec	*wq_spec;
	const struct work_spec	**work_spec;	/* NULL terminated */
};

static const struct wq_spec dfl_wq_spec[] = {
	{
		.id		= 0,
		.max_active	= 32,
		.flags		= 0,
	},
	{
		.id		= 1,
		.max_active	= 32,
		.flags		= 0,
	},
	{
		.id		= 2,
		.max_active	= 32,
		.flags		= WQ_RESCUER,
	},
	{
		.id		= 3,
		.max_active	= 32,
		.flags		= WQ_FREEZABLE,
	},
	{
		.id		= 4,
		.max_active	= 1,
		.flags		= WQ_UNBOUND | WQ_FREEZABLE/* | WQ_DBG*/,
	},
	{
		.id		= 5,
		.max_active	= 32,
		.flags		= WQ_NON_REENTRANT,
	},
	{
		.id		= 6,
		.max_active	= 4,
		.flags		= WQ_HIGHPRI,
	},
	{
		.id		= 7,
		.max_active	= 4,
		.flags		= WQ_CPU_INTENSIVE,
	},
	{
		.id		= 8,
		.max_active	= 4,
		.flags		= WQ_HIGHPRI | WQ_CPU_INTENSIVE,
	},
	{ .id = -1 },
};

/*
 * Scenario 0.  All are on cpu0.  work16 and 17 burn cpus for 10 and
 * 5msecs respectively and requeue themselves.  18 sleeps 2 secs and
 * cancel both.
 */
static const struct work_spec work_spec0[] = {
	{
		.id		= 16,
		.requeue_cnt	= 1024,
		.actions	= (const struct work_action[]) {
			{ ACT_BURN,	{ 10 }},
			{ ACT_REQUEUE,	{ 0 }, NR_CPUS },
			{ ACT_TERM },
		},
	},
	{
		.id		= 17,
		.requeue_cnt	= 1024,
		.actions	= (const struct work_action[]) {
			{ ACT_BURN,	{ 5 }},
			{ ACT_REQUEUE,	{ 0 }, NR_CPUS },
			{ ACT_TERM },
		},
	},
	{
		.id		= 18,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "will sleep 2s and cancel both" }},
			{ ACT_SLEEP,	{ 2000 }},
			{ ACT_CANCEL,	{ 16 }},
			{ ACT_CANCEL,	{ 17 }},
			{ ACT_TERM },
		},
	},
	{ .id = -1 },
};

static const struct test_scenario scenario0 = {
	.wq_spec		= dfl_wq_spec,
	.work_spec		=
	(const struct work_spec *[]) { work_spec0, NULL },
};

/*
 * Scenario 1.  All are on cpu0.  Work 0, 1 and 2 sleep for different
 * intervals but all three will terminate at around 30secs.  3 starts
 * at @28 and 4 at @33 and both sleep for five secs and then
 * terminate.  5 waits for 0, 1, 2 and then flush wq which by the time
 * should have 3 on it.  After 3 completes @32, 5 terminates too.
 * After 4 secs, 4 terminates and all test sequence is done.
 */
static const struct work_spec work_spec1[] = {
	{
		.id		= 0,
		.actions	= (const struct work_action[]) {
			{ ACT_BURN,	{ 3 }},	/* to cause sched activation */
			{ ACT_LOG,	{ .s = "will sleep 30s" }},
			{ ACT_SLEEP,	{ 30000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_BURN,	{ 5 }},
			{ ACT_LOG,	{ .s = "will sleep 10s and burn 5msec and repeat 3 times" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_BURN,	{ 5 }},
			{ ACT_LOG,	{ .s = "@10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_BURN,	{ 5 }},
			{ ACT_LOG,	{ .s = "@20s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_BURN,	{ 5 }},
			{ ACT_LOG,	{ .s = "@30s" }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 2,
		.actions	= (const struct work_action[]) {
			{ ACT_BURN,	{ 1 }},
			{ ACT_LOG,	{ .s = "will sleep 3s and burn 1msec and repeat 10 times" }},
			{ ACT_SLEEP,	{ 3000 }},
			{ ACT_BURN,	{ 1 }},
			{ ACT_LOG,	{ .s = "@3s" }},
			{ ACT_SLEEP,	{ 3000 }},
			{ ACT_BURN,	{ 1 }},
			{ ACT_LOG,	{ .s = "@6s" }},
			{ ACT_SLEEP,	{ 3000 }},
			{ ACT_BURN,	{ 1 }},
			{ ACT_LOG,	{ .s = "@9s" }},
			{ ACT_SLEEP,	{ 3000 }},
			{ ACT_BURN,	{ 1 }},
			{ ACT_LOG,	{ .s = "@12s" }},
			{ ACT_SLEEP,	{ 3000 }},
			{ ACT_BURN,	{ 1 }},
			{ ACT_LOG,	{ .s = "@15s" }},
			{ ACT_SLEEP,	{ 3000 }},
			{ ACT_BURN,	{ 1 }},
			{ ACT_LOG,	{ .s = "@18s" }},
			{ ACT_SLEEP,	{ 3000 }},
			{ ACT_BURN,	{ 1 }},
			{ ACT_LOG,	{ .s = "@21s" }},
			{ ACT_SLEEP,	{ 3000 }},
			{ ACT_BURN,	{ 1 }},
			{ ACT_LOG,	{ .s = "@24s" }},
			{ ACT_SLEEP,	{ 3000 }},
			{ ACT_BURN,	{ 1 }},
			{ ACT_LOG,	{ .s = "@27s" }},
			{ ACT_SLEEP,	{ 3000 }},
			{ ACT_BURN,	{ 1 }},
			{ ACT_LOG,	{ .s = "@30s" }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 3,
		.initial_delay	= 29000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "started@28s, will sleep for 5s" }},
			{ ACT_SLEEP,	{ 5000 }},
			{ ACT_TERM },
		}
	},
	{
		.id		= 4,
		.initial_delay	= 33000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "started@33s, will sleep for 5s" }},
			{ ACT_SLEEP,	{ 5000 }},
			{ ACT_TERM },
		}
	},
	{
		.id		= 5,
		.wq_id		= 1,	/* can't flush self */
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "flushing 0, 1 and 2" }},
			{ ACT_FLUSH,	{ 0 }},
			{ ACT_FLUSH,	{ 1 }},
			{ ACT_FLUSH,	{ 2 }},
			{ ACT_FLUSH_WQ,	{ 0 }},
			{ ACT_TERM },
		},
	},
	{ .id = -1 },
};

static const struct test_scenario scenario1 = {
	.wq_spec		= dfl_wq_spec,
	.work_spec		=
	(const struct work_spec *[]) { work_spec1, NULL },
};

/*
 * Scenario 2.  Combination of scenario 0 and 1.
 */
static const struct test_scenario scenario2 = {
	.wq_spec		= dfl_wq_spec,
	.work_spec		=
	(const struct work_spec *[]) { work_spec0, work_spec1, NULL },
};

/*
 * Scenario 3.  More complex flushing.
 *
 *               2:burn 2s        3:4s
 *                <---->      <---------->
 *     0:4s                1:4s
 * <---------->      <..----------->
 *    ^               ^
 *    |               |
 *    |               |
 * 4:flush(cpu0)    flush_wq
 * 5:flush(cpu0)    flush
 * 6:flush(cpu1)    flush_wq
 * 7:flush(cpu1)    flush
 */
static const struct work_spec work_spec2[] = {
	{
		.id		= 0,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 1,
		.initial_delay	= 6000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 2,
		.initial_delay	= 5000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "burning 2s" }},
			{ ACT_BURN,	{ 2000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 3,
		.initial_delay	= 9000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},

	{
		.id		= 4,
		.wq_id		= 1,
		.initial_delay	= 1000,
		.actions	= (const struct work_action[]) {
			{ ACT_FLUSH,	{ 0 }},
			{ ACT_SLEEP,	{ 2500 }},
			{ ACT_FLUSH_WQ,	{ 0 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 5,
		.wq_id		= 1,
		.initial_delay	= 1000,
		.actions	= (const struct work_action[]) {
			{ ACT_FLUSH,	{ 0 }},
			{ ACT_SLEEP,	{ 2500 }},
			{ ACT_FLUSH,	{ 1 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 6,
		.wq_id		= 1,
		.cpu		= 1,
		.initial_delay	= 1000,
		.actions	= (const struct work_action[]) {
			{ ACT_FLUSH,	{ 0 }},
			{ ACT_SLEEP,	{ 2500 }},
			{ ACT_FLUSH_WQ,	{ 0 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 7,
		.wq_id		= 1,
		.cpu		= 1,
		.initial_delay	= 1000,
		.actions	= (const struct work_action[]) {
			{ ACT_FLUSH,	{ 0 }},
			{ ACT_SLEEP,	{ 2500 }},
			{ ACT_FLUSH,	{ 1 }},
			{ ACT_TERM },
		},
	},
	{ .id = -1 },
};

static const struct test_scenario scenario3 = {
	.wq_spec		= dfl_wq_spec,
	.work_spec		=
	(const struct work_spec *[]) { work_spec2, NULL },
};

/*
 * Scenario 4.  Mayday!  To be used with MAX_CPU_WORKERS_ORDER reduced
 * to 2.
 */
static const struct work_spec work_spec4[] = {
	{
		.id		= 0,
		.requeue_cnt	= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 5s" }},
			{ ACT_SLEEP,	{ 5000 }},
			{ ACT_REQUEUE,	{ 5000 }, NR_CPUS },
			{ ACT_TERM },
		},
	},
	{
		.id		= 1,
		.requeue_cnt	= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 5s" }},
			{ ACT_SLEEP,	{ 5000 }},
			{ ACT_REQUEUE,	{ 5000 }, NR_CPUS },
			{ ACT_TERM },
		},
	},
	{
		.id		= 2,
		.requeue_cnt	= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 5s" }},
			{ ACT_SLEEP,	{ 5000 }},
			{ ACT_REQUEUE,	{ 5000 }, NR_CPUS },
			{ ACT_TERM },
		},
	},
	{
		.id		= 3,
		.requeue_cnt	= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 5s" }},
			{ ACT_SLEEP,	{ 5000 }},
			{ ACT_REQUEUE,	{ 5000 }, NR_CPUS },
			{ ACT_TERM },
		},
	},
	{
		.id		= 4,
		.wq_id		= 2,
		.requeue_cnt	= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 1s" }},
			{ ACT_SLEEP,	{ 1000 }},
			{ ACT_REQUEUE,	{ 5000 }, NR_CPUS },
			{ ACT_TERM },
		},
	},
	{
		.id		= 5,
		.wq_id		= 2,
		.requeue_cnt	= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 1s" }},
			{ ACT_SLEEP,	{ 1000 }},
			{ ACT_REQUEUE,	{ 5000 }, NR_CPUS },
			{ ACT_TERM },
		},
	},
	{
		.id		= 6,
		.wq_id		= 2,
		.requeue_cnt	= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 1s" }},
			{ ACT_SLEEP,	{ 1000 }},
			{ ACT_REQUEUE,	{ 5000 }, NR_CPUS },
			{ ACT_TERM },
		},
	},
	{
		.id		= 7,
		.wq_id		= 2,
		.requeue_cnt	= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 1s" }},
			{ ACT_SLEEP,	{ 1000 }},
			{ ACT_REQUEUE,	{ 5000 }, NR_CPUS },
			{ ACT_TERM },
		},
	},
	{ .id = -1 },
};

static const struct test_scenario scenario4 = {
	.wq_spec		= dfl_wq_spec,
	.work_spec		=
	(const struct work_spec *[]) { work_spec4, NULL },
};

/*
 * Scenario 5.  To test cpu off/onlining.  A bunch of long running
 * tasks on cpu1.  Gets interesting with various other conditions
 * applied together - lowered MAX_CPU_WORKERS_ORDER, induced failure
 * or delay during CPU_DOWN/UP_PREPARE and so on.
 */
static const struct work_spec work_spec5[] = {
	/* runs for 30 secs */
	{
		.id		= 0,
		.cpu		= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 1,
		.cpu		= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 2,
		.cpu		= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 3,
		.cpu		= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_TERM },
		},
	},

	/* kicks in @15 and runs for 15 from wq0 */
	{
		.id		= 4,
		.cpu		= 1,
		.initial_delay	= 10000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 5,
		.cpu		= 1,
		.initial_delay	= 10000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 6,
		.cpu		= 1,
		.initial_delay	= 10000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 7,
		.cpu		= 1,
		.initial_delay	= 10000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_TERM },
		},
	},
#if 0
	/* kicks in @15 and runs for 15 from wq2 */
	{
		.id		= 8,
		.wq_id		= 2,
		.cpu		= 1,
		.initial_delay	= 15000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 15s" }},
			{ ACT_SLEEP,	{ 15000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 9,
		.wq_id		= 2,
		.cpu		= 1,
		.initial_delay	= 15000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 15s" }},
			{ ACT_SLEEP,	{ 15000 }},
			{ ACT_TERM },
		},
	},

	/* kicks in @30 and runs for 15 */
	{
		.id		= 10,
		.cpu		= 1,
		.initial_delay	= 30000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 15s" }},
			{ ACT_SLEEP,	{ 15000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 11,
		.cpu		= 1,
		.initial_delay	= 30000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 15s" }},
			{ ACT_SLEEP,	{ 15000 }},
			{ ACT_TERM },
		},
	},
#endif
	{ .id = -1 },
};

static const struct test_scenario scenario5 = {
	.wq_spec		= dfl_wq_spec,
	.work_spec		=
	(const struct work_spec *[]) { work_spec5, NULL },
};

/*
 * Scenario 6.  Scenario to test freezeable workqueue.  User should
 * freeze the machine between 0s and 9s.
 *
 * 0,1:sleep 10s
 * <-------->
 *      <--freezing--><--frozen--><-thawed
 *         2,3: sleeps for 10s
 *          <.....................-------->
 *          <.....................-------->
 */
static const struct work_spec work_spec6[] = {
	/* two works which get queued @0s and sleeps for 10s */
	{
		.id		= 0,
		.wq_id		= 3,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 1,
		.wq_id		= 3,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_TERM },
		},
	},
	/* two works which get queued @9s and sleeps for 10s */
	{
		.id		= 2,
		.wq_id		= 3,
		.initial_delay	= 9000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 3,
		.wq_id		= 3,
		.initial_delay	= 9000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 10s" }},
			{ ACT_SLEEP,	{ 10000 }},
			{ ACT_TERM },
		},
	},

	{ .id = -1 },
};

static const struct test_scenario scenario6 = {
	.wq_spec		= dfl_wq_spec,
	.work_spec		=
	(const struct work_spec *[]) { work_spec6, NULL },
};

/*
 * Scenario 7.  Scenario to test multi-colored workqueue.
 *
 *   0 1 2 3 4 5 6 7 8 9 0 1 2	: time in seconds
 * 0:  <------>				cpu0
 * 1:    <------>			cpu1
 * 2:      <------>			cpu2
 * 3:        <------>			cpu3
 * 4:          <------>			cpu0
 * 5:            <------>		cpu1
 * 6:              <------>		cpu2
 * 7:                <------>		cpu3
 * Flush workqueues
 * 10:^
 * 11:  ^
 * 12:  ^
 * 13:      ^
 * 14:        ^
 * 15:        ^
 * 16:            ^
 * 17:              ^
 * 18:              ^
 */
static const struct work_spec work_spec7[] = {
	/* 8 works - each sleeps 4sec and starts staggered */
	{
		.id		= 0,
		.wq_id		= 0,
		.cpu		= 0,
		.initial_delay	= 1000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s @ 1s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 1,
		.wq_id		= 0,
		.cpu		= 1,
		.initial_delay	= 2000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s @ 2s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 2,
		.wq_id		= 0,
		.cpu		= 2,
		.initial_delay	= 3000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s @ 3s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 3,
		.wq_id		= 0,
		.cpu		= 3,
		.initial_delay	= 4000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s @ 4s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 4,
		.wq_id		= 0,
		.cpu		= 0,
		.initial_delay	= 5000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s @ 5s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 5,
		.wq_id		= 0,
		.cpu		= 1,
		.initial_delay	= 6000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s @ 6s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 6,
		.wq_id		= 0,
		.cpu		= 2,
		.initial_delay	= 7000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s @ 7s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 7,
		.wq_id		= 0,
		.cpu		= 3,
		.initial_delay	= 8000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s @ 8s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},

	/* 9 workqueue flushers */
	{
		.id		= 10,
		.wq_id		= 1,
		.initial_delay	= 500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "flush_wq @ 0.5s" }},
			{ ACT_FLUSH_WQ,	{ 0 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 11,
		.wq_id		= 1,
		.initial_delay	= 1500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "flush_wq @ 1.5s" }},
			{ ACT_FLUSH_WQ,	{ 0 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 12,
		.wq_id		= 1,
		.initial_delay	= 1500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "flush_wq @ 1.5s" }},
			{ ACT_FLUSH_WQ,	{ 0 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 13,
		.wq_id		= 1,
		.initial_delay	= 3500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "flush_wq @ 3.5s" }},
			{ ACT_FLUSH_WQ,	{ 0 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 14,
		.wq_id		= 1,
		.initial_delay	= 4500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "flush_wq @ 4.5s" }},
			{ ACT_FLUSH_WQ,	{ 0 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 15,
		.wq_id		= 1,
		.initial_delay	= 4500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "flush_wq @ 4.5s" }},
			{ ACT_FLUSH_WQ,	{ 0 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 16,
		.wq_id		= 1,
		.initial_delay	= 6500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "flush_wq @ 6.5s" }},
			{ ACT_FLUSH_WQ,	{ 0 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 17,
		.wq_id		= 1,
		.initial_delay	= 7500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "flush_wq @ 7.5s" }},
			{ ACT_FLUSH_WQ,	{ 0 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 18,
		.wq_id		= 1,
		.initial_delay	= 7500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "flush_wq @ 7.5s" }},
			{ ACT_FLUSH_WQ,	{ 0 }},
			{ ACT_TERM },
		},
	},

	{ .id = -1 },
};

static const struct test_scenario scenario7 = {
	.wq_spec		= dfl_wq_spec,
	.work_spec		=
	(const struct work_spec *[]) { work_spec7, NULL },
};

/*
 * Scenario 8.  Scenario to test single thread workqueue.  Test with
 * freeze/thaw, suspend/resume at various points.
 *
 * 0@cpu0 <------>
 * 1@cpu1     <...--->
 * 2@cpu2         <...--->
 * 3@cpu3                  <------>
 * 4@cpu0                      <...--->
 * 5@cpu1                              <------>
 */
static const struct work_spec work_spec8[] = {
	{
		.id		= 0,
		.wq_id		= 4,
		.cpu		= 0,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s @0s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 1,
		.wq_id		= 4,
		.cpu		= 1,
		.initial_delay	= 2000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 2s @2:4s" }},
			{ ACT_SLEEP,	{ 2000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 2,
		.wq_id		= 4,
		.cpu		= 2,
		.initial_delay	= 4000,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 2s @4:6s" }},
			{ ACT_SLEEP,	{ 2000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 3,
		.wq_id		= 4,
		.cpu		= 3,
		.initial_delay	= 8500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s @8.5s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 4,
		.wq_id		= 4,
		.cpu		= 0,
		.initial_delay	= 10500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 2s @10.5:12.5s" }},
			{ ACT_SLEEP,	{ 2000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 5,
		.wq_id		= 4,
		.cpu		= 1,
		.initial_delay	= 14500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 4s @14.5s" }},
			{ ACT_SLEEP,	{ 4000 }},
			{ ACT_TERM },
		},
	},
	{ .id = -1 },
};

static const struct test_scenario scenario8 = {
	.wq_spec		= dfl_wq_spec,
	.work_spec		=
	(const struct work_spec *[]) { work_spec8, NULL },
};

/*
 * Scenario 9.  Scenario to test non-reentrant workqueue.  
 *
 *        0   2   4   6   8   10  11
 * 0@cpu0 <------>
 * 0@cpu0     <...------->			(requeued to cpu0)
 * 1@cpu0 <------>
 * 1@cpu0     <...------->			(requeued to cpu1)
 * 2@cpu1     <------>
 * 2@cpu1         <...------->			(requeued to cpu1)
 * 3@cpu1     <------>
 * 3@cpu1         <...------->			(requeued to cpu0)
 * 4@cpu0                     <-->
 * 4@cpu1                           <-->	(requeued to cpu1)
 */
static const struct work_spec work_spec9[] = {
	{
		.id		= 0,
		.wq_id		= 5,
		.cpu		= 0,
		.requeue_cnt	= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 2s, step A, target cpu0" }},
			{ ACT_SLEEP,	{ 2000 }},
			{ ACT_REQUEUE,	{ 0 }, 0 },
			{ ACT_LOG,	{ .s = "sleeping for 2s, step B" }},
			{ ACT_SLEEP,	{ 2000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 1,
		.wq_id		= 5,
		.cpu		= 0,
		.requeue_cnt	= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 2s, step A, target cpu1" }},
			{ ACT_SLEEP,	{ 2000 }},
			{ ACT_REQUEUE,	{ 0 }, 1 },
			{ ACT_LOG,	{ .s = "sleeping for 2s, step B" }},
			{ ACT_SLEEP,	{ 2000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 2,
		.wq_id		= 5,
		.cpu		= 1,
		.initial_delay	= 2000,
		.requeue_cnt	= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 2s, step A, target cpu1" }},
			{ ACT_SLEEP,	{ 2000 }},
			{ ACT_REQUEUE,	{ 1 }, 1 },
			{ ACT_LOG,	{ .s = "sleeping for 2s, step B" }},
			{ ACT_SLEEP,	{ 2000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 3,
		.wq_id		= 5,
		.cpu		= 1,
		.initial_delay	= 2000,
		.requeue_cnt	= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 2s, step A, target cpu0" }},
			{ ACT_SLEEP,	{ 2000 }},
			{ ACT_REQUEUE,	{ 1 }, 0 },
			{ ACT_LOG,	{ .s = "sleeping for 2s, step B" }},
			{ ACT_SLEEP,	{ 2000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 4,
		.wq_id		= 5,
		.cpu		= 0,
		.initial_delay	= 10000,
		.requeue_cnt	= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping for 1s, step A, target cpu1" }},
			{ ACT_SLEEP,	{ 1000 }},
			{ ACT_REQUEUE,	{ 2000 }, 1 },
			{ ACT_LOG,	{ .s = "sleeping for 1s, step B" }},
			{ ACT_SLEEP,	{ 1000 }},
			{ ACT_TERM },
		},
	},
	{ .id = -1 },
};

static const struct test_scenario scenario9 = {
	.wq_spec		= dfl_wq_spec,
	.work_spec		=
	(const struct work_spec *[]) { work_spec9, NULL },
};

/*
 * Scenario 10.  Scenario to test high priority workqueue.
 *
 *     0  0.5  1  1.5  2  |
 * 0l  <-------~~f4~~     | ->
 * 1l  <.......~~         | ~~...---->
 * 2l  <.......~~         | ~~........---->
 * 3l      <...~~         | ~~.............---->
 * 4h      <---~~         | ->
 * 5h              <---~~ | ~~-->
 * 6h              <---~~ | ~~-->
 * 7h              <---~~ | ~~-->
 */
static const struct work_spec work_spec10[] = {
	{
		.id		= 0,
		.wq_id		= 0,
		.cpu		= 0,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "burning for 1s" }},
			{ ACT_BURN,	{ 1000 }},
			{ ACT_FLUSH,	{ 4 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 1,
		.wq_id		= 0,
		.cpu		= 0,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "burning for 1s" }},
			{ ACT_BURN,	{ 1000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 2,
		.wq_id		= 0,
		.cpu		= 0,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "burning for 1s" }},
			{ ACT_BURN,	{ 1000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 3,
		.wq_id		= 0,
		.cpu		= 0,
		.initial_delay	= 500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "burning for 1s from 500ms" }},
			{ ACT_BURN,	{ 1000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 4,
		.wq_id		= 6,
		.cpu		= 0,
		.requeue_cnt	= 1,
		.initial_delay	= 500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "highpri burning for 2s from 500ms" }},
			{ ACT_BURN,	{ 2000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 5,
		.wq_id		= 6,
		.cpu		= 0,
		.requeue_cnt	= 1,
		.initial_delay	= 1500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "highpri burning for 2s from 1500ms" }},
			{ ACT_BURN,	{ 2000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 6,
		.wq_id		= 6,
		.cpu		= 0,
		.requeue_cnt	= 1,
		.initial_delay	= 1500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "highpri burning for 2s from 1500ms" }},
			{ ACT_BURN,	{ 2000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 7,
		.wq_id		= 6,
		.cpu		= 0,
		.requeue_cnt	= 1,
		.initial_delay	= 1500,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "highpri burning for 2s from 1500ms" }},
			{ ACT_BURN,	{ 2000 }},
			{ ACT_TERM },
		},
	},
	{ .id = -1 },
};

static const struct test_scenario scenario10 = {
	.wq_spec		= dfl_wq_spec,
	.work_spec		=
	(const struct work_spec *[]) { work_spec10, NULL },
};

/*
 * Scenario 11.  Scenario to test cpu intensive workqueue.
 *
 *     0      
 * 0l  <---~~--->
 * 1l  <...~~    <------>
 * 2c  <...~~            <--~~-->
 * 3c  <...~~            <--~~-->
 * 4l  <...~~            <--~~-->  
 * 5l  <...~~                ~~..------>
 * 6ch <---~~--->
 */
static const struct work_spec work_spec11[] = {
	{
		.id		= 0,
		.wq_id		= 0,
		.cpu		= 0,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "burning for 1s" }},
			{ ACT_BURN,	{ 1000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 1,
		.wq_id		= 0,
		.cpu		= 0,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "burning for 1s" }},
			{ ACT_BURN,	{ 1000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 2,
		.wq_id		= 7,
		.cpu		= 0,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "burning for 1s, cpu intensive" }},
			{ ACT_BURN,	{ 1000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 3,
		.wq_id		= 7,
		.cpu		= 0,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "burning for 1s, cpu intensive" }},
			{ ACT_BURN,	{ 1000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 4,
		.wq_id		= 0,
		.cpu		= 0,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "burning for 1s" }},
			{ ACT_BURN,	{ 1000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 5,
		.wq_id		= 0,
		.cpu		= 0,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "burning for 1s" }},
			{ ACT_BURN,	{ 1000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 6,
		.wq_id		= 8,
		.cpu		= 0,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "burning for 1s" }},
			{ ACT_BURN,	{ 1000 }},
			{ ACT_TERM },
		},
	},
	{ .id = -1 },
};

static const struct test_scenario scenario11 = {
	.wq_spec		= dfl_wq_spec,
	.work_spec		=
	(const struct work_spec *[]) { work_spec11, NULL },
};

static const struct work_spec work_spec12[] = {
	{
		.id		= 0,
		.cpu		= 1,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "burning 10s" }},
			{ ACT_BURN,	{ 10000 }},
			{ ACT_LOG,	{ .s = "done burning, sleeping 1s" }},
			{ ACT_SLEEP,	{ 1000 }},
			{ ACT_LOG,	{ .s = "burning 3s" }},
			{ ACT_BURN,	{ 3000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 1,
		.cpu		= 1,
		.initial_delay	= 100,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping 1s" }},
			{ ACT_SLEEP,	{ 1000 }},
			{ ACT_LOG,	{ .s = "burning 3s" }},
			{ ACT_BURN,	{ 3000 }},
			{ ACT_TERM },
		},
	},
	{
		.id		= 2,
		.cpu		= 1,
		.initial_delay	= 100,
		.actions	= (const struct work_action[]) {
			{ ACT_LOG,	{ .s = "sleeping 1s" }},
			{ ACT_SLEEP,	{ 1000 }},
			{ ACT_LOG,	{ .s = "burning 3s" }},
			{ ACT_BURN,	{ 3000 }},
			{ ACT_TERM },
		},
	},
	{ .id = -1 },
};

static const struct test_scenario scenario12 = {
	.wq_spec		= dfl_wq_spec,
	.work_spec		=
	(const struct work_spec *[]) { work_spec12, NULL },
};

static const struct test_scenario *scenarios[] = {
	&scenario0, &scenario1, &scenario2, &scenario3, &scenario4, &scenario5,
	&scenario6, &scenario7, &scenario8, &scenario9, &scenario10, &scenario11,
	&scenario12,
};

/*
 * Execute
 */
static struct task_struct *sequencer;
static char wq_names[MAX_WQS][MAX_WQ_NAME];
static struct workqueue_struct *wqs[MAX_WQS];
static struct delayed_work dworks[MAX_WORKS];
#ifdef CONFIG_LOCKDEP
static struct lock_class_key wq_lockdep_keys[MAX_WORKS];
static struct lock_class_key dwork_lockdep_keys[MAX_WORKS];
#endif
static const struct work_spec *work_specs[MAX_WORKS];
static bool sleeping[MAX_WORKS];
static wait_queue_head_t wait_heads[MAX_WORKS];
static int requeue_cnt[MAX_WORKS];

static void test_work_fn(struct work_struct *work)
{
	int id = to_delayed_work(work) - dworks;
	const struct work_spec *spec = work_specs[id];
	const struct work_action *act = spec->actions;
	int rc;

#define pd(lvl, fmt, args...)	\
	printk("w%02d/%04d@%d "lvl": "fmt"\n", id, current->pid, raw_smp_processor_id() , ##args);
#define plog(fmt, args...)	pd("LOG ", fmt , ##args)
#define pinfo(fmt, args...)	pd("INFO", fmt , ##args)
#define perr(fmt, args...)	pd("ERR ", fmt , ##args)
repeat:
	switch (act->action) {
	case ACT_TERM:
		pinfo("TERM");
		return;
	case ACT_LOG:
		plog("%s", act->s);
		break;
	case ACT_BURN:
		mdelay(act->v);
		break;
	case ACT_SLEEP:
		sleeping[id] = true;
		wait_event_timeout(wait_heads[id], !sleeping[id],
				   msecs_to_jiffies(act->v));
		if (!sleeping[id])
			pinfo("somebody woke me up");
		sleeping[id] = false;
		break;
	case ACT_WAKEUP:
		if (act->v < MAX_WORKS && sleeping[act->v]) {
			pinfo("waking %lu up", act->v);
			sleeping[act->v] = false;
			wake_up(&wait_heads[act->v]);
		} else
			perr("trying to wake up non-sleeping work %lu",
			     act->v);
		break;
	case ACT_REQUEUE:
		if (requeue_cnt[id] > 0 || requeue_cnt[id] < 0) {
			int delay = act->v, cpu = act->v1;

			get_online_cpus();

			if (cpu >= nr_cpu_ids || !cpu_online(cpu))
				cpu = raw_smp_processor_id();

			if (delay)
				queue_delayed_work_on(cpu, wqs[spec->wq_id],
						      &dworks[id],
						      msecs_to_jiffies(delay));
			else
				queue_work_on(cpu, wqs[spec->wq_id],
					      &dworks[id].work);

			pinfo("requeued on cpu%d delay=%dmsecs", cpu, delay);
			if (requeue_cnt[id] > 0)
				requeue_cnt[id]--;

			put_online_cpus();
		} else
			pinfo("requeue limit reached");

		break;
	case ACT_FLUSH:
		if (act->v < MAX_WORKS && work_specs[act->v]) {
			pinfo("flushing work %lu", act->v);
			rc = flush_work(&dworks[act->v].work);
			pinfo("flushed work %lu, rc=%d", act->v, rc);
		} else
			perr("trying to flush non-existent work %lu", act->v);
		break;
	case ACT_FLUSH_WQ:
		if (act->v < MAX_WQS && wqs[act->v]) {
			pinfo("flushing workqueue %lu", act->v);
			flush_workqueue(wqs[act->v]);
			pinfo("flushed workqueue %lu", act->v);
		} else
			perr("trying to flush non-existent workqueue %lu",
			     act->v);
		break;
	case ACT_CANCEL:
		if (act->v < MAX_WORKS && work_specs[act->v]) {
			pinfo("canceling work %lu", act->v);
			rc = cancel_delayed_work_sync(&dworks[act->v]);
			pinfo("canceled work %lu, rc=%d", act->v, rc);
		} else
			perr("trying to cancel non-existent work %lu", act->v);
		break;
	}
	act++;
	goto repeat;
}

#define for_each_work_spec(spec, i, scenario)				\
	for (i = 0, spec = scenario->work_spec[i]; spec;		\
	     spec = (spec + 1)->id >= 0 ? spec + 1 : scenario->work_spec[++i])

#ifdef CONFIG_WORKQUEUE_DEBUGFS
#include <linux/seq_file.h>

static bool show_work(struct seq_file *m, struct work_struct *work, bool running)
{
	struct delayed_work *dwork = to_delayed_work(work);

	if (running)
		return false;

	seq_printf(m, "test work %ld%s", dwork - dworks, running ? " R" : "");
	return true;
}
#endif

static int sequencer_thread(void *__scenario)
{
	const struct test_scenario *scenario = __scenario;
	const struct wq_spec *wq_spec;
	const struct work_spec *work_spec;
	int i, id;

	for (wq_spec = scenario->wq_spec; wq_spec->id >= 0; wq_spec++) {
		if (wq_spec->id >= MAX_WQS) {
			printk("ERR : wq id %d too high\n", wq_spec->id);
			goto err;
		}

		if (wqs[wq_spec->id]) {
			printk("ERR : wq %d already occupied\n", wq_spec->id);
			goto err;
		}

		snprintf(wq_names[wq_spec->id], MAX_WQ_NAME, "test-wq-%02d",
			 wq_spec->id);
		wqs[wq_spec->id] = __alloc_workqueue_key(wq_names[wq_spec->id],
						wq_spec->flags,
						wq_spec->max_active,
						&wq_lockdep_keys[wq_spec->id],
						wq_names[wq_spec->id]);
		if (!wqs[wq_spec->id]) {
			printk("ERR : failed create wq %d\n", wq_spec->id);
			goto err;
		}
#ifdef CONFIG_WORKQUEUE_DEBUGFS
		workqueue_set_show_work(wqs[wq_spec->id], show_work);
#endif
	}

	for_each_work_spec(work_spec, i, scenario) {
		struct delayed_work *dwork = &dworks[work_spec->id];
		struct workqueue_struct *wq = wqs[work_spec->wq_id];

		if (work_spec->id >= MAX_WORKS) {
			printk("ERR : work id %d too high\n", work_spec->id);
			goto err;
		}

		if (!wq) {
			printk("ERR : work %d references non-existent wq %d\n",
			       work_spec->id, work_spec->wq_id);
			goto err;
		}

		if (work_specs[work_spec->id]) {
			printk("ERR : work %d already initialized\n",
			       work_spec->id);
			goto err;
		}
		INIT_DELAYED_WORK(dwork, test_work_fn);
#ifdef CONFIG_LOCKDEP
		lockdep_init_map(&dwork->work.lockdep_map, "test-dwork",
				 &dwork_lockdep_keys[work_spec->id], 0);
#endif
		work_specs[work_spec->id] = work_spec;
		init_waitqueue_head(&wait_heads[work_spec->id]);
		requeue_cnt[work_spec->id] = work_spec->requeue_cnt ?: -1;
	}

	for_each_work_spec(work_spec, i, scenario) {
		struct delayed_work *dwork = &dworks[work_spec->id];
		struct workqueue_struct *wq = wqs[work_spec->wq_id];
		int cpu;

		get_online_cpus();

		if (work_spec->cpu < nr_cpu_ids && cpu_online(work_spec->cpu))
			cpu = work_spec->cpu;
		else
			cpu = raw_smp_processor_id();

		if (work_spec->initial_delay)
			queue_delayed_work_on(cpu, wq, dwork,
				msecs_to_jiffies(work_spec->initial_delay));
		else
			queue_work_on(cpu, wq, &dwork->work);

		put_online_cpus();
	}

	set_current_state(TASK_INTERRUPTIBLE);
	while (!kthread_should_stop()) {
		schedule();
		set_current_state(TASK_INTERRUPTIBLE);
	}
	set_current_state(TASK_RUNNING);

err:
	for (id = 0; id < MAX_WORKS; id++)
		if (work_specs[id])
			cancel_delayed_work_sync(&dworks[id]);
	for (id = 0; id < MAX_WQS; id++)
		if (wqs[id])
			destroy_workqueue(wqs[id]);

	set_current_state(TASK_INTERRUPTIBLE);
	while (!kthread_should_stop()) {
		schedule();
		set_current_state(TASK_INTERRUPTIBLE);
	}

	return 0;
}

static int scenario_switch = -1;
module_param_named(scenario, scenario_switch, int, 0444);

static int flush_on_down = 0;
module_param_named(flush_on_down, flush_on_down, int, 0444);

static int __cpuinit test_cpu_callback(struct notifier_block *nfb,
				       unsigned long action, void *hcpu)
{
	int id;

	action &= ~CPU_TASKS_FROZEN;

	switch (action) {
	case CPU_DOWN_PREPARE:
		if (flush_on_down) {
			printk("INFO: CPU_DOWN_PREPARE: flushing work items\n");
			for (id = 0; id < MAX_WORKS; id++)
				if (work_specs[id])
					flush_delayed_work_sync(&dworks[id]);
			printk("INFO: CPU_DOWN_PREPARE: flushing done\n");
		}
		break;
	}

	return 0;
}

static struct notifier_block test_cpu_nb __cpuinitdata =
	{ .notifier_call = test_cpu_callback };

static int __init test_init(void)
{
	if (scenario_switch < 0 || scenario_switch >= ARRAY_SIZE(scenarios)) {
		printk("TEST WQ - no such scenario\n");
		return -EINVAL;
	}

	register_cpu_notifier(&test_cpu_nb);

	printk("TEST WQ - executing scenario %d\n", scenario_switch);
	sequencer = kthread_run(sequencer_thread,
				(void *)scenarios[scenario_switch],
				"test-wq-sequencer");
	if (IS_ERR(sequencer)) {
		unregister_cpu_notifier(&test_cpu_nb);
		return PTR_ERR(sequencer);
	}
	return 0;
}

static void __exit test_exit(void)
{
	kthread_stop(sequencer);
	unregister_cpu_notifier(&test_cpu_nb);
}

module_init(test_init);
module_exit(test_exit);
MODULE_LICENSE("GPL");

Re: [PATCH 00/10] workqueue: restructure flush_workqueue() and start all flusher at the same time

[Tejun Heo]

Hello, Lai.

On Tue, Sep 25, 2012 at 05:02:43PM +0800, Lai Jiangshan wrote:
> It is not possible to remove cascading. If cascading code is
> not in flush_workqueue(), it must be in some where else.

Yeah, sure, I liked that it didn't have to be done explicitly as a
separate step.

> If you force overflow to wait for freed color before do flush(which also
> force only one flusher for one color), and force the sole flush_workqueue()
> to grab ->flush_mutex twice, we can simplify the flush_workqueue().
> (see the attached patch, it remove 100 LOC, and the cascading code becomes
> only 3 LOC). But these two forcing slow down the caller a little.

Hmmm... so, that's a lot simpler.  flush_workqueue() isn't a super-hot
code path and I don't think grabbing mutex twice is too big a deal.  I
haven't actually reviewed the code but if it can be much simpler and
thus easier to understand and verify, I might go for that.

> (And if you allow to use SRCU(which is only TWO colors), you can remove another
> 150 LOC. flush_workqueue() will become single line. But it will add some more overhead
> in flush_workqueue() because SRCU's readsite is lockless)

I'm not really following how SRCU would factor into this but
supporting multiple colors was something explicitly requested by
Linus.  The initial implementation was a lot simpler which supported
only two colors.  Linus was worried that the high possibility of
flusher clustering could lead to chaining of latencies.

Thanks.

-- 
tejun

Re: [PATCH 00/10] workqueue: restructure flush_workqueue() and start all flusher at the same time

[Lai Jiangshan]

On 09/26/2012 04:24 AM, Tejun Heo wrote:
> Hello, Lai.
> 
> On Tue, Sep 25, 2012 at 05:02:43PM +0800, Lai Jiangshan wrote:
>> It is not possible to remove cascading. If cascading code is
>> not in flush_workqueue(), it must be in some where else.
> 
> Yeah, sure, I liked that it didn't have to be done explicitly as a
> separate step.
> 
>> If you force overflow to wait for freed color before do flush(which also
>> force only one flusher for one color), and force the sole flush_workqueue()
>> to grab ->flush_mutex twice, we can simplify the flush_workqueue().
>> (see the attached patch, it remove 100 LOC, and the cascading code becomes
>> only 3 LOC). But these two forcing slow down the caller a little.
> 
> Hmmm... so, that's a lot simpler.  flush_workqueue() isn't a super-hot
> code path and I don't think grabbing mutex twice is too big a deal.  I
> haven't actually reviewed the code but if it can be much simpler and
> thus easier to understand and verify, I might go for that.

I updated it. it is attached, it forces flush_workqueue() to grab mutex twice(no other forcing).
overflow queue is implemented in a different way. This new algorithm may become our choice
likely, please review this one.

> 
>> (And if you allow to use SRCU(which is only TWO colors), you can remove another
>> 150 LOC. flush_workqueue() will become single line. But it will add some more overhead
>> in flush_workqueue() because SRCU's readsite is lockless)
> 
> I'm not really following how SRCU would factor into this but
> supporting multiple colors was something explicitly requested by
> Linus.  The initial implementation was a lot simpler which supported
> only two colors.  Linus was worried that the high possibility of
> flusher clustering could lead to chaining of latencies.
> 

I did not know this history, thank you.

But the number of colors is not essential.
"Does the algorithm chain flushers" is essential.

If we can have multiple flushers for each color. It is not chained.
If we have only one flusher for one color. It is chained. Even we have multiple
color, it is still partially chained(image we have very high frequent flush_workqueue()).

The initial implementation of flush_workqueue() is "chained" algorithm.
The initial implementation of SRCU is also "chained" algorithm.
but the current SRCU which was implemented by me is not "chained"
(I don't propose to use SRCU for flush_workqueue(), I just discuss it)

The simple version of flush_workqueue() which I sent yesterday is "chained",
because it forces overflow flushers wait for free color and forces only one
flusher for one color.

Since "not chaining" is important/essential. I sent a new draft implement today.
it uses multiple queues, one for each color(like SRCU).
this version is also simple, it remove 90 LOC.

Thanks,
Lai

This patch is still applied on top of patch7. it replaces patch8~10

 workqueue.c |  152 ++++++++++++--------------------diff --git a/kernel/workqueue.c b/kernel/workqueue.c
index be407e1..00f02ba 100644

--- a/kernel/workqueue.c
+++ b/kernel/workqueue.c
@@ -208,7 +208,6 @@ struct cpu_workqueue_struct {
  */
 struct wq_flusher {
 	struct list_head	list;		/* F: list of flushers */
-	int			flush_color;	/* F: flush color waiting for */
 	struct completion	done;		/* flush completion */
 };
 
@@ -250,9 +249,7 @@ struct workqueue_struct {
 	int			work_color;	/* F: current work color */
 	int			flush_color;	/* F: current flush color */
 	atomic_t		nr_cwqs_to_flush[WORK_NR_COLORS];
-	struct wq_flusher	*first_flusher;	/* F: first flusher */
-	struct list_head	flusher_queue;	/* F: flush waiters */
-	struct list_head	flusher_overflow; /* F: flush overflow list */
+	struct list_head	flusher[WORK_NR_COLORS]; /* F: flushers */
 
 	mayday_mask_t		mayday_mask;	/* cpus requesting rescue */
 	struct worker		*rescuer;	/* I: rescue worker */
@@ -1000,8 +997,11 @@ static void wq_dec_flusher_ref(struct workqueue_struct *wq, int color)
 	 * If this was the last reference, wake up the first flusher.
 	 * It will handle the rest.
 	 */
-	if (atomic_dec_and_test(&wq->nr_cwqs_to_flush[color]))
-		complete(&wq->first_flusher->done);
+	if (atomic_dec_and_test(&wq->nr_cwqs_to_flush[color])) {
+		BUG_ON(color != wq->flush_color);
+		complete(&list_first_entry(&wq->flusher[color],
+					   struct wq_flusher, list)->done);
+	}
 }
 
 /**
@@ -2540,27 +2540,20 @@ static void insert_wq_barrier(struct cpu_workqueue_struct *cwq,
  * becomes new flush_color and work_color is advanced by one.
  * All cwq's work_color are set to new work_color(advanced by one).
  *
- * The caller should have initialized @wq->first_flusher prior to
- * calling this function.
- *
  * CONTEXT:
  * mutex_lock(wq->flush_mutex).
- *
- * RETURNS:
- * %true if there's some cwqs to flush.  %false otherwise.
  */
-static bool workqueue_start_flush(struct workqueue_struct *wq)
+static void workqueue_start_flush(struct workqueue_struct *wq)
 {
 	int flush_color = wq->work_color;
 	int next_color = work_next_color(wq->work_color);
-	bool wait = false;
 	unsigned int cpu;
 
 	BUG_ON(next_color == wq->flush_color);
 	wq->work_color = next_color;
 
 	BUG_ON(atomic_read(&wq->nr_cwqs_to_flush[flush_color]));
-	/* this ref is held by first flusher */
+	/* this ref is held by the first flusher of previous color */
 	atomic_set(&wq->nr_cwqs_to_flush[flush_color], 1);
 
 	for_each_cwq_cpu(cpu, wq) {
@@ -2569,18 +2562,14 @@ static bool workqueue_start_flush(struct workqueue_struct *wq)
 
 		spin_lock_irq(&gcwq->lock);
 
-		if (cwq->nr_in_flight[flush_color]) {
+		if (cwq->nr_in_flight[flush_color])
 			atomic_inc(&wq->nr_cwqs_to_flush[flush_color]);
-			wait = true;
-		}
 
 		BUG_ON(next_color != work_next_color(cwq->work_color));
 		cwq->work_color = next_color;
 
 		spin_unlock_irq(&gcwq->lock);
 	}
-
-	return wait;
 }
 
 /**
@@ -2597,7 +2586,6 @@ void flush_workqueue(struct workqueue_struct *wq)
 {
 	struct wq_flusher this_flusher = {
 		.list = LIST_HEAD_INIT(this_flusher.list),
-		.flush_color = -1,
 		.done = COMPLETION_INITIALIZER_ONSTACK(this_flusher.done),
 	};
 	struct wq_flusher *next, *tmp;
@@ -2607,115 +2595,39 @@ void flush_workqueue(struct workqueue_struct *wq)
 	lock_map_release(&wq->lockdep_map);
 
 	mutex_lock(&wq->flush_mutex);
-
-	/*
-	 * Start-to-wait phase
-	 */
+	/* prepare to wait */
 	flush_color = wq->work_color;
-	next_color = work_next_color(wq->work_color);
-
-	if (next_color != wq->flush_color) {
-		/* Color space is not full */
-		BUG_ON(!list_empty(&wq->flusher_overflow));
-		this_flusher.flush_color = flush_color;
-
-		if (!wq->first_flusher) {
-			/* no flush in progress, become the first flusher */
-			BUG_ON(wq->flush_color != flush_color);
-
-			wq->first_flusher = &this_flusher;
-
-			if (!workqueue_start_flush(wq)) {
-				/* nothing to flush, done */
-				wq_dec_flusher_ref(wq, flush_color);
-				wq->flush_color = next_color;
-				wq->first_flusher = NULL;
-				goto out_unlock;
-			}
-
-			wq_dec_flusher_ref(wq, flush_color);
-		} else {
-			/* wait in queue */
-			BUG_ON(wq->flush_color == this_flusher.flush_color);
-			list_add_tail(&this_flusher.list, &wq->flusher_queue);
-			workqueue_start_flush(wq);
-		}
-	} else {
-		/*
-		 * Oops, color space is full, wait on overflow queue.
-		 * The next flush completion will assign us
-		 * flush_color and transfer to flusher_queue.
-		 */
-		list_add_tail(&this_flusher.list, &wq->flusher_overflow);
-	}
-
+	next_color = work_next_color(flush_color);
+	list_add_tail(&this_flusher.list, &wq->flusher[flush_color]);
+	/* is color enough ? */
+	if (next_color != wq->flush_color)
+		workqueue_start_flush(wq);
+	/* itself is the tip flusher */
+	if (flush_color == wq->flush_color)
+		wq_dec_flusher_ref(wq, flush_color);
 	mutex_unlock(&wq->flush_mutex);
 
 	wait_for_completion(&this_flusher.done);
-
-	/*
-	 * Wake-up-and-cascade phase
-	 *
-	 * First flushers are responsible for cascading flushes and
-	 * handling overflow.  Non-first flushers can simply return.
-	 */
-	if (wq->first_flusher != &this_flusher)
+	/* is it the first flusher of the color? */
+	if (unlikely(list_empty(&this_flusher.list)))
 		return;
 
 	mutex_lock(&wq->flush_mutex);
-
-	BUG_ON(wq->first_flusher != &this_flusher);
-	BUG_ON(!list_empty(&this_flusher.list));
-	BUG_ON(wq->flush_color != this_flusher.flush_color);
-
+	BUG_ON(flush_color != wq->flush_color);
+	list_del_init(&this_flusher.list);
 	/* complete all the flushers sharing the current flush color */
-	list_for_each_entry_safe(next, tmp, &wq->flusher_queue, list) {
-		if (next->flush_color != wq->flush_color)
-			break;
+	list_for_each_entry_safe(next, tmp, &wq->flusher[flush_color], list) {
 		list_del_init(&next->list);
 		complete(&next->done);
 	}
-
-	BUG_ON(!list_empty(&wq->flusher_overflow) &&
-	       wq->flush_color != work_next_color(wq->work_color));
-
 	/* this flush_color is finished, advance by one */
-	wq->flush_color = work_next_color(wq->flush_color);
-
-	/* one color has been freed, handle overflow queue */
-	if (!list_empty(&wq->flusher_overflow)) {
-		/*
-		 * Assign the same color to all overflowed
-		 * flushers, advance work_color and append to
-		 * flusher_queue.  This is the start-to-wait
-		 * phase for these overflowed flushers.
-		 */
-		list_for_each_entry(tmp, &wq->flusher_overflow, list)
-			tmp->flush_color = wq->work_color;
-
-		list_splice_tail_init(&wq->flusher_overflow,
-				      &wq->flusher_queue);
+	wq->flush_color = next_color;
+	/* start flush for overflowed flushers */
+	if (!list_empty(&wq->flusher[wq->work_color]))
 		workqueue_start_flush(wq);
-	}
-
-	if (list_empty(&wq->flusher_queue)) {
-		BUG_ON(wq->flush_color != wq->work_color);
-		wq->first_flusher = NULL;
-		goto out_unlock;
-	}
-
-	/*
-	 * Need to flush more colors.  Make the next flusher
-	 * the new first flusher and arm it.
-	 */
-	BUG_ON(wq->flush_color == wq->work_color);
-	BUG_ON(wq->flush_color != next->flush_color);
-
-	list_del_init(&next->list);
-	wq->first_flusher = next;
-	wq_dec_flusher_ref(wq, wq->flush_color);
-
-out_unlock:
+	/* arm next flusher */
+	if (wq->work_color != wq->flush_color)
+		wq_dec_flusher_ref(wq, next_color);
 	mutex_unlock(&wq->flush_mutex);
 }
 EXPORT_SYMBOL_GPL(flush_workqueue);
@@ -3219,10 +3131,10 @@ struct workqueue_struct *__alloc_workqueue_key(const char *fmt,
 	wq->flags = flags;
 	wq->saved_max_active = max_active;
 	mutex_init(&wq->flush_mutex);
-	for (color = 0; color < WORK_NR_COLORS; color++)
+	for (color = 0; color < WORK_NR_COLORS; color++) {
 		atomic_set(&wq->nr_cwqs_to_flush[color], 0);
-	INIT_LIST_HEAD(&wq->flusher_queue);
-	INIT_LIST_HEAD(&wq->flusher_overflow);
+		INIT_LIST_HEAD(&wq->flusher[color]);
+	}
 
 	lockdep_init_map(&wq->lockdep_map, lock_name, key, 0);
 	INIT_LIST_HEAD(&wq->list);----------------------------
 1 file changed, 32 insertions(+), 120 deletions(-)

Re: [PATCH 00/10] workqueue: restructure flush_workqueue() and start all flusher at the same time

[Tejun Heo]

Hello, Lai.

On Wed, Sep 26, 2012 at 12:48:59PM +0800, Lai Jiangshan wrote:
> > Hmmm... so, that's a lot simpler.  flush_workqueue() isn't a super-hot
> > code path and I don't think grabbing mutex twice is too big a deal.  I
> > haven't actually reviewed the code but if it can be much simpler and
> > thus easier to understand and verify, I might go for that.
> 
> I updated it. it is attached, it forces flush_workqueue() to grab
> mutex twice(no other forcing).  overflow queue is implemented in a
> different way. This new algorithm may become our choice likely,
> please review this one.

Will do shortly.

> I did not know this history, thank you.
> 
> But the number of colors is not essential.
> "Does the algorithm chain flushers" is essential.
> 
> If we can have multiple flushers for each color. It is not chained.
> If we have only one flusher for one color. It is chained. Even we
> have multiple color, it is still partially chained(image we have
> very high frequent flush_workqueue()).

If you have very few colors, you can end up merging flushes of a lot
of work items which in turn delays the next flush and thus merging
more of them.  This was what Linus was worried about.

> The initial implementation of flush_workqueue() is "chained" algorithm.

I don't know what you mean by "chained" here.  The current mainline
implementation has enough colors for most use cases and don't assign a
color to single work item.  It's specifically designed to avoid
chained latencies.

> The initial implementation of SRCU is also "chained" algorithm.
> but the current SRCU which was implemented by me is not "chained"
> (I don't propose to use SRCU for flush_workqueue(), I just discuss it)

So, you lost me.  The current implementation doesn't have a problem on
that front.

> The simple version of flush_workqueue() which I sent yesterday is "chained",
> because it forces overflow flushers wait for free color and forces only one
> flusher for one color.
>
> Since "not chaining" is important/essential. I sent a new draft implement today.
> it uses multiple queues, one for each color(like SRCU).
> this version is also simple, it remove 90 LOC.

I'll review your patch but the current implementation is enough on
that regard.  I was trying to advise against going for two-color
scheme.

Thanks.

-- 
tejun

Re: [PATCH 00/10] workqueue: restructure flush_workqueue() and start all flusher at the same time

[Tejun Heo]

Hello, again.

On Wed, Sep 26, 2012 at 09:49:58AM -0700, Tejun Heo wrote:
> > The simple version of flush_workqueue() which I sent yesterday is "chained",
> > because it forces overflow flushers wait for free color and forces only one
> > flusher for one color.
> >
> > Since "not chaining" is important/essential. I sent a new draft implement today.
> > it uses multiple queues, one for each color(like SRCU).
> > this version is also simple, it remove 90 LOC.
> 
> I'll review your patch but the current implementation is enough on
> that regard.  I was trying to advise against going for two-color
> scheme.

So, I like it.  Two things.

* I think we still want to optimize noop case.  IOW, please keep the
  early exit path for cases where there's no work item to flush.

* Can you please redo the patch series so that it doesn't go too much
  roundabout?

Thanks.

-- 
tejun