It's worth reporting wait-event circular dependency even if it doesn't lead to an actual deadlock, because it's a good information about a circular dependency anyway. However, it should be suppressed once turning out it doesn't lead an actual deadlock, for instance, there are other wake-up(or event) paths.
The report needs to be suppressed by annotating that an event can be recovered by other sites triggering the desired wake-up, using a newly introduced API, dept_recover_event() specifying an event site and its recover site.
By the introduction, need of a new type of dependency tracking arises since a loop of recover dependency could trigger another type of deadlock. So implement a logic to track the new type of dependency between multi event sites for a single wait.
Lastly, to make sure that recover sites must be used in code, introduce a section '.dept.event_sites' to mark it as 'used' only if used in code, and warn it if dept_recover_event()s are annotated with recover sites, not used in code.
Signed-off-by: Byungchul Park byungchul@sk.com --- include/asm-generic/vmlinux.lds.h | 13 +- include/linux/dept.h | 91 ++++++++++++++ kernel/dependency/dept.c | 196 ++++++++++++++++++++++++++++++ 3 files changed, 299 insertions(+), 1 deletion(-)
diff --git a/include/asm-generic/vmlinux.lds.h b/include/asm-generic/vmlinux.lds.h index a464ff6c1a61..2680f85b677a 100644 --- a/include/asm-generic/vmlinux.lds.h +++ b/include/asm-generic/vmlinux.lds.h @@ -717,6 +717,16 @@ #define KERNEL_CTORS() #endif
+#ifdef CONFIG_DEPT +#define DEPT_EVNET_SITES_USED() \ + . = ALIGN(8); \ + __dept_event_sites_start = .; \ + KEEP(*(.dept.event_sites)) \ + __dept_event_sites_end = .; +#else +#define DEPT_EVNET_SITES_USED() +#endif + /* init and exit section handling */ #define INIT_DATA \ KEEP(*(SORT(___kentry+*))) \ @@ -741,7 +751,8 @@ EARLYCON_TABLE() \ LSM_TABLE() \ EARLY_LSM_TABLE() \ - KUNIT_INIT_TABLE() + KUNIT_INIT_TABLE() \ + DEPT_EVNET_SITES_USED()
#define INIT_TEXT \ *(.init.text .init.text.*) \ diff --git a/include/linux/dept.h b/include/linux/dept.h index 8b41f7a65abb..44083e6651ab 100644 --- a/include/linux/dept.h +++ b/include/linux/dept.h @@ -142,6 +142,82 @@ struct dept_ext_wgen { unsigned int wgen; };
+struct dept_event_site { + /* + * event site name + */ + const char *name; + + /* + * function name where the event is triggered in + */ + const char *func_name; + + /* + * for associating its recover dependencies + */ + struct list_head dep_head; + struct list_head dep_rev_head; + + /* + * for BFS + */ + unsigned int bfs_gen; + struct dept_event_site *bfs_parent; + struct list_head bfs_node; + + /* + * flag indicating the event is not only declared but also + * actually used in code + */ + bool used; +}; + +struct dept_event_site_dep { + struct dept_event_site *evt_site; + struct dept_event_site *recover_site; + + /* + * for linking to dept_event objects + */ + struct list_head dep_node; + struct list_head dep_rev_node; +}; + +#define DEPT_EVENT_SITE_INITIALIZER(es) \ +{ \ + .name = #es, \ + .func_name = NULL, \ + .dep_head = LIST_HEAD_INIT((es).dep_head), \ + .dep_rev_head = LIST_HEAD_INIT((es).dep_rev_head), \ + .bfs_gen = 0, \ + .bfs_parent = NULL, \ + .bfs_node = LIST_HEAD_INIT((es).bfs_node), \ + .used = false, \ +} + +#define DEPT_EVENT_SITE_DEP_INITIALIZER(esd) \ +{ \ + .evt_site = NULL, \ + .recover_site = NULL, \ + .dep_node = LIST_HEAD_INIT((esd).dep_node), \ + .dep_rev_node = LIST_HEAD_INIT((esd).dep_rev_node), \ +} + +struct dept_event_site_init { + struct dept_event_site *evt_site; + const char *func_name; +}; + +#define dept_event_site_used(es) \ +do { \ + static struct dept_event_site_init _evtinit __initdata = \ + { .evt_site = (es), .func_name = __func__ }; \ + static struct dept_event_site_init *_evtinitp __used \ + __attribute__((__section__(".dept.event_sites"))) = \ + &_evtinit; \ +} while (0) + extern void dept_stop_emerg(void); extern void dept_on(void); extern void dept_off(void); @@ -179,6 +255,14 @@ static inline void dept_ecxt_enter_nokeep(struct dept_map *m) extern void dept_key_init(struct dept_key *k); extern void dept_key_destroy(struct dept_key *k); extern void dept_map_ecxt_modify(struct dept_map *m, unsigned long e_f, struct dept_key *new_k, unsigned long new_e_f, unsigned long new_ip, const char *new_c_fn, const char *new_e_fn, int new_sub_l); +extern void __dept_recover_event(struct dept_event_site_dep *esd, struct dept_event_site *es, struct dept_event_site *rs); + +#define dept_recover_event(es, rs) \ +do { \ + static struct dept_event_site_dep _esd = DEPT_EVENT_SITE_DEP_INITIALIZER(_esd);\ + \ + __dept_recover_event(&_esd, es, rs); \ +} while (0)
extern void dept_softirq_enter(void); extern void dept_hardirq_enter(void); @@ -192,8 +276,10 @@ extern void dept_hardirqs_off(void); struct dept_key { }; struct dept_map { }; struct dept_ext_wgen { }; +struct dept_event_site { };
#define DEPT_MAP_INITIALIZER(n, k) { } +#define DEPT_EVENT_SITE_INITIALIZER(es) { }
#define dept_stop_emerg() do { } while (0) #define dept_on() do { } while (0) @@ -224,6 +310,7 @@ struct dept_ext_wgen { }; #define dept_key_init(k) do { (void)(k); } while (0) #define dept_key_destroy(k) do { (void)(k); } while (0) #define dept_map_ecxt_modify(m, e_f, n_k, n_e_f, n_ip, n_c_fn, n_e_fn, n_sl) do { (void)(n_k); (void)(n_c_fn); (void)(n_e_fn); } while (0) +#define dept_recover_event(es, rs) do { } while (0)
#define dept_softirq_enter() do { } while (0) #define dept_hardirq_enter() do { } while (0) @@ -234,4 +321,8 @@ struct dept_ext_wgen { };
#define dept_set_lockdep_map(m, lockdep_m) do { } while (0) #endif + +#define DECLARE_DEPT_EVENT_SITE(es) extern struct dept_event_site (es) +#define DEFINE_DEPT_EVENT_SITE(es) struct dept_event_site (es) = DEPT_EVENT_SITE_INITIALIZER(es) + #endif /* __LINUX_DEPT_H */ diff --git a/kernel/dependency/dept.c b/kernel/dependency/dept.c index 1de61306418b..b14400c4f83b 100644 --- a/kernel/dependency/dept.c +++ b/kernel/dependency/dept.c @@ -973,6 +973,117 @@ static void bfs(void *root, struct bfs_ops *ops, void *in, void **out) } }
+/* + * Recover dependency between event sites + * ===================================================================== + * Even though an event is in a chain of wait-event circular dependency, + * the corresponding wait might be woken up by another site triggering + * the desired event. To reflect that, dept allows to annotate the + * recover relationship between event sites using __dept_recover_event(). + * However, that requires to track a new type of dependency between the + * event sites. + */ + +/* + * Print all events in the circle. + */ +static void print_recover_circle(struct dept_event_site *es) +{ + struct dept_event_site *from = es->bfs_parent; + struct dept_event_site *to = es; + + dept_outworld_enter(); + + pr_warn("===================================================\n"); + pr_warn("DEPT: Circular recover dependency has been detected.\n"); + pr_warn("%s %.*s %s\n", init_utsname()->release, + (int)strcspn(init_utsname()->version, " "), + init_utsname()->version, + print_tainted()); + pr_warn("---------------------------------------------------\n"); + + do { + print_spc(1, "event site(%s@%s)\n", from->name, from->func_name); + print_spc(1, "-> event site(%s@%s)\n", to->name, to->func_name); + to = from; + from = from->bfs_parent; + + if (to != es) + pr_warn("\n"); + } while (to != es); + + pr_warn("---------------------------------------------------\n"); + pr_warn("information that might be helpful\n"); + pr_warn("---------------------------------------------------\n"); + dump_stack(); + + dept_outworld_exit(); +} + +static void bfs_init_recover(void *node, void *in, void **out) +{ + struct dept_event_site *root = (struct dept_event_site *)node; + struct dept_event_site_dep *new = (struct dept_event_site_dep *)in; + + root->bfs_gen = bfs_gen; + new->recover_site->bfs_parent = new->evt_site; +} + +static void bfs_extend_recover(struct list_head *h, void *node) +{ + struct dept_event_site *cur = (struct dept_event_site *)node; + struct dept_event_site_dep *esd; + + list_for_each_entry(esd, &cur->dep_head, dep_node) { + struct dept_event_site *next = esd->recover_site; + + if (bfs_gen == next->bfs_gen) + continue; + next->bfs_parent = cur; + next->bfs_gen = bfs_gen; + list_add_tail(&next->bfs_node, h); + } +} + +static void *bfs_dequeue_recover(struct list_head *h) +{ + struct dept_event_site *es; + + DEPT_WARN_ON(list_empty(h)); + + es = list_first_entry(h, struct dept_event_site, bfs_node); + list_del(&es->bfs_node); + return es; +} + +static enum bfs_ret cb_check_recover_dl(void *node, void *in, void **out) +{ + struct dept_event_site *cur = (struct dept_event_site *)node; + struct dept_event_site_dep *new = (struct dept_event_site_dep *)in; + + if (cur == new->evt_site) { + print_recover_circle(new->recover_site); + return BFS_DONE; + } + + return BFS_CONTINUE; +} + +/* + * NOTE: Must be called with dept_lock held. + */ +static void check_recover_dl_bfs(struct dept_event_site_dep *esd) +{ + struct bfs_ops ops = { + .bfs_init = bfs_init_recover, + .extend = bfs_extend_recover, + .dequeue = bfs_dequeue_recover, + .callback = cb_check_recover_dl, + }; + + bfs((void *)esd->recover_site, &ops, (void *)esd, NULL); +} + /* * Main operations * ===================================================================== @@ -3166,8 +3277,78 @@ static void migrate_per_cpu_pool(void) } }
+static bool dept_recover_ready; + +void __dept_recover_event(struct dept_event_site_dep *esd, + struct dept_event_site *es, struct dept_event_site *rs) +{ + struct dept_task *dt = dept_task(); + unsigned long flags; + + if (unlikely(!dept_working())) + return; + + if (dt->recursive) + return; + + if (!esd || !es || !rs) { + DEPT_WARN_ONCE("All the parameters should be !NULL.\n"); + return; + } + + /* + * Check locklessly if another already has done it for us. + */ + if (READ_ONCE(esd->evt_site)) + return; + + if (!dept_recover_ready) { + DEPT_WARN("Should be called once dept_recover_ready.\n"); + return; + } + + flags = dept_enter(); + if (unlikely(!dept_lock())) + goto exit; + + /* + * Check if another already has done it for us with lock held. + */ + if (esd->evt_site) + goto unlock; + + /* + * Can be used as an indicator of whether this + * __dept_recover_event() has been processed or not as well as + * for storing its associated events. + */ + WRITE_ONCE(esd->evt_site, es); + esd->recover_site = rs; + + if (!es->used || !rs->used) { + if (!es->used) + DEPT_INFO("dept_event_site %s has never been used.\n", es->name); + if (!rs->used) + DEPT_INFO("dept_event_site %s has never been used.\n", rs->name); + + DEPT_WARN("Cannot track recover dependency with events that never used.\n"); + goto unlock; + } + + list_add(&esd->dep_node, &es->dep_head); + list_add(&esd->dep_rev_node, &rs->dep_rev_head); + check_recover_dl_bfs(esd); +unlock: + dept_unlock(); +exit: + dept_exit(flags); +} +EXPORT_SYMBOL_GPL(__dept_recover_event); + #define B2KB(B) ((B) / 1024)
+extern char __dept_event_sites_start[], __dept_event_sites_end[]; + /* * Should be called after setup_per_cpu_areas() and before no non-boot * CPUs have been on. @@ -3175,6 +3356,21 @@ static void migrate_per_cpu_pool(void) void __init dept_init(void) { size_t mem_total = 0; + struct dept_event_site_init **evtinitpp; + + /* + * dept recover dependency tracking works from now on. + */ + for (evtinitpp = (struct dept_event_site_init **)__dept_event_sites_start; + evtinitpp < (struct dept_event_site_init **)__dept_event_sites_end; + evtinitpp++) { + (*evtinitpp)->evt_site->used = true; + (*evtinitpp)->evt_site->func_name = (*evtinitpp)->func_name; + pr_info("dept_event %s@%s is initialized.\n", + (*evtinitpp)->evt_site->name, + (*evtinitpp)->evt_site->func_name); + } + dept_recover_ready = true;
local_irq_disable(); dept_per_cpu_ready = 1;