LWN: Comments on "Toward a better list iterator for the kernel"

Toward a better list iterator for the kernel

mcortese — Sat, 26 Mar 2022 07:09:49 +0000

Am I the only one who thinks that depending on the names of the variables is extremely fragile? There are so many corner cases where this hack will fail that I wonder if developers can really be convinced to begin using it.

Inventors and heroes

ghane — Sun, 20 Mar 2022 10:24:17 +0000

> I wouldn't say "obvious" but Isaac Newton (one of the very few who was _really_ way ahead of his time) put it best: "If I have seen further it is by standing on the shoulders of Giants."

The way I understand it, it was a dig at his arch-rival (in the 1670s), Hooke, who was short (and may have had a twisted back).

Independent invention

giraffedata — Sat, 19 Mar 2022 20:54:42 +0000

Alexander Graham Bell is credited with the invention of the telephone, but he just happened to beat his competitor to the patent office. I think the same is true of the Wright Brothers (the first successful aircraft was built in 1896 in England - it just didn't actually fly til about 10 years later ... :-)

Being the first to fly, first to file and the first to publicize count for a lot. I think it's vanishingly rare for someone to be so smart he comes up with an idea that no one else has; turning such an idea into an invention is more worthy of credit than having the idea.

I've read that many things were invented in China before they were invented in Europe (in days before the two were in communication), but it's because of the European inventor that I have them today, so I tend to celebrate the European inventor.

I find myself rejoicing...

smitty_one_each — Fri, 18 Mar 2022 01:43:13 +0000

...that even the Really Smart Folks have to bang their heads as much as I do trying to get things working.

Inventors and heroes

excors — Thu, 17 Mar 2022 13:05:27 +0000

That was Hooke, not Leibniz. (Newton seems to have been rather antagonistic and had several bitter rivalries. And as Master of the Mint he also had dozens of counterfeiters prosecuted and hanged, so those people probably weren't too happy with him either. But (to bring this marginally back on-topic) as Linus Torvalds said when asked about his heroes, "even though [Newton] was apparently not a very nice person, he was certainly one of those people who changed the world in many different ways" (https://archive.computerhistory.org/resources/access/text...))

Inventors and heroes

mathstuf — Thu, 17 Mar 2022 08:56:07 +0000

The "shoulders of giants" quote was also meant as a slight to Leibnitz who was not tall.

Toward a better list iterator for the kernel

jem — Mon, 14 Mar 2022 19:51:41 +0000

The difference between C and Rust is that Rust allows you reuse a variable name in the same block, which is an error i C.

The scope of a Rust variable variable ends either at the end of the block, or when a new variable with the same name is declared. You can use the old variable when computing the initial value of the new variable, i.e. you can initialize a variable with the value of the variable "itself".

This can be used to change a variable from being mutable to immutable when there is no need to change the value after some point in the program. (Technically there are two separate variables with the same name.)

Toward a better list iterator for the kernel

laarmen — Mon, 14 Mar 2022 16:43:38 +0000

In Rust, variable name re-use is actually rather idiomatic. I used to be skeptical about it, as my experience also was of confusing bugs, or at least code. However, I've embraced this idiom in Rust for purely pragmatic reasons:

In C, your 'char* str' variable will be the same type before and after your null check, but in Rust those are two separate types. A given "content" can undergo multiple type changes in as many lines as the assumptions are checked, it'd be really tedious to have to come up with new names for essentially the same content.

You can find an example of shadowing in the Rust Book in the second chapter! https://doc.rust-lang.org/book/ch02-00-guessing-game-tuto... (the 'guess' name is reused as we go from the raw input string to the actual integer)

Inventors and heroes

ballombe — Mon, 14 Mar 2022 15:53:19 +0000

Being French, I will argue that Fermat invented calculus before them!
Really, ideas only exist when they are shared, and for that you need to be at least two.

While Hilbert gave his theorems numbers (90, 92 are the most well known)
Poincarré gave them the names of people whose work inspired him.

Toward a better list iterator for the kernel

PengZheng — Mon, 14 Mar 2022 02:26:04 +0000

Unfortunately, code size will be a concern, even in user space. Nowadays, devices with 64MB flash storage does a lot of things, doubling code-size as mentioned in ianmcc's comment is terrifying.

Inventors and heroes

marcH — Mon, 14 Mar 2022 00:13:05 +0000

> > Isaac Newton (one of the very few who was _really_ way ahead of his time)

> Certainly it's disputed whether he was the "inventor" of Calculus, and the same is probably true of most of his other advances.

OK, but:

> > heroes make much better stories and movies

So here it is: https://youtu.be/gMlf1ELvRzc "Then Newton came along and changed the game"

;-)

There is a genuine mathematician in awe of Newton in this video, so I think he was pretty far ahead. I have no idea whether he was ahead _alone_.

> or was it we just have no real record of their predecessors? (Because before the Royal Society there *were* no records?)

I'm not an expert but I'm pretty sure we have plenty of scientific records much, much older than Newton. Newton lived more than 200 years after Gutenberg so I really doubt that was still a problem at a time.

Inventors and heroes

roc — Sun, 13 Mar 2022 22:33:46 +0000

Shakespeare wasn't just first, he actually was incredibly good.

Inventors and heroes

NYKevin — Sun, 13 Mar 2022 22:16:47 +0000

The current consensus is that Newton and Leibniz invented calculus at more or less the same time, independently of each other, but (in the English-speaking world at least) Newton had better publicity.

Interestingly, they also had very different ideas of what calculus was good for. Newton wanted to use it to model the physical world, while Leibniz seemed to think it had more metaphysical/philosophical significance. Arguably, they were both right, because the notion of Taylor series and analytic continuation have greatly improved our intuition and understanding of What Functions Are... and that has in turn been used to bring complex analysis into the world of physics and engineering (e.g. in the form of modern Fourier analysis). It's all connected in the end.

Inventors and heroes

Wol — Sun, 13 Mar 2022 20:32:56 +0000

> I wouldn't say "obvious" but Isaac Newton (one of the very few who was _really_ way ahead of his time) put it best: "If I have seen further it is by standing on the shoulders of Giants." This sentence was apparently inspired by older, similar sentences in an interesting, "recursive" twist.

Was he? I think he was probably one of the founding members of the Royal Society, and many of them were equally "ahead of their time" - or was it we just have no real record of their predecessors? (Because before the Royal Society there *were* no records? Just like Shakespeare is "the greatest English playwright", not because he was necessarily any good, but also because he was the *first* major English playwright, writing at the time "modern English" was born.)

And while Newton wrote "In Principia Mathematica", I think it was primarily written to beat his contemporaries into the history books. Certainly it's disputed whether he was the "inventor" of Calculus, and the same is probably true of most of his other advances.

From what I can make out, the rivalry was intense, and Newton just won the publicity war.

Cheers,
Wol

Toward a better list iterator for the kernel

marcH — Sun, 13 Mar 2022 20:23:59 +0000

https://www.ted.com/talks/linus_torvalds_the_mind_behind_...

> Well, so this is kind of cliché in technology, the whole Tesla versus Edison, where Tesla is seen as the visionary scientist and crazy idea man. And people love Tesla. I mean, there are people who name their companies after him.

> The other person there is Edison, who is actually often vilified for being kind of pedestrian and is -- I mean, his most famous quote is, "Genius is one percent inspiration and 99 percent perspiration." And I'm in the Edison camp, even if people don't always like him. Because if you actually compare the two, Tesla has kind of this mind grab these days, but who actually changed the world? Edison may not have been a nice person, he did a lot of things -- he was maybe not so intellectual, not so visionary. But I think I'm more of an Edison than a Tesla.

PS: funny enough Elon Musk was there early but not at the very beginning of Tesla. There's a great interview of the Tesla founders where they (among others) acknowledge everything that came before Tesla.

Inventors and heroes

marcH — Sun, 13 Mar 2022 20:13:54 +0000

> I think the same is true of the Wright Brothers (the first successful aircraft was built in 1896 in England - it just didn't actually fly til about 10 years later ... :-)

If you're French you know that the "first" flight was performed by either Clément Ader or Louis Blériot, if you're Brazilian then you know that it was Alberto Santos-Dumont, if you're German then maybe it's Gustav Weißkopf / Whitehead? Etc.

Everyone is correct as long as you tweak the definition of "first flight".

> These things are probably obvious to any competent mind that decides it wants to tackle the problem.

I wouldn't say "obvious" but Isaac Newton (one of the very few who was _really_ way ahead of his time) put it best: "If I have seen further it is by standing on the shoulders of Giants." This sentence was apparently inspired by older, similar sentences in an interesting, "recursive" twist.

Humanity is a very social species who can't achieve anything alone yet we love celebrating heroes. Inventors' contribution to progress is nothing compared to the Excel spreadsheets of the Department of Education but heroes make much better stories and movies and are a little bit more... inspirational! Heroes are especially important in American culture where the gaps are the widest; dispensing hope is so much cheaper. Panem, circenses and... "spes"?

> but he just happened to beat his competitor to the patent office.

Exactly: whatever you do, make sure you get some lawyers and businessmen on your side. History shows you can't make a difference without their help.

Toward a better list iterator for the kernel

Wol — Sun, 13 Mar 2022 16:39:05 +0000

> >One might argue that all of this is self-inflicted pain caused by the continued use of C in the kernel. That may be true, but better alternatives are in somewhat short supply.

> I disagree; alternatives are not in short supply, but they have tradeoffs that some people may be unwilling to go with. The Linux kernel linked list implementation has two properties:

Please note you are disagreeing with a straw man. Jon didn't write what you imply he did - you've elided the very important word *better*.

Cheers,
Wol

Toward a better list iterator for the kernel

ianmcc — Sun, 13 Mar 2022 15:43:49 +0000

It depends on how exceptions are implemented by the compiler. Exceptions require RTTI, because you need to be able to match the type of the thrown object with a corresponding catch (...) clause. When you have a try {...} block, the compiler needs to know how to unwind the stack. Most modern compilers use a 'zero overhead' model, meaning that the runtime cost (in CPU time) is basically zero for the no-exception case. ie, there is no penalty for having a try {...} block if no exception is actually thrown. The way they do this is with a lookup table from the instruction pointer to the exception handler for the current stack frame. This basically doubles the code size. Also the cost of throwing an exception is quite high, so you normally only want to do it for really exceptional events, not as an alternative to a return statement. But in some cases exceptions can be faster than return codes, i.e. since you need to check the return code every time, in a tight loop using exceptions might be faster.

More info: https://wg21.link/p1947

Toward a better list iterator for the kernel

Wol — Sun, 13 Mar 2022 11:39:53 +0000

Basically, anywhere you are hardware-constrained (and an OS is a perfect example) you need to be very careful about knowing exactly what abstractions the compiler is using. C++ makes this rather tricky!

Once you're in user space, especially if you're in an online state (ie the computer is a lot faster than the person behind the keyboard), you no longer need to worry and can use the full power of C++. Just make sure you don't use the bits you don't understand :-)

Cheers,
Wol

Toward a better list iterator for the kernel

PengZheng — Sun, 13 Mar 2022 10:08:17 +0000

Thanks for pointing me to SerenityOS. It seems that memory allocation failure will lead to crash:
https://github.com/SerenityOS/serenity/blob/master/AK/Vec...

I assume (it might be false) that C++ exception is not suitable for kernel development and some constrained embedded environment.
Are there any good guidelines for such C++ usages?

Toward a better list iterator for the kernel

Wol — Sat, 12 Mar 2022 19:28:24 +0000

The same way all these things happen.

Alexander Graham Bell is credited with the invention of the telephone, but he just happened to beat his competitor to the patent office. I think the same is true of the Wright Brothers (the first successful aircraft was built in 1896 in England - it just didn't actually fly til about 10 years later ... :-)

These things are probably obvious to any competent mind that decides it wants to tackle the problem.

Cheers,
Wol

Toward a better list iterator for the kernel

moorray — Sat, 12 Mar 2022 17:48:23 +0000

I suggested exactly what Linus "came up with" a week later - solution #2 here:
https://lore.kernel.org/all/20220228223228.24cf3fd4@kicin...

I wonder how these things happen...

Toward a better list iterator for the kernel

alonz — Sat, 12 Mar 2022 17:04:42 +0000

Actually in C11 it is possible to create a shadowing variable. However, this usually triggers a compiler warning - since such shadowing is rather confusing to the readers, and is usually considered bad practice (and a harbinger of confusing bugs).

Toward a better list iterator for the kernel

droundy — Sat, 12 Mar 2022 02:59:03 +0000

If C had the ability rust has to create a new variable shadowing the name of a former one, the macro could just create a new variable of a the same name but a different type to make any further use cause a compile error.

But of course if this weren't C we wouldn't have this problem.

Toward a better list iterator for the kernel

timon — Fri, 11 Mar 2022 18:55:35 +0000

As I read this, you misunderstood the "cpp" part; the OP is talking about the C preprocessor and you are talking about C++.

Toward a better list iterator for the kernel

geert — Fri, 11 Mar 2022 11:20:03 +0000

Mindlessly adding preinitializations to uninitialized variables instead of fixing the real problems prevents the compiler from flagging newly introduced uninitialized users of the same variable later.

BTW, I used to fix all newly introduced non-false positives reported by gcc-4.1.2, which was rather strict (compared to later gcc versions), and caused lots of false positives. But every kernel release, I did catch a handful of real bugs. Later, gcc improved, Arnd started to build the kernel with bleeding edge gcc versions catching more bugs before I found them, and support for gcc-4.1.2 was dropped. But I believe there still are areas for improvements...

Initialization

bartoc — Fri, 11 Mar 2022 01:29:10 +0000

Note, I'm talking more about /RTCs rather than "InitAll", which might work better.

Initialization

bartoc — Fri, 11 Mar 2022 01:25:24 +0000

MSVC's behavior is a bit of a problem because there's no great opt-out, and it doesn't really do the optimizations in debug mode, meaning if you ever use stack arrays it's really easy to have awful debug mode performance. It's one of the bigger "MSVC debug perf sucks" things around (along with like, not having a way to write inline functions that are always inlined, even in debug).

If there was an opt-out, and if MSVC had a saner "debug mode" (really these optimizations should be turned on in debug mode imo) then it would be a great behavior.

Toward a better list iterator for the kernel

roc — Fri, 11 Mar 2022 01:24:34 +0000

My point is that a lot of those "dead stores" are already being performed by kernel hardening. https://github.com/torvalds/linux/blob/186d32bbf034417b40...

So on one hand we've got developers saying "adding dead stores hurts performance, don't do it and keep that essential warning disabled", and on the other hand developers are adding dead stores all over the place for the sake of security.

Initialization

tialaramex — Fri, 11 Mar 2022 00:29:09 +0000

There was a CPP Con talk some years back about exactly this work by Microsoft. Basically let us teach the compiler to zero initialize everything, then run tests to see how awful the results are, teach the compiler to optimize away these dead stores and/or perform zero initialization that it more easily recognises as dead stores, iterate. IIRC The first few loops are very, very bad, nothing you could possibly ship, but as they learn what they're doing by the end they can more or less do this over the bulk of the system and get the same performance as before but with more confidence there aren't scary initialisation bugs. Obviously they were in C++ and their own C++ compiler, where Linux would want C and GCC, but it's not so different otherwise. If people can't find it themselves I can search Youtube maybe.

Toward a better list iterator for the kernel

NYKevin — Thu, 10 Mar 2022 23:53:23 +0000

If the compiler wrongly thinks that a variable is used before initialization, then it will probably fail to optimize away the dead store resulting from eager initialization. Whether that dead store is worth worrying about is another matter, of course, and probably depends on how hot a given codepath is.

Toward a better list iterator for the kernel

roc — Thu, 10 Mar 2022 22:50:30 +0000

> the "use of uninitialized variable" warning is disabled in the kernel due to excessive false positives.

Wow, this is terrible. I had no idea.

Given there are hardening patches to force zeroing of local variables, why not just initialize them in the source as necessary to eliminate the existing warnings and turn that warning on?

Toward a better list iterator for the kernel

roc — Thu, 10 Mar 2022 22:47:44 +0000

The main point of Rust in the kernel is to get much-improved safety properties. Zig doesn't provide that.

Toward a better list iterator for the kernel

ppisa — Thu, 10 Mar 2022 22:13:51 +0000

I have need for poor STL relative in C year ago and uLUt library was a result. Because it has been intended even for use in kernel at the times of RTLinux I have decide to be compatible/reuse kernel list but provide type-safe interfaces for each relation

https://sourceforge.net/p/ulan/ulut/ci/master/tree/ulut/u...

This way you never use container_of directly and risk to use incorrect offset between list node location and start of containing structure is suppressed. For AVL, hashes and sorted arrays I have used other structures than kernel. The library provides even iterators which works over all of these basic types.

But macros which expands to the static inline functions are really huge. But reasonable compilers generate code better for these variants with CUSTom prefix than when generic functions with void pointers are used.

The library is base in many project, our RS485 multimaster project http://ulan.sourceforge.net/ , CAN and CANopen http://ortcan.sourceforge.net/ more instruments using inhouse our SmallToolKit graphic library https://gitlab.com/pikron/sw-base/suitk/-/wikis/home which has been used even is safety sensitive medical devices etc.

Toward a better list iterator for the kernel

bartoc — Thu, 10 Mar 2022 21:55:02 +0000

Note that what the list iterator does is pretty far from how C++ iterators work. This style of iterator is "I write the loop, and I'll insert your body with the right item all set up", where C++ is "you write the loop, and ask me for each item"

There's nothing really preventing you from doing the C++ approach in C, although you need to be careful about inlining, you just write an "iterator init from structure" "iterator next" and "is iterator done" function and call them in the appropriate places in a for loop. However I think the more intrusive way of doing things is quite a lot clearer when reading the iterator implementation, esp for more complicated iterators.

Toward a better list iterator for the kernel

bartoc — Thu, 10 Mar 2022 21:47:07 +0000

I'm concerned about how long zig tends to defer typechecking of code. Maybe it doesn't matter in the real world though.

I really love how zig does generics; you write type constructors as just .... normal functions that return a type!

Toward a better list iterator for the kernel

pankyraghv — Thu, 10 Mar 2022 20:04:40 +0000

I know many people in the kernel community hates cpp but I would recommend everyone to take a look at SerenityOS. They have done a fantastic job of rolling out an in-house standard library that actually makes coding in cpp enjoyable (mostly) while reaping the benefits of all the modern features that can catch bugs at compile time. IMO a subset of cpp with a good custom standard library would be a better fit to writing kernel drivers than use something like Rust which has a very different programming paradigm. I also feel something light like Zig might also be a good option.

Toward a better list iterator for the kernel

EnigmaticSeraph — Thu, 10 Mar 2022 17:52:18 +0000

The kernel generally tolerates no performance hits, esp. with such a widely-used structure. And while there exists e.g.:
https://www.boost.org/doc/libs/1_78_0/doc/html/intrusive/...
, which can be configured to be as would've been at the C level, but generic. However, kernel devs tend to be wary of C++ in the kernel, for not-unfounded reasons.

Toward a better list iterator for the kernel

jengelh — Thu, 10 Mar 2022 17:08:06 +0000

>One might argue that all of this is self-inflicted pain caused by the continued use of C in the kernel. That may be true, but better alternatives are in somewhat short supply.

I disagree; alternatives are not in short supply, but they have tradeoffs that some people may be unwilling to go with. The Linux kernel linked list implementation has two properties:

- the linked list metadata (prev/next) pointers is not separated from the struct => layering violation
- an object can be part of multiple linked list => who's the owner responsible for cleanup?
(- the iterator interface of list_head is just a consequence of the two)

And these are approached with

- inode is, in terms of responsibility, strictly a child of the list and/or its internal metadata
- only one owner is allowed so there is no doubt who has to clean up

Using C++ as a concrete example now, one would arrive at:

1. Use std::list<std::shared_ptr<inode>>. Safe from leaks, safe from dangling pointers, but it needs refcounting to do the job, and some people may not like the performance characteristics of that refcounting.
2. Use std::list<inode> for the main list, and std::list<inode *> for the secondaries. Cleanup is still guaranteed, but you traded refcounting for the potential danger of dangling pointers.
(3. Keep on allocating your inodes and lists manually like before... as C++ is almost source-compatible with C.)

My linked lists

abatters — Thu, 10 Mar 2022 16:15:56 +0000

For non-circular linked lists in my userspace code, my approach is to define a dedicated macro for each specific list, defining the name of its head, tail, forward, and back pointers. Then that specific macro can be used in combination with one of ~25 generic doubly-linked list macros I have defined. Works well for having a single object in multiple lists, and having multiple lists in a single container. No iteration macro is necessary, since you have pointers to the real types (no container_of needed) and it terminates with NULL.

// Generic doubly-linked list macro (one of ~25)
#define DLIST_ADD_TAIL(head, tail, forw, back, item) \
   do { \
      if ((tail) == NULL) { \
         (head) = (item); \
      } else { \
         (item)->back = (tail); \
         (tail)->forw = (item); \
      } \
      (tail) = (item); \
   } while (0)

// Example linked list structs
struct item {
  struct item *iforw, *iback;
};
struct container {
  struct item *ihead, *itail;
};

// Example macro defining a specific list
#define CONTAINER_ITEM_LIST(container, func, args...) \
  func((container)->ihead, (container)->itail, iforw, iback , ## args)

void container_add_item_tail(struct container *container, struct *item)
{
   CONTAINER_ITEM_LIST(container, DLIST_ADD_TAIL, item);
}