c++ - 迭代单链表不工作的驱动程序

Question

我正在尝试编写一个实现 md5 哈希单链表的驱动程序。

我目前的代码是:

签名.h

#ifndef SIGNATURE_H
#define SIGNATURE_H

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

#endif

签名列表.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;
    }
}

主.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"));

我真的想不通..它没有崩溃，WinDBG 输出是:

我已阅读 this blog post和 this msdn article但我仍然不知道我的驱动程序出了什么问题

Answer 1

我看到几个可能的问题。

• 您的循环未正确初始化。

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

第一次通过这个循环，pSig指向 Head 不是 SIGNATURE 的一部分结构，所以调用 CONTAINING_RECORD导致无意义的指针。

• 您也没有正确退出循环。单向链表的末尾由空指针表示，而不是由指向表头的指针表示。

• 而且，对于三元组，您也没有正确地递增列表:

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

Sig->next指向当前节点，而不是下一个节点。

• IsListEmpty适用于双链表，而不是单链表。该代码甚至不应该编译。

• 选择PSINGLE_LIST_ENTRY而不是 SINGLE_LIST_ENTRY对于 Head是奇数，初始化 Head 的代码不见了。

• 参数hash被声明为 32 个字符的数组，它应该是 33 个字符以允许空终止符。

我认为函数应该更像这样:

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

另外，请注意 SINGLE_LINKED_LIST 更常见成为结构的第一个元素，并称它为next具有误导性。像这样的东西可能更可取:

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