一度挫折したHaskellだけど

「プログラミングHaskell」の第八章と第九章で枕を涙で濡らした自分。
このままモナドまわりが何となもやもやしたままで終わると思いきや---。こんなサイトを発見。
http://learnyouahaskell.com/
海外では有名な初心者向けサイトらしく、Webで読む分には無料。5月には日本語版の書籍も販売されるそうだ。
もう一度Monadにトライしてみるか。

exec elfの続き

NetBSD Currentのkern/exec_elf.cのexec_elf_makecmdsを読んだ続き。

まずはELFヘッダのチェック。

671   if (epp->ep_hdrvalid < sizeof(Elf_Ehdr))
672     return ENOEXEC;
673 
674   is_dyn = elf_check_header(eh, ET_DYN) == 0;
675   /*
676    * XXX allow for executing shared objects. It seems silly
677    * but other ELF-based systems allow it as well.
678    */
679   if (elf_check_header(eh, ET_EXEC) != 0 && !is_dyn)
680     return ENOEXEC;
681 
682   if (eh->e_phnum > MAXPHNUM || eh->e_phnum == 0)
683     return ENOEXEC;
684 

次にELFヘッダ内から.interpセクションを見付だし、そこに入っている文字列(ELFインタプリタへのパス)を抜き出します。

708   for (i = 0; i < eh->e_phnum; i++) {
709     pp = &ph[i];
710     if (pp->p_type == PT_INTERP) {
711       if (pp->p_filesz >= MAXPATHLEN) {
712         error = ENOEXEC;
713         goto bad;
714       }
715       interp = PNBUF_GET();
716       interp[0] = '\0';
717       if ((error = exec_read_from(l, epp->ep_vp,
718           pp->p_offset, interp, pp->p_filesz)) != 0)
719         goto bad;
720       break;
721     }
722   }

次の処理・・・。これは何をしているのだろう。
おそらくinterpをロードか何かしているのか。

elf_probe_funcはsys/exec.h内でstruct execswのメンバとして定義されている。
execswでgrepをかけると、kern/exec_elf32.c内で引っかかる。
中を見ると、exec_elf32_execswという構造体定義があり、この中で「netbsd_elf32_probe」という関数が対応した位置に記述されている。

733   if (epp->ep_esch->u.elf_probe_func) {
734     vaddr_t startp = (vaddr_t)pos;
735 
736     error = (*epp->ep_esch->u.elf_probe_func)(l, epp, eh, interp,
737                 &startp);
738     if (error)
739       goto bad;
740     pos = (Elf_Addr)startp;
741   }

先に書いた記事と同様、netbsd_elf32_probeはnetbsd_elf_probeであるが、特にinterpをどうこうしている箇所はなさそうだ。
(netbsd_elf_probeでは確かにELF_MD_PROBE_FUNCという定義があれば何かinterpに対する操作をしていそうだが、この定義はどうやらmipsにのみ存在しているようだ)

次の処理はPT_LOADなセクションをロードする作業。ソースは長いので省略。
そしていよいよinterpなセクションに記述されたファイル(ELFインタプリタ)をロードする。
そして、エントリポイントも取り出しておく。

820   if (interp) {
821     int j = epp->ep_vmcmds.evs_used;
822     u_long interp_offset;
823 
824     if ((error = elf_load_file(l, epp, interp,
825         &epp->ep_vmcmds, &interp_offset, ap, &pos)) != 0) {
826       goto bad;
827     }
828     ap->arg_interp = epp->ep_vmcmds.evs_cmds[j].ev_addr;
829     epp->ep_entry = ap->arg_interp + interp_offset;
830     PNBUF_PUT(interp);
831   } else

さらにこの後check_exec()に戻る。
・・・まだまだ先は長そうだ。

ザッカーバーグの手紙

http://techse7en.com/archives/3824847.html
この文章を読んで非常に感銘を受けました。
とりわけ「ハッカーウェイ」の部分に。

特に

ハッカーはすぐに全てを良くしようとするよりはむしろ素早くリリースしたり、より小さな反復から学ぶことによって長期的に最高のサービスを作ろうとします。

の部分が自分には欠けていたのかな、と感じました。
完全なものなんてないのだから、まずリリース。その心がけでブログも小さいトピックでいいから頻繁に更新していきたいなと改めて考えさせられました。

そうすることで少しでもハッカーに近づけたらいいな！

netbsd-currentでexec_elf32_makecmdsはどこにあるの？

netbsd-currentでsys/kern/kern_exec.cを読んでいたが、まずどこでelfヘッダの中身を取り出すのかが分からなかった。
そこで追ってみるとどうもcheck_exec()の以下箇所で実施しているらしいことまではわかりました。

403 for (i = 0; i < nexecs; i++) {
404 int newerror;
405
406 epp->ep_esch = execsw[i];
407 newerror = (*execsw[i]->es_makecmds)(l, epp);
408
(sys/kern/kern_exec.c)

ということは・・・。会社で2.0なNetBSDをいじっている私はexec_elf32_makecmdsがあることを期待しました。
grepすると確かにあるのですが、ctagsなタグを読んでも定義先に行き着けない・・・。

仕方なしにmakecmdsでgrepをかけてみるとsys/kern/exec_elf.cというファイルがあり、その中を探すとexec_elf_makecmds()という関数がありました。
さらに探すと

95 #define exec_elf_makecmds ELFNAME2(exec,makecmds)
(sys/kern/exec_elf.c)

という定義がありました。
ELFNAME2はマクロで

939 #if defined(ELFSIZE)
940 #define CONCAT(x,y) __CONCAT(x,y)
941 #define ELFNAME(x) CONCAT(elf,CONCAT(ELFSIZE,CONCAT(_,x)))
942 #define ELFNAME2(x,y) CONCAT(x,CONCAT(_elf,CONCAT(ELFSIZE,CONCAT(_,y))))
943 #define ELFNAMEEND(x) CONCAT(x,CONCAT(_elf,ELFSIZE))
944 #define ELFDEFNNAME(x) CONCAT(ELF,CONCAT(ELFSIZE,CONCAT(_,x)))
945 #endif
(sys/sys/exec_elf.h)

となっています。
ELFSIZEは・・・あちこちで定義されていてどこのELFSIZE使っているんだか分からない・・・orz
しかし、仮にELFSIZEが32だとすると
#define exec_elf_makecmdsは CONCAT(exec,CONCAT(_elf,CONCAT(32,CONCAT(_makecmds))))
になり、文字列をつなぎ合わせる事で
exec_elf_makecmds -> exec_elf32_makecmds
となります。
つまり、exec_elf32_makecmdsの本体はexec_elf_makecmdsだということになります。
こんなところにいたのか・・・・。

今日は遅いので明日この関数の中を読んでみる事にします。

netbsdのスケジューリング(覚書)

netbsdのスケジューリングの流れを忘れてしまったので、ソースを読み直した。
この記録は、次に忘れないようにするための備忘録である。

1.スケジューリングが行われる流れ(sleepなどで自発的に実行権を手放す場合は除く。
hardclock()から、100msに1回sched_tick()をコール。
lwpのスケジューリングポリシがSCHED_FIFOでない場合、cpu_need_resched()を呼び出す。

mipsの場合、cpu_need_resched()は

aston(ci->ci_data.cpu_onproc);
ci->ci_want_resched = 1;

でaston(ci->ci_data.cpu_onproc);は
((l)->l_md.md_astpending = 1)
となっている。

例外やシステムコールの戻り時にmd_astpendingを見て、非ゼロの場合、ast()をコールする。

ast()ではci->ci_want_reschedの値をチェックし、非ゼロな場合、preempt()をコールする。
preempt()の中ではmi_switch()がコールされるため、スケジューリングが行われる。

2.runqueueと優先度
runqueue_t構造体で定義。
キューは2種類ある。
1.r_rt_queue
2.r_ts_queue
r_rt_queueの方が優先度が高いものらしい。
優先度がPRI_HIGHEST_TS以下であればr_ts_queueを使う。

キューはcpu_infoごとに存在する。
cpu_info中のschedstate_percpu構造体内のspc_sched_infoがrunqueue_t構造体である。
この中からもっとも優先度が高い（spc_maxpriority）キューの先頭のlwpを取得する。

3.優先度の計算
lwp_eprio()で計算する。
l_priorityの値をベースに優先度を決定する。

1.l_kpriorityがtrueでありながらl_priorityの値がPRI_KERNELより小さければ「l_krpbase + l_priority / 2」を優先度とする。
2.1以外の場合はl_priorityの値を優先度とする。
3.1もしくは2で得られた値とl_inheritedprioを比較し、大きな値を最終的に優先度とする。

4.どうやって優先度を変動しているの
(以下の文章は、スケジューラが4bsdの場合を想定する。)
l_priorityに値を設定している人がsched_changepri()くらいである。
この関数は、sched_syncobjというsyncobj_t型の構造体メンバになっている。
メンバ名はsobj_changepri。

sobj_changepriを使っているのは、lwp.h内のlwp_changepri()のみである。
sched_4bsdな場合、lwp_changepri()をresetpriority()の中で呼び出す。
resetpriority()は優先度の再計算をしたのち、lwp_changepriをコール。

resetpriority()がコールされるのは以下の4箇所である。
1.sched_schedclock()
2.sched_pstats_hook()
3.updatepri()
4.sched_nice()

1.はhardclock()から定期的にコール。現在動いているlwpの優先度の再計算をする。
「定期的に」とは1秒間に16回を想定している。

schedhzというグローバル変数が0の場合、ci->ci_schedstate.spc_schedticks = hardscheddivな粒度で呼ばれる。
schedhzはalphaもしくはsparc64以外は0なので、mipsでは0となる。
なお、hardscheddivの値は、hz / 16　となっている。
よって、1秒間に約16回実効状態のlwpの優先度を再計算することになる。

2.はsched_lwp_stats()からコール。
sched_lwp_stats()は、kern_synch.c内のsched_pstats()からコールされている。
sched_pstats()は全プロセスのlwpをたどり、優先度の再計算をしている。
sched_pstats()はuvm_schedulerからコールされる。kpause()で1秒おきに起きてsched_pstatsをコールするようだ。
よって、1秒ごとにすべてのlwpの優先度が再計算されることになる。

3.はsched_4bsdなソースのsched_setrunnable()からコールされている。
sched_setrunnable()では、対象とするlwpのl_slptimeが1を上回る場合にのみupdatepri()を呼び出す。

sched_setrunnable()は以下2通りのケースで呼び出す。
3-1.sleepq_removeでlwpを起こすとき、起こそうとするlwpに対してsched_setrunnable()を呼び出す。
3-2.setrunnableでlwpを実行可能状態にするとき、該当lwpに対してsched_setrunnable()を呼び出す。

また、l_slptimeについては、該当lwpのsleep状態(LSSLEEP/LSSTOP/LSSUSPENDED)に遷移してから最初にsched_lwp_stats()がコールされるまでsleep状態が続いたときにl_slptimeが++される。

4はdonice()でコールされる。
donice()はsys_setpriorityからコールされる。つまり、setpriority()による優先度の変更があった場合にも優先度の再計算がされる。

ftraceについて（スタック書き換え）

前回の続き。
prepare_ftrace_return()では「parent」を求める。
parentはmcount呼び出し先関数の戻りアドレスが格納されているスタックポインタのことである。
これを取得するのがftrace_get_parent_addr()である。

unsigned long ftrace_get_parent_addr(unsigned long self_addr,
				     unsigned long parent,
				     unsigned long parent_addr,
				     unsigned long fp)
{
	unsigned long sp, ip, ra;
	unsigned int code;
	int faulted;

	/* in module or kernel? */
	if (self_addr & 0x40000000) {
		/* module: move to the instruction "lui v1, HI_16BIT_OF_MCOUNT" */
		ip = self_addr - 20;
	} else {
		/* kernel: move to the instruction "move ra, at" */
		ip = self_addr - 12;
	}

	/* search the text until finding the non-store instruction or "s{d,w}
	 * ra, offset(sp)" instruction */
	do {
		ip -= 4;

		/* get the code at "ip": code = *(unsigned int *)ip; */
		safe_load_code(code, ip, faulted);

		if (unlikely(faulted))
			return 0;

		/* If we hit the non-store instruction before finding where the
		 * ra is stored, then this is a leaf function and it does not
		 * store the ra on the stack. */
		if ((code & S_R_SP) != S_R_SP)
			return parent_addr;

	} while (((code & S_RA_SP) != S_RA_SP));

	sp = fp + (code & OFFSET_MASK);

	/* ra = *(unsigned long *)sp; */
	safe_load_stack(ra, sp, faulted);
	if (unlikely(faulted))
		return 0;

	if (ra == parent)
		return sp;
	return 0;
}

mipsではレジスタに格納されている値をみただけでは関数呼び出しによってどのくらいスタックポインタが移動したかがわからない。よって、戻りアドレスがスタックのどこにつまれたのかもレジスタ値だけではわからないことになる。

その代わりにmipsでは関数呼び出し直後付近で、ベタなストア命令を使って戻りアドレスをスタックに格納している。
よって、戻りアドレス格納先のアドレスを知るためには、関数の先頭付近の命令をトレースし該当ストア命令を検索し、この命令を解析して戻りアドレスを知ることになる。具体的には

s{d,w} ra,offset(sp)

を実行している箇所を見つけ、offsetにあたる値の取得を行う。
これによって、sp(スタックポインタ）+ offsetが戻りアドレスの格納先アドレスであることがわかる。

あとは、prepare_ftrace_return()に戻り、safe_store_stack()で「mcount呼び出し先関数の戻りアドレス」を書き換え、元の戻りアドレスなどをftrace_push_return_trace()で保存しておくことになる。

ftraceについて調べる(前々回からの続き)

前々回では「スタック弄りはなさそう」と書いた。
ところで、今回参照した論文でスタック弄りについて触れた部分のタイトルが「2 Adding Function Graph Tracing to ARM」となっていた。
このスタック弄りの概要を図示すると、以下のとおりとなる。

確かに前々回まででは「Graph Trace」の部分は読めていなかった。もう一度mcountを見直すと以下のように関数ポインタの値を判断したうえでftrace_graph_callerを呼び出している。

  PTR_LA  t1, ftrace_stub
　（中略）
#ifdef  CONFIG_FUNCTION_GRAPH_TRACER
  PTR_L t3, ftrace_graph_return
  bne t1, t3, ftrace_graph_caller
   nop
  PTR_LA  t1, ftrace_graph_entry_stub
  PTR_L t3, ftrace_graph_entry
  bne t1, t3, ftrace_graph_caller
   nop
#endif
||<　

ftrace_graph_callerは以下の関数。

>|C|
#ifdef CONFIG_FUNCTION_GRAPH_TRACER

NESTED(ftrace_graph_caller, PT_SIZE, ra)
#ifdef CONFIG_DYNAMIC_FTRACE
  PTR_L a1, PT_R31(sp)  /* load the original ra from the stack */
#ifdef KBUILD_MCOUNT_RA_ADDRESS
  PTR_L t0, PT_R12(sp)  /* load the original t0 from the stack */
#endif
#else
  MCOUNT_SAVE_REGS
  move  a1, ra    /* arg2: next ip, selfaddr */
#endif

#ifdef KBUILD_MCOUNT_RA_ADDRESS
  bnez  t0, 1f    /* non-leaf func: t0 saved the location of the return address */
   nop
  PTR_LA  t0, PT_R1(sp) /* leaf func: get the location of at(old ra) from our own stack */
1:  move  a0, t0    /* arg1: the location of the return address */
#else
  PTR_LA  a0, PT_R1(sp) /* arg1: &AT -> a0 */
#endif
  jal prepare_ftrace_return
#ifdef CONFIG_FRAME_POINTER
   move a2, fp    /* arg3: frame pointer */
#else
#ifdef CONFIG_64BIT
   PTR_LA a2, PT_SIZE(sp)
#else
   PTR_LA a2, (PT_SIZE+8)(sp)
#endif
#endif

  MCOUNT_RESTORE_REGS
  RETURN_BACK
  END(ftrace_graph_caller)

この関数ではprepare_ftrace_returnがコールされる。

/*
 * Hook the return address and push it in the stack of return addrs
 * in current thread info.
 */
void prepare_ftrace_return(unsigned long *parent, unsigned long self_addr,
         unsigned long fp)
{
  unsigned long old;
  struct ftrace_graph_ent trace;
  unsigned long return_hooker = (unsigned long)
      &return_to_handler;
  int faulted;

  if (unlikely(atomic_read(&current->tracing_graph_pause)))
    return;

  /* "parent" is the stack address saved the return address of the caller
   * of _mcount.
   *
   * if the gcc < 4.5, a leaf function does not save the return address
   * in the stack address, so, we "emulate" one in _mcount's stack space,
   * and hijack it directly, but for a non-leaf function, it save the
   * return address to the its own stack space, we can not hijack it
   * directly, but need to find the real stack address,
   * ftrace_get_parent_addr() does it!
   *
   * if gcc>= 4.5, with the new -mmcount-ra-address option, for a
   * non-leaf function, the location of the return address will be saved
   * to $12 for us, and for a leaf function, only put a zero into $12. we
   * do it in ftrace_graph_caller of mcount.S.
   */

  /* old = *parent; */
  safe_load_stack(old, parent, faulted);
  if (unlikely(faulted))
    goto out;
#ifndef KBUILD_MCOUNT_RA_ADDRESS
  parent = (unsigned long *)ftrace_get_parent_addr(self_addr, old,
               (unsigned long)parent,
               fp);
  /* If fails when getting the stack address of the non-leaf function's
   * ra, stop function graph tracer and return */
  if (parent == 0)
    goto out;
#endif
  /* *parent = return_hooker; */
  safe_store_stack(return_hooker, parent, faulted);
  if (unlikely(faulted))
    goto out;

  if (ftrace_push_return_trace(old, self_addr, &trace.depth, fp) ==
      -EBUSY) {
    *parent = old;
    return;
  }

  trace.func = self_addr;

  /* Only trace if the calling function expects to */
  if (!ftrace_graph_entry(&trace)) {
    current->curr_ret_stack--;
    *parent = old;
  }
  return;
out:
  ftrace_graph_stop();
  WARN_ON(1);
}

ソースのコメントから、KBUILD_MCOUNT_RA_ADDRESSはgcc4.5以降で有効なオプションと推定できる。
長くなるので、続きは次回。次回以降はスタック弄りを見たいので、gcc4.5未満のgccを使っていると仮定してソースを読む。