2013/11/01(金)jiffies更新を追いかける

Tickless kernelにより、既存の和文資料の示すところから離れだす。
仕方が無いのでソースコードを頼りに追いかけることにする。

主目的は最低限必要なタイマリソースはなにか、の確認。
scheduler、jiffiesの更新がなされれば、要件を満たすので、更新処理を遡る。

kernelはv3.10を参照した(LTSI候補だというのを見かけたはず?)

jiffies更新を追いかける

システム時刻:xtime だったはず

jiffies更新箇所
/*
 * The 64-bit jiffies value is not atomic - you MUST NOT read it
 * without sampling the sequence number in xtime_lock.
 * jiffies is defined in the linker script...
 */
void do_timer(unsigned long ticks)
{
	jiffies_64 += ticks;
	update_wall_time();
	calc_global_load(ticks);
}
コイツが大ボス. jiffiesそのものじゃないけどいいんか( system call "times"で返している)
jiffies更新は別か..

→一緒だった。物理メモリで同一アドレスにしてあるので、64の更新がjiffies更新と一致する(Little Endian)。
FILE: System.map
8xxxxxxx D jiffies
8xxxxxxx D jiffies_64

void xtime_update(unsigned long ticks) write_seqlock(&xtime_lock); do_timer(ticks); write_sequnlock(&xtime_lock);

FILE: kernel/time/tick-sched.c
/*
 * Must be called with interrupts disabled !
 */
static void tick_do_update_jiffies64(ktime_t now)
{
	unsigned long ticks = 0;
	ktime_t delta;

	/*
	 * Do a quick check without holding xtime_lock:
	 */
	delta = ktime_sub(now, last_jiffies_update);
	if (delta.tv64 < tick_period.tv64)
		return;

	/* Reevalute with xtime_lock held */
	write_seqlock(&xtime_lock);

	delta = ktime_sub(now, last_jiffies_update);
	if (delta.tv64 >= tick_period.tv64) {

		delta = ktime_sub(delta, tick_period);
		last_jiffies_update = ktime_add(last_jiffies_update,
						tick_period);

		/* Slow path for long timeouts */
		if (unlikely(delta.tv64 >= tick_period.tv64)) {
			s64 incr = ktime_to_ns(tick_period);

			ticks = ktime_divns(delta, incr);

			last_jiffies_update = ktime_add_ns(last_jiffies_update,
							   incr * ticks);
		}
		do_timer(++ticks);

		/* Keep the tick_next_period variable up to date */
		tick_next_period = ktime_add(last_jiffies_update, tick_period);
	}
	write_sequnlock(&xtime_lock);
}
tick_do_update_jiffies64()を呼び出すヒト.
 static void tick_nohz_update_jiffies(ktime_t now)
 void tick_nohz_stop_sched_tick(int inidle)
  tick_program_event()って?
 static void tick_nohz_restart(struct tick_sched *ts, ktime_t now)
 void tick_nohz_restart_sched_tick(void)
 static void tick_nohz_handler(struct clock_event_device *dev)  // The nohz low res interrupt handler
 static enum hrtimer_restart tick_sched_timer(struct hrtimer *timer) // high-res. timer持っているとき.
いずれも、ktime_get();で現時刻をとってきている(CPU寝ていても回っているカウンタを想定)


FILE: kernel/time/timekeeping.c
ktime_t ktime_get(void)
{
	unsigned int seq;
	s64 secs, nsecs;

	WARN_ON(timekeeping_suspended);

	do {
		seq = read_seqbegin(&xtime_lock);
		secs = xtime.tv_sec + wall_to_monotonic.tv_sec;
		nsecs = xtime.tv_nsec + wall_to_monotonic.tv_nsec;
		nsecs += timekeeping_get_ns();
		/* If arch requires, add in gettimeoffset() */
		nsecs += arch_gettimeoffset();

	} while (read_seqretry(&xtime_lock, seq));
	/*
	 * Use ktime_set/ktime_add_ns to create a proper ktime on
	 * 32-bit architectures without CONFIG_KTIME_SCALAR.
	 */
	return ktime_add_ns(ktime_set(secs, 0), nsecs);
}
EXPORT_SYMBOL_GPL(ktime_get);
ktime_get()は、xtimeを見ている。あれ..?

コチラを見ると、http://d.hatena.ne.jp/enakai00/20111117/1321508379
別の所でハードウェアリソースを参照していた。


FILE: kernel/time/timekeeping.c
/**
 * update_wall_time - Uses the current clocksource to increment the wall time
 *
 * Called from the timer interrupt, must hold a write on xtime_lock.
 */
static void update_wall_time(void)
{
	struct clocksource *clock;
	cycle_t offset;
	int shift = 0, maxshift;

	/* Make sure we're fully resumed: */
	if (unlikely(timekeeping_suspended))
		return;

	clock = timekeeper.clock;        // ★★コレがSoC全域で使える、cpu idleでも時間を刻むクロックソースを握っている。

#ifdef CONFIG_ARCH_USES_GETTIMEOFFSET
	offset = timekeeper.cycle_interval;
#else
	offset = (clock->read(clock) - clock->cycle_last) & clock->mask;
#endif
	timekeeper.xtime_nsec = (s64)xtime.tv_nsec << timekeeper.shift;

	/*
	 * With NO_HZ we may have to accumulate many cycle_intervals
	 * (think "ticks") worth of time at once. To do this efficiently,
	 * we calculate the largest doubling multiple of cycle_intervals
	 * that is smaller then the offset. We then accumulate that
	 * chunk in one go, and then try to consume the next smaller
	 * doubled multiple.
	 */
	shift = ilog2(offset) - ilog2(timekeeper.cycle_interval);
	shift = max(0, shift);
	/* Bound shift to one less then what overflows tick_length */
	maxshift = (8*sizeof(tick_length) - (ilog2(tick_length)+1)) - 1;
	shift = min(shift, maxshift);
	while (offset >= timekeeper.cycle_interval) {
		offset = logarithmic_accumulation(offset, shift);
		if(offset < timekeeper.cycle_interval<<shift)
			shift--;
	}

	/* correct the clock when NTP error is too big */
	timekeeping_adjust(offset);

	/*
	 * Since in the loop above, we accumulate any amount of time
	 * in xtime_nsec over a second into xtime.tv_sec, its possible for
	 * xtime_nsec to be fairly small after the loop. Further, if we're
	 * slightly speeding the clocksource up in timekeeping_adjust(),
	 * its possible the required corrective factor to xtime_nsec could
	 * cause it to underflow.
	 *
	 * Now, we cannot simply roll the accumulated second back, since
	 * the NTP subsystem has been notified via second_overflow. So
	 * instead we push xtime_nsec forward by the amount we underflowed,
	 * and add that amount into the error.
	 *
	 * We'll correct this error next time through this function, when
	 * xtime_nsec is not as small.
	 */
	if (unlikely((s64)timekeeper.xtime_nsec < 0)) {
		s64 neg = -(s64)timekeeper.xtime_nsec;
		timekeeper.xtime_nsec = 0;
		timekeeper.ntp_error += neg << timekeeper.ntp_error_shift;
	}


	/*
	 * Store full nanoseconds into xtime after rounding it up and
	 * add the remainder to the error difference.
	 */
	xtime.tv_nsec =	((s64) timekeeper.xtime_nsec >> timekeeper.shift) + 1;
	timekeeper.xtime_nsec -= (s64) xtime.tv_nsec << timekeeper.shift;
	timekeeper.ntp_error +=	timekeeper.xtime_nsec <<
				timekeeper.ntp_error_shift;

	/*
	 * Finally, make sure that after the rounding
	 * xtime.tv_nsec isn't larger then NSEC_PER_SEC
	 */
	if (unlikely(xtime.tv_nsec >= NSEC_PER_SEC)) {
		int leap;
		xtime.tv_nsec -= NSEC_PER_SEC;
		xtime.tv_sec++;
		leap = second_overflow(xtime.tv_sec);
		xtime.tv_sec += leap;
		wall_to_monotonic.tv_sec -= leap;
		if (leap)
			clock_was_set_delayed();
	}

	timekeeping_update(false);
}

FILE: kernel/time/timekeeping.c
/**
 * timekeeper_setup_internals - Set up internals to use clocksource clock.
 *
 * @clock:		Pointer to clocksource.
 *
 * Calculates a fixed cycle/nsec interval for a given clocksource/adjustment
 * pair and interval request.
 *
 * Unless you're the timekeeping code, you should not be using this!
 */
static void timekeeper_setup_internals(struct clocksource *clock)
{
	cycle_t interval;
	u64 tmp, ntpinterval;

	timekeeper.clock = clock;
	clock->cycle_last = clock->read(clock);
以下略
この関数でセットしている。張り替えもできる模様。
static int change_clocksource(void *data)
FILE: kernel/time/timekeeping.c
/*
 * timekeeping_init - Initializes the clocksource and common timekeeping values
 */
void __init timekeeping_init(void)
{
	struct clocksource *clock;
	unsigned long flags;
	struct timespec now, boot;

	read_persistent_clock(&now);
	read_boot_clock(&boot);

	write_seqlock_irqsave(&xtime_lock, flags);

	ntp_init();

	clock = clocksource_default_clock();
	if (clock->enable)
		clock->enable(clock);
	timekeeper_setup_internals(clock);
...
おうふ...
clocksource_default_clock()のデフォルトは jiffiesを返すだけの論理的なクロックソースだ。
kernel/time/jiffies.c

ドライバの初期化処理で、タイマリソースを追加して、張り替える処理が走っていると想像。
/**
 * timekeeping_notify - Install a new clock source
 * @clock:		pointer to the clock source
 *
 * This function is called from clocksource.c after a new, better clock
 * source has been registered. The caller holds the clocksource_mutex.
 */
void timekeeping_notify(struct clocksource *clock)
{
	if (timekeeper.clock == clock)
		return;
	stop_machine(change_clocksource, clock, NULL);
	tick_clock_notify();
}
これか. inline関数になってる。SMPとSTOP_MACHINEが定義されていなければ関数呼び出しに置換される。
FILE: include/linux/stop_machine.h
change_clocksource( clock );


FILE: kernel/time/clocksource.c
#ifndef CONFIG_ARCH_USES_GETTIMEOFFSET

/**
 * clocksource_select - Select the best clocksource available
 *
 * Private function. Must hold clocksource_mutex when called.
 *
 * Select the clocksource with the best rating, or the clocksource,
 * which is selected by userspace override.
 */
static void clocksource_select(void)
コレ呼び出しているところが多数ある。。
clocksource_listの先頭がbest ratingになるらしい?
→追加するときに大きい物順になるようにコーディングしてある。
static void clocksource_enqueue(struct clocksource *cs)


カウントオーバーするまでに、起き上がる保証は?

なんとなく、登録情報で上限が定まるから、ここからタイマーを張っているような気がする。
タイマを貼ってしまったらTicklessじゃないような気がしないでもないよなぁ。

FILE: include/linux/clocksource.h
/*
 * Don't call __clocksource_register_scale directly, use
 * clocksource_register_hz/khz
 */
extern int
__clocksource_register_scale(struct clocksource *cs, u32 scale, u32 freq);
extern void
__clocksource_updatefreq_scale(struct clocksource *cs, u32 scale, u32 freq);

static inline int clocksource_register_hz(struct clocksource *cs, u32 hz)
{
	return __clocksource_register_scale(cs, 1, hz);
}
FILE: kernel/time/clocksource.c
/**
 * __clocksource_register_scale - Used to install new clocksources
 * @t:		clocksource to be registered
 * @scale:	Scale factor multiplied against freq to get clocksource hz
 * @freq:	clocksource frequency (cycles per second) divided by scale
 *
 * Returns -EBUSY if registration fails, zero otherwise.
 *
 * This *SHOULD NOT* be called directly! Please use the
 * clocksource_register_hz() or clocksource_register_khz helper functions.
 */
int __clocksource_register_scale(struct clocksource *cs, u32 scale, u32 freq)
{

	/* Initialize mult/shift and max_idle_ns */
	__clocksource_updatefreq_scale(cs, scale, freq);   // ★★★ここでcs->max_idle_nsに最長時間を設定してくれる。

	/* Add clocksource to the clcoksource list */
	mutex_lock(&clocksource_mutex);
	clocksource_enqueue(cs);
	clocksource_enqueue_watchdog(cs);
	clocksource_select();
	mutex_unlock(&clocksource_mutex);
	return 0;
}
EXPORT_SYMBOL_GPL(__clocksource_register_scale);
この最長時間を返す関数が以下にある。(timerクロックリソースを保持するオブジェクト(ファイルスコープ))
FILE: kernel/time/timekeeping.c
u64 timekeeping_max_deferment(void)
これを使っていて、スケジューラ絡みのソースは以下。
FILE: kernel/time/tick-sched.c
/**
 * tick_nohz_stop_sched_tick - stop the idle tick from the idle task
 *
 * When the next event is more than a tick into the future, stop the idle tick
 * Called either from the idle loop or from irq_exit() when an idle period was
 * just interrupted by an interrupt which did not cause a reschedule.
 */
void tick_nohz_stop_sched_tick(int inidle)
{

		if (ts->nohz_mode == NOHZ_MODE_HIGHRES) {
			hrtimer_start(&ts->sched_timer, expires,
				      HRTIMER_MODE_ABS_PINNED);
			/* Check, if the timer was already in the past */
			if (hrtimer_active(&ts->sched_timer))
				goto out;
		} else if (!tick_program_event(expires, 0))
				goto out;
tickを止める前に、タイマを貼ってますなぁ。ハイレゾが有効ならそれ。違えば普通の。

ハイレゾタイマが存在している場合。
FILE: kernel/hrtimer.c
/**
 * hrtimer_start_range_ns - (re)start an hrtimer on the current CPU
 * @timer:	the timer to be added
 * @tim:	expiry time
 * @delta_ns:	"slack" range for the timer
 * @mode:	expiry mode: absolute (HRTIMER_ABS) or relative (HRTIMER_REL)
 *
 * Returns:
 *  0 on success
 *  1 when the timer was active
 */
int hrtimer_start_range_ns(struct hrtimer *timer, ktime_t tim,
		unsigned long delta_ns, const enum hrtimer_mode mode)
{
	return __hrtimer_start_range_ns(timer, tim, delta_ns, mode, 1);
}
EXPORT_SYMBOL_GPL(hrtimer_start_range_ns);
"nohz_mode = NOHZ_MODE_HIGHRES"を設定しているのは、以下。
/**
 * tick_setup_sched_timer - setup the tick emulation timer
 */
void tick_setup_sched_timer(void)
{
	struct tick_sched *ts = &__get_cpu_var(tick_cpu_sched);
	ktime_t now = ktime_get();

	/*
	 * Emulate tick processing via per-CPU hrtimers:
	 */
	hrtimer_init(&ts->sched_timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
	ts->sched_timer.function = tick_sched_timer;

	/* Get the next period (per cpu) */
	hrtimer_set_expires(&ts->sched_timer, tick_init_jiffy_update());

	for (;;) {
		hrtimer_forward(&ts->sched_timer, now, tick_period);
		hrtimer_start_expires(&ts->sched_timer,
				      HRTIMER_MODE_ABS_PINNED);
		/* Check, if the timer was already in the past */
		if (hrtimer_active(&ts->sched_timer))
			break;
		now = ktime_get();
	}

#ifdef CONFIG_NO_HZ
	if (tick_nohz_enabled) {
		ts->nohz_mode = NOHZ_MODE_HIGHRES;
		printk(KERN_INFO "Switched to NOHz mode on CPU #%d\n", smp_processor_id());
	}
#endif
}
#endif /* HIGH_RES_TIMERS */

普通の。
/**
 * tick_program_event
 */
int tick_program_event(ktime_t expires, int force)
{
	struct clock_event_device *dev = __this_cpu_read(tick_cpu_device.evtdev);

	return tick_dev_program_event(dev, expires, force);
}

タイマリソースの張替えが自由にできてしまうので、
AMPで同一カウンタを参照するような実装をしたければ、
抜けないようにしておくのが良い。stop requestでnack返せばいいかなぁ?(要確認)





ハイレゾタイマがあれば、それを使ってしまうぽい?
FILE: kernel/timer.c
/*
 * This function runs timers and the timer-tq in bottom half context.
 */
static void run_timer_softirq(struct softirq_action *h)
{
	struct tvec_base *base = __this_cpu_read(tvec_bases);

	hrtimer_run_pending();

	if (time_after_eq(jiffies, base->timer_jiffies))
		__run_timers(base);
}
void __init init_timers(void)
{
	int err = timer_cpu_notify(&timers_nb, (unsigned long)CPU_UP_PREPARE,
				(void *)(long)smp_processor_id());

	init_timer_stats();

	BUG_ON(err != NOTIFY_OK);
	register_cpu_notifier(&timers_nb);
	open_softirq(TIMER_SOFTIRQ, run_timer_softirq);
}

FILE: kernel/timer.c
/*
 * Called from timer softirq every jiffy, expire hrtimers:
 *
 * For HRT its the fall back code to run the softirq in the timer
 * softirq context in case the hrtimer initialization failed or has
 * not been done yet.
 */
void hrtimer_run_pending(void)
{
	if (hrtimer_hres_active())   //★★ ->hres_activeを返す。
		return;

	/*
	 * This _is_ ugly: We have to check in the softirq context,
	 * whether we can switch to highres and / or nohz mode. The
	 * clocksource switch happens in the timer interrupt with
	 * xtime_lock held. Notification from there only sets the
	 * check bit in the tick_oneshot code, otherwise we might
	 * deadlock vs. xtime_lock.
	 */
	if (tick_check_oneshot_change(!hrtimer_is_hres_enabled())) // hrtimer_is_hres_enabled()は真になりやすい(hrtimer_hres_enabledを返す)
		hrtimer_switch_to_hres();
}
hrtimer_hres_active()が
/*
 * Switch to high resolution mode
 */
static int hrtimer_switch_to_hres(void)
{
	int i, cpu = smp_processor_id();
	struct hrtimer_cpu_base *base = &per_cpu(hrtimer_bases, cpu);
	unsigned long flags;

	if (base->hres_active)
		return 1;

	local_irq_save(flags);

	if (tick_init_highres()) {
		local_irq_restore(flags);
		printk(KERN_WARNING "Could not switch to high resolution "
				    "mode on CPU %d\n", cpu);
		return 0;
	}
	base->hres_active = 1;
	for (i = 0; i < HRTIMER_MAX_CLOCK_BASES; i++)
		base->clock_base[i].resolution = KTIME_HIGH_RES;

	tick_setup_sched_timer();
	/* "Retrigger" the interrupt to get things going */
	retrigger_next_event(NULL);
	local_irq_restore(flags);
	return 1;
}
clocksourceとclockeventとhrtimerと。
clockeventがhrtimerの代わりになれる?
clocksourceは、永続的に回るカウンタで、NO_HZに必要、か。
起き上がるのに別途タイマが必要になってくる。
(compare "以上"で割込みが出せるなら、一発でいける、か?)
hrtimerとしては登録しない

参考
 http://www.spinics.net/lists/linux-rt-users/msg06427.html


clocksource
 カレンダ時計みたいなもん。NO_HZで起き上がった時にデルタを見るために使う。
登録したratioの最大値のものを採用する(名前を指定して動的にもとれる)
デフォルトがjiffiesになっているので、昔ながらの定周期割込みでも運用できるぽい。

clockevent
 hrtimerにも使われる(どこでそうしているか未確認)
 属性をしっかりと設定して、PERIODIC,ONESHOTがアレば良さそう。
 インタフェースと使われ方を照会して、インプリする。

 ドキュメントはあまりない
(2013/03のコミットで、timerまわりの設計思想はthomasが書いているけど、ドライバの実装の話はナシ)



これ、ticklessだと?無効ですよ..
FILE: arm/kernel/time.c
#ifndef CONFIG_GENERIC_CLOCKEVENTS
/*
 * Kernel system timer support.
 */
void timer_tick(void)
{
	profile_tick(CPU_PROFILING);
	do_leds();
	xtime_update(1);
#ifndef CONFIG_SMP
	update_process_times(user_mode(get_irq_regs()));
#endif
}
#endif


別件

ARMのbootメモは、以下も詳しい。なぞる感じになるなぁ
http://amitshah.bizhat.com/arm/arm_linux_boot-1.html

2013/10/27(日)LDD2_Chap13

本コンテンツは更新中です。
書籍を置いてきたので、和文(本)を読めば進みが早いかもしれません。
が、単語の役され方次第で混乱するので原文も参照する必要があるでしょう。
内容理解という点では、進みは同じかもしれません。。

前置き

ざっくりとここを流し読み。基本、ドライバ開発者向けの資料なので、何もなければkernel空間での話だと思う。
DMAを触るためには、kernelのメモリ管理を知らなければならない、ということですね。
メモリ枯渇も目にすることが多いけれど、意味がわからないことがあるので、
ちょっとお勉強…。このレベルでもguruには程遠いというので、精進が足りなさすぎる…のね。

http://www.xml.com/ldd/chapter/book/ch13.html

アドレスの種類

name 説明
User virtual addresses,仮想アドレスユーザ空間のプログラムから見える一般的なアドレスです。 ユーザアドレスは、32bitか64bitの長さで、ハードウェアアーキテクチャと 各プロセス毎の仮想アドレス空間に基づきます。
Physical addresses, 物理アドレスこのアドレスは、プロセッサとシステムのメモリとの間で使用される。 物理アドレスは32bitまたは64bitの量である。 32ビットシステムでも、いくつかの状況では、64ビットの物理アドレスを使用することができます。
Bus addresses, バスアドレスこのアドレスは周辺バスとメモリの間で使用される。 多くの場合、それらは、プロセッサによって使用される物理アドレスと同じであるが、それは必ずしもそうではない。 バスアドレスは、もちろん、非常にアーキテクチャに依存している。
Kernel logical addresses, カーネル論理アドレスこれらはカーネルの通常のアドレス空間を構成しています。 これらのアドレスは、ほとんどまたはメインメモリのすべてのマップします。 そして、これらは物理アドレスであるかのように頻繁に扱われます。 ほとんどのアーキテクチャでは、(カーネル)論理アドレスとそれに関連付けられた 物理アドレスは、一定のオフセットだけ異なる。 (カーネル)論理アドレスは、ハードウェアのネイティブポインタサイズを使用するので、 重度に使用する*1 32ビットシステム上の物理メモリのすべてに対処できない可能性があります。 論理アドレスは通常型unsigned long型またはvoid*の変数に格納されています。 kmallocのから返されたメモリは、(カーネル)論理アドレスを持っています。
Kernel virtual addresses, カーネル仮想アドレスこれらは、必ずしも物理アドレスに直接マッピングされていないという点で、(カーネル)論理アドレスとは異なる。 すべての論理アドレスは、カーネル仮想アドレスである; vmalloc()で割り当てられたメモリは、仮想アドレスも持ちます。ただし物理アドレスに直接マッピングされていません。 kmap関数も、仮想アドレスを返します。 仮想アドレスは、通常はポインタ変数に格納されています。

論理アドレスを使用している場合、マクロ __pa()(<asm/page.h>で定義されている)は、それに関連する物理アドレスを返します。
物理アドレスは、__va()マクロで(カーネル)論理アドレスにマッピングできます。ただしlow-memoryページに対してのみです。
異なるカーネル関数は、異なるアドレスの型を要求します。
必要なアドレスの種類が明示的となるように定義された別のCの型があったならば良いだろうが、我々はそのような運を持っていません。
どちらのアドレス型をどこで使うのかを明確にします。

High and Low Memory

論理アドレスと、カーネル仮想アドレスとの差は、大量のメモリが装備されている32bitシステム上で強調される。
32bitだと、4GBのメモリを表現することができる。
最近までは、32bitシステムのLinuxは、それよりも大幅に少ないメモリに限定されていました。
しかし、仮想アドレス空間を設定することで解決することができます。(超意訳)
そのシステムでは、論理アドレスを設定することができ、より多くのメモリを扱うことができませんでした。
それが必要なので、すべてのメモリをカーネルアドレスに直接マップしました。

最近の開発では、メモリの制限を排除しており、32bitシステムでは、今のシステムメモリである4GBを優に超えるメモリで作業できます。
(もちろん、プロセッサ自身がより多くのメモリをアドレスできると仮定する)
しなしながら、多くのメモリを直接論理アドレスにマッピングする方法についての制限は残っている。

メモリの最下部(上限1〜2GB、kernel config.とハードウェアに依存します)だけは、論理アドレスを持っています。残り(high-memory)は違います。
high-memoryは、64bit物理アドレスを必要とすることができます。
そして、カーネルは、それを操作するための明示的な仮想アドレスのマッピングを設定する必要があります。
したがって、多くのカーネル関数は、メモリ不足に制限される。
high memoryは、ユーザ空間プロセスページのために予約される傾向にある。

"high memory"という語は、PCの世界で別の意味を持っているため、誰かを混乱させることがあります。
ここでは、語彙を以下のように定義します。
Type describe
Low memoryカーネル空間に存在する、論理アドレスメモリ。 よく遭遇するほぼすべてのシステムで、すべてのメモリはlow memoryです。
On almost every system you will likely encounter, all memory is low memory.
High memoryカーネル空間に論理アドレスが存在しないメモリ。 32bitでアドレッシングできるよりも多い物理メモリを搭載したシステム。
と、いいつつも、実際には memory mapped I/Oが存在するので、
自由に使える空間は32bit全域では無いわけですが。。
時間も無いのでキーワードだけ。

The Memory Map and struct page

high memoryをサポートするため、struct pageが存在する。
参照カウントとwait queueを有しており、low-memoryにmapされていればそのアドレスを持つ。
low-memoryにmapされていない状態もある。

ruct page *virt_to_page(void *kaddr);
カーネル論理アドレスを引数に渡す。vmalloc()やhigh memoryのアドレスでは、機能しない。
void *page_address(struct page *page);
page構造体のポインタを渡して、このページが指すカーネルアドレスを返す。
high-memoryの場合、mapされている場合に返してくる。
#include <linux/highmem.h>
void *kmap(struct page *page);
void kunmap(struct page *page);
low-memoryでも、high-memoryでも適切に機能し、カーネル仮想アドレスを返す。
high-memoryの場合、適切な(システムに依存した定められた)空間にmapしてから返してくれる。
限られた空間なので、kunmap()の呼び出しは必須である。

Page Tables

kernelのメモリ管理にかかわる構造体。<asm/page.h>にて定義されている。
(ARMで云うなら、4Kpageまで分解するのにテーブルルックアップを3回必要とするので、そのソフトウェア版と見ればよい、か?(消化中))
略語 name description
?struct mm_struct
PGDpgd_tPage Directory.
PMDpmd_tPage mid-level Directory.
PTEpte_tPage Table.
?struct page



*1 : heavily equipped 32-bit systems.

補足事項?

"BSS"は、歴史的な遺物です。
古いアセンブリ演算子から来ていて、意味は"Block Started by Symbol"です。

[ARM] compressed kernel

2013/10/20linux::ARMimport

zImageの展開処理

調査対象は、【kernel 3.0.39 "Sneaky Weasel"】です。

例として、u-bootから起動する場合を考えます。
ここで上げるのは、とあるボードへの移植時に調査した値です。
ボード依存部の値は、デタラメに書いている可能性があるので、注意してください。


NOR bootの場合は、ROM上のコード実行が可能ですが、昨今の方式*1ではbootloaderがDRAM上に展開してから実行することが多いでしょう。

u-bootが読み込むファイル、uImageは、zImageにuImageヘッダがついたもの。
図にしてみると以下のイメージ。(AAでスミマセン)
+------------------------+
| u-boot header(64oct.)  |
+------------------------+
| zImage decompress code |
| .text                  |
| (with compressed data )|
| .got                   |
| .got.plt               |
| .bss                   |
+------------------------+
このデータの読み込みは、u-bootによって行われるため、任意のアドレスに展開されます。


ldscriptを見ると、ざっくりとこんな感じ。
  _text = .;
  .text : {}
  _etext = .;
  _got_start = .;
  .got			: { *(.got) }
  _got_end = .;
  .got.plt		: { *(.got.plt) }
  _edata = .;

  __bss_start = .;
  .bss			: { *(.bss) }
  _end = .;

*1 : NAND/SDから2nd boot programを読み出して、本当のローダを呼び出す。

事前準備

実際には、コードを読みながら参照していった結果です。

FILE: arch/arm/boot/compressed/Makefile
# Supply ZRELADDR to the decompressor via a linker symbol.
ifneq ($(CONFIG_AUTO_ZRELADDR),y)
LDFLAGS_vmlinux += --defsym zreladdr=$(ZRELADDR)
ZRELADDRは、以下で定義されます。
FILE: arch/arm/boot/Makefile
ZRELADDR    := $(zreladdr-y)
右辺は、SoC依存部にて定義されています。
FILE: arch/arm/mach-*/Makefile.boot
zreladdr-y	:= 0x40008000
params_phys-y	:= 0x40000100
initrd_phys-y	:= 0x40800000


zImage先頭から

エントリーポイントはここ。

bootloaderから飛んでくるところ

アドレスは任意。

FILE: ./boot/compressed/head.S
start:
 ※cache有効, TLBはVA-PA一対一対応, 

restart:
		.align	2
		.type	LC0, #object
LC0:
		.word	LC0					@ r1
		.word	__bss_start			@ r2
		.word	_end				@ r3
		.word	_edata				@ r6
		.word	input_data_end - 4	@ r10 (inflated size location)
		.word	_got_start			@ r11
		.word	_got_end			@ ip(r12)

		.word	.L_user_stack_end	@ sp

		.size	LC0, . - LC0

		/*
		 * We might be running at a different address.  We need
		 * to fix up various pointers.
		 */
		sub	r0, r0, r1		@ calculate the delta offset
		add	r6, r6, r0		@ _edata
		add	r10, r10, r0	@ inflated kernel size location
LC0(DRAMの位置)から、"LC0"の配置した位置(ldscriptでは先頭0、コード配置後のLC0の位置)を差っ引いて、r0に保持する。
圧縮カーネルの、展開後のサイズは、build systemによって、圧縮カーネルの後ろにLEで付与される。したがって、r10へloadする値は、input_data_endから4引いてある。(32bit決め打ちだね)
spも、relocate後のアドレスをセット。r10にsp+64kのアドレスをセット(malloc用に64k確保)(CONFIG_ZBOOT_ROM未定義の場合。定義時はコード本体がROMに入るから、_edataの後ろに配置する)

このイメージがロードされる位置がどこでも動けるようになっている。

展開後のkernel位置と、この展開コード、edata類の空間が重なっているかをチェックする。重複している場合、reset〜edataまでを、後ろからコピーする(memmove相当)。その後、コピーした後のrestartへjumpする。(これで重複しない位置で再度relocateする)

※ユーザモードで入ってきた場合、SVCで特権を得るようになってます。
ヴェクタ位置へのロードを期待しているようですが、必ずしもそうではないから、ちょっと不味そうな気がするネ。

relocate後

decompress処理のソフトと、圧縮イメージとを再配置して、kernel imageを展開できる状態になって、wont_overwriteへたどり着く。前述のように、最初のバイナリがロードされる位置によって、ここへ直接来ることもあれば、relocateすることもありますね。
wont_overwrite:
/*
 * If delta is zero, we are running at the address we were linked at.
 *   r0  = delta
 *   r2  = BSS start
 *   r3  = BSS end
 *   r4  = kernel execution address
 *   r7  = architecture ID
 *   r8  = atags pointer
 *   r11 = GOT start
 *   r12 = GOT end
 *   sp  = stack pointer
 */
・GOT書き換え(オフセット分加算して、飛び先がrelocate先のアドレスになるように)
・BSSをゼロクリア


本来のImage(vmlinux)へ

kernelの展開先アドレスを第一引数、spからsp+64kを第二〜三引数に渡して、第四引数にアーキテクチャIDをのせてcall。
void decompress_kernel(unsigned long output_start, unsigned long free_mem_ptr_p, unsigned long free_mem_ptr_end_p, int arch_id)
展開が終わったら、cache clean、cache-offしてから、圧縮前のkernel先頭へ飛ぶ。


ARM boot

2013/10/19linux::ARMimport
kernel bootからの処理をみてみましょう。
kernel先頭へは、u-bootやbare-boxから飛んできます。

そこはそれ。wiki contentsとして記事を置いておきます。

2013/10/06(日)[dbg] kernel panicネタ

togetterのまとめ、カーネルパラメータとお茶目なガチャピン先生より。
@frsyukiさんのconsole logから、ざっくりとメモリ枯渇の推定がなされる様子がわかります。

要約すると、SoftIrq中、kmalloc(,GFP_KERNEL)したときに、メモリが足りなかった、という事象です。
通常空間から呼ばれる場合は、page cacheを開放して秋メモリを確保したりもできるのでしょうが、
softirqからでは、それができない様子。呼び出し元でGFP_*を選択できると思うけれど、
呼び出し時のコンテキストによって、使って良いか、エラーになるかはあるはず。(要確認)