views:

1791

answers:

13

In C, is i+=1; atomic?

+8  A: 

No, i += 1 is not guaranteed to atomic. Changing memory values is never atomic. It implies reading from memory, incrementing the value and writing the result back to memory.

Martinho Fernandes
That's not entirely true: there are simple operators (such as increment) that **can** be mapped to atomic machine code operations.
jldupont
Is it in the standard as: "no, it isn't." or is it that it's up the the implementation/archtiecture?
San Jacinto
yes but C says nothing about atomicity.
Jason S
But in the case at hand here, this **may** or not be true depending on optimization results.
jldupont
Not quote right. The standard *does* mention atomicity, see <signal.h>.
DevSolar
is that really in the C standard? (or just one of the standard libraries)
Jason S
The standard library is *part* of the C standard, hence its name.
DevSolar
Not sure if I'm being thick, but how can you even assume this is a memory operation? "i" could be in a register, surely? (Unless we're assuming volatile).
stusmith
Because you can't tell when it's stored in a register or memory, you can't make assumptions about atomicity, because messing with memory is not atomic.
Martinho Fernandes
While an increment *could* be atomic, I'm not aware of any compilers that implement it as such.
Mark Ransom
+1  A: 

No, it isn't. If the value of i is not loaded to one of the registers already, it cannot be done in one single assembly instruction.

DrJokepu
Yes it can -- I've done this on x86. The compiler is *not* guaranteed to emit an atomic instruction here though.
LnxPrgr3
On x86 and x86_64, with gcc (so definitely not portable): `#define ATOMIC_ADD(x, y) asm volatile("lock add %1, %0" :"=m" (x) :"g" (y))`
LnxPrgr3
+1  A: 

Not usually.

If i is volatile, then it would depend on your CPU architecure and compiler - if adding two integers in main memory is atomic on your CPU, then that C statement might be atomic with a volatile int i.

gnud
No, even with a volatile int, an increment still consists of a read, an increment and a store. CISC architectures such as the x86 typically combine the increment with either the load or the store, but the entire sequence is not atomic. Volatile doesn't help in this case.
jalf
Not necessarily - you could have a CPU with an atomic memory increment instruction, but a C compiler which still outputs three instructions (load/increment/store) for a volatile int. If the single atomic instruction is faster then that's a missed optimization by the compiler, but AFAIK not illegal.
Steve Jessop
Samuel
@Samuel: You've apparently never studied the x86 ISA very closely. It has a prefix that can make most any instruction atomic!
Novelocrat
Who said this was about the x86?
DevSolar
@Novelocrat. You are right, I haven't studied x86 ISA in almost a decade(and never very closely). I'm curious, which is that "prefix"?But, sincerely, I would be very surprised if any widely used C compiler generates that "prefix" automatically for that C code. Do you know of any?
Samuel
I think Novelocrat is referring to the lock prefix, though it only works for a limited subset of instructions. ADD is one of them though, and ADD can take a memory operand as its destination, so you can use it to atomically increment a variable.
LnxPrgr3
+2  A: 

It really depends on your target and the mnemonic set of your uC/processor. If i is a variable held in a register then it is possible to have it atomic.

Dan Cristoloveanu
+66  A: 

The C standard does not define whether it is atomic or not.

In practice, you never write code which fails if a given operation is atomic, but you might well write code which fails if it isn't. So assume it isn't.

Steve Jessop
This answer makes much more sense then the one being up-voted right now (from M. Fernandes)
jldupont
This should be the accepted answer.
San Jacinto
agreed, although I am starting a rule of thumb that "i+=1;" is not atomic for portability.
Crazy Chenz
@Crazy: that's exactly right. If you assume it isn't atomic, but it is, then no harm will come of the assumption except that there may exist platforms where you're doing unnecessary locking. The right thing is probably to define your own atomic_increment function (or macro) in your portability layer. Then on Windows it would call InterlockedIncrement, on an embedded platform it might disable interrupts around the increment, etc. The default POSIX-portable implementation maybe uses a global semaphore, that has to be initialised safely. The platform-of-wonder just increments.
Steve Jessop
If the C standard doesn't say, then the answer to the OP's question is, "No". End of answer. It would be like asking if `i+=1` is carbon neutral. If the standard is silent, then the answer must be *no*. If some implementation happens to ensure that the CPU absorbs one carbon dioxide molecule for every carbon dioxide molecule generated during the increment, then that doesn't mean that, *in C*, increment is carbon neutral, or even that *in C* increment *may* be carbon neutral. It just means that some environmentalist compiler writer went nuts one day. :)
Dan Moulding
That's true. But the answer to the question "is it atomic" is "no", and the answer to the question "is it non-atomic" is also "no". Rather than act like an inscrutable oracle which tries to trick querants into misunderstanding the answers to questions, I have drilled a little deeper than the question strictly calls for. This isn't a quiz show or a hostile cross-examination, I demand the right to give more than a yes/no answer ;-)
Steve Jessop
@Steve, as you should when considering the semantics of a language specification. +1 from me.
San Jacinto
This is further confused by the fact that "non-atomic" is defined in terms of something that might happen, not something which definitely happens. So if an implementation defines, "increment is atomic", I guess maybe you could argue that despite being atomic, increment is *also* non-atomic, since it does not contradict any defined behaviour of a non-atomic operation. So maybe the answer to that second question should be "yes". But anyway, I have tried to answer in a way which explains the situation. You cannot be sure your compiler won't emit an atomic insn for increment, but I'd bet it won't.
Steve Jessop
Atomic means non-divisible (from the greek *atomos*). Therefore non-atomic should mean divisible. I think if "increment is atomic" it is not "non-atomic".
Martinho Fernandes
One thing to add: There are platform-specific functions for doing atomic increment. Under Windows, look at the Interlocked functions.
msemack
+13  A: 

No.

The only operation guaranteed by the C language standard to be atomic is assigning or retrieving a value to/from a variable of type sig_atomic_t, defined in <signal.h>.

(C99, chapter 7.14 Signal handling.)

DevSolar
jldupont
I had never heard of this type, but a (brief) google search seems to show that it can only be *accessed* atomically. Am I understanding that right?
Roel
@ jldupont: Absolutely true. The question was if the operation is atomic *in the language C*, not a specific platform / compiler setting. The only place the *language* makes any claims of atomicity is `sig_atomic_t`, so you have to assume any other operation is `not` atomic to be on the safe side.
DevSolar
@ Roel: The standard states that *accessing* this type should be atomic; I read this to mean using the operator "=" either to set or retrieve a value, because it would be somewhat useless if all you could do is reading from it.
DevSolar
+1: Best answer, for sure. Everybody else here is smoking crack, or something. The question was about C (not whether increment is atomic in *some* implementations on *some* architectures). You are correct DevSolar, the answer is NO! It's *not* atomic in C. If it happens to compile to an atomic operation on some platform, it's not because the C standard made it so, it's because the implementation did.
Dan Moulding
@Dan: I understood "in C" to mean "in conforming C implementations". I don't recognise the utility of this platonic ideal of the C language, in which for all integers N "it is false that int is of width N bits", and simultaneously "there exists an integer N such that int is of width N bits". Hence the logical rules of induction and generalisation do not apply. "In C", int "may be" of width 32 bits. Also it "may be" of width 23 bits. In C, increment "may be" atomic. If I say something is false "in C", I mean it's forbidden, not that it isn't required. Sorry if that's a crack hallucination.
Steve Jessop
@ Steve: No, in C, **increment is not atomic**. If you need an atomic operation, use your platform's corresponding API. Relying on implementation-defined behaviour (which might change with compiler options or version without further notice) is the road to pain. The value of "this platonic ideal of the C language" is that your code doesn't randomly break for no apparent reason when your co-worker compiles it on a different machine. Been there, done that for about ten years.
DevSolar
Yes, I'm very familiar with writing portable code. Are you equally adamant that in C, **signed integer types are not 1's complement**? I prefer to say that in C, signed representation may be 1's complement, to avoid implying a 2-valued logic which isn't appropriate. I haven't noticed it affecting the quality or portability of my code to express the standard in terms of requirements and prohibitions on implementations, rather than true or false statements "in C". Either is fine IMO as long as you know what it means for your program, but I think my way is less likely to mislead.
Steve Jessop
Do you happen to mean 2's complement? ;-)
DevSolar
1's complement is what I meant to say, but of course the same applies to 2's complement: "in C, signed integers may be 2's complement"; "in C, signed integers may be sign-magnitude". Actually I normally wouldn't say that integers "may be" 2's complement, I'd say they're "almost always" 2's complement. That's not a statement about the standard, though, it's a review of currently-available C implementations. By the same token, increment is almost-always interruptable.
Steve Jessop
Note that the C99 standard only guarantees that in an asynchronous signal handler that a `sig_stomic_t` object can only be written (in a well-defined manner). Reading from a `sig_atomic_t` object in an asynchronous signal handler is not defined. So `i += 1` would not be well defined in this particular case anyway (though `i = 1` would be).
Michael Burr
@Steve: What's the use in saying signed integers *may* be one type versus the other, or in saying that increment *may* be atomic, simply because the standard doesn't say one or the other? Should we assume that the compiler *may* rain down rubber chickens on your head when you dereference a null-pointer, just because the standard doesn't say that it won't? If you write a program that depends on raining rubber chickens, then you'll have a serious portability problem, no? So why not just say "No, rubber chuckens will not rain down". Similarly, "No, increment is not atomic".
Dan Moulding
"What's the use in saying signed integers may be one type versus the other". In order to distinguish between the three possible situations: (a) the standard requires that integers be 1's complement (we say, "integers are 1's complement"; (b) the standard requires that integers are not 1's complement (I say, "integers are not 1's complement); (c) the standard neither requires it nor forbids it (I say, "integers may be 1's complement", you say "integers are not 1's complement"). See RFC 2119 for terminology to handle a 5-valued logic which is similar to the 3-valued logic of the C standard.
Steve Jessop
And it is wrong to say that rubber chickens "will not" rain down. They might, or they might not. You cannot depend on them raining, and you cannot depend on them not raining, so it is extremely misleading to say that they will not rain. (Misleading as far as the standard is concerned. Obviously you can make a shrewd prediction based on your knowledge of C implementations, but that's a whole different statement). If anyone sees that I say, "integers in C may be 1's complement", and writes code relying on them to be, then I think it's obviously their mistake. They should read RFC 2119.
Steve Jessop
All I'm saying is that nobody should encourage others to expect that rubber chickens might rain down (even though in *theory* it's possible), because it would be patently stupid to rely on such behavior. Same goes for atomic increment.
Dan Moulding
And for the record, I don't have a problem with your answer. I just like bringing up the topic of rubber chickens any chance I get ;)
Dan Moulding
@ Steve: I get your point now. But I've seen too many developers being bitten by "but it worked here", so I've grown a bit paranoid and tend to formulate absolutes. Where Dan here likes rubber chicken, I usually tell people that "undefined behaviour" means their hard drive will get deleted. ;-) So you are right, the *correct* statement would be **In C, increment is not *guaranteed* to be atomic**. I still think the more instructive statement is the one I made: *It is not atomic*. For all practical purposes.
DevSolar
Yes, in this case "it's not atomic" works well, because as I said in another comment there's no behaviour of non-atomic things which someone could wrongly rely on as a result. All that I don't like is in general dividing statements about what happens in C into "true" and "false", because there is such a large middle ground of "not specified". If someone wants to delete a hard-drive, it makes a big difference to them whether undefined behavior means their hard-drive "will" be deleted, or "may" be deleted at the discretion of the implementation.
Steve Jessop
+1  A: 

The C / C++ language itself makes no claim of atomicity or lack thereof. You need to rely on intrinsics or library functions to ensure atomic behavior.

Jason S
The _two_ C / C++ language_s_!
Thomas Padron-McCarthy
Or more, for those of us who have to deal in both C89 and C99.
Steve Jessop
C++0x adds claims of atomicity for a number of operations does it not?
Dan Olson
+1  A: 

Just put a mutex or a semaphore around it. Of course it is not atomic and you can make a test program with 50 or so threads accessing the same variable and incrementing it, to check it for yourself

nikifor
+4  A: 

Whether the expression is atomic or not depends only on the machine code that the compiler generates, and the CPU architectre that it will run on. Unless the addition can be achieved in one machine instruction, its unlikely to be atomic.

If you are using Windows then you can use the InterlockedIncrement() API function to do a guaranteed atomic increment. There are similar functions for decrement, etc.

Andy Johnson
A: 

Although i may not be atomic for the C language, it should be noted that is atomic on most platforms. The GNU C Library documentation states:

In practice, you can assume that int and other integer types no longer than int are atomic. You can also assume that pointer types are atomic; that is very convenient. Both of these assumptions are true on all of the machines that the GNU C library supports and on all POSIX systems we know of.

Tomas
Note that "atomic" here means atomic read and atomic write. It does not apply to i+=1.
Tomas
LnxPrgr3
+1  A: 

No, the C standard doesn't guarantee atomicity, and in practice, the operation won't be atomic. You have to use a library (eg the Windows API) or compiler builtin functions (GCC, MSVC).

Christoph
+6  A: 

Defined in C, no. In practice, maybe. Write it in assembly.

The standard make no guarantees.

Therefore a portable program would not make the assumption. It's not clear if you mean "required to be atomic", or "happens to be atomic in my C code", and the answer to that second question is that it depends on a lot of things:

  • Not all machines even have an increment memory op. Some need to load and store the value in order to operate on it, so the answer there is "never".

  • On machines that do have an increment memory op, there is no assurance that the compiler will not output a load, increment, and store sequence anyway, or use some other non-atomic instruction.

  • On machines that do have an increment memory operation, it may or may not be atomic with respect to other CPU units.

  • On machines that do have an atomic increment memory op, it may not be specified as part of the architecture, but just a property of a particular edition of the CPU chip, or even just of certain core logic or motherboard designs.

As to "how do I do this atomically", there is generally a way to do this quickly rather than resort to (more expensive) negotiated mutual exclusion. Sometimes this involves special collision-detecting repeatable code sequences. It's best to implement these in an assembly language module, because it's target-specific anyway so there is no portability benefit to the HLL.

Finally, because atomic operations that do not require (expensive) negotiated mutual exclusion are fast and hence useful, and in any case needed for portable code, systems typically have a library, generally written in assembly, that already implements similar functions.

DigitalRoss
+1 for the elaborate explanation
Ruben Steins
+1 For mentioning atomic wrt other CPU units.
Chris O
+1  A: 

The answer to your question depends on whether i is a local, static, or global variable. If i is a static or global variable, then no, the statement i += 1 is not atomic. If, however, i is a local variable, then the statement is atomic for modern operating systems running on the x86 architecture and probably other architectures as well. @Dan Cristoloveanu was on the right track for the local variable case, but there is also more that can be said.

(In what follows, I assume a modern operating system with protection on an x86 architecture with threading entirely implemented with task switching.)

Given that this is C code, the syntax i += 1 implies that i is some kind of integer variable, the value of which, if it is a local variable, is stored in either a register such as %eax or in the stack. Handling the easy case first, if the value of i is stored in a register, say %eax, then the C compiler will most likely translate the statement to something like:

addl    $1, %eax

which of course is atomic because no other process/thread should be able to modify the running thread's %eax register, and the thread itself cannot modify %eax again until this instruction completes.

If the value of i is stored in the stack, then this means that there is a memory fetch, increment, and commit. Something like:

movl    -16(%esp), %eax
addl    $1, %eax
movl    %eax, -16(%esp)  # this is the commit. It may actually come later if `i += 1` is part of a series of calculations involving `i`.

Normally this series of operations is not atomic. However, on a modern operating system, processes/threads should not be able to modify another thread's stack, so these operations do complete without other processes being able to interfere. Thus, the statement i += 1 is atomic in this case as well.

Daniel Trebbien
I am assuming, of course, that your program is not being debugged by a debugger, that your program does not have a security problem which allows an attacker to corrupt stack space or inject machine code, and that your program does not corrupt its own stack (by, for example, returning a pointer to a local variable, the value of which is then modified concurrently by another thread of the process).
Daniel Trebbien