C言語で継続の取得と呼び出し（後編）

2024年 08月 29日

この記事はC言語で継続の取得と呼び出し（前編）の続きです．

仕組み

通常のx86-64のプログラムでは関数が呼び出されると，メモリのスタック領域にリターンアドレスやローカル変数の値を配置しています．
よって，main()関数のスタックフレームから継続を取得したい処理を実行している関数のスタックフレームまでの領域を保存しておき，継続を呼び出すタイミングでスタック領域の値を書き戻すことで，継続の呼び出しの実装が可能です．

また，setjmp()/longjmp()でCPUのレジスタの値を復元しています．保存されるレジスタには次に実行される命令のアドレスも含まれています．

setjmp/longjmp

C言語ではsetjmp()/longjmp()関数を用いて関数の呼び出しを越えたgotoが可能です．
これはJavascriptやPythonなどに実装されているtry-catchのような動作をします．

下記がサンプルコードです．

#include <stdio.h>
#include <setjmp.h>

jmp_buf buf;

void func2() {
  puts("func2 called");
  longjmp(buf, 1);
  puts("this line is not called");
}

void func1() {
  puts("func1 called");
  func2();
  puts("this line is not called");
}

int main() {
  puts("main()");
  if (setjmp(buf) == 0) {
    puts("context saved");
    func1();
  } else {
    puts("longjmp was called");
  };
}

main関数はsetjmpをグローバル変数bufとともに呼び出します．
setjmpはコンテキストを保存した際は0を返り値として返します．
func1はfunc2を呼び出しますが，func2がlongjmpを呼び出すのでこれらの関数がreturnすることはありません．
longjmpの第二引数はsetjmpの返り値となるので，処理が戻ってきたことを検知できます．(0の場合は0でない別の数になります)

この二つの関数はCPUの汎用レジスタなどの実行コンテキストを保存/復元して以上の動作を実現します．

C言語の関数の呼び出しの仕組み

機械語にコンパイルされたC言語のコードが呼び出されるとき，CPUとメモリではなにが起こるのかを整理します．

int add(int a, int b) {
    puts("add");
    return a + b;
}

このような関数を最適化オプションなしでコンパイルしたものが下記のコードです．(x86-64 gcc 14.1.1)

.LC0:
  .string "add"
add:
  pushq %rbp
  movq %rsp, %rbp
  subq $16, %rsp
  movl %edi, -4(%rbp)
  movl %esi, -8(%rbp)
  movl $.LC0, %edi
  call puts
  movl -4(%rbp), %edx
  movl -8(%rbp), %eax
  addl %edx, %eax
  leave
  ret

関数の呼び出しの様子を把握するのに重要なのが%rbpと%rspレジスタの値の変化です．

関数は呼び出されるとスタックフレームを生成します．このフレームには関数を読んだ命令の次のアドレスや%rbpの値，ローカル変数などの情報が記録されています．

関数が呼び出されたとき，%rbpレジスタの値は呼び出し元(ここではcallerと呼びます)の関数の%rbpのままになっています．
この値は保存しないとcallerが値を復元できなくなってしまうため，push命令で%rbpをスタックに保存します．

関数のローカル変数などの領域は%rspの値を減じて(スタックはメモリアドレスが減る方向に伸びます)確保します．
(x-86-64では%rspは16byte単位で伸ばす必要があるため，上記の例ではint(=4byte)x2個の領域を確保する)

GCCでは関数を呼び出さない関数の場合%rspの値を変更しませんが，今回のプログラムの場合は問題とならないため考慮しません．

つまり，一つの関数の持つフレームのアドレスは%rsp~%rbpということになります．複数の関数の際も同様で，継続を取得する関数の%rsp~最も上位の関数の%rbpの範囲を保持すれば良いことになります．

メモリをコピーする前にalloca()を実行する理由

継続を呼び出すcall_continuation関数はスタックのコピーを書き戻す際にallocaを呼び出しています．
これは書き換えているスタックのメモリ領域と実行中の関数のスタックフレームの位置が被らないようにするためです．

    volatile void *q = 0;
    do {
        q=alloca(8);
    } while (q > c->rsp);
    _cc(c, val);

問題点

このライブラリはいくつか問題点があります．

C言語で未定義の動作に大きく依存している

ライブラリはx86-64のレジスタを直接読み出しています．また，スタックがメモリアドレスの高い方から低い方向に伸びることを仮定しています．また，C言語の標準では未定義の動作を使用しているため，移植性があまり高くありません．

効率が悪い

get_continuation()関数はINIT_CONTINUATION()マクロを実行したところから%rspまでのスタックの全てをコピーします．
例えば下記のような例ではほとんど同じ内容のメモリ領域が2つ生成されます．

int func() {
    if (get_continuation(c1) == 0)
        puts("get_continuation1");
    else
        puts("resume1");
    if (get_continuation(c2) == 0)
        puts("get_continuation2");
    else
        puts("resume2");
}

また，継続を呼び出す際もスタックの領域を全て書き換えます．非常に多くのメモリコピーが発生するため，実行時間は長くなります．