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

Date:	Fri, 02 May 2014 14:25:00 -0700
From:	Tim Chen <tim.c.chen@...ux.intel.com>
To:	Peter Hurley <peter@...leysoftware.com>
Cc:	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


> >   /*
> > + * Guide to the rw_semaphore's count field for common values.
> > + * (32 bit case illustrated, similar for 64 bit)
> 
> The values below are x86-specific; the actual defines are arch-dependent.
> Do other archs use different values?

This is also the value used also for generic case.  I don't see other
arch specific values defined.

> 
> > + *
> > + * 0x0000000X	(1) X readers active or attempting lock, no writer waiting
> > + *		    X = #active_readers + #readers attempting to lock
> > + *		    (X*ACTIVE_BIAS)
> 
> Not sure it matters, but maybe you want to note that it's possible for 0 readers
> to be active with this value, and all of the other readers may have initially
> failed to claim the lock but may be successful if one can claim the wait_lock while
> the count is still > 0.

I'll add the explanation for the down_read_failed scenario in
the note section below.

> 
> > + *
> > + * 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
> > + *		    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
> > + *		    (ACTIVE_BIAS + 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)
> 
> The count can have more values than just 0xfffe0001 because multiple
> failed write lock attempts plus failed read lock attempts can produce other
> values than those listed.

You're correct.  The values are not comprehensive.  I tried to show the common 
ones and how they arose.  How about I replace the 0xfffe0001 case with
	
count < WAITING_BIAS
	(1) X writer active, Y writers attempting lock, Z readers attempting lock, no waiters
		where X = 0 or 1, (X+Y) >= 2, Z >= 0
		(X+Y) * ACTIVE_WRITE_BIAS + Z * ACTIVE_BIAS
	(2) X writer active, Y writers attempting lock, Z readers attempting lock, with waiters
		where X = 0 or 1, (X+Y) >= 1, Z >= 0
		(X+Y) * ACTIVE_WRITE_BIAS + Z * ACTIVE_BIAS + WAITING_BIAS

Thanks.

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/