Archives

perfbook 读书笔记:livelock

注:本文以及后面的文章中提到的 perfbook 均是指大牛 Paul E. McKenney 的书,《Is Parallel Programming Hard, And, If So, What Can You Do About It?》,书名太长,故简写之。

最近一直在读这本 perfbook,它算是少有的全面而专门介绍 locking 的书,值得每个系统程序员去读。在读的过程中发现有的地方它介绍的并不是很详细,所以就写几篇读书笔记也算是对它的小小补充。

书中 6.1.2 节讲到了 livelock,即所谓的“活锁”,相对于死锁(deadlock)而言。因为上过操作系统课的原因,我估计很多人对 deadlock 并不陌生,但是 livelock 相对不那么熟悉。livelock 无非是饥饿(starvation)的极端情况。饥饿是由竞争引起,所谓竞争(contention)是指尝试获取一个已经被锁住的锁,长时间竞争会导致这些得不到锁的进程饥饿,所以饥饿的极端情况就是多个进程一直在尝试获取某一(几)把锁,但一直都得不到满足。

书中给出的例子很简单,解决方法是给两个进程加上不同延迟,也同时增加了 overhead,所以这个例子并不是很好。我们看一个现实中的例子,Linux 内核中的一个 livelock 的 bug:

commit eaf5f9073533cde21c7121c136f1c3f072d9cf59
Author: Miklos Szeredi
Date: Tue Jan 10 18:22:25 2012 +0100

fix shrink_dcache_parent() livelock

发生 livelock 的地方是 shrink_dcache_parent(),看其定义:
[c]
void shrink_dcache_parent(struct dentry * parent)
{
LIST_HEAD(dispose);
int found;

    while ((found = select_parent(parent, &dispose)) != 0)
            shrink_dentry_list(&dispose);

}
[/c]

根据这个 commit 的描述,我们可以发现存在下面这种情况:

1. CPU0 上的进程调用 select_parent(P) 找到了 dentry C,并把它放入 dispose 链表中,返回1;

2. 与此同时,CPU1 上的另一个进程也调用了select_parent(P),获取了 dentry P 的 ->d_lock;

3. CPU0 上的进程继续调用 shrink_dentry_list(),获取了 dentry C 的 ->d_lock,然后又调用 try_prune_one_dentry(C),dentry_kill(C):

[c]

if (inode && !spin_trylock(&inode->i_lock)) {
relock:
spin_unlock(&dentry->d_lock);
cpu_relax();
return dentry; / try again with same dentry /
}
if (IS_ROOT(dentry))
parent = NULL;
else
parent = dentry->d_parent;
if (parent && !spin_trylock(&parent->d_lock)) {
if (inode)
spin_unlock(&inode->i_lock);
goto relock;
}
[/c]

因为另一个进程持有dentry P的->d_lock,所以 dentry_kill() 中 spin_trylock(&parent->d_lock) 失败,转而 spin_unlock(&dentry->d_lock) 并返回;

4. CPU1 上的进程此时仍在调用 select_parent(P),并找到了 dentry C,锁住了它的->d_lock,放入 dispose 链表并返回1(其实就是重复步骤(1));

5. CPU0 上的进程继续 shrink_dentry_list() 中的循环,发现 dispose 链表已经为空,退出循环并返回;

6. CPU1 的进程开始重复步骤(3);

7. CPU0 的进程开始重复步骤(2)。

Livelock 产生了!

这里问题的关键在于那个 dispose list,如果 dentry C被某个进程加入到 dispose list 中,另外的进程不应该再找到它,所以修复就是加一个标志位 DCACHE_SHRINK_LIST,来标示这个 dentry 有没有被加入。

用宏实现 alignof

我们知道在C2011标准中引入了 alignof 操作符,但是在 gcc 和 glibc 完全支持 C2011 之前,我们仍然不能使用它。其实我们可以自己用宏实现一个(出自c.l.c):

define AlignOf(type) (offsetof(struct { char c; type t; }, t))

它巧妙地把参数指定的类型放入一个结构体中,在此结构体的最前面镶入一个 char 类型,这样该成员在结构体中的偏移就是它对齐的位置。看例子:

[c]

include

include

include

define AlignOf(type) (offsetof(struct { char c; type t; }, t))

int main(void)
{
struct foo { char a; int b; long c; };
typedef struct foo bar[128];

printf("sizeof foo: %lun", sizeof(struct foo));
printf("AlignOf foo: %lun", AlignOf(struct foo));
printf("sizeof bar: %lun", sizeof(bar));
printf("AlignOf bar: %lun", AlignOf(bar));
return 0;

}
[/c]
输出:
sizeof foo: 16
AlignOf foo: 8
sizeof bar: 2048
AlignOf bar: 8

再见,大理!

从去年7月初开始,在大理待了半年多了。明天一早就要离开大理了,各种舍不得……这期间因为去新疆离开过一次,可这次不同,下次再回来不知道是何时。

大理是我在国内能找到的最适宜居住和生活的地方了,没有之一。我理想中的生活有两种:一种是在路上,四处漂泊浪迹天涯;另一种是像在大理这样,白天晒晒太阳,晚上和朋友喝喝茶,打打牌,聊聊天,日子就这么无忧无虑地过着……

希望以后你们哪一位去往大理转,路过人民路超人蔬菜馆,给鸟哥打声招呼;路过人民路养生粥,买碗粥,顺便给老板小月打声招呼;若住在叶榆路阿弟家客栈给老板杨姐问声好!

再见,大理!不知道下次再回来你会变成什么样子!就算是真变成了“失败者乐园,老少边穷文艺中青年扎堆,街上十个人九个神经病,五个飞叶子,三个修禅的,一个摆地摊的”也千万不要变成丽江那样搞一夜情的圣地!不要!

(相册:在大理的日子

关于 extern inline

(本文是《C语言编程艺术》的一部分,转载请注明出处,勿用于商业用途。)

大家一定对C语言 inline 关键字不陌生,甚至经常用到 static inline 的函数。可能感到陌生的是 extern inline。C11 标准在6.7.4 p7 中对此进行了描述,不过比较生涩难读。简单地讲,static line 和 extern inline 的区别,从名字上也能看得出来,就是编译单元之外可见性的问题。把一个普通函数给内联掉之后,一个显著的区别就是外部可见性没了,怎么能同时既能内联又能保留外部的可见性呢?为了解决这个问题就有了extern inline。

static inline 是说这个函数就这么一个,而且没有外部可见性,在所有的编译单元中大家必须共用这么一个定义,这也是为什么 static inline 通常要放到头文件中的原因;而 extern inline 就不一样了,它是说这个函数虽然只有一个定义,但是既有内联的版本,也有非内联的版本,如果你能看得到它的定义。即在同一个编译单元中,那么你就可以用它的内联版本;看不到的话,你就可以用非内联版本,即和其它普通函数一模一样。

而如果既不带 static 也不带 extern 的话,含义又不同了:前面的 extern inline 只需要定义一次,只是不同的地方看到的版本不同,有的地方看到的是内联的版本,而有的地方看到的只是个 external reference。而仅用 inline 的话,就变成了要定义两次,带 inline 关键字的这个定义就是内联版本,在这个编译单元中都用这个版本,而在外部,还是使用普通的非内联定义。换句话说,带 inline 的定义遮盖住了外部的定义。既然有两个不同的版本,那么也就需要保持这两个版本的定义相同,否则就会有问题。

以上是标准C的定义,而 GNU89 的定义就不同了,基本上是把”extern inline”和”inline”的含义给交换了,“static line” 的含义都是相同的。看下面的标准C的例子:

[c]
//a.c
//C99
extern inline int max(int a, int b)
{
return a > b ? a : b;
}

int a = 10;
int b = 20;
int foo(void)
{
return max(a, b);
}

extern int bar(void);

int main(void)
{
return foo() + bar();
}

//b.c
//C99
extern int max(int a, int b);

int bar(void)
{
int a = 10;
int b = 20;
return max(a, b);
}
[/c]

我们这么编译:
% gcc -std=c99 -O2 -Wall -W a.c b.c -o c

而我们如果把它编译成 GNU89 的话,就会报错:
% gcc -std=gnu89 -O2 -Wall -W a.c b.c -o c
/tmp/ccAJTzwY.o: In function bar': b.c:(.text+0xb): undefined reference tomax’
collect2: ld returned 1 exit status

很明显,因为 GNU89 中的 extern inline 需要两个定义,明显我们少了一个。修改后的代码如下:

[c]
//a.c
//GNU89
extern inline int max(int a, int b)
{
return a > b ? a : b;
}

int a = 10;
int b = 20;
int foo(void)
{
return max(a, b);
}

extern int bar(void);

int main(void)
{
return foo() + bar();
}

// b.c
//GNU89
int max(int a, int b)
{
return a > b ? a : b;
}

int bar(void)
{
int a = 10;
int b = 20;
return max(a, b);
}
[/c]

glibc 中就用到了 GNU89 的extern inline 特性,在 ctype.h 中,tolower()/toupper() 的定义是:
[c]

ifdef __USE_EXTERN_INLINES

extern_inline int NTH (tolower (int c))
{
return
c >= -128 && c = -128 && c = -128 && c = -128 && c < 256 ? __ctype_toupper[c] : c;
}
[/c]

顺便说一句,gcc 提供了-fgnu89-inline 和 -fno-gnu89-inline 选项可在编译时控制上述 inline 的行为。

Stackoverflow 上有人做了一个很好的总结,我翻译了一下:

GNU89:

"inline": 函数可能会被内联掉,非内联的版本总是会生成,而且外部可见,因此内联的定义在本编译单元中只能有一次,其它地方看到的是非内联版本。

"static inline":不会生成外部可见的非内联版本,可能会生成一个 static 的非内联版本。它当然可以被定义多次,因为外部看不到它。

"extern inline":不会生成一个非内联的版本,但是可以调用一个非内联版本(因此你必须在其它编译单元中定义它)。只能有一个定义的规则当然也适用,非内联版本和内联版本的代码必须是一样的。

C99 (or GNU99):

"inline":和 GNU89 的 "extern inline" 一样,没有外部可见的函数生成,但是外部可见的函数必须存在,因为有可能会用到它。

"extern inline":和 GNU89 的 "inline" 一样, 会生成外部可见的代码,最多一个编译单元可以使用它。

"static inline":和 GNU89 的 "static inline" 一样,这是唯一一个在 GNU89 和 C99之间可移植的。

最后,我们可以看大神 Linus Torvalds 如何描述 extern inline:

“static inline” means “we have to have this function, if you use it, but don’t inline it, then make a static version of it in this compilation unit”. “extern inline” means “I actually have an extern for this function, but if you want to inline it, here’s the inline-version”.

参考资料:
http://www.greenend.org.uk/rjk/tech/inline.html
http://gcc.gnu.org/ml/gcc/2006-11/msg00006.html
http://stackoverflow.com/questions/6312597/is-inline-without-static-or-extern-ever-useful-in-c99
http://www.cnblogs.com/cnmaizi/archive/2011/01/19/1939686.html

不同人眼中的我

在别人眼中我是

在我朋友眼中我是

在同行眼中我是

在我女朋友眼中我是

在我父母眼中我是

我以为我是

而实际上我是

终有一天我会是

怀念适之

先生过世已经整整50周年了,可先生充满智慧的话至今仍振聋发聩。无怪乎有人说“二十世纪是鲁迅的世纪,二十一世纪是胡适的世纪”!

1. “容忍比自由更重要 。

我常常用来自勉。

2. “宁鸣而死,不默而生。

适用于沉默的大多数。

3. “做学问要在不疑处有疑,待人时要在有疑处不疑。

适用于方舟子。

4. “有人告诉你‘牺牲你个人的自由去争取国家的自由’可是我要告诉你‘为个人争自由就是为国家争自由,争取个人的人格就是为社会争人格。真正自由平等的国家不是一群奴才建立起来的。’

适用于司马南、胡锡进这种奴才。

5. “一个肮脏的国家,如果人人讲规则而不是谈道德,最终会变成一个有人味儿正常国家,道德自然逐渐回归;一个干净的国家,如果人人都不讲规则而大谈道德、高尚,天天没事儿就谈道德规范,人人大公无私,最终会堕落成为一个伪君子遍布的肮脏国家。

适用于那些天天号召别人学习雷锋的人。

6. “美国人来了,既有面包也有自由;苏俄来了,只有面包没有自由;他们来了,既没有面包也没有自由。

原来先生几十年前就看破了……

关于 tmpfs

“tmpfs” 是 Linux 内核中另一个让人困惑的名字,它的实现是在 mm/shmem.c,”shmem” 猛一看和 “tmpfs” 根本不沾边,虽然我们知道 tmpfs 是基于内存的!我们可以通过看一下 tmpfs 都被用到哪些地方来了解它到底为什么叫这个名字。

你的桌面 Linux 系统中基本上都会挂载了 tmpfs:

% grep tmpfs /proc/mounts
devtmpfs /dev devtmpfs rw,seclabel,nosuid,relatime,size=1958956k,nr_inodes=489739,mode=755 0 0
tmpfs /dev/shm tmpfs rw,seclabel,nosuid,nodev,relatime 0 0
tmpfs /run tmpfs rw,seclabel,nosuid,nodev,relatime,mode=755 0 0
tmpfs /sys/fs/cgroup tmpfs rw,seclabel,nosuid,nodev,noexec,relatime,mode=755 0 0
tmpfs /media tmpfs rw,rootcontext=system_u:object_r:mnt_t:s0,seclabel,nosuid,nodev,noexec,relatime,mode=755 0 0

正如这篇文章中提到的,/dev/shm 是 POSIX IPC 用到的,用来实现进程间通信。除了 sem_open(3) 的中 oflag 参数,基本上看不出来和文件有什么相关。

除此之外,另一个用到它的地方是 anonymous shared mapping!

mmap_region():

        if (file) {
        //...
        } else if (vm_flags & VM_SHARED) {
                error = shmem_zero_setup(vma);
                if (error)
                        goto free_vma;
        }

shmem_zero_setup() 在内核通过 kern_mount() 挂载的(用户不可见的) tmpfs 的根目录中创建了一个”dev/zero”的文件,注意,这里可以重复创建哦,因为内核跳过了类似 may_create() 的检查,而且这个文件本身很特殊,它一开始就是 unlinked 的。所以内核实际上是通过 tmpfs 中的一个文件来实现了匿名的共享映射!到此,你可以看出,tmpfs 这个名字其实名副其实了。

另外,tmpfs 本身可以随意挂载,通过 mount -t tmpfs,你可以在上面进行任意文件操作。所以,内核通过 tmpfs 一套代码把下面三个东西给统一起来了:1. 匿名共享映射;2. POSIX IPC;3. tmpfs 文件操作。Mel Gorman 这样解释到:

This is a very clean interface that is conceptually easy to understand but it does not help anonymous pages as there is no file backing. To keep this nice interface, Linux creates an artifical file-backing for anonymous pages using a RAM-based filesystem where each VMA is backed by a “file” in this filesystem. Every inode in the filesystem is placed on a linked list called shmem_inodes so that they may always be easily located. This allows the same file-based interface to be used without treating anonymous pages as a special case.

之所以用 tmpfs 而不是同样基于内存的 ramfs 是因为:1) tmpfs 文件是可以 swap 的;2) tmpfs 是有大小限制的,不会允许用户无限制使用内存从而导致 OOM。(注:只有当 CONFIG_SHMEM=n 时,tmpfs 才会调用 ramfs 代码。)

bash 反斜线的一个疑问

ABS 里在讲解 echo 的转义时,给出过下面这几个例子:

bash-4.2$ echo \z
z
bash-4.2$ echo \z
z
bash-4.2$ echo echo \z
z
bash-4.2$ echo echo \z
z

我们知道反引号会把里面命令的输出直接传递给外面的命令,那么,既然前两个echo的输出一样,为什么后面就不一样呢?这里一定发生了什么我们没有注意到。我来根据我的理解来解释一下。

从第一个开始看,”\z”中的第一个反斜线表示转义后面的那个反斜线,所以输出””,”z”直接输出,最后得到“z”。

第二个也不难,”\z”中前两个反斜线同样输出””,后面剩下”z”,因为 echo 默认不解释转义,所以就算是”z”有特殊含义也不会被解释,因此”z”中的””会把”z”的特殊含义(本身就没有)去掉,然后输出”z”,最后得到”z”。

从第三个开始就复杂了。因为有了 subshell,所以里面的反斜线一定被处理过两次:一次是 subshell 中,另一次是外面的 shell。外面的shell开始处理,”\”同样被处理成””,处理完成后得到:echo echo z;然后 subshell 开始执行里面的”echo z”,处理””然后输出z,最后外面的shell 看到的是 echo z,输出”z”,结束。

第四个更复杂一些,外面的shell处理反斜线后得到:echo echo \z,前两个”\”依旧被解释成””,剩下的”z”会原封不动,因为”z”对于外面的shell来说没兴趣,它只对”`”或”$”这样的转义感兴趣!subshell 执行“echo \z”,同第一个例子,输出z,这时外面的shell看到的是echo z,输出”z”,结束。

例子虽简单,却能反映出我们确实对 bash 还有一些角落的地方没有理解清楚。理解 ABS 后面的例子就留给你作为课后作业了。:-)

2012 年祝你幸运

2011 年马上就要过去了,回顾过去的一年,我发现最正确的决定就是离开北京。北京的空气污染已经到了非常严重的程度,奉劝各位能不去北京就别去,别拿自己的身体健康开玩笑。在这个神奇的国度,能让自己健康地活着本身就是一种很大的成功!

在 2011 年中,中华民族已经到了最坑爹的时候,所以在 2012 年里,祝愿大家都能有新鲜的空气呼吸,能有正常的牛奶喝,能有健康的食用油吃,能有一所房子不被强拆,能有个孩子是亲生的,能扶起老太不被讹,最关键的是,能让自己不被活埋!

虽然你仍然不可能像对岸一样能投上一票,但是你能选择离开。所以,有钱有本事的还是尽早移民吧!没本事的就好好练习游泳,游到对岸去!要自由从来都不丢人,“我们这儿”才丢人!

说了那么多,我觉得,在所有的新年祝福辞里,“祝你幸运”是最好的,也是最现实的祝福了。所以,祝你 2012 年幸运!

最后祝愿所有的五毛,全家都搬到朝鲜去,早日体会到社会主义的优越性!

2012 年,要幸福,更要自由。

扩展文件属性

我们知道,在 Linux 上最基本的文件属性是,

# ls -l foo
-rw-r--r--. 1 root root 0 Jan 19 00:03 foo

可以通过chmod 命令来更改,ls -l 来查看。

除此之外,一些文件系统上还提供额外的属性,比如 ext4 提供了额外的属性,比如 append only (a), compressed (c), immutable (i) 等属性,这些属性可以通过 e2fsprogs 软件包提供的 chattr(1) 来改变,lsattr(1) 来查看。更多属性也可参考 chattr(1)。比如:

# chattr +i foo
# lsattr foo
----i--------e- foo

这个是和文件系统密切相关的,一是因为 chattr 来自 e2fsprogs,二是因为它调用的系统调用也是和文件系统相关的一个 ioctl,可以看下面 strace 的输出:

open("foo", O_RDONLY|O_NONBLOCK|O_LARGEFILE) = 3
ioctl(3, EXT2_IOC_SETFLAGS or EXT3_IOC_SETFLAGS or FIONCLEX, 0xfffc347335c) = 0
close(3)                                = 0

还有一种文件属性叫扩展文件属性,eXtended ATTRibutes,也就是通常所说的 xattr。和前一种相比,这个就不那么和文件系统密切相关了,但是仍然需要文件系统的支持。这个是通过系统调用 getxattr(2) 和 setxattr(2) 来实现的,对应的命令是 getfattr(1) 和 setfattr(1),来自 attr 软件包。看例子:

# mount -o remount,acl,user_xattr /home
# touch bar
# setfattr -n user.comment -v "this is a comment" bar
# getfattr bar
# file: bar
user.comment

# getfattr bar -n user.comment
# file: bar
user.comment="this is a comment"

需要注意两点:一,挂载时需要加 "user_xattr" 选项;二,name 是有命名空间的,并不是任何命名空间都可以,比如,
# setfattr -n my.comment -v "this is my comment" bar
setfattr: bar: Operation not supported
用户只能用 user.* 名字,而后面的 ACL 则会用 system.posix_acl_access。当然了,SELinux 也会用到 xattr,security.*。 基于此,ACL 实现了访问控制列表,也就是说,设置某些用户的文件权限不再依赖于用户所在的组了,省去了不少麻烦。对应的命令是 setfacl(1) 和 getfacl(1) ,来自 [acl 软件包](http://acl.bestbits.at/)。从下面 strace 的输出,也可以看出它们确实是基于 xattr 的:
getxattr("foo", "system.posix_acl_access", 0xfffe455cca0, 132) = -1 ENODATA (No data available)
stat("foo", {st_mode=S_IFREG|0644, st_size=0, ...}) = 0
setxattr("foo", "system.posix_acl_access", "x02x00x00x00x01x00x06x00xffxffxffxffx02x00x06x00x00x00x00x00x04x00x04x00xffxffxffxffx10x00x06x00xffxffxffxff x00x04x00xffxffxffxff", 44, 0) = -1 EPERM (Operation not permitted)

之所以出现 ENODATA 是因为挂载文件系统时我没有指定”acl”,需要重新挂载:mount -o remount,acl /home 然后重新创建文件,因为旧的文件依旧是没有 ACL的。