WAT (WebAssembly Text Format) と Common Lisp で遊ぶ～malloc, freeをつくる編～

Null領域: 灰色のブロック
- オフセット0: ここは利用しない
確保済み領域: オレンジ色のブロック
- 各領域先頭のブロック内の数字はデータ領域（後続の空欄部分）のサイズを表す
- mallocした側には先頭の次のブロックのオフセットが返される（これをポインタのように扱う）
  - 例. 1番左の確保済み領域であればオフセット3をポインタとして扱う
未仕様領域
- 各領域先頭のブロックに入っている数字は次の空き領域のオフセットを表す
  - ブロック下の矢印はこのつながりを表す
- 次のブロックに入っている数字は空き領域のサイズを表す
- 最初と最後の空き領域は特別な扱いをする
  - 最初の空き領域は1つのブロックに次の空き領域へのオフセットだけを持つ
  - 最後の空き領域は先頭のブロックに0を格納する

ここから想像されるように、malloc, free の大まかな動作は次のようになります（場合分け部分はちゃんと図で説明しないと伝わらないやつだなーと思いつつサボっているので雰囲気だけ...）。

malloc
1. 空き領域のオフセットを辿りながら必要サイズ以上の空きがある領域を見つけるか、もしくは末尾の空き領域まで辿り着く
  - この手前の空き領域をA, 見つけた空き領域をB, （あれば）次の空き領域をCとする
2. 空き領域Bの先頭のブロックに容量の情報を入れる
  - 元々入っていたCのオフセットは変数に退避しておく
3. 状況に応じて空き領域を指すオフセットを調整する
  - Bが末尾の空き領域である場合 → Aが指す先をBの次のブロックのオフセットにする
  - そうでない場合
    - Bが全て埋まった場合 → Aが指す先をCのオフセットにする
    - Bがまだ残っている場合 → Aが指す先を残った領域の先頭のブロックのオフセットにし、残った空き領域が指す先をCのオフセットにする
free
1. 解放する領域の手前の空き領域Aと後ろの空き領域Cを見つける
2. 新たに解放する領域を空き領域Bとし、次のようにオフセットを調整する
  - Aが指す先をBの先頭のブロックのオフセットにする
  - Bが指す先をCの先頭のブロックのオフセットにする
    - またBの2番目のブロックにサイズの情報を入れる
3. 空き領域AまたはCと隣接している場合は空き領域をマージする
  - Aとのみ隣接している場合
    - Aが指す先をCの先頭のブロックのオフセットにする
    - Aのサイズ情報にBのサイズを足す
  - Cとのみ隣接している場合
    - Cが末尾の空き領域である場合はBの先頭のブロックに0をセットする
    - そうでない場合はBの指す先をCの次の空き領域のオフセットにする
  - A, C両方と隣接している場合
    - Cが末尾の空き領域である場合はAの先頭のブロックに0をセットする
    - そうでない場合はAの指す先をCの次の空き領域のオフセットにする

（先頭と末尾を例外として）空き領域には次の2ブロック分の情報が必要な点に注意が必要です。

次の空き領域の先頭のオフセット
空き領域のサイズ

とすると、1ブロックだけ余ってしまうと空き領域として繋ぎ込むことができず、空いているのに永遠に利用できない領域になってしまいます。そこで、必ずメモリは2の倍数のサイズ（サイズ情報を入れるブロックを含めて）で確保するという力技で解決します。そのため、要求したサイズと実際に確保されたサイズが異なる場合があります。本来それらの情報は分けて持つべきですが、今回はそれをサボっているので、malloc で要求したサイズに対して大きめのメモリが割り当てられたことが呼び出し側から見えてしまったりします。まあそこは面倒なので妥協ということで...。

中身

前項が概要と言いつつ一通りのアルゴリズムを説明しているので、あとは地道にそれを実装していくだけです。

準備：メモリの用意

今回1次元の配列をメモリとして扱いますが、その1次元配列の用意です。

JavaScript側では次のように WebAssembly.Memory でメモリを用意してWASMに渡します。

const memory = new WebAssembly.Memory({initial:1});
var importObject = {
    console: {
        log: console.log
    },
    js: {
        mem: memory
    }
};

WebAssembly.instantiateStreaming(fetch('wasm/main.wasm'), importObject)
    .then(results => {
        results.instance.exports.test_list();
    });

WASM側ではこれを次のようにimportします。

(defimport.wat mem js.mem (memory 1))

用語

メモリのオフセットはいくつかの意味で利用するので、変数の命名等で下記を使い分けています。

head：空き領域の先頭ブロックのオフセット
ptr（ポインタ）：確保領域のヘッダ領域(*)を除いた先頭のブロックのオフセット
- malloc の返り値はこのオフセットになる

(*) 確保領域のサイズ情報を持つブロックのことで header と呼びます

補助関数

malloc, free の前にそれぞれで利用する補助関数を作っておきます。

i32 型の値のメモリからの読み取り・メモリへの格納には次の組み込み演算子が使えます。

;; メモリからの値の読み取り
(i32.load <オフセット>)
;; メモリへの値の格納
(i32.store <オフセット> <格納する値>)

ただし、ここで言う「オフセット」には注意が必要で、これは32bitではなく8bitの単位になっています。今回、概要の項で説明したようにメモリ上のデータは32bit単位で扱います。毎回4をかけるのも面倒なので、32bit単位で扱えるload, store関数をそれぞれ用意しておきます。なお、以降オフセットといった場合は32bit単位のものを指します（プログラム中の "offset" も同様に32bit単位）。

(defun.wat load-i32 ((offset i32)) (i32)
  (i32.load (i32.mul offset (i32.const 4))))

(defun.wat store-i32 ((offset i32) (value i32)) ()
  (i32.store (i32.mul offset (i32.const 4))
             value))

次に、定数を表に出さないための関数群を定義していきます。それぞれソース中にコメントしていきます。

;; メモリ配列先頭のブロックはいわゆるNullポインタとして扱います
(defun.wat get-null-ptr () (i32)
  (i32.const 0))

;; 2番目（オフセット1）に最初の空き領域へのオフセットが入ります
(defun.wat get-global-memory-head () (i32)
  (i32.const 1))

(defun.wat global-memory-head-p ((head i32)) (i32)
  (i32.eq head (i32.const 1)))

;; 末尾の空き領域の先頭には0が入ります
(defun.wat last-empty-head-p ((head i32)) (i32)
  (i32.eqz (load-i32 head)))

;; 割り当てられたメモリ領域のヘッダサイズは1で、サイズ情報が入ります
;; (get-allocated-memory-header-size とかの方が良いかも...)
(defun.wat get-header-size () (i32)
  (i32.const 1))

;; 空き領域の先頭の次の領域には、空き領域のサイズ情報が入ります
(defun.wat get-empty-memory-size ((head i32)) (i32)
  (load-i32 (i32+ head 1)))

(defun.wat set-empty-memory-size ((head i32) (size i32)) ()
  (store-i32 (i32+ head 1)
             size))

;; 空き領域の先頭には次の空き領域のオフセットが入ります
(defun.wat get-next-head ((head i32)) (i32)
  (load-i32 head))

;; 「ポインタ」として呼び出し側に渡されるのはヘッダ以降の部分なので、
;; そこから1つ手前に割り当てサイズの情報が入ります
(defun.wat get-pointer-size ((ptr i32)) (i32)
  (load-i32 (i32- ptr 1)))

補助関数と分類して良いか微妙ですが、初期化用の関数も示します。

(defun.wat init-memory () ()
  ;; オフセット1のブロックから、オフセット2の空き領域を指す
  (store-i32 (get-global-memory-head)
             (i32.const 2))
  ;; オフセット2の空き領域は末尾の空き領域
  (store-i32 (i32.const 2)
             (i32.const 0)))

malloc

malloc の実装は本体の他、2つの補助関数 adjust-malloc-size, malloc-recからなります。

malloc
- シグネチャ
  - 引数：size = 確保したいメモリサイズ
  - 返り値：確保したメモリへのポインタ
- 実装的には adjust-malloc-size でサイズを調整後、 malloc-rec を呼び出してその値を返すだけ
adjust-malloc-size
- 概要で書いたように、半端なメモリを生まないためのサイズ調整をするのがここです
- シグネチャ
  - 引数：
    - size = 確保したいメモリサイズ
    - header-size = ヘッダのサイズ
    - align-size = ※返り値の中で説明
  - 返り値：align-size の倍数かつ size + header-size 以上の最小の値から header-size を引いた値
malloc-rec
- 概要で書いたような、空き領域を辿って十分な空きがある領域を探したり、確保後に場合分けに応じてオフセットの値を書き換えたり... という一連の面倒な処理を引き受けている関数です
- シグネチャ
  - 引数
    - size = 確保したいメモリサイズ
    - prev-head = 1つ手前の空き領域の先頭オフセット
    - head = 空き領域の先頭オフセット
  - 返り値：確保したメモリへのポインタ

それぞれ見ていきます。malloc の実装は上に書いた通り補助関数を呼ぶ程度のものです。

(defun.wat malloc ((size i32)) (i32)
  (let (((actual-size i32) (adjust-malloc-size size
                                               (get-header-size)
                                               (i32.const 2)))
        ((global-head i32) (get-global-memory-head)))
    (malloc-rec actual-size
                global-head
                (get-next-head global-head))))

次にメモリサイズを調整する adjust-malloc-size です。前述の「align-size の倍数かつ size + header-size 以上の最小の値から header-size を引いた値」を返すようにぼちぼち計算します。

(defun.wat adjust-malloc-size ((size i32) (header-size i32) (align-size i32)) (i32)
  (let* (((required i32) (i32+ size header-size))
         ((rem i32) (i32.rem-u required align-size))
         (aligned i32))
    (if (i32.eqz rem)
        (set-local aligned required)
        ;; 境界まで足りない分を足す
        (set-local aligned (i32+ required
                                 (i32- align-size rem))))
    (i32- aligned header-size)))

実装的には本丸の malloc-rec です。適宜コメントを補うので雰囲気を感じてください。ちなみに、前回実装した cond マクロのおかげで分岐の見通しが良いですね。

(defun.wat malloc-rec ((size i32) (prev-head i32) (head i32)) (i32)
  (let (((next-head i32) (get-next-head head))
        (new-head i32)
        (rest-size i32)
        (result i32))
    (cond
      ;; --- 末尾の空き領域の場合 ---
      ((i32.eq next-head (i32.const 0))
       ;; ※全体のメモリが不足していたら伸ばす処理が必要ですがTODOのままです...
       ;; - 空き領域のオフセット調整 - ;;
       (set-local new-head
                  (i32+ head size (get-header-size)))
       (store-i32 new-head (i32.const 0))
       (store-i32 prev-head new-head)
       ;; - 確保した領域のポインタ返却準備 - ;;
       (store-i32 head size)
       (set-local result (i32+ head (get-header-size))))

      ;; --- （末尾までに）十分な空きを見つけた場合 ---
      ((i32.ge-u (get-empty-memory-size head)
                 size)
       ;; - 空き領域のオフセット調整 - ;;
       ;; 確保した後に空きが残っているか否かで場合分け
       (set-local rest-size (i32- (get-empty-memory-size head)
                                  size))
       (if (i32.eqz rest-size)
           (set-local new-head next-head)
           (progn (set-local new-head (i32+ head size (get-header-size)))
                  (store-i32 new-head next-head)
                  ;; アラインメント調整で先頭の次のブロックが空いていることが保証されているので、
                  ;; そこに空き領域のサイズ情報をセットします
                  (set-empty-memory-size new-head
                                         (i32- rest-size (get-header-size)))))
       (store-i32 prev-head new-head)
       ;; - 確保した領域のポインタ返却準備 - ;;
       (store-i32 head size)
       (set-local result (i32+ head (get-header-size))))

      ;; --- 空きが不十分だった場合 ---
      ;; 次の空き領域を再帰的に見にいく
      (t (malloc-rec size head next-head)
         (set-local result))))
  (get-local result))

free

free は補助関数を含め次のような関数からなります。

free
- シグネチャ
  - 引数：ptr = 解放したいポインタ
- 補足：二重解放はご法度です（未定義動作）
find-prev-empty-head
- 渡されたポインタの1つ手前の空き領域を見つける
- シグネチャ
  - 引数：ptr = ポインタ
  - 返り値：ptr の1つ手前の空き領域の先頭のオフセット
- 補足：補助関数として find-prev-empty-head-rec を持つ
merge-empty-memory-if-enable
- 2つの空き領域がマージ可能だったらマージする
- シグネチャ
  - 引数
    - prev-head = head の1つ前の空き領域の先頭のオフセット
    - head = 空き領域の先頭のオフセット
  - 返り値：マージ可能なら1, そうでなければ0

コメントを補いながら実装を並べていきます。

まず free の実装です。補助関数を2つ呼ぶだけの malloc に比べると仕事が多いです。

(defun.wat free ((ptr i32)) ()
  ;; ポインタの前後の空き領域を探す
  (let* (((prev-head i32) (find-prev-empty-head ptr))
         ((next-head i32) (get-next-head prev-head))
         ((new-head i32) (i32- ptr (get-header-size)))
         ((size i32) (get-pointer-size ptr)))
    ;; ポインタ領域を空き領域にする
    (store-i32 prev-head new-head)
    (store-i32 new-head next-head)
    (set-empty-memory-size new-head size)
    ;; 可能なら手前の空き領域にマージする
    (when (merge-empty-memory-if-enable prev-head new-head)
      ;; NOTE: ここで new-head を移動しておくことで↓で場合分けがいらなくなる
      (set-local new-head prev-head))
    ;; 可能なら直後の空き領域にマージする
    ;; NOTE: そのまま呼ぶとi32型の値を返すことになってしまうのでwhenで囲っておく
    ;;       もっと標準的なやり方がある気がする
    (when (merge-empty-memory-if-enable new-head next-head))))

次に、ポインタ手前の空き領域を探す find-prev-empty-head(-rec) です。

(defun.wat find-prev-empty-head-rec ((ptr i32) (head i32)) (i32)
  (let (((next-head i32) (get-next-head head))
        (result i32))
    (cond ((i32.eqz next-head)
           ;; 見つかる前に末尾の空き領域に着いてしまったケース（起こり得ない）
           (set-local result (i32.const 0)))
          ;; 見つかった
          ((i32.gt-u next-head ptr)
           (set-local result head))
          ;; 見つからなかったので次を見る
          (t (find-prev-empty-head-rec ptr next-head)
             (set-local result)))
    (get-local result)))

(defun.wat find-prev-empty-head ((ptr i32)) (i32)
  (find-prev-empty-head-rec ptr (get-global-memory-head)))

最後に、可能なら空き領域をマージする merge-empty-memory-if-enable です。

(defun.wat merge-empty-memory-if-enable ((prev-head i32) (head i32)) (i32)
  (let (((result i32) (i32.const 0)))
    ;; 最初の空き領域（オフセット1）にはマージしない
    (unless (global-memory-head-p prev-head)
      ;; 空き領域が隣接していることの確認
      (when (i32.eq (i32+ prev-head
                          (get-header-size)
                          (get-empty-memory-size prev-head))
                    head)
        (store-i32 prev-head
                   (get-next-head head))
        ;; 末尾の空き領域でなければ足し合わせたサイズの値を格納する
        (unless (last-empty-head-p head)
          (set-empty-memory-size prev-head
                                 (i32+ (get-empty-memory-size prev-head)
                                       (get-header-size)
                                       (get-empty-memory-size head))))
        (set-local result (i32.const 1))))
    (get-local result)))

malloc, free を使ってみる: リスト構造

せっかく malloc, free を作ったので、これを使って下記のように cons 関数を作ってリスト構造を構成できるようにしてみます。

(defun.wat test-list () ()
  (let ((lst i32))
    (set-local lst (cons (new-i32 (i32.const 10))
                         (cons (new-i32 (i32.const 20))
                               (new-i32 (i32.const 30)))))
    (log (get-i32 (car lst)))       ; -> 10 
    (log (get-i32 (car (cdr lst)))) ; -> 20
    (log (get-i32 (cdr (cdr lst)))) ; -> 30
    (free-typed lst)))

メモリ上のデータがコンスセルなのか数値（i32）なのかといったことを区別するため、ここで型を（雑に）導入します。型情報を持つデータはメモリ上で次のように表現されます。

1ブロック目：型を表すi32型の値が入る（以降「型ID」と呼ぶ）
2ブロック目以降：データ領域。このサイズや使い方はそれぞれの型によって決まる

ということで、型を定義する deftype.wat と補助関数を定義します。

;; ヘッダ = 型IDが入る領域
(defun.wat get-type-header-size () (i32)
  (i32.const 1))

;; 確保領域の先頭のブロックには型を表す値が入る
(defun.wat get-type ((ptr i32)) (i32)
  (load-i32 ptr))

;; データは確保領域の2ブロック目から始まる
(defun.wat get-type-data-offset ((ptr i32)) (i32)
  (i32+ ptr (i32.const 1)))

;; ※本文で解説
(defmacro deftype.wat (name size id)
  `(progn (defun.wat ,(symbolicate "MAKE-" name) () (i32)
            (let (((ptr i32) (malloc (i32+ (get-type-header-size)
                                           (i32.const ,size)))))
              (store-i32 ptr (i32.const ,id))
              (get-local ptr)))
          (defun.wat ,(symbolicate name "-ID-P") ((typ i32)) (i32)
            (i32.eq typ (i32.const ,id)))
          (defun.wat ,(symbolicate name "-P") ((type-ptr i32)) (i32)
            (,(symbolicate name "-ID-P") (get-type type-ptr)))))

例えば、(deftype.wat hoge 2 1) とした場合、型ID = 1で hoge 型に関する3つの関数が生成されます（型IDは自動インクリメントなどにしたいところ...）。

make-hoge：malloc で hoge 型に必要なメモリを確保してそのポインタを返す
- deftype.wat で指定したサイズ2 + ヘッダサイズ1 = 3ブロック分のメモリを確保する
hoge-id-p：渡された型IDが hoge 型のものであるかを返す
hoge-p：渡されたポインタ領域に入っているデータが hoge 型であるかを返す

まずはこれを利用して、i32 型を型ID = 1で義します。データ領域にWATの i32 型の数値1つを持つだけの型です。取りあえず初期化関数, getter, setterとfree用の関数も用意します。

(deftype.wat i32 1 1)

(defun.wat new-i32 ((value i32)) (i32)
  (let (((ptr i32) (make-i32)))
    (set-i32 ptr value)
    (get-local ptr)))

(defun.wat get-i32 ((i32-ptr i32)) (i32)
  (load-i32 (get-type-data-offset i32-ptr)))

(defun.wat set-i32 ((i32-ptr i32) (value i32)) ()
  (store-i32 (get-type-data-offset i32-ptr)
             value))
             
(defun.wat free-i32 ((i32-ptr i32)) ()
  (free i32-ptr))

次に肝心の cons-cell を型ID = 101で定義します。これはブロック2つ分のデータ領域を持ち、それぞれにポインタを格納します*1。

(deftype.wat cons-cell 2 101)

(defun.wat cons ((ptr-car i32) (ptr-cdr i32)) (i32)
  (let (((ptr i32) (make-cons-cell)))
    (set-car ptr ptr-car)
    (set-cdr ptr ptr-cdr)
    (get-local ptr)))

;; データ領域の1ブロック目がcar部
(defun.wat car ((cons-cell-ptr i32)) (i32)
  (load-i32 (get-type-data-offset cons-cell-ptr)))

(defun.wat set-car ((cons-cell-ptr i32) (value i32)) ()
  (store-i32 (get-type-data-offset cons-cell-ptr)
             value))

;; データ領域の2ブロック目がcdr部
(defun.wat cdr ((cons-cell-ptr i32)) (i32)
  (load-i32 (i32+ (get-type-data-offset cons-cell-ptr)
                  (i32.const 1))))

(defun.wat set-cdr ((cons-cell-ptr i32) (value i32)) ()
  (store-i32 (i32+ (get-type-data-offset cons-cell-ptr)
                   (i32.const 1))
             value))

;; car部, cdr部のメモリも含めて解放する
(defun.wat free-cons-cell ((cons-cell-ptr i32)) ()
  (free-typed (car cons-cell-ptr))
  (free-typed (cdr cons-cell-ptr))
  (free cons-cell-ptr))

free-cons-cell は、任意の型のfreeを行う下記 free-typed との再帰定義になっています。

(defun.wat free-typed ((type-ptr i32)) ()
  (cond ((i32-p type-ptr) (free-i32 type-ptr))
        ((cons-cell-p type-ptr) (free-cons-cell type-ptr))))

ということで、冒頭に掲げた例のようにリストを構成できるようになりました（再掲）。

(defun.wat test-list () ()
  (let ((lst i32))
    (set-local lst (cons (new-i32 (i32.const 10))
                         (cons (new-i32 (i32.const 20))
                               (new-i32 (i32.const 30)))))
    (log (get-i32 (car lst)))       ; -> 10 
    (log (get-i32 (car (cdr lst)))) ; -> 20
    (log (get-i32 (cdr (cdr lst)))) ; -> 30
    (free-typed lst)))

今後

とりあえずこんなのが考えられそう...ぐらいのもので特に具体的な展望はないやつです。

ガベージコレクタ...？

現状自分で malloc, free するしかないので参照カウンタ方式なりマーク・アンド・スイープ方式なりのガベージコレクタが欲しいところです。

純LISP...？

せっかくリスト構造ができたので純LISP（参考：Wikipedia, ポール・グレアム Lispの起源 (The Roots of Lisp)）にも心惹かれるところです。今回 cons を作りましたが、この横に defun.wat で関数を並べてできる訳ではなく、cons で構成したリストをプログラムとして解釈するインタプリタをつくることが必要なのだろうなと思います。

おまけ：書き出されるWAT（抜粋）

前回作成したCommon Lispのガワを利用してWATを書いてきましたが、実際に書き出されるWATがどんなものかを見てみます。

まずは今回書いたもののうち、一番複雑な malloc-rec を再掲します。個人的にはがんばれば読めそうかな...という範疇に収まっているように見えます（そもそもが少々面倒なことをしているので、こうしてコメントを除くとちょっと辛い...というのは目をつむって見た目として）。

(defun.wat malloc-rec ((size i32) (prev-head i32) (head i32)) (i32)
  (let (((next-head i32) (get-next-head head))
        (new-head i32)
        (rest-size i32)
        (result i32))
    (cond
      ((i32.eq next-head (i32.const 0))
       (set-local new-head
                  (i32+ head size (get-header-size)))
       (store-i32 new-head (i32.const 0))
       (store-i32 prev-head new-head)
       (store-i32 head size)
       (set-local result (i32+ head (get-header-size))))
      ((i32.ge-u (get-empty-memory-size head)
                 size)
       (set-local rest-size (i32- (get-empty-memory-size head)
                                  size))
       (if (i32.eqz rest-size)
           (set-local new-head next-head)
           (progn (set-local new-head (i32+ head size (get-header-size)))
                  (store-i32 new-head next-head)
                  (set-empty-memory-size new-head
                                         (i32- rest-size (get-header-size)))))
       (store-i32 prev-head new-head)
       (store-i32 head size)
       (set-local result (i32+ head (get-header-size))))
      (t (malloc-rec size head next-head)
         (set-local result))))
  (get-local result))

そして、実際に書き出されるWATがこちらです（相変わらずインデントは手動）。こちらはがんば...る気がまず一目で削がれるのですがいかがでしょう？call や get_localなど、本質的にはプログラムには関係ない「装飾」が多過ぎるのかなと。WATそのものなのでシンタックスハイライトはきれいに出るのですが...。

※変数名や関数名は実際には大文字で書き出されますが、見た目の比較としてはアンフェアな気がしたので小文字に直しています（なお大文字の方がゴツくて読み辛い印象でした）

(func $malloc-rec (param $size i32) (param $prev-head i32) (param $head i32) (result i32)
  (local $next-head i32)
  (local $new-head i32)
  (local $rest-size i32)
  (local $result i32)
  (set_local $next-head (call $get-next-head (get_local $head)))
  (if (i32.eq (get_local $next-head) (i32.const 0))
    (then
      (set_local $new-head (i32.add (get_local $head)
                                    (i32.add (get_local $size)
                                             (call $get-header-size))))
      (call $store-i32 (get_local $new-head) (i32.const 0))
      (call $store-i32 (get_local $prev-head) (get_local $new-head))
      (call $store-i32 (get_local $head) (get_local $size))
      (set_local $result (i32.add (get_local $head)
                                  (call $get-header-size))))
    (else
      (if (i32.ge_u (call $get-empty-memory-size (get_local $head))
                    (get_local $size))
        (then
          (set_local $rest-size
                     (i32.sub (call $get-empty-memory-size (get_local $head))
                              (get_local $size)))
          (if (i32.eqz (get_local $rest-size))
            (then
              (set_local $new-head (get_local $next-head)))
            (else
              (set_local $new-head (i32.add (get_local $head)
                                            (i32.add (get_local $size)
                                                     (call $get-header-size))))
              (call $store-i32 (get_local $new-head) (get_local $next-head))
              (call $set-empty-memory-size (get_local $new-head)
                                           (i32.sub (get_local $rest-size)
                                                    (call $get-header-size)))))
          (call $store-i32 (get_local $prev-head) (get_local $new-head))
          (call $store-i32 (get_local $head) (get_local $size))
          (set_local $result (i32.add (get_local $head)
                                      (call $get-header-size))))
        (else
          (call $malloc-rec (get_local $size)
                            (get_local $head)
                            (get_local $next-head))
          (set_local $result)))))
  (get_local $result))

次回

eshamster.hatenablog.com

*1:もしかしたらポインタ型を用意してそれを持たせた方が良いのかもしれませんが、良し悪しをまだ検討できていません