Re: [tip:locking/core] rwsem: Add comments to explain the meaning of the rwsem's count field

[Tim Chen <tim.c.chen@linux.intel.com>]

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