ExInterlockedInsertTailList.C

/*
链表一个重要的概念，
数据结构里面有，内核里面有双链表。

本文主要操作的是同步安全的双链表。
不用单链表的原因是，内核里面的结构大多是双链表。

应用层的有stl等。
那几个应用层的链表API不适用，还不如自己实现链表的结构和操作。

内核中的主要操作安全性的双链表的函数有：
KeInitializeSpinLock
InitializeListHead
ExInterlockedInsertTailList //插入尾，这是正常的思维。
ExInterlockedInsertHeadList //这个不常用，特殊的情况下使用。
ExInterlockedRemoveHeadList //带锁的双链表没有尾删除的。所以使用的用途第队列不是堆栈。
IsListEmpty //这个可以不用。

本文是简单的示例，要使用，还要进一步的加强。
链表怎能不会，光看别人的代码是不行的，必须自己体验：编码调试。
微软没有完整的例子，所以自己写。
made by correy
made at 2012.12.07
QQ:112426112
Email:kouleguan at hotmail dot com
Homepage:http://correy.webs.com
*/

#include <ntddk.h>

KSPIN_LOCK g_sl;
LIST_ENTRY g_le;

#define TAG 'tset' //test

typedef struct _dl{ //加不加下划线都可以。
    LIST_ENTRY le;
    int x;
}dl;//定义指针会出错。不知啥原因。*dl

VOID OnUnload(IN PDRIVER_OBJECT DriverObject) { }

void InsertTail()
{
    int i = 0;

    for (i = 0; i < 9; i++)
    {
        dl * dl1 = (dl *)ExAllocatePoolWithTag(NonPagedPool, sizeof(dl), TAG);//不能用栈内空间，否则移除会蓝屏。
        if (dl1 == NULL)
        {
            return;
        }

        dl1->x = i;
        ExInterlockedInsertTailList(&g_le, &dl1->le, &g_sl);//前两个个参数的顺序翻了会蓝屏的,并且注意第二个参数的用法。
        DbgPrint("%08x\n",dl1->x);
    }
}

void Ergodic_chain_table()
{
    LIST_ENTRY * p = g_le.Flink;//&g_le;//

    do
    {
        dl * temp = CONTAINING_RECORD(p, dl, le);      
        p = p->Flink;
        if (p == g_le.Flink)//不加这一句的后果是：这样会再最后一次多现实第一个一次。
        {
            break;
        }
        DbgPrint("%08x\n",temp->x);
    } while (p != g_le.Flink);
}

void RemoveHead()
{
    PLIST_ENTRY temp;

    do
    {
        temp = ExInterlockedRemoveHeadList(&g_le, &g_sl);
        if (temp)
        {
            dl * dl2 = CONTAINING_RECORD(temp, dl, le);//是一个宏，用于取自己定义的结构的指针。
            DbgPrint("%08x\n",dl2->x);
            ExFreePoolWithTag(dl2, TAG);
        }
    } while (temp != 0);//为啥是不等呢？还有分号。
}

NTSTATUS DriverEntry(PDRIVER_OBJECT DriverObject,PUNICODE_STRING RegistryPath)
{
    KdBreakPoint();//#define KdBreakPoint() DbgBreakPoint()
    DriverObject->DriverUnload = OnUnload;

    KeInitializeSpinLock(&g_sl);
    InitializeListHead(&g_le);

    InsertTail();//插入，形成一个双链表示例
    Ergodic_chain_table();//遍历示例。查询就是添加个比较的条件而已。
    RemoveHead();//从全部头删除示例

    return STATUS_SUCCESS;
}


//添加一些函数.
int InsertTail(HANDLE pid) //插入一个到尾部 HANDLE DWORD
{
    dl * dl1;

    dl1 = (dl *)ExAllocatePoolWithTag(NonPagedPool, sizeof(dl), TAG);//不能用栈内空间，否则移除会蓝屏。
    if (dl1 == NULL)
    {
        return 0 /*false*/;
    }

    dl1->x = pid;

    if (ExInterlockedInsertTailList(&g_le, &dl1->le, &g_sl) == 0)//前两个个参数的顺序翻了会蓝屏的,并且注意第二个参数的用法。
    { //第一次操作，链表为空，ExInterlockedInsertTailList返回值为0。
        return 1 /*false*/;
    }

    KdPrint(("成功插入：%d\n",pid));

    return 1 /*true*/;
}

int delete_node(HANDLE pid) //DWORD
{
    LIST_ENTRY * p = g_le.Flink;//&g_le;//
    dl * head = CONTAINING_RECORD(p, dl, le);

    do
    {
        dl * temp = CONTAINING_RECORD(p, dl, le);      
        p = p->Flink;
        if (p == g_le.Flink)//不加这一句的后果是：这样会再最后一次多现实第一个一次。
        {
            break;
        }

        if (temp->x == pid)
        {
            //没有删除特定节点的函数，所以自己实现:
            /*
            1.替换链表的节点的指针，把本节点释放掉。
            * p = temp->le;
            ExFreePoolWithTag(temp, TAG);
            2.把第一个节点的值赋值给指定的节点，然后ExInterlockedRemoveHeadList删除第一个。
            3.把指定的节点的值赋值给0，这个值是没有用的。但这样做浪费内存。
            4.删除链表的特定的节点:
              遍历,从头删除,不是就添加到尾部,
                              是就直接删除,不再添加.
              不过要先判断一下存在不,以防使循环.
              还可以先添加在删除(看看允许重复添加不).
            */

            temp->x = head->x;//注意这个结构的一些操作最好加锁同步。
            ExInterlockedRemoveHeadList(&g_le, &g_sl);//IsListEmpty

            KdPrint(("成功删除：%d\n",pid));

            return 1;
        }      

    } while (p != g_le.Flink);

    KdPrint(("删除失败：%d\n",pid));
    return 0;
}

BOOLEAN find (HANDLE pid) //查询  DWORD
{
    LIST_ENTRY * p = g_le.Flink;//&g_le;//

    do
    {
        dl * temp = CONTAINING_RECORD(p, dl, le);      
        p = p->Flink;
        if (p == g_le.Flink)//不加这一句的后果是：这样会再最后一次多现实第一个一次。
        {
            //KdPrint(("没有找到：%d\n",temp->x));//这个显示的频率太多.
            break;
        }

        if (temp->x == pid)
        {
            //KdPrint(("成功找到：%d\n",temp->x));//这个显示的频率太多.
            return 1;
        }
    } while (p != g_le.Flink);

    return 0;
}

int ListAll() //遍历示例。
{
    LIST_ENTRY * p = g_le.Flink;//&g_le;//

    KdPrint(("开始显示\n"));

    do
    {
        dl * temp = CONTAINING_RECORD(p, dl, le);      
        p = p->Flink;
        if (p == g_le.Flink)//不加这一句的后果是：这样会再最后一次多现实第一个一次。
        {
            break;
        }

        KdPrint(("pid：%d\n",temp->x));

    } while (p != g_le.Flink);

    KdPrint(("显示结束\n\n"));

    return 0;
}

void RemoveAll() //从全部头删除示例
{
    PLIST_ENTRY temp;
    NTSTATUS status = STATUS_UNSUCCESSFUL;

    do
    {
        temp = ExInterlockedRemoveHeadList(&g_le, &g_sl);
        if (temp)
        {
            dl * dl2 = CONTAINING_RECORD(temp, dl, le);//是一个宏，用于取自己定义的结构的指针。
            ExFreePoolWithTag(dl2, TAG);
        }
    } while (temp != 0);//为啥是不等呢？还有分号。
}

//以后添加单链表的操作,因为但链表的操作更多,只不过要加个同步的处理而已.