Monday, April 11, 2022

[SOLVED] Explain list_for_each_entry and list_for_each_entry_safe

Issue

Can anyone explain the working of list_for_each_entry and ...entry_safe loop in linux. It is like

list_for_each_entry(type *cursor, struct list_head *list, member)

list_for_each_entry_safe(type *cursor, type *next, struct list_head *list,member)

What are the role of all these parameters and how they are used to traverse the list.

Thanks in ADVANCE


Solution

EDIT: sorry, it must be late, I've made a lot of typos.

They are pure fun! :) The difference is that list_for_each_entry will break if you delete something while iterating the list and list_for_each_entry_safe won't (of course, at the expense of some extra CPU instructions).

The kernel has settled on doubly-linked lists (which I'm presuming you understand), although there is a singingly linked list implementation in list.h. Your list is just:

struct list_head {
    struct list_head *next;
    struct list_head *prev;
};

Note that the same struct is used for both the "head" of the list as well as each node. When the list is empty, the head's next and prev members just point to the head its self. Thus, iterating the list is just a process of starting with the head's next member and calling that a node, unless it's the same address as prev (when you stop). Otherwise, your for body is invoked and you can use the container_of() macro to get a pointer to your actual struct and play with it. Then, in the 3rd field of the for, we just just move to the next next.

EDIT: whoops, I apologize, you asked for an explanation of the parameters. Well, I would check it out directly if I were you rather than taking somebody's word for it. For those, I would suggest the Kernel API docs themselves, which at least exist for the linked list library. I'm trying to get a patch set through that will add them for the red-black tree library as well, but getting stuff through can be quite a process.

Also of note: http://kernelnewbies.org/FAQ/LinkedLists

Here's a quick example:

struct list_head my_actual_list;
struct my_struct {
    struct list_head node;
    /* some other members */
};

/* in a function body somewhere... */
struct list_head *i;
list_for_each(i, &my_actual_list) {
    struct my_struct *obj = list_entry(i, struct my_struct, node);
    // do something with obj
}

list_entry is just an alias for container_of

EDIT #2

OK, so in answer to your question in comments, I'm going to just expand my answer. I can actually appreciate the difficulty in grasping this concept as it does have a few strange things in it compared to C++ STL containers, C arrays, etc, but once you are accustom to the idioms, it will seem quite natural. Still in the future, I really urge you to start looking at the definition for these structs, functions & macros yourself and trying to piece together an understanding, then ask the questions.

So first off, each node in your list is a struct that contains a member of type struct list_head and the list its self is of type struct list_head. Thus, who is the container and who is the contained in this case, simply depends upon how they are used, but typically, it will be expressed in the names these members are given. The type of the iterator is struct list_head *. Here's an example and I'll replace the normal function & macro calls with their equivalent code:

struct my_container {
    struct list_head list;
    int some_member;
    /* etc. */
};

struct my_obj {
    struct list_head node;
    int some_member;
    /* etc. */
};

void func() {
    struct my_container container;
    struct my_obj obj1, obj2;
    struct list_head *i;

    /* INIT_LIST_HEAD(&container.list); */
    container.list.next = &container.list;
    container.list.prev = &container.list;

    /* list_add_tail(&obj1.node); */
    container.list.prev = &obj1.node;
    obj1.node.next = &container.list;
    obj1.node.prev = &container.list;
    container.list.next = &obj1.node;

    /* list_add_tail(&obj2.node); */
    container.list.prev = &obj2.node;
    obj2.node.next = &container.list;
    obj2.node.prev = &obj1.node;
    obj1.node.next = &obj2.node;

    /* list_for_each(i, &container.list) { */
    for (i = container.list.next; i != &container.list; i = i->next) {
        struct my_obj *obj = list_entry(i, struct my_obj, node);
        /* do stuff */
    }

}

Now go read! :)



Answered By - Daniel Santos
Answer Checked By - Dawn Plyler (WPSolving Volunteer)
at