async: reimplement synchronization
PATCH 1/1 async: reimplement synchronization
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.
Signature · 1 line
tejun
PATCH 1/4 async: bring sanity to the use of words domain and running
Quoted 1 line
From
eefff28c548fc92cd85dc2b6f22282c9400bce52Mon Sep 17 00:00:00 2001
From: Tejun Heo <[email protected]>
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/
--- include/linux/async.h | 6 ++--- kernel/async.c | 68 +++++++++++++++++++++++++-------------------------- 2 files changed, 37 insertions(+), 37 deletions(-)
include/linux/async.h +3 -3
@@ -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 }
kernel/async.c +34 -34
192 lines not on this page · raw message
Signature · 1 line
1.8.0.2
PATCH 2/4 async: use ULLONG_MAX for infinity cookie value
In reply to Tejun HeoQuoted 1 line
From
25ad5d23db71cda13511f3c9c07ab0c88ece394cMon Sep 17 00:00:00 2001
From: Tejun Heo <[email protected]>
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().
--- kernel/async.c | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-)
kernel/async.c +6 -5
@@ -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);
Signature · 1 line
1.8.0.2
PATCH 3/4 async: keep pending tasks on async_domain and remove async_pending
In reply to Tejun HeoQuoted 1 line
From
e5877615929e13719fde210bc4b776bfd25c16c8Mon Sep 17 00:00:00 2001
From: Tejun Heo <[email protected]>
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.
--- include/linux/async.h | 9 +++----- kernel/async.c | 63 ++++++++++++--------------------------------------- 2 files changed, 17 insertions(+), 55 deletions(-)
include/linux/async.h +3 -6
@@ -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);
kernel/async.c +14 -49
118 lines not on this page · raw message
Signature · 1 line
1.8.0.2
PATCH 4/4 async: replace list of active domains with global list of pending items
In reply to Tejun HeoQuoted 1 line
From
0e18802ed054fc97026973e94a58f0b9beb1b294Mon Sep 17 00:00:00 2001
From: Tejun Heo <[email protected]>
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.
--- kernel/async.c | 63 +++++++++++++++++++++++++++------------------------------- 1 file changed, 29 insertions(+), 34 deletions(-)
kernel/async.c +29 -34
@@ -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 ();
Signature · 1 line
1.8.0.2
Re: [PATCH 4/4] async: replace list of active domains with global list of pending items
Hi,
kernel/async.c static void async_run_entry_fn(struct work_struct *work) · line 138
Quoted 9 lines · Tejun Heo
kernel/async.c +2
-3@@ -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...
Quoted 7 lines
kernel/async.c +0
-0/* 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);
kernel/async.c static async_cookie_t __async_schedule(async_func_ptr *ptr, void *data, struct a · line 185
Quoted 10 lines
kernel/async.c +6
-3+ +/* 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
Hello,
Review
Quoted 3 lines · James Hogan
Should it have this?
(quoted diff) +2
-0+ 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.
Signature · 1 line
tejun
Re: [PATCH 4/4] async: replace list of active domains with global list of pending items
Quoted 11 lines · Tejun Heo
Hello,
Review
Quoted 3 lines · James Hogan
Should it have this?
(quoted diff) +2
-0+ 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 afterkzalloc()?
How does the following patch look? Feel free to squash it into the original to avoid breaking bisection :).
Cheers
James
From: James Hogan <[email protected]>
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.
--- kernel/async.c | 2 ++ 1 files changed, 2 insertions(+), 0 deletions(-)
kernel/async.c +0 -0
@@ -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;
Signature · 1 line
1.7.7.6
Re: [PATCH 4/4] async: replace list of active domains with global list of pending items
Quoted 8 lines · James Hogan
Quoted 7 lines · Tejun Heo
Hello,
Quoted 3 lines · James Hogan
Should it have this?
(quoted diff) +2
-0+ else + INIT_LIST_HEAD(&entry->global_list)
Quoted 7 lines
Quoted 4 lines
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 afterkzalloc()?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
In reply to Tejun HeoThe 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.
--- kernel/async.c | 2 ++ 1 files changed, 2 insertions(+), 0 deletions(-)
kernel/async.c +2 -0
@@ -172,6 +172,8 @@ static async_cookie_t __async_schedule(async_func_ptr *ptr, void *data, struct aptr (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;
Signature · 1 line
1.7.7.6
Re: [PATCH 1/1] async: initialise list heads to fix crash
Quoted 8 lines · James Hogan
The commit "async: replace list of active domains with global list of pending items" added a struct
list_headglobal_listin structasync_entry, which isn't initialised. This means that if !domain->registered at__async_schedule(), thenlist_del_init()will be called on the list head inasync_run_entry_fnwith both pointers NULL, causing a crash. This is fixed by initialising both theglobal_listanddomain_listlist_headsafter kzalloc'ing the entry.
Quoted 4 lines
This was noticed due to
dapm_power_widgets()which usesASYNC_DOMAIN_EXCLUSIVE, which initialises thedomain->registeredto 0.Signed-off-by James Hogan <[email protected]>
Applied wq/for-3.9-async.
Thanks!
Signature · 1 line
tejun
Tejun Heo
AppliedQuoted 6 lines · Tejun Heo
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.
Quoted 6 lines
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.
Signature · 1 line
tejun