지난 스터디 시간에 나왔던 커널이 사용하는 연결 리스트에 대해 정리를 해봅니다.
struct list_head는 커널에 다음과 같이 정의 되어 있습니다.
struct list_head {
struct list_head *next, *prev;
};
커널이 사용하는 구조체 변수들을 연결 리스트로 만들 때 자주 사용하며 상당히 간단하고 유용합니다.
다음과 같은 구조체 형이 있다고 했을 때 struct list_head 멤버를 살짝? 넣어줌으로써 구조체를 손쉽게
연결 리스트로 만들 수 있습니다.
typedef struct bootmem_data {
unsigned long node_min_pfn;
unsigned long node_low_pfn;
void *node_bootmem_map;
unsigned long last_end_off;
unsigned long hint_idx;
struct list_head list;
} bootmem_data_t;
다음과 같이 구조체 변수를 세개 만듭니다.
bootmem_data_t aaa, bbb, ccc;
구조체의 멤버인 struct list_head list를 통해 연결리스트로 만들어 줍니다.
aaa.list->next = &bbb.list;
bbb.list->prev = &aaa.list;
bbb.list->next = &ccc.list;
ccc.list->prev = &bbb.list;
ccc.list->next = &aaa.list;
aaa.list->prev = &ccc.list;
그런데 여기서 문제가 발생 합니다.
구조체들을 연결 리스트로 연결해서 뽀대?가 나게 되었는데 정작 필요한 데이터를 저장하고 있는
구조체의 멤버들에 접근 할 길이 없어 보입니다.
하지만 커널은 다음과 같이 꼼수를 발휘해서 이 난관을 극복합니다.
다음의 코드를 실행하면 offset에 얼마가 저장이 될까요?
size_t offset;
offset = &((bootmem_data_t *)0)->list
offset에는 20이 저장이 됩니다.
bootmem_data_t 타입의 구조체가 0번지에 존재한다고 가정을 했으므로
이 구조체의 첫번째 멤버인 node_min_pfn는 0번지 주소에 배치되고
두번째 멤버인 node_low_pfn는 4번지 주소에 배치되고 ...
hint_idx 멤버는 16번지 주소에 배치 됩니다. 결국 list 멤버는 20번지 주소에 배치가 되게 되는 것입니다.
즉, 조금 전에 만들었던 구조체 변수 aaa의 시작 주소는 ((char*)&aaa.list - 20)를 통해서 구할 수 있습니다.
이제 aaa의 시작 주소를 알았으니 다음과 같이 캐스팅을 통해(bootmem_data_t *)((char*)&aaa.list - 20)
이 구조체의 모든 멤버에 접근이 가능하게 되는 것입니다.
그림을 그려서 좀 더 이해하기 쉽게 설명을 하고 싶은데 시간이 여의치 않네요.
잘못된 내용은 지적 부탁 드립니다.
댓글 2
.
제가 지난주 구라(?)를 펼쳐놓은 리스트 운용방법을 깔끔하게 설명해 놓으셨네요. ^^
이런식의 리스트 노드운용을 가끔 다른 오픈소스에서도 목격하게 됩니다.
장점은 노드 사이즈가 슬림해지는것일 테고, 단점은 코드 분석하기 힘들다 인것 같습니다.