Question About Sequence Points and Interrupt/Thread Safety

On Feb 25, 6:56=A0am, "Jujitsu Lizard" <jujitsu.liz...@gmail.com> wrote:
> "Jujitsu Lizard" <jujitsu.liz...@gmail.com> wrote in message
>
> news:u4-dnQJnm70QdznUnZ2dnUVZ_uudnZ2d@giganews.com...
>
>
>
> > "Jack Klein" <jackkl...@spamcop.net> wrote in message
> >news:gqc9q4hjd9cguqvvdcd2efbd6ti9qehmgq@4ax.com...
>
> >> The real crime is the fact there's a paper showing a number of
> >> compilers that actually have errors in their implementation of
> >> volatile that can be detected by a strictly conforming program. =A0See=
:
>
> >>http://www.cs.utah.edu/~regehr/papers/emsoft08-preprint.pdf
>
> >> Hopefully, compilers for real embedded systems processor architectures
> >> do better than this.
>
> > That is the single most depressing paper I've read recently.
>
> > But thanks for the link : )
>
> > The Lizard
>
> Jack,
>
> In fact, the paper you linked to was SO depressing, I just had to try to
> match you ... try this one on for size:
>
> http://sunnyday.mit.edu/papers/therac.pdf
>
> What always amazed me about the Therac affair is the initial denial of th=
e
> existence of a problem.
>
> The Lizard

Get a better STM8 compiler?

"Jujitsu Lizard" <jujitsu.lizard@gmail.com> writes:

> I've included a function below and the generated STM8 assembly-language.  As 
> it ends up (based on the assembly-language), the function is interrupt safe 
> as intended.
> 
> My question is, let's assume I have this:
> 
> DI();
> if (x)
>    x--;
> EI();
> 
> where DI and EI just expand to the compiler's asm( ) feature to insert the 
> right machine instruction to disable and enable interrupts, ...
> 
> Is there any reason that the compiler cannot delay writing "x" back so that 
> I get effectively this:
> 
> DI();
> cpu_register = x;
> if(cpu_register)
>    cpu_register--;
> EI();
> x = cpu_register;
> 
> ???
> 
> It isn't clear to me if "volatile" is required on "x" or if there is any 
> possibility of the write of the variable back to memory being delayed.
> 
> Thanks for any insight.
> 
> Function below.
> 
> The Lizard
> 
> ----------
> 
> //---------------------------------------------------------------------------
> //DESCRIPTION
> //   Decrements an array of zero or more 8-bit unsigned integers, but not
> //   below zero.  This function is intended for software timers, but may
> //   have other applications as well.
> //
> //INPUTS
> //   in_arg
> //      Pointer to first element to be decremented.  This pointer must
> //      be valid if in_nelem > 0.
> //
> //   in_nelem
> //      Number of elements to be decremented.  If this value is 0, in_nelem
> //      will not be dereferenced and may be NULL or otherwise invalid.
> //
> //INTERRUPT CONSIDERATIONS
> //   This function must be called only with interrupts enabled (it uses 
> //   simple DI/EI protocol).
> //
> //   This function may be called from non-ISR software only.
> //
> //   In the case of software timers, individual software timers may be 
> //   safely shared with interrupt service, due to the critical section
> //   protocol.  So, an ISR may safely set and test software timers.  Note
> //   that the behavior of individual software timers is guaranteed by DI/EI,
> //   but the relationship between timers is not, as an interrupt may occur
> //   while an array or sets of arrays are being decremented.
> //
> //MNEMONIC
> //   "dec"     : decrement.
> //   "u8"      : unsigned 8-bit.
> //   "arr"     : array.
> //   "nbz"     : not below zero.
> //
> //UNIT TEST HISTORY
> //
> //
> //--------------------------------------------------------------------------------
> void MF_decu8arr_nbz(UINT8 *in_arg, UINT16 in_nelem)
>    {
>    while (in_nelem)
>       {
>       DI();
>       if (*in_arg)
>          (*in_arg)--;
>       EI();
>       in_nelem--;
>       }
>    }
> 
>
> [assembly code snipped]

Several comments.

One:  I assume the timers (the counters in the 'in_arg' array)
might be read and/or modified during an interrupt routine, which
is why it's necessary to delimit the access with DI()/EI(),
plus whatever else may be necessary.

Two:  The comment to the function talks about decrementing an
array of timers, but the function body shown only ever deals with
the first element of such an array.  So something is amiss there.

Three:  If the assumption about interrupt routines accessing the
counters holds, this case certainly is one where 'volatile'
should be used inside the DI()/EI() region to access the
counters.

Four:  As some other people have noted, if 'in_arg' is changed to
be a pointer to volatile (so, 'volatile UINT8 *in_arg'), then the
'if(*in_arg) (*in_arg)--;' can access a counter three times (two
reads and a write) instead of two.  Whether this actually happens
is either implementation-defined behavior or an ambiguity in the
Standard (take your pick).  One way around this potential
performance hit is to use a temporary:

   { UINT8 t = *in_arg;  if(t)  *in_arg = t-1; }

Five:  Another way around the problem is to use 'volatile'
selectively rather than changing the declaration for 'in_arg':

   if( *(volatile UINT8*)in_arg )
      *(volatile UINT8*)in_arg = *in_arg - 1;

Of course, there is no guarantee any particular compiler will be
smart enough to optimize away the second read, so declaring
'volatile UINT8 *in_arg' and using a temporary is probably safer.

Six:  Although the Standard requires the write to the "object" to
complete in the implementation machine, whether that write has
actually made it out through the memory pipeline depends on the
memory subsystem and on the particulars of the interruption
mechanism.  Some systems require a call to insert a write barrier
into the store queue so that subsequent loads are guaranteed to
do the right thing.  Different kinds of write barriers can be
required depending on what accesses are necessary to guarantee
(single core, multi-core, multiprocessor).

Seven:  For a single threaded, single core, single processor
system (which sounds like what you're describing), just getting
the store into the store queue (which using volatile should do)
will be enough, provided the interrupt service routines do enough
to flush the store queue before they start accessing any
counters.  Check what guarantees are made regarding pending
writes by the hardware interrupt mechanism and by the interrupt
service routines themselves;  the two together /can/ guarantee
that all pending writes have completed, the question is are the
ISR's written in such a way that they /do/ guarantee it.

Eight:  There is a corresponding question going the other
direction, i.e., from the ISR back to the interrupted process.

Nine:  The question of what the basic interrupt mechanism does
can be rendered moot by putting in suitable write barriers around
the code in ISR's that accesses the clock timers in question.
Accesses of clock timers in the interrupt routines should also
use volatile;  probably not necessary in a practical sense,
but the smart choice unless the performance consequences are
too costly.

Ten:  Unless the compilers are known to be rock solid, it's a
good idea to check the generated assembly code in any case.

Summary:

   use volatile, with explicit temporary;
   verify particulars of memory and hardware interrupt system;
   verify guarantee of pending writes, either
      (a) for general ISR invocation and return, or
      (b) specifically surrounding counter-access region in ISR's;
   also use volatile for counter access in ISR's;
   sanity check of generated assembly, just in case.

Jujitsu Lizard wrote:
> I've included a function below and the generated STM8 
> assembly-language.  As it ends up (based on the assembly-language), the 
> function is interrupt safe as intended.
> 
> My question is, let's assume I have this:
> 
> DI();
> if (x)
>   x--;
> EI();
> 
> where DI and EI just expand to the compiler's asm( ) feature to insert 
> the right machine instruction to disable and enable interrupts, ...
> 
> Is there any reason that the compiler cannot delay writing "x" back so 
> that I get effectively this:
> 
> DI();
> cpu_register = x;
> if(cpu_register)
>   cpu_register--;
> EI();
> x = cpu_register;
> 
> ???
> 
> It isn't clear to me if "volatile" is required on "x" or if there is any 
> possibility of the write of the variable back to memory being delayed.
> 
> Thanks for any insight.
> 
> Function below.
> 

You've had quite a number of comments from others - rather than replying 
to everyone, I'll add a few points here.

Someone suggested making DI() and EI() external functions.  If the 
compiler is calling these as external functions which it knows nothing 
about, then it must assume that they could read or write any globally 
accessible data, and thus it follows sequence points strictly ("x" is 
not read until after "DI();", and written back before "EI();").  But 
that's a big *if* - if information is available about the function 
(maybe it's defined in a header, or you have some sort of intern-module 
optimisation), all bets are off.  It might be good enough for your tools 
now, but not for future compilers.

Using "volatile" accesses can certainly help with sequencing.  In 
particular, the compiler will not re-organise volatile accesses with 
respect to each other.  However, it is perfectly free to re-organise 
other accesses before, after, and around those volatile accesses.  If 
your compiler does not consider your DI() and EI() to act as volatile 
accesses to memory, it can re-arrange them around accesses to "x" even 
if "x" is declared volatile.

One point to remember about "volatile", especially when trying to write 
optimal code - it is *accesses* that are volatile, not the data itself. 
  It is perfectly possible to have "x" as a normal "UINT8", and force 
volatile accesses as and when needed by using *((volatile UINT8*) &x). 
It is also possible to cast away the volatile access on a variable that 
is declared volatile, but that should give you compiler warnings, and is 
probably better achieved by explicitly caching to a local variable.  If 
you use gcc, this macro can be handy:

#define volatileAccess(v) *((volatile typeof((v)) *) &(v))

Once you have made "x" volatile (or added volatile access casts), the 
next issue is to make sure that DI() and EI() are considered volatile 
accesses to memory.  This is highly dependent on the compiler.

For many compilers, inline assembly and assembly functions are *always* 
considered volatile memory accesses.  Some compilers, however, are 
smarter than that, and can do a substantial amount of optimising of 
inline assembly.  gcc, for example, will move an "asm ("DI")" 
instruction back and forth - sometimes even if it is declared "asm 
volatile ("DI")" (the "volatile" will ensure that things like loop 
unrolling don't duplicate the assembly).  The trick is to tell gcc that 
it "clobbers" memory: asm ("DI" ::: "memory").

Of course, the *real* fun comes when you are using a processor that 
re-orders accesses in hardware which the compiler can't directly control...

Here's a links on the subject:

http://lkml.indiana.edu/hypermail/linux/kernel/9605.0/0214.html

"Jujitsu Lizard" <jujitsu.lizard@gmail.com> writes:

> "Jack Klein" <jackklein@spamcop.net> wrote in message 
> news:gqc9q4hjd9cguqvvdcd2efbd6ti9qehmgq@4ax.com...
> >
> > The real crime is the fact there's a paper showing a number of
> > compilers that actually have errors in their implementation of
> > volatile that can be detected by a strictly conforming program.  See:
> >
> > http://www.cs.utah.edu/~regehr/papers/emsoft08-preprint.pdf
> >
> > Hopefully, compilers for real embedded systems processor architectures
> > do better than this.
> 
> That is the single most depressing paper I've read recently.

That wasn't my reaction at all.  For developers, it had
this set of suggestions:

  7.3 Recommendations for application developers

    We recommend that the developers of mission-critical or
    safety-critical embedded software that is written in C and
    that relies on volatile take one or more of the following
    steps:

      * Manually validate the compiler's output for functions that
	rely importantly on proper compilation of accesses to
	volatile variables.

      * Develop specific tests to ensure that the compiler
	generates proper code for the kinds of volatile accesses
	found in the software of interest.

      * Factor accesses to volatiles into small helper functions,
	if the overhead of this can be tolerated.

      * Compile functions that critically rely on volatile with
	optimizations turned off, if the overhead of this can be
	tolerated.  Our belief (based on observations, but
	unsupported by systematic data) is that code emitted by
	compilers for accessing volatiles is generally correct when
	optimizations are turned off.  It is folklore among embedded
	software researchers that in many cases, safety-critical
	embedded software for applications such as commercial
	avionics is always compiled without optimizations.


On top of that there was lots of other stuff about why the
problems may tend to come up, and how to go about dealing
with them (meaning, at a compiler level).  The main result
is that it identifies an area of C compilers that is likely
to be weak, which isn't that surprising since volatile tends
not to be used - if more attention is put on it, the results
should get better relatively easily.

>>>>> "JL" == Jujitsu Lizard <jujitsu.lizard@gmail.com> writes:

    JL> "Tim Wescott" <tim@seemywebsite.com> wrote in message
    JL> news:aMudnZUqkt-1KjnUnZ2dnUVZ_vqdnZ2d@web-ster.com...

    >> So you have one of three choices:

    >> 3: (I hate these folks) Write your critical stuff in whatever,
    >> and move on to a new job before your sins catch up to you.

    JL> #3 shows that you are not under 30 years old.

Hardly; my first real programming job, part time while I was a student,
was as a maintenance programmer, and the person before me thought
nothing mattered except whether the program compiled and did mostly what
it was supposed to.

That taught me the value of clear code by the time I was 20 years old.

Charlton






-- 
Charlton Wilbur
cwilbur@chromatico.net

Tim Wescott wrote:


> So you have one of three choices:

0: Use synchronization functions provided by OS.

> 1:  Write all your really critical stuff in assembly.

> 2:  Write your critical stuff in C, check the compiler output, and
>     be prepared for bugs if you get a different compiler -- even
>     a new version of the same old.

Yes, yes, yes. For anything more complex then "Hello world", switching 
the compiler version can be painful. For that matter, keep the complete 
backup of the virtual machine with the older toolchain.

> 3:  (I hate these folks) Write your critical stuff in whatever,
>     and move on to a new job before your sins catch up to you.

Well, messy code is a job security for some.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

Jack Klein <jackklein@spamcop.net> writes:
> The real crime is the fact there's a paper showing a number of
> compilers that actually have errors in their implementation of
> volatile that can be detected by a strictly conforming program.  See:
>
> http://www.cs.utah.edu/~regehr/papers/emsoft08-preprint.pdf

I'm feeling a bit dense currently. I'm having issues with the 
following:
"""
2. WHAT DOES VOLATILE MEAN?
...
  A compiler may not move accesses to volatile variables across
sequence points.[1] 
...
[1.
  According to Section 3.8 of the C FAQ [18], "A sequence point is a point
in time at which the dust has settled and all side effects which have been
seen so far are guaranteed to be complete. The sequence points listed in
the C standard are at the end of the evaluation of a full expression (a full
expression is an expression statement, or any other expression which is not
a subexpression within any larger expression); at the ||, &&, ?:, and comma
operators; and at a function call (after the evaluation of all the arguments,
and just before the actual call)."
]
...
No guarantees are made about the atomicity of 
any given volatile access, about the ordering of multiple volatile
accesses between two consecutive sequence points, or about the
ordering of volatile and non-volatile accesses. 
"""

That final clause seems to contradict the initial footnoted clause,
on the presumption that the non-volatile accesses begin with, end 
with, or contain, a sequence point.

"""
For example, the
following code illustrates a common mistake in which a volatile
variable is used to signal a condition about a non-volatile data struc-
ture, perhaps to another thread:

   volatile int buffer_ready;
   char buffer[BUF_SIZE];
   void buffer_init() {
      int i;
      for (i=0; i<BUF_SIZE; i++)
        buffer[i] = 0;
      buffer_ready = 1;
   }

   The for-loop does not access any volatile locations, nor does it
perform any side-effecting operations. Therefore, the compiler is
free to move the loop below the store to buffer_ready, defeating
the developer's intent.
"""

However, it contains bucket loads of sequence points. Moving the 
loop below the volatile store just a different way of saying moving 
the volatile store before the loop (with all its sequence points).
But "a compiler may not move accesses to volatile variables across
sequence points". Contradiction, non?

Where have I gone wrong?

TIA,
Dozy Phil
-- 
I tried the Vista speech recognition by running the tutorial. I was 
amazed, it was awesome, recognised every word I said. Then I said the 
wrong word ... and it typed the right one. It was actually just 
detecting a sound and printing the expected word! -- pbhj on /.

["Followup-To:" header set to comp.lang.c.]
On 2009-02-25, Phil Carmody <thefatphil_demunged@yahoo.co.uk> wrote:
> Jack Klein <jackklein@spamcop.net> writes:
>> The real crime is the fact there's a paper showing a number of
>> compilers that actually have errors in their implementation of
>> volatile that can be detected by a strictly conforming program.  See:
>>
>> http://www.cs.utah.edu/~regehr/papers/emsoft08-preprint.pdf
>
> I'm feeling a bit dense currently. I'm having issues with the 
> following:
> """
> 2. WHAT DOES VOLATILE MEAN?
> ...
>   A compiler may not move accesses to volatile variables across
> sequence points.[1] 

But it may move all other accesses however it wants.

I.e. if two volatile accesses happen in the same evaluation phase, then their
order relative to each other is not well-defined, but if they are separated by
a sequence point, their order /is/ well defined.

But other accesses do not constitute side effects, and so can be eliminated or
reordered arbitrarily.

> No guarantees are made about the atomicity of 
> any given volatile access, about the ordering of multiple volatile
> accesses between two consecutive sequence points, or about the
> ordering of volatile and non-volatile accesses. 
> """
>
> That final clause seems to contradict the initial footnoted clause,
> on the presumption that the non-volatile accesses begin with, end 
> with, or contain, a sequence point.

All accesses are contained in some evaluation phase that is delimited
by sequence points.

The final clause is about accesses that are delimited in the same evaluation
phase, whereas the footnoted sentence is about accesses that have a sequence
point between them, and are thus in separate evaluation phases.

So there is no contradiction; the texts are about different situations.

>
> """
> For example, the
> following code illustrates a common mistake in which a volatile
> variable is used to signal a condition about a non-volatile data struc-
> ture, perhaps to another thread:
>
>    volatile int buffer_ready;
>    char buffer[BUF_SIZE];
>    void buffer_init() {
>       int i;
>       for (i=0; i<BUF_SIZE; i++)
>         buffer[i] = 0;
>       buffer_ready = 1;
>    }
>
>    The for-loop does not access any volatile locations, nor does it
> perform any side-effecting operations. Therefore, the compiler is
> free to move the loop below the store to buffer_ready, defeating
> the developer's intent.
> """
>
> However, it contains bucket loads of sequence points.

But sequence points do not constrain accesses.

> Moving the 
> loop below the volatile store just a different way of saying moving 
> the volatile store before the loop (with all its sequence points).

No it isn't, because the volatile store is not being reordered with
respect to other volatile stores.

> But "a compiler may not move accesses to volatile variables across
> sequence points". Contradiction, non?

Not really. 

You can regard the division into sequence points as being a fixed medium, in
which accesses can move around. When accesses are relocated from one evaluation
phase (space between sequence points) to another, the medium itself does not
move; these moves do not drag the sequence points along.

Volatile accesses must stay in their evaluation phases, but non-volatile
accesses can be moved, coalesced or eliminated.

On Feb 24, 6:58=A0pm, "Jujitsu Lizard" <jujitsu.liz...@gmail.com> wrote:
> I've included a function below and the generated STM8 assembly-language. =
=A0As
> it ends up (based on the assembly-language), the function is interrupt sa=
fe
> as intended.
>
> My question is, let's assume I have this:
>
> DI();
> if (x)
> =A0 =A0x--;
> EI();
>
> where DI and EI just expand to the compiler's asm( ) feature to insert th=
e
> right machine instruction to disable and enable interrupts, ...
>
> Is there any reason that the compiler cannot delay writing "x" back so th=
at
> I get effectively this:
>
> DI();
> cpu_register =3D x;
> if(cpu_register)
> =A0 =A0cpu_register--;
> EI();
> x =3D cpu_register;
>

Hopefully, the regulars will confirm or discount this, but I believe
you can force the ordering by making wrappers for your two functions
at take x as a parameter. I think this make the compiler think they
are dependent on x's value, and not reorder the code.  Something like:

DIx(x);
if (x)
    x--;
EIx(x);



REH

Jujitsu Lizard wrote:

> It isn't clear to me if "volatile" is required on "x" 

Setting aside the interrupt disable, 'x' should to be qualified volatile 
for exactly the same reasons that made you want to disable interrupts 
around that fragment.

Whether or not it's strictly necessary depends on the semantics of those 
non-standard calls DI()/EI().  If the compiler can be sure that EI() 
doesn't reference x (e.g. because it's a tightly described bit of inline 
asm, or a compiler intrinsic), it's allowed to delay storing 'x' in 
memory unless you qualify it as volatile.

> or if there is any 
> possibility of the write of the variable back to memory being delayed.

If you don't tell the compiler about it needing protection by qualifying 
it as 'volatile', there is.