Locking scheme to block less

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.

Does it, really?

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.

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

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

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

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

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

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.

I've seen bad things.

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

--John Richard Moser <[email protected]> wrote (on Monday, August 09, 2004 23:20:26 -0400):

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.

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