BYB

低レイヤ好き学生エンジニアによる備忘録

Linuxで動くNICドライバの開発をしている

概要

Linuxで動くe1000eドライバを開発しようとしており、ドライバと紐付けたNICのstateがupになるところまで進めました。
個人的に忙しくなった都合で一旦ここでプロジェクトを止めるため、備忘録としてここまでの作業内容を簡単に書き記し、詰まった点についても文章として残しておこうと思います。
前半部では、NICドライバ実装のために必要な処理のうちパケット送受信以外に関する部分について書いています。
後半部では、ドライバ実装中にLinuxカーネル関連で詰まった箇所とその解決の様子を書いています。

おことわり

実はまだパケットを送受信する部分を作りこめていません。 そのこともあって、ドライバがパケットを送受信する仕組みなどについてはこの記事では一切触れないことにしました。
知りたい方は別の何かを読んでください、すみません。
自分は下記のような記事を読んで理解することができましたので、ご興味のある方はぜひ見てみてください。(すごくわかりやすいです)

MikanOS に NIC ドライバを実装する - 準備編 #自作OS - Qiita
Intel NIC ドライバにおけるパケット送信について - かーねるさんとか

流れ

以前xv6へe1000eドライバを実装し、無事送受信ができることを確認できたので(ソースコード)、次はそのドライバをLinuxで動かそうと思いました。

Linuxではドライバをカーネルモジュールとして組み込むことができるので、カーネルと一緒にビルドする必要がありません。
自分もこの機能を使って自作ドライバを動かす方針にしました。
またLinuxではカーネル側が提供するAPI関数を使うことで、自作のNICドライバとカーネルのネットワークスタックを連携させることもできます。


[前半]:NICドライバ実装に必要な作業

デバイスドライバの実装してカーネルモジュールとして動かす方法は、こちらの記事と書籍を参考にさせていただきました。
組み込みLinuxデバイスドライバの作り方 (1) #Linux - Qiita
Linuxデバイスドライバプログラミング | SBクリエイティブ

pci_diriver構造体を定義して、ドライバを登録

ドライバを登録する方法は、デバイスの種類によって異なる。
PCIバイスに関しては、insmod時のエントリポイントとなる関数で、pci_divice登録用の関数を呼び出すことで登録できる。
引数となるのはpci_driver構造体で、ここにこのドライバが取り扱うデバイスのリストや、デバイスの状態変化時に呼び出される関数を定義する。
こうすることで、今実装しているドライバとデバイスを紐づけることができる。

static struct pci_driver yama_e1000_driver = {
	.name     = yama_e1000e_driver_name, //name
	.id_table	  = yama_e1000_pci_tbl, //the list which specify the PCI devices supported by the driver.
	.probe    = yama_e1000_probe, //function that is called when the kernel discovers an appropriate PCI device 
	.remove = yama_e1000_remove // function that is called when a matching PCI device is removed from the system
};

今回実装したのはこれだけだが、きちんとしたドライバを作るには他にも実装すべき項目はある。

net_deviceとして登録

probe関数内で、デバイスをnet_deviceとして登録する。

struct net_device *netdev = alloc_etherdev(sizeof(struct yama_e1000e_adapter));
if(!netdev){
	return -ENOMEM;
}
netdev->netdev_ops=&yama_e1000e_netdev_ops;
// some ops
ret=register_netdev(netdev);

alloc_etherdev関数の引数となっているyama_e1000e_adapterという構造体は、ドライバ実装において必要な変数を含むものを自分で定義したものである。
こうすることで、任意の必要な値をprivateデータとしてnet_device構造体の末尾にくっつけて取り扱うことができる。
現時点で自分が定義しているデータは、以下である。
https://github.com/yushoyamaguchi/yama_driver/blob/debug1/yama_e1000e/include/yama_e1000e.h#L33

net_deviceハンドラ関数を用意してハンドラテーブルに登録

static const struct net_device_ops yama_e1000e_netdev_ops = {
	.ndo_open = yama_e1000e_netdev_open,
	.ndo_stop = yama_e1000e_netdev_close,
	.ndo_start_xmit = yama_e1000e_start_xmit,
	.ndo_set_mac_address = yama_e1000e_set_mac_addr,
	.ndo_get_stats = yama_e1000e_get_stats,
};

下記のような仕様に沿った形で、net_deviceとしての様々な役割をこなす関数を作成し、テーブルに登録する。
https://elixir.bootlin.com/linux/latest/source/include/linux/netdevice.h#L1400

全てを実装することはできないので、とりあえず必要そうな関数だけを登録した。(それでもその中身はまだ完成なのですが...)


パケット送信時に呼び出される関数は、ndo_start_xmit のところに登録する。

割り込みの定義(未動作確認)

受信はパケットが入ってきた時に、割り込み処理として実行されるようにしたい。
そのため以下のように、受信時に呼び出したい関数 yama_e1000e_irq_handler を登録した。

ret=request_irq(adapter->pdev->irq,yama_e1000e_irq_handler,IRQF_SHARED,yama_e1000e_driver_name,adapter);

この関数の第一引数には、該当するirq番号を入れる。
PCIバイスの場合は、スロットごとにIRQ番号が自動で決められており、OSから教えてもらうことができる。

MMIOレジスタを適切に初期化して、実際にパケットを処理する部分を書いていく(未実装)

上記のように、パケット送受信部の処理を実装する。

ハンドラとスケジューリング

割り込み
割り込みの後半部、Softirq、Tasklet、Work Queue
上記の記事のように、割り込みハンドラ自体の処理を短くすることで、割り込み禁止の時間をを短くする必要がある。
時間的制約のある処理だけをハンドラで行い、残りの処理はよしなにスケジューリングする。





[後半]:Linuxカーネル関連で詰まったところ

insmod時のカーネルクラッシュ

はじめ、insmod時にカーネルがクラッシュする症状が出ていた。
クラッシュ時のメッセージを読むために、

-serial file:path_to/serial.log

上記のオプションをつけて起動したQEMU上でUbuntuを動かして、
ゲストUbuntu上で /etc/default/grub を編集してコンソールの内容をシリアル出力するように変えた上で、ドライバを動かした。

[  646.160007] genirq: Flags mismatch irq 11. 00000000 (yama_e1000e) vs. 00000080 (uhci_hcd:usb1)

クラッシュ時にこのようにirq番号に関するエラー出力を観測できたので、request_irq関数の第三引数をIRQF_SHAREDに変えることで、カーネルクラッシュが起こらないようにした。

インターフェースのstateがUPにならない問題

動作しているインターフェースを iproute2を利用して見た際は通常、下記の写真のようにstateがUPになっている。

ip link show を実行した様子

しかし自分が実装したドライバが紐づいているインターフェースをiproute2を使って見たところ、stateがUNKNOWNになっていた。
原因を探るべく、iproute2のnetlinkメッセージを読み取る部分にデバッグプリントを入れて実行してみたところ、netlinkメッセージのoperstateという部分が原因であるように思えた。

iproute2にデバッグプリントを入れて実行した様子

そこで今度は、Linuxカーネル内のどこの部分がnetlinkメッセージのこの部分に値を設定しているのかを調べた。
https://elixir.bootlin.com/linux/v6.6.6/source/net/core/rtnetlink.c#L1807
すると、net_device構造体のoperstateという変数が参照されているような記述が見つかったので、ドライバでその値を適切に設定するように変えた。
その結果、無事に自作ドライバと紐づくインターフェースのstateがUPという風に表示されるようになった。

netlinkメッセージ内のoperstateの値が変更され、NICのstateがUPに


処理を全て追いかけたわけではないが、この rtnl_fill_ifinfo という関数は、

から呼び出されていた。

ソースコード

  • ドライバ(実装途中)

github.com

github.com

さいごに

怪しい記述や間違っている箇所を見つけてくださった方がいれば、教えていただけると嬉しいです...

MikanOSにユーザースレッド風機能を実装

概要

初めに

このブログは以前書いたものを、2022 自作 OS Advent Calendar用に書き換えて再公開したものです。
当初は備忘録的な意味で書き殴っていたものであるため、非常に長くまとまりのない文章になってしまってすみません。
また勘違いをしていて間違った内容を書いているところがあるかもしれないので、気付いた方はご指摘をいただけると嬉しいです。

このブログの内容について

前回のブログでMikanOSにspinlockを実装したつもりであったが、勉強していくうちに、MikanOSはシングルスレッドなのでCPUで割り込み防止をするだけで排他制御が可能であることが分かった。
そしてMikanOSにはアプリケーションを並列処理で実行するための仕組みが備わっていないことも知った。
今回はそれを実現するためのユーザースレッドを実装した。
なお前回のブログに書いていた通り、自力で調べて実装までするのは難しいと感じたため、サイボウズ・ラボユースに応募してそこで取り組ませてもらうことにした。
labs.cybozu.co.jp
サイボウズ・ラボユースは、世界に通用する日本の若手エンジニアの発掘と育成を目指すことを目的に、学生の若手クリエイターに研究開発の機会を提供する場としてサイボウズ・ラボさんが開いてくだっさっている。
ここに採択されると、サイボウズ・ラボの方にメンターとしてついてもらって自分のしたい研究・開発に取り組むことができ、奨励金もいただくことができるという嘘みたいな本当の制度である。

ユーザースレッドについて

スレッドとは

そもそもスレッドとはどういったものだろうか。
スレッドとプロセスの違いなども含めて説明しておきたいと思う。
簡単に述べると、

  • プロセス:プロセスID,メモリ空間,コンテキストなどを独自に持つ実行単位
  • スレッド:プロセスに紐づいている、メモリ空間をプロセスと共有するひとまとまりの命令処理

といった具合だろうか。
(おまけ)低レイヤの話 ~Linuxとの比較~|Goでの並行処理を徹底解剖!
なおこのブログにも書いてある通り、Linuxカーネル内部ではプロセスとスレッドはtask_struct構造体という共通のデータ構造で扱われている。

ユーザースレッド

ユーザースレッドとは、ユーザー空間上で生成されるスレッドのことである。
スケジューリングはライブラリ内のスレッドスケジューラが行う。

今回実現したユーザースレッドの機能と仕様

今回は、POSIXスレッドにおけるpthread_createとpthread_joinにあたる機能を実装した。
create関数は引数として、新スレッドに対応するapp_thread_t構造体へのポインタと新スレッドのエントリポイント関数のアドレス、その関数に渡す引数をとる。
pthread_createと違い、属性の指定はできない。
apps/app_thread.cpp

int app_thread_create(app_thread_t* t, void* f, int64_t data){
    auto [ret, err] =SyscallThreadCreate((void *)f,data);
    t->task_id=ret;
    return 0;
}


join関数は引数として待ち合わせたいスレッドに対応するapp_thread_t構造体へのポインタを引数として取る。
pthread_join関数ではpthread_t構造体そのものを引数として取るが、createと違う形にすることに特に意味はないと思ったので、join関数もポインタを引数にすることとした。
処理の中身は、指定したスレッドが終わっているかを無限ループで監視し続け、終わっていたらループを抜けるというものである。

int app_thread_join(app_thread_t *thread){
    int64_t task_id=thread->task_id;
    while(1){
        auto [ret, err]=SyscallTaskExist(task_id);
        if(ret==0){
            break;
        }
    }
    return 0;
}


スレッドのエントリポイント関数は、引数として64bitの値をとる。

実装に必要な前提知識

実装に必要な計算機科学やMikanOSについての前提知識をまとめる。

MikanOSにおけるマルチタスクの実現

MIkanOSを含む多くのOSにおいて、マルチタスクの実現はコンテキストを切り替えることによって行う。
スタックポインタや命令ポインタなどの値をそっくりすげ替えることで、CPUからすると命令を逐次実行しているだけにも関わらず、全く違う処理に飛ぶことができるのだ。
ただし、タスクを切り替える前の処理にもう一度戻ってこれるように、前のタスクにおけるスタックポインタや命令ポインタなどの値を保存しておく必要がある。
このようなデータや変数のまとまりのことをコンテキストと呼ぶ。
MikanOSのコンテキスト構造体を以下に示す。
コンテキストを切り替える際に値の保存と復帰が必要なレジスタを全て含んでいる。

struct TaskContext {
  uint64_t cr3, rip, rflags, reserved1; // offset 0x00
  uint64_t cs, ss, fs, gs; // offset 0x20
  uint64_t rax, rbx, rcx, rdx, rdi, rsi, rsp, rbp; // offset 0x40
  uint64_t r8, r9, r10, r11, r12, r13, r14, r15; // offset 0x80
  std::array<uint8_t, 512> fxsave_area; // offset 0xc0
} __attribute__((packed));

タスクの自動切り替えは、タイマーによって一定時間が来たら割り込みを行うような処理をして、その割り込みのハンドラでSwichTask関数を呼ぶことで実現している。

メモリ空間

MikanOSを始めとするx86-64の64bitモードで動くOSは、メモリ管理をページングによって行う必要がある。
ページングとは仮想記憶(仮想メモリ)の方式の一つで、メモリ領域をページと呼ばれる一定の大きさの領域に分割し、物理的なアドレス(番地)とは別に仮想的なアドレスを割り当てて管理する方式である。
ページング方式 - Wikipedia

x86_64におけるページング構造は、次のような階層を持っている。
この構造通りにメモリ上に階層ページング構造(ページテーブル等)を構築すれば、MMUがそれを辿ることで仮想メモリ-物理メモリ間の変換を行うことができる。

出典:
https://qiita.com/mopp/items/82bef23d0470de21b5d3


特権レベル3で動くアプリの呼び出しと復帰 (CallApp)

特権レベル3で動かすアプリの処理へ移行するためには、以下のことが必要である。

  • 予めDPL(descriptor_privilege_level)=3を持つコードセグメントとデータセグメントを構築し、GDT(Grobal Descriptor Table)に登録しておく。
  • アプリを呼び出す前に、アプリ用のスタック領域や引数受け渡し用の領域をアプリ用のアドレス空間に構築しておく。

アプリ用のページテーブルへのポインタをcr3レジスタに入れた上で、userビット1の領域をSetupPageMaps関数で確保することで、アプリ用のアドレス空間にアプリが使えるメモリ領域を作ることができる。


移行時の処理としては、

  1. OS用のスタック領域に、現在の各種レジスタの値を保存する。
  2. アプリ呼び出しの際に、セグメントレジスタであるCS・SSがそれぞれ先程登録したコードセグメント・データセグメントを指すようにする。
  3. rspを書き換えてスタックをアプリ用のものに変える。
  4. ripの値をアプリのエントリポイント関数のアドレスに書き換える。

上記の処理を行うことで、そのタスクにおいて権限レベル3でアプリが動き出す。
なお上記の内2-4のレジスタ書き換え処理は、スタックに適切な順番で値を積んだ後に、far returnを呼び出すことで実現している。
(権限が低いコードセグメントへのfar returnの場合、rip・csだけでなく、ss・rspもスタックから取り出される。)
この処理を行うのがCallApp関数である。

kernel/asmfunc.asm

global CallApp
CallApp:  ; int CallApp(int argc, char** argv, uint16_t ss,
          ;             uint64_t rip, uint64_t rsp, uint64_t* os_stack_ptr);
    push rbx
    push rbp
    push r12
    push r13
    push r14
    push r15
    mov [r9], rsp ; OS 用のスタックポインタを保存

    push rdx  ; SS
    push r8   ; RSP
    add rdx, 8
    push rdx  ; CS
    push rcx  ; RIP
    o64 retf
    ; アプリケーションが終了してもここには来ない


アプリを終了して特権レベル3から0に戻す処理には、システムコールを利用する。
通常のシステムコールは処理が終わるとsysret命令で呼び出し元の処理に戻る。
しかしアプリ終了システムコールは、処理の最後でスタックをアプリ用のものに切り替えたのち、ret命令を呼ぶ。
そうすることで、CallApp関数を呼んだOS側の処理に戻る。
CallApp関数がここへのreturnを呼ぶことはないので、CallApp関数呼び出し時のcall命令でスタックに積まれたripの値を、アプリ終了システムコールが利用するという形である。
(CallApp関数の最後のfar returnが呼ばれるときは、スタック(やその他レジスタ)がアプリ用のものになっていて、スタックに積まれた取り出すべきripの値はアプリのエントリポイントである。)


アプリケーションから画面への出力

アプリ上のprintf()関数等からターミナルへの出力を行うためには、write()システムコールが必要である。
sourceware.org Git - newlib-cygwin.git/tree
(このようなドキュメントを見ていくことで、標準関数に必要な関数とその形式を調べることができる。)
MikanOSにおけるwrite()はapps/newlib_support.cppの中に実装されており、その実体はPutStringシステムコールを呼び出すことである。
PutStringシステムコールでは、指定されたファイルディスクリプタの番号に従って、適切な場所に文字列を送り込むことである。
(MikanOSにて実装されているのは、ターミナルへの出力およびコマンドのパイプライン上への出力である)


設計と実装

設計の背景と概要

プロセス

MikanOS上でタスクと呼ばれているものは、メモリ空間を別に持つためLinuxにおけるプロセスのようなものである。
ただしMikanOSではLinuxと違って、タスクをツリー構造ではなくリストとして管理しており、タスク同士の親子関係という概念も存在しない。
しかしスレッドを実装する上でどのプロセスのメモリ空間と紐づくスレッドかという情報をタスクに置いておく必要があるため、リスト構造となっているのとは別に親子関係を示すポインタを保持しておく。

スケジューリング

なお本来ユーザースレッドのスケジューリングはアプリ側のライブラリ内のスレッドスケジューラが行うものだが、今回はユーザースレッドも他のプロセスと同様にOSがスケジューリングを行うようにした。

メモリ空間

またMikanOSにおけるtaskはLinuxのプロセスのように、データやメモリ空間をそれぞれ独立して持つ。
一方ユーザースレッドは、親タスクや他のスレッドとメモリ空間を共有している必要がある。
ページング方式のメモリ管理において、メモリ空間を共有するということは、ページマップ(ページング構造)を共有するということである。
そのためスレッドは、親タスクが持つページング構造をそのまま利用するような実装にした。

入出力

またCLIアプリケーションから呼び出すスレッドということで、スレッドが呼び出し元タスクと同じターミナルと紐づく必要がある。
ファイルディスクリプタを共有することで、その要件を満たした。

追加したデータ構造

task、terminal、layer(画面に出力する平面の画像データ。複数重ね合わせることで、windowの重なりやマウスポインタなどを表現。)を繋ぐデータ構造を変更した。

元々の実装

  • terminal-task
  • layer-task
  • (もちろんlayer-terminalも)


がそれぞれ1対1対応だった。
キーボードからの入力があった際に、アクティブな(一番上に来ていて入力を受け付けている)レイヤーと対応しているタスクに、入力された文字列を送信する仕組みをとっていた。

新しい実装

1つのターミナルに複数のタスクが紐づくようになり、layerとtaskが1対1対応ではなくなった。
そこで、

class Terminal {
  //省略
  uint64_t input_task_id=0; 
  //省略
};

このような変数を付け加えて、ターミナルの中のどのタスク(スレッド)から入力があったかを記録するようにした。
また、

  • terminal-layer

間は1対1対応である。

そこで、

  • layer->terminal ->task(input_task_idを持つもの)

というふうに辿ることで、入力を適切なタスクに送り届けるようにした。


システムコールの準備

ユーザースレッドは、アプリケーションからシステムコール呼び出しで作成される。
今回はスレッドを作成するシステムコールに加え、指定したタスクIDをもつタスクが存在するか調べるもの、アプリケーションが動くタスクにて使用しているCR3レジスタの値を返すもの、CPUの割り込み禁止/許可によって排他制御を実現するシステムコールを加えた。

apps/syscall.h

struct SyscallResult SyscallThreadCreate(void *f,uint64_t data);
struct SyscallResult SyscallCR3toApp();
struct SyscallResult SyscallTaskExist(uint64_t task_id);
struct SyscallResult SyscallIntrLock();
struct SyscallResult SyscallIntrUnlock();

スレッド生成処理の流れ

スレッド生成システムコールが呼び出されると、まずはthread_create関数が呼び出される。
そこから呼び出される関数ごとに、処理の流れを説明してゆく。

thread_create
  • まずは空のタスクを生成して、タスク構造体に親子関係を記述する。
  • その後、生成したタスクのコンテキスト構造体に各種設定をしてゆく。
  • スレッドでは呼び出し元タスクとメモリ空間を共有するため、現在のcr3レジスタの値を取得して、それをそのまま新たなスレッドのコンテキスト構造体のcr3の値に設定する。

(システムコールによって処理がカーネル側に奪われた際も、cr3レジスタの値は変化しないようになっている。)

  • ripにはexec_thread_funcのアドレスをセットし、引数を示すrdi、rsi、rdxに引数の値をセットする。

そして最後にこのスレッドをWakeupさせれば、ここまでで作成したタスクにCPU時間が割り振られるようになる。
このタスクが初めて実行される時、ripにセットしたexec_thread_func関数のアドレスから実行が始まる。
kernel/thread.cpp

uint64_t thread_create(ThreadFunc* f,int64_t data){
    __asm__("cli");
    Task* current=&(task_manager->CurrentTask());
    Task* new_task=&(task_manager->NewTask());
    __asm__("sti");
    new_task->is_thread=true;
    new_task->parent_id=current->ID();
    current->children_id.push_back(new_task->ID());
    //ここでいろいろコピー
    const size_t stack_size = new_task->kDefaultKernelStackBytesOfThread / sizeof(new_task->stack_[0]);
    new_task->stack_.resize(stack_size);
    uint64_t stack_end = reinterpret_cast<uint64_t>(&new_task->stack_[stack_size]);

    memset(&(new_task->context_), 0, sizeof(new_task->context_));
    new_task->context_.cr3 = GetCR3();
    //printk("thread_create : cr3=%lx\n",new_task->context_.cr3);
    new_task->context_.rflags = 0x202;
    new_task->context_.cs = kKernelCS;
    new_task->context_.ss = kKernelSS;
    new_task->context_.rsp = (stack_end & ~0xflu) - 8;

    void (*etfunc)(ThreadFunc* ,u_int64_t,int64_t)=exec_thread_func;
    new_task->context_.rip = reinterpret_cast<uint64_t>(etfunc);
    new_task->context_.rdi = reinterpret_cast<uint64_t>(f); 
    new_task->context_.rsi = new_task->ID();
    new_task->context_.rdx = data;

    task_manager->Wakeup(new_task);

    return new_task->ID();
}
exec_thread_func
  • まずstack_frame用のメモリ領域に、スレッド用のスタック領域を確保する。

具体的にはスタック領域として使用したいアドレスの範囲をSetupPageMaps関数渡すと、この関数がページング構造を設定してくれるので、その領域にアクセスすることが可能となる。

これによって、親タスクと同じターミナルからの入出力が可能となる。

  • デマンドページングによって使用可能なアドレスの範囲も親タスクと共有する。
  • 最後に、CallAppforThreadを呼ぶ。

CallAppforThreadは、引数の数以外は CallApp関数と同じである。
戻ってきたら、その自分自身のタスクをスリープさせておく。

kernel/thread.cpp

void exec_thread_func(ThreadFunc* f,uint64_t task_id,int64_t data){
    Task* child=task_manager->GetTaskFromID(task_id);
    Task* parent=task_manager->GetTaskFromID(child->parent_id);
    const int stack_size = 16 * 4096;
    num_of_thread++;
    LinearAddress4Level stack_frame_addr{0xffff'ffff'ffff'f000 - (stack_size)*(num_of_thread+1)};
    // #@@range_end(increase_appstack)
    if (auto err = SetupPageMaps(stack_frame_addr, stack_size / 4096)) {
        printk("thread exec func : stack page map err\n");
        while(1) __asm__("hlt");
        return ;
    }
    for (int i = 0; i < parent->files_.size(); ++i) {
        child->Files().push_back(parent->files_[i]);
    }
    child->SetDPagingBegin(parent->DPagingBegin());
    child->SetDPagingEnd(parent->DPagingEnd());
    int ret = CallAppforThread(data, 3 << 3 | 3, reinterpret_cast<uint64_t>(f),
                    stack_frame_addr.value + stack_size - 8,
                    &(child->OSStackPointer()));

    while(1){
        __asm__("cli"); 
        task_manager->Sleep(task_id);  
    }    
    return;
}
後処理

スレッドを呼び出したアプリケーションの終了時に、sleepしているはずの子スレッドを終了させるような実装にしている。
もしjoin忘れ等で親タスク終了時に子スレッドが走っていた際は、子スレッドをsleepさせるような実装にした。


難しかった点

今回の改造には様々な前提知識が必要なので、それを体系的に学ぶまでは難しいというより歯が立たない状態だった。
逆に、ラボユースのメンターの方とのミーティングの中でそれらの知識を手に入れて以降は、スムーズに設計と実装をすることができた。
QEMUが落ちてしまうバグ(おそらくトリプルフォールト?)に見舞われてデバッグに苦労した時期も一度あったが、printデバッグGDBによるデバッグを組み合わせることで、原因を特定することができた。
(スレッド終了の待ち合わせができておらず、アプリ終了時に解放したメモリ領域にスレッドからアクセスしようとしていたのが原因だった。)
以下はMikanOSでのgdbデバッグのやり方をまとめたスライドである。
ゼロからのOS自作入門 輪読会 第7回 - Google スライド


マルチスレッドを用いたサンプルアプリケーション

実装したユーザースレッドの動作確認のために、3つのアプリケーションを作成した。
いずれも意図通り動作した。

テスト出力アプリ

2つのスレッドから異なるメッセージをターミナルに出力する。


2つのスレッドからの出力が、毎回違う順番で表示される様子

mikanos_thread1/uthread1.cpp at u_thread · yushoyamaguchi/mikanos_thread1 · GitHub

入出力アプリ

入力スレッドはキーボードからの入力があると、その数字をグローバル変数に設定する。
出力スレッドはグローバル変数の値を無限ループで表示し続ける。
このアプリで確認したいことは、

  • 同ターミナルへの入出力を違うスレッドで行うことができること
  • スレッド間でグローバル変数を共有できること

である。

mikanos_thread1/uthread2.cpp at u_thread · yushoyamaguchi/mikanos_thread1 · GitHub


ソートアプリ

int型配列を前後半2つに分けて、2つのスレッドでそれぞれマージソートした後、さらにマージする。
これもスレッド間で同じ配列を扱うテストである。

https://github.com/yushoyamaguchi/mikanos_thread3/blob/u_thread/apps/uthread1/uthread3.cpp


ソースコード

github.com
元のソースコードとの差分を見たい方は以下
github.com

謝辞

この実装は自分ひとりの力では絶対にできませんでした。
ラボユースでメンターをしてくださっている川合さんと様々なアドバイスをくださった内田さんという、ビッグなお二人の知恵をお借りしてで実現することができました。
ありがとうございました。

BuildしたFRRoutingをDockerコンテナで動作させ、BGPのオレオレPath Attributeを流す

buildしたFRRoutingをDockerコンテナで動かす

imageのbuild

まず、FRR自体のbuildを行う。
Ubuntu 20.04 LTS — FRR latest documentation
例えばUbuntu20で動かす場合、このドキュメントに従えば良い。
次にそのバイナリをコンテナに組み込めるように、docker image をbuildする。
なお2回目以降のbuildに関しては、

 sudo make install

だけでよい。

次に、そのバイナリを含んだdocker image をビルドする。
この部分に関しては、このシェルスクリプトを実行するだけで良い。
github.com

 sudo bash path_to_frr/docker/alpine/build.sh

これが成功すれば、 frr:alpine-XXXXXX のような名前のdocker image が出来上がっているはずである。

コンテナ上でbgpdを動かす

docker run したのちそのコンテナのシェルに入り、以下のコマンドを実行する

sed -i -e 's/bgpd=no/bgpd=yes/g' /etc/frr/daemons
/usr/lib/frr/frrinit.sh start

/etc/frr/daemonsにて、動かすデーモンの種類を指定する。
デフォルトでは多くが動かない設定となっている。



FRRoutingでbgpdを小改造し、自作path_attrをパケットに入れて運ぶ

eniyo0.hatenablog.com
この記事にならってオレオレPath Attribute を自作し、それをdockerコンテナ上で動かした。
Path Attributeの実装については、この記事を見ていただきたい。
実装が終わったらbuildして、前章の内容のとおりにdocker imageに組み込む。
コンテナを立ち上げてbgpdを起動し、次にvtysh(FRRのネットワーク設定用シェル)で以下のような設定をする。
(この設定は一例であり、必ずこの設定で正しく動くことを保証するものではない。)

conf te
router bgp 3
no bgp ebgp-requires-policy
yama_filter
bgp router-id 3.3.3.3
neighbor 10.0.2.1 remote-as 2
!
address-family ipv4 unicast
redistribute connected
exit-address-family
!

AS3にてAS2と接続する際の設定である。

yama_filterというのは、bgpのupdateメッセージのPath Attributeに自作path attrを挿入するためのコマンドである。

no bgp ebgp-requires-policy

については、次章のRoute Mapの項を見ていただきたい。

redistribute connected

については、次章のRedistributeの項を見ていただきたい。

BGPあれこれ

BGPの設定をする中で調べたBGP内の概念についていくつか説明する。

Route Map

Route Mapとは、特定のパケットやルートを定義した条件と、その時に実行される処理とで構成されるリストのことである。
経路フィルタや再配布などの条件設定に使われる。
FRRでは基本的にRoute Mapを用いて明示的に広報する/受け取る経路を指定する必要があるが、

no bgp ebgp-requires-policy

とすることで、すべてのフィルタを取り払って動かすこともできる。

Redistribute

BGP以外で手に入れた経路をbgpで流すための設定。
例えば、connectedである経路をBGPで広報したい場合は、

redistribute connected

という設定を入れる。
この情報は、Address Famillyごとに設定する。

Address Familly

MP-BGPでは、IPv4IPv6の複数のプロトコルをサポートすることから、それぞれの経路情報を区別して管理するためのグループであるAddress Famillyを定義している。
以下のような種類がある。

Split Horizon

iBGPピアからの経路情報をiBGPピアに流さないことで、iBGPルートがループするのを防止する。

Route-Reflector

AS内の全ルータをフルメッシュでiBGP接続すると、張らなければいけないピア数が増えすぎる。
そこで、Route-Reflectorと複数のクライアントという関係を結び、eBGPルータは得た経路をRoute-Reflectorのみに流すようにする。
そうすることでクライアントは、Route-ReflectorとさえiBGPピアを張りさえすれば各経路を受け取ることができるようになる。

動作確認

自作Path Attributeを含むBGP updateメッセージのパケットをキャプチャした様子は以下である。

自作Path Attribute

ただ単に文字列を含んでるだけであるが、確かにBGP updateメッセージに乗っている。




おまけ : topotestsの動かし方

FRRでは作った機能を試す際に、topotestsという機能を使うことができる。
利用方法は以下のリンクを参照されたい。

docs.frrouting.org

github.com

help等を見れば、topotestsで立てた仮想ルータに対する各種操作の方法が分かるが、bashに入るときは工夫が必要である。

PID = ` ps aux | grep /bin/cat `
sudo nsenter -t $PID -a bash --norc

筆者は上記のように、nsenterコマンドによってbashに入っていた。


Github

自作Path Attribute
github.com


dockerコンテナでのテスト(tinetを使用)
github.com

MikanOSのUSBブートの方法とmikanos-netの実機での通信実験

概要

MikanOSをUSBブートの方法についてまとめる。
また後半では、mikanos-netのe1000のデバイスドライバが実機でも使えることを確かめる実験を行っている様子を載せてている。

注意

なお、使用するハードウェアによってうまくいったりいかなかったりすします。
この記事に掲載する方法も、すべての環境で動くことを保証するものではありません。
また、この方法を実行してマシンを壊してしまっても筆者は責任を負いかねます。
ご了承ください。



行った環境

Dellのデスクトップを使用した。
CPUはintel製で64ビットである。
(型番は忘れてしまった。)
そこにUSB端子でキーボードとマウスを接続した。


なおPanasonic製のノートパソコンであるLet't noteで試したところ、内臓キーボードとUSBマウスを認識しなかった。

方法

まずマシンのBIOS画面に入り、セキュアブートをOFFにしたのち、UEFIブートの優先順位のトップをUSBブートにする。
そして、USBメモリの適切な場所にブートローダカーネルコード・アプリのコードのバイナリを配置したのちマシンを起動すると、MikanOSが実機で立ち上がる。

コード修正

qiita.com
このサイトを参考に、2箇所の修正を行った。

エントリポイント

メモリマップを確認したところ、kernelのmain関数がロードされるアドレスが予約済みの領域だったため、Makefileを修正した。
kernel/Makefile

#LDFLAGS  += --entry KernelMain -z norelro --image-base 0x100000 --static  
LDFLAGS  += --entry KernelMain -z norelro --image-base 0x110000 --static

USBマウスの認識

上記のサイトを参考にして、以下の点の修正を行った。
詳細はリンクを見てほしい。

kernel/usb/memory.hpp

 // [org] static const size_t kMemoryPoolSize = 4096 * 32
 static const size_t kMemoryPoolSize = 4096 * 64; 

USBメモリへのコピー

上記の点を修正してBuildしたら、次はその内容をUSBメモリに格納する。
一つ一つコマンドを打っていくと長くなるので、シェルスクリプトを利用した。
ゼロからのOS自作入門メモ: 実機で動かすためのメモzenn.dev

このシェルスクリプトは、こちらのブログを執筆されているmaeharinさんからいただいたものを改造して作った。(ありがとうございます。)

大まかな流れとしては、

という流れである。
UEFIの仕様により、ブートローダ/EFI/BOOT/BOOTX64.EFIに配置することとする。
ゼロからのOS自作入門メモ: 第1章

#!/bin/bash

set -ex

#
# usbを差し込んでdmsgコマンドを実行した結果、/dev/sda1になっていることを確認のうえ実行
#/path_to_mikanosのところは、自分の環境のものに置き換える
#
USB=/dev/sda1
KERNEL_ELF=/path_to_mikanos/mikanos/kernel/kernel.elf
LOADER_EFI=$HOME/edk2/Build/MikanLoaderX64/DEBUG_CLANG38/X64/Loader.efi
APPS_DIR_IN_DEV=/path_to_mikanos/mikanos/apps
MNT_DIR=/mnt/usbmem


umount $USB
mkfs.fat $USB
mkdir -p $MNT_DIR
mount $USB $MNT_DIR
mkdir -p $MNT_DIR/EFI/BOOT
cp $KERNEL_ELF $MNT_DIR/kernel.elf
cp $LOADER_EFI $MNT_DIR/EFI/BOOT/BOOTX64.EFI

#アプリをすべてコピー
for APP in $(ls $APPS_DIR_IN_DEV)
do
  if [ -f "$APPS_DIR_IN_DEV/$APP/$APP" ]
  then
    cp "$APPS_DIR_IN_DEV/$APP/$APP" $MNT_DIR
  fi
done
umount $USB

mikanos-netを用いたUbuntuマシンとの通信の実験

MikanOSにNIC であるe1000のデバイスドライバTCP/IPプロトコルを入れたものを、mikanos-netという名前で公開してくださっている方がいらっしゃる。
github.com


このコードを利用して、mikanos-net搭載のマシンとUbuntuマシン間で通信を行う実験を行った。

ソースコードの改変

PCIバスからNICを識別するところで、ベンダIDを指定する部分の処理を省いた。
この操作が必要であるかどうかは、どのマシンを用いて実験するかによると思う。

    for (int i = 0; i < pci::num_device; ++i) {
         //if (pci::ReadVendorId(pci::devices[i]) != 0x8086 || pci::ReadDeviceId(pci::devices[i]) != 0x10d3) {
         if ( !(pci::devices[i].class_code.Match(0x02u, 0x00u, 0x00u))) { //変更箇所
             continue;
         }


加えて、デバイスドライバ内の送信処理の中のbusy waitの部分にデバッグプリントを加えた。
空のwhile文をやめたのだが、なぜこれでうまくいったかは分かっていないが、最適化がかかってbusy waitの部分がバイナリから省かれたのかもしれない。

static ssize_t
e1000_write(struct net_device *dev, const uint8_t *data, size_t len)
{
    struct e1000 *adapter = (struct e1000 *)dev->priv;
    uint32_t tail = e1000_reg_read(adapter, E1000_TDT);
    struct tx_desc *desc = &adapter->tx_ring[tail];
    desc->addr = (uintptr_t)data;
    desc->length = len;
    desc->status = 0;
    desc->cmd = (E1000_TXD_CMD_EOP | E1000_TXD_CMD_RS);
    debugf("%s: %u bytes data transmit", adapter->dev->name, desc->length);
     e1000_reg_write(adapter, E1000_TDT, (tail + 1) % TX_RING_SIZE);
     while(!(desc->status & 0x0f)) {
         // busy wait
         debugf("busy wait");//追加分:ここを抜くと固まる
     }
     return len;
 }

実験

2台のサーバをLANケーブルで繋いだのち、片方にUbuntuをインストールして適当なIPアドレスを設定する。
もう片方にはmikanos-netをUSBブートで立ち上げて、こちらもIPアドレスを設定する。
その後、mikanos-net側でtcp echoサーバを立ち上げ、Ubuntu側からncコマンドで文字列をパケットに乗せて送信する。

TCP echoサーバ(mikanos-net)
クライアント側(Ubuntu)

実機を用いても、e1000のデバイスドライバを通じてパケットのやり取りができることが分かった。

自作TCP/IPスタックをMikanOSへ移植

Klab Expert Camp

Klab Expert Camp は Klab株式会社さんが開催してくださっているインターンで、Linuxカーネル上で動作する自作TCP/IPスタックmicropsのコードを写経・穴埋めしながらTCP/IPについての理解を深めることができるイベントである。
3月に開催された第5回に参加してmicropsの再実装に取り組んだ。

micropsの実装について

上が、micropsの構成を図にしたものである。
本来TCP/IPスタックはOSのカーネル内で動いており、もちろんLinuxでも同じである。
そのLinux上のユーザ空間でプロトコルスタックを動かすために、少し工夫が必要がある。
具体的には、

  • パケットを受け取った際に割り込み処理を行う必要があるが、ユーザ空間のプログラムから割り込みを起こすことはできない。そこでmicropsではSIGNALを送ることで擬似割り込みを起こしている。

のような点が、カーネル内に実装されるTCP/IPスタックとmicropsの実装上の違いとして挙げられる。

またユーザ空間で動くmicropsにはシステムコールという概念は存在しないが、カーネル内のTCP/IPスタックのようにTCPUDPの通信をPCB(Protocol Control Block)で管理しており、ソケット風のAPI関数を用いてmicropsで通信を行うプログラムを書くことができるようになっている。


micropsはすごく簡潔な実装がしてあるプロトコルスタックで、他にも紹介したい点が山ほどあるが、それについては自分が話すより、公開資料 を見ていただくほうがいいだろう。



TCP/IPスタックをMikanOSへ移植


micropsのTCP/IPスタックをMikanOSへ移植する際にすべきことはいくつかあるが、ここでは4つに分けて説明する。
なお、このTCP/IPスタックのMikanOS移植はmicrops作者の方が mikanos-net という名前のリポジトリで行っておられるので、今回はその実装を大いに参考にさせていただいた。

NICの準備とMikanOS用のデバイスドライバの実装

自分はMikanOSをQEMUで動かしていたので、QEMUNICを準備してそのデバイスドライバを実装する必要があった。
今回はE1000という種類のNICを使用する。(E1000はIntelNIC の一種のエミュレート バージョン)
NICの準備とデバイスドライバに関しては、mikanos-netの他に以下の一連のサイトの解説を参考にした。
qiita.com

実装の流れを端的に述べると

  • NICバイスとそのI/Oを扱うための特殊なレジスタを見つけ出す。
  • 送受信の際のバッファ用のメモリ領域を用意する。
  • 特殊レジスタを操作することによる、バッファ用領域を通したNICとの送受信を実現するための関数を用意する。


実装においては、NICの仕様に合うように様々な工夫をする必要があるが、ここではその説明は省略する。
是非上で示したサイトを参照していただきたい。

擬似割り込み処理をMikanOSの割り込みによって行うように変更

MikanOS(や他多くのOS)において、割り込みベクタ(番号)とそれに対応する割り込み記述子をIDT(割り込み記述子テーブル)という形で登録することによって割り込みが実現されている。
割り込み記述子には割り込みハンドラなどを登録する。

よってここで追加する処理は以下のようなものになる

  • NICからの割り込みの番号と割り込みハンドラをIDTに登録

kernel/interrupt.cpp

set_idt_entry(InterruptVector::kE1000, IntHandlerE1000);
  • ハンドラの処理内容は、タスクに通知を送ること

kernel/interrupt.cpp

  __attribute__((interrupt))
  void IntHandlerE1000(InterruptFrame* frame) {
    task_manager->SendMessage(1, Message{Message::kInterruptE1000});
    NotifyEndOfInterrupt();
  }
  • mainタスクはその通知を受け取ったら、NICからデータを読み込む関数を呼び出す

kernel/main.cpp

    case Message::kInterruptE1000:
      e1000_intr();
      break;
ソケット風API関数をシステムコール関数として登録


MikanOSのシステムコールは、アセンブリ言語のsyscall命令でSyscallEntry関数にシステムコール番号を渡すような設定をレジスタに入れておき、SyscallEntry関数で番号に応じた関数を呼び出すことによって行われている。
関数をシステムコールとして登録する際は、syscall_tableという関数ポインタ表にシステムコール番号とその関数へのポインタを登録すればよい。
具体的には、

apps/syscall.asm

define_syscall SocketOpen,       0x80000010
define_syscall SocketClose,      0x80000011
define_syscall SocketIOCTL,      0x80000012

apps/syscall.h

struct SyscallResult SyscallSocketOpen(int domain, int type, int protocol);
struct SyscallResult SyscallSocketClose(int soc);
struct SyscallResult SyscallSocketIOCTL(int soc, int req, void *arg);

kernel/syscall.cpp

SYSCALL(SocketOpen) {
  uint64_t ret = socketopen((int)arg1, (int)arg2, (int)arg3);
  return {ret, 0};
}

SYSCALL(SocketClose) {
  struct socket *s = socketget((int)arg1);
  uint64_t ret = socketclose(s);
  return {ret, 0};
}


SYSCALL(SocketIOCTL) {
  struct socket soc = {0, (int)arg1};
  uint64_t ret = socketioctl(&soc, (int)arg2, (void *)arg3);
  return {ret, 0};
}
  /* 0x10 */ syscall::SocketOpen,
  /* 0x11 */ syscall::SocketClose,
  /* 0x12 */ syscall::SocketIOCTL,

このようなソースコードを付け加えればよい。

その他のLinux特有システムコールを用いた関数(Timer関連,Thread関連等)を置き換え


micropsでは、pthread/mutexやtimerなどLinux系特有のシステムコールを用いた関数(POSIX標準関数など)を利用している。
当然自作OSのプログラムではそれらの関数を使用することはできないので、代わりとなる関数を自分で用意する必要がある。

下の例のように、POSIXの関数を同名でMikanOS内のタイマーを用いる関数として定義し直している。

net/port/mikanos.cpp

int
gettimeofday(struct timeval *tv, void *tz)
{
    unsigned long tick = timer_manager->CurrentTick();

    tv->tv_sec = tick / kTimerFreq;
    tv->tv_usec = tick % kTimerFreq * (1000000 / kTimerFreq);
    return 0;
}


mikados-netではmutex_lock/unlockなどのMikanOSに機能のない関数は空の関数として定義している。
続編のブログでは、mutex_lock関数の中身を自作spin_lockに置き換えるまでの作業内容を書いている。

ソースコードは以下の中にある。
https://github.com/yushoyamaguchi/mikanos_sub1github.com

c言語でNAT自作 [実機で動作確認]

やったこと

  • jsonファイルの設定をcのプログラムから読み込めるようにする。
  • jsonファイル形式で書き込んだルーティングテーブルの内容を読みこんで、それを基にパケットフォワーディングできるようにする
  • NATを作る

jsonの読み取り

janssonというライブラリを使用すると、jsonファイルの内容を関数一つで構造体に取り出せるようになる。
qiita.com

簡易ルーティングテーブルの読み取り

元のルーターにはルーティングテーブルという概念がなく、デフォルトゲートウェイまたは直に繋がっているサブネットにしか送信できないものだったので、ルーティングテーブルを基にパケットフォワーディングをできるようにした。
本来はCLIでルーティングテーブルの要素の追加や削除を行えるようにするのがよいが、時間がないので今回はルーティングテーブルの情報はあらかじめすべてjsonファイルに書いておいて、それをプログラムから読むという仕様にした。
次のような記法で、ネットワークインターフェースとルーティングテーブルの中身のリストを記述する。

{
    "interfaces":[
        "net0",
        "net1",
        "net2"
    ],
    "routing_table":[
        {
            "dest_addr":"10.1.0.0",
            "subnet_mask":"16",
            "next_hop":"10.2.23.2"
        },
        {
            "dest_addr":"10.1.14.0",
            "subnet_mask":"24",
            "next_hop":"10.2.24.2"
        }
    ]
}

データ構造

ルーティングテーブルのデータ構造として、Radix Tree を採用する。
ja.tech.jar.jp
テーブルをRadix Tree にすると、宛先の情報・サブネットの情報・ネクストホップの情報をその構造自体に内包することができるため、木の探索を行うだけで最長一致によるフォワード先の決定ができる。

struct node  {
        struct node      *parent;
        struct node      *child[2];
        u_int32_t       daddr_subnet;
        u_int8_t        subnet_mask;
        u_int32_t       next_hop;
        u_int32_t       daddr_full;
        int             is_empty;
        int             is_root;
};

処理内容と難しかったポイント

アドレス、サブネットアドレス、サブネットマスクに関する計算する部分を実装するのが一番手間がかかった。
ノードの最長一致での探索は、マスクを一つずつシフトしながら一致するものがないか見てゆく。
今回はシフト処理がうまく書けなかったので、サブネットマスクにあたる数字(0~32)をインクリメントしていき、その数字をネットバイトオーダのマスクに変換する関数に渡している。
この際バイトオーダに注意が必要である。
ノードのroot(サブネットマスク0)からチェックしていき、サブネットが一致するものが見つかったらそれを保存したのち、さらに長いサブネットを持つものと一致しないか探しに木を下ってゆく。
ノードの挿入においては、挿入する本体の親がいないと探索の時に困るため、ダミーノードを作ることで対応した。

NAT機能実装

データ構造

LAN側とWAN側の5tuple(src addr / port , dest addr / port , protocol)を対応づけたものをNATテーブルの要素とする。
またその他にも、現在払い出しているポート番号の情報などもNATテーブルにて保持する。

struct nat_table{
    struct nat_table_element *start;
    struct nat_table_element *end;
    int     num;
    int     used_port[MAX_TABLE_SIZE];
    int     last_gave_port;
};

struct nat_table_element{
    struct  nat_table_element *prev;
    struct  nat_table_element *next;
    struct  five_tuple  *loc_tpl;
    struct  five_tuple  *glo_tpl;
    u_int8_t     protocol;
    time_t      last_time;
    int         is_tcp_estab;
    int         tcp_state;
};

struct five_tuple{
    u_int32_t   src_addr;
    u_int16_t   src_port;
    u_int32_t   dst_addr;
    u_int16_t   dst_port;
    u_int8_t    protocol;
};

処理

パケットの宛先port,addrと送信元port,addrとプロトコルの5つを識別要素として通信の単位を構成し、LAN側からのパケットにその単位ごとにWANでの送信元portを割り振り、パケットを書き換える。
WAN側からのパケットを受け取ったらNATテーブルを参照し、宛先を然るべきLAN側のport,addrに書き換える。

難しかったポイント

ポートの概念がないICMPパケットに関しては、ICMPヘッダに含まれるicmp idをport代わりに識別子として使わなければならないことに気づくまでに時間がかかった。
また、TCPUDPチェックサムには擬似ヘッダを用いなければならない点などは、事前知識として知ってなければならないだろう。

実験

ネットワークシミュレーションツールのtinet を用いてNATの動作確認を行ったので、その様子を載せる。

上記のようなネットワークを組んでc2からr1にpingを飛ばし、r1でパケットキャプチャを行った。
結果は以下の通り。

r2でNATが行われた結果、r1では10.255.1.2(r2)からパケットが飛んできているように見えている。

実機で実験

一方のNICグローバルIPを持ち、もう片方のNICはLANのアドレスをもつUbuntuマシンで動作確認を行った。

ICMP

きちんとNATの役割を果たした。

NATプログラム起動前後のping疎通の様子

TCP

帰りのパケットが壊れてしまう現象に見舞われた。

TCPパケットが壊れて帰ってくる様子

コンテナ上で動く簡易BGPソフトウェアをc言語で実装した話 [SecCamp2021]

セキュリティキャンプ2021のZ4トラックでBGPルーターのサブセットを自作したときのメモを書いていきます。
僕がこれを曲がりなりにも作ることができたのは、講師の城倉さんと齋藤さんの手厚いサポートのおかげです。本当にありがとうございました。

概要

FRRoutingというソフトウェアルータとBGPでのやりとりができるプログラムをLinux上で開発しました。
開発はC言語で行いました。
実装の都合上、1つのピアとしか繋がれなくて再接続もできないものです。
他にも経路情報の取り消しができなかったり、4バイトASに対応していなかったりと、必要な機能が全然備わっていませんが許してください。

BGPのしくみ

www.infraexpert.com
この通りBGPピアは状態遷移を行いながら、それに合わせた種類のパケットを送り合うことで繋がりを保ちながら必要な経路情報をやり取りします。

この部分をswitch文を利用しました。

void bgp_process(struct BGP *bgp,struct Peer *p,char *bgp_msg,int sock) {
	switch (p->state) {
		case OpenSent:
                         bgp_process_open_sent(p, bgp_msg,sock);
			break;
                case OpenConfirm:
                         bgp_process_open_confirm(bgp,p, bgp_msg,sock);
			break;
                case Established:
			bgp_process_established(bgp,p, bgp_msg,sock);
			break;
		default:
			break;
	}
}

繋がりが切れたときの再接続や複数台とピアを張ることを考えていないので、だいぶ簡素な作りになっています。(真似しないでね)

BGPパケットを作り込む

BGPのパケットの構造を掴むためにRFCなどやその解説書とかを読むのもいいですが、大枠を知るためには実際のBGPのやり取りをパケットキャプチャして観察するのが早いです。

BGPのパケットの中身

このような中身のパケットを送れるようにプログラムを作っていきます。
BGPはTCPの上で動くプロトコルなので、TCPソケットを作ってそこにBGPメッセージに相当するバイナリ列を送ればよいです。

struct bgp_update
  {
    uint8_t marker[16];
    uint16_t len;
    uint8_t type;
    uint16_t withdrawn_len;
    uint8_t contents[64];
  }__attribute__((__packed__));  

パケットの中身をこのような構造体で埋めていきます。(これはupdateメッセージに相当する構造体です。)

packedをつけておかないとコンパイルの過程で構造体が意図しない形に変わってしまうので注意が必要です。
また、ビッグエンディアンとリトルエンディアンの違いにも要注意です。
1バイト(8bit)を超える大きさの数値のビット演算をする際には必ず意識する必要があります。

configファイルの読み込み

今回はBGPのルーターIDやAS番号などをjsonファイルで与えます。
jsonの読み込みにはjanssonというライブラリを使用しました。

ベストパスセレクション

ピアから広告された経路情報はリストにして保持してます。
本来は木構造にするのが鉄則ですが、これも僕の実装力不足です。
そしてそのリストをチェックして、一番経由するASパスが短い経路をベストパスにするというアルゴリズムを実装しました。
この選んだパスの情報(宛先とネクストホップ)を、route addコマンドを用いてルーティングテーブルに反映するようにしています。

まとめ

githubソースコードを載せています。
https://github.com/yushoyamaguchi/bgp1/tree/main/dev5

ちなみにこのBGPのサブセットのプログラムは実際にインターネット上では動かすことができません。
(僕の怠慢です、ごめんなさい。)

tinetというネットワークシュミレーションツール上で動かしながら実装をしました。