A bug story: data alignment in C on x86 (2016)
pzemtsov.github.io
pzemtsov.github.io
https://elixir.bootlin.com/linux/latest/source/arch/x86/incl...
Or even NetBSD: http://ftp.netbsd.org/pub/NetBSD/NetBSD-current/src/sys/net/...
EDIT:
freebsd: https://github.com/freebsd/freebsd/blob/master/sys/netinet/i...
openbsd: https://github.com/openbsd/src/blob/master/sys/netinet/in4_c...
Also like the kernel is fairly sanely laid out. Its a project with literally hundreds of contributors so keeping the code base organized is important.
Copy code from NT kernel instead.
But looking back at the article, it seems like the author is complaining that the compiler used an unaligned move instead of an aligned one–but based on the code they wrote, this seems necessary. The compiler has no knowledge of any data alignment (how would it know that the data is always aligned without telling it?), so it emits conservative instructions.
This is where it became evident that the class of bug was going to be "assumed the language's machine model gets out of the way if you know the target platform". It's funny how easily we all forget about the nasal demons, but UB != implementation defined.
Which is a large part of why people complain.
The incorrect logic that causes the bug is thinking "I know that I can do X in assembly, therefore the naive translation to C should let me do the same thing." The idea that C is portable assembler is very widespread, but it is quite wrong, and it has been wrong for decades. A lot of people complain when they find out that the compiler doesn't work when they to write what is effectively assembler in C syntax, but quite frankly, many more people (including many of those who want it to be portable assembler) would complain if the compiler were to actually treat all C code as portable assembler.
The trouble here is that lots of programmers want/need a language that is like a portable assembler. It's all well and fine to say that C isn't such a language, but then what language shall we use?
Since there isn't an alternative, C needs to be that language.
The problem is that almost no one needs a portable assembler, and even those who want it very often only want it for very small snippets of code. If you want to specify something very exactly that is legal only because of the particulars of your machine, then use assembly. There are certainly a few things that compilers could expose that are poorly exposed in most languages (floating point environment, various flag bit manipulation including checked overflow and add-with-carry, vector instructions, synchronization barriers, underaligned types). But you don't need portable assembly for those things, just better compilers.
Ironic, considering that C was specifically designed for that from the beginning.
C isn't the first portable systems programming language, it just became ubiquitous thanks to UNIX.
Whichever way it happens, you'd have to rewrite the code for different architectures. If you're rewriting the code on different systems, why aren't you just using an assembler instead of a portable assembler?
However, Rust may be the answer you're looking for.
Right now, in safe code, all operations are well defined; there are a few compiler and standard library bugs which allow undefined behavior, but that's not intentional and many of them are just waiting on some compiler refactoring to land before they will be fixed.
In safe code in Rust, you can pass around references (bare pointers with no GC), work with byte arrays, allocate things on the stack or on the heap, etc. It does provide some restrictions in what you can do to make it possible to check statically that all of your code is safe.
There is also an unsafe subset; this allows the "I know what I'm doing" kind of manipulations you can do in C. Of course, this means that you could encounter undefined behavior; if you do something incorrectly, it could cause arbitrary behavior. The compiler has to be able to rely on certain guarantees that you uphold, because otherwise it could perform not even the most basic of optimizations, nor in many cases even know how to correctly compile the code.
There is an active effort to specify the exact guarantees applied to unsafe code. Right now it's "whatever the current compiler and LLVM happen to do", which is not particularly good in terms of guarantees.
The idea is to try to make something which will be amenable to validating the code. If undefined behavior is sufficiently well specified, then you can compile the code in an instrumented mode which will detect undefined behavior (at significant cost in speed), and you can run your test suite in that mode to get reasonably good guarantees that you don't have UB in your program (as long as your test suite has sufficient coverage).
Clang and GCC have similar modes, undefined behavior sanitizers, that compile code with instrumentation that can detect certain classes of UB. Since C's memory model wasn't designed with this in mind, and C has a fairly weak type system, they can't cover everything.
The hope with the current work on Rust is that a memory model can be formally defined such that all UB could be detected by such a sanitizer, so as long as you have sufficient test coverage, you can be confident of avoiding UB.
Of course, there are other tools you can use as well to avoid UB, like formal proofs of correctness, but it can be quite difficult to fully specify the language in a formal system, and writing proofs of correctness in such systems is not a trivial task.
I'd be interested in your ideas as to how this would be possible.
What we're looking for here is a certain sort of sane non-extremist portability. We want to support hardware that actually ships today as the primary application processor for a cell phone, laptop/notebook, tablet, desktop, or serious SQL or web server.
We don't want to think about opcodes or registers.
The hardware in use today is ARM, x86, and POWER. All of these normally support unaligned accesses, and so we expect that of the language. We see it in x86 except with that weird instruction that gcc wrongly used (it is slower) in this article. We see it in ARMv7 and ARMv8. We see it in POWER, going back at least to the PowerPC days.
All 3 of those architectures support little-endian code. It is now extremely rare to find big-endian ARM, and POWER is rapidly heading that way. It is essentially required by the web now, due to javascript Typed Arrays exposing endianness.
RISC-V is the same way: little-endian with support for unaligned access. This is the future.
The type of control and predictability desired is as follows:
If I have a 32-bit value, and I shift it left by 40 bits, there are only two reasonable answers. The compiler can do exactly as requested, producing a zero. The compiler can mask the shift down to 5 bits first, because hardware commonly does this, causing the shift to be by 8 bits. It is not at all OK for the compiler to do weird shit however, such as assuming that the code path can never be hit and then doing dead code elimination.
If I have a 32-bit 0x7fffffff and I shift it left by 1, that should produce the obvious result even if the data type is signed. (it is -2 in that case) Again, it is unacceptable to do weird shit. It is simply not OK to presume that my code will not run (due to an allowance made in the C standard for some 1960s hardware) and then do dead code elimination.
If I have a signed value and I shift it right, I expect the compiler to use the opcode for a signed shift. At least gcc promises to do this.
For the 1% non portable stuff there is unsafe code blocks or Assembly.
It doesn't need to be. Anyone who has done x86 Asm knows that it is (with the horrible exception of SSE) pretty much completely insensitive to alignment.
expecting some mythical version of x86 where all types are 1-byte aligned.
It's real, and it's called "#pragma pack(1)"
The System V ABI appears to explicitly allow so-called misaligned pointer dereferences, which makes sense as misalignment is, in general, not really a big issue on x86:
"Compilers should allocate independent data objects with the proper alignment ... However, some language facilities (such as FORTRAN EQUIVALENCE statements) may create objects with only byte align- ment. Consequently, arbitrary data accesses, such as pointers dereference or refer- ence arguments, might or might not be properly aligned. Accessing misaligned data will be slower than accessing properly aligned data, but otherwise there is no difference."
Similar wording permits it for x86-64:
"Like the Intel386 architecture, the AMD64 architecture in general does not re- quire all data accesses to be properly aligned. Misaligned data accesses are slower than aligned accesses but otherwise behave identically. The only exceptions are that __m128 and __m256 must always be aligned properly."
The Windows x64 ABI has suggested alignments for max performance but appears to allow anything.
"Although the access of data can stem from any alignment, it is recommended that data be aligned on its natural boundary to avoid performance loss (or a multiple thereof)."
You can ignore ABI if you are standalone. But you can't ignore the CPU.
Consider just the main function. You are free to ignore the ABI there but you still need to obey the cpu spec.
Requiring alignment with certain SSE instructions was the original poorly-thought-out misstep that lead to this bug. One of the basic principles of CISC is to implement instructions flexibly in hardware even if it requires microcode, then optimise that hardware to gain a performance advantage with each new generation.
If the original SSE instructions worked fine with unaligned data, perhaps being slower in such cases like all the other instructions did, then no expectations would be violated and everything would've worked out nicely. The fact that the explicitly unaligned version is now actually slightly faster in the benchmarks shown (because there doesn't need to be extra code to do alignment) is evidence enough that the original decision to have separate aligned/unaligned versions was really shortsighted. Very wide memory buses and multistage pipelines make alignment pretty much a non-issue.
The other big point this article doesn't mention is that rather than fighting with the compiler, if you already know what instructions you want, it would be better to write the Asm directly. For short sequences like these the Asm is going to be even clearer and shorter than "truly portable" C. In practice there really aren't that many architectures your code is going to run on.
_Bool check_ip_header_sum(const char* p, size_t size) {
struct Chunk { char arr[4]; };
const Chunk* chunks =
(const Chunk*)p;
union {
Chunk chunk;
uint32_t n;
} helper;
uint64_t sum=0;
for (size_t i=.....) {
helper.chunk=chunks[i];
sum+=helper.n;
}
........
}
(The latter is not something I've seen any compiler ever exploit though)
Well, other than memcpy. And it's kinda sketchy in the way that they did it: it was a tacked-on footnote in the C99 standard retained through to C11.
> create an array of function pointers of different types
Well, void * * or char * * (spaces so Hacker News doesn’t eat it) would do just as well…
It's assuming "size" is >= 20 and is a multiple of 4. That might be true for all valid headers, but at least in this snippet, there's no comment or anything stating the precondition that callers ensure the headers are valid. That's a(nother) bug.
If it's not true, it will read too much data. This means producing the wrong result. It also could make the read happen to cross a page boundary into space that isn't mapped into the process's virtual address space.
This is what happened to all unaligned accesses in the PowerPC 601 -> 603e transition in ~1995. Game developers writing their own “optimized” blit code suddenly found that every single unaligned access on the 603 would succeed, but it would go through an ISR to get there!
I feel for these kind of routines, either write it in dumb, straightforward C code and just use -O2 or -Os, or make an assembler version—possibly just a saved copy of the compiler’s output, but that’s enough to completely kill any interprocedural optimization. Trying to write ultra-optimized C code gives me a bit of a headache, unless it’s something that you can express straightforwardly as SSE intrinsics or something like that. You end up going through contortions to satisfy constraints imposed by the language which aren’t imposed by the machine.
> It's assuming "size" is >= 20 and is a multiple of 4. That might be true for all valid headers, but at least in this snippet, there's no comment or anything stating the precondition that callers ensure the headers are valid. That's a(nother) bug.
That’s too much of a reach to call it a bug. The IP header’s size is measured in multiples of 4 bytes, there is simply no way to encode a header which is not a multiple of 4 bytes. It becomes a question of how gracefully you want to handle true garbage being passed into the function… at best this is a matter of style. Should strlen() call assert(p!=NULL)? These days with asan, I’m not so sure that writing these assert() is the best way to spend my time.
I'd expect crossing a boundary between two valid pages to be fine; that's just part of making unaligned accesses work.
I'm talking specifically about an unmapped page. I don't have any data, but I'm pretty confident access to an unmapped page (such as null pointers) is a much more common source of SIGSEGV in general than unaligned access, to the extent that most programmers probably don't even know the latter is a possibility.
> That’s too much of a reach to call it a bug. The IP header’s size is measured in multiples of 4 bytes, there is simply no way to encode a header which is not a multiple of 4 bytes.
I take a pretty hard stance on this kind of thing.
The function might be used in a way you're not expecting. The article mentioned the IP frames can be read from a file. Maybe they're in some record-delimited format that states length in bytes, and that's the length that gets passed in rather than the original one. Redundant framing information like that is pretty common I think when you're using some general-purpose code (a library that handles a variety of record formats as well as some functions that operate on specific types like IP frames). Those records could get corrupted, even maliciously so; callers probably expect then to get back a nonsense result then but not an out-of-bounds read.
Or there could be a bug in the logic that decodes the header's length. By itself that won't cause memory errors, but combined with this assumption it does, and so I'm uncomfortable with the assumption being implicit.
I think a lot of C code's memory safety is dependent on this sort of implicit assumption that rots over time (if it was ever correct to begin with), and every time I see it I prefer memory-safe languages a little more.
Working in a language (Rust) that requires you to explicitly annotate such places with "unsafe" and have your public interfaces be "sound" (have it be impossible for safe code to cause the unsafe code to do the wrong thing) makes this more clear to me.
> Should strlen() call assert(p!=NULL)?
If it behaves in a surprising way when called with NULL, it should mention that case (either in an interface comment/manpage or via explicit assert). In practice on modern machines strlen raises SIGSEGV. [1] When folks see a SIGSEGV from strlen, they probably think wild pointer or missing terminator and will figure out exactly what happened before long.
[1] Although I imagine it's actually undefined behavior according to the C standard, so now I wonder if some compiler does / my compiler will someday do something more strange, and I'm sad.
In any case, I'd still say strlen(NULL) is qualitatively different than check_ip_header_sum(malloc(4095), 4095). The former's undefined behavior is standard (strlen is expected to dereference the pointer, so it makes sense that it has whatever problems doing that has). The latter shouldn't be expected to exceed the stated bounds without that being clearly stated.
if (!s) puts("hi");
strlen(s);
More fun is memset(0,0,0) which is technically verboten.
The function is already full of UB as we know it. You can add one more UB to the pile if you like.
> I take a pretty hard stance on this kind of thing.
That’s a valid choice that you can make, as is writing code in Rust. But what’s you’re doing is criticizing the design of an API that you have no actual knowledge of. For all we know this function is an internal function, not exported for use elsewhere, buried in some other code which performs the appropriate checks. We know, from the article, that other checks are performed elsewhere in the code, because it’s explicitly mentioned.
“Taking a hard stance” is all fine when you are writing or reviewing code, but in this case this kind of criticism is just noise. Save it for when you see a complete enough picture that your disagreements are more than just stylistic.
> In addition, the size can never be less than that – this is checked before calling this function.
Pointer casts are ALWAYS bad in C. Try to avoid them. Reply and down vote you old hat C programmers who will defend this. Your old practices are actively harmful to people learning the language.
int *i = malloc(sizeof(int));
IIRC, it is not valid C++. But malloc()/void * is somewhat rarer to find there, as you have better options.
void *malloc(size_t size);Also yes I'm radical enough to suggest the 50+ year old C standard library API is bad. Which isn't really a radical position >.>
mmap, for example, is free to require that the requested range be a multiple of a page; trying to use it as if it were malloc() would, on such systems, cause any allocations less than a page to require a whole page. And since this is a rather common case, you'd be using a ton more memory.
malloc(), however, can subdivide a large allocation from the OS into small allocations for the process; it is my understanding that most modern malloc()s will do this, in some form. (It is also my understanding that some malloc() implementations will use mmap() for allocating memory from the OS…)
Generally speaking `mmap` is the system call that
* Allocates memory
* Moves allocations around
`malloc` is the common entry point into a library that attempts to ensure you invoke the `mmap` system call as little as possible.
trying to use it as if it were malloc() would, on such systems,
cause any allocations less than a page to require a whole page.
And since this is a rather common case, you'd be using a ton more
memory.
[1] https://stackoverflow.com/questions/45458732/how-are-memory-...
> If you ask for 50bytes, it'll give you a full 4KiB page, because hardware can only segment memory in 4KiB chunks.
No, not really. (But you seem to realize this, as you contradict this point in the next quote I'll pull.) A malloc implementation is free to divvy up a page in order to service several allocations. Just because the pointer it returns to you is somewhere within a page that must, almost by definition, be a full page is irrelevant to the point of this discussion (that malloc() is not needed b/c mmap exists, and is somehow superior). The point is that the allocation consumes, in the grand scale of things, an amount on par with the requested size. (There is some overhead, of course, but not nearly the same are the mmap-must-return-a-full-page overhead.)
> Actually some allocators will attempt to _use_ those non-allocated regions of the remaining ~4046 bytes for other allocations in order to be faster (less systemcalls), this is why sometimes writing past buffer ends can give you garbage data instead of segfaults.
That was part of the point I was making.
You seem to have misunderstood my post. malloc() is free to divvy up a page (potentially handed to it by mmap) into several allocations. mmap() cannot. The point here is that replacing every malloc() call with a call to mmap() results in the loss of that ability to divvy up pages, requiring each allocation to be a full page; this would significantly bloat the memory consumed by an application, as small allocations would not share pages. Hence why those two calls are not equivalent, which is what the original post:
> you mean `mmap`?
> Also yes I'm radical enough to suggest the 50+ year old C standard library API is bad.
Very much seemed to imply. Though, again, I asked for clarification on your point, to make sure I'm understanding it, and you again failed to provide it. So, again,
> You didn't really clarify why you thought malloc() was bad, or why you think someone should call mmap() [in lieu of malloc()], so I'm mostly left to guess.
A malloc implementation is free to divvy up a page in
order to service several allocations
So when ever `malloc` gives you 50bytes without allocating an entire page it's just lying to you and giving you a pointer offset from another allocation. This isn't strictly being enforced by anything. There is zero contract that enforces what memory you can/cannot use.
There is, though; malloc's specification forms a contract. You are not allowed to access outside the bounds of the returned pointer. That some hardware allows it sometimes does not mean that there is "zero contract".
The function represents an interface, and an interface is a set of rules and behavior both the user & consumer of that interface expect. If you stray from that, it's UB, and the machine can do whatever at that point.
In this case, that's what matters. We don't know what hardware malloc or mmap will run on, and it isn't impossible that someone could implement a malloc() implementation that did enforce those bounds. valgrind, for example, is very close to this: it already knows when you access memory outside of the bounds of a malloc'd region (as that's its purpose: to report such accesses), and it would be a trivial modification to it to kill the program on an illegal access.
In short (as already stated, of course), you don't need to cast void * in C to/from other object pointers. Adding a cast to the return value of malloc() is a bad idea (I'm biased).
Nope. There's a reason that void * exists. How would you write a "generic" function like qsort without a pointer cast?
int compare_xyzzy(const void *a, const void *b)
{
const struct xyzzy *sa = a;
const struct xyzzy *sb = b;
return (sa->i > sb->i) - (sa->i < sb->i);
}
Example: https://svnweb.freebsd.org/base/head/sys/sys/tree.h?revision...
If anything it's the insanity of standards-lawyering antagonistic compiler-writers which is "actively harmful".
No one wants things like integer overflow checks being silently removed, yet there's an apparent surplus of people whose only reaction is to worship The Holy Standard and laugh at you for trying to use the language in the straightforward portable-assembler way that it was originally designed for.
Just because it was designed that way doesn't mean that's the way it works now. There are reasons why pointer casts are left undefined (as opposed to many other sources of undefined behavior, to which I heartily agree should have been left implementation-defined).