Questions about linked list

Angus · 02-12-2011, 04:12 PM

I'm looking through the source code for the linked list in <linux/list.h> and I have a few questions. You should probably know that I've never done any kernel writing, and the only C I've been doing for the past 10 years is C++:

What's rcu? And I'll probably need to know what "rcu protection" is too
Why no payload? It seems that the only members of list_head are next and prev. Where does the data go? Or is this the C kernel implementation of what would otherwise be a C++ template? I suppose to insert the payload, there's some clever code to find where list_head members end, and the payload is put there
Why poison the next and prev when deleting a node? This seems awfully inefficient debug code. I might do such a thing in an application, but surround the code with #ifndef NDEBUG and then use asserts later. And why poison it to those values? Can there be no danger that those would be addresses assigned to pointers?

nini09 · 02-14-2011, 02:31 PM

Searching list_for_each_entry keyword in kernel source, you can find out a lot of example. They can explain why linked list doesn't have payload field.

Angus · 02-14-2011, 03:15 PM

I'm afraid I didn't. I did find http://isis.poly.edu/kulesh/stuff/src/klist/ which explains how to dereference the payload, by not why it's designed like that.

I'm guessing that it is designed this way, so that when forward traversing a list, the next pointer is at the same address as the current list struct, thereby avoiding the burden of having to calculate next's address. But that doesn't sound terribly useful.