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?

It certainly does not mean "no x86 lock instruction prefix is used". https://en.cppreference.com/w/cpp/atomic/atomic_is_lock_free — n. m. could be an AI, Nov 17 '21 at 05:40
@n.1.8e9-where's-my-sharem. thanks. then what does `std::atomic::is_always_lock_free` being true really mean? — HCSF, Nov 17 '21 at 05:51
If I don't mistake, the link is for `std::atomic_is_lock_free()` and my question is for `std::atomic::is_always_lock_free`. Former a function call return an integer [-1, 1]. Latter is just `bool`ean value. — HCSF, Nov 17 '21 at 06:00
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. — n. m. could be an AI, Nov 17 '21 at 06:09
The surprise is that `std::atomic::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. — HCSF, Nov 17 '21 at 06:13
Your question and your last comment appear to be about entirely different things. — n. m. could be an AI, Nov 17 '21 at 06:23
@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::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. — Nate Eldredge, Nov 17 '21 at 06:30
@NateEldredge right, I was thinking of the macros...my typo in my comment above. — HCSF, Nov 17 '21 at 06:53

Nate Eldredge · Accepted Answer · 2021-11-17T06:27:58.047

12

"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.

edited Nov 17 '21 at 06:27

answered Nov 17 '21 at 06:20

Nate Eldredge

48,811
6
54
82

Technically, I don't think an implementation of `std::atomic` 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?](https://stackoverflow.com/posts/comments/87615626). (For non-lock-free objects, real implementations use a hash table of locks.) – Peter Cordes Nov 17 '21 at 06:58
1

Separately, [Anything in std::atomic is wait-free?](https://stackoverflow.com/q/61849972) 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). – Peter Cordes Nov 17 '21 at 07:04
1

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.) – Peter Cordes Nov 17 '21 at 07:09
@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) – Alex Guteniev Nov 17 '21 at 15:29
(more likely though that there would be a `SRWLOCK` directly rather than in a shiny `std::mutex` wrapper) – Alex Guteniev Nov 17 '21 at 15:31
1

@PeterCordes: In https://stackoverflow.com/questions/69245183/dcas-alternative-with-no-help-of-the-kernel#comment122474027_69245183 we looked at MSVC++ disassembly for `atomic` 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. – Nate Eldredge Nov 17 '21 at 23:47
@NateEldredge "It's even possible that some objects of type std::atomic are lock-free and others are not." May I ask how? – Mohammad Rahimi Dec 18 '22 at 09:59
3

@MohammadRahimi: cppreference suggests that this could happen if lock-free atomicity requires some extra alignment more than `alignof(std::atomic)`. 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. – Nate Eldredge Dec 19 '22 at 21:48

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

1 Answers1