[3기 대전 김재원] Linux Kernel - Data Structure (1)

안녕하세요! 대전멤버십 Elite Member 3기 김재원입니다.

벌써 4번째 포스트가 되었네요~

지난 3번의 포스트에서는 Kernel을 Debugging하는 방법으로 실행중에 Debugging을 할 수 있는 Dynamic Probes를 알아보았습니다.

이번시간부터는 Linux Kernel에서 사용하고 있는 자료구조들을 알아보도록 하겠습니다.

Linux Kernel에서는 많이 사용하는 자료구조들은 대부분 구현되어 있기때문에 편리하게 사용할 수 있습니다. 일부 자료구조는 헤더만 가지고 와서 사용해도 되기때문에 Kernel이 아니더라도 여러 곳에서 사용가능 합니다.

List

Linux Kernel에서는 예전부터 list에 관한 헤더를 제공하였다. list에 관련된 헤더는 <linux/list.h>에 정의 되어있습니다. 노드 추가, 삭제, 순회 등등 여러가지 함수들을 기본적으로 제공하고 있습니다.

기본적으로 Double Linked List입니다.

실습을 통해 순서대로 차곡차곡 알아가보도록 하겠습니다.

우선 연결할 노드를 만듭니다.

Double Linked List를 사용하기 위해서는 이전노드를 가리키는 포인터와 다음 노드를 가르키는 포인터를 가지고 있어야 합니다. next와 prev 노드를 가리키는 포인터를 가지고 있는것이 list_head 구조체 입니다.

list_haed 구조체는 <linux/types.h>에 정의되어 있으며 

list_head 구조체를 확인해 보면 다음과 같습니다. 

위와 같이 next와 prev는 Node의 위치를 가르키는 것이 아닌 list_head 구조체의 위치를 가리키고 있습니다.

그럼 list_head 구조체는 담고있는 Node의 정보를 알기 위해서는 어떻게해야 할까요??

바로 list_entry()라는 메크로를 사용합니다. list_entry()를 살펴보면 바로 container_of()라는 메크로를 호출합니다. 그럼 container_of()를 살펴보면 다음과 같습니다.

container_of 메크로는 <linux/kernel.h>에 정의되어 있으며 변수를 가지고 있는 구조체를 반환하도록 구성되어 있습니다. list_entry를 사용하면 해당 리스트를 가지고 있는 Node의 주소를 알수 있고 이 주소를 통해 Data들에게 접근 가능합니다.

Linux Kernel에서 제공하는 List 구조는 알아 보았고 이제 List를 사용하기 위해 제공하는 기본적인 함수들을 알아보도록 하겠습니다.

<linux/list.h>안에는 List와 관련된 많은 함수들이 존재합니다. 그중 대표적인 것은 

list_add()            - List에 head 뒤에 Node를 추가  list_del()             - List에서 해당 Node 삭제  list_replace()       - 기존의 Node를 새로운 Node로 교체  list_del_init()        - 모든 Node를 지움  list_move()          - 해당 Node를 지우고 새로운 Node 추가  list_is_last()        - 해당 Node가 마지막 Node인지 검사  list_empty()         - 리스트가 비어 있는지 검사

위와 같이 List의 Node를 검사하는 함수들이 있습니다. 

이렇게 Node관련된 함수가 아닌 List의 사용을 편리하게 해주는 List를 순회하는 매크로들도 존재 합니다.

list_for_each()              - List의 list_head를 순회하는 매크로  list_for_each_entry()      - Node를 순회하며 각 Node의 주소를 반환  list_for_each_entry_safe - Node를 제거하며 순회

위와 같이 List를 사용하기 쉽도록 Kernel에서 다양한 메크로와 함수를 제공합니다. 

이제 직접 실습을 해보도록 하겠습니다.

Kernel에서 사용하는 함수이기 때문에 간단한 module을 제작하여 테스트 해보도록 하겠습니다.

Linux Kernel Data Struct - List Example

결과

위와 같이 module init 부분에 List를 구성하여 add외 del, replace를 해보고 Node들을 순회 하며 data을 출력 해보았습니다. 

속도 향상을 위해 대부분의 함수는 inline을 통하여 구성되어 있습니다. 

Kernel 내부에서 List를 많이 사용하고 있으며 대표적으로 task_struct역시 list로 구성되어 있습니다. 

다음시간에는 Queue라고 할수 있는 FIFO와 tree에 대해 알아 보도록 하겠습니다.