CODEWITHSUNDEEP
clinuxlinked-listlinux-kernel
Willy Cole
Willy Cole

Reputation: 144

Adding element twice into Linux kernel double linked list

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)

Upvotes: 0

Views: 703

Answers (1)

Stack Exchange Broke The Law
Stack Exchange Broke The Law

Reputation: 58888

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.

Upvotes: 1

Related Questions