linux-kernel - Re: [PATCH] docs: lockdep-design: correct the notation for writer

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <YKu9oDtJ7l00k+Yh@boqun-archlinux>
Date:   Mon, 24 May 2021 22:52:16 +0800
From:   Boqun Feng <boqun.feng@...il.com>
To:     Waiman Long <llong@...hat.com>
Cc:     Xiongwei Song <sxwjean@...il.com>, Xiongwei Song <sxwjean@...com>,
        peterz@...radead.org, mingo@...hat.com, will@...nel.org,
        corbet@....net,
        Linux Kernel Mailing List <linux-kernel@...r.kernel.org>,
        linux-doc@...r.kernel.org
Subject: Re: [PATCH] docs: lockdep-design: correct the notation for writer

On Mon, May 24, 2021 at 09:42:20AM -0400, Waiman Long wrote:
> On 5/24/21 6:32 AM, Boqun Feng wrote:
> > On Mon, May 24, 2021 at 12:24:00PM +0800, Xiongwei Song wrote:
> > > On Fri, May 21, 2021 at 11:17 PM Waiman Long <llong@...hat.com> wrote:
> > > > On 5/21/21 2:29 AM, Xiongwei Song wrote:
> > > > > From: Xiongwei Song <sxwjean@...il.com>
> > > > > 
> > > > > The block condition matrix is using 'E' as the writer noation here, so it
> > > > > would be better to use 'E' as the reminder rather than 'W'.
> > > > > 
> > > > > Signed-off-by: Xiongwei Song <sxwjean@...il.com>
> > > > > ---
> > > > >    Documentation/locking/lockdep-design.rst | 2 +-
> > > > >    1 file changed, 1 insertion(+), 1 deletion(-)
> > > > > 
> > > > > diff --git a/Documentation/locking/lockdep-design.rst b/Documentation/locking/lockdep-design.rst
> > > > > index 9f3cfca..c3b923a 100644
> > > > > --- a/Documentation/locking/lockdep-design.rst
> > > > > +++ b/Documentation/locking/lockdep-design.rst
> > > > > @@ -462,7 +462,7 @@ Block condition matrix, Y means the row blocks the column, and N means otherwise
> > > > >        | R | Y | Y | N |
> > > > >        +---+---+---+---+
> > > > > 
> > > > > -     (W: writers, r: non-recursive readers, R: recursive readers)
> > > > > +     (E: writers, r: non-recursive readers, R: recursive readers)
> > > > > 
> > > > > 
> > > > >    acquired recursively. Unlike non-recursive read locks, recursive read locks
> > > > I would say it should be the other way around. Both W and E refer to the
> > > > same type of lockers. W emphasizes writer aspect of it and E for
> > > > exclusive. I think we should change the block condition matrix to use W
> > > > instead of E.
> > > The doc uses 'E'  to describe dependency egdes too. Should we change them
> > > to 'W'? Personally,  both 'W' and 'E' are fine.
> > > 
> > I also think Waiman's suggestion is solid, there are two ways to
> > classify locks:
> > 
> > 1.	W (Writers), R (Recursive Readers), r (Non-recursive Readers)
> > 
> > 2.	E (Exclusive locks), S (Shared locks), R (Recursive Readers),
> > 	N (Non-recursive locks)
> > 
> > And the relations between them are as follow:
> > 
> > 	E = W
> > 	R = R
> > 	N = W \/ r
> > 	S = R \/ r
> > 
> > , where "\/" is the set union.
> > 
> > The story is that I used the way #1 at first, and later on realized way
> > #2 is better for BFS implementation, also for reasoning, so here came
> > this leftover..
> > 
> My suggestion was based on the fact that it is harder to associate E with
> writer. So from a readability perspective, it is better to change the block
> condition matrix to use 'W' to make it more readable.
> 

Yes, I agree. It's probably due to the curse of knowledge, I cannot see
the difficultly of associating E with writer ;-) So thanks for pointing
out!

Actually there are two block condition matrices in my mind:

The block condition matrix describes the natural of block conditions of
write/read locks, this one provides better readability for lock users,
it can be used to answer questions like: which lock blocks another lock.

	|   | W | r | R |
	+---+---+---+---+
	| W | Y | Y | Y |
	+---|---+---+---+
	| r | Y | Y | N |
	+---+---+---+---+
	| R | Y | Y | N |

(answer whether row blocks column)

Based on this, we have a more abstract block condition matrix in
lockdep, it's used to reason about deadlock possibility and implement
the deadlock detection, it might not be the good one for normal lock
users to read.

	|   |  N  |  R  |
	+---+-----+-----+
	| E | Yes | Yes |
	+---+-----+-----+
	| S | Yes | No  |

(answer whether row blocks column)

FWIW, if we are going to put the second block condition matrix in the
doc, we'd better place it somewhere in the section "Dependency types and
strong dependency paths".

Just clarify a little while we are at it.

Regards,
Boqun

> Cheers,
> Longman
>