473,842 Members | 1,835 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 13191
On Fri, 24 Mar 2006 12:04:43 -0700, Al Balmer wrote:
On Fri, 24 Mar 2006 10:05:23 +1100, Andrew Reilly
<an************ *@areilly.bpc-users.org> wrote:
Why do you want to create an address that you're not allowed to
dereference?


Because the ability to do so is implied by the syntax of pointer
arithmetic.


Heh. The presence of an open balcony on the 15th floor implies the
ability to jump off.


Sure. And it's OK to talk about it, too. No harm, no foul.

Forming a pointer to non-object space is "talking about it". Outlawing
talking about it goes against the grain of C, IMO.

--
Andrew

Mar 24 '06 #311
"Andrew Reilly" <an************ *@areilly.bpc-users.org> wrote in message
news:pa******** *************** ****@areilly.bp c-users.org...
On Fri, 24 Mar 2006 08:20:12 +0000, David Holland wrote:
I think you're overlooking something about how segmented architectures
actually work.


I think you're overlooking my assertions that I don't care how
(some) segmented architectures actually work. They are by *far* the least
significant of the processor architectures in use at the moment. Most of
the segmented architectures (by installed number: x86) are not used as
such, and even those that are do *not* have the particular behaviour with
respect to the range of the "offset" component of the non-flat pointer.

Sure, it's possible to write C code that operates within the restrictions
of such architecures. It's even easy. It is, however, not historically
representative of quite large bodies of C code. That's OK. The
architecture wasn't designed to run C code, and is not primarily coded in
C.


Interestingly, I wasn't even aware the AS/400 did this until I started
reading comp.arch, yet in nearly 10 years of C coding I've never (even
accidentally) written code that would trigger such a trap. I thought the
rule against forming pointers outside an object made sense, and I never saw
any valid reason to do so since the alternative was always cleaner and more
obvious to me. If your pointers are never invalid, you never have to worry
if it's safe to dereference them. Then again, I set pointers to NULL after
every free() too, so you probably consider me paranoid.

I also follow several open-source projects that have AS/400 ports, and the
patches those port maintainers submit is very rarely in this area: it's
usually in the OS-specific API calls (which the Windows folks have to submit
as well), Makefile adjustments, etc.
> If it doesn't trap, why should p -= 1 succeed, but p -= 2 fail?


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. The standard
has effectively forbidden such a construction (which is well defined and
works perfectly on every other architecture, and is convenient in many
obvious algorithms) just because this one architecture traps before any
attempt is made to access memory. The onus should instead have
been on the C implementation on this particular machine to paper over
this machine defect.


This "defect", as you so impolitely call it, is considered by the folks that
use such machines to be a feature, not a bug. Specifically, it is a feature
that _catches_ bugs.

Personally, I'd love if x86 had some automatic means to catch invalid
pointers on formation instead of catching them on access. Even the latter
isn't very effective, since it only catches pointers that are outside that
page of _any_ valid object; it happily misses accesses not only outside the
original object but also outside of any valid object but on a valid page.

You might consider it "correct" to form invalid pointers, which I'll grant
seems to make a tiny bit of sense if you're used to algorithms that do that,
but if being unable to do that is the price one must pay to catch invalid
accesses, that's a tradeoff I'd make.
You may have noticed that the compilation I did above is not actually
standards-conforming; because of the one-past-the-end rule, the size
of the segment for the array "a" has to be one larger than the array.
Otherwise, forming the pointer to the one-past-the-end element would
trap.


Only because the machine architecture is antipathetic to C. The syntax
and behaviour of C operators offers no suggestion that symmetrical
behaviour, or non-unit steps past the end of the "object" would fail, when
that particular idiom is catered-to (by hacking the underlying object
model: over-allocating the memory segment).


Over-allocating the segment defeats the main purpose of the model: catching
bugs. At best, when your hack does catch a bug, you'll usually be looking
in the wrong place.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin

*** Free account sponsored by SecureIX.com ***
*** Encrypt your Internet usage with a free VPN account from http://www.SecureIX.com ***
Mar 25 '06 #312
On Fri, 24 Mar 2006 22:55:56 -0600, "Stephen Sprunk"
<st*****@sprunk .org> wrote:
"Andrew Reilly" <an************ *@areilly.bpc-users.org> wrote in message
news:pa******* *************** *****@areilly.b pc-users.org...
On Fri, 24 Mar 2006 08:20:12 +0000, David Holland wrote:
I think you're overlooking something about how segmented architectures
actually work.


I think you're overlooking my assertions that I don't care how
(some) segmented architectures actually work. They are by *far* the least
significant of the processor architectures in use at the moment. Most of
the segmented architectures (by installed number: x86) are not used as
such, and even those that are do *not* have the particular behaviour with
respect to the range of the "offset" component of the non-flat pointer.

Sure, it's possible to write C code that operates within the restrictions
of such architecures. It's even easy. It is, however, not historically
representative of quite large bodies of C code. That's OK. The
architecture wasn't designed to run C code, and is not primarily coded in
C.


Interestingl y, I wasn't even aware the AS/400 did this until I started
reading comp.arch, yet in nearly 10 years of C coding I've never (even
accidentally ) written code that would trigger such a trap. I thought the
rule against forming pointers outside an object made sense, and I never saw
any valid reason to do so since the alternative was always cleaner and more
obvious to me.


After following this thread for quite a while, I still do not
understand what the problem is even with separate data and address
registers and memory access rules.

While very trivial addressing expressions (usually register indirect
or base+offset) can be handled directly by the memory access unit in
most architectures, any more complex addressing expressions (e.g.
multidimensiona l arrays) needs a lot of integer arithmetic processing
until the final result is _moved_ into the address register for the
actual memory access.

With separate data and address registers p=s-1 and p++ could as well
be calculated in integer registers and the final result (==s) would be
transferred to the address registers for memory access.

I do net find this problematic even in segmented access, unless
saturating integer arithmetic is used.

Paul


Mar 25 '06 #313
pemo wrote:
Just in case it hasn't been mentioned [a rather long thread to check!], and
might be useful, Google has an interesting summary on finding a nul in a
word by one Scott Douglass - posted to c.l.c back in 1993.

"Here's the summary of the responses I got to my query asking for the
trick of finding a nul in a long word and other bit tricks."

http://tinyurl.com/m7uw9


The earliest citation I found was from 1987 by Alan Mycroft here:

http://tinyurl.com/qtdt3

As to when some company is going to patent this technique some time in
the future, we'll just have to wait and see.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

Mar 25 '06 #314
On Fri, 24 Mar 2006 23:55:56 -0600, Stephen Sprunk wrote:
Interestingly, I wasn't even aware the AS/400 did this until I started
reading comp.arch, yet in nearly 10 years of C coding I've never (even
accidentally) written code that would trigger such a trap.
I do signal processing code. Working backwards through data, or in
non-unit strides happens all the time. I expect that *most* of my code,
for the last twenty years would break according to this rule. None of it
is "incorrect" (on the platforms that it runs on). None of it accesses
data outside allocated blocks of memory. It just happens that the
pointer-walking access code leaves the pointer dangling past the
allocated block, after the last access.

This rule essentially means that *p-- is an invalid access mechanism,
unless peculiar care is taken to exit loops early, while *p++ is valid,
*only* because they made a particular exception for that particular case,
because they figured that C compilers on AS/400 systems could afford to
over-allocate all arrays by one byte, so that that last p++ would not
leave the pointer pointing to an "invalid" location. That's a hack, plain
and simple.
I thought the
rule against forming pointers outside an object made sense, and I never
saw any valid reason to do so since the alternative was always cleaner
and more obvious to me.
Explicit index arithmetic, rather than pointer arithmetic, I guess?

See: it's not symmetrical or idempotic after all.
If your pointers are never invalid, you never
have to worry if it's safe to dereference them. Then again, I set
pointers to NULL after every free() too, so you probably consider me
paranoid.
Hey, I do that too. I just don't consider leaving a pointer dangling one
element short of an allocated array to be any less "invalid" than dangling
one element past the end. Or two elements, or some other stride.
And this is the behaviour that is at odds with idiomatic C. The
standard has effectively forbidden such a construction (which is well
defined and works perfectly on every other architecture, and is
convenient in many obvious algorithms) just because this one
architecture traps before any attempt is made to access memory. The
onus should instead have been on the C implementation on this
particular machine to paper over this machine defect.


This "defect", as you so impolitely call it, is considered by the folks
that use such machines to be a feature, not a bug. Specifically, it is
a feature that _catches_ bugs.


Sure. They write code for banks. Good for them. That machine feature
probably works beautifully in that situation, with the designed-for COBOL
or PL/1 codebase.

I write code that has to waste as few cycles as possible, and take up as
little code space as possible, and be portable to the widest variety of
chips as possible. I don't need to be unrolling the last loops of my
algorithms, just to make sure that the pointers aren't decremented that
one last time.
Personally, I'd love if x86 had some automatic means to catch invalid
pointers on formation instead of catching them on access. Even the
latter isn't very effective, since it only catches pointers that are
outside that page of _any_ valid object; it happily misses accesses not
only outside the original object but also outside of any valid object
but on a valid page.
You know, you can have that, if you want it. There are plenty of people
who build C compilers and run-time environments that put all sorts of
run-time checks into your code. Or: you could use a language (like Java)
that gave you good solid guarantees that you'll get an exception if you
even try to read something out of range. And they don't have pointers as
such to worry about. Peachy keen.
You might consider it "correct" to form invalid pointers, which I'll
grant seems to make a tiny bit of sense if you're used to algorithms
that do that, but if being unable to do that is the price one must pay
to catch invalid accesses, that's a tradeoff I'd make.


It *doesn't* catch invlaid accesses. If anything, some other mechanism
catches invalid accesses. Traping on out-of-range pointer formation just
gets in the way of clean code.
Only because the machine architecture is antipathetic to C. The syntax
and behaviour of C operators offers no suggestion that symmetrical
behaviour, or non-unit steps past the end of the "object" would fail,
when that particular idiom is catered-to (by hacking the underlying
object model: over-allocating the memory segment).


Over-allocating the segment defeats the main purpose of the model:
catching bugs. At best, when your hack does catch a bug, you'll usually
be looking in the wrong place.


You seem to have missed the part of the discussion where over-allocation
was the concession that the AS/400 C implementers gave to the standards
body so that the wildly more common loop-until-just-past-the-end idiom
worked OK. It's *their* hack. Bet their COBOL and PL/1 and Java
compilers don't have to over-allocate like that. They declined to
over-allocate by one element before an array because there's no telling
how large each element might be. That would be too costly. So you end up
with this pallid, asymmetric shadow of the C that might have been (and
once was).

--
Andrew

Mar 25 '06 #315
"Paul Keinanen" <ke******@sci.f i> wrote in message
news:t8******** *************** *********@4ax.c om...
On Fri, 24 Mar 2006 22:55:56 -0600, "Stephen Sprunk"
<st*****@sprunk .org> wrote:
Interestingly , I wasn't even aware the AS/400 did this until I started
reading comp.arch, yet in nearly 10 years of C coding I've never (even
accidentall y) written code that would trigger such a trap. I thought the
rule against forming pointers outside an object made sense, and I
never saw any valid reason to do so since the alternative was always
cleaner and more obvious to me.
After following this thread for quite a while, I still do not
understand what the problem is even with separate data and address
registers and memory access rules.

While very trivial addressing expressions (usually register indirect
or base+offset) can be handled directly by the memory access unit in
most architectures, any more complex addressing expressions (e.g.
multidimensiona l arrays) needs a lot of integer arithmetic processing
until the final result is _moved_ into the address register for the
actual memory access.


Perhaps. Or perhaps the same operations are allowed on address registers.
I don't know the AS/400 well enough to say, but I'm certain that there are
instructions to increment/decrement address registers. I'd also expect
complex addressing modes to be available on instructions using those
registers, whereas you'd have to use several arithmetic instructions on
integer registers.
With separate data and address registers p=s-1 and p++ could as well
be calculated in integer registers and the final result (==s) would be
transferred to the address registers for memory access.

I do net find this problematic even in segmented access, unless
saturating integer arithmetic is used.


Considering that s is probably already in an address register, doing the
manipulation your way would require transferring it to an integer register,
doing the decrement, then doing the increment, then transferring it back to
an address register when it's needed for dereferencing. Why do that when
you can adjust the address register directly?

Also consider that pointers on such a system are likely to be longer than
the largest integer register. That means you'd have to store the pointer to
RAM, load part of it into an integer register, manipulate it, store that
part, load the other part, manipulate it, store it, and load the new pointer
back into an address register. That's a lot of work to do.

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.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin

*** Free account sponsored by SecureIX.com ***
*** Encrypt your Internet usage with a free VPN account from http://www.SecureIX.com ***
Mar 26 '06 #316
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?
Mar 26 '06 #317
"Stephen Sprunk" <st*****@sprunk .org> writes:
"Andrew Reilly" <an************ *@areilly.bpc-users.org> wrote in
message news:pa******** *************** ****@areilly.bp c-users.org...
On Fri, 24 Mar 2006 08:20:12 +0000, David Holland wrote:
I think you're overlooking something about how segmented architectures
actually work.


I think you're overlooking my assertions that I don't care how
(some) segmented architectures actually work. They are by *far* the least
significant of the processor architectures in use at the moment. Most of
the segmented architectures (by installed number: x86) are not used as
such, and even those that are do *not* have the particular behaviour with
respect to the range of the "offset" component of the non-flat pointer.

Sure, it's possible to write C code that operates within the restrictions
of such architecures. It's even easy. It is, however, not historically
representative of quite large bodies of C code. That's OK. The
architecture wasn't designed to run C code, and is not primarily coded in
C.


Interestingly, I wasn't even aware the AS/400 did this until I started
reading comp.arch, yet in nearly 10 years of C coding I've never (even
accidentally) written code that would trigger such a trap. I thought
the rule against forming pointers outside an object made sense, and I
never saw any valid reason to do so since the alternative was always
cleaner and more obvious to me. If your pointers are never invalid,
you never have to worry if it's safe to dereference them. Then again,
I set pointers to NULL after every free() too, so you probably
consider me paranoid.

I also follow several open-source projects that have AS/400 ports, and
the patches those port maintainers submit is very rarely in this area:
it's usually in the OS-specific API calls (which the Windows folks
have to submit as well), Makefile adjustments, etc.

[...]

I asked in comp.std.c whether the AS/400 actually influenced the C
standard. Here's a reply from P.J. Plauger:

] AS/400 might have been mentioned. Several of us had direct experience
] with the Intel 286/386 however, and its penchant for checking anything
] you loaded into a pointer register. IIRC, that was the major exmaple
] put forth for disallowing the generation, or even the copying, of an
] invalid pointer.

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Mar 26 '06 #318
On Sat, 25 Mar 2006 19:46:43 -0600, Stephen Sprunk 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.


Why force the AS/400's restrictive memory model on coders for all other
architectures? The "use the subset that's known to work anywhere"
argument is no kind of absolute: it's a moveable trade-off. Some systems
are just so restricted or so different, and represent such a small portion
of the market that it doesn't make sense to accommodate them: they need to
accommodate the wider community, if they want to join in that particular
game. Now, obviously, the AS/400 memory model managed to sneak it's nose
into the C standards tent one day when the standards body was feeling
particularly inclusive, and now we're all saddled with it (to mix a few
metaphors.)

--
Andrew

Mar 26 '06 #319
On Sun, 26 Mar 2006 02:53:13 +0000, Keith Thompson wrote:
I asked in comp.std.c whether the AS/400 actually influenced the C
standard. Here's a reply from P.J. Plauger:

] AS/400 might have been mentioned. Several of us had direct experience
] with the Intel 286/386 however, and its penchant for checking anything
] you loaded into a pointer register. IIRC, that was the major exmaple
] put forth for disallowing the generation, or even the copying, of an
] invalid pointer.


I don't understand this argument. The 286/386 doesn't even *have* pointer
registers, as such. It has segment descriptors, which can be used to make
things complicated, if you want to, but when you use a 286 as the 16-bit
machine that it is, then there is no issue here at all. Similarly, the
386 can be used as a perfectly reasonable "C machine", and generally is,
these days. It only gets curly when you try to synthesize an extended
address range out of it. Unfortunately, the dominant compiler and platform
made a hash of that, rather than putting in the effort to make it work in
a (more) reasonable way.

Since that particular platform is (thankfully) falling into obsolescence,
can't we start to consider tidying up the standard, to allow more
traditional, idiomatic, symmetrical codeing styles? Restore
pointer-oriented algorithm expressions to their place of idempotic
symmetry with index-oriented expressions? Please?

--
Andrew

Mar 26 '06 #320

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.