linux-kernel - Re: [tip:locking/core] rwsem: Add 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]

Date:	Mon, 05 May 2014 15:51:16 -0700
From:	Tim Chen <tim.c.chen@...ux.intel.com>
To:	Ingo Molnar <mingo@...nel.org>
Cc:	linux-tip-commits@...r.kernel.org, linux-kernel@...r.kernel.org,
	torvalds@...ux-foundation.org, peterz@...radead.org,
	peter@...leysoftware.com, jason.low2@...com, riel@...hat.com,
	alex.shi@...aro.org, paulmck@...ux.vnet.ibm.com,
	akpm@...ux-foundation.org, tglx@...utronix.de, walken@...gle.com,
	davidlohr@...com, "H. Peter Anvin" <hpa@...or.com>
Subject: Re: [tip:locking/core] rwsem: Add comments to explain the meaning
 of the rwsem's count field

On Mon, 2014-05-05 at 20:27 +0200, Ingo Molnar wrote:

> > Ingo,
> > 
> > The delta patch is included below.  Thinking a bit more,
> > the state diagram approach is not necessarily less verbose
> > because the state is a tuple (count, wait queue state).
> > After enumerating the states, we may wind up with very similar
> > to what I have.
> 
> Could we at least try with one diagram and see how it goes?
> 

I've tried (see below).  But I don't like how it came out :(

Tim


---

Events:
	(1) Attempt read lock (+ACTIVE_BIAS)
	(2) Attempt write lock (+ACTIVE_WRITE_BIAS)
	(3) Abort read lock or read unlock  (-ACTIVE_BIAS)
	(4) Abort write lock or write unlock  (-ACTIVE_WRITE_BIAS)
	(5) Put reader/writer on queue after read/write lock attempt has been aborted
			  (+WAITING_BIAS if queue empty)
	(6) Pull reader/writer from head of queue
			  (-WAITING_BIAS if queue becomes empty)

State	Event	Next-State
-----   -----   ----------
(A)	count > 0 (0x0000000X), queue empty  

	1 => 	(A)
	2 => 	(C.0) 
	3 => 	(A if count > 1, B if count =1)
	4 not applicable
	5 => 	(C.0)
	6 not applicable

(B)	count = 0 (0x00000000), queue empty   

	1 => 	(A)
	2 => 	(C.0) 
	3, 4 not applicable
	5 =>	(E.0)
	6 not applicable

(C.0)	0 > count > WAITING_BIAS (0xffff000X), queue empty

	1 => 	(C.0)
	2 => 	(E.0)
	3 => 	(count=0xffff0001 implies 1 writer, no readers to abort, C.0 if count > 0xffff0001)
	4 => 	(B if count=0xffff0001, A if count > 0xffff0001)
	5 => 	(E.1)
	6 not applicable

(C.1)	0 > count > WAITING_BIAS (0xffff000X), queue non-empty

	1 => 	(C.1) 
	2 => 	(E.1)
	3 => 	(D if count=0xffff0001, C.1 if count > 0xffff0001)
	4 => 	(B if count=0xffff0001, A if count > 0xffff0001)
	5 => 	(E.1)
	6 =>	(A or B if queue becomes empty, C.1 if queue remains non-empty)
	     
(D)	count = WAITING_BIAS (0xffff0000), queue non-empty

	1 =>	(C.0)
	2 =>	(E.0)
	3,4 not applicable
	5 =>	(D)
	6 =>	(A if queue becomes empty, D otherwise)

(E.0)	count < WAITING_BIAS, queue empty

	1 =>	(E.0)
	2 =>	(E.0)
	3 =>	(E.0)
	4 =>	(C.0 if count > 2*WAITING_BIAS  E.0 otherwise)
	5 => 	(E.1)
	6 not applicable 

(E.1)	count < WAITING_BIAS, queue non-empty   

	1 =>	(E.1)
	2 =>	(E.1)
	3 =>	(E.1)
	4 =>	(C.1 if count < 2*WAITING_BIAS,  E.1 otherwise)
	5 => 	(E.1)
	6 =>	(D if count = 2*WAITING_BIAS, E.1 otherwise, queue remains non-empty) or
		E.0 otherwise 


--
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/