lkml.org 
[lkml]   [2019]   [May]   [29]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [PATCH v2 02/17] locking/lockdep: Add read-write type for dependency
    On Thu, May 16, 2019 at 04:00:00PM +0800, Yuyang Du wrote:
    > Direct dependency needs to keep track of its locks' read-write types. A
    > union field is added to lock_list struct so the type is stored there as
    > this:
    >
    > lock_type[1] (u16), lock_type[0] (u16)
    >
    > or:
    >
    > dep_type (int)
    >
    > where value:
    >
    > 0: exclusive / write
    > 1: read
    > 2: recursive read
    >
    > Note that (int) dep_type value may vary with different architectural
    > endianness, so use helper functions to operate on these types.
    >
    > Signed-off-by: Yuyang Du <duyuyang@gmail.com>
    > ---
    > include/linux/lockdep.h | 12 ++++++++++++
    > kernel/locking/lockdep.c | 34 +++++++++++++++++++++++++++++++---
    > kernel/locking/lockdep_internals.h | 3 +++
    > 3 files changed, 46 insertions(+), 3 deletions(-)
    >
    > diff --git a/include/linux/lockdep.h b/include/linux/lockdep.h
    > index 1009c47..bc09c85 100644
    > --- a/include/linux/lockdep.h
    > +++ b/include/linux/lockdep.h
    > @@ -195,6 +195,18 @@ struct lock_list {
    > struct lock_class *links_to;
    > struct lock_trace trace;
    > int distance;
    > + /*
    > + * This field keeps track of the read-write type of this dependency.
    > + *
    > + * With L1 -> L2:
    > + *
    > + * lock_type[0] stores the type of L1, while lock_type[1] stores the
    > + * type of L2.
    > + */
    > + union {
    > + int dep_type;
    > + u16 lock_type[2];

    This takes extra space for storing the type of dependencies. In my
    previous patchset, only 2bits are used, because you only need to care
    about four types of dependencies:

    1. Exclusive -> Recursive
    2. Shared (read or recursive read) -> Recursive
    3. Exclusize -> Non-Recursive (write or non-recursive readers)
    4. Shared (read or recursive read) -> Non-Recursive

    To understand why, here are my slides for Linux Plumber Conference last
    year:

    https://www.linuxplumbersconf.org/event/2/contributions/74/attachments/67/78/Recursive_read_deadlocks_and_Where_to_find_them.pdf

    And we can steal two bits from "distance", since 2^30 would be enough.
    I think it's important to save the size of lock_list since we will have
    a lot of them.

    Regards,
    Boqun

    > + };
    >
    > /*
    > * The parent field is used to implement breadth-first search, and the
    > diff --git a/kernel/locking/lockdep.c b/kernel/locking/lockdep.c
    > index fb6be63..e7eedbf 100644
    > --- a/kernel/locking/lockdep.c
    > +++ b/kernel/locking/lockdep.c
    > @@ -1225,7 +1225,7 @@ static struct lock_list *alloc_list_entry(void)
    > static int add_lock_to_list(struct lock_class *this,
    > struct lock_class *links_to, struct list_head *head,
    > unsigned long ip, int distance,
    > - struct lock_trace *trace)
    > + struct lock_trace *trace, int dep_type)
    > {
    > struct lock_list *entry;
    > /*
    > @@ -1240,6 +1240,8 @@ static int add_lock_to_list(struct lock_class *this,
    > entry->links_to = links_to;
    > entry->distance = distance;
    > entry->trace = *trace;
    > + entry->dep_type = dep_type;
    > +
    > /*
    > * Both allocation and removal are done under the graph lock; but
    > * iteration is under RCU-sched; see look_up_lock_class() and
    > @@ -1677,6 +1679,30 @@ unsigned long lockdep_count_backward_deps(struct lock_class *class)
    > return ret;
    > }
    >
    > +static inline int get_dep_type(struct held_lock *lock1, struct held_lock *lock2)
    > +{
    > + /*
    > + * With dependency lock1 -> lock2:
    > + *
    > + * lock_type[0] is lock1, while lock_type[1] is lock2.
    > + *
    > + * Avoid architectural endianness difference composing dep_type.
    > + */
    > + u16 type[2] = { lock1->read, lock2->read };
    > +
    > + return *(int *)type;
    > +}
    > +
    > +static inline int get_lock_type1(struct lock_list *lock)
    > +{
    > + return lock->lock_type[0];
    > +}
    > +
    > +static inline int get_lock_type2(struct lock_list *lock)
    > +{
    > + return lock->lock_type[1];
    > +}
    > +
    > /*
    > * Check that the dependency graph starting at <src> can lead to
    > * <target> or not. Print an error and return 0 if it does.
    > @@ -2446,14 +2472,16 @@ static inline void inc_chains(void)
    > */
    > ret = add_lock_to_list(hlock_class(next), hlock_class(prev),
    > &hlock_class(prev)->locks_after,
    > - next->acquire_ip, distance, trace);
    > + next->acquire_ip, distance, trace,
    > + get_dep_type(prev, next));
    >
    > if (!ret)
    > return 0;
    >
    > ret = add_lock_to_list(hlock_class(prev), hlock_class(next),
    > &hlock_class(next)->locks_before,
    > - next->acquire_ip, distance, trace);
    > + next->acquire_ip, distance, trace,
    > + get_dep_type(next, prev));
    > if (!ret)
    > return 0;
    >
    > diff --git a/kernel/locking/lockdep_internals.h b/kernel/locking/lockdep_internals.h
    > index 150ec3f..c287bcb 100644
    > --- a/kernel/locking/lockdep_internals.h
    > +++ b/kernel/locking/lockdep_internals.h
    > @@ -26,6 +26,9 @@ enum lock_usage_bit {
    > #define LOCK_USAGE_DIR_MASK 2
    > #define LOCK_USAGE_STATE_MASK (~(LOCK_USAGE_READ_MASK | LOCK_USAGE_DIR_MASK))
    >
    > +#define LOCK_TYPE_BITS 16
    > +#define LOCK_TYPE_MASK 0xFFFF
    > +
    > /*
    > * Usage-state bitmasks:
    > */
    > --
    > 1.8.3.1
    >
    [unhandled content-type:application/pgp-signature]
    \
     
     \ /
      Last update: 2019-05-29 13:38    [W:5.139 / U:0.020 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site