Toward a better list iterator for the kernel [LWN.net]

Toward a better list iterator for the kernel

Posted Mar 10, 2022 17:08 UTC (Thu) by jengelh (subscriber, #33263)
Parent article: Toward a better list iterator for the kernel

>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.)

Toward a better list iterator for the kernel

Posted Mar 10, 2022 21:55 UTC (Thu) by bartoc (guest, #124262) [Link]

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

Posted Mar 12, 2022 2:59 UTC (Sat) by droundy (guest, #4559) [Link] (3 responses)

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

Posted Mar 12, 2022 17:04 UTC (Sat) by alonz (subscriber, #815) [Link] (2 responses)

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

Posted Mar 14, 2022 16:43 UTC (Mon) by laarmen (subscriber, #63948) [Link]

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)

Toward a better list iterator for the kernel

Posted Mar 14, 2022 19:51 UTC (Mon) by jem (subscriber, #24231) [Link]

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

Posted Mar 13, 2022 16:39 UTC (Sun) by Wol (subscriber, #4433) [Link]

> >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