Linux Kernel Linked List Explained
(Note: This is a working copy, last updated on April 5th, 2005. Feel free to email your comments.)
Introduction:
Linux kernel is mostly written in the C language. Unlike many other languages C does not have
a good collection of data structures built into it or supported by a collection of standard libraries.
Therefore, you're probably excited to hear that you can borrow a good implementation of a
circularly-linked list in C from the Linux kernel source tree.
The file
include/linux/list.h
in the source tree implements a type oblivious, easy-to-use, circularly-linked list in the C
language. The implementation is efficient and portable-- otherwise it would not have made it
into the kernel. Whenever someone needs a list in the Linux kernel they rely on this
implementation to strung up any data structure they have. With very little modifications
(removing hardware prefetching of list items) we can also use this list in our applications.
A usable version of this file is available
here for download.
Some of the advantages of using this list are:
- Type Oblivious:
This list can be used to strung up any data structure you have in mind.
- Portable:
Though I haven't tried in every platform it is safe to assume the list implementation
is very portable. Otherwise it would not have made it into the kernel source tree.
- Easy to Use:
Since the list is type oblivious same functions are used to initialize, access,
and traverse any list of items strung together using this list implementation.
- Readable:
The macros and inlined functions of the list implementation makes the resulting
code very elegant and readable.
- Saves Time:
Stops you from reinventing the wheel. Using the list really saves a lot of
debugging time and repetitively creating lists for every data structure
you need to link.
Linux implementation of the linked list is different from the many
linked list
implementations you might have seen. Usually a linked list
contains the items that are to be linked. For example:
struct my_list{
void *myitem;
struct my_list *next;
struct my_list *prev;
};
The kernel's implementation of linked list gives the illusion that the
list is contained in the items it links! For example, if you were to
create a linked list of
struct my_cool_list you would do the following:
struct my_cool_list{
struct list_head list; /* kernel's list structure */
int my_cool_data;
void* my_cool_void;
};
Couple of things to note here:
- List is inside the data item you want to link together.
- You can put struct list_head anywhere in your structure.
- You can name struct list_head variable anything you wish.
- You can have multiple lists!
So for example, the declaration below is also a valid one:
struct todo_tasks{
char *task_name;
unsigned int name_len;
short int status;
int sub_tasks;
int subtasks_completed;
struct list_head completed_subtasks;/* list structure */
int subtasks_waiting;
struct list_head waiting_subtasks; /* another list of same or different items! */
struct list_head todo_list; /* list of todo_tasks */
};
Here are some examples of such lists from the kernel:
While we are at this, kernel's list structure is declared as follows in
include/linux/list.h:
struct list_head{
struct list_head *next;
struct list_head *prev;
}
Having said that this is probably a good time to delve into the details.
First let us see how we can use this data structure in our programs. Then,
we will see how the data structure actually works.
Using the List:
I think the best way to get familiar with the list functions is to simply scan
the file for them.
The file is well commented so there should not be any trouble understanding what is available to
a user.
Here is an example of creating, adding, deleting, and traversing the list. You can download the source
code
here.
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
struct kool_list{
int to;
struct list_head list;
int from;
};
int main(int argc, char **argv){
struct kool_list *tmp;
struct list_head *pos, *q;
unsigned int i;
struct kool_list mylist;
INIT_LIST_HEAD(&mylist.list);
/* or you could have declared this with the following macro
* LIST_HEAD(mylist); which declares and initializes the list
*/
/* adding elements to mylist */
for(i=5; i!=0; --i){
tmp= (struct kool_list *)malloc(sizeof(struct kool_list));
/* INIT_LIST_HEAD(&tmp->list);
*
* this initializes a dynamically allocated list_head. we
* you can omit this if subsequent call is add_list() or
* anything along that line because the next, prev
* fields get initialized in those functions.
*/
printf("enter to and from:");
scanf("%d %d", &tmp->to, &tmp->from);
/* add the new item 'tmp' to the list of items in mylist */
list_add(&(tmp->list), &(mylist.list));
/* you can also use list_add_tail() which adds new items to
* the tail end of the list
*/
}
printf("\n");
/* now you have a circularly linked list of items of type struct kool_list.
* now let us go through the items and print them out
*/
/* list_for_each() is a macro for a for loop.
* first parameter is used as the counter in for loop. in other words, inside the
* loop it points to the current item's list_head.
* second parameter is the pointer to the list. it is not manipulated by the macro.
*/
printf("traversing the list using list_for_each()\n");
list_for_each(pos, &mylist.list){
/* at this point: pos->next points to the next item's 'list' variable and
* pos->prev points to the previous item's 'list' variable. Here item is
* of type struct kool_list. But we need to access the item itself not the
* variable 'list' in the item! macro list_entry() does just that. See "How
* does this work?" below for an explanation of how this is done.
*/
tmp= list_entry(pos, struct kool_list, list);
/* given a pointer to struct list_head, type of data structure it is part of,
* and it's name (struct list_head's name in the data structure) it returns a
* pointer to the data structure in which the pointer is part of.
* For example, in the above line list_entry() will return a pointer to the
* struct kool_list item it is embedded in!
*/
printf("to= %d from= %d\n", tmp->to, tmp->from);
}
printf("\n");
/* since this is a circularly linked list. you can traverse the list in reverse order
* as well. all you need to do is replace 'list_for_each' with 'list_for_each_prev'
* everything else remain the same!
*
* Also you can traverse the list using list_for_each_entry() to iterate over a given
* type of entries. For example:
*/
printf("traversing the list using list_for_each_entry()\n");
list_for_each_entry(tmp, &mylist.list, list)
printf("to= %d from= %d\n", tmp->to, tmp->from);
printf("\n");
/* now let's be good and free the kool_list items. since we will be removing items
* off the list using list_del() we need to use a safer version of the list_for_each()
* macro aptly named list_for_each_safe(). Note that you MUST use this macro if the loop
* involves deletions of items (or moving items from one list to another).
*/
printf("deleting the list using list_for_each_safe()\n");
list_for_each_safe(pos, q, &mylist.list){
tmp= list_entry(pos, struct kool_list, list);
printf("freeing item to= %d from= %d\n", tmp->to, tmp->from);
list_del(pos);
free(tmp);
}
return 0;
}
How Does This Work?
Well most of the implementation is quite trivial but finesse. The finesse relies on the fact that
somehow we can obtain the address of an item that contains the list (struct list_head list) given
the pointer to the list. This trick is done by the
list_entry() macro as we saw above. Let
us now understand what it does.
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
Macro expansion for the above example is as follows:
((struct kool_list *)((char *)(pos) - (unsigned long)(&((struct kool_list *)0)->list)))
This is what confuses most people but it is quite simple and a
well-known technique (See Question 2.14). Given a pointer to
struct list_head in a data structure, macro
list_entry() simply computes the pointer
of
the data structure. To achieve this we need to figure out where in the
data structure the list_head is (offset of list_head). Then, simply
deduct the list_head's offset from the actual pointer passed to the
macro.
Now the question is how can we compute the offset of an element in a structure? Suppose you have a data structure
struct foo_bar and you want to find the offset of element
boo in it, this is how you do it:
(unsigned long)(&((struct foo_bar *)0)->boo)
Take memory address 0, and cast it to whatever the type of structure you have-- in this case
struct foo_bar.
Then, take the address of the member you're interested in. This gives
the offset of the member within the structure. Since we already know
the absolute memory address of this element for a particular instance
of the structure (for example, by way of
pos) deducting this
offset points us to the address of the structure itself. That's all
there is to it. To get a better handle on this I suggest you play
around with this
piece of code.
#include <stdio.h>
#include <stdlib.h>
struct foobar{
unsigned int foo;
char bar;
char boo;
};
int main(int argc, char** argv){
struct foobar tmp;
printf("address of &tmp is= %p\n\n", &tmp);
printf("address of tmp->foo= %p \t offset of tmp->foo= %lu\n", &tmp.foo, (unsigned long) &((struct foobar *)0)->foo);
printf("address of tmp->bar= %p \t offset of tmp->bar= %lu\n", &tmp.bar, (unsigned long) &((struct foobar *)0)->bar);
printf("address of tmp->boo= %p \t offset of tmp->boo= %lu\n\n", &tmp.boo, (unsigned long) &((struct foobar *)0)->boo);
printf("computed address of &tmp using:\n");
printf("\taddress and offset of tmp->foo= %p\n",
(struct foobar *) (((char *) &tmp.foo) - ((unsigned long) &((struct foobar *)0)->foo)));
printf("\taddress and offset of tmp->bar= %p\n",
(struct foobar *) (((char *) &tmp.bar) - ((unsigned long) &((struct foobar *)0)->bar)));
printf("\taddress and offset of tmp->boo= %p\n",
(struct foobar *) (((char *) &tmp.boo) - ((unsigned long) &((struct foobar *)0)->boo)));
return 0;
}
Output from this code is:
address of &tmp is= 0xbfffed00
address of tmp->foo= 0xbfffed00 offset of tmp->foo= 0
address of tmp->bar= 0xbfffed04 offset of tmp->bar= 4
address of tmp->boo= 0xbfffed05 offset of tmp->boo= 5
computed address of &tmp using:
address and offset of tmp->foo= 0xbfffed00
address and offset of tmp->bar= 0xbfffed00
address and offset of tmp->boo= 0xbfffed00
See Also
- Please also have a look at the hash table that uses the linked list.
- /sutff/src/ for more source code
TODO
- Figure to explain list_entry() better
- Post the C Data Structures Library (CDSL) that contains hashtables, maps etc. for peer review. Think of it as the Java.Util for C. Clean syntax, prepackaged data structures to make your C life easy!
출처 : http://isis.poly.edu/kulesh/stuff/src/klist/
memory barrier는 execution
memory barrier는 execution ordering을 보장하기 위한 것이지요.
execution reordering은 컴파일러 최적화에 의해서 일어날 수 도 있고,
CPU의 execute queue(정확한 용어인지...-_-;;)에서 발생할 수 있기 때문에
이것을 사용하는 것이라고 알고 있습니다.
제가 테스트해본 경험에 의하면, 컴파일러의 경우 최적화가 아무리 높더라도,
코드내부에 asm과 같은 어셈블러 코드가 들어가면, 절대로 reordering을 하지 않았고,
reordering이 걱정되는 경우에는 강제로 dependency를 만들어서 코딩하는 경우도 있습니다.
코드에서
A struct task_struct *old = parent;
/*
* Make sure we read the pid before re-reading the
* parent pointer:
*/
B smp_rmb();
C parent = me->group_leader->real_parent;
D if (old != parent)
continue;
에서 A와 C의 순서를 강제로 보장하는 것인데,
만일 C->A의 순서대로 수행이 된다고 생각해 보십시요.
D의 수행결과가 엉망이 되겠지요.
왜 이런 코드가 생기는가는 A라인이 특성 때문입니다.
컴파일러 최적화는 논리적으로는 라인과 라인 물리적으로는 opcode block과 opcode block간의
dependency가 없고, reordering에 의해서 수행비용이 낮아질 수 있다면 무조건 순서를 바꿉니다.
혹은 CPU도 opcode간의 비용계산을 통해 수행순서를 바꾸지요.
애석하게도 위의 A는 C와 아무런 의존관계가 없기 때문에 이러한 현상이 나타날 수 있습니다.
사람의 생각으로는 이전의 parent값을 가져오는 논리적인 의존관계가 있지만,
컴파일러나 CPU입장에서는 단지 임시값을 저장하는 A의 코드를 의존관계를 보지 않지요.
물론, 사람은 D의 라인을 통해 이전의 값과 최신값을 비교하는 기능을 하고 싶은 것이지만,
컴파일러나 CPU는 그렇지 않다는데 문제가 있습니다.
사실 이런 문제를 코딩할 때 제대로 catch하기는 상당히 힘듭니다.
제가 몸담고 있는 회사의 경우에도 설계/구현시에는 아무런 문제가 없었다가,
IBM p690이라는 CPU 32개의 기계에서 memory barrier관련 문제가 발생하여서,
상당히 혼난적이 있습니다.
경험으로는 위의 코드는 강제로 depencency를 주어서 해결하기도 하였지만,
100% 보장은 못하겠습니다.
int a = 0;
if (a++ == 0)
{
execution A;
}
if (a++ == 1)
{
execution B;
}
이렇게 해결한 적도 있습니다만..쩝.
김성진
고도의 추상화, 극도의 구체화, 에디슨을 그리워하다.
그런데 코멘트를 보게 되면
설명 감사드립니다.
그런데 코드 안의 아래 코멘트를 참조하면
Make sure we read the pid before re-reading the parent pointer
old 보다는 pid 를 읽는게 실질적인 이유인것 같은데 어떻게 생각하시는지요 ?
rmb 는 read간의 순서를 맞춰주기 위한 barrier 입니다.
rmb, smp_rmb 모두 read memory barrier로, barrier위의 read가 끝난 뒤, barrier 아래의 read를 수행하라는 내용입니다.
두 read간의 순서가 어긋날 수 있는 것은 위의 김성진님이 말씀하신 것처럼, compiler의 optimization에 의해 일어날 수도 있고, cpu에서 최적화하는 과정에서 일어날 수도 있습니다. 물론 rmb 는 이 둘 모두를 막아주는 것이지요.
위의 내용은 맨 윗줄의 주석에 보니, real_parent라는 값 자체가 다른 cpu에 의해 변할 수 있는 값이라고 나오는군요. 따라서 정확한 값을 읽으려면 spinlock 을 사용하면 되겠지만, optimistic한 알고리즘을 써서 그냥 좀 비정확하더라도 spinlock overhead를 줄이겠다는 것이지요.
따라서 약간의 텀을 두고 real_parent를 두번 읽은 다음, 두번 사이에 변하지 않았다면 그게 맞는 거다 라고 생각하겠다 라는 것인듯 합니다. 그리고 그 두번의 텀을 주기 위해(라면 좀 이상할 수도 있겠지만. 여튼) real_parent의 pid를 먼저 읽고 그 뒤에 다시 real_parent를 읽겠다는 것입니다. 그리고 그 두 read간의 순서를 보장하기 위해 smp_rmb를 사용했다. 라고 생각하시면 될 듯 합니다.
이 코드의 효과를 잘 모르겠네요.
컴파일러가 barrier 없이 만들 수 있는 최악의 코드는
temp = me->group_leader->real_parent;
*old = parent;
parent = temp;
이정도로 보입니다.
barrier가 있다면 현재 소스 코드 형태로 코드가 생성되는 걸 보장할 수 있겠죠.
그래봐야 최악의 경우랑 비교해볼 때 old와 parent 값을 구하는 사이에 시간이 살짝 (인스트럭션 몇개 수행하는 시간 정도) 차이가 나니. 당연히 그사이에 값이 바뀔 확률이 높아 지는 건 맞는 것 같아보입니다.
아는 것만큼 보인다고 저게 뭔 효과가 명확하게 있나 모르겠네요.
고수님들 있고 없고의 차이와 성능에 대해 설명 좀 부탁드립니다.
그리고 #ifdef로 SMB와 PREEMPT가 있던데 왜 이 경우에 해당하는지도 설명해주시면 좋겠네요.
커널 소스는 참 어렵네요.
컴파일러가 더욱
컴파일러가 더욱 바람직하지 않은 코드를 만들 수도 있습니다. 커널 소스의 경우 기본적으로 -O2 최적화가 이뤄지는데, 위 코드에서 smb_rmb() (내지는 barrier())가 없는 경우 컴파일러는 parent 변수의 값이 항상 동일할 것이라고 판단하여 "if defined(CONFIG_SMP) || defined(CONFIG_PREEMPT)" 내의 코드를 모두 생략해 버릴 수 있습니다. 타이밍 내지는 확률 정도의 문제가 아닌 게 되는 거죠. :-)
SMP와 PREEMPT의 의미는...
위 코드의 "if defined ..." 안에 있는 내용은 위 코드의 일부가 실행된 상태에서 me->group_leader->real_parent의 값을 바꿔버리는 다른 코드(가령, kernel/exit.c의 forget_original_parent())가 실행되는 경우에 발생할 수 있는 문제(반환되는 pid 값이 유효하지 않은 값이 되는 것)에 대처하기 위한 것입니다. 그런 경우는 크게 두 가지가 있습니다. 다른 코드가 이웃 CPU에서 동시에 실행되는 경우와, 실행 도중에 이 코드를 다른 코드가 선점하는 경우입니다. 각각 CONFIG_SMP와 CONFIG_PREEMPT에 대응하게 됩니다.
& 그나저나... 위 코드가 어느 버전의 코드인지는 모르겠지만, 최근 버전에서는 rcu를 이용해서 훨씬 단순하게 바뀌었나 보군요.
----
$PWD `date`
깔끔한 답변
깔끔한 답변 감사합니다.
컴파일러 입장에서는 값이 바뀌는 경우가 없으니 for loop 밖에서 구한 me->goup_leader->real_parent의 값을 for loop안에서 그대로 이용하겠네요.
더 최적화한다면 똑같은 값을 parent에 넣는 거니 의미 없는 코드로 생각해 삭제해도 전혀 문제가 되지 않는 군요.
이런 건 정말 사람 눈에 보이지 않겠습니다.
컴파일러가 warning을 발생이라도 시켠 준단 몰라도 사람이 판단해기는 어렵겠네요.
코드에 워닝 나는 거 대충 생까주고 있는데, 낼부터 조심해서 봐야겠습니다.
아무리 compiler가 ILP
아무리 compiler가 ILP 최적화를 수행하고, processor에서 reorder 한다고 해도 위코드는 말씀하신대로 reorder 되지는 않습니다.
===========================================
A: pid = temp;
B: old = temp;
C: temp = me->group_leader->real_parent;
===========================================
A,B와 C와의 관계는 ANTI-depedency 관계에 있기 때문에 일반적인 방법으로 reorder 할수 없습니다.
ANTI-dependency와 같은 false depedency는 register renameing과 같은 방법을 쓰면 reorder 할수 있습니다.
그리고 이때는 renaming 했기 때문에 reorder해도 아무 문제가 없기 때문에 질문하신분의 내용과는 크게 관계 없을듯 합니다.
때문에 굳이 smp_rmb()를 넣은 이유를 들라면 molla님께서 잘 설명해주셨듯이
spinlock을 동기화 해야 될 부분을 real_parent의 값을 두번읽어봄으로써 spinlock을
안쓰고 overheader 줄이려고 했고 이때 wariua님 말대로 이전에 읽은 parent를 보장하기 위해
smp_rmb()를 넣은 것입니다.
쓰신 내용에 제가
쓰신 내용에 제가 모르는 내용이 많아서 몇가지 검색하면서 새로운 것들 많이 배웠습니다.
Processor Reordering이 뭔지 어떻게 되나 알수가 없었는데, Out-of-Order Processor라는 게 있더군요.
인스트럭션을 큐에다 집어넣고, 인스트럭션의 operand가 가용할 때까지 기다렸다고 수행해서 메모리에서 로드될 때까지 기다리는 시간을 줄이는 방법이더군요.
상세히는 모르겟지만 대충 감은 잡히더군요.
그런데 이런 의문이 들더군요.
고수님들은 Processor의 이런 기능까지 고려해서 코드를 작성합니까?
어셈블러가 아닌 C 언어에서도 이 기능들을 이용한 최적화가 가능합니까?
저로서는 도저히 감이 안 잡힙니다. 혹 이런 원칙이 있으면 알려주세요.
적다 보니 살짝 한심한 생각이 드네요.
N^2이니 NlogN 같은 루프 수행 회수나 확실히 줄이고, 그 다음에 몇 clock 줄이는 방법 고민해야지.
걷지도 못하는 주제에 뛸려고 하는 것 같습니다.
그래도 요런게 신기하고 또 재미는 있네요.
이런 놈들 때문에 클럭 단위의 수행 시간 계산은 거의 불가능하네요.
cache hit에다가 instruction도 순서대로 수행 안 될 수도 있으니.. 참 복잡하고 경이로운 세상입니다.
엔지니어링의 마지막은 최적화인가 봅니다.
수많은 패러미터들 위에서 최적 방법을 찾는 건 정말 Art입니다.
일반적으로
일반적으로 application을 개발할때는 고려하지 않습니다.
사실 이런류의 architecture 최적화는 들이는 노력에 비해 얻는것이 크지 않기 때문입니다.
그 보다는 알고리즘 level 또는 자료구조를 잘 설계하기 위해 노력합니다.
하지만 OS, compiler와 같은 system level 프로그래밍을 하거나 codec과 같은 성능에 민감한 프로그래밍을 할때는 고려를 합니다.
compiler의 경우 compiler 자체 source code에서는 고려하지 않고 compiler가 생성하는 code에 대해서는 모두 이런 특징을 고려하고 있습니다.
OS와 같은 경우에는 linux kernel source에서 보신봐와 같이 c level에서 어떻게 assembly code가 생성될지... 그리고 그 assembly code가 architecture 특징에 따라 어떻게 scheduling 될지에 따라 최적화 되고 안되고의 문제를 떠나 정상적으로 수행될지 안될지의 문제가 생기기 때문에 항상 c 소스를 코딩하면서 머리속으로 컴파일 하고 scheduling 하면서 코딩을 합니다. 그렇지 않으면 이런류의 오류는 쉽게 발견되기도 힘들고 큰 사고로 연결될수 있기 때문입니다.
그리고 c level에서 이렇게 생각할수 있는건 어느 정도의 compiler 지식과, architecture 지식을 가지고 습관적으로 연습하면 어렵지 않게 할수 있습니다.
codec 같은 경우에는 이정도까지 고려는 하지 않고 SIMD와 DMA 쓰는것 정도로 고려를 하는것 같습니다. codec 하시는 분들은 대부분 architecture나 compiler에 대해서는 깊게 모르시더군요. 하지만 워낙 성능에 민감한 프로그램이라서 architecture에서 제공해주는 최적화 기능들을 사용하려고 노력하는것 같았습니다.
결국 일반적인 application을 작성할때는 고려를 하면 좋지만 굳이 그럴필요까지는 없다고 생각합니다. processor나 compiler에 맞겨버리면 되는 문제라는 생각이 듭니다. 하지만 처음부터 고려를 하는것이 목적인 프로그램을 작성하시거나, 고려하지 않으면 문제가 발생할수 있는 프로그래밍을 하실때는 그때는 심각하게 고려를 해야겠지요.
parent구하기와 pid구하기를 atomic하게 실행할 수 없기 때문
아래 두 statement를 atomic하게 실행할 수 없기 때문이라고 봅니다.
parent = me->group_leader->real_parent;
pid = parent->tgid;
위의 두 statement를 실행하는 동안 real_parent가 바뀔 수도 있고 결과적으로 parent의 pid도 바뀔 수 있습니다(SMP, preemptive환경에서).
이를 막기 위해 두 statement의 앞뒤로 lock 쓸 수 있으나 그럴 경우 성능이 떨어지기 때문에 안쓴겁니다.
대신에 아래와 같이 parent 포인터 구하기를 두 번 실행하고
parent = me->group_leader->real_parent;
pid = parent->tgid;
parent = me->group_leader->real_parent;
그 두 parent 포인터가 변하지 않았다면 처음 두 statement를 실행하는 동안 real_parent가 변하지 않았다는 것을 입증할 수 있습니다.
그러나 instruction reordering에 의해 pid구하기가 두 번의 parent 포인터 구하기 사이에 실행되지 않고 그 후에 실행된다면 real_parent가 변하지 않았다는 것을 입증할 수 없습니다.
이를 방지하기 위해 memory barrier를 사용한 것으로 보입니다.
/***************************************
Being the one is just like being in love.
***************************************/