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

To step through your code a bit at a time and see where the values are/aren't what you expect. — aschepler
– aschepler, Commented Apr 13, 2017 at 22:50
char[32] ==> char[33]. Your terminated strings container 32 characters and a nullchar character, which you're not providing space for. Probability is high the initial copy to your nodes is breaching your buffer and invoking UB. — WhozCraig
– WhozCraig, Commented Apr 13, 2017 at 22:53
@L3n You need to account space for the terminator yourself. I also question your use of double-indirection, pSig = &Sig->next. That has a code smell on its own. It may just be a thing I'm not used to seeing, but it looks odd. Regardless, the buffer size is definitely a problem. — WhozCraig
– WhozCraig, Commented Apr 13, 2017 at 22:54
@ZanLynx, I think the code as currently posted in the question is a combination of old and new code. Head was originally a PSINGLE_LINKED_LIST. — Harry Johnston
– Harry Johnston, Commented Apr 14, 2017 at 21:54

Harry Johnston · Accepted Answer · 2017-04-14 01:32:12Z

2

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;

edited Apr 14, 2017 at 1:32

answered Apr 14, 2017 at 0:55

Harry Johnston

36.7k7 gold badges74 silver badges169 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

David Gomes Over a year ago

thanks for the effort, btw in the parameters I can put 32 length right? also is AddToSignatureList right?

Harry Johnston Over a year ago

You're using strcmp so the hash array must allow space for the null terminator. If you used memcmp instead you might not need one, although you'd also have to update the debug statement accordingly. I don't see anything wrong in AddToSignatureList, assuming that CopyCharArrays does the right thing.

David Gomes Over a year ago

Added to the signaturelist.h btw I used a do {} while(0) uselessly because I was getting a compiler error and after googling I concluded that I need that.

Harry Johnston Over a year ago

Easy enough to add in debug statements to check, at the end of the add method and the beginning of the scan method, whether or not Head->Next is null.

Harry Johnston Over a year ago

Perhaps the SIGNATURE structure is being tightly packed so the pointer is misaligned? Add some code to verify that the address of Sig->next is a multiple of eight.

|

Collectives™ on Stack Overflow

Iterating a singly linked list not working drivers

1 Answer 1

10 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related