看流星社区

 找回密码
 注册账号
查看: 1943|回复: 0

内核数据结构总结

[复制链接]

该用户从未签到

发表于 2017-6-1 13:34:14 | 显示全部楼层 |阅读模式
内核数据结构
1.LIST_ENTRY
2.HASH表
3.TREE树
4.LookAside结构


一.LIST_ENTRY
typedef _struct _MYDATA_LIST
{
    LIST_ENTRY Entry;
    WCHAR NameBuffer[MAX_PATH];
} MYDATA_LIST_ENTRY,
*PMYDATA_LIST_ENTRY;
PLIST_ENTRY                    pListHead;//头指针


typedef struct _LIST_ENTRY
{
   struct _LIST_ENTRY *Flink;
   struct _LIST_ENTRY *Blink;
} LIST_ENTRY,*PLIST_ENTRY;
[/code]





获取成员在结构体中的偏移

#define offsetof(s,m) (size_t)&(((s *)0)->m)  [/code]


根据上面得到Entry
PMYDATA_LIST_ENTRY  dataEntry = CONTAINING_RECORD(pList, MYDATA_LIST_ENTRY, Entry);
dataEntry->wszFileName
#define CONTAINING_RECORD(address, type, field) ((type *)( \
                                                  (PCHAR)(address) - \
                                                  (ULONG_PTR)(&((type *)0)->field)))
[/code]


LIST_ENTRY使用方法
   
LIST_ENTRY                    listHead;//头指针


PMYDATA_LIST_ENTRY  tmpEntry;//结点,须自己初始化值


InitializeListHead(&listHead);//初始化


InsertHeadList(&listHead, &tmpEntry->Entry); //结点头插入
InsertTailList(&listHead, &tmpEntry->Entry); //结点尾插入
如果是接点头移除 节点为插入则为队列
头部插入头部删除 就是栈 尾部插入 尾部删除也是栈




IsListEmpty(&listHead);//判断是否为空链表


PLIST_ENTRY listEntry = RemoveHeadList(&listHead);//移除
PLIST_ENTRY listEntry = RemoveTailList(&listHead);//移除[/code]



//枚举
PLIST_ENTRY         plistHead        = &listHead;
PLIST_ENTRY         pList         = NULL;
PMYDATA_LIST_ENTRY         dataEntry         = NULL;
For(pList = plistHead ->Flink; pList != plistHead; pList = pList->Flink)
{
        dataEntry = CONTAINING_RECORD(pList,
                                                                MYDATA_LIST_ENTRY, Entry);
        DbgPrint(“%S\n”, dataEntry->NameBuffer);
}
RemoveEntryList(&dataEntry->Entry);


//删除
while(!IsListEmpty(&listHead))
{
listEntry = RemoveHeadList(&listHead);
dataEntry = CONTAINING_RECORD(
listEntry,
SBPROCESS_ENTRY,
Entry
);
DbgPrint(“%ws\n”, dataEntry->NameBuffer);
RemoveEntryList(listEntry);//删除接点
ExFreePool(dataEntry);
}
[/code]


例子:删除文件夹下的所有文件
#include <ntddk.h>


typedef unsigned long ULONG;
typedef struct _FILE_DIRECTORY_INFORMATION {
    ULONG NextEntryOffset;
    ULONG FileIndex;
    LARGE_INTEGER CreationTime;
    LARGE_INTEGER LastAccessTime;
    LARGE_INTEGER LastWriteTime;
    LARGE_INTEGER ChangeTime;
    LARGE_INTEGER EndOfFile;
    LARGE_INTEGER AllocationSize;
    ULONG FileAttributes;
    ULONG FileNameLength;
    WCHAR FileName[1];
} FILE_DIRECTORY_INFORMATION, *PFILE_DIRECTORY_INFORMATION;


typedef struct _FILE_LIST_ENTRY {


    LIST_ENTRY Entry;
    PWSTR NameBuffer;


} FILE_LIST_ENTRY, *PFILE_LIST_ENTRY;




NTSTATUS
ZwQueryDirectoryFile(
    __in HANDLE  FileHandle,
    __in_opt HANDLE  Event,
    __in_opt PIO_APC_ROUTINE  ApcRoutine,
    __in_opt PVOID  ApcContext,
    __out PIO_STATUS_BLOCK  IoStatusBlock,
    __out PVOID  FileInformation,
    __in ULONG  Length,
    __in FILE_INFORMATION_CLASS  FileInformationClass,
    __in BOOLEAN  ReturnSingleEntry,
    __in_opt PUNICODE_STRING  FileName,
    __in BOOLEAN  RestartScan
    );


NTSTATUS
dfDeleteFile(const WCHAR *fileName)
{
    OBJECT_ATTRIBUTES                        objAttributes        = {0};
    IO_STATUS_BLOCK                            iosb                        = {0};
    HANDLE                                   handle                        = NULL;
    FILE_DISPOSITION_INFORMATION            disInfo                        = {0};
        UNICODE_STRING                                                uFileName                = {0};
    NTSTATUS                                status                        = 0;


        RtlInitUnicodeString(&uFileName, fileName);


    InitializeObjectAttributes(&objAttributes, &uFileName,
        OBJ_KERNEL_HANDLE | OBJ_CASE_INSENSITIVE, NULL, NULL);


    status = ZwCreateFile(
                &handle,
                SYNCHRONIZE | FILE_WRITE_DATA | DELETE,
        &objAttributes,
                &iosb,
                NULL,
                FILE_ATTRIBUTE_NORMAL,
        FILE_SHARE_READ | FILE_SHARE_WRITE | FILE_SHARE_DELETE,
                FILE_OPEN,
        FILE_SYNCHRONOUS_IO_NONALERT | FILE_DELETE_ON_CLOSE,
                NULL,
                0);
    if (!NT_SUCCESS(status))
        {
        if (status == STATUS_ACCESS_DENIED)
                {
            status = ZwCreateFile(
                                &handle,
                                SYNCHRONIZE | FILE_READ_ATTRIBUTES | FILE_WRITE_ATTRIBUTES,
                &objAttributes,
                                &iosb,
                                NULL,
                                FILE_ATTRIBUTE_NORMAL,
                FILE_SHARE_READ | FILE_SHARE_WRITE | FILE_SHARE_DELETE,
                                FILE_OPEN,
                FILE_SYNCHRONOUS_IO_NONALERT,
                                NULL,
                                0);
            if (NT_SUCCESS(status))
                        {
                FILE_BASIC_INFORMATION        basicInfo = {0};


                status = ZwQueryInformationFile(handle, &iosb,
                    &basicInfo, sizeof(basicInfo), FileBasicInformation);
                if (!NT_SUCCESS(status))
                                {
                    KdPrint(("ZwQueryInformationFile(%wZ) failed(%x)\n", &uFileName, status));
                }
                  
                basicInfo.FileAttributes = FILE_ATTRIBUTE_NORMAL;
                status = ZwSetInformationFile(handle, &iosb,
                    &basicInfo, sizeof(basicInfo), FileBasicInformation);
                if (!NT_SUCCESS(status))
                                {
                    KdPrint(("ZwSetInformationFile(%wZ) failed(%x)\n", &uFileName, status));
                }


                ZwClose(handle);
                status = ZwCreateFile(
                                        &handle,
                                        SYNCHRONIZE | FILE_WRITE_DATA | DELETE,
                    &objAttributes,
                                        &iosb,
                                        NULL,
                                        FILE_ATTRIBUTE_NORMAL,
                    FILE_SHARE_READ | FILE_SHARE_WRITE | FILE_SHARE_DELETE,
                                        FILE_OPEN,
                    FILE_SYNCHRONOUS_IO_NONALERT | FILE_DELETE_ON_CLOSE,
                                        NULL,
                                        0);
            }
        }


        if (!NT_SUCCESS(status))
                {
            KdPrint(("ZwCreateFile(%wZ) failed(%x)\n", &uFileName, status));
            return status;
        }
    }


    disInfo.DeleteFile = TRUE;
    status = ZwSetInformationFile(handle, &iosb,
        &disInfo, sizeof(disInfo), FileDispositionInformation);
    if (!NT_SUCCESS(status))
        {
        KdPrint(("ZwSetInformationFile(%wZ) failed(%x)\n", &uFileName, status));
    }


    ZwClose(handle);
    return status;
}


NTSTATUS
dfDeleteDirectory(const WCHAR * directory)
{
        OBJECT_ATTRIBUTES                        objAttributes        = {0};
    IO_STATUS_BLOCK                            iosb                        = {0};
    HANDLE                                    handle                        = NULL;
    FILE_DISPOSITION_INFORMATION            disInfo                        = {0};
    PVOID                                    buffer                        = NULL;
    ULONG                                    bufferLength        = 0;
    BOOLEAN                                    restartScan                = FALSE;
    PFILE_DIRECTORY_INFORMATION                dirInfo                        = NULL;
    PWSTR                                    nameBuffer                = NULL;        //记录文件夹
    UNICODE_STRING                            nameString                = {0};
    NTSTATUS                                status                        = 0;
    LIST_ENTRY                                listHead                = {0};        //链表,用来存放删除过程中的目录
    PFILE_LIST_ENTRY                        tmpEntry                = NULL;        //链表结点
    PFILE_LIST_ENTRY                        preEntry                = NULL;
        UNICODE_STRING                                                uDirName                = {0};


        RtlInitUnicodeString(&uDirName, directory);


    nameBuffer = (PWSTR) ExAllocatePoolWithTag(PagedPool, uDirName.Length + sizeof(WCHAR), 'DRID');
    if (!nameBuffer)
        {
        return STATUS_INSUFFICIENT_RESOURCES;
    }


    tmpEntry = (PFILE_LIST_ENTRY) ExAllocatePoolWithTag(PagedPool, sizeof(FILE_LIST_ENTRY), 'DRID');
    if (!tmpEntry)
        {
        ExFreePool(nameBuffer);
        return STATUS_INSUFFICIENT_RESOURCES;
    }


    RtlCopyMemory(nameBuffer, uDirName.Buffer, uDirName.Length);
    nameBuffer[uDirName.Length / sizeof(WCHAR)] = L'\0';


    InitializeListHead(&listHead);        //初始化链表
    tmpEntry->NameBuffer = nameBuffer;
    InsertHeadList(&listHead, &tmpEntry->Entry);        //将要删除的文件夹首先插入链表   


        //listHead里初始化为要删除的文件夹。
        //之后遍历文件夹下的文件和目录,判断是文件,则立即删除;判断是目录,则放进listHead里面
        //每次都从listHead里拿出一个目录来处理
    while (!IsListEmpty(&listHead))
        {


                //先将要删除的文件夹和之前打算删除的文件夹比较一下,如果从链表里取下来的还是之前的Entry,表明没有删除成功,说明里面非空
                //否则,已经成功删除,不可能是它自身;或者还有子文件夹,在前面,也不可能是它自身。
        tmpEntry = (PFILE_LIST_ENTRY) RemoveHeadList(&listHead);
        if (preEntry == tmpEntry)
                {
            status = STATUS_DIRECTORY_NOT_EMPTY;
            break;
        }


        preEntry = tmpEntry;
        InsertHeadList(&listHead, &tmpEntry->Entry); //放进去,等删除了里面的内容,再移除。如果移除失败,则说明还有子文件夹或者目录非空


        RtlInitUnicodeString(&nameString, tmpEntry->NameBuffer);
        InitializeObjectAttributes(&objAttributes, &nameString,
            OBJ_CASE_INSENSITIVE, NULL, NULL);
       //打开文件夹,进行查询
        status = ZwCreateFile(
                        &handle,
                        FILE_ALL_ACCESS,
            &objAttributes,
                        &iosb,
                        NULL,
                        0,
                        0,
                        FILE_OPEN,
            FILE_SYNCHRONOUS_IO_NONALERT,
                        NULL,
                        0);
        if (!NT_SUCCESS(status))
                {
            KdPrint(("ZwCreateFile(%ws) failed(%x)\n", tmpEntry->NameBuffer, status));
            break;
        }
                //从第一个扫描
        restartScan = TRUE;
        while (TRUE)
                {


            buffer = NULL;
            bufferLength = 64;
            status = STATUS_BUFFER_OVERFLOW;


            while ((status == STATUS_BUFFER_OVERFLOW) || (status == STATUS_INFO_LENGTH_MISMATCH))
                        {
                if (buffer)
                                {
                    ExFreePool(buffer);
                }
               
                bufferLength *= 2;
                buffer = ExAllocatePoolWithTag(PagedPool, bufferLength, 'DRID');
                if (!buffer)
                                {
                    KdPrint(("ExAllocatePool failed\n"));
                    status = STATUS_INSUFFICIENT_RESOURCES;
                    break;
                }


                status = ZwQueryDirectoryFile(handle, NULL, NULL,
                    NULL, &iosb, buffer, bufferLength, FileDirectoryInformation,
                    FALSE, NULL, restartScan);
            }


            if (status == STATUS_NO_MORE_FILES)
                        {
                ExFreePool(buffer);
                status = STATUS_SUCCESS;
                break;
            }


            restartScan = FALSE;


            if (!NT_SUCCESS(status))
                        {
                KdPrint(("ZwQueryDirectoryFile(%ws) failed(%x)\n", tmpEntry->NameBuffer, status));
                if (buffer)
                                {
                    ExFreePool(buffer);
                }
                break;
            }


            dirInfo = (PFILE_DIRECTORY_INFORMATION) buffer;


            nameBuffer = (PWSTR) ExAllocatePoolWithTag(PagedPool,
                                wcslen(tmpEntry->NameBuffer) * sizeof(WCHAR) + dirInfo->FileNameLength + 4, 'DRID');
            if (!nameBuffer)
                        {
                KdPrint(("ExAllocatePool failed\n"));
                ExFreePool(buffer);
                status = STATUS_INSUFFICIENT_RESOURCES;
                break;
            }


                        //tmpEntry->NameBuffer是当前文件夹路径
                        //下面的操作在拼接文件夹下面的文件路径


            RtlZeroMemory(nameBuffer, wcslen(tmpEntry->NameBuffer) * sizeof(WCHAR) + dirInfo->FileNameLength + 4);
            wcscpy(nameBuffer, tmpEntry->NameBuffer);
            wcscat(nameBuffer, L"\\");
            RtlCopyMemory(&nameBuffer[wcslen(nameBuffer)], dirInfo->FileName, dirInfo->FileNameLength);
            RtlInitUnicodeString(&nameString, nameBuffer);


            if (dirInfo->FileAttributes & FILE_ATTRIBUTE_DIRECTORY)
                        {
                                //如果是非'.'和'..'两个特殊的目录,则将目录放入listHead
                if ((dirInfo->FileNameLength == sizeof(WCHAR)) && (dirInfo->FileName[0] == L'.'))
                                {
                                       
                }
                                else if ((dirInfo->FileNameLength == sizeof(WCHAR) * 2) &&
                                        (dirInfo->FileName[0] == L'.') &&
                                        (dirInfo->FileName[1] == L'.'))
                                {
                }
                                else
                                {
                                        //将文件夹插入listHead中
                    PFILE_LIST_ENTRY localEntry;
                    localEntry = (PFILE_LIST_ENTRY) ExAllocatePoolWithTag(PagedPool, sizeof(FILE_LIST_ENTRY), 'DRID');
                    if (!localEntry)
                                        {
                        KdPrint(("ExAllocatePool failed\n"));
                        ExFreePool(buffer);
                        ExFreePool(nameBuffer);
                        status = STATUS_INSUFFICIENT_RESOURCES;
                        break;
                    }


                    localEntry->NameBuffer = nameBuffer;
                    nameBuffer = NULL;
                    InsertHeadList(&listHead, &localEntry->Entry); //插入头部,先把子文件夹里的删除
                }
            }
                        else
                        {
                                //文件,直接删除
                status = dfDeleteFile(nameBuffer);
                if (!NT_SUCCESS(status))
                                {
                    KdPrint(("dfDeleteFile(%wZ) failed(%x)\n", &nameString, status));
                    ExFreePool(buffer);
                    ExFreePool(nameBuffer);
                    break;
                }
            }


            ExFreePool(buffer);
            if (nameBuffer)
                        {
                ExFreePool(nameBuffer);
            }//继续在循环里处理下一个子文件或者子文件夹
        }//  while (TRUE) ,一直弄目录里的文件和文件夹


        if (NT_SUCCESS(status))
                {
                        //再删除目录
            disInfo.DeleteFile = TRUE;
            status = ZwSetInformationFile(handle, &iosb,
                &disInfo, sizeof(disInfo), FileDispositionInformation);
            if (!NT_SUCCESS(status))
                        {
                KdPrint(("ZwSetInformationFile(%ws) failed(%x)\n", tmpEntry->NameBuffer, status));
            }
        }


        ZwClose(handle);


        if (NT_SUCCESS(status))
                {
                        //删除成功,从链表里移出该目录
            RemoveEntryList(&tmpEntry->Entry);
            ExFreePool(tmpEntry->NameBuffer);
            ExFreePool(tmpEntry);
        }
                //如果失败,则表明在文件夹还有子文件夹,继续先删除子文件夹
    }// while (!IsListEmpty(&listHead))


    while (!IsListEmpty(&listHead))
        {
        tmpEntry = (PFILE_LIST_ENTRY) RemoveHeadList(&listHead);
        ExFreePool(tmpEntry->NameBuffer);
        ExFreePool(tmpEntry);
    }


    return status;
}


VOID DriverUnload(PDRIVER_OBJECT pDriverObject)
{
        DbgPrint("Goodbye Driver\n");
}


NTSTATUS DriverEntry(PDRIVER_OBJECT pDriverObject, PUNICODE_STRING pRegPath)
{
        pDriverObject->DriverUnload = DriverUnload;
        dfDeleteDirectory(L"\\??\\e:\\Program Files");
        return STATUS_SUCCESS;
}
[/code]



二:Hash表
typedef struct _ELEMENT
{
    int x;
} ELEMENT, *PELEMENT;
typedef struct _HNODE
{
        DWORD key;
        ELEMENT data;
        LIST_ENTRY linkfield;
} HNODE, *PHNODE;
typedef struct _HASHTABLE
{
        unsigned int tableSize;
        PLIST_ENTRY *pListHeads;
} HASHTABLE, *PHASHTABLE;


PHASHTABLE InitializeTable(unsigned int tableSize);
PTWOWAY Find(DWORD key,
        PHASHTABLE pHashTable)
void Insert(DWORD key, PELEMENT pData,
        PHASHTABLE pHashTable);
void Remove(DWORD key,
        PHASHTABLE pHashTable);
void DestroyTable(PHASHTABLE pHashTable);
ULONG DumpTable(PHASHTABLE pHashTable);[/code]



FileMon4.34HASH表的使用


Hash表可以看做数组 数组的大小是质数(我的理解是MAP)
比如我们的Hash表有7个元素
那么我想存同学的成绩,Name等等
每个同学都有学号
比如我想存13号同学的成绩
那么13%7 = 6 那么我们在元素6下存下13号同学的信息等等
但是现在我又想存6号同学的成绩 那么6 % 7 = 6 我们又要存在6号元素下 但是6下有数据了怎么办了
那么就碰撞了 这个时候我们引用LIST_ENTRY 即Value是LIST_ENTRY 这样就可以解决这个问题了
我们需要记下学号 然后遍历链表找到相关的信息即可


KEYVALUE
常用的KEY:
EPROCESS%size
FILE_OBJECT%size
MD5%size


例子:
Hash.h

#ifndef _Hash_H
#define _Hash_H


typedef unsigned char BYTE;
typedef unsigned long DWORD;
typedef unsigned short WORD;


typedef struct _DATA
{
        unsigned int threadID;
        unsigned int processID;
        BYTE *imageName;
        unsigned xlow;
        unsigned xhigh;
} DATA, *PDATA;


typedef struct _ELEMENT
{
        unsigned int threadID;
        unsigned int processID;
        unsigned xlow;
        unsigned xhigh;
        BYTE imageName[16];
} ELEMENT, *PELEMENT;


typedef struct _TWOWAY
{
        DWORD key;
        ELEMENT data;
        LIST_ENTRY linkfield;
} TWOWAY, *PTWOWAY;


typedef struct _HASHTABLE
{
        unsigned int tableSize;
        PLIST_ENTRY *pListHeads;
} HASHTABLE, *PHASHTABLE;
typedef struct _HASHTABLE HASHTABLE, *PHASHTABLE;


PHASHTABLE InitializeTable(unsigned int tableSize);
void Insert(DWORD key, PDATA pData, PHASHTABLE pHashTable);
void Remove(DWORD key, PHASHTABLE pHashTable);
void DestroyTable(PHASHTABLE pHashTable);
ULONG DumpTable(PHASHTABLE pHashTable);


#endif // _Hash_H
[/code]

Hash.c


// Functions that implement the separate chaining hashtable algorithms.
// The skeletons for these algorithms was taken from the book
// "Data Structures and Algorithm Analysis in C, Second Edition" by
// Mark Allen Weiss.
//
// Kimmo


#include "ntddk.h"
#include "ntstrsafe.h"
#include "hash.h"


#define DRIVERTAG1 'HSAH'
extern DWORD num;






PNPAGED_LOOKASIDE_LIST pLookasideList_TWOWAY = NULL;


/* Return next prime; assume N >= 10 */
static unsigned int NextPrime(int N)
{
    int i;


    if( N % 2 == 0 )
        N++;
    for( ; ; N += 2 )
    {
        for( i = 3; i * i <= N; i += 2 )
            if( N % i == 0 )
                goto ContOuter;  /* Sorry about this! */
        return N;
        ContOuter: ;
    }
}


unsigned int Hash(DWORD key, unsigned int tableSize)
{
        return key % tableSize;
}


PHASHTABLE InitializeTable(unsigned int tableSize)
{
        PHASHTABLE pHashTable = NULL;
        PTWOWAY pNode = NULL;
        unsigned int i;


        // Allocate space for the hashtable
        pHashTable = ExAllocatePoolWithTag(NonPagedPool, sizeof(HASHTABLE), DRIVERTAG1);
        if (pHashTable == NULL)
        {
                DbgPrint("ExAllocatePoolWithTag returned NULL!\n");
                return NULL;
        }


        pHashTable->tableSize = NextPrime(tableSize);


        // Allocate array of pointers to linkedlists
        pHashTable->pListHeads = ExAllocatePoolWithTag(NonPagedPool, sizeof(PLIST_ENTRY) * pHashTable->tableSize, DRIVERTAG1);
        if (pHashTable->pListHeads == NULL)
        {
                DbgPrint("ExAllocatePoolWithTag returned NULL!\n");
                return NULL;
        }


        // Allocate space for the lookaside list for the TWOWAY-structures.
        pLookasideList_TWOWAY = ExAllocatePoolWithTag(NonPagedPool, sizeof(NPAGED_LOOKASIDE_LIST), DRIVERTAG1);
        if (pLookasideList_TWOWAY == NULL)
        {
                DbgPrint("ExAllocatePoolWithTag returned NULL!\n");
                return NULL;
        }


        // Initialize the lookaside list.
        ExInitializeNPagedLookasideList(
                pLookasideList_TWOWAY,
                NULL,
                NULL,
                0,
                sizeof(TWOWAY),
                DRIVERTAG1,
                0);


        // Allocate empty nodes for the each linked list.
        for (i = 0; i < pHashTable->tableSize; i++)
        {
                pNode = ExAllocateFromNPagedLookasideList(pLookasideList_TWOWAY);
                if (pNode == NULL)
                {
                        DbgPrint("ExAllocateFromNPagedLookasideList returned NULL!\n");
                        return NULL;
                }
                else
                {
                        pNode->key = 0x00000000;
                        RtlZeroMemory(&pNode->data, sizeof(ELEMENT));
                        InitializeListHead(&pNode->linkfield);
                }
                pHashTable->pListHeads = &pNode->linkfield;
        }


        return pHashTable;
}


PTWOWAY Find(DWORD key, PHASHTABLE pHashTable)
{
        PTWOWAY pNode = NULL;
        PLIST_ENTRY pListHead = NULL;
        PLIST_ENTRY pListLink = NULL;


        pListHead = pListLink = pHashTable->pListHeads[Hash(key, pHashTable->tableSize)];
        if (pListHead == NULL)
        {
                DbgPrint("pListHead is NULL!\n");
                return NULL;
        }


        if (!IsListEmpty(pListHead))
        {
                do
                {
                        pNode = CONTAINING_RECORD(pListLink, TWOWAY, linkfield);
                        if (pNode->key == key)
                        {
                                return pNode;
                        }
                        pListLink = pListLink->Flink;
                } while (pListLink != pListHead);
        }


        return NULL;
}


void Insert(DWORD key, PDATA pData, PHASHTABLE pHashTable)
{
        PTWOWAY pNode = NULL;
        PTWOWAY pNewNode = NULL;
        PLIST_ENTRY pListHead = NULL;


        pNode = Find(key, pHashTable);
        // The node with the given key was not found.
        if (pNode == NULL)
        {
                pNewNode = ExAllocateFromNPagedLookasideList(pLookasideList_TWOWAY);
                if (pNewNode == NULL)
                {
                        DbgPrint("ExAllocateFromNPagedLookasideList returned NULL!\n");
                        return;
                }
               
                // Insert the data to the node.
                pNewNode->key = key;
                pNewNode->data.threadID = pData->threadID;
                pNewNode->data.processID = pData->processID;
                pNewNode->data.xlow = pData->xlow;
                pNewNode->data.xhigh= pData->xhigh;
                if (STATUS_SUCCESS != RtlStringCbCopyA(pNewNode->data.imageName, 16, pData->imageName))
                {
                        DbgPrint("RtlStringCbCopyA failed!\n");
                }


                // Insert the node to the doubly-linked list.
                pListHead = pHashTable->pListHeads[Hash(key, pHashTable->tableSize)];
                InsertTailList(pListHead, &pNewNode->linkfield);
                //num++;
#ifdef MY_DEBUG
                DbgPrint("INSERT: thread ID = 0x%x process ID = 0x%x image = %s\n", pData->threadID, pData->processID, pData->imageName);
#endif
        }
#ifdef MY_DEBUG
        else
        {
                if (pNode->data.processID != pData->processID)
                {
                        Remove(key, pHashTable);
                        pNewNode = ExAllocateFromNPagedLookasideList(pLookasideList_TWOWAY);
                        if (pNewNode == NULL)
                        {
                                DbgPrint("ExAllocateFromNPagedLookasideList returned NULL!\n");
                                return;
                        }
               
                        // Insert the data to the node.
                        pNewNode->key = key;
                        pNewNode->data.threadID = pData->threadID;
                        pNewNode->data.processID = pData->processID;
                        pNewNode->data.xlow = pData->xlow;
                        pNewNode->data.xhigh= pData->xhigh;
                        if (STATUS_SUCCESS != RtlStringCbCopyA(pNewNode->data.imageName, 16, pData->imageName))
                        {
                                DbgPrint("RtlStringCbCopyA failed!\n");
                        }


                        // Insert the node to the doubly-linked list.
                        pListHead = pHashTable->pListHeads[Hash(key, pHashTable->tableSize)];
                        InsertTailList(pListHead, &pNewNode->linkfield);
                        //num++;
                        DbgPrint("Node with key = 0x%x already in list\n", key);
                        DbgPrint("OLD: thread ID = 0x%x process ID = 0x%x image = %s\n", pNode->data.threadID, pNode->data.processID, pNode->data.imageName);
                        DbgPrint("NEW: thread ID = 0x%x process ID = 0x%x image = %s\n", pData->threadID, pData->processID, pData->imageName);
                }
        }
#endif
}


void Remove(DWORD key, PHASHTABLE pHashTable)
{
        PTWOWAY pNode = NULL;
        PLIST_ENTRY pListHead = NULL;


        pNode = Find(key, pHashTable);


        // The node with the given key was found.
        if (pNode != NULL)
        {
#ifdef MY_DEBUG
                DbgPrint("REMOVE: thread ID = 0x%x process ID = 0x%x image = %s\n", pNode->data.threadID, pNode->data.processID, pNode->data.imageName);
#endif
                RemoveEntryList(&pNode->linkfield);
                ExFreeToNPagedLookasideList(pLookasideList_TWOWAY, pNode);
        }
        //num--;
}


void DestroyTable(PHASHTABLE pHashTable)
{
        PTWOWAY pNode = NULL;
        PTWOWAY pTmpNode = NULL;
        PLIST_ENTRY pListHead = NULL;
        PLIST_ENTRY pListLink = NULL;
            unsigned int i;


        for (i = 0; i < pHashTable->tableSize; i++)
        {
                pListHead = pListLink = pHashTable->pListHeads;
                if (pListHead == NULL)
                {
                        DbgPrint("pListHead is NULL!\n");
                        continue;
                }
                if (!IsListEmpty(pListHead))
                {
                        do
                        {
                                pNode = CONTAINING_RECORD(pListLink, TWOWAY, linkfield);
                                pListLink = pListLink->Flink;
                                ExFreeToNPagedLookasideList(pLookasideList_TWOWAY, pNode);
                        } while (pListLink != pListHead);
                }
                else
                {
                        pNode = CONTAINING_RECORD(pListHead, TWOWAY, linkfield);
                        ExFreeToNPagedLookasideList(pLookasideList_TWOWAY, pNode);
                }
        }
        num = 0;


        ExDeleteNPagedLookasideList(pLookasideList_TWOWAY);
        ExFreePoolWithTag(pLookasideList_TWOWAY, DRIVERTAG1);
        ExFreePoolWithTag(pHashTable->pListHeads, DRIVERTAG1);
        ExFreePoolWithTag(pHashTable, DRIVERTAG1);
}


ULONG  DumpTable(PHASHTABLE pHashTable)
{
        PTWOWAY pNode = NULL;
        PLIST_ENTRY pListHead = NULL;
        PLIST_ENTRY pListLink = NULL;
       unsigned int i;
        ULONG total = 0;


        for (i = 0; i < pHashTable->tableSize; i++)
        {
                pListHead = pListLink = pHashTable->pListHeads;
                if (pListHead == NULL)
                {
                        DbgPrint("pListHead is NULL!\n");
                        continue;
                }
                if (!IsListEmpty(pListHead))
                {
                        do
                        {
                                pNode = CONTAINING_RECORD(pListLink, TWOWAY, linkfield);
                                pListLink = pListLink->Flink;
                                if (pNode->key != 0)
                                {
                                        //DbgPrint("key = 0x%8x  threadID = %4d  processID = %4ld  image = %s\n",
                                                //pNode->key, pNode->data.threadID, pNode->data.processID, pNode->data.imageName);
                                    total++;
                                }
                        } while (pListLink != pListHead);
                }
        }
        return total;
}
[/code]

三:平衡树

如果HASH还是无法满足需要,怎么办?
WRK里面的:AvlTable.c (\wrk-v1.2\base\ntos\rtl)
使用方法:
RTL_AVL_TABLE         g_FileNameTable;
RtlInitializeGenericTableAvl(
                                &g_FileNameTable,
                        CompareNameFunc,
                        AllocateFunc,
                        FreeFunc,
                        NULL);
ExAcquireFastMutex(&g_FileNameTableMutex);
RtlInsertElementGenericTableAvl(&g_FileNameTable, &Key, sizeof(FILE_NAME_ENTRY), NULL);
ExReleaseFastMutex(&g_FileNameTableMutex);
[/code]


四:LookAside结构 这个不太用到 就不详见说了
频繁的内存分配产生空洞和碎片
频繁分配固定大小内存
LookAside类别
PAGED_LOOKASIDE_LIST
NPAGED_LOOKASIDE_LIST


PAGED_LOOKASIDE_LIST g_pageList;
ExInitializePagedLookasideList(
&g_pageList,
NULL,
NULL,
0,
sizeof(MYDATA),
‘HSAH',
0);


MYDATA * pMyData = (MYDATA*)
        ExAllocateFromPagedLookasideList(
        &g_pageList);


ExFreeToPagedLookasideList(
        &g_pageList,
        pMyData);
ExDeletePagedLookasideList(&g_pageList);
[/code]
点击按钮快速添加回复内容: 支持 高兴 激动 给力 加油 苦寻 生气 回帖 路过 感恩
您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

小黑屋|手机版|Archiver|看流星社区 |网站地图

GMT+8, 2024-3-19 19:19

Powered by Kanliuxing X3.4

© 2010-2019 kanliuxing.com

快速回复 返回顶部 返回列表