Liuw's Thinkpad

I’ve been reading Linux Device Drivers 3rd for quite a long time, and once built a sacrifice system in VMWare. After I upgraded VMWare, the sacrifice kernel hangs, unable to discover root filesystem. It seems to be a driver issue. No matter how I compile my kernel, it hangs at the same place.

I finally give up, I don’t want to waste my time any more. Maybe I should just dump that 2.6.10 and try new ones. No need to

I have a Debian system working as my development system. I just need to install kernel header to get a module building environment.

# apt-get install linux-headers-`uname -r`

When it’s done, build directory should be found in

# ls -d /lib/modules/`uname -r`/build

Here is a handy Makefile for modules.

obj-m += hello.o

all:
        make -C /lib/modules/$(shell uname -r)/build M=$(PWD) modules

clean:
        make -C /lib/modules/$(shell uname -r)/build M=$(PWD) clean

Pete Zaitcev gives the following summary:

• If you are in a process context (any syscall) and want to lock other process out, use a semaphore. You can take a semaphore and sleep ( copy_from_user* or kmalloc(x,GFP_KERNEL) ).
• Otherwise (== data can be touched in an interrupt), use spin_lock_irqsave() and spin_unlock_irqrestore().
• Avoid holding spinlock for more than 5 lines of code and across any function call (except accessors like readb).

Read the rest of this entry »

I used to find some papers on Read-Copy Update mechanism, but I didn’t quite get the point, that the Updater is sure that no reader will hold a reference to old data when all CPU has been scheduled at least once so that the Updater can safely reclaim the old data.

I found the answer in Linux Device Drivers 3rd edition, as quoted.

On the read side, code using an RCU-protected data structure should bracket its references with calls to rcu_read_lock and rcu_read_unlock. as a result, RCU code tends to look like:

struct my_stuff *stuff;

rcu_read_lock();
stuff = find_the_stuff(args…);
do_something_with(stuff);
rcu_read_unlock();

The rcu_read_lock call is fast; it disables kernel preemption but does not wait for anything. The code that executes while the read “lock” is held must be atomic. No reference to the protected resource may be used after the call to rcu_read_unlock.

[...snip...]

All that remains is to free the old version. The problem, of course, is that code running on other processors may still have a reference to the older data, so it cannot be freed immediately. Instead, the write code must wait until it knows that no such reference can exist. Since all code holding references to this data stucture must (by the rules) be atomic, we know that once every processor on the system has been scheduled at least once, all references must be gone. So that is what RCU does; it sets aside a callback that waits until all processors have scheduled; that callback is then run to perform the cleanup work.

As the bold text mentioned above, RCU is working mostly by the rules.

In fact, a ‘^M’ in text file is a carriage return (CR), often introduced by DOS text file format. It’s possible to do a simple substitution to get rid of it.

Easiest way is to use a dedicated tool called `dos2unix’, and yes, there is a corresponding tool called `unix2dos’.

Or, we can use Vim/Emacs to convert it.

(first open file with Vim)
:set ff=unix
:set ff=dos

Or use Vim command line switches.

$ vim +"set ff=unix" +wq $DOS_FILE

In Emacs, just do a substitution. Use C-q C-m to input ^M.

# dpkg-reconfigure locales
# dpkg-reconfigure tzdata

第一个方法，最简单那当时是直接写脚本。但是那样不够灵活，每次只能执行特定的指令。

第二个方法，使用tentakel。

第三个方法，使用multixterm。

个人觉得第三个方法最好，但是也没有实际用过。这些东西都是老林问我我才查查的，没有实践，先记下了。

换了一台新机器去做TPM硬件驱动的开发，于是从远程仓库把代码clone下来。试着把代码编译一次，出问题了，满版的错误，费点时间看了一下，其实是stddef.h没有找到造成的。

新机器和原来的机器都是一样系统，工具链也是一样的，代码也已经在我原来的机器上编译通过了。用find找了一下stddef.h，在机器上也是有的。仔细对比了一下通过和不通过的CFLAGS，发现不通过的情况下，头文件路径中没有gcc的包含路径，问题就出在这里了。

再看Makefile，gcc路径是通过如下的方法取得的。

GCC_INSTALL = $(shell gcc --print-serarch-dirs | sed -n -e 's/install: \(.*\)/\1/p')

使用sed匹配了以install开头的行。

但是，我现在这个系统的locale是中文的，所以“install”没有出现，取而代之的是“安装”，匹配不成功，GCC_INSTALL就成了空值，那么也没有把路径加入。

追踪了半天，没想到是locale出了问题。因为我原来一直用的是英文系统，所以没有遇到过这种情况。所以以后装系统，最好还是用英文的locale，不是说崇洋媚外不喜欢中文，要是遇到我今天的情况，估计还是挺恶心的，看着满版的错误，挺郁闷的。

我们的项目需要改Xen用户空间的工具。Xen用户空间的工具是用Python写的，代码量还不小，用人肉方法去跟踪执行路径那是很笨的办法。我们需要trace调用，又不能改变函数原来的行为，那么最好的办法就是用decorator了。上网找一下，已经有人做过这样的工作了，我综合一下，改成下面的样子。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Decorators used to trace function/method calls
# derive from:
# http://wordaligned.org/svn/etc/echo/echo.py
# http://svn.osafoundation.org/chandler/trunk/chandler/util/autolog.py
#
# liuw
# 2010-5-27

import types

# Should use python log facility?
def do_log(s):
    print s

def _format_arg_value(arg_val):
    arg, val = arg_val
    return '%s=%r' % (arg, val)

def log_wrapper(fn, display_name=None):
    import functools
    if not display_name: display_name = fn.__name__

    code = fn.func_code
    arg_count = code.co_argcount
    arg_names = code.co_varnames[:arg_count]
    fn_defaults = fn.func_defaults or list()
    arg_defs = dict(zip(arg_names[-len(fn_defaults):], fn_defaults))

    @functools.wraps(fn)
    def wrapped(*v, **k):
        global indent

        positional = map(_format_arg_value, zip(arg_names, v))
        defaulted = [_format_arg_value((a, arg_defs[a]))
                     for a in arg_names[len(v):] if a not in k]
        nameless = map(repr, v[arg_count:])
        keyword = map(_format_arg_value, k.items())

        args = positional + defaulted + nameless + keyword

        do_log('%s(%s)' % (display_name, ', '.join(args)))
        return fn(*v, **k)
    return wrapped

def log_class(cls, methodAsFunction=False):
    """Python does not support class decorator, use it this way:
        class ClassName:
            ...
        ClassName = log_class(ClassName)
    """
    # disallow ALL builtin functions/methods
    allow = lambda s: not (s.startswith('__') and s.endswith('__'))

    names = cls.__dict__.keys()

    for name in names:
        if not allow(name): continue

        value = getattr(cls, name)

        if methodAsFunction and callable(value):
            setattr(cls, name, log_wrapper(value))
        elif isinstance(value, types.MethodType):
            # a normal instance method
            if value.im_self == None:
                setattr(cls, name, log_wrapper(value))

            # class and static method are more complex
            # class method
            elif value.im_self == cls:
                w = log_wrapper(value.im_func,
                               display_name='%s.%s' % (cls.__name__,
                                                       value.__name__))
                setattr(cls, name, classmethod(w))
            else:
                assert False

        # static method
        elif isinstance(value, types.FunctionType):
            w = log_wrapper(value,
                            display_name='%s.%s' % (cls.__name__,
                                                    value.__name__))
            setattr(cls, name, staticmethod(w))
    return cls

def log_module(m):
    # import m if m hasn't been imported
    if isinstance(m, str):
        d = {}
        exec 'import %s' % m in d
        import sys
        m = sys.modules[m]

    names = m.__dict__.keys()
    for name in names:
        value = getattr(m, name)
        if isinstance(value, type):
            setattr(m, name, log_class(value))
        elif isinstance(value, types.FunctionType):
            setattr(m, name, log_wrapper(value))

# ------------------------------TEST----------------------------------
class C1:
    @classmethod
    def f1(self, a, b=1, c=2):
        """f1"""
        pass

    @staticmethod
    def f2(d , e=3, f=4):
        """f2"""
        pass

    def f3(self, g):
        """f3"""
        pass
C1 = log_class(C1)

@log_wrapper
def test(x):
    pass

if __name__ == '__main__':
    inst = C1()
    inst.f1(10)
    inst.f2(20)
    inst.f3(1000)
    test(321)

functools.wraps这个decorator可以保证被修饰函数/方法的其他attribute与被wrap之前无异。比较让我感慨的是，我参考的有一部分是Chandler的代码，这个项目现在仍健在，实在不易。

看到很多散列表（hash table）的实现中，长度都是一个素数。至于为什么一定要用素数，一下子也没想出所以然来。上网搜索了一下相关的文章，发现很多人也在讨论这个问题。

http://www.cs.unm.edu/~saia/numtheory.html

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth-2

http://blog.csdn.net/ilibaba/archive/2009/03/05/3960142.aspx

长度是否要是素数，能不能是合数，这个问题大家的意见得不到统一。支持用素数的人的理由是，素数可以使得散列的分布更加均匀。

自己总结一下看这些文章的心得。一个散列运算可以等价如下式：

hash(k) = mix(k) mod m

散列计算中，求余往往是最后一步，因为没有机器拥有无限的内存，所以必须把结果放入到有限的桶（bucket）中。求余前的运算，假如混淆（mix）得比较好的话，那么m使用素数还是合数，分布是一样的。假如混淆（mix）得不够好的话，那么一个素数可以把一些common pattern加以区别。至于什么样的数据混淆用什么样的mix算法比较好，这个得经统计才可以得出结论。总的来讲，使用一个素数总没有错，虽然运行慢了点，却可以得到相对较好的统计特性。个人看法。

Knuth的The Art of Computer Programming中，也用的是一样的理由推荐用素数的m。手上没有书，他应该没有提到合数的问题。上面也仅仅是我个人的一些想法，没有经过严格的证明，我也没有能力去证明。当然，很欢迎有人来指正我的错误。

手上有《算法导论》，第十一章散列表，对这个问题也没有给出严格的证明。但是它提到这样的一个问题，若m=2^p-1，则所有以2^p为基数的解释的字符串，无论字符位置怎么变化，得出的散列值都是一样的。这个证明比较简单，用同余的性质就可以证明，最后的值，其实是各个字符值的和再对m取余，所以散列值不会随字符的位置发生变化。

UPDATE：

StackOverflow上也有对这个问题的讨论。

http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus

上面的文章的观点和我总结出来的基本一致。

“零拷贝”这个词也听到不少了，据说是可以明显提高性能。网上找到好文一篇。

Zero Copy I: User-Mode perspective

在一些程序，比如说HTTP服务器，需要向用户发送文件，有一部分是图片、静态网页之类不需要处理就可以直接发送的文件。土一点的做法无非是：

read(file_fd, buf, len);
write(socket_fd, buf, len);

实际上，read(2)这个操作，是首先把文件内容读入到内核缓冲区中去，然后再把文件内容从内核缓冲区拷贝到用户缓冲区；而write(2)这个操作，需要把用户缓冲区的内容拷贝到内核缓冲区。我们不需要对文件内容进行处理的情况下，却多用了一道拷贝工序，直接造成的开销有多了一次的上下文切换，以及浪费了缓冲区的内存。

为什么不把拷贝到用户空间的这一道工序去掉了，内核的两个缓冲区直接拷贝就好了。目前流行的做法是用sendfile(2)，在Linux里面的作用是把数据从一个文件描述符直接拷贝到别一个文件描述符。但是sendfile(2)的实现，好像是各个系统都有差异，使用的时候需要注意一下，在使用的时候最好先查一下手册。

但是从内核缓冲区到内核缓冲区的“零拷贝”，还不算真的完全没有拷贝。真正的“零拷贝”需要硬件支持。在具备Gather操作的DMA硬件支持下，内核只需要修改内部文件描述符的指向，然后等待硬件自动执行Gather操作，把数据取走。