0

I am trying to use linux kernel doubly linked-list implementation mentioned in https://github.com/torvalds/linux/blob/master/include/linux/list.h in user-space which its user-space implementation can be found in https://gist.github.com/roychen/1710968

following is the code which I used at first and it works fine :)

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include "list.h"

struct Node
{
    int data;
    char name[10];
    struct list_head mylist;
};

int main()
{
    LIST_HEAD(plist);

    struct Node node1 = {.data = 10, .name = "node1", .mylist = LIST_HEAD_INIT(node1.mylist)};
    struct Node node2;

    node2.data = 20;
    strcpy(node2.name, "node2");
    INIT_LIST_HEAD(&node2.mylist);

    list_add_tail(&node1.mylist, &plist);
    list_add_tail(&node2.mylist, &plist);

    struct Node* iter;

    list_for_each_entry(iter, &plist, mylist)
    {
        printf("name = %s, data = %d\n", iter->name, iter->data);
    }

    return 0;
}

the output of the above code is

name = node1, data = 10
name = node2, data = 20

which is as expected.

now assume that I want to add node1 twice

Scenario number 1:

    list_add_tail(&node1.mylist, &plist);
    list_add_tail(&node1.mylist, &plist);

output 1:

name = node1, data = 10
name = node1, data = 10
name = node1, data = 10
name = node1, data = 10
name = node1, data = 10
name = node1, data = 10
name = node1, data = 10
name = node1, data = 10
name = node1, data = 10
name = node1, data = 10
name = node1, data = 10
name = node1, data = 10
name = node1, data = 10
name = node1, data = 10
... -> non-stopping loop (to infinity)

Scenario number 2:

    list_add_tail(&node1.mylist, &plist);
    list_add_tail(&node2.mylist, &plist);
    list_add_tail(&node1.mylist, &plist);

output 2:

name = node1, data = 10 (-> just one node is added to the list instead of 3 nodes)

The above outputs show that the list.h implementation has bug, at least in one of its function macros.

I don't know where is the bug which we cannot add a node twice in the linked list.

Any idea?! :|

***** EDIT ***** Scenario 3:

    list_add_tail(&node1.mylist, &plist);
    list_add_tail(&node2.mylist, &plist);
    list_add_tail(&node1.mylist, &plist);

    struct Node* iter;

    list_for_each_entry_reverse(iter, &plist, mylist)
    {
        printf("name = %s, data = %d\n", iter->name, iter->data);
    }

output 3:

name = node2, data = 20
name = node1, data = 10
name = node2, data = 20
name = node1, data = 10
name = node2, data = 20
name = node1, data = 10
name = node2, data = 20
name = node1, data = 10
name = node2, data = 20
name = node1, data = 10
... -> non-stopping loop (to infinity)
10
  • 6
    This is not a bug in Linux. It's a bug in your program where you expect that the same piece of memory can appear more than once in a list without creating a cycle. Commented Oct 31, 2019 at 7:12
  • 1
    The next pointer for a single element in the list can only point to one location, but when you add it twice, it needs to point to two different locations at the same time (which it can't do). What you see are side-effects of this intrinsic limitation. Commented Oct 31, 2019 at 7:19
  • 3
    Consider which is more likely — (1) hundreds, if not thousands or millions, of Linux hackers have used the doubly-linked list mechanism without finding the problem that you suddenly came across, but they were all wrong and should have noticed what you found, or (2) you are misusing a well-tested and known-to-work-when-not-abused system. On the whole, I think it's more likely you've made a mistake than that everyone else has. Sorry, but in circumstances similar to this, the chance that everyone else is wrong is slim to negligible. It's almost (but not quite) invariably something you're doing. Commented Oct 31, 2019 at 7:37
  • 1
    You might observe the comments before list_add_tail() in the main implementation you link to first: —— /** * list_add_tail - add a new entry * @new: new entry to be added * @head: list head to add it before * * Insert a new entry before the specified head. * This is useful for implementing queues. */ —— Note the presence of 'new entry' multiple times. Your code is not creating a new entry; it is trying to reuse an existing entry. Commented Oct 31, 2019 at 7:41
  • 1
    I admire your confidence, but remember that hubris leads to nemesis. Commented Oct 31, 2019 at 7:45

1 Answer 1

1

The Linux linked list does not support adding a node more than once. You can't add it twice to the same list, and you can't add it to two different lists.

Sign up to request clarification or add additional context in comments.

4 Comments

is there any macro to make a copy instance?
I accept this answer, also thanks to @JonathanLeffler
@WillyCole You don't need a macro, you can just assign the struct Node value to another struct Node, for example struct Node node1copy = node1; list_add_tail(&node1copy.myList, &plist);. There is no need to do INIT_LIST_HEAD(&node1copy.myList); before adding it to the list, because the pointers in node1copy.myList will be overwritten by list_add_tail anyway.
@IanAbbott this is not permitted in C (that assignment is useful in C++ not in C)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.