这是我今年去日本参加 LinuxCon 要讲的，主要是最近在做的一些和 dracut 相关的东西。
Slides 可以在这里下载：dracut.pdf
另外，今年日本 LinuxCon 的会议日程在这里。今年没有 Linus 大神了，他去年去参加果然是因为 Linux 20周年的原因。
抱怨一句：好羡慕 akong 他们部门，公司赞助参加 KVM Forum，光去听就可以。不像我这样，没有要讲的东西连去都去不了；就算有东西要讲，公司也不赞助，费用都是回来找 Linux Foudation 包销；开会三天还不能算工作日……唉，同一个公司的人出去开会差距怎么这么大呢……
Floyd’s cycle-finding algorithm 是一个经典的算法，用来检测一个链表中是否有环这种问题。因为它使用了两个指针，快的指针被称为兔子，慢的指针被称为乌龟，所以这个算法又被称为“龟兔算法”。
Emacs 源代码中有它的一个完美实现，我们可以看 src/eval.c 中的 signal_error()。
[c]
/ Signal `error’ with message S, and additional arg ARG.
If ARG is not a genuine list, make it a one-element list. /
void
signal_error (s, arg)
char *s;
Lisp_Object arg;
{
Lisp_Object tortoise, hare;
hare = tortoise = arg;
while (CONSP (hare))
{
hare = XCDR (hare);
if (!CONSP (hare))
break;
hare = XCDR (hare);
tortoise = XCDR (tortoise);
if (EQ (hare, tortoise))
break;
}
if (!NILP (hare))
arg = Fcons (arg, Qnil); / Make it a list. /
xsignal (Qerror, Fcons (build_string (s), arg));
}
[/c]
上面有一些 lisp “词汇” 可能你看不懂，翻译成你看得懂的代码如下。
[c]
bool
list_has_cycle(NODE list)
{
NODE tortoise, *hare;
hare = tortoise = list;
while (hare)
{
hare = hare->next;
if (!hare)
break;
hare = hare->next;
tortoise = tortoise->next;
if (hare == tortoise)
break;
}
if (hare)
return true;
return false;
}
[/c]
整数溢出大家都不陌生，可能陌生的是 gcc 对带符号整数溢出的处理。
先看标准怎么说，对于无符号整数，标准如此描述：
A computation involving unsigned operands can never overflow,
because a result that cannot be represented by the resulting unsigned
integer type is reduced modulo the number that is one greater than the
largest value that can be represented by the resulting type.
换句话说，无符号整数的溢出总是 wrap 回去的，但依旧在无符号整数的表示范围内。
对于带符号整数的溢出，标准规定是未定义行为：
If an exceptional condition occurs during the evaluation of an expression (that is, if the
result is not mathematically defined or not in the range of representable values for its
type), the behavior is undefined.
实际上（使用二进制补码），如果溢出的话，两个正数结果会变成负数，超出了正数本身的范围。wikipedia 中如此说：
Most computers distinguish between two kinds of overflow conditions. A carry occurs when the result of an addition or subtraction, considering the operands and result as unsigned numbers, does not fit in the result. Therefore, it is useful to check the carry flag after adding or subtracting numbers that are interpreted as unsigned values. An overflow proper occurs when the result does not have the sign that one would predict from the signs of the operands (e.g. a negative result when adding two positive numbers). Therefore, it is useful to check the overflow flag after adding or subtracting numbers that are represented in two’s complement form (i.e. they are considered signed numbers).
正是因为“未定义”，所以 gcc 会大胆地做出一些可能令你吃惊的优化。看下面的例子：
[c]
int wrap(int a) {
return (a + 1 > a);
}
int main(void) {
printf(“%sn”, wrap(INT_MAX) ? “no wrap” : “wrapped”);
}
[/c]
很好理解，可是 gcc 完全可以如此生成 wrap() 函数的代码：
00000000004004f0 :
4004f0: b8 01 00 00 00 mov $0x1,%eax
4004f5: c3 retq
因为 gcc 假设了带符号的整数从来不会溢出，所以”a + 1 > a” 总会是真，所以直接返回1！这么做完全符合标准，但不符合我们的期待。我们期望 wrap() 函数能够检测是否会溢出。
为此，gcc 引入了几个相关的命令行选项：-fwrapv，-fstrict-overflow/-fno-strict-overflow，-Wstrict-overflow。简单地说，-fstrict-overflow 就是告诉编译器，带符号整数溢出是未定义的，你可以假设它不会发生，从而继续做优化。而 -fwrapv 是说，带符号整数的溢出是定义好的，就是 wrap，你按照这个定义来编译。gcc 文档中提到：
Using -fwrapv means that integer signed overflow is fully defined: it wraps. When -fwrapv is used, there is no difference between -fstrict-overflow and -fno-strict-overflow for integers. With -fwrapv certain types of overflow are permitted. For example, if the compiler gets an overflow when doing arithmetic on constants, the overflowed value can still be used with fwrapv, but not otherwise.
我们加上 -fno-strict-overflow 之后再去编译上面的代码，结果明显不同：
00000000004004f0 :
4004f0: 8d 47 01 lea 0x1(%rdi),%eax
4004f3: 39 f8 cmp %edi,%eax
4004f5: 0f 9f c0 setg %al
4004f8: 0f b6 c0 movzbl %al,%eax
4004fb: c3 retq
而对于使用二进制补码的机器来说，-fwrapv 和 -fno-strict-overflow 只有细微的区别： -fno-strict-overflow 只是说不去优化，而-fwrapv 明确地定义了溢出的行为。
Linux 内核中曾经出现一个相关的 bug，是 Linus 大神出手搞定了，他说道：
It looks like ‘fwrapv’ generates more temporaries (possibly for the code
that treies to enforce the exact twos-complement behavior) that then all
get optimized back out again. The differences seem to be in the temporary
variable numbers etc, not in the actual code.So fwrapv really is different from fno-strict-pverflow, and disturbs the
code generation more.IOW, I’m convinced we should never use fwrapv. It’s clearly a buggy piece
of sh*t, as shown by our 4.1.x experiences. We should use
-fno-strict-overflow.
所以编译 Linux 内核时使用的是 -fno-strict-overflow。
Red Hat 北京的内核测试组正在招人，现有3个实习的职位和5个全职的职位。欢迎来应聘，也欢迎来明年毕业的同学来实习。
工作地点都是北京中关村。感兴趣的同学可以把你的英文简历直接发给我：xiyou 点 wangcong 在 gmail 点 com，邮件中请注明应聘的是哪个职位。虽然我不在测试组，但我会帮你转发简历。:-)
详情见下：
Intern 1:
Job Description:
The Quality Engineering team at Red Hat is looking for intern to test
Linux kernel. Responsibilities include:
Requirements:
Keywords: kernel; testing
Intern 2:
Job Description:
The Quality Engineering team at Red Hat is looking for intern to test
Linux file system. Responsibilities include:
Requirements:
Keywords: kernel; file system; testing
Intern 3:
Job Description:
The Quality Engineering team at Red Hat is looking for intern to test
Linux network. Responsibilities include:
Job Requirements:
Keywords: kernel; network; testing
Regular Job 1:
Job Description:
The Quality Engineering team at Red Hat is looking for engineer to test
linux kernel network, including network protocols, NIC drivers, bonding,
vlan, bridge, etc. You need to search for, analyze, report, track kernel
network defects and verify bug fixes. You should be a self motivated
person and have passion in finding bugs/defects in linux network.
Responsibilities include:
Required Skills:
Regular Job 2:
Job Description:
The Quality Engineering team at Red Hat is looking for QE lead for Linux
kernel testing. You will test the kernel and communicate/coordinate with
developers and other QEs including assigning tasks. We are looking for
an experienced QA Engineer with strong technical and coordinating
skills . You must be a flexible and self-motivated person who can work
under pressure and implement jobs in tight schedule.
Responsibilities include:
Required Skills:
Regular Job 3:
Job Description:
The Quality Engineering team at Red Hat is looking for engineer to test
linux file systems, including btrfs, xfs, ext4, etc. You need to search
for, analyze, report, track kernel file system defects and verify bug
fixes. You should be a self motivated person and have passion in finding
bugs/defects in linux file systems.
Responsibilities include:
Required Skills:
Regular Job 4:
Job Description:
The Quality Engineering team at Red Hat is looking for engineers to
search for, analyze, report, track defects and verify bug fixes in the
Linux kernel. We are looking for an experienced QA Engineer with strong
technical skills. You must be a flexible self-starter who can come up to
speed quickly with new technologies and can adapt to a growing and
evolving team.
Responsibilities include:
Required Skills:
Regular Job 5:
Job Description:
The Quality Engineering team at Red Hat is looking for engineer to test
linux kernel network, including network protocols, NIC drivers, bonding,
vlan, bridge, etc. You need to search for, analyze, report, track kernel
network defects and verify bug fixes. You should be a self motivated
person and have passion in finding bugs/defects in linux network.
Responsibilities include:
Required Skills:
From: Hacker’s Delight Author: Henry S. Warren
I think that I shall never envision
An op unlovely as division.
An op whose answer must be guessed
And then, through multiply, assessed;
An op for which we dearly pay,
In cycles wasted every day.
Division code is often hairy;
Long division’s downright scary.
The proofs can overtax your brain,
The ceiling and floor may drive you insane.
Good code to divide takes a Knuthian hero,
But even God can’t divide by zero!
可能你也会感到吃惊，在C99/C11标准中，bool 的定义居然是个宏，而不是 typedef 类型！
C11 第 7.18 节中明确提到： The macro “bool” expands to _Bool.
而且 false 和 true 也是宏……不过，它下面接着有解释：
Notwithstanding the provisions of 7.1.3, a program may undefine and perhaps then
redefine the macros bool, true, and false.
可见之所以把它们定义成宏是为了让用户可以重定义，想必在C99 之前应该有不少C程序都自己定义了 bool，false 和 true 吧！而且第 7.31.9 节中说这个以后会去掉：
The ability to undefine and perhaps then redefine the macros bool, true, and false is
an obsolescent feature.
你要是感到不爽，你可以这么做：
[c]
typedef _Bool bool;
[/c]
From: http://www.3quarksdaily.com/3quarksdaily/2011/06/a-crab-canon-for-douglas-hofstadter.html
读过《集异璧》的同学一定对里面的“卡农”印象深刻，这里有人又专门写了一首“卡农”的诗，窃以为更好。转过来欣赏一下。
SEASIDE CANON, for Douglas Hofstadter
by Julia Galef
~
The ocean was still.
In an empty sky, two gulls turned lazy arcs, and
their keening cries echoed
off the cliff and disappeared into the sea.
When the child, scrambling up the rocks, slipped
out of her parents’ reach,
they called to her. She was already
so high, but those distant peaks beyond —
they called to her. She was already
out of her parents’ reach
when the child, scrambling up the rocks, slipped
off the cliff and disappeared into the sea.
Their keening cries echoed
in an empty sky. Two gulls turned lazy arcs, and
the ocean was still.
~
From: http://edweissman.com/53640595
Author: Ed Weissman
My friends all think
that I’m a neb
Cause I spend much time
here on the web
The good things here
I do not abuse
Except lots of time
on hacker news
I don’t read reddit
I will not digg
I’m not on facebook
My work’s too big
I do not text
I do not tweet
I just work on
Things that are neat
I check email
throughout the day
But there are no games
that I will play
My phone’s on vibrate
I do not chat
My work is really
Where it’s at
Knuth and Turing
are my big heroes
I love to move
Ones and zeros
My head is down
I’m in the mode
Don’t bother me
I have to code
Those who need me
leave voicemail
I’m much too busy
trying not to fail
I learn on-line
and from my schools
But I must avoid
all sorts of trolls
I can’t believe
I wrote this ode
When I have so much
I have to code
I’m not an addict
I have no drug
I’ve got to go
To fix a bug