Friday, 26. January 2007, 08:43:41

这真是一本让人惊讶的科幻小说！

全书充满了古怪和滑稽，想像大胆而疯狂，带给我们无限快乐的同时又不乏对人类的批判和嘲讽，可以说是有史以来最出色的科幻小说之一。有人评价说它很“无厘头”，作者在“一本正经地扯淡”，而作者恰恰就是在这种气氛中无声地嘲笑着人类的无知和麻木。你在被它逗乐的同时有没有进一步思考生命的意义呢？没有？很可能。不过没关系，记住《银河系漫游指南》封面上用大而友善的字母写下的忠告吧：不要恐慌。

小说中的几个主角，从最后的地球人阿瑟，到毫无实权的宇宙总统赞福德，再到唠唠叨叨的“唐僧”式的机器人马文，个个生动有趣，活灵活现，在整个搞怪的气氛中上演了一幕幕滑稽的表演。几位主人公用各种各样，一次比一次荒谬的方法在各种古怪的地方之间转移，整个故事从地球开始……

阿瑟是一个普通的地球人，住的房子要被拆除了，而他竟然提前一天从一个来推他房子的工人口中花5块钱打才听到这一消息，最后终于在规划办公室的一间废弃厕所里扔着的一个上了锁的文件柜的最低层中找到了那个被宣称“在本地的规划办公室展示了9个月了”的计划！古怪还没完，后面你会马上发现地球其实也是被一个非常类似的理由给清除了！因为修建星际快速通道，地球要在两分钟内被清除，这一计划同样在位于半人马座主星上的这个地区的规划部门里展示了50个地球年！天哪！结果地球上除了阿瑟和另外一个地球人（崔莉恩，到后面才出现），无一幸存！多么无厘头啊！全书就在这种气氛这中开始了。

阿瑟被他的伙伴──一个装扮成地球人的个星际漫游──福特·普里弗克特带到前来执行清除任务的那艘沃贡人的飞船中。沃贡人是银河系中最令人不愉快的种族之一，宇宙中最非凡的书《银河系漫游指南》就是这么说的。他们很不走运地被沃贡人发现了，所以，他们俩很快就扔了出去，却又神奇地被刚好路过的赞福德的“无限非概率驱动”飞船无意中救了上去。于是他们就结识了以后的旅伴──一个毫无实权的前宇宙总统赞福德，同样是来自地球的崔莉恩和一个唠唠叨叨的机器人马文。

接着他们去了“曾经存在过的最不可思议的行星”──已经死去500万年的曼格拉斯。原本是为了寻找宝藏，结果还没着陆就遇到了那里的古代原子能防御系统，但又离奇地躲过了攻击，因为飞船的非概率驱动把射来的核弹头变成了“不到时节就开放但又突然死掉的一盆牵牛花和一头无辜的鲸鱼”！！他们着陆后登上这颗行星，遇到了一个曼格拉斯老人──司拉提巴特法斯特和两只老鼠，后来他们终于知道了地球只不过是一台有机电脑的母体，运行着一个为期1000万年的研究程序来解决为什么“关于生命、宇宙，以及一切的终极答案”竟然只是小小的42！更让人懊恼的是，地球上的老鼠竟然是定制和管理地球的主人！“人类在老鼠身上作实验，观察它们行为的过程，竟然是老鼠精心安排的，以此用来研究人类”！！但是，如前所述，地球这台宇宙一切空间和时间中第一强大的电脑，在完成它的任务之前5分钟被毁掉了！

他们侥幸逃脱了曼格拉斯，准备驶向宇宙尽头餐馆。途中却遇到沃贡人的攻击，险些丧命，幸好赞福德的祖父的灵魂及时相救才幸免。赞福德被转送到了小熊星座贝塔星，可他还是没有逃过追捕，追捕者把他躲藏的大楼和他一起搬到了蛙星去接受处罚。他离奇地逃离了绝对透视旋涡后，又在被遗忘了的巡航班机上遇到了扎尼乌普，他正在寻找那个掌握实权的制造宇宙的家伙！他们从人造宇宙中转到真实宇宙中时掉进了非概率中，又正好落进他原来的非概率飞船中！和阿瑟他们又汇合了！

他们去了宇宙尽头餐厅，还没目睹宇宙尽头的景色就离开了，不巧的是他们进了一个被设定驶向太阳的飞船上！幸运的是在飞船上发现了一个神奇的传送设备，留下的可怜的马文把其它有机生物都传送走了。赞福德和崔莉恩又被送回了非概率飞船，和在那的扎尼乌普一起去了统治宇宙的人住的地方，拜访了这位神秘的人物；而阿瑟和福特却被传送到一艘高尔伽弗林查姆人移民的飞船上，他们随着一起到了那个殖民星球，而根据司拉提巴特法斯特留在冰川中的签名认出了这竟然是二百万年前的地球！可怜的阿瑟和福特，从地球来，结果转了一大圈又回到了地球！

故事就这样结束了，情节离奇而又生动。故事中间还经常一些穿插作者古怪的想像，比如：有个人竟然研究“过去这些年来他买的所有圆珠笔最后都怎么样了”；阿瑟的那句“看来我的生活方式碰到了相当大的困难”竟然被一个反常的虫洞带到了在时间上很早很早以前、在空间上几乎是无限远的一个银河系中，又引发了一场大规模杀戮。读完后不能不佩服作者过人的丰富想像力。同时，作者的语言风趣却又充满讽刺：可怜的人类居然是被他们一直瞧不起的老鼠所控制，而最终被离奇地消灭掉了；宇宙的命运和可爱的猫咪（让人想起薛定谔的猫）似乎又非常相关，因为那个统治宇宙的人也养着一只宠物猫；没有人能理解统治宇宙的人所讲的“疯疯癫癫”的话和奇怪的举动。

生命的意义到底是什么？宇宙的起源和命运又是什么？这似乎就是作者留给我们思考的问题，有答案了吗？恐怕没几个人会有！没关系，不要恐慌！有足够的时间留给你慢慢思考……

Sunday, 25. February 2007, 07:16:44

Linux内核源代码中有这么一个脚本文件：scripts/gcc-version.sh。它的主要代码如下：

     9  compiler=”$*”
    10
    11  MAJOR=$(echo GNUC | $compiler -E -xc - | tail -n 1)
    12  MINOR=$(echo GNUC_MINOR | $compiler -E -xc - | tail -n 1)
    13  printf “%02d%02dn” $MAJOR $MINOR
    14

从上面我们很容易看出它的用法，它要带一个参数，指明该平台上 GNU C编译器的命令（可能有些平台是cc）。它会给出GNU C编译器的版本号，以如下格式：XXYY，其中XX是主版本号，YY是次版本号，比如gcc-4.1的版本号就是0401。

这个脚本的实现很简单，它通过把GNU C编译器预先定义的宏GNUC和GNUC_MINOR展开后交给编译器的预处理器处理，处理后其实就应该是想要的结果了，但gcc会自动在前面插入自己的一些东西，所以，要截取最后一行才是真正的结果。-E选项是指明只进行预处理，注意：如果没有-o，-E默认的输出是标准输出；-x选项是要指明所使用的语言，这里指明的是c；-是说明输入来自标准输入，这主要是照顾管道。

另一个和gcc相关的脚本是scripts/gcc-x86_64-has-stack-protector.sh，它用来测试x86_64（x86_64是AMD的，IA-64才是Intel的）上是不是有堆栈保护，代码如下：

     3  echo “int foo(void) { char X[200]; return 3; }” | $1 -S -xc -c -O0 -mcmodel=kernel -fstack-protector - -o - 2< /dev/null | grep -q “%gs”
     4  if [ “$?” -eq “0” ] ; then
     5          echo $2
     6  fi

-fstack-protector选项是指明要检查堆栈是否会溢出，这是为了保护程序免于缓冲区溢出的攻击；-mcmodel=kernel是指明要为内核模式生成代码，Linux内核似乎要使用此选项。第3行的命令使用得更妙，还把中间命令的错误重定向到了/dev/null，而且还为grep开启了安静模式。似乎是从生成的汇编中找到”%gs”这个寄存器就说明有堆栈保护，但原理还是不明白;-(。

Friday, 2. February 2007, 06:07:27

王聪@西邮
红黑树是平衡二叉树的一种，它有很好的性质，树中的结点都是有序的，而且因为它本身就是平衡的，所以查找也不会出现非常恶劣的情况，基于二叉树的操作的时间复杂度是O(log(n))。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。

先到include/linux/rbtree.h中看一下rbtree的定义，如下：

struct rb_node
{
        unsigned long  rb_parent_color;
#define RB_RED          0
#define RB_BLACK        1
        struct rb_node *rb_right;
        struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

struct rb_root只是struct rb_node*的一个包装，这样做的好处是看起来不用传递二级指针了。不错，很简单。再看一下下面几个重要的宏，细心的你一定会发现，rb_parent_color其实没那么简单，Andrea Arcangeli在这里使用了一个小的技巧，不过非常棒。正如名字所暗示，这个成员其实包含指向parent的指针和此结点的颜色！它是怎么做到的呢？很简单，对齐起了作用。既然是sizeof(long)大小的对齐，那么在IA-32上，任何rb_node结构体的地址的低两位肯定都是零，与其空着不用，还不如用它们表示颜色，反正颜色就两种，其实只要一位就够了（估计此处也是照顾16位的机器）。 这样，提取parent指针只要把rb_parent_color成员的低两位清零即可：

#define rb_parent(r)   ((struct rb_node *)((r)-

取颜色只要看最后一位即可：

#define rb_color(r)   ((r)-

测试颜色和设置颜色也是水到渠成的事了。需要特别指出的是下面的一个内联函数：

static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link);

它把parent设为node的父结点，并且让rb_link指向node。 我们把重点集中在lib/rbtree.c上，看看一些和红黑树相关的重要算法。开始之前我们一起回忆一下红黑树的规则： 1\. 每个结点要么是红色要么是黑色； 2\. 根结点必须是黑色； 3\. 红结点如果有孩子，其孩子必须都是黑色； 4\. 从根结点到叶子的每条路径必须包含相同数目的黑结点。 这四条规则可以限制一棵排序树是平衡的。 __rb_rotate_left是把以root为根的树中的node结点进行左旋，__rb_rotate_right是进行右旋。这两个函数是为后面的插入和删除服务，而不是为外部提供接口。 新插入的结点都设为叶子，染成红色，插入后如果破坏了上述规则，通过调整颜色和旋转可以恢复，二叉树又重新平衡。插入操作的接口函数是

void rb_insert_color(struct rb_node *node, struct rb_root *root);

它把已确定父结点的node结点融入到以root为根的红黑树中，具体算法的分析可以参考MIT的《算法导论》第14.3节，这里的实现和书中的讲解几乎完全一样！怎么确定node的父结点应该在调用rb_insert_color之前通过手工迭带完成。值得指出的一点是，虽然插入操作需要一个循环迭代，但是总的旋转次数不会超过两次！所以效率还是很乐观的。 删除操作多多少少都有点麻烦，它要先执行像普通二叉查找树的“删除”，然后根据删除结点的颜色来判断是否执行进一步的操作。删除的接口是

void rb_erase(struct rb_node *node, struct rb_root *root);

其实它并没有真正删除node，而只是让它和以root为根的树脱离关系，最后它还要判断是否调用__rb_erase_color来调整。具体算法的讲解看参考《算法导论》13.3和14.4节，__rb_erase_color对应书中的RB-DELETE-FIXUP。此处的实现和书上也基本上一致。 其余的几个接口就比较简单了。

struct rb_node *rb_first(struct rb_root *root);

在以root为根的树中找出并返回最小的那个结点，只要从根结点一直向左走就是了。

struct rb_node *rb_last(struct rb_root *root);

是找出并返回最大的那个，一直向右走。

struct rb_node *rb_next(struct rb_node *node);

返回node在树中的后继，这个稍微复杂一点。如果node的右孩子不为空，它只要返回node的右子树中最小的结点即可；如果为空，它要向上查找，找到迭带结点是其父亲的左孩子的结点，返回父结点。如果一直上述到了根结点，返回NULL。

struct rb_node *rb_prev(struct rb_node *node);

返回node的前驱，和rb_next中的操作对称。

void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root);

用new替换以root为根的树中的victim结点。 红黑树接口使用的一个典型例子如下：

static inline struct page * rb_search_page_cache(struct inode * inode,
                                                 unsigned long offset)
{
        struct rb_node * n = inode-_
        struct page * page;

        while (n)
        {
                page = rb_entry(n, struct page, rb_page_cache);

                if (offset > page-
                        n = n-
                else if (offset < page-
                        n = n-
                else
                        return page;
        }
        return NULL;
}

static inline struct page * __rb_insert_page_cache(struct inode * inode,
                                                   unsigned long offset,
                                                   struct rb_node * node)
{
        struct rb_node ** p = &inode-
        struct rb_node * parent = NULL;
        struct page * page;

        while (*p)
        {
                parent = *p;
                page = rb_entry(parent, struct page, rb_page_cache);

                if (offset > page-
                        p = &(*p)-
                else if (offset < page-
                        p = &(*p)-
                else
                        return page;
        }

        rb_link_node(node, parent, p);

        return NULL;
}

static inline struct page * rb_insert_page_cache(struct inode * inode,
                                                 unsigned long offset,
                                                 struct rb_node * node)
{
        struct page * ret;
        if ((ret = __rb_insert_page_cache(inode, offset, node)))
                goto out;
        rb_insert_color(node, &inode-
 out:
        return ret;
}
_

Friday, 2. February 2007, 05:58:24

王聪@西邮

Linux内核中大量使用了队列，这里仅列举它在进程管理中的几处应用。

状态为TASK_RUNNING的进程都会被放入运行队列（runqueue）中，这是通过task_struct（定义在include/linux/sched.h）中的run_list成员来链接的。不过，为了让内核每次都能选取优先级最合适的进程，Linux为每个优先级构建了一个queue！这是通过struct prio_array来实现的，struct prio_array的定义（在kernel/sched.c）大致如下：

struct prio_array {
int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
};

queue成员就是队列数组。每个CPU有各自的runqueue，每一个runqueue又有包含两个prio_array，一个是活动队列，一个是时间片耗尽的队列。当运行队列空时，内核便会交换两个队列的指针！原来的耗尽队列就成了新的活动队列！这和prio_array中的bitmap是决定调度算法为O(1)的关键！

状态为TASK_STOPPED，EXIT_ZOMBIE或EXIT_DEAD的进程不会被放入专门的队列中，它们直接通过pid或者通过父进程的孩子队列来访问。

TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE状态的进程会被放入等待队列。不同的是，每个等待事件都会有一个等待队列，该队列中的进程等待同一事件的完成（不要惊慌！“事件”一个动态的过程，不好通过具体的结构来定义一个“事件”。这里等待一个事件就是查看某个条件是否为真，比如某个标志变量是否为真。）。wait_queue_head_t的定义（include/linux/wait.h）如下：

typedef struct _ _wait_queue_head {
        spinlock_t lock;
        struct list_head task_list;
    }wait_queue_head_t;

wait_queue_t的定义如下：

typedef struct _ _wait_queue {
        unsigned int flags;
        struct task_struct  task;
        wait_queue_func_t func;
        struct list_head task_list;
    }wait_queue_t;

进入等待状态的接口有两类：
prepare_to_wait()/finish_wait()
wait_event()
其实wait_event()内部也是调用prepare_to_wait()，把它放入一个循环中。而且wait_event()在事件完成时会自动调用finish_wait()。决定使用哪个要看情况而定。sleep_on*()是遗弃的接口，现在已经不再使用，虽然还支持。等待队列中的进程有两种，一种是exclusive的进程，另一种是nonexclusive的进程。所谓exclusive是指唤醒的进程等待的资源是互斥的，每次只唤醒一个（唤醒多个也可以，不过最后还是只有一个会被唤醒，其余的又被重新添加到等待队列中，这样效率会大打折扣）。一般，等待函数会把进程设为nonexclusive和uninterruptible，带“interruptible”的会专门指定状态为interruptible；而带“timeout”的会在超时后退出，因为它会调用schedule_timeout()；带“exclusive”的则会把进程设为exclusive。

唤醒的接口虽然只有wake_up*()，但它内部也分成好几种。带“interruptible”的唤醒函数只会唤醒状态是TASK_INTERRUPTIBLE的进程，而不带的则会唤醒TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE的进程；所有唤醒函数都会把等待同一事件的nonexclusive进程全部唤醒，或者把其中一个exclusive的进程唤醒；而带“nr”的则会唤醒指定个数的exclusive的进程，带“all”的会把全部exclusive进程唤醒。带“sync”会忽略优先级的检查，高优先级的进程可能会被延迟。最后，持有自旋锁时只能调用wait_up_locked()。