I'm not sure why the article removed comments from the code and replaced variable names like "indirect" with "p". Here are the two code samples verbatim from Linus's presentation:
remove_list_entry(entry)
{
prev = NULL;
walk = head;
// Walk the list
while (walk != entry) {
prev = walk;
walk = walk->next;
}
// Remove the entry by updating the
// head or the previous entry
if (!prev)
head = entry->next;
else
prev->next = entry->next;
}
remove_list_entry(entry)
{
// The "indirect" pointer points to the
// *address* of the thing we'll update
indirect = &head;
// Walk the list, looking for the thing that
// points to the entry we want to remove
while ((*indirect) != entry)
indirect = &(*indirect)->next;
// .. and just remove it
*indirect = entry->next;
}
I can't help but notice how this code, as well as in the article, there's no checks for a) a NULL list or b) that the item is in fact part of the list. A simple fix is:
while (!!walk && walk != entry) {
prev = walk;
walk = walk->next;
}
...because without those checks it's pretty easy to see where you'll crash... but by putting in those checks, perhaps the second method might actually be less 'elegant'.
Edit: did I miss something? Re-checking this, the second method will still crash if/when next is NULL (because you can't get the address of NULL), which means the 'elegant' seems to be a quagmire of lurking faults.
That code is not a general purpose library function; it assumes the element exists.
If you call that method and the element doesn't exist, presumably something has gone wrong already. Adding a NULL pointer check is not going to fix it. You just silently ignore the error. You'll prevent the crash, but there's no mechanism for handling the error.
And instead of adding a check and crashing visibly here you wait even longer until your program misbehaves due to the error? The longer the program runs after something went wrong, the harder it is to debug, and the more likely it becomes that you get an exploitable bug.
Where you add safety checks like that is a top-down system organization issue, not something you can couch quarterback while looking at twelve lines from a million-line codebase. There is simply no way to determine if an assert is appropriate without further context, and it has nothing to do with the choice of algorithm.
NULL being passed in is not the only problem. Dangling pointers, coding mistakes by other team members and race conditions during initialisation can all contribute to this blowing up. Some argue (correctly) that it's best to have it blow up, other that assertions are the way to go. I'm of the latter ideology. Make your debug build do assertions, but release code be crash proof by doing NULL checks.
There are several comments indicating the performance cost of a NULL check. Go and look at the disassembler and see the code. You should find that it equates to JZ, which at worst case costs 1 clock cycle. Am I incorrect?
So, another comment below mentioned 10 million deletions per second. Ignoring the fact that you should be using a double linked list at that point (like the kernel does), in a single threaded 2.4GHz CPU a 1 step opcode (JZ) equates to a bit over 4ms/sec. With branch prediction, I expect to be far less.
So, the NULL check is almost free. Even on embedded systems, it'd still be a good idea to keep it in, to insulate yourself from flipped bits (eg, solar flares, or degrading memory) and coding mistakes elsewhere.
In these days of security research, I strongly advise for defensive code: it means that each function has had it's edge cases thought about, which means the developer has spent time thinking about the stability of their program, which cannot be a bad thing. Don't make your code a deliberate point of exploitation.
This makes a big assumption that the null check, which is the result of a programmer error, can be recovered. What would you do once you catch the null? Log that there was a null, maybe with some debug information, then halt? I personally would prefer a proper crash handler to do all of that for me.
I guess my question is, what's wrong with crashing, in the case of a real screwup, where something has gone horrible wrong, assuming you have a proper crash handler?
it's one instruction in the generated code and we can reasonably expect the branch predictor to do the right thing, but branches and error handling can inhibit vectorization which is a much higher performance cost. While in this particular case you probably aren't vectorizing much, it is not always the case that error handling is almost free
If the null check silently ignores the attempt to remove a non-existent item from the list, then the null check did not prevent a bug, it merely hid it.
IMO, even though this is C, the Zen of Python still applies, which states:
> Errors should never pass silently unless explicitly silenced.
Its the caller with the bug, not the library code.
Can we all at least agree that if the language could express non-nullable pointers, we'd all be better off? (Something like `Option<T>` in Rust, or Swift's `?` sugar for their `Optional`, etc etc)
Then the type of the function would just declare a that the pointer can't be null, and code which sends a nullable pointer would refuse to compile.
I would argue that if you have code that is trying to remove a non-existent item from a list, then making it silently fail is only giving the appearance of making it work.
It's definitely not right, while probably not really working either. The immaterial performance gain from removing the null check is completely irrelevant.
It's a foot-gun for sure, but it's up to you to not pull the trigger.
I'm arguing that we should use asserts or similar defensive coding mechanisms to ensure that preconditions are met instead of merrily continuing to run our program with cascading error effects.
I've had this argument a ton with people used to new high level languages that make null safety "too easy" like:
next?.doThing()
Where doThing is never called if next is null.
Languages that do this use "scary" operators to crash on null:
next!!.doThing()
And it's drilled into people's heads the latter is a Bad Thing (tm)
-
You really need to consider context in null handling.
Imagine an app that alerts a nurse when the patients heartbeat is out of range.
In an application where the UI context might have been closed out, it's common to see
someUiContext?.showAlert()
But what actually happens if the context is gone?
It's better to crash and have part of your startup procedure be communicating that a crash occurred, and the doctor should check that something went wrong, than silently continuing.
-
The problem is when you tell people this, the kneejerk reaction is always "are you saying we intentionally add crashes"!
Because safe null handling was specifically added to avoid the situation where that crashes...
(For example, if the app was a news reader and the alert was "Article failed to load", you wouldn't want the app to crash just because the user left a certain page before the alert was shown)
But I think the pendulum has swung too far at this point, people are so used to just sweeping nulls under the rug, and it's not great for finding issues
Yes - and that is the point the OP you responded to is making. This is not a generic library function. It used in a specific setting where preconditions exist and presumably are checked _prior_ to calling this code.
Sure you could make the argument that we don't _know_ they are being checked, but it's a pointless discussion. Who cares? _If_ preconditions are met, this code is safe, if they aren't, it's not safe. Since we don't know one way or the other, there's no point in discussing further. The kernel developers know their stuff...
It's a bad idea, especially in kernel/low-level/performant code. It's OK to check some values at specific points (like when a value is passed from user space), but in general it's bad practice to check it at every single function. You trust in your program flow.
Imagine if at every function down a complex stack you go with:
This is nice in theory but a bad idea in practice (as a blanket statement, I am all for checking preconditions in general). An easy example is binary search, which I think is a reasonable "piece" of code by your definition. One should never check its preconditions _inside_ the binary search function (that the list of elements being searched is partitioned by the search predicate). Checking the precondition is O(n) while the algorithm is O(lg n).
The thing is that you aren’t really advocating for just that... Since this is pretty general support library code, the result of this philosophy is defensive checks in all support functions and that means checks every spinlock, mutex/semaphore, and god knows how many other places... everything really. We also would want these checks at multiple levels since we shouldn’t trust that other people checked things. This would have a significant effect on performance and many would prefer their system not to run however-many percent slower. All to avoid a possible issue that can’t be very large or systems would be kernel panic’ing all over the place.
From a black box, zero-knowledge, perspective it’s maybe worth remembering that code built this way successfully runs mission critical systems all over the world every day. Thoughtful people would have switched to other (slower, more pedantic) systems if doing things differently was a real overall life improvement. People have had the choice, there are plenty of OS’s out there... some far more formal/pedantic. Linux wasn’t the safe choice back in the day, it was just better by several important metrics consistently over time.
Perhaps these insanely experienced kernel devs know what they are doing.
This isn't possible in many cases - consider the simple C library function strlen, one of who's preconditions is that it must only be called on a zero-terminated string. There is no way to write code in strlen to check that this is true.
Which is one of the reasons why coding standards like MISRA forbid using strlen (at least in C++, I guess even MISRA doesn't want to force you to write safer C with sane string types).
Asserts have run-time cost. What you need is to ensure ensure those preconditions are met in the first place, statically, by formal methods for example.
It’s not a bug, in this case. It depends on the behaviour the library is specified to handle, but if you ask me to remove a specific item from a list, and that item isn’t in the list, what should I do?
I can fail so you can catch it, or if you don’t catch it, you’ll at least see exactly what went wrong. You expected the item to be in the list and it wasn’t. Your preconditions were wrong from the beginning and you have an (unknown) bug in the code.
The alternative is that I can’t find the item and I silently suck it up and don’t notify you. If that’s the api we’ve all agreed on, that’s fine. It was on you to check for the thing in the list first and then remove it. But it’s a bit weird if you think about it - now you need to traverse the list twice. Once to check for the existence (and fail out yourself) and once to remove.
I think a better approach is to return a bool or something like that, rather than crashing. But I agree that silently handling this case is the worst of the options.
Clearly you've never worked with contract developers whose only purpose is to write a crap ton of code to get a "feature" out that crashes as soon as it encounters the real world. As they say, "doveryay, no proveryay" and it's served me well.
Then it ought to document that it assumes that entry exists and that this walk will not hit the end of the list. Which also implies the list is not empty.
It should, yeah, but if it can safely assume there will be no nulls, it will save a nontrivial amount of defensive programming checks for each cycle. And IIRC, the Linux kernel uses tons of linked lists, millions of items per second sometimes; any operation that can be removed will make a big impact. Relatively.
But for general purpose code, e.g. libraries where performance isn't super important but stability is, more defensive programming would be a thing to do.
I believe the implicit requirement is that the item is known to exist within the list. With that requirement in place the extra guards aren't requisite (they're implicit) and in kernel code this probably offers a performance edge and is a reasonable requirement. Either having an implementation that has an extra check once at the end of the list, or that verifies the presence of the item and passes that node through to a deletion subroutine, would be good alternatives but still utilize the same pointer to structure view.
Simply put, safety slows code down. It's a matter of whether you know what's happening underneath or not. The more you try to make C completely safe, the more you slow it down and therefore remove the need to have written it in C in the first place. Whether that's a good thing or not is an exercise for the implementer.
True, but costs of comparison to NULL aren't massive. It is one of the fastest things out there.
It was my experience when tuning a linear algebra library (just for internal use) that such comparisons are almost unobservable in total performance tests.
If you're writing a linear algebra library, then the bulk of executing code should be floating point vector operations in tight loops with known bounds. A NULL pointer check in the prolog where you set up the loop is going to be negligible.
This is very different from kernel code, which by its nature isn't very computational but doing resource management all day long and pretty much all it does is stuff that looks like walking linked lists.
That was a very specific linear algebra, we toyed around with huge but sparse matrices. Not anything graphics-related, rather number theory-related. But there was a lot of integer comparisons in there.
This was around 2001-2002 anyway. Things might have changed.
Depends on how often you are doing the comparison. Is it 1 time/second, or 10 million times a second?
There is a difference.
If the code above is the one in charge of putting/removing network packets in a queue, or putting threads ordered by priority for the scheduler, then you should consider the side effects of checking for NULL.
If you are going to implement this function in a library for Jimmy The Programmer[1], then check for NULL.
It's written in C because C is popular, has platform support and the code was originally written in C, not because the kernel should be a security nightmare.
That's irrelevant to what Linus is saying. He's not saying "this is good code, but only with the caveat that it's written in C and run in the Linux Kernel". He's saying that changing it to make it far more difficult to read and modify, but cleverer, has made it better code in general.
See, and this is where I (and I'm guessing you) might beg to differ. I'm a web developer, so the vast majority of my time is spent working in JavaScript. Our team has been working in ES6 for the past ~2 years. Our lead developer just LOVES him some ES6 - destructuring, aliasing, lambdas, you name it, and he's all-in.
Me, though? Well, let's just put it like this: when we find some framework-level bug that's written in "clever" ES6 syntax, our first step in debugging is almost ALWAYS to rewrite the given function traditionally, without any of the ES6 shorthand. And the reason we do that is because reading and debugging a whole stack of anonymous lambda calls is a PAIN IN THE ASS. Or figuring out where a certain variable is coming from when someone uses overly-complex destructuring syntax to magically pull a value from deep within a nested object.
I mean, don't get me wrong, I do like and use almost all of the modern ES6 niceties, but I also feel like it's much more difficult to parse and understand code compared to what we were all writing a few years back. People will, I'm sure, be arguing about what constitutes "good code" for decades to come, but to me, when working in an evolving codebase, especially with other people, plain ol' human readability is paramount. If people can't figure out what your code is doing without throwing in a breakpoint and stepping through line-by-line, you've failed at writing good code. And this will be my opinion right up until the day humans stop writing code by hand.
This is why Linus' code shouldn't be copied verbatim and used in the real world. The Kernel is an extremely isolated and contained system.
At the very least, the code should add comments on the the assumptions that are vital...otherwise n00bs will copy the code as gospel and run into all sorts of problems.
In C any nonzero value is considered "truthy", and on most architectures NULL is defined to be (void * )(0) or similar. The logical not operator AKA bang operator will replace truthiness with 0, and falsiness with 1. So applying it twice collapses all nonzero values to 1.
I'm not sure about the current state of compiler optimisations, but IIRC in the olde-days, a not not in an if() statement would assemble to JZ, saving a clock cycle (& an opcode?), and wouldn't need to stall to load in the full width of the register.
Today's branch predicting compilers are beyond me.
I still use it as a clarification that it's a deliberate boolean operation, rather than implicit.
I highly doubt that any modern compiler would generate different code with or without the !!. Not even sure why an old compiler would do that? It's the exact same semantics, surely.
Jimmy is a diminutive form of James. It's the sort of thing where parents would call a kid "jimmy" and when they grow up they will ask people to call them "Jim" or "James."
Adding "little" in front just stresses the fact that we are talking about a kid, so the references are about dumbing it down for kids.
Johnny is probably a bit more common than Jimmy, but I've seen both. See e.g. [1]
A 1992 poem Bukowski originally entitled “stone tiger, frozen sea,” was completely reworked with just two lines left unchanged. Its new title: “like a dolphin.”
Normally with an identity-based API like this, you can put it as a requirement that you must not remove items other than those which actually exist in the collection. Another example of an API that doesn't check for presence: c++ iterator-based removal. If you ask a C++ list to remove an iterator element outside its range, it may crash the program. See the exception safety section of this documentation: http://www.cplusplus.com/reference/list/list/erase/ If you look at most "remove this object from yourself" APIs in low-level code, it behaves this way, because it's unnecessarily complex to check for presence when that is a fact the program can condition on instead.
As the other person said, it's not really about complexity. Complexity isn't all that different here; personally I'd find something like the following to be simpler (I imagine others might disagree):
remove_list_entry(entry)
{
for (p = &head; *p; p = &(*p)->next)
{
if (*p == entry)
{
*p = entry->next;
break;
}
}
}
However, what the choice does objectively impact is performance. Being able to assume the object exists allows you to avoid checking against NULL, which removes instructions in the loop. I'd guess they anticipate this code might be called from performance-critical code, and that might be why they coded it like this.
With linked lists, memory latency dominates, since you're chasing pointers all over the heap. I guess the null check costs nothing most of the time. On the other hand, removing random objects from lists that you don't know are actually in those lists is a smell.
Two terms that would not fly in kernel level programming; with kernel programming, low-level libraries, you want both optimized speed and predictability.
Yeah you do - the kernel uses linked lists to store everything from running tasks to memory pages. Insertion and deletion of entries are much faster in a linked list than in an array, and that's a very performance-sensitive operation in the kernel.
> Insertion and deletion of entries are much faster in a linked list than in an array
That's a really broad statement. Arrays can get surprisingly big while being faster. Performance-wise, you'd usually want to use arrays up to a certain size and then link between entire arrays. I'd say the biggest advantage of a standard linked list is that it can be intrusive.
> I'd say the biggest advantage of a standard linked list is that it can be intrusive.
That's one big benefit. I teach operating systems and, when the semester has been good, we dig into physical memory dumps with a few python scripts, and show the students how to parse Windows process list following _EPROCESS structures.
That's one of the big things they find themselves surprised every year: that the process list is a chain of LIST_ENTRY structures embedded within the _EPROCESSes[0] (or any other structure that is doubly-linked in memory). And LIST_ENTRY is just 2 pointers going hand in hand with list_entry->flink and list_entry->blink attributes and nothing more.
[0] You can read some about this structures here https://www.nirsoft.net/kernel_struct/vista/index.html but beware this is based on Vista and a bit old. Kernel data structures vary with versions of the OS (and not even major versions at that) and target processor (x86, x86-64, ARM too would be reasonable).
Unnecessary is not really the correct term, it’s one of a huge number of tradeoffs. The you don’t want it for safety critical systems, but Linux isn’t designed to be used for such things.
Usually variable names in a loop is the object being manipulated not the address of that pointer which means p isn't a pointer to the object which makes it completely confusing.
If the article used pp which is the typical way you describe a pointer to pointer it'd help
// The "indirect" pointer points to the
// *address* of the thing we'll update
The "indirect" pointer points to the thing we'll update. See at the bottom, it's updating *indirect, so "indirect" points to the thing being updated. On the other hand, "indirect" points to the address of the thing we'll remove. There's a specific item being removed, and there's a specific thing that will be updated; the thing being updated comes immediately before the thing being removed; they're not the same thing.
Agreed. The 'indirect pointer' points to the memory address of the previous 'next' (or the head). So, as long as neither are NULL, then dereferencing the pointer is the actual head (or the previous 'next').
> The 'indirect pointer' points to the memory address of the previous 'next' (or the head).
I don't think so. I think the 'indirect pointer' points to the previous 'next' (or the head). It doesn't point to the address of the previous 'next' (or the head). What you say is adding an additional level of indirection that doesn't exist.
Reality:
indirect -> previous next -> first element
What you're saying:
indirect -> address of previous next -> previous next -> first element
In reality indirect contains the address of the previous next, but it doesn't point to the address of the previous next.
> The "thing" is the variable that holds the "entry".
What does "holds" mean? If holds means actually contains the memory, then I don't see the distinction between "thing" and "entry". They both refer to the exact same piece of memory.
This is a circular linked list, where the ->next pointer points back to the head of the list. It's helpful for iteration tasks, since you can always walk the full list when you get access to one node.
In most cases you use a linked list like this, you don't care about the order of things, just that you can iterate over all items in the list.
Question for experienced C programmers (I'm not one). The comments for remove_list_entry strike me as fluff, only suitable for a didactic piece.
Would you find the comments in the second version helpful, or should they also be removed?
Edit: let me lay my cards on the table. If the comments really are necessary, it doesn’t seem elegant. I’m pro-comments, but that’s because not all code can be readable and elegant all the time.
While I wouldn't write this much comment, I can see a use for this: navigation. If I'm trying to quickly find the part I want to modify, the comments do help me skim through quickly and zoom in on the part I care about. It's the same reason a blog post is often broken up into section headings. Without the comments, I'd have to spend a few extra seconds trying to map chunks of the code with my mental model of how linked lists work. Those few seconds can interrupt the flow of work.
So I'll disagree with the notion that only illegible or unreadable code needs comment.
For my tastes there is way too much whitespace and I usually only use multi-line comments to describe the high level algorithm for a full function. I prefer to pepper single-line comments which describe the sequence of events in a human-readable way.
My taste is that function level comments describe the "what" and inline comments describe the "why".
So at a function level the comments is giving a highlevel description to the reader as to the functionality contained, and at the line level comments exist only to say describe the programmers intentionality, why it was implemented this way rather than some other way.
I have generally found (there are always exceptions) that if you find yourself needing "what" comments within a function you should be considering breaking it into smaller pieces.
I've been being paid to write c/c++ for about 25 years
The main takeaway here might be that two 25 year veterans both make function level and line level comments. The particulars are somewhat of a matter of flavor preference :)
The comments certainly don't detract from the code in my opinion. They may not be _helpful_ per se to an experienced developer, but there may be a chance that a more inexperienced developer will read this code in the future, and it could benefit them.
The top pattern is extremely common so comments are somewhat unnecessary since everyone would know what you're doing. In the second one, comments would be less necessary with a type annotation and perhaps a better name. Maybe "next_ptr" instead of "indirect"---all pointers are indirection, so that name is redundant. But the comments are necessary, to me at least.
All pointers are pointers too, so I don't see much of a difference between "indirect" and "next_ptr", other than the "next" part. In similar situations at my job, I've drawn a small ASCII diagram in the comments, and named the variable something like "splice_point", with a corresponding label in the diagram.
Well "next_ptr" is also a bad name, I agree, but I'm trying to name it something that indicates "this is a pointer to the 'next' pointer in the linked list".
I'm kinda confused on how this will behave if we want to remove `head`—if `head` is in the stack frame (assuming it's a parameter to `remove_list_entry`), wouldn't `*(&head) = entry->next;` be a no-op as far as the caller is concerned? (Sorry for the n00b question.)
As others have said, often you don't want to free the node, you want to do something else with it. E.g., put it in a free list. However, usually if you're not freeing it, you'd null out the next field so that you don't accidentally access it when it's not part of the list (at least I would).
How likely it is for code to be misunderstood depends on the code readability as well, not just on the person who gets it wrong. Personally, I find the style of Linux lists unintuitive. To me it seems a case of sacrificing code readability to workaround limitations of the C language.
I don't see what you're saying.. the OP added that bit (the IntList struct) himself but it doesn't really change the scenario or take away from what he is trying to explain.
