Counting 1 bits.

Go 標準ライブラリの中に符号なし整数をビット列と見たとき、 1 のビットを数える関数がある。この実装がなかなか膝打ちのアイデアで面白い。なおここで紹介するアイデアは "Hacker's Delight" 第5章に詳しく書かれている。

以下の 16 bit の数を考える。

f:id:toasa3:20210113222239p:plain

1 の数は 8 個ある。 数え上げのナイーブな実装として、 16 回ループを回し 1 のビットを見つけたらカウンタをインクリメントすることを思いつく。 これだと計算量は O(n)となる。 しかし、分割統治法を使うことで O(log(n)) にすることができる。すごい。

分割統治法

肝となる考えは「大きな問題を部分的な問題へ分割し、部分問題の結果をもとに大きな問題を解決する」ということだ。 16 個のビットを一度に計算するのではなく、より小さいビット幅で計算することを考える。

再び例にもどる。

f:id:toasa3:20210113222239p:plain

はじめに 2 ビット幅ずつ見てみよう。 見やすいよう下図のように 7 個の仕切りを追加する。

f:id:toasa3:20210114093900p:plain

仕切りにより 8 個の 2 ビットのペアが出来た。 仕切られた空間をここでは 部屋 と呼ぶことにする。つまり上図では 8 個の 2 ビット幅の部屋がある。

次に各部屋ごとにビットの数を計算しよう。各部屋の計算結果を 2 進数で格納すると下図になる。

f:id:toasa3:20210114093905p:plain
(左から 1、2、3 つ目の部屋にはそれぞれ 1 個、0 個、2 個の 1 があることを表す)

同様に 4 ビット幅、8 ビット幅、16 ビット幅と、ビット幅を倍にして 1 の個数を求め続ける。これらの操作により下図のようになる。

f:id:toasa3:20210114093912p:plain

最後部屋を見ると求めたかった 1 の個数 0b1000、つまり 8 が得られた。

実装

例えば 2つの 2 ビット幅の部屋から、4 ビット幅の部屋を求めることを考える。 これは左の部屋を右に 2 ビットシフトし右の部屋の値と足し合わせれば良い。

f:id:toasa3:20210114203243p:plain

実装上の注意として、不要な値を無視するために 00110011 ... のビットマスクを使用する。

以下のコードはGo標準ライブラリにある、64ビットの符号なし整数の 1 の数を数える関数 OnesCount64 である。 (一部簡略化した形で引用した。)

const m0 = 0x5555555555555555 // 01010101 ...
const m1 = 0x3333333333333333 // 00110011 ...
const m2 = 0x0f0f0f0f0f0f0f0f // 00001111 ...

func OnesCount64(x uint64) int {
    x = x>>1&m0 + x&m0
    x = x>>2&m1 + x&m1
    x = (x>>4 + x) & m2
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return int(x) & (1<<7 - 1)
}

ここまでくれば関数の各行から、ビットの幅を倍にして部屋の値を求めている操作が想像できるだろう。 なお標準ライブラリのコードでは 8 ビットシフトからマスクを取らない。 これは uint64 の 1 の数は高々 64 = 26 個 であり、最終行の 1<<7-1 のマスクで 7 ビット目以降は無視できるからである。

参考資料

++i is better than i++ in C++?

タイトルの答えは条件付きの Yes。その条件は「インクリメントする式の値を無視する場合」というもの。

たとえば次のように単にiをインクリメントしたい場合++iと書くほうが良い。

int i = 0;
while (true) {
    // use i
    i++;
}

何故「良い」のかはGoogleのC++スタイルガイドに書かれている。 要約するとi++の場合iのコピーをつくる必要があり*1、その必要がない++iと比べ*2メモリがお得だからという理由。

さらにC++の場合オペレータのオーバーロードができる。そのため i が整数でない場合、より両者の性能差が広がる可能性がある。ガイドの次の文はおそらくこのことを述べている。

If i is an iterator or other non-scalar type, copying i could be expensive.

それでは Proof Of Concept として次の実験をしてみよう。

実験

前置++と後置++オーバーロードしたクラスを用意し、両者の性能差を計測する。

クラス

クラス 説明
HugeClass 実験対象のクラス
Timer 実行時間の計測用クラス

なお今回のTimerの実装はC++でフリープラットフォームな時間計測を参考にした。

コード

#include <iostream>
#include <chrono>

using namespace std;

class HugeClass {
public:
    // prefix increment
    HugeClass& operator ++() {
        for (int &num : this->nums) {
            ++num;
        }
        return *this;  
    }

    // postfix increment
    HugeClass operator ++(int) {
        HugeClass ret = *this;
        for (int &num : this->nums) {
            num++;
        }
        return ret;
    }

private:
    int nums[100000];
};

class Timer {
private:
    chrono::system_clock::time_point startTime;
    chrono::system_clock::time_point endTime;
public:
    void start(){ this->startTime = chrono::system_clock::now();};
    void end(){ this->endTime = chrono::system_clock::now();};
    chrono::microseconds diff(){ 
        return chrono::duration_cast<chrono::microseconds>(
            this->endTime - this->startTime
        );
    };
};


int main() {
    int REPEAT_NUMBER = 10000;

    // post increment
    HugeClass hc_post = HugeClass();
    Timer t_post = Timer();
    t_post.start();
    for (int i = 0; i < REPEAT_NUMBER; i++) {
        hc_post++;
    }
    t_post.end();
    
    // pre increment
    HugeClass hc_pre = HugeClass();
    Timer t_pre = Timer();
    t_pre.start();
    for (int i = 0; i < REPEAT_NUMBER; i++) {
        ++hc_pre;
    }
    t_pre.end();


    cout << "post inc: " << t_post.diff().count() << " " << endl;
    cout << "pre  inc: " << t_pre.diff().count() << " ticks" << endl;
}

結果

wandbox上で試した結果、期待通り後置インクリメントが遅かった。

post inc: 3606617 ticks
pre  inc: 3338294 ticks

今回はインクリメントに話題を限定したが、デクリメントも同様の議論がなりたつ。

参考資料

*1:i++ の実装は i のコピーをつくり、コピー元をインクリメントした上ででコピーを返す

*2:++i の実装は i の値をインクリメントにより書き換え、それを返す

Zen言語で作るRISC-Vエミュレータ、その1

Zen言語とは今注目の言語です。 そしてRISC-Vとは今注目の命令セットです。 (多分に個人的感想ですが)どちらも聞かない日はありません。

そんな両者の接点ともいえるエミュレータを開発します。現時点で実装している命令は5種類のみですが、 第一目標のフィボナッチ数列が計算できるようになりました。

開発環境

公式サイトのダウンロードページよりコンパイラのバイナリをダウンロード出来ます。

バージョンは次のコマンドにより確認できます。

$ zen version
0.8.20191124+552247019

注意

  • ここに登場する命令はすべてRV32Iと呼ばれる基本命令セットです。

リポジトリ

RISC-Vの5とZenをあわせ、「5zen」と名付けました。

github.com

現在の完成度

フィボナッチ数列の計算を最初の目標とし、それを達成した時点での記事のため、出来は非常にミニマルです。 RV32I命令セットの全47命令のなかで以下の5命令にしか実装していません。

  • add
  • addi
  • blt
  • jal
  • jalr

以下は第10項目のフィボナッチ数を求める、C言語コードとRISC-Vアセンブリ言語です。 実際に5zenではユニットテスト により計算結果を確かめています。

int main() {
    int lhs = 1;
    int rhs = 1;
    int result = 0;
    // 第1, 2項目は計算済とし、第3項から数え上げる
    int counter = 3;
    while (counter <= 10) {
        result = lhs + rhs;
        lhs = rhs;
        rhs = result;
        counter++;
    }

    // result == 55
}
## t0: lhs
## t1: rhs
## t2: result
## t3: counter
addi t0, t0, 1
addi t1, t1, 1
addi t3, t3, 3
addi t4, t4, 10

## if (t3 < t4) { jump to `ret`}
blt t4, t3, 24
add t2, t0, t1
add t0, t1, zero
add t1, t2, zero
addi t3, t3, 1

## unconditional jump to `blt t4, t3, 24`
jal zero, -20
ret

一年前の私へ

タイトルとここまでを一読しても、一年前の私にはほとんどピンと来ず、わからなかったでしょう。 そんな過去の自分に向けた章です。もし役立つ方がいれば幸甚です。

RISC-Vとは命令セットの一種です。 「セット」には集まりという意味があり、命令セットとは(ラフにいうと)命令の集まりです。 そしてこの「命令」とは、コンピュータの根幹部品であるCPUに対し、特定の動作を定めるものです。 例えばRISC-Vにはaddi命令があります。これは次のように、3つのオペランドと合わせて1つの命令を構成します。

addi rd, rs, imm

具体的にはaddi x5, x6, 1などと書き、これは「x6レジスタの値に即値1を足し、結果をx5レジスタに格納する」 という命令として実行されます。

命令にはその命令を実行できるCPUが必要です。 例えば、SiFive社が開発したHiFive1RISC-Vプロセッサが搭載されたボードです。

これは物理的なCPUですが、その動作を模倣するようなソフトウェアをエミュレータと呼びます。

そして今回は 「Zen言語を用いて、RISC-V命令を実行できるCPUエミュレータとして実装しました」 ということを紹介するブログポストです。

方針は決まりました。では一歩目は何をすれば良いのでしょう。 その答えは、CPUの具体的な動作を知ることで見えてきます。

CPUの動作

CPUは「フェッチ」、「デコード」、「実行」と呼ばれる3種類の動作を行います。

動作 解説
フェッチ 実行する命令をメモリからロードする
デコード フェッチした命令が命令セットのどの命令にあたるか解釈する
実行 デコードした命令を実行する

それぞれが一度きりの動作ではなく、 フェッチ、デコード、実行、フェッチ、デコード、実行、フェッチ・・・ とループされます。このループをCPUの実行サイクルと呼びます。

3つの動作例として、前章に挙げたaddi x5, x6, 1のフェッチから実行までを見てみましょう。

フェッチ例

命令はすべてメモリ内に機械語として格納されています。

f:id:toasa3:20200229220051p:plain
メモリ内のaddi命令

フェッチでは現在のPC(プログラムカウンタ)が指す命令をメモリからロードします。

デコード例

フェッチにより、実行すべき命令の機械語00000000000100110000001010010011を取得できました。 デコードではこのビット列が何命令であるか、そのオペランドは何かを解釈します。

このままでは見ずらいため、これを意味のあるビット列に分割すると次のようになります。

000000000001 00110 000 00101 0010011

ここで公式ドキュメントにある次の図を引用します。

f:id:toasa3:20200229221925p:plain
addi命令

ビット列と図を見比べてみてください。フェッチしたビット列がaddi x5, x6, 1命令であることがわかります。*1

実行例

デコードによりaddi x5, x6, 1という命令だとわかりました。 あとは「x6レジスタの値に即値1を足し、結果をx5レジスタに格納する」ことを行い、プログラムカウンタの値をインクリメントし次の命令をフェッチできるようにします。

CPUの実装

5zenではフェッチ、デコード、実行の三動作をCPU構造体のメソッドとしてそれぞれ次のように実装しています。

pub const CPU = struct {
    ...

    pub fn fetch(self: *Self) PROG_TYPE {
    ...
    }

    pub fn decode(self: *Self, inst_bytes: PROG_TYPE) InstructionSet {
    ...
    }

    pub fn execute(self: *Self, inst: InstructionSet) void {
    ...
    }
}

エミュレータの実装

5zenではEmulator構造体のrunメソッドにCPU実行サイクルを実装しました。 RISC-Vにはサイクルを止めるhalt命令に相当する命令が存在しません。 そのため現在はret命令を実行後、サイクルループを脱出しています。これはMOIZこちらの記事*2を参考にしました。

pub const Emulator = struct {
    const Self = @This();
    cpu: CPU,

    ...

    pub fn run(self: *Self) void {
        // Stop the CPU cycle loop when pc equals `RET_ADDR`.
        while (self.cpu.pc != RET_ADDR) {
            const inst_bytes = self.cpu.fetch();
            const inst = self.cpu.decode(inst_bytes);
            self.cpu.execute(inst);
        }
    }
};

Zen言語のメリット

今回の開発では、Zenで提供されるタグ付き共用体というデータ構造の有用性を実感しました。これはHaskellでは代数的データ型、Rustでは列挙型に相当するものです。

タグ付き共用体はあらかじめ取りうる選択肢がタグにより定められており、そのどれか1つを(紐づくヴァリアントを用いて)実行するような処理を書きたいときに便利です。 そしてこの特徴はエミュレータの実装において、命令セットからどれか1つの命令を実行したいという動機とマッチします。

実際RISC-Vの命令セットをタグ付き共用体で次のように実装しました。

pub const InstructionSet = union(Opcode) {
    Add: AddInst,
    Addi: AddiInst,
    Blt: BltInst,
    Jal: JalInst,
    Jalr: JalrInst,
}

ここでOpcode列挙型として次のように定義することで、実装する命令にタグを付けます。

pub const Opcode = enum {
    Add,
    Addi,
    Blt,
    Jal,
    Jalr,
};

そして5zenexecuteメソッドでは、switch文により各命令を分岐して、それぞれの動作を実行します。

    pub fn execute(self: *Self, inst: InstructionSet) void {
        switch(inst) {
            .Add => |add| {
                ...
            },
            .Addi => |addi| {
                ...
            },
            .Blt => |blt| {
                ...
            },
            .Jal => |jal| {
                ...
            },
            .Jalr => |jalr| {
                ...
            }
        }
    }

このとき分岐をもれなくカバーしないとコンパイルエラーとしてくれます。そしてこの機能が開発に役立ちます。 5zenでは実装する命令を1つづつ追加する、インクリメンタルな開発を行います。 そのときこの機能のおかげで、「Opcodeには新命令をタグとして追加したが、execute内の実装を忘れてしまった」というミスをコンパイル時に発見してくれます。 (実際にAddi命令がある状態で、Add命令を実装しようとしたとき、コンパイラが分岐の網羅漏れを発見してくれました。)

今回はインクリメンタルな開発を目指し、1つづつ対応する命令を増やして行きました。 Zen言語ではソースコード内にユニットテストをかける、コンパイラによるタグ付き共用体の網羅性チェックなど、 インクリメンタルな開発と相性が良いようです。 このあたりはZenの思想に通じており公式サイトではと紹介されています。

さいごに

RV32I命令だけ見ても全47命令中5命令しか実装できておらず、割合では完成は程遠く感じます。ただインクリメンタルな開発のおかげで命令を増やす心理的な負荷はあまり感じません。いずれにせよなかなか楽しい趣味になりそうなので、空いた時間に開発を続けようと思います。

参考

サイト

書籍

*1:RV32Iの命令は6つの基本形式に分類され、addi 命令は I 形式に属します。実際のデコードでは0から6bit目までで表されるオペコードにより形式が確定し、funct と呼ばれるオペランドの値により RV32I としての命令が一意に定まります。

*2:http://uzusayuu.hatenadiary.jp/entry/2019/09/03/095235

xv6 initプロセス ことはじめ

あるプロセスには親プロセスという生みの親がいます。その親にも親がいます。 そして、プロセスの系譜をさかのぼり続けると一つのプロセスに行き着きます。 それはinitプロセス。Unix及びUnix系のOSではこの名前がついています。*1

またタイトルにあるxv6とは、2006年MITで開発された教育用OSです*2ANSI Cで書かれておりソースコードリーディングに適しています。

今回はあらゆるプロセスの祖先といえるinitプロセスの生成と実行はじめまでを、xv6ソースコードを読み、観察してみましょう。(同じ内容のスライドがあります。こちらはブログと比べスタックの動的な操作がわかりやすいです。)

あらすじ

  • xv6のプロセス
  • initプロセスの生成
  • スケジューラがinitプロセスを選択
  • スケジューラからinitへのコンテキストスイッチ
  • initの実行

注意

  • initプロセスに話をしぼるため、ブートローダーやカーネルの設定や初期化は完了済とします。
  • 掲載するソースコードのなかで今回の話に不要と思われる記述は修正や省略をしました。例えばxv6マルチプロセッサに対応しており、排他制御を行うコードも存在します。しかし私の理解不足と紙面の都合上意図的に省略しました。
  • 以下に登場するメモリ領域の図は上が high アドレスとなっており、スタックは下に積まれます。

xv6のプロセス

早速initプロセスの生成を見ていきたいところですが、その前にxv6ではプロセスをどのように実装しているのでしょう。 それはproc.hproc構造体として定義されています。

struct proc {
    pde_t* pgdir;          
    char *kstack;          
    enum procstate state;  
    int pid;                 
    struct proc *parent;     
    struct trapframe *tf;
    struct context *context;
};

*3

フィールド 説明
pgdir 仮想メモリと物理メモリのマッピングを定める
kstack tfcontextを格納する領域
state プロセスの状態を表す。proc.henum型として定義される
pid プロセスに割り振られる一意な整数値
parent 親プロセス
tf トラップの発生時に使用される。今回はinitプロセスの実行に必要なレジスタを格納する
context コンテキストスイッチ時にレジスタを格納する、または復元するために使用される

initもプロセスであるため、その生成はproc構造体のインスタンスとして定義されます。 Cの構造体は各メンバが連続したメモリに配置されます。 つまりinitの生成は以下のようなメモリ領域を作成することと同じです。

f:id:toasa3:20200218184635p:plain
proc構造体のメモリレイアウト

initプロセスの生成

この節では上に挙げたメモリ領域をinitのために作成することが目標です。

すでにカーネルの設定は終わっているためmain関数の中で今回の話と関係のある関数はuserinitmpmainの2つです。

int main(void) {
    \\ カーネル、割り込みの設定のため略
    userinit();
    mpmain();
}

userinit

userinitは次の4つの仕事を行います。

  1. initプロセスの生成
  2. initのカーネル空間のpagingの設定
  3. initのプログラムをメモリに展開
  4. トラップフレームの設定

そのうち上3つを以下の関数がuserinit内で呼ばれることで、それぞれ請け負います。

  1. allocproc
  2. setupkvm
  3. inituvm

次のコードはuserinitの前半部分です。早速allocprocが呼ばれていることがわかります。

void userinit(void) {
    struct proc *p;

    p = allocproc();

    if((p->pgdir = setupkvm()) == 0)
        panic("userinit: out of memory?");

    inituvm(p->pgdir, _binary_initcode_start, (int)_binary_initcode_size);
    .....   
}

allocproc

allocprocの主な仕事は次の3つです。

  • UNUSEDなプロセスをテーブルから探す
  • そのプロセスの設定
    • pid, state, trapframe, etc…
  • 設定したプロセスを返す

なおallocprocは1つのプロセスを生成するので、userinitからだけではなくforkからも呼び出されます。

まずプロセステーブルの中からUNUSEDなプロセスを探す処理が次のコードです。

static struct proc* allocproc(void) {
   struct proc *p;

   for (p = ptable.proc; p < &ptable.proc[NPROC]; p++)
       if (p->state == UNUSED)
           goto found;
   return 0;

found:
   ... 

}

プロセステーブルptableproc.cグローバル変数として定義されており、64個のプロセスエントリを格納します。 コードではプロセステーブルの先頭から最後まで見て、UNUSEDなプロセスを見つけた場合foundラベルへと飛びます。

foundラベル以降は次のようなコードです。

found:
    p->state = EMBRYO;
    p->pid = nextpid++;

    // Allocate kernel stack.
    if ((p->kstack = kalloc()) == 0){
        p->state = UNUSED;
        return 0;
    }
    .....

UNUSEDなプロセスが見つかったためその初期化を行います。まずstateEMBRYOにしています。 EMBRYOは「生まれたて」という意味があります。またpidの割り当てを行い、グローバル変数であるnextpidをインクリメントします。これにより次回のallocproc呼び出しではプラス1された整数値がpidとして割り当てられます。

次にkallocを呼び出しpカーネルスタックを割り当てます。これにより1ページ(4096バイト)分のメモリ領域がカーネルスタックの領域として確保されました。この領域はトラップフレームやコンテキストを格納するためにあります。ここまでの処理により次のようなメモリ領域の図になります。

f:id:toasa3:20200218210804p:plain
kalloc直後

カーネルスタックの設定

次に確保したカーネルスタック領域を複数の部分領域へ区切ります。後の処理によりそこにトラップフレームやコンテキストを格納できるようにします。

具体的なコードは次のようなものです。

   sp = p->kstack + KSTACKSIZE;

   // Leave room for trap frame.
   sp -= sizeof *p->tf;
   p->tf = (struct trapframe*)sp;
   .....

まずspカーネルスタックの最上部を指すようにします。そしてsizeof *p->tf;によりspをトラップフレームのメモリ領域分を押し下げ、そのアドレスをp->tfに代入しています。

f:id:toasa3:20200218213057p:plain

   sp -= 4;
   *(uint*)sp = (uint)trapret;

    sp -= sizeof *p->context;
    p->context = (struct context*)sp;
    memset(p->context, 0, sizeof *p->context);
    p->context->eip = (uint)forkret;

    return p;

同様にまずspを4バイト下げ、関数trapretの関数ポインタを格納します。 さらにspをコンテキスト分下げ、eipの領域に関数forkretを格納します。 関数trapretforkretコンテキストスイッチが起こり、スケジューラからプロセスへ制御が渡された後すぐに実行されます。

最後にpをリターンして関数を抜けます。ここまでの処理によりinitは次のようなメモリ領域を構築できました。

f:id:toasa3:20200218215358p:plain
allocproc脱出時

userinit

再びuserinitに処理が戻ってきました。次は以下の3行です。

   if((p->pgdir = setupkvm()) == 0)
       panic("userinit: out of memory?");
   inituvm(p->pgdir, _binary_initcode_start, _binary_initcode_size);

まずsetupkvmによりinit用のページテーブルを設定します。ページテーブルにより仮想アドレスと物理アドレスマッピングが設定されます。inituvmはこのマッピングにもとづいて仮想アドレスの0番地にinit用のプログラムinitcodeを展開します。

f:id:toasa3:20200218220047p:plain
initcode用のメモリ確保&展開

次にinitのトラップフレームの設定を行います。

    p->tf->cs = (SEG_UCODE << 3) | DPL_USER;
    p->tf->ds = (SEG_UDATA << 3) | DPL_USER;
    p->tf->es = p->tf->ds;
    p->tf->ss = p->tf->ds;
    p->tf->eflags = FL_IF;
    p->tf->esp = PGSIZE;
    p->tf->eip = 0;  // beginning of initcode.S

コメントにもある通りp->tf->eip = 0;initcodeが格納されている0番地をeipが来るようにしています。eipx86アーキテクチャの32bit版命令ポインタで、実行する次のアドレスを格納します。今p->tf->eipが0となっているため、コンテキストスイッチ後に0番地から実行できるよう下準備をしました。

userinitの最後はpの状態をRUNNABLEにして関数を抜けます。

    p->state = RUNNABLE;

これまで作成したinitのメモリは次のようになります。

f:id:toasa3:20200218224149p:plain

スケジューラがinitプロセスを選択

xv6のスケジューラはシンプルに実装されています。プロセステーブルを先頭から調べstateRUNNABLEなプロセスをみつけたらそのプロセスへとコンテキストスイッチします。

以下がスケジューラのコードの一部です。for文が入れ子になっており、外側のループは無限ループになっています。

void scheduler(void) {
    struct proc *p;
    struct cpu *c = mycpu();
    c->proc = 0;
    
    for(;;) {
        
        ...
        for (p = ptable.proc; p < &ptable.proc[NPROC]; p++) {
            if (p->state != RUNNABLE)
                continue;

            c->proc = p;
            
            switchuvm(p);
            p->state = RUNNING;

            swtch(&(c->scheduler), p->context);

            ...
        }

    }
}

RUNNABLEなプロセスを見つけると、まずswitchuvm(p);が呼ばれます。今RUNNABLEなプロセスはinitしかいません。 そのためswtchuvmではinitのページング設定をcr3レジスタにロードし、スケジューラのアドレス空間からinitプロセスのアドレス空間へ切り替えます。

次にinitRUNNNIG状態にします。そしてようやくswtch関数によるコンテキストスイッチです。 swtchの第一引数と第二引数には、それぞれ古いコンテキスト(のアドレス、理由は後述)と新しいコンテキストを指定します。 今swtch(&(c->scheduler), p->context);であるためスケジューラからinitプロセスへとコンテキストスイッチすることがわかります。

スケジューラからinitへのコンテキストスイッチ

swtch

関数swtchswtch.Sアセンブリで書かれています。

.glonl swtch
swtch:
    # load `old`
    movl 4(%esp), %eax
    # load `new`
    movl 8(%esp), %edx

    # Save old callee-saved registers
    pushl %ebp
    pushl %ebx
    pushl %esi
    pushl %edi

    # Switch stacks
    movl %esp, (%eax)
    movl %edx, %esp

    # Load new callee-saved registers
    popl %edi
    popl %esi
    popl %ebx
    popl %ebp
    ret

swtch呼び出し直後はスケジューラのカーネルスタックに、第二引数p-context, 第一引数&(c->scheduler), swtchの戻り先のアドレスの順に積みます。

f:id:toasa3:20200218231922p:plain

まず先頭2行のアセンブリeaxedxに、それぞれスイッチ先のプロセスのコンテキストとスケジューラのアドレスを代入します。

    # load `old`
    movl 4(%esp), %eax
    # load `new`
    movl 8(%esp), %edx

次の4つのpushl命令によりスケジューラのコンテキストを保存します。

    # Save old callee-saved registers
    pushl %ebp
    pushl %ebx
    pushl %esi
    pushl %edi

次に2つのmovl命令が続きます。

    movl %esp, (%eax)
    movl %edx, %esp

1つ目の命令movl %esp, (%eax)によりスケジューラのコンテキストを保存します。(実際はスケジューラのコンテキストの先頭を指すスタックポインタespの値を保存します。スケジューラのコンテキストの保存先は&(c->scheduler)で定まる特定のアドレスであり、このためにアンパサンドがついていました。)

2つ目の命令movl %edx, %espコンテキストスイッチの肝です。今までスケジューラのスタックを指していたespをプロセスのスタックを指すようにします。つまり

f:id:toasa3:20200218234153p:plain
スケジューラのカーネルスタック

から

f:id:toasa3:20200218234726p:plain
プロセスのカーネルスタック

へとespが移動しました。

残りは下準備したinitのコンテキストへ切り替えるためpop命令を繰り返します。

    # Load new callee-saved registers
    popl %edi
    popl %esi
    popl %ebx
    popl %ebp
    ret

4度のpoplによりespは次の位置まであがります。

f:id:toasa3:20200218235248p:plain

ret命令により、eipに格納されているforkret関数ポインタをポップし、そこにジャンプします。 forkretC言語の関数として定義されていますが、関数を抜ける際にスタックをポップし、 そこへとジャンプすることは変わりません。よってtrapret関数の関数ポインタがポップされ、関数の先頭へジャンプします。

f:id:toasa3:20200219000301p:plain
trapret呼び出し直後

残るトラップフレームのポップはtrapretによって行われます。trapretは次のようなアセンブリで書かれています。

.globl trapret
trapret:
  popal
  popl %gs
  popl %fs
  popl %es
  popl %ds
  addl $0x8, %esp  # trapno and errcode
  iret

トラップフレーム内のレジスタに注目するため、一つ上に載せたカーネルスタックからトラップフレームの部分を拡大します。それは次のような図になります。今espはトラップフレームの最下部を指していることに注意してください。

f:id:toasa3:20200219220048p:plain

まずpopalにより汎用レジスタを復元します。次の4つのpopl命令によりセグメントレジスタを復元します。そして次のaddl命令によりespを8バイト押し上げ、trapnoerrcodeを無視します。最後のiretにより残るレジスタの復元を行います。具体的にはeip, cs, eflags, esp, ssが復元されます。特にeipespの復元により、initcodeinitプロセスの実行プログラム)のために格納した4096バイトの最下部と最上部を、それぞれeipespが指すようになり、無事initcodeの実行が始まります。

f:id:toasa3:20200219001341p:plain

参考文献

*1:https://ja.wikipedia.org/wiki/Init

*2:https://pdos.csail.mit.edu/6.828/2019/xv6.html

*3:本テーマと不要なメンバは省略しています

浮動小数点数の悲劇

"Roundoff Error and the Patriot Missile" を読んだ。以下要約。

場面: 1991年2月25日 湾岸戦争 アメリカvsイラク

結果: イラクスカッドミサイルがアメリカ陸軍兵舎に向け放たれた。 アメリカのパトリオットミサイルは迎撃に失敗、28人の兵士が死亡。

原因: パトリオットミサイルのシステムは、内部クロックとして0.1秒ごとにインクリメントするカウンタ を採用していた。0.1を2進数の浮動小数点数で表すと循環小数になり、どこかで数を丸める必要がある(実際は仮数部を23bitで保持していた)。 システム起動から100時間後には、丸めから生じる誤差は、実時間と比べおよそ0.34秒になった。 迎撃システムの性質上、長時間連続して可動させた上でも、正確な計算が求められるのだろう。0.34秒という誤差は致命的だった。 実際の直接的な原因は、システム内のタイマーを正確なものに置き換えたとき、 一部、誤差が存在するタイマーがそのまま残ってしまったことだったようだ。

欅坂46 ブログの自動生成 (開発日記)

 

以下は先日ポストした欅坂ブログ自動生成アプリ「zelkova」

github.com

 

の開発日記です。

当初はアンドロイドアプリとして動かそうと思っていましたが、PCのターミナル上で自動生成できたところで、日記として掲載します。

 

-----------------------------------------------------------------------------------------------------

20180905

 

pythonwebスクレイピングを行った。

urllib3ライブラリを使い、<script>タグの中にあるブログ更新日時文字列の取得に成功した。

 

その文字列からメンバーIDを鍵、更新日時を値とした辞書"member_update_time"を作成した

 

 

20180906 

 

webスクレイピングにより、blogのタイトルと文面を取得できた。

CSSセレクターを使うことでより直接値を取得できた。(昨日のやり方では、存在する<script>タグのループを回し、該当箇所を見つけていた)

 

LSTM(long short term memory)の概要を学んだ。

RNN(Recurrent neural network)の拡張であり、どちらも時系列データ(sequential data)を扱う。

時系列順にならんだデータに対し、入力と出力のデータの位置が時系列として近い場合、RNNは過去のデータをもとに学習できる。

だが、その位置が遠い場合(長期依存性の問題という)、RNNでは学習が進まなかった。

LSTMではそれを克服し、長期的な依存関係を学習できるようになった。

これを日本語文の自動生成に当てはめると、今までの単語の列を時系列データとして、次に予想される単語を生成することができるようになる(らしい)

 

 

参考文献

1. https://qiita.com/t_Signull/items/21b82be280b46f467d1b#%E7%AC%AC4%E9%83%A8rnn%E7%9C%9F%E3%81%AB%E6%B7%B1%E3%81%84%E3%83%8D%E3%83%83%E3%83%88%E3%83%AF%E3%83%BC%E3%82%AF

 

2. https://qiita.com/KojiOhki/items/89cd7b69a8a6239d67ca

 

 

今の所、理論よりもすぐに日本語を自動生成した意欲が勝っている。

 

なにか本を買うべきなのか?

 

明日は、今開いているLSTM文章生成ページのどれかを参考にし、文章を生成したい

 

 

 

20180907

 

pipインストールがうまく動かない。python3mecab(日本語形態素解析ツール)を入れようとしたが通らず。

 

この記事を参考にアナコンダをアンインストールした。

https://qiita.com/pickles/items/12c8c73d3d4bbd61f738

python3, pip3も再インストールした。

 

mecabインストールできた。

 

ブログの各文から、mecabを使い形態素に分解できた

ex.

'5', '', '', 'もうすぐ', '', '終わり', '', '', '', '', 'そう', 'いえ', '', '', 'これ', 'といった', '五月', '', '', 'かかっ', '', 'ない', 'かも', 'しれ', '', '!', '', '', '', '', '今年', '', '小林', '', '一味', 'ちがう', '', '', '!', '小林', '由依', 'です'

 

 

アンドロイドアプリはうまくいくのかな?

 

ストップウォッチアプリを作ろうと思い

https://employment.en-japan.com/engineerhub/entry/2017/06/23/110000
を試した。初kotlin。たくさんエラーが出て放置。

 

 

 

20180908(土)

 

できていないこと

・分割した各形態素を学習し、文章をLSTMにて自動生成すること

androidアプリをつくり、実機でテストすること。

 

python3へのtensorflowのインストールに手間取った。

pyenvpython 3.6.0へダウングレードしてから、

pip3 install tensorflow

で通った

 

いまのところLSTMを用いた文章生成のサンプルソースコードを見てもよくわからない。

なので、本「ゼロから作るDeep Learning 自然言語処理編」を注文した。

 

届くまでの間、kotlin入門をやろうと思う。

http://www.atmarkit.co.jp/ait/series/8323/

 

 

 

20180913(木)

ブログの最終更新日時取得のコードはpythonで書いた。

android studiokotlinを用い、androidアプリでそれを利用したい場合、

pythonコードをサーバー上において、androidアプリからはそのresponseを受け取る形にしてはどうか?(竹宮)

 

 

 

20180920(木)

 

本「ゼロから作るDeep Learning 自然言語処理編」の71節「言語モデルを使った文章生成」まで読んだ。

学習済みの重み行列を用いてはいないが(CPUで計算する場合、学習に2日かかると記述があり、怖気づいた)、文章生成は行えた。

うまくいきそう。アンドロイドアプリとなるかはおいといて。

 

githubにレポジトリを作成。最近、覚えたて。嬉しくてよくpushしてる。

 

pythonによるwebscrapingも久しぶりに行った。

主な変更点は、

現在(18/09/20)までの過去の全ブログ(小林由依の)の、文章、タイトル、更新日をカラムとするcsvファイルを生成できた。

 

できていないこと、改良点は、

・メンバーごとの変数(ブログでの管理番号)は別ファイルに定数として保存

・各メンバーブログの最初のポストがあるurlまで、for文をまわすこと

例:

メンバーのブログは、ポストが新しい順にならんでいる。いかのurlにおいて

http://www.keyakizaka46.com/s/k46o/diary/member/list?ima=0000&cd=member&ct=07&page=XXXX

XXXXが大きいほど、古いブログポスト。XXXX=nが最初のポストがあるページだとすると、

http://www.keyakizaka46.com/s/k46o/diary/member/list?ima=0000&cd=member&ct=07&page=n+1

まではforループが回ってほしくない

csvファイルを読み取りcorpusを作ること(mecabを使う)

 

 

20180921(金)

 

改良点は主に2点。

1, word2vecCBOWモデルを用い, 指定した単語と類似度の高いものを列挙できるようになった。

なお、この場合の類似度は、メンバーが書いたブログをもとに、生成するもの。

[query] 織田

鈴本: 0.86669921875

今泉: 0.828125

菅井: 0.8173828125

: 0.787109375

米谷: 0.78662109375

 

[query] see

  おやすみなさい: 0.92431640625

  you: 0.92236328125

  again: 0.82763671875

  うら: 0.8037109375

  では: 0.78173828125

 

2, 関数と定数をそれぞれディレクト"functions", "datasets"の中に入れ、共通パーツ化した。

  なお、関数のコード自体は数日前に書いたものもある。

関数は

getUpdateTime(): ブログの最新更新日時を取得する

getBlogPutCSV(): webサイトへスクレイピングに行き、全投稿ブログの、投稿日時、タイトル、本文を取得し、csvファイルとして出力する

generatePkl(): NNで学習や推論時、使用するcorpus, word_to_id, id_to_word, wordsを格納した辞書型ファイルをpickleファイルとして生成する

 

次に目指すことは、時系列データを生成し(改良点の1ではtargetとなる単語のの両脇の単語を、同等のものとして学習した、これは時系列データの学習ではない)、ブログの文面を自動生成することを目指す。

 

 

 

20180922(土)

 

備忘のため。

1. SGDS(stochastic: 確率的)のイミ。

2. Adamとは

 

1. そもそもNNの学習手順は

mini-batch処理、勾配の算出、パラメータの更新を繰り返す。

このときのmini-batch処理とは、訓練データの中からランダムに一部のデータを選び出す。

その選出がstochasticの由来

2. AdamAdaGradMomentumという、2つのパラメータの更新方法を融合したもの。

AdaGradは、大きく学習すると学習率を小さくし、小さく学習すると学習率を大きくするように調整する、パラメータの更新法。

Momentumは重みWの更新に、速度ベクトルvを導入したもの。

 

 

本「ゼロから作るDeep Learning 自然言語処理編」の「6.3RNNLMのさらなる改善」では

RNNLM(recurrent neural network language model)の改善モデルBetter RNNLMモデルを導入した。

そのモデルの学習用コードではcorpus, corpus_val, corpus_testptbのデータセットから得られるcorpus3つ作成していた。

その意図がわからない。

ptb.train.txtptb.valid.txtptb.test.txtとあるが、ある全体の文章を8:1:1に分割してそれぞれ作成してみてはどうか?

した。うまくいきそう。明日の朝結果を確かめる

 

今の所ブログをスクレイピングしてきたデータは時系列順になっている。

corpus8:1:1に分割してDLするなら、1ブログ単位でシャッフルしたほうが良いと思う。

やろう

 

python3でサーバーをたて、ブログの最新更新日時や、自動生成したブログを返すようなコードをサーバー上で実行し、

アンドロイドアプリとして受け取るのはどうか?python3のサーバーは簡単に建てられたと思う。

 

 

 

20180923(日)

 

ch06/zelkova_train_better_rnnlm.pyを行った。8時間ぐらいかかった。

学習ではppl(パープレキシティ)が良い方向に更新されたときに、パラメータのsaveを行うのだが、

学習開始1時間半後が最終更新となっていた。そのため、あとの6時間半はpplを更新できていなかったのかも。

 

とにかく昨晩作成したパラメータ(zelkova_trained_weight_better_rnnlm_kobayashi.pkl)を用いて、

ch07/zelkova_generate_better_text.pyでブログの文章生成を行おうと思う。

 

エラー

toasa:ch07 $ python3 zelkova_generate_better_text.py

Traceback (most recent call last):

  File "zelkova_generate_better_text.py", line 25, in <module>

    model.load_params('../ch06/zelkova_trained_weight_better_rnnlm_kobayashi.pkl')

  File "../common/base_model.py", line 49, in load_params

    param[...] = params[i]

ValueError: could not broadcast input array from shape (7647,650) into shape (10000,650)

 

 

20180924(月)

 

toasa:ch07 $ python3 /Users/tohyama/sample/python/zelkova/dl-master/ch07/zelkova_generate_better_text.py

私 の マスカラ に 踊っ て しまい まし た 。 ホワイト もらい まし た それ と 2017 みん が 信じ ない 方 は もう 出来る ん です よ よ ね ~ なんて 幸せ な ん です ファン 番組 の 大好き な 気分 は あっ たら 大丈夫 な そう だ な ~ と 思っ て い ます 。 ららぽーと 使い ない 力 。 という こと で どっち の こと で こういう 期生 の 人間 観 ましょ う (°´ ˘ `°)/ さあ どんどん 撮り は ます 。 明日 から 、 握手 会 汚れ 握 で 大阪 でし た ! ZIP CM

 

できた。はじめての文章生成、小林由依のブログ。

こちらで最初の一文字目""を選択。残りの99文字は自動生成されている。

 

 

20180925(火)

 

ブログを取得し、csvファイルとして出力し、corpusまで作成するファイルをprepare/prep_all.pyとして実装した。コマンドライン引数にメンバーの

名前を書くことで実行できる

ex.

$ python3 prep_all.py kobayashi