linux-kernel - Re: semaphore: lockless fastpath using atomic_{inc,dec}

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Wed, 09 Jul 2008 20:27:29 +0100
From:	Bruno Santos <bsantos@...it.pt>
To:	Arjan van de Ven <arjan@...radead.org>
CC:	linux-kernel@...r.kernel.org
Subject: Re: semaphore: lockless fastpath using atomic_{inc,dec}_return

Bruno Santos wrote:
> Arjan van de Ven wrote:
>> On Wed, 09 Jul 2008 16:39:43 +0100
>> Bruno Santos <bsantos@...it.pt> wrote:
>>
>>  
>>> Hi,
>>>
>>>  >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 ...).
>>>     
>>
>> 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);
>
> ?
>
>>  
>>> 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)
>>
>>   
>
> 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.
> - 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.
>

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/