Japanese - Ht

Bins & Memory Allocations

htARTE（HackTricks AWS Red Team Expert） でゼロからヒーローまでAWSハッキングを学ぶ！

HackTricks をサポートする他の方法:

基本情報

チャンクの格納効率を向上させるために、各チャンクは1つのリンクリストにだけではなく、複数のタイプに分かれて格納されます。これらはビンであり、5種類のビンがあります: 62 small bins、63 large bins、1 unsorted bin、10 fast bins、およびスレッドごとに64個のtcache binsがあります。

各unsorted、small、large binsの初期アドレスは同じ配列内にあります。インデックス0は未使用で、1はunsorted bin、2〜64はsmall bins、65〜127はlarge binsです。

Tcache（スレッドごとのキャッシュ）Bins

スレッドは独自のヒープを持とうとしますが（ArenasおよびSubheapsを参照）、多くのスレッドを持つプロセス（Webサーバーなど）は他のスレッドとヒープを共有する可能性があります。この場合、主な解決策はロッカーの使用であり、これはスレッドを著しく遅くする可能性があります。

したがって、tcacheは、チャンクをマージしないシングルリンクリストであるため、各スレッドには64個の単方向リンクtcache binsがあります。各ビンには、64ビットシステムでは24〜1032B、32ビットシステムでは12〜516Bの同じサイズのチャンク7つまで格納できます。

スレッドがチャンクを解放するとき、それがtcacheに割り当てられるには大きすぎないことと、対応するtcache binが満杯でない（すでに7つのチャンクがある）ことが必要です。tcacheに移動できない場合は、ヒープロックを待ってグローバルな解放操作を行うことができるようにする必要があります。

チャンクが割り当てられると、必要なサイズの空きチャンクがTcacheにあれば、それを使用します。そうでない場合は、グローバルビンから見つけるか新しいものを作成するためにヒープロックを待つ必要があります。 また、この場合の最適化もあり、ヒープロックを取得したとき、スレッドは要求されたサイズのヒープチャンク（7つ）でTcacheを埋めるため、必要な場合はTcacheでそれらを見つけることができます。

tcacheチャンクの例を追加

```c #include #include

int main(void) { char *chunk; chunk = malloc(24); printf("Address of the chunk: %p\n", (void *)chunk); gets(chunk); free(chunk); return 0; }

コンパイルして、main 関数からの ret オペコードにブレークポイントを設定してデバッグします。その後、gef を使用して tcache bin が使用されているのを確認できます:
```bash
gef➤  heap bins
──────────────────────────────────────────────────────────────────────────────── Tcachebins for thread 1 ────────────────────────────────────────────────────────────────────────────────
Tcachebins[idx=0, size=0x20, count=1] ←  Chunk(addr=0xaaaaaaac12a0, size=0x20, flags=PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)

Tcacheの構造体と関数

以下のコードでは、max binsとchunks per index、**tcache_entry構造体が作成されており、二重解放を回避するために使用されています。また、各スレッドがビンの各インデックスのアドレスを格納するために使用されるtcache_perthread_struct**という構造体も確認できます。

Tcache インデックス

Tcache には、サイズに応じて複数のビンがあり、各インデックスの最初のチャンクへのポインタと、各インデックスごとのチャンクの数がチャンク内に配置されています。これは、この情報を持つチャンク（通常は最初のチャンク）を見つけることで、すべての tcache の初期ポイントと Tcache チャンクの数を見つけることができます。

ファストビン

ファストビンは、小さなチャンクのメモリ割り当てを高速化するために、最近解放されたチャンクをクイックアクセス構造に保持するように設計されています。これらのビンは、最後に解放されたチャンクが再利用されるため、最近解放されたチャンクが最初になる Last-In, First-Out（LIFO）アプローチを使用します。この動作は、スピード向上に有利であり、スタック（LIFO）の先頭に挿入および削除する速度が、キュー（FIFO）よりも速いためです。

さらに、ファストビンは単方向リンクリストを使用しており、ダブルリンクリストではないため、さらなる速度向上が図られています。ファストビンのチャンクは隣接するチャンクとマージされないため、中間からの削除を許可する複雑な構造は不要です。単方向リンクリストは、これらの操作に対してより単純で迅速です。

基本的に、ここで起こることは、ヘッダー（チェックする最初のチャンクへのポインタ）が常にそのサイズの最新の解放されたチャンクを指しているということです。したがって：

  • そのサイズの新しいチャンクが割り当てられると、ヘッダーは使用する空きチャンクを指しています。この空きチャンクが次に使用するチャンクを指しているため、このアドレスはヘッダーに保存され、次の割り当てがどこから利用可能なチャンクを取得するかを知っています。

  • チャンクが解放されると、空きチャンクは現在の利用可能なチャンクへのアドレスを保存し、この新しく解放されたチャンクへのアドレスがヘッダーに配置されます。

リンクリストの最大サイズは 0x80 であり、サイズ 0x20-0x2f のチャンクはインデックス 0 に、サイズ 0x30-0x3f のチャンクは idx 1 に配置されます。

ファストビンのチャンクは利用可能として設定されていないため、周囲の他の空きチャンクとマージできる代わりに、一定時間ファストビンのチャンクとして保持されます。

// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711

/*
Fastbins

An array of lists holding recently freed small chunks.  Fastbins
are not doubly linked.  It is faster to single-link them, and
since chunks are never removed from the middles of these lists,
double linking is not necessary. Also, unlike regular bins, they
are not even processed in FIFO order (they use faster LIFO) since
ordering doesn't much matter in the transient contexts in which
fastbins are normally used.

Chunks in fastbins keep their inuse bit set, so they cannot
be consolidated with other free chunks. malloc_consolidate
releases all chunks in fastbins and consolidates them with
other free chunks.
*/

typedef struct malloc_chunk *mfastbinptr;
#define fastbin(ar_ptr, idx) ((ar_ptr)->fastbinsY[idx])

/* offset 2 to use otherwise unindexable first 2 bins */
#define fastbin_index(sz) \
((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)


/* The maximum fastbin request size we support */
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)

#define NFASTBINS  (fastbin_index (request2size (MAX_FAST_SIZE)) + 1)

Unsorted bin

未整列のビンは、ヒープマネージャーがメモリ割り当てを迅速に行うために使用するキャッシュです。動作は次のとおりです。プログラムがチャンクを解放すると、そのチャンクがtcacheやfast binに割り当てられず、かつトップチャンクと衝突していない場合、ヒープマネージャーはそのチャンクをすぐに特定の小さなビンや大きなビンに配置しません。代わりに、隣接する空きチャンクとマージしてより大きな空きメモリブロックを作成しようとします。その後、この新しいチャンクを「未整列のビン」と呼ばれる一般的なビンに配置します。

プログラムがメモリを要求すると、ヒープマネージャーは未整列のビンをチェックして十分なサイズのチャンクがあるかどうかを確認します。見つかればすぐに使用します。未整列のビンに適切なチャンクが見つからない場合、このリスト内のすべてのチャンクを、サイズに応じてそれぞれのビン（小さなビンまたは大きなビン）に移動します。

大きなチャンクが2つに分割され、残りがMINSIZEより大きい場合、それは未整列のビンに戻されます。

したがって、未整列のビンは、最近解放されたメモリを迅速に再利用し、時間のかかる検索とマージの必要性を減らすことで、メモリ割り当てを高速化する方法です。

異なるカテゴリのチャンクであっても、利用可能なチャンクが他の利用可能なチャンクと衝突している場合（元々異なるビンに属していても）、それらはマージされます。

Small Bins

Small binsはlarge binsよりも速いですが、fast binsよりは遅いです。

62のbinのそれぞれには同じサイズのチャンクがあります: 16, 24, ... (32ビットでは最大504バイト、64ビットでは1024バイト)。これにより、空間を割り当てるべきbinを見つける速度や、これらのリストにエントリを挿入および削除する速度が向上します。

これがsmall binのサイズがbinのインデックスに応じてどのように計算されるかです:

  • 最小サイズ: 2*4*index (例: インデックス5 -> 40)

  • 最大サイズ: 2*8*index (例: インデックス5 -> 80)

// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711
#define NSMALLBINS         64
#define SMALLBIN_WIDTH    MALLOC_ALIGNMENT
#define SMALLBIN_CORRECTION (MALLOC_ALIGNMENT > CHUNK_HDR_SZ)
#define MIN_LARGE_SIZE    ((NSMALLBINS - SMALLBIN_CORRECTION) * SMALLBIN_WIDTH)

#define in_smallbin_range(sz)  \
((unsigned long) (sz) < (unsigned long) MIN_LARGE_SIZE)

#define smallbin_index(sz) \
((SMALLBIN_WIDTH == 16 ? (((unsigned) (sz)) >> 4) : (((unsigned) (sz)) >> 3))\
+ SMALLBIN_CORRECTION)

Function to choose between small and large bins:

小さなビンと大きなビンの間を選択するための関数:

#define bin_index(sz) \
((in_smallbin_range (sz)) ? smallbin_index (sz) : largebin_index (sz))

ラージビン

小さなビンが固定サイズのチャンクを管理するのに対し、各ラージビンは一定のチャンクサイズの範囲を扱います。これにより、システムはさまざまなサイズを別々のビンを必要とせずに収容できるようになります。

メモリアロケーターにおいて、ラージビンは小さなビンの終わりから始まります。ラージビンの範囲は徐々に大きくなり、最初のビンは512から576バイトのチャンクをカバーし、次のビンは576から640バイトをカバーします。このパターンが続き、最大のビンには1MBを超えるすべてのチャンクが含まれます。

ラージビンは、割り当てに最適なチャンクを見つけるためにさまざまなチャンクサイズのリストをソートして検索する必要があるため、小さなビンよりも操作が遅くなります。チャンクがラージビンに挿入されると、ソートされなければならず、メモリが割り当てられるときにシステムは適切なチャンクを見つけなければなりません。この追加作業により、ラージビンは遅くなりますが、大きな割り当てが小さなものよりも一般的でないため、これは許容できるトレードオフです。

以下のようなものがあります：

  • 64B範囲の32ビン（小さなビンと衝突する）

  • 512B範囲の16ビン（小さなビンと衝突する）

  • 4096B範囲の8ビン（一部が小さなビンと衝突する）

  • 32768B範囲の4ビン

  • 262144B範囲の2ビン

  • 残りのサイズ用の1ビン

トップチャンク

// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1711

/*
Top

The top-most available chunk (i.e., the one bordering the end of
available memory) is treated specially. It is never included in
any bin, is used only if no other chunk is available, and is
released back to the system if it is very large (see
M_TRIM_THRESHOLD).  Because top initially
points to its own bin with initial zero size, thus forcing
extension on the first malloc request, we avoid having any special
code in malloc to check whether it even exists yet. But we still
need to do so when getting memory from system, so we make
initial_top treat the bin as a legal but unusable chunk during the
interval between initialization and the first call to
sysmalloc. (This is somewhat delicate, since it relies on
the 2 preceding words to be zero during this interval as well.)
*/

/* Conveniently, the unsorted bin can be used as dummy top on first call */
#define initial_top(M)              (unsorted_chunks (M))

基本的に、これは現在利用可能なヒープ全体を含むチャンクです。mallocが実行されると、使用可能なフリーチャンクがない場合、このトップチャンクは必要なスペースを提供するためにサイズを減らします。 Top Chunkへのポインタはmalloc_state構造体に格納されています。

さらに、最初に、未整列のチャンクをトップチャンクとして使用することができます。

最後のリマインダー

malloc が使用され、チャンクが分割されると（未リンクリストからまたはトップチャンクからなど）、分割されたチャンクから作成されたチャンクは「最後のリマインダー」と呼ばれ、そのポインタは malloc_state 構造体に格納されます。

割り当てフロー

次をチェックしてください：

解放フロー

次をチェックしてください：

ヒープ関数のセキュリティチェック

ヒープ内で頻繁に使用される関数によって実行されるセキュリティチェックを確認してください：

参考文献

PreviousLibc HeapNextHeap Memory Functions

Last updated