HackTricksLibc Heap
Reading time: 21 minutes
ヒープの基本
ヒープは基本的に、プログラムが**malloc、callocなどの関数を呼び出してデータを要求する際にデータを保存できる場所です。さらに、このメモリがもはや必要ない場合は、free**関数を呼び出すことで利用可能になります。
示されているように、これはバイナリがメモリに読み込まれた直後の場所です（[heap]セクションを確認してください）：
.png)
基本的なチャンクの割り当て
ヒープに保存するデータが要求されると、ヒープの一部がそれに割り当てられます。このスペースはビンに属し、要求されたデータ + ビンヘッダーのスペース + 最小ビンサイズオフセットの分だけがチャンクのために予約されます。目標は、各チャンクの位置を見つけるのを複雑にせず、できるだけ少ないメモリを予約することです。このために、メタデータチャンク情報を使用して、使用中/未使用の各チャンクの位置を把握します。
スペースを予約する方法はいくつかありますが、主に使用されるビンに依存しますが、一般的な方法論は次のとおりです：
- プログラムは特定の量のメモリを要求することから始まります。
- チャンクのリストに、要求を満たすのに十分な大きさの空きがあれば、それが使用されます。
- これは、利用可能なチャンクの一部がこの要求に使用され、残りがチャンクリストに追加されることを意味する場合もあります。
- リストに利用可能なチャンクがないが、割り当てられたヒープメモリにまだスペースがある場合、ヒープマネージャーは新しいチャンクを作成します。
- 新しいチャンクを割り当てるのに十分なヒープスペースがない場合、ヒープマネージャーはカーネルにヒープに割り当てられたメモリを拡張するように要求し、その後このメモリを使用して新しいチャンクを生成します。
- すべてが失敗した場合、
mallocはnullを返します。
要求されたメモリが閾値を超えた場合、**mmap**が要求されたメモリをマッピングするために使用されることに注意してください。
アリーナ
マルチスレッドアプリケーションでは、ヒープマネージャーはクラッシュを引き起こす可能性のあるレースコンディションを防ぐ必要があります。最初は、グローバルミューテックスを使用して、同時に1つのスレッドだけがヒープにアクセスできるようにしていましたが、これによりミューテックスによるボトルネックが発生し、パフォーマンスの問題が生じました。
これに対処するために、ptmalloc2ヒープアロケータは「アリーナ」を導入しました。ここで各アリーナは独自のデータ構造とミューテックスを持つ別々のヒープとして機能し、異なるアリーナを使用する限り、複数のスレッドが互いに干渉することなくヒープ操作を実行できます。
デフォルトの「メイン」アリーナは、シングルスレッドアプリケーションのヒープ操作を処理します。新しいスレッドが追加されると、ヒープマネージャーは競合を減らすためにセカンダリアリーナを割り当てます。最初に、各新しいスレッドを未使用のアリーナに接続しようとし、必要に応じて新しいアリーナを作成します。32ビットシステムではCPUコア数の2倍、64ビットシステムでは8倍の制限があります。制限に達すると、スレッドはアリーナを共有しなければならず、競合の可能性が生じます。
メインアリーナとは異なり、brkシステムコールを使用して拡張されるメインアリーナに対し、セカンダリアリーナはmmapとmprotectを使用して「サブヒープ」を作成し、マルチスレッド操作のためのメモリ管理の柔軟性を提供します。
サブヒープ
サブヒープは、マルチスレッドアプリケーションにおけるセカンダリアリーナのメモリ予備として機能し、メインヒープとは別に自分自身のヒープ領域を成長させ、管理することを可能にします。サブヒープが初期ヒープとどのように異なり、どのように機能するかは次のとおりです：
- 初期ヒープとサブヒープ：
- 初期ヒープはプログラムのバイナリの直後にメモリに位置し、
sbrkシステムコールを使用して拡張されます。 - セカンダリアリーナによって使用されるサブヒープは、指定されたメモリ領域をマッピングするシステムコールである
mmapを通じて作成されます。
mmapによるメモリ予約：
- ヒープマネージャーがサブヒープを作成するとき、大きなメモリブロックを
mmapを通じて予約します。この予約は即座にメモリを割り当てるわけではなく、他のシステムプロセスや割り当てが使用しないべき領域を指定するだけです。 - デフォルトでは、サブヒープの予約サイズは32ビットプロセスで1MB、64ビットプロセスで64MBです。
mprotectによる段階的拡張：
- 予約されたメモリ領域は最初に
PROT_NONEとしてマークされ、カーネルがこのスペースに物理メモリを割り当てる必要がないことを示します。 - サブヒープを「成長させる」ために、ヒープマネージャーは
mprotectを使用してページの権限をPROT_NONEからPROT_READ | PROT_WRITEに変更し、カーネルに以前に予約されたアドレスに物理メモリを割り当てるように促します。この段階的アプローチにより、サブヒープは必要に応じて拡張できます。 - サブヒープが完全に使い果たされると、ヒープマネージャーは新しいサブヒープを作成して割り当てを続けます。
heap_info
この構造体はヒープの関連情報を割り当てます。さらに、ヒープメモリは追加の割り当ての後に連続していない場合があり、この構造体はその情報も保存します。
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/arena.c#L837
typedef struct _heap_info
{
mstate ar_ptr; /* Arena for this heap. */
struct _heap_info *prev; /* Previous heap. */
size_t size; /* Current size in bytes. */
size_t mprotect_size; /* Size in bytes that has been mprotected
PROT_READ|PROT_WRITE. */
size_t pagesize; /* Page size used when allocating the arena. */
/* Make sure the following data is properly aligned, particularly
that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
MALLOC_ALIGNMENT. */
char pad[-3 * SIZE_SZ & MALLOC_ALIGN_MASK];
} heap_info;
malloc_state
各ヒープ（メインアリーナまたは他のスレッドアリーナ）には**malloc_state構造体があります。
メインアリーナのmalloc_state構造体はlibcのグローバル変数であることに注意することが重要です（したがって、libcのメモリ空間にあります）。
スレッドのヒープのmalloc_state**構造体は、各スレッドの「ヒープ」内にあります。
この構造体から注目すべき興味深い点がいくつかあります（以下のCコードを参照）：
-
__libc_lock_define (, mutex);は、このヒープの構造体が1つのスレッドによって同時にアクセスされることを保証するためにあります。 -
フラグ：
-
#define NONCONTIGUOUS_BIT (2U)
#define contiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) == 0) #define noncontiguous(M) (((M)->flags & NONCONTIGUOUS_BIT) != 0) #define set_noncontiguous(M) ((M)->flags |= NONCONTIGUOUS_BIT) #define set_contiguous(M) ((M)->flags &= ~NONCONTIGUOUS_BIT)
- `mchunkptr bins[NBINS * 2 - 2];` は、**小さな、大きな、未ソートの** **ビン**の**最初と最後のチャンク**への**ポインタ**を含んでいます（-2はインデックス0が使用されないためです）。
- したがって、これらのビンの**最初のチャンク**はこの構造体への**逆ポインタ**を持ち、これらのビンの**最後のチャンク**はこの構造体への**前方ポインタ**を持ちます。基本的に、もしあなたが**メインアリーナでこれらのアドレスを漏洩させることができれば**、あなたは**libc**内の構造体へのポインタを持つことになります。
- 構造体`struct malloc_state *next;`と`struct malloc_state *next_free;`はアリーナのリンクリストです。
- `top`チャンクは最後の「チャンク」であり、基本的に**ヒープの残りのすべてのスペース**です。トップチャンクが「空」であるとき、ヒープは完全に使用されており、さらにスペースを要求する必要があります。
- `last reminder`チャンクは、正確なサイズのチャンクが利用できない場合に発生し、したがって大きなチャンクが分割され、残りの部分のポインタがここに置かれます。
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/malloc/malloc.c#L1812
struct malloc_state { /* Serialize access. */ __libc_lock_define (, mutex);
/* Flags (formerly in max_fast). */ int flags;
/* Set if the fastbin chunks contain recently inserted free blocks. / / Note this is a bool but not all targets support atomics on booleans. */ int have_fastchunks;
/* Fastbins */ mfastbinptr fastbinsY[NFASTBINS];
/* Base of the topmost chunk -- not otherwise kept in a bin */ mchunkptr top;
/* The remainder from the most recent split of a small request */ mchunkptr last_remainder;
/* Normal bins packed as described above */ mchunkptr bins[NBINS * 2 - 2];
/* Bitmap of bins */ unsigned int binmap[BINMAPSIZE];
/* Linked list */ struct malloc_state *next;
/* Linked list for free arenas. Access to this field is serialized by free_list_lock in arena.c. */ struct malloc_state *next_free;
/* Number of threads attached to this arena. 0 if the arena is on the free list. Access to this field is serialized by free_list_lock in arena.c. */ INTERNAL_SIZE_T attached_threads;
/* Memory allocated from the system in this arena. */ INTERNAL_SIZE_T system_mem; INTERNAL_SIZE_T max_system_mem; };
### malloc_chunk
この構造体は特定のメモリチャンクを表します。さまざまなフィールドは、割り当てられたチャンクと未割り当てのチャンクで異なる意味を持ちます。
// https://github.com/bminor/glibc/blob/master/malloc/malloc.c struct malloc_chunk { INTERNAL_SIZE_T mchunk_prev_size; /* Size of previous chunk, if it is free. / INTERNAL_SIZE_T mchunk_size; / Size in bytes, including overhead. / struct malloc_chunk fd; /* double links -- used only if this chunk is free. / struct malloc_chunk bk; /* Only used for large blocks: pointer to next larger size. / struct malloc_chunk fd_nextsize; /* double links -- used only if this chunk is free. / struct malloc_chunk bk_nextsize; };
typedef struct malloc_chunk* mchunkptr;
以前にコメントしたように、これらのチャンクにはメタデータも含まれており、以下の画像で非常に良く表現されています：
<figure><img src="../../images/image (1242).png" alt=""><figcaption><p><a href="https://azeria-labs.com/wp-content/uploads/2019/03/chunk-allocated-CS.png">https://azeria-labs.com/wp-content/uploads/2019/03/chunk-allocated-CS.png</a></p></figcaption></figure>
メタデータは通常0x08Bで、現在のチャンクサイズを示し、最後の3ビットを使用して次のことを示します：
- `A`: 1の場合はサブヒープから、0の場合はメインアリーナにあります
- `M`: 1の場合、このチャンクはmmapで割り当てられたスペースの一部であり、ヒープの一部ではありません
- `P`: 1の場合、前のチャンクは使用中です
次に、ユーザーデータのためのスペースがあり、最後にチャンクが利用可能なときの前のチャンクサイズを示すために0x08Bがあります（または割り当てられているときにユーザーデータを格納するため）。
さらに、利用可能な場合、ユーザーデータは他のデータも含むために使用されます：
- **`fd`**: 次のチャンクへのポインタ
- **`bk`**: 前のチャンクへのポインタ
- **`fd_nextsize`**: リスト内で自分より小さい最初のチャンクへのポインタ
- **`bk_nextsize`:** リスト内で自分より大きい最初のチャンクへのポインタ
<figure><img src="../../images/image (1243).png" alt=""><figcaption><p><a href="https://azeria-labs.com/wp-content/uploads/2019/03/chunk-allocated-CS.png">https://azeria-labs.com/wp-content/uploads/2019/03/chunk-allocated-CS.png</a></p></figcaption></figure>
<div class="mdbook-alerts mdbook-alerts-note">
<p class="mdbook-alerts-title">
<span class="mdbook-alerts-icon"></span>
note
</p>
このようにリストをリンクすることで、すべてのチャンクが登録されている配列を持つ必要がなくなることに注意してください。
</div>
### チャンクポインタ
mallocが使用されると、書き込むことができるコンテンツへのポインタが返されます（ヘッダーの直後）、ただし、チャンクを管理する際には、ヘッダー（メタデータ）の先頭へのポインタが必要です。\
これらの変換には、次の関数が使用されます：
// https://github.com/bminor/glibc/blob/master/malloc/malloc.c
/* Convert a chunk address to a user mem pointer without correcting the tag. / #define chunk2mem(p) ((void)((char*)(p) + CHUNK_HDR_SZ))
/* Convert a user mem pointer to a chunk address and extract the right tag. / #define mem2chunk(mem) ((mchunkptr)tag_at (((char)(mem) - CHUNK_HDR_SZ)))
/* The smallest possible chunk */ #define MIN_CHUNK_SIZE (offsetof(struct malloc_chunk, fd_nextsize))
/* The smallest size we can malloc is an aligned minimal chunk */
#define MINSIZE
(unsigned long)(((MIN_CHUNK_SIZE+MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK))
### アライメントと最小サイズ
チャンクへのポインタと `0x0f` は 0 でなければなりません。
// From https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/sysdeps/generic/malloc-size.h#L61 #define MALLOC_ALIGN_MASK (MALLOC_ALIGNMENT - 1)
// https://github.com/bminor/glibc/blob/a07e000e82cb71238259e674529c37c12dc7d423/sysdeps/i386/malloc-alignment.h #define MALLOC_ALIGNMENT 16
// https://github.com/bminor/glibc/blob/master/malloc/malloc.c /* Check if m has acceptable alignment */ #define aligned_OK(m) (((unsigned long)(m) & MALLOC_ALIGN_MASK) == 0)
#define misaligned_chunk(p)
((uintptr_t)(MALLOC_ALIGNMENT == CHUNK_HDR_SZ ? (p) : chunk2mem (p))
& MALLOC_ALIGN_MASK)
/* pad request bytes into a usable size -- internal version /
/ Note: This must be a macro that evaluates to a compile time constant
if passed a literal constant. */
#define request2size(req)
(((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE) ?
MINSIZE :
((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
/* Check if REQ overflows when padded and aligned and if the resulting value is less than PTRDIFF_T. Returns the requested size or MINSIZE in case the value is less than MINSIZE, or 0 if any of the previous checks fail. */ static inline size_t checked_request2size (size_t req) __nonnull (1) { if (__glibc_unlikely (req > PTRDIFF_MAX)) return 0;
/* When using tagged memory, we cannot share the end of the user block with the header for the next chunk, so ensure that we allocate blocks that are rounded up to the granule size. Take care not to overflow from close to MAX_SIZE_T to a small number. Ideally, this would be part of request2size(), but that must be a macro that produces a compile time constant if passed a constant literal. / if (__glibc_unlikely (mtag_enabled)) { / Ensure this is not evaluated if !mtag_enabled, see gcc PR 99551. */ asm ("");
req = (req + (__MTAG_GRANULE_SIZE - 1)) & ~(size_t)(__MTAG_GRANULE_SIZE - 1); }
return request2size (req); }
合計必要スペースを計算する際、`prev_size` フィールドがデータを格納するために使用できるため、`SIZE_SZ` は1回だけ追加されることに注意してください。そのため、初期ヘッダーのみが必要です。
### チャンクデータを取得し、メタデータを変更する
これらの関数はチャンクへのポインタを受け取り、メタデータをチェック/設定するのに便利です：
- チャンクフラグをチェック
// From https://github.com/bminor/glibc/blob/master/malloc/malloc.c
/* size field is or'ed with PREV_INUSE when previous adjacent chunk in use */ #define PREV_INUSE 0x1
/* extract inuse bit of previous chunk */ #define prev_inuse(p) ((p)->mchunk_size & PREV_INUSE)
/* size field is or'ed with IS_MMAPPED if the chunk was obtained with mmap() */ #define IS_MMAPPED 0x2
/* check for mmap()'ed chunk */ #define chunk_is_mmapped(p) ((p)->mchunk_size & IS_MMAPPED)
/* size field is or'ed with NON_MAIN_ARENA if the chunk was obtained from a non-main arena. This is only set immediately before handing the chunk to the user, if necessary. */ #define NON_MAIN_ARENA 0x4
/* Check for chunk from main arena. */ #define chunk_main_arena(p) (((p)->mchunk_size & NON_MAIN_ARENA) == 0)
/* Mark a chunk as not being on the main arena. */ #define set_non_main_arena(p) ((p)->mchunk_size |= NON_MAIN_ARENA)
- サイズと他のチャンクへのポインタ
/* Bits to mask off when extracting size
Note: IS_MMAPPED is intentionally not masked off from size field in macros for which mmapped chunks should never be seen. This should cause helpful core dumps to occur if it is tried by accident by people extending or adapting this malloc. */ #define SIZE_BITS (PREV_INUSE | IS_MMAPPED | NON_MAIN_ARENA)
/* Get size, ignoring use bits */ #define chunksize(p) (chunksize_nomask (p) & ~(SIZE_BITS))
/* Like chunksize, but do not mask SIZE_BITS. */ #define chunksize_nomask(p) ((p)->mchunk_size)
/* Ptr to next physical malloc_chunk. */ #define next_chunk(p) ((mchunkptr) (((char *) (p)) + chunksize (p)))
/* Size of the chunk below P. Only valid if !prev_inuse (P). */ #define prev_size(p) ((p)->mchunk_prev_size)
/* Set the size of the chunk below P. Only valid if !prev_inuse (P). */ #define set_prev_size(p, sz) ((p)->mchunk_prev_size = (sz))
/* Ptr to previous physical malloc_chunk. Only valid if !prev_inuse (P). */ #define prev_chunk(p) ((mchunkptr) (((char *) (p)) - prev_size (p)))
/* Treat space at ptr + offset as a chunk */ #define chunk_at_offset(p, s) ((mchunkptr) (((char *) (p)) + (s)))
- インスイービット
/* extract p's inuse bit */
#define inuse(p)
((((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size) & PREV_INUSE)
/* set/clear chunk as being inuse without otherwise disturbing */
#define set_inuse(p)
((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size |= PREV_INUSE
#define clear_inuse(p)
((mchunkptr) (((char *) (p)) + chunksize (p)))->mchunk_size &= ~(PREV_INUSE)
/* check/set/clear inuse bits in known places */
#define inuse_bit_at_offset(p, s)
(((mchunkptr) (((char *) (p)) + (s)))->mchunk_size & PREV_INUSE)
#define set_inuse_bit_at_offset(p, s)
(((mchunkptr) (((char *) (p)) + (s)))->mchunk_size |= PREV_INUSE)
#define clear_inuse_bit_at_offset(p, s)
(((mchunkptr) (((char *) (p)) + (s)))->mchunk_size &= ~(PREV_INUSE))
- チャンク番号が使用されている場合、ヘッダーとフッターを設定する
/* Set size at head, without disturbing its use bit */ #define set_head_size(p, s) ((p)->mchunk_size = (((p)->mchunk_size & SIZE_BITS) | (s)))
/* Set size/use field */ #define set_head(p, s) ((p)->mchunk_size = (s))
/* Set size at footer (only when chunk is not in use) */ #define set_foot(p, s) (((mchunkptr) ((char *) (p) + (s)))->mchunk_prev_size = (s))
- チャンク内の実際に使用可能なデータのサイズを取得する
#pragma GCC poison mchunk_size #pragma GCC poison mchunk_prev_size
/* This is the size of the real usable data in the chunk. Not valid for
dumped heap chunks. */
#define memsize(p)
(__MTAG_GRANULE_SIZE > SIZE_SZ && __glibc_unlikely (mtag_enabled) ?
chunksize (p) - CHUNK_HDR_SZ :
chunksize (p) - CHUNK_HDR_SZ + (chunk_is_mmapped (p) ? 0 : SIZE_SZ))
/* If memory tagging is enabled the layout changes to accommodate the granule size, this is wasteful for small allocations so not done by default. Both the chunk header and user data has to be granule aligned. */ _Static_assert (__MTAG_GRANULE_SIZE <= CHUNK_HDR_SZ, "memory tagging is not supported with large granule.");
static __always_inline void * tag_new_usable (void *ptr) { if (__glibc_unlikely (mtag_enabled) && ptr) { mchunkptr cp = mem2chunk(ptr); ptr = __libc_mtag_tag_region (__libc_mtag_new_tag (ptr), memsize (cp)); } return ptr; }
## 例
### クイックヒープの例
[https://guyinatuxedo.github.io/25-heap/index.html](https://guyinatuxedo.github.io/25-heap/index.html) からのクイックヒープの例ですが、arm64で:
#include <stdio.h> #include <stdlib.h> #include <string.h>
void main(void) { char *ptr; ptr = malloc(0x10); strcpy(ptr, "panda"); }
メイン関数の終わりにブレークポイントを設定し、情報がどこに保存されたかを見てみましょう：
<figure><img src="../../images/image (1239).png" alt=""><figcaption></figcaption></figure>
文字列pandaが`0xaaaaaaac12a0`に保存されていることがわかります（これは`x0`内のmallocによって返されたアドレスです）。0x10バイト前を確認すると、`0x0`は**前のチャンクが使用されていない**ことを示しており（長さ0）、このチャンクの長さは`0x21`です。
予約された余分なスペース（0x21-0x10=0x11）は**追加ヘッダー**（0x10）から来ており、0x1は0x21Bが予約されたことを意味するのではなく、現在のヘッダーの長さの最後の3ビットには特別な意味があります。長さは常に16バイト境界に揃えられているため（64ビットマシンで）、これらのビットは実際には長さの数値によって使用されることはありません。
0x1: Previous in Use - Specifies that the chunk before it in memory is in use 0x2: Is MMAPPED - Specifies that the chunk was obtained with mmap() 0x4: Non Main Arena - Specifies that the chunk was obtained from outside of the main arena
### マルチスレッドの例
<details>
<summary>マルチスレッド</summary>
#include <stdio.h> #include <stdlib.h> #include <pthread.h> #include <unistd.h> #include <sys/types.h>
void* threadFuncMalloc(void* arg) { printf("Hello from thread 1\n"); char* addr = (char*) malloc(1000); printf("After malloc and before free in thread 1\n"); free(addr); printf("After free in thread 1\n"); }
void* threadFuncNoMalloc(void* arg) { printf("Hello from thread 2\n"); }
int main() { pthread_t t1; void* s; int ret; char* addr;
printf("Before creating thread 1\n"); getchar(); ret = pthread_create(&t1, NULL, threadFuncMalloc, NULL); getchar();
printf("Before creating thread 2\n"); ret = pthread_create(&t1, NULL, threadFuncNoMalloc, NULL);
printf("Before exit\n"); getchar();
return 0; }