Compiler Support for Ensuring that a Statement is Atomic

This is slightly off-topic, as it involves implementation rather than the C 
language.

It frequently comes up in embedded systems that one wishes to ensure that a 
C-language statement is atomic.  One might have available functions or 
macros to disable or enable interrupts, so one might write:

   volatile int sempahore;

   DI();
   sempahore++;
   EI();

Whether an increment can be handled atomically depends on the processor, 
where in memory the variable is located, its size, and on specific decisions 
the compiler makes.

Other operations that one might wish to ensure atomicity with include 
assignments, bitfield assignments, tests, etc.

For example, in the code:

   volatile unsigned long x;

   if (x > 29204) ...

there might be a problem because an asynchronous process may update the 
variable and cause the test to get inconsistent bytes as it performs the 
test.

In most cases, one can protect the statements of concern with DI()/EI() or 
find a way to guarantee atomicity.  The issue is that this method of 
protection can be inefficient.  It consumes memory, consumes CPU cycles, and 
affects the timing of interrupts.

Here is my question:

Has anyone seen any compilers that support guaranteeing that a certain 
statement or test is atomic?

What I'd be looking for is something like:

#pragma ASSERT_ATOMIC_STATEMENT_START
  semaphore++;
#pragma ASSERT_ATOMIC_STATEMENT_END

The pragmas would advise the compiler to:

a)Try to compile the statement atomically (using a single instruction), and

b)Create an error if it can't be compiled atomically.

This would save the expense of DI()/EI(), or generate an error if the 
statement can't be compiled atomically.

Is there anything like this in the world?

Thanks, Datesfat 

Datesfat Chicks wrote:
> This is slightly off-topic, as it involves implementation rather than 
> the C language.
> 
> It frequently comes up in embedded systems that one wishes to ensure 
> that a C-language statement is atomic.  One might have available 
> functions or macros to disable or enable interrupts, so one might write:
> 
>   volatile int sempahore;

Hey, that is exactly how I usually mistype "semaphore". Must be 
something in the qwerty layout...

>   DI();
>   sempahore++;
>   EI();
> 
> Whether an increment can be handled atomically depends on the processor, 
> where in memory the variable is located, its size, and on specific 
> decisions the compiler makes.
> 
> Other operations that one might wish to ensure atomicity with include 
> assignments, bitfield assignments, tests, etc.
> 
> For example, in the code:
> 
>   volatile unsigned long x;
> 
>   if (x > 29204) ...
> 
> there might be a problem because an asynchronous process may update the 
> variable and cause the test to get inconsistent bytes as it performs the 
> test.

The C standard (C99, at least, I believe) defines the type 
"sig_atomic_t" which is guaranteed to be accessible (read/write) as a 
whole, so it solves the problem with the ">" test, but not the problem 
with increment operations. However, "sig_atomic_t" is guaranteed only to 
be at least 8 bits wide, not "long". In practice "sig_atomic_t" is 
probably as large as the processor's memory interface allows, so it 
could be as wide as "long".

> In most cases, one can protect the statements of concern with DI()/EI() 
> or find a way to guarantee atomicity.  The issue is that this method of 
> protection can be inefficient.  It consumes memory, consumes CPU cycles, 
> and affects the timing of interrupts.
> 
> Here is my question:
> 
> Has anyone seen any compilers that support guaranteeing that a certain 
> statement or test is atomic?

I haven't, except for sig_atomic_t, which does less than you are asking for.

> What I'd be looking for is something like:
> 
> #pragma ASSERT_ATOMIC_STATEMENT_START
>  semaphore++;
> #pragma ASSERT_ATOMIC_STATEMENT_END
> 
> The pragmas would advise the compiler to:
> 
> a)Try to compile the statement atomically (using a single instruction), and
> 
> b)Create an error if it can't be compiled atomically.

A good suggestion. But I suspect that compiler writers would find it 
easier to introduce compiler-specific "built-in" functions for things 
that can be done atomically, such as increment/decrement of a memory 
word, or swapping the contents of a memory word and a register. Maybe 
some such functions could be standardised? For example, a function 
called "atomic_increment" (decorated with suitable '_' marks to make it 
a reserved identifier). The compiler would accept or reject a call of 
such functions depending on the types of the parameters and on the 
capabilities of the target processor.

GCC has a set of built-in atomic memory access functions 
(http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html). It 
seems that they don't support counting semaphores but do support locks 
(binary semaphores).

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Niklas Holsti <niklas.holsti@tidorum.invalid> wrote:
<snip>
> A good suggestion. But I suspect that compiler writers would find it 
> easier to introduce compiler-specific "built-in" functions for things 
> that can be done atomically, such as increment/decrement of a memory 
> word, or swapping the contents of a memory word and a register. Maybe 
> some such functions could be standardised? For example, a function 
> called "atomic_increment" (decorated with suitable '_' marks to make it 
> a reserved identifier). The compiler would accept or reject a call of 
> such functions depending on the types of the parameters and on the 
> capabilities of the target processor.

IIRC, C++0x has <cstdatomic>. The proposal also put forth stdatomic.h, which
I think is being considered for inclusion in C1x.

There were/are actually many similar proposals, but I believe the one that
was actually settled on was this one:

http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2007/n2324.html

Op Sat, 16 Jan 2010 01:52:21 +0100 schreef Datesfat Chicks  
<datesfat.chicks@gmail.com>:
> This is slightly off-topic, as it involves implementation rather than  
> the C language.
>
> It frequently comes up in embedded systems that one wishes to ensure  
> that a C-language statement is atomic.

For you maybe.

> One might have available functions or macros to disable or enable  
> interrupts, so one might write:
>
>    volatile int sempahore;
>
>    DI();
>    sempahore++;
>    EI();

Imagine how a program with DI/EI all over the place can wreak havoc on  
your worst-case interrupt latency.

> Whether an increment can be handled atomically depends on the processor,  
> where in memory the variable is located, its size, and on specific  
> decisions the compiler makes.
>
> Other operations that one might wish to ensure atomicity with include  
> assignments, bitfield assignments, tests, etc.
>
> For example, in the code:
>
>    volatile unsigned long x;
>
>    if (x > 29204) ...
>
> there might be a problem because an asynchronous process may update the  
> variable and cause the test to get inconsistent bytes as it performs the  
> test.

Don't do that then.  Use an OS service that ensures exclusive data  
ownership, like a messaging interface.

> In most cases, one can protect the statements of concern with DI()/EI()  
> or find a way to guarantee atomicity.  The issue is that this method of  
> protection can be inefficient.  It consumes memory, consumes CPU cycles,  
> and affects the timing of interrupts.
>
> Here is my question:
>
> Has anyone seen any compilers that support guaranteeing that a certain  
> statement or test is atomic?

No.

> What I'd be looking for is something like:
>
> #pragma ASSERT_ATOMIC_STATEMENT_START
>   semaphore++;
> #pragma ASSERT_ATOMIC_STATEMENT_END
>
> The pragmas would advise the compiler to:
>
> a)Try to compile the statement atomically (using a single instruction),  
> and

Assuming that the architecture guarantees that any instruction so  
generated is atomic.

> b)Create an error if it can't be compiled atomically.

And then what?  Try a different compiler?  Switch architectures?  Redesign  
the software?

> This would save the expense of DI()/EI(), or generate an error if the  
> statement can't be compiled atomically.
>
> Is there anything like this in the world?
>
> Thanks, Datesfat


-- 
Gemaakt met Opera's revolutionaire e-mailprogramma:  
http://www.opera.com/mail/
(remove the obvious prefix to reply by mail)

Boudewijn Dijkstra wrote:
> Op Sat, 16 Jan 2010 01:52:21 +0100 schreef Datesfat Chicks 
> <datesfat.chicks@gmail.com>:
>> This is slightly off-topic, as it involves implementation rather than 
>> the C language.
>>
>> It frequently comes up in embedded systems that one wishes to ensure 
>> that a C-language statement is atomic.
> 
> For you maybe.

For me, too, although only occasionally, not "frequently". But then I 
don't spend much time programming in C.

>> One might have available functions or macros to disable or enable 
>> interrupts, so one might write:
>>
>>    volatile int sempahore;
>>
>>    DI();
>>    sempahore++;
>>    EI();
> 
> Imagine how a program with DI/EI all over the place can wreak havoc on 
> your worst-case interrupt latency.

The effect on the worst-case interrupt latency does not depend on the 
number of DI/EI pairs "all over" the program, nor on how often they are 
executed. It depends only on the duration of the DI/EI pair that has the 
most code between the DI and the EI, in terms of the execution time of 
that code.

But why do you, Boudewijn, criticize Datesfat for mentioning DI/EI, when 
Datesfat's very aim is to *avoid* DI/EI by making the compiler use an 
instruction that is intrinsically atomic?

> Don't do that then.  Use an OS service that ensures exclusive data 
> ownership, like a messaging interface.

Such OS services tend to have longer interrupt-disabled regions than a 
simple "semaphore++" and thus more effect on the worst-case latency. And 
then we have the bare-board systems that use just background + 
interrupts with no OS to speak of. Finally, Datesfat's question and 
proposal are also applicable to the internals of OS services, which also 
could benefit from using intrinsically atomic instructions instead of DI/EI.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

"Niklas Holsti" <niklas.holsti@tidorum.invalid> wrote in message 
news:4b54246f$0$3863$4f793bc4@news.tdc.fi...
> Boudewijn Dijkstra wrote:
>> Op Sat, 16 Jan 2010 01:52:21 +0100 schreef Datesfat Chicks 
>> <datesfat.chicks@gmail.com>:
>>> This is slightly off-topic, as it involves implementation rather than 
>>> the C language.
>>>
>>> It frequently comes up in embedded systems that one wishes to ensure 
>>> that a C-language statement is atomic.
>>
>> For you maybe.
>
> For me, too, although only occasionally, not "frequently". But then I 
> don't spend much time programming in C.
>
>>> One might have available functions or macros to disable or enable 
>>> interrupts, so one might write:
>>>
>>>    volatile int sempahore;
>>>
>>>    DI();
>>>    sempahore++;
>>>    EI();
>>
>> Imagine how a program with DI/EI all over the place can wreak havoc on 
>> your worst-case interrupt latency.
>
> The effect on the worst-case interrupt latency does not depend on the 
> number of DI/EI pairs "all over" the program, nor on how often they are 
> executed. It depends only on the duration of the DI/EI pair that has the 
> most code between the DI and the EI, in terms of the execution time of 
> that code.

You are correct in the mathematical analysis.  All that matters is the worst 
case for any one critical section.  The number of critical sections is 
irrelevant for a worst-case latency analysis.

Most critical sections are very short (by design), but why use them at all 
if you can select intrinsically atomic instructions?

> But why do you, Boudewijn, criticize Datesfat for mentioning DI/EI, when 
> Datesfat's very aim is to *avoid* DI/EI by making the compiler use an 
> instruction that is intrinsically atomic?
>
>> Don't do that then.  Use an OS service that ensures exclusive data 
>> ownership, like a messaging interface.

The systems that I work on tend to have about 32K of FLASH memory and 2K or 
so of RAM.  There is no formal operating system that provides such services. 
The logic is typically just to execute a loop at a constant rate, with 
interrupts happening at the same time based on timer compares or overflows, 
received SCI characters, etc.

> Such OS services tend to have longer interrupt-disabled regions than a 
> simple "semaphore++" and thus more effect on the worst-case latency. And 
> then we have the bare-board systems that use just background + interrupts 
> with no OS to speak of.

The "no OS to speak of" describes the type of system I work on.

> Finally, Datesfat's question and proposal are also applicable to the 
> internals of OS services, which also could benefit from using 
> intrinsically atomic instructions instead of DI/EI.

This is also correct.

I've done some work also with Windows in a multi-threaded sense.  Some of 
the Windows documentation guarantees that reads and writes of certain types 
of 32-bit variables will always be atomic.  I believe that, but I still like 
to look at the assembly-language.

Additionally, some computer instructions are made just for the purpose you 
described--to efficiently implement operating system primitives and/or 
solutions to classic IPC problems.

One example that comes to mind is this one:

http://en.wikipedia.org/wiki/Test-and-set

http://www.if.uidaho.edu/~bgray/classes/cs341/doc/tsl.html

The instruction is there specifically to address a specific IPC problem.  An 
instruction like TSL serves no purpose of any kind in a single-threaded 
framework.

Datesfat 

Datesfat Chicks wrote:

[attributions elided]

>>> Imagine how a program with DI/EI all over the place can wreak havoc 
>>> on your worst-case interrupt latency.
>>
>> The effect on the worst-case interrupt latency does not depend on the 
>> number of DI/EI pairs "all over" the program, nor on how often they 
>> are executed. It depends only on the duration of the DI/EI pair that 
>> has the most code between the DI and the EI, in terms of the execution 
>> time of that code.
> 
> You are correct in the mathematical analysis.  All that matters is the 
> worst case for any one critical section.  The number of critical 
> sections is irrelevant for a worst-case latency analysis.

Not quite.  In the (admittedly unlikely) case that one critical
region follows another, they can become cumulative (it depends on
when your processor actually enables interrupts).

E.g., I typically use critical regions to manipulate shared
structures at the beginning and end of a "routine" (function).
So, you might see a "ret" immediately following an "EI()"
(using your notation).  The routine that it returns to may
then immediately enter another critical region.

I have no qualms about nesting critical regions.  Sometimes
it makes the code a *lot* easier to deal with.

In other cases, it is possible that your critical regions *never*
impact interrupt latency.  E.g., consider:

spinwait(foo);
EI()
blah;
DI()

where "foo" is signalled by an ISR.  I.e., the interrupt has
just *finished* when the EI() commences...

> Most critical sections are very short (by design), but why use them at 
> all if you can select intrinsically atomic instructions?

You can't always do this.  And, sometimes the instructions that
you use to implement this may be nonintuitive (unlikely for
a compiler to chose)

>> But why do you, Boudewijn, criticize Datesfat for mentioning DI/EI, 
>> when Datesfat's very aim is to *avoid* DI/EI by making the compiler 
>> use an instruction that is intrinsically atomic?
>>
>>> Don't do that then.  Use an OS service that ensures exclusive data 
>>> ownership, like a messaging interface.

Even a messaging service has, at some level, a need for atomic
operations.  Putting it under a bushel doesn't cause it to
cease to exist.

> The systems that I work on tend to have about 32K of FLASH memory and 2K 
> or so of RAM.  There is no formal operating system that provides such 
> services. The logic is typically just to execute a loop at a constant 
> rate, with interrupts happening at the same time based on timer compares 
> or overflows, received SCI characters, etc.
> 
>> Such OS services tend to have longer interrupt-disabled regions than a 
>> simple "semaphore++" and thus more effect on the worst-case latency. 
>> And then we have the bare-board systems that use just background + 
>> interrupts with no OS to speak of.
> 
> The "no OS to speak of" describes the type of system I work on.
> 
>> Finally, Datesfat's question and proposal are also applicable to the 
>> internals of OS services, which also could benefit from using 
>> intrinsically atomic instructions instead of DI/EI.
> 
> This is also correct.
> 
> I've done some work also with Windows in a multi-threaded sense.  Some 
> of the Windows documentation guarantees that reads and writes of certain 
> types of 32-bit variables will always be atomic.  I believe that, but I 
> still like to look at the assembly-language.

This "guarantee" is undoubtedly relateed to the machine's
architecture.  E.g., block moves (pretend a 40 byte structure is
a data object) are probably not true, here.)

> Additionally, some computer instructions are made just for the purpose 
> you described--to efficiently implement operating system primitives 
> and/or solutions to classic IPC problems.
> 
> One example that comes to mind is this one:
> 
> http://en.wikipedia.org/wiki/Test-and-set
> http://www.if.uidaho.edu/~bgray/classes/cs341/doc/tsl.html
> 
> The instruction is there specifically to address a specific IPC 
> problem.  An instruction like TSL serves no purpose of any kind in a 
> single-threaded framework.

Well, that's not entirely true, either.  One can imagine
having a piece of code that manipulates a boolean.  And,
some other piece of code EXECUTING IN THE SAME THREAD
wants to check to see if that boolean is set and, regardless,
set it thereafter.

"D Yuniskis" <not.going.to.be@seen.com> wrote in message 
news:hj2nrj$vra$1@speranza.aioe.org...
>
> Well, that's not entirely true, either.  One can imagine
> having a piece of code that manipulates a boolean.  And,
> some other piece of code EXECUTING IN THE SAME THREAD
> wants to check to see if that boolean is set and, regardless,
> set it thereafter.

You are correct.  I didn't think of that scenario.

Datesfat 

Op Mon, 18 Jan 2010 23:47:20 +0100 schreef D Yuniskis  
<not.going.to.be@seen.com>:
> Datesfat Chicks wrote:
>
> [attributions elided]
>
>>>> Don't do that then.  Use an OS service that ensures exclusive data  
>>>> ownership, like a messaging interface.
>
> Even a messaging service has, at some level, a need for atomic
> operations.  Putting it under a bushel doesn't cause it to
> cease to exist.

Absolutely right.  But consider the differences between a solution written  
and maintained by specialized people, and one by people with much less  
experience.

>> The systems that I work on tend to have about 32K of FLASH memory and  
>> 2K or so of RAM.  There is no formal operating system that provides  
>> such services.

That sounds as if there was no decision process for hardware & tools.  I  
would have expected something along the lines of: "it was decided to keep  
hardware cost low and not use an OS."

>> The logic is typically just to execute a loop at a constant rate, with  
>> interrupts happening at the same time based on timer compares or  
>> overflows, received SCI characters, etc.
>>
>>> Such OS services tend to have longer interrupt-disabled regions than a  
>>> simple "semaphore++" and thus more effect on the worst-case latency.

Since in your case an OS means richer hardware, then you might actually  
reduce latency by having a faster processor.  ;)

>>> And then we have the bare-board systems that use just background +  
>>> interrupts with no OS to speak of.
>>  The "no OS to speak of" describes the type of system I work on.
>>
>>> Finally, Datesfat's question and proposal are also applicable to the  
>>> internals of OS services, which also could benefit from using  
>>> intrinsically atomic instructions instead of DI/EI.

And some OSes do utilize these.  Not by depending on the compiler, but  
with plain assembler code.


-- 
Gemaakt met Opera's revolutionaire e-mailprogramma:  
http://www.opera.com/mail/
(remove the obvious prefix to reply by mail)

Op Mon, 18 Jan 2010 10:04:56 +0100 schreef Niklas Holsti  
<niklas.holsti@tidorum.invalid>:
> Boudewijn Dijkstra wrote:
>> Op Sat, 16 Jan 2010 01:52:21 +0100 schreef Datesfat Chicks  
>> <datesfat.chicks@gmail.com>:

>>> One might have available functions or macros to disable or enable  
>>> interrupts, so one might write:
>>>
>>>    volatile int sempahore;
>>>
>>>    DI();
>>>    sempahore++;
>>>    EI();
>>  Imagine how a program with DI/EI all over the place can wreak havoc on  
>> your worst-case interrupt latency.
>
> The effect on the worst-case interrupt latency does not depend on the  
> number of DI/EI pairs "all over" the program, nor on how often they are  
> executed. It depends only on the duration of the DI/EI pair that has the  
> most code between the DI and the EI, in terms of the execution time of  
> that code.

Right.  But every DI/EI pair does increase _average_ interrupt latency,  
for all interrupts, so even those that might be really important and  
cannot even access that particular piece of shared data.

> But why do you, Boudewijn, criticize Datesfat for mentioning DI/EI, when  
> Datesfat's very aim is to *avoid* DI/EI by making the compiler use an  
> instruction that is intrinsically atomic?

I merely intended to point out a disadvantage of using DI/EI (which  
horribly failed).  In fact, in the context of his question, the widely  
used DI/EI is very illustrative and it would be unwise to not mention it.



-- 
Gemaakt met Opera's revolutionaire e-mailprogramma:  
http://www.opera.com/mail/
(remove the obvious prefix to reply by mail)