Locking scheme to block less

Locking scheme to block less

[John Richard Moser]

Currently, the kernel uses only spin_locks, which are similar to mutex 
locks; locks constrict operations to being mutually exclusive.  There 
are many cases where a set of three or more operations has two or more 
which can occur concurrently, and one or more which cannot occur 
concurrently with other operations.  These are normally handled with 
read-write locks.

If the kernel provided a read-write locking semaphore, the time spent 
blocking could be greatly reduced in a safe and effective manner.  To 
maximize efficiency, the following functions would be needed:

spin_read_lock(spin_rwlock_t *lock);
Read lock a spin_rwlock_t.  Multiple concurrent read locks can be 
held, and will block write locks.  A write lock blocks read locks.

spin_write_lock(spin_rwlock_t *lock);
Write lock a spin_rwlock_t.  Only one write lock can be held at any one 
time, and no read lock may be held during write locks.  Held read locks 
block write locks; held write locks block read locks.

spin_read_to_write_lock(spin_rwlock_t *lock);
This is a read lock that will become a write lock.  It allows other read 
locks; but blocks write locks and other read_to_write locks.  It is 
blocked by write locks.

In the course of kernel execution, some functions will wish to read 
through a linked list, find a point to insert or remove data, and then 
perform the operation.  Two such operations will race for a write lock 
when they find the point in the list they wish to alter.  If the points 
are significantly close-- for example, insertion after an index to be 
deleted, or both inserting after a given index-- then a race condition 
occurs, creating an inconsistent internal state and a possible reference 
to freed memory.

A read_to_write lock will block two such operations from occuring 
concurrently, while still allowing read only operations AND still being 
blocked when switched to write mode by both read and write operations.

spin_r2w_write(spin_rwlock_t *lock);
Exchange currently held read_to_write lock for a write lock.  Same rules 
as a write lock apply; this operation is blocked by read locks and 
blocks all locks.

spin_rw_unlock(spin_rwlock_t *lock);
Unlocks a held spin_rwlockt_lock.

I believe that these locking semaphores would be generically useful in
reducing the time spent blocking in the kernel.

Notice that these are similar to pthreads rwlocks; except that there is 
a read_to_write lock specified.  This is not userspace, this is a 
kernel; nobody cares about standards internally, but everyone hates races.

-- 
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

Re: Locking scheme to block less

[viro]

On Mon, Aug 09, 2004 at 08:38:33PM -0400, John Richard Moser wrote:
> Currently, the kernel uses only spin_locks, which are similar to mutex 
> locks;

Does it, really?

> If the kernel provided a read-write locking semaphore,

or if you would care to RTFS and find that it does...

Re: Locking scheme to block less

[John Richard Moser]

viro@parcelfarce.linux.theplanet.co.uk wrote:
> On Mon, Aug 09, 2004 at 08:38:33PM -0400, John Richard Moser wrote:
> 
>>Currently, the kernel uses only spin_locks, which are similar to mutex 
>>locks;
> 
> 
> Does it, really?
> 
> 
>>If the kernel provided a read-write locking semaphore,
> 
> 
> or if you would care to RTFS and find that it does...

o_o I haven't found it.


-- 
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

Re: Locking scheme to block less

[Rik van Riel]

On Mon, 9 Aug 2004, John Richard Moser wrote:

> Currently, the kernel uses only spin_locks,

Oh ?   Haven't you seen the read/write locks in
include/linux/spinlock.h or the lockless synchronisation
provided by include/linux/rcu.h ?

> If the kernel provided a read-write locking semaphore,

Funny, it does.  You're not looking at a 2.0 kernel, are
you?

> spin_read_to_write_lock(spin_rwlock_t *lock);

> A read_to_write lock will block two such operations from occuring 
> concurrently, while still allowing read only operations AND still being 
> blocked when switched to write mode by both read and write operations.

In fact, two threads trying to upgrade their read lock to a
write lock simultaneously will block EACH OTHER, FOREVER.

Sounds like an exceedingly bad idea to me ;)

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

Re: Locking scheme to block less

[John Richard Moser]

Rik van Riel wrote:
> On Mon, 9 Aug 2004, John Richard Moser wrote:
> 
> 
>>Currently, the kernel uses only spin_locks,
> 
> 
> Oh ?   Haven't you seen the read/write locks in
> include/linux/spinlock.h or the lockless synchronisation
> provided by include/linux/rcu.h ?
> 

No, last I looked was in 2.4, and it was a passing glance long ago.

> 
>>If the kernel provided a read-write locking semaphore,
> 
> 
> Funny, it does.  You're not looking at a 2.0 kernel, are
> you?
> 
> 
>>spin_read_to_write_lock(spin_rwlock_t *lock);
>

[Reinsert->]
This is a read lock that will become a write lock.  It allows other read 
locks; but blocks write locks and other read_to_write locks.  It is 
blocked by write locks [and other read_to_write locks](sorry).
> 
>>A read_to_write lock will block two such operations from occuring 
>>concurrently, while still allowing read only operations AND still being 
>>blocked when switched to write mode by both read and write operations.
> 
> 
> In fact, two threads trying to upgrade their read lock to a
> write lock simultaneously will block EACH OTHER, FOREVER.
> 

What no, read that.  It blocks write locks and other read_to_write 
locks.  It should have the above ammendment that it blocks other 
read_to_write locks from beginning, although it is mentioned that this 
DOES block its own kind.  I guess I need to repete myself sometimes.

The point is to prevent operations that find an index on a linked list 
to insert/remove at from altering while something could be reading. 
Concurrent read locks can both find nearby indicies, then race for a 
write lock, leaving the first to clobber the second.

With this type of semaphore (am I using this word correctly?), any 
number of readlocks can exist concurrently with exactly one 
read_write_lock, but will block that read_write_lock from transforming 
to write mode.  Similarly, only one read_write_lock can actually be 
unblocked at any one time, to prevent these races.

> Sounds like an exceedingly bad idea to me ;)
> 

I've seen bad things.

-- 
All content of all messages exchanged herein are left in the
Public Domain, unless otherwise explicitly stated.

Re: Locking scheme to block less

[Martin J. Bligh]

--John Richard Moser <nigelenki@comcast.net> wrote (on Monday, August 09, 2004 23:20:26 -0400):
> 
> Rik van Riel wrote:
>> On Mon, 9 Aug 2004, John Richard Moser wrote:
>> 
>> 
>>> Currently, the kernel uses only spin_locks,
>> 
>> 
>> Oh ?   Haven't you seen the read/write locks in
>> include/linux/spinlock.h or the lockless synchronisation
>> provided by include/linux/rcu.h ?
>> 
> 
> No, last I looked was in 2.4, and it was a passing glance long ago.

Perhaps recommending kernel design changes based on distant passing
glances at the code isn't the finest of plans. Rest assured that others
have given it more than passing thought, and moreover had the audacity
to implement their ideas and benchmark them.

M.

Re: Locking scheme to block less

[Rik van Riel]

On Mon, 9 Aug 2004, John Richard Moser wrote:
> Rik van Riel wrote:
> > On Mon, 9 Aug 2004, John Richard Moser wrote:

> >>Currently, the kernel uses only spin_locks,
> > 
> > Oh ?   Haven't you seen the read/write locks in
> > include/linux/spinlock.h or the lockless synchronisation
> > provided by include/linux/rcu.h ?
> 
> No, last I looked was in 2.4, and it was a passing glance long ago.

We've had read write locks since 2.2...

-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan