语源科技BlogJava-Snowdream

慎用xen的make world...

ZelluX — Wed, 01 Apr 2009 17:38:00 GMT

写了好几天的代码因为还有bug没de掉，没commit到svn上

然后不知怎么的在make的时候生成的kernel没变化，于是直接make world，然后发现linux kernel目录被清空了。。。

只能明天靠记忆慢慢补了，皑皑。

ZelluX 2009-04-02 01:38 发表评论

内存模型相关的资料

ZelluX — Wed, 25 Mar 2009 14:14:00 GMT

yifanw大牛半个月前发在c++版上的，怕以后忘了看先放在这备个忘吧

白话入门
http://www.newsmth.net/bbscon.php?bid=335&id=250203

白话解决方案
http://www.newsmth.net/bbscon.php?bid=335&id=250237

白话参考文献
http://www.newsmth.net/bbscon.php?bid=335&id=250260

ZelluX 2009-03-25 22:14 发表评论

安全方面的经典论文：A Logic of Authentication

ZelluX — Tue, 17 Mar 2009 19:10:00 GMT

最近有点忙，今天总算在某个课题deadline前把论文憋出来交上去了。跑这儿来推荐两篇上个月看到的比较有意思的paper，都比较偏理论，也很老。

今天写介绍下第一篇，剑桥大学的A Logic of Authentication，中了SOSP '89，整理后发在1990年的ACM Transactions on Computer Systems上。
http://www.csie.fju.edu.tw/~yeh/research/papers/os-reading-list/burrows-tocs90-logic.pdf

（另一篇是Safe Kernel Extensions Without Run-Time Checking，改天再写点介绍）

这篇paper的主要工作是通过构造一种多种类的模态逻辑(many-sorted model logic)，来检查网络中验证协议的安全性。

基础的逻辑分三部分：
原语，如验证双方A和B，以及服务器S，下文用P Q R泛指
密钥，如K_ab代表a和b之间的通讯密钥，K_a代表a的公钥，{K_a}^{-1}代表对应的私钥，下文用K泛指
公式（或者陈述），用N_a, N_b等表示，下文用X Y泛指

接下来定义以下约定（constructs）
P 信任 X: 原语P完全信任X
P 看到 X: 有人发送了一条包含X的信息给P，P可以阅读它或者重复它（当然通常是在做了解密操作后）
P 说了 X: 原语P发送过一条包含X的信息，同时也可以确定P是相信X的正确性的
P 控制 X: P可以判定X的正确与否。例如生成密钥的服务器通常被默认为拥有对密钥质量的审核权。
X 是新鲜的: 在此之前X没有被发送过。这个事实可以通过绑定一个时间戳或者其他只会使用一次的标记来证明。
P <-K-> Q: P和Q可以通过共享密钥K进行通讯，且这个K是好的，即不会被P Q不信任的原语知道。
K-> P: P拥有K这么一个公钥，且它对应的解密密钥K^{-1}不会被其他不被P信任的原语知道。
P <=X=> Q: X是一个只被P和Q或者P和Q共同信任的原语知道的陈述，只有P和Q可以通过X来相互证明它们各自的身份，X的一个例子就是密码。
{X}_K: X是一个被K加密了的陈述
_Y: 陈述X被Y所绑定，Y可以用来证明发送X的人的身份

好了，总算把这些约定列完了，然后来看看通过这些约定能推出一些什么东东：
如果 P 相信 (P <-K-> Q), 且 P 看到 {X}_K，那么 P 相信 Q 说了 X。
这个例子很简单，既然P Q有安全的密钥K，那么P看到通过K加密后的X肯定认为就是Q发出的。

又比如，
如果 P 相信 Q 控制 X，P 相信 (Q 相信 X)，那么 P 相信 X
也很容易理解，既然 P 相信 Q 的判断，那么 Q 相信什么 P 自然也就相信了。

再举一个例子
如果 P 相信 Y 是新鲜的，那么 P 相信 (X, Y) 也是新鲜的。
这里(X, Y)表示 X 和 Y 的简单拼接，也很容易理解，既然 Y 之前没出现过，那么 X 和 Y 的组合自然也没出现过。

一个协议要被定义为安全，最起码要满足
A 相信 A <-K->B，B 相信 A <-K->B
即双方要互相信任密钥是安全的

再健壮一点的协议，还要满足
A 相信 (B 相信 (A 相信 A <-K->B))，反之一样
即A B不仅相信密钥，也相信对方相信自己对密钥的信任。

有了这些简单却强大的工具后，接下来这篇paper开始着手分析一些协议，包括Kerberos协议，Andrew Secure RPC 握手协议等，还指出了其中的一些问题和改进措施，例如CCITT X.509 协议中可以通过重复发送一条老的信息来模仿成加密双方中的一员。

具体的分析不贴上来了，一方面对于我这个不熟悉TeX的人来说码公式实在麻烦，另一方面我实在困死了 =_=

建议有兴趣的朋友好好看看这篇经典paper

ZelluX 2009-03-18 03:10 发表评论

Lock-Free 算法的几个链接

ZelluX — Tue, 17 Mar 2009 12:48:00 GMT

Some notes on lock-free and wait-free algorithms

http://www.audiomulch.com/~rossb/code/lockfree/

NOBLE - a library of non-blocking synchronization protocols

http://www.cs.chalmers.se/~noble/

An optimistic approach to lock-free FIFO queues (Distributed Computing 2008)

http://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf

High performance dynamic lock-free hash tables and list-based sets

http://portal.acm.org/citation.cfm?id=564870.564881

Concurrent Programming Without Locks

http://www.cl.cam.ac.uk/research/srg/netos/papers/2007-cpwl.pdf

Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms

http://www.research.ibm.com/people/m/michael/podc-1996.pdf

ZelluX 2009-03-17 20:48 发表评论

10 Papers Every Programmer Should Read

ZelluX — Mon, 02 Mar 2009 10:24:00 GMT

抓抓大牛的博客(http://www.cnblogs.com/JeffreyZhao)上看到的链接，原文地址是
http://blog.objectmentor.com/articles/2009/02/26/10-papers-every-programmer-should-read-at-least-twice

貌似我只读过那篇Reflections on Trusting Trust，水木的Programming版搜索作者为modico的帖子的前四篇就是介绍这篇paper的。

先贴个列表，改天好好读一读

On the criteria to be used in decomposing systems into modules – David Parnas
A Note On Distributed Computing – Jim Waldo, Geoff Wyant, Ann Wollrath, Sam Kendall
The Next 700 Programming Languages – P. J. Landin
Can Programming Be Liberated from the von Neumann Style? – John Backus
Reflections on Trusting Trust – Ken Thompson
Lisp: Good News, Bad News, How to Win Big – Richard Gabriel
An experimental evaluation of the assumption of independence in multiversion programming – John Knight and Nancy Leveson
Arguments and Results – James Noble
A Laboratory For Teaching Object-Oriented Thinking – Kent Beck, Ward Cunningham
Programming as an Experience: the inspiration for Self – David Ungar, Randall B. Smith

作者博客后面还新增了对它们的简要评论

ZelluX 2009-03-02 18:24 发表评论

PieTTY中按Ctrl+S导致挂起的问题解决

ZelluX — Tue, 17 Feb 2009 04:12:00 GMT

2009-01-08

以前碰到这个问题都得先重启PieTTY然后用screen -x恢复到原来的工作界面，今天不知怎么的emacs里C-x C-s按了就挂起，只能google。

传说中，早期的终端会遇到显示字符的速度慢于接收字符的速度，为了解决这个问题，C-s用于先挂起当前终端，在数据传输之后用C-q恢复显示。所以最简单的解决方法就是在挂起后按C-q。

不过我的WinXP中C-q已经和快速启动工具（寝室里是Turbo Launcher，实验室的是Launchy）绑定了，也懒得为了这么个问题改操作习惯，于是再次google，终于找到一个一劳永逸的方法，以bash为例，在~/.bashrc中加入一行

stty -ixoff -ixon

即可。另外这样设置后似乎恢复了C-s在bash中正向增量查找的功能。恩。

ZelluX 2009-02-17 12:12 发表评论

Finding and Reproducing Heisenbugs in Concurrent Programs

ZelluX — Tue, 17 Feb 2009 03:30:00 GMT

今年的ASPLOS '09上zhou yuanyuan也有一篇关于如何concurrent program中发现隐藏的atomicity violation bugs的paper，里面提到了这篇paper

2008-11-30

OSDI '08上MSR发的paper，针对并发编程中难以发现的bug问题。

paper的内容主要分两大块。

一是如何在发现bug的时候记录下线程的运行先后(thread interleaving)，途径是在线程API和用户程序多写一层wrapper functions，这里还有一些其他的问题，比如只记录下了thread interleaving的话出现data race怎么解决等。

另外一块内容是如何遍历出给定程序运行后所能产生的结果的集合，加入这个能实现的话那就能把所有隐藏的bug都找出来了。但是这个搜索空间很大，是指数级的，的一个结论就是：给定一个程序有n个的线程，所有线程共完成k条指令，那么c次占先调度后线程的排列情况数的复杂度是的，所以在实现遍历代码的时候必须有效的降低k和c的值。

ZelluX 2009-02-17 11:30 发表评论

Ubuntu 8.10 浏览网页不稳定的解决方法

ZelluX — Wed, 28 Jan 2009 16:30:00 GMT

问题现象：上校内、一些国内论坛时经常出现连接重置(Connect reset)错误，而上google baidu等网站却没什么问题。ping那些有问题的网站的结果很正常。

google了一堆关键词后终于发现问题出在MTU上，至少在偶的本本上运行
sudo ifconfig eth1 mtu 1412
就没问题了（eth1是无线网卡）

p.s 多谢万熊 XD

ZelluX 2009-01-29 00:30 发表评论

[zz]苏南经济模式兴衰亲历记

ZelluX — Wed, 21 Jan 2009 06:47:00 GMT

摘要: 发信人: linelf (水水), 信区: Real_Estate
标题: 苏南经济模式兴衰亲历记zz
发信站: 日月光华 (2009年01月15日20:39:22 星期四)

阅读全文

ZelluX 2009-01-21 14:47 发表评论

为什么Python中的self必须保留？

ZelluX — Sat, 15 Nov 2008 11:58:00 GMT

Bruce Eckel的一篇日志建议把self从方法的参数列表中移除，并把它作为一个关键字使用。
http://www.artima.com/weblogs/viewpost.jsp?thread=239003

Guido的这篇日志说明了self作为参数是必不可少的。
http://neopythonic.blogspot.com/2008/10/why-explicit-self-has-to-stay.html

第一个原因是保证foo.meth(arg)和C.meth(foo, arg)这两种方法调用的等价（foo是C的一个实例)，关于后者可以参见Python Reference Manual 3.4.2.3。这个原因理论上的意义比较大。

第二个原因在于通过self参数我们可以动态修改一个类的行为：

# Define an empty class:
class C:
pass

# Define a global function:
def meth(myself, arg):
myself.val = arg
return myself.val

# Poke the method into the class:
C.meth = meth

这样类C就新增了一个meth方法，并且所有C的实例都可以通过c.meth(newval)调用这个方法。

前面两个原因或许都可以通过一些workaround使得不使用self参数时实现同样的效果，但是在存在decorator的代码中Bruce的方法存在致命的缺陷。(关于decorator的介绍可以参见http://www.python.org/dev/peps/pep-0318/)

根据修饰对象，decorator分两种，类方法和静态方法。两者在语法上没有什么区别，但前者需要self参数，后者不需要。而Python在实现上也没有对这两种方法加以区分。Bruce日志评论中有一些试图解决decorator问题的方法，但这些方法都需要修改大量底层的实现。

最后提到了另一种语法糖实现，新增一个名为classmethod的decorator，为每个方法加上一个self参数，当然这种实现也没必要把self作为关键字使用了。不过我觉得这么做还不如每次写类方法时手工加个self =_=

ZelluX 2008-11-15 19:58 发表评论