RCU revisited
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.
Get rid of ^M in file
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.
Debian system-wide locale and timezone configuration
# dpkg-reconfigure locales # dpkg-reconfigure tzdata
Linux同时SSH到多个主机,执行相同命令
第一个方法,最简单那当时是直接写脚本。但是那样不够灵活,每次只能执行特定的指令。
第二个方法,使用tentakel。
第三个方法,使用multixterm。
个人觉得第三个方法最好,但是也没有实际用过。这些东西都是老林问我我才查查的,没有实践,先记下了。
locale惹的祸
换了一台新机器去做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,不是说崇洋媚外不喜欢中文,要是遇到我今天的情况,估计还是挺恶心的,看着满版的错误,挺郁闷的。
Python中跟踪函数/方法调用的Decorator
我们的项目需要改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
“零拷贝”这个词也听到不少了,据说是可以明显提高性能。网上找到好文一篇。
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操作,把数据取走。
好文传递:How To Become A Hacker
有个小计划,就是尽量能做到每日抽出一段时间来读点有趣的文章,把链接放在这,然后再记一下自己的想法。
其实前面也有写,比如说公众演说技巧和Memory Barriers的一些小结,应该都算是这类文章。但是直到今天,才真正萌发起这样的想法,能否把这个事情做得系统点,坚持下来,对自己也有好处。假如能做到有周期有规律,那自然是最好的,但是目前的情况是比较难实现的了,只能说有看就写了。
今天看的是Eric Steven Raymond写的How To Become A Hacker。
简要摘录一下,Hacker应有的态度是:1. 世界上有大量有趣的问题是等待解决的;2. 没有人应该需要解决同样的问题两次;3. 拒绝沉闷的事情;4. 自由;5. 信念不能代替能力。
ESR还提到Hacker的基本技能自然是过硬的编程能力、基本功等等。
个人觉得后面对于社区的讨论也比较有价值。在有了前面的基本能力之后,就必须要融入社区之中,从社区获取,也为社区作贡献。个人觉得,这是Hacker和一般程序员的最大的区别。在我的印象中,Hacker们总是热衷于各种各样的争吵,呵呵。
Shell实现求两个文件中不同行的行数
小胖提到的一个问题:有两个已经排序好的URL文件a和b,想要求出b中与a不同的行数。
太久没有写Shell了,还想了一阵用哪个命令好。
expr `wc -l b` - `comm -1 -2 a b | wc -l`
有更好的方法请指教。