Linked Lists - Some doubts - Linux

This is a discussion on Linked Lists - Some doubts - Linux ; Hi, I'm working on a kernel module and I have some doubts about kernel implementation of Linked Lists.. I've read Linux Kernel Development (Robert Love) and there the author says that if you need a linked list you should use ...

+ Reply to Thread
Results 1 to 5 of 5

Thread: Linked Lists - Some doubts

  1. Linked Lists - Some doubts

    Hi, I'm working on a kernel module and I have some doubts about kernel
    implementation of Linked Lists.. I've read Linux Kernel Development
    (Robert Love) and there the author says that if you need a linked list
    you should use the implementation provided by the kernel.. The problem
    is that there is
    something that I don't understand (or perhaps, I've understood
    "everything" but there is something that seems quite strange to me).

    R.Love says (pag.347, I give the page reference for those ones who have
    the book) that Linux Linked Lists are implemented in such a way that:

    1) There is no need for an head pointer and
    2) You can start traversing the list from which element you want.

    These two points sound quite strange to me.. Usually the list is used
    in this way:

    struct kool_list{
    struct list_head list;
    int data;
    };

    struct kool_list mylist;
    mylist.data = -1
    INIT_LIST_HEAD(&mylist.list);

    for(i=0; i < 5; i++){
    tmp= (struct kool_list *)kmalloc(sizeof(struct
    kool_list), GFP_KERNEL);
    tmp->data = i;
    list_add(&(tmp->list), &(mylist.list));
    }

    list_for_each(pos, &mylist.list){
    tmp = list_entry(pos, struct kool_list, list);
    printk("%d ", tmp->data);
    }


    1) you don't need an head pointer, but you waste an entire head
    structure, mylist, which is used as pointer to the list and which is
    passed to the list_for_each function to traverse the entire list.

    2) you must start from mylist when traversing the list with
    list_for_each.. the code above prints all the data in the list, "0, 1,
    2, 3, 4," because you start from mylist, but if you start from the
    structure that contains "3" for example, the list_for_each block
    above prints "4, -1, 0, 1, 2,", which is not what we want because
    it prints also "-1" and doesn't print 3..

    I need a linked list to manage data related to stations in a wireless
    network, and I'd like to be able to travel the entire list starting
    from every element in the list, including the element itself and
    avoiding the element used as head of the list (mylist in the above
    code).. It would be sufficient to add a flag in the data structure
    that tells if the data structure is the one used as head or if it
    contains useful data, but perhaps there is a better way to do that..

    I don't understand if there is something that I'm missing, perhaps you
    can explain me what is wrong in the above discussion.


    PS: I hope I've been quite clear.

    Thank you in advance for any suggestion you will give me,
    Gianni


  2. Re: Linked Lists - Some doubts

    On Mon, 24 Jul 2006 09:20:30 -0700, Slaytanic wrote:

    > R.Love says (pag.347, I give the page reference for those ones who have
    > the book) that Linux Linked Lists are implemented in such a way that:
    >
    > 1) There is no need for an head pointer and 2) You can start traversing
    > the list from which element you want.

    A, hopefully, qualified guess:-)
    1) The kernel knows the exact size of the entire list at any time.
    2) The kernel ensures that the entire list is placed in a contiguous place
    in memory.
    3) The kernel knows the exact size of each element in the list.

    Given the above idioms the two statements make sense.
    Elem* seek(struct List* list, int i)
    {
    if ((list + (sizeof(Elem) * i)) > end_adress(list))
    return seek(list, (list + (sizeof(Elem) * i) - end_adress(list));
    if ((list + (sizeof(Elem) * i)) < list)
    return seek(list, (end_adress(list) - list + (sizeof(Elem) * i));
    return
    (Elem*) ((list + (sizeof(Elem)) * i)));
    }

    Not tested!

    --
    Hilsen/Regards
    Michael Rasmussen
    http://keyserver.veridis.com:11371/p...rch=0xE3E80917


  3. Re: Linked Lists - Some doubts


    Michael Rasmussen wrote:
    > On Mon, 24 Jul 2006 09:20:30 -0700, Slaytanic wrote:
    >
    > > R.Love says (pag.347, I give the page reference for those ones who have
    > > the book) that Linux Linked Lists are implemented in such a way that:
    > >
    > > 1) There is no need for an head pointer and 2) You can start traversing
    > > the list from which element you want.

    > A, hopefully, qualified guess:-)
    > 1) The kernel knows the exact size of the entire list at any time.
    > 2) The kernel ensures that the entire list is placed in a contiguous place
    > in memory.


    Kernel does not place the entire list in a contiguous place, each
    element is linked through pointers and each element can be at different
    memory addresses (YOU kmalloc the element and then add it to a linked
    list, so it's at the position decided by kmalloc).. Just think that a
    single element can be placed in multiple lists, so it would be
    impossible to place all the elements contiguously in memory.

    BTW, thank you for the answer


  4. Re: Linked Lists - Some doubts

    On Mon, 24 Jul 2006 10:27:27 -0700, Slaytanic wrote:

    >
    > Kernel does not place the entire list in a contiguous place, each element
    > is linked through pointers and each element can be at different memory
    > addresses (YOU kmalloc the element and then add it to a linked list, so
    > it's at the position decided by kmalloc).. Just think that a single
    > element can be placed in multiple lists, so it would be impossible to
    > place all the elements contiguously in memory.
    >

    Pages in memory are off-course scattered around, but logically the could
    be connected as a contiguous chunk of memory. This is one of the ways the
    kernel solves applications need of contiguous memory when it is not
    physical possible.

    --
    Hilsen/Regards
    Michael Rasmussen
    http://keyserver.veridis.com:11371/p...rch=0xE3E80917


  5. Re: Linked Lists - Some doubts


    Michael Rasmussen ha scritto:

    > Pages in memory are off-course scattered around, but logically the could
    > be connected as a contiguous chunk of memory. This is one of the ways the
    > kernel solves applications need of contiguous memory when it is not
    > physical possible.
    >


    I understand what you say.. but the problem is, as said before, this:
    you kmalloc a piece of memory for structure A, then you kmalloc another
    piece for structure B and at this point they can be placed at different
    addresses in both physical and virtual memory. Then you decide to put
    both A and B in the same list: the kernel does not remap the memory in
    order to make A and B data structures contiguous. So, linked lists
    elements are not contiguous in memory (otherwise there would not be the
    need of having forward and backward pointers as the kernel linked lists
    do).


+ Reply to Thread