list 내 double pointer

상황

커널에선 list 는 흔히 쓰이는 자료구조인데,
어떤 경우엔 list node (HLIST_NODE) 에 double pointer 가 들어가는 경우가 있다.

hlist (hash list) 의 경우

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

tasklet 의 경우

struct tasklet_head {
	struct tasklet_struct *head;
	struct tasklet_struct **tail;
};

struct tasklet_struct
{
	struct tasklet_struct *next;
	unsigned long state;
	atomic_t count;
	bool use_callback;
	union {
		void (*func)(unsigned long data);
		void (*callback)(struct tasklet_struct *t);
	};
	unsigned long data;
};

목적

double pointer 작성자가 마주한 문제가 어떤것이고, 어떠한 생각으로 결정(디자인)을
하였는지 정리

hlist_node 와 hlist_head

구조체 메모리 footprint 를 줄이려는 의도

• 구조체 내에 list head 를 둘떄,
  struct list_head 는 16 bytes, struct hlist_head 는 8바이트로 후자가 경제적

• "hash list" 를 순회할때,
  tail 을 접근할 일은 거의 없으므로, head 에 있던 tail 포인터를 뺀것

• doubly linked list 기능은 유지하기 위해,
  node 쪽 (struct hlist_node) 에 double pointer 를 배치

tasklet_struct 와 tasklet_head

현재 list 의 tail 을 head 에서 저장, 가리키려는 의도

• node (struct tasklet_struct) 는 항상 tail 에 들어가므로,
  미리 tail 을 알고 있어야 할 필요가 있음
• head 에 저장해둔 tail pointer 를 사용후,
  새 tail node 를 가리킬수 있게 double pointer 를 배치

디자인적인 차이점과 효과

hlist 쪽에선 node 에 double pointer 를 둠으로서,
list head 가 있는 구조체의 memory footprint 를 줄였고

tasklet 쪽에선 head 에 double pointer 를 둠으로서,
tail 에 새 node 를 삽입시, tail 을 찾으려고 순회할 필요가 없어짐

참고링크

hlist
https://www.mail-archive.com/kernelnewbies@nl.linux.org/msg10939.html
https://lkml.org/lkml/2000/7/28/10

tasklet
https://lwn.net/Articles/269072/