{"id":108,"date":"2007-02-24T13:50:19","date_gmt":"2007-02-24T13:50:19","guid":{"rendered":"https:\/\/driverentry.com.br\/en\/2007\/02\/24\/linked-lists-on-ddk\/"},"modified":"2026-07-25T13:35:54","modified_gmt":"2026-07-25T13:35:54","slug":"linked-lists-on-ddk","status":"publish","type":"post","link":"https:\/\/driverentry.com.br\/en\/2007\/02\/24\/linked-lists-on-ddk\/","title":{"rendered":"Linked lists on DDK"},"content":{"rendered":"
\"\"<\/a><\/div>\n

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\u00a0course at\u00a0ETE Jorge Street<\/a>.\u00a0An excellent school and I learned a lot there.\u00a0However I have only learned what a linked list is in a professional environment during my internship.\u00a0Years later, the university introduced me to these lists in form of classes written in Java<\/a>, where we dealt with references and garbage collectors<\/a>. Even those who work with Visual C\/C++, handles, templates and classes offered by MFC<\/a>, ATL<\/a>, WTL<\/a> and STL<\/a>, which end up abstracting real linked list implementation.\u00a0In this post, I will talk a little about resources offered by DDK<\/strong> regarding to this subject.<\/p>\n

But I am already a big boy and I already know how to build linked lists in C\/C++.\u00a0Why should I use DDK resources?<\/h3>\n

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<\/strong> structures, it would be, at least, interesting to know how they are stored in lists.\u00a0Some situations require you to know how to use DDK<\/strong> lists.\u00a0An example is: If you implement the custom control queue for IRPs<\/a> in your driver, the pIrp->Tail.Overlay.ListEntry<\/em> field will be free to be used while such IRP<\/strong> is held by your driver.<\/p>\n

The simplest of these resources is SINGLE_LIST_ENTRY<\/a> structure that is defined at ntdef.h<\/em>, as shown below:<\/p>\n

\n
typedef<\/span> struct<\/span> _SINGLE_LIST_ENTRY {<\/pre>\n
  struct<\/span> _SINGLE_LIST_ENTRY *Next;<\/pre>\n
} SINGLE_LIST_ENTRY, *PSINGLE_LIST_ENTRY;<\/pre>\n<\/div>\n
A\u00a0SINGLE_LIST_ENTRY<\/strong> variable must be set to be the head of our list.\u00a0This variable should have its Next <\/em>member initialized with NULL before being used.\u00a0The\u00a0PushEntryList()<\/a> and\u00a0PopEntryList()<\/a> routines\u00a0are used respectively to add and remove elements from the list head.\u00a0Like most linked lists, nodes are referenced by the Next <\/em>member until it is NULL, thus indicating the node chain\u00a0ending.<\/p>\n
\n
VOID <\/pre>\n
  PushEntryList(<\/pre>\n
    IN PSINGLE_LIST_ENTRY  ListHead,<\/pre>\n
    IN PSINGLE_LIST_ENTRY  Entry<\/pre>\n
    );<\/pre>\n
 <\/pre>\n
PSINGLE_LIST_ENTRY <\/pre>\n
  PopEntryList(<\/pre>\n
    IN PSINGLE_LIST_ENTRY  ListHead<\/pre>\n
    );<\/pre>\n<\/div>\n
But wait a minute.\u00a0All this is beautiful, but isn’t anything missing?<\/strong> 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.\u00a0In the example below, the pNext<\/em> member is the one responsible for it.<\/p>\n
\n
\/\/-f--> Structure that defines the node list<\/span><\/pre>\n
\/\/      which will be used as an example.<\/span><\/pre>\n
typedef<\/span> struct<\/span> _MY_NODE<\/pre>\n
{<\/pre>\n
    \/\/-f--> Your private data that will be defined<\/span><\/pre>\n
    \/\/      by yourself.<\/span><\/pre>\n
    UNICODE_STRING      usSomeData;<\/pre>\n
    ULONG               ulAnotherData;<\/pre>\n
    struct<\/span> _MY_NODE     *pNext;<\/pre>\n
    PVOID               pMoreData;<\/pre>\n
 <\/pre>\n
} MY_NODE, *PMY_NODE;<\/pre>\n<\/div>\n
But from what we could see at the DDK <\/strong>structure, there are no useful members on it, those ones that contain information that will be kept in the list, like fields as usSomeData<\/em> or pMoreData<\/em>.\u00a0At the structure offered by the DDK<\/strong>, there is only the next node address.<\/p>\n
What is the point on saving only nodes?<\/h3>\n
Actually, the SINGLE_LIST_ENTRY<\/strong> structure as well as other DDK lists\u00a0structures should be used in conjunction with the CONTAINING_RECORD<\/a> macro.\u00a0This macro returns the structure\u00a0base address that contains a known\u00a0field in a known address.\u00a0Well, 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<\/strong> in our previous example.\u00a0Thus, we would have the following structure:<\/p>\n
\n
\/\/-f--> Structure that defines a register on our linked list<\/span><\/pre>\n
\/\/      and will be used in this example<\/span><\/pre>\n
typedef<\/span> struct<\/span> _MY_NODE<\/pre>\n
{<\/pre>\n
    \/\/-f--> Register's private data on the list node.<\/span><\/pre>\n
    \/\/      These fields are not fixed and defined by you.<\/span><\/pre>\n
    UNICODE_STRING      usSomeData;<\/pre>\n
    ULONG               ulAnotherData;<\/pre>\n
 <\/pre>\n
    \/\/-f--> That member doesn't necessarily need<\/span><\/pre>\n
    \/\/      to be the first or the last one at this structure;<\/span><\/pre>\n
    \/\/      it can be at any position here inside.<\/span><\/pre>\n
    SINGLE_LIST_ENTRY   Entry;<\/pre>\n
 <\/pre>\n
    \/\/-f--> More data<\/span><\/pre>\n
    PVOID               pMoreData;<\/pre>\n
 <\/pre>\n
} MY_NODE, *PMY_NODE;<\/pre>\n<\/div>\n
Our structure is basically the same, except the member pNext, which has now been changed to use the structure SINGLE_LIST_ENTRY<\/strong>. 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<\/strong> nodes.<\/p>\n
\n
NTSTATUS PrepareDataAndPush(VOID)<\/pre>\n
{<\/pre>\n
    PMY_NODE            pMyNode;<\/pre>\n
 <\/pre>\n
    \/\/-f--> Here we get the already allocated node<\/span><\/pre>\n
    \/\/      with its fields correctly initialized.<\/span><\/pre>\n
    pMyNode = AllocateAndFillNode();<\/pre>\n
 <\/pre>\n
    \/\/-f--> Testing is never too much.<\/span><\/pre>\n
    ASSERT(pMyNode != NULL);<\/pre>\n
 <\/pre>\n
    \/\/-f--> To put the node at the list, it is necessary to use<\/span><\/pre>\n
    \/\/      the SINGLE_LIST_ENTRY member address.<\/span><\/pre>\n
    PushEntryList(&m_ListHead, &pMyNode->Entry);<\/pre>\n
 <\/pre>\n
    return<\/span> STATUS_SUCCESS;<\/pre>\n
}<\/pre>\n<\/div>\n
At the time  to include the node in the list, we use the SINGLE_LIST_ENTRY<\/strong> member address, as suggested by the PushEntryList <\/strong>prototype function.  Follow the example below that demonstrates how to get this node using PopEntryList<\/strong> function. This function returns the address passed to PushEntryList<\/strong> function, which is a PSINGLE_LIST_ENTRY<\/strong>. From this address, as I had commented before, we can get the base address of our structure using CONTAINING_RECORD<\/strong> macro. See the example below.<\/p>\n
\n
NTSTATUS PopAndProcessNode(VOID)<\/pre>\n
{<\/pre>\n
    PSINGLE_LIST_ENTRY  pEntry;<\/pre>\n
    PMY_NODE            pMyNode;<\/pre>\n
 <\/pre>\n
    \/\/-f--> Here we get the node from the list.<\/span><\/pre>\n
    pEntry = PopEntryList(&m_ListHead);<\/pre>\n
 <\/pre>\n
    \/\/-f--> Now we can check if a register really was retrieved<\/span><\/pre>\n
    \/\/      from the list.<\/span><\/pre>\n
    if<\/span> (!pEntry)<\/pre>\n
        return<\/span> STATUS_NO_MORE_ENTRIES;<\/pre>\n
 <\/pre>\n
    \/\/-f--> Now we use the CONTAINING_RECORD macro<\/span><\/pre>\n
    \/\/      to get the base address we need.<\/span><\/pre>\n
    pMyNode = (PMY_NODE) CONTAINING_RECORD(pEntry, MY_NODE, Entry);<\/pre>\n
 <\/pre>\n
    \/\/-f--> Now we can access the whole structure.<\/span><\/pre>\n
    ProcessAndFreeNode(pMyNode);<\/pre>\n
 <\/pre>\n
    return<\/span> STATUS_SUCCESS;<\/pre>\n
}<\/pre>\n<\/div>\n
This same style is also used with the LIST_ENTRY<\/a> structure, which is the one used in most drivers. This  structure allows you to create doubly linked lists, and like  SINGLE_LIST_ENTRY<\/strong>, a LIST_ENTRY<\/strong> variable is set to be our list head. Its initialization is done using InitializeListHead()<\/a> function, which initializes the Flink<\/em> and Blink<\/em> members with the list head address.<\/p>\n
\n
typedef<\/span> struct<\/span> _LIST_ENTRY {<\/pre>\n
  struct<\/span> _LIST_ENTRY *Flink;<\/pre>\n
  struct<\/span> _LIST_ENTRY *Blink;<\/pre>\n
} LIST_ENTRY, *PLIST_ENTRY;<\/pre>\n<\/div>\n
The Flink<\/em> member points to the next node, whereas the Blink<\/em> member points to the previous node. Unlike most linked lists we know, its endings are not marked by NULL at Flink<\/em> and Blink<\/em> 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<\/strong> structures, use IsListEmpty()<\/a> function.<\/p>\n
\n
\/\/-f--> Looks for a node through a list<\/span><\/pre>\n
\/\/      composed by nodes using LIST_ENTRY structures.<\/span><\/pre>\n
BOOLEAN SearchEntry(PUNICODE_STRING  pusLookFor)<\/pre>\n
{<\/pre>\n
    PLIST_ENTRY pEntry;<\/pre>\n
    PMY_NODE    pMyNode;<\/pre>\n
 <\/pre>\n
    \/\/-f--> Before any operation, it is necessary<\/span><\/pre>\n
    \/\/      to check for an empty list condition.<\/span><\/pre>\n
    if<\/span> (IsListEmpty(&m_ListHead))<\/pre>\n
        return<\/span> FALSE;<\/pre>\n
 <\/pre>\n
    \/\/-f--> Get the first node address.<\/span><\/pre>\n
    pEntry = m_ListHead.Flink;<\/pre>\n
 <\/pre>\n
    \/\/-f--> While pEntry is not the head list node address,<\/span><\/pre>\n
    \/\/      it means we have a valid node address.<\/span><\/pre>\n
    while<\/span>(pEntry != &m_ListHead)<\/pre>\n
    {<\/pre>\n
        \/\/-f--> Get the node structure base address.<\/span><\/pre>\n
        pMyNode = (PMY_NODE) CONTAINING_RECORD(pEntry, MY_NODE, Entry);<\/pre>\n
 <\/pre>\n
        \/\/-f--> Check if this is the node we're looking for.<\/span><\/pre>\n
        if<\/span> (RtlEqualUnicodeString(pusLookFor,<\/pre>\n
                                  &pMyNode->usSomeData,<\/pre>\n
                                  TRUE))<\/pre>\n
        {<\/pre>\n
            \/\/-f--> Returning TRUE to indicate the node was found.<\/span><\/pre>\n
            return<\/span> TRUE;<\/pre>\n
        }<\/pre>\n
 <\/pre>\n
        \/\/-f--> Get the next node address.<\/span><\/pre>\n
        pEntry = pEntry->Flink;<\/pre>\n
    }<\/pre>\n
 <\/pre>\n
    \/\/-f--> If we got here, it means that the node we were looking for<\/span><\/pre>\n
    \/\/      was not found. So, returning FALSE to indicate that.<\/span><\/pre>\n
    return<\/span> FALSE;<\/pre>\n
}<\/pre>\n<\/div>\n
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.<\/strong><\/p>\n
To manipulate lists formed by LIST_ENTRY<\/strong>, you can use routines like InsertHeadList()<\/a>, InsertTailList()<\/a>, RemoveHeadList()<\/a> and so on. I will not list all the functions here, I’m sure DDK <\/strong>reference do it better than me.<\/p>\n
For both types of lists, there are functions like ExInterlockedXxxList<\/strong> that take a Spin Lock<\/em> to synchronize changes in the list. Remember that if you synchronize access to lists using Spin Locks<\/em>, all nodes must reside in non-paged memory. As some of you may know, when acquiring a Spin Lock<\/em>, the thread IRQL<\/a> goes to DISPATCH_LEVEL<\/strong>. In this IRQL, Memory Manager<\/em> is unable to retrieve data page that was paged out to disk, resulting in a BugCheck<\/a>.<\/p>\n
It is also important to remember that you should not mix the use of ExInterlockedXxxList<\/strong> functions with unsynchronized ones. If a list is accessed by multiple threads, all access to it should be controlled.<\/p>\n
\n
typedef<\/span> struct<\/span> _SLIST_ENTRY {<\/pre>\n
  struct<\/span> _SLIST_ENTRY *Next;<\/pre>\n
} SLIST_ENTRY, *PSLIST_ENTRY;<\/pre>\n<\/div>\n
The SLIST_ENTRY<\/a> structure is an alternative to SINGLE_LIST_ENTRY<\/strong> lists with synchronized access. This version aims at being more efficient using the functions like ExInterlockedPopEntryList()<\/a> and ExInterlockedPushEntryList()<\/a>. 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<\/strong>, which is an opaque structure that should be initialized by ExInitializeSListHead()<\/a> function.<\/p>\n
Other  advantage on using this list type is that DDK<\/strong> offers the ExQueryDepthSList()<\/a> function, which returns the number of nodes stored the list.<\/p>\n
If your main problem is performance, then the ideal situation would be to use the group of functions that work with Generic Tables<\/em>. The list head is defined by an opaque structure called RTL_GENERIC_TABLE<\/strong>. This  structure, along with its manipulation functions, such as  RtlGetElementGenericTable()<\/a>, creates binary trees with self balancing. What a chic thing, huh?<\/p>\n
But Generic Tables<\/em> is an issue that deserves a dedicated post. Until next time!<\/p>\n","protected":false},"excerpt":{"rendered":"
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\u00a0course at\u00a0ETE Jorge Street.\u00a0An excellent school and I learned a lot there.\u00a0However I have only learned what a linked list is in a professional environment during my […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"pagelayer_contact_templates":[],"_pagelayer_content":"","footnotes":""},"categories":[1],"tags":[],"class_list":["post-108","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/driverentry.com.br\/en\/wp-json\/wp\/v2\/posts\/108","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/driverentry.com.br\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/driverentry.com.br\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/driverentry.com.br\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/driverentry.com.br\/en\/wp-json\/wp\/v2\/comments?post=108"}],"version-history":[{"count":1,"href":"https:\/\/driverentry.com.br\/en\/wp-json\/wp\/v2\/posts\/108\/revisions"}],"predecessor-version":[{"id":109,"href":"https:\/\/driverentry.com.br\/en\/wp-json\/wp\/v2\/posts\/108\/revisions\/109"}],"wp:attachment":[{"href":"https:\/\/driverentry.com.br\/en\/wp-json\/wp\/v2\/media?parent=108"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/driverentry.com.br\/en\/wp-json\/wp\/v2\/categories?post=108"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/driverentry.com.br\/en\/wp-json\/wp\/v2\/tags?post=108"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}