Advanced 3: Writing Your Own Heap#

Sample code#

  • Directory: docs/os-on-arduino/code/adv3_heap

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

Output starts when you send the single character S.

Source code#

The sketch for this chapter. Click a file name to expand. The code is mirrored automatically from the manuscript repository, so what you see here is always current.

src/main.cpp — 75 lines

Open on GitHub

 1/**
 2 * 応用編 第3章: ヒープ自作 — malloc / free を書く
 3 *
 4 * 本章の課題 3.9.1 をそのまま実行する。
 5 *
 6 *   heap_init() → a=malloc(100) → b=malloc(100) → c=malloc(100)
 7 *               → free(b) → free(a)
 8 *
 9 * 各ステップで heap_dump() を呼び、free(a) のあとに a と b が
10 * ひとつの空きブロックへ結合されることを確かめる。
11 * 最後に外部断片化（合計は足りるのに連続では取れない）を再現する。
12 */
13
14#include <Arduino.h>
15#include "os_heap.h"
16
17static void step(const char *label)
18{
19    Serial.println();
20    Serial.print(F("### ")); Serial.println(label);
21    heap_dump();
22}
23
24void setup()
25{
26    Serial.begin(115200);
27    while (!Serial) { }
28    while (Serial.read() != 'S') { delay(1); }
29
30    Serial.println(F("=== Advanced 3: my_malloc / my_free ==="));
31
32    heap_init();
33    step("heap_init()");
34
35    void *a = my_malloc(100);  step("a = my_malloc(100)");
36    void *b = my_malloc(100);  step("b = my_malloc(100)");
37    void *c = my_malloc(100);  step("c = my_malloc(100)");
38
39    my_free(b);                step("my_free(b)");
40    my_free(a);                step("my_free(a)  <- a と b が結合されるはず");
41    my_free(c);                step("my_free(c)  <- ヒープが 1 つの空きブロックに戻る");
42
43    // 課題: ヒープを満杯にしてから 1 つおきに解放すると、
44    // 空き合計は足りるのに連続では取れない（外部断片化）
45    Serial.println();
46    Serial.println(F("### 外部断片化の確認"));
47
48    void *p[8];
49    for (int i = 0; i < 8; i++) {
50        p[i] = my_malloc(496);   // (ヘッダ 16 + 496) × 8 = 4096 で満杯
51    }
52    my_free(p[1]);
53    my_free(p[3]);
54    my_free(p[5]);               // 496 バイトの穴が 3 つ
55    Serial.print(F("空き合計 = ")); Serial.println((unsigned)heap_free_total());
56
57    void *d = my_malloc(600);
58    Serial.print(F("my_malloc(600) -> ")); Serial.println(d ? "OK" : "NULL");
59    Serial.println(F("空きの合計は足りていても、連続した領域が無ければ取れない"));
60
61    my_free(p[2]);               // p[1]〜p[3] が 1520 バイトの穴に結合される
62    void *e = my_malloc(600);
63    Serial.print(F("my_free(p[2]) 後の my_malloc(600) -> ")); Serial.println(e ? "OK" : "NULL");
64
65    // 3.7 デバッグ機能: 二重 free を検出する
66    Serial.println();
67    Serial.println(F("### 二重 free の検出"));
68    my_free(p[0]);
69    my_free(p[0]);   // ここで [heap] double free detected が出る
70
71    Serial.println();
72    Serial.println(F("done."));
73}
74
75void loop() { }
include/os_heap.h — 22 lines

Open on GitHub

 1// os_heap.h
 2//
 3// 本書 応用編 第3章「ヒープ自作」で作る freelist 型アロケータ。
 4
 5#pragma once
 6
 7#include <stddef.h>
 8#include <stdint.h>
 9
10#ifdef __cplusplus
11extern "C" {
12#endif
13
14void  heap_init(void);
15void *my_malloc(size_t n);
16void  my_free(void *p);
17void  heap_dump(void);          // 3.7 デバッグ機能
18size_t heap_free_total(void);   // 空き合計（断片化の観察用）
19
20#ifdef __cplusplus
21}
22#endif
src/os_heap.cpp — 128 lines

Open on GitHub

  1// os_heap.cpp
  2//
  3// 本書 応用編 第3章の実装。ブロックヘッダ + 単方向フリーリスト + first-fit +
  4// 隣接結合。ヒープは明示的な配列として持つ（3.2.2 の「スタックとヒープの衝突」
  5// を避けるため）。
  6
  7#include <Arduino.h>
  8#include <string.h>
  9#include "os_heap.h"
 10
 11typedef struct block_header {
 12    size_t                size;   // データ部のバイト数 (ヘッダは含まない)
 13    int                   free;   // 1 なら空き、0 なら使用中
 14    struct block_header  *next;   // 次のブロックヘッダ
 15    uint32_t              magic;  // 二重 free / 破壊検出用
 16} block_header_t;
 17
 18#define HEAP_MAGIC 0xA110CA7E    // "ALLOCATE" の語呂合わせ
 19#define ALIGN8(x)  (((x) + 7u) & ~7u)
 20#define HEAP_SIZE  4096
 21
 22static uint8_t heap_area[HEAP_SIZE] __attribute__((aligned(8)));
 23static block_header_t *heap_head = NULL;
 24
 25void heap_init(void)
 26{
 27    heap_head        = (block_header_t *)heap_area;
 28    heap_head->size  = HEAP_SIZE - sizeof(block_header_t);
 29    heap_head->free  = 1;
 30    heap_head->next  = NULL;
 31    heap_head->magic = HEAP_MAGIC;
 32}
 33
 34void *my_malloc(size_t n)
 35{
 36    if (n == 0) return NULL;
 37    n = ALIGN8(n);                 // 8 の倍数に切り上げ
 38
 39    block_header_t *b = heap_head;
 40    while (b != NULL) {
 41        if (b->magic != HEAP_MAGIC) {
 42            // ヘッダが破壊されている (バッファオーバーラン等)
 43            return NULL;
 44        }
 45        if (b->free && b->size >= n) {
 46            // 余りが十分なら分割 (split)
 47            if (b->size >= n + sizeof(block_header_t) + 8) {
 48                block_header_t *rest =
 49                    (block_header_t *)((uint8_t *)b + sizeof(block_header_t) + n);
 50                rest->size  = b->size - n - sizeof(block_header_t);
 51                rest->free  = 1;
 52                rest->next  = b->next;
 53                rest->magic = HEAP_MAGIC;
 54                b->size = n;
 55                b->next = rest;
 56            }
 57            b->free = 0;
 58            return (uint8_t *)b + sizeof(block_header_t);
 59        }
 60        b = b->next;
 61    }
 62    return NULL;                   // 空きなし
 63}
 64
 65void my_free(void *p)
 66{
 67    if (p == NULL) return;
 68
 69    block_header_t *b =
 70        (block_header_t *)((uint8_t *)p - sizeof(block_header_t));
 71
 72    if (b->magic != HEAP_MAGIC) {
 73        // 不正なポインタ、もしくはヘッダ破壊
 74        Serial.println(F("[heap] bad pointer or corrupted header"));
 75        return;
 76    }
 77    if (b->free) {
 78        // すでに free 済み → 二重 free 検出
 79        Serial.println(F("[heap] double free detected"));
 80        return;
 81    }
 82    b->free = 1;
 83
 84    // 後続ブロックと結合
 85    if (b->next != NULL && b->next->free) {
 86        b->size += sizeof(block_header_t) + b->next->size;
 87        b->next  = b->next->next;
 88    }
 89
 90    // 前のブロックと結合 (単方向リストなので先頭から探す)
 91    block_header_t *prev = heap_head;
 92    while (prev != NULL && prev->next != b) prev = prev->next;
 93    if (prev != NULL && prev->free) {
 94        prev->size += sizeof(block_header_t) + b->size;
 95        prev->next  = b->next;
 96    }
 97}
 98
 99void heap_dump(void)
100{
101    block_header_t *b = heap_head;
102    int i = 0;
103    size_t total_free = 0, total_used = 0;
104
105    Serial.println(F("---- heap dump ----"));
106    while (b != NULL) {
107        char line[72];
108        snprintf(line, sizeof(line), "[%02d] +%04u size=%5u %s",
109                 i, (unsigned)((uint8_t *)b - heap_area),
110                 (unsigned)b->size, b->free ? "FREE" : "USED");
111        Serial.println(line);
112        if (b->free) total_free += b->size;
113        else         total_used += b->size;
114        b = b->next;
115        i++;
116    }
117    Serial.print(F("total free=")); Serial.print((unsigned)total_free);
118    Serial.print(F(" used="));      Serial.println((unsigned)total_used);
119}
120
121size_t heap_free_total(void)
122{
123    size_t total = 0;
124    for (block_header_t *b = heap_head; b != NULL; b = b->next) {
125        if (b->free) total += b->size;
126    }
127    return total;
128}

On the board#

../_images/adv3_heap.gif

Sending S prints all the dumps at once. The last part shows that an allocation fails when there is no contiguous block even though the total free space is enough, and the detection of a double free.#

Pitfalls#

(Collected from reader questions — ask via GitHub Issues.)