커널 API 에는 편리한 함수들이 많이 있다.

오늘은 그중에  linked list 를 소개하고자 한다.

기본적으로 모두 double linked list 라는 것을 기억하자.

커널디렉토리를 보면 include/linux/list.h 파일이 있다.

거의 대부분 매크로의 조합이다.

하지만 역시 자주쓰는 것들은 정해져 있다.

LIST_HEAD(name)

list_add(new, head)

list_add_tail(new, head)

list_del(entry)

list_empty(head)

위의 다섯가지가 기본적인 다섯가지이다.

이름에서 보듯이 매우 쉽다.

INIT_LIST_HEAD(ptr)  :  리스트 자료구조를 초기화함

list_add(new, head)          :  이전에 만든  리스트에 새로운 리스트를 하나 추가(맨앞으로 들어간다)

list_add_tail(new, head)   :  이전에 만든 리스트의 맨뒤에 리스트를 하나 추가

list_del(entry)                  :   원하는 리스트를 삭제해준다.

list_empty(head)             :   헛갈리지 마세요 비어 있으면 참이다(본인도 항상 착각합니다)

여기까지는 매우 평이합니다.

하지만 리스트를 만들었다는 것은 무언가 자료를 찾기 위한 것입니다.

리스트안에 있는 entry를 찾는 함수를 보겠습니다.

#define    list_entry(ptr, type, member)   container_of(ptr, type, member) 

네... 이번엔 뭔가 좀 다릅니다. container_of  매크로가 나왔습니다.

이 설명을 위해서 하나의 구조체를 선언하겠습니다.

struct data_list {

      int    a;

      int    b;

     struct list_head list;

}

struct data_list mylist;

INIT_LIST_HEAD(&mylist.list);       초기화를 수행합니다.

list_add(new, mylist)                            5개의 entry를 추가합니다.

이 리스트에서 data_list 를 하나 꺼내기를 원합니다.

struct data_list   *d;

    d = list_entry(&mylist.next, struct data_list, list) 와 같이 했을때

    d 에는 list_add 를 통해 저장된 첫번째 리스트 자료구조의 포인터를 얻게 됩니다.

이번에는 list_for_each 입니다.

이 매트로는 리스트를 쭉 돌면서 내가 원하는 하나의 리스트를 찾고자 할때 사용합니다.

즉  mylist 에 a 의 값이 100 이상인 녀석을 찾으려고 합니다.

struct list_head *entry;

struct data_list *target;

   list_for_each(entry, &mylist) {

           target = list_entry(entry, struct data_list, list);

           if(target->a  > 100) {

                       ok....  찾았습니다.

           }

    }

위의 예에서 처럼 보통 list_for_each 는 list_entry 와 조합을 이루어 사용하면 쉽습니다.

list_for_each는 mylist 에서 처음부터 끝까지 순방향으로 서치를 합니다.

list_for_each_prev 가 있는데 이것은 용법은 동일하지만 역방향으로 서치를 합니다.

리스트의 사용에 있어서 주의할 점이 있습니다.

바로 자료의 보호에 관한 것입니다.

기본적으로   위에 설명한 자료들에 대한 보호가 되지 않는다는 것입니다.

이러한 해결을 위해서 safe 라는 이름이 들어가는  매크로를 제공하는데

이것은 사용하려고 하는 entry 의 복사본을 사용함으로써 수행시 해당 자료가

삭제되더라도 오류가 나지 않게 하는 것입니다만 저는 이것을 권하지 않습니다.

저는 모든 list 와 관련된 매크로를 별도로 만들고 보호가 필요한 자료를 위해서는

모두 lock  을 이용해 보호합니다.(경험상 확실한 방법을 택합니다.)

마지막으로 누구나 이런 링크드 리스트를 순회하며 서치하는 함수를 만들수 있습니다.

그러나 커널에는 또한가지의 적절한 지원이 있습니다.

그것을  prefetch 를 통한 효율적인 수행입니다.

기본적으로 루프를 돌면서 행하는 작업이기 때문에 수행에 부담이 되게 됩니다.

하지만 list_for_each 의 원형으로 찾아 보시면 

   for (pos = (head)->next; prefetch(pos->next), pos != (head);  pos = pos->next)

와 같이 되어 있습니다.

모든 아키텍쳐에서 지원하는 것은 아니고 arm에서는 armv5 에서만 지원되는 것입니다.

이것은 하나이상의 인스트럭션을 가져와서 수행속도에 도움이 되게 하는 것입니다.

운이 좋다면 직접 만드는 것보다 더 나은 수행속도를 기대할수 있습니다.