Skip to contentSkip to conversation

semaphore: lockless fastpath using atomic_{inc,dec}_return

DISCUSSION Bruno Santos 2 participants 5 messages Jul 9, 2008

lore
Share & tools
lore
#0 lore raw

Hi,

Quoted 5 lines

hi,

not to ruin the party but... how is this lockless? An atomic variable is every bit a "lock" as a spinlock is... and very much equally expensive as well for most cases ;-(

Perhaps not the best the choice of words, I should have omitted the word lockless. But it seems my understanding of lockless and yours is different.
And indeed, it's very expensive as a spinlock, but comparatively, is only one operation, that if successful doesn't have to lock and then unlock (that's why I called it lockless ...). The mutex takes the same approach, however it uses it's own flavour of atomic ops. What I'm really interested is if this brings any benefit in terms of performance.

Quoted 2 lines

And is this safe? It seems that we can always be rescheduled after the atomic operation and interrupts can occur too. You need to tell us why this is safe in all cases.

The slowpaths take care of that:
In 'down' slowpath after acquiring the spinlock the semaphore may have been unlocked ("we can always be rescheduled after the atomic operation and interrupts can occur too"), so we test again doing an atomic_dec_return, like in fastpath case, if it fails we proced to wait list and wait loop until someone wake us, if we get task_interrupted/timeout we just abandon the wait list. In 'up' slowpath after acquiring the spinlock we wake up one waiter, however the list may be empty because we acquired the lock faster than a possible waiter(s) or the waiter(s) abandoned the wait list, in such case we atomic_inc the count to value that is >= 1 (taking into account another 'up').

#1 lore raw
Quoted 8 lines · On Wed, 09 Jul 2008 16:39:43 +0100 Bruno Santos <[email protected]> wrote:

Hi,

Quoted 5 lines

hi,

not to ruin the party but... how is this lockless? An atomic variable is every bit a "lock" as a spinlock is... and very much equally expensive as well for most cases ;-(

Quoted 5 lines

Perhaps not the best the choice of words, I should have omitted the word lockless. But it seems my understanding of lockless and yours is different. And indeed, it's very expensive as a spinlock, but comparatively, is only one operation, that if successful doesn't have to lock and then unlock (that's why I called it lockless ...).

ok I only come from an Intel/x86 background, where unlock is basically free, and the "lock" is exactly the same cost as an atomic op. (in fact, an atomic op and a lock are the exact same code.. you're just open coding it)

Quoted 3 lines

The mutex takes the same approach, however it uses it's own flavour of atomic ops. What I'm really interested is if this brings any benefit in terms of performance.

on x86... I would highly doubt it since you have the same number of atomic operations. (it's not the lock that is expensive. ever. it's always the fact that a lock implies an atomic operation that makes it expensive)

#2 lore raw
Quoted 19 lines · Arjan van de Ven
Quoted 8 lines · On Wed, 09 Jul 2008 16:39:43 +0100 Bruno Santos <[email protected]> wrote:

Hi,

Quoted 5 lines

hi,

not to ruin the party but... how is this lockless? An atomic variable is every bit a "lock" as a spinlock is... and very much equally expensive as well for most cases ;-(

Quoted 6 lines

Perhaps not the best the choice of words, I should have omitted the word lockless. But it seems my understanding of lockless and yours is different. And indeed, it's very expensive as a spinlock, but comparatively, is only one operation, that if successful doesn't have to lock and then unlock (that's why I called it lockless ...).

Quoted 5 lines

ok I only come from an Intel/x86 background, where unlock is basically free, and the "lock" is exactly the same cost as an atomic op. (in fact, an atomic op and a lock are the exact same code.. you're just open coding it)

From your words if we do:

spin_lock()
val = --foo;
spin_unlock();

Has the same cost than:

val = atomic_dec_return(&foo);

?

Quoted 6 lines
Quoted 5 lines

The mutex takes the same approach, however it uses it's own flavour of atomic ops. What I'm really interested is if this brings any benefit in terms of performance.

Quoted 6 lines

on x86... I would highly doubt it since you have the same number of atomic operations. (it's not the lock that is expensive. ever. it's always the fact that a lock implies an atomic operation that makes it expensive)

How come I have the same number of atomic ops?

Let's consider the fast case scenario (semaphore is unlocked for the 'down' and has no waiters for 'up') in x86:
- with the spinlock only approach we have 2 atomic ops, xadd for lock, inc for unlock. The unlock doesn't come for free in x86 after all.
- with the approach I presented we have 1 atomic op (xadd or it could be inc/dec if optimized)

If go the slow path things get more expensive than the spinlock only approach: we have to lock, do some atomic ops for correctness, and unlock.

#3 lore raw
Quoted 50 lines · Bruno Santos
Quoted 19 lines · Arjan van de Ven
Quoted 8 lines · On Wed, 09 Jul 2008 16:39:43 +0100 Bruno Santos <[email protected]> wrote:

Hi,

Quoted 5 lines

hi,

not to ruin the party but... how is this lockless? An atomic variable is every bit a "lock" as a spinlock is... and very much equally expensive as well for most cases ;-(

Quoted 6 lines

Perhaps not the best the choice of words, I should have omitted the word lockless. But it seems my understanding of lockless and yours is different. And indeed, it's very expensive as a spinlock, but comparatively, is only one operation, that if successful doesn't have to lock and then unlock (that's why I called it lockless ...).

Quoted 5 lines

ok I only come from an Intel/x86 background, where unlock is basically free, and the "lock" is exactly the same cost as an atomic op. (in fact, an atomic op and a lock are the exact same code.. you're just open coding it)

From your words if we do:

spin_lock()
val = --foo;
spin_unlock();

Has the same cost than:

val = atomic_dec_return(&foo);

?

Quoted 6 lines
Quoted 5 lines

The mutex takes the same approach, however it uses it's own flavour of atomic ops. What I'm really interested is if this brings any benefit in terms of performance.

Quoted 6 lines

on x86... I would highly doubt it since you have the same number of atomic operations. (it's not the lock that is expensive. ever. it's always the fact that a lock implies an atomic operation that makes it expensive)

Quoted 5 lines

How come I have the same number of atomic ops?

Let's consider the fast case scenario (semaphore is unlocked for the 'down' and has no waiters for 'up') in x86:
- with the spinlock only approach we have 2 atomic ops, xadd for lock,
inc for unlock. The unlock doesn't come for free in x86 after all.

Sorry about typo, the inc for unlock is not atomic, so it indeed comes for free, but we still have to pay for all the overhead of lock - unlock.

Quoted 5 lines

- with the approach I presented we have 1 atomic op (xadd or it could be inc/dec if optimized)

If go the slow path things get more expensive than the spinlock only approach: we have to lock, do some atomic ops for correctness, and unlock.

#4 lore raw
In reply to Bruno Santos
Quoted 10 lines
Quoted 1 line

From your words if we do:

spin_lock()
val = --foo;
spin_unlock();

Has the same cost than:

val = atomic_dec_return(&foo);

yes

Quoted 7 lines

How come I have the same number of atomic ops?

Let's consider the fast case scenario (semaphore is unlocked for the 'down' and has no waiters for 'up') in x86:
- with the spinlock only approach we have 2 atomic ops, xadd for lock, inc for unlock. The unlock doesn't come for free in x86 after all.

the unlock does not use an atomic operation.

Signature · 3 lines
If you want to reach me at my work email, use [email protected]
For development, discussion and tips for power savings, 
visit http://www.lesswatts.org