| 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
| ||
|
Date: Fri, 02 May 2014 06:10:48 -0700
From: Randy Dunlap <rdunlap@...radead.org>
To: Tim Chen <tim.c.chen@...ux.intel.com>
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 05/01/2014 04: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
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)
> + *
> + * 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
> + * 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,
>
--
~Randy
--
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/
Powered by blists - more mailing lists