Growi

2020/06/23

2020/06/23

# 研究目的

  • OSの信頼性を保証する必要がある
  • 信頼性の保証にはモデル検査や定理証明を使用したい
    • 継続ベースの状態遷移系で再実装することで表現しやすくしたい
  • 既存のunixであるxv6をCbCで書き換えて、検証を行いやすくしたい
    • kernel/user両方をCbCで実装する
  • CbCの変換スクリプトなどはPerlで実装されており煩雑
  • CbCを用いたプログラミング言語を作りたい
    • GearsOS用の内部言語
    • Cに依存しないCbCのsyntaxを作成する
  • 実装のプロトタイプとしてCbCを用いてインタプリタ/コンパイラを作成する

# 進捗

  • Gearsの例題の修正とgenerate_stubの修正
  • 様々な理由でperlインタプリタを読んでいた
  • xv6そろそろやりはじめた
  • シス管関係……
  • 明日寄稿した雑誌が発売します!!

# Gearsの例題

# インタプリタ/コンパイラ

  • 実装に進める段階までコードを直した(セグフォしなくなった)
    • Gearsのプログラムを停止させる場合は次のCodeGearを呼び出す必要がある
1
2
3
4
5
6
7

__code code2(struct TaskManager* taskManager) {
    goto taskManager->shutdown(exit_code);
}

__code code2_stub(struct Context* context) {
    goto code2(context, &Gearef(context, TaskManager)->taskManager->TaskManager);
}
  • exit_codeはtaskManager経由で呼び出さないとセグフォする
    • 今まではpar gotoが全て終了したタイミングでcode2が実行されていた

# generate_stubのバグ修正 

1
2
3
4

__code createTask1(struct LoopCounter* loopCounter, struct TaskManager* taskManager) {
    Lexer* lexer = createLexerImpl(context);
    goto lexer->test(code2);
}

こういうCodeGearを書いた場合次のマクロが生成されてほしい

1
2
3
4
5
6
7

__code createTask1(struct Context *context,struct LoopCounter* loopCounter, struct TaskManager* taskManager) {
    Lexer* lexer = createLexerImpl(context);
        Gearef(context, Lexer)->lexer = (union Data*) lexer;
        Gearef(context, Lexer)->next = C_code2;
    context->before = C_createTask1;
    goto meta(context, lexer->printtest);
}

…が、Gearef(context, Lexer)->nextが生成されず、Gearef(context, Lexer)->lexerに代入されてしまっていた

# hoge->nextに値摘んでくれない問題

  • generate_stubの527行目くらいが問題そう
    • 実際にgoto文を生成している場所
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

 } elsif (/^(.*)goto (\w+)\-\>(\w+)\((.*)\);/) {
     # handling goto statement
     # convert it to the meta call form with two arugments, that is context and enum Code
     my $prev = $1;
     my $next = $2;
     my $method = $3;
     my $tmpArgs = $4;
     #$tmpArgs =~ s/\(.*\)/\(\)/;
     my @args = split(/,/,$tmpArgs);
     if (! defined $dataGearVarType{$codeGearName}) {
        print $fd $_ ;
        next ;
     }
     my @types = @{$dataGearVarType{$codeGearName}};
     my $ntype;
     my $ftype;
     for my $v (@{$dataGearVar{$codeGearName}}) {
         my $t = shift @types;
         if ($v eq $next || $v eq "O_$next") {
             $ntype = $t;
             $ftype = lcfirst($ntype);
         }
     }
     if (!defined $ntype) {
         $ntype = $localVarType{$next};
         $ftype = lcfirst($ntype);
     }
     print $fd "\tGearef(${context_name}, $ntype)->$ftype = (union Data*) $next;\n";
     # Put interface argument
     my $prot = $code{$ntype}->{$method};
     my $i = 1;
     for my $arg (@args) {
         my $pType;
         my $pName;
         my $p = @$prot[$i];
         next if ($p eq $arg);
         $p =~ s/^(.*)\s(\w+)//;
         $pType = $1;
         $pName = $2;
         $arg =~ s/^(\s)*(\w+)/$2/;
         if ($pType =~ s/\_\_code$//) {
             if ($arg =~ /(\w+)\(.*\)/) {
                 print $fd "\tGearef(${context_name}, $ntype)->$pName = $1;\n";
             } else {
                 print $fd "\tGearef(${context_name}, $ntype)->$pName = C_$arg;\n";
             }
         } elsif ($pType =~ /Data\**$/){
             print $fd "\tGearef(${context_name}, $ntype)->$pName = (union $pType) $arg;\n";
         } else {
             print $fd "\tGearef(${context_name}, $ntype)->$pName = $arg;\n";
         }
         $i++;
     }
     print $fd "${prev}context->before = C_$codeGearName;\n";
     print $fd "${prev}goto meta(context, $next->$method);\n";
     next;
  • デバッグしたところ問題となってるのがこのところ
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

  print $fd "\tGearef(${context_name}, $ntype)->$ftype = (union Data*) $next;\n";
  # Put interface argument
  my $prot = $code{$ntype}->{$method};
  my $i = 1;
  for my $arg (@args) {
      my $pType;
      my $pName;
      my $p = @$prot[$i];
      next if ($p eq $arg);
      $p =~ s/^(.*)\s(\w+)//;
      $pType = $1;
      $pName = $2;
      $arg =~ s/^(\s)*(\w+)/$2/;
      if ($pType =~ s/\_\_code$//) {
          if ($arg =~ /(\w+)\(.*\)/) {
              print $fd "\tGearef(${context_name}, $ntype)->$pName = $1;\n";
          } else {
              print $fd "\tGearef(${context_name}, $ntype)->$pName = C_$arg;\n";
          }
      } elsif ($pType =~ /Data\**$/){
          print $fd "\tGearef(${context_name}, $ntype)->$pName = (union $pType) $arg;\n";
      } else {
          print $fd "\tGearef(${context_name}, $ntype)->$pName = $arg;\n";
      }
      $i++;
  }
  print $fd "${prev}context->before = C_$codeGearName;\n";
  print $fd "${prev}goto meta(context, $next->$method);\n";
  next;

  • $nextは次のCodeGearの名前じゃなくて、インスタンスが入っている

  • my $prot = $code{$ntype}->{$method};でInterfaceのメソッド一覧を取り出している

    • $ntypeは現在のinterface名、 $methodは->で呼び出す先

  • なんかデバッガでdumpしたら%codeが明らかにおかしい結果に…

    • LexerとLexer が混在している
    • ここが関係していそう
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

  DB<11> p %code
{
    ''            {},
    Lexer         {},
    'Lexer '      {
        eat_whitespace   [
            [0] "Impl* lexer",
            [1] "char* ch",
            [2] "__code next"
        ],
        next             [],
        next_token       [
            [0] "Impl* lexer",
            [1] "__code next"
        ],
        printtest        [
            [0] "Impl* lexer",
            [1] "__code next"
        ],
        read_char        [
            [0] "Impl* lexer",
            [1] "char* ch",
            [2] "__code next"
        ]
    },
    TaskManager   {
        decrementTaskCount   [
            [0] "Impl* taskManagerImpl",
            [1] "__code next"
        ],
        incrementTaskCount   [
            [0] "Impl* taskManagerImpl",
            [1] "__code next"
        ],
        next                 [],
        next1                [],
        setWaitTask          [
            [0] "Impl* taskManagerImpl",
            [1] "Context* task",
            [2] "__code next"
        ],
        shutdown             [

# 原因

  • InterfaceからCodeGearを取り出す箇所のキャプチャがおかしかった

書いていたInteface

1
2
3
4
5
6
7

typedef struct Lexer <Type, Impl> {
  __code read_char(Impl* lexer, char* ch, __code next(... ));
  __code eat_whitespace(Impl* lexer, char* ch, __code next(... ));
  __code next_token(Impl* lexer, __code next(struct token* tok, ...));
  __code printtest(Impl* lexer, __code next(...));
  __code next(....);
} Lexer;

ここのtypedef struct Lexer <Typeの行をキャプチャしにいっていたが…

  • elsif(/^typedef struct (.*)<.*>\s*{/) {
    • (.*)でキャプチャしていたので、空白も含まれる状態に….
    • (\w+)に書き直すことでなんとなかなった
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

--- a/src/parallel_execution/generate_stub.pl   Tue Jun 16 21:09:01 2020 +0900
+++ b/src/parallel_execution/generate_stub.pl   Mon Jun 22 09:17:31 2020 +0900
@@ -203,10 +203,10 @@
     open my $fd,"<",$filename or die("can't open $filename $!");
     my ($name,$impln);
     while (<$fd>) {
-        if (/^(\w+)(\*)+ create(\w+)\(/) {
+        if (/^(\w+)\s*(\*)+ create(\w+)\(/) {
             $name = $1;
             $impln = $3;
-        } elsif(/^typedef struct (.*)<.*>\s*{/) {
+        } elsif(/^typedef struct (\w+)\s*<.*>\s*{/) {
             $name = $1;
         }
         if (defined $name) {
  • xv6側もその実装だったので、去年あったマクロがずれるとかの問題も影響していそう…

# xv6側

  • システムコール呼び出し側から実装していく
    • 去年書いたコードは使えなさそうな気がする…..
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

void syscall(void)
{
    int num;
    int ret;

    num = proc->tf->r0;

    if (num == 5)
        num = 22;
    //cprintf ("syscall(%d) from %s(%d)\n", num, proc->name, proc->pid);

    if((num >= NELEM(syscalls)) && (num <= NELEM(cbccodes)) && cbccodes[num]) {
        proc->cbc_arg.cbc_console_arg.num = num;
        goto (cbccodes[num])(cbc_ret);
        //goto meta(&proc->cbc_context, cbccodes[num]);
    }


    if((num > 0) && (num < NELEM(syscalls)) && syscalls[num]) {
        ret = syscalls[num]();

        // in ARM, parameters to main (argc, argv) are passed in r0 and r1
        // do not set the return value if it is SYS_exec (the user program
        // anyway does not expect us to return anything).
        if (num != SYS_exec) {
            proc->tf->r0 = ret;
        }
    } else {
        cprintf("%d %s: unknown sys call %d\n", proc->pid, proc->name, num);
        proc->tf->r0 = -1;
    }
}

  • 現状はcbc_readだけgotoする様になっている

    • cbc_read自体は__ncodeで書かれていてIntertface化されていない

  • とりあえずSyscall Interfaceを書いてそれを各システムコールで実装する

    • file->read()とかにするとかっこいいけれど、それはシステムコールディスパッチしてから記述する
    • syscallの実装をContextに持っておかないと行けないので、kernelのContextを最初に作らないとダメそう

# kernelのContext

  • システムコールディスパッチの箇所や、例外処理などで必要そう
    • context間通信みたいなのを実装すれば必要無い可能性はある
  • どのタイミングで生成する?
    • 仮想メモリ自体も管理したいなら、仮想メモリマネージャーを作る前で作成する必要がある
    • 具体的に言うとmain.cのinit_vmmの実行前にするべき?
  • どうやって保存する?
    • 大域変数が一番楽ではあるけれど……
  • kernelのContextがprocess Contextを管理する形にすると良さそう
  • とりあえずmain.cに大域変数で実装してみている
    • シングルトンっぽくなるのであまりやりたくはない….
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

struct Context kernel_context;

#define MB (1024*1024)

void kmain (void)
{
    uint vectbl;

    cpu = &cpus[0];

    uart_init (P2V(UART0));

    // interrrupt vector table is in the middle of first 1MB. We use the left
    // over for page tables
    vectbl = P2V_WO (VEC_TBL & PDE_MASK);

    init_vmm ();
    kpt_freerange (align_up(&end, PT_SZ), vectbl);
    kpt_freerange (vectbl + PT_SZ, P2V_WO(INIT_KERNMAP));
    paging_init (INIT_KERNMAP, PHYSTOP);

    kmem_init ();
    kmem_init2(P2V(INIT_KERNMAP), P2V(PHYSTOP));
    initContext(&kernel_context);

    trap_init ();                               // vector table and stacks for models
    pic_init (P2V(VIC_BASE));   // interrupt controller
    uart_enable_rx ();                  // interrupt for uart
  • init_vmmからkmem_init2までの一連のルーチンに鑑賞できない点が辛い
    • どうにかしたい気がする…..
    • 諦める?

# 今後の方針

  • kernelのcontextを実装する
    • kernelのcontextを初期化する場所を決める
    • 新しい変換スクリプトを書く/generateContextに手を加える
  • read systemcallのinterface化

# Perlインタプリタ

  • 字句解析/構文解析/AST関連を見てた
  • 主に連鎖比較関係
Growi
Licensed under CC BY-NC-SA 4.0
comments powered by Disqus
© 2020 - 2024 Hugo Theme Stack Starter
Built with Hugo
Theme Stack designed by Jimmy