473,842 Members | 1,838 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Making Fatal Hidden Assumptions

We often find hidden, and totally unnecessary, assumptions being
made in code. The following leans heavily on one particular
example, which happens to be in C. However similar things can (and
do) occur in any language.

These assumptions are generally made because of familiarity with
the language. As a non-code example, consider the idea that the
faulty code is written by blackguards bent on foulling the
language. The term blackguards is not in favor these days, and for
good reason. However, the older you are, the more likely you are
to have used it since childhood, and to use it again, barring
specific thought on the subject. The same type of thing applies to
writing code.

I hope, with this little monograph, to encourage people to examine
some hidden assumptions they are making in their code. As ever, in
dealing with C, the reference standard is the ISO C standard.
Versions can be found in text and pdf format, by searching for N869
and N1124. [1] The latter does not have a text version, but is
more up-to-date.

We will always have innocent appearing code with these kinds of
assumptions built-in. However it would be wise to annotate such
code to make the assumptions explicit, which can avoid a great deal
of agony when the code is reused under other systems.

In the following example, the code is as downloaded from the
referenced URL, and the comments are entirely mine, including the
'every 5' linenumber references.

/* Making fatal hidden assumptions */
/* Paul Hsiehs version of strlen.
http://www.azillionmonkeys.com/qed/asmexample.html

Some sneaky hidden assumptions here:
1. p = s - 1 is valid. Not guaranteed. Careless coding.
2. cast (int) p is meaningful. Not guaranteed.
3. Use of 2's complement arithmetic.
4. ints have no trap representations or hidden bits.
5. 4 == sizeof(int) && 8 == CHAR_BIT.
6. size_t is actually int.
7. sizeof(int) is a power of 2.
8. int alignment depends on a zeroed bit field.

Since strlen is normally supplied by the system, the system
designer can guarantee all but item 1. Otherwise this is
not portable. Item 1 can probably be beaten by suitable
code reorganization to avoid the initial p = s - 1. This
is a serious bug which, for example, can cause segfaults
on many systems. It is most likely to foul when (int)s
has the value 0, and is meaningful.

He fails to make the valid assumption: 1 == sizeof(char).
*/

#define hasNulByte(x) ((x - 0x01010101) & ~x & 0x80808080)
#define SW (sizeof (int) / sizeof (char))

int xstrlen (const char *s) {
const char *p; /* 5 */
int d;

p = s - 1;
do {
p++; /* 10 */
if ((((int) p) & (SW - 1)) == 0) {
do {
d = *((int *) p);
p += SW;
} while (!hasNulByte (d)); /* 15 */
p -= SW;
}
} while (*p != 0);
return p - s;
} /* 20 */

Let us start with line 1! The constants appear to require that
sizeof(int) be 4, and that CHAR_BIT be precisely 8. I haven't
really looked too closely, and it is possible that the ~x term
allows for larger sizeof(int), but nothing allows for larger
CHAR_BIT. A further hidden assumption is that there are no trap
values in the representation of an int. Its functioning is
doubtful when sizeof(int) is less that 4. At the least it will
force promotion to long, which will seriously affect the speed.

This is an ingenious and speedy way of detecting a zero byte within
an int, provided the preconditions are met. There is nothing wrong
with it, PROVIDED we know when it is valid.

In line 2 we have the confusing use of sizeof(char), which is 1 by
definition. This just serves to obscure the fact that SW is
actually sizeof(int) later. No hidden assumptions have been made
here, but the usage helps to conceal later assumptions.

Line 4. Since this is intended to replace the systems strlen()
function, it would seem advantageous to use the appropriate
signature for the function. In particular strlen returns a size_t,
not an int. size_t is always unsigned.

In line 8 we come to a biggie. The standard specifically does not
guarantee the action of a pointer below an object. The only real
purpose of this statement is to compensate for the initial
increment in line 10. This can be avoided by rearrangement of the
code, which will then let the routine function where the
assumptions are valid. This is the only real error in the code
that I see.

In line 11 we have several hidden assumptions. The first is that
the cast of a pointer to an int is valid. This is never
guaranteed. A pointer can be much larger than an int, and may have
all sorts of non-integer like information embedded, such as segment
id. If sizeof(int) is less than 4 the validity of this is even
less likely.

Then we come to the purpose of the statement, which is to discover
if the pointer is suitably aligned for an int. It does this by
bit-anding with SW-1, which is the concealed sizeof(int)-1. This
won't be very useful if sizeof(int) is, say, 3 or any other
non-poweroftwo. In addition, it assumes that an aligned pointer
will have those bits zero. While this last is very likely in
todays systems, it is still an assumption. The system designer is
entitled to assume this, but user code is not.

Line 13 again uses the unwarranted cast of a pointer to an int.
This enables the use of the already suspicious macro hasNulByte in
line 15.

If all these assumptions are correct, line 19 finally calculates a
pointer difference (which is valid, and of type size_t or ssize_t,
but will always fit into a size_t). It then does a concealed cast
of this into an int, which could cause undefined or implementation
defined behaviour if the value exceeds what will fit into an int.
This one is also unnecessary, since it is trivial to define the
return type as size_t and guarantee success.

I haven't even mentioned the assumption of 2's complement
arithmetic, which I believe to be embedded in the hasNulByte
macro. I haven't bothered to think this out.

Would you believe that so many hidden assumptions can be embedded
in such innocent looking code? The sneaky thing is that the code
appears trivially correct at first glance. This is the stuff that
Heisenbugs are made of. Yet use of such code is fairly safe if we
are aware of those hidden assumptions.

I have cross-posted this without setting follow-ups, because I
believe that discussion will be valid in all the newsgroups posted.

[1] The draft C standards can be found at:
<http://www.open-std.org/jtc1/sc22/wg14/www/docs/>

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell. org/google/>
Also see <http://www.safalra.com/special/googlegroupsrep ly/>

Mar 6 '06
351 13183
On Mon, 27 Mar 2006 10:35:54 +0000, Dik T. Winter wrote:
How many instructions will it take in that case to dereference p?


None or one? I don't know AS/400 assembly language, but it's said that
x86 learned from it. That can do scaled indexed access in zero cycles, if
the scale factor is one of the usual suspects. A reasonable compiler
would hide or elide essentially all of the other operations.

Why does it matter, anyway? AS/400 is no-one's speed demon. The whole
show runs on a VM. What the C compiler couldn't hide, the dynamic
recompilation engine (JIT) almost certainly could.

It's not as though C is the system's native tongue, nor it's system
implementation language. So what else is a system language going to do
there?

--
Andrew

Mar 27 '06 #341
On Mon, 27 Mar 2006 12:59:59 +0100, Chris Dollin wrote:
The C standard don't /outlaw/ forming illegal pointer values; they
just say that if you do that, they don't say anything more about the
behaviour of your code, so if you want defined behaviour, you have
to look elsewhere for the definition.
How much undefined behaviour can you stand? Sure, your code works OK this
year, but what if next year's super-optimizer switch takes a different
reading on some behaviour that you've coded to, because it was
"universall y" supported, but never the less undefined. Want to chase down
those bugs?

How many substantial applications do you suppose are written, that *only*
use defined behaviours? I suspect that the answer is very close to none.
If you're writing code that has, for whatever reason, to rely on
non-C-standard definitions, well then, rely on them. I've written code
that relies on non-C-standard behaviour, too - but I didn't expect it to
port everywhere, and I didn't expect such use to be a requirement on
future standardisation to support it, much as I might like to; the
leaves-it-undefined /allows/ the code to work where it works.


I like C. A lot.

I think that it could do to have a few fewer undefined behaviours, and a
few more defined (obvious) behaviours that you could rely on to describe
your algorithms.

That's one of the main things that I like about assembly language, btw: it
might be all kinds of painful to express an algorithm (although generally
not really all that bad), but the instruction descriptions in
the data books tell you *precicely* what each one will do, and
you can compose your code with no doubts about how it will perform.

[I don't read comp.lang.c, so if you want me to see any replies (hah! :-),
you won't take comp.arch.embed ded out of the Newsgroups. Of course, I can
imagine that just about everyone doesn't care, at this stage...]

--
Andrew

Mar 27 '06 #342
Andrew Reilly wrote:
On Mon, 27 Mar 2006 03:07:28 +0000, Dik T. Winter wrote:
Jordan Abel <ra*******@gmai l.com> writes:
On 2006-03-26, Stephen Sprunk <st*****@sprunk .org> wrote:

It simply doesn't make sense to do things that way since the
only purpose is to allow violations of the processor's memory
protection model. Work with the model, not against it.

Because it's a stupid memory protection model.

Why can't the trap be caught and ignored?


It can be ignored. But the result is that the operation is a
no-op. Again consider:
char a[10];
char *p;
p = a - 1;
p = p + 1;
what is the value of p after the fourth statement if the trap in
the third statement is ignored?


The trap isn't ignored. There is no trap: the platform's "sane C
memory model" compiler and run-time system updated p.array_index
to -1 and p.array_base to a.array_base at the third line, as
expected. The trap would be left enabled, so that it would
actually hit if/when a real pointer was formed from
&p.array_bas e[p.C_pointer_ind ex] if/when *p was ever referenced
in the subsequent code.

Consequently, the above code leaves p == a, as expected, and no
trap is encountered. Neat, huh?


Nope. Consider some code such as:

for (...; ...; ++p) {
for (...; ...; ++q) {
dothingswith(*p , *q);
/* qchecktime */
}
/* pchecktime */
}

With the normal check at pointer creation time, p is checked once
per iteration of the outer for. Your way, it is checked at every
use of *p, which will probably be far more often. Thus slowing
down the whole system and bringing snarlers_agains t_runtime_check s
out of every crack in the walls.

Checking pointer validity can be an involved process, depending on
architecture. It should be avoided, similar to casts, which at
least are obvious because the programmer writes them in.

--
Some informative links:
news:news.annou nce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html
Mar 27 '06 #343
Andrew Reilly wrote:
On Mon, 27 Mar 2006 12:59:59 +0100, Chris Dollin wrote:
The C standard don't /outlaw/ forming illegal pointer values; they
just say that if you do that, they don't say anything more about the
behaviour of your code, so if you want defined behaviour, you have
to look elsewhere for the definition.
How much undefined behaviour can you stand?


No more than what's covered by the defined behaviour on the platforms
I'm prepared to support, where `defined` isn't limited to the C
standard but over-enthusiatic uses of random other definitions isn't
desired.
Sure, your code works OK this
year, but what if next year's super-optimizer switch takes a different
reading on some behaviour that you've coded to, because it was
"universall y" supported, but never the less undefined. Want to chase down
those bugs?
Were I actively writing C - which at the moment I'm not - I'd have
tests to check behaviour, for this reason among others.
How many substantial applications do you suppose are written, that *only*
use defined behaviours? I suspect that the answer is very close to none.
That only use behaviour defined by the C standard? Few. That only
use behaviour defined by their intended platforms? Rather more.
If you're writing code that has, for whatever reason, to rely on
non-C-standard definitions, well then, rely on them. I've written code
that relies on non-C-standard behaviour, too - but I didn't expect it to
port everywhere, and I didn't expect such use to be a requirement on
future standardisation to support it, much as I might like to; the
leaves-it-undefined /allows/ the code to work where it works.


I like C. A lot.

I think that it could do to have a few fewer undefined behaviours, and a
few more defined (obvious) behaviours that you could rely on to describe
your algorithms.


Well, me too. But that doesn't stop me thinking that the standard seems
to be a reasonable compromise between the different requirements, as
things stand.
That's one of the main things that I like about assembly language, btw: it
might be all kinds of painful to express an algorithm (although generally
not really all that bad), but the instruction descriptions in
the data books tell you *precicely* what each one will do, and
you can compose your code with no doubts about how it will perform.


The first half is the reason I'd typically stay away from assembly
language, and I'm not convinced about the second unless one goes
into the amount of detail I'd happily leave to the compiler-writer.

--
Chris "x.f(y) == f(x, y) == (x, y).f" Dollin
The shortcuts are all full of people using them.
Mar 27 '06 #344

On Mon, 27 Mar 2006, CBFalconer wrote:
Andrew Reilly wrote:
On Mon, 27 Mar 2006 03:07:28 +0000, Dik T. Winter wrote:
Jordan Abel <ra*******@gmai l.com> writes:
On 2006-03-26, Stephen Sprunk <st*****@sprunk .org> wrote:
>
> It simply doesn't make sense to do things that way since the
> only purpose is to allow violations of the processor's memory
> protection model. Work with the model, not against it.

(FWIW, I agree with Stephen's sentiment. C's memory model seems
consistent to me: pointers point at objects, or are NULL, or are
garbage, with one special-case exception for pointers that point
"one past" objects. Extending the model to allow pointers that point
"one before" objects, or "ten past," doesn't seem useful enough to
be worth the hassle of defining all the behaviors on overflow, or
what happens if 'x' is "ten past" 'y' in memory, and so on. Just don't
write code that loops backward in an unsafe manner.)

[Proposing a different, flat-memory model for C.] The trap isn't ignored. There is no trap: the platform's "sane C
memory model" compiler and run-time system updated p.array_index
to -1 and p.array_base to a.array_base at the third line, as
expected. The trap would be left enabled, so that it would
actually hit if/when a real pointer was formed from
&p.array_bas e[p.C_pointer_ind ex] if/when *p was ever referenced
in the subsequent code.

Consequently, the above code leaves p == a, as expected, and no
trap is encountered. Neat, huh?
Nope. Consider some code such as:

for (...; ...; ++p) {
for (...; ...; ++q) {
dothingswith(*p , *q);
/* qchecktime */
}
/* pchecktime */
}

With the normal check at pointer creation time, p is checked once
per iteration of the outer for. Your way, it is checked at every
use of *p, which will probably be far more often. Thus slowing
down the whole system and bringing snarlers_agains t_runtime_check s
out of every crack in the walls.


Straw man. Every decent compiler does hoisting of loop invariants,
making both checks equivalent. (And if your compiler doesn't hoist
invariants, then you have no business talking about runtime efficiency
in the first place.)
Checking pointer validity can be an involved process, depending on
architecture. It should be avoided, similar to casts, which at
least are obvious because the programmer writes them in.


Obviously. That's why precious few C implementations /do/ pointer
validity checking in the first place. As I understand it, not even
the AS/400's compiler did pointer checking in software; it just did
whatever the hardware forced it to. And the hardware check presumably
/would/ have gone off at each dereference.

-Arthur
Mar 27 '06 #345
On 2006-03-27, Richard Bos <rl*@hoekstra-uitgeverij.nl> wrote:
Andrew Reilly <an************ *@areilly.bpc-users.org> wrote:
On Fri, 24 Mar 2006 08:20:12 +0000, David Holland wrote:
> Because p -= 2, when performed on the pointer 1234:4, tries to deduct
> 8 from the offset field. This underflows and traps.


And this is the behaviour that is at odds with idiomatic C.


_Whose_ idiom? No programmer I'd respect writes such code intentionally.

Richard


maybe not that in particular, but *p-- past 0 is no less idiomatic than
*p++ past the end.
Mar 27 '06 #346
On 2006-03-27, Arthur J. O'Dwyer <aj*******@andr ew.cmu.edu> wrote:
That's why precious few C implementations /do/ pointer validity
checking in the first place. As I understand it, not even the AS/400's
compiler did pointer checking in software; it just did whatever the
hardware forced it to. And the hardware check presumably /would/ have
gone off at each dereference.


according to others in this thread, apparently not, hence why it checks
on load.
Mar 27 '06 #347
Jordan Abel <ra*******@gmai l.com> writes:
maybe not that in particular, but *p-- past 0 is no less idiomatic than
*p++ past the end.


Really? It's not in *my* idiom, because I like to write code
that doesn't gratuitously invoke undefined behavior.
--
Ben Pfaff
email: bl*@cs.stanford .edu
web: http://benpfaff.org
Mar 27 '06 #348
On 2006-03-27, Ben Pfaff <bl*@cs.stanfor d.edu> wrote:
Jordan Abel <ra*******@gmai l.com> writes:
maybe not that in particular, but *p-- past 0 is no less idiomatic than
*p++ past the end.


Really? It's not in *my* idiom, because I like to write code
that doesn't gratuitously invoke undefined behavior.


a circular argument when you are defending the decision to leave it
undefined.
Mar 27 '06 #349
In article <pa************ *************** *@areilly.bpc-users.org>
Andrew Reilly <an************ *@areilly.bpc-users.org> wrote:
How much undefined behaviour can you stand?
Quite a bit, *provided* that this "undefined" is only in terms of
the C standard.

As I have noted elsewhere, doing something like:

#include <graphics.h>

invokes undefined behavior. I have no problem with including such
a file, though, where the behavior defined by some *other* document
is required.

What I try to avoid is:

- depending on behavior that is not only not defined by the C
standard, but also not defined by anything else, and merely
"happens to work today";

- making use of implementation( s)-specific behavior when there is
a well-defined variant of the code that also meets whatever
specifications are in use.

The latter covers things like doing arithmetic in "int" that
deliberately overflow temporarily, assumes that the overflow does
not trap, and then "un-overflows" back into range. If one codes
this in "unsigned int" arithmetic instead, one gets guaranteed
mod-2-sup-k behavior, and the code is just as small and fast as
the not-guaranteed version.
That's one of the main things that I like about assembly language, btw: it
might be all kinds of painful to express an algorithm (although generally
not really all that bad), but the instruction descriptions in
the data books tell you *precicely* what each one will do, and
you can compose your code with no doubts about how it will perform.


Actually, there are a number of instruction sets (for various
machines) that tell you to avoid particular situations with particular
instructions. Consider the VAX's "movtuc" ("move translated until
character") instruction, which takes a source-and-source-length,
destination (and destination-length?), and translation-table. The
manual says that the effect of the instruction is unpredictable if
the translation table overlaps with the source (and/or destination?).

Someone put a comment into a piece of assembly code in 4.1BSD that
read "# comet sucks". I wondered what this was about.

It turns out that whoever implemented the printf engine for the
VAX used "movtuc" to find '%' and '\0' characters, and did the
movtuc with the source string having "infinite" length (actually
65535 bytes, the length being restricted to 16 bits) so that
it often overlapped the translation table. On the VAX-11/780,
this "worked right" (as in, did what he wanted it to). On the
VAX-11/750 -- known internally as the "Comet" -- it did not behave
the way he wanted. The result was that printf() misbehaved for
various programs, because the assembly code depended on
undefined behavior.

(The "fix" applied, along with the comment, was to limit the length
of the source so as not to overlap the table. Of course, when we
rewrote the printf engine in C for portability and C89 support, we
stopped using movtuc entirely.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (4039.22'N, 11150.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
Mar 27 '06 #350

This thread has been closed and replies have been disabled. Please start a new discussion.

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.