Linuxカーネルを読む前にやったこと

linux

「カーネルのコードがよくわからない。Linuxカーネルに関する本を読んでもいまいちしっくりこない。」 から、「読めば理解できそう..!」 になるまでにやったことのまとめ。

はじめに

低レイヤの話がわかるようになりたかった。 カーネルの中身が知りたかった。 とりあえず本を読もうと思い詳解 Linuxカーネル 第3版を読んだが知識がなさ過ぎてよくわからない。 知らない用語だらけで都度調べればなんとなくはわかる気もするが、いまいち頭に入ってこない。 今思うとそもそもCPUの話なのかカーネルの話なのかさえよくわからない状態で読んでいたような気がする。

そんな状態を克服するためにやったことをまとめておく。

学習前

学習前の自分の知識はこんな感じだった。

知っていた

よく知らなかった

補足:

  • 大学は情報学部ではなく工学部卒。OSのことはほとんど学んでいなかった。
  • 仕事はWebアプリケーション開発がメイン

何をやったか

ここからがメイン。何をしたか、どのような効果があったか。

1. CPUの基礎の学習

学習内容

  • CPUの創りかたを読んだ。高校理科程度の知識から簡単なCPUを作れるようになる本。

効果

  • 本当に簡単なCPUなら作れるのでは、という気持になった。
  • CPUのイメージができるようになりレジスタやアセンブリ周りの話が理解しやすくなった気がする。
  • FPGAにも手を出したくなった…が、時間の制約で保留とした

2. コンパイラの作成

学習内容

効果

  • アセンブリに慣れた。
  • スタックの使い方に慣れた。
  • Calling Conventionを知った。（後のOS開発の役に立った）

3. OSの学習(1)

学習内容

効果

  • GDT、システムコール、割り込み…などの用語がOSから見た意味でわかるようになった。
  • CPUの機能を知った。

4. OSの学習(2)

学習内容

  • MITのOSの授業を進めた。 内容はメモリ管理、ページテーブル、システムコール、ネットワークドライバなどのコードを自分で書いていってOSを作っていくというもの。ほぼ機能のないOSが最終的にはhttpサーバが動くようになる。課題の答えはないがテストコードがあり、それで自分のコードを確認できる。 scheduleに沿ってすすめると、次の課題までにこれを読め、など適切なテキストも与えてくれる。もちろん全部英語。
  • 進めたときのログはこちら

効果

まとめ

CPUの本を読んでコンパイラ作ってOSを作ったら、低レイヤの話が以前よりもわかるようになり、詳解 Linuxカーネル 第3版を見ながらLinuxのコードも追えるようになった。

上の内容を全部やると結構時間がかかるので、強くおすすめするわけではありませんが、この辺りを学ぼうとしている人の参考になれば幸いです。

CPUの創りかた

CPUの創りかた

ふつうのコンパイラをつくろう

ふつうのコンパイラをつくろう

30日でできる! OS自作入門

30日でできる! OS自作入門

32ビットコンピュータをやさしく語る　はじめて読む486 (アスキー書籍)

32ビットコンピュータをやさしく語る　はじめて読む486 (アスキー書籍)

詳解 Linuxカーネル 第3版

詳解 Linuxカーネル 第3版

Rubyのメソッド周りの動作まとめ

ruby

今までRubyにあまり触れていなかったため、 初めてのRuby、 メタプログラミングRuby 第2版、 Rubyのしくみ -Ruby Under a Microscope- を一気に読んだ。

この記事の内容は、学習の記録&復習としてメソッド周りの動作をまとめたもの。

公式ドキュメントは読んだがそれ以上はやってないという方にはもしかしたら役に立つかもしれない。 もうすでにバリバリ使ってる方には当たり前の内容かもしれない。

コードの動作は

$ ruby -v
ruby 2.3.1p112 (2016-04-26) [x86_64-linux-gnu]

で確認した。

目次

  • メソッドの実行
  • メソッドの探索
  • メソッドの定義

メソッドの実行

メソッドの呼び出し時の動作：

  • 常にレシーバが設定される
  • レシーバを明示しない場合は呼び出したスコープでのselfがレシーバとなる
  • メソッド内のselfは呼び出されたときのレシーバとなる
def whoami(); self; end

whoami # => main //トップレベルのselfはmainオブジェクト(Objectクラスのインスタンス)
class C
  whoami # => C
  def f
    whoami
  end
end
o = C.new
o   # => #<C:0x000000008c7c88>
o.f # => #<C:0x000000008c7c88> // レシーバはo. whoami内のselfはo

sendを使えばメソッド名のシンボルを使って呼び出すこともできる。 その際のレシーバはsendのレシーバが使われる。

# つづき
o.send(:f) # => #<C:0x000000008c7c88> // レシーバはo. whoami内のselfはo

メソッドの探索

オブジェクトは内部で

  • そのクラスへの参照をもつ
  • スーパークラスへの参照をもつ（クラスオブジェクトの場合）

これらの参照先はclassメソッドやsuperclassメソッドで得られるものとは異なる。 説明のため以下ではそれらの参照を単にそれぞれklass, superという言葉で表す。 （klass、superはRubyのC言語での実装で使われているポインタの名前。 もしかしたら新しいバージョンでは実装や名前が変わっているかもしれないが、大きく実装が変わらない限り当分このイメージで問題ないだろう）

obj.method_name()としてメソッドを実行すると、

  1. objのklassが指すクラスにmethod_nameが定義されているか
  2. そのsuperのクラスに定義されているか
  3. そのsuperのクラスに定義されているか
  4. …

と探索し、最初に見つかったものを実行する。

ancestorsでそのsuperのチェーンを確認できる。

class P; end
module M; end

module N
    include M # N -super-> M
end
N.ancestors # => [N, M]

class C < P # C -super-> P
  include N # C -super-> N -super-> M -super-> P
end
C.ancestors # => [C, N, M, P, Object, Kernel, BasicObject]

N.ancestors # => [N, M] // インクルード時にはmoduleのコピーをインクルードするのでここで M -super-> Pになっているわけではない

メソッドを探索し最後まで見つからなければ、最初に戻ってmethod_missingメソッドを探索する。 BasicObjectクラスにはもともとmethod_missingが定義されているため何もしなければそれが実行される。

BasicObject.private_instance_methods(false) # => [..., :method_missing, ...]

method_missingを定義すれば存在しないメソッドを処理することもできる。(ゴーストメソッドとよばれる)

class C
    def method_missing(name)
        "#{name} is called!"
    end
end
C.new.hogehoge # => "hogehoge is called!"
C.new.helloworld # => "helloworld is called!"

メソッドの定義

defによってメソッドを定義する方法は2つ

  1. def + メソッド名で定義（ def methodname() ...)
  2. def + オブジェクト名.メソッド名 で定義（ def obj.methodname() ...)

1. def methodname() ...で定義

この場合、defが現れた場所のカレントクラスのインスタンスメソッドとして定義される。 （"カレントクラス"はメタプログラミングRuby 第2版で使われていた用語で、公式の用語ではなさそう）

カレントクラスはスコープが参照しているクラスのことで、次のようになっている。

# カレントクラス: Object
module M
  # カレントクラス: M
  class C
    # カレントクラス: C. hogeはCのインスタンスメソッドとなる
    def hoge()
      # カレントクラス: self.class
    end
  end
  # カレントクラス: M
end
p M::C.instance_methods(false) # => [:hoge]

2. def obj.methodname() ...で定義

この場合、そのobjの固有のクラス(特異クラス)のインスタンスメソッドに定義される。 (以下、objオブジェクトの特異クラスには#を付けて#objと表す）

class C
  def func
  end
end
obj = C.new
obj2 = C.new
def obj.sfunc #  objの特異クラス#objのインスタンスメソッドとして定義
end
obj.sfunc
obj2.sfunc # Error

p obj.class.instance_methods(false) #=> [:func]
p obj.singleton_class.instance_methods(false) #=> [:sfunc]

上記のobj.sfuncはobjの特異メソッド(singleton method)と呼ばれる。 このときメソッドの探索で説明したklassとsuperは

obj -klass-> #obj -super-> C -super-> ...

のようになっており、#objにsfunc、Cにfuncが定義されているため、前述のメソッドの探索でobj.funcもobj.sfuncも実行できる。 obj2.sfuncがErrorなのはその探索するクラスにsfuncが定義されていないため。

クラスでは…

クラスもオブジェクトであるため、

def C.classfunc
end

とすればクラスの特異メソッド（クラスメソッド）が定義でき、C.classfuncで実行できる。 class ClassName ... end内のselfはそのクラスになることから、上記は以下のようにも定義できる。

class C
  def self.classfunc # ここでのselfはC. Cの特異クラスに定義
  end
end

class << objectとするとそのオブジェクトの特異クラスをカレントクラスとしてオープンできるので、下のようにもかける。

class << C
  # このスコープでのカレントクラスはCの特異クラス
  def classfunc
  end
end

クラスの特異クラスのことをメタクラスとよぶこともある。

スーパークラスの特異クラスは特異クラスのスーパークラスなので、クラスメソッドはサブクラスでも実行できる。

class P
    def self.classf
        "ok"
    end
    classf # => "ok"
end

class C < P
    classf # => "ok" // selfはC. C -klass-> #C -super-> #P
end

C.singleton_class.superclass == P.singleton_class # => true

 P --klass-> #P (def classf)
 ^           ^
super       super    
 ^           ^
 C --klass-> #C

クラスがオブジェクトであるように、特異クラスもオブジェクトであるため特異クラスの特異クラスも作成できる。（使い道があるかどうかは別として）

トップレベル

トップレベルでのカレントクラスはObjectであり、 トップレベルでオブジェクト指定なしでメソッドを定義するとObjectのprivateメソッドとして定義される。 この事実と、

  • レシーバを指定せずにメソッドを実行するとselfがレシーバとして設定される
  • Objectはあらゆるクラスのスーパークラス

ということから、トップレベルで定義した関数はあらゆる場所でレシーバなし実行できる。 (Objectのサブクラスではないクラスも作れるため、全ての場所で実行できるわけではない。)

def top; "ok!" end
Object.private_instance_methods(false) # => [..., :top, ...]

class C
    top() # => ok! // selfはC。 CはClassクラスのインスタンス
    def hoge
        top()
    end
end
C.new.hoge # => ok! // hoge内のselfはCクラスのインスタンス

class Clean < BasicObject
    top() # => ok! // selfはClean, CleanはClassクラスのインスタンス
    def fuga
        top()
    end
end
Clean.ancestors # => [Clean, BasicObject]
Clean.new.fuga # NoMethodError // topがundefined. selfのメソッド探索ルートにObjectがいないため

ちなみにprivateメソッドはレシーバを明示できないため（privateの制約）、 トップレベルのメソッドはレシーバなし実行できるというよりは、 レシーバを明示したobj.method()の形式では実行できない。

特異クラスはいつ作られるのか（おまけ）

p ObjectSpace.count_objects[:T_CLASS] # => 612
class C; end
p ObjectSpace.count_objects[:T_CLASS] # => 614 // Cと#Cが作られた?
o = C.new
p ObjectSpace.count_objects[:T_CLASS] # => 614
def o.f; end
p ObjectSpace.count_objects[:T_CLASS] # => 615　// #oがつくられた？

クラスの数だけで判断すると、クラスの特異クラスはクラス定義時に作成される、 クラスでないオブジェクトの特異クラスは必要になったら作成される、っぽい。 （前半の、クラス定義時に2つクラスができる、というのはRubyのしくみ -Ruby Under a Microscope-に記載されている内容。）

初めてのRuby

初めてのRuby

メタプログラミングRuby 第2版

メタプログラミングRuby 第2版

Rubyのしくみ -Ruby Under a Microscope-

Rubyのしくみ -Ruby Under a Microscope-

Linuxカーネル コードリーディング ( kernel/sched.c )

linux code reading

詳解 Linuxカーネル 第3版とLinuxカーネル2.6解読室を参考に Linuxカーネルのkernel/sched.cのschedule()の一部を読んだのでその記録を残しておきます。

この記事はただのコードリーディングのログで、内部を知りたい人向けではありません。 これから読もうと思っている人への何かしらのヒントになったらいいかなと思って公開しています。 （※実際ここに記載するスケジューラのアルゴリズムは2.6.23以降使われていません。 参考:Completely Fair Scheduler の内側）

バージョンはv2.6.12、ハードウェア依存のコードはi386のものです。

なぜ読んだか

  • kernelのコードを読むということに慣れておきたい
  • ついでに何か発見があったらラッキー

ただなんとなく読んでみたかった、という気持ちも大きいです。

なぜこの部分を選んだか

  • 上記２つの書籍で解説があったので困ったら頼れる
  • スケジューリングのアルゴリズムなら「○○とは」のような事前知識がなくても読めそう

ここからコードリーディング

kernel/sched.c内のschedule関数を読みます。 わかりそうな所はちゃんと読みつつ、難しそう、または今読まなくてもよさそうな所は後回しにして気楽に読んでいきます。

関数全体はこんな感じです。

https://github.com/komukomo/linux/blob/v2.6.12-read/kernel/sched.c#L2607

…長いので一旦全部忘れて、重要そうなところを抜き出します。

asmlinkage void __sched schedule(void) {
  task_t *prev, *next;
  runqueue_t *rq;
  ...
  prev = context_switch(rq, prev, next);
  ...
}

変数宣言と１つの関数呼び出しのみになりました。 コンテキストスイッチ、つまりあるプロセスから次のプロセスへの切り替えをしています。これがこの関数で最終的にやりたいことです。 (プロセスやらスレッドやら紛らわしいので以降ここではプロセスではなくtaskと呼ぶことにします)

とりあえずcontext_switchの中身は触れず、次にrq,next,prevに代入されているコードを埋めてみます。代入箇所は複数ありますが、最も意味のありそうな行を書いておきます。

asmlinkage void __sched schedule(void) {
  task_t *prev, *next;
  runqueue_t *rq;
  struct list_head *queue;
  int idx;
  ...
  prev = current;
  ...
  rq = this_rq();
  ...
  next = list_entry(queue->next, task_t, run_list);
  ...
  prev = context_switch(rq, prev, next);
  ...
}

prevはcurrentを代入しているだけなので簡単そうです。名前からして現在のtaskを表しているようですが、一応中身を見てみます。

include/asm-i386/current.h

static inline struct task_struct * get_current(void) {
  return current_thread_info()->task;
}
#define current get_current()

include/asm-i386/thread_info.h

// how to get the thread information struct from C
static inline struct thread_info *current_thread_info(void) {
  struct thread_info *ti;
  __asm__("andl %%esp,%0; ":"=r" (ti) : "0" (~(THREAD_SIZE - 1)));
  return ti;
}

インラインアセンブラ構文が現れました。 インラインアセンブラとは、cのコードの中にアセンブリを直接書くことのできる機能です。 ここではespレジスタ（現在のスタックのトップを指しているもの）を使ってthread_infoのアドレスを取得してそのtaskがcurrentになっています。 thread_infoはespの値の下位12ビット(THREAD_SIZEによります)を0にした位置に配置されているためこのような処理でアドレスを求めることができます。 thread_infoを割り当てている部分を読めばそれが確認できそうですが今は飛ばします。

次はrq = this_rq(); を見てみます。

kernel/sched.c

static DEFINE_PER_CPU(struct runqueue, runqueues);
#define this_rq()      (&__get_cpu_var(runqueues))

include/asm-generic/percpu.h

/* var is in discarded region: offset to particular copy we want */
#define per_cpu(var, cpu) (*RELOC_HIDE(&per_cpu__##var, __per_cpu_offset[cpu]))
#define __get_cpu_var(var) per_cpu(var, smp_processor_id())

smp_processor_idは長いので、意味がわかりそうな部分だけ書きます。

lib/kernel_lock.c

unsigned int smp_processor_id(void) {
  ...
    int this_cpu = __smp_processor_id();
  ...
    return this_cpu;
}

細かく見ていくと難しそうですが、cpuごとにrunqueueというものが定義されていて、 this_rqはコードを実行しているcpuのrunqueueを返しているということでしょう。 スケジューラのアルゴリズムにはあまり関係ないので、ここではcpuごとにrunqueueというものがある、 と思っておく程度でよいと思います。

prevとrqが終わったので次はnext の方をみてみます。 一行だけでは意味がわからないので関係のありそうな3行を追加します。

asmlinkage void __sched schedule(void) {
  task_t *prev, *next;
  runqueue_t *rq;
  struct list_head *queue;
  int idx;
  ...
  prev = current;
  ...
  rq = this_rq();
  ...
  array = rq->active; // ここ

  idx = sched_find_first_bit(array->bitmap);　// ここ
  queue = array->queue + idx; // ここ
  next = list_entry(queue->next, task_t, run_list);
  ...
  prev = context_switch(rq, prev, next);
  ...
}

コードをそのまま読むと、rqのactiveのbitmapから目的のidxを探し、queueのその位置のentryをnextに代入しているようです。 nextの選び方は気になるのでこのあたりでrunqueue_tの構造を把握しておきます。 大きな構造体なので使われる部分だけ抜き出します。

kernel/sched.c

#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
typedef struct prio_array prio_array_t;
struct prio_array {
  unsigned int nr_active;
  unsigned long bitmap[BITMAP_SIZE];
  struct list_head queue[MAX_PRIO];
};

typedef struct runqueue runqueue_t;

struct runqueue {
  unsigned long nr_running;
  ...
  prio_array_t *active;
  prio_array_t *expired;
  prio_array_t arrays[2];
  ...
};

include/linux/sched.h

#define MAX_USER_RT_PRIO    100
#define MAX_RT_PRIO        MAX_USER_RT_PRIO
#define MAX_PRIO       (MAX_RT_PRIO + 40)

include/linux/list.h

struct list_head {
  struct list_head *next, *prev;
};

list_headはただの双方向リストです。 便利なデータ構造なので、include/linuxの下に置いてあってlinuxのコード内のいろいろなところで使わているようです。

prioというのはpriority、つまり優先度を表していて最大はMAX_PRIOの140と定義されています。 定義をみると100という数字にも意味がありそうです。

prio_arrayは優先度の数、つまり140個分のリスト(queue[MAX_PRIO])を持ち、 そこにリンクされたtaskの数(nr_active)とその優先度ごとのリストにtaskが存在するかどうかを表すbitmapをもっています。

runqueueはactive, expiredという２つのprio_arrayへのポインタと、 それらのポインタが指し示す実際のprio_arrayであるarrays[2]があります。 activeは実行可能で、割り当てを待っているtaskのリスト、 expiredは既に実行されてある時間消費したのち、他のプロセス実行権を渡したたtaskのリストを意味します。

f:id:komukomo:20170403012506p:plain

構造が把握できたところでidx = sched_find_first_bit(array->bitmap);の行にあるsched_find_first_bitの中身をみてみます。

inclide/asm-i386/bitops.h

/**
 * __ffs - find first bit in word.
 * @word: The word to search
 *
 * Undefined if no bit exists, so code should check against 0 first.
 */
static inline unsigned long __ffs(unsigned long word)
{
    __asm__("bsfl %1,%0"
        :"=r" (word)
        :"rm" (word));
    return word;
}

/*
 * Every architecture must define this function. It's the fastest
 * way of searching a 140-bit bitmap where the first 100 bits are
 * unlikely to be set. It's guaranteed that at least one of the 140
 * bits is cleared.
 */
static inline int sched_find_first_bit(const unsigned long *b)
{
    if (unlikely(b[0]))
        return __ffs(b[0]);
    if (unlikely(b[1]))
        return __ffs(b[1]) + 32;
    if (unlikely(b[2]))
        return __ffs(b[2]) + 64;
    if (b[3])
        return __ffs(b[3]) + 96;
    return __ffs(b[4]) + 128;
}

__ffsの中で使われているbsflは最下位ビット位置を探す命令です。 例えば__ffs(12)とすると12はbitで表すと1100なので3が返されます。 (bsflの最後のlはデータ型がlongであるという意味なのでマニュアル等で解説を探すときは"bsf"を探しましょう）

unlikelyは、

include/linux/compiler.h

#define likely(x)   __builtin_expect(!!(x), 1)
#define unlikely(x)    __builtin_expect(!!(x), 0)

と定義されており、__builtin_expectというのは、コンパイラに分岐の予測情報を与えて ジャンプが少なくなるような最適なコードを生成させるようにするものです。 条件が真になる可能性が高いときにif(likely(..))、 低いときにif(unlikely(...))というようにかきます。

参考

関数名とコメントだけでもなんとなくわかりますが、つまりsched_find_first_bitは指定されたアドレスから32*5ビット分をみて一番初めに1になっているビットの位置を返す関数です。

コメントとunlikelyの使われ方をみると、はじめの100bitのどれかが立っている可能性は低い、ということもわかります。

続いてlist_entryを見てみます。

include/linux/list.h

/**
 * list_entry - get the struct for this entry
 * @ptr:   the &struct list_head pointer.
 * @type:  the type of the struct this is embedded in.
 * @member:    the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member) \
   container_of(ptr, type, member)

include/linux/kernel.h

/**
 * container_of - cast a member of a structure out to the containing structure
 *
 * @ptr:   the pointer to the member.
 * @type:  the type of the container struct this is embedded in.
 * @member:    the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({           \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);  \
        (type *)( (char *)__mptr - offsetof(type,member) );})

include/linux/stddef.h

#undef offsetof
#ifdef __compiler_offsetof
#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
#else
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#endif

container_ofが見づらいので具体的な引数を入れて、型も括弧もいろいろ無視するとこのように展開されます。

container_of(ptr, task_t, run_list)
 ↑を展開↓
  __mptr = ptr;
  tmp = __mptr - offsetof(task_t,run_list);
  (task_t *)tmp;

第一引数の示すアドレスから、構造体のメンバのoffsetを引いたアドレスを返しています。

f:id:komukomo:20170403012841p:plain

struct list_headはそれ単体で使われるわけではなく、別の構造体のメンバとして使われるのでリストの具体的な要素を取得するときにはlist_entryが使われます。

ここまでくればnextへの代入は読めそうです。

asmlinkage void __sched schedule(void) {
  task_t *prev, *next;
  runqueue_t *rq;
  struct list_head *queue;
  int idx;
  ...
  prev = current;
  ...
  rq = this_rq(); // 現在のcpuのrunqueue
  ...
  array = rq->active; // のactiveな方...

  idx = sched_find_first_bit(array->bitmap);　// ...の初めのビット位置
  queue = array->queue + idx; // = &(array->queue[idx]) // の優先度のqueue
  next = list_entry(queue->next, task_t, run_list); // の先頭の要素を次のプロセスとする
  ...
  prev = context_switch(rq, prev, next);
  ...
}

現在のcpuのキューrq->activeのbitmapのうち1となる初めのビット位置 を取得し（優先度の値が小さいほうが優先される）、 その次の行でその優先度のtaskのリスト(idx位置のリスト)を取得し、 そのリストの先頭のtaskのアドレスをnextとしています。

この選び方なら、次のtaskを選ぶのにかかる時間はtaskの数に依存しないということもわかりました。

ここまでで、現在のプロセスprevと次のプロセスnextを選んでcontext_switchする、というところまで書きました。 schedule関数を読むといいつつ行数でいうと5%くらいしか書いていませんが、このペースで全部読んでまとめると量がすごいことになるので、ここで区切って気が向いたらまたどこかを読んでまとめてみます。

詳解 Linuxカーネル 第3版

詳解 Linuxカーネル 第3版

Linuxカーネル2.6解読室

Linuxカーネル2.6解読室