Linuxにシステムコールとスケジューラを追加してみた
はじめに（文責：灘）
この記事では、
Linuxに
- システムコール
- スケジューラ
を追加した手順について、できる限り詳細に（読んだ人が再現できるくらいに）解説する。
PCの環境
- ubuntu18
- 結局仮想マシン内で作業するので、virtualboxが入ったPCなら何でもOK
環境構築（文責 菊岡）
何はともあれ、まずは環境構築から始める。今回はlinuxのソースコードをいじることになるのだが、最終的にいじったソースコードを実際に動かすための環境が必要になる。お持ちのパソコンがMacやWindowsの方はもちろん、linuxであっても本体のソースコードを勝手に変更して、動作がおかしくなっては目も当てられないので、仮想マシン上でlinuxを動かすことにする。
準備
まずは仮想マシンを走らせるための準備として、VirtualBoxとVagrantをインストールする。なお、全体を通して、特に記載がなければ参考にしたのはこのサイトである。少し変更点はあるが、概ねこの手順に従っておけば問題ない。最終的に、変更したソースコードを反映させて動かすマシン（以下debuggeeと呼ぶ）と、debuggeeにデバッグをかけるマシン（以下debuggerと呼ぶ）の二つを作成することになる。以下で詳しく説明していく。
VirtualBoxのインストール
この部分に関しては、このサイトを参考にしている。英語のサイトだが、Method 3の部分を見てもらうか、面倒なら下の説明を見てもらえば良い。
まず、以下のコマンドによりVirtualBox用の公開鍵を追加する。
~$ wget -q https://www.virtualbox.org/download/oracle_vbox_2016.asc -O- | sudo apt-key add -
続いて、以下のコマンドでVirtualBoxのレポジトリに接続できるようにする。
~$ sudo add-apt-repository "deb [arch=amd64] http://download.virtualbox.org/virtualbox/debian $(lsb_release -cs) contrib"
以下のコマンドでVirtualBoxを実際にインストールできる。
~$ sudo apt update && sudo apt install virtualbox-6.0
Vagrantのインストール
まず、以下のコマンドでパッケージファイルをダウンロードする。この際手持ちの環境に応じてコマンドが異なるので注意する。班員全員がx86系統のマシンを使っていたため、下のコマンドはそれに合わせたものとなっている。
~$ wget https://releases.hashicorp.com/vagrant/2.2.6/vagrant_2.2.6_x86_64.deb
以下のコマンドで、先ほどダウンロードしたパッケージファイルからVagrantをインストールする。
~$ sudo dpkg -i vagrant_2.2.6_x86_64.deb
なお、コマンドを見るとわかる通り、今回インストールするバージョンは、VirtualBoxが6.0、Vagrantが2.2.6となっているが、どちらかが新しすぎると、もう片方がそれに対応しておらず、正常に動作しないケースがあるので、特に理由がなければこのバージョンに揃えることをおすすめする。
仮想マシンの作成
いよいよ仮想マシンを作成する。そのために以下のコマンドで、作業を進めるディレクトリを作成しその中に入る。
~$ mkdir -p ~/Vagrant/ubuntu18
~$ cd Vagrant/ubuntu18
Vagrantを初期化する。このときVagrantfileというVagrantの設定ファイルが生成される。
~/Vagrant/ubuntu18$ vagrant init ubuntu/bionic64
このファイルを修正するのだが、その前に、仮想マシンの容量を増やすために必要なプラグインをインストールする。
~$ vagrant plugin install vagrant-disksize
これにより、Vagrantfileに適切な記述をすることで、容量を増やすことができるようになる。これをしないと、仮想マシンを立ち上げたあと容量不足でエラーを起こす可能性があるので注意する。
生成されたVagrantfileを開き、以下のように修正する。
Vagrant.configure("2") do |config|
config.vm.box = "ubuntu/bionic64"
config.vm.define "debugger" do |c|
c.vm.provider "virtualbox" do |vb|
vb.customize ["modifyvm", :id, "--uart2", "0x2F8", "3"]
vb.customize ["modifyvm", :id, "--uartmode2", "server", "/tmp/vagrant-ttyS1"]
vb.memory = "8192"
end
end
config.vm.define "debuggee" do |c|
c.vm.provider "virtualbox" do |vb|
vb.customize ["modifyvm", :id, "--uart2", "0x2F8", "3"]
vb.customize ["modifyvm", :id, "--uartmode2", "client", "/tmp/vagrant-ttyS1"]
end
end
config.disksize.size = '100GB'
end
いよいよ仮想マシンを起動する。以下のコマンドで仮想マシンを起動する。
~/Vagrant/ubuntu18$ vagrant up
debuggerとdebuggeeが両方問題なく起動したら、以下のコマンドを入力し、ターミナルでdebuggeeを開く。
~/Vagrant/ubuntu18$ vagrant ssh debuggee
以下のコマンドでdebuggeeの設定を追加する。
debuggee:~$ sudo systemctl enable serial-getty@ttyS1.service
以下のコマンドで仮想マシンを再起動する。
~/Vagrant/ubuntu18$ vagrant reload
今度はdebuggerを開き、シリアル通信ができるか確認する。
debugger:~$ sudo screen /dev/ttyS1
<ENTRYを押下>
Ubuntu 18.04.3 LTS ubuntu-bionic ttyS1
ubuntu-bionic login:
kgdbの設定
ここまでで仮想マシンを起動できるようになったが、このままではデバッグをすることが難しいので、カーネルを再ビルドして、kgdbに対応させる。
以下のコマンドで、debuggerにカーネルの開発環境を構築する。
debugger:~$ sudo apt-get install git build-essential kernel-package fakeroot libncurses5-dev libssl-dev ccache bison flex gdb
続いて、debuggerのホームディレクトリのカーネルのソースコードをダウンロードする。今回はバージョン5.3.9を対象とする。
debugger:~$ wget https://cdn.kernel.org/pub/linux/kernel/v5.x/linux-5.3.9.tar.xz
ダウンロードファイルを解凍する。
debugger:~$ tar Jxfv ./linux-5.3.9.tar.xz
生成されたディレクトリに入り、コンフィグの設定をする。
debugger:~$ cd linux-5.3.9
debugger:~/linux-5.3.9$ cp /boot/config-`uname -r` .config
debugger:~/linux-5.3.9$ yes '' | make oldconfig
debugger:~/linux-5.3.9$ make menuconfig
コンフィグ設定画面が開くので、以下の項目を探し、はじめの５つはチェックをつけ、最後の１つはチェックを外す。
Kernel hacking -> [*]KGDB: kernel debugger
Kernel hacking -> KGDB: kernel debugger -> [*]KGDB: use kgdb over the serial console
Kernel hacking -> KGDB: kernel debugger -> [*]KGDB: internal test suite
Kernel hacking -> KGDB: kernel debugger -> [*]KGDB: Allow debugging with traps in notifiers
Kernel hacking -> KGDB: kernel debugger -> [*]KGDB_KDB: include kdb frontend for kgdb
Processor type and features -> [ ]Randomize the address of the kernel image (KASLR)
カーネルのソースコードをビルドする。使ってるパソコンによるが、平気で数時間はかかるので、しばらくお休みしてパソコンに頑張ってもらおう。
debugger:~/linux-5.3.9$ make clean
debugger:~/linux-5.3.9$ make -j `getconf _NPROCESSORS_ONLN` deb-pkg
ビルドにより生成されたパッケージをdebuggeeに共有する。/vagrantのパスで指定されるディレクトリが、共有フォルダとして設定されていることを利用し、一度パッケージをそこに移す。
debugger:~/linux-5.3.9$ mv ../linux-headers-5.3.9_5.3.9-1_amd64.deb /vagrant
debugger:~/linux-5.3.9$ mv ../linux-libc-dev_5.3.9-1_amd64.deb /vagrant
debugger:~/linux-5.3.9$ mv ../linux-image-5.3.9_5.3.9-1_amd64.deb /vagrant
debugger:~/linux-5.3.9$ mv ../linux-image-5.3.9-dbg_5.3.9-1_amd64.deb /vagrant
debuggeeを開き、先程共有したパッケージをインストールする。
debuggee:~$ sudo dpkg -i /vagrant/linux-headers-5.3.9_5.3.9-1_amd64.deb
debuggee:~$ sudo dpkg -i /vagrant/linux-libc-dev_5.3.9-1_amd64.deb
debuggee:~$ sudo dpkg -i /vagrant/linux-image-5.3.9_5.3.9-1_amd64.deb
debuggee:~$ sudo dpkg -i /vagrant/linux-image-5.3.9-dbg_5.3.9-1_amd64.deb
これで、kdgbを用いてデバッグすることができるようになった。なお、一度新しいパッケージをインストールした際は、仮想マシンを再起動することをおすすめする。正常にkdgbが動かなかったり、カーネルの動作自体に問題が生じることがあるためである。
また、VSCodeのRemote-SSHという拡張をインストールすると、仮想マシン内のファイルをVSCodeで編集することが可能になるため、VSCodeに慣れている人や宗教上の理由でvimを使えない人は試してみるといいだろう。
ここまでで、linuxのソースコードに変更を加えて、実際に動かすための、環境が整ったことになる。それでは、ここから実際にソースコードをいじっていこう。
新しいシステムコールを作ってみよう（文責: 菊岡）
見出しの通り、新しいシステムコールを追加し、実際に呼び出して動作を確認することが目標とする。システムコールとは、オペレーティングシステム（のカーネル）の機能を、プログラム中で呼び出すために使う機能のことである。ファイルの入出力や、ネットワークを利用した通信などがシステムコールとして実装されているが、今回新たに追加するのは、整数の引数を二つ取ってそれを足し合わせるだけの簡単なものとする。実装の際にはこちらのサイトが韓国語だがとても参考になった。以下で手順を説明する。
システムコールの追加
まず、linuxソースコード内で、arch/x86/entry/syscalls/syscall_64.tblで指定されるファイルを探そう。そこには、現在のバージョンで実装されているシステムコールが、一覧表形式でずらりと並べられていることと思う。
ここの空いている番号に、自分たちが追加したいシステムコールを書き足してしまえばいいことになる。すでに書かれている他のシステムコールの書き方を真似ると、このようになる。
548 64 mycall __x64_sys_mycall
548番にあるmycallなるシステムコールこそ、我々が追加するシステムコールである。もちろんこのままでは、表に名前が乗っただけで実体が何もないため動かない。
次に、_include/linux/syscalls.h_で指定されるファイルを見に行こう。そこでは、実装されているシステムコールの型の宣言がされていることだろう。
ここの関数名は、先程の一覧表に追加した四列目の、x64以下の部分に当たる。よって、適当な位置に、sys_mycallの型を宣言してやればいい。
asmlinkage long sys_mycall(int a,int b, int *to_user);
a、bは足し算を行う二変数で、to_userという引数にはシステムコールの呼び出し元の情報が入り、カーネルが行った計算結果を引き渡すために必要となる。
宣言をしたら、いよいよ実体を定義していく。_kernel_というディレクトリ内にmycall.c(名前は何でも良いが)というファイルを作り、そこに関数を定義する。
# include <linux/kernel.h>
# include <linux/syscalls.h>
# include <asm/processor.h>
# include <asm/uaccess.h>
SYSCALL_DEFINE3(mycall, int, a, int, b, int *, to_user)
{
int sum = 0;
printk("[Kernel Message] a = %d, b = %d\n", a, b);
sum = a + b;
put_user(sum, to_user);
return 21;
}
SYSCALL_DEFINEとは、システムコールを定義する際に用いるマクロであり、宣言の際の引数の数を後ろに添えて用いる。今回は引数３つであったため、SYSCALL_DEFINE3となる。実際の引数は、システムコールの番号を第一引数に指定するため、その数字よりも１つ多くなる。また、実際にシステムコールを呼び出すときは、マクロではなく、システムコール名mycallで呼び出すことになる。なお引数0の場合は、宣言のときと同様asmlinkageを用いるとのことである。
これでようやく実体の定義も終わり、あとはカーネルを正しくビルドすればmycallが使えるようになるはずである。
実際に使ってみよう
mycallの動作確認をする。そのためにはもう一度カーネルのビルドをする必要があるが、このままではmycall.cをビルドの際に反映させられないため、Makefileに少々追記しておく。
obj-y = fork.o exec_domain.o panic.o \
.................................................
mycall.o
その上でもう一度ビルドし、debuggeeでパッケージをインストールして再起動まですれば、新たなシステムコールが使えるようになる。
試しにテストコードを走らせてみよう。
このコードをコンパイルして実行すると以下のように出力される。
sumの値として正しい計算結果が出力され、retの値としてmycallの返り値である21が出力されており、正しくシステムコールが呼び出されているのがわかる。
またdmesgコマンドでカーネルメッセージを呼び出してみる。
最後尾にカーネルメッセージとしてa、bの値が出力されており、カーネルに正しく値を渡せていることがわかる。
スケジューリングクラスを作ろう(文責：チェ・ジェヒョン)
アルゴリズムの実装
ランダムスケジューリングとは
ランダムスケジューリングは、CPUから次のタスクを選ぶときに、待機のタスクの中でランダムに選ぶ方法を示す。
ランダムランキューの実装
struct random_rq{
struct list_head task_list;
unsigned int random_nr_running;
int random_queued;
int random_throttled;
u64 random_time;
u64 random_runtime;
};
list_headの説明
list_headはLinuxのソースコードのなかで連結リストのデータ構造を実装したもので、(linuxのソースコードディレクトリ)/tools/include/linux/types.hに書いてある。
struct list_head {
struct list_head *next, *prev;
};
一般に連結リストを使うときにはデータの構造体の中にその構造体のポインタを使ってnextとprevを示す。(次のコードを参照）
struct linked_list{
int data; //データ
struct linked_list *next, *prev; //構造体のポインタ
}
しかし、list_headはデータの構造体にlist_headの変数を追加することで連結リストを実装する。(次のコードを参照）
struct linked_list{
int data; //データ
struct list_head list; //連結リスト
}
では、list_headはどのように要素(ノード)をつなぐかを見ると、次のような関数を使う。( (linuxのソースコードディレクトリ)/include/linux/list.hに書いてある）
- INIT_LIST_HEAD
- list_add & list_add_tail
- list_del & list_del_init
INIT_LIST_HEADはlist_headのnextとprevを自分自身になるようにすることで、list_headの初期化をする。
static inline void INIT_LIST_HEAD(struct list_head *list)
{
WRITE_ONCE(list->next, list);
list->prev = list;
}
図を見ると、次のようになり、双方向循環リストができる。
list_addとlist_add_tailは連結リストに要素を追加する関数で、引数としてリストの先頭となるheadのポインタと追加したい要素のポインタを受ける。
static inline void __list_add(struct list_head *new,
struct list_head *prev,
struct list_head *next)
{
if (!__list_add_valid(new, prev, next))
return;
next->prev = new;
new->next = next;
new->prev = prev;
WRITE_ONCE(prev->next, new);
}
static inline void list_add(struct list_head *new, struct list_head *head)
{
__list_add(new, head, head->next);
}
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
__list_add(new, head->prev, head);
}
list_addとlist_add_tailのコアとなる関数は__list_addで、prevとnextの中にnewを入れることである。list_addとlist_add_tailの違いは先頭であるheadとheadの次の要素になるhead->nextの中にnewを入れるか、headとheadの前の要素になるhead->prevの中にnewを入れるかである。結局list_addはリストの最初に要素を入れて、list_add_tailはリストの最後に要素を入れる。
list_delとlist_del_initは連結リストから要素を外すときに使う関数である。
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
next->prev = prev;
WRITE_ONCE(prev->next, next);
}
static inline void __list_del_entry(struct list_head *entry)
{
if (!__list_del_entry_valid(entry))
return;
__list_del(entry->prev, entry->next);
}
static inline void list_del(struct list_head *entry)
{
__list_del_entry(entry);
entry->next = LIST_POISON1;
entry->prev = LIST_POISON2;
}
static inline void list_del_init(struct list_head *entry)
{
__list_del_entry(entry);
INIT_LIST_HEAD(entry);
}
list_delとlist_del_initの違いは外す要素のnextとprev変数をどうするかにある。list_delはそのデータを意味がないポインタにするが、list_del_initは自分自身にする。(LIST_POISONの説明：https://lists.kernelnewbies.org/pipermail/kernelnewbies/2016-March/015879.html)
random_rqではランダムスケジューリングで扱うタスクのリストを実装するためlist_headを使い、そこで任意の乱数n(扱うタスクの吸うより小さい整数)番目のタスクを選べる必要があった。そのため、リストを巡回するマクロであるlist_for_eachを使った。
# define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
単純に先頭の次の要素から始まり、先頭になるまでに繰り返すことである。
ここまでにすると、連結リストの部分は全部実装したが、連結リスト(list_head)は実際にデータを持たないので、list_for_eachでn番目の要素を求めたとしても、そのn番目の要素が持つデータは分からない状態である。そのデータを求めるため、Linuxではlist_entryというマクロを使う。(/include/linux/list.hに書いてある)
# define list_entry(ptr, type, member) \
container_of(ptr, type, member)
container_ofマクロは次のようになる。(/include/linux/kernel.hに書いてある)
# define container_of(ptr, type, member) ({ \
void *__mptr = (void *)(ptr); \
BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) && \
!__same_type(*(ptr), void), \
"pointer type mismatch in container_of()"); \
((type *)(__mptr - offsetof(type, member))); })
offsetofマクロは次のようになる。
# define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
詳しい説明はhttps://stackoverflow.com/questions/5550404/list-entry-in-linux に書いてあるけど、簡単に説明するとlist_headのポインタptr、求めたいデータがある構造体のタイプtype(上の例によるとstruct linked_list)、求めたいデータがある構造体でlist_headの変数名member(上の例によるとlist)を引数として受けて、求めたい構造体の始まりからlist_headまでのバイト数を計算し(offsetofの役割)list_headのポインタからそれを引くことで求めたいデータがある構造体のポインタを求める。図にしめすと次のようになる。
各関数の実装
スケジューラに必要である関数の中に実際に実装した部分は次のようになる。(参照：https://trepo.tuni.fi/bitstream/handle/10024/96864/GRADU-1428493916.pdf , p.27 ~ p.28)
- enqueue_task
- dequeue_task
- yield_task
-
check_preempt_curr - pick_next_task
- put_prev_task
-
set_curr_task - task_tick
-
task_fork -
prio_changed -
switched_from -
switched_to -
update_curr
enqueue_task
static void enqueue_task_random(struct rq *rq, struct task_struct *p, int flags){
enqueue_list(&rq->rd_rq,p,flags);
add_nr_running(rq,1);
rq->rd_rq.random_nr_running++;
}
ここでenqueue_listは次のようになる。
void enqueue_list(struct random_rq *rd_rq,struct task_struct *p, int flags){
INIT_LIST_HEAD(&p->rd_list);
list_add_tail(&p->rd_list,&rd_rq->task_list);
}
dequeue_task
static void dequeue_task_random(struct rq *rq, struct task_struct *p, int flags){
dequeue_list(&rq->rd_rq,p,flags);
sub_nr_running(rq,1);
rq->rd_rq.random_nr_running--;
}
ここでdequeue_listは次のようになる。
void dequeue_list(struct random_rq *rd_rq,struct task_struct *p, int flags){
list_del_init(&p->rd_list);
}
yield_task
static void yield_task_random(struct rq *rq){
struct task_struct *p = rq->curr; //TODO
dequeue_list(&rq->rd_rq,p,0);
enqueue_list(&rq->rd_rq,p,0);
}
yield_task関数は現在のタスクを取り出してリストの末に移動することで実装出きるので、dequeue_listから現在のタスクpを取り出し、enqueue_listからそれを再びリストの末に入れる。
pick_next_task
static struct task_struct * pick_next_task_random(struct rq *rq, struct task_struct *prev, struct rq_flags *rf){
put_prev_task(rq,prev);
struct task_struct *p;
struct random_rq *rd_rq= &rq->rd_rq;
p = pick_random_entity(rd_rq);
return p;
}
pick_random_entity関数の実装は次のようになる。
static struct task_struct* pick_random_entity(struct random_rq *random_rq){ //Pick one task randomly -> return p
struct task_struct *p;
unsigned long random_val;
unsigned long cnt;
struct list_head *ptr;
if(random_rq->random_nr_running){
random_val = 0UL;
get_random_bytes(&random_val,sizeof(unsigned long));
random_val = random_val%(random_rq->random_nr_running);
cnt = 0UL;
list_for_each(ptr,&random_rq->task_list){
if(cnt==random_val){
p = list_entry(ptr,struct task_struct,rd_list);
return p;
}
cnt++;
}
}
return NULL;
}
get_random_bytes関数を用い、random_valに乱数を入れて、それをランダムランキューに入っているタスクの数に割って残るあまりにすることで求めたい乱数nを計算する。その後、list_for_eachとlist_entryを使ってタスクpを求める。
put_prev_task
static void put_prev_task_random(struct rq *rq, struct task_struct *p){
enqueue_list(&rq->rd_rq,p,0);
}
put_prev_taskはランキューで作業したタスクをランキューリストの末に入れることである。
task_tick
static void task_tick_random(struct rq *rq, struct task_struct *p, int queued){
if(!queued){
resched_curr(rq);
}
return;
}
task_tickは指定された時間ぶりに呼ばれる関数で、ランダムスケジューラはタスクの待機時間や終了時間などの計算が必要ないのでreschedulingすることだけ行う。
実装したスケジューラを使わせる（文責： 灘）
次に、上で実装したスケジューラクラスが実際に使われるようにする。
ここでは主にkernel/sched/core.c（以下、core.cと省略）をいじることになる。
プロセス（厳密にはtask_struct）にスケジューラを割り振る
// kernel/sched/core.c
int sched_fork(...){
(中略)
if (dl_prio(p->prio))
return -EAGAIN;
else if (rt_prio(p->prio))
p->sched_class = &rt_sched_class;
else
p->sched_class = &fair_sched_class;
(略)
}
static void __setscheduler(struct rq *rq, struct task_struct *p,
const struct sched_attr *attr, bool keep_boost)
(中略)
if (dl_prio(p->prio))
p->sched_class = &dl_sched_class;
else if (rt_prio(p->prio))
p->sched_class = &rt_sched_class;
else
p->sched_class = &fair_sched_class;
(略)
}
スケジューラクラスがどのようにしてカーネルで扱われているのかを調べるために、他のスケジューラクラス
rt_sched_class, fair_sched_classなどをGNU globalで探すと、core.c内の上記箇所がヒットする。
おそらく、ここに私達のランダムスケジューラに関する処理を加えればよいのだろう。
調べてみると、{スケジューラ名}_prioという関数(rt_prio, dl_prio...)は、{スケジューラ名}.hというファイルで定義されている。
試しにdl_prioの実装を見ると、task_struct（プロセス）の優先度(p->prio)を受け取って, スケジューラの担当する優先度の範囲なら1を返し、そうでない場合は0を返すようだ。
例：dl_prioの実装
// include/linux/sched/deadline.h
# define MAX_DL_PRIO 0
static inline int dl_prio(int prio)
{
if (unlikely(prio < MAX_DL_PRIO))
return 1;
return 0;
}
これに倣って、rd_prioという関数をランダムスケジューラのヘッダファイルinclude/linux/sched/random_sched.hに実装する。
// include/linux/sched/random_sched.h
static inline int rd_prio(int prio)
{
if (121 <= prio && prio <= 139)
return 1;
return 0;
}
ここでは、優先度が121 ~ 139の範囲のプロセスに対して1を返すものとした。
この関数を使って、core.cを以下のように書き換える。
// kernel/sched/core.c
int sched_fork(...){
(中略)
if (dl_prio(p->prio))
return -EAGAIN;
else if (rt_prio(p->prio))
p->sched_class = &rt_sched_class;
else if (rd_prio(p->prio)) // Added this line
p->sched_class = &random_sched_class;
else
p->sched_class = &fair_sched_class;
(略)
}
static void __setscheduler(struct rq *rq, struct task_struct *p,
const struct sched_attr *attr, bool keep_boost)
(中略)
if (dl_prio(p->prio))
p->sched_class = &dl_sched_class;
else if (rt_prio(p->prio))
p->sched_class = &rt_sched_class;
else if (rd_prio(p->prio)) // Added this line
p->sched_class = &random_sched_class;
else
p->sched_class = &fair_sched_class;
(略)
}
これで、タスクがプロセスへ割り当てられるようになった。
ただし、新たに作ったrandom_sched.hファイルをcore.cにincludeする必要がある。
ここでも、他のスケジューラの実装に倣って、kernel/sched/sched.hのinclude文がまとまっている箇所に
#include <linux/sched/random_sched.h> を追記した。core.cはkernel/sched/sched.hをincludeするので、これでcore.cからrandom_sched.h内の関数を使えるようになった。
Policy関数の実装
スケジューラ一般のヘッダファイルkenel/sched/sched.h内を見ていくと、
static inline int idle_policy(int policy)
{
return policy == SCHED_IDLE;
}
static inline int fair_policy(int policy)
{
return policy == SCHED_NORMAL || policy == SCHED_BATCH;
}
static inline int rt_policy(int policy)
{（中略）}
static inline int dl_policy(int policy)
{ （中略）}
static inline bool valid_policy(int policy)
{
return idle_policy(policy) || fair_policy(policy) ||
rt_policy(policy) || dl_policy(policy);
}
という関数が定義されているのを発見した。おそらく、valid_policy関数でスケジューラが適切に指定されているのかを調べているものだと当たりがつけられる。
そこで、ランダムスケジューラもこれに倣って、以下のように
// Added this function
static inline int random_policy(int policy)
{
return policy == SCHED_RANDOM;
}
static inline bool valid_policy(int policy)
{
return idle_policy(policy) || fair_policy(policy) ||
rt_policy(policy) || dl_policy(policy) || random_policy(policy); // Fixed this line
}
random_policyという関数を実装し、valid_policyの中に入れた。
ここででてくるSCHED_RANDOMという定数値は、他のSCHED_NORMAL, SCHED_IDLEといった定数値にならい、include/uapi/sched.hの中で
# define SCHED_NORMAL 0
# define SCHED_FIFO 1
# define SCHED_RR 2
# define SCHED_BATCH 3
/* SCHED_ISO: reserved but not implemented yet */
# define SCHED_IDLE 5
# define SCHED_DEADLINE 6
# define SCHED_RANDOM 7
と定義した。
実行結果とデバッギング(Debugging) （文責：チェ・ジェヒョン）
まずはhttps://leavatail.hatenablog.com/entry/2019/11/04/235300 のビルド環境と同様にして、ビルドした結果、Linuxを起動するときに次のようなエラーが発生した。vagrantのフォルダ(/Vagrant/ubuntu18)ではカーネルのメッセージ(printkで出力されたもの)が書いてあるログがある。(ubuntu-bionic-18.04-cloudimg-console.log) そこでLinuxが動けないようになる理由を確認できた。
エラーログ
[ 28.333395] watchdog: BUG: soft lockup - CPU#2 stuck for 22s! [kworker/2:1:88]
[ 28.333395] Modules linked in:
[ 28.333395] CPU: 2 PID: 88 Comm: kworker/2:1 Not tainted 5.3.9+ #1
[ 28.333395] Hardware name: innotek GmbH VirtualBox/VirtualBox, BIOS VirtualBox 12/01/2006
[ 28.333395] Workqueue: events timer_update_keys
[ 28.333395] RIP: 0010:smp_call_function_many+0x239/0x270
[ 28.333395] Code: 08 89 c7 e8 e9 f7 90 00 3b 05 77 a8 70 01 0f 83 5c fe ff ff 48 63 c8 48 8b 13 48 03 14 cd 00 a9 3d 82 8b 4a 18 83 e1 01 74 0a <f3> 90 8b 4a 18 83 e1 01 75 f6 eb c7 0f 0b e9 0b fe ff ff 48 c7 c2
[ 28.333395] RSP: 0018:ffffc9000028bd08 EFLAGS: 00000202 ORIG_RAX: ffffffffffffff13
[ 28.333395] RAX: 0000000000000000 RBX: ffff88803eaab500 RCX: 0000000000000001
[ 28.333395] RDX: ffff88803ea30fe0 RSI: 0000000000000000 RDI: ffff88803e445a98
[ 28.333395] RBP: ffffc9000028bd40 R08: ffff88803eb40000 R09: ffff88803e403c00
[ 28.333395] R10: ffff88803e445a98 R11: 0000000000000000 R12: 0000000000000006
[ 28.333395] R13: 000000000002b4c0 R14: ffffffff810390a0 R15: 0000000000000000
[ 28.333395] FS: 0000000000000000(0000) GS:ffff88803ea80000(0000) knlGS:0000000000000000
[ 28.333395] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 28.333395] CR2: 0000000000000000 CR3: 000000000260a000 CR4: 00000000000406e0
[ 28.333395] Call Trace:
[ 28.333395] ? poke_int3_handler+0x70/0x70
[ 28.333395] on_each_cpu+0x2d/0x60
[ 28.333395] text_poke_bp_batch+0x8c/0x160
[ 28.333395] arch_jump_label_transform_apply+0x33/0x50
[ 28.333395] __jump_label_update+0x116/0x160
[ 28.333395] jump_label_update+0xb9/0xd0
[ 28.333395] static_key_enable_cpuslocked+0x5a/0x80
[ 28.333395] static_key_enable+0x1a/0x30
[ 28.333395] timers_update_migration+0x30/0x40
[ 28.333395] timer_update_keys+0x1a/0x40
[ 28.333395] process_one_work+0x1fd/0x3f0
[ 28.333395] worker_thread+0x34/0x410
[ 28.333395] kthread+0x121/0x140
[ 28.333395] ? process_one_work+0x3f0/0x3f0
[ 28.333395] ? kthread_park+0xb0/0xb0
[ 28.333395] ret_from_fork+0x35/0x40
ここでRIPを見ると，smp_call_function_many関数でエラーが発生したことが分かって、SMPとはなにかについて検索して見たら、同じメモリを二ツ以上のプロセッサーが使うことで、この部分はランダムスケジューリングでは実装したことがないので、SMPオプションを解除して再ビルドした。（参照：https://en.wikipedia.org/wiki/Symmetric_multiprocessing）
SMPを解除したとき
SMPを解除した時は、 ==> debuggee: Machine booted and ready! で機動はできたけど、==> debuggee: Checking for guest additions in VM... のときエラーが発生した。そのエラーログは次のようになった。
[ 31.591660][ T1283] BUG: kernel NULL pointer dereference, address: 0000000000000000
[ 31.592313][ T1283] #PF: supervisor read access in kernel mode
[ 31.592667][ T1283] #PF: error_code(0x0000) - not-present page
[ 31.593014][ T1283] PGD 38cbf067 P4D 38cbf067 PUD 3d23e067 PMD 0
[ 31.593377][ T1283] Oops: 0000 [#1] NOPTI
[ 31.593615][ T1283] CPU: 0 PID: 1283 Comm: control Tainted: G OE 5.3.9+ #20
[ 31.594097][ T1283] Hardware name: innotek GmbH VirtualBox/VirtualBox, BIOS VirtualBox 12/01/2006
[ 31.594640][ T1283] RIP: 0010:rb_erase+0x149/0x380
[ 31.594927][ T1283] Code: f6 c2 01 0f 84 c2 01 00 00 48 83 e2 fc 0f 84 ee 00 00 00 48 89 c1 48 89 d0 48 8b 50 08 48 39 ca 0f 85 71 ff ff ff 48 8b 50 10 <f6> 02 01 48 8b 4a 08 75 3a 48 89 c7 48 89 48 10 48 89 42 08 48 83
[ 31.596105][ T1283] RSP: 0018:ffffc90001df7988 EFLAGS: 00010046
[ 31.596454][ T1283] RAX: ffff88803deb0060 RBX: ffff888037a30000 RCX: 0000000000000000
[ 31.596909][ T1283] RDX: 0000000000000000 RSI: ffffffff8245ee90 RDI: ffff888037a30060
[ 31.597381][ T1283] RBP: ffffc90001df7988 R08: 0000000000000000 R09: ffffc90000343b88
[ 31.597846][ T1283] R10: 00000000faccb043 R11: 0000000078dc05ec R12: ffffffff8245ee40
[ 31.598322][ T1283] R13: 0000000000000009 R14: ffff888037a30060 R15: 0000000000000001
[ 31.598787][ T1283] FS: 00007fef954dc700(0000) GS:ffffffff82447000(0000) knlGS:0000000000000000
[ 31.599314][ T1283] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 31.599694][ T1283] CR2: 0000000000000000 CR3: 000000003de92000 CR4: 00000000000406f0
[ 31.600157][ T1283] Call Trace:
[ 31.600347][ T1283] dequeue_task_fair+0x9f/0x2a0
[ 31.600687][ T1283] deactivate_task+0x57/0xf0
[ 31.600957][ T1283] ? update_rq_clock+0x2c/0x80
[ 31.601235][ T1283] __schedule+0x344/0x5d0
[ 31.601559][ T1283] schedule+0x32/0xa0
[ 31.601823][ T1283] rtR0SemEventMultiLnxWait.isra.3+0x33b/0x370 [vboxguest]
[ 31.602298][ T1283] ? wait_woken+0x90/0x90
[ 31.602569][ T1283] VBoxGuest_RTSemEventMultiWaitEx+0xe/0x10 [vboxguest]
[ 31.603009][ T1283] VBoxGuest_RTSemEventMultiWaitNoResume+0x28/0x30 [vboxguest]
[ 31.603496][ T1283] vgdrvHgcmAsyncWaitCallbackWorker+0xda/0x210 [vboxguest]
[ 31.603925][ T1283] vgdrvHgcmAsyncWaitCallbackInterruptible+0x15/0x20 [vboxguest]
[ 31.604385][ T1283] VbglR0HGCMInternalCall+0x3ff/0x1180 [vboxguest]
[ 31.604764][ T1283] ? vgdrvHgcmAsyncWaitCallback+0x20/0x20 [vboxguest]
[ 31.605168][ T1283] ? prep_new_page+0x8e/0x130
[ 31.605435][ T1283] ? get_page_from_freelist+0x6db/0x1160
[ 31.605827][ T1283] ? page_counter_cancel+0x22/0x30
[ 31.606122][ T1283] ? page_counter_uncharge+0x22/0x40
[ 31.606426][ T1283] ? drain_stock.isra.49.constprop.76+0x33/0xb0
[ 31.606795][ T1283] ? try_charge+0x62e/0x760
[ 31.607062][ T1283] ? tomoyo_init_request_info+0x80/0x90
[ 31.607407][ T1283] vgdrvIoCtl_HGCMCallWrapper+0x127/0x2c0 [vboxguest]
[ 31.607856][ T1283] VGDrvCommonIoCtl+0x3ca/0x1a20 [vboxguest]
[ 31.608234][ T1283] ? __check_object_size+0xdd/0x1a0
[ 31.609064][ T1283] ? _copy_from_user+0x3d/0x60
[ 31.609829][ T1283] vgdrvLinuxIOCtl+0x113/0x290 [vboxguest]
[ 31.610671][ T1283] do_vfs_ioctl+0xa9/0x620
[ 31.611427][ T1283] ? tomoyo_file_ioctl+0x19/0x20
[ 31.612197][ T1283] ksys_ioctl+0x75/0x80
[ 31.612901][ T1283] __x64_sys_ioctl+0x1a/0x20
[ 31.613633][ T1283] do_syscall_64+0x59/0x130
[ 31.614355][ T1283] entry_SYSCALL_64_after_hwframe+0x44/0xa9
[ 31.615173][ T1283] RIP: 0033:0x7fef965f56d7
[ 31.615877][ T1283] Code: b3 66 90 48 8b 05 b1 47 2d 00 64 c7 00 26 00 00 00 48 c7 c0 ff ff ff ff c3 66 2e 0f 1f 84 00 00 00 00 00 b8 10 00 00 00 0f 05 <48> 3d 01 f0 ff ff 73 01 c3 48 8b 0d 81 47 2d 00 f7 d8 64 89 01 48
[ 31.618044][ T1283] RSP: 002b:00007fef954dba18 EFLAGS: 00000246 ORIG_RAX: 0000000000000010
[ 31.619237][ T1283] RAX: ffffffffffffffda RBX: 00007fef954dba60 RCX: 00007fef965f56d7
[ 31.620163][ T1283] RDX: 00007fef954dba60 RSI: 00000000c0485607 RDI: 0000000000000003
[ 31.621066][ T1283] RBP: 00007fef954dba20 R08: 0000000000000079 R09: 0000000000000000
[ 31.621966][ T1283] R10: 00007fef900008d0 R11: 0000000000000246 R12: 0000000000693410
[ 31.622844][ T1283] R13: 00007fef954dbdbc R14: 00007fef954dbdac R15: 00007fef954dcdac
[ 31.623731][ T1283] Modules linked in: nls_utf8 isofs snd_intel8x0 snd_ac97_codec ac97_bus input_leds snd_pcm snd_timer serio_raw snd soundcore vboxguest(OE) mac_hid sch_fq_codel ib_iser rdma_cm iw_cm ib_cm ib_core iscsi_tcp libiscsi_tcp libiscsi scsi_transport_iscsi ip_tables x_tables autofs4 btrfs zstd_compress raid10 raid456 async_raid6_recov async_memcpy async_pq async_xor async_tx xor raid6_pq libcrc32c raid1 raid0 multipath linear crct10dif_pclmul crc32_pclmul ghash_clmulni_intel aesni_intel aes_x86_64 crypto_simd cryptd glue_helper vboxvideo drm_vram_helper ttm drm_kms_helper syscopyarea psmouse sysfillrect sysimgblt mptspi mptscsih mptbase scsi_transport_spi i2c_piix4 fb_sys_fops e1000 drm pata_acpi video
[ 31.630278][ T1283] CR2: 0000000000000000
[ 31.631004][ T1283] ---[ end trace 7027dee837a160c7 ]---
しかし、Oracle VMで直接起動するときは問題なく動けるようになって、そこでテストコードを試した。
テストコード
# include <assert.h>
# include <sched.h>
# include <sys/time.h>
# include <sys/types.h>
# include <stdio.h>
# include <stdlib.h>
# include <unistd.h>
/* 時刻 begin -- end まで proc 上で動いていた記録 */
typedef struct {
double begin;
double end;
int proc;
} rec_t;
/* 現在時刻を得る */
double cur_time() {
struct timeval tp[1];
gettimeofday(tp, 0);
return tp->tv_sec + tp->tv_usec * 1.0E-6;
}
void die(char * s) {
perror(s);
exit(1);
}
/* T秒間走り続け, CPUが割り当てられていたと思しき時間帯を記録する */
int run(double T, int n) {
pid_t pid = getpid();
struct sched_param param;
double limit = cur_time() + T;
rec_t * R = (rec_t *)calloc(n, sizeof(rec_t));
int i = 0;
R[i].begin = R[i].end = cur_time();
R[i].proc = sched_getcpu();
int ret_1 = syscall(145,pid);
printf("GET_SCHEDULER : %d\n",ret_1);
param.sched_priority = 139;
int ret_2 = syscall(144,pid,7,¶m);
if(ret_2==0){
printf("SET_SCHEDULER TO SCHED_RANDOM SUCCESS\n");
} else {
printf("SET_SCHEDULER TO SCHED_RANDOM FAILED\n");
}
ret_1 = syscall(145,pid);
printf("GET_SCHEDULER : %d\n",ret_1);
while (R[i].end < limit && i < n) {
double t = cur_time(); /* 現在時刻を得る */
int proc = sched_getcpu();
if (t - R[i].end < 1.0E-3 && proc == R[i].proc) {
/* 最後に見た時刻とあまり変わらない(< 1ms) -> R[i].endを増やす */
R[i].end = t;
} else {
/* 最後に見た時刻から1ms以上たっている -> 新しい区間に入る */
if (i + 1 >= n) break;
i++;
R[i].proc = proc;
R[i].begin = R[i].end = cur_time();
}
}
assert(i < n);
int j;
for (j = 0; j <= i; j++) {
printf("%d %f %f %d %f\n",
pid, R[j].begin, R[j].end, R[j].proc,
R[j].end - R[j].begin);
}
return 0;
}
int main(int argc, char ** argv) {
double T = (argc > 1 ? atof(argv[1]) : 10.0);
int n = (argc > 2 ? atoi(argv[2]) : 100000);
run(T, n);
return 0;
}
ターミナルから渡された引数からプログラムが動く時間T(秒)を設定して、sched_set_scheduler関数を用いてスケジューラをランダムスケジューラを使うようにする。ここでターミナルからは優先度(priority)をniceコマンドを使って設定する。
vagrant@ubuntu-bionic:~$ nice -15 ./test_2
niceコマンドはnice値を変更することで、上のコマンドはnice値を15にする。すなわち、優先度(priority)は120+15=135になり、ランダムスケジューラに入る。
実行結果
実行したときタスクがランダムキューに入ることは確認できたけど、その後エラーが発生した。
[ 107.960596][ C0] BUG: kernel NULL pointer dereference, address: 0000000000000058
[ 107.961544][ C0] #PF: supervisor read access in kernel mode
[ 107.962053][ C0] #PF: error_code(0x0000) - not-present page
[ 107.962552][ C0] PGD 3abb1067 P4D 3abb1067 PUD 3abb0067 PMD 0
[ 107.963078][ C0] Oops: 0000 [#1] NOPTI
[ 107.963432][ C0] CPU: 0 PID: 1515 Comm: lsb_release Tainted: G OE 5.3.9+ #20
[ 107.964161][ C0] Hardware name: innotek GmbH VirtualBox/VirtualBox, BIOS VirtualBox 12/01/2006
[ 107.964929][ C0] RIP: 0010:task_tick_fair+0xcc/0x160
[ 107.965382][ C0] Code: 73 8b 0d 93 be 3a 01 48 39 ca 72 29 48 8b 0d 73 b5 3a 01 48 8d 51 e8 48 85 c9 b9 00 00 00 00 48 0f 44 d1 48 8b 8b a0 00 00 00 <48> 2b 4a 58 78 05 48 39 c8 72 12 0f 1f 44 00 00 48 83 c4 08 5b 41
[ 107.967048][ C0] RSP: 0000:ffffc90000003e78 EFLAGS: 00010046
[ 107.967563][ C0] RAX: 000000002d17f460 RBX: ffff88803abd8000 RCX: 000000076403fcc9
[ 107.968239][ C0] RDX: 0000000000000000 RSI: 0000000000000000 RDI: 000b45fd181a81d0
[ 107.968913][ C0] RBP: ffffc90000003ea0 R08: 003ffff0b9e49c00 R09: 0000000000000400
[ 107.969584][ C0] R10: 0000000000000000 R11: 0000000000000000 R12: 0000000000000000
[ 107.970253][ C0] R13: ffff88803abd8048 R14: ffffffff810f4650 R15: 000000191c91658e
[ 107.970926][ C0] FS: 00007fd781841740(0000) GS:ffffffff82447000(0000) knlGS:0000000000000000
[ 107.971675][ C0] CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
[ 107.972231][ C0] CR2: 0000000000000058 CR3: 000000003bf5e000 CR4: 00000000000406f0
[ 107.972914][ C0] Call Trace:
[ 107.973188][ C0] <IRQ>
[ 107.973437][ C0] ? tick_sched_do_timer+0x60/0x60
[ 107.973867][ C0] scheduler_tick+0x44/0x60
[ 107.974245][ C0] update_process_times+0x45/0x60
[ 107.974666][ C0] tick_sched_handle+0x25/0x70
[ 107.975069][ C0] ? tick_sched_do_timer+0x52/0x60
[ 107.975505][ C0] tick_sched_timer+0x3b/0x80
[ 107.975909][ C0] __hrtimer_run_queues.constprop.24+0x10e/0x210
[ 107.976443][ C0] hrtimer_interrupt+0xd9/0x240
[ 107.976856][ C0] ? ksoftirqd_running+0x2f/0x40
[ 107.977281][ C0] smp_apic_timer_interrupt+0x68/0x100
[ 107.977743][ C0] apic_timer_interrupt+0xf/0x20
[ 107.978607][ C0] </IRQ>
[ 107.979290][ C0] RIP: 0033:0x56fd37
[ 107.980039][ C0] Code: ff 00 00 00 0f 8f 89 02 00 00 4c 8d 3c 07 48 81 fe 40 45 9d 00 0f 85 d3 03 00 00 4c 89 f5 4d 89 e2 4c 21 e5 48 0f be 5c 2a 28 <48> 83 fb ff 0f 84 3f 02 00 00 4c 8d 1c 5b 4f 8d 1c df 49 8b 73 08
[ 107.982571][ C0] RSP: 002b:00007fff64ad6810 EFLAGS: 00000202 ORIG_RAX: ffffffffffffff13
[ 107.983732][ C0] RAX: 0000000000000080 RBX: 0000000000000040 RCX: 00007fff64ad68b0
[ 107.984854][ C0] RDX: 000000000275fac0 RSI: 00000000009d4540 RDI: 000000000275fae8
[ 107.985985][ C0] RBP: 0000000000000075 R08: 0000000000000000 R09: 00007fd7817ccd80
[ 107.987119][ C0] R10: 9aa0515eaaf52cf5 R11: 00007fd781823130 R12: 9aa0515eaaf52cf5
[ 107.988255][ C0] R13: 00007fd7817d0db0 R14: 000000000000007f R15: 000000000275fb68
[ 107.989397][ C0] Modules linked in: nls_utf8 isofs snd_intel8x0 snd_ac97_codec ac97_bus input_leds snd_pcm serio_raw vboxguest(OE) snd_timer snd soundcore mac_hid sch_fq_codel ib_iser rdma_cm iw_cm ib_cm ib_core iscsi_tcp libiscsi_tcp libiscsi scsi_transport_iscsi ip_tables x_tables autofs4 btrfs zstd_compress raid10 raid456 async_raid6_recov async_memcpy async_pq async_xor async_tx xor raid6_pq libcrc32c raid1 raid0 multipath linear crct10dif_pclmul crc32_pclmul ghash_clmulni_intel aesni_intel aes_x86_64 crypto_simd cryptd glue_helper vboxvideo drm_vram_helper ttm drm_kms_helper syscopyarea psmouse sysfillrect sysimgblt mptspi mptscsih mptbase scsi_transport_spi i2c_piix4 fb_sys_fops e1000 drm pata_acpi video
[ 107.997916][ C0] CR2: 0000000000000058
[ 107.998821][ C0] ---[ end trace 717bffdc6fc42d15 ]---
このエラーを分析すると、task_tick_fair関数でNULLポインタをアクセスした理由でエラーが発生した。(kernel NULL pointer dereference) task_tick_fair関数はCFSスケジューラの部分であるので、もともとCFSスケジューラに入るべきの優先度範囲をランダムスケジューラの範囲にしたことでエラーが発生したと考えた。
おわりに
Linuxを書き換えるとき、全体を理解して書くのはとても難しいので、適宜GNU Globalなどのツールを活用しつつ実装してゆくことがおすすめです。
最後になりましたが、
い か が で し た か ？