Hacker News Reader

> [You probably found the bug, right ? If not: the obvious issue is that 'struct ip_weight' needs padding for the second field.

No, the bug is thinking that hashing random bytes in your memory is correct. Why wouldn't you make a correct hash function for your struct ?!

I really have to second this one. It's still a rough point against C, but if padding isn't treaded as "semantically unreachable" idiomatically that IS the real gotcha.

The idiom here is to take the address of the struct and read the width of it's whole footprint in memory not just the field data. It's a weak idiom breaking under a common use case.

Maybe this is the biggest mistake of C, allowing users to access underlying raw memory so easily and misleading people with "convenient" functions like memcmp etc ?

Most "UB bugs" stem from users who think they know that a struct or data type will be laid out in a certain sequence in memory.

Unless I'm mistaken, the low-level acess to memory is one of the defining features of C. It's basically designed to be human-readable assembly (which is just human-readable machine code).

If anything, I'd blame compilers here -- IMO, they should automatically throw at least a warning any time they need to pad/rearrange a struct to make it explicitly clear to developers what's happening.

Access to low level memory such as registers is always explicitly requested with the volatile keyword. All other memory is implementation details. C is far from being a human readable assembly and has never been, except accidentally.

Even the old language spec from 1989 talks about an "abstract machine with the expressions being evaluated as specified by the semantics". One of the first chapters 1.2 Scope makes this very clear and then 2.1.2.3 Program execution clarifies this even further. Other things to note is that the spec doesn't mention variables being ever stored on the stack, instead it's called automatic storage, see "Storage durations of objects", the word stack is not even mentioned once throughout the whole spec.

Today with modern CPUs all this is even more important, if you think you are operating on a global memory array you are doing it wrong.

By 'mistake' I am considering the context of the times in which C was developed. Most of the UBE in C is there because of (1) the cost of mitigating it and (2) specifying it would impede portability.

Buffer overflows are UBE, too. But the way I proposed the fix is a pretty much cost-free solution, and it's optional.

Redefining C so that struct padding is always 0'd is an expensive solution, and rarely needed.

I am curious why you say cost-free.

Using std::vector/array/string::at would literally eliminate buffer overflows and yet programmers aren't generally using this style.

I would love it if I could prove to my colleagues that mandatory bounds-checking would not result in a noticeable performance loss, but my gut feeling is that it's not so. Interestingly Rust (and I guess D) does just that and seems to be getting away with it.

However, in the C UB thread the author of a Rust crate mentioned that a case for using unsafe is exactly this: avoiding the performance loss of bounds checking.

Turning the bounds checking on/off is done with a compiler switch. There indeed is a cost for leaving it on. Most users, however, regard the cost as worth paying for the protection.

It's still up to you, the programmer. With C, though, you have no choice. No checking for you!

I meant cost-free in the sense that one way or another in C code you wind up passing the length anyway, or in the case of 0 terminated strings, you wind up recomputing it if you don't pass it.

Regarding being worthwhile to pay for the protection, I would quote Hoare, regarding his experience with Algol compilers in production presented at the Turing Awards speech.

"Many years later we asked our customers whether they wished us to provide an option to switch off these checks in the interests of efficiency on production runs. Unanimously, they urged us not to--they already knew how frequently subscript errors occur on production runs where failure to detect them could be disastrous. I note with fear and horror that even in 1980, language designers and users have not learned this lesson. In any respectable branch of engineering, failure to observe such elementary precautions would have long been against the law."

I will reply with another Hoare quote, from a paper from 15 years later:

> Fortunately, the problem of program correctness has turned out to be far less serious than predicted. A recent analysis by Mackenzie has shown that of several thousand deaths so far reliably attributed to dependence on computers, only ten or so can be explained by errors in the software: most of these were due to a couple of instances of incorrect dosage calculations in the treatment of cancer by radiation.

https://www.gwern.net/docs/math/1996-hoare.pdf

Except that "far less serious than predicted" is not the same as non-existent, and that quote in no way talks about bounds checking, which is the issue being discussed here.

In real life, we use safety gloves, seatbelts, elbow and knee protection, helmets, chainsaw cover, gun lock, ....

Naturally there are those that think such protections are only for children and an accident will never occur to them, until the day they happen to be part of the statistic.

I long for the day that lawsuits for buggy software become a regular activity, only then the industry will actually care to change.

"Except that "far less serious than predicted" is not the same as non-existent"

Pure strawman. The statement was that program correctness is far less serious than predicted, not totally benign.

"and that quote in no way talks about bounds checking, which is the issue being discussed here"

Um, programs that exceed array bounds are not correct, so yes, it does talk about them.

[further strawmen not worth addressing]

Sure, you made it clear where we stand regarding quality.

"I am curious why you say cost-free."

What's the cost? It's an optional feature.

"Using std::vector/array/string::at would literally eliminate buffer overflows and yet programmers aren't generally using this style."

C programmers don't use that because it doesn't exist in C.

"I would love it if I could prove to my colleagues that mandatory bounds-checking would not result in a noticeable performance loss"

Did you read his article? There's nothing in it about mandatory bounds-checking.

If the feature is not used in production, it's not exactly improving safety any more than ASan, which is already available for C. So it has to be mandatory (e.g. by team/company decision) and then one has to look at the costs of enabling it.

No, that's completely wrong.

Interestingly, the idea of hashing over the bytes of a data structure would be possible in C++, but it is non-idiomatic and instead one would use hash functions for each type and in the case of a struct the individual members would be accessed to build the hash value.

The idea of using bytes is error-prone, but now that you mentioned it, pretty typical of the C mindset.

Of course C++ also has some of these cultural biases. I think they're an important reason why unsafe code continues to be written.

In C++, it depends from which tribe you came from.

The safe programming tribe, which I include myself, usually refugees from Wirth languages, makes use of C++ abstractions and type safety to deal with unsafety, including type driven development.

Meaning heavy use of templates, type wrappers, STL (or standard library if you prefer) data types, pre-processor only for #include and yes some meta-programming as well.

Then there is the tribe of C refugees, whose C++ compiler was forced on them due to a platform SDK, usually eschew anything standard. Might write some C++ like code due to interop with the SDK APIs and that's it.

Naturally there are a few tribes in-between, but these are the two major groups.

I object to reinterpreting bytes of one object as object of another type being C mindset. Yes, this is done sometimes if you really need it (compression being one example) but it's not really something you write everyday in C and doing it to calculate hash is just lazy.

Except that hashing a block of memory is likely to be much faster than hashing individual fields once there are more than a couple fields.

IMO the right solution would be a special annotation on a struct that says “I want the logical value of this struct to uniquely determine the bytes of the struct’s in-memory representation.”

Of course, adding such an attribute without nasty edge cases may be tricky.

But this mostly matter for arrays and then an alternative optimization might be to store it as a structure of arrays. This doesn't need the padding and is more simd friendly.

The C mindset is one of always looking for optimisations and thinking at the bit & byte level. The above solution flows naturally...

"Interestingly, the idea of hashing over the bytes of a data structure would be possible in C++, but it is non-idiomatic"

Because it's not conformant. Those possible C++ programs are broken.

I was making a point about language culture and decision making.

Conformance is a property of the code, the programmer's decision process is the really interesting thing here to me and I was arguing that such a solution is not unusual for C, but it would be for C++ , where a programmer would avoid it not because it's not conformant, but because it looks odd. pjmpl further clarified that it depends on the type of C++ programmer - I agree.

Non conformant code doesn't become an idiom, because it's broken. If you want to wrap that in a cultural framework, go ahead, but it rather misses the point.

> I was arguing that such a solution is not unusual for C

You may have asserted that (funny how people call their unsupported assertions "arguments"), but you're wrong if so. Again, it's broken, in C just as much as C++. You wrote

> instead one would use hash functions for each type and in the case of a struct the individual members would be accessed to build the hash value.

But this is just as much true in C as C++, because hashing pad bytes is wrong. In fact, C programmers are probably more aware of this than C++ programmers.

Bonus mess: If hash_function operates on bytes, but the input is cast to uint8_t* instead of (unsigned) char*, this is also a violation of aliasing rules and the compiler can technically just do whatever.

But uint8_t will most of the time be typedefed to unsigned char in stdint.h. So your code should be fine right now but may or may not become undefined in the future

Hummm, are you sure ? C Standard seems to allow signed/unsigned variants for aliasing rules ("a type that is the signed or unsigned type corresponding to the effective type of the object, a type that is the signed or unsigned type corresponding to a qualified version of the effective type of the object")

Probably not a big deal assuming uint8_t is a typedef for unsigned char.

The problem is that this is an assumption, not a guarantee. If somewhere, somewhen, some toolchain decides "actually, let's define this to __u8 and do fancy stuff with this compiler-internal type", your code breaks in the most mysterious way possible.

Type uint8_t is guaranteed to have 8 bit, no padding bits, 2s complement. You are talking about uint_least8_t or int_fast8_t.

Quote:

Exact-width integer types

           The  typedef  name  intN_t  designates  a signed integer type with width N, no padding bits, and a two's-complement representation.
           Thus, int8_t denotes a signed integer type with a width of exactly 8 bits.

           The typedef name uintN_t designates an unsigned integer type with width N.  Thus, uint24_t denotes an unsigned integer type with  a
           width of exactly 24 bits.

But what about unsigned char? It is guaranteed to have CHAR_BIT bits, where CHAR_BIT is at least 8. If CHAR_BIT is greater than 8, then uint8_t cannot be typedef'd to unsigned char.

I've stopped programming in C if I can help it. It's a crazy language with support for crazy machines.

If CHAR_BITS is greater than 8, then uint8_t cannot be defined because CHAR_BITS is defined as the width of the smallest object that is not a bit-field. If uint8_t exists, it must be the same width as unsigned char.

It must have the same width as unsigned char in that scenario, but that does not make it unsigned char. § 6.5 of C11 only allows casting to "a character type" (and a few cases irrelevant in this context), not "a type of CHAR_BITS width". There's no requirement that uint8_t is a typedef for unsigned char.

This wouldn’t be obvious if met in the wild, but once you pointed that bug exists, it is clear. The problem here is that we trust written code (its author) and rarely go into deep analysis at each line.

But like you said, you have to be aware of this effect at least, and it is not possible to eliminate that by simply clearing all variables to zero. See,

  p = (struct ip_weight *)some_used_mem;
  p->ip = ip;
  p->weight = weight;

At which point should imaginary p->garbage be set to zero? At cast? But that may again do unexpected thing, since casts usually do not modify data. The entire struct abstraction seems leaky as hell, but that’s the price of not dealing with asm directly.

These examples show that not C itself is hard, but low-level semantics are. You have to somehow deal with struct {x, y} and the fact that y has to be aligned at the same time. And have different platforms in mind. Maybe it is platforms that should be fixed? Maybe, but these are hardware with other issues that may be even harder to get right.

I think C is okay, really (apart from compilers that push ub to the limit). Type systems in successors try to hide its rough edges, but in the end of the day you end up with semantics of the compiler (c++, rust), that a regular guy has to understand anyway; it’s trading one complexity for another. C++ folks often seen treating it as magic, simply not doing what they’re not sure about. Good part is some languages force you to write correct code, no matter how much knowledge you have. But NewC could e.g. instead force one to create that ‘auto garbage’ to make it clear (why not, safety measures are inconvenient irl too).

I have no strong conclusion, but at least let’s think of all non-cs people who make their 64KB arduinos drive around and blink leds.

You don't need to set those bytes to 0 at all, why would you? The problem is that inside hash function you do incorrect type puning aka interpreting random bytes as numbers. Just read the fields and use their values for hashing.

Clang has -Wpadded to catch these kinds of bugs, FWIW. (and at least on my system it inits locals' padding with zero)

-Wpadded causes interesting... results when including glibc's headers.

While other comments suggest the solution is to implement the hash function based on field values, it throws away the simple, efficient, and general implementations of original memory based hash function. But if we understand the true source of the problem, isn't the obvious solution is to redefine the structure into two 64-bit fields or add in explicit padding bytes so one can explicitly zero them when necessary?

The reason for undefined behaviors is to avoid over engineering. In a capable engineer's eye, it is beautiful.

That, or declare them as packed.

C requires you to understand its conceptual execution and memory layout model in order to write safe code. That is, how the call stack works, the different types of storage, that each type has alignment requirements, and I'm not even mentioning threading issues.

No amount of syntax sugar on top will prevent you from writing unsafe code, unless that basic model is thrown away.

Quite the contrary, it's when people think they understand the memory layout, the callstack, the alignment requirements, etc and abuse that knowledge to "optimize" their code or out of sheer laziness you get all the problems of C. Just ignore how things are stored in memory and treat it like Java and you will be just fine. Only difference should be that you have to think about memory allocation and object lifetime/ownership.

Except that languages even older than C made those issues easier to track down.

You don't need to know anything about alignment to write normal safe C code. Only when to dive deep into performance optimization you start to worry about those things but hopefully by then you care enough to make sure to check what the language spec allows.

Seriously, just don't cast object of one type to another type and you can forget about alignment until you need to optimize.

Compiler generated SSE, and multithreading primitives, etc. will break on unaligned access even on relatively unalignment-tolerant x86 chips - to say nothing of stricter ARM CPUs.

You need to keep this in mind basically any time you're going from byte buffers to more complicated types. Basically anything touching allocation or IO needs to be aware of it, IMO, even before optimization.

Rust solved this particular class of problems nicely with `#[derive(Hash)]` without having to define what the padding bytes are.

I think Walter gave a very good argument for why it's the biggest mistake, and no warning will help with the consequences that he pointed out.

That C has UBE is not a mistake, it's fundamental to the language design, which allows for unrestricted access to the bare metal. If you want a different sort of language, use Java.

I don't think there is any UB case that applies to the given snippet, or am I missing something? Treating unpacked structs as byte buffers is asking for trouble.

To run into UB here you need to read struct's bytes as something else and then do calculations on them. UB or not it is asking for trouble. Why not just read field of the struct and use them to computer a hash?

I don't know much about C. Are there code analysis tools that would have caught the issue?

valgrind (--tool=memcheck) would probably have detected the issue, yes.

Why is struct ip_weight padded.. is it to make it word aligned on 64-bit platforms?

in_addr_t is a 32 bit integer. On 64 bit archs this will usually result in a 32 bit padding for word alignment.

Padding is needed for two reasons: 8 bytes element need to start at multiple of 8 bytes address and to make the whole struct size multiple of the biggest member. This is needed for alignment once those structs are need to each other for example in an array.

To align 'weight' member on its size.

so the pad will be before the 'weight' member in memory?

Yes. See here: https://stackoverflow.com/questions/4306186/structure-paddin...