[PATCH] rwsem: Comments to explain the meaning of the rwsem's count field

[PATCH] rwsem: Comments to explain the meaning of the rwsem's count field

[Tim Chen]

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.

Signed-off-by: Tim Chen <tim.c.chen@linux.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,
-- 
1.7.11.7

Re: [PATCH] rwsem: Comments to explain the meaning of the rwsem's count field

[Davidlohr Bueso]

On Thu, 2014-05-01 at 10:50 -0700, 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.

Agreed, this is nice to have. I'm planning on sending a minor set of
patches for rwsem once the optistic spinning stuff is taken. To simplify
things, I can take this in the series and resend along with the others.

Thanks,
Davidlohr

Re: [PATCH] rwsem: Comments to explain the meaning of the rwsem's count field

[Peter Hurley]

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@linux.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,
>

Re: [PATCH] rwsem: Comments to explain the meaning of the rwsem's count field

[Tim Chen]

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@linux.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)
+ *
+ * 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
+ *		    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)
+ *
+ * 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,
-- 
1.7.11.7

Re: [PATCH] rwsem: Comments to explain the meaning of the rwsem's count field

[Randy Dunlap]

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@linux.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

Re: [PATCH] rwsem: Comments to explain the meaning of the rwsem's count field

[Tim Chen]

On Fri, 2014-05-02 at 06:10 -0700, Randy Dunlap wrote:

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

Oops, should be       (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

Thanks for correcting my grammar mistakes.  Will update the changes.

Tim

Re: [PATCH] rwsem: Comments to explain the meaning of the rwsem's count field

[Tim Chen]

On Thu, 2014-05-01 at 11:38 -0700, Davidlohr Bueso wrote:
> On Thu, 2014-05-01 at 10:50 -0700, 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.
> 
> Agreed, this is nice to have. I'm planning on sending a minor set of
> patches for rwsem once the optistic spinning stuff is taken. To simplify
> things, I can take this in the series and resend along with the others.

I'm fine with whichever way is more convenient for Peter or Ingo.

Thanks.

Tim

Re: [PATCH] rwsem: Comments to explain the meaning of the rwsem's count field

[Peter Hurley]

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@linux.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,
>

Re: [PATCH] rwsem: Comments to explain the meaning of the rwsem's count field

[Tim Chen]

> >   /*
> > + * 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?

This is also the value used also for generic case.  I don't see other
arch specific values defined.

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

I'll add the explanation for the down_read_failed scenario in
the note section below.

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

You're correct.  The values are not comprehensive.  I tried to show the common 
ones and how they arose.  How about I replace the 0xfffe0001 case with
	
count < WAITING_BIAS
	(1) X writer active, Y writers attempting lock, Z readers attempting lock, no waiters
		where X = 0 or 1, (X+Y) >= 2, Z >= 0
		(X+Y) * ACTIVE_WRITE_BIAS + Z * ACTIVE_BIAS
	(2) X writer active, Y writers attempting lock, Z readers attempting lock, with waiters
		where X = 0 or 1, (X+Y) >= 1, Z >= 0
		(X+Y) * ACTIVE_WRITE_BIAS + Z * ACTIVE_BIAS + WAITING_BIAS

Thanks.

Tim