lkml.org 
[lkml]   [2011]   [Apr]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[RFC][PATCH 7/7] lockdep: Consider the rw_state of lock while validating the chain
    From: Gautham R Shenoy <ego@in.ibm.com>

    Currently, while validating a particular dependency chain, we check if by
    following the the locks_after list of current lock A, we can reach one of the
    previous locks in the current chain.

    i.e, if current chain is : A --> B --> C, then starting from C -->
    locks_after, can we reach B.

    However, if there are dependency chains:

    C--> D --> Rlock(E)

    Rlock(E) --> A,

    where E is a Recursive Read lock, this chain cannot cause a deadlock because
    of the recursive nature of E.

    However, if the dependency chain was:

    Wlock(E) --> A,

    it could have caused a deadlock.

    We solve this problem by defining conflicting states of each lock where:

    Conflict(WRITE) = WRITE, READ, RECURSIVE_READ
    Conflict(READ) = WRITE, READ
    Conflict(RECURSIVE_READ) = WRITE

    Thus, while traversing the locks_after chain of a particular lock A, we traverse
    through only those entries in the chain where the state of the lock A in the
    entry conflicts with the state of the lock A with which we started the
    traversal.

    Signed-off-by: Gautham R Shenoy <ego@in.ibm.com>
    Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
    ---
    kernel/lockdep.c | 43 ++++++++++++++++++++++++++++++++++++++++---
    1 file changed, 40 insertions(+), 3 deletions(-)

    Index: linux-2.6/kernel/lockdep.c
    ===================================================================
    --- linux-2.6.orig/kernel/lockdep.c
    +++ linux-2.6/kernel/lockdep.c
    @@ -949,6 +949,26 @@ static inline int get_lock_depth(struct
    return depth;
    }

    +/*
    + * Conflicting states:
    + * - A Recursive read conflicts only with a write.
    + * - A Non-recursive read can conflict with a non-recursive read and write.
    + * - A Write conflicts with Write, simple read and recursive read.
    + */
    +
    +#define get_rec_read_conflict(state) \
    + ((((is_write(state)) << (_RR_ - _W_))) & STATE_RECURSIVE_READ)
    +
    +#define get_simple_read_conflict(state) \
    + (((((is_write(state)) << (_R_ - _W_))) | (is_simple_read(state))) \
    + & STATE_READ)
    +#define get_write_conflict(state) STATE_WRITE
    +
    +#define get_lock_conflict_states(state) \
    + (get_rec_read_conflict(state) | \
    + get_simple_read_conflict(state) | \
    + get_write_conflict(state))
    +
    static int __bfs(struct lock_list *source_entry,
    void *data,
    int (*match)(struct lock_list *entry, void *data),
    @@ -958,6 +978,7 @@ static int __bfs(struct lock_list *sourc
    struct lock_list *entry;
    struct list_head *head;
    struct circular_queue *cq = &lock_cq;
    + unsigned int conflict;
    int ret = 1;

    if (match(source_entry, data)) {
    @@ -992,9 +1013,13 @@ static int __bfs(struct lock_list *sourc
    else
    head = &lock->dep_class->locks_before;

    + conflict = get_lock_conflict_states(lock->dep_lock_rw_state);
    +
    list_for_each_entry(entry, head, entry) {
    if (!lock_accessed(entry)) {
    unsigned int cq_depth;
    + if (!(entry->this_lock_rw_state & conflict))
    + continue;
    mark_lock_accessed(entry, lock);
    if (match(entry, data)) {
    *target_entry = entry;
    @@ -1411,8 +1436,9 @@ check_usage(struct task_struct *curr, st
    struct lock_list *uninitialized_var(target_entry1);

    this.parent = NULL;
    -
    this.dep_class = hlock_class(prev);
    + this.this_lock_rw_state = next->rw_state;
    + this.dep_lock_rw_state = prev->rw_state;
    ret = find_usage_backwards(&this, bit_backwards, &target_entry);
    if (ret < 0)
    return print_bfs_bug(ret);
    @@ -1421,6 +1447,8 @@ check_usage(struct task_struct *curr, st

    that.parent = NULL;
    that.dep_class = hlock_class(next);
    + that.this_lock_rw_state = prev->rw_state;
    + that.dep_lock_rw_state = next->rw_state;
    ret = find_usage_forwards(&that, bit_forwards, &target_entry1);
    if (ret < 0)
    return print_bfs_bug(ret);
    @@ -1663,6 +1691,8 @@ check_prev_add(struct task_struct *curr,
    */
    this.dep_class = hlock_class(next);
    this.parent = NULL;
    + this.this_lock_rw_state = prev->rw_state;
    + this.dep_lock_rw_state = next->rw_state;
    ret = check_noncircular(&this, hlock_class(prev), &target_entry);
    if (unlikely(!ret))
    return print_circular_bug(&this, target_entry, next, prev);
    @@ -1776,7 +1806,8 @@ check_prevs_add(struct task_struct *curr
    * Only non-recursive-read entries get new dependencies
    * added:
    */
    - if (!is_rec_read(hlock->rw_state)) {
    + if (!is_rec_read(hlock->rw_state) ||
    + is_first_rec_read(hlock->rw_state)) {
    if (!check_prev_add(curr, hlock, next,
    distance, trylock_loop))
    return 0;
    @@ -1950,9 +1981,15 @@ static int validate_chain(struct task_st

    if (!ret)
    return 0;
    +
    + if (ret != 2 && is_rec_read(hlock->rw_state))
    + hlock->rw_state |= STATE_FIRST_RECURSIVE_READ;
    +
    +
    /*
    * Add dependency only if this lock is not the head
    - * of the chain, and if it's not a secondary read-lock:
    + * of the chain, and if it's not the first instance of
    + * the recursive read-lock:
    */
    if (!chain_head && ret != 2)
    if (!check_prevs_add(curr, hlock))



    \
     
     \ /
      Last update: 2011-04-17 12:01    [W:0.031 / U:155.668 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site