ヒープの仕組み (Look Aside List, ルックアサイドリスト)

この資料では Windows XP 以前のデフォルトであった、ルックアサイドリスト (Look Aside List, LAL) をフロントエンドアロケータとする、ヒープメモリの仕組みについてご説明します。

尚、Vista 以降では LAL ではなく、LFH (Low Fragmentation Heap) がデフォルトとなり、 またセキュリティ対策のためにヒープマネージャには大きな変更が加えられました。 これについては別の資料で書きたいと思います。この資料では特に断りが無い限り、ヒープと言えば LAL を利用するヒープのことを指しています。

ちなみに、はじめにお断りしておきますが、この資料は主にこちらの Advanced Windows Debugging とインターネット上の情報をもとに、 私が動作確認をして記述しました。

可能な限りデバッガで動作確認をしていますが、私の理解不足などが原因で細部を誤っているところがあるかと思いますので、 他の資料も参考にしつつご理解くださいますようお願いします。(ソースが無いと調べきれない部分が多いので確認しようがありませんでした...)

ヒープの概要

フロントエンドアロケータとバックエンドアロケータ

ヒープの構造は大まかに言って、フロントエンドアロケータ (Front End Allocator) とバックエンドアロケータ (Back End Allocator) に分けられます。

フロントエンドアロケータは、メモリ割り当てを最適化するために配置されます。

Windows では前述の通り、以下の２種類のフロンドエンドアロケータをサポートします。

  • ルック・アサイド・リスト (Look Aside List, LAL)
  • ロー・フラグメンテーション (Low Fragmentation, LF)

LAL は Windows XP 以前でデフォルトです。Windows Vista 以降は LF がデフォルトになりました。

この資料では LAL ヒープについて説明します。

バックエンドアロケータは、要はヒープの構造そのものであり、ヒープメモリの実際の割り当てを司ります。 フロントエンドアロケータは、それを効率よく行うための最適化レイヤーです。

ヒープの構造

ヒープのメモリレイアウトは大まかに言って下図 1 のようになります。


図1. ヒープセグメント (Heap Segment) とヒープエントリ (Heap Entry)

ヒープヘッダブロック (_HEAP) に続き、ヒープセグメント (_HEAP_SEGMENT) が続き、 その後にルックアサイドリスト (Look Aside List) を含むヒープエントリが続きます。 その後にユーザーのメモリブロック割り当て領域が続きます。

ヒープのヘッダブロックのレイアウトは以下の通りです。 

0:000> dt ntdll!_HEAP
   +0x000 Entry            : _HEAP_ENTRY
   +0x008 Signature        : Uint4B
   +0x00c Flags            : Uint4B
   +0x010 ForceFlags       : Uint4B
   +0x014 VirtualMemoryThreshold : Uint4B
   +0x018 SegmentReserve   : Uint4B
   +0x01c SegmentCommit    : Uint4B
   +0x020 DeCommitFreeBlockThreshold : Uint4B
   +0x024 DeCommitTotalFreeThreshold : Uint4B
   +0x028 TotalFreeSize    : Uint4B
   +0x02c MaximumAllocationSize : Uint4B
   +0x030 ProcessHeapsListIndex : Uint2B
   +0x032 HeaderValidateLength : Uint2B
   +0x034 HeaderValidateCopy : Ptr32 Void
   +0x038 NextAvailableTagIndex : Uint2B
   +0x03a MaximumTagIndex  : Uint2B
   +0x03c TagEntries       : Ptr32 _HEAP_TAG_ENTRY
   +0x040 UCRSegments      : Ptr32 _HEAP_UCR_SEGMENT
   +0x044 UnusedUnCommittedRanges : Ptr32 _HEAP_UNCOMMMTTED_RANGE
   +0x048 AlignRound       : Uint4B
   +0x04c AlignMask        : Uint4B
   +0x050 VirtualAllocdBlocks : _LIST_ENTRY
   +0x058 Segments         : [64] Ptr32 _HEAP_SEGMENT
   +0x158 u                : __unnamed
   +0x168 u2               : __unnamed
   +0x16a AllocatorBackTraceIndex : Uint2B
   +0x16c NonDedicatedListLength : Uint4B
   +0x170 LargeBlocksIndex : Ptr32 Void
   +0x174 PseudoTagEntries : Ptr32 _HEAP_PSEUDO_TAG_ENTRY
   +0x178 FreeLists        : [128] _LIST_ENTRY
   +0x578 LockVariable     : Ptr32 _HEAP_LOCK
   +0x57c CommitRoutine    : Ptr32     long
   +0x580 FrontEndHeap     : Ptr32 Void
   +0x584 FrontHeapLockCount : Uint2B
   +0x586 FrontEndHeapType : UChar
   +0x587 LastSegmentIndex : UChar

またメモリの割り当てはヒープセグメント (Heap Segment) として予約された連続領域からコミットされます。 ヒープセグメントは _HEAP_SEGMENT というデータ構造で表されます。

ひとつのセグメントを使い切ったらヒープマネージャが新たなセグメントを割り当てます。 セグメントはひとつのヒープに最大 64 個まで作成されます。

セグメントの場所はヒープヘッダ _HEAP のオフセット 0x058 に記録されています。 この場所に _HEAP_SEGMENT へのポインタの配列が配置されているのですが、この配列のサイズが 64 であることから、 セグメントの数の上限も 64 であることがわかります。

ヒープセグメント _HEAP_SEGMENT は以下の構造です。 

0:000> dt _HEAP_SEGMENT
ntdll!_HEAP_SEGMENT
   +0x000 Entry            : _HEAP_ENTRY
   +0x008 Signature        : Uint4B
   +0x00c Flags            : Uint4B
   +0x010 Heap             : Ptr32 _HEAP
   +0x014 LargestUnCommittedRange : Uint4B
   +0x018 BaseAddress      : Ptr32 Void
   +0x01c NumberOfPages    : Uint4B
   +0x020 FirstEntry       : Ptr32 _HEAP_ENTRY
   +0x024 LastValidEntry   : Ptr32 _HEAP_ENTRY
   +0x028 NumberOfUnCommittedPages : Uint4B
   +0x02c NumberOfUnCommittedRanges : Uint4B
   +0x030 UnCommittedRanges : Ptr32 _HEAP_UNCOMMMTTED_RANGE
   +0x034 AllocatorBackTraceIndex : Uint2B
   +0x036 Reserved         : Uint2B
   +0x038 LastEntryInSegment : Ptr32 _HEAP_ENTRY

_HEAP と _HEAP_SEGMENT をよく見ると分かるように、どちらも _HEAP_ENTRY というデータ構造で始まっています。 この _HEAP_ENTRY は次の形をしています。 

0:000> dt _HEAP_ENTRY
ntdll!_HEAP_ENTRY
   +0x000 Size             : Uint2B
   +0x002 PreviousSize     : Uint2B
   +0x000 SubSegmentCode   : Ptr32 Void
   +0x004 SmallTagIndex    : UChar
   +0x005 Flags            : UChar
   +0x006 UnusedBytes      : UChar
   +0x007 SegmentIndex     : UChar

この中にこのヒープエントリで管理するメモリブロックサイズが記録されているために、 次々とメモリブロックをたどることが可能になります。

ちなみに、この Size フィールドから実際のバイト数を求めるには、Size を 8 倍します。

実際に動きを見てみよう！

さてここまでの説明について、実際にテストプログラムを走らせて、デバッガでメモリ割り当ての様子を確認して理解を深めましょう。

テストプログラムは次の通りです。 

#include <windows.h>
#include <stdio.h>

#define ELEMENT_NUM (8)

int main ( int argc, char* argv[] ) {

     int          i;
     SIZE_T     c;
     PVOID     p[ELEMENT_NUM];
     HANDLE     hHeap;

     //
     // ヒープを作る
     //
     
     hHeap = HeapCreate ( 0, 0, 0 );
     
     if ( !hHeap ) {
          printf( "HeapCreate failed.\n" );
          return 1;
     }

     //
     // メモリブロックを割り当て文字で埋める
     //
     
     for ( i=0; i<sizeof(p)/sizeof(p[0]); i++ ) {

          c = ( i + 1 ) * 8;

          p[i] = HeapAlloc ( hHeap, 0, c );

          if ( !p[i] ){
               printf( "HeapAlloc failed.\n" );
               return 1;
          }

          FillMemory ( p[i], c, 'a' + i );
               
     }

     __asm int 3;
     

     //
     // メモリブロックの解放
     //

     for ( i=0; i<sizeof(p)/sizeof(p[0]); i++ ) {
          
          HeapFree ( hHeap, 0, p[i] );

     }


     //
     // ヒープの破棄
     //

     HeapDestroy ( hHeap );

     return 0;
}

このプログラムでは新しくひとつヒープを作成し、そのヒープから ELEMENT_NUM (=8) 個だけメモリサイズ、 8 バイト, 16 バイト, 24 バイト, ... のメモリブロックを割り当て、それぞれを 'a', 'b', ... という文字で埋めます。

ですからメモリブロックとして、

aaaaaaaa
bbbbbbbbbbbbbbbb
cccccccccccccccccccccccc
...

という領域がどこかに確認できるはずです。

さて、デバッガ上でプログラムを実際に走らせ、デバッガでそのメモリ割り当ての様子を確認しましょう。 

     __asm int 3;

この部分でデバッガに制御が渡るはずです。 

0:000> g
(8e0.8f8): Break instruction exception - code 80000003 (first chance)
eax=00000008 ebx=7ffdf000 ecx=00000000 edx=00000000 esi=00000000 edi=00000000
eip=004010a9 esp=0012ff4c ebp=0012ff78 iopl=0         nv up ei pl zr na pe nc
cs=001b  ss=0023  ds=0023  es=0023  fs=0038  gs=0000             efl=00000246
test!main+0xa9:
004010a9 cc              int     3

確かに int 3 でブレークしました。ここでローカル変数を確認します。 

0:000> dv
           argc = 1
           argv = 0x00322ff8
              c = 0x40
          hHeap = 0x00340000
              i = 8
              p = void *[8]

ヒープハンドル hHeap には 0x00340000 がセットされています。 このときに !heap デバッガコマンドでヒープの一覧を見ると次のようになり、確かに 5 番目に同じヒープが確認できます。 (逆に言うとヒープハンドルはヒープのアドレスを示しているということになります。) 

0:000> !heap
NtGlobalFlag enables following debugging aids for new heaps:    tail checking
    free checking
    validate parameters
Index   Address  Name      Debugging options enabled
  1:   00140000                 tail checking free checking validate parameters
  2:   00240000                 tail checking free checking validate parameters
  3:   00250000                 tail checking free checking validate parameters
  4:   00320000                 tail checking free checking validate parameters
  5:   00340000                 tail checking free checking validate parameters

上述の通りヒープはヘッダ (_HEAP) から始まるはずですから、_HEAP という型に当てはめてアドレス 0x00340000 を確認します。 

0:000> dt _HEAP 00340000
ntdll!_HEAP
   +0x000 Entry            : _HEAP_ENTRY
   +0x008 Signature        : 0xeeffeeff
   +0x00c Flags            : 0x50001062
   +0x010 ForceFlags       : 0x40000060
   +0x014 VirtualMemoryThreshold : 0xfe00
   +0x018 SegmentReserve   : 0x100000
   +0x01c SegmentCommit    : 0x2000
   +0x020 DeCommitFreeBlockThreshold : 0x200
   +0x024 DeCommitTotalFreeThreshold : 0x2000
   +0x028 TotalFreeSize    : 0x1f1
   +0x02c MaximumAllocationSize : 0x7ffdefff
   +0x030 ProcessHeapsListIndex : 5
   +0x032 HeaderValidateLength : 0x608
   +0x034 HeaderValidateCopy : (null)
   +0x038 NextAvailableTagIndex : 0
   +0x03a MaximumTagIndex  : 0
   +0x03c TagEntries       : (null)
   +0x040 UCRSegments      : (null)
   +0x044 UnusedUnCommittedRanges : 0x00340598 _HEAP_UNCOMMMTTED_RANGE
   +0x048 AlignRound       : 0x17
   +0x04c AlignMask        : 0xfffffff8
   +0x050 VirtualAllocdBlocks : _LIST_ENTRY [ 0x340050 - 0x340050 ]
   +0x058 Segments         : [64] 0x00340640 _HEAP_SEGMENT
   +0x158 u                : __unnamed
   +0x168 u2               : __unnamed
   +0x16a AllocatorBackTraceIndex : 0
   +0x16c NonDedicatedListLength : 1
   +0x170 LargeBlocksIndex : (null)
   +0x174 PseudoTagEntries : (null)
   +0x178 FreeLists        : [128] _LIST_ENTRY [ 0x342080 - 0x342080 ]
   +0x578 LockVariable     : 0x00340608 _HEAP_LOCK
   +0x57c CommitRoutine    : (null)
   +0x580 FrontEndHeap     : 0x00340688
   +0x584 FrontHeapLockCount : 0
   +0x586 FrontEndHeapType : 0x1 ''
   +0x587 LastSegmentIndex : 0 ''

セグメントはオフセット 0x058 にアドレスが書いてあるはずなので、見てみます。 

0:000> dc 00340000+0x058
00340058  00340640 00000000 00000000 00000000  @.4.............
00340068  00000000 00000000 00000000 00000000  ................
00340078  00000000 00000000 00000000 00000000  ................
00340088  00000000 00000000 00000000 00000000  ................
00340098  00000000 00000000 00000000 00000000  ................
003400a8  00000000 00000000 00000000 00000000  ................
003400b8  00000000 00000000 00000000 00000000  ................
003400c8  00000000 00000000 00000000 00000000  ................

念のため !heap デバッグコマンドの出力結果と見比べると、次のようになります。 

0:000> !heap -a 00340000
Index   Address  Name      Debugging options enabled
  5:   00340000
    Segment at 00340000 to 00380000 (00003000 bytes committed)
    Flags:                50001062
    ForceFlags:           40000060
    Granularity:          8 bytes
    Segment Reserve:      00100000
    Segment Commit:       00002000
    DeCommit Block Thres: 00000200
    DeCommit Total Thres: 00002000
    Total Free Size:      000001f1
    Max. Allocation Size: 7ffdefff
    Lock Variable at:     00340608
    Next TagIndex:        0000
    Maximum TagIndex:     0000
    Tag Entries:          00000000
    PsuedoTag Entries:    00000000
    Virtual Alloc List:   00340050
    UCR FreeList:        00340598
    FreeList Usage:      00000000 00000000 00000000 00000000
    FreeList[ 00 ] at 00340178: 00342080 . 00342080
    Unable to read nt!_HEAP_FREE_ENTRY structure at 00342080
    Segment00 at 00340640:
        Flags:           00000000
        Base:            00340000
        First Entry:     00340680
        Last Entry:      00380000
        Total Pages:     00000040
        Total UnCommit:  0000003d
        Largest UnCommit:0003d000
        UnCommitted Ranges: (1)
            00343000: 0003d000

    Heap entries for Segment00 in Heap 00340000
        00340000: 00000 . 00640 [01] - busy (640)
        00340640: 00640 . 00040 [01] - busy (40)
        00340680: 00040 . 01818 [07] - busy (1800), tail fill - unable to ...
        00341e98: 01818 . 00020 [07] - busy (8), tail fill - unable to read ...
        00341eb8: 00020 . 00028 [07] - busy (10), tail fill - unable to read ...
        00341ee0: 00028 . 00030 [07] - busy (18), tail fill - unable to read ...
        00341f10: 00030 . 00038 [07] - busy (20), tail fill - unable to read ...
        00341f48: 00038 . 00040 [07] - busy (28), tail fill - unable to read ...
        00341f88: 00040 . 00048 [07] - busy (30), tail fill - unable to read ...
        00341fd0: 00048 . 00050 [07] - busy (38), tail fill - unable to read ...
        00342020: 00050 . 00058 [07] - busy (40), tail fill - unable to read ...
        00342078: 00058 . 00f88 [14] free fill
        00343000:      0003d000      - uncommitted bytes.

確かにセグメント 00 は 0x00340640 にあることが確認できます。

さらに、ヒープヘッダの先頭には _HEAP_ENTRY があります。 

0:000> dt _HEAP_ENTRY 00340000
ntdll!_HEAP_ENTRY
   +0x000 Size             : 0xc8
   +0x002 PreviousSize     : 0
   +0x000 SubSegmentCode   : 0x000000c8
   +0x004 SmallTagIndex    : 0x13 ''
   +0x005 Flags            : 0x1 ''
   +0x006 UnusedBytes      : 0 ''
   +0x007 SegmentIndex     : 0 ''

Size が c8 とありますので、次のメモリブロックはアドレス 0x00340000 + 0xc8 * 8 から始まっているはずです。 

0:000> ?00340000+(0xc8*8)
Evaluate expression: 3409472 = 00340640

確かにこの値は上記で確認したヒープセグメントのアドレスと一致します。

次のブロックを見てみましょう。 

0:000> dt _HEAP_ENTRY 00340640
ntdll!_HEAP_ENTRY
   +0x000 Size             : 8
   +0x002 PreviousSize     : 0xc8
   +0x000 SubSegmentCode   : 0x00c80008
   +0x004 SmallTagIndex    : 0 ''
   +0x005 Flags            : 0x1 ''
   +0x006 UnusedBytes      : 0 ''
   +0x007 SegmentIndex     : 0 ''
0:000> ?00340640+(0x8*8)
Evaluate expression: 3409536 = 00340680
0:000> dt _HEAP_ENTRY 00340680
ntdll!_HEAP_ENTRY
   +0x000 Size             : 0x303
   +0x002 PreviousSize     : 8
   +0x000 SubSegmentCode   : 0x00080303
   +0x004 SmallTagIndex    : 0xc3 ''
   +0x005 Flags            : 0x7 ''
   +0x006 UnusedBytes      : 0x18 ''
   +0x007 SegmentIndex     : 0 ''

このブロックは後述のルックアサイドリストが配置されています。

次のブロックは、0x303 * 8 バイト進めた次の場所です。 

0:000> dt _HEAP_ENTRY 00340680+(0x303*8)
ntdll!_HEAP_ENTRY
   +0x000 Size             : 4
   +0x002 PreviousSize     : 0x303
   +0x000 SubSegmentCode   : 0x03030004
   +0x004 SmallTagIndex    : 0xc0 ''
   +0x005 Flags            : 0x7 ''
   +0x006 UnusedBytes      : 0x18 ''
   +0x007 SegmentIndex     : 0 ''

この中身をみてみましょう。 

0:000> dc 00340680+(0x303*8)
00341e98  03030004 001807c0 61616161 61616161  ........aaaaaaaa
00341ea8  abababab abababab 00000000 00000000  ................
00341eb8  00040005 001807c4 62626262 62626262  ........bbbbbbbb
00341ec8  62626262 62626262 abababab abababab  bbbbbbbb........
00341ed8  00000000 00000000 00050006 001807cf  ................
00341ee8  63636363 63636363 63636363 63636363  cccccccccccccccc
00341ef8  63636363 63636363 abababab abababab  cccccccc........
00341f08  00000000 00000000 00060007 001807f1  ................
0:000>

これはプログラムから割り当てた 8 バイトのデータに他なりません。

いかがでしょうか。たった上記の知識だけで、このくらいはメモリをたどることが可能になります。

フリーリスト

一度割り当てたメモリを効率よく使い回しするために、フリーリスト (Free List) というリストを管理しています。


図2. フリーリスト (Free List)

フリーリストは上記で示した _HEAP から直ちに取得できます。 

0:000> dt ntdll!_HEAP
   +0x000 Entry            : _HEAP_ENTRY
   ...
   +0x174 PseudoTagEntries : Ptr32 _HEAP_PSEUDO_TAG_ENTRY
   +0x178 FreeLists        : [128] _LIST_ENTRY
   +0x578 LockVariable     : Ptr32 _HEAP_LOCK
   +0x57c CommitRoutine    : Ptr32     long
   ...
   +0x587 LastSegmentIndex : UChar

すなわちヒープの先頭からオフセット 0x178 の場所に、_LIST_ENTRY の配列 (要素数 128) として、 フリーリストが配置されています。

フリーリストは、解放されたメモリブロックのリストです。そして、 メモリブロックのサイズによって、FreeLists のインデックスが決められています。 メモリブロックのサイズはインデックス * 8 で決められます。すなわち、 24 バイトの解放済みメモリブロックは、フリーリストのインデックス 3 (=24/8) を、 リストヘッドとする双方向リストからたどることができます。

この仕組みによって、次回 24 バイトのメモリ割り当てが必要になった場合には、 既に解放された 24 バイトのメモリブロックを、FreeLists[3] をリストヘッドとする 双方向リストから取得することが可能となります。

尚、管理データのために 16 バイト (=2*8) を消費するので、有効なインデックスの最小値は 3 になります。

また、フリーリストではブロックスプリッティング (Block Splitting) も行われます。 これは例えば 16 バイトの割り当て要求が必要であり、16 バイトの解放済みブロックがフリーリストに存在せずに、 32 バイトのブロックがある場合、32 バイトのブロックを分割して、片方を返し、片方を 16 バイトの解放済み領域としてフリーリストに登録するというものです。

ルックアサイドリスト

前述の通りヒープセグメント 00 には、ルックアサイドリスト (Look Aside List, LAL) があります。

これは解放済みメモリ領域を指し示す単方向リストです。 メモリ割り当ての要求があった場合、最初にルックアサイドリストを見て、そこからメモリブロックを返せるときは返します。 ルックアサイドリストからメモリが割り当てられない場合に初めて、バックエンドアロケータであるフリーリストを確認し、 それでもメモリが割り当てられない場合は、ヒープマネージャが必要なメモリ領域を割り当てます。

ルックアサイドリストは、128 個の単方向リストのリストヘッドの配列に他なりません。 それぞれのエントリは、特定のバイトするの解放済みヒープブロックを指しています。

例えばインデックス 1 は 16 バイトのブロックを、2 は 24 バイトのブロックを、 3 は 32 バイトのブロックを指します。 これは (8 バイトのヒープメタデータ) + (8 バイト * インデックス) サイズのブロックを必要とするためです。

サイズの大きなメモリブロック割り当て

メモリブロックの割り当て要求が、比較的小さなメモリブロックであれば上述のように ルックアサイドリストまたはフリーリストなどから返すことが可能です。

しかし、フリーリスト等でカバーできないサイズの大きなメモリブロックについては、 ヒープマネージャが個別にメモリを割り当てます。 

0:000> dt ntdll!_HEAP
   +0x000 Entry            : _HEAP_ENTRY
   +0x008 Signature        : Uint4B
   ...
   +0x04c AlignMask        : Uint4B
   +0x050 VirtualAllocdBlocks : _LIST_ENTRY
   +0x058 Segments         : [64] Ptr32 _HEAP_SEGMENT
   ...
   +0x587 LastSegmentIndex : UChar

ヒープマネージャから割り当てた仮想メモリブロックは、上記の VirtualAllocdBlocks リストからたどることが可能です。

セグメントからの割り当てと、仮想メモリの直接割り当ての違い

ここで実験をして動作を確認しましょう。

実験1

  1. プライベートヒープ g_hMyHeap を作成
  2. HeapCreate g_hMyHeap から 256kb のメモリブロックを割り当てる
  3. 2 を 1 秒に 1 回のペースで 3 分間繰り返す
  4. 割り当てたメモリを全て解放する (HeapFree)
  5. プライベートヒープを削除 HeapDestroy

上記を行った場合のメモリ割り当ての様子を、パフォーマンスカウンタ Memory (Available Bytes) と Process の Private Bytes と Virtual Bytes を利用して確認します。

結果、Virtual Bytes が時折段階的に増加することが確認できます。 これはセグメント内のメモリが消費され、ヒープマネージャによって新しいセグメントが予約されるからです。

また、Private Bytes は割り当て (コミット) 量に比例して増加しています。

メモリを解放したところで、Private Bytes は減少しましたが、予約済みの領域 (Virtual Bytes) は増加したままとなります。

ヒープを削除することによって初めて、Virtual Bytes が解放されます。

実験 2

上記と同様の実験をメモリ割り当てサイズを大きくします。

結果、Private Bytes と Virtual Bytes が比例して増加しています。これはセグメント内からメモリを割り当てたのではないことを示しています。

メモリも解放と同時に Virtual Bytes も減少しています。

以上、この資料では LAL ヒープについて、ヒープヘッダ、セグメント、エントリについて概要を説明し、 デバッガで実際のメモリを確認しました。また、割り当てサイズによってバックエンドアロケータのメモリ割り当て方法が異なることを、 パフォーマンスモニタを利用して確認しました。

ここまでお読みいただき、誠にありがとうございます。SNS 等でこの記事をシェアしていただけますと、大変励みになります。どうぞよろしくお願いします。

© 2024 Web/DB プログラミング徹底解説