What does std::atomic::is_always_lock_free = true really mean?

Question

I have the following code:

#include <atomic>

int main () {
    std::atomic<uint32_t> value(0);
    value.fetch_add(1, std::memory_order::relaxed);
    static_assert(std::atomic<uint32_t>::is_always_lock_free);
    return 0;
}

It compiles and so it means std::atomic<uint32_t>::is_always_lock_free is true.

Then, the assembly code looks like this with gcc 10 and -std=c++20 -O3 -mtune=skylake-avx512 -march=skylake-avx512:

0000000000401050 <main>:
  401050:       c7 44 24 fc 00 00 00    mov    DWORD PTR [rsp-0x4],0x0
  401057:       00 
  401058:       f0 ff 44 24 fc          lock inc DWORD PTR [rsp-0x4]
  40105d:       31 c0                   xor    eax,eax
  40105f:       c3                      ret    

Many posts point out that read-modify-write operation (fetch_add() here) can't be an atomic operation without a lock.

My question is what std::atomic::is_always_lock_free being true really means.

This page states Equals true if this atomic type is always lock-free and false if it is never or sometimes lock-free.

What does it mean by "this atomic type is always lock-free" then?

Despicable

It certainly does not mean "no x86 lock instruction prefix is used". en.cppreference.com/w/cpp/atomic/atomic_is_lock_free – Gilt

@n.1.8e9-where's-my-sharem. thanks. then what does std::atomic::is_always_lock_free being true really mean? – Despicable

The linked page has the answer. – Gilt

If I don't mistake, the link is for std::atomic_is_lock_free() and my question is for std::atomic<T>::is_always_lock_free. Former a function call return an integer [-1, 1]. Latter is just boolean value. – Despicable

I assumed you are asking what the term "lock-free" means in general. "Always lock-free" is the combination of that meaning with the meaning of "always", no surprise here. – Gilt

The surprise is that std::atomic<uint32_t>::is_always_lock_free is true while std::atomic_is_lock_free(&value) is 1, which means for the built-in atomic types that are sometimes lock-free. Sounds like a conflict to me. – Despicable

Your question and your last comment appear to be about entirely different things. – Gilt

@HCSF: std::atomic_is_lock_free(&value) returns bool, which when true just means that this particular object is lock-free at the moment; it doesn't distinguish between "always" and "sometimes". You might be thinking of the ATOMIC_XXX_LOCK_FREE macros; if std::atomic<T>::is_always_lock_free is true then ATOMIC_T_LOCK_FREE ought to have the value 2, though I'm not sure if this is technically required. It should be harmless for an implementation to promise less than it actually provides. – Fluter

@NateEldredge right, I was thinking of the macros...my typo in my comment above. – Despicable

Answer 1

"Lock" here is in the sense of "mutex", not specifically in reference to the x86 instruction prefix named lock.

A trivial and generic way to implement std::atomic<T> for arbitrary types T would be as a class containing a T member together with a std::mutex, which is locked and unlocked around every operation on the object (load, store, exchange, fetch_add, etc). Those operations can then be done in any old way, and need not use atomic machine instructions, because the lock protects them. This implementation would be not lock free.

A downside of such an implementation, besides being slow in general, is that if two threads try to operate on the object at the same time, one of them will have to wait for the lock, which may actually block and cause it to be scheduled out for a while. Or, if a thread gets scheduled out while holding the lock, every other thread that wants to operate on the object will have to wait for the first thread to get scheduled back in and complete its work first.

So it is desirable if the machine supports truly atomic operations on T: a single instruction or sequence that other threads cannot interfere with, and which will not block other threads if interrupted (or perhaps cannot be interrupted at all). If for some type T the library has been able to specialize std::atomic<T> with such an implementation, then that is what we mean by saying it is lock free. (It is just confusing on x86 because the atomic instructions used for such implementations are named lock. On other architectures they might be called something else, e.g. ARM64's ldxr/stxr exclusive load/store instructions.)

The C++ standard allows for types to be "sometimes lock free": maybe it is not known at compile time whether std::atomic<T> will be lock-free, because it depends on special machine features that will be detected at runtime. It's even possible that some objects of type std::atomic<T> are lock-free and others are not. That's why atomic_is_lock_free is a function and not a constant. It checks whether this particular object is lock-free on this particular day.

However, it might be the case for some implementations that certain types can be guaranteed, at compile time, to always be lock free. That's what is_always_lock_free is used to indicate, and note that it's a constexpr bool instead of a function.

Fluter

Technically, I don't think an implementation of std::atomic<T> that includes a std::mutex inside the class object itself could satisfy all the other requirements, including initialization or lack thereof. At least not if it wants to be compatible with ISO C _Atomic, because of fairly relaxed rules on initializing such objects while still requiring them to work. See my comment on Where is the lock for a std::atomic?. (For non-lock-free objects, real implementations use a hash table of locks.) – Salvidor

Separately, Anything in std::atomic is wait-free? covers the CS meaning of the term "lock-free" and how it applies to std::atomic. (But doesn't get bogged down in the fact that "lock-free" doesn't mean "not involving the word "lock" :P Instead there are thorny issues like whether you count instructions executed / iterations of a retry loop, or actual cycles, for "concurrent progress" requirements). – Salvidor

And BTW, historically the lock prefix on x86 systems did involve a bus-lock signal that blocked (memory) progress by other cores. These days it doesn't, it's purely local to the CPU doing the operation, once it gets exclusive ownership the same way it would need for a plain store. (Except with cache-line-split operations, but compilers make sure std::atomic is sufficiently aligned, because split-lock is so disastrously expensive that modern CPUs even have hardware support for making that fault to help detect accidental use of it.) – Salvidor

@PeterCordes, starting in C++20 std::atomic has constexpr constructor instead of lack of constructor. std::atomic_init and ATOMIC_FLAG_INIT are deprecated in C++20. Starting in Windows 7, there's SRWLOCK mutex, which does not need a non-trivial destructor, and std::mutex is allowed to have a trivial destructor. So it is possible that future ABI MSVC will put std::mutex there. (MSVC never cared to support "don't have constructor" behavior, as it is more of a bug, than of a feature, even in pre-C++20 modes) – Zoilazoilla

(more likely though that there would be a SRWLOCK directly rather than in a shiny std::mutex wrapper) – Zoilazoilla

@PeterCordes: In #69245683 we looked at MSVC++ disassembly for atomic<struct { uint64_t a,b; }> and concluded that there really is a spinlock inside the struct (though indeed not a std::mutex). In particular its sizeof is 24. I guess a spinlock circumvents some of the issues in your comment, e.g. there are no OS resources to allocate or free. – Fluter

@NateEldredge "It's even possible that some objects of type std::atomic<T> are lock-free and others are not." May I ask how? – Calvities

@MohammadRahimi: cppreference suggests that this could happen if lock-free atomicity requires some extra alignment more than alignof(std::atomic<T>). In that case, some objects may happen to land on a sufficiently aligned address and therefore be able to accessed lock-free, while those which aren't so lucky would need a lock. – Fluter