セプキャン2011のCTFで出題されたOSのタスク切換え問題の解説です。1週間経ってしまったので今更な感は否めないですね……。

問題

以下はsetjmp()/longjmp()を用いてOSのタスク切換えっぽいものをユーザランドで実装した例です。ただし２箇所、空行にしてあります。

以下が期待通りにタスク切換えしながら動作するように完成させて実行したとき、出力される文字列を答えてください。

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

#define TASKNUM 3

typedef void (*func_t)(int arg);

struct tcb {
  int active;
  func_t func;
  jmp_buf context;
};

struct tcb task[TASKNUM];
struct tcb *current;

void task_change();
void task_end();

void main1(int arg)
{
  printf("%d", arg);
  printf("A");
  task_change();
  task_change();
  printf("B");
}

void main2(int arg)
{
  printf("%d", arg);
  task_change();
  printf("C");
  task_change();
  printf("D");
  task_change();
  printf("E");
  task_change();
  printf("F");
}

void main3(int arg)
{
  printf("%d", arg);
  printf("G");
  task_change();
  printf("H");
  task_end();
  printf("I");
}

func_t task_main[] = { main1, main2, main3 };

void schedule()
{
  static int n = 0;
  int i;
  for (i = 0; i < TASKNUM; i++) {
    n = (n + 1) % TASKNUM;
    current = &task[n];
    if (current->active) {
      /* ほげほげ */
    }
  }
  exit(0);
}

void task_change()
{
  if (setjmp(current->context) == 0)
    /* ほげほげ */;
}

void task_end()
{
  current->active = 0;
  schedule();
}

void task_start(int arg)
{
  current->func(arg);
  task_end();
}

void task_create()
{
  volatile char stack[1024];
  static int n = 0;

  if (n == TASKNUM)
    schedule();

  memset(&stack, 0, sizeof(stack));
  task[n].active = 1;
  task[n].func = task_main[n];
  if (setjmp(task[n].context))
    task_start(n);

  n++;
  task_create();
}

int main()
{
  memset(task, 0, sizeof(task));
  task_create();
  return 0;
}

答え

一応伏せておくので見たい人は以下の空間を選択してください。

答えは「33G3ACHDBEF」です。2箇所の空欄にはそれぞれ「longjmp(current->context, 1);」「schedule();」が入ります。

setjmp/longjmp

setjmpとlongjmpは関数を跨いだジャンプを実現するための関数です。setjmpを呼び出すとその時のスタックポインタやレジスタなどの状態を引数として渡したjmp_buf型の変数に書き出します。longjmpでは逆に値を書き戻すことでsetjmpした時の状態に戻ることができます。ただ、完全に元の状態に戻ってしまうとsetjmpで書き出したのかlongjmpで書き戻したのか区別できなくなってしまうので、setjmpの戻り値で区別します。以下のように、戻り値が0であれば状態を保存した後であり、0以外であればlongjmpで戻ってきたと判断できます。

jmp_buf buf;

if (setjmp(buf) != 0) {
  /* longjmpで復帰 */
}
else {
  /* bufに状態を保存 */
}

解法

最終日に発表したように、地道にコードを読んでいけば答えにたどり着けます。

tcb構造体は、タスクがアクティブかどうかを示すactive、タスクのメイン関数を示すfunc、longjmpでの戻り先を保持するcontextからなっています。この構造体は各タスクに1つずつ用意されており、現在実行中のものを示すポインタとしてcurrentが用意されています。

schedule関数は、アクティブなタスクを探して最初に見つかったものを実行する関数です。タスクが見つかったらすぐにlongjmpするので、この関数に戻って他のタスクが探索されることはありません。探索の始点はstaticな変数nに保存された値+1からとなるので、同じタスクが連続して実行されずにすべてのタスクが順番に実行されます。すべての要素を探索してアクティブなタスクが存在しなかった場合はexit関数でプログラムを終了します。

task_change関数は、現在の状態を保存して次のタスクを実行する関数です。次のタスクの実行は、schedule関数を呼び出すことで実現できます。

task_end関数は、自分のアクティブフラグを落として次のタスクを実行する関数です。アクティブでなくなることでschedule関数で実行する条件から外れ、タスクが実行されなくなります。

task_start関数は、登録された関数を呼び出した後task_endを呼び出す関数です。main1からmain3の関数のおわりでtask_endを記述する必要がないのはこの関数が挟まれているためです。

task_create関数は、自分を再帰呼び出ししながらタスクを生成していき、すべてのタスクを生成し終えるとschedule関数を呼び出してタスクの実行を始める関数です。タスクの実行が始まるとまずこの関数でsetjmpした場所に来てtask_start関数を呼び出すことで各タスクのmain関数に移るわけですが、ここで引数として渡しているnの値に注意する必要があります。コードをなんとなく眺めているとnは0,1,2が渡されるのではないかと勘違いしてしまいがちですが、実際にはsetjmpで状態を保存するタイミングではなくlongjmpで戻ってきた時の値になるため、すべてのタスクに対してTASKNUM(==3)が渡されます。

別の解法

問題のコードは空欄を埋めればコンパイルして実行することができるので、2つのバグに気付かなくても正しい答えを導くことができます。というか、後で聞いたところによると問題の意図としてはそちらが正しくて、バグはコードを適当に読んで答えを出せないようにするためのものだったようです。

元ネタ

この問題の元ネタはこちらだそうです。OSを作るのにあたって、OSが実現しているタスク切換えがどのように動作するかをユーザーランドのアプリケーション上で、かつ環境に依存するAPIなしで試すことができる方法としてsetjmp/longjmpを利用する方法が有効なのではないか、とのことでした。

また、今回の問題ではタスクが自らタスク切換えを行うノンプリエンプティブな動作になっていますが、元ネタではsignalを利用することでプリエンプティブな動作を実現しています。

おわりに

OSのタスク切換えと言われるとなかなか縁がなさそうに聞こえてしまいますが、この手法は意外と多くの場所で利用されています。

例えばRuby 1.8系のスレッドの実装は、Rubyのコードレベルではプリエンプティブな動作になっているように見えますが、処理系の実装レベルではsetjmp/longjmpを使ったノンプリエンプティブな動作をしています。

また、ノンプリエンプティブなタスク切換えがコルーチン(coroutine)やファイバ(fiber)などの名称で提供されている環境も多くあります。これらを利用することで、1つ1つのタスクの流れを自然に記述でき、状態変数の少ないコードを書くことができるようになります。

といったように、タスク切換えは普段のプログラミングにおいてもなかなか便利に使えるのではないかと思います。ぜひ活用してみてください。