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

2008年4月10日

http://blog.yxwang.me/

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

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

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

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

posted @ 2009-04-02 01:38 ZelluX 阅读(883) | 评论 (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 阅读(839) | 评论 (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 阅读(2498) | 评论 (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 阅读(2710) | 评论 (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 阅读(776) | 评论 (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 阅读(2131) | 评论 (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 阅读(621) | 评论 (0)编辑 收藏

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

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

p.s 多谢万熊  XD

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

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

  阅读全文

posted @ 2009-01-21 14:47 ZelluX 阅读(886) | 评论 (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 阅读(2527) | 评论 (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 阅读(529) | 评论 (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 阅读(8757) | 评论 (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 阅读(504) | 评论 (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 阅读(1895) | 评论 (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 阅读(1427) | 评论 (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 阅读(433) | 评论 (0)编辑 收藏

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

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

posted @ 2008-10-13 18:26 ZelluX 阅读(1270) | 评论 (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 阅读(479) | 评论 (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 阅读(584) | 评论 (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 阅读(636) | 评论 (5)编辑 收藏

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

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

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

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

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

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

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

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

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

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

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

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

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

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

不枉我周末练了那么多ZvP

不过总比分太惨了。。

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

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

posted @ 2008-06-05 21:10 ZelluX 阅读(761) | 评论 (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 阅读(773) | 评论 (0)编辑 收藏

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

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

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

posted @ 2008-05-28 15:23 ZelluX 阅读(500) | 评论 (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 阅读(2413) | 评论 (1)编辑 收藏

睡觉去恩

P.S 点球真不是人看的

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

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

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

     摘要: 发信人: NetMD (C++), 信区: CPlusPlus
标 题: [FAQ] C/C++中的序列点
发信站: 水木社区 (Wed Feb 7 01:13:41 2007), 站内  阅读全文

posted @ 2008-05-16 10:42 ZelluX 阅读(2126) | 评论 (1)编辑 收藏

VIM Calender是个很好用的写日记的插件(http://www.vim.org/scripts/script.php?script_id=52)

水木上的rmrf写了一个同步VIM Calender和Google Calender的脚本(http://code.google.com/p/diaryvgc/downloads/list)

想到blogger.com支持通过发送邮件发布日志,于是我也写了个把VIM Calender中的日记发布到blogger.com的脚本。

这个脚本把发布情况记录在diary/poster.log中,以后每次执行只会发布最新的日志,同时考虑到当天的日记可能会被修改(blogger.com似乎不支持通过email修改日志),所以当天的日记不会被发布。

使用的时候修改开头几行的配置信息即可

#!/usr/bin/python

# A script for posting diaries created by VIM Calender to blogger.com
#
 Author: Wang Yuanxuan <zellux@gmail.com>

import smtplib, os, re, datetime
from email.mime.text import MIMEText

fromaddr 
= xxxxx@fudan.edu.cn'
toaddr 
= xxxx.xxxx@blogger.com'
smtpserver 
= 'mail.fudan.edu.cn'
diarydir 
= '/home/user_name/diary'
username 
= 'xxxxxx'
password 
= 'xxxxxx'
logpath 
= diarydir + '/poster.log'

def PostMail(title, content):
    msg 
= MIMEText(content + '\r\n#end\r\n')
    msg[
'Subject'= title
    msg[
'From'= fromaddr
    msg[
'To'= toaddr

    server 
= smtplib.SMTP(smtpserver)
    server.login(username, password)
    
# server.set_debuglevel(1)
    server.sendmail(fromaddr, [toaddr], msg.as_string())
    server.quit()

# Load log file. Create a new one if not exist.
posted = []
if os.path.isfile(logpath):
    temp 
= open(logpath, 'r')
    posted 
= [line[:-1for line in temp.readlines()]
    log 
= open(logpath, 'a')
else:
    
print "A new poster log has been created at " + logpath
    log 
= open(logpath, 'w')

pattern 
= r'(\d{4})/(\d{1,2})/(\d{1,2}).cal$'
scanner 
= re.compile(pattern)

for (top, dirname, filenames) in os.walk(diarydir):
    
for filename in filenames:
        fullpath 
= os.path.join(top, filename)
        
if scanner.search(fullpath):
            (year, month, day) 
= scanner.search(fullpath).groups()
            filedate 
= datetime.date(int(year), int(month), int(day))
            title 
= filedate.isoformat()
            
if filedate == datetime.date.today():
                
continue
            
if fullpath not in posted:
                log.write(fullpath 
+ '\n')
                text 
= open(fullpath).read()
                PostMail(title, text)
                
print 'The diary ' + title + ' has been posted'

log.close()

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

这书的数学分析方面有点过于简单了,连绝对值、二维坐标系是个什么东东都会给你解释一下,所以看起来很快。

第一章 经济学十大原理

第二章 像经济学家一样思考
生产可能性边界(production possibilites frontier)通常是凹向原点的形状。
实证表述(positive statements):企图描述世界是什么的观点。经济学的许多内容是实证的。
规范表述(normative statements):企图描述世界应该是什么的观点。

第三章 相互依赖性与贸易的好处
机会成本与比较优势

第四章 供给与需求的市场力量

第五章 弹性及其应用
需求价格弹性 = 需求量变动百分比 / 价格变动百分比
供给价格弹性 = 供给变动百分比 / 价格变动百分比
例:由于毒品的需求缺乏弹性,禁毒引起的毒品价格提高的比例大于毒品使用减少的比例,因此禁毒会增加与毒品相关的犯罪。(短期)

第六章 供给、需求与政府政策
限制性价格上限导致短缺,限制性价格下限导致过剩。
例:最低工资法导致失业。
一旦市场达到新均衡,无论向谁征税,都是买者与卖者分摊税收负担。
例:由于劳动的供给远比劳动的需求缺乏弹性,是工人而不是企业承担了大部分工薪税的负担。

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

发信人: bluegene (蓝色基因||多看paper才是王道), 信区: Quant
标 题: 美国次贷危机之通俗演义 zz (转载)
发信站: BBS 未名空间站 (Fri Mar 21 01:24:10 2008)

【 以下文字转载自 ChinaNews 讨论区 】
发信人: chaoz (饭局局长), 信区: ChinaNews
标 题: 美国次贷危机之通俗演义 zz
发信站: BBS 未名空间站 (Thu Mar 20 23:49:57 2008)

在美国,贷款是非常普遍的现象,从房子到汽车,从信用卡到电话账单,贷款无处不在。当地人很少全款买房,通常都是长时间贷款。可是我们也知道,在这里失业 和再就业是很常见的现象。这些收入并不稳定甚至根本没有收入的人,他们怎么买房呢?因为信用等级达不到标准,他们就被定义为次级贷款者。

大约从10年前开始,那个时候贷款公司漫天的广告就出现在电视上、报纸上、街头,抑或在你的信箱里塞满诱人的传单:

“你想过中产阶级的生活吗?买房吧!”

“积蓄不够吗?贷款吧!”

“没有收入吗?找阿牛贷款公司吧!”

“首付也付不起?我们提供零首付!”

“担心利息太高?头两年我们提供3%的优惠利率!”

“每个月还是付不起?没关系,头24个月你只需要支付利息,贷款的本金可以两年后再付!想想看,两年后你肯定已经找到工作或者被提升为经理了,到时候还怕付不起!”

“担心两年后还是还不起?哎呀,你也真是太小心了,看看现在的房子比两年前涨了多少,到时候你转手卖给别人啊,不仅白住两年,还可能赚一笔呢!再说了,又不用你出钱,我都相信你一定行的,难道我敢贷,你还不敢借?”

在这样的诱惑下,无数美国市民毫不犹豫地选择了贷款买房。(你替他们担心两年后的债务?向来自我感觉良好的美国市民会告诉你,演电影的都能当上州长,两年后说不定我还能竞选总统呢。)

阿牛贷款公司短短几个月就取得了惊人的业绩,可是钱都贷出去了,能不能收回来呢?公司的董事长——阿牛先生,那也是熟读美国经济史的人物,不可能不知道房 地产市场也是有风险的,所以这笔收益看来不能独吞,要找个合伙人分担风险才行。于是阿牛找到美国经济界的带头大哥——投行。这些家伙可都是名字响当当的主 儿(美林、高盛、摩根),他们每天做什么呢?就是吃饱了闲着也是闲着,于是找来诺贝尔经济学家,找来哈佛教授,用上最新的经济数据模型,一番鼓捣之后,弄 出几份分析报告,从而评价一下某某股票是否值得买进,某某国家的股市已经有泡沫了,一群在风险评估市场里面骗吃骗喝的主儿,你说他们看到这里面有风险没? 用脚都看得到!可是有利润啊,那还犹豫什么,接手搞吧!于是经济学家、大学教授以数据模型、老三样评估之后,重新包装一下,就弄出了新产品——CDO (注: Collateralized Debt Obligation,债务抵押债券),说穿了就是债券,通过发行和销售这个CDO债券,让债券的持有人来分担房屋贷款的风险。

光这样卖,风险太高还是没人买啊,假设原来的债券风险等级是6,属于中等偏高。于是投行把它分成高级和普通CDO两个部分,发生债务危机时,高级CDO享 有优先赔付的权利。这样两部分的风险等级分别变成了4和8,总风险不变,但是前者就属于中低风险债券了,凭投行三寸不烂“金”舌,当然卖了个满堂彩!可是 剩下的风险等级8的高风险债券怎么办呢?

于是投行找到了对冲基金,对冲基金又是什么人,那可是在全世界金融界买空卖多、呼风唤雨的角色,过的就是刀口舔血的日子,这点风险小意思!于是凭借着老关 系,在世界范围内找利率最低的银行借来钱,然后大举买入这部分普通CDO债券,2006年以前,日本央行贷款利率仅为1.5%;普通CDO利率可能达到 12%,所以光靠利息差对冲基金就赚得盆满钵满了。

这样一来,奇妙的事情发生了,2001年末,美国的房地产一路飙升,短短几年就翻了一倍多,这样一来就如同阿牛贷款公司开头的广告一样,根本不会出现还不 起房款的事情,就算没钱还,把房子一卖还可以赚一笔钱。结果是从贷款买房的人,到阿牛贷款公司,到各大投行,到各个银行,到对冲基金人人都赚钱,但是投行 却不太高兴了!当初是觉得普通CDO风险太高,才扔给对冲基金的,没想到这帮家伙比自己赚的还多,净值一个劲地涨,早知道自己留着玩了,于是投行也开始买 入对冲基金,打算分一杯羹了。这就好像“老黑”家里有馊了的饭菜,正巧看见隔壁邻居那只讨厌的小花狗,本来打算毒它一把,没想到小花狗吃了不但没事,反而 还越长越壮了,“老黑”这下可蒙了,难道馊了的饭菜营养更好,于是自己也开始吃了!

这下又把对冲基金乐坏了,他们是什么人,手里有1块钱,就能想办法借10块钱来玩的土匪啊,现在拿着抢手的CDO还能老实?于是他们又把手里的CDO债券 抵押给银行,换得10倍的贷款,然后继续追着投行买普通CDO。嘿,当初可是签了协议,这些CDO都归我们的!!!投行心里那个不爽啊,除了继续闷声买对 冲基金之外,他们又想出了一个新产品,就叫CDS (注:Credit Default Swap,信用违约交换)好了,华尔街就是这些天才产品的温床:不是都觉得原来的CDO风险高吗,那我投保好了,每年从CDO里面拿出一部分钱作为保金, 白送给保险公司,但是将来出了风险,大家一起承担。

保险公司想,不错啊,眼下CDO这么赚钱,1分钱都不用出就分利润,这不是每年白送钱给我们吗?干了!

对冲基金想,不错啊,已经赚了几年了,以后风险越来越大,光是分一部分利润出去,就有保险公司承担一半风险,干了!

于是再次皆大欢喜,CDS也卖火了!但是事情到这里还没有结束:因为“聪明”的华尔街人又想出了基于CDS的创新产品!我们假设CDS已经为我们带来了 50亿元的收益,现在我新发行一个“三毛”基金,这个基金是专门投资买入CDS的,显然这个建立在之前一系列产品之上的基金的风险是很高的,但是我把之前 已经赚的50亿元投入作为保证金,如果这个基金发生亏损,那么先用这50亿元垫付,只有这50亿元亏完了,你投资的本金才会开始亏损,而在这之前你是可以 提前赎回的,首发规模500亿元。天哪,还有比这个还爽的基金吗?1元面值买入的基金,亏到0.90元都不会亏自己的钱,赚了却每分钱都是自己的!评级机 构看到这个天才设想,简直是毫不犹豫:给予AAA评级!

结果这个“三毛”可卖疯了,各种养老基金、教育基金、理财产品,甚至其他国家的银行也纷纷买入。虽然首发规模是原定的500亿元,可是后续发行了多少亿, 简直已经无法估算了,但是保证金50亿元却没有变。如果现有规模5000亿元,那保证金就只能保证在基金净值不低于0.99元时,你不会亏钱了。

当时间走到了2006年年底,风光了整整5年的美国房地产终于从顶峰重重摔了下来,这条食物链也终于开始断裂。因为房价下跌,优惠贷款利率的时限到了之 后,先是普通民众无法偿还贷款,然后阿牛贷款公司倒闭,对冲基金大幅亏损,继而连累保险公司和贷款的银行,花旗、摩根相继发布巨额亏损报告,同时投资对冲 基金的各大投行也纷纷亏损,然后股市大跌,民众普遍亏钱,无法偿还房贷的民众继续增多……最终,美国次贷危机爆发。(屈直言)

次贷危机是否会酿成全球危机?
--
只要功夫深, 一夜夫妻百日恩.


※ 来源:·WWW 未名空间站 海外: mitbbs.com 中国: mitbbs.cn·[FROM: 141.219.]

posted @ 2008-05-08 00:26 ZelluX 阅读(421) | 评论 (0)编辑 收藏

     摘要: 一种利用虚拟机进行的攻击手段(下篇)  阅读全文

posted @ 2008-05-06 14:35 ZelluX 阅读(1466) | 评论 (1)编辑 收藏

     摘要: 一种利用虚拟机进行的攻击手段  阅读全文

posted @ 2008-05-05 21:53 ZelluX 阅读(1736) | 评论 (0)编辑 收藏










Fight Club

1. 不能谈论斗阵俱乐部。
2. 不能谈论斗阵俱乐部。
3. 只要有人喊停,或者受伤,快累死了,打斗就得停。
4. 一次只能两人打
5. 一次一场
6. 脱掉衬衫和鞋子
7. 打斗没有时限
8. 只要你是初次参加,就一定得打。


太混乱了

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











秒速5センチメートル

“樱花飘落的速度,是每秒5厘米。”

凄美无奈的故事,有点像村上的《国境以南》,只是主人公最后仍然在寻找着对方。

新海诚的动画色彩很斑斓,很华丽。

写到这里,千千静听里正好随机播放到了那首One More Time, One More Chance,几百分之一的概率,呵呵。

晚上看风格截然不同的National Trasure: Book of Secrets

posted @ 2008-05-03 18:10 ZelluX 阅读(556) | 评论 (4)编辑 收藏

在机房电脑的Arch Linux上搭了个MediaWiki,作为自己的知识库。
前几天在水木上看到的想法,觉得这样很有成就感,尽管现在还没学多少东西。
一步一个脚印,慢慢扩充。

Mika的歌还真是好听。

posted @ 2008-04-26 14:39 ZelluX 阅读(373) | 评论 (2)编辑 收藏

Problem

Every bus in the Ekaterinburg city has a special man (or woman) called conductor. When you ride the bus, you have to give money to the conductor. We know that there are more then P% conductors and less then Q% conductors. Your task is to determine a minimal possible number of Ekaterinburg citizens.


我只能说太挫了。。。精度问题搞了半天,看来浮点还是要尽量化成整型再算啊。


还有个问题就是q*i是开区间还是闭区间,总之Wrong Answer了无数次后总算过了。。。

posted @ 2008-04-23 22:44 ZelluX 阅读(807) | 评论 (10)编辑 收藏

     摘要: 算法导论第27章,在并行处理的条件下高效的排序算法。  阅读全文

posted @ 2008-04-23 20:22 ZelluX 阅读(1740) | 评论 (2)编辑 收藏

因为MSN一开始会尝试连接crl.microsoft.com,把这个网站屏蔽了就行。
在hosts文件中加入
127.0.0.1   crl.microsoft.com

posted @ 2008-04-20 17:10 ZelluX 阅读(1185) | 评论 (3)编辑 收藏

贴几个链接,以后有空再看

Microsoft Live Mail  http://securitylabs.websense.com/content/Blogs/3063.aspx#
http://securitylabs.websense.com/content/Blogs/2907.aspx

Google http://securitylabs.websense.com/content/Blogs/2919.aspx#

posted @ 2008-04-18 00:30 ZelluX 阅读(418) | 评论 (1)编辑 收藏

http://www.nocow.cn/index.php

抽时间多做做,提高下我可怜的算法功底 >,<

posted @ 2008-04-17 11:48 ZelluX 阅读(698) | 评论 (2)编辑 收藏

~/.vim/ftplugin/ 下有c.vim和cpp.vim
但是vim打开cpp和c文件时使用的配置都是c.vim中指定的

使用vim xxx.cpp -V跟踪了打开的配置列表,发现有这么一段

line 17: sourcing "/usr/share/vim/ftplugin/cpp.vim"
Searching for "ftplugin/c.vim ftplugin/c_*.vim ftplugin/c/*.vim" in "/home/wyx/.vim,/usr/share/vim,/usr/share/vim,
/usr/share/vim/after,/home/wyx/.vim/after"
Searching for "/home/wyx/.vim/ftplugin/c.vim"
line 12: sourcing "/home/wyx/.vim/ftplugin/c.vim"

原来/usr/share/vim/ftplugin/cpp.vim中直接调用了c.vim
runtime! ftplugin/c.vim ftplugin/c_*.vim ftplugin/c/*.vim
把这行注释掉,问题解决

posted @ 2008-04-17 00:48 ZelluX 阅读(1924) | 评论 (0)编辑 收藏

要提高效率果然得远离网络,躺床上看paper理解起来快多了
总算把晚上要讲的ppt做出来了,囧

posted @ 2008-04-16 14:57 ZelluX 阅读(336) | 评论 (1)编辑 收藏

下午打球直到体力极限,一路淋雨跑回寝室,洗澡,感冒,低落。想回家。

有时候会想,几年后,真的就要在上海这个地方工作立足吗?

我想看一堆电影 想读一堆书 想学C# Lisp Python 想上ACM OJ网站切题 想参加一次TopCoder比赛 想学埙 想学钢琴 想睡觉 想看微经 想练英语 想看内核 想到处旅游

终会和现实冲突。于是我想退实验室。几个小时后又放弃这个决定。

终究是怕这怕那保守着缓慢前进的人。

posted @ 2008-04-15 22:23 ZelluX 阅读(354) | 评论 (1)编辑 收藏

计算机科学论坛最近举办了一个阅读样章,提交书评的活动,具体内容请见http://www.ieee.org.cn/dispbbs.asp?boardID=42&ID=61162

这里我想针对样章上的一个问题谈谈自己的理解。

问题很简单,求二进制中1的个数。对于一个字节(8bit)的变量,求其二进制表示中"1"的个数,要求算法的执行效率尽可能的高。

先来看看样章上给出的几个算法:

解法一,每次除二,看是否为奇数,是的话就累计加一,最后这个结果就是二进制表示中1的个数。

解法二,同样用到一个循环,只是里面的操作用位移操作简化了。

   1:  int Count(int v)  
   2:  {  
   3:      int num = 0;
   4:      while (v) {  
   5:          num += v & 0x01;  
   6:          v >>= 1;  
   7:      }  
   8:      return num;  
   9:  }

解法三,用到一个巧妙的与操作,v & (v -1 )每次能消去二进制表示中最后一位1,利用这个技巧可以减少一定的循环次数。

解法四,查表法,因为只有数据8bit,直接建一张表,包含各个数中1的个数,然后查表就行。复杂度O(1)。

   1:  int countTable[256] = { 0, 1, 1, 2, 1, ..., 7, 7, 8 };  
   2:     
   3:  int Count(int v) {  
   4:      return countTable[v];  
   5:  }
  
好了,这就是样章上给出的四种方案,下面谈谈我的看法。

首先是对算法的衡量上,复杂度真的是唯一的标准吗?尤其对于这种数据规模给定,而且很小的情况下,复杂度其实是个比较次要的因素。

查表法的复杂度为O(1),我用解法一,循环八次固定,复杂度也是O(1)。至于数据规模变大,变成32位整型,那查表法自然也不合适了。

其次,我觉得既然是这样一个很小的操作,衡量的尺度也必然要小,CPU时钟周期可以作为一个参考。

解法一里有若干次整数加法,若干次整数除法(一般的编译器都能把它优化成位移),还有几个循环分支判断,几个奇偶性判断(这个比较耗时间,根据CSAPP上的数据,一般一个branch penalty得耗掉14个左右的cycle),加起来大概几十个cycle吧。

再看解法四,查表法看似一次地址计算就能解决,但实际上这里用到一个访存操作,而且第一次访存的时候很有可能那个数组不在cache里,这样一个cache miss导致的后果可能就是耗去几十甚至上百个cycle(因为要访问内存)。所以对于这种“小操作”,这个算法的性能其实是很差的。

这里我再推荐几个解决这个问题的算法,以32位无符号整型为例。

   1:  int Count(unsigned x) {  
   2:     x = x - ((x >> 1) & 0x55555555);   
   3:     x = (x & 0x33333333) + ((x >> 2) & 0x33333333);   
   4:     x = (x + (x >> 4)) & 0x0F0F0F0F;   
   5:     x = x + (x >> 8);   
   6:     x = x + (x >> 16);   
   7:     return x & 0x0000003F;   
   8:  }
  
这里用的是二分法,两两一组相加,之后四个四个一组相加,接着八个八个,最后就得到各位之和了。

还有一个更巧妙的HAKMEM算法

   1:  int Count(unsigned x) {
   2:     unsigned n;   
   3:     
   4:     n = (x >> 1) & 033333333333;   
   5:     x = x - n;  
   6:     n = (n >> 1) & 033333333333;  
   7:     x = x - n;   
   8:     x = (x + (x >> 3)) & 030707070707;  
   9:     x = modu(x, 63); 
   10:     return x;  
   11:  }
  
首先是将二进制各位三个一组,求出每组中1的个数,然后相邻两组归并,得到六个一组的1的个数,最后很巧妙的用除63取余得到了结果。

因为2^6 = 64,也就是说 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63),这里的等号表示同余。

这个程序只需要十条左右指令,而且不访存,速度很快。

由此可见,衡量一个算法实际效果不单要看复杂度,还要结合其他情况具体分析。

关于后面的两道扩展问题,问题一是问32位整型如何处理,这个上面已经讲了。

问题二是给定两个整数A和B,问A和B有多少位是不同的。

这个问题其实就是数1问题多了一个步骤,只要先算出A和B的异或结果,然后求这个值中1的个数就行了。

总体看来这本书还是很不错的,比较喜欢里面针对一个问题提出不同算法并不断改进的风格。这里提出一点个人的理解,望大家指正 ;-)

(by ZelluX   http://www.blogjava.net/zellux)

posted @ 2008-04-15 00:23 ZelluX 阅读(4249) | 评论 (8)编辑 收藏

http://www.25hoursaday.com/CsharpVsJava.html#wishlist

有点长,不过写得很不错

posted @ 2008-04-14 12:27 ZelluX 阅读(357) | 评论 (0)编辑 收藏

     摘要: 以下简单的整理来自游侠 netshow论坛的帖子 部分补充  阅读全文

posted @ 2008-04-13 11:30 ZelluX 阅读(1052) | 评论 (1)编辑 收藏

     摘要: 问题:
给定n个32位无符号整数,求出其中异或结果最大的两个整数。  阅读全文

posted @ 2008-04-10 00:33 ZelluX 阅读(4646) | 评论 (5)编辑 收藏