This is a function to do an atomic add of 1, mod a
limit, without blocking, for circular buffers. Is
this absolutely free of race conditions? Can anyone prove that?
Cases:
oldval < mod No problem
oldval == mod Returns 0,
*loc incremented to mod+1
*loc has mod subtracted from it
at exit, *loc = 1
oldval > mod Can happen if two threads execute
the first atomic_add value before
any thread executes atomic_sub.
The first thread will see oldval == mod,
and will reduce *loc by mod. The second
thread will see *loc > mod, and will
not reduce *loc. So for each time oldval
= mod, exactly one subtraction will occur.
John Nagle
Team Overbot
//
// atomic_incmod_value – add to value, modular.
// as atomic operation
//
inline unsigned atomic_incmod_value(volatile unsigned* loc,
unsigned mod)
{ // add 1, return value, atomic operation
unsigned oldval = atomic_add_value(loc, 1);
if (oldval >= mod) // if overflow
{ if (oldval == mod) // if exactly at overflow
{ atomic_sub(loc,mod); } // must reduce by one cycle
oldval %= mod; // must reduce result
}
return(oldval);
}
John Nagle wrote:
This is a function to do an atomic add of 1, mod a
limit, without blocking, for circular buffers. Is
this absolutely free of race conditions?
I think it is, assuming that “mod” is the same value in
relation to the address of “loc” for each thread that calls
atomic_incmod_value().
Can anyone prove that?
Can’t produce a mathematical proof, but I did excersize
it to my own satisfaction.
Rennie
Rennie Allen wrote:
John Nagle wrote:
This is a function to do an atomic add of 1, mod a
limit, without blocking, for circular buffers. Is
this absolutely free of race conditions?
I think it is, assuming that “mod” is the same value in
relation to the address of “loc” for each thread that calls
atomic_incmod_value().
Yes, that is a constraint. Good point.
Can anyone prove that?
Can’t produce a mathematical proof, but I did excersize
it to my own satisfaction.
Here’s the entire bounded buffer package of which this
is a part.
http://www.overbot.com/public/qnx/
Also in there is “logprintf”, which works like “printf” but
is non-blocking. When the buffer fills, lines
are discarded ("…") appears in the output. Useful for
debug print from real-time programs.
John Nagle
Team Overbot
As of the 9th, your links do not seem to be valid.
Regards,
–Jeff Strickrott
John Nagle wrote:
Rennie Allen wrote:
John Nagle wrote:
This is a function to do an atomic add of 1, mod a
limit, without blocking, for circular buffers. Is
this absolutely free of race conditions?
I think it is, assuming that “mod” is the same value in
relation to the address of “loc” for each thread that calls
atomic_incmod_value().
Yes, that is a constraint. Good point.
Can anyone prove that?
Can’t produce a mathematical proof, but I did excersize
it to my own satisfaction.
Here’s the entire bounded buffer package of which this
is a part.
http://www.overbot.com/public/qnx/
Also in there is “logprintf”, which works like “printf” but
is non-blocking. When the buffer fills, lines
are discarded ("…") appears in the output. Useful for
debug print from real-time programs.
John Nagle
Team Overbot
Sorry, needed to update the site. Thanks.
John Nagle
Jeff Strickrott wrote:
As of the 9th, your links do not seem to be valid.
Regards,
–Jeff Strickrott
John Nagle wrote:
Rennie Allen wrote:
John Nagle wrote:
This is a function to do an atomic add of 1, mod a
limit, without blocking, for circular buffers. Is
this absolutely free of race conditions?
I think it is, assuming that “mod” is the same value in
relation to the address of “loc” for each thread that calls
atomic_incmod_value().
Yes, that is a constraint. Good point.
Can anyone prove that?
Can’t produce a mathematical proof, but I did excersize
it to my own satisfaction.
Here’s the entire bounded buffer package of which this
is a part.
http://www.overbot.com/public/qnx/
Also in there is “logprintf”, which works like “printf” but
is non-blocking. When the buffer fills, lines
are discarded ("…") appears in the output. Useful for
debug print from real-time programs.
John Nagle
Team Overbot