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

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

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

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

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).

Linked Lists - Some doubts - Linux

Thread: Linked Lists - Some doubts

LinkBack

Tools

Linked Lists - Some doubts

Re: Linked Lists - Some doubts

Re: Linked Lists - Some doubts

Re: Linked Lists - Some doubts

Re: Linked Lists - Some doubts