シンプルなメモリアロケーターをx86_64アセンブリで実装してみた

## 📌 GitHubリポジトリ & クローン方法  

コードの詳細や最新のアップデートは GitHub で公開しています。  
興味があればぜひチェックしてみてください！🚀  

🔗 **リポジトリ:** [hnk_clang_std_lib](https://github.com/hnkNkm/hnk_clang_std_lib)  

**クローンコマンド:**
```sh
git clone https://github.com/hnkNkm/hnk_clang_std_lib.git
```
---
# 1. はじめに

今回の記事では、シンプルなメモリアロケーターの実装例を紹介します。  
本実装は、システムコールに依存せず、固定サイズのヒープ領域からメモリを確保する基本的な技術を示すものです。  
また、ブロック分割やフリーリストによる管理といった基本概念を理解するためのシンプルな実装例として設計しています。


# 2. メモリアロケーションの基本概念

メモリアロケーションは、プログラム実行中に必要なメモリ領域を動的に割り当てたり解放したりする技術です。  
実際のシステムでは、より高度な管理手法（ブロックの連結、セキュリティ対策など）が用いられますが、  
ここでは以下の基本的なコンセプトに焦点を当てます。

- **固定ヒープ領域の利用:**  
  システムコールに依存せず、1MBの固定領域からメモリを割り当てる

- **ブロック管理:**  
  各ブロックには、ヘッダ部にブロックのサイズと次の空きブロックへのポインタが格納される

- **ブロック分割:**  
  要求サイズに対して十分な余裕がある場合、ブロックを分割し、残り部分を新たな空きブロックとして管理する

- **シンプルなフリーリスト:**  
  解放されたブロックは、単純にフリーリストの先頭に追加される

---

# 3. 実装の詳細

## 3.1 ヘッダ構造の拡張

各ブロックは16バイトのヘッダを持ち、以下のように構成されます。

- **先頭8バイト:**  
  ブロック全体のサイズ（ヘッダを含む）

- **次の8バイト:**  
  空きブロックの場合に有効な、次の空きブロックへのポインタ

この拡張により、各ブロックのサイズ管理とフリーリストによる管理が容易になります。

## 3.2 ヒープの初期化

ヒープは1MBの静的領域として定義され、初期化時には  
**`heap_end` でヒープの終端アドレスを取得し、ヒープ全体のサイズを計算して1つの空きブロックとして設定** します。  
これにより、最初のメモリ割り当て要求時に、フリーリストが適切に管理されます。

## 3.3 メモリ割り当て (my_malloc)

`my_malloc` 関数の主な処理は以下の通りです。

1. **要求サイズの調整:**  
   `my_malloc` では、**8バイト境界にアライメントするため、`add rax, 7` で丸め、`and rax, -8` で調整を行います。**

2. **空きブロックの探索:**  
   フリーリストを走査し、要求サイズを満たすブロックを探します。

3. **ブロック分割:**  
   **ブロックの分割は、`MIN_SPLIT_SIZE`（ヘッダ+8バイト）以上の空きがある場合にのみ行われる**。  
   それ未満の場合は、**ブロック全体をそのまま使用** します。

4. **返却:**  
   ユーザーにはヘッダの直後の領域（実際のデータ領域）のポインタを返します。

## 3.4 メモリ解放 (my_free)

`my_free` 関数では、解放されたブロックのヘッダを取得し、  
単純にフリーリストの先頭に連結します。  
**`free_list` の先頭に追加され、`+8` バイトのポインタに元の `free_list` をセットする** ことで管理されます。

なお、隣接する空きブロックとの連結（coalescing）は実装されていません。

## 3.5 エラーチェック

- `my_malloc` では、0バイトのメモリ割り当て要求が来た場合、  
  **`test rdi, rdi` によるチェックで `NULL` を返すようになっています** (`return_null` ラベルで `RAX=0` にセット)。

- その他、基本的なエラーチェックは実装されていますが、  
  本実装はあくまでシンプルな例であり、実運用向けの堅牢なエラーチェックは行っていません。

---

# 4. コード例
```nasm
; 各ブロックは16バイトのヘッダを持ち、ヘッダは以下の構造：
;   [0]: ブロックサイズ（ブロック全体のサイズ、ヘッダを含む）
;   [8]: 次の空きブロックへのポインタ（空きブロックの場合のみ利用）
; ユーザーにはヘッダの直後のアドレスが返る。

section .bss
    ; 1MB の静的ヒープ領域
    heap       resb 1048576
    ; free_list: 空きブロックの先頭ポインタ（初期状態は未初期化）
    free_list  resq 1

section .data
    ; ヒープ終端の値：heap のアドレス + 1048576
    heap_end   dq heap + 1048576

section .text
global my_malloc
global my_free

; ヘッダサイズ定義（サイズ＋次ポインタ）
%define HEADER_SIZE 16
; 分割可能な最小サイズ（ここでは、ヘッダ＋最低8バイトのユーザーデータ領域＝24バイト未満は分割しない）
%define MIN_SPLIT_SIZE (HEADER_SIZE + 8)

; ------------------------------------------------
; void* my_malloc(size_t size)
;  引数:
;      RDI = 確保するサイズ（バイト単位）
;  戻り値:
;      RAX = 確保したメモリのポインタ（失敗時はNULL）
; ------------------------------------------------
my_malloc:
    ; 0バイト要求なら NULL を返す
    test rdi, rdi
    jz .return_null

    ; アライメント調整（8バイト境界に丸める）
    mov rax, rdi
    add rax, 7
    and rax, -8
    mov rdi, rax

    ; 必要ブロックサイズ = 要求サイズ + ヘッダサイズ
    mov rax, rdi
    add rax, HEADER_SIZE
    mov rcx, rax    ; rcx に調整後の必要サイズ

    ; free_list をチェック、NULLならヒープを初期化
    mov rsi, [free_list]
    test rsi, rsi
    jnz .search_block

    ; ヒープ初期化：ヒープ全体を1つの空きブロックにする
    mov rsi, heap
    mov [free_list], rsi
    ; ブロックサイズ = heap_end - heap
    mov rax, [heap_end]
    sub rax, heap
    mov [rsi], rax
    ; 次ポインタを初期化
    mov qword [rsi+8], 0

.search_block:
    ; rsi: 現在の空きブロックの先頭アドレス
    ; rbx: 直前のブロック（更新用、無ければ0）
    xor rbx, rbx

.search_loop:
    test rsi, rsi
    jz .return_null       ; 空きブロックが見つからなければ失敗

    ; 現在のブロックサイズを取得
    mov rdx, [rsi]        ; rdx = ブロックサイズ（ヘッダ含む）
    cmp rdx, rcx          ; 必要サイズと比較
    jb .not_enough

    ; 十分なサイズがある
    ; 残りサイズ = 現在のブロックサイズ - 必要サイズ
    mov r8, rdx
    sub r8, rcx
    ; 分割可能か判定：残りサイズが MIN_SPLIT_SIZE 以上なら分割する
    mov r9, MIN_SPLIT_SIZE
    cmp r8, r9
    jb .use_whole_block

    ; --- ブロック分割 ---
    ; 割り当て部分：先頭 rcx バイトを使用
    ; 残り部分：r8 バイト、アドレスは (rsi + rcx)
    lea r10, [rsi + rcx]
    ; 新たな空きブロックのヘッダを設定
    mov [r10], r8           ; サイズを設定
    ; 現在のブロックの次ポインタを新ブロックにコピー
    mov r11, [rsi+8]
    mov [r10+8], r11

    ; free_list から現在のブロックを除去
    cmp rbx, 0
    je .update_free_list_head_split
    mov [rbx+8], r10        ; 前のブロックの next を更新
    jmp .return_alloc

.update_free_list_head_split:
    mov [free_list], r10
    jmp .return_alloc

.use_whole_block:
    ; --- ブロック全体を使用（分割しない） ---
    cmp rbx, 0
    je .update_free_list_head_whole
    ; 前のブロックの next を現在のブロックの next に更新
    mov rax, [rsi+8]
    mov [rbx+8], rax
    jmp .return_alloc

.update_free_list_head_whole:
    mov rax, [rsi+8]
    mov [free_list], rax

.return_alloc:
    ; rsi は割り当てたブロックの先頭（ヘッダ位置）
    ; ユーザーデータ領域の先頭は (rsi + HEADER_SIZE)
    lea rax, [rsi + HEADER_SIZE]
    ret

.not_enough:
    ; 次のブロックへ
    mov rbx, rsi          ; 現在のブロックを previous として記憶
    mov rsi, [rsi+8]      ; 次の空きブロックへ
    jmp .search_loop

.return_null:
    xor rax, rax
    ret

; ------------------------------------------------
; void my_free(void* ptr)
;  引数:
;      RDI = 解放するメモリのポインタ（ユーザーデータ領域の先頭）
; ------------------------------------------------
my_free:
    test rdi, rdi
    jz .free_done
    ; ブロックヘッダの先頭を得るために HEADER_SIZE (16) バイト戻る
    sub rdi, HEADER_SIZE
    ; 単純に free_list の先頭に連結する
    mov rax, [free_list]
    mov [rdi+8], rax
    mov [free_list], rdi
.free_done:
    ret

; ------------------------------------------------
; NX対応：実行可能スタックの警告を回避
section .note.GNU-stack noalloc
```
---

# 5. テストコードの紹介
```c
#include <stdio.h>
#include "hnk_c_std_lib.h"

int main() {
    printf("Allocating memory...\n");

    void* ptr = my_malloc(64);
    printf("After my_malloc() call\n");

    if (ptr) {
        printf("Memory allocated at: %p\n", ptr);
        my_free(ptr);
        printf("Memory freed successfully.\n");
    } else {
        printf("Memory allocation failed!\n");
    }

    return 0;
}
```
結果
```bash
root@238e44df2d9f:/app# ./test/malloc_free 
Allocating memory...
After my_malloc() call
Memory allocated at: 0x40403c
Memory freed successfully.
root@238e44df2d9f:/app# 
```
---

# 6. 考察と今後の展望

今回の実装は、非常にシンプルなメモリアロケーターとして、基本的な概念を学ぶための例となっています。  
ただし、以下のような改善点が考えられます。

- **ブロックの連結 (Coalescing):**  
  解放時に隣接する空きブロックを統合することで、メモリの断片化を防ぐことができます。

- **エラーチェックの強化:**  
  不正なメモリアクセスやダブルフリーなど、より堅牢なエラーチェックが必要です。

- **セキュリティ対策:**  
  バッファオーバーフロー防止やその他のセキュリティ対策を実装する必要があります。

---

# 7. 結論

本記事では、**固定ヒープ領域を利用したシンプルなメモリアロケーターの実装例** を紹介しました。  
この実装は **学習目的であり、実運用向けではありません。**  
ヘッダ構造の拡張、ブロック分割、フリーリストによる管理など、メモリアロケーションの **基本概念を理解するためのシンプルな例** として設計されています。

### **本記事のポイント**
- **固定ヒープ領域の利用**  
  システムコールを使わずに 1MB の静的メモリから動的にメモリを割り当てる。
- **ブロック管理**  
  ヘッダを用いてサイズ管理を行い、フリーリストで解放済みメモリを管理。
- **ブロック分割**  
  要求サイズに応じて適切にメモリを分割し、フラグメンテーションを軽減。
- **フリーリストの活用**  
  解放されたメモリを再利用して管理。

# 8. 感想  

今回、シンプルなメモリアロケーターを実装してみて、いくつかの気づきがありました。  

1. **メモリの操作は目に見えないためイメージを掴むのが難しかった**  
   メモリアロケーションの処理は、実際にどのようにメモリが確保・解放されているのかが見えないため、  
   **動作のイメージを掴むのが意外と難しかった** です。  
   特に、フリーリストの管理やブロックの分割・統合を考える際に、  
   **「このアドレスが今どうなっているのか？」** を常に意識する必要がありました。  

2. **動作をアセンブリに書き起こすのが意外と難しかった**  
   C言語であれば、ポインタやメモリ操作の抽象化がある程度進んでいますが、  
   アセンブリでは **「どのレジスタを使うか」「どの順番で操作するか」** まで考えなければならず、  
   **思った以上に試行錯誤が必要** でした。  
   特に、ヒープの初期化やフリーリストの管理をアセンブリで実装するのは大変でした。  

3. **アセンブリで書くとより具体的な命令になっており、抽象化の偉大さを感じられた**  
   高級言語では、メモリの確保・解放は `malloc()` や `free()` のように  
   **シンプルな関数として抽象化** されていますが、  
   **アセンブリで書くと、一つ一つの命令が具体的に記述されるため、  
   どれだけ高度に抽象化されているのかがよく分かりました。**  
   例えば、`my_malloc()` の処理をCで書くのは比較的簡単ですが、  
   アセンブリで書くと「サイズ調整」「ブロック検索」「フリーリスト更新」など、  
   細かい処理の積み重ねになるため、抽象化の偉大さを実感しました。  

この実装を通じて、メモリアロケーションの基本概念を学びつつ、  
低レベルな実装の難しさや、抽象化のありがたみを改めて感じることができました。  
今後は **「ブロックの統合」や「スレッドセーフな実装」** なども試してみたいです。