39

As we know, in C to dereference a null pointer is undefined behaviour. From what I understand, the PDP-7 and the PDP-11 both have ordinary memory that can be written to and read from at address 0.

On the PDP-11, that address is part of a memory region used to specify EMT and TRAP vectors. An operating system probably needs to be able to initialise these to the entry point of device drivers or whatever. And depending on model and configuration, writing to this memory location might cause a trap -- but the same goes for all other memory locations. So location 0 is not unique in that respect on this platform.

From what I can tell, the PDP-7 had ordinary memory at that address, just as many other machines do. But I understand that UB is very useful to compilers which need to be able to not guarantee a particular behaviour so that a particular architecture can be targeted easily.

So my question is what led some C standard to treat the NULL pointer differently from any other pointer? Did K&R want to target an exotic architecture or something?

  • 48
    Your question seems to assume that NULL is 0x00000000. That was not always the case. On various C compilers it was 0xFFFFFFFF or even 0xDEADBEEF. It was always bad practice to assume NULL was zero. – Chenmunka Feb 6 '18 at 11:54
  • 3
    DEADBEEF originated on IBM mainframes as a code for an invalid value, but it did spread to other systems. See stackoverflow.com/q/2907262/2870922 for a little information. – Chenmunka Feb 6 '18 at 12:17
  • 13
    DEADBEEF is a common 'joke' calue to denote special situations. It works fine in hex dumps, usually on big endian machines. Often data structures start with link pointers, DEADBEEF instead of 00000000 also made clear that it's on purpose, as a value of 00000000 (or FFFFFFFF) could also originate in a previous clearing of the memory area. – Raffzahn Feb 6 '18 at 12:25
  • 1
    @Raffzahn: Yes, but I always thought of those machines as mainframes. I can see this becoming a question in its own right. – Chenmunka Feb 6 '18 at 12:29
  • 9
    @Chenmunka Ok, I see. Well, being in contact to /370ish machines since the late 1970, I developed a quite fundamentalist view here. Only /370 and alike machnes are mainframe. everything else is a toy, made for department use where business suits try to emulate real IT. A midrange system and it's users where in the old days to us about the same as some loony trying to run a company on Excel sheets and Word-macros. The only exception here are eventually scientific machines (CDC/Cray/etc.). While not being able to do real work, they do have some feats. – Raffzahn Feb 6 '18 at 12:44
27

The definition of NULL is a syntactic crutch to allow a programmer a clear expression that a pointer is, at certain times, pointing nowhere. It's meant for readability - and with increased compiler bloat even for automated checks.

On a hardware level there is no such thing. A pointer is a word, and a word always holds a valid number. So by convention zero was chosen - it could have been any other. Like -1 for example. Selecting 0 offered the advantage that a simple if(pointer) could be used to check if it's a valid pointer (or more correct, not 0).

So my question is what led some C standard to treat the NULL pointer differently from any other pointer?

C also doesn't treat NULL different from any other pointer. The C-Lib in contrast does, but not because of NULL, but rather as its (runtime) value of 0 will make some functions fail, when used as input.

Did K&R want to target an exotic architecture or something?

Nop. It's a concept needed from a pure software engineering point of view. Having a syntactic construct to handle uninitialized pointers improves readability and possibly enables further checks.


Now, for the historic part, NULL is, like the related handling of TRUE/FALSE inherited from BCPL (through B). Just here it was called nil.


Even with that little historic bit, I'm not sure if Retrocomputing is the right place to ask for this, as it's about a basic concept in software engineering and not anything burdened with historic implication. So a quick search in Software Engineering and Stack Overflow shows that this question has been asked many times. It's something people always stumble on, isn't it?

  • 1
    Comments are not for extended discussion; this conversation has been moved to chat. – Chenmunka Feb 7 '18 at 12:21
  • 4
    A NULL pointer does not need store the number 0. The C standard says that converting the integer 0 to a pointer will produce a NULL pointer. That's why memset() for 0 initialization is only safe to use with integers. When you put pointer inside an if, the pointer is converted to an integer - that's why you can use it in an if expression. – martinkunev Feb 7 '18 at 13:11
  • I've never heard of a NULL pointer referred to as a VOID pointer. A void pointer (aka a value with type void*) is a pointer that doesn't have a concrete type, not one that is null. – Mike Caron Feb 7 '18 at 15:40
  • 4
    The C standard does treat null pointer differently form any other pointer. E.g. see 6.3.2.3/3: An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function. – Ruslan Feb 7 '18 at 16:04
  • 2
    @martinkunev: "The C standard says that converting the integer 0 to a pointer will produce a NULL pointer." No, only integral constants, not values of integer variables. "When you put pointer inside an if, the pointer is converted to an integer" No, the if statement controlling expression is compared against 0. And the conversion turns the integral constant zero into a null pointer value -- the pointer is not turned into an integer. – Ben Voigt Feb 8 '18 at 5:02
19

The important thing you may be missing is that a null pointer in C is not required by the standard to have the same binary representation as the number zero. It is still a "normal" pointer, but it points to a special location that the program is not allowed to use.

The integer constant 0 is turned into nullptr when used as a pointer. Similarly, 0 will become 0.0 when used in floating-point calculations, or false in boolean operations. Coercions are not just one-way: if(ptr) will convert a pointer into a boolean which indicates whether the pointer is not null. All of these conversions serve to avoid requiring that a null pointer shares the same representation as zero.

Most machines represent integer zero as all-bits-zero and comparisons against that are particularly cheap, so it is worthwhile to arrange things so that sentinel values such as null pointers and end-of-string markers are all-bits-zero, and also that +0.0 and false are also all-bits-zero.

There is some subtlety in C in that a literal 0 is converted into nullptr, whereas casting an integer that happens to be zero into a pointer will produce a pointer to location zero. Because they are the same thing on modern platforms, a whole class of potential bugs go away.

  • Which standard have you described here? – Wilson Feb 6 '18 at 12:11
  • 1
    @Wilson I informally described the C standard. My copy is marked ISO/IEC 9899 and pointers are discussed in section 6.3.2.3. Note what is not said there. – pndc Feb 6 '18 at 12:22
  • 11
    I think you meant "a null pointer" where you wrote nullptr - the latter is a C++ keyword, but not defined in C. – Toby Speight Feb 6 '18 at 18:09
  • 4
    Converting an integer expression that evaluates to zero -- and that is not an integer constant expression -- to a pointer type produces implementation-defined behavior, and carries a bunch of caveats. This might yield a pointer to address 0, or it might not. – John Bollinger Feb 6 '18 at 21:24
  • 3
    You seem to be describing C++. There is no nullptr in C. Also, if works with integers. If you put a pointer inside, it is converted to an integer (not to a boolean). – martinkunev Feb 7 '18 at 13:15
13

Another relevant historical tidbit: You may have noticed that the values chosen for NULL - i.e 0xFFFFFFFF and 0xDEADBEEF - are both odd-valued addresses. Most architectures (certainly most at the time Unix was created) did not implement addressing down to the individual byte; they were only able to address words of two or four bytes - that is, only even-valued addresses were legal. By choosing an odd-valued address for the value of NULL, the C compiler and runtime system ensured that any attempt to actually dereference NULL would immediately trap to the OS; that is why the usual error for dereferencing NULL on Unix is 'Segmentation Violation'.

  • 9
    On many systems you get SIGBUS (Bus error) for presenting an unaligned address - usually SIGSEGV is for any access to memory not mapped for the process. – Toby Speight Feb 6 '18 at 18:17
  • 1
    Apart from that final error, addressed in @TobySpeight's comment, this answer is correct. It brings something up that not many previous answers have. Welcome to Retrocomputing Stack Exchange. You might find the tour interesting. – wizzwizz4 Feb 6 '18 at 20:55
  • You get SIGSEGV for NULL dereference on modern Unix systems (including ones where alignment is required) because the zero page of virtual address space is not mapped. Most systems do use 0 as the run-time bit-pattern for NULL. – Peter Cordes Feb 7 '18 at 2:02
  • You're conflating word-addressable memory (you can't reference the individual bytes of a word with single-byte load/store) with alignment-required for word loads, but still having byte-addressable memory. (So two adjacent 4-byte words have a difference of 4 in address. Even if (like on early Alpha AXP) there aren't byte load/store instructions. Many RISC machines require alignment for word loads, but still have byte loads. So yes, a NULL deref with a word load might SIGBUS. – Peter Cordes Feb 7 '18 at 2:06
8

Tony Hoare somewhat-famously in 2009 said this:

I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn't resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.

While I don't have any specific citations, I suspect that C was influenced by ALGOL, or just made the same decision separately since having a specific value to represent "not a valid reference" was an easy and useful thing to do. It wasn't so much about "how to point to a specific part in memory that's named 'zero'" as much as "we need to define a way to indicate that a pointer is not currently valid", particularly as a sentinel value. Given the constraints of computers at that time, it seemed a reasonable thing to do. So, one just creates a value called "NULL" which can be assigned to any pointer type, and there you have it.

  • 7
    I see no reasonable basis for regarding null as a mistake. It's often necessary to create an array of pointers and then read out some values before all values have been written. Having non-written items read out as null is better than any other alternative unless one has separate syntax for "read out and trap if null" and "read value without trapping even if null". The biggest problem with null is that many language implementations do not adequately trap for it. – supercat Feb 6 '18 at 21:54
  • 2
    Well, @supercat, your argument is with Tony Hoare, not with Peter, who's just quoting here. For a (non-retro) way to tame NULL, one worthwhile approach is the Null Object design pattern. It's still hard to enforce in C-family languages, where we can point to NULL or to deallocated memory (C++ references don't quite fit, as they aren't reseatable). – Toby Speight Feb 7 '18 at 8:04
  • 1
    Yes, I wasn't trying to present an opinion on the usefulness of NULL so much as present the little bit of the history that I'd heard of, that it was added to ALGOL because it was easy and seemed useful. Especially as the question was looking for the influences that led to C having NULL as a concept, I thought the quote might shed some light on it. – user616 Feb 7 '18 at 13:08
  • @supercat So you do see a reasonable basis for regarding null as a mistake after all. See your last sentence and look out for adequately trapping null values in ALGOL. :-) – BlackJack Feb 7 '18 at 14:22
  • @BlackJack: From what I understand, the choice Hoare faced was between having pointers only be usable as values if they identify valid storage, or having a default pointer value which cannot be dereferenced but can be treated as a value. Given those choices, the former is not by any stretch of the imagination a "mistake". Having implementations trap attempts to dereference null pointers or apply a non-zero displacement would have been reasonably practical, and if languages had routinely included features to do so, CPUs could have added instructions to assist with the latter part of that. – supercat Feb 7 '18 at 15:34
4

For the PDP-11, you're thinking of physical address 0 for interrupt vectors. Logical address 0 in a user program just contains the first bytes of program code, i.e. the primary entry point ("start" from crt0.s). On a default executable, nothing stops you from reading it or writing to it, though if you write after the address returned to by main, you're gonna have a bad time. With ld -n, it'll be read-only and attempting to write it will cause SIGSEGV.

So in that sense, a null pointer and a pointer to the "start" routine were identical, but it wasn't actually possible to reference assembly routines that did not begin with underscores from C. The PDP-11 probably wasn't the only architecture to put machine code (particularly startup code) that was not a valid C function at the zero address... it's a natural place to begin execution at, it wasn't something you could intentionally make a C pointer to, and it's something you need anyway.

The other solution is just to waste some small amount of space ensuring that that address is not used for anything. On "split I/D" executables on the PDP-11, data address 0 contains a zero explicitly put there for that purpose in crt0.s - in my test program, this was followed immediately by character data for the string literals I used with printf. (As has been pointed out, this could be at any address, not necessarily 0.)

3

As we know, in C to dereference a null pointer is undefined behaviour.

It is now, but the PDP-11 was an obsolete architecture before the first standard C was published. At the time when the PDP-11was current hardware, the only thing close to a standard was The C Programming Language by Kernighan and Ritchie (henceforth referred to as K&R).

The null pointer wasn't a formal a concept back then and pointers were generally considered to be interchangeable with ints although that wasn't always the case (a primary source of pain for portability). A pointer whose value was 0 was considered special and there was a macro NULL whose definition was something like ((char *) 0). Note that K&R C has no void type.

Dereferencing a null pointer is only designated as undefined behaviour so that the compiler doesn't have add a check to every dereference to make sure the pointer is not null. It's perfectly acceptable for your architecture to have that work as with any other address. In fact, if your program crashes with a SIGSEGV when you dereference a null pointer, it is not because the compiler put a check in but because your operating system has made it illegal for user space programs to access the location.

So an operating system writer could set up the PDP-11 trap vector table in C as long as he is confident that the compiler will treat address 0 like any other. Since, in early versions of Unix the OS team and the compiler team overlapped, this was obviously not an issue.

So my question is what led some C standard to treat the NULL pointer differently from any other pointer? Did K&R want to target an exotic architecture or something?

No. The C standard came a decade after C and Unix were written. By this time it was obvious that null pointers were causing issues.

Edit

OK, so I had a look at my copy of The C Programming Language (first edition) and it turns out that I was wrong. On page 97 we have (in relation to implementing a custom allocator)

C guarantees that no pointer that validly points at data will contain zero, so a return value of zero can be used to signify an abnormal event.

On page 190

A pointer may be compared to an integer but the result is machine dependent unless the integer is the constant 0. A pointer to which 0 has been assigned is guaranteed not to point to any object, and will appear to be equal to 0; in conventional usage, such a pointer is considered to be null.

[my emphasis]

Setting up an interrupt table for an operating system would not be considered conventional usage.

1

C treats NULL differently because it is undefined behaviour.

Undefined behaviour is very different to implementation defined behaviour. Implementation-defined behaviour can simplify portability by allowing different implementations to make different choices (for example, different platforms have different native integer representations).

Undefined behaviour is only partly related to portability - there's no requirement that undefined behaviour be consistent, even on the same platform (so even if C had only targetted a single platform, it may still have included undefined behaviour). In addition to the portability gains, undefined behaviour allows implementations to emit simpler or faster code, by making error handling optional for certain error conditions. To quote the C rationale document (copied from here):

The terms unspecified behavior, undefined behavior, and implementation-defined behavior are used to categorize the result of writing programs whose properties the Standard does not, or cannot, completely describe. The goal of adopting this categorization is to allow a certain variety among implementations which permits quality of implementation to be an active force in the marketplace as well as to allow certain popular extensions, without removing the cachet of conformance to the Standard. Appendix F to the Standard catalogs those behaviors which fall into one of these three categories.

Unspecified behavior gives the implementor some latitude in translating programs. This latitude does not extend as far as failing to translate the program.

Undefined behavior gives the implementor license not to catch certain program errors that are difficult to diagnose. It also identifies areas of possible conforming language extension: the implementor may augment the language by providing a definition of the officially undefined behavior.

Implementation-defined behavior gives an implementor the freedom to choose the appropriate approach, but requires that this choice be explained to the user. Behaviors designated as implementation-defined are generally those in which a user could make meaningful coding decisions based on the implementation definition. Implementors should bear in mind this criterion when deciding how extensive an implementation definition ought to be. As with unspecified behavior, simply failing to translate the source containing the implementation-defined behavior is not an adequate response.

  • The intended purpose was portability and efficiency of "straightforward" code. The authors of the C89 Rationale clearly intended that an expression like (ushort1 * ushort2) & 0xFFFF consistently yield the lower 16 bits of the result on modern implementations (they cite the behavior of "most current implementations" in such cases as part of the reason for making unsigned short promote to int when the latter is a larger type). I've seen no evidence that the authors of the Standard intended to invite compilers to assume that ushort1 <= 2147483647/ushort2 in such cases. – supercat Feb 7 '18 at 15:43
  • I've updated my commentary to be closer to the meaning of the rationale document. You're right that aggressive compiler optimisation is a relatively recent development, and it was misleading to suggest it's what the authors intended. Do you reckon I should strip the answer back to just the rationale document? Including that was my main aim anyway. – James_pic Feb 8 '18 at 20:38
  • I think it may be worthwhile to mention that the rationale identifies some typical ways implementations may act in cases where the Standard imposes no requirements; it does not offer any guidance as to when quality implementations should seek to behave in the manners described. On some implementations, an attempted null access would access whatever happened to be at address zero (which might on a few occasions be useful, e.g. if 8086 code needs to set the divide-by-zero interrupt vector which is located there). On others, it would trap. Today, it may negate laws of time and causality. – supercat Feb 15 '18 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.