Much ado about NULL: An introduction to virtual memory(blogs.oracle.com)
blogs.oracle.com
Much ado about NULL: An introduction to virtual memory
https://blogs.oracle.com/linux/post/much-ado-about-null-an-introduction-to-virtual-memory
31 comments
There are 2 types of C programmers: those who have read Van der Linden, and those who have not.
In the context of vulnerability analysis it is often more convenient to mark undefined behavior with something implementation-defined. This is why you can say "a buffer overflow will overwrite the return address" or "this integer will wrap to be negative", or, in this context, NULL is represented with the zero address/bit pattern.
The article is from 2010 (missing tag) so the author likely is talking about 32 bit x86 machines. Also compilers from that era were less likely to exploit UB if at all. Certainly knowledge about it had only started trickling out in the general industry at the time as compilers started exploiting it with Chris Partner’s blog about it following about a year later [1].
[1] http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
[1] http://blog.llvm.org/2011/05/what-every-c-programmer-should-...
> Certainly knowledge about it had only started trickling out in the general industry at the time as compilers started exploiting it
It was common knowledge among C programmers long before then, for both security and portability reasons but optimization was also done. Old MacOS even used the higher 8-bits of pointers for MM flags. Other popular systems did equally weird things (think VAX.) That discussion linked to by the Jargon file is from 1992.
It was common knowledge among C programmers long before then, for both security and portability reasons but optimization was also done. Old MacOS even used the higher 8-bits of pointers for MM flags. Other popular systems did equally weird things (think VAX.) That discussion linked to by the Jargon file is from 1992.
I've programmed all these, old Macs certainly did weird stuff with the upper bits of pointers, Vaxen though have quite ordinary virtual address spaces, they do use upper bits to choose between page tables but that's about it
> Also compilers from that era were less likely to exploit UB if at all
No. Here's an LWN discussion of a CERT advisory in 2008 trying this nonsense, claiming it's a problem that GCC 4.2 elides futile late NULL checks. https://lwn.net/Articles/278137/
In fact several other compilers already had this optimisation, and CERT had to go back and revise the advisory because in practice all that's going on is, as now Real Programmers think their undefined program ought to do whatever it was they intended, and that's not how programming works.
No. Here's an LWN discussion of a CERT advisory in 2008 trying this nonsense, claiming it's a problem that GCC 4.2 elides futile late NULL checks. https://lwn.net/Articles/278137/
In fact several other compilers already had this optimisation, and CERT had to go back and revise the advisory because in practice all that's going on is, as now Real Programmers think their undefined program ought to do whatever it was they intended, and that's not how programming works.
> The article is from 2010 compilers from that era
Funny.
tcc was created in 2001 as a specifically non-optimising compiler.
Funny.
tcc was created in 2001 as a specifically non-optimising compiler.
> There is no guarantee that the in-memory representation of a NULL pointer is "all bits zero", that is implementation-defined and completely up the the architecture you're running on (and the compiler).
I always wondered if all the C codebases that do "if (somepointer)" to check for NULL were actually wrong of if the standard guaranteed that NULL always evaluates to false even if it's not implemented as zero. Apparently it's valid and everything works even in a theoretical architecture where NULL was not implemented as 0:
http://c-faq.com/null/ptrtest.html
I always wondered if all the C codebases that do "if (somepointer)" to check for NULL were actually wrong of if the standard guaranteed that NULL always evaluates to false even if it's not implemented as zero. Apparently it's valid and everything works even in a theoretical architecture where NULL was not implemented as 0:
http://c-faq.com/null/ptrtest.html
Yep, NULL doesn’t have a defined value, but that value must be false in a boolean context.
Under the hood, for this to work there's an implicit cast to boolean, even though at the time it was invented C doesn't have a formal boolean type.
So, (almost?) every expression in C has an implied boolean value, and the implied boolean value of pointers is false if they're NULL or true otherwise.
A better design is to have a boolean type, and require that the if condition tests only actual booleans, but this requires a substantial eco-system wide commitment, if you just insist on actual booleans you make programming needlessly tiresome and programmers say this language is bad because I have to write so much boilerplate for no gain. You need to actually provide the rest of the language features that make this pain worth it.
That commitment seems relatively affordable in 2021, but it was probably too big an ask when C was invented and by the time C was standardised it's too late. Likewise for C++.
So, (almost?) every expression in C has an implied boolean value, and the implied boolean value of pointers is false if they're NULL or true otherwise.
A better design is to have a boolean type, and require that the if condition tests only actual booleans, but this requires a substantial eco-system wide commitment, if you just insist on actual booleans you make programming needlessly tiresome and programmers say this language is bad because I have to write so much boilerplate for no gain. You need to actually provide the rest of the language features that make this pain worth it.
That commitment seems relatively affordable in 2021, but it was probably too big an ask when C was invented and by the time C was standardised it's too late. Likewise for C++.
> which is of course not a world that co-exists with our own
The "our own" world you are describing has recently been created by UB-exploiting compilers; it's a very strange and unintuitive place, is only described in inscrutable standards documents, and compilers don't properly warn you if you do something wrong even if you ask them to. A bit more understanding of people making mistakes seems appropriate.
The "our own" world you are describing has recently been created by UB-exploiting compilers; it's a very strange and unintuitive place, is only described in inscrutable standards documents, and compilers don't properly warn you if you do something wrong even if you ask them to. A bit more understanding of people making mistakes seems appropriate.
And in fact, most of "us" don't inhabit this world voluntarily.
And the standards in question are actually have very clear and simple language disallowing those shenanigans.
"Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message)."
Alas, that language was made non-binding and now the people who made it non-binding pretend it doesn't exist at all.
https://blog.metaobject.com/2018/07/a-one-word-change-to-c-s...
And the standards in question are actually have very clear and simple language disallowing those shenanigans.
"Permissible undefined behavior ranges from ignoring the situation completely with unpredictable results, to behaving during translation or program execution in a documented manner characteristic of the environment (with or without the issuance of a diagnostic message), to terminating a translation or execution (with the issuance of a diagnostic message)."
Alas, that language was made non-binding and now the people who made it non-binding pretend it doesn't exist at all.
https://blog.metaobject.com/2018/07/a-one-word-change-to-c-s...
Hm, I think "ignoring the situation completely with unpredictable results" pretty much covers everything. It's how optimizations generally work. Each optimization pass simply assumes there's no UB in the input and will optimize based on that assumption.
Optimizing compilers don't intentionally break programs with UB, they just ignore the possibility... with very unpredictable results.
Optimizing compilers don't intentionally break programs with UB, they just ignore the possibility... with very unpredictable results.
I don't think "optimising based on UB" is covered by "ignoring".
And neither is "optimising assuming UB never happens", especially if said UB is explicitly written in the code, thus contradicting the assumption.
And neither is "optimising assuming UB never happens", especially if said UB is explicitly written in the code, thus contradicting the assumption.
The compiler doesn't know if the program contains UB or not. How could it? Sure it can have warnings for some well know UB patterns but it can't catch them all. There are dedicated tools designed to detect UB which are not only very slow but fail to be totally effective (they have both false positive and negatives).
So the compiler simply ignores this possibility and optimizes assuming the input is a valid C program.
So the compiler simply ignores this possibility and optimizes assuming the input is a valid C program.
This isn't remotely true.
Unless you use the sleight of hand that is commonly used in vastly expanding the meaning of the word "valid" to mean "the compiler can assume there is no UB".
Which, again, isn't "ignoring the situation".
Unless you use the sleight of hand that is commonly used in vastly expanding the meaning of the word "valid" to mean "the compiler can assume there is no UB".
Which, again, isn't "ignoring the situation".
I disagree that it isn't "ignoring the situation". By analogy, if you saw a purple streetlight would you keep driving, stop, turn left, turn right, or make a U turn? You have to do something!
You'd probably assume it's a prank, and treat it as a green light by proceeding normally. Compiler code gen around UB is no more complex than this, though the consequences can cause complex chains of reasoning in later optimization passes.
You'd probably assume it's a prank, and treat it as a green light by proceeding normally. Compiler code gen around UB is no more complex than this, though the consequences can cause complex chains of reasoning in later optimization passes.
Hard disagree, your analogy is (still) incorrectly equating UB with "this should never happen".
That's not what UB is. UB is "the standard doesn't say anything about this particular situation, because we intentionally left the standard incomplete". It never said "UB cannot happen".
But even assuming your "purple streetlight" analogy, it exactly does not cover the "complex chains of reasoning" that the compilers then do.
I saw a purple streetlight, therefore I can just assume it is green. Nope.
I saw a purple streetlight, therefore I can now run over pedestrians. Nope.
I saw a purple streetlight, therefore this now an airport runway. Nope.
The compiler-writers' justifications don't pass even the most minimal test for coherence.
That's not what UB is. UB is "the standard doesn't say anything about this particular situation, because we intentionally left the standard incomplete". It never said "UB cannot happen".
But even assuming your "purple streetlight" analogy, it exactly does not cover the "complex chains of reasoning" that the compilers then do.
I saw a purple streetlight, therefore I can just assume it is green. Nope.
I saw a purple streetlight, therefore I can now run over pedestrians. Nope.
I saw a purple streetlight, therefore this now an airport runway. Nope.
The compiler-writers' justifications don't pass even the most minimal test for coherence.
> you cannot pass a pointer-sized value when you tell printf() you're passing an integer.
Actually you can. You probably shouldn't, particularly now that many 64 bit C machine models have different sized pointers and ints. If they were going to use an int conversion, they should have used %ld.
> You should use %p which is for printing pointers,
Agreed.
> [no nasal daemons] That's just being lucky,
Actually it isn't "just lucky". Well, to be precise it wasn't just lucky back when C compiler writers didn't stretch the idea of UB way beyond the breaking point, and way beyond certainly the intent and arguably the letter of the standard.
(The cop out is that the part of the standard that explicitly says all these shenanigans are not OK was made non-binding in later versions of the standard, it originally was binding, and thus people pretend that this part of the standard doesn't exist at all. But it does.)
> There is no guarantee that the in-memory representation of a NULL pointer is "all bits zero",
There is no guarantee of this in the C standard. However, the C standard is intentionally incomplete, i.e. conformance to the standard is not enough for an implementation to be "fit for purpose". I think it even used to say that somewhere in the standard.
> I realize that in practice, on common hardware, NULL is typically implemented as all-bits-zero,
For a very not to say overwhelmingly large value of "typically". I can't name a single implementation that does not, and my guess would be that total market share of such implementations would be less than 0.1%, and I believe I am being very conservative with that estimate. Which also means that if you are on such an architecture, you almost certainly know it.
> but that is not defined by the language.
...because the language definition is intentionally incomplete. People talk about the "C abstract" machine as if it were a thing. It's not. C maps to real hardware, that's the point of the language, and so taking the real-world behavior of the hardware that you are going to run on into account is perfectly fine.
Actually you can. You probably shouldn't, particularly now that many 64 bit C machine models have different sized pointers and ints. If they were going to use an int conversion, they should have used %ld.
> You should use %p which is for printing pointers,
Agreed.
> [no nasal daemons] That's just being lucky,
Actually it isn't "just lucky". Well, to be precise it wasn't just lucky back when C compiler writers didn't stretch the idea of UB way beyond the breaking point, and way beyond certainly the intent and arguably the letter of the standard.
(The cop out is that the part of the standard that explicitly says all these shenanigans are not OK was made non-binding in later versions of the standard, it originally was binding, and thus people pretend that this part of the standard doesn't exist at all. But it does.)
> There is no guarantee that the in-memory representation of a NULL pointer is "all bits zero",
There is no guarantee of this in the C standard. However, the C standard is intentionally incomplete, i.e. conformance to the standard is not enough for an implementation to be "fit for purpose". I think it even used to say that somewhere in the standard.
> I realize that in practice, on common hardware, NULL is typically implemented as all-bits-zero,
For a very not to say overwhelmingly large value of "typically". I can't name a single implementation that does not, and my guess would be that total market share of such implementations would be less than 0.1%, and I believe I am being very conservative with that estimate. Which also means that if you are on such an architecture, you almost certainly know it.
> but that is not defined by the language.
...because the language definition is intentionally incomplete. People talk about the "C abstract" machine as if it were a thing. It's not. C maps to real hardware, that's the point of the language, and so taking the real-world behavior of the hardware that you are going to run on into account is perfectly fine.
Android on 64-bit ARM uses the MSB of pointers for a tag. There are 2^8 NULL pointer values at the hardware level there.
Interesting! Do we actually need any of them apart from all zeros? Are the tags retained when converting?
The follow up post: https://blogs.oracle.com/linux/post/much-ado-about-null-expl...
^^^ This is where the actually interesting bits are, and it's not directly linked from part 1.
Note that this article is from 2010. Title should probably include a "(2010)".
HP-UX actually had an executable attribute bit that would control whether dereferencing a pointer to address 0 would accvio or result in the value 0.
I learned this fact when at least one library (OpenSSL? Kerberos?) shipped with the OS relied on the non-crashing behavior, unconditionally dereferencing an optional pointer-to-struct argument.
That was a fun debugging session.
I learned this fact when at least one library (OpenSSL? Kerberos?) shipped with the OS relied on the non-crashing behavior, unconditionally dereferencing an optional pointer-to-struct argument.
That was a fun debugging session.
> NULL is only slightly special as a pointer value: if we look in stddef.h, we can see that it's just defined to be the pointer with value 0.
Your C compiler is at liberty to use a different value than 0 for the actual NULL pointer stored in memory or in a register. It has to pretend to you that it is 0, but could be 0xDEADBEEF in reality.
Before ANSI C, NULL was #define-d as the actual bit value required. In modern C NULL is always 0.
In all the modern architectures I can think of a NULL pointer is represented by a value with all bits 0, but there are lots of examples of older architectures where this wasn't true.
There is a section in the comp.lang.c FAQ about this:
http://c-faq.com/null/machexamp.html
Your C compiler is at liberty to use a different value than 0 for the actual NULL pointer stored in memory or in a register. It has to pretend to you that it is 0, but could be 0xDEADBEEF in reality.
Before ANSI C, NULL was #define-d as the actual bit value required. In modern C NULL is always 0.
In all the modern architectures I can think of a NULL pointer is represented by a value with all bits 0, but there are lots of examples of older architectures where this wasn't true.
There is a section in the comp.lang.c FAQ about this:
http://c-faq.com/null/machexamp.html
Needing to care about a wart that's only there due to 40 year old, dead architectures is yet another problem with C.
At least in this case the standard goes to some length to make sure you don't have to care.
At least in this case the standard goes to some length to make sure you don't have to care.
40-year old dead architectures like Android on 64-bit ARM?[1] Pointer tagging isn't that rare, and as memory expands in practice I'd expect we might even end up wanting >64-bit systems to allow for >48-bit real address spaces and/or >16-bit tags.
The C standard means you don't have to care that there might actually be 2^8 NULL pointers since you're running on ARM with Top Byte Ignore in use.
[1]https://source.android.com/devices/tech/debug/tagged-pointer...
The C standard means you don't have to care that there might actually be 2^8 NULL pointers since you're running on ARM with Top Byte Ignore in use.
[1]https://source.android.com/devices/tech/debug/tagged-pointer...
This:
is not okay, you cannot pass a pointer-sized value when you tell printf() you're passing an integer. It needs to be:
You should use %p which is for printing pointers, and cast to void pointer.
Edit1: Oh, and I realize it "worked" for the author, no nasal demons [1] appeared and the code printed a number. That's just being lucky, and it's not a very nice foundation to base an argument on.
Edit2: Okay, now I read a little bit further and I'm pretty sure the author lives in the "pointers are just integers, and NULL is zero" world, which is of course not a world that co-exists with our own.
There is no guarantee that the in-memory representation of a NULL pointer is "all bits zero", that is implementation-defined and completely up the the architecture you're running on (and the compiler).
I realize that in practice, on common hardware, NULL is typically implemented as all-bits-zero, but that is not defined by the language. I don't even know if I make sense, obviously I'm a C buff and take these things rather seriously.
[1]: http://catb.org/jargon/html/N/nasal-demons.html