Delphi研究之驅動開發篇（五）--使用後備列表

作 者: mickeylan
時 間: 2008-02-03,11:24
鏈 接: http://bbs.pediy.com/showthread.php?t=59265

上篇教程我們介紹了驅動開發中如何使用系統內存堆，這一節讓我們看看後備列表的使用。堆管理器管理著系統和用戶堆，它把堆空間分為相同尺寸的塊(block)。堆管理器會根據堆分配請求，去選擇一個合適尺寸的未使用的塊。顯然，這個過程需要點時間。如果你需要固定尺寸的內存塊，但是你事先並不知道它的大小和使用頻率，這樣的話為了性能的原因，你還是使用後備列表（Lookaside Lists）吧，後備列表是只有內核模式才有的。
後備列表和系統內存池的主要的區別是什麼呢？後備列表只可以分配固定大小的事先定義尺寸的內存塊。後備列表會快很多，因為它不需要去搜索可用的未分配的內存。
當你剛接觸後備列表，你需要解決的問題不是怎麼創建後備列表，而是管理你要分配的內存塊。
具體來說，你把你要使用和釋放的內存存貯在哪裡? 怎麼存貯？這不是個簡單的問題，因為你不知道塊的數量。有三種結構來解決這個問題：
◎ 單向鏈表(Singly linked list)
◎ S-list排序的單向鏈表（S-list, sequenced singly-linked list） (單向鏈表的改進)
◎ 雙向鏈表（Doubly linked list）

我們將只接觸雙向鏈表，因為它最通用。
如果你是第一次接觸後備列表和雙向鏈表這些概念，你會覺得下面的代碼有點復雜，但實際上它們是非常簡單的。
後備列表（lookaside list）和雙向鏈表（Doubly linked list）的英文名稱都有一個"list"，但是它們是完全不同的。後備列表是一組事先分配的相同尺寸的內存塊。這些塊有些在使用，有些沒被使用。當有內存分配請求的時候，系統會遍歷這個列表尋找最近的未分配的塊。如果未分配的塊找到了，分配請求就很快被滿足了。否則系統必須從分頁或不分頁內存池去分配。根據列表中分配行為發生的頻率，系統會自動調整未分配塊的數量來滿足分配請求，分配的頻率越高，會有越多的塊被存儲在後備列表中。後備列表如果總是不被使用，也會自動減少空間大小。
雙向鏈表是數據組織的一種形式。可以很方便地把同類結構連接在一起，並且很容易遍歷。雙向鏈表被系統廣泛地使用來處理內部結構。

我想了半天，也沒有找到一個適合的簡單的例子。所以下面這個驅動程序好像意義不大。但是可以幫助你理解相關的概念，還有雙向鏈表。
這裡也沒有提供驅動控制程序。你可以使用KmdKit4D 包中的KmdManager 或者類似的工具，還可以使用DebugView或SoftICE 控制台來查看調試信息。

代碼:unit LookasideList;

interface

uses
    nt_status, ntoskrnl, macros;

function _DriverEntry(pDriverObject: PDRIVER_OBJECT;
                    pusRegistryPath: PUNICODE_STRING): NTSTATUS; stdcall;

implementation

type
    PSOME_STRUCTURE = ^SOME_STRUCTURE;
    SOME_STRUCTURE = record
      SomeField1: DWORD;
      SomeField2: DWORD;
      { . . .}                            {這裡放入一些別的字段}
      ListEntry: LIST_ENTRY;              {主角^_^，可以放在結構的開始}
                                        {放在這裡是為了演示的需要}
      { . . .}                            {這裡放入一些別的字段}
      SomeFieldX: DWORD;
    end;

var
    g_pPagedLookasideList: PPAGED_LOOKASIDE_LIST;
    g_ListHead: LIST_ENTRY;
    g_dwIndex: DWORD;
    dwCnt: DWORD;

procedure AddEntry;
var
    pEntry: PSOME_STRUCTURE;
begin
    {從後備列表中分配內存塊}
    pEntry := ExAllocateFromPagedLookasideList(g_pPagedLookasideList);
    if pEntry <> nil then
    begin
      DbgPrint(LookasideList: + Memory block allocated from lookaside list at address %08X#13#10, pEntry);
      {初始化分配到的內存}
      memset(pEntry, 0, sizeof(SOME_STRUCTURE));
      {一個節點可以添加到鏈表的頭部、尾部或者其他地方，視個人喜好了}
      {本例添加到表頭}
      InsertHeadList(@g_ListHead, @pEntry^.ListEntry);
      {使用SomeField1保存表項的索引. 這是為了讓我們能看見它在工作.}

      inc(g_dwIndex);
      pEntry^.SomeField1 := g_dwIndex;
      DbgPrint(LookasideList: + Entry #%d added#13#10, pEntry^.SomeField1);
    end else
    begin
      DbgPrint(LookasideList: Very bad. Couldnt allocate from lookaside list#13#10);
    end;
end;

procedure RemoveEntry;
var
    pEntry, pTemp: pointer;
    ss: SOME_STRUCTURE;
    offs: DWORD;
begin
    if IsListEmpty(@g_ListHead) <> TRUE then
    begin
      {刪除表項也一樣，可以從頭、尾或者其他地方刪除,}
      {這裡我們還是從頭部開始刪除.}

      {計算offs是因為RemoveHeadList返回的是SOME_STRUCTURE.ListEntry的地址}
      {offs就是SOME_STRUCTURE.ListEntry到結構開始處的偏移量}
      offs := DWORD(@ss.ListEntry) - DWORD(@ss);

      {這裡pEntry ==> SOME_STRUCTURE.ListEntry}
      {我們需要得到指向包含這個ListEntry的SOMT_STRUCTURE結構的指針}
      {以便釋放內存，用pEntry - offs即可得到結構的指針.}
      pEntry := RemoveHeadList(@g_ListHead);

      {pTemp ==> SOME_STRUCTURE，這裡一定要弄明白}
      pTemp := pointer(DWORD(pEntry) - offs);
      DbgPrint(LookasideList: - Entry #%d removed#13#10,
               PSOME_STRUCTURE(pTemp)^.SomeField1);

      {向後備列表歸還不用的內存}
      ExFreeToPagedLookasideList(g_pPagedLookasideList, pTemp);
      DbgPrint(LookasideList: - Memory block at address %08X returned to lookaside list#13#10, pTemp);
    end else
    begin
     &n