概要

スレッドといえば，pthreadなど，言語やライブラリが提供しているものを使うのが定石だが，自作できるかもしれないことを発見したので実際にやってみた，という話．ここで作るスレッドは，１つのプロセスで実行される．現実的なソフトウェア開発で利用しないけれど，例えば組み込みシステムでスレッドを実装するとか，ある程度までPCで動作を確認したいときとかには使えるかもしれない．

環境

OS: MacOSX 10.12.6
アセンブリ言語: nasm 2.14.02(home brewでインストール)

[以前の記事](https://qiita.com/hiro4669/items/348ba278aa31aa58fa95)は，実はこの実装のための実験だった．

完成イメージ

main.c

void secondt() {
    printf("Second Thread\n");    
    int count = 0;
    for (int i = 0; i < 3; ++i, ++count) {
        printf("second [%d]\n", i);
        thwait();
    }
    printf("total count in second = %d\n", count);
    thwait();
}

void mainthread() {
    printf("Main Thread Run\n");

    create_thread(secondt, 1);
    thwait();
    int count = 0;
    for (int i = 0; i < 3; ++i, ++count) {
        printf("main   [%d]\n", i);
        thwait();
    }
    printf("total count in second = %d\n", count);
    printf("Main Thread Rung\n");     
    exit(1);
}

int main(void) {    
    current = NULL;
    tid = 0;
    create_mainthread(mainthread);
    thrun();
    printf("end of main\n");

    return 0;
}

このようなソースコードを書いたとき，以下のような結果になることが目標

Main Thread Run - (1)
Second Thread   - (2)
second [0]      - (3)
main   [0]
second [1]
main   [1]
second [2]
main   [2]
total count in second = 3
total count in second = 3
Main Thread Rung -(4)

この結果は，まず(1)メインスレッドの実行し，その中でセカンドスレッドを作って切り替える．そして(2)スレッドが切り替わってセカンドスレッドが実行，その後メインとセカンドスレッドが交互に切り替わって実行され，(4)最後にメインスレッドに戻って処理を終える．
ここで，スレッドの実行はthrun(), スレッドの切り替えはthwait()で行っている．

コンテキスト

スレッドを実装するには，コンテキストという概念を知らなければならない．コンテキストとは，プログラムが実行されている時の状態を指す(と思っている)．プログラムの実行状態とは，プログラムがどこまで実行されたか，とか，変数の値はどうなっているか，とかだと考えれば良いと思う．これらの値は，メモリかレジスタに格納されており，メモリにアクセスするにもレジスタが使われるので，レジスタの値を全部保存すれば，コンテキストを保存できたことになる．そして，スレッドを切り替える，とは，このコンテキストを切り替えることだと考えて良いと思う．

また，プログラム実行中は計算にスタックが使われる．スタックの説明は割愛するとして，別々のスレッドがスタックを共有したらとんでもないことになってしまう．そのため，1つのスレッドには専用のスタックを用意しなければならない．

というわけで，スレッドのコンテキストを保存するには，

レジスタを保存しておくこと
スタックを分離しておくこと

が必要である．そこで，スレッドごとにこれらを保持する構造体を定義する．

スレッド構造体

qthread.h

#ifndef _QTHREAD_H_
#define _QTHREAD_H_
#include <stdint.h>

typedef void (*tfunc)();

typedef struct _q_thread {
    uint64_t ctx[18];  // レジスタの値を保存する
    char* stack;       // スタック
    tfunc f;           // スレッドが実行する関数
    uint32_t tid;      // とりあえず定義したが使ってない
} q_thread;

q_thread threads[2]; // スレッドのための構造体

void create_thread(tfunc f, int idx);
void create_mainthread(tfunc mainf);

q_thread *current; // 現在実行中のスレッドコンテキストを保持する
int tid;           // 現在実行中のスレッド番号(とはいえ，現状は配列のインデックス)
#endif

スレッド構造体(q_thread)の中身はコメントの通りだが少し補足．今回は，X86-64を対象とするので，各レジスタは64ビットとなる．そのため，uint64_tを使っている．また，X86-64はX86からのレジスタ8個の他に，R8-R15まで追加され，かつフラグレジスタも保存しておいたほうが良いと思うので，8+8+1 = 17個．なんとなく切りが悪いので，18にしておいた．
また，スレッドが実行する関数も，とりあえず引数なし，返り値なし，とした．

スレッドの生成

スレッドの生成は，create_thread, create_mainthreadで行う．

qthread.c

void create_mainthread(tfunc mainf) {    
    create_thread(mainf, 0);
    current = &threads[0];
}

create_mainthreadは，内部でcreate_threadを呼び出し，currentにthreads[0]を設定しているだけ．

qthread.c

void create_thread(tfunc f, int idx) {
    char* sp;   
    threads[idx].f = f;                                (1)
    memset(threads[0].ctx, 0, sizeof(uint64_t) * 18);  (2)
    threads[idx].stack = malloc(0x8000);               (3)
    memset(threads[idx].stack, 0, 0x8000);             (4)
    sp = threads[idx].stack + 0x8000 - 0x100;          (5)
    ((uint64_t*)sp)[0] = (uint64_t)threads[idx].f;     (6)※
    threads[idx].ctx[0] = (uint64_t)sp;                (7)※※
}

create_threadでは，スレッドのコンテキストを保持するための初期設定を行う．
(1)
q_thread構造体のfに，スレッドで最初に実行する関数のアドレスを設定する．
(2)
レジスタを保持するためのctxを0で初期化する
(3)
スタックのための領域をヒープに確保する
(4)
獲得したヒープ領域を0で初期化する
(5)
スレッドが使うスタックポインタを初期化する．この例では，スタック領域として0x8000だけ確保しており，スタックにpushされるとスタックポインタはマイナスされていくので，初期値をずらす必要がある．0x8000ずらしたあとに，更に-0x100しているのは，スレッドが終了したときに後処理する関数のためと(いつか書く予定)，こうしないとMacOSが16バイトアライメントエラーを出すため．このエラーに関しては現時点ではよくわからない．
(6)
スタックポインタが指す領域に，スレッドが最初に実行すべき関数のアドレスを代入する．これにより，スタックポインタが指している位置に，関数のアドレスが設定される．ここは重要なところで，普通関数を呼び出すときにはf()のようにして実行するが，後述するように，スレッドを切り替えるときにはこの方法は使えない．なぜなら，f()のような呼び出し方では，常に関数の先頭から実行してしまうからである．中断した処理の途中から実行するには，現在実行中のプログラムカウンタの値を保持しておく必要がある．そして，それにはX86の仕組みを使わなければできない．そのため，ここでアドレスを設定するのは，関数を登録するというよりも，初めて実行するスレッドの最初に飛んでいくプログラムカウンタの値を設定する，と捉えるほうが正しい．

(7)
スタックポインタの値をctx[0]に設定する．つまり，ctxはレジスタの値を保存するものだが，その0番目にスタックポインタの値を保持することにする．

###スレッドの実行
スレッドは，まずmainthreadから実行される．これは，current=&threads[0]によって，currentに0番目のq_threadが設定されるためである．そして，実際に実行するのはthrunだが，この関数自身はnasmで書いている．

ctx.asm

extern _current // currentを見えるようにする

GLOBAL _thrun  // グローバルからthrunを呼べるようにする

SECTION .text
_thrun:
    mov rax, _current ; _currentのアドレスがraxに入る. _currentとthread[0]のアドレスは別物である！
    mov rax, [rax]    ; thread[0]のアドレスがraxに入る
    mov rsp, [rax]    ; thread[0].ctx[0]がrspに入る
    ret

各行の説明は，コメントの通りだが，この関数の目的はrspにスタックポインタの値を設定することにある．X86では，retを実行すると，スタックの先頭(スタックポインタが指しているメモリ)の中身のアドレスにプログラムカウンタを設定する．そのため，スレッドを作るとき，関数の先頭アドレスをスタックポインタが指すメモリにコピーしておいた．そして，その状態でret命令を実行することで，メインスレッドが最初に実行する関数にジャンプする．

スレッドの切り替え(コンテキストスイッチ)

スレッドの実行が理解できれば，コンテキストスイッチのやり方は想像つく．つまり

現在のコンテキスト(current)を保存する
次に実行したいq_thread構造体を選択し，currentに設定する
currentから，レジスタの情報を復元する

をすればよい．これを実行するのが，以下に示す`thwaitである

ctx.asm

extern _current
extern _dispatch

GLOBAL _thwait

SECTION .text
; context switch
_thwait:
    push rax
    pushfq
    mov rax, _current
    mov rax, [rax]
    add rsp, 16
    mov [rax], rsp         ;save sp
    mov [rax +   8], rbp   ;save bp
    mov [rax +  16], rdi
    mov [rax +  24], rsi
    mov [rax +  32], rdx
    mov [rax +  40], rcx
    mov [rax +  48], rbx   ;rbxを保存．以降，rbxは自由に使える
    mov rbx, [rsp - 16]
    mov [rax +  56], rbx   ;save rax
    mov rbx, [rsp - 8]     
    mov [rax +  64], rbx   ;save flagq
    mov [rax +  72], r8
    mov [rax +  80], r9
    mov [rax +  88], r10
    mov [rax +  96], r11
    mov [rax + 104], r12
    mov [rax + 112], r13
    mov [rax + 120], r14
    mov [rax + 128], r15
    call _dispatch
    mov rax, _current
    mov rax, [rax]
    mov rsp, [rax]      ; raxにspが入るはず
    mov rbx, [rax + 64] ; flagqをrbxに代入
    push rbx            ; スタックに積む
    mov rbx, [rax + 56] ; raxをrbxに代入
    push rbx            ; スタックに積む
    add rsp, 16         ; spを戻す
    mov rbp, [rax +   8]
    mov rdi, [rax +  16]
    mov rsi, [rax +  24]
    mov rdx, [rax +  32]
    mov rcx, [rax +  40]
    mov rbx, [rax +  48]
    mov r8,  [rax +  72]
    mov r9,  [rax +  80]
    mov r10, [rax +  88]
    mov r11, [rax +  96]
    mov r12, [rax + 104]
    mov r13, [rax + 112]
    mov r14, [rax + 120]
    mov r15, [rax + 128]
    mov rax, [rsp - 16] ; raxを復元
    sub rsp, 8          ; flagqを復元
    popfq
    ret

(2)の処理をするのがcall _dispatchで，これ以前が(1)の処理，これ以降が(3)の処理である．やっていることは，レジスタの保存，dispatchの実行，レジスタの復元なので，詳しくはコメントとスタックの様子を想像して下さい．1つ重要な点は，この関数を呼ぶのは現在のスレッドで，この関数が呼ばれると，スタックの先頭にこの関数の呼び出し後のアドレスがこそっと積まれていることである．つまり，このスタックポインタを保存しておけば，必然的に再びこのスレッドに戻った時のプログラムカウンタの値を得ることができる，ということである．なお，プログラムカウンタの値はmovなどで設定することはできない．また，フラグレジスタも取り出せないので，flagqを使ってスタックに積んだあと，その値をコピーするようにしている．

スレッドの選択

スレッドの選択(スケジューリング)をするのはdispatchである．現在の実装は単なるラウンドロビン

qthread.c

void dispatch() {
    if (tid == 0) {
        tid = 1;
        current = &threads[tid];
    } else if (tid == 1) {
        tid = 0;
        current = &threads[tid];
    }
}

むちゃくちゃダサいけど，動きはする．本来は，リスト構造などにして，切り替える必要があるが，今回は固定で2スレッドなのでこれでまあよい．

ここまでの実装は，以下のコマンドで確認できる(要MacOSX and x86-64)

>git clone https://github.com/hiro4669/qthread.git
>cd qthread
>git branch ver1 origin/ver1
>git checkout ver1
>make
>./hbs 
Main Thread Run
Second Thread
second [0]
main   [0]
second [1]
main   [1]
second [2]
main   [2]
total count in second = 3
total count in second = 3
Main Thread Rung

nasmのコンパイルオプションを変更すれば，X86-64なら動くと思います．．(未確認)

その２に続く

P.S　16バイトアライメントエラー，本質的にはどうやって解決したらよいか，ご教授いただけると幸いです．．