Iterating a singly linked list not working drivers

Question

I'm trying to code a driver that implements a singly linked list for md5 hashes.

The code I have so far is:

Signature.h

#ifndef SIGNATURE_H
#define SIGNATURE_H

typedef struct {
    char hash[33]; // last byte for null terminator
    SINGLE_LIST_ENTRY next;
} SIGNATURE, *PSIGNATURE;

#endif

SignatureList.h

#define CopyCharArrays(src, dest, len)      \
do {                                    \
    for (int i = 0; i < len; i++)       \
        dest[i] = src[i];               \
    dest[len] = '\0';                   \
} while(0)           

/* Return TRUE if strings are equal */
static BOOLEAN IsEqual(char* str1, char* str2, int len)
{
    for (int i = 0; i < len; i++)
        if (str1[i] != str2[i])
            return FALSE;

    return TRUE;
}
SINGLE_LIST_ENTRY Head;

static void AddToSignatureList(char hash[32]) {
    PSIGNATURE Sig = ExAllocatePool(NonPagedPoolNx, sizeof(SIGNATURE)); // allocate memory to store a SIGNATURE node

    CopyCharArrays(hash, Sig->hash, 32); // place the hash in our new allocated node (puts null terminator at position 33)

    DbgPrintEx(0, DPFLTR_ERROR_LEVEL, "Hash: %s\n", Sig->hash);
    PushEntryList(&Head, &Sig->next); // insert the new node in our list
}

/*Returns TRUE if the hash is in the library*/
static BOOLEAN SignatureScan(char hash[32])
{
    if (IsListEmpty(Head)) { // if there is no signature in the index
        return FALSE;
    }
    else {
        PSINGLE_LIST_ENTRY pSig = Head; // this is the pointer we will use to iterate
        PSIGNATURE Sig;

        do {
            Sig = CONTAINING_RECORD(pSig, SIGNATURE, next); // get the PSIGNATURE on the current pointer

            DbgPrintEx(0, DPFLTR_ERROR_LEVEL, "%s - %s\n", Sig->hash, hash);
            if (!IsEqual(Sig->hash, hash, 32)) {
                return TRUE;
            }

            pSig = &Sig->next; // go to the next node
        } while (pSig != Head);

        return FALSE;
    }
}

Main.c

AddToSignatureList("2d75cc1bf8e57872781f9cd04a529256");
AddToSignatureList("00f538c3d410822e241486ca061a57ee");
AddToSignatureList("3f066dd1f1da052248aed5abc4a0c6a1");
AddToSignatureList("781770fda3bd3236d0ab8274577dddde");
AddToSignatureList("86b6c59aa48a69e16d3313d982791398");

DbgPrintEx(0, DPFLTR_ERROR_LEVEL, "Should return TRUE: %d\n", SignatureScan("3f066dd1f1da052248aed5abc4a0c6a1"));
DbgPrintEx(0, DPFLTR_ERROR_LEVEL, "Should return FALSE: %d\n", SignatureScan("3f066dd1f1da052248aed5abc4a0c6a2"));
DbgPrintEx(0, DPFLTR_ERROR_LEVEL, "Should return FALSE: %d\n", SignatureScan("526ae1b5f10eccfa069f4fd1c8b18097"));

I can't really figure out.. It doesn't crash and the WinDBG output is:

I have read this blog post and this msdn article but I still don't know what is wrong in my driver

Answer 1

I see several likely issues.

• Your loop isn't being initialized correctly.

  PSINGLE_LIST_ENTRY pSig = Head;
  PSIGNATURE Sig;
  
  do {
      Sig = CONTAINING_RECORD(pSig, SIGNATURE, next);
  

The first time through this loop, pSig is pointing at Head which is not part of a SIGNATURE structure, so the call to CONTAINING_RECORD results in a meaningless pointer.

• You're not exiting the loop correctly either. The end of a singly-linked list is represented by a null pointer, not by a pointer to the header.

• And, going for the triple, you aren't incrementing the list properly either:

  pSig = &Sig->next; // go to the next node
  

Sig->next points to the current node, not the next node.

• IsListEmpty is for doubly-linked lists, not singly-linked lists. That code shouldn't even compile.

• The choice of PSINGLE_LIST_ENTRY rather than SINGLE_LIST_ENTRY for Head is odd, and the code that initializes Head is missing.

• The argument hash is declared as a 32-character array, it should be 33 characters to allow for the null terminator.

I think the function should look more like this:

SINGLE_LIST_ENTRY Head = {NULL};

static BOOLEAN SignatureScan(char hash[33])
{
    PSINGLE_LIST_ENTRY pSig = Head->Next;
    PSIGNATURE Sig;

    while (pSig != NULL)
    {
        Sig = CONTAINING_RECORD(pSig, SIGNATURE, next);

        DbgPrintEx(0, DPFLTR_ERROR_LEVEL, "%s - %s\n", Sig->hash, hash);

        if (!strcmp(Sig->hash, hash)) return TRUE;

        pSig = pSig->Next;
    }

    return FALSE;
}

Also, note that it is more usual for the SINGLE_LINKED_LIST to be the first element of the structure, and that calling it next is misleading. Something like this might be preferable:

typedef struct {
    SINGLE_LIST_ENTRY list_node;
    char hash[33]; // last byte for null terminator
} SIGNATURE, *PSIGNATURE;