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: <5363F969.5060601@hurleysoftware.com>
Date:	Fri, 02 May 2014 16:00:41 -0400
From:	Peter Hurley <peter@...leysoftware.com>
To:	Tim Chen <tim.c.chen@...ux.intel.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

On 05/01/2014 07:05 PM, Tim Chen wrote:
> On Thu, 2014-05-01 at 16:18 -0400, Peter Hurley wrote:
>> On 05/01/2014 01:50 PM, Tim Chen wrote:
>>> It takes me a while to understand how rwsem's count field mainifest
>>> 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/holding 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.
>>
>> Except there are a lot of transition states for the count that look like
>> stable states for some other condition, and vice versa.
>>
>> For example, 0xffff000X could be:
>> 1. stable state as described below.
>> 2. 1 or more (but not X) readers active,
>>      1 writer which failed to acquire and has not yet backed out the adjustment
>>      0 or more readers which failed to acquire because of the waiting writer
>>          and have not yet backed out
>> 3. 1 writer active,
>>      1 or more readers which failed to acquire because of the active writer and
>>          have not yet backed out
>> 4. maybe more states where a owning writer has just dropped the lock
>
> Thanks for the feedback.  Yes, one thing I missed was to account for the
> readers and writers who are actively attempting to lock by adding
> ACTIVE_BIAS or ACTIVE_WRITE_BIAS to the count.  Once we account for
> those we should take care of the transition states.
> The revised comments also look at the readers and writers actively
> attempting the lock.
>
>>
>> Because of this, it's hazardous to infer lock state except for the specific
>> existing tests (eg., the count observed by a failed reader after it has
>> acquired the wait_lock).
>
> Thanks.
>
> Tim
>
> ---
>
> It takes me quite a while to understand how rwsem's count field mainifest
> 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)

The values below are x86-specific; the actual defines are arch-dependent.
Do other archs use different values?

> + *
> + * 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.

> + *
> + * 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.

Regards,
Peter Hurley

> + *
> + * 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)
> + *
> + *	 Writer attempt to lock by adding ACTIVE_WRITE_BIAS in down_write and
> + *	 checking the count becomes ACTIVE_WRITE_BIAS for succesful lock
> + *	 acquisition (i.e. nobody else has lock or attempts lock).  If
> + *	 unsuccessful, in rwsem_down_write_failed, we'll check to see if there
> + *	 are only waiters but none active (5th case above), and attempt to
> + *	 steal the lock.
> + *
> + */
> +
> +/*
>    * Initialize an rwsem:
>    */
>   void __init_rwsem(struct rw_semaphore *sem, const char *name,
>

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