But it fits the common Linux implementation of the function... e.g. the Debian manpage says:
> Upon error, crypt_r, crypt_rn, and crypt_ra write an invalid hash to the _output_ field of their _data_ argument, and crypt writes an invalid hash to its static storage area. This string will be shorter than 13 characters, will begin with a ‘*’, and will not compare equal to _setting_.
That says 'begin with,' which does not remotely require it be exactly the 1-character string '*' which probably was a bit of an insane choice under GP's logic.
And that's also only in Debian 11 and later. That man page said something entirely different in Debian 10 and earlier, when they shipped glibc's libcrypt. Now they ship libxcrypt instead.
Fedora asked libxcrypt to give them back glibc's behavior, returning NULL, and they obliged by adding ./configure --disable-failure-tokens. But it's an option that Debian never enabled.
To the best of my knowledge, only OpenBSD and Fedora have a crypt(3) that returns NULL. Everybody else returns a string starting with "*" on error.
For example on Debian the manpage says:
> Upon error, crypt_r, crypt_rn, and crypt_ra write an _invalid_ hash to the output field of their _data_ argument, and crypt writes an invalid hash to its static storage area. This string will be shorter than 13 characters, will begin with a ‘*’, and will not compare equal to _setting_.
In my experience, any questions about an obscure or rare problem was likely to be marked as a duplicate if it sounded even vaguely similar to a common problem. My impression was that some moderators just were unwilling to admit they didn't know the answer to a question.
It's neither, really. OS X takes its command line utilities from BSD world, while Linux's mostly come from GNU. They're independent implementations, and GNU utilities are as a rule much more featureful than their BSD equivalents. Or much more bloated, depending on your point of view.
Both aim to conform to the POSIX, but POSIX is a very spartan spec, people routinely use non-POSIX features without realizing it.
This comment made me feel awkward for two reasons.
First, Linux was never GNU - the GNU ecosystem has always been a significant part, but if you were obstinate enough, you could get away without using any GNU tools (which is even easier today).
Second, you give just two examples. A few years ago we had a trend to rewrite everything in Rust with these newer tools usually not being part of the GNU project. Sure, you can replace everything now. However, most GNU tools are here to stay for a long time especially in enterprise distros where backward compatibility is important.
So no, Linux has never been GNU, and whatever fluctuations we had over decades with innumerable fights like egcs vs gcc etc., the GNU ecosystem is and will long be part of Linux distros.
Over time I see fewer and fewer gnu tools in my standard mainstream Linux. The tooling I used 25 years ago was far more gnu based than today, and crucially the FSF view of what free software is, and by extension the gnu public license, seems to be constantly retreating.
25 years ago it was reasonable to say the typical Linux machine was “gnu/linux”. Today it’s not.
The intro of this article repeats the common assertion that
> ARM is the most relaxed, allowing significant hardware optimizations; and x86 is the most strict, enforcing a very strong coherency model that doesn’t allow a lot of room for optimization
[Disclaimer: I wrote Rosetta 2 and determined the spec for Apple's TSO mode, so I am obviously biased.]
Giesen's article comes off as well-meaning cope from an x86 fan. A relaxed memory model really does give you some performance. Another memory model flaw here in x86 is more architectural, which is that every instruction with the LOCK prefix is essentially a full barrier (of course, x86 could have provided different instructions while still being under TSO). In programs that make heavy usage of atomic reference counting, this actually helps quite a bit.
I would probably put that performance benefit in the single digit percentage range like my sibling comment, which may not seem like much to a SW engineer but is actually pretty serious in CPU microarchitecture. It also helps to be stacked with other architectural advantages over x86, e.g. fixed-length instructions, 32 GPRs (which Intel copied in APX), LDP/STP (which Intel also copied in APX), etc.
One of the old arguments from TSO enjoyers was that TSO helps avoid concurrency bugs that people would accidentally introduce, but this was before the C++ memory model propagated throughout the programming world. Nowadays, I think people generally conceptualize memory consistency in terms of acquire/release anyways, so why not use a CPU architecture that uses the same model?
Do you think there would be any worthwhile gains from relaxing address-dependent load ordering, like on Alpha/AXP? Or was that just a lot of extra pain for little reward?
Fun fact: ARM actually has relaxed address dependencies for non-temporal loads, although I don't know if too many implementations of ARM take advantage of this relaxation.
I think it is an interesting question. During the Alpha's lifetime as a non-hobbyist architecture, this decision was pretty much universally derided, but this was in the prehistoric eras of concurrent memory models, where people were just trying their best with a mix of C code, intrinsics, uses of `volatile` sprinkled around to hopefully disable optimizations, and inline assembly. When the C++11 memory model came around, they tried to integrate dependency ordering with `memory_order_consume`, and this famously failed, along with every attempt to fix it. I believe the plan is now for C++ (and later C?) to add special-cased RCU primitives.
The relaxation makes sense in the abstract. As evidenced from the `memory_order_consume` saga, compiler optimizations regularly violate dependency ordering anyways, so in the strictest sense you can't really rely on it. Of course, that doesn't stop people from "knowing" what their compilers will do in such a situation, but that strategy has become a worse one as the years have passed. I would feel better about the whole situation if there was a good greenfield design for a low-level PL that incorporates explicit dependency ordering.
I think it's less clear where the potential HW benefit is in a contemporary CPU. The obvious answer is value prediction, but any CPU performing value prediction has to deal with so many other microarchitectural conditions that can invalidate its speculation decisions that it's not clear this minor one is a huge burden. Of course, people who love TSO might make the same argument, i.e. that it's not a huge burden to snoop cache traffic and invalidate loads (although this is only the load half of TSO, not the store half). I know an Alpha architect who argued that Alpha was right for this decision. I even knew a Transmeta architect who argued for implementing sequential consistency in HW (as Transmeta and derived CPUs actually did).
In practice, microarchitectural structures have capacity/throughput limitations, and there are implementations and complexities that only come up in a real design, so everything needs to be evaluated in the context of a real project. I personally think the sweet spot falls to the weaker side of TSO, which also happens to be near the memory consistency model of the low-level languages we're using anyways.
> and this famously failed, along with every attempt to fix it.
What was the cause of failure? I see that it is now deprecated which surprises me. It was my understanding that large portions of this were taken from the Java memory model and in the JVM, it seems to have been pretty successful.
Is it because the compilers themselves refused to respect it?
The C/C++ memory model starts with Java's data-race free memory model, but makes data races fully UB. Atomics are introduced into C/C++ that allows fine-grained definition of synchronization, with four different models of atomics: sequentially-consistent (equivalent to Java's volatile), release-acquire, release-consume, and relaxed (which are not synchronizing and are therefore closer to a defined data race than proper atomics). The Java 5 memory model doesn't have the concept of atomics, except that volatile variables act like C/C++ sequentially-consistent atomics.
Relaxed atomics took a couple of tries to specify, and still have a known out-of-thin-air hole that people are still struggling to solve. But the problem with relaxed atomics is that the practical operational semantics are pretty clear, but the formal model is quite tricky for various reasons.
Sequentially-consistent matches the model that most people naively think is going on in hardware (execute a single instruction at a time from a random thread). Release-acquire is a slight relaxation of that model that works well most of the time; the main difference between sequentially-consistent and release-acquire is that release-acquire requires you to specifically release and acquire on the same memory location to get the synchronization, whereas sequentially-consistent synchronizes across different memory locations. Since most multithreaded code tends to have a concept of something like a lock or mutex that is guarding access to a particular region of memory, release-acquire is usually sufficient.
Release-consume is supposed to be release-acquire, but only for data-dependent loads of the consume. This is the only part of the memory model that has really failed, and that's because compilers cannot really guarantee preservation of data dependence in the optimizer. (This also comes up with pointer provenance, FWIW).
As my sibling comment from jcranmer points out, it was only `memory_order_consume` that failed outright. The other aspects of the C++ memory model mostly worked out, at least after revision.
I believe the last attempt to come up with a comprehensive new proposal was P0190 (https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p01...), which reduced the ordering-imposing dependencies in the model to essentially just be pointer dependencies (which does eliminate some legitimately useful cases, e.g. stealing bits from pointers). The paper mentions the unresolved problem of control dependencies from compiler knowledge of pointer equality, which is intertwined with the pointer provenance discussions from around the same time.
I would like to see the basic concept realized in another language some day.
In my opinion, conceptualizing memory consistency in terms of acquire/release is wrong and it confuses many programmers.
One problem is that 2 kinds of ordered loads and stores are not enough, 4 kinds are needed.
Some algorithms need not only load-acquire and store-release, but also a store that is guaranteed to be executed before all subsequent stores and a load that is guaranteed to be executed after all previous loads. These properties are the opposite of those provided by load-acquire and store-release. Except for x86 where any loads and stores behave like this, the other popular ISAs do not have such loads and stores, so stronger than necessary instructions must be used, i.e. load barriers and store barriers. Moreover, the instruction that is named a load barrier in the Arm ISA is not a load barrier, but a stronger barrier, but it must be used instead of a load barrier as no better alternative exists.
Besides the fact that not only load-acquire and store-release, but also other 2 ordered loads and stores are needed, a much more serious problem is that load-acquire is not the instruction that is really needed.
I have never seen any useful algorithm where load-acquire is the correct instruction to use. In all algorithms, what you want is not an instruction, but a loop that compares memory repeatedly, waiting for some condition to be fulfilled. The 4 most frequent kinds of loops that are needed are wait-for-not-equal, wait-for-equal, wait-for-even and wait-for-zero.
These loops may execute a load-acquire, but that is not the desired behavior. What you really need are 2 kinds of barriers, one inside the loop and one immediately after the loop.
The internal barrier must prevent the CPU from speculatively executing many future loop instances beyond the conditional jump that terminates the loop body, as it normally does. On x86-64, the instruction PAUSE provides such a barrier. On Aarch64, I suspect that a load-acquire instruction does inhibit this kind of speculative execution, despite the fact that this behavior is not documented. Otherwise, a CPU executing this kind of loop would waste a lot of energy and resources.
The barrier after such a loop must prevent speculative memory accesses beyond it. The semantics of load-acquire are not really needed, because all such loads are done in a loop and the memory accesses that follow the loop cannot be executed before such a load, due to the control dependency created by the conditional jump that follows the load. Nonetheless, while normal execution is impossible, the CPU can execute speculatively any loads following the loop and only this speculative execution can break the acquire semantics. Therefore what you really need is a speculation barrier after the loop, not an acquire barrier, whose behavior is provided automatically by the loop, even without any instruction with acquire semantics.
On x86-64, if a loop is terminated by an unconditional jump, it is said that such a jump blocks the speculative accesses beyond it. This is why the examples provided by Intel in its optimization manual about how to write this kind of acquire loop show loops terminated with unconditional jumps, even if this makes the loops longer, as otherwise the unconditional jump could have been eliminated by moving the conditional jump at the end of the loop. On x86-64, an alternative to unconditional jumps is the LFENCE instruction, which is a barrier for speculative memory accesses.
The so-called load-acquire instruction of Arm might also implement the textbook behavior of load-acquire, of ordering the memory accesses, despite the fact that this behavior is always superfluous, but it must also have the undocumented behavior of being a speculation barrier for memory accesses, otherwise the Arm CPUs would have been very inefficient. However, dedicated speculation barriers of the 2 kinds needed inside the loop and outside the loop would have been more efficient than a load-acquire instruction.
well it depends on your error bars. On many modern system you can have +/- 5% variation or more run to run just due to the non-determinism present in modern CPU architectures and operating systems (even things like room temperature, time of day, the number of environment variables, etc, can affect this). While you could maybe run a set of careful experiments to characterize and remove this, in my experience most researchers don't bother. So something as small as 3% would need a lot of convincing to me to make the argument that it is significant.
First, is a measured improvement actually real or just an artifact of noise?
Second, if it is real, is 3% anywhere close to the true value?
Third, if 3% is real, is it an important difference?
I'm just commenting on the third one. If 3% is real, it's important.
I'm inclined to believe there's a real improvement. They made a lot of different measurements. If the measured improvement was a result of noise, you'd expect a lot of variation an a lot of measurements where TSA was actually faster, and then 3% was the average of that variation. There was a lot of variation (expected, because they were measuring different things) but nearly all of them had TSO being either neutral or slower. Looking at their benchmark graphs, I see two (out of dozens) where TSO was faster.
As far as being close to the true value, these results suggest there is no single true value, as it depends on the workload. No surprise there.
It’s a question of how much resources to allocate to the hardware team, and how much resources to be distributed diffusely to the software engineers but especially to the compiler team.
Even your linked paper contends that the actual observed slowdown is as much as 22% in the Geekbench example, but the thesis is that the slowdown is not inherent to TSO, but merely to the specific hardware implementation. Is it worthwhile for a company to optimize its TSO to chase the final gains, or is it better not to have this feature in the first place and just change the compiler?
Indeed my instinct is that it is better to do this in software, where the programmer clearly communicates which stores are ordered, and which may happen in arbitrary order.
> but I've seen some compelling arguments that a relaxed model doesn't necessarily have much of a benefit,
"ELI5" oversimplified explanation why this is insane and can be no other way:
You write A (not in cache), you write B, you write C, ... you write Y, you read Z (in L1d).
In ARM, when A misses L1d, L2, and L3, you can issue writes to B..Y, and the read of Z (which hits in 2 cycles) and go on your merry way, your pipeline sure of the value of Z.
With TSO you CANNOT allow the writes to B..Y to be seen by anyone before A, because everyone expects to only see them after A, so you either buffer them or, eventually, sit on your proverbial ass and wait for A to drain. You might have the buffers to put off the consequences for a while, but that is explicitly a cost ARM lacks, AND(this one hurts the most) you can't simply let the load of Z become an architecturally committed observation before A is done. You can speculate it, but you have to preserve the TSO ordering constraints. Eventually you'll run out of write-buffer slots or other resources, or find that your guess of Z's value was ... wrong. This is an example of how TSO loses perf compared to relaxed. The list of how it gains perf compared to relaxed is shorter: { }
So, in some cases TSO is the same perf as relaxed, in no cases it is faster, in some cases it is slower. So it must be slower overall, since "overall" is a weighted mix of those. "By how much" is a question of detail and workload. However, unless your workload miraculously never suffers a cache miss while a later instruction hits, TSO must be slower. :)
Because it imagines that no library other than libc has an ABI that depends on intmax_t.
Suppose I have a libfoo that has a public function that takes an intmax_t parameter. Or that has a public struct with an intmax_t field. It will be compiled for a particular definition of intmax_t. If you try to link it with a program that uses a different definition, it will fail.
The article's solution with the "MY_LIBC_NEW_CODE" define cannot work because no existing C code knows about "MY_LIBC_NEW_CODE".
The proposed mechanism is somewhat useful to a library that wants to provide multiple incompatible implementations of a function. (But this is mostly only interesting for libc implementations that need to handle historic incompatibilities between all the various Unix specs. Other libraries can just give their new, incompatible function a new name.) It's useless if you want to make an incompatible change to a type definition.
> Because it imagines that no library other than libc has an ABI that depends on intmax_t.
I don't get quite the same impression. The sense I get is more that such a change would basically need to happen "bottom-up":
> Some of [the scenarios that aren't fixed by this proposal] are just the normal dependency management issues. If you build a library on top of something else that uses one of the changed types (such as intmax_t or something else), then you can’t really upgrade until your dependents do.
>
> For those of us in large ecosystems who have to write plugins or play nice with other applications and system libraries, we’re generally the last to get the benefits.
In which case the benefit of the proposal (as far as I understand) is that such bottom-up changes can occur without forcibly breaking other consumers.
It was never really possible to compile a library with one C compiler and expect it to link against code produced by another C compiler, unless both compilers happen to agree on specific ABI details that are either defined outside the C standard or not at all.
And to be honest, this sort of compiler-specific ABI interoperability is a non-problem that doesn't need solving, it's at most relevant for software developers of closed source libraries who distribute the libraries as precompiled blobs. But those must be stamped out for different target-triples anyway.
Compiler interoperability is the only ABI related problem area that's remotely in the scope for the C standard, but IMHO not even that (it's really not a problem that needs solving).
Ultimately any ABI discussions need to happen between CPU and OS vendors, compiler toolchains implement whatever comes out of those discussions.
> Compiler interoperability is the only ABI related problem area that's remotely in the scope for the C standard
idk, given how ABI impacts the evolution of C I think it's not unreasonable to provide a mechanism by which ABI can be evolved even if it's not specifically for compiler interop.
> Ultimately any ABI discussions need to happen between CPU and OS vendors, compiler toolchains implement whatever comes out of those discussions.
I think part of the article author's reasoning for proposing this feature is that toolchains have implemented something like this feature to try to address ABI issues and that the rest of the ecosystem could benefit from a similar technique.
Huh, compiler interoperability is extremely useful. It usually works by ABI groups defining a common ABI for each architecture and compilers then following these ABIs (although not required a compilers that does not is poor)
It's useful for closed-source developers who want to sell their libraries as precompiled binary blobs for static linking, but as soon as MSVC is involved that idea of "one library for different compilers" is out the window anyway ;)
For areas like application plugins via DLLs it's the OS ABI that matters.
I don't understand this comment. There are well-defined ABIs for many platforms. Sometimes there is a defacto ABI defined by the first compiler supporting this platform, but generally there ABI groups that agree on a common ABI for each architecture. This then allows code compiled by different compiler to be linked against common libraries - not just glibc. I can compile my projects with either clang, gcc, or some other compiler and link statically or dynamically against all the same libraries distributed by my distribution regardless of which compiler was used to compile them. This is extremely useful.
> Upon error, crypt_r, crypt_rn, and crypt_ra write an invalid hash to the _output_ field of their _data_ argument, and crypt writes an invalid hash to its static storage area. This string will be shorter than 13 characters, will begin with a ‘*’, and will not compare equal to _setting_.
reply