[PATCHSET] async: reimplement synchronization

[PATCHSET] async: reimplement synchronization

[Tejun Heo]

Hello, guys.

Synchronization in async got messy as more features were added and
while being converted to workqueue.  It currently has a global list of
pending async items and per-domain running lists.  Per-domain sync has
to search through the global pending list and global sync has to
iterate over all active registered domains.

This patchset reimplements async synchronization such that async items
stay on two pending lists - global and per-domain - the whole time
till completion, which simplifies both execution and synchronization.
There's no need to moving around items on execution and both domain
and global sync can look at the head of the list to determine the
lowest cookie in flight.

This patchset contains the following four patches.

 0001-async-bring-sanity-to-the-use-of-words-domain-and-ru.patch
 0002-async-use-ULLONG_MAX-for-infinity-cookie-value.patch
 0003-async-keep-pending-tasks-on-async_domain-and-remove-.patch
 0004-async-replace-list-of-active-domains-with-global-lis.patch

0001 is a prep patch.  0002 fixes a theoretical problem, which also
helps the reimplemntation.

0003-0004 reimplement synchronization.

This patch is on top of linus#master and "[PATCH] async: fix
__lowest_in_progress()"

  http://thread.gmane.org/gmane.linux.kernel/1420814/focus=1423758

Once the __lowest_in_progress() fix patch is merged, I can route this
series through a workqueue branch for 3.9.

diffstat follows.

 include/linux/async.h |    9 --
 kernel/async.c        |  151 ++++++++++++++++++--------------------------------
 2 files changed, 59 insertions(+), 101 deletions(-)

Thanks.

-- 
tejun

[PATCH 1/4] async: bring sanity to the use of words domain and running

[Tejun Heo]

>From eefff28c548fc92cd85dc2b6f22282c9400bce52 Mon Sep 17 00:00:00 2001
From: Tejun Heo <tj@kernel.org>
Date: Fri, 18 Jan 2013 16:34:15 -0800

In the beginning, running lists were literal struct list_heads.  Later
on, struct async_domain was added.  For some reason, while the
conversion substituted list_heads with async_domains, the variable
names weren't fully converted.  In more places, "running" was used for
struct async_domain while other places adopted new "domain" name.

The situation is made much worse by having async_domain's running list
named "domain" and async_entry's field pointing to async_domain named
"running".

So, we end up with mix of "running" and "domain" for variable names
for async_domain, with the field names of async_domain and async_entry
swapped between "running" and "domain".

It feels almost intentionally made to be as confusing as possible.
Bring some sanity by

* Renaming all async_domain variables "domain".

* s/async_running/async_dfl_domain/

* s/async_domain->domain/async_domain->running/

* s/async_entry->running/async_entry->domain/

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Arjan van de Ven <arjan@linux.intel.com>
Cc: Dan Williams <djbw@fb.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
---
 include/linux/async.h |  6 ++---
 kernel/async.c        | 68 +++++++++++++++++++++++++--------------------------
 2 files changed, 37 insertions(+), 37 deletions(-)

diff --git a/include/linux/async.h b/include/linux/async.h
index 7a24fe9..6f23442 100644
--- a/include/linux/async.h
+++ b/include/linux/async.h
@@ -19,7 +19,7 @@ typedef u64 async_cookie_t;
 typedef void (async_func_ptr) (void *data, async_cookie_t cookie);
 struct async_domain {
 	struct list_head node;
-	struct list_head domain;
+	struct list_head running;
 	int count;
 	unsigned registered:1;
 };
@@ -29,7 +29,7 @@ struct async_domain {
  */
 #define ASYNC_DOMAIN(_name) \
 	struct async_domain _name = { .node = LIST_HEAD_INIT(_name.node), \
-				      .domain = LIST_HEAD_INIT(_name.domain), \
+				      .running = LIST_HEAD_INIT(_name.running), \
 				      .count = 0, \
 				      .registered = 1 }
 
@@ -39,7 +39,7 @@ struct async_domain {
  */
 #define ASYNC_DOMAIN_EXCLUSIVE(_name) \
 	struct async_domain _name = { .node = LIST_HEAD_INIT(_name.node), \
-				      .domain = LIST_HEAD_INIT(_name.domain), \
+				      .running = LIST_HEAD_INIT(_name.running), \
 				      .count = 0, \
 				      .registered = 0 }
 
diff --git a/kernel/async.c b/kernel/async.c
index 8f9f5cf..c082fed 100644
--- a/kernel/async.c
+++ b/kernel/async.c
@@ -62,7 +62,7 @@ static async_cookie_t next_cookie = 1;
 #define MAX_WORK	32768
 
 static LIST_HEAD(async_pending);
-static ASYNC_DOMAIN(async_running);
+static ASYNC_DOMAIN(async_dfl_domain);
 static LIST_HEAD(async_domains);
 static DEFINE_SPINLOCK(async_lock);
 static DEFINE_MUTEX(async_register_mutex);
@@ -73,7 +73,7 @@ struct async_entry {
 	async_cookie_t		cookie;
 	async_func_ptr		*func;
 	void			*data;
-	struct async_domain	*running;
+	struct async_domain	*domain;
 };
 
 static DECLARE_WAIT_QUEUE_HEAD(async_done);
@@ -84,7 +84,7 @@ static atomic_t entry_count;
 /*
  * MUST be called with the lock held!
  */
-static async_cookie_t  __lowest_in_progress(struct async_domain *running)
+static async_cookie_t __lowest_in_progress(struct async_domain *domain)
 {
 	async_cookie_t first_running = next_cookie;	/* infinity value */
 	async_cookie_t first_pending = next_cookie;	/* ditto */
@@ -94,13 +94,13 @@ static async_cookie_t  __lowest_in_progress(struct async_domain *running)
 	 * Both running and pending lists are sorted but not disjoint.
 	 * Take the first cookies from both and return the min.
 	 */
-	if (!list_empty(&running->domain)) {
-		entry = list_first_entry(&running->domain, typeof(*entry), list);
+	if (!list_empty(&domain->running)) {
+		entry = list_first_entry(&domain->running, typeof(*entry), list);
 		first_running = entry->cookie;
 	}
 
 	list_for_each_entry(entry, &async_pending, list) {
-		if (entry->running == running) {
+		if (entry->domain == domain) {
 			first_pending = entry->cookie;
 			break;
 		}
@@ -109,13 +109,13 @@ static async_cookie_t  __lowest_in_progress(struct async_domain *running)
 	return min(first_running, first_pending);
 }
 
-static async_cookie_t  lowest_in_progress(struct async_domain *running)
+static async_cookie_t lowest_in_progress(struct async_domain *domain)
 {
 	unsigned long flags;
 	async_cookie_t ret;
 
 	spin_lock_irqsave(&async_lock, flags);
-	ret = __lowest_in_progress(running);
+	ret = __lowest_in_progress(domain);
 	spin_unlock_irqrestore(&async_lock, flags);
 	return ret;
 }
@@ -130,11 +130,11 @@ static void async_run_entry_fn(struct work_struct *work)
 	struct async_entry *pos;
 	unsigned long flags;
 	ktime_t uninitialized_var(calltime), delta, rettime;
-	struct async_domain *running = entry->running;
+	struct async_domain *domain = entry->domain;
 
 	/* 1) move self to the running queue, make sure it stays sorted */
 	spin_lock_irqsave(&async_lock, flags);
-	list_for_each_entry_reverse(pos, &running->domain, list)
+	list_for_each_entry_reverse(pos, &domain->running, list)
 		if (entry->cookie < pos->cookie)
 			break;
 	list_move_tail(&entry->list, &pos->list);
@@ -160,8 +160,8 @@ static void async_run_entry_fn(struct work_struct *work)
 	/* 3) remove self from the running queue */
 	spin_lock_irqsave(&async_lock, flags);
 	list_del(&entry->list);
-	if (running->registered && --running->count == 0)
-		list_del_init(&running->node);
+	if (domain->registered && --domain->count == 0)
+		list_del_init(&domain->node);
 
 	/* 4) free the entry */
 	kfree(entry);
@@ -173,7 +173,7 @@ static void async_run_entry_fn(struct work_struct *work)
 	wake_up(&async_done);
 }
 
-static async_cookie_t __async_schedule(async_func_ptr *ptr, void *data, struct async_domain *running)
+static async_cookie_t __async_schedule(async_func_ptr *ptr, void *data, struct async_domain *domain)
 {
 	struct async_entry *entry;
 	unsigned long flags;
@@ -199,13 +199,13 @@ static async_cookie_t __async_schedule(async_func_ptr *ptr, void *data, struct a
 	INIT_WORK(&entry->work, async_run_entry_fn);
 	entry->func = ptr;
 	entry->data = data;
-	entry->running = running;
+	entry->domain = domain;
 
 	spin_lock_irqsave(&async_lock, flags);
 	newcookie = entry->cookie = next_cookie++;
 	list_add_tail(&entry->list, &async_pending);
-	if (running->registered && running->count++ == 0)
-		list_add_tail(&running->node, &async_domains);
+	if (domain->registered && domain->count++ == 0)
+		list_add_tail(&domain->node, &async_domains);
 	atomic_inc(&entry_count);
 	spin_unlock_irqrestore(&async_lock, flags);
 
@@ -225,7 +225,7 @@ static async_cookie_t __async_schedule(async_func_ptr *ptr, void *data, struct a
  */
 async_cookie_t async_schedule(async_func_ptr *ptr, void *data)
 {
-	return __async_schedule(ptr, data, &async_running);
+	return __async_schedule(ptr, data, &async_dfl_domain);
 }
 EXPORT_SYMBOL_GPL(async_schedule);
 
@@ -233,18 +233,18 @@ EXPORT_SYMBOL_GPL(async_schedule);
  * async_schedule_domain - schedule a function for asynchronous execution within a certain domain
  * @ptr: function to execute asynchronously
  * @data: data pointer to pass to the function
- * @running: running list for the domain
+ * @domain: the domain
  *
  * Returns an async_cookie_t that may be used for checkpointing later.
- * @running may be used in the async_synchronize_*_domain() functions
- * to wait within a certain synchronization domain rather than globally.
- * A synchronization domain is specified via the running queue @running to use.
- * Note: This function may be called from atomic or non-atomic contexts.
+ * @domain may be used in the async_synchronize_*_domain() functions to
+ * wait within a certain synchronization domain rather than globally.  A
+ * synchronization domain is specified via @domain.  Note: This function
+ * may be called from atomic or non-atomic contexts.
  */
 async_cookie_t async_schedule_domain(async_func_ptr *ptr, void *data,
-				     struct async_domain *running)
+				     struct async_domain *domain)
 {
-	return __async_schedule(ptr, data, running);
+	return __async_schedule(ptr, data, domain);
 }
 EXPORT_SYMBOL_GPL(async_schedule_domain);
 
@@ -284,7 +284,7 @@ void async_unregister_domain(struct async_domain *domain)
 	mutex_lock(&async_register_mutex);
 	spin_lock_irq(&async_lock);
 	WARN_ON(!domain->registered || !list_empty(&domain->node) ||
-		!list_empty(&domain->domain));
+		!list_empty(&domain->running));
 	domain->registered = 0;
 	spin_unlock_irq(&async_lock);
 	mutex_unlock(&async_register_mutex);
@@ -293,10 +293,10 @@ EXPORT_SYMBOL_GPL(async_unregister_domain);
 
 /**
  * async_synchronize_full_domain - synchronize all asynchronous function within a certain domain
- * @domain: running list to synchronize on
+ * @domain: the domain to synchronize
  *
  * This function waits until all asynchronous function calls for the
- * synchronization domain specified by the running list @domain have been done.
+ * synchronization domain specified by @domain have been done.
  */
 void async_synchronize_full_domain(struct async_domain *domain)
 {
@@ -307,17 +307,17 @@ EXPORT_SYMBOL_GPL(async_synchronize_full_domain);
 /**
  * async_synchronize_cookie_domain - synchronize asynchronous function calls within a certain domain with cookie checkpointing
  * @cookie: async_cookie_t to use as checkpoint
- * @running: running list to synchronize on
+ * @domain: the domain to synchronize
  *
  * This function waits until all asynchronous function calls for the
- * synchronization domain specified by running list @running submitted
- * prior to @cookie have been done.
+ * synchronization domain specified by @domain submitted prior to @cookie
+ * have been done.
  */
-void async_synchronize_cookie_domain(async_cookie_t cookie, struct async_domain *running)
+void async_synchronize_cookie_domain(async_cookie_t cookie, struct async_domain *domain)
 {
 	ktime_t uninitialized_var(starttime), delta, endtime;
 
-	if (!running)
+	if (!domain)
 		return;
 
 	if (initcall_debug && system_state == SYSTEM_BOOTING) {
@@ -325,7 +325,7 @@ void async_synchronize_cookie_domain(async_cookie_t cookie, struct async_domain
 		starttime = ktime_get();
 	}
 
-	wait_event(async_done, lowest_in_progress(running) >= cookie);
+	wait_event(async_done, lowest_in_progress(domain) >= cookie);
 
 	if (initcall_debug && system_state == SYSTEM_BOOTING) {
 		endtime = ktime_get();
@@ -347,6 +347,6 @@ EXPORT_SYMBOL_GPL(async_synchronize_cookie_domain);
  */
 void async_synchronize_cookie(async_cookie_t cookie)
 {
-	async_synchronize_cookie_domain(cookie, &async_running);
+	async_synchronize_cookie_domain(cookie, &async_dfl_domain);
 }
 EXPORT_SYMBOL_GPL(async_synchronize_cookie);
-- 
1.8.0.2

[PATCH 2/4] async: use ULLONG_MAX for infinity cookie value

[Tejun Heo]

>From 25ad5d23db71cda13511f3c9c07ab0c88ece394c Mon Sep 17 00:00:00 2001
From: Tejun Heo <tj@kernel.org>
Date: Fri, 18 Jan 2013 16:34:16 -0800

Currently, next_cookie is used as the infinity value.  In most cases,
this should work fine but it theoretically could bring subtle behavior
difference between async_synchronize_full() and
async_synchronize_full_domain().

async_synchronize_full() keeps waiting until there's no registered
async_entry left regardless of what next_cookie was when the function
was called.  It guarantees that the queue is completely drained at
least once before returning.

However, async_synchronize_full_domain() doesn't.  It synchronizes
upto next_cookie and if further async jobs are queued after the
next_cookie value to synchronize is decided, they won't be waited for.

For unrelated async jobs, the behavior difference doesn't matter;
however, if async jobs which are related (nested or otherwise) to the
executing ones are queued while sychronization is in progress, the
resulting behavior difference could be problematic.

This can be easily fixed by using ULLONG_MAX as the infinity value
instead.  Define ASYNC_COOKIE_MAX as ULLONG_MAX and use it as the
infinity value for synchronization.  This makes
async_synchronize_full_domain() fully drain the domain at least once
before returning, making its behavior match async_synchronize_full().

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Arjan van de Ven <arjan@linux.intel.com>
Cc: Dan Williams <djbw@fb.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
---
 kernel/async.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

diff --git a/kernel/async.c b/kernel/async.c
index c082fed..4cb4823 100644
--- a/kernel/async.c
+++ b/kernel/async.c
@@ -59,7 +59,8 @@ asynchronous and synchronous parts of the kernel.
 
 static async_cookie_t next_cookie = 1;
 
-#define MAX_WORK	32768
+#define MAX_WORK		32768
+#define ASYNC_COOKIE_MAX	ULLONG_MAX	/* infinity cookie */
 
 static LIST_HEAD(async_pending);
 static ASYNC_DOMAIN(async_dfl_domain);
@@ -86,8 +87,8 @@ static atomic_t entry_count;
  */
 static async_cookie_t __lowest_in_progress(struct async_domain *domain)
 {
-	async_cookie_t first_running = next_cookie;	/* infinity value */
-	async_cookie_t first_pending = next_cookie;	/* ditto */
+	async_cookie_t first_running = ASYNC_COOKIE_MAX;
+	async_cookie_t first_pending = ASYNC_COOKIE_MAX;
 	struct async_entry *entry;
 
 	/*
@@ -264,7 +265,7 @@ void async_synchronize_full(void)
 			domain = list_first_entry(&async_domains, typeof(*domain), node);
 		spin_unlock_irq(&async_lock);
 
-		async_synchronize_cookie_domain(next_cookie, domain);
+		async_synchronize_cookie_domain(ASYNC_COOKIE_MAX, domain);
 	} while (!list_empty(&async_domains));
 	mutex_unlock(&async_register_mutex);
 }
@@ -300,7 +301,7 @@ EXPORT_SYMBOL_GPL(async_unregister_domain);
  */
 void async_synchronize_full_domain(struct async_domain *domain)
 {
-	async_synchronize_cookie_domain(next_cookie, domain);
+	async_synchronize_cookie_domain(ASYNC_COOKIE_MAX, domain);
 }
 EXPORT_SYMBOL_GPL(async_synchronize_full_domain);
 
-- 
1.8.0.2

[PATCH 3/4] async: keep pending tasks on async_domain and remove async_pending

[Tejun Heo]

>From e5877615929e13719fde210bc4b776bfd25c16c8 Mon Sep 17 00:00:00 2001
From: Tejun Heo <tj@kernel.org>
Date: Fri, 18 Jan 2013 16:34:16 -0800

Async kept single global pending list and per-domain running lists.
When an async item is queued, it's put on the global pending list.
The item is moved to the per-domain running list when its execution
starts.

At this point, this design complicates execution and synchronization
without bringing any benefit.  The list only matters for
synchronization which doesn't care whether a given async item is
pending or executing.  Also, global synchronization is done by
iterating through all active registered async_domains, so the global
async_pending list doesn't help anything either.

Rename async_domain->running to async_domain->pending and put async
items directly there and remove when execution completes.  This
simplifies lowest_in_progress() a lot - the first item on the pending
list is the one with the lowest cookie, and async_run_entry_fn()
doesn't have to mess with moving the item from pending to running.

After the change, whether a domain is empty or not can be trivially
determined by looking at async_domain->pending.  Remove
async_domain->count and use list_empty() on pending instead.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Arjan van de Ven <arjan@linux.intel.com>
Cc: Dan Williams <djbw@fb.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
---
 include/linux/async.h |  9 +++-----
 kernel/async.c        | 63 ++++++++++++---------------------------------------
 2 files changed, 17 insertions(+), 55 deletions(-)

diff --git a/include/linux/async.h b/include/linux/async.h
index 6f23442..849fb8c 100644
--- a/include/linux/async.h
+++ b/include/linux/async.h
@@ -19,8 +19,7 @@ typedef u64 async_cookie_t;
 typedef void (async_func_ptr) (void *data, async_cookie_t cookie);
 struct async_domain {
 	struct list_head node;
-	struct list_head running;
-	int count;
+	struct list_head pending;
 	unsigned registered:1;
 };
 
@@ -29,8 +28,7 @@ struct async_domain {
  */
 #define ASYNC_DOMAIN(_name) \
 	struct async_domain _name = { .node = LIST_HEAD_INIT(_name.node), \
-				      .running = LIST_HEAD_INIT(_name.running), \
-				      .count = 0, \
+				      .pending = LIST_HEAD_INIT(_name.pending), \
 				      .registered = 1 }
 
 /*
@@ -39,8 +37,7 @@ struct async_domain {
  */
 #define ASYNC_DOMAIN_EXCLUSIVE(_name) \
 	struct async_domain _name = { .node = LIST_HEAD_INIT(_name.node), \
-				      .running = LIST_HEAD_INIT(_name.running), \
-				      .count = 0, \
+				      .pending = LIST_HEAD_INIT(_name.pending), \
 				      .registered = 0 }
 
 extern async_cookie_t async_schedule(async_func_ptr *ptr, void *data);
diff --git a/kernel/async.c b/kernel/async.c
index 4cb4823..711fc34 100644
--- a/kernel/async.c
+++ b/kernel/async.c
@@ -62,7 +62,6 @@ static async_cookie_t next_cookie = 1;
 #define MAX_WORK		32768
 #define ASYNC_COOKIE_MAX	ULLONG_MAX	/* infinity cookie */
 
-static LIST_HEAD(async_pending);
 static ASYNC_DOMAIN(async_dfl_domain);
 static LIST_HEAD(async_domains);
 static DEFINE_SPINLOCK(async_lock);
@@ -81,42 +80,17 @@ static DECLARE_WAIT_QUEUE_HEAD(async_done);
 
 static atomic_t entry_count;
 
-
-/*
- * MUST be called with the lock held!
- */
-static async_cookie_t __lowest_in_progress(struct async_domain *domain)
-{
-	async_cookie_t first_running = ASYNC_COOKIE_MAX;
-	async_cookie_t first_pending = ASYNC_COOKIE_MAX;
-	struct async_entry *entry;
-
-	/*
-	 * Both running and pending lists are sorted but not disjoint.
-	 * Take the first cookies from both and return the min.
-	 */
-	if (!list_empty(&domain->running)) {
-		entry = list_first_entry(&domain->running, typeof(*entry), list);
-		first_running = entry->cookie;
-	}
-
-	list_for_each_entry(entry, &async_pending, list) {
-		if (entry->domain == domain) {
-			first_pending = entry->cookie;
-			break;
-		}
-	}
-
-	return min(first_running, first_pending);
-}
-
 static async_cookie_t lowest_in_progress(struct async_domain *domain)
 {
+	async_cookie_t ret = ASYNC_COOKIE_MAX;
 	unsigned long flags;
-	async_cookie_t ret;
 
 	spin_lock_irqsave(&async_lock, flags);
-	ret = __lowest_in_progress(domain);
+	if (!list_empty(&domain->pending)) {
+		struct async_entry *first = list_first_entry(&domain->pending,
+						struct async_entry, list);
+		ret = first->cookie;
+	}
 	spin_unlock_irqrestore(&async_lock, flags);
 	return ret;
 }
@@ -128,20 +102,11 @@ static void async_run_entry_fn(struct work_struct *work)
 {
 	struct async_entry *entry =
 		container_of(work, struct async_entry, work);
-	struct async_entry *pos;
 	unsigned long flags;
 	ktime_t uninitialized_var(calltime), delta, rettime;
 	struct async_domain *domain = entry->domain;
 
-	/* 1) move self to the running queue, make sure it stays sorted */
-	spin_lock_irqsave(&async_lock, flags);
-	list_for_each_entry_reverse(pos, &domain->running, list)
-		if (entry->cookie < pos->cookie)
-			break;
-	list_move_tail(&entry->list, &pos->list);
-	spin_unlock_irqrestore(&async_lock, flags);
-
-	/* 2) run (and print duration) */
+	/* 1) run (and print duration) */
 	if (initcall_debug && system_state == SYSTEM_BOOTING) {
 		printk(KERN_DEBUG "calling  %lli_%pF @ %i\n",
 			(long long)entry->cookie,
@@ -158,19 +123,19 @@ static void async_run_entry_fn(struct work_struct *work)
 			(long long)ktime_to_ns(delta) >> 10);
 	}
 
-	/* 3) remove self from the running queue */
+	/* 2) remove self from the pending queues */
 	spin_lock_irqsave(&async_lock, flags);
 	list_del(&entry->list);
-	if (domain->registered && --domain->count == 0)
+	if (domain->registered && list_empty(&domain->pending))
 		list_del_init(&domain->node);
 
-	/* 4) free the entry */
+	/* 3) free the entry */
 	kfree(entry);
 	atomic_dec(&entry_count);
 
 	spin_unlock_irqrestore(&async_lock, flags);
 
-	/* 5) wake up any waiters */
+	/* 4) wake up any waiters */
 	wake_up(&async_done);
 }
 
@@ -204,9 +169,9 @@ static async_cookie_t __async_schedule(async_func_ptr *ptr, void *data, struct a
 
 	spin_lock_irqsave(&async_lock, flags);
 	newcookie = entry->cookie = next_cookie++;
-	list_add_tail(&entry->list, &async_pending);
-	if (domain->registered && domain->count++ == 0)
+	if (domain->registered && list_empty(&domain->pending))
 		list_add_tail(&domain->node, &async_domains);
+	list_add_tail(&entry->list, &domain->pending);
 	atomic_inc(&entry_count);
 	spin_unlock_irqrestore(&async_lock, flags);
 
@@ -285,7 +250,7 @@ void async_unregister_domain(struct async_domain *domain)
 	mutex_lock(&async_register_mutex);
 	spin_lock_irq(&async_lock);
 	WARN_ON(!domain->registered || !list_empty(&domain->node) ||
-		!list_empty(&domain->running));
+		!list_empty(&domain->pending));
 	domain->registered = 0;
 	spin_unlock_irq(&async_lock);
 	mutex_unlock(&async_register_mutex);
-- 
1.8.0.2

[PATCH 4/4] async: replace list of active domains with global list of pending items

[Tejun Heo]

>From 0e18802ed054fc97026973e94a58f0b9beb1b294 Mon Sep 17 00:00:00 2001
From: Tejun Heo <tj@kernel.org>
Date: Fri, 18 Jan 2013 16:34:16 -0800

Global synchronization - async_synchronize_full() - is currently
implemented by keeping a list of all active registered domains and
syncing them one by one until no domain is active.

While this isn't necessarily a complex scheme, it can easily be
simplified by keeping global list of the pending items of all
registered active domains instead of list of domains and simply using
the globl pending list the same way as domain syncing.

This patch replaces async_domains with async_global_pending and update
lowest_in_progress() to use the global pending list if @domain is
%NULL.  async_synchronize_full_domain(NULL) is now allowed and
equivalent to async_synchronize_full().  As no one is calling with
NULL domain, this doesn't affect any existing users.

async_register_mutex is no longer necessary and dropped.

Signed-off-by: Tejun Heo <tj@kernel.org>
Cc: Arjan van de Ven <arjan@linux.intel.com>
Cc: Dan Williams <djbw@fb.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
---
 kernel/async.c | 63 +++++++++++++++++++++++++++-------------------------------
 1 file changed, 29 insertions(+), 34 deletions(-)

diff --git a/kernel/async.c b/kernel/async.c
index 711fc34..ddc59fd 100644
--- a/kernel/async.c
+++ b/kernel/async.c
@@ -62,13 +62,13 @@ static async_cookie_t next_cookie = 1;
 #define MAX_WORK		32768
 #define ASYNC_COOKIE_MAX	ULLONG_MAX	/* infinity cookie */
 
+static LIST_HEAD(async_global_pending);	/* pending from all registered doms */
 static ASYNC_DOMAIN(async_dfl_domain);
-static LIST_HEAD(async_domains);
 static DEFINE_SPINLOCK(async_lock);
-static DEFINE_MUTEX(async_register_mutex);
 
 struct async_entry {
-	struct list_head	list;
+	struct list_head	domain_list;
+	struct list_head	global_list;
 	struct work_struct	work;
 	async_cookie_t		cookie;
 	async_func_ptr		*func;
@@ -82,15 +82,25 @@ static atomic_t entry_count;
 
 static async_cookie_t lowest_in_progress(struct async_domain *domain)
 {
+	struct async_entry *first = NULL;
 	async_cookie_t ret = ASYNC_COOKIE_MAX;
 	unsigned long flags;
 
 	spin_lock_irqsave(&async_lock, flags);
-	if (!list_empty(&domain->pending)) {
-		struct async_entry *first = list_first_entry(&domain->pending,
-						struct async_entry, list);
-		ret = first->cookie;
+
+	if (domain) {
+		if (!list_empty(&domain->pending))
+			first = list_first_entry(&domain->pending,
+					struct async_entry, domain_list);
+	} else {
+		if (!list_empty(&async_global_pending))
+			first = list_first_entry(&async_global_pending,
+					struct async_entry, global_list);
 	}
+
+	if (first)
+		ret = first->cookie;
+
 	spin_unlock_irqrestore(&async_lock, flags);
 	return ret;
 }
@@ -104,7 +114,6 @@ static void async_run_entry_fn(struct work_struct *work)
 		container_of(work, struct async_entry, work);
 	unsigned long flags;
 	ktime_t uninitialized_var(calltime), delta, rettime;
-	struct async_domain *domain = entry->domain;
 
 	/* 1) run (and print duration) */
 	if (initcall_debug && system_state == SYSTEM_BOOTING) {
@@ -125,9 +134,8 @@ static void async_run_entry_fn(struct work_struct *work)
 
 	/* 2) remove self from the pending queues */
 	spin_lock_irqsave(&async_lock, flags);
-	list_del(&entry->list);
-	if (domain->registered && list_empty(&domain->pending))
-		list_del_init(&domain->node);
+	list_del_init(&entry->domain_list);
+	list_del_init(&entry->global_list);
 
 	/* 3) free the entry */
 	kfree(entry);
@@ -168,10 +176,14 @@ static async_cookie_t __async_schedule(async_func_ptr *ptr, void *data, struct a
 	entry->domain = domain;
 
 	spin_lock_irqsave(&async_lock, flags);
+
+	/* allocate cookie and queue */
 	newcookie = entry->cookie = next_cookie++;
-	if (domain->registered && list_empty(&domain->pending))
-		list_add_tail(&domain->node, &async_domains);
-	list_add_tail(&entry->list, &domain->pending);
+
+	list_add_tail(&entry->domain_list, &domain->pending);
+	if (domain->registered)
+		list_add_tail(&entry->global_list, &async_global_pending);
+
 	atomic_inc(&entry_count);
 	spin_unlock_irqrestore(&async_lock, flags);
 
@@ -221,18 +233,7 @@ EXPORT_SYMBOL_GPL(async_schedule_domain);
  */
 void async_synchronize_full(void)
 {
-	mutex_lock(&async_register_mutex);
-	do {
-		struct async_domain *domain = NULL;
-
-		spin_lock_irq(&async_lock);
-		if (!list_empty(&async_domains))
-			domain = list_first_entry(&async_domains, typeof(*domain), node);
-		spin_unlock_irq(&async_lock);
-
-		async_synchronize_cookie_domain(ASYNC_COOKIE_MAX, domain);
-	} while (!list_empty(&async_domains));
-	mutex_unlock(&async_register_mutex);
+	async_synchronize_full_domain(NULL);
 }
 EXPORT_SYMBOL_GPL(async_synchronize_full);
 
@@ -247,13 +248,10 @@ EXPORT_SYMBOL_GPL(async_synchronize_full);
  */
 void async_unregister_domain(struct async_domain *domain)
 {
-	mutex_lock(&async_register_mutex);
 	spin_lock_irq(&async_lock);
-	WARN_ON(!domain->registered || !list_empty(&domain->node) ||
-		!list_empty(&domain->pending));
+	WARN_ON(!domain->registered || !list_empty(&domain->pending));
 	domain->registered = 0;
 	spin_unlock_irq(&async_lock);
-	mutex_unlock(&async_register_mutex);
 }
 EXPORT_SYMBOL_GPL(async_unregister_domain);
 
@@ -273,7 +271,7 @@ EXPORT_SYMBOL_GPL(async_synchronize_full_domain);
 /**
  * async_synchronize_cookie_domain - synchronize asynchronous function calls within a certain domain with cookie checkpointing
  * @cookie: async_cookie_t to use as checkpoint
- * @domain: the domain to synchronize
+ * @domain: the domain to synchronize (%NULL for all registered domains)
  *
  * This function waits until all asynchronous function calls for the
  * synchronization domain specified by @domain submitted prior to @cookie
@@ -283,9 +281,6 @@ void async_synchronize_cookie_domain(async_cookie_t cookie, struct async_domain
 {
 	ktime_t uninitialized_var(starttime), delta, endtime;
 
-	if (!domain)
-		return;
-
 	if (initcall_debug && system_state == SYSTEM_BOOTING) {
 		printk(KERN_DEBUG "async_waiting @ %i\n", task_pid_nr(current));
 		starttime = ktime_get();
-- 
1.8.0.2

Re: [PATCHSET] async: reimplement synchronization

[Tejun Heo]

On Fri, Jan 18, 2013 at 04:39:23PM -0800, Tejun Heo wrote:
> Synchronization in async got messy as more features were added and
> while being converted to workqueue.  It currently has a global list of
> pending async items and per-domain running lists.  Per-domain sync has
> to search through the global pending list and global sync has to
> iterate over all active registered domains.
> 
> This patchset reimplements async synchronization such that async items
> stay on two pending lists - global and per-domain - the whole time
> till completion, which simplifies both execution and synchronization.
> There's no need to moving around items on execution and both domain
> and global sync can look at the head of the list to determine the
> lowest cookie in flight.

Applied to wq/for-3.9-async.  Thanks.

-- 
tejun

Re: [PATCH 4/4] async: replace list of active domains with global list of pending items

[James Hogan]

Hi,

On Fri, Jan 18, 2013 at 04:41:00PM -0800, Tejun Heo wrote:
> @@ -125,9 +134,8 @@ static void async_run_entry_fn(struct work_struct *work)
>  
>  	/* 2) remove self from the pending queues */
>  	spin_lock_irqsave(&async_lock, flags);
> -	list_del(&entry->list);
> -	if (domain->registered && list_empty(&domain->pending))
> -		list_del_init(&domain->node);
> +	list_del_init(&entry->domain_list);
> +	list_del_init(&entry->global_list);

this unconditionally unlinks the global_list entry, however...

>  
>  	/* 3) free the entry */
>  	kfree(entry);
> @@ -168,10 +176,14 @@ static async_cookie_t __async_schedule(async_func_ptr *ptr, void *data, struct a
>  	entry->domain = domain;
>  
>  	spin_lock_irqsave(&async_lock, flags);
> +
> +	/* allocate cookie and queue */
>  	newcookie = entry->cookie = next_cookie++;
> -	if (domain->registered && list_empty(&domain->pending))
> -		list_add_tail(&domain->node, &async_domains);
> -	list_add_tail(&entry->list, &domain->pending);
> +
> +	list_add_tail(&entry->domain_list, &domain->pending);
> +	if (domain->registered)
> +		list_add_tail(&entry->global_list, &async_global_pending);

if (!domain->registered) then entry->global_list will have NULL pointers
from the kzalloc, so the list_del_init above will crash.

Should it have this?
+	else
+		INIT_LIST_HEAD(&entry->global_list)

Cheers
James

Re: [PATCH 4/4] async: replace list of active domains with global list of pending items

[Tejun Heo]

Hello,

On Fri, Jan 25, 2013 at 12:13:45AM +0000, James Hogan wrote:
> Should it have this?
> +	else
> +		INIT_LIST_HEAD(&entry->global_list)

I think it would be better to have INIT_LIST_HEAD() during @entry
initialization.  Heh, I forgot that.  I wonder why it didn't crash on
my machine.  Can you please cook up a patch to init both list fields
right after kzalloc()?

Thanks.

-- 
tejun

Re: [PATCH 4/4] async: replace list of active domains with global list of pending items

[James Hogan]

On 25 January 2013 01:01, Tejun Heo <tj@kernel.org> wrote:
> Hello,
>
> On Fri, Jan 25, 2013 at 12:13:45AM +0000, James Hogan wrote:
>> Should it have this?
>> +     else
>> +             INIT_LIST_HEAD(&entry->global_list)
>
> I think it would be better to have INIT_LIST_HEAD() during @entry
> initialization.  Heh, I forgot that.  I wonder why it didn't crash on
> my machine.  Can you please cook up a patch to init both list fields
> right after kzalloc()?

How does the following patch look? Feel free to squash it into the
original to avoid breaking bisection :).

Cheers
James


From: James Hogan <james.hogan@imgtec.com>
Date: Fri, 25 Jan 2013 09:46:58 +0000
Subject: [PATCH 1/1] async: initialise list heads to fix crash

The commit "async: replace list of active domains with global list of
pending items" added a struct list_head global_list in struct
async_entry, which isn't initialised. This means that if
!domain->registered at __async_schedule(), then list_del_init() will be
called on the list head in async_run_entry_fn with both pointers NULL,
causing a crash. This is fixed by initialising both the global_list and
domain_list list_heads after kzalloc'ing the entry.

This was noticed due to dapm_power_widgets() which uses
ASYNC_DOMAIN_EXCLUSIVE, which initialises the domain->registered to 0.

Signed-off-by: James Hogan <james.hogan@imgtec.com>
---
 kernel/async.c |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

diff --git a/kernel/async.c b/kernel/async.c
index 6958000..8ddee2c 100644
--- a/kernel/async.c
+++ b/kernel/async.c
@@ -172,6 +172,8 @@ static async_cookie_t
__async_schedule(async_func_ptr *ptr, void *data, struct a
 		ptr(data, newcookie);
 		return newcookie;
 	}
+	INIT_LIST_HEAD(&entry->domain_list);
+	INIT_LIST_HEAD(&entry->global_list);
 	INIT_WORK(&entry->work, async_run_entry_fn);
 	entry->func = ptr;
 	entry->data = data;
-- 
1.7.7.6

Re: [PATCH 4/4] async: replace list of active domains with global list of pending items

[James Hogan]

On 25 January 2013 10:08, James Hogan <james@albanarts.com> wrote:
> On 25 January 2013 01:01, Tejun Heo <tj@kernel.org> wrote:
>> Hello,
>>
>> On Fri, Jan 25, 2013 at 12:13:45AM +0000, James Hogan wrote:
>>> Should it have this?
>>> +     else
>>> +             INIT_LIST_HEAD(&entry->global_list)
>>
>> I think it would be better to have INIT_LIST_HEAD() during @entry
>> initialization.  Heh, I forgot that.  I wonder why it didn't crash on
>> my machine.  Can you please cook up a patch to init both list fields
>> right after kzalloc()?
>
> How does the following patch look? Feel free to squash it into the
> original to avoid breaking bisection :).

Sorry, gmail has screwed with the patch. I'll send separately.

Cheers
James

[PATCH 1/1] async: initialise list heads to fix crash

[James Hogan]

The commit "async: replace list of active domains with global list of
pending items" added a struct list_head global_list in struct
async_entry, which isn't initialised. This means that if
!domain->registered at __async_schedule(), then list_del_init() will be
called on the list head in async_run_entry_fn with both pointers NULL,
causing a crash. This is fixed by initialising both the global_list and
domain_list list_heads after kzalloc'ing the entry.

This was noticed due to dapm_power_widgets() which uses
ASYNC_DOMAIN_EXCLUSIVE, which initialises the domain->registered to 0.

Signed-off-by: James Hogan <james.hogan@imgtec.com>
---
 kernel/async.c |    2 ++
 1 files changed, 2 insertions(+), 0 deletions(-)

diff --git a/kernel/async.c b/kernel/async.c
index 6958000..8ddee2c 100644
--- a/kernel/async.c
+++ b/kernel/async.c
@@ -172,6 +172,8 @@ static async_cookie_t __async_schedule(async_func_ptr *ptr, void *data, struct a
 		ptr(data, newcookie);
 		return newcookie;
 	}
+	INIT_LIST_HEAD(&entry->domain_list);
+	INIT_LIST_HEAD(&entry->global_list);
 	INIT_WORK(&entry->work, async_run_entry_fn);
 	entry->func = ptr;
 	entry->data = data;
-- 
1.7.7.6

Re: [PATCH 1/1] async: initialise list heads to fix crash

[Tejun Heo]

On Fri, Jan 25, 2013 at 10:13:59AM +0000, James Hogan wrote:
> The commit "async: replace list of active domains with global list of
> pending items" added a struct list_head global_list in struct
> async_entry, which isn't initialised. This means that if
> !domain->registered at __async_schedule(), then list_del_init() will be
> called on the list head in async_run_entry_fn with both pointers NULL,
> causing a crash. This is fixed by initialising both the global_list and
> domain_list list_heads after kzalloc'ing the entry.
> 
> This was noticed due to dapm_power_widgets() which uses
> ASYNC_DOMAIN_EXCLUSIVE, which initialises the domain->registered to 0.
> 
> Signed-off-by: James Hogan <james.hogan@imgtec.com>

Applied wq/for-3.9-async.

Thanks!

-- 
tejun