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: <5362AC24.9050508@hurleysoftware.com>
Date:	Thu, 01 May 2014 16:18:44 -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 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

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).

Regards,
Peter Hurley

> Signed-off-by: Tim Chen <tim.c.chen@...ux.intel.com>
> ---
>   kernel/locking/rwsem-xadd.c | 22 ++++++++++++++++++++++
>   1 file changed, 22 insertions(+)
>
> diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
> index 1d66e08..305c15f 100644
> --- a/kernel/locking/rwsem-xadd.c
> +++ b/kernel/locking/rwsem-xadd.c
> @@ -12,6 +12,28 @@
>   #include <linux/export.h>
>
>   /*
> + * Meaning of the rw_semaphore's count field:
> + * (32 bit case illustrated, similar for 64 bit)
> + *
> + * (listed in decreasing order)
> + * 0x0000000X  X readers active, no writer waiting (X*ACTIVE_BIAS)
> + * 0x00000000  rwsem is unlocked, and no one is waiting for the lock
> + * 0xffff000X  X readers active, writer and/or reader waiting.
> + *	       (X*ACTIVE_BIAS + WAITING_BIAS)
> + * 0xffff0001  (1) one writer active, nobody queued. (ACTIVE_WRITE_BIAS)
> + *	       or
> + *	       (2) one reader active, writer(s) queued.
> + *		   (WAITING_BIAS + ACTIVE_BIAS)
> + * 0xffff0000  There are writers or readers queued but none active
> + *	       (WAITING_BIAS), a writer can try to grab the lock and
> + *	       take itself off wait list if awake.  Writer who has just
> + *	       completed its task seeing this count will try to
> + *	       wake people up from wait list.
> + * 0xfffe0001  Writer active, readers/writer queued
> + *	       (ACTIVE_WRITE_BIAS + WAITING_BIAS)
> + */
> +
> +/*
>    * 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/