posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

2008年5月20日

http://blog.yxwang.me/

posted @ 2009-12-30 09:48 ZelluX 阅读(458) | 评论 (0)编辑 收藏

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

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

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

posted @ 2009-04-02 01:38 ZelluX 阅读(871) | 评论 (3)编辑 收藏

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

posted @ 2009-03-25 22:14 ZelluX 阅读(827) | 评论 (2)编辑 收藏

最近有点忙,今天总算在某个课题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加密了的陈述
<X>_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

posted @ 2009-03-18 03:10 ZelluX 阅读(2474) | 评论 (0)编辑 收藏

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

posted @ 2009-03-17 20:48 ZelluX 阅读(2686) | 评论 (0)编辑 收藏

抓抓大牛的博客(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的。

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

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

posted @ 2009-03-02 18:24 ZelluX 阅读(760) | 评论 (0)编辑 收藏

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中正向增量查找的功能。恩。


posted @ 2009-02-17 12:12 ZelluX 阅读(2119) | 评论 (0)编辑 收藏

今年的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}的,所以在实现遍历代码的时候必须有效的降低k和c的值。

posted @ 2009-02-17 11:30 ZelluX 阅读(609) | 评论 (0)编辑 收藏

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

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

p.s 多谢万熊  XD

posted @ 2009-01-29 00:30 ZelluX 阅读(858) | 评论 (2)编辑 收藏

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

  阅读全文

posted @ 2009-01-21 14:47 ZelluX 阅读(868) | 评论 (0)编辑 收藏

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 =_=


posted @ 2008-11-15 19:58 ZelluX 阅读(2515) | 评论 (2)编辑 收藏

2008年评出了1998年最具影响力的PLDI论文,获奖论文的作者将分摊1000美元的奖金(还没一等奖学金多 -_-b)

2008 (for 1998): The Implementation of the Cilk-5 Multithreaded Language, Matteo Frigo, Charles E. Leiserson, and Keith H. Randall

Citation

“The 1998 PLDI paper “Implementation of the Cilk-5 Multithreaded Language” by Matteo Frigo, Charles E. Leiserson, and Keith H. Randall introduced an efficient form of thread-local deques to control scheduling of multithreaded programs. This innovation not only opened the way to faster and simpler runtimes for fine-grained parallelism, but also provided a basis for simpler parallel recursive programming techniques that elegantly extend those of sequential programming. The stack-like side of a deque acts just like a standard procedure stack, while the queue side enables breadth-first work-stealing by other threads. The work-stealing techniques introduced in this paper are beginning to influence common practice, such as the Intel Threading Building Blocks project, an upcoming standardized fork-join framework for Java, and a variety of projects at Microsoft.”

另外前几年的获奖paper有:
2007 (for 1997): Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling, Glenn Ammons, Thomas Ball, and James R. Larus

2006 (for 1996): TIL: A Type-Directed Optimizing Compiler for ML, David Tarditi, Greg Morrisett, Perry Cheng, Christopher Stone, Robert Harper, and Peter Lee

2005 (for 1995): Selective Specialization for Object-Oriented Languages, Jeffrey Dean, Craig Chambers, and David Grove

2004 (for 1994): ATOM: a system for building customized program analysis tools, Amitabh Srivastava and Alan Eustace

2003 (for 1993): Space Efficient Conservative Garbage Collection, Hans Boehm

2002 (for 1992): Lazy Code Motion, Jens Knoop, Oliver Rüthing, Bernhard Steffen.

2001 (for 1991): A data locality optimizing algorithm, Michael E. Wolf and Monica S. Lam.

2000 (for 1990): Profile guided code positioning, Karl Pettis and Robert C. Hansen.

posted @ 2008-10-17 20:08 ZelluX 阅读(521) | 评论 (2)编辑 收藏

两者配合,更完美的知识管理方案

http://hi.baidu.com/qq303520912/blog/item/de5cba082db83e36e924889e.html

Endnote是目前国内科研人员使用最多的文献管理软件,功能最完备,各数据库或大学图书馆等和它的兼容也是最好。它的Filter和style 也最为丰富,而且可以自己创建修改。看看周围的人,大部分都是Endnote的用户。   Zotero作为一个新的文件管理系统,与Endnote相比还是稚嫩了些,特别对于国内数据库的支持不佳,更是限制了它的应用。

不过,Zotero作为Firefox浏览器的插件,还是有一些特别之处。

第一,便携。Firefox是有Portable版本的,当然Zotero也就是Portable了,也就是说可以把火狐和Zotero放到U盘里,在任何一台电脑上都可以 使用。而Endnote就没有这么方便了。

第二,便利。使用电脑时,我们使用浏览器的时间要大大多于Endnote的时间,遇到有用的文献、网页或者需要做笔记,直接使用Zotero更加省时省力。而且它自动收集网页中文献信息的功能也大大方便了操作。

第三, 分享。EndnoteX以后可以把一个library发送成一个档案文件(.enlx),使得文献交换更为方便。不过有时我们只需要几条文献时,这样操作 就大动干戈了。当然Endnote也支持所选部分文献的导出,但这样有不能够导出附件,包括图片、PDF等(此处为个人经验,是否Endnote也能导出 附件来还望您不吝赐教)。而Zotero就可以实现某条文献所有内容(题录、笔记、附件)的全部导出,而且可以为另一Zotero用户所完整接受。

第四,跟踪文献的收集。很多数据都支持检索式或者引文的提醒,会随时把新的内容发送到邮箱或者以RSS的形式发布。一般来说,查看这些都需要浏览器。有了Zotero,我们可以在查看的同时收集下有用的文献信息。

Zotero更适合于在日常工作、学习甚至娱乐时使用,而Endnote更适合在有明确目的时使用。有人说Zotero更像“知识管理软件”, 而 Endnote就是为文献服务的。两者可以实现互补,在日常工作中使用Zotero收集零散的资料,积累一定量之后将文献信息导入到Endnote中,使 用Endnote管理、引用文献信息。至于PDF、图片等附件的管理,我还是建议使用Zotero,方便且可以完整导出。

下面谈一下Zotero和Endnote中文献的互相导入。

Zotero导入Endnote:
1 选定文献,右键点选”export selected items”;如果是导入整个Library或者cellection可在相应图标上右键点选;
2 在弹出的对话框中选择导出的格式为”Refer/BibIX”, 选择文件目录,保存文件,格式为.txt;
3 在Endnote中打开一个library,执行“files-import”;
4 在对话框中选择刚才的.txt文件, Impott Option选Refer/BibIX,Text Translation选Unicode(UTF-8)。点确定后即可导入。

Endnote导入Zotero:
1 选择文献后,执行“files-export”;
2 选择Output Style为Endnote Export,命名后导入,得到.txt文件。
3 在Zotero中执行“actions-import” ,选择得到的文件,点确定即可导入。
上述导入方式仅能实现文献题录的导入。

posted @ 2008-10-17 20:07 ZelluX 阅读(8723) | 评论 (0)编辑 收藏

BBS上的一个帖子,问题是
def a():
    
def b():
        x 
+= 1
 
    x 
= 1
    
print "a: ", x
    b()
    
print "b: ", x
 
def c():
    
def d():
        x[0] 
= [4]
    x 
= [3]
    
print "c: ", x[0]
    d()
    
print "d: ", x[0]

运行a()会报UnboundLocalError: local variable ‘x’ referenced before assignment
但是运行c()会正确地显示3和4。

原因在于原因在于CPython实现closure的方式和常见的functional language不同,采用了flat closures实现。

“If a name is bound anywhere within a code block, all uses of the name within the block are treated as references to the current block.”

在第一个例子中,b函数x += 1对x进行赋值,rebind了这个对象,于是Python查找x的时候只会在local environment中搜索,于是就有了UnboundLocalError。

换句话说,如果没有修改这个值,比如b中仅仅简单的输出了x,程序是可以正常运行的,因为此时搜索的范围是nearest enclosing function region。

而d方法并没有rebind x变量,只是修改了x指向的对象的值而已。如果把赋值语句改成x = [4],那么结果就和原来不一样了,因为此时发生了x的rebind。

所以Python中的closure可以理解为是只读的。

另外第二个例子也是这篇文章中提到的一种workaround:把要通过inner function修改的变量包装到数组里,然后在inner function中访问这个数组。

至于为什么Python中enclosed function不能修改enclosing function的binding,文中提到了主要原因还是在于Guido反对这么做。因为这样会导致本应该作为类的实例保存的对象被声明了本地变量。

参考网站:http://www.python.org/dev/peps/pep-0227/


posted @ 2008-10-17 20:06 ZelluX 阅读(494) | 评论 (0)编辑 收藏

acm queue 9月的杂志的主题是The Concurrency Problem,力推了Erlang这个语言,其中有篇文章简单的介绍了下这个message-oriented语言。

查了下这个名字的读法,正确的读法应该是air-lang,这里元音a的发音和bang中的a一样。

文章中的第一个程序就有点令人费解,主要原因在于Erlang的语法和一般的imperative language差别很大,和functional language比较类似,但是本质上也有很大的不同。

以Java的一个计数程序为例
// A shared counter.
public class Sequence {
    
private int nextVal = 0;
 
    
// Retrieve counter and increment.
    public synchronized int getNext() {
        
return nextVal++;
    }
 
    
// Re-initialize counter to zero.
    public synchronized void reset() {
        nextVal 
= 0;
    }
}

这个程序的功能不用多说了,一个同步的计数程序。它的Erlang翻译版的代码为

-module(sequence1).
-export([make_sequence/0, get_next/1, reset/1]).
 
% Create a new shared counter.
make_sequence() ->
spawn(fun() -> sequence_loop(0)end).
 
sequence_loop(N) ->
receive
{From, get_next} ->
From!{self(), N},
sequence_loop(N + 1)<SEMI>
reset ->
sequence_loop(0)
end.
 
% Retrieve counter and increment.
get_next(Sequence) ->
Sequence!{self(), get_next},
receive
{Sequence, N} -> N
end.
 
% Re-initialize counter to zero.
reset(Sequence) ->
Sequence! reset.

初看这个程序自然是一头雾水,不过程序的函数式风格味还是很浓的。

前面提到,Erlang是基于message的,或者说message sending机制是包含在语言系统内部的,语法就是 pid ! message

接下来再来分析这个简单的程序。开头两行是模块和函数声明,略去。make_sequence开始这个进程,spawn/1内置函数创建一个新的进程,并返回pid到调用者。

初始时运行的函数是sequence_loop(0),这个函数接收两种信息,用receive表达式声明:如果收到形式是{From, get_next}的信息,就返回当前的N并调用sequence_loop(N+1),这样下一次收到同样的信息时就能返回N+1了;reset则等价 于Java版本中的n=0语句。

get_next/1则是发送给pid为Sequence的进程 {self(), get_next} 这样一个信息,上面解释的sequence_loop/1函数收到这个信息后会返回一个 {self(), N} 的tuple给get_next/1,收到这个信息后get_next/1就能返回N这个值了。

最后reset/1函数则是发送给Sequence一个reset信息。

这个简单的程序里能大致窥见一些Erlang的特点,尤其是它基于信息发送的本质。

posted @ 2008-10-17 20:05 ZelluX 阅读(1886) | 评论 (0)编辑 收藏

09月 18, 2008
第一个testkernel在Xen中的载入

The Definitive Guide to Xen中第二章的例子,make成功后运行xen create domain_config,报错
Error: (2, ‘Invalid kernel’, ‘xc_dom_compat_check: guest type xen-3.0-x86_32 not supported by xen kernel, sorry\n’)

google之后发现是虚拟机类型设置的问题,运行xm info可以看到
xen_caps : xen-3.0-x86_32p
末尾的p表示Xen内核开启了PAE模式,所以载入的kernel也必须开启PAE,在bootstrap.x86_32.S中加入PAE=yes选项即可。

09月 25, 2008
DomainU中调用do_console_io

The Definitive Guide to Xen第二章的Exercise,通过调用hypercall page中的console_io项输出Hello World。

void start_kernel(start_info_t * start_info)
{
    HYPERVISOR_console_io(CONSOLEIO_write,
12,"Hello World\n");
    
while(1);
}


但是默认选项编译和启动的Xen是不会保留DomainU中输出的信息。参考drivers/char/console.c,可以看到主要有两个选项控制了DomainU的do_console_io输出:

#ifndef VERBOSE
    
/* Only domain 0 may access the emergency console. */
    
if ( current-&gt;domain-&gt;domain_id != 0 )
        
return -EPERM;
#endif

if ( opt_console_to_ring )
{
    
for ( kptr = kbuf; *kptr != '\0'; kptr++ )
        putchar_console_ring(
*kptr);
    send_guest_global_virq(dom0, VIRQ_CON_RING);
}


VERBOSE选项可以在编译Xen的时候开启debug选项,而opt_console_to_ring则是一个启动选项,在grub的启动选项中增加loglvl=all guest_loglvl=all console_to_ring即可。

重启Xen后就能通过xm dmesg看到Hello World了。

09月 25, 2008
Xen: Remove support for non-PAE 32-bit

看来我还是用Xen 3.1吧 = =

Subject: [Xen-devel] [PATCH] xen: remove support for non-PAE 32-bitLink to this message
From: Jeremy Fitzhardinge (jer…@goop.org)
Date: 05/09/2008 04:05:34 AM
List: com.xensource.lists.xen-devel

Non-PAE operation has been deprecated in Xen for a while, and is rarely tested or used. xen-unstable has now officially dropped non-PAE support. Since Xen/pvops’ non-PAE support has also been broken for a while, we may as well completely drop it altogether.

10月 07, 2008
IA-32 Memory Virtualization
http://www.intel.com/technology/itj/2006/v10i3/3-xen/4-extending-with-intel-vt.htm
o_figure_3.gif
上图为full virtulization的情况,即不修改Guest OS的行为时的解决方案。Xen为每个Guest OS维护了一张shadow page table,其中映射的地址为machine address。一种比较高效的方案是设置Guest OS的page table为只读,当Guest OS试图修改这个虚拟页表时,发生page fault被Xen截获,Xen修改shadow page table中相应的数据(把pseudo-physical address转化成machine address)。另外一个优化是guest page table被修改时不修改shadow page table,只是把它放到一个待更新列表中,等Guest OS执行了刷新tlb的指令后再一次性更新。

The Definitive Guide to Xen上还提到了另一种基于full paravirtulization和shadow page table之间的方案。Xen把Guest OS的page table置为只读,当Guest OS试图修改page table时,Xen捕获到page fault,把page directory中对应的入口置为无效,再把page table改成可写让Guest OS修改。由于page directory中对应的入口被设成无效了,下次访问该地址时还是会发生page fault,这时候Xen再修改page directory和page table的对应项就行了。

这种方法意味着Guest OS中内核管理模块直接和machine address打交道,而其他部分则仍然使用pseudo-physical address。另外这种情况下page directory不能被Guest OS修改。

另外Xen还用到了段机制,用来为Xen保留地址空间开始的64M内存。

posted @ 2008-10-17 20:01 ZelluX 阅读(1417) | 评论 (6)编辑 收藏

好不容易找到的一个php,直接贴这儿了,方便其他网友。
wordpress的wp-syntax插件用的也是geshi,所以同样也适用于wp-syntax

<?php
/*************************************************************************************
 * erlang.php
 * --------
 * Author: Uwe Dauernheim (uwe@dauernheim.net)
 * Copyright: (c) 2008 Uwe Dauernheim (http://www.kreisquadratur.de/)
 * Release Version: 1\.0\.0
 * Date Started: 2008-09-27
 *
 * Erlang language file for GeSHi.
 *
 * CHANGES
 * -------
 * 2008-09-27 (1.0.0)
 *   [ ] First Release
 *
 * 2008-09-28 (1.0.0.1)
 *   [!] Bug fixed with keyword module.
 *   [+] Added more function names   
 *
 * TODO (updated 2008-09-27)
 * -------------------------
 *   [!] Stop ';' from being transformed to '<SEMI>'
 * 
 ***********************************************************************************
*/

$language_data = array (
    
'LANG_NAME' => 'Erlang',
    
'COMMENT_SINGLE' => array(1 => '%'),
    
'CASE_KEYWORDS' => GESHI_CAPS_NO_CHANGE,
    
'QUOTEMARKS' => array('"'),
    
'HARDQUOTE' => array("'", "'"), 
    
'HARDESCAPE' => array('\\\'',), 
    
'ESCAPE_CHAR' => '\\',
    
'KEYWORDS' => array(
        1 => array(
            
'module''export''import''author''behaviour'
            ),
        2 => array(
            
'case''of''if''end''receive''after'
            ),
        3 => array(
            // erlang
            
'set_cookie''get_cookie'
            // io
            
'format''fwrite''fread'
            // gen_tcp
            
'listen''accept''close'
            // gen_server
            
'call''start_link'
            )
        ),
    
'SYMBOLS' => array(
        
':''=''!''|'
        ),
    
'CASE_SENSITIVE' => array(
        GESHI_COMMENTS => false,
        1 => true,
        2 => true,
        3 => true
        ),
    
'STYLES' => array(
        
'KEYWORDS' => array(
            1 => 
'color: #b1b100;',
            2 => 'color: #b1b100;',
            
3 => 'color: #000066;'
            )
,
        
'COMMENTS' => array(
            
1 => 'color: #666666; font-style: italic;',
            
2 => 'color: #009966; font-style: italic;',
            
3 => 'color: #0000ff;',
            
4 => 'color: #cc0000; font-style: italic;',
            
5 => 'color: #0000ff;',
            
'MULTI' => 'color: #666666; font-style: italic;'
            )
,
        
'ESCAPE_CHAR' => array(
            
0 => 'color: #000099; font-weight: bold;',
            
'HARD' => 'color: #000099; font-weight: bold;'
            )
,
        
'BRACKETS' => array(
            
0 => 'color: #009900;'
            )
,
        
'STRINGS' => array(
            
0 => 'color: #ff0000;',
            
'HARD' => 'color: #ff0000;'
            )
,
        
'NUMBERS' => array(
            
0 => 'color: #cc66cc;'
            )
,
        
'METHODS' => array(
            
1 => 'color: #006600;',
            
2 => 'color: #006600;'
            )
,
        
'SYMBOLS' => array(
            
0 => 'color: #339933;'
            )
,
        
'REGEXPS' => array(
            
0 => 'color: #0000ff;',
            
4 => 'color: #009999;',
            )
,
        
'SCRIPT' => array(
            )
        )
,
    
'URLS' => array(
        
1 => '',
        
2 => '',
        
3 => 'http://www.erlang.org/doc/man/{FNAMEL}.html'
        )
,
    
'OOLANG' => true,
    
'OBJECT_SPLITTERS' => array(
        
1 => '-&gt;',
        
2 => ':'
        )
,
    
'REGEXPS' => array(
        
// Variable
        0 => '[A-Z][_a-zA-Z0-9]*',
        
// File Descriptor
        4 => '&lt;[a-zA-Z_][a-zA-Z0-9_]*&gt;'
        )
,
    
'STRICT_MODE_APPLIES' => GESHI_NEVER,
    
'TAB_WIDTH' => 4
);

?>

posted @ 2008-10-16 20:36 ZelluX 阅读(426) | 评论 (0)编辑 收藏

http://www.codeproject.com/KB/work/FontSurvey.aspx

主要的衡量标准是可读性、是否等宽、特殊字符的辨认度(比如0和O)

posted @ 2008-10-13 18:26 ZelluX 阅读(1264) | 评论 (1)编辑 收藏

依然是内网日志的汇总

1. sysenter的介绍
http://www.codeguru.com/cpp/w-p/system/devicedriverdevelopment/article.php/c8223

System Call Optimization with the SYSENTER Instruction
by John Gulbrandsen
Windows下的

2. The SLUB allocator
slab的改进版本

http://lwn.net/Articles/229984/

http://lwn.net/Articles/229096/

Christoph’s response is the SLUB allocator, a drop-in replacement for the slab code. SLUB promises better performance and scalability by dropping most of the queues and related overhead and simplifying the slab structure in general, while retaining the current slab allocator interface.

Wider use may be in the cards: the SLUB allocator is in the -mm tree now and could hit the mainline as soon as 2.6.22. The simplified code is attractive, as is the claimed 5-10% performance increase. If merged, SLUB is likely to coexist with the current slab allocator (and the SLOB allocator intended for small systems) for some time. In the longer term, the current slab code may be approaching the end of its life.

3. Compilers and More: Parallel Programming Made Easy?
http://www.hpcwire.com/features/Compilers_and_More_Parallel_Programming_Made_Easy.html

by Michael Wolfe, Compiler Engineer, The Portland Group, Inc.

4. OpenCL slides, SIGGRAPH '08
发信人: jjgod (while(!asleep()) sheep++;), 信区: CSArch
标  题: SIGGRAPH 08 上的 OpenCL slides
发信站: 水木社区 (Mon Sep 15 01:32:03 2008), 站内

※ 来源:·水木社区 newsmth.net·[FROM: 125.33.176.*]

附件: munshi-opencl.pdf (1338 KB) 链接:
http://att.newsmth.net/att.php?p.272.35430.226.pdf
全文链接:http://www.newsmth.net/bbscon.php?bid=272&id=35430

5. linux-gate.so
http://www.trilithium.com/johan/2005/08/linux-gate/
linux下使用sysenter的机制

posted @ 2008-10-10 15:29 ZelluX 阅读(464) | 评论 (0)编辑 收藏

转自偶的内网博客

Time : 2008-08-20 21:44
汇编文件中导出函数符号

Linux 2.4.18的linux/linkage.h文件定义了若干相关的宏

#define SYMBOL_NAME(X) X
#ifdef __STDC__
#define SYMBOL_NAME_LABEL(X) X##:
#else
#define SYMBOL_NAME_LABEL(X) X/**/:
#endif
 
#define __ALIGN .align 16,0x90
#define __ALIGN_STR ".align 16,0x90"
 
#define ALIGN __ALIGN
#define ALIGN_STR __ALIGN_STR
 
#define ENTRY(name) \
  .globl SYMBOL_NAME(name); \
  ALIGN; \
  SYMBOL_NAME_LABEL(name)

用ENTRY(name)就能定义函数了。后来发现Flux OSKit中本来就提供了类似功能的宏,定义在inc/asm.h中。
使用的时候需要再写一个c语言的wrapper function(至少2.4.18里面是这么做的)
asmlinkage void ret_from_fork(void) __asm__("ret_from_fork");

Time : 2008-08-22 15:56
OS Lab 4 debugging notes [1]
系统调用 fork()

用Simics跟踪一条条汇编分析页表映射、寄存器值还真是体力活啊。。

1. 实现Copy On Write时,如果某一个用户态页面有多个进程共享,其中一个进程修改该页面时需要创建一个新的页面。一开始偶忘了把原来页面的内容复制到新的页面了 =_= 另外由于新的页面要代替老的页面,或者说它们的物理地址不同,但虚拟地址相同,我的方法是在内核态开辟一个大小为一个页面的空间作为中转。

2. do_fork函数中,子进程复制父进程的页表的同时会把父进程页表项置为不可写,注意最后要flush tlb。因为一开始没有flush tlb,导致最后用户态fork返回以后读取的信息来自于tlb,直接改写了共享页面中fork的返回地址,导致切换到子进程时fork的返回地址丢失。这个bug让我郁闷了两三个小时。。

3. 使用两次fork时,第二次fork返回的pid会被改掉。查了下发现为用户空间分配物理页面的代码里居然在分配好以后没有把对应的struct置为已使用,结果导致第二个子进程COW创建新页面时得到了原来的父进程页面,改写了父进程页面内容。

Time : 2008-08-23 19:41
OS Lab4 debugging notes [2]
 
系统调用 exec()

1. 清空页表的用户空间映射的函数一开始写得yts,bug到处都是,比如free的时候没使用指向内存块首地址的指针,记录内存地址的变量没有累加。

2. exec传递给内核态的两个参数必须先在内核态保存一个副本,否则清空用户态页表后就无法得到这两个参数信息了。

3. 分配给用户态的页面必须先清零,一方面考虑到安全性,另一方面不清零会隐藏一些潜在的bug。一开始我没有在内核执行exec的时候完整的复制所有的参数,而是直接指向了原进程的内存空间,由于清空页表后再次申请新页表时得到了原来的页面,结果正好原来那个保存参数的页面和新进程的该页面重合了 =_= 于是浪费了不少时间在这个bug上

Time : 2008-08-31 1:18
OS Lab5 debugging notes

还算顺利,不过这个lab蛮无聊的,等有空了把syscall改成类似linux的做法,单一中断号+寄存器选择syscall。

1. 最花时间的一个bug是ls返回值没有改成应用程序数,结果一开始一直以为是brk系统调用没写好,最后才发现问题出在这么小的地方。

2. brk的逻辑还不是很清楚,尽管通过了简单的测试,但是debug输出的信息显示brk增长的很快,经常是一个页一个页涨的,看来还得查下brk的具体行为。

3. 写了个比MAGIC_BREAK好用一点的宏,因为用户态的程序都是按二进制读入的,Simics无法得到函数信息(函数名、当前行数等),利用C99的宏写了个新的INFO_BREAK

#define INFO_BREAK \
    
do {  \
        lprintf_kern(
"break in %s:%d", __FUNCTION__, __LINE__); \
        MAGIC_BREAK; \
    }
 while (0) \

posted @ 2008-10-10 15:21 ZelluX 阅读(578) | 评论 (0)编辑 收藏

发信人: Zellux (null), 信区: Software_06
标 题: OSLab之中断处理
发信站: 日月光华 (2008年08月30日20:15:58 星期六), 站内信件

1. 准备工作
在开始分析Support Code之前,先配置下我们的Source Insight,使它能够支持.s文件的搜索。

在Options->Document Options->Document Types中选择x86 Asm Source File,在File fileter中增加一个*.s,变成*.asm;*.inc;*.s 然后在Project->Add and Remove
Project Files中重新将整个oslab的目录加入,这样以后进行文本搜索时.s文件也不会漏掉了。

2. Source Insight使用
接下来简单分析下内核启动的过程,在浏览代码的过程中可以迅速的掌握Source Insight的使用技巧。

lib/multiboot /multiboot.s完成了初始化工作,可以看到其中一句call
EXT(multiboot_main)调用了C函数multiboot_main,使用ctrl+/搜索包含multiboot_main的所有文件,最终base_multiboot_main.c中找到了它的定义。依次进行cpu、内存的初
始化,然后开启中断,跳转到kernel_main函数,也是Lab1中所要改写的函数之一。另外
在这里可以通过ctrl+单击或者ctrl+=跳转到相应的函数定义处,很方便。

3. irq处理初始化工作
来看下Lab 1的重点之一,irq的处理。跟踪multiboot_main->base_cpu_setup->base_cp
u_init->base_irq_init,可以看到这行代码
gate_init(base_idt, base_irq_inittab, KERNEL_CS);
继续使用ctrl+/找到base_irq_inittab的藏身之处:base_irq_inittab.s

4. base_irq_inittab.s
这个汇编文件做了不少重复性工作,方便我们在c语言级别实现各种handler。
GATE_INITTAB_BEGIN(base_irq_inittab) /* irq处理函数表的起始,还记得jump
table 吗? */
MASTER(0, 0) /* irq0 对应的函数 */


来看看这个MASTER(0, 0)宏展开后是什么样子:
#define MASTER(irq, num) \
GATE_ENTRY(BASE_IRQ_MASTER_BASE + (num), 0f, ACC_PL_K|ACC_INTR_GATE) ;\
P2ALIGN(TEXT_ALIGN) ;\
0: ;\
pushl $(irq) /* error code = irq vector */ ;\
pushl $BASE_IRQ_MASTER_BASE + (num) /* trap number */ ;\
pusha /* save general registers */ ;\
movl $(irq),%ecx /* irq vector number */ ;\
movb $1 << num,%dl /* pic mask for this irq */ ;\
jmp master_ints

依次push irq号,trap号(0x20+irq号),通用寄存器(eax ecx等)入栈,把irq号保
存到ecx寄存器,然后跳转到master_ints,master_ints是所有master interrupts公用
的代码。

跳过master_ints的前几行,从第七行开始
/* Acknowledge the interrupt */
movb $0x20,%al
outb %al,$0x20

/* Save the rest of the standard trap frame (oskit/x86/base_trap.h). */
pushl %ds
pushl %es
pushl %fs
pushl %gs

/* Load the kernel's segment registers. */
movw %ss,%dx
movw %dx,%ds
movw %dx,%es

/* Increment the hardware interrupt nesting counter */
incb EXT(base_irq_nest)

/* Load the handler vector */
movl EXT(base_irq_handlers)(,%ecx,4),%esi

注释写得很详细,首先发送0x20到0x20端口,也就是Lab1文档上所说的发送INT_CTL_DON
E到INT_CTL_REG,看来这一步support code已经替我们完成了。接下来保存四个段寄存
器ds es fs gs,并读入kernel态的段寄存器信息。

最后一句很关键,把base_irq_handlers + %ecx * 4这个值保存到了esi寄存器中,%ecx
中保存了irq号,而*4则是一个函数指针的大小,那么base_irq_handlers是什么呢?继
续用ctrl+/搜索,可以在base_irq.c中找到这个数组的定义
unsigned int (*base_irq_handlers[BASE_IRQ_COUNT])(struct trap_state *ts)
且初始时这个数组的每一项都是base_irq_default_handler

看来这句汇编代码的功能是把处理irq对应的函数地址保存到了esi寄存器中。
为了证实这一点,继续看base_irq_inittab.s的代码:
#else
/* Call the interrupt handler with the trap frame as a parameter */
pushl %esp
call *%esi
popl %edx
#endif
果然,在保存了esp值后,紧接着就调用了esi指向的那个函数。而从那个函数返回后,
之前在栈上保存的相关信息都被恢复了:

/* blah blah blah */
/* Return from the interrupt */
popl %gs
popl %fs
popl %es
popl %ds
popa
addl $4*2,%esp /* Pop trap number and error code */
iret
这样就恢复到了进入这个irq处理单元前的状态,文档中所要求的保存通用寄存器这一步
其实在这里也已经完成了,不需要我们自己写代码。

好了,这样一分析后,我们要做的事情就很简单,就是把base_irq_handlers数组中的对
应项改成相应的handler函数就行了。
注意index是相应的idt_entry号减去BASE_IRQ_SLAVE_BASE,或者直接使用IRQ号。

另外这个数组的初始值都是base_irq_default_handler,用ctrl+左键跳到这个函数的定
义,可以看到这个函数只有一句简单的输出语句:
printf("Unexpected interrupt %d\n", ts->err);
而这就是没有注册handler前我们所看到的那句Unexpected interrupt 0的来源了。

5. struct trap_state *ts
所有的handler函数的参数都是一个struct trap_state *ts,这个参数是哪来的呢?
注意call *%esi的前一行
/* Call the interrupt handler with the trap frame as a parameter */
pushl %esp
这里把当前的esp当作指向ts的指针传给了handler,列一下从esp指向的地址开始的内容
,也就是在此之前push入栈的内容:

pushl $(irq) /* error code = irq vector */ ;\
pushl $BASE_IRQ_MASTER_BASE + (num) /* trap number */ ;\
pusha /* save general registers */ ;\
pushl %ds
pushl %es
pushl %fs
pushl %gs

再看一下trap_state的定义,你会发现正好和push的顺序相反:
/* Saved segment registers */
unsigned int gs;
unsigned int fs;
unsigned int es;
unsigned int ds;

/* PUSHA register state frame */
unsigned int edi;
unsigned int esi;
unsigned int ebp;
unsigned int cr2; /* we save cr2 over esp for page faults */
unsigned int ebx;
unsigned int edx;
unsigned int ecx;
unsigned int eax;

/* Processor trap number, 0-31. */
unsigned int trapno;

/* Error code pushed by the processor, 0 if none. */
unsigned int err;

而这个定义后面的
/* Processor state frame */
unsigned int eip;
unsigned int cs;
unsigned int eflags;
unsigned int esp;
unsigned int ss;
则是发生interrupt时硬件自动push的五个数据(参见Understand the Linux Kernel)

也就是说,ts指针指向的是调用当前handler前的寄存器状态,也是当前handler结束后
用来恢复的寄存器状态,了解这一点对以后的几个lab帮助很大。

p.s. 另外提一句和这个lab无关的话,非vm86模式下栈上是不会有v86_es等四个寄存器
信息的,所以以后根据task_struct指针计算*ts的地址时使用的偏移量不应该是sizeof(
struct trap_state)

6. The End
这样差不多就把support code中处理interrupt的方法过了一遍(另外还有base_trap_in
ittab.s,不过和irq的处理很相似)

了解这些后Lab1就比较简单了,不需要任何内嵌汇编代码即可完成。

posted @ 2008-09-02 11:55 ZelluX 阅读(627) | 评论 (5)编辑 收藏

     摘要: 美国为什么需要这么多大学生,而中国培育出这么多优秀大学生为什么失业?难道是我们学生程度不够?难道是我们同学不够用功?难道是我们同学专业不对口?那我告诉所有读者,为什么大学生就业难……   阅读全文

posted @ 2008-07-28 11:31 ZelluX 阅读(661) | 评论 (5)编辑 收藏

用ctags -R或者ctags * -R的时候只能生成当前目录下的tag,检查了半天发现原来这个版本的ctags的参数顺序只能老老实实的来:ctags -R *

太囧了,总归要bs下的,虽说也有那么一点点可能是bash解析参数时的问题,不过我猜问题来源还是这个低版本的ctags = =

话说我也挺圡的,不习惯用source insight,还是喜欢用vim写代码

posted @ 2008-07-15 10:41 ZelluX 阅读(534) | 评论 (3)编辑 收藏

没心思看离散,也不准备坚持看没有荷兰的欧洲杯决赛。闲着点好友的Q-Zone,原来Q-Zone首先会判断你的浏览器,如果是Firefox它会重定向到RSS阅读界面。

安然在开学后2个月写的一篇日志,“记忆里的名单”,惊喜的看到有我。也列出了一张属于我的名单。好,等待时间的遴选。

“于是想 如果有个妹妹 我要告诉她 好好放肆猖狂 做不可思议的事情 为友情和少年青涩的爱情花心思 做只是喜欢没有功利目的的事情 这么好的年华 就是用来这样浪费 和珍惜的~”

可惜我只保持了四五个月的这种疯狂,现在依然纠结于功利的选择。有时候曾想,或许那次失败更适合我,或许我终将把这么一条平淡无奇的路走到尽头。“表面强者”,或许还是很有道理的。

看到fofo的博的文字,“我要去杭州,把所有的事情抛掉,不管后果。这个地方太让人压抑,尽管有很玩得来的室友,有很好的足球队的队友,可以看很多以前爸妈不让看的喜欢的书还有过米的比赛,吃的东西也都很习惯,还是会在天气很好的星期天下午突然想起曾经在冬日的阳光照射下一家人在阳台上围着一张桌子吃饭的情景,还是会在一个人骑在去计算机协会的路上很难过地想着再也不会有那么四个或者五个人在一起吃完小炒放肆地在铺满夕阳的校园小路上勾肩搭背地行走了,还是会在一百多个人的课堂上怀念起那些艰苦却简单的日子里所有的笑声,还是会在网吧包夜的时候想起初中时捏着饭钱偷偷摸摸地去电脑房玩星际……想找找朋友们,调整一下自己的心情。”

真的找不回来了。在写这篇博文时也找不到以前写字的感觉了。

明天离散考试,某个记录或许将要因此打破。

posted @ 2008-06-30 02:09 ZelluX 阅读(367) | 评论 (1)编辑 收藏

不枉我周末练了那么多ZvP

不过总比分太惨了。。

posted @ 2008-06-24 00:20 ZelluX 阅读(394) | 评论 (0)编辑 收藏

     摘要: 一篇关于函数式编程的介绍,在水木Java版引起了热烈讨论。  阅读全文

posted @ 2008-06-05 21:10 ZelluX 阅读(751) | 评论 (1)编辑 收藏

1. framwork/policies/Singleton.h
Singleton模式,可以指定相应的线程模型、创建策略和生命期控制策略。
对于全局范围的Singleton实例,定义了若干个宏便于访问,例如
#define sLog MaNGOS::Singleton<Log>::Instance()
#define sMaster MaNGOS::Singleton<Master>::Instance()

Singleton的定义:


不知道这里的注释Prohibited actions...this does not prevent hijacking.是什么意思,copy constructor和hijacking有什么关系呢?

另外注意这行typedef typename ThreadingModel::Lock Guard;,原来typedef还可以用在函数上。

Singleton的Instance方法用的是标准的double-checked lock方法,关于DCL可以参考这篇博文http://www.blogjava.net/zellux/archive/2008/04/07/191365.html

2. Explicit Constructors
game/WorkPacket.h中看到的语法,防止构造函数中参数的隐式转型
比如explicit String(int n); 用String('c')声明时就会报错

posted @ 2008-06-03 19:03 ZelluX 阅读(767) | 评论 (0)编辑 收藏

一套基于文件系统的安全方案,主要通过隔离运行不可信任的程序、taint记录、事故恢复。

我的presentation:
http://docs.google.com/Presentation?id=dcjk4xx7_473cv5ddgc8

出于时间考虑没有提到paper中进程间通信的解决方法

posted @ 2008-05-28 15:23 ZelluX 阅读(492) | 评论 (0)编辑 收藏

水木上有人贴了个有趣的程序

#include  < stdlib.h >
#include 
< stdio.h >

void  print_forever( int  n)
{
    printf(
" %d\n " , n);
    print_forever(n 
+   1 );
}


int  main( int  argc,  char   * argv[])
{
    print_forever(
0 );
    
return   0 ;
}


用gcc -O2编译运行后会不停地打印从0开始的自然数,注意如果编译器没有做优化的话,打印到某个数的时候肯定会发生栈溢出从而程序终止的情况,但这个程序却能一直运行下去,说明编译器做了尾递归优化。

用gcc -O2 -S生成这个程序的汇编代码后证实了这一点。
.L6:
        movl    
%ebx, 4(%esp)
        addl    $
1%ebx
        movl    $.LC0, (
%esp)
        call    printf
        jmp     .L6
print_forever的关键部分被优化成了一个n不断增加的死循环。

接下来是分析哪个优化选项处理了尾递归。

用O3 O2 O1三个优化强度编译程序,查看汇编代码后,发现尾递归优化是O2中新增的功能。于是查看O2新开启的优化开关:
gcc -c -Q -O1 --help=optimizers > /tmp/O1-opts
gcc -c -Q -O2 --help=optimizers > /tmp/O2-opts
diff /tmp/O2-opts /tmp/O1-opts | grep enabled
输出结果:

经证实是-foptimize-sibling-calls这个选项实现了尾递归的优化,具体内容可以参看
http://gcc.gnu.org./ml/gcc-patches/2000-03/msg00867.html

posted @ 2008-05-24 02:05 ZelluX 阅读(2386) | 评论 (1)编辑 收藏

睡觉去恩

P.S 点球真不是人看的

posted @ 2008-05-22 05:44 ZelluX 阅读(435) | 评论 (0)编辑 收藏

     摘要: 一篇介绍一种全新的Web架构,另一篇介绍虚拟机的探测方法  阅读全文

posted @ 2008-05-20 20:18 ZelluX 阅读(2222) | 评论 (1)编辑 收藏