応用編 第3章: ヒープ自作 — malloc / free を書く

malloc / free を自分で書き、断片化と戦います。

サンプルコード

• ディレクトリ: docs/os-on-arduino/code/adv3_heap

• ビルドと書き込み:

uv run pio run -d adv3_heap -t upload
uv run pio device monitor -b 115200

S を 1 文字送ると出力が始まります。

コードを見る: docs/os-on-arduino/code/adv3_heap

ソースコード

この章のスケッチです。ファイル名をクリックすると開きます。コードは原稿リポジトリから自動で同期されているので、ここに出ているものが常に最新です。

src/main.cpp — 75 行

GitHub で開く

/**
 * 応用編 第3章: ヒープ自作 — malloc / free を書く
 *
 * 本章の課題 3.9.1 をそのまま実行する。
 *
 *   heap_init() → a=malloc(100) → b=malloc(100) → c=malloc(100)
 *               → free(b) → free(a)
 *
 * 各ステップで heap_dump() を呼び、free(a) のあとに a と b が
 * ひとつの空きブロックへ結合されることを確かめる。
 * 最後に外部断片化（合計は足りるのに連続では取れない）を再現する。
 */

#include <Arduino.h>
#include "os_heap.h"

static void step(const char *label)
{
    Serial.println();
    Serial.print(F("### ")); Serial.println(label);
    heap_dump();
}

void setup()
{
    Serial.begin(115200);
    while (!Serial) { }
    while (Serial.read() != 'S') { delay(1); }

    Serial.println(F("=== Advanced 3: my_malloc / my_free ==="));

    heap_init();
    step("heap_init()");

    void *a = my_malloc(100);  step("a = my_malloc(100)");
    void *b = my_malloc(100);  step("b = my_malloc(100)");
    void *c = my_malloc(100);  step("c = my_malloc(100)");

    my_free(b);                step("my_free(b)");
    my_free(a);                step("my_free(a)  <- a と b が結合されるはず");
    my_free(c);                step("my_free(c)  <- ヒープが 1 つの空きブロックに戻る");

    // 課題: ヒープを満杯にしてから 1 つおきに解放すると、
    // 空き合計は足りるのに連続では取れない（外部断片化）
    Serial.println();
    Serial.println(F("### 外部断片化の確認"));

    void *p[8];
    for (int i = 0; i < 8; i++) {
        p[i] = my_malloc(496);   // (ヘッダ 16 + 496) × 8 = 4096 で満杯
    }
    my_free(p[1]);
    my_free(p[3]);
    my_free(p[5]);               // 496 バイトの穴が 3 つ
    Serial.print(F("空き合計 = ")); Serial.println((unsigned)heap_free_total());

    void *d = my_malloc(600);
    Serial.print(F("my_malloc(600) -> ")); Serial.println(d ? "OK" : "NULL");
    Serial.println(F("空きの合計は足りていても、連続した領域が無ければ取れない"));

    my_free(p[2]);               // p[1]〜p[3] が 1520 バイトの穴に結合される
    void *e = my_malloc(600);
    Serial.print(F("my_free(p[2]) 後の my_malloc(600) -> ")); Serial.println(e ? "OK" : "NULL");

    // 3.7 デバッグ機能: 二重 free を検出する
    Serial.println();
    Serial.println(F("### 二重 free の検出"));
    my_free(p[0]);
    my_free(p[0]);   // ここで [heap] double free detected が出る

    Serial.println();
    Serial.println(F("done."));
}

void loop() { }

include/os_heap.h — 22 行

GitHub で開く

// os_heap.h
//
// 本書 応用編 第3章「ヒープ自作」で作る freelist 型アロケータ。

#pragma once

#include <stddef.h>
#include <stdint.h>

#ifdef __cplusplus
extern "C" {
#endif

void  heap_init(void);
void *my_malloc(size_t n);
void  my_free(void *p);
void  heap_dump(void);          // 3.7 デバッグ機能
size_t heap_free_total(void);   // 空き合計（断片化の観察用）

#ifdef __cplusplus
}
#endif

src/os_heap.cpp — 128 行

GitHub で開く

// os_heap.cpp
//
// 本書 応用編 第3章の実装。ブロックヘッダ + 単方向フリーリスト + first-fit +
// 隣接結合。ヒープは明示的な配列として持つ（3.2.2 の「スタックとヒープの衝突」
// を避けるため）。

#include <Arduino.h>
#include <string.h>
#include "os_heap.h"

typedef struct block_header {
    size_t                size;   // データ部のバイト数 (ヘッダは含まない)
    int                   free;   // 1 なら空き、0 なら使用中
    struct block_header  *next;   // 次のブロックヘッダ
    uint32_t              magic;  // 二重 free / 破壊検出用
} block_header_t;

#define HEAP_MAGIC 0xA110CA7E    // "ALLOCATE" の語呂合わせ
#define ALIGN8(x)  (((x) + 7u) & ~7u)
#define HEAP_SIZE  4096

static uint8_t heap_area[HEAP_SIZE] __attribute__((aligned(8)));
static block_header_t *heap_head = NULL;

void heap_init(void)
{
    heap_head        = (block_header_t *)heap_area;
    heap_head->size  = HEAP_SIZE - sizeof(block_header_t);
    heap_head->free  = 1;
    heap_head->next  = NULL;
    heap_head->magic = HEAP_MAGIC;
}

void *my_malloc(size_t n)
{
    if (n == 0) return NULL;
    n = ALIGN8(n);                 // 8 の倍数に切り上げ

    block_header_t *b = heap_head;
    while (b != NULL) {
        if (b->magic != HEAP_MAGIC) {
            // ヘッダが破壊されている (バッファオーバーラン等)
            return NULL;
        }
        if (b->free && b->size >= n) {
            // 余りが十分なら分割 (split)
            if (b->size >= n + sizeof(block_header_t) + 8) {
                block_header_t *rest =
                    (block_header_t *)((uint8_t *)b + sizeof(block_header_t) + n);
                rest->size  = b->size - n - sizeof(block_header_t);
                rest->free  = 1;
                rest->next  = b->next;
                rest->magic = HEAP_MAGIC;
                b->size = n;
                b->next = rest;
            }
            b->free = 0;
            return (uint8_t *)b + sizeof(block_header_t);
        }
        b = b->next;
    }
    return NULL;                   // 空きなし
}

void my_free(void *p)
{
    if (p == NULL) return;

    block_header_t *b =
        (block_header_t *)((uint8_t *)p - sizeof(block_header_t));

    if (b->magic != HEAP_MAGIC) {
        // 不正なポインタ、もしくはヘッダ破壊
        Serial.println(F("[heap] bad pointer or corrupted header"));
        return;
    }
    if (b->free) {
        // すでに free 済み → 二重 free 検出
        Serial.println(F("[heap] double free detected"));
        return;
    }
    b->free = 1;

    // 後続ブロックと結合
    if (b->next != NULL && b->next->free) {
        b->size += sizeof(block_header_t) + b->next->size;
        b->next  = b->next->next;
    }

    // 前のブロックと結合 (単方向リストなので先頭から探す)
    block_header_t *prev = heap_head;
    while (prev != NULL && prev->next != b) prev = prev->next;
    if (prev != NULL && prev->free) {
        prev->size += sizeof(block_header_t) + b->size;
        prev->next  = b->next;
    }
}

void heap_dump(void)
{
    block_header_t *b = heap_head;
    int i = 0;
    size_t total_free = 0, total_used = 0;

    Serial.println(F("---- heap dump ----"));
    while (b != NULL) {
        char line[72];
        snprintf(line, sizeof(line), "[%02d] +%04u size=%5u %s",
                 i, (unsigned)((uint8_t *)b - heap_area),
                 (unsigned)b->size, b->free ? "FREE" : "USED");
        Serial.println(line);
        if (b->free) total_free += b->size;
        else         total_used += b->size;
        b = b->next;
        i++;
    }
    Serial.print(F("total free=")); Serial.print((unsigned)total_free);
    Serial.print(F(" used="));      Serial.println((unsigned)total_used);
}

size_t heap_free_total(void)
{
    size_t total = 0;
    for (block_header_t *b = heap_head; b != NULL; b = b->next) {
        if (b->free) total += b->size;
    }
    return total;
}

実機での出力

Arduino UNO R4 WiFi の実機で実際に取得した出力です（macOS / Windows の 両方で同じ結果を確認しています）。手元の出力と見比べてください。

ヒープの状態を段階ごとにダンプしています。

S を送ると、すべてのダンプがまとめて出ます。最後は「空きの合計は 足りていても連続領域が無ければ取れない」ところと、二重 free の検出です

=== Advanced 3: my_malloc / my_free ===

### heap_init()
---- heap dump ----
[00] +0000 size= 4080 FREE
total free=4080 used=0

### a = my_malloc(100)
---- heap dump ----
[00] +0000 size=  104 USED
[01] +0120 size= 3960 FREE
total free=3960 used=104

### b = my_malloc(100)
---- heap dump ----
[00] +0000 size=  104 USED
[01] +0120 size=  104 USED
[02] +0240 size= 3840 FREE
total free=3840 used=208
...

つまずきやすいポイント

（読者からの質問に応じて随時追記します。質問は GitHub Issues へどうぞ）