linux-kernel - Re: [PATCH] rwsem: Comments to explain the meaning of the rwsem's count field

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] [thread-next>] [day] [month] [year] [list]

Message-ID: <1399046942.2970.144.camel@schen9-DESK>
Date:	Fri, 02 May 2014 09:09:02 -0700
From:	Tim Chen <tim.c.chen@...ux.intel.com>
To:	Randy Dunlap <rdunlap@...radead.org>
Cc:	Peter Hurley <peter@...leysoftware.com>,
	Ingo Molnar <mingo@...e.hu>,
	Peter Zijlstra <peterz@...radead.org>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Davidlohr Bueso <davidlohr@...com>,
	Alex Shi <alex.shi@...aro.org>,
	Andi Kleen <andi@...stfloor.org>,
	Michel Lespinasse <walken@...gle.com>,
	Rik van Riel <riel@...hat.com>,
	Thomas Gleixner <tglx@...utronix.de>,
	"Paul E.McKenney" <paulmck@...ux.vnet.ibm.com>,
	Jason Low <jason.low2@...com>, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] rwsem: Comments to explain the meaning of the rwsem's
 count field

On Fri, 2014-05-02 at 06:10 -0700, Randy Dunlap wrote:

> >
> > It takes me quite a while to understand how rwsem's count field mainifest
> 
>                                                                 manifests
> 
> > itself in different scenarios.  I'm adding comments to provide a quick
> > reference on the the rwsem's count field for each scenario where readers
> > and writers are contending for the lock.  Hopefully it will be useful
> > for future maintenance of the code and for people to get up to speed on
> > how the logic in the code works.
> >
> > Signed-off-by: Tim Chen <tim.c.chen@...ux.intel.com>
> > ---
> >   kernel/locking/rwsem-xadd.c | 48 +++++++++++++++++++++++++++++++++++++++++++++
> >   1 file changed, 48 insertions(+)
> >
> > diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
> > index 1d66e08..b92a403 100644
> > --- a/kernel/locking/rwsem-xadd.c
> > +++ b/kernel/locking/rwsem-xadd.c
> > @@ -12,6 +12,54 @@
> >   #include <linux/export.h>
> >
> >   /*
> > + * Guide to the rw_semaphore's count field for common values.
> > + * (32 bit case illustrated, similar for 64 bit)
> 
>         32-bit                               64-bit
> 
> > + *
> > + * 0x0000000X	(1) X readers active or attempting lock, no writer waiting
> > + *		    X = #active_readers + #readers attempting to lock
> > + *		    (X*ACTIVE_BIAS)
> > + *
> > + * 0x00000000	rwsem is unlocked, and no one is waiting for the lock or
> > + *		attempting to read lock or write lock.
> > + *
> > + * 0xffff000X	(1) X readers active or attempt lock, there are waiters for lock
> 
> 			                        attempting
> 
> > + *		    X = #active readers + # readers attempting lock
> > + *		    (X*ACTIVE_BIAS + WAITING_BIAS)
> > + *		(2) 1 writer attempting lock, no waiters for lock
> > + *		    X-1 = #active readers + #readers attempting lock
> > + *		    ((X-1)*ACTIVE_BIAS + ACTIVE_WRITE_BIAS)
> > + *		(3) 1 writer active, no waiters for lock
> > + *		    X-1 = #active readers + #readers attempting lock
> > + *		    ((X-1)*ACTIVE_BIAS + ACTIVE_WRITE_BIAS)
> > + *
> > + * 0xffff0001	(1) 1 reader active or attempting lock, waiters for lock
> > + *		    (WAITING_BIAS + ACTIVE_BIAS)
> > + *		(2) 1 writer active or attempt lock, no waiters for lock
> 
> 		                       attempting
> 
> > + *		    (ACTIVE_BIAS + ACTIVE_WRITE_BIAS)

Oops, should be       (ACTIVE_WRITE_BIAS)

> > + *
> > + * 0xffff0000	(1) There are writers or readers queued but none active
> > + *		    or in the process of attempting lock.
> > + *		    (WAITING_BIAS)
> > + *		Note: writer can attempt to steal lock for this count by adding
> > + *		ACTIVE_WRITE_BIAS in cmpxchg and checking the old count
> > + *
> > + * 0xfffe0001	(1) 1 writer active, or attempting lock. Waiters on queue.
> > + *		    (ACTIVE_WRITE_BIAS + WAITING_BIAS)
> > + *
> > + * Note: Reader attempt to lock by adding ACTIVE_BIAS in down_read and checking
> > + *	 the count becomes more than 0, i.e. the case where there are only
> > + *	 readers or no body has lock. (1st and 2nd case above)
> 
> 	            nobody
> 
> > + *
> > + *	 Writer attempt to lock by adding ACTIVE_WRITE_BIAS in down_write and
> > + *	 checking the count becomes ACTIVE_WRITE_BIAS for succesful lock
> 
> 	                                                  successful

Thanks for correcting my grammar mistakes.  Will update the changes.

Tim



--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/