I'm not sure I can answer that about their malloc, now and in the past.

But your question reminded me of another aspect of linked lists in the Linux kernel: unlike a lot of high level languages, there isn't an extra allocation for a node structure. The node structure is a member of the structure being linked.

Often the structure being linked might be something like a reference counted heap object, so the question of adding an extra member to store the next pointer is not a big difference.

> unlike a lot of high level languages, there isn't an extra allocation for a node structure. The node structure is a member of the structure being linked.

That's good, but it seems like how-hanging fruit. Boost offers intrusive_prt for this. [0]

make_shared goes half way, and performs a single allocation to return a shared_ptr to a new object. It eventually made its way from Boost to the standard. [1][2]

See also [3] which contrasts the two. (As you can imagine, intrusive_prt is slightly more efficient.)

[0] https://www.boost.org/doc/libs/latest/libs/smart_ptr/doc/htm...

[1] https://www.boost.org/doc/libs/latest/libs/smart_ptr/doc/htm...

[2] https://en.cppreference.com/cpp/memory/shared_ptr/make_share...

[3] https://stackoverflow.com/a/13913161

About 20 years ago I read a paper, I think it was a C++ retrospective by Stroustrup talking about the justification for C++ templates.

He actually cited this use case, of a structure that has list or tree nodes inline with the data type, as a strength of the model.

I think that's fair. It's neat that it's possible through C++'s template system. It wouldn't be possible in many other languages.

IIRC Linux looks pretty much everything.

Well not explicitly, but it uses a version of malloc that has a pool for every rounded object size.