Ring Buffer Index

D

David Merposa

Hello,

We have some code that runs on Linux and Windows. The code uses a ring
buffer. To "increment" the index of the ring buffer, the following
construct is used:

index = ++index % N;

We recently had a review of this code, and my co-worker Tony and I
pointed out to the guy who wrote this code--Sporty--that it is undefined
behavior. The code currently "works" on both Linux and Windows, so he
told us that if it works, don't fix it.

While we agree with Sporty that it currently "works" on both Linux and
Windows, we're a bit concerned that it may not "work" in the future.
Sporty is like an old dog, and it is difficult if not impossible to
teach him "new tricks".

Here is an example program that demonstrates what I am talking about. It
outputs the same (currently "correct") results (3 and 0) on Linux and
Windows.

#include <stdio.h>
int main(void)
{
int x = 2;
x = ++x % 32;
printf("x = %d\n", x);
x = 31;
x = ++x % 32;
printf("x = %d\n", x);
return 0;
}

My question is: What to do about this? On the one hand, it's currently
not a problem. But on the other hand, it seems like a time bomb waiting
to go off.

One thing to keep in mind is that our management recently told us to
focus on the high priority tasks. Sporty says this is not a high
priority task, and that we're wasting time whenever we bring it up. I
fear that if we keep bringing this up, our jobs might be at risk. In
this day and age, jobs are hard to come by, so having a job is a pretty
fortunate thing. Still, it bugs me.

Thanks
 
C

Chris Dollin

Richard wrote:

(re: `index = ++index % N;`)
I wonder if the pre-increment is as undefined as the post increment ....

It is. In both cases, the same location is written to more than once
before a sequence point, viz, the semicolon, resulting in explicitly
undefined behaviour.
I don't see why it should since the pre increment is done before any
overwriting as part of the assignment in this case.

What's your evidence? All that's required, as I understand it, is that
the update implied by `++index` be complete before the next sequence
point. /When/ before that sequence point is (deliberately) not specified.
Had there been another instance of a in the expression then yes.

Don't you mean `index`, or have I missed something?
Just thinking out loud and inviting ridicule I know.

I trust not.
 
B

Bart van Ingen Schenau

I wonder if the pre-increment is as undefined as the post increment ....

Yes, it is.
I don't see why it should since the pre increment is done before any
overwriting as part of the assignment in this case. Had there been
another instance of a in the expression then yes. Just thinking out loud
and inviting ridicule I know.

What makes you think that the result of the increment must be written
to memory before the result of the assignment?

This is a perfectly correct assembly translation of the line 'x = ++x
% 32;':

MOV [x], R0
INC R0
MOV R0, R1
AND R1, 31
MOV R1, [x]
MOV R0, [x]

Here, the result of '++x' is written to memory *last* and has the
effect that the modulo operator is canceled.

Comparatively, the correct version 'x = (x+1) % 32' could have
resulted in the *shorter* assembly listing:

MOV [x], R0
INC R0
AND R0, 31
MOV R0, [x]

This saves two MOV operations (one register-register and one to
memory) and it clobbers fewer registers.

Bart v Ingen Schenau
 
E

Eric Sosman

David said:
Hello,

We have some code that runs on Linux and Windows. The code uses a ring
buffer. To "increment" the index of the ring buffer, the following
construct is used:

index = ++index % N;

We recently had a review of this code, and my co-worker Tony and I
pointed out to the guy who wrote this code--Sporty--that it is undefined
behavior. The code currently "works" on both Linux and Windows, so he
told us that if it works, don't fix it.

Fix it. Even if it happens to do what's desired (just by
chance), you're at the mercy of the compiler's whim. Install
a new compiler version, or change the optimization level, or
even just add an innocent-looking printf() twelve lines earlier,
and all bets are off.

Remember how those silent-movie villains would tie helpless
damsels to the railroad tracks? The "nothing bad has happened
yet" viewpoint calls for leaving the damsel where she is until
after the train rolls over her.
While we agree with Sporty that it currently "works" on both Linux and
Windows, we're a bit concerned that it may not "work" in the future.
Sporty is like an old dog, and it is difficult if not impossible to
teach him "new tricks".

I've not met your Sporty, but I'll take a guess that I'm
an even older dog than he is. But I'm still capable of learning
from experience (especially from bad experience), and you won't
find *me* sniffing at the intake end of the running snow-blower,
no, never again!
 
U

user923005

Hello,

We have some code that runs on Linux and Windows. The code uses a ring
buffer. To "increment" the index of the ring buffer, the following
construct is used:

index = ++index % N;

We recently had a review of this code, and my co-worker Tony and I
pointed out to the guy who wrote this code--Sporty--that it is undefined
behavior. The code currently "works" on both Linux and Windows, so he
told us that if it works, don't fix it.

The correct version of that expression is:
"If it ain't broke, don't fix it!"

Unfortunately, it's broke. So fix it.
While we agree with Sporty that it currently "works" on both Linux and
Windows, we're a bit concerned that it may not "work" in the future.
Sporty is like an old dog, and it is difficult if not impossible to
teach him "new tricks".

Here is an example program that demonstrates what I am talking about. It
outputs the same (currently "correct") results (3 and 0) on Linux and
Windows.

#include <stdio.h>
int main(void)
{
   int x = 2;
   x = ++x % 32;
   printf("x = %d\n", x);
   x = 31;
   x = ++x % 32;
   printf("x = %d\n", x);
   return 0;

}

My question is: What to do about this? On the one hand, it's currently
not a problem. But on the other hand, it seems like a time bomb waiting
to go off.

One thing to keep in mind is that our management recently told us to
focus on the high priority tasks. Sporty says this is not a high
priority task, and that we're wasting time whenever we bring it up. I
fear that if we keep bringing this up, our jobs might be at risk. In
this day and age, jobs are hard to come by, so having a job is a pretty
fortunate thing. Still, it bugs me.

Relying upon undefined behavior to do what you hope is not a good
idea.
 
D

David Merposa

Richard Heathfield wrote:

Getting rid of bugs ought to be a high priority task. Getting rid of
those who stop you getting rid of bugs is an even higher priority
task. If Sporty can't accept facts that contradict his point (see
3.3 EXPRESSIONS: "Between the previous and next sequence point an
object shall have its stored value modified at most once by the
evaluation of an expression. Furthermore, the prior value shall be
accessed only to determine the value to be stored."), then getting
rid of /him/ is an even higher priority task.

Good news. The short story is that Tony and I showed Sporty your post
and convinced him that what he coded was really a problem. He has agreed
to change it to the following form:

index = (index + 1) % N;

I should also point out that Sporty has a copy of the book C Unleashed,
and has used it as a reference for some of the code he has written. If
I'm not mistaken, you are one of the co-authors of that book?
Regardless, I think he assumed that and it played a part in his
"paradigm shift". I guess you really can teach an old dog new tricks.

Thanks
 
F

Flash Gordon

David said:
Richard Heathfield wrote:



Good news. The short story is that Tony and I showed Sporty your post
and convinced him that what he coded was really a problem. He has agreed
to change it to the following form:

index = (index + 1) % N;

That's good. You should also look at the warning options for the
compiler. gcc at least can warn about the original code whan properly
prompted, and I'm sure other compilers can as well.
I should also point out that Sporty has a copy of the book C Unleashed,
and has used it as a reference for some of the code he has written. If
I'm not mistaken, you are one of the co-authors of that book?
Regardless, I think he assumed that and it played a part in his
"paradigm shift". I guess you really can teach an old dog new tricks.

He is one of the authors, and not the only one to post here. We also
sometimes have members of the ISO C committee posting here, authors of
other excellent books on C, and even sometimes a certain well known
person with the initials DMR.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,898
Latest member
BlairH7607

Latest Threads

Top