Naturally, this article inspires multiple comments declaring that the way the kernel allocates or arranges memory is so obviously stupid and wrong, and that they know the right way of doing it.
I love the certainty of Hacker News posters! So confident in their own abilities and opinions. Never a moment of concern, introspection or doubt. What a world to live in!
Also, has someone thought of writing a 'it should be re-implemented in Rust' comment auto-generator? Or is that already running here?
Since you appear to me to be referring to my comment (as I'm the only top-level comment to mention Rust) let me quote some of my comment, with emphasis added to phrases I used to indicate that I was presenting was my opinion, not presenting my opinion as fact, and indeed not suggesting a rewrite in Rust (which you appear to have incorrectly inferred.)
This is, in my opinion, a rather generous interpretation
of events ... What I see when reading this is a system
(the Linux kernel and surrounding infrastructure like the C
language) that is very poorly designed. ... I'm not trying to suggest the kernel should be rewritten in Rust.
If one cannot mention their opinion on this site what indeed is the point of the site? Furthermore, your response is typical of what I've seen to shutdown discussion of kernel development: to suggest the author is an idiot and cannot possibly understand the complexities involved, and if they did they would follow the established development procedures. Do you believe the current state of kernel development is perfect? If not, if one cannot discuss problems how will one ever improve? In this particular case it seems to be a well studied class of bug (use-after-free). Why do you suggest that the many years of work on tools and other methods to address this problem should be ignored?
Completely agree. I try to practice the Principle of Charity[1]. This means when arguing see the counter argument in its best light. I think this can also be expanded when reading others code. Assume they were not idiots (in this case they were kernel developers...), and that they made decisions for a reason. Figure out those reasons, and only then improve/criticize the code.
I'll bite! I admit a bias against using linked lists. I've rarely had a need for them in a professional context. In one of the few instances I have used them, I later replaced the list with an array and got better performance. The Doom 3 BFG edition writeup on intrusive lists seems similarly bearish on the concept, unless your lists are very long.
But my experience is in a particular type of software, and maybe I'm shit at my job. :P So why does the kernel use linked lists so much? Are there cases where I can do better by using them myself?
Well, you are participating in this allocation bikeshedding too by implying that some doubt is deserved. It doesn't matter really, networking stack's performance is dominated by other issues and the whole article is not even about performance, but about bugs. And there are definitely ways to prevent bugs or at least prevent them from causing problems.
Right back at you: have you considered the possibility that those people are right? Maybe the reason lots of people are saying this is bad design in the kernel and it would be better off written in Rust is simply that this bad design in the kernel and it would be better off written in Rust.
(Please don't use sarcasm, it's rarely constructive)
The real problem is that developer (who is a graduate student) doesn't understand how to do use the kernel structure. You can't just have "your own linked list". In order to do what you are doing, you have to add a list_head structure to the struct sock structure just for that linked list, and that struct list_head has to be initialized when the struct sock is initialized, and list_del() is called when the struct sock is released --- oh, and you need to handle locking properly to avoid races between adding a struct sock to the list and removing it. Or you can use RCU, but you do need to avoid races one way or another.
It's not hard, but you do need to understand the idiom. Why isn't there safety mechanisms? Because the kernel is optimized for speed, and instead of adding run-time checks which can be expensive, there are various debugging tools, including slab poisoning and KASAN to find such issues.
Another possibility: the developer understands these things, but wrote a blog post with an explanation that omits some details in order to appeal to a broader audience.
Why would one ever prefer a linked list over a dynamic array? I know about the asymptotic performance, but if you take actual memory performance into account (locality, cache, pointers are slow, etc), it seems dynamic arrays should be simpler and perform better.
There seems to be a lot of jumping to conclusions and knee-jerk reactions in this thread. As a C developer, and having worked on Linux drivers, the description here is quite strange; memory is always freed by the same "layer" that allocated it. The implementation of release_sock (http://lxr.free-electrons.com/source/net/core/sock.c#L2536) appears to have a callback, and appears to not free memory, so it doesn't look like we have the full story here. What is clear is that the author misunderstood the "right way" to use the API in some way, and the lack of good documentation for a lot of kernel APIs is a big problem.
Perhaps Rust could have prevented the bug? I don't know. I haven't looked into Rust a great deal, but the impression I get from what I've read is that it severely limits expressiveness (read: the ways in which you can define APIs) unless you encapsulate things in blocks annotated "unsafe", at which point you lose any checking the Rust does. Would it even be possible to port the sockets code to Rust without fundamentally changing the APIs and data structures? To the Rust people: it comes off pretty badly when you throw around claims like "C effectively is unsafe everywhere" because "unsafe" in English doesn't mean what it means in Rust nomenclature; calling something "unsafe" implies it has bugs or security holes. It is perfectly possible to write bug-free secure C code, and also perfectly possible to write buggy or insecure Rust code. What I think you mean is: C code is roughly equivalent to what you'd find in a Rust block annotated "unsafe", and thus cannot perform some of the compile-time checks that Rust can. Calling it something else like "lowlevel", "expressive", or "tricky" would be better.
"I guess the moral of this story is that tools are excellent, and you should probably use them."
This is, in my opinion, a rather generous interpretation of events. What I see when reading this is a system (the Linux kernel and surrounding infrastructure like the C language) that is very poorly designed.
For example, resource allocation is a fundamental issue and a constant source of problems. We've known this as a field for a very long time. Why are fundamental things like resource allocation at least not standardised in the kernel? Better would be to enforce safe resource usage by static checking. Rust is an example of what can be done here, but much more is possible. (I'm not trying to suggest the kernel should be rewritten in Rust. I'm just using it as an example that resource usage [in particular, memory allocation in Rust] can be done in a way that prevents errors.)
Burning huge amounts of human effort is a popular approach to software development but I really hope we can do better in the next few decades. The worst thing about the current situation is the programmer blames themself ("This one kept me up until 3AM. In hindsight, every bug looks simple, and when I figured it out, I was embarassed that it took me so long") rather than wondering why this problem is even possible in the first place.
I think this is a typical reaction from someone with no clue what is going on inside.
> Why are fundamental things like resource allocation at
least not standardised in the kernel?
I'm an outsider myself, so take this with a grain of salt. But having implemented a few datastructures in C, this gave me a little chuckle. You can't "standardize" resource allocation. To be efficient and organized you need to tailor allocation to the problem at hand. I bet there are at least half a dozen common strategies for allocation in the kernel. (And most individual methods are of course "standardized". Do you suggest kernel developers are too stupid to see obvious improvements?)
What you can, and probably should, do is have all elements of one type allocated/managed through the same mechanism.
One issue with Rust (which I know you weren't actually suggesting for use in the kernel) is that it's difficult to implement recursive mutable data structures in a way that makes the borrow checker happy. Recursive mutable data structures are pretty common in the kernel, I should think.
> Why are fundamental things like resource allocation at least not standardised in the kernel?
They are. The slab allocator mentioned in the article is one part of that. The problem here was not that allocation is ad hoc, but that the author was unaware of the conventions.
It would, of course, be nice to have some static analysis to help out people in that situation.
I think it's poor methodology combined with a "dangerous" language: lack of unit-testing/TDD, low-level verbosity, lack of formal behavior prooofs, kitchen-sink features lumped into the kernel, constantly reinventing the wheel and lack of minimal package code re-use.
Don't get me wrong, I learned all the sharp edges by trial-and-error in the C89 days with Pascal and embedded assembly, but I think we've got to have systems languages which provide higher-level abstraction for bare-metal kernels. It's just that even codebases like OpenBSD don't go far enough like seL4 to verify their security model beyond reasonable doubt with formal methods.
> The worst thing about the current situation is the programmer blames themself ... rather than wondering why this problem is even possible in the first place.
Absolutely agree. I think environment is partly to blame. Devs fight fires rather than prevent them because it makes their efforts more visible.
It's the reason you can demand metrics to justify everything - the only metric that justifies defensive programming are examples of bugs/failure, and it would be better to just avoid them in the first place.
"It turns out that MPTCP sockets are allocated using a slab cache. I found this out early on, but forgot about it nearly as soon as I found out."
The real problem isn't linked lists. It's that the author learned how something worked (the spec), forgot about that, and then essentially coded against the wrong spec. The title might have instead been: "I forgot something and broke a kernel." Much more accurate given people who know they're dealing with slab allocators, linked lists, etc usually use them correctly. They can also sleep a bit better instead of being up until 3am debugging.
A linked list is almost certainly not what you want either. They're so deeply cache-unfriendly that their appearance in kernel code should be viewed as suspect.
[+] [-] joosters|9 years ago|reply
Naturally, this article inspires multiple comments declaring that the way the kernel allocates or arranges memory is so obviously stupid and wrong, and that they know the right way of doing it.
I love the certainty of Hacker News posters! So confident in their own abilities and opinions. Never a moment of concern, introspection or doubt. What a world to live in!
Also, has someone thought of writing a 'it should be re-implemented in Rust' comment auto-generator? Or is that already running here?
[+] [-] fao_|9 years ago|reply
It's a nice antidote to Hacker News, on days when Hacker News is too... Hacker Newsy :^)
[+] [-] noelwelsh|9 years ago|reply
This is, in my opinion, a rather generous interpretation of events ... What I see when reading this is a system (the Linux kernel and surrounding infrastructure like the C language) that is very poorly designed. ... I'm not trying to suggest the kernel should be rewritten in Rust.
If one cannot mention their opinion on this site what indeed is the point of the site? Furthermore, your response is typical of what I've seen to shutdown discussion of kernel development: to suggest the author is an idiot and cannot possibly understand the complexities involved, and if they did they would follow the established development procedures. Do you believe the current state of kernel development is perfect? If not, if one cannot discuss problems how will one ever improve? In this particular case it seems to be a well studied class of bug (use-after-free). Why do you suggest that the many years of work on tools and other methods to address this problem should be ignored?
[+] [-] matwood|9 years ago|reply
[1] https://en.wikipedia.org/wiki/Principle_of_charity
[+] [-] obstinate|9 years ago|reply
But my experience is in a particular type of software, and maybe I'm shit at my job. :P So why does the kernel use linked lists so much? Are there cases where I can do better by using them myself?
Edit: someone already asked, here: https://news.ycombinator.com/item?id=14182922
[+] [-] zzzcpan|9 years ago|reply
[+] [-] lmm|9 years ago|reply
(Please don't use sarcasm, it's rarely constructive)
[+] [-] bostand|9 years ago|reply
>> Why are fundamental things like resource allocation at least not standardised in the kernel?
> I think this is a typical reaction from someone with no clue what is going on inside.
[+] [-] DigitalJack|9 years ago|reply
[+] [-] tytso|9 years ago|reply
It's not hard, but you do need to understand the idiom. Why isn't there safety mechanisms? Because the kernel is optimized for speed, and instead of adding run-time checks which can be expensive, there are various debugging tools, including slab poisoning and KASAN to find such issues.
[+] [-] brenns10|9 years ago|reply
[+] [-] qeternity|9 years ago|reply
[+] [-] andreasvc|9 years ago|reply
[+] [-] dooglius|9 years ago|reply
Perhaps Rust could have prevented the bug? I don't know. I haven't looked into Rust a great deal, but the impression I get from what I've read is that it severely limits expressiveness (read: the ways in which you can define APIs) unless you encapsulate things in blocks annotated "unsafe", at which point you lose any checking the Rust does. Would it even be possible to port the sockets code to Rust without fundamentally changing the APIs and data structures? To the Rust people: it comes off pretty badly when you throw around claims like "C effectively is unsafe everywhere" because "unsafe" in English doesn't mean what it means in Rust nomenclature; calling something "unsafe" implies it has bugs or security holes. It is perfectly possible to write bug-free secure C code, and also perfectly possible to write buggy or insecure Rust code. What I think you mean is: C code is roughly equivalent to what you'd find in a Rust block annotated "unsafe", and thus cannot perform some of the compile-time checks that Rust can. Calling it something else like "lowlevel", "expressive", or "tricky" would be better.
[+] [-] noelwelsh|9 years ago|reply
This is, in my opinion, a rather generous interpretation of events. What I see when reading this is a system (the Linux kernel and surrounding infrastructure like the C language) that is very poorly designed.
For example, resource allocation is a fundamental issue and a constant source of problems. We've known this as a field for a very long time. Why are fundamental things like resource allocation at least not standardised in the kernel? Better would be to enforce safe resource usage by static checking. Rust is an example of what can be done here, but much more is possible. (I'm not trying to suggest the kernel should be rewritten in Rust. I'm just using it as an example that resource usage [in particular, memory allocation in Rust] can be done in a way that prevents errors.)
Burning huge amounts of human effort is a popular approach to software development but I really hope we can do better in the next few decades. The worst thing about the current situation is the programmer blames themself ("This one kept me up until 3AM. In hindsight, every bug looks simple, and when I figured it out, I was embarassed that it took me so long") rather than wondering why this problem is even possible in the first place.
[+] [-] jstimpfle|9 years ago|reply
> Why are fundamental things like resource allocation at least not standardised in the kernel?
I'm an outsider myself, so take this with a grain of salt. But having implemented a few datastructures in C, this gave me a little chuckle. You can't "standardize" resource allocation. To be efficient and organized you need to tailor allocation to the problem at hand. I bet there are at least half a dozen common strategies for allocation in the kernel. (And most individual methods are of course "standardized". Do you suggest kernel developers are too stupid to see obvious improvements?)
What you can, and probably should, do is have all elements of one type allocated/managed through the same mechanism.
[+] [-] foldr|9 years ago|reply
[+] [-] Rusky|9 years ago|reply
They are. The slab allocator mentioned in the article is one part of that. The problem here was not that allocation is ad hoc, but that the author was unaware of the conventions.
It would, of course, be nice to have some static analysis to help out people in that situation.
[+] [-] ReligiousFlames|9 years ago|reply
Don't get me wrong, I learned all the sharp edges by trial-and-error in the C89 days with Pascal and embedded assembly, but I think we've got to have systems languages which provide higher-level abstraction for bare-metal kernels. It's just that even codebases like OpenBSD don't go far enough like seL4 to verify their security model beyond reasonable doubt with formal methods.
[+] [-] Chris2048|9 years ago|reply
Absolutely agree. I think environment is partly to blame. Devs fight fires rather than prevent them because it makes their efforts more visible.
It's the reason you can demand metrics to justify everything - the only metric that justifies defensive programming are examples of bugs/failure, and it would be better to just avoid them in the first place.
[+] [-] nickpsecurity|9 years ago|reply
The real problem isn't linked lists. It's that the author learned how something worked (the spec), forgot about that, and then essentially coded against the wrong spec. The title might have instead been: "I forgot something and broke a kernel." Much more accurate given people who know they're dealing with slab allocators, linked lists, etc usually use them correctly. They can also sleep a bit better instead of being up until 3am debugging.
[+] [-] ReligiousFlames|9 years ago|reply
Here's one: https://github.com/troydhanson/uthash
[+] [-] monomaniar|9 years ago|reply
[+] [-] grabcocque|9 years ago|reply