fast-pathed rw-mutex with single eventcount for the slow-path...

Chris Thomasson

unread,

Oct 31, 2006, 3:16:32 AM10/31/06

to

Here is an example of how you can use an eventcount to help implement a
speedy fast-pathed rw-mutex...

class rwmutex {
typedef unsigned int state_t;

enum flags_e {
WRITER_FLAG = 0x80000000,
READER_MASK = 0x7FFFFFFF
};

private:
mutable state_t volatile m_state;
eventcount m_waiters;

public:
rwmutex() : m_state(0) {}

public:
void rdlock() const {
state_t local = ATOMIC_INC(&m_state);
while (local & WRITER_FLAG) {
eventcount::count_t waits = m_waiters.get();
local = ATOMIC_LOAD(&m_state);
if (! (local & WRITER_FLAG)) { return; }
m_waiters.wait(waits);
local = ATOMIC_LOAD(&m_state);
}
}

void wrlock() {
do {
state_t local = ATOMIC_LOAD(&m_state);
while (local) {
eventcount::count_t waits = m_waiters.get();
local = ATOMIC_LOAD(&m_state);
if (! local) { break; }
m_waiters.wait(waits);
local = ATOMIC_LOAD(&m_state);
}
} while(! ATOMIC_CAS(&m_state, local, local | WRITER_FLAG));
}

public:
void unlock() const {
local = m_state;
if(local & READER_MASK) {
if (! ATOMIC_DEC(&m_state)) {
// atomic-op free fast-path...
m_waiters.signal();
}
} else {
// m_state &= ~WRITER_FLAG
ATOMIC_AND_NOT(&m_state, WRITER_FLAG);

// atomic-op free fast-path...
m_waiters.broadcast();
}
}
};

What do you think here? Look okay to you Joe?

:^)

Joe Seigh

unread,

Oct 31, 2006, 9:05:02 AM10/31/06

to

Chris Thomasson wrote:
> Here is an example of how you can use an eventcount to help implement a
> speedy fast-pathed rw-mutex...
>

[...]

>
>
>
> What do you think here? Look okay to you Joe?
>
> :^)
>
>

I'm going to wait for you to do your 3 or 4 corrections
first. :)

One thing you have to be careful with is the memory barrier
interaction between the eventcount and the lock-free
data structures. If the latter doesn't provide them then
eventcount has to. In some respects condvar is easier to
implement since the mutex provides memory synchronization
independent of the data structure implementation.

--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

Peter Dimov

unread,

Oct 31, 2006, 6:05:48 PM10/31/06

to

Chris Thomasson wrote:
> Here is an example of how you can use an eventcount to help implement a
> speedy fast-pathed rw-mutex...

[...]

> public:
> void rdlock() const {
> state_t local = ATOMIC_INC(&m_state);

[...]

> void wrlock() {
> do {
> state_t local = ATOMIC_LOAD(&m_state);
> while (local) {

Starving writers? :-)

Chris Thomasson

unread,

Nov 4, 2006, 7:20:24 AM11/4/06

to

"Peter Dimov" <pdi...@gmail.com> wrote in message
news:1162335948.1...@e64g2000cwd.googlegroups.com...

> Chris Thomasson wrote:
>> Here is an example of how you can use an eventcount to help implement a
>> speedy fast-pathed rw-mutex...

[...]

> Starving writers? :-)

This one happens to... However, it's fairly trivial to change this behavior
in my algorithm...

Tell me, what do you think of the following approach:

class rwmutex {
typedef unsigned int state_t;

enum flags_e {
WRITER_FLAG = 0x80000000,

READER_MASK = 0x0FFFFFFF
};

private:
mutable state_t volatile m_state;
eventcount m_waiters;

public:
rwmutex() : m_state(0) {}

public:
void rdlock() const {
state_t local = ATOMIC_INC(&m_state);

while(local & WRITER_FLAG) {
if (ATOMIC_CAS(&m_state, local, local - 1)) {

eventcount::count_t waits = m_waiters.get();
local = ATOMIC_LOAD(&m_state);

if (local & WRITER_FLAG) {
m_waiters.wait(waits);
}
local = ATOMIC_INC(&m_state);
} else {
local = ATOMIC_LOAD(&m_state);
}
}
}

void wrlock() {
while(! ATOMIC_BTS(&m_state, WRITER_FLAG)) {

eventcount::count_t waits = m_waiters.get();

if (! ATOMIC_BTS(&m_state, WRITER_FLAG)) {
m_waiters.wait(waits);
}
}

state_t local = ATOMIC_LOAD(&m_state);
while (local & READER_MASK) {

eventcount::count_t waits = m_waiters.get();
local = ATOMIC_LOAD(&m_state);

if (! (local & READER_MASK)) { return; }
m_waiters.wait(waits);
local = ATOMIC_LOAD(&m_state);
}
}

public:
void unlock() const {
state_t local = m_state;
if (local & READER_MASK) {
local = ATOMIC_DEC(&m_state);
if (! local || local & WRITER_FLAG) {

// atomic-op free fast-path...
m_waiters.signal();
}
} else {
// m_state &= ~WRITER_FLAG
ATOMIC_AND_NOT(&m_state, WRITER_FLAG);

// atomic-op free fast-path...
m_waiters.broadcast();
}
}
};

This version will not starve any writers...

;^)