lkml.org 
[lkml]   [2009]   [May]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    From
    Subject[PATCH 4/8] kernel:lockdep:implement find_usage_*wards by BFS
    Date
    From: Ming Lei <tom.leiming@gmail.com>

    This patch uses BFS to implement find_usage_*wards(),which
    was originally writen by DFS.

    Signed-off-by: Ming Lei <tom.leiming@gmail.com>
    ---
    kernel/lockdep.c | 180 ++++++++++++++++++++++--------------------------------
    1 files changed, 72 insertions(+), 108 deletions(-)

    diff --git a/kernel/lockdep.c b/kernel/lockdep.c
    index f740088..94b2f1f 100644
    --- a/kernel/lockdep.c
    +++ b/kernel/lockdep.c
    @@ -963,7 +963,7 @@ exit:
    return ret;
    }

    -static inline int __bfs_forward(struct lock_list *src_entry,
    +static inline int __bfs_forwards(struct lock_list *src_entry,
    void *data,
    int (*match)(struct lock_list *entry, void *data),
    struct lock_list **target_entry)
    @@ -972,7 +972,7 @@ static inline int __bfs_forward(struct lock_list *src_entry,

    }

    -static inline int __bfs_backward(struct lock_list *src_entry,
    +static inline int __bfs_backwards(struct lock_list *src_entry,
    void *data,
    int (*match)(struct lock_list *entry, void *data),
    struct lock_list **target_entry)
    @@ -1085,18 +1085,6 @@ static int noinline print_bfs_bug(int ret)
    return 0;
    }

    -#define RECURSION_LIMIT 40
    -
    -static int noinline print_infinite_recursion_bug(void)
    -{
    - if (!debug_locks_off_graph_unlock())
    - return 0;
    -
    - WARN_ON(1);
    -
    - return 0;
    -}
    -
    unsigned long __lockdep_count_forward_deps(struct lock_class *class,
    unsigned int depth)
    {
    @@ -1170,7 +1158,7 @@ check_noncircular(struct lock_list *root, struct lock_class *target,

    debug_atomic_inc(&nr_cyclic_checks);

    - result = __bfs_forward(root, target, class_equal, target_entry);
    + result = __bfs_forwards(root, target, class_equal, target_entry);

    return result;
    }
    @@ -1181,101 +1169,70 @@ check_noncircular(struct lock_list *root, struct lock_class *target,
    * proving that two subgraphs can be connected by a new dependency
    * without creating any illegal irq-safe -> irq-unsafe lock dependency.
    */
    -static enum lock_usage_bit find_usage_bit;
    static struct lock_class *forwards_match, *backwards_match;

    +
    +#define BFS_PROCESS_RET(ret) do { \
    + if (ret < 0) \
    + return print_bfs_bug(ret); \
    + if (ret == 1) \
    + return 1; \
    + } while (0)
    +
    +static inline int usage_match(struct lock_list *entry, void *bit)
    +{
    + return entry->class->usage_mask & (1 << (enum lock_usage_bit)bit);
    +}
    +
    +
    +
    /*
    * Find a node in the forwards-direction dependency sub-graph starting
    - * at <source> that matches <find_usage_bit>.
    + * at @root->class that matches @bit.
    *
    - * Return 2 if such a node exists in the subgraph, and put that node
    - * into <forwards_match>.
    + * Return 0 if such a node exists in the subgraph, and put that node
    + * into *@target_entry.
    *
    - * Return 1 otherwise and keep <forwards_match> unchanged.
    - * Return 0 on error.
    + * Return 1 otherwise and keep *@target_entry unchanged.
    + * Return <0 on error.
    */
    -static noinline int
    -find_usage_forwards(struct lock_class *source, unsigned int depth)
    +static int
    +find_usage_forwards(struct lock_list *root, enum lock_usage_bit bit,
    + struct lock_list **target_entry)
    {
    - struct lock_list *entry;
    - int ret;
    -
    - if (lockdep_dependency_visit(source, depth))
    - return 1;
    -
    - if (depth > max_recursion_depth)
    - max_recursion_depth = depth;
    - if (depth >= RECURSION_LIMIT)
    - return print_infinite_recursion_bug();
    + int result;

    debug_atomic_inc(&nr_find_usage_forwards_checks);
    - if (source->usage_mask & (1 << find_usage_bit)) {
    - forwards_match = source;
    - return 2;
    - }

    - /*
    - * Check this lock's dependency list:
    - */
    - list_for_each_entry(entry, &source->locks_after, entry) {
    - debug_atomic_inc(&nr_find_usage_forwards_recursions);
    - ret = find_usage_forwards(entry->class, depth+1);
    - if (ret == 2 || ret == 0)
    - return ret;
    - }
    - return 1;
    + result = __bfs_forwards(root, (void *)bit, usage_match, target_entry);
    +
    + return result;
    }

    /*
    * Find a node in the backwards-direction dependency sub-graph starting
    - * at <source> that matches <find_usage_bit>.
    + * at @root->class that matches @bit.
    *
    - * Return 2 if such a node exists in the subgraph, and put that node
    - * into <backwards_match>.
    + * Return 0 if such a node exists in the subgraph, and put that node
    + * into *@target_entry.
    *
    - * Return 1 otherwise and keep <backwards_match> unchanged.
    - * Return 0 on error.
    + * Return 1 otherwise and keep *@target_entry unchanged.
    + * Return <0 on error.
    */
    -static noinline int
    -find_usage_backwards(struct lock_class *source, unsigned int depth)
    +static int
    +find_usage_backwards(struct lock_list *root, enum lock_usage_bit bit,
    + struct lock_list **target_entry)
    {
    - struct lock_list *entry;
    - int ret;
    -
    - if (lockdep_dependency_visit(source, depth))
    - return 1;
    -
    - if (!__raw_spin_is_locked(&lockdep_lock))
    - return DEBUG_LOCKS_WARN_ON(1);
    -
    - if (depth > max_recursion_depth)
    - max_recursion_depth = depth;
    - if (depth >= RECURSION_LIMIT)
    - return print_infinite_recursion_bug();
    + int result;

    debug_atomic_inc(&nr_find_usage_backwards_checks);
    - if (source->usage_mask & (1 << find_usage_bit)) {
    - backwards_match = source;
    - return 2;
    - }

    - if (!source && debug_locks_off_graph_unlock()) {
    - WARN_ON(1);
    - return 0;
    - }
    + result = __bfs_backwards(root, (void *)bit, usage_match, target_entry);

    - /*
    - * Check this lock's dependency list:
    - */
    - list_for_each_entry(entry, &source->locks_before, entry) {
    - debug_atomic_inc(&nr_find_usage_backwards_recursions);
    - ret = find_usage_backwards(entry->class, depth+1);
    - if (ret == 2 || ret == 0)
    - return ret;
    - }
    - return 1;
    + return result;
    }

    +
    static int
    print_bad_irq_dependency(struct task_struct *curr,
    struct held_lock *prev,
    @@ -1343,18 +1300,21 @@ check_usage(struct task_struct *curr, struct held_lock *prev,
    enum lock_usage_bit bit_forwards, const char *irqclass)
    {
    int ret;
    + struct lock_list this;
    + struct lock_list *uninitialized_var(target_entry);
    +
    + this.parent = NULL;
    +
    + this.class = hlock_class(prev);
    + ret = find_usage_backwards(&this, bit_backwards, &target_entry);
    + BFS_PROCESS_RET(ret);
    + backwards_match = target_entry->class;
    +
    + this.class = hlock_class(next);
    + ret = find_usage_forwards(&this, bit_forwards, &target_entry);
    + BFS_PROCESS_RET(ret);
    + forwards_match = target_entry->class;

    - find_usage_bit = bit_backwards;
    - /* fills in <backwards_match> */
    - ret = find_usage_backwards(hlock_class(prev), 0);
    - if (!ret || ret == 1)
    - return ret;
    -
    - find_usage_bit = bit_forwards;
    - ret = find_usage_forwards(hlock_class(next), 0);
    - if (!ret || ret == 1)
    - return ret;
    - /* ret == 2 */
    return print_bad_irq_dependency(curr, prev, next,
    bit_backwards, bit_forwards, irqclass);
    }
    @@ -2029,14 +1989,16 @@ check_usage_forwards(struct task_struct *curr, struct held_lock *this,
    enum lock_usage_bit bit, const char *irqclass)
    {
    int ret;
    + struct lock_list root;
    + struct lock_list *uninitialized_var(target_entry);

    - find_usage_bit = bit;
    - /* fills in <forwards_match> */
    - ret = find_usage_forwards(hlock_class(this), 0);
    - if (!ret || ret == 1)
    - return ret;
    + root.parent = NULL;
    + root.class = hlock_class(this);
    + ret = find_usage_forwards(&root, bit, &target_entry);
    + BFS_PROCESS_RET(ret);

    - return print_irq_inversion_bug(curr, forwards_match, this, 1, irqclass);
    + return print_irq_inversion_bug(curr, target_entry->class,
    + this, 1, irqclass);
    }

    /*
    @@ -2048,14 +2010,16 @@ check_usage_backwards(struct task_struct *curr, struct held_lock *this,
    enum lock_usage_bit bit, const char *irqclass)
    {
    int ret;
    + struct lock_list root;
    + struct lock_list *uninitialized_var(target_entry);

    - find_usage_bit = bit;
    - /* fills in <backwards_match> */
    - ret = find_usage_backwards(hlock_class(this), 0);
    - if (!ret || ret == 1)
    - return ret;
    + root.parent = NULL;
    + root.class = hlock_class(this);
    + ret = find_usage_backwards(&root, bit, &target_entry);
    + BFS_PROCESS_RET(ret);

    - return print_irq_inversion_bug(curr, backwards_match, this, 0, irqclass);
    + return print_irq_inversion_bug(curr, target_entry->class,
    + this, 1, irqclass);
    }

    void print_irqtrace_events(struct task_struct *curr)
    --
    1.6.0.GIT


    \
     
     \ /
      Last update: 2009-05-31 16:53    [W:0.035 / U:30.404 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site