How to trigger races reliably in the Linux kernel
people.kernel.org
people.kernel.org
Check out the EXAMPLES section of the manual page. You can use the mechanisms to inject delay on some percentage of executions, and more generally some integer value can be injected, which can be used to simulate device failures (EIO) or whatever.
It's very powerful for creating reliable reproducers for all kinds of failures, including race conditions. And the KPI is not quite as verbose as the one presented in TFA.
This article makes the common mistake of saying that a race condition is inherently a bug.
A race condition just means that observable program behaviour is dependent on the interleaving of two tasks. A race condition is only a bug if you don't want one of the possible interleavings.
You can often find great performance optimisations by working out how to work with race conditions rather than disallowing them.
Indeed, there is even a debate about this issue in the talk page of wikipedia [https://en.wikipedia.org/wiki/Talk:Race_condition#Race_condi...]
https://link.springer.com/referenceworkentry/10.1007%2F978-0...
It says "Race conditions that can cause unintended non-determinacy are programming errors." and provides 23 references to the literature that you can follow for more history on it.
Worth noting however, that the first article I found in those 23 references that actually used the phrase 'race condition' (in "What are race conditions? Some issues and formalizations") explicitly stated:
> However, in the literature, there seems to be little agreement as to precisely what constitutes a race condition. Indeed, two different notions have been used, but the distinction between them has not been previously recognized. Because no consistent terminology has appeared, several terms have been used with different intended meanings... [0]
Further,
> Data races cause nonatomic execution of critical sections and are failures in (nondeterministic) programs
All I'm trying to suggest is that colloquially, people will use this phrase to mean a lot of things, and I'm not sure the literature is entirely clear cut.
Yes data races are always bugs, according to Padua et al.
But I think from some accepted definitions (such as Padua et al) a data race specifically is a bug, so this data interleaving if we're happy with it isn't a data race because it isn't a bug.
jerf disagrees in last sentence of other comment: https://news.ycombinator.com/item?id=23079788
https://github.com/oracle/graal/blob/4553ea71f15c9e4721565e9...
You can argue this is a bug and they shouldn't write like this, but they don't consider it a bug and they do write like this.
So your choices here tend to be: sometimes wrong, or completely useless.
That's a data race, the result will vary between executions because the row order will be different depending on how fast the various servers respond, but acknowledging that the order is not-well defined or guaranteed makes this data race accomodatable and even useful, since that gives a performance benefit compared to any solution that needs to ensure a specific order of these rows.
Since the header on each fragment contained the total message size, I was able to pre-allocate the full size of the message upon receipt of the first fragment.
Then, as fragments arrived, I would copy their data into their respective areas of the message.
Typically, everything would arrive in order, so the message would be copied from beginning to end, piece by piece.
However, since this was Ethernet/UDP, it was possible for frames to arrive out of order.
This would result in the message being pieced together, with each fragment filling in its hole until all fragments have been received.
I guess this is a form of a data race? Or rather, a case where a data race at least wasn't detrimental.
There is no data race in your example, since the fragments are all written to different parts of memory, unless you had something else reading the message while the individual fragments were still being written.
The second thread does an unsynchronized fetch of the queue length, and then uses that fetched length as a condition in a loop that does a synchronised dequeue of a single item.
In this case, the race condition is not a problem, because the only place that data is removed is in that loop, which is a synchronised access.
So the worse case for a race here is that the length that's been read is less than the actual length, which is not a problem because that new data will just be handled the next time round.
How critical this ends up being to the program is heavily dependent on the queue data structure and how its being manipulated. But in a simple copy/linked list type situation referencing garbage data is quite likely.
A lot of traditional comp sci programs are plenty happy to teach about data synchronization primitives but completely fail to mention that most general API (posix/etc) primitives also have read/write fences implied. Those fences are as important on any processor made in the last two decades as the atomic operations themselves. As generally the implementations also provide both architectural memory barriers as well as compiler level fencing to assure the compiler isn't reordering the primitive with the code it is intended to protect. Going further, many architectures provide unfenced atomics. So, if you decide to code your own atomic_inc/swap/etc you have to also understand the memory model of the target machine before you have actually created something equivalent to what is taught in your average comp-sci department.
// Called from Thread 1.
public void AddData(Data theData) {
lock(dataQueue) {
dataQueue.Enqueue(theData);
}
}
// Worker for Thread 2.
private void ProcessingThread() {
while(true) {
int length = dataQueue.Count;
for (int i = 0; i < length; i++) {
Data curData;
lock(dataQueue) {
curData = dataQueue.Dequeue();
}
// Process data.
}
// Sleep for a short while.
}
}
So, from what I can see, in the event where the length is updated before the data is actually inserted, Thread 2 is still forced to wait until Thread 1 is finished before it can access it so it's still safe. Though if I'm wrong, please tell me. No one wants garbage data.
Also, it is possible that Count is not a member but an accessor and it might return garbage or crash if it sees some inconsistent data.
Still, both of the above can be rare occurrences. The reason that you are not seeing no particular issues is because you are basically busy waiting and polling the queue (i.e. the sleep comment); if you replaced the dataQueue.Count with just a random number generator, the code will still work. If you were doing proper signaling instead of sleeping, then your code will get stuck in case of a missed wakeup.
You are correct in that `Count` is a property, and it could be doing extra things, but according to the implementation [1] it just returns the value of a private integer. Of course, this is an implementation detail and shouldn't be relied upon, but I'm not sure how much that could be changed.
However, you are mistaken about the code continuing to work if `dataQueue.Count` were replaced with an RNG, or if it were otherwise higher than it should be. The `Dequeue` function raises an exception if called on an empty queue. This one is part of the API, not an implementation detail. An uncaught exception here would crash the thread, not just blindly carry on.
Of course, I'm no expert, and could just be talking out of my ass.
[0] https://docs.microsoft.com/en-gb/dotnet/api/system.collectio... [1] https://github.com/dotnet/runtime/blob/master/src/libraries/...
Count is implemented as a simple read currently, but that's not guaranteed to be the case in the future (that's the whole reason for having a property.
Fair enough about the rng, I'm not really a c# programmer, so I just assumed that dequeue would return a null on an empty queue.
I'm not an expert either, and certainly not a c# expert (although I kind of like the language, I haven't written a line in 7 years), so YMMV.
In certain kinds of signals intelligence software, the primary concern is access to the current frame of data. You don’t want to miss an RF peak that lasts just a few nanoseconds. It can be preferable to have half the the frame overwritten mid-processing every few million iterations than to slow down each iteration and force a lower overall refresh rate.
One practical example of using those is Hogwild, which is an implementation of stochastic gradient descent which skips synchronization on individual parameter updates, assuming that it'll converge even if some writes are lost or some reads are stale.
https://papers.nips.cc/paper/4390-hogwild-a-lock-free-approa...
It is possible (and in rare cases, desirable) to have data races while still having a perfectly safe program.
Even if your program is not conforming to whatever standard, it may be very well be useful and working in most compilers out there.
As an example, Linux is not conforming C, including triggering UB. But at least two major compilers support the intended semantics even if they are forbidden by the standard.
Linux, as Linus has said, isn't written in ISO C it's written (or was) in GNU C. The two had something of a symbiotic relationship for a long time. Which is why porting it to LLVM was such a tremendous effort.
Which is to say, Linux conforms to the memory model of the compilers it compiles on (or vice versa). Not ISO C's memory model. So I'm not sure how your example is relevant.
If your software is designed with that in mind, then a data race is not a bug.
Data races are undefined behavior on all major programming languages (C, C++, Rust, Java, Go, Swift, ...) and all major compilers compile code under the assumption that they do not happen.
If your program has a data-race, neither the language specification nor the compiler make any guarantees about the behavior of such programs.
Needles to say, this is neither safe, nor desirable, nor doing so produces perfectly safe programs.
The idea that data-races are safe because the load and store memory instructions that the CPU has are atomic is completely flawed, because it ignores the fact that the CPU does not execute the program you wrote, but the machine code that the compiler generates, and the compiler can and will reorganize non-atomic loads and stores under the assumption that they don't need to be atomic.
If your program has a data-race, the compiler provides no guarantees. It does not guarantee that the binary will reach the location where the data race happens. It does not even guarantee that the binary produced will be an executable binary, or that it will produce a binary at all (e.g. it does not guarantee that compilation terminates successfully).
* Data races using normal memory access function are impossible in safe code, and undefined behaviour in unsafe code. So unsafe code attempting this is incorrect.
* Data races using atomic types are possible in safe code. Some of the setup code might be unsafe internally while presenting a safe API (e.g. creating shared memory and giving you an `&[AtomicU8]` to that memory).
* Other race conditions (mostly non-deterministic order of lock acquisition) are also possible in safe code. The typical example of this is that writing to the console from multiple threads uses locks on individual write calls, which prevents torn writes but the order of those write outputs in non deterministic.
The average developer assessment that some race condition is completely harmless is wrong; there's usually a bug in the complicated state space somewhere.
A performance optimization involving a deliberate race condition should be pretty much your last resort.
Even the obvious ones are often less of a good idea than they may look, like a leaky incrementing counter for logging purposes. You might model that as being unlikely to lose more than a couple of percent, but I've seen cases where it lost the majority of logged events. Granted, this probably won't crash your program, but it can still result in surprisingly deceptive logging.
And many race conditions don't have anything to do with the memory model or compiler optimizations.
For example, poorly structured response-handlers in JavaScript. If the code assumes that request R1 always returns before request R2, things may misbehave if that assumption is violated. That's a race condition, but as you say, it's nothing to do with memory models or compiler trickery, as JavaScript gives you just the one thread (not counting workers).
That's not correct. Look at chrisseaton's definition.
If the observable program behaviour doesn't change depending on the order in which the requests complete, there's no race condition. (In JavaScript this might be done with Promise.all.) You're right that not all race conditions are bugs.
Can you give an example of when one would (sanely) want to create a race condition?
For example two consumers pushing results to a single result queue is a race condition, because the order in which they arrive depends on timing and is non-deterministic. That's a pretty normal thing to have.
Many languages people think of as being safe and high level are extremely racey - Erlang is my go-to example - two processes sending messages to a third is a race. Which message do you get first? It's non-deterministic. But it doesn't have to be a problem.
That's what a race condition is - non-deterministic behavior of a thread-safe primitive.
> On the other hand, a true race condition in the queue could mean messages overwriting each other.
That's a data race, not a race condition.
(Code that is proven to work correctly without using synchronisation primitives, ie across the possible interleavings, is generally called "lock free")
Scheduler-dependent behaviour ends up being an absolute nightmare for automated testing and hunting of other bugs. It's not unreasonable to declare that all race conditions are bugs just for that reason.
I use 'race condition', but if you reserve that for something with bugs you'll need to invent a new term for the benign version.
More than once in my life I have thought that this was a bug, tried to correct it, and introduced another bug, followed by teeth gnashing, hair pulling, swearing, and then a revert.
Think of two worker threads pushing entires to a synchronised log. It's non-deterministic which order they arrive in the log, as different schedulings and other things will cause the threads to run in different orders (they 'race' to put entries in the log, we say), but it's not a bug, and it's not lock-free because the log is synchronised.
"Non-deterministic" works? However, I'm arguing that nondeterministic results from deterministic input are themselves a mild form of bug, like a compiler warning or "code smell".
Perhaps we also have to talk about causality and serialisability, clocks and timestamping. In a concurrent or distributed system it may not be easy to determine what order things happen in without unreasonable effort or performance impairment, but if so the system has to be designed so that doesn't matter.
> Think of two worker threads pushing entires to a synchronised log. It's non-deterministic which order they arrive in the log, as different schedulings and other things will cause the threads to run in different orders (they 'race' to put entries in the log, we say), but it's not a bug, and it's not lock-free because the log is synchronised.
Those I would call independent. Unless they're acting on something in common, in which case having the transactions serialised as A before B then logged as B before A is immensely annoying.
Otherwise, yes, agreed on all counts. It's telling that even when posing the question of what other term to use besides race condition, the op used 'non-deterministic'.
Informally, some people use it for that. But lock-free code is not that.
You may have lock-free code with locks, or lock-free code without data races, or lock-free code that can be shown to be incorrect (by your definition) yet work for the designed purpose...
That doesn't sound very lock-free?
I don't see how you can have that. If one process holding a lock halts then it will prevent system-wide progress, which is not allowed in the definition of 'lock-free'.
As others have mentioned already, if you had code that did that, that code would not be "lock-free". Lock-free requires progress in all circumstances even in the presence of ordering primitives (what we colloquially call "locks").
Are you replying to the right person? That's what I just explained to the person I was replying to. You've quoted part of my comment but left out the "...which is not allowed in the definition of 'lock-free'".
That doesn't sound right. I suppose you could have locks in the trivial sense, where it never actually blocks, but I don't imagine that's what you meant.
https://concurrencyfreaks.blogspot.com/2013/05/lock-free-and...
https://www.cs.yale.edu/homes/aspnes/pinewiki/ObstructionFre...
This other blog post [0] seems to use a stricter definition of lock-free which precludes any way to schedule threads which would cause progress to cease indefinitely. That seems to be what the ConcurrencyFreaks blog refers to as Wait-free.
Any experts in lock-free programming able to clarify things?
[0] https://preshing.com/20120612/an-introduction-to-lock-free-p...
Given the context, and the confusion about what race conditions even are in some of the comments in the thread, I'd say the comment opened some good discussion. GP also provided examples of race conditions that are simple to reason about elsewhere in the thread, and also explained the difference between race conditions in general, and data races.
No, it defines race condition, for purposes of the article, as something which is a bug. The author is only concerned with cases in which non-deterministic behavior causes errors.
When you write your own article, you are free to define "race condition" to include non-deterministic behavior that does not cause errors. But I don't think you can claim that the author's usage is simply wrong.