atomic modular increment - is this sound?

bridged with qnx.development_tools
Post Reply
John Nagle

atomic modular increment - is this sound?

Post by John Nagle » Fri Jun 04, 2004 5:29 pm

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);
}

Rennie Allen

Re: atomic modular increment - is this sound?

Post by Rennie Allen » Sat Jun 05, 2004 3:54 pm

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

John Nagle

Re: atomic modular increment - is this sound?

Post by John Nagle » Sat Jun 05, 2004 5:03 pm

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

Jeff Strickrott

Re: atomic modular increment - is this sound?

Post by Jeff Strickrott » Wed Jun 09, 2004 6:47 pm

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

John Nagle

Re: atomic modular increment - is this sound?

Post by John Nagle » Sat Jun 12, 2004 7:28 am

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

Post Reply

Return to “qnx.development_tools”