Zero overhead overflow checking

[jacob navia]

Abstract:

Overflow checking is not done in C. This article proposes a solution
to close this hole in the language that has almost no impact in the run
time behavior.

1: The situation now
--------------------

Any of the four operations on signed integers can overflow. The result
of the operation is meaningless, what can have a catastrophic impact
on the operations that follow. There are important security issues
associated with overflows.

The only way to catch overflows now is to use cumbersome C expressions
that force modifications of source code, and are very slow since done
in C.

2: The proposed solution
------------------------

In the experimental compiler lcc-win, I have implemented since 2003 an
overflow checking mechanism.

From that work I have derived this proposal.

2.A: A new pragma
------------------

#pragma STDC OVERFLOW_CHECK on_off_flag

When in the ON state, any overflow of an addition, subtraction,
multiplication or division provokes a call to the overflow handler.
Operations like +=, -=, *=, and /= are counted also.

Only the types signed int and signed long long are concerned.

The initial state of the overflow flag is implementation defined.

2.B: Setting the handler for overflows
---------------------------------------

overflow_handler_t set_overflow_handler(overflow_handler_t newvalue);

The function set_overflow_handler sets the function to be called in
case of overflow to the specified value. If "newvalue" is NULL,
the function sets the handler to the default value (the value
it had at program startup).

2.C: The handler function
-------------------------

typedef void (*overflow_handler_t)(unsigned line_number,
char *filename,
char *function_name,...);
This function will be called when an overflow is detected. The
arguments have the same values as __LINE__ __FILE__ and __FUNC__

If this function returns, execution continues with an implementation
defined value as the result of the operation that overflowed.

-------------------------------------------------------------------

Implementation.

I have implemented this solution, and the overhead is almost zero.
The most important point for implementors is to realize that the
normal flow (i.e. when there is no overflow) should not be disturbed.

No overhead implementation:
--------------------------
1. Perform operation (add, subtract, etc)
2. Jump on overflow to an error label
3: Go on with the rest of the program

The overhead of this is below accuracy in a PC system.
It can't be measured.

Implementation with small overhead (3-5%)
1. Perform operation
2. If no overflow jump to continuation
3. save registers
4. Push arguments
5. Call handler
6. Pop arguments
7. Restore registers
continuation:

The problem with the second implementation is that the flow of control
is disturbed. The branch to the continuation code will be mispredicted
since it is a forward branch. This provokes pipeline turbulence.

The first solution provokes no pipeline turbulence since the forward
jump will be predicted as not taken. This will be a good prediction
in the overwhelming majority of situations (no overflow). The only
overhead is just an additional instruction, i.e. almost nothing.
----------------------------------------------------------------------

 

[Dag-Erling Smørgrav]

Any of the four operations on signed integers can overflow. The result
of the operation is meaningless, what can have a catastrophic impact
on the operations that follow. There are important security issues
associated with overflows.

There are plenty of cases - such as a linear congruential PRNG or
certain parts of a TCP stack - where overflow is either unimportant or
intentional. There are also plenty of cases where the programmer can
safely assume that overflow can not possibly happen.

The only way to catch overflows now is to use cumbersome C expressions
that force modifications of source code, and are very slow since done
in C.

Your solution also requires modifying the source code, and to claim that
something is very slow just because it is "done in C" is simply idiotic.
As a compiler author, you should know better. A good compiler could
recognize at least some (correctly implemented) overflow checks as such
and generate code that checks the CPU's integer overflow flag instead of
performing an explicit comparison.

2.A: A new pragma
------------------

#pragma STDC OVERFLOW_CHECK on_off_flag

When in the ON state, any overflow of an addition, subtraction,
multiplication or division provokes a call to the overflow handler.
Operations like +=, -=, *=, and /= are counted also.

Only the types signed int and signed long long are concerned.

What about signed long? And why only signed? Overflow can be just as
painful in unsigned arithmetic.

2.B: Setting the handler for overflows
---------------------------------------

overflow_handler_t set_overflow_handler(overflow_handler_t newvalue);

The function set_overflow_handler sets the function to be called in
case of overflow to the specified value. If "newvalue" is NULL,
the function sets the handler to the default value (the value
it had at program startup).

2.C: The handler function
-------------------------

typedef void (*overflow_handler_t)(unsigned line_number,
char *filename,
char *function_name,...);
This function will be called when an overflow is detected. The
arguments have the same values as __LINE__ __FILE__ and __FUNC__

C already has a tried and tested mechanism for this kind of thing:
signals.

I have implemented this solution, and the overhead is almost zero.
The most important point for implementors is to realize that the
normal flow (i.e. when there is no overflow) should not be disturbed.

I find that slightly condescending. Compiler writers are (usually not)
idiots.

No overhead implementation:

I assume that the code that follows the error label calls the handler.
What happens when the handler returns? Does the flow of control return
to the point immediately after the expression or sub-expression that
triggered the overflow?

The overhead of this is below accuracy in a PC system.
It can't be measured.

That depends entirely on the workload. Programs that perform large
amounts of integer arithmetic (e.g. signal processing, or numerical
analysis using arbitrary-precision arithmetic) may be noticeably
affected - not just because of the processing overhead, but also because
of the extra instructions, which reduce spatial locality.

Implementation with small overhead (3-5%)
1. Perform operation
2. If no overflow jump to continuation
3. save registers
4. Push arguments
5. Call handler
6. Pop arguments
7. Restore registers
continuation:

The problem with the second implementation is that the flow of control
is disturbed. The branch to the continuation code will be mispredicted
since it is a forward branch. This provokes pipeline turbulence.

The branch in your "no-overhead" implementation is also a forward
branch.

Unlike lcc, the C standard is not limited to i386 and amd64 systems.
Most CPUs don't do branch prediction; many (if not most) of those that
do allow the compiler to provide hints. Some compilers (such as gcc)
allow the programmer to specify which branch is more likely to be taken.

Even in the absence of hints, you can't make any assumptions about what
the CPU will do; it is reasonable (and, in this case, correct) for the
CPU to assume that a branch conditional on the overflow flag is used to
handle exceptional conditions, and therefore less likely to be followed.

BTW, I have yet to see a C compiler where the caller is responsible for
saving and restoring registers. Perhaps that is a peculiarity of lcc,
or of the Windows ABI? Usually, the callee saves and restores registers
that it intends to use for itself; some CPUs use register renaming or
other mechanisms to avoid pushing registers onto the stack.

The first solution provokes no pipeline turbulence since the forward
jump will be predicted as not taken. This will be a good prediction
in the overwhelming majority of situations (no overflow). The only
overhead is just an additional instruction, i.e. almost nothing.

On many microcontrollers, an additional instruction means an additional
clock cycle, no matter what.

DES

 

[Chris Dollin]

What about signed long? And why only signed? Overflow can be just as
painful in unsigned arithmetic.

The C standard specifies that unsigned arithmetic wraps around and
does not "overflow"; there's nothing to check and no room to manoeuver.

--
"The career of Hern VI from its native Acolyte cluster - James Blish
across the centre of the galaxy made history -- /Earthman, Come Home/
particularly in the field of instrumentation."

Hewlett-Packard Limited registered no:
registered office: Cain Road, Bracknell, Berks RG12 1HN 690597 England

 

[jacob navia]

Dag-Erling Smørgrav a écrit :

There are plenty of cases - such as a linear congruential PRNG or
certain parts of a TCP stack - where overflow is either unimportant or
intentional. There are also plenty of cases where the programmer can
safely assume that overflow can not possibly happen.

In that case, in MOST cases you have... nothing to do.
If you do not enable the checking with the pragma
the code does the same thing as before.

I just do not understand your objection. Or maybe you start answering
messages before reading them to the end?

Your solution also requires modifying the source code,

No. The lcc-win compiler accepts a command line argument that sets the
overflow checking for the compilation unit.

and to claim that
something is very slow just because it is "done in C" is simply idiotic.

C is in general slower as assembly language, specially here.

As a compiler author, you should know better. A good compiler could
recognize at least some (correctly implemented) overflow checks as such
and generate code that checks the CPU's integer overflow flag instead of
performing an explicit comparison.

There is NO compiler in the world that does that. And with good reasons.

What about signed long? And why only signed? Overflow can be just as
painful in unsigned arithmetic.

Unsigned arithmetic is defined in standard C. PLease read the
corresponding standard pages.

C already has a tried and tested mechanism for this kind of thing:
signals.

Why not using the signal mechanism?

The problem with it is that here more information abouty WHERE the
error occurs is passed to the program. This is important, to be
able to use this feature in an effective manner. Obviously the
information can be available in a debugger, if you put a
breakpoint in a signal handler, but the solution I propose
doesn't need that, and can be used in a production setting
(logging the coordinates in a faults file for instance)

I find that slightly condescending. Compiler writers are (usually not)
idiots.

Sorry, I can't please everyone. In another message Mr Nilsson asked me

Have you offered to show M$ or GCC how to implement it?

When I do that, you complain now.

I assume that the code that follows the error label calls the handler.
What happens when the handler returns?

You should read the entire message before answering. That question
is answered just below.

Does the flow of control return
to the point immediately after the expression or sub-expression that
triggered the overflow?

Yes.


That depends entirely on the workload. Programs that perform large
amounts of integer arithmetic (e.g. signal processing, or numerical
analysis using arbitrary-precision arithmetic) may be noticeably
affected - not just because of the processing overhead, but also because
of the extra instructions, which reduce spatial locality.

Maybe it is measurable, maybe not. In any case since you can turn it off
at any time this is not so important.

The branch in your "no-overhead" implementation is also a forward
branch.

Again. It is a forward branch that will be correctly predicted
since in most cases you have no overflow!

In the other implementation you have a forward branch that will be
almost always taken, provoking the turbulence.

Unlike lcc, the C standard is not limited to i386 and amd64 systems.

That is big news to me.

Most CPUs don't do branch prediction; many (if not most) of those that
do allow the compiler to provide hints. Some compilers (such as gcc)
allow the programmer to specify which branch is more likely to be taken.

So what? What is your point here?

Even in the absence of hints, you can't make any assumptions about what
the CPU will do; it is reasonable (and, in this case, correct) for the
CPU to assume that a branch conditional on the overflow flag is used to
handle exceptional conditions, and therefore less likely to be followed.

BTW, I have yet to see a C compiler where the caller is responsible for
saving and restoring registers. Perhaps that is a peculiarity of lcc,
or of the Windows ABI? Usually, the callee saves and restores registers
that it intends to use for itself; some CPUs use register renaming or
other mechanisms to avoid pushing registers onto the stack.

lcc saves all registers before calling the handler procedure because an
operation is interrupted before we reach the next sequence point.

Normally, as you correctly point out, the callee doesn't save any
registers because the scratch registers are saved before calling a
function. But here, we are maybe in the middle of an expression

z = (R+67)/(w-34)+Height;

Scratch registers are holding values that need to be saved since
if the handler returns, the computation goes on.

> On many microcontrollers, an additional instruction means an additional
clock cycle, no matter what.

You seem to be more interested in fast execution with maybe wrong
results than correct results at all times. In any case if you program
a coffee machine and overflow is not a problem: it suffices to do
NOTHING and everything will work as before.

What is the problem then?

 

[jacob navia]

jacob navia a écrit :

Only the types signed int and signed long long are concerned.

AAAARGH!

I forgot signed long. Sorry.

Thanks to Mr Smorgrav that pointed me to this error.

 

[jacob navia]

Gordon Burditt a écrit :

Specific mention of ++ and -- here is more important than mentioning
+=, etc.

I will add them.

How fine-grained does this have to operate? If, for example:
e = ((a+b)
#pragma STDC OVERFLOW_CHECK on
*
#pragma STDC OVERFLOW_CHECK off
(c+d))+1;
will that check only the multiplication for overflow? If not, how do
I check only the multiplication for overflow?

This will work in lcc-win, but for a standard it is problematic because
it could be difficult for the optimizer to move code around.

Why not signed long also?

I corrected that already. It was an oversight.

And signed short? Why can't signed chars
overflow?

Because they are promoted to ints when doing arithmetic.

And why no checks for floating point?

Because they have their own set of flags.

Pointers can wrap, too.

Sure, but if the wrapping around is done using unsigned arithmetic
the behavior is correct.

This seems problematical for existing (bad) code.

The goal here is to be as compatible with the existing code as possible.
If the default is on, as mandated by the standard, old code will no
longer work because it will call a handler at overflow and the program
will crash. Not very funny.

This allows also for an implementation of C in secure environments
where overflow can't be tolerated and sets it as ON by default. Or
it uses some global file, command line option, whatever.

This intrudes on the programmer's namespace, unless you put
declarations like this into a new (to-become-standard) header file
where they will interfere only if that header file is included.

Yes I would propose that we use the same file as the safer C library
of Microsoft or some

You have failed to state what the default handler *does* when
it is called. This is too important to make it "implementation
defined" and leave it at that.

It does... whatever it wants. How can we specify what a handler does?

Let's get real. Did the standard specify what does a signal handler do?

This is a variable-argument function? Why?


Under what circumstances will it be called with more than 3 arguments?

It could be that some implementations pass MORE information to the
overflow handler than the bare required minimum. What can that be
is up to the implementation.

This makes it very difficult to deal with overflow in a way other
than spitting out an error message and optionally dying. In
particular, if I want to test if a particular expression overflowed,
I end up embedding *LINE NUMBERS* into the code, line numbers which
may very well change even if the only change is running it through
"indent" or editing comments. (A try/catch structure would work
better here.)

Sure, lcc-win implements try/catch. But it is already difficult
(as you see) to convince people of this extremely simple stuff,
try/catch is much more complex.

Can this be a trap value? If so, the program may die before I
decide that the whole computation produced a useless value and
substitute a default or demand better input.

Then you have to search for a better implementation, what do you expect?

You can always have a setjmp BEFORE the computation and treat the error
in the setjmp clause. Your handler just makes a longjmp.

 

[Dag-Erling Smørgrav]

So what? What is your point here?

That your claims about the comparative performance of the two
implementations have no basis in reality.

lcc saves all registers before calling the handler procedure because an
operation is interrupted before we reach the next sequence point.

I'll have to remember never to use it, then.

Normally, as you correctly point out, the callee doesn't save any
registers because the scratch registers are saved before calling a
function.

I said the *caller* normally doesn't save any registers.

You seem to be more interested in fast execution with maybe wrong
results than correct results at all times.

*you* were the one who brought up performance; *you* were the one who
claimed that overflow checking has no performance overhead.

DES

 

[jacob navia]

Dag-Erling Smørgrav a écrit :

That your claims about the comparative performance of the two
implementations have no basis in reality.

I measured the performance difference in my machine,
but I haven't done an extensive study.

What is obvious is that the performance hit will be almost
zero for most advanced CPUs.


If, as you said above, some compilers allow to specify
the branch that is going to be taken, it will be even easier
to do that in assembly by the compiler without the user
having to modify the code.

I'll have to remember never to use it, then.

Sure, nobody is forcing you to use it. If you take care to try top
understand what I am saying however, it would be more practical.

In an expression evaluation (that you snipped) scratch registers are
used to hold intermediate values. Since we maybe will come back to this
point (if the handler returns), those values will be used in the
evaluation of the full expression. We need to save them.

This is not a normal call. In a normal call, all scratch registers have
been saved to RAM or are unused, so there is no need to save them in the
caller code. This is NOT a normal call since it has to preserve context
WITHIN two sequence points.

I said the *caller* normally doesn't save any registers.

Yes, you said that. But you misunderstood. See the explanation above.

*you* were the one who brought up performance; *you* were the one who
claimed that overflow checking has no performance overhead.

I brought performance because many people are concerned about that. If
you review this dicussion, performance issues are the bulk of the
critics to this proposal. So, I tried to address those concerns with a
solution that doesn't impact performance at all.

 

[Dag-Erling Smørgrav]

What is obvious is that the performance hit will be almost zero for
most advanced CPUs.

C is not restricted to "the most advanced CPUs". For every "advanced
CPU" in the world, there are tens or hundreds of embedded processors,
microcontrollers, DSPs etc. Even a COTS desktop, laptop or server with
an "advanced CPU" can contain multiple secondary processors: I've worked
with IBM servers that had an i486 (IIRC) on the backplane monitoring the
main CPUs.

DES

 

[Eric Sosman]

Abstract:

Overflow checking is not done in C. This article proposes a solution
to close this hole in the language that has almost no impact in the run
time behavior.

1: The situation now
--------------------

Any of the four operations on signed integers can overflow. The result
of the operation is meaningless, what can have a catastrophic impact
on the operations that follow. There are important security issues
associated with overflows.

It seems "the four operations" are +, -, *, / and their
variants. Why omit <<? (Especially, why omit << if an
optimizer is likely to substitute it for *?)

The only way to catch overflows now is to use cumbersome C expressions
that force modifications of source code, and are very slow since done
in C.

2: The proposed solution
------------------------

In the experimental compiler lcc-win, I have implemented since 2003 an
overflow checking mechanism.

From that work I have derived this proposal.

2.A: A new pragma
------------------

#pragma STDC OVERFLOW_CHECK on_off_flag

When in the ON state, any overflow of an addition, subtraction,
multiplication or division provokes a call to the overflow handler.
Operations like +=, -=, *=, and /= are counted also.

Only the types signed int and signed long long are concerned.

A peculiar limitation. Is there a reason for omitting
`signed long', and the signed <stdint.h> types that don't
promote to `int'? If the implementation permits wider-than-int
bit-fields, shouldn't their arithmetic be testable, too?

The initial state of the overflow flag is implementation defined.

2.B: Setting the handler for overflows
---------------------------------------

overflow_handler_t set_overflow_handler(overflow_handler_t newvalue);

The function set_overflow_handler sets the function to be called in
case of overflow to the specified value. If "newvalue" is NULL,
the function sets the handler to the default value (the value
it had at program startup).

The main alternative would be to raise a signal and run the
signal handler. A weakness of that approach is that it's hard
to smuggle much information through C's bare-bones signal scheme;
the "wider" interface described here is more flexible.

Note that since the overflow handler function may be called
at pretty much any moment in the evaluation of an expression,
the values of variables modified by that expression are uncertain.
This shouldn't be any more troublesome than `y[i++] = f(x[j++])',
though.

If overflow checking is enabled (perhaps by way of the I-D
initial state) but set_overflow_handler() has not been called,
what happens if an overflow occurs? Presumably there's a default
handler pre-set by the implementation; what does (should) it do?

2.C: The handler function
-------------------------

typedef void (*overflow_handler_t)(unsigned line_number,
char *filename,
char *function_name,...);
This function will be called when an overflow is detected. The
arguments have the same values as __LINE__ __FILE__ and __FUNC__

ITYM __func__, but I also question the utility. On an
implementation where __FILE__ is meaningful, it and __LINE__
suffice to locate the overflow site within a reasonably narrow
range, and __func__ does not narrow the range any further. Note
that all three pieces of information are meaningful only to a
person with access to the source code; none is helpful to a
source-less end user.

What variadic arguments are supplied, and how does the
handler learn about them?

If this function returns, execution continues with an implementation
defined value as the result of the operation that overflowed.

-------------------------------------------------------------------

Implementation.

I have implemented this solution, and the overhead is almost zero.
The most important point for implementors is to realize that the
normal flow (i.e. when there is no overflow) should not be disturbed.

No overhead implementation:

The jump can't be a "pure" jump unless there's a separate
error label for every possible overflow site. Without some
notion of where the jump came from, I don't see how you could
figure out the __LINE__ value, nor how you could resume execution
if the overflow handler returns. If you jump to an error label
that's shared by all overflow sites in the function, you'll need
some kind of "JSR" or "BAL" jump. On architectures where this
kind of jump is unconditional, you'd need both a conditional
jump to test the overflow and a jump-with-back-link to get to
the overflow processing code.

3: Go on with the rest of the program

The overhead of this is below accuracy in a PC system.
It can't be measured.

Implementation with small overhead (3-5%)
1. Perform operation
2. If no overflow jump to continuation
3. save registers
4. Push arguments
5. Call handler
6. Pop arguments
7. Restore registers
continuation:

The problem with the second implementation is that the flow of control
is disturbed. The branch to the continuation code will be mispredicted
since it is a forward branch. This provokes pipeline turbulence.

The first solution provokes no pipeline turbulence since the forward
jump will be predicted as not taken. This will be a good prediction
in the overwhelming majority of situations (no overflow). The only
overhead is just an additional instruction, i.e. almost nothing.

Architectures with "branch delay slots" may also require
inserting a no-op, unless the code generator can find something
something that can be done safely regardless of whether the
overflow handler is called.

There remains the question implementation for architectures
where overflow detection is more burdensome. The Digital Alpha
has been cited as a machine where detection requires additional
compare instructions. Also, if you need both the operands and
the results to do post-hoc overflow detection, you can't use
instructions that overwrite operands with results; this means
that arithmetic uses more distinct CPU registers than it would
otherwise, restricting the optimizer's freedom to use those
registers for other purposes.

On the whole, the proposal seems a reasonable beginning.
Some of the design decisions (ignoring shifts, ignoring long,
handler arguments, ...) need more scrutiny, and the questions
of implementation efficiency are not altogether settled.

 

[jacob navia]

Eric Sosman a écrit :

It seems "the four operations" are +, -, *, / and their
variants. Why omit <<? (Especially, why omit << if an
optimizer is likely to substitute it for *?)

Why omit << and >>
------------------

Signed overflow on shifts could mean that when shifting bits out,
the sign changes. I do not think that in a shift operation a call
to a trap handler and all the big overhead is justified. Most shift-out
operations handle the numbers as a bit sequence, not as arithmetical
values. True, you can substitut a multiplication by 2 with a shift,
and then the overflow wouldn't be detected, but that's life, you can't
have everything

The compiler should be careful that when the pragma overflow check
is ON, the usual optimization of substituting a multiplication by a
power of two with a shift is no longer valid!

[snip]

A peculiar limitation. Is there a reason for omitting
`signed long',

This was an oversight.

and the signed <stdint.h> types that don't
promote to `int'?

Which ones? I mean short and chars promote to int as far as
I know.

If the implementation permits wider-than-int

bit-fields, shouldn't their arithmetic be testable, too?

If the bit-fields are promoted they will be tested anyway.

The main alternative would be to raise a signal and run the
signal handler. A weakness of that approach is that it's hard
to smuggle much information through C's bare-bones signal scheme;
the "wider" interface described here is more flexible.

Note that since the overflow handler function may be called
at pretty much any moment in the evaluation of an expression,
the values of variables modified by that expression are uncertain.
This shouldn't be any more troublesome than `y[i++] = f(x[j++])',
though.

If there is an overflow, the whole expression is undefined. Now,
nobody knows and sometimes a program gives wrong results or makes
the software crash hours later.

If overflow checking is enabled (perhaps by way of the I-D
initial state) but set_overflow_handler() has not been called,
what happens if an overflow occurs?

The default handler is called.

Presumably there's a default
handler pre-set by the implementation; what does (should) it do?

This is implementation defined.

ITYM __func__, but I also question the utility. On an
implementation where __FILE__ is meaningful, it and __LINE__
suffice to locate the overflow site within a reasonably narrow
range, and __func__ does not narrow the range any further. Note
that all three pieces of information are meaningful only to a
person with access to the source code; none is helpful to a
source-less end user.

As all bugs, theyt aren't user friendly. But what would you expect
that the C runtime tells the user?

You should setup a handler that does a sensible thing, for instance
to use the name of the function as a key into a hashtable of recovery
points where the program can recover.

What variadic arguments are supplied, and how does the
handler learn about them?

This is implementation defined. An implementation could store the source
code of the offending lines and pass it as a char * to the handler,
or it could pass a pointer to the stack frame so that the program
could change the values of some variables, who knows?

There are a lot of possibilities. The variable arguments allows
implementations to pass more information...

The jump can't be a "pure" jump unless there's a separate
error label for every possible overflow site.

I do exactly that. I setup a special label for each line of
code where an overflow is possible.

Without some
notion of where the jump came from, I don't see how you could
figure out the __LINE__ value, nor how you could resume execution
if the overflow handler returns.

I thought at the beginning of this exactly like you and I had
a version with
operation
if not overflow goto continuation
call handler
continuation:

But this inccurs a 3-5% performance hit.

If you jump to an error label
that's shared by all overflow sites in the function, you'll need
some kind of "JSR" or "BAL" jump. On architectures where this
kind of jump is unconditional, you'd need both a conditional
jump to test the overflow and a jump-with-back-link to get to
the overflow processing code.

Yes.


Architectures with "branch delay slots" may also require
inserting a no-op, unless the code generator can find something
something that can be done safely regardless of whether the
overflow handler is called.

Sure, but that is with all jumps.

There remains the question implementation for architectures
where overflow detection is more burdensome. The Digital Alpha
has been cited as a machine where detection requires additional
compare instructions.

Happily DEC is no longer there, and COMPAQ, that bought DEC
is no longer there either, being bought by Hewlett Packard.

Also, if you need both the operands and
the results to do post-hoc overflow detection, you can't use
instructions that overwrite operands with results; this means
that arithmetic uses more distinct CPU registers than it would
otherwise, restricting the optimizer's freedom to use those
registers for other purposes.

Maybe. If overflow checking is too expensive and your application
doesn't need it, then just do not turn it on.

 

[Keith Thompson]

Gordon Burditt a écrit : [...]

Pointers can wrap, too.

Sure, but if the wrapping around is done using unsigned arithmetic
the behavior is correct.

If pointer arithmetic causes a pointer to wrap around, it's almost
certainly not the correct behavior, unless the implementation has
allocated an object in an address range that wraps around to zero.

Pointers are not numbers. Pointer "overflow" occurs when a pointer
goes beyond the bounds of the object to which it points, not when its
numeric value overflows. Some kind of checking for pointer "overflow"
would certainly be useful if it could be done reasonably efficiently,
but I don't think it should be part of a proposal for integer overflow
checking. It would require some sort of "fat pointers", and it's not
practical to require that for all implementations.

[...]

It does... whatever it wants. How can we specify what a handler does?

Um, by specifying what the default handler does. Remember, we're
talking about a default handle that's set up *by the implementation*.

There's an argument to be made for leaving it implementation-defined,
but it certainly *could* be specified.

[...]

 

[Keith Thompson]

jacob navia wrote: [...]

2.C: The handler function
-------------------------

typedef void (*overflow_handler_t)(unsigned line_number,
char *filename,
char *function_name,...);
This function will be called when an overflow is detected. The
arguments have the same values as __LINE__ __FILE__ and __FUNC__

ITYM __func__, but I also question the utility. On an
implementation where __FILE__ is meaningful, it and __LINE__
suffice to locate the overflow site within a reasonably narrow
range, and __func__ does not narrow the range any further. Note
that all three pieces of information are meaningful only to a
person with access to the source code; none is helpful to a
source-less end user.

There is precedent: the assert() macro prints the values of __FILE_-,
__LINE__, and __func__. In another thread, I had suggested that jacob
should borrow that wording.

[...]

 

[Keith Thompson]

Eric Sosman a écrit : [...]

There remains the question implementation for architectures
where overflow detection is more burdensome. The Digital Alpha
has been cited as a machine where detection requires additional
compare instructions.

Happily DEC is no longer there, and COMPAQ, that bought DEC
is no longer there either, being bought by Hewlett Packard.

[...]

Alpha processors are still in production use.

Are there other processors, perhaps even new ones, that use similar
schemes to what the Alpha uses? Or ones that use other schemes?
Personally, I don't know, and unless you've done an exhaustive study
of all CPUs currently in use, I suggest that you don't know either.

If this proposal is to have any chance of being accepted into the
standard, you can't ignore architectures that differ from the ones
you're accustomed to.

Maybe the best possible implementation of your proposal on the XYZ-137
imposes a 15% overhead on typical code -- and maybe that's acceptable.
I'm not saying you need to know everything about every CPU, just that
you need to acknowledge the issue. If you give the impression, even
unintentionally, of having an "All the world's an x86" attitude,
you'll be taken less seriously.

 

[Keith Thompson]

Abstract:

Overflow checking is not done in C.

Correction: Overflow checking is not required in C. Since the
behavior of signed integer overflow is undefined, an implementation
can already do anything it likes, including checking.

Of course a standardized solution would have the advantage that users
could write portable code that uses it, unlike the current situation
where extensions are either inconsistent or nonexistent.

[...]

Any of the four operations on signed integers can overflow.

Restricting this to +, -, *, /, even including ++, --, and the
compound assignment operators, is IMHO a bad idea.

The shift operators are not fundamentally different from +-*/.
Treating them differently would be an inconsistency in the language.

"/" can overflow in one rare case: INT_MIN/-1. "%" has problems with
the same operands; <TYPE>_MIN%-1 doesn't produce a mathematical result
that's outside the range of the type, but the C standard committee
recently added wording to 6.5.5 saying that the behavior of "%" is
undefined when "/" would overflow on the same operands. Your proposal
should cover this case.

[...]

Only the types signed int and signed long long are concerned.

And signed long, as you've already acknowledged.

What about extended integer types? ("lcc-win doesn't support extended
integer types" is not a good answer.)

[...]

 

[Eric Sosman]

[...]
2.A: A new pragma
------------------

#pragma STDC OVERFLOW_CHECK on_off_flag

When in the ON state, any overflow of an addition, subtraction,
multiplication or division provokes a call to the overflow handler.
Operations like +=, -=, *=, and /= are counted also.
[...]

It occurs to me that this #pragma needs some tightening
up, because there are corner cases:

#pragma STDC OVERFLOW_CHECK OFF
x = a
#pragma STDC OVERFLOW_CHECK ON
+ b + c;


/* Different (?) from the above */
#pragma STDC OVERFLOW_CHECK OFF
x = a +
#pragma STDC OVERFLOW_CHECK ON
b + c;

One possibility would be to leave the tightening to the
implementation: If an expression contains sub-expressions in
which the state of overflow checking differs, let it be up to
the implementation how much of the expression actually gets
overflow checking.

A (weakly) related issue is to describe how faithfully the
generated code must follow the abstract machine. For example,
is it permissible to rewrite

#define OVERHEAD 1
#pragma STDC OVERFLOW_CHECK ON
x = a + OVERHEAD - 1;
as
x = a;

? The original expression can overflow if executed literally,
but the rewritten expression cannot; is the transformation
allowed? What optimizations (if any) must overflow detection
inhibit?

 

[Keith Thompson]

From that work I have derived this proposal.

2.A: A new pragma

[...]

A tiny quibble: the standard refers to this as "on-off-switch", not
"on_off_flag" (note '-' rather than '_').

 

[Eric Sosman]

Eric Sosman a écrit :

Why omit << and >>
------------------

Signed overflow on shifts could mean that when shifting bits out,
the sign changes. I do not think that in a shift operation a call
to a trap handler and all the big overhead is justified. Most shift-out
operations handle the numbers as a bit sequence, not as arithmetical
values. True, you can substitut a multiplication by 2 with a shift,
and then the overflow wouldn't be detected, but that's life, you can't
have everything

The compiler should be careful that when the pragma overflow check
is ON, the usual optimization of substituting a multiplication by a
power of two with a shift is no longer valid!

The decision seems capricious. Also, forbidding the use
of shift to evaluate a multiplication adds to the cost of doing
the overflow checks (on the assumption that shifts are cheaper
than multiplications).

This was an oversight.


Which ones? I mean short and chars promote to int as far as
I know.

Yes (except that char might promote to unsigned int). But
<stdint.h> can define types that are wider than int, and these
types do not promote at all. Arithmetic on int39_t values is
done (as if) in 39-bit arithmetic, not in promoted-to-64-bit
arithmetic. (This has implications for detection of overflow,
if the underlying hardware uses 64-bit arithmetic to simulate
39-bit operations.)

If the implementation permits wider-than-int

If the bit-fields are promoted they will be tested anyway.

A bit-field wider than int cannot possibly promote to int.
(It can't promote at all, in fact.)

2.C: The handler function
-------------------------

typedef void (*overflow_handler_t)(unsigned line_number,
char *filename,
char *function_name,...);

[...]
What variadic arguments are supplied, and how does the
handler learn about them?

This is implementation defined. An implementation could store the source
code of the offending lines and pass it as a char * to the handler,
or it could pass a pointer to the stack frame so that the program
could change the values of some variables, who knows?

Ugh. That means the source code needs a different version
of the overflow handler for every implementation it might run on.
Sounds like a return to the pre-ANSI days, with separate #ifdef
blocks for every compiler known to Man.

I do exactly that. I setup a special label for each line of
code where an overflow is possible.

Is that enough? You say that if the overflow handler returns,
execution proceeds as if the overflowing operation had produced
some implementation-defined value. But if there are several
possible overflow sites in the same expression, and you have
only one "bail out" label per line, how can you know where in
the expression execution should resume?

x = a * f() >= 0 ? b * g() : c * h();

The choice of "What next?" -- and the observable side-effects
of that choice -- cannot be figured out based only on knowing
that the overflow occurred in line 42.

Sure, but that is with all jumps.

Sure, but you're going to greatly increase the number of
jumps by inserting a new one after every arithmetic operation.
Many more jumps means many more delay slots, which means it's
less likely that useful work can be found for them, which means
that more of them will be filled with no-ops. Instead of one
ADD or whatever, you get ADD,JOV,NOP -- maybe not quite as bad
as it looks because there are other instructions to load operands
and store results and stuff, but it still has the effect of
shrinking the instruction cache.

Happily DEC is no longer there, and COMPAQ, that bought DEC
is no longer there either, being bought by Hewlett Packard.

It's my impression -- only an impression, mind you -- that
ISO is not interested in a "Programming Languages - C for x86"
standard. You can't simply live in the 8086 past and ignore
modern designs.

Maybe. If overflow checking is too expensive and your application
doesn't need it, then just do not turn it on.

What happened to "zero overhead?"

 

[Keith Thompson]

1. In addition to "off" and "on", the pragma could have a third
setting "restore" which will restore to the state before the previous
"on" or "off", allowing this to be nested. So if someone doing
encryption wants no overflow checking, they put "off" and "restore"
around their code, and after that code we are back to the initial
setting.

The existing STDC pragmas (see C99 6.10.6) take an "on-off-switch"
argument, which can be any of ON, OFF, or DEFAULT.

What you're suggesting would require an implicit stack of settings.
Having every occurence of the pragma push a new value onto that stack
seems wasteful, conceptually if not practically.

I think there's some precedent for having PUSH and POP arguments. So
you could have:

#pragma STDC OVERFLOW_CHECK PUSH
/* doesn't change the current state, but sets things up for a
following POP */

#pragma STDC OVERFLOW_CHECK ON

...

#pragma STDC OVERFLOW_CHECK POP
/* restores previous state */

Or perhaps:

#pragma STDC OVERFLOW_CHECK PUSH_ON
...
#pragma STDC OVERFLOW_CHECK POP

I'm undecided whether this is worth doing, and if so just how it
should be specified. But if this were to be done for the
OVERFLOW_CHECK pragma, it should be done for all the STDC pragmas.

[...]

 

[Hallvard B Furuseth]

[...]
2.A: A new pragma
------------------

#pragma STDC OVERFLOW_CHECK on_off_flag

When in the ON state, any overflow of an addition, subtraction,
multiplication or division provokes a call to the overflow handler.
Operations like +=, -=, *=, and /= are counted also.
[...]

It occurs to me that this #pragma needs some tightening
up, because there are corner cases:

#pragma STDC OVERFLOW_CHECK OFF
x = a
#pragma STDC OVERFLOW_CHECK ON
+ b + c;
(...)

Make it scoped and copy the scope rules of the floating-point pragmas.
(#pragma STDC FP_CONTRACT, FENV_ACCESS, CX_LIMITED_RANGE).

Well, actually I haven't checked carefully if they have the same rules,
but it seems preferable to not have different arithmetic pragmas with
different scope rules.

A (weakly) related issue is to describe how faithfully the
generated code must follow the abstract machine. For example,
is it permissible to rewrite

#define OVERHEAD 1
#pragma STDC OVERFLOW_CHECK ON
x = a + OVERHEAD - 1;
as
x = a;
?

Heh. I can argue both sides of that one. If it's permissible, the
pragma definition would need to define what kind of code rewrites are
permissible. Anything between two sequence points, perhaps?

Nitpick: That's the same as the simpler "x = a + 1 - 1" since macros
are textually replaced, the replacement text doesn't carry a private
"OVERFLOW_CHECK" tagging around.



Some other thoughts:

char and short arithmetic can overflow, if they are as wide as int so
promotion to int does not protect from overflow. (In the case of char,
that means char must be at least 16 bits wide.)

Defining a overflow handler function is still fairly limiting for what
one can do once overflow is detected. Since the example implementation
already does a goto, it'd be possible to turn this into a try-except
with unfriendly syntax instead, by allowing something like
#pragma STDC OVERFLOW_CHECK goto oops;
Except if the hardware traps on overflow instead of setting a flag.
Maybe C++ people can say how exception handling deals with that, and
what it'd cost to insert it in C. Possibly too much except as an
option, I don't know. Jacob has already been invited to submit it to
C++ folks, who can submit to C after working with it.

I'd call it #pragma STDC INT_OVERFLOW_CHECK or something, to make the
distinction from floating-point pragmas visible.