intrusive - structures

공부용·2025년 4월 23일

~~11미터 모형탑 침투~~

리눅스 커널이 침투형 자료구조를 사용하는 이유

리눅스 커널은 list, tree, hash table 등의 자료구조를 구현할 때 침투형(intrusive) 방식을 선호한다. 침투형 구조는 데이터 구조체가 스스로 자료구조의 노드 역할을 수행하는 구조를 의미한다.

1. 침투형 자료구조란?

침투형 구조란 구조체 내부에 리스트, 트리 등을 위한 연결 정보(hook) 를 직접 포함시키는 방식이다.
대표적인 예로, 다음과 같이 리스트에 연결되기 위한 list_node를 구조체 내부에 포함시킬 수 있다.

struct list_node {
    struct list_node *next;
    struct list_node *prev;
};

struct Task {
    int id;
    struct list_node hook;  // 리스트 연결을 위한 hook
};

이처럼 구조체가 스스로 리스트의 노드 역할을 수행하므로, 별도의 노드 구조체가 필요하지 않다.

2. 커널이 침투형 구조를 사용하는 이유

2.1 캐시 친화적 성능

침투형 구조는 데이터와 연결 포인터가 같은 메모리 블록에 위치하므로, 캐시 적중률이 높아지고 dereference가 줄어든다. 이는 CPU 입장에서 매우 빠른 자료 접근을 가능하게 한다.

2.2 메모리 효율성

침투형 구조는 데이터 + 노드가 하나의 구조체로 존재하므로, 별도의 래퍼 구조체나 추가 메모리 할당이 필요 없다.

2.3 락 없는 동기화 구조에 적합

container_of() 매크로를 사용하면 intrusive 필드만으로도 객체 전체를 역추적할 수 있다. 이는 락 없는 설계나 RCU 같은 동기화 방식에 매우 유리하다.

2.4 여러 자료구조에 동시에 연결 가능

하나의 구조체가 여러 자료구조에 연결되어야 할 경우, 각 자료구조에 대응하는 hook을 구조체 내부에 포함시킬 수 있다.

struct inode {
    struct list_head sb_list;     // 슈퍼블록 리스트 연결
    struct hlist_node i_hash;     // 해시 테이블 연결
    struct rb_node i_rb;          // 레드블랙 트리 연결
};

이처럼 inode 구조체는 하나의 객체로서 리스트, 해시, 트리 등에 동시에 연결된다.

2.5 일반화를 피하고 최적화된 구조를 설계함

커널은 범용성보다 성능과 효율을 중시한다. 침투형 구조는 자료구조와 타입이 고정되어 있어 컴파일 타임에 최적화가 가능하다.

3. Hook과 Callback의 차이

Hook: 연결 정보. 자료구조에 "내가 연결될 수 있도록" 포함시키는 필드이다.
Callback: 동작 알림. 객체가 어떤 이벤트를 감지하고 외부에 통지할 수 있도록 등록하는 함수 포인터이다.

struct Employee {
    int id;
    struct list_node hook;  // 리스트 연결용
    void (*on_change)(struct Employee *);  // 변경 감지용 콜백
};

4. 비침투형 자료구조에서는 왜 어렵나?

비침투형 구조에서는 데이터가 자료구조와 분리되어 있기 때문에, 변경 사실을 자료구조가 알 수 없다. 예를 들어 다음 구조에서는 변경 여부를 추적할 수 없다.

struct Data {
    int key;
    char name[32];
};

struct Node {
    struct Data *data;
    struct Node *next;
};

이 경우 data가 바뀌더라도 리스트는 그 사실을 알 수 없기 때문에, 변경 여부를 추적하려면 전체 순회를 통해 비교해야 한다.

5. 요약

항목	침투형 구조가 유리한 이유
성능	dereference가 없고, 캐시 친화적이다.
메모리	node + data를 하나로 처리하므로 메모리 절약 가능하다.
다중 구조 연결	하나의 구조체에 여러 hook을 포함시켜 다양한 자료구조에 동시에 속할 수 있다.
변경 추적	값이 스스로 변경을 인식하고 통지할 수 있다.
락 없는 설계	container_of를 활용한 lockless 접근에 적합하다.

6. 대표 구조체 예시

구조체	용도
`struct list_head`	이중 연결 리스트
`struct hlist_node`	해시 리스트
`struct rb_node`	Red-Black Tree
`struct rcu_head`	RCU 지연 삭제
`struct kref`	참조 카운팅