10 ms·
Null References: The Billion Dollar Mistake (2009) [video]
- brundolf 4y ago(2009)
- dang 4y agoAdded. Thanks!
- WalterBright 4y agoNah. The billion dollar mistake is actually C arrays decaying to pointers, enabling buffer overflows, the #1 cause of bugs and malware injection in shipped C programs. https://www.digitalmars.com/articles/C-biggest-mistake.html https://www.digitalmars.com/articles/C-biggest-mistake.html It's simple to fix this in C, too.
- LanceH 4y agoWhich would all be a rounding area if C gets to take credit for everything produced using it.
- asguy 4y agoThis is what C/C++ haters, anti x86/amd64 snobs, and Rust elitists always forget: what works, works. Sure, it could be a local maximum, hopefully there will be better, but who knows? To quote Sean Connery in The Rock: Losers always whine about their best. Winners go home and fuck the prom queen! https://m.youtube.com/watch?v=gXDSxgDUv-c https://m.youtube.com/watch?v=gXDSxgDUv-c
- pjmlp 4y agoSome of us are old enough to be coding when C was only relevant for university departments privileged to have UNIX boxes. So we know there are other ways, we used systems with zero lines of C into them. The prom queen came naked offering herself to everyone and the party was done for the other folks.
- asguy 4y agoThat excuse sounds like the guy in highschool who would have treated the girl so much better, but she was into assholes. If you are old enough to remember those days, then you remember COBOL, Algol, Fortran, Pascal, BASIC, Ada, Oberon, Lisp/Scheme, Forth, O’Caml etc. They’re all great languages, some still have their uses. There’s a reason all of the major operating systems have cores written in C/C++. It’s entirely because they’re pragmatic and “work”, and not some conspiracy. Edit: although now that I write it, what if C/C++ was planted on earth by an alien intelligence in order to slow down the development of the human race.
- pjmlp 4y agoThe power of free beer with source tapes is very mighty. Thankfully governments have finally start paying attention regarding software liability.
- WalterBright 4y ago> Thankfully governments have finally start paying attention regarding software liability. And we'll see a great slowdown in the software industry.
- pjmlp 4y agoWhen people buy damaged goods, they ask for a refund, they don't expect to close and reopen the box and have the product reappear in perfect shape. The industry has miseducated them, and now it is finally happening, software products aren't a special snowflake. Digital stores with returns, consulting contracts with warranty clauses with fixes at the expense of provider, and naturally cyber security bills. Move fast and break things only works due to lack of liability.
- nickpp 4y agoA strong, competitive free market naturally selects what people value the most. Because there is no black and white - most decisions are tradeoffs between cost, difficulty, time, convenience, safety, functionality, and so on. Government regulations practically place an infinity price on selected characteristics. The result is less entrants in the market, less competition and naturally worse results across all parameters.
- Oxidation 4y agoIt doesn't even have to be a local maximum, just higher up some hillside will do (maybe it's even on a different hillside to the one you're on at the moment).
- mariosisters 4y agoNailed it with this quote, especially because it scales to all levels of product development. Literally the only thing that matters (in the context of business success, of course) is if it works enough to keep going up and the the right. No one cares about your code.
- rcoveson 4y ago> ...is if it works enough to keep going up and the the right. Right, because that's a one-bit truth value, not a scalar. The slope doesn't matter, it just has to be positive. Everything is so simple! There's no such thing as high margins, or success in degrees. Is there something adding friction to the process of making software/food/cars? Well, is it adding enough friction to make our profits go negative? No? Then literally no one cares.
- mariosisters 4y agoThe one bit value of growing vs not is the primary determinant of success (in this industry), yes. I’m not making a lifestyle biz.
- rcoveson 4y agoWith your philosophy that literally reduces engineering to “does it make any profit at all true or false”, I would hope that you would confine yourself to the lifestyle industry.
- kilgnad 4y agoCode matters, it's hidden technical debt that bites you in the ass later, kind of like contracting HIV. Guess where I'm taking that prom queen analogy
- bitwize 4y agoJohn Ousterhout put it like: Not working to working is the biggest performance improvement. No misogyny needed.
- kilgnad 4y agoThe prom queen fucked the only thing that was available. Nowadays the prom queen has tinder, loads of competing options and is woke.
- HWR_14 4y agoUnless you went to a very small school, the prom queen always had lots of options. That's the point of the quote. Tinder is irrelevant. The winners are the people who eventually she chooses. As for "is woke", I have no idea how to read that point.
- kilgnad 4y ago>Unless you went to a very small school, the prom queen always had lots of options. No, C was really the only available systems options. C and C++. >Tinder is irrelevant. The winners are the people who eventually she chooses. In the dating market today, tinder has created essentially a shit show for males. With that much choice and selection female hypegamy becomes expressed to the max. The top 80% of the top females match with the top 20% of males; It has never been this way for most of humanity. Even the top female always had a limited pool to choose from and her feelings would naturally calibrate to that fact. With tinder everything changed. You get the top tier males having a lot of fun and never settling down, while the rest just give up. That's hook up culture for you. C would NEVER have been chosen if there were more options. >As for "is woke", I have no idea how to read that point. It's the same thing. Wokeness is the result of more womens' rights. Historically, all women couldn't be as selective as they are now because they couldn't hunt for food or work corporate jobs. Survival depended on them finding a man. This is no longer the case and is responsible for much greater female selectivity. Again C succeeded because of very few alternative options and necessity. Anyway I can see why you or other people missed the analogy. You have to be familiar with the modern dating game AND familiar with what programming was like 20-30 years ago. Most people capable of even making the comparison have been out of the game for ages. The state of programming languages that are chosen today is very very much like the hookup culture of today. Especially on the front end, the front end is a woke prom queen for sure.
- deleted 4y ago
- bitwize 4y ago1) Connery's character's attempt to out-chad Cage's character failed because the latter replied: "Carla was the prom queen." 2) The proportion of prom queen fuckers among systems programming experts is probably much lower than among the general population. 3) The real Unix philosophy is a perverse form of "worse is better", i.e., it prefers making it easy to slap together something that kinda sorta works without worrying about "edge cases" that people are likely to run into, over crafting a reasonably complete, responsible solution. C is the result of this philosophy applied to language design. If it hadn't been for Unix becoming ubiquitous, we wouldn't have made that disastrous choice. (Come to think of it, under this rubric, Electron is a Unix philosophy exemplar.)
- asguy 4y ago> 1) Connery's character's attempt to out-chad Cage's character failed because the latter replied: "Carla was the prom queen." Your calibration is off: he wasn’t trying to put-Chad him.. he was telling him to “git gud”
- renox 4y agoWhile I agree with you. It's still infuriating that these (serious) flaws in C apparently can't be fixed/evolved inside the language and that instead you have to use a different language instead.. That's throwing the baby with the bathwater :-(
- saagarjha 4y agoCar crashes are also a rounding error compared to the number of people who get to their destination safely. There's substantial investment in both vehicular safety and program analysis to improve both.
- Mindless2112 4y agoAbsolutely. Null pointers doesn't even make the list of things that I worry about when writing C code.
- dpkirchner 4y agoWe could go further: the billion dollar mistake was allowing values intended to be used as data to be executed (pre-NX bit). Zero-terminated C strings is up there as well.
- GuB-42 4y agoThe code vs data distinction is a hardware thing, this is not about C. More precisely, it is the difference between a Harvard and a Von Neumann architecture. A Harvard architecture has completely separate paths between instructions and data: different buses, different memories. A Von Neumann architecture has common instruction and data paths, and therefore, naturally, data is executable. You can write C code for both. Modern PC-style hardware is kind of a hybrid, acts like Harvard with regard to cache, and like Von Neumann with regard to RAM. Furthermore, it has a fancy MMU that allows for things like the NX bit. All C compilers/linkers I am aware of know the difference between code and data and are able to put each one in the appropriate section, what is done after that is the OS/hardware responsibility. As for zero-terminated strings, I also think it is mostly a mistake, though it does have a few advantages. You can still work with size+pointer though, using mem- instead of the str- functions, and "%.*s" in printf(), not ideal though.
- renox 4y ago> Zero-terminated C strings is up there as well. I disagree here, remember that at the time some strings with length implementations used only one or two bytes for the length, this can creates lots of issues that zero terminated strings don't have. Of course nowadays zero terminated strings don't make sense anymore.
- mjevans 4y agoI think golang's slices are a better solution than the linked article. https://go.dev/ref/spec#Slice_types https://go.dev/ref/spec#Slice_types Slices can still be nil (null), but it isn't an unsafe memory access operation, just another type of potentially useful or potentially errant invocation to handle.
- josephg 4y agoZig and Rust also support array slices. But they can’t be null, because that’s - as the article says - a mistake. https://ziglang.org/documentation/master/#Slices https://ziglang.org/documentation/master/#Slices https://doc.rust-lang.org/book/ch04-03-slices.html https://doc.rust-lang.org/book/ch04-03-slices.html
- WalterBright 4y agoD slices can be null, but they're not a mistake, as the runtime will not let you read/write a 0 length array.
- saagarjha 4y agoWhat's the relation between a null slice and a 0-length array?
- WalterBright 4y agoNeither can be successfully indexed.
- feffe 4y agoPerhaps this is similar to how they work in go? "var x []int; fmt.Printf(`%p %d`, x, len(x))" outputs "0x0 0" Indexing "x[0]" results in: "panic: runtime error: index out of range [0] with length 0" They can also be appended to and then produce a valid slice.
- pjmlp 4y agoOther languages avoid the mistake by preventing direct access unless either there is a null check or they are declared as non nullable.
- convolvatron 4y agoI think this is actually an artifact of the 'check the single return value for errors' that requires that the return domain contain at least one error code point. how else you might structure errors without changing much of the rest of C left for an exercise
- amenghra 4y agojust require the programmer to check errno after every function call? /s
- convolvatron 4y agoomg. I forgot about that. the one thing even worse than overloading the return domain.
- kilgnad 4y agoBit my company in the ass recently we uncovered a bug that was causing us to lose 20% of our data for a year. sqlite C libraries apparently still do this. The person who wrote the code was both not very good and had no idea that an error was even occuring.
- Gibbon1 4y agoStrange but true you can create functions where you pass a pointer to an error variable. error_t oops; int x = foo(10, &oops); if(oops) goto whoops; int x = foo(10, 0); // yolo!
- marcodiego 4y agoGenuinely curious: why don't suggest that to WG14? (WG14) is the ISO workgroup which maintains the C specification.
- Arch-TK 4y agoAnd what would it achieve to "fix" this (without re-designing the rest of the language)? Every piece of code such as: int a[SIZE]; foo(a, SIZE); Would have to be rewritten to: int a[SIZE]; foo(&a[0], SIZE); And this additional noise would just make C harder to write for no reason. Rather than making C harder to write, just pick a different programming language.
- WalterBright 4y agoThe article I referenced says how this is fixed. It is not harder to write at all.
- Arch-TK 4y agoAdding fat pointers to C is a major redesign and the fact that the explanation fits within a short blog post doesn't make it an easy fix. If you don't add fat pointers (thereby requiring a major re-design of the language and causing an endless amount of pain with regards to ABIs etc) then the solution, which involves removing the implicit conversion of an array to a pointer to its first element in expressions where it is not used as an operand of the sizeof operator, unary & operator or as a string literal used to initialise an array, certainly DOES make it harder to write C.
- WalterBright 4y ago> Adding fat pointers to C is a major redesign No, it isn't. I implemented it in D, and know what is involved. I've written two C compilers, as well. > the fact that the explanation fits within a short blog post doesn't make it an easy fix. Correct, but since I've actually done it, I'm in a good position to say it is an easy fix.
- nicoburns 4y agoThey're probably BOTH quite literally billion dollars mistakes.
- WalterBright 4y agoI remember the bad old DOS days where a null pointer write would scramble DOS. I absolutely hated that, and it cost me a lot of extra work. Enter protected mode programming. It was a miracle! Null pointer writes now meant a seg fault with a traceback, and voila! A few minutes of fix and I'm on my way. I immediately switched all my dev work to a protected mode system, and ported to real mode only as a last step. Buffer overflows are the primary entry point for malware. Seg faults are not. Hence the former are far more costly.
- unxdfa 4y agoI can confirm I have fucked up on numerous occasions which resulted in NPEs which caused business processes to fail spectacularly and write off millions of dollars instantly. Fortunately in every case it was possible to recover, replay or repair the data so the only real cost was a little bit of reputation and time and money. But that adds up across tens of thousands of engineers, probably to billions by now globally. I learned a lot from this and discovered that the real issue is that a process can fail spectacularly and do any damage at all. There are so many other concerns other than NPEs which need to be considered.
- imoverclocked 4y ago> There are so many other concerns other than NPEs which need to be considered. Yes. However, not all of those are trivially avoidable by just slightly changing the tech underneath. I chose a battle with NPEs in a giant Java codebase and largely won. It wasn't trivial to do but the main take-away is that in order for Java to be backward compatible, javac can't enforce any mechanism to make a codebase consistent enough to be NPE free. One way to get this consistency is to change the semantics slightly to trace nulls accurately (some JVM languages attempt this and fail with 3rd party dependencies for eg) and enforce that you can't write code that will produce an NPE. There is even an errorprone plugin that does a pretty good (though not perfect) job of this called NullAway. For codebases that think they can do better and that "need" more flexibility in null handling, there are other frameworks. I'm hard-pressed to meet that need outside of legacy/untouchable code constraints.
- live_video 4y agothe choice of von neumann architecture over harvard architecture enabled this
- munchler 4y agoThat’s a problem that’s pretty much limited to C. Null pointers have infected many other languages as well.
- Arch-TK 4y agoNothing is decaying. It is an implicit conversion. To say something "decays" implies something else is lost, the array is still there.
- WalterBright 4y agoSomething is lost - the array length. "Decays" is the correct word.
- Arch-TK 4y agoIt is not correct. The array length is still there, what is happening is that you are implicitly asking for only a pointer to the first element of the array because of the context in which it is used. You did not ask for its length. The language has no way of passing an array itself by value. You could have asked for a pointer to the whole array but you didn't. When you are using an array in the context in which it is not an operand of the sizeof operator, the unary & operator, and not as a string literal used to initialise an array, then the expression which forms the use of the array involves an implicit conversion which produces a pointer to its first element. You might think it's pedantic, but we're talking about C, it is important to be clear in language used to talk about C as it's an unforgiving language. There is an untold amount of confusion surrounding how arrays work in C at least in part because of silly wording like "decay". As a final note: When you write "f(foo.bar)" to call "f" while referring only to the "bar" field of the struct "foo" you are not losing "foo" and it is not "decaying" solely because the function which receives the result of the expression which formed the first argument of its invocation only sees the "bar" field of "foo". And now I'm not saying that it's a conversion either, but the point still stands. If "f(a)" where "a" is an array involves decay then so does array indexing or accessing a struct field.
- WalterBright 4y ago> The array length is still there If it was, we wouldn't be having this discussion and array bounds checking would have been added to C compilers 40 years ago.
- xjay 4y agoNot to forget that classic increment of a signed integer waiting to overflow and trigger an exception on some critical (unpatched) hard disk drive controller out there.. ++countdown;
- slaymaker1907 4y agoI don't think it's quite so simple to fix since you still need to decide when to actually check the size vs. when it is safe to omit. While branch predictors are great, you can end up having so many potential branches that it starts to lose effectiveness. In practice, I rarely see anything besides strings that lack the size variable, it's just that the bounds may not be checked. Null terminated strings were a horrible mistake though and really should have been fat pointers.
- MichaelMoser123 4y agoThey didn't like to pass around the dimension of the array with the argument value. That got them a few bytes at the cost of a billion dollars. That's the same kind of trade off as with zero as end of string marker. On the other side: the platform might not have received any following without saving a few bytes here and there, computer memory was a scarce resource at the time.
- yakubin 4y agoThat also means that making substrings requires both additional memory and time. Penny wise, dollar stupid. Not to mention the cycles wasted on recomputing strlen().
- _kst_ 4y agoYour proposed fix in [the article](https://www.digitalmars.com/articles/C-biggest-mistake.html https://www.digitalmars.com/articles/C-biggest-mistake.html) is to add a new function declaration syntax: void foo(char a[..]); that causes an array argument to be passed as a "fat pointer", consisting of a pointer to the initial element of the array plus a `size_t` value for the array dimension. Tentatively, I like the idea. As you acknowledge, this wouldn't fix existing code, but writing new code to use this new feature doesn't look difficult. (But converting all existing C code would take approximately forever.) How does the function access the dimension? Is there a new syntax for extracting the length from a fat pointer, or do you just propose extending the semantics of `sizeof`? Is there an existing C compiler that implements this? A minor question: Given the above declaration, would char c = '?'; foo(&c); be valid, treating `c` as a single-element array? Finally, a very minor point: `...` is already a valid punctuator. I can't think of any ambiguities that would be introduced by adding `..` as a new symbol, but that might be just my lack of imagination. (Note that gcc uses `...` in its case range extension.)
- tadfisher 4y agoI would go all-in and make arrays a distinct type, so the only way to create an array is with the [..] syntax, and forbid implicit type compatibility between arrays and pointers (which would discard the dimension part of the array type). An explicit conversion (cast) from pointer-to-array should require the dimension as part of the type. So &c on a char should produce char, and &c on a char[20] should produce char[20].
- tylerhou 4y agoWhy not standardize something like std::span in C?
- pjmlp 4y agoLack of willigness.
- _kst_ 4y agoArrays are already distinct types. char c; &c; // type is char* char arr[20]; &arr; // type is char (*p)[20], pointer to array of 20 char (A small quibble: the term "type compatibility" in C doesn't mean implicit convertibility. Two types are compatible if they're literally the same type, and in just a few other cases. You can assign an int value to a long object, but int and long are not compatible, even if they happen to be the same size.) The problem with dropping implicit array-to-pointer conversion is that it would break most existing C code. It would be a great idea for a new language. Suggested reading: Section 6 of the comp.lang.c FAQ, <https://www.c-faq.com/ https://www.c-faq.com/>. The relationship between arrays and pointers in C is admittedly confusing; this is the best resource I know of for explaining it.
- _8j50 4y agoHate to break it to you but buffer overflows don't need arrays, for stack at least, regardless of how arrays are constructed, the ability to predictably overwrite the saved IP is all you need. X86 restricting saved IP read/write on the stack to special instructions like call or ret would have been nice (mark stack memory as restricted when call saves eip for example$
- vippy 4y ago[flagged]
- dang 4y agoCould you please stop posting unsubstantive comments? You've unfortunately done that repeatedly, and we're trying for something else here. Fortunately you've also posted good comments, so this should be easy to fix. If you wouldn't mind reviewing https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html and taking the intended spirit of the site more to heart, we'd be grateful.
- petilon 4y agoIf null references are a mistake, isn't initializing an array index variable to -1 a mistake too?
- itronitron 4y agoYes, I suppose null references are only a problem if you are unable to write a conditional statement.
- josephg 4y agoThe problem with null references is you have to write those conditional statements everywhere, otherwise your program might crash. You generally know as the programmer which pointers you expect to be nullable and which should always be an object. But the compiler has no idea, so it can’t help make sure you have null checks in all the places you need them.
- GoblinSlayer 4y agoAnd what to do if null check fails? Call abort()?
- tadfisher 4y agonull references are a problem when: - null is a valid member of every type - there's no way to constrain a reference to only non-null members of the referenced type - the compiler allows dereferencing values of a nullable type Weirdly, all three are true of C, C++ and Java.
- GoblinSlayer 4y agoNull is a valid member of every type only in Java. C and C++ have value types.
- lmm 4y agoYes. Make illegal states unrepresentable.
- revskill 4y agoThe compiler should check for null reference before deferencing here.
- josephg 4y agoWhy? So the program can crash? It’ll usually crash anyway when you read from the first memory page.
- Arch-TK 4y agoAt the cost of basically all performance or incredible compiler complexity. A better solution: Implement a different language with a better type system instead. Or pick one of the hundreds that already exist and can represent the concept of a tagged union without having to implement it manually.
- pjmlp 4y agoAs proven by languages like Eiffel or Kotlin, it is quite alright.
- kaba0 4y agoI am absolutely in favor of languages that exclude nulls from their type systems, bur your first point is a very simplictic take. Null pointer checks are very, very cheap, no additional memory fetch since the pointer value is needed either way, easy to predict the slow path and if we are talking about languages that can deoptimize, then it is literally free (checked by hardware either way) -> a null value will cause a segfault, which will deoptimize the code on the slow path and continue from there. So it is not a problem from a performance point of view.
- Arch-TK 4y agoWhen you're talking about a language which people treat like a portable assembly language, yes it IS expensive. It may be cheap from the point of view of a higher level language where literally every operation is already expensive, but from the point of view of C this would be a killer. You are talking about a language in which people work to reduce the number of indirections, fiddle about with struct layout to optimise for cache line alignment and spend days trying to squeeze out performance by passing structs directly instead of pointers to the structs. Yes, the NULL check (effectively, in most cases) happens via hardware either way, but it's a lot cheaper to have the MMU raise a page fault because you tried to read/write an unmapped page than it is to litter every pointer access (or at least every initial non-volatile pointer access) with a conditional jump. I have no problem with someone adding compiler flags to enable slightly optimised NULL checking across every pointer access but I guarantee nobody will enable it for any code written in C for a reason as it will kill performance. Consider the instruction cache impact. You're also way over-estimating the branch predictor. Yes in hot code you will not see a major impact, but this is not something the kind of people who write high performance C really bet on anyway. And don't bring up __builtin_expect and friends, they don't do anything on AMD64, one of the most popular architectures in the world. Now for software which is written in C for no good reason, there's a perfectly sensible target for this feature.
- pjmlp 4y agoBesides the approach taken by some FP languages, others like Eiffel already fixed it in the 1990's, while having nullable types, by making it a compiler error to access reference types without checking for null, unless the types are declared a non nullable. So it just took some time to get mainstream.
- noogle 4y agoSounds similar to Kotlin's and TypeScript's approach. The basic issue exists - how to handle unknown values. It goes beyond programming language constructs.
- deleted 4y ago[deleted]
- dang 4y agoRelated: Tony Hoare's Null References: The Billion Dollar Mistake - https://news.ycombinator.com/item?id=30719472 https://news.ycombinator.com/item?id=30719472 - March 2022 (13 comments) Null References: The Billion Dollar Mistake - https://news.ycombinator.com/item?id=22019627 https://news.ycombinator.com/item?id=22019627 - Jan 2020 (150 comments) Null References: The Billion Dollar Mistake – Tony Hoare (2009) [video] - https://news.ycombinator.com/item?id=11798518 https://news.ycombinator.com/item?id=11798518 - May 2016 (79 comments) Tony Hoare / Historically Bad Ideas: "Null References: The Billion Dollar Mistake" - https://news.ycombinator.com/item?id=473158 https://news.ycombinator.com/item?id=473158 - Feb 2009 (2 comments)
- mkoubaa 4y agoI have a hard time taking this seriously. The alternative to null pointers isn't no null pointers, it's programmers hand rolling their own conventions around optional pointers, and it would have been a nightmare ( at least in C)
- dzdt 4y agoIn older C and C++ code by convention the meaning of the pointer object was what we would now call Option(Pointer) : it can either be a valid pointer or can be null. Both are correct, and correct code should handle both cases. The mistake was in not providing any language features to enforce or support that convention, or to communicate when the pointer is guaranteed to be valid vs when the null option needs to be handled. Having an optional type as the language default is fine and sensible but could really have used aome language support to make it less of a footgun.
- berjin 4y agoGolang has to be the worst language for this problem considering it's young age. It was launched the same year at this post so it would have been a great opportunity back then to deal with the problem in a fresh language without needing to worry about compatibility constraints. It also doesn't have any ?. operator to elegantly deal with the problem. I know fast compilation and explicitness are the goals with go but I think this was a mistake.
- yarg 4y agoWe keep going on about this as if it's in any way different from every other situation where we've benefited significantly from an abstraction from the underlying machine. But reflecting the underlying machine was not just a completely reasonable default it was the most viable performant option at the time. And provided a clean enough means for writing cross platform compilers for more abstracted languages. We probably took too long coming up with validated optionals as an abstraction, but so much is obvious in retrospect. There is a lot that can be done, that must be done, but should only be done rarely - but the powers provided by a language that reflects the underlying machine are vital nonetheless. You shouldn't be writing goto on a daily basis, but it's very useful for custom loop definitions.