외부 라이브러리 사용에 있어서 제약이 많은 커널 개발 환경에서는 처리할 데이터가 많지 않고, 단순한 형태의 iteration/search 기능이 필요할 때 대부분 linked list 자료구조를 선택하게 된다. Linked list의 구현이나 이용에는 큰 어려움이 따르지 않고 이미 드라이버 개발 환경에도 헤더 파일(winnt.h, wdm.h)을 통하여 관련 함수에 대한 코드를 제공하고 있다.
특히 linked list를 활용한 iteration의 예는 쉽게 찾아볼 수 있는데, 가장 자주 눈에 띄는 것으로는 EPROCESS, ETHREAD와 같은 커널 객체들을 스케쥴링 및 iteration 할 때이다.
Winnt.h 에는 single/double linked list를 위한 구조체가 정의되어 있다.
//
// Doubly linked list structure. Can be used as either a list head, or
// as link words.
//
typedef struct _LIST_ENTRY {
struct _LIST_ENTRY *Flink;
struct _LIST_ENTRY *Blink;
} LIST_ENTRY, *PLIST_ENTRY, *RESTRICTED_POINTER PRLIST_ENTRY;
//
// Singly linked list structure. Can be used as either a list head, or
// as link words.
//
typedef struct _SINGLE_LIST_ENTRY {
struct _SINGLE_LIST_ENTRY *Next;
} SINGLE_LIST_ENTRY, *PSINGLE_LIST_ENTRY;
이 linked list들을 다루는 함수들은 wdm.h에 inline으로 정의되어 있다.
FORCEINLINE
VOID
InitializeListHead(
IN PLIST_ENTRY ListHead
)
{
ListHead->Flink = ListHead->Blink = ListHead;
}
FORCEINLINE
BOOLEAN
RemoveEntryList(
IN PLIST_ENTRY Entry
)
{
PLIST_ENTRY Blink;
PLIST_ENTRY Flink;
Flink = Entry->Flink;
Blink = Entry->Blink;
Blink->Flink = Flink;
Flink->Blink = Blink;
return (BOOLEAN)(Flink == Blink);
}
위의 코드에서 볼 수 있듯 커널에서 제공하는 기본 함수 내부에는 동기화 코드가 있지 않으므로 만약 이 linked list 자료구조를 다룰 때 동기화 기능이 필요하다면 함수를 호출하기 전 외부에서 직접 동기화 처리를 해 주거나, SLIST_HEADER 구조체를 이용하여 동기화 기능이 추가된 single/double linked list 관련 함수들을 사용해야 한다.
실제 상용 코드를 개발할 때에는 거의 대부분 list에 대한 동기화가 필요하다. 일반적으로 event, mutex나, IRQL 레벨에 따라 spinlock을 사용해야 한다. 커널에서 제공하는 동기화 포함 list 조작 함수인 ExInterlocked 함수들(예-ExInterlockedPushEntrySList)은 어떠한 IRQL에서도 동작할 수 있다.
LIST_ENTRY 필드를 추가하여 각자 고유한 구조체를 정의하였을 경우 구조체의 시작 포인터 주소를 얻어야 하는 경우가 빈번하게 발생하는데 그럴 때를 위하여 CONTAINING_RECORD라는 매크로가 이미 정의되어 있다.
//
// Calculate the address of the base of the structure given its type, and an
// address of a field within the structure.
//
#define CONTAINING_RECORD(address, type, field) ((type *)( \
(PCHAR)(address) - \
(ULONG_PTR)(&((type *)0)->field)))
특히 LIST_ENTRY를 이용하여 개발했을 경우에는 WinDBG를 통해 list 코드의 디버깅을 할 때 DL 이라는 커맨드를 활용하면 쉽게 그 리스트의 내용을 덤프할 수도 있다.
(참고: http://blogs.msdn.com/doronh/archive/2006/08/09/693765.aspx)
linked list는 그 구조와 구현이 단순하여 만약 list를 활용하는 코드와 관련한 에러가 발생하면 비교적 쉽게 대처가 가능하다. 우선 포인터가 올바른지 확인하고 WinDBG를 통해 list의 prev, next 필드가 올바른 메모리 위치나 list를 가르치고 있는지 확인하는 것이 가장 중요하다. 또한 IRQL이 DISPATCH_LEVEL 이상이라면 list가 할당된 메모리가 non-paged pool인지도 반드시 확인하자. 동기화 코드에서 문제가 발생한다면 좀 해결하기에 난감하겠지만, 이때에도 IRQL과 데드락을 의심해보고, 또는 원시적인 방법이지만 디버그 메시지를 통해 문제의 원인을 해결하도록 한다.
윈도우 커널에서 제공하는 보다 자세한 linked list 구현 내용은 아래 osr 링크를 참고하도록 하자.
Kernel-Mode Basics: Windows Linked Lists