- 注册时间
- 2011-3-6
- 最后登录
- 1970-1-1
该用户从未签到
|
内核数据结构
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] |
|