Linked Lists in Linux

Linux linked list 소개

SPDX 라이선스 식별자: GPL-2.0+

Linux의 linked list (Linked Lists in Linux)

저자: Nicolas Frattaroli <nicolas.frattaroli@collabora.com>

이 페이지에는 contents directive가 있습니다.

Linked list는 많은 program에서 사용하는 가장 기본적인 data structure 중 하나입니다. Linux kernel은 여러 종류의 linked list를 구현합니다. 이 문서는 linked list 일반 이론이 아니라 새 kernel developer가 Linux kernel 구현을 사용하는 방법을 설명합니다.

Linked list가 널리 쓰이기는 하지만 단순한 array로 충분하지 않은 경우에도 최선의 data structure인 때는 드뭅니다. 특히 data locality가 좋지 않으므로 performance가 중요할 때는 나쁜 선택입니다. Concurrent access가 관련된 경우를 포함해 kernel의 다른 generic data structure도 익히기를 적극 권장합니다.

Linux doubly linked list

Linux의 doubly linked list 구현

Linux linked list 구현은 `<linux/list.h>` header file을 include하여 사용할 수 있습니다.

Doubly-linked list는 앞뒤 방향으로 효율적으로 순회할 수 있는 익숙한 형태입니다. Linux kernel의 doubly-linked list는 circular 구조이므로 head node에서 edge 하나를 뒤로 이동하면 tail에 닿고, tail에서 앞으로 더 이동하면 head로 돌아옵니다.

node 선언

Doubly-linked list의 node는 list에 포함할 data structure에 `struct list_head` member를 추가하여 선언합니다.

.. code-block:: c

  struct clown {
          unsigned long long shoe_size;
          const char *name;
          struct list_head node;  /* the aforementioned member */
  };

전통적인 설명은 previous/next node pointer와 payload를 한 list node structure에 두지만 Linux는 payload structure 안에 `struct list_head`를 embedded합니다. 이 방식은 list에 담긴 data type과 무관하게 generic modification code를 사용할 수 있게 합니다.

`struct list_head` member는 pointer가 아니라 structure 자체의 일부이므로 list 구현은 `container_of()` pattern으로 실제 type을 몰라도 payload data에 접근할 수 있습니다.

list 선언과 초기화

Doubly-linked list 자체도 `struct list_head`로 선언합니다. 최초 assignment에서는 `LIST_HEAD_INIT()` macro로, 이후에는 `INIT_LIST_HEAD()` function으로 초기화합니다.

.. code-block:: c

  struct clown_car {
          int tyre_pressure[4];
          struct list_head clowns;        /* Looks like a node! */
  };

  /* ... Somewhere later in our driver ... */

  static int circus_init(struct circus_priv *circus)
  {
          struct clown_car other_car = {
                .tyre_pressure = {10, 12, 11, 9},
                .clowns = LIST_HEAD_INIT(other_car.clowns)
          };

          INIT_LIST_HEAD(&circus->car.clowns);

          return 0;
  }

List 자체에 별도의 type이 없다는 점이 혼동될 수 있습니다. 전체 linked list라는 개념과 다른 entry를 가리키는 `struct list_head` member는 같은 표현을 사용합니다.

head 뒤에 node 추가

Linked list에 node를 추가할 때는 `list_add()` macro를 사용합니다. 다음 clown car 예제는 Grock과 Dimitri를 차례로 list head 뒤에 넣습니다.

.. code-block:: c

  static int circus_fill_car(struct circus_priv *circus)
  {
          struct clown_car *car = &circus->car;
          struct clown *grock;
          struct clown *dimitri;

          /* State 1 */

          grock = kzalloc(sizeof(*grock), GFP_KERNEL);
          if (!grock)
                  return -ENOMEM;
          grock->name = "Grock";
          grock->shoe_size = 1000;

          /* Note that we're adding the "node" member */
          list_add(&grock->node, &car->clowns);

          /* State 2 */

          dimitri = kzalloc(sizeof(*dimitri), GFP_KERNEL);
          if (!dimitri)
                  return -ENOMEM;
          dimitri->name = "Dimitri";
          dimitri->shoe_size = 50;

          list_add(&dimitri->node, &car->clowns);

          /* State 3 */

          return 0;
  }

State 1에서는 clown list가 비어 있고 head가 자신을 가리킵니다.

State 2에서는 list head 바로 뒤에 Grock을 추가했습니다. Grock의 다음 edge는 다시 `clowns` head로 돌아갑니다.

State 3에서는 Dimitri를 다시 head 뒤에 추가했으므로 순서는 `clowns`, Dimitri, Grock이 됩니다.

tail에 node 추가

Dimitri를 list 끝에 넣으려면 `list_add_tail()`을 사용합니다.

.. code-block:: c

  static int circus_fill_car(struct circus_priv *circus)
  {
          /* ... */

          list_add_tail(&dimitri->node, &car->clowns);

          /* State 3b */

          return 0;
  }

그 결과 Grock 뒤에 Dimitri가 오고 Dimitri의 다음 edge가 `clowns` head로 돌아갑니다.

list 순회

`list_for_each()`로 list의 모든 node를 순회할 수 있습니다. 다만 cursor가 `struct list_head`이므로 payload를 얻기 위해 `list_entry()`를 호출해야 합니다.

.. code-block:: c

  static unsigned long long circus_get_max_shoe_size(struct circus_priv *circus)
  {
          unsigned long long res = 0;
          struct clown *e;
          struct list_head *cur;

          list_for_each(cur, &circus->car.clowns) {
                  e = list_entry(cur, struct clown, node);
                  if (e->shoe_size > res)
                          res = e->shoe_size;
          }

          return res;
  }

`list_entry()`는 내부에서 `container_of()`를 사용해 `node`가 속한 data structure instance를 찾습니다. 실제로 순회하려는 것은 node가 아니라 이를 포함하는 `struct clown` payload이므로 이 추가 변환은 다소 번거롭습니다.

`list_for_each_entry()`를 사용하면 payload type의 cursor로 직접 순회할 수 있습니다.

.. code-block:: c

  static unsigned long long circus_get_max_shoe_size(struct circus_priv *circus)
  {
          unsigned long long res = 0;
          struct clown *e;

          list_for_each_entry(e, &circus->car.clowns, node) {
                  if (e->shoe_size > res)
                          res = e->shoe_size;
          }

          return res;
  }

이 macro에는 clown structure 안에서 list의 `struct list_head`에 해당하는 member name을 전달하므로 `list_entry()` 단계 없이도 list를 이동할 수 있습니다.

node 제거와 재초기화

`list_del()`은 entry를 list에서 제거하고 `prev` 및 `next` pointer를 poison value로 바꿉니다. 따라서 제거한 entry를 의도치 않게 다시 사용하면 조용히 넘어가지 않습니다.

.. code-block:: c

  static int circus_fill_car(struct circus_priv *circus)
  {
          /* ... */

          list_add(&dimitri->node, &car->clowns);

          /* State 3 */

          list_del(&dimitri->node);

          /* State 4 */

          return 0;
  }

State 4에서 Grock만 list에 남고 Dimitri는 분리되어 어느 곳도 가리키지 않는 poisoned 상태입니다.

제거한 node를 빈 list head처럼 다시 자신을 가리키게 하려면 `list_del_init()`을 사용합니다.

.. code-block:: c

  static int circus_fill_car(struct circus_priv *circus)
  {
          /* ... */

          list_add(&dimitri->node, &car->clowns);

          /* State 3 */

          list_del_init(&dimitri->node);

          /* State 4b */

          return 0;
  }

State 4b에서 Dimitri는 분리되어 있지만 self-loop로 재초기화되었습니다.

제거하면서 안전하게 순회

`list_for_each()` 또는 `list_for_each_entry()`로 순회하면서 현재 entry를 삭제하면 `next` pointer가 바뀌어 다음 entry로 올바르게 이동할 수 없습니다.

`list_for_each_safe()`와 `list_for_each_entry_safe()`는 iteration 중 다음 entry를 임시 저장할 추가 `struct list_head` pointer를 받아 이 문제를 해결합니다.

.. code-block:: c

  static void circus_eject_insufficient_clowns(struct circus_priv *circus)
  {
          struct clown *e;
          struct clown *n;      /* temporary storage for safe iteration */

          list_for_each_entry_safe(e, n, &circus->car.clowns, node) {
                if (e->shoe_size < 500)
                        list_del(&e->node);
          }
  }

삭제한 node를 free하면서 다른 reference가 없는지 확인하는 올바른 memory management는 이 예제의 범위를 벗어납니다.

list 자르기

List를 자르는 helper는 두 가지이며 모두 `head` list에서 element를 떼어 `list` destination의 내용을 대체합니다.

`list_cut_position()`은 `head`부터 `entry`를 포함한 위치까지 제거해 `list`로 옮깁니다. 시작 상태는 다음과 같습니다.

다음 code는 Pic까지의 모든 clown을 local stack의 `retirement` list로 옮깁니다.

.. code-block:: c

  static void circus_retire_clowns(struct circus_priv *circus)
  {
          struct list_head retirement = LIST_HEAD_INIT(retirement);
          struct clown *grock, *dimitri, *pic, *alfredo;
          struct clown_car *car = &circus->car;

          /* ... clown initialization, list adding ... */

          list_cut_position(&retirement, &car->clowns, &pic->node);

          /* State 1 */
  }

`list_cut_before()`는 `entry` 직전까지만 잘라 `entry`는 원본에 남깁니다. 같은 초기 상태에서 다음 code를 적용합니다.

.. code-block:: c

  static void circus_retire_clowns(struct circus_priv *circus)
  {
          struct list_head retirement = LIST_HEAD_INIT(retirement);
          struct clown *grock, *dimitri, *pic, *alfredo;
          struct clown_car *car = &circus->car;

          /* ... clown initialization, list adding ... */

          list_cut_before(&retirement, &car->clowns, &pic->node);

          /* State 1b */
  }

두 함수 모두 destination `struct list_head *list`에 기존 node가 연결되어 있었다면 그 link를 파괴한다는 점에 주의해야 합니다.

entry와 부분 list 이동

`list_move()`와 `list_move_tail()`은 entry를 다른 list의 시작 또는 끝으로 각각 옮깁니다. 초기 State 0에는 `clowns`와 `sidewalk` 두 list가 있습니다.

.. code-block:: c

  static void circus_clowns_exit_car(struct circus_priv *circus)
  {
          struct list_head sidewalk = LIST_HEAD_INIT(sidewalk);
          struct clown *grock, *dimitri, *pic, *alfredo, *pio;
          struct clown_car *car = &circus->car;

          /* ... clown initialization, list adding ... */

          /* State 0 */

          list_move(&pic->node, &sidewalk);

          /* State 1 */

          list_move_tail(&dimitri->node, &sidewalk);

          /* State 2 */
  }

State 1에서 `list_move()`는 Pic을 sidewalk head 바로 뒤로 옮깁니다.

State 2에서 `list_move_tail()`은 Dimitri를 sidewalk의 tail로 옮깁니다.

Source와 destination list head가 같은 list에 속한다면 `list_bulk_move_tail()`로 연속 구간을 list tail에 효율적으로 옮길 수 있습니다. 다음 code는 Pic부터 Pio까지를 sidewalk tail로 이동합니다.

.. code-block:: c

  static void circus_clowns_exit_car(struct circus_priv *circus)
  {
          struct list_head sidewalk = LIST_HEAD_INIT(sidewalk);
          struct clown *grock, *dimitri, *pic, *alfredo, *pio;
          struct clown_car *car = &circus->car;

          /* ... clown initialization, list adding ... */

          /* State 0 */

          list_move(&pic->node, &sidewalk);

          /* State 1 */

          list_move_tail(&dimitri->node, &sidewalk);

          /* State 2 */

          list_bulk_move_tail(&sidewalk, &pic->node, &pio->node);

          /* State 3 */
  }

`list_bulk_move_tail()`은 전달한 세 `struct list_head *`가 실제로 같은 list에 속하는지 검사하지 않습니다. 문서가 정한 제약을 벗어나 호출하면 결과를 보장할 수 없습니다.

entry 회전

Queue처럼 list를 사용할 때 흔한 write operation은 앞의 entry를 뒤로 보내는 rotation입니다. Linux는 `list_rotate_left()`와 `list_rotate_to_front()`를 제공합니다.

`list_rotate_left()`는 circular bicycle chain처럼 head 다음 entry를 tail로 옮겨 전체 list를 한 칸 회전합니다. `list_rotate_to_front()`는 지정 entry가 새 front가 될 때까지 회전합니다.

.. code-block:: c

  static void circus_clowns_rotate(struct circus_priv *circus)
  {
          struct clown *grock, *dimitri, *pic, *alfredo, *pio;
          struct clown_car *car = &circus->car;

          /* ... clown initialization, list adding ... */

          /* State 0 */

          list_rotate_left(&car->clowns);

          /* State 1 */

          list_rotate_to_front(&alfredo->node, &car->clowns);

          /* State 2 */

  }

entry 교환

두 entry의 위치를 바꾸는 흔한 작업에는 `list_swap()`을 사용합니다. State 0은 세 entry로 시작합니다.

.. code-block:: c

  static void circus_clowns_swap(struct circus_priv *circus)
  {
          struct clown *grock, *dimitri, *pic;
          struct clown_car *car = &circus->car;

          /* ... clown initialization, list adding ... */

          /* State 0 */

          list_swap(&dimitri->node, &pic->node);

          /* State 1 */
  }

State 1에서는 Pic과 Dimitri의 위치가 서로 바뀝니다.

두 list 잇기

두 circus list `knie`와 `stey`를 합치는 예제입니다. 초기 State 0은 다음과 같습니다.

두 list를 잇는 함수는 `list_splice()`입니다.

.. code-block:: c

  static void circus_clowns_splice(void)
  {
          struct clown *grock, *dimitri, *pic, *alfredo, *pio;
          struct list_head knie = LIST_HEAD_INIT(knie);
          struct list_head stey = LIST_HEAD_INIT(stey);

          /* ... Clown allocation and initialization here ... */

          list_add_tail(&grock->node, &knie);
          list_add_tail(&dimitri->node, &knie);
          list_add_tail(&pic->node, &knie);
          list_add_tail(&alfredo->node, &stey);
          list_add_tail(&pio->node, &stey);

          /* State 0 */

          list_splice(&stey, &dimitri->node);

          /* State 1 */
  }

이 호출은 `stey`의 모든 entry를 Dimitri의 `node` 다음에 삽입합니다.

이 상태에서 `stey`를 `list_for_each()`로 순회하면 head로 돌아오지 않아 infinite loop가 됩니다. `list_splice()`가 donor `list_head`를 재초기화하지 않아 pointer가 이제 다른 list 내부를 가리키기 때문입니다.

이를 피하려면 `list_splice_init()`을 사용합니다. `list_splice()`와 같은 transplant를 수행한 뒤 donor `list_head`를 다시 초기화합니다.

concurrency 고려 사항

대부분의 경우 list에 대한 concurrent access와 modification은 lock으로 보호해야 합니다. Read가 많고 modification이 적은 use case에서는 list용 RCU primitive를 사용하는 편이 좋습니다. 자세한 내용은 `Documentation/RCU/listRCU.rst`를 참조하십시오.

더 읽을 자료

더 읽을 자료 (Further reading)

• How does the kernel implements Linked Lists? - KernelNewbieshttps://kernelnewbies.org/FAQ/LinkedLists

전체 List API

전체 List API (Full List API)

List API의 internal kernel-doc은 `include/linux/list.h`에서 가져옵니다.

.. kernel-doc:: include/linux/list.h
   :internal: