Linked lists on DDK

February 24th, 2007 - Fernando Roberto

Since the beginning of my studies, I have always chosen to study something that would unite computer science with electronics, and this led me to choose the Computing Industrial course at ETE Jorge Street. An excellent school and I learned a lot there. However I have only learned what a linked list is in a professional environment during my internship. Years later, the university introduced me to these lists in form of classes written in Java, where we dealt with references and garbage collectors. Even those who work with Visual C/C++, handles, templates and classes offered by MFC, ATL, WTL and STL, which end up abstracting real linked list implementation. In this post, I will talk a little about resources offered by DDK regarding to this subject.

But I am already a big boy and I already know how to build linked lists in C/C++. Why should I use DDK resources?

If you only store private data, such as a list of buffers to be sent to the device, that’s fine, but to deal with DDK structures, it would be, at least, interesting to know how they are stored in lists. Some situations require you to know how to use DDK lists. An example is: If you implement the custom control queue for IRPs in your driver, the pIrp->Tail.Overlay.ListEntry field will be free to be used while such IRP is held by your driver.

The simplest of these resources is SINGLE_LIST_ENTRY structure that is defined at ntdef.h, as shown below:

typedef struct _SINGLE_LIST_ENTRY {
  struct _SINGLE_LIST_ENTRY *Next;
} SINGLE_LIST_ENTRY, *PSINGLE_LIST_ENTRY;

SINGLE_LIST_ENTRY variable must be set to be the head of our list. This variable should have its Next member initialized with NULL before being used. The PushEntryList() and PopEntryList() routines are used respectively to add and remove elements from the list head. Like most linked lists, nodes are referenced by the Next member until it is NULL, thus indicating the node chain ending.

VOID 
  PushEntryList(
    IN PSINGLE_LIST_ENTRY  ListHead,
    IN PSINGLE_LIST_ENTRY  Entry
    );
 
PSINGLE_LIST_ENTRY 
  PopEntryList(
    IN PSINGLE_LIST_ENTRY  ListHead
    );

But wait a minute. All this is beautiful, but isn’t anything missing? Like any linked list structure, among the members of each node, there must be one which points to a similar structure, which is the link to the list next node. In the example below, the pNext member is the one responsible for it.

//-f--> Structure that defines the node list
//      which will be used as an example.
typedef struct _MY_NODE
{
    //-f--> Your private data that will be defined
    //      by yourself.
    UNICODE_STRING      usSomeData;
    ULONG               ulAnotherData;
    struct _MY_NODE     *pNext;
    PVOID               pMoreData;
 
} MY_NODE, *PMY_NODE;

But from what we could see at the DDK structure, there are no useful members on it, those ones that contain information that will be kept in the list, like fields as usSomeData or pMoreData. At the structure offered by the DDK, there is only the next node address.

What is the point on saving only nodes?

Actually, the SINGLE_LIST_ENTRY structure as well as other DDK lists structures should be used in conjunction with the CONTAINING_RECORD macro. This macro returns the structure base address that contains a known field in a known address. Well, I have tried to rewrite this sentence three times, but I think you will only understand when you see the example below. Suppose we are using the SINGLE_LIST_ENTRY in our previous example. Thus, we would have the following structure:

//-f--> Structure that defines a register on our linked list
//      and will be used in this example
typedef struct _MY_NODE
{
    //-f--> Register's private data on the list node.
    //      These fields are not fixed and defined by you.
    UNICODE_STRING      usSomeData;
    ULONG               ulAnotherData;
 
    //-f--> That member doesn't necessarily need
    //      to be the first or the last one at this structure;
    //      it can be at any position here inside.
    SINGLE_LIST_ENTRY   Entry;
 
    //-f--> More data
    PVOID               pMoreData;
 
} MY_NODE, *PMY_NODE;

Our structure is basically the same, except the member pNext, which has now been changed to use the structure SINGLE_LIST_ENTRY. Notice that the field doesn’t need to be either at the beginning or the end of our structure. The example below demonstrates how to include nodes in lists composed by SINGLE_LIST_ENTRY nodes.

NTSTATUS PrepareDataAndPush(VOID)
{
    PMY_NODE            pMyNode;
 
    //-f--> Here we get the already allocated node
    //      with its fields correctly initialized.
    pMyNode = AllocateAndFillNode();
 
    //-f--> Testing is never too much.
    ASSERT(pMyNode != NULL);
 
    //-f--> To put the node at the list, it is necessary to use
    //      the SINGLE_LIST_ENTRY member address.
    PushEntryList(&m_ListHead, &pMyNode->Entry);
 
    return STATUS_SUCCESS;
}

At the time to include the node in the list, we use the SINGLE_LIST_ENTRY member address, as suggested by the PushEntryList prototype function. Follow the example below that demonstrates how to get this node using PopEntryList function. This function returns the address passed to PushEntryList function, which is a PSINGLE_LIST_ENTRY. From this address, as I had commented before, we can get the base address of our structure using CONTAINING_RECORD macro. See the example below.

NTSTATUS PopAndProcessNode(VOID)
{
    PSINGLE_LIST_ENTRY  pEntry;
    PMY_NODE            pMyNode;
 
    //-f--> Here we get the node from the list.
    pEntry = PopEntryList(&m_ListHead);
 
    //-f--> Now we can check if a register really was retrieved
    //      from the list.
    if (!pEntry)
        return STATUS_NO_MORE_ENTRIES;
 
    //-f--> Now we use the CONTAINING_RECORD macro
    //      to get the base address we need.
    pMyNode = (PMY_NODE) CONTAINING_RECORD(pEntry, MY_NODE, Entry);
 
    //-f--> Now we can access the whole structure.
    ProcessAndFreeNode(pMyNode);
 
    return STATUS_SUCCESS;
}

This same style is also used with the LIST_ENTRY structure, which is the one used in most drivers. This structure allows you to create doubly linked lists, and like SINGLE_LIST_ENTRY, a LIST_ENTRY variable is set to be our list head. Its initialization is done using InitializeListHead() function, which initializes the Flink and Blink members with the list head address.

typedef struct _LIST_ENTRY {
  struct _LIST_ENTRY *Flink;
  struct _LIST_ENTRY *Blink;
} LIST_ENTRY, *PLIST_ENTRY;

The Flink member points to the next node, whereas the Blink member points to the previous node. Unlike most linked lists we know, its endings are not marked by NULL at Flink and Blink members. Instead, their ending points to the address of the node designated as our list head. The example below demonstrates how we could sweep this kind of list, searching a certain node. Before performing any operation with the lists composed by LIST_ENTRY structures, use IsListEmpty() function.

//-f--> Looks for a node through a list
//      composed by nodes using LIST_ENTRY structures.
BOOLEAN SearchEntry(PUNICODE_STRING  pusLookFor)
{
    PLIST_ENTRY pEntry;
    PMY_NODE    pMyNode;
 
    //-f--> Before any operation, it is necessary
    //      to check for an empty list condition.
    if (IsListEmpty(&m_ListHead))
        return FALSE;
 
    //-f--> Get the first node address.
    pEntry = m_ListHead.Flink;
 
    //-f--> While pEntry is not the head list node address,
    //      it means we have a valid node address.
    while(pEntry != &m_ListHead)
    {
        //-f--> Get the node structure base address.
        pMyNode = (PMY_NODE) CONTAINING_RECORD(pEntry, MY_NODE, Entry);
 
        //-f--> Check if this is the node we're looking for.
        if (RtlEqualUnicodeString(pusLookFor,
                                  &pMyNode->usSomeData,
                                  TRUE))
        {
            //-f--> Returning TRUE to indicate the node was found.
            return TRUE;
        }
 
        //-f--> Get the next node address.
        pEntry = pEntry->Flink;
    }
 
    //-f--> If we got here, it means that the node we were looking for
    //      was not found. So, returning FALSE to indicate that.
    return FALSE;
}

NOTE: The above example is only used to illustrate the search for a node. To implement a search like this in a production environment, you must keep in mind issues about multiple thread access synchronism control and reference counters.

To manipulate lists formed by LIST_ENTRY, you can use routines like InsertHeadList(), InsertTailList(), RemoveHeadList() and so on. I will not list all the functions here, I’m sure DDK reference do it better than me.

For both types of lists, there are functions like ExInterlockedXxxList that take a Spin Lock to synchronize changes in the list. Remember that if you synchronize access to lists using Spin Locks, all nodes must reside in non-paged memory. As some of you may know, when acquiring a Spin Lock, the thread IRQL goes to DISPATCH_LEVEL. In this IRQL, Memory Manager is unable to retrieve data page that was paged out to disk, resulting in a BugCheck.

It is also important to remember that you should not mix the use of ExInterlockedXxxList functions with unsynchronized ones. If a list is accessed by multiple threads, all access to it should be controlled.

typedef struct _SLIST_ENTRY {
  struct _SLIST_ENTRY *Next;
} SLIST_ENTRY, *PSLIST_ENTRY;

The SLIST_ENTRY structure is an alternative to SINGLE_LIST_ENTRY lists with synchronized access. This version aims at being more efficient using the functions like ExInterlockedPopEntryList() and ExInterlockedPushEntryList(). Unlike other structures presented here, the list ending is formed by a different structure of that used on its nodes; this structure is the SLIST_HEADER, which is an opaque structure that should be initialized by ExInitializeSListHead() function.

Other advantage on using this list type is that DDK offers the ExQueryDepthSList() function, which returns the number of nodes stored the list.

If your main problem is performance, then the ideal situation would be to use the group of functions that work with Generic Tables. The list head is defined by an opaque structure called RTL_GENERIC_TABLE. This structure, along with its manipulation functions, such as RtlGetElementGenericTable(), creates binary trees with self balancing. What a chic thing, huh?

But Generic Tables is an issue that deserves a dedicated post. Until next time!

One Response to “Linked lists on DDK”

  1. yk says:

    What started as a Google search for CONTAINING_RECORD turned into a background overview of kernel linked lists. Cheers for the info!

Leave a Reply