Linked list should be a separate typedef

[Jiri Svoboda]

Currently link_t is used both:

• to declare a linked list (i.e. its head)
• to declare a list link

This is confusing. There should be a separate structure typedef list_t for declaring the list itself.

[shm]

list_t patch

[shm]

Attached patch should resolve this ticket.

[Jiri Svoboda]

I looked at your patch. While it does (literally) what the ticket description says, it could be improved a lot. Firstly, renaming list_t to list_head_t in SBI sources was uncalled for. The correct way would be to add an entry to compat.h renaming list_t to sbi_list_t.

Also, simply adding the definition and changing the types of corresponding variables is not enough. At the minimum the variables should be renamed so that their names do not include 'head'.

Ideally an API for traversing the lists (list_first, list_next) should be defined so that we avoid directly accessing the head element. But that can be done as follow-up.

[Jiri Svoboda]

The kernel part is implemented in changeset:mainline,1043. Summary of changes:

• list_t represents lists
• Use list_first(), list_last(), list_empty() where appropriate
• Use list_foreach() where possible
• Replace improper uses of list_prepend() with list_insert_after()
• Replace improper uses of list_append() with list_insert_before()
• Appropriately rename variables

I've yet to do the user-space part to complete work for this ticket.

[Jiri Svoboda]

The user-space part is implemented in changeset:mainline,1048. This is analogous to the kernel changes. Also, added macro assert_link_not_used() to check that a structure that is being freed is not linked into a list anymore.

[Jiri Svoboda]

Migration guide

Firstly, if you merge my changes and you code still compiles, then you're off the hook. The changes merely enforce stricter checking via types. If the code compiles, it will run. If it does not compile, you need to fix it.

You can fix your code in a trivial and safe way, but I urge you not to do that. Rather take the opportunity to improve your code (but watch out for making mistakes!)

What has changed:

• List is now represented by list_t (instead of link_t). This structure has one member, link_t head
• Adequate changes of list function prototypes
• Some new functions and macros: list_last(), assert_link_not_used(), list_count()

What you need to do: The compile errors will point you to the things you need to change. Typically the things you will hit first:

• Declare uninitialized lists as list_t instead of link_t. Please change variable names appropriately. (e.g link_t foo_head → list_t foos or list_t foo_list)
• Distiguish between list_initialize() and link_initialize()

When you fix these, usually the compiler will complain that list_t does not have a member .next or .prev. Now the easiest thing to do would be to change list_head.next to list.head.next and list_head.prev to list.head.prev. This always works and is the last resort. However in many cases you can improve the code to be more abstract, instead.

(1) Simple walks such as:

for (link_t *link = list_head.next; link != &list_head; link = link->next) {
    foo;
}

or

link_t *link = list_head.next;
while (link != &list_head) {
    foo;
    link = link->next;
}

can be substituted for:

list_foreach(list, link) {
    foo;
}

Do not use list_foreach() when the loop body changes the structure of the list or moves the iterator manually (apart from the regular advance step). That usually leads to trouble.

(2) 'Dismantle list' pattern

while (list_head.next != &list_head) {
    link_t *link = list_head.next;
    foo;
    list_remove(link);
}

can be replaced with e.g.

while (!list_empty(&list)) {
    link_t *link = list_first(&list);
    foo;
    list_remove(link);
}

Generally list_first() and list_last() are nice to use instead of list.head.next and list.head.prev. Be careful though, they return NULL instead of &list.head. They are definitely safe to use in expressions like list_get_instance(list_first(...), ...).

(3) Get first entry in a list
Either you can use:

if (!list_empty(&list)) {
	link_t *link = list_first(&list);
	foo;
} else {
	/* list empty */
}

or, alternatively:

link_t *link = list_first(&list);
if (link != NULL) {
	foo;
} else {
	/* list empty */
}

Here's a complex iteration case that we convert trivially, to be on the safe side:

link_t *link = list_head.next;
while (link != &list_head) {
    /*
     * do strange stuff with link, like compare link->prev to &list_head, modify the list
     * structure, etc.
     */
    link = link->next;
}

convert to:

link_t *link = list.head.next;
while (link != &list.head) {
    /*
     * do strange stuff with link, like compare link->prev to &list.head, modify the list
     * structure, etc.
     */
    link = link->next;
}

Eventually I might try eliminating direct access to list_t.head, link_t.next and link_t.prev. But that is for another day.

Finally, if you are destroying a structure containing a link_t, you can make sure you didn't forget to remove it from the list.

• When you create the structure foo, link_initialize(&foo.link)
• When you destroy the structure foo, assert_link_not_used(&foo.link)

This checks that foo.next and foo.link.prev are NULL. This is true when the link is initialized with link_initialize() until it is inserted into a list. When foo is removed from the list, list_remove() again sets foo.link.prev and foo.link.next to NULL.

If you have any questions or concerns, please let me know.