(SINGLE_)LIST_ENTRY & CONTAINING_RECORD

By Michael Schöbel

Lists are a basic data structure in any operating system kernel, e.g. used for thread queue management. The WRK provides a set of struct definitions and list related functions/macros. In this post a short survey of these elements is given.

There are two types of lists available in the WRK: singly linked lists and doubly linked lists. The definition of the corresponding data structures is part of the public kernel interface in public/sdk/inc/ntdef.h.

//
//  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;

An element of a doubly linked lists contains a pointer to the next element (a forward link - Flink) and a pointer to the previous element (a back link - Blink). Each SINGLE_LIST_ENTRY contains a reference to the next element.

As the comments state these data structures "can be used as either a list head, or as link words": each list has one special list head and a set of elements, e.g. the list head KiProcessListHead for the list of active processes is defined in base/ntos/ke/kernldat.c.

Each list head has to be initialized: Singly linked lists are initialized by simple setting the next pointer of the list head to NULL. Doubly linked lists are initialized by calling InitializeListHead (defined in public/sdk/inc/ntrtl.h).

VOID
FORCEINLINE
InitializeListHead(
    IN PLIST_ENTRY ListHead
    )
{
    ListHead->Flink = ListHead->Blink = ListHead;
}

As you can see, the forward and the backward link are both set to point to the list head.

To check whether a given list is empty, the list head has to be checked: A singly linked list is empty if the next pointer points to NULL and a doubly linked list is empty if Flink points to the list head itself. For doubly linked lists the macro IsListEmpty does this test.

Data structures which represent list elements must contain a data field of the type LIST_ENTRY (or SINGLE_LIST_ENTRY).

typedef struct _MyListElement {
    ...
    LIST_ENTRY Link;
    ...
} MyListElement;

The WRK list operations are based on (1) a reference to the list head, and (2) a reference to the LIST_ENTRY field of a list element. An example: if you want to insert the element MyListElement e at the head of the list LIST_ENTRY l you call InsertListHead(&l, &e->Link).

The available functions for singly linked lists are:

• PSINGLE_LIST_ENTRY PopEntryList(PSINGLE_LIST_ENTRY ListHead);
• VOID PushEntryList(PSINGLE_LIST_ENTRY ListHead, PSINGLE_LIST_ENTRY Entry);
• PSINGLE_LIST_ENTRY ExInterlockedPopEntryList (PSINGLE_LIST_ENTRY ListHead, PKSPIN_LOCK Lock);
• PSINGLE_LIST_ENTRY ExInterlockedPushEntryList (PSINGLE_LIST_ENTRY ListHead, PSINGLE_LIST_ENTRY ListEntry, PKSPIN_LOCK Lock);

The available functions for doubly linked lists are:

• VOID InitializeListHead(PLIST_ENTRY ListHead);
• BOOLEAN IsListEmpty(PLIST_ENTRY ListHead);
• BOOLEAN RemoveEntryList(PLIST_ENTRY Entry);
• PLIST_ENTRY RemoveHeadList(PLIST_ENTRY ListHead);
• PLIST_ENTRY RemoveTailList(PLIST_ENTRY ListHead);
• VOID InsertTailList(PLIST_ENTRY ListHead, PLIST_ENTRY Entry);
• VOID InsertHeadList(PLIST_ENTRY ListHead, PLIST_ENTRY Entry);
• PLIST_ENTRY ExInterlockedInsertHeadList (PLIST_ENTRY ListHead, PLIST_ENTRY ListEntry, PKSPIN_LOCK Lock);
• PLIST_ENTRY ExInterlockedInsertTailList (PLIST_ENTRY ListHead, PLIST_ENTRY ListEntry, PKSPIN_LOCK Lock);
• PLIST_ENTRY ExInterlockedRemoveHeadList (PLIST_ENTRY ListHead, PKSPIN_LOCK Lock);

The function/macro names are self-explanatory - their implementation can be found in public/sdk/inc/ntrtl.h or in base/ntos/inc/ex.h (ExInterlocked* functions). The interlocked functions synchronize access to the list data structures in multiprocessor systems by using the provided spinlock.

Functions which can be used to query list elements (e.g. PopEntryList or RemoveHeadList) return pointer to the LIST_ENTRY link of list elements. To get the "real" list data element the macro CONTAINING_RECORD (see public/sdk/inc/ntdef.h) has to be used:

#define CONTAINING_RECORD(address, type, field) \
    ((type *)( \
    (PCHAR)(address) - \
    (ULONG_PTR)(&((type *)0)->field)))

The address parameter is a reference to a LIST_ENTRY structure, type is the name of the structure that describe the actual list element, and field is the name of the data field in the list element data structure that is used for linking the list elements. If we have a pointer PLIST_ENTRY p which references a Link field of a MyListElement structure, we can get a reference to the actual MyListElement as follows:

MyListElement* element = CONTAINING_RECORD(p, MyListElement, Link);

How does it work? Let's expand the macro:

MyListElement* element = ((MyListElement *)((PCHAR)(p) - (ULONG_PTR)(&((MyListElement *)0)->Link)));

The last term (&((MyListElement *)0)->Link) determines the offset of the link element relative to the start (= first byte) of the list element data structure. The trick is to cast the address 0 into a MyListElement - afterwards the address of the Link field is the offset which must be subtracted from the pointer p. Finally, this updated address now refers to the start of the actual list element data structure and can be casted accordingly. Note, that CONTAINING_RECORD works for both types (singly linked and doubly linked) of lists.

As a final example the following code fragment shows how to process all elements of a doubly linked list.

PLIST_ENTRY pe = head.Flink;
while(pe != &head) {
    ...
    pe = pe->Flink;
}

A list entry reference pe is initialized to point to the first list element (head.Flink). While this reference does not point to the list head, either because the list is empty or the last element was processed, the loop is executed. The last line of the loop body sets the pe reference to the next list element.

More information can be found in the WRK source code and in the MSDN.

Comments