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

詳解 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版

作者: Daniel P. Bovet,Marco Cesati,高橋浩和,杉田由美子,清水正明,高杉昌督,平松雅巳,安井隆宏
出版社/メーカー: オライリー・ジャパン
発売日: 2007/02/26
メディア: 大型本
購入: 9人クリック: 269回
この商品を含むブログ (71件) を見る

Linuxカーネル2.6解読室

作者: 高橋浩和,小田逸郎,山幡為佐久
出版社/メーカー: ソフトバンククリエイティブ
発売日: 2006/11/18
メディア: 単行本
購入: 14人クリック: 197回
この商品を含むブログ (119件) を見る