64位内核开发第十三讲,内核中常用的链表等数据结构

内核中常用的数据结构

数据结构

1.何为数据结构

不管是Ring0还是Ring3数据结构都是必须要知道的.数据结构是一种思想. 以及怎么存储数据. 跟语言无关.平台无关.

如:(链表,数组,栈,队列.图.树...)

ring0下数据结构非彼数据结构. 意思就是数据结构思想都是一样的. 你只需要熟悉ring0下数据结构怎么定义的.以及使用即可.

ring0常见的数据结构:

双向链表

** LIST_ENTRY**

** HASH 表 TREE 树**

** LookAside**

2.方便使用的数据结构双向链表 (LIST_ENTRY)

typedef struct _LIST_ENTRY {
   struct _LIST_ENTRY *Flink;
   struct _LIST_ENTRY *Blink;
} LIST_ENTRY, *PLIST_ENTRY, *RESTRICTED_POINTER PRLIST_ENTRY;

FLINK(front)前向指针 指向后一个节点 BLink(back)后向指针.指向前边的指针.

相应的还是 LIST_ENTRY64 以及 LIST_ENTRY32

typedef struct LIST_ENTRY32 {
    ULONG Flink;
    ULONG Blink;
} LIST_ENTRY32;
typedef LIST_ENTRY32 *PLIST_ENTRY32;
typedef struct LIST_ENTRY64 {
    ULONGLONG Flink;
    ULONGLONG Blink;
} LIST_ENTRY64;
typedef LIST_ENTRY64 *PLIST_ENTRY64;

求出结构体所在的位置

CONTAINING_RECORD(address,type,field);

展开:

#define CONTAINING_RECORD(address, type, field) ((type *)( \
                                                  (PCHAR)(address) - \
                                                  (ULONG_PTR)(&((type *)0)->field)))

使用方法:

它的作用就是求出field在type中的偏移.然后用address - 偏移 得到位置.

如下:

typedef struct _MY_DATA
{
  ULONG a;
  ULONG b;
  LIST_ENTRY MyEntry;
}MY_DATA,*PMY_DATA

PMY_DATA plist;

PMY_DATA list = CONTAINING_RECORD(pList,MY_DATA,MyEntry);

寻找结构体的偏移.

3.list_entry 的使用

使用就很简单了.跟鞋ring3代码一样.

LIST_ENTRY listHead; 
PMY_DATA plist; //对我们自定义结构进行初始化.

InitializeListHead(&listHead); //初始化ListHead

//插入数据

InsertHeadLisst(&listHead,&plist->MyEntry);//将这个结构放到头结点中.

InSertTailList(&listHead,&pList->MyEntry); //尾部插入.

PLIST_ENTRY pRemList = RemoveHeadList(&listHead); //移除头结点
pRemList  pRemList = RemoveTailList(&listHead) //尾部移除.

二丶 平衡树.

使用现成的树. 在 wrk-v1.2\base\ntos\rtl里面有一个文件

AvlTable.c. 这里面就有树.抠出代码来即可使用.

WDK中 有一个树 RTL_AVL_TABLE 这个是WDK中的.

可以自己实现.也可以自己做. 主要是要了解 LIST_ENTRY

三丶 LookAside结构.

我们调用 malloc new 或者 ExAllocatePoolWithTag等分配内存的 时候.都会产生碎片.

而对于我们频繁分配内存.每次都是固定大小的时候.如结构体. 就可以使用这个结构用来分配.

它有两种分配类别. 一种是分页内存.一种是非分页内存.

** PAGED_LOOKASIDE_LIST ** 分页 ** NPAGED_LOOKASIDE_LIST ** 非分页

使用方法:

PAGED_LOOKASIDE_LIST MyPagedList;

//第一步要初始化.你指定你要分配的大小
ExInitializePagedLookasideList(&MyPagedList,NULL,NULL,NULL,0,sizeof(MY_DATA),'BINI',0):
注意sizeof(MY_DATA) 这个是你指定的.

//分配内存
MY_DATA *pData = ExAllocatFromPagedLookasideList(&MyPagedList);

//释放内存
ExFreeToPageLookasideList(&MyPagedList,pdata);//注意要还回去.

//卸载的时候要删除
ExDeletPageLookasideList(&MyPagedList);

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券