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

2008年2月6日

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)编辑 收藏

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

posted @ 2008-05-16 10:42 ZelluX 阅读(2103) | 评论 (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 阅读(1263) | 评论 (0)编辑 收藏

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

第一章 经济学十大原理

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

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

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

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

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

posted @ 2008-05-10 15:29 ZelluX 阅读(481) | 评论 (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 阅读(410) | 评论 (0)编辑 收藏

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

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

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

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










Fight Club

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


太混乱了

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











秒速5センチメートル

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

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

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

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

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

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

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

Mika的歌还真是好听。

posted @ 2008-04-26 14:39 ZelluX 阅读(360) | 评论 (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 阅读(796) | 评论 (10)编辑 收藏

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

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

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

posted @ 2008-04-20 17:10 ZelluX 阅读(1178) | 评论 (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 阅读(409) | 评论 (1)编辑 收藏

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

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

posted @ 2008-04-17 11:48 ZelluX 阅读(691) | 评论 (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 阅读(1913) | 评论 (0)编辑 收藏

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

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

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

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

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

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

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

posted @ 2008-04-15 22:23 ZelluX 阅读(343) | 评论 (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 阅读(4235) | 评论 (8)编辑 收藏

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

有点长,不过写得很不错

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

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

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

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

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

转载请注明 作者 ZelluX    http://www.blogjava.net/zellux

看OOP教材时,提到了一个双检测锁定(Double-Checked Lock, DCL)的问题,但是书上没有多介绍,只是说这是一个和底层内存机制有关的漏洞。查阅了下相关资料,对这个问题大致有了点了解。

从头开始说吧。

在多线程的情况下Singleton模式会遇到不少问题,一个简单的例子

   1:  class Singleton {     
   2:      private static Singleton instance = null;     
   3:        
   4:      public static Singleton instance() {     
   5:          if (instance == null) {     
   6:              instance = new Singleton();     
   7:          }     
   8:          return instance;    
   9:      }    
   10:  }

  
假设这样一个场景,有两个线程调用Singleton.instance(),首先线程一判断instance是否等于null,判断完后一瞬间虚拟机把线程二调度为运行线程,线程二再次判断instance是否为null,然后创建一个Singleton实例,线程二的时间片用完后,线程一被唤醒,接下来它执行的代码依然是instance = new Singleton();
两次调用返回了不同的对象,出现问题了。

最简单的方法自然是在类被载入时就初始化这个对象:private static Singleton instance = new Singleton();

JLS(Java Language Specification)中规定了一个类只会被初始化一次,所以这样做肯定是没问题的。

但是如果要实现延迟初始化(Lazy initialization),比如这个实例初始化时的参数要在运行期才能确定,应该怎么做呢?

依然有最简单的方法:使用synchronized关键字修饰初始化方法:

    public synchronized static Singleton instance() {       
        if (instance == null) {
            instance = new Singleton();
        }
        return instance;
    }

   
这里有一个性能问题:多个线程同时访问这个方法时,会因为同步而导致每次只有一个线程运行,影响程序性能。而事实上初始化完毕后只需要简单的返回instance的引用就行了。

DCL是一个“看似”有效的解决方法,先把对应代码放上来吧:

    1 :   class Singleton {  
    2 :       private static Singleton instance = null ;  
    3 :     
    4 :       public static Singleton instance() {  
    5 :           if (instance == null ) {
    6 :               synchronized (this) {  
    7 :                   if (instance == null)
    8 :                      instance = new Singleton();
    9 :              }
    10 :          }
    11 :          return instance;
    12 :      }
    13 :  }

用JavaWorld上对应文章的标题来评论这种做法就是smart, but broken。来看原因:

Java编译器为了提高程序性能会进行指令调度,CPU在执行指令时同样出于性能会乱序执行(至少现在用的大多数通用处理器都是out-of-order的),另外cache的存在也会改变数据回写内存时的顺序[2]。JMM(Java Memory Model, 见[1])指出所有的这些优化都是允许的,只要运行结果和严格按顺序执行所得的结果一样即可。

Java假设每个线程都跑在自己的处理器上,享有自己的内存,和共享的主存交互。注意即使在单核上这种模型也是有意义的,考虑到cache和寄存器会保存部分临时变量。理论上每个线程修改自己的内存后,必须立即更新对应的主存内容。但是Java设计师们认为这种约束会影响程序性能,他们试着创造了一套让程序跑得更快、但又保证线程之间的交互与预期一致的内存模型。

synchronized关键字便是其中一把利器。事实上,synchronized块的实现和Linux中的信号量(semaphore)还是有区别的,前者过程中锁的获得和释放都会都会引发一次Memory Barrier来强制线程本地内存和主存之间的同步。通过这个机制,Java中的同步机制保证了synchronized块中指令的原子性(atomic)。

好了,回过头来看DCL问题。看起来访问一个未同步的instance字段不会产生什么问题,我们再次来假设一个场景:

线程一进入同步块,执行instance = new Singleton(); 线程二刚开始执行getResource();

按照顺序的话,接下来应该执行的步骤是 1) 分配新的Singleton对象的内存 2) 调用Singleton的构造器,初始化成员字段 3) instance被赋为指向新的对象的引用。

前面说过,编译器或处理器都为了提高性能都有可能进行指令的乱序执行,线程一的真正执行步骤可能是1) 分配内存 2) instance指向新对象 3) 初始化新实例。如果线程二在2完成后3执行前被唤醒,它看到了一个不为null的instance,跳出方法体走了,带着一个还没初始化的Singleton对象。

错误发生的一种情形就是这样,关于更详细的编译器指令调度导致的问题,可以参看这个网页 [4]。

[3] 中提供了一个编译器指令调度的证据

instance = new Singleton(); 这条命令在Symantec JIT中被编译成

0206106A   mov         eax,0F97E78h
0206106F   call        01F6B210                  ; 分配空间
02061074   mov         dword ptr [ebp],eax       ; EBP中保存了instance的地址

02061077   mov         ecx,dword ptr [eax]       ; 解引用,获得新的指针地址

02061079   mov         dword ptr [ecx],100h      ; 接下来四行是inline后的构造器
0206107F   mov         dword ptr [ecx+4],200h   
02061086   mov         dword ptr [ecx+8],400h
0206108D   mov         dword ptr [ecx+0Ch],0F84030h

可以看到,赋值完成在初始化之前,而这是JLS允许的。
 
另一种情形是,假设线程一安稳地完成Singleton对象的初始化,退出了同步块,并同步了和本地内存和主存。线程二来了,看到一个非空的引用,拿走。注意线程二没有执行一个Read Barrier,因为它根本就没进后面的同步块。所以很有可能此时它看到的数据是陈旧的。

还有很多人根据已知的几种提出了一个又一个fix的方法,但最终还是出现了更多的问题。可以参阅[3]中的介绍。

[5]中还说明了即使把instance字段声明为volatile还是无法避免错误的原因。

由此可见,安全的Singleton的构造一般只有两种方法,一是在类载入时就创建该实例,二是使用性能较差的synchronized方法。

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

参考资料:

[1] Java Language Specification, Second Edition, 第17章介绍了Java中线程和内存交互关系的具体细节。
[2] out-of-order与cache的介绍可以参阅Computer System, A Programmer's Perspective的第四、五章。
[3] The "Double-Checked Locking is Broken" Declaration, http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
[4] Synchronization and the Java Memory Model, http://gee.cs.oswego.edu/dl/cpj/jmm.html
[5] Double-checked locking: Clever, but broken, http://www.javaworld.com/javaworld/jw-02-2001/jw-0209-double.html?page=1
[6] Holub on Patterns, Learning Design Patterns by Looking at Code

 

posted @ 2008-04-07 21:58 ZelluX 阅读(2307) | 评论 (7)编辑 收藏

感冒发烧。

把不应该存在的博文全删了。

我知道我在和自己赌气。

那又如何。

回过头来,这两年我所得到的,不过是可以随手扔掉的东西。

最后,acm的那些人们加油。

posted @ 2008-04-06 14:05 ZelluX 阅读(324) | 评论 (3)编辑 收藏

翘课大半,作业一半不交一半抄,总之太不像学生了。
搞得现在Super Scalar都只知道个大概,tableaux也知其然而不知所以然。
下星期好好参与一次,上课、作业一个都不能少,恩。
至于之后么,再说咯。

posted @ 2008-04-04 15:33 ZelluX 阅读(389) | 评论 (0)编辑 收藏

没事干找了几个SICP上的习题做,先是一道以前只想出一种很啰嗦的写法的题目

Ex 2.18
把一个列表倒过来。不习惯在lisp里用iterative方式 >,<

接下来几题都是Map-Reduce思想的应用(或者照书上的说法,用enumerator - filter - map - accumulator这四个步骤操作一个list)

用到的几个函数:

enumrate-tree 的功能是遍历一个树状结构,把其中的所有叶子保存在一个list中。

Ex 2.34
利用Horner's rule计算多项式结果(这公式这几天还经常碰到)

Ex 2.35
数出一棵树中的叶子数。这题我的做法比较土,没想到map-reduce操作上的递归,而是把叶子节点的值都改成1然后一个累加。

其实只要递归调用主函数就行了

Ex 2.36
可以理解为计算矩阵各列之和吧


> (accumulate-n + 0 (list (list 1 2 3) (list 4 5 6) (list 7 8 9) (list 10 11 12)))
(22 26 30)

posted @ 2008-04-03 22:33 ZelluX 阅读(1084) | 评论 (0)编辑 收藏

这语言真不错,不像Java那么呆,可惜不开源。
入门看的书是CLR via C#中文版,翻译质量不错,起码到现在还没觉得有必要翻一翻原版(不过为什么中文书都喜欢把“栈”叫成“堆栈”呢)。
前面几章粗略看了下,从第四章类型基础开始重点阅读。
继续漫无目的的学习感兴趣的东西,学习之中经常会惊喜的发现,自己看问题的角度已经不同于之前了。

1. 类的new操作会递归调用该类的所有父类构造器,直到System.Object,后者的构造器只是简单返回,用ILDasm查看MSCorLib.dll可以证实这一点。

2. is和as操作符,is类似于Java中的instanceof,as会先检查类型,如果兼容返回该对象的引用,反之返回null。
Emplooee e = o as Employee;
if (e != null{
    
// blah
}
利用as可以做到只检验一次对象类型,提高程序性能。这本书的很多地方都提到了性能因素。

3. 方法调用和x86上汇编语言调用机制很类似。先是参数入栈,接着返回地址入栈,返回的时候也差不多。不知道x64等寄存器较多的架构上会不会使用寄存器传参呢,呵呵。

4. 作为方法的prologue的一部分,CLR会自动将所有局部变量初始化为null或0。感觉这个自动初始化没什么必要,在第五章可以看到。
SomeVal v1;
SomeVal v1 
= new SomeVal();
这里的SomeVal都是值类型,CLR都会将它们初始化为0。区别在于C#认为前者没有初始化,直接使用这个值会报错;而后者在不赋值的情况下使用这个值。
可能这是CLR和C#之间不统一导致的冗余步骤吧。

5. CLR开始在一个进程中运行时,会给System.Type类型创建一个实例,每个类都会包含指向System.Type类型的指针。

6. CLR提供了执行溢出检查的计算指令,例如add.ovf对应add,mul.ovf对应mul。C#中默认关闭溢出检查。
可以使用checked关键字使用溢出检查。一般情况下,对预计可能发生溢出的代码放到checked块中,对允许溢出的代码(比如计算hash值)放到一个unchecked块中,其他情况,Debug时打开编译器的/checked+开关,Release版本关闭。

7. 所有的值类型都是从System.ValueType继承的。后者重写了Equals方法,比较两个值对象是否完全相等。

8. boxing和unboxing。
boxing:托管堆中分配内存,复制值类型,然后返回对象地址。
unboxing:相当于一个通过指针取值的过程,不过这个指针是已装箱部分中的实际值部分。

9. FCL(Framework Class Library)中包含了支持值类型的泛型容器类,不需要对容器中的元素进行boxing/unboxing处理。
不过这里就有个问题了,值类型的话是放在栈上的,生命周期小于容器的,这个怎么处理呢?
第16章才详细解释泛型,先把这个问题留着吧 =,=

10. 依然是性能问题。有时候编译器会反复对一个值类型boxing,此时手动boxing会提高一些性能。
Int32 v = 5;
// 需三次boxing
Console.WriteLine("{0}, {1}, {2}", v, v, v);

// 只需一次boxing
Object o = v;
Console.WriteLine(
"{0}, {1}, {2}", o, o, o);

接下来书上举了个很搞的例子说明boxing和unboxing的各种情况,其实也很容易理解。

posted @ 2008-04-02 23:33 ZelluX 阅读(1524) | 评论 (14)编辑 收藏

    火车缓缓地开着,混杂的人群。此时的我不属于两边世界中的任何一个,孤立于这种空间和从属感的交界处。理下思路,趁着记忆的新鲜,在手机上敲下这四天的感受,以弥补将来的某天可能发生的对这次旅行的淡忘。

Zijingang Campus: A Fudaner's Perspective

1. Abstract
一次课堂电影(话剧《暗恋桃花源》[5])
旁听两节课,图形学和线性代数。图形学课上回答一次问题 =_=
一场越剧,小百花越剧团的《春琴传》
一场话剧,黑白剧社[1]的《我在天堂等你》[2]
半天图书馆自修,读了半章SICP[4]和一篇paper
半天机房灌水,水木C版版主上任后的第一个操作居然是在浙大完成的
半天在“风雨操场”打球
一晚上在浙大战网打了十盘星际,九胜一负

2. Introduction
    K900到车管所,一站的路程后到达正门。紫金港的正门没有试图制造一种空间隔离感,宽敞的道路上横躺着一块刻有“浙江大学”的石块,构成了形式上的正门。步行百余部后,回头才意识到原来百余步前的所处位置竟是一个入口。
    这个入口给人一种宽广、松驰的感觉,与复旦的正门放置伟人像不同,紫金港的封面很平坦。除了草坪就无其他,可以望到天际。整个紫金港都给我这样的感觉:草坪、树、湖的世界中,点缀着几幢风格各异的建筑。

3. Details
3.1 上课
    其实到浙大吃完饭后做的第一件事就是旁听了一节数媒专业的图形学,上的是三维空间的坐标变换。老师上课进度偏慢,绝大部分学生上课都很认真。感到那么一点点的压力 >,<

3.2 图书馆
    一直觉得图书馆是大学的灵魂组成部分之一。甚至大一的时候觉得有个好的图书馆和一套优秀的借阅制度就足以成为一个好的大学了。也因此新到一个大学后总是特别关注那里的图书馆。
    紫金港图书馆依傍在高耸的行政楼旁,可以把它比成计算中心,行政楼对应于光华主楼,较之后者它们靠得更紧密些。浙大同学说外校同学来看图书馆时,第一反应总是误把行政楼当图书馆。喜欢图书馆的这种低调。
    图书馆的书架分类很笼统,所有的理工类书橱都被贴上了“自然科学”的标签,恐怕找书的时候要很依赖电脑。抽样调查了计算机类书籍,书目较小,重复率较大,甚至会有十几册同本书罢占一层书架的情况。阅读环境很不错,落地窗,明亮。窗外便是那片湖,一如图书馆般地平静。若是把座椅换成摇椅,再加上一杯咖啡,最愉悦的享受莫过于此。
    离开图书馆时还让同学代借了本SICP[4],本想带回上海以此要胁该同学五一来复旦,到时候再还的。无奈多带本书太麻烦,回来之前还是还掉了。

3.3 付费
    住宿楼旁有几家小吃店,其中不少店都是设置了一个单独的付费窗,而这个付费机制里没有任何凭证,或者说点了吃的却不付钱是很容易做到。别的不多说,这样一种店与客之间的信任给人一种亲切感。当然这也和紫金港地理位置较偏远,外人较少有关。

3.4 话剧
    看了黑白剧社[1]的《我在天堂等你》[2]。话剧在一个可容纳百人左右的小书屋里进行。由于一个月前刚看过人艺的《榆树下的欲望》[3],相比之下学生的功底自然略逊一筹,尤其是对老年人的刻划上。不过总体还是很不错的。
    记忆最深的是社员的那份激情,话剧结束后,演员和工作人员挨个自我介绍完毕,然后跑出书屋,站在门口等待出来的观众,齐喊“再见”“谢谢”。下楼走出百余米后,听到后面三声击掌,接着是社员们高喊“谢谢你们”,如此重复几遍,一阵高过一阵。被这种热情所震撼。

3.5 肆
    一位同学的寝室门口贴着一张记录着这个班级同学的奋斗目标之类的墙纸,中间是一个硕大的草体“肆”。奋斗目标都很直接,譬如要被Stanford商学院录取,要进入某某大公司云云。不怎么喜欢这种过于外露的上进心,更欣赏复旦略带散漫的风格。

3.6 还是课
    浙大课比较多。上下午各5节,每节45分钟,中间休息5/15分。同时周末有课也是很常见的现象,为了提高绩点而重修的同学通常周末的课表也很满。个人不喜欢这种课多的生活,喜欢兴趣驱动的学习,不喜欢自己的学习方向太受外力的牵引。

4. The End
    总是有一种声音提醒自己,我不属于这里,注定不属于。太多的不应该出现的巧合,太多的主观的或是客观的借口。我有自己的天地,那里与浙大没有交集,即便我希望会有。

5. Acknowledgements
    感谢浙大那些被我折腾、蹭吃蹭喝的同学。
    感谢版主的m或b。

6. References
[1] 黑白剧社 http://www.qsc.zju.edu.cn/heibai/
[2] 我在天堂等你 http://www.douban.com/subject/1310322/
[3] 榆树下的欲望 Desire Under the Elms, http://www.douban.com/subject/1297393/
[4] Structure and Interpretation of Computer Programs, http://www.douban.com/subject/1451622/
[5] 暗恋桃花源,富含搞笑因素却又错综复杂值得深深体味的一部话剧,推荐一看 http://www.douban.com/subject/1299889/
[6] 春琴传,较传统的日本爱情故事 http://www.douban.com/subject/1949657/

posted @ 2008-03-31 21:18 ZelluX 阅读(556) | 评论 (1)编辑 收藏

其实理解了 Regular Expression -> NFA -> DFA 这个过程,大致的复杂度确定也不难

发信人: styc (styc), 信区: Algorithm
标  题: Re: 请问一下大家正则表达式的时间复杂度
发信站: 水木社区 (Wed Mar 26 20:37:02 2008), 站内

NFA构造O(n),匹配O(nm)
DFA构造O(2^n),最小化O(kn'logn')(N'=O(2^n)),匹配O(m)
n=regex长度,m=串长,k=字母表大小,n'=原始的dfa大小
大概是这样子吧

posted @ 2008-03-27 00:21 ZelluX 阅读(1667) | 评论 (0)编辑 收藏

试试Google Document


posted @ 2008-03-26 17:01 ZelluX 阅读(402) | 评论 (0)编辑 收藏

翘课去浙大。

posted @ 2008-03-25 21:20 ZelluX 阅读(403) | 评论 (7)编辑 收藏

一个用Lattice Boltzmann Method模拟三维空间中不可压缩流体的程序,示意图见底部。
转这个程序实在是太耗体力了 -_-b

Brook本身的不少缺陷、bug,加上不习惯科学计算程序的代码风格,导致大多数时间都在fix bug。

其中de掉以后最有快感的一个bug:(只能这么形容了 >,<)

每个cell都有一个flag值,尽管类型是double,但是程序中是用一个MAGIC_CAST宏把它当作整型处理的。
初始情况,每个cell的flag都为~f,也就是一个1~28位都是1,29~32位为0的double型浮点。根据IEEE标准,应该是个NaN。
CPU上没有问题,放到GPU上问题就出来了,GPU不支持这种转型操作,在对这个double型进行运算操作的时候,所有结果都会变成NaN。

解决方法:
在把数据传给GPU之前可以先把这些flag值转换为GPU可以操作的double型,最简单的方法就是都先转成int(会有truncating),然后取反,再传给GPU。


what_you_compute.png

posted @ 2008-03-24 21:16 ZelluX 阅读(674) | 评论 (1)编辑 收藏

看来这年头Stream Programming要越来越热哈,恩,期待~~



发信人: freelife (陪你一起老), 信区: METech
标 题: Intel披露CPU/GPU混合芯片细节和时间 zz
发信站: 水木社区 (Tue Mar 18 22:54:49 2008), 站内

估计AMD和NV要急了~~

3月18日消息,英特尔2008年春季开发商论坛会议下个月将在中国上海召开。英特尔在会前的新闻发布会上简单地介绍了英特尔即将推出的图形芯片内核“Larrabee”的状况。

  “Larrabee”与AMD的Radeon和NVIDIA的GeForce处理器有很大区别。“Larrabee”是以中央处理器架构中使用的 x86指令集为基础的。英特尔副总裁Steve Smith强调说,
“Larrabee”不仅是一个图形处理器,而且是能够完成任何流处理任务的多核芯片。

  Smith没有详细说明“Larrabee”芯片中有多少个内核,不过,英特尔2006年披露的早期方案是采用16个内核。每个内核的运行速度都超过2GHz。

  “Larrabee”芯片显然能够升级到数千个内核,共享与英特尔的Tera级计划相同的研究成果。除了x86的方式之外,英特尔将很快发布一个名为 “Advanced Vector
Extensions”(高级矢量扩展)的另一种像SSE扩展那样的扩展集。这些扩展可能把“Larrabee”芯片的x86指令集与Core 2 Duo和Phenom处理器的x86指令区别开来。Smith说,
“Larrabee”将支持OpenGL、 DirectX控件和光跟踪指令。

  英特尔把处理器与图形处理器混合在一起的芯片将有两种版本。这两种版本都采用Nehalem处理器架构。第一种版本代号为“Havendale”,是一种台式电脑芯片,第二种版
本代号为“Auburndale”,是一种笔记本电脑芯片。

  “Auburndale”和“Havendale”这两种芯片将采用两个Nehalem内核和一个图形子系统。两个内核共享4MB二级缓存和一个集成的双通道内存控制器,支持内存配置最高可
达DDR3-1333。

  图形子系统最初是采用英特尔G45集成图形芯片。这表明上述两种芯片都没有强大的图形处理能力,只不过是集成图形芯片的替代品。

  事实上,这两种图形芯片内核都省略了支持DirectX 9和DirectX 10的关键功能。这个基于G45图形芯片的内核最终将被高级的“Larrabee”图形处理器所取代。

  根据英特尔的产品路线图,这种新的处理器预计将在2009年上半年进入市场。这将早于AMD Fusion处理器预计推出的时间。Fusion处理器计划在2009年下半年推出。

  Smith许诺说,“Larrabee”芯片最终推出的时候将比Radeon和GeForce芯片更有竞争力。

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

     摘要: 包括各种paper, survey以及workshop上的讲座等内容  阅读全文

posted @ 2008-03-15 14:46 ZelluX 阅读(1013) | 评论 (6)编辑 收藏

禅 意--之二

当一切都会过去
我知道 我会
慢慢地将你忘记

心上的重担卸落
请你原谅我
生命原是要

不断地受伤和不断地复原
世界仍然是一个
在温柔地等待着我成熟的果园

天这样蓝 树这样绿
生活原来可以
这样的安宁和 美丽

posted @ 2008-02-29 17:50 ZelluX 阅读(354) | 评论 (0)编辑 收藏

本来想看完pagefault的处理的,不过实验室有事情了,只能先把这一半放上来了。

页面的分配与回收使用了一个叫做buddy allocator的机制,kernelnewbies上的解释
The memory allocation scheme used in the kernel. A vector of lists of free pages is kept, ordered by the size of the chunk (in powers of two). When a chunk is allocated, it is removed from the relevant list. When a chunk is freed back to the free pages pool, it is placed in the relevant list, starting from the top. If it is physically contiguous with a present chunk, they are merged and placed in the list above (i.e. where the chunks are twice the size), and this operation percolates up the vector. As regions are merged whenever possible, this design helps to reduce memory fragmentation.

首先在zone_struct{} 中保存了一个free_area_t数组,这个数组记录了各种大小的空闲内存块的信息。
include/linux/mmzone.h:


free_area_struct {}

页面分配时,找到适合大小的free_area_struct{},然后从free_list中找有没有空闲的内存块,如果没有就找更大的free_area_struct{},因为大小都是2^n,很容易把大块内存拆开,一块分配给请求,剩下的保存到对应大小的队列中。
页面回收时主要的问题是如何解决过多的内存碎片。当页面块被释放时,先检查是否有相同大小的相邻空闲块存在,如果有的话就结合起来(递归过程)。

posted @ 2008-02-27 23:29 ZelluX 阅读(671) | 评论 (4)编辑 收藏

几天前的bug了,突然有兴趣想再试试

http://kerneltrap.org/Linux/Patching_CVE-2008-0600_Local_Root_Exploit

posted @ 2008-02-27 23:15 ZelluX 阅读(429) | 评论 (0)编辑 收藏

     摘要: 转载自水木KernelTech版。关于hack系统调用表的一篇文章,里面还涉及了上学期ICS Lab中的二进制代码注入,很好很强大。略作整理(为什么技术博客默认的字体不是等宽的 T.T)=-|================================================-{ www.enye-sec.org }-====|=-[ LKM Rootkits on Linux x86...  阅读全文

posted @ 2008-02-26 19:36 ZelluX 阅读(1278) | 评论 (4)编辑 收藏

     摘要: 越狱第三季最后一幕的歌曲蛮不错的,查到歌名叫Llorando,西班牙中“哭泣”的意思。google过程中还发现了这是某部叫做《穆赫兰道》的电影中的曲子,于是对这部电影也产生了兴趣。  阅读全文

posted @ 2008-02-26 11:56 ZelluX 阅读(458) | 评论 (0)编辑 收藏





Lyric:

posted @ 2008-02-22 13:11 ZelluX 阅读(425) | 评论 (0)编辑 收藏

这学期想上这门课,纯属娱乐,不准备深入。
主要还是考虑到有机会和安然小朋友合作一个大程 ;-)

关于计算机图形学的学习
注意:
本文尽量避免理论化的描述,试图用最通俗的语言介绍一下计算机图形学的学习,以及一些参考书目和网络资源;
本文不涉及对概念的定义,以免陷入学术讨论之中
本文是作者学习计算机图形学的体会,如果有不同的意见,请不要攻击和漫骂

本文合适的题目应当是:白话说学计算机图形学?

1. 引言
什么是计算机图形学? 本文尽量避免给它做严格的定义,但是通常来说,计算机图形学是数字图象处理的逆过程,这只是一个不确切的定义,后面我们会看到,实际上,计算机图形学、数字图象处理和计算机视觉在很多地方的区别不是非常清晰的,很多概念是相通的。
计算机图形学是用计算机来画东西的学科,数字图象处理是把外界获得的图象用计算机进行处理的学科。在法国,图形图象是一门课程。
如何学习计算机图形学呢?除了计算机图形学的基础知识以外,你还需要有以下的知识,你懂的越多,当然做的越好。
* 英语, 你一定要把英语学好,如果你想学习计算机图形学的话,尽量看英文的书籍和资料
* 数学, 计算机图形学里面的数学用的比较多,,我们可以列举一些常用的:
高等数学,数值分析,微分几何,拓扑,概率, 插值理论,(偏)微分方程…
* 物理, 如果你要进行基于物理的建模,一些物理理论是要学习的:
力学(运动学,动力学,流体力学…),光学,有限元…
* 编程语言: C或C++是计算机图形学最通用的‘普通话’,
* 数据结构: 你需要数据结构来描述你的图形对象,除了通用的链表、树等数据结构外,图形学还有自己特殊的数据结构
* 其他类别: 有的时候你需要其他学科的知识,根据你的需要去学习吧

上面列举的不是你必须学习的东西,而是计算机图形学可能会用到的东西,一定要记住,不要指望通过一本教材就学会计算机图形学,它比你想象的要复杂的多。

2. 图形学的问题
每个学科都有自己学科的特定问题,图形学要解决的是如何画出图来,得到需要的效果,当然这是图形学最大的一个问题。

在开始学习计算机图形学的时候,找一本简单的书看,对计算机图形学有个大概的认识,你就可以开始图形学之旅了:

OpenGL Programming Guide: The Official Guide to Learning OpenGL, Version 1.4, Fourth Edition
OpenGL SuperBible (3rd Edition) 

是比较好的学习计算机图形学的入门教材,在练中去学,一开始就去啃

Foley的
Computer Graphics: Principles and Practice, Second Edition in C 
不是好主意,会看的一头雾水,一本什么都讲的书的结果往往是什么都没讲清楚。
当你把OpenGL的基本内容掌握之后,你对图形学就有了大概的了解了

那么下面你可以来学习一下计算机图形学的数据结构和算法,下面的书比较适合
Joseph O'Rourke 的Computational Geometry in C,书里面有C的源代码,讲述简单,清晰,适合程序员学习

总的来说,计算机图形学涉及到2大部分:建模和渲染
2.1建模

你想画一个东西,首先要有它的几何模型,那么这个几何模型从什么地方来呢?下面的书很不错的:
Gerald Farin 的Curves and Surfaces for CAGD: A Practical Guide
这本书就有一点的难度了,呵呵,要努力看啊

这本书算是CAGD (计算机辅助几何设计)的经典图书,CAGD方面的全貌,还有2本很好的讲述曲面的书Bezier和Nurbs的书

Les A. Piegl, Wayne Tiller 的The Nurbs Book 
书里面有NURBS曲线、曲面的程序伪代码,很容易改成C的,书讲的通俗、易懂,但是你要有耐心看的:)

曲线与曲面的数学
这本书是法国人写的中文翻译版,里面还有Bezie本人写的序J,翻译的很不错的,看了你就掌握Bezier曲面技术了


//另外一些你想知道的事情:其他的造型方式-开始
注意:在后面会有这样的章节,标明
//另外一些你想知道的事情:其他的造型方式-开始
//另外一些你想知道的事情:其他的造型方式-结束
里面是我认为的一些高级话题,跳过他们不影响你学习计算机图形学,但是要学好就要注意了,呵呵
还有其他的一些造型技术,比如:
隐式曲面(Implicit Surface)的造型:
就是用函数形式为F( x ,y ,z ) = 0的曲面进行造型,这样的造型技术适合描述动物器官一样的肉乎乎的东西,有2本书推荐大家
Jules Bloomenthal编辑的Introduction to Implicit Surfaces,是一本专著,讲述了Implicit Surface建模型(Modeling),面片化(Polygonization),渲染(Rendering)的问题
Luiz Velho 的 Implicit Objects Computer Graphics 也是一本专著,讲述个更新的一些进展

细分曲面(Subdivision Surface)造型
当用NURBS做造型的时候,曲面拼接是复杂的问题,在动画的时候,可能产生撕裂或者褶皱,Subdivision Surface用来解决这个问题
Joe Warren的Subdivision Methods for Geometric Design: A Constructive Approach就是这方面的专著

从实际物体中得到造型,现在的技术可以用三维扫描仪得到物体表面的点,然后根据这些点把物体的表面计算出来,称为重建(Reconstruction),因为这些技术之在文章中论述,所以我们省略对它的描述

//另外一些你想知道的事情:其他的造型方式-结束


下面还是一个高级话题:)

//另外一些你想知道的事情:光有造型是不够的!-开始
在你的几何模型做好之后,有一些问题需要对这个模型进一步处理,得到适合的模型,当面片很多的时候,或者模型很复杂的时候,需要对几何模型进行简化,才可以满足一些实时绘制的需要,这个技术叫做层次细节(LOD-Level of Detail)。下面的书就是讲这个的:
David Luebke编著的 Level of Detail for 3D Graphics
//另外一些你想知道的事情:光有造型是不够的!-结束

2.2渲染
有了模型,怎么把这个几何模型画出来呢?这个步骤就是渲染啦
如果你看了上面的OpenGL的书,那么你就知道一些渲染的知识了,但是别高兴的太早,OpenGL使用的是局部光照模型(Local Illumination Model),不要被这个词吓住了

Local illumination Model指的是在做渲染的时候只考虑光源和物体之间的相互作用,不考虑物体和物体之间的影响,所以OpenGL不支持阴影,一个(半)透明物体的效果..,这些需要考虑物体之间的影响才可以实现。

//另外一些你想知道的事情:OpenGL可以实现阴影-开始
OpenGL本身不支持,但是通过一些方法可以实现的:),用Google搜索一下
Shadow Volume, OpenGL就找到答案啦
//另外一些你想知道的事情:OpenGL可以实现阴影-结束

Global Illumination Model 这类模型考虑的就比较全啦。现在关于Global Illumination的技术有3大类,具体的技术就不在这里介绍了,如果想了解,可以联系我,大家一起讨论:

光线追踪(Ray Tracing)
关于Ray Tracing的好书有2本:

Andrew Glassner 的An Introduction to Ray tracing 
Glasser是图形界的名人,这本书也是Ray Tracing的经典

R. Keith Morley, Peter Shirley 的Realistic Ray Tracing, Second Edition
这本书第一版是伪代码,第二版是C代码。它的结构不是很清楚,虎头蛇尾的感觉。

辐射度(Radiosity)
关于Radiosity的好书有4本:
Michael Cohen 的Radiosity and Realistic Image Synthesis , Cohen获得SIGGRAPH 1998计算机图形学成就奖,他把Radiosity变成实际可用,现在Cohen在MSR图形::URL::http://research.microsoft.com/~cohen/CohenSmallBW2.jpg

Francois X. Sillion的Radiosity and Global Illumination , Sillion是法国人,他的主要研究方向是Radiosity,这本书写的很不错的,非常清晰

Philip Dutre 的新书Advanced Global Illumination ,看起来还不错,刚拿到手,还没看,呵呵,所以不好评价

Ian Ashdown的Radiosity: A Programmer's Perspective 
有源代码的书啊!! 就凭这个,得给5*****

Photon mapping
这个我也不知道怎么翻译,呵呵。这个技术出现的比较晚,一本好书!
Henrik Wann Jensen的Realistic Image Synthesis Using Photon Mapping
Henrik Wann Jensen是Photon mapping技术的发明者

3.3这些也是图形学吗? 图形和图象的区别模糊了:(
除了上面讲的‘经典’的计算机图形学,还有下面的一些东西,它们也叫计算机图形学吗?是的!!!
3.3.1非真实性图形学(Non-Photorealistic Graphics)
真实性不是计算机图形学的唯一要求,比如:你给我画一个卡通效果的图出来,或者我要用计算机画水彩画怎么办?或者:把图象用文字拼出来怎么做?,解决这些问题要用到非真实性图形学, 好书继续推荐!!!
Bruce Gooch, Amy Ashurst Gooch的 Non-Photorealistic Rendering 

3.3.2体图形学(Volume Graphics)
用CT机做很多切片(比如头骨),那么能通过这些切片得到3D的头骨吗?Volume Graphics就是解决这样的问题的
Min Chen 编著的Volume Graphics 

上面的2个图形学技术就和图象的界限不明显了,实际上他们是图形图象的综合


4 .还有其他的书吗?
还有一些好书啊,呵呵,好书看不完的:),继续放送:

Graphics Gems I ~ V,一大帮子人写的书,包括研究人员,程序员…
有计算机图形学的各种数据结构,编程技巧

Tomas Akenine-Moller 等人编著的Real-Time Rendering (2nd Edition) 
许多最新的计算机图形学进展

David Ebert等人的Texturing & Modeling: A Procedural Approach, Third Edition 
讲述如何通过程序实现纹理、山、地形等图形学要素
F. Kenton Musgrave号称分形狂(Fractal Mania)
Ken Perlin就是Perlin噪声的发明者,用过3d软件的人对Perlin Noise不会陌生的

关于图形学的特定对象,有特定的专题图书,
Evan Pipho Focus On 3D Models,对于图形学的常用模型格式,进行了讲解
Trent Polack的 Focus On 3D Terrain Programming ,讲地形的
Donald H. House 的Cloth Modeling and Animation ,讲布料的
Nik Lever的Real-time 3D Character Animation with Visual C++ ,讲角色动画的
……

还有:)
Richard Parent的 Computer Animation: Algorithms and Techniques,当然是讲动画的啦,呵呵。
David H. Eberly的3D Game Engine Design : A Practical Approach to Real-Time Computer Graphics ,有代码的啊!呵呵:)

最后,没事情的时候,看看下面的书吧
Alan H. Watt, 3D Computer Graphics (3rd Edition) 

James D. Foley等人的 Computer Graphics: Principles and Practice in C (2nd Edition) ,这本圣经没事的时候再看吧,呵呵

累了:( 不说了,上面的书差不多了,还有一些shader的书,我不了解,以后会补上的:)

5.从哪里找到这些书啊?还有什么资源啊?
我保证,上面的书在www.amazon.com 都可以买到:) 别打我

那好,大部分的书在国家图书馆可以复印到,北京的兄弟有福啦,3年前的书借出来复印,1角/页,但是新书要早图书馆里复印,5~6角/页,还是比Amazon便宜啊,呵呵。

不行大家就到国外买,合买吧,还负担的起。
我对DirectX不了解,所以没有涉及关于DirectX的内容:)

posted @ 2008-02-21 15:46 ZelluX 阅读(1949) | 评论 (3)编辑 收藏

     摘要: Unix - semaphore examplehttp://docs.linux.cz/programming/c/unix_examples/semab.htmlCode highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->/**//* semabinit.c ...  阅读全文

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

     摘要: ipc/shm.c: sys_shmat 连接共享内存 Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> ...  阅读全文

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

能用上非盗版的Visual Studio了。。。

https://downloads.channel8.msdn.com/Default.aspx

Welcome to Microsoft DreamSpark

Professional Developer and Designer tools

Visual Studio 2008 Professional EditionExpression Studio
Windows Server 2003 Standard EditionXNA Game Studio
View All Products


DreamSpark is simple, it's all about giving students Microsoft professional-level developer and design tools at no charge so you can chase your dreams and create the next big breakthrough in technology - or just get a head start on your career.

Who can get this right now?
We are kicking this off in 11 countries/regions, giving DreamSpark to millions of students in the United States, the United Kingdom, Canada, China, Germany, France, Finland, Spain, Sweden, Switzerland and Belgium. If you are not residing in one of the countries listed keep checking back, we will be adding more countries throughout the year.

Does that mean that I might not get in?
Possibly, if you are not residing in one of the countries listed, not attending an accredited university or not a member of one of the student organizations that we're connected with. But keep checking back, as we're working on adding more ways to verify your student status all the time.

What do I have to do to get this software? Not much really, just select a product and follow the steps below.

  • Sign In with your Windows Live ID. If you don't have one, go get one here. Pretty basic stuff.

  • Get verified as a student. The system is linked to schools and organizations around the world that can confirm student status. Simply choose your country and school, enter your info and hit submit.

  • Download your products. Now remember these are professional tools. This means they are pretty big files so make sure you have the bandwidth and space to bring them to your machine. We support the latest versions of both Internet Explorer and Firefox for your download.

posted @ 2008-02-20 00:21 ZelluX 阅读(412) | 评论 (0)编辑 收藏

声嘶力竭 俯视 渗透 渺小感
单独放出来听可能就远没那么强烈的效果了

校内下载连接:http://10.132.141.124/zellux/Llorando.mp3
Online:http://www.ttt0.com/play/4/4789/ting130532.htm
Download:http://hiero.ru/david/mp3/Llorando.mp3

Rebekah Del Rio 《Llorando (Crying)》

歌词

英文版

posted @ 2008-02-19 23:32 ZelluX 阅读(618) | 评论 (0)编辑 收藏

昨天硬是没找到正确的sys_call_table的地址,原来我之前在虚拟机上装的ArchLinux是64位的。。
今天在真机上成功地修改了系统调用表。
测试环境:ArchLinux 2.6.24

1. 2.4.20以后的内核出于安全考虑,没有导出sys_call_table符号,所以要先通过System.map找到sys_call_table的地址
$ cat /boot/System.map26 | grep sys_call_table
c0375680 R sys_call_table
另外也可以用nm工具获得vmlinux中的所有符号
$ nm /usr/src/linux-2.6.24-ARCH/vmlinux | grep sys_call_table
结果一样

2. 以添加一个把uid改成root(0)为例,写一个内核模块:
addcall.c

对应的Makefile:

3. 使用insmod addcall.ko载入模块后,用dmesg可以看到the call has been added.
4. 测试程序
test.c

使用gcc -o test test.c编译

5. 运行./test,即可看到类似的成功信息:
Previous uid = 1002
Current uid = 0

6. 卸载模块rmmod addcall,此时再次运行./test就会失败

posted @ 2008-02-19 14:55 ZelluX 阅读(739) | 评论 (0)编辑 收藏

《边干边学》上一个简单的共享内存的例程:
主要的API:
shmget 创建一块共享内存
shmat 将一块已经存在的共享内存映射到一个进程的地址空间
shmdt 取消一个进程的地址空间中的一块共享块的映射
shmctl 管理共享内存,和ioctl的风格很像

每一个新创建的共享都由一个shmid_ds{}表示。struct shmid_ds在linux/shm.h中的定义:

其中存放权限信息的ipc_perm{}的定义为:
include/linux/ipc.h

mode为该共享的内存的读写权限,和chmod的参数有点像。mode低九位定义了访问许可,解释如下:
0400 用户可读  0200用户可写  0040 组成员可读  0020 组成员可写  0004 其他用户可读  0002 其他用户可写
没有执行位 0100 0010 和 0001

 

posted @ 2008-02-19 11:30 ZelluX 阅读(434) | 评论 (0)编辑 收藏

_syscall 宏:
最简单的没有参数的系统调用的实现:
/* XXX - _foo needs to be __foo, while __NR_bar could be _NR_bar. */
#define _syscall0(type,name) \
type name(
void) \
{ \
long __res; \
__asm__ 
volatile ("int $0x80" \
    : 
"=a" (__res) \
    : 
"0" (__NR_##name)); \
__syscall_return(type,__res); \
}

以getuid()为例,_syscall0(int, getuid)展开后就变成
int getuid(void)
{
    
long __res;
    __asm__ 
volatile("int $0x80"
                    :
"=a" (__res)
                    :
"0"  (__NR_getuid));
    __syscall_return(
int, __res);
}

程序把系统调用号__NR_getuid放入eax寄存器,然后调用软中断。
include/asm-i386/hw_irq.h中的定义:
00025   #define SYSCALL_VECTOR  0x80;

arch/i386/kernel/traps.c中把该中断号绑定到system_call函数:
00944   set_system_gate(SYSCALL_VECTOR,&system_call);

system_call函数在arch/i386/kernel/entry.S中:
ENTRY(system_call)
    pushl %eax            # save orig_eax
    SAVE_ALL
    GET_CURRENT(%ebx)
    testb $0x02
,tsk_ptrace(%ebx)    # PT_TRACESYS
    jne tracesys
    cmpl $(NR_syscalls)
,%eax
    jae badsys
    call *SYMBOL_NAME(sys_call_table)(
,%eax,4)
    movl %eax
,EAX(%esp)        # save the return value
ENTRY(ret_from_sys_call)
    cli                # need_resched and signals atomic test
    cmpl $
0,need_resched(%ebx)
    jne reschedule
    cmpl $
0,sigpending(%ebx)
    jne signal_return
restore_all:
    RESTORE_ALL
主要步骤:
1. 保留一份系统调用号的最初拷贝
2. 保存堆栈环境(SAVE_ALL)
3. 得到当前task_struct的地址,保存到ebx中
4. 检查系统调用号
5. 根据%eax调用号计算地址,调用相应函数
6. 在entry.S后面可以看到,
.data
ENTRY(sys_call_table)
    .long SYMBOL_NAME(sys_ni_syscall)    /* 
0  -  old "setup()" system call*/
        
    .long SYMBOL_NAME(sys_getuid16)
    .long SYMBOL_NAME(sys_stime)        /* 
25 */
    .long SYMBOL_NAME(sys_ptrace)
        
sys_call_table + %eax * 4是sys_getuid16地址,kernel/uid16.c中:
asmlinkage long sys_getuid16(void)
{
    
return high2lowuid(current->uid);
}
很简单的处理代码,返回当前进程的uid。这里asmlinkage修饰符表示函数必须从堆栈中,而不是从寄存器中拿参数(防止gcc用寄存器传参优化)。
7. 保存返回值eax到堆栈中的eax
8. RESTORE_ALL

另外这里再提一下GET_CURRENT的实现
#define GET_CURRENT(reg) \
    movl $-
8192, reg; \
    andl %esp, reg
很巧妙的实现,把栈指针与掩码-8192做与操作,末尾13位清零,就是当前的进程的task_struct地址了。


接下来是利用内核模块动态添加一个系统调用的例程,由于2.4.20以后sys_call_table符号不再被导出了,要获得这个地址得手动hack。尚未成功,下次回过头来看看。

posted @ 2008-02-18 14:35 ZelluX 阅读(542) | 评论 (4)编辑 收藏

Mars: A MapReduce Framework on Graphics Processors
by Bingsheng He @ Hong Kong Univ. of Sci. & Tech. 
    Nage K. Govindaraju @ Microsoft Corp.
    Qiong Luo, Tuyong Wang @ Sina Corp.

一些重点摘记:
1. Introduction
Three challenges in implementing the MapReduce framework on the GPU:
First, the synchronization overhead in the run-time system of the framework must be low.
Second, a fine-grained load balancing scheme is required.
Third, the core tasks of MapReduce, including string processing, file manipulation and concurrent reads and writes, are unconventional to GPUs and must be handled efficiently.
Each thread is responsible for a Map or a Reduce task with a small number of key/value pairs as input.
Performance improvement: 1.5-16 times

2. Priliminary and Related Work
2.1. Graphics Processors
It is desirable to schedule the tasks between the CPU and the GPU to fully exploit their computation power.
Given a kernel program, the occupancy of the GPU is the ratio of active schedule units to the maximum number of schedule units supported on the GPU.
The GPU has a hardware feature called coalesced access to exploit the spatial locality of memory accesses among threads.

2.2. GPGPU
2.3. MapReduce
Map: (k1, v1) -> (k2, v2)*
Reduce: (k2, v2*) -> v3*

3. Design and Immplementation
3.1. Design Goals
3.2. System Workflow and Configuration
3.3. APIs
3.4. Implementation Techniques
Based on this compilation information and the total computation resources on the GPU, we set the number of threads per thread group and the number of thread groups to achieve a high occupancy at run time.

4. Evaluation
4.1. Experimental Setup


posted @ 2008-02-15 19:51 ZelluX 阅读(538) | 评论 (0)编辑 收藏

作者是豆瓣上的草薰风暖
http://www.douban.com/people/1299430/

  长大以后,不会仅仅因为文笔而喜欢一个作家,也不会因为情节曲折而喜欢一部书。有一种读者和作者之间的传神,我领会为“心跳的合拍”,从字里行间,从遣词造句,从审美风格,从情感表达,从思维方式……我深信,如果喜欢一本书,必然和这本书的作者在性情上有某种程度的相似或者共鸣。
   
  我不喜欢杜拉斯的语言,只记得她说过的一种偏爱,她说她喜欢只写过一部作品的作家。我的体会是,我只喜欢至少有过一部作品使我感到“心跳的合拍”的作家。比如陈丹燕,那个被朋友称之为面目阴暗的女子,却因为她的一部《女中学生之死》令我坚持喜欢,尽管她后来的上海系列再不能打动我。(可能今天的我再去读《女》就不会那么感慨,可能。)
   
  相对于欧美小说的叙述笔调,我更能体会和揣摩部分日本小说里的情欲,不是说前者不能明白,只是对后者的玩味更得心应手。比如村上春树,尽管他的作品除了幽微蓝调、内心独白的风格之外,也透着阴郁潮湿的气味,我想,恐怕算得上微微一点病态而不至于变态的美感,像爵士乐,村上春树的抒情深沉而敏感。
   
  是的,安静下来,你能够听到心脏的声音。听到一个沉静又自命不凡的男子从12岁到37岁的心脏的声音。手边的这本《国境以南,太阳以西》是很早就借的,在这样热的夏天读起来却格外喜欢。
   
  这部小说不妨说是一个人的成长史,而里面的每个人,初君,岛本,泉,有纪子,也都不能说不是可爱的。
   
  【岛本】
   
  两个12岁的被群体隔膜的独生子女成为好朋友,那种心灵共振的好朋友。恐怕谁都会觉得那样一种场景无限美好,两个孩子坐在一起一下午,听李斯特的钢琴,说话。我宁可把他们的交谈称之为说话,说心里想的话,说思考过的话,说简单又蕴藏真切感受的话。两个相似的独生子女,在一起说话,在一起听话,宁静的,专注的,不被周围的人打扰,陪伴彼此安静的时间和声音,缓缓的,淡淡的,一点一点的,就像异常漂亮但腿有点跛的岛本走路的情状,耐心而从容。
   
  【初君】
   
  不用说,若有细心人细心观察,应该不难看出初君是免不了有其自身问题的,然而说到底,世界上又哪里存在没有其自身问题的少年呢?初君是一个异常孤独而傲慢的少年,需要和同伴配合的体育项目他无论如何喜欢不来,同他人抢分的竞赛也不屑一顾。但也不是彻头彻尾的孤独。尽管为数不多,还是交了几个要好的朋友。假如身边没有那样的朋友,一个人在通过二十岁以前那段不安稳岁月的过程中难免受到更深的伤害。
   
  初君的第一个女朋友泉指出他是一个独生子,并非说他是被宠坏了的孩子,而是指他有孤独倾向的个性,很难走出一个人的世界。从某种意义上,岛本为了保护自己会使得自己微笑,而初君连随和的微笑都觉得累赘。
   
  恐怕我们每个人多少都会认同独生子女有着强烈的自我意识,并略感悲哀我们难以向别人敞开心扉。假如不是通过书,我们不可能分享初君那样一个独生子从12岁到37岁内心隐秘的情感和意象,这也是我曾经喜欢陈丹燕《一个女孩》的原因。虽然都不过是孩子,也未尝不具备某种“思想家”和“艺术家”的潜质。而通过他们的内心独白,你大概会觉得自己不孤单,甚至连那些白日梦都让你觉得可亲和会心,后来明白,一个孩子苦心经营的白日梦,不外乎是自我中心的或者连接着某个重要的人,不外乎是自己变得不同寻常出色厉害或者沉溺于悲伤惨淡的情境情结中……我不知道有多少人是如此,或者说生活太吵闹而这些人又隐匿在自我里,所以彼此看不见。 但我想总是有一部分人如此。
   
  国境以南,太阳以西,看见,人生的样子。时光,是很冷的东西。一个人,一个个人,从遇事不知所措的懦弱的少年走到平和的微笑的知足惜福的也带一点伤感的中年,尽管途经波涛暗涌,最后仍只剩下沙漠。岁月这东西是要把人变成各种样子的,有纪子其后遇上了初君,而泉大概谁也没有遇上。而无论初君说什么,岛本都浮现出将所有感情吞噬一尽的迷人微笑看着他,就好像在说“没关系的,这样可以的。”“活法林林总总,死法种种样样,都没什么大不了的。剩下来的唯独沙漠,真正活着的只有沙漠。”
   
  小说里几乎每个人物的性格都透着一点清冷,读起来却有一股温暖的温柔的温情的东西在。也许人是难以活得过分自我的,即使有心也不能。岛本的幽微美丽荡漾着死的气息,美人对男人有安抚的作用,初君也期待“专为我准备”的一个女子,可惜时间不能挽回,她所要求的全部非死不能成全。有纪子对初君并非完完全全,而他们最终在沙漠里好端端活下去。既非生气,又不悲伤,有纪子仅仅是将事实作为事实说出口来。“你的确是个自私自利的人、不地道的人……但这些都不是问题。你肯定什么都不明白。”有纪子是懂得初君的。
   
  (这不见得是一部多么精彩的书,不过可以从中窥见几许人性自然,但很令人不爽的一点是,最终作者也不肯告诉我们岛本过去究竟有着怎样的经历现在有着怎样的身份!!他不想说就不要卖关子!!!)
   
  人和人是不同的,有些人是写字的,有些人是看字的,事实上这两种人又有相通的潜质,否则不会懂得。世间,一直有像村上春树,像普鲁斯特,像卡夫卡那样曲径通幽的灵魂,因而也就一直有读他们灵魂的人,虽然,艺术气质永不是生存的主流。

posted @ 2008-02-14 16:26 ZelluX 阅读(409) | 评论 (1)编辑 收藏

不想一天到晚呆坐电脑前,灌灌水,聊聊天

还是读点村上的

《挪威的森林》估计是因为太喜欢,带到学校里了

那就先重读《国境以南,太阳以西》

当时应该是一行推荐我看安妮的书,然后我看到99的书单上安妮推荐了这本书,于是我就没买安妮的,买了这本 =_=

从此就迷上村上的小说了。尽管这本和《挪威的森林》与村上其他作品的风格还是有一定出入的。

posted @ 2008-02-11 23:47 ZelluX 阅读(347) | 评论 (0)编辑 收藏

发现自己对Python的语法的兴趣远比对使用Python本身的兴趣浓厚得多
为什么水木上的帖子每行末尾都是用空格填充的,每次转载还要先放到vim里面处理一下。。。

by ilovecpp

让Python支持true closure有多难?
只需修改11行代码。

如果你不知道什么是true closure,这里简单解释一下。Python支持lexicalscope:

>>> def add_n(n):
...     def f(m):
...             return n+m
...     return f
>>> add_2 = add_n(2)
>>> add_2(0)
2
>>> add_2(2)
4

f引用了外层函数add_n的局部变量n。有趣的是,f引用n的时候,add_n已经结束,n似乎不存在了。f所以能正常工作,是因为创建它的时候就把n作为f的上下文(closure)保存了下来,并不随add_n结束而消失。
但是,Python的lexical scope和Scheme/Smalltalk/Ruby还有一点区别:不能在内层函数中rebind外层函数的局部变量。
>>> def f():
...     def g():
...             n=1
...     n=0
...     g()
...     return n
...
>>> f()
0

这是因为Python没有变量声明, n=1 自动使n成为g的局部变量,也就无法rebind f中的n了。可以说Python的closure是只读的。如果你听到有人说"Python不支持true closure",就是指这个。其实,Python VM能够支持true closure。因为,Python支持内层函数看见外层函数的name rebinding:

>>> def f():
...     def g():
...             yield n
...             yield n
...     x = g()
...     n = 0
...     print x.next()
...     n = 1
...     print x.next()
...
>>> f()
0
1

对于Python的closure实现(flat closure),"外层函数rebind name"和"内层函数rebind name"其实没有区别。我们知道用global关键字可以rebind module scopename。如果增加一个类似的outer关键字,就可以支持rebind outer scope name。真正的限制是Guido不愿意为支持true closure增加关键字。

也可以不增加关键字,而是把global n的语义改为"如果outer scope定义了n,rebind outer scope n;否则rebind module scope n"。简单起见,我没有修改Python的built-in compiler,而是修改了compiler module(用Python实现的Python compiler)。你只需把下面这个patch打到compiler/symbols.py(Python 2.5.1)就可以体验true closure了:

C:\Python\Lib>diff -u compiler/symbols.py.orig compiler/symbols.py
--- compiler/symbols.py.orig    Thu Aug 17 10:28:56 2006
+++ compiler/symbols.py Mon Feb 11 12:03:01 2008
@@ -21,6 +21,7 @@
         self.params = {}
         self.frees = {}
         self.cells = {}
+        self.outers = {}
         self.children = []
         # nested is true if the class could contain free variables,
         # i.e. if it is nested within another function.
@@ -54,8 +55,10 @@
         if self.params.has_key(name):
             raise SyntaxError, "%s in %s is global and parameter" % \
                   (name, self.name)
-        self.globals[name] = 1
-        self.module.add_def(name)
+        if self.nested:
+            self.outers[name] = 1
+        else:
+            self.globals[name] = 1

     def add_param(self, name):
         name = self.mangle(name)
@@ -90,6 +93,8 @@
         """
         if self.globals.has_key(name):
             return SC_GLOBAL
+        if self.outers.has_key(name):
+            return SC_FREE
         if self.cells.has_key(name):
             return SC_CELL
         if self.defs.has_key(name):
@@ -107,6 +112,7 @@
             return ()
         free = {}
         free.update(self.frees)
+        free.update(self.outers)
         for name in self.uses.keys():
             if not (self.defs.has_key(name) or
                     self.globals.has_key(name)):
@@ -134,6 +140,9 @@
         free.
         """
         self.globals[name] = 1
+        if self.outers.has_key(name):
+            self.module.add_def(name)
+            del self.outers[name]
         if self.frees.has_key(name):
             del self.frees[name]
         for child in self.children:

因为我们没有修改built-in compiler,所以程序要写在字符串里,用compiler.compile编译,用exec执行:
>>> from compiler import compile
>>> s = '''
... def counter():
...     n = 0
...     def inc():
...             global n
...             n += 1
...     def dec():
...             global n
...             n -= 1
...     def get():
...             return n
...     return inc, dec, get
... '''
>>> exec compile(s, '', 'exec')
>>> inc, dec, get = counter()
>>> get()
0
>>> inc()
>>> get()
1
>>> dec()
>>> get()
0

后记

1 搞这个东西的缘起是Selfless Python(http://www.voidspace.org.uk/python/weblog/arch_d7_2006_12_16.shtml#e583)。很有趣的bytecode hack,给一个类中的所有函数补上self参数。既然PythonVM支持true closure,能不能用类似的手法让Python支持true closure呢?不过很快就明白这个在bytecode层面不好弄,还是得修改编译器。不过改起来还真是出乎意料地简单。

2 Guido早已明确表示不能改变global的语义(因为会影响现有代码),所以这个只是玩玩而已,不用指望成为现实。当然你可以只发布bytecode,大概还能把反编译器搞挂掉。:-)
3 我可以理解Guido的决定。除非你之前一直在用Scheme,否则我觉得像上面counter例子那种一组共享状态的函数还是写成class为好,至少共享状态是什么一目了然。Lexical scope太implicit,用在开头add_n那种地方挺方便,再复杂就不好了。

又:很抱歉"幕后的故事"拖了这么久。写起来才发现自己还是不懂descriptor。
不过我肯定不会让它烂尾的。

 

posted @ 2008-02-11 16:18 ZelluX 阅读(793) | 评论 (0)编辑 收藏

zz from 游侠
http://game.ali213.net/viewthread.php?tid=1874905

转自巴哈姆特,原帖主clover0425

原帖地址
http://forum.gamer.com.tw/C.php?bsn=01223&snA=9101


==============(等级~等级)============================

怪物(分类)等级+怪物(分类)等级=怪物(分类)等级

合成结果如下:

==============(LV.1~LV.10)============================

青蛙(生物)LV.1+蟾蜍(生物)LV.1=蟾蜍(生物)LV.1
青蛙(生物)LV.1+刺胡蜂(生物)LV.3=蟾蜍(生物)LV.1
青蛙(生物)LV.1+通臂猖猿(精怪)LV.4=青蛙(生物)LV.1

草妖(精怪)LV.1+草妖(精怪)LV.1=泥童(活尸)LV.2

泥童(活尸)LV.2 +草妖(精怪)LV.1=青蛙(生物)LV.1
泥童(活尸)LV.2 +泥童(活尸)LV.2=草妖(精怪)LV.1

蟾蜍(生物)LV.1+蟾蜍(生物)LV.1=蟾蜍(生物)LV.1
蟾蜍(生物)LV.1+草妖(精怪)LV.1=蟾蜍(生物)LV.1
蟾蜍(生物)LV.1+刺胡蜂(生物)LV.3=蟾蜍(生物)LV.1
蟾蜍(生物)LV.1+通臂猖猿(精怪)LV.4=蟾蜍(生物)LV.1
蟾蜍(生物)LV.1+长颈鬼(活尸)LV.5=毒蛇(生物)LV.2
★备注:魏国士兵无法收服,所以无法炼化。

蝙蝠(生物) LV.1+蝙蝠(生物) LV.1=蟾蜍(生物)LV.1
蝙蝠(生物) LV.1+蟾蜍(生物)LV.1=蟾蜍(生物)LV.1
蝙蝠(生物) LV.1+毒蛇(生物)LV.2=蟾蜍(生物)LV.1
蝙蝠(生物) LV.1+刺胡蜂(生物)LV.3=蟾蜍(生物)LV.1
蝙蝠(生物) LV.1+通臂猖猿(精怪)LV.4=蟾蜍(生物)LV.1

刺胡蜂(生物)LV.3+刺胡蜂(生物)LV.3=魏国亡兵(鬼魂)LV.7
刺胡蜂(生物)LV.3+通臂猖猿(精怪)LV.4=魏国亡兵(鬼魂)LV.7

毒蛇(生物)LV.2+蟾蜍(生物)LV.1=蟾蜍(生物)LV.1
毒蛇(生物)LV.2+毒蛇(生物)LV.2=蟾蜍(生物)LV.1
毒蛇(生物)LV.2+刺胡蜂(生物)LV.3=蟾蜍(生物)LV.1
毒蛇(生物)LV.2+通臂猖猿(精怪)LV.4=蟾蜍(生物)LV.1

蜘蛛(生物) LV.2+蝙蝠(生物) LV.1=蟾蜍(生物)LV.1
蜘蛛(生物) LV.2+蜘蛛(生物) LV.2=魏国亡兵(鬼魂)LV.7
蜘蛛(生物) LV.2+通臂猖猿(精怪)LV.4=魏国亡兵(鬼魂)LV.7
蜘蛛(生物) LV.2+魏国亡兵(鬼魂)LV.7=青蛙(生物)LV.1

狐精(妖灵) LV.2+狐精(妖灵)LV.2=蟾蜍(生物)LV.1
狐精(妖灵) LV.2+魏国亡兵(鬼魂)LV.7=青蛙(生物)LV.1

通臂猖猿(精怪)LV.4+泥童(生物)LV.2 =长颈鬼(活尸)LV.5
通臂猖猿(精怪)LV.4+通臂猖猿(精怪)LV.4=魏国亡兵(鬼魂)LV.7

魏国亡兵(鬼魂)LV.7+毒蛇(生物)LV.2=青蛙(生物)LV.1
魏国亡兵(鬼魂)LV.7+通臂猖猿(精怪)LV.4=青蛙(生物)LV.1
魏国亡兵(鬼魂)LV.7+魏国亡兵(鬼魂)LV.7=角鹰(生物)LV.10

芙蕖精(仙灵)LV.10+污泥怪(活尸)LV.25=玄龟(神兽)LV.39
芙蕖精(仙灵)LV.10+雨女(妖灵)LV.11=颙(妖灵)LV.21
角鹰(生物)LV.10+角鹰(生物)LV.10=等活狱兵(?)LV.?

獍(魔兽)LV.10+碧鬼魔(魔神)LV.22=娥仙(仙灵)LV.17

==============(LV.11~LV.20)============================

雨女(妖灵)LV.11+雨女(妖灵)LV.11=赑屃(神兽)LV.30

九曜神兵(天神)LV.13+角鹰(生物)LV.10=赑屃(神兽)LV.30

娥仙(仙灵)LV.17+仙芝(仙灵)LV.14=蛟蝮魔(魔兽)LV.24

髑髅(活尸)LV.18+仙芝(仙灵)LV.14=玄龟(神兽)LV.39

无头鬼(鬼魂)LV.19+鬼瞳(鬼魂)LV.22=马面(魔神)LV.42

==============(LV.21~LV.30)============================

颙(妖灵)LV.21+獍(魔兽)LV.10=牛头(魔神)LV.42
颙(妖灵)LV.21+白玉琼浆(?)LV.30=赤焰仙子(仙灵)LV.31
颙(妖灵)LV.21+鹿皮靴(?)LV.14=马面(魔神)LV.42

碧鬼魔(魔神)LV.22+罴(生物)LV.14=污泥怪(活尸)LV.25
碧鬼魔(魔神)LV.22+碧鬼魔(魔神)LV.22=希夷(?)LV.28

竦斯(妖灵)LV.23+蛟蝮魔(魔兽)LV.24=马面(?)LV.42

蛟蝮魔(魔兽)LV.24+药草(?)LV.1=牛头(魔神)LV.42
博木妖(精怪)LV.25+博木妖(精怪)LV.25=阴颅(活尸)LV.36

锁爷(鬼魂)LV.26+锁爷(鬼魂)LV.26=黑血巨蟒(生物)LV.36
巨怪(魔兽)LV.26+蛟蝮魔(魔兽)LV.24=丹顶(仙灵)Lv.32

化虎(?)LV.27+武虎虎王(?)LV.35=夜叉(?)LV.44

魔剑客(妖灵)LV.29+化虎(妖灵)LV.27=英招(神兽)LV.42
魔剑客(妖灵)LV.29+五方天兵(天神)LV.18=金线草妖(精怪)LV.30
魔剑客(妖灵)LV.29+苞娘(精怪)lv.30=灵目鬼(鬼魂)lv.35
魔剑客(妖灵)LV.29+食人妖花(精怪)lv.23=怨魂(鬼魂)lv.29
魔剑客(妖灵)LV.29+赤焰仙子(仙灵)lv.31=山神(仙灵)lv.33
魔剑客(妖灵)LV.29+蝶仙(仙灵)LV.32=晶硥(妖灵)LV.32

==============(LV.31~LV.40)============================

赤焰仙子(仙灵)LV.31+赤焰仙子(仙灵)LV.31=虣虎王(?)LV.35
赤焰仙子(仙灵)LV.31+硥(妖灵)LV.25=蝶仙(仙灵)LV.32

蝶仙(仙灵)LV.32+怨魂(鬼魂)LV.27=鬼菇(精怪)LV..38
蝶仙(仙灵)LV.32+鬼朣(鬼魂)LV..22=寒玉藤(精怪)LV..32

阴颅(活尸)LV.36+黑血巨莽(生物)LV.36)=殍髅(活尸LV.40

巨灵神将(天神)LV.38+巨?怪(魔兽)LV.20=青尾凤友(生物)LV.50
巨灵神将(天神)LV.38+苞娘(精怪)LV.30=女英(仙灵)LV.35
巨灵神将(天神)LV.38+金线草妖(精怪)LV.30=娥皇(仙灵)LV.35
巨灵神将(天神)LV.38+食人妖花(精怪)LV.23=镇山元帅(仙灵)LV.34

九天玄女(仙灵)LV.38+娥皇(仙灵)LV.35=炎罴兽(魔兽)LV.40
九天玄女(仙灵)LV.38+山神(仙灵)LV.35=天火假猿(魔兽)LV.38
九天玄女(仙灵)LV.38+食火蛛(妖灵)LV.36=朱[舌鸟](仙灵)LV.36
黑绳狱卒(鬼魂)LV.38+苞娘(精怪)LV.30=枷爷(鬼魂)LV.40

鴸(妖灵)LV.40+苞娘(精怪)LV.30=冥府鬼焰(鬼魂LV.40
鴸(妖灵)LV.40+金线草妖(精怪)LV.30=吴兵亡灵(鬼魂)LV.42
鴸(妖灵)LV.40+山神(仙灵)LV.35=朱[舌鸟](仙灵)LV.30

==============(LV.41~LV.50)============================

牛头(魔神)LV.42+镇山元帅(?)LV.?=阿鼻狱使(鬼魂)LV.49

英昭(神兽)LV.42+蛟腹魔(魔兽)LV.24=玄龟(神兽)LV.39

夜叉(魔神)LV.44+蝶仙(仙灵)LV.32=阿鼻狱使(鬼魂)LV.49
夜叉(魔神)LV.44+玄龟(天神)LV.39=战死尸鬼(活尸)LV.45
夜叉(魔神)LV.44+枷爷(鬼魂)LV.40=赤滕(妖灵)LV.47
夜叉(魔神)LV.44+吴兵亡灵(鬼魂)LV.42=鬼魈(妖灵)LV.48
夜叉(魔神)LV.44+殍髅(活尸)LV.42=蝮魔王(魔兽)LV.44

诸怀(神兽)LV.45+蝮魔王(魔兽)LV.44=白虎(神兽)LV.52
诸怀(神兽)LV.45+独目鬼(魔兽)LV.46=青龙(神兽)LV.52
诸怀(神兽)LV.45+吴兵亡灵(鬼魂)LV.42=上元夫人(仙灵)LV.52
诸怀(神兽)LV.45+炎罴兽(魔兽)LV.40=开明兽(仙灵)LV.52

雷电灵霸(魔兽)LV.50+开明兽(神兽)LV.52=麒麟(神兽)LV.55
雷电灵霸(魔兽)LV.50+诛怀(神兽)LV.45=黑龙(神兽)LV.55
雷电灵霸(魔兽)LV.50+黑龙(神兽)LV.55)=兕(魔兽)LV.58

==============(LV.51~LV.60)============================

青龙(神兽)LV.52+黑龙(神兽)LV.55=奇[仓鸟](妖灵)LV.56
青龙(神兽)LV.52+蛟腹魔(魔兽)LV.24=希有(神兽)LV.49
青龙(神兽)LV.52+鬼火(鬼魂)LV.20=朱舌鸟(仙灵)LV.36

上元夫人(仙灵)LV.52+骑督亡灵(鬼魂)LV.47=鬼蔷(精怪)LV.56

阿修罗(魔神)LV.55+夜叉(魔神)LV.44=托塔天王(天神)LV.58

麒麟(神兽)LV.55+蛟腹魔(魔兽)LV.24=哮天犬(神兽)LV.50
云生兽(神兽)LV.55+殍髅(活尸)LV.40=焰尾朱鸟(生物)LV.54
云生兽(神兽)LV.55+蛊使(鬼魂)LV.45=镇元大仙(仙灵)LV.52
云生兽(神兽)LV.55+炎罴兽(魔兽)LV.40=黑龙(神兽)LV.55
云生兽(神兽)LV.55+蝮魔王(魔兽)LV.44=犎魔元帅(魔兽)LV.55
云生兽(神兽)LV.55+天火假元(魔兽)LV.38=雷电灵霸(魔兽)LV.50
云生兽(神兽)LV.55+兕(魔兽)LV.58=龙王(神兽)LV.62

托塔天王(天神)LV.58+阿修罗(魔神)LV.52=菩提祖师(天神)LV.62
托塔天王(天神)LV.58+焰尾朱鸟(生物)LV.54)=云生兽(神兽)LV.55

兕(魔兽)LV.58+开明兽(神兽)LV.52=凤凰(神兽)LV.60

posted @ 2008-02-11 12:24 ZelluX 阅读(1836) | 评论 (0)编辑 收藏

zz from 游侠
http://game1.ali213.net/thread-1874977-1-1.html

转自巴哈姆特,原帖主fitbtm6810,修正部分错字加重新排版。

原帖地址
http://forum.gamer.com.tw/C.php?bsn=01223&snA=9714
http://forum.gamer.com.tw/C.php?bsn=01223&snA=9751

==========================================================

武器:

炼化规则:
神兽+饰品 & 鬼魂+饰品 & 活尸+防具 & 奇物+防具 & 饰品+饰品 & 武器+防具 (出现武器或防具)

剑:
昆吾剑15级=泥童+沉胜衣
雁翎刀20级=月隐服+振心散 & 赑屃+金牛角
青釭剑26级=无法利用炼化出现
龙鳞32级=玄雀+沉胜衣 & 金刚月牙+沉胜衣
纯钧剑40级=无法利用炼化出现
百辟48级=青龙+云隐戒指 & 神臂弓+九霄连摆甲
封魔刀55级=纯钩剑+银狐裘 & 百辟+神影游龙服

刃:
五毒刀13级=振心散+诫袍
炎突18级=铁甲+振心散
星驰24级=无法利用炼化出现
玄雀30级=雁翎刀+水镜银衫 & 火神弓+须弥琉璃甲
九绝38级=无法利用炼化出现
鬼眼46级=无法利用炼化出现
翔风53级=百辟+九霄连摆甲 & 百辟+赤焰霓裳

戟:
玄铁枪16级=无法利用炼化出现
透甲枪21级=樊木+铁甲 & 赤焰连环甲+抑神粉
蛇矛27级=无法利用炼化出现
铁戟33级=龙鳞+天星甲 & 玄龟+明日香包
百胜戟41级=玄雀+九霄连摆甲 & 金星白玉锤+水镜银衫
竞月勾49级=青龙+蓝玉戒指 & 青龙+琥珀戒指 & 九绝+神影游龙服
逐日戟56级=护法神杖+玄溟战甲 & 振心粉+水镜银衫
镇魂神枪60级=封魔刀+银狐裘

杖:
夜叉杵13级=等活狱兵+金牛角
樊木18级=无法利用炼化出现
天师诚24级=无法利用炼化出现
金刚月牙30级=污泥怪+沉胜衣 & 火神弓+沉胜衣
冲霄神杖38级=无法利用炼化出现
太虚神杖46级=百战戟+水镜银衫 & 九霄连摆甲+龙鳞
无极53级=百战戟+御灵圣环铠
护法神杖56级=封魔刀+神影游龙服 & 翔风+银狐裘

弓:
桑弧弓14级=无法利用炼化出现
火神弓19级=等活狱兵+神草结 & 振心散+天羽彩衣
伏魔弓25级=无法利用炼化出现
逐日弓31级=蓝玉戒指+鬼瞳 & 透甲枪+沉胜衣
神臂弓39级=金星白玉锤+天星甲 & 铁戟+须弥琉璃甲
刚侯弓47级=金刚月牙+神影游龙服 & 太虚神杖+水镜银衫

斧:
开明斧19级=无法利用炼化出现
诛剌25级=沉胜衣+抑神粉
金星白玉锤39级=逐日弓+水镜银衫
狂章47级=无法利用炼化出现
雷公震54级=无法利用炼化出现

==========================================================

防具:

炼化规则:
天神+武器 & 精怪+灵药 & 生物+灵药 & 武器+足具 & 灵药+灵药 & 武器+防具 (出现武器或防具)

武士:
铣甲17级=药草+返魂香
赤焰连环甲21级=跌打伤药+返魂香
天星甲27级=白玉琼浆+返魂香 & 雁翎刀+沉胜衣
须弥琉璃甲33级=逐日弓+沉胜衣 & 金刚月牙+天星甲
九霄连摆甲41级=龙鳞+赤焰霓裳 & 神臂弓+水镜银衫
御灵圣环铠49级=太虚神杖+九霄连摆甲 & 龙鳞+银狐裘
玄冥战甲56级=无极+神影游龙服 & 翔风+御灵圣环铠

法师:
天羽彩衣15级=解毒草+返魂香
月隐服20级=消疲丸+返魂香
沉胜衣26级=活络散(灵仙酒)+返魂香 & 返魂香+返魂香
水镜银衫32级=雁翎刀+须弥琉璃甲 & 白玉琼浆+白玉琼浆
赤焰霓裳40级=龙鳞+水镜银衫 & 铁戟+水镜银衫
神影游龙服48级=百胜戟+九霄连摆甲 & 百胜戟+赤焰霓裳
银狐裘55级=神影游龙服+太虚神杖 & 百辟+攀云踏风鞋

==========================================================

足具:

炼化规则:
神兽+防具 & 饰品+防具 & 鬼魂+防具 & 活尸+奇物 & 奇物+奇物 & 奇物+足具 (出现足具或奇物)

鹿皮靴14级=铁甲+金牛角
驰云履19级=振心散+抑神粉
鬼爪履25级=沉胜衣+神草结 & 沉胜衣+汉兵亡灵
龙麟百足靴31级=赑屃+天星甲 & 水镜银衫+汉兵亡灵
追风流光鞜39级=须弥琉璃甲+赑屃 & 九霄连摆甲+蓝玉戒指
攀云踏风鞋47级=玄龟+九霄连摆甲 & 玄龟+赤焰霓裳
疾风鞮54级=诸怀+神影游龙服 & 云生兽+40级以上防具

==========================================================

饰品:

炼化规则:
天神+灵药 & 生物+足具 & 精怪+足具 & 武器+武器 & 灵药+足具

金牛角03级=草药+布鞋
防御手环03级=短刃+短刃
防毒香包08级=跌打药伤+布鞋
驱邪香包08级=消疲丸+布鞋
天仙符10级=返魂香+布鞋
凰羽10级=活络散+布鞋
醒脑香包12级=九曜神兵+活络散
神草结15级=五方神兵+返魂香
明目香包15级=五方神兵+活络散
照妖镜18级=龙鳞+雁翎刀
芭蕉扇18级=金刚月牙+雁翎刀
太极护符18级=龙鳞+金星白玉锤
镇心炼18级=龙鳞+龙鳞
万宝节环20级=
护身令牌20级=
云隐戒指22级=金星白玉锤+金星白玉锤
玄冥戒25级=
龟蛇旗25级=
蓝玉戒指25级=
琥珀戒指25级=
天女丝巾28级=
北斗挂日链30级=
白玉龙纹佩35级=镇魂神枪+护法神杖

==========================================================

灵药:

炼化原则:
神兽+奇物 & 活尸+饰品 & 鬼魂+奇物 & 防具+防具 & 奇物+饰品

恢复生命:
跌打伤药15级=赤焰连环甲+铁甲
金创药24级=抑神粉+玄龟
天创药32级=九霄连摆甲+九霄连摆甲(须弥琉璃甲)
地脉血泉08级=赤焰连环甲+藤甲
不死泉水18级=赑屃+振心散
破元仙露26级=须弥琉璃甲+天星甲(水镜银衫)

恢复体力:
消疲丸10级=镇心炼+长颈鬼
活络散20级=沉胜衣+沉胜衣
活骨灵药28级=九霄连摆甲+天星甲
灵山雪参35级=

恢复灵力:
金蜂蜜10级=天羽彩衣+天羽彩衣
灵仙酒20级=天星甲+天星甲
蟠桃28级=水镜银衫+赤焰连环甲
归元花露水35级=赤焰霓裳+赤焰霓裳

恢复生命&体力&灵力:
九命猫脑浆40级=

状态恢复:
返思铃01级=藤甲+护身短甲
绝情膏12级=铁甲+铁甲
润喉丸06级=护身短甲+护身短甲
龙爪花15级=赤焰连环甲+赤焰连环甲
目药粉06级=诫袍+诫袍
溶石魔羽15级=天星甲+铁甲
返魂香25级=九霄连摆甲+赤焰连环甲
白玉琼浆30级=
轮回盘40级=

==========================================================

奇物:

炼化原则:
天神+足具 & 武器+生物 & 足具+足具 & 武器+精怪 & 武器+灵药 & 足具+奇物

土地神符8级=草药+铜剑
诱敌女娃8级=跌打伤药+铜剑
振心散15级=消疲丸+铜剑
抑神粉15级=活络散(返魂香)+昆吾剑
神秘果60级=无法炼化
雪肌冰饱60级=无法炼化

posted @ 2008-02-11 12:23 ZelluX 阅读(3149) | 评论 (0)编辑 收藏

新绝代双骄的插曲,当时蛮有感觉的,突然想起来我还没听过完整的。
http://www.whjsr.com/dc.mp3

我的双脚陷进爱中
等了已好久好久
你的手从指间经过
只能碰却不能握
心里好多话对你说
你却看着我沉默
这样的相爱那儿有错
连云也难说服我
我不是个稻草人
不能动不能说
已把爱紧紧绑心中
我不是个稻草人
没人爱没人懂
再难再疯我要结果
我不是个稻草人
看天亮看日落
就等你给我一双手
我不是个稻草人
不做梦不还手
别用泪水逼我放手

就算全界都笑我
爱个人谁敢说错
就算全世界都怪我
我只要你跟我走

posted @ 2008-02-10 21:32 ZelluX 阅读(337) | 评论 (1)编辑 收藏

借用里面的话来说,就是
连年动众,未能成功——盖应变、将略,非其所长!

posted @ 2008-02-10 21:28 ZelluX 阅读(1624) | 评论 (3)编辑 收藏

     摘要: /proc文件系统不是直接从内核的存储区中读写数据,二是通过回调函数实现文件读写的。struct proc_dir_entry有一对读写操作函数指针read_proc_t, write_proc_t。 一个编写内核模块操作proc文件系统的例子,书上的源程序是在2.4.18下跑起来的,改了三个地方在2.6.23下成功运行。当然Makefile也按照2.6中make modules的方式写了。 ...  阅读全文

posted @ 2008-02-10 18:53 ZelluX 阅读(897) | 评论 (0)编辑 收藏

 

作者:晏渭川
随着Linux2.6的发布,由于2.6内核做了新的改动,各个设备的驱动程序在不同程度上要进行改写。为了方便各位Linux爱好者我把自己整理的这分 文档share出来。该文当列举了2.6内核同以前版本的绝大多数变化,可惜的是由于时间和精力有限没有详细列出各个函数的用法。

1、 使用新的入口
必须包含 <linux/init.h>
module_init(your_init_func);
module_exit(your_exit_func);
老版本:int init_module(void);
void cleanup_module(voi);
2.4中两种都可以用,对如后面的入口函数不必要显示包含任何头文件。

2、 GPL
MODULE_LICENSE("Dual BSD/GPL");
老版本:MODULE_LICENSE("GPL");

3、 模块参数
必须显式包含<linux/moduleparam.h>
module_param(name, type, perm);
module_param_named(name, value, type, perm);
参数定义
module_param_string(name, string, len, perm);
module_param_array(name, type, num, perm);
老版本:MODULE_PARM(variable,type);
MODULE_PARM_DESC(variable,type);

4、 模块别名
MODULE_ALIAS("alias-name");
这是新增的,在老版本中需在/etc/modules.conf配置,现在在代码中就可以实现。

5、 模块计数
int try_module_get(&module);
module_put();
老版本:MOD_INC_USE_COUNT 和 MOD_DEC_USE_COUNT

http://www.fsl.cs.sunysb.edu/~sean/parser.cgi?modules

In 2.4 modules, the MOD_INC_USE_COUNT macro is used to prevent unloading of the module while there is an open file. The 2.6 kernel, however, knows not to unload a module that owns a character device that's currently open.
However, this requires that the module be explicit in specifying ownership of character devices, using the THIS_MODULE macro.

You also have to take out all calls to MOD_INC_USE_COUNT and MOD_DEC_USE_COUNT.
       
    static struct file_operations fops =
{
         .owner = THIS_MODULE,
         .read = device_read,
         .write = device_write,
         .open = device_open,
         .release = device_release
}    
       

The 2.6 kernel considers modules that use the deprecated facility to be unsafe, and does not permit their unloading, even with rmmod -f.

2.6,2.5的kbuild不需要到处加上MOD_INC_USE_COUNT来消除模块卸载竞争(module unload race)

6、 符号导出
只有显示的导出符号才能被其他模块使用,默认不导出所有的符号,不必使用EXPORT_NO_SYMBOLS
老板本:默认导出所有的符号,除非使用EXPORT_NO_SYMBOLS

7、 内核版本检查
需要在多个文件中包含<linux/module.h>时,不必定义__NO_VERSION__
老版本:在多个文件中包含<linux/module.h>时,除在主文件外的其他文件中必须定义__NO_VERSION__,防止版本重复定义。

8、 设备号
kdev_t被废除不可用,新的dev_t拓展到了32位,12位主设备号,20位次设备号。
unsigned int iminor(struct inode *inode);
unsigned int imajor(struct inode *inode);
老版本:8位主设备号,8位次设备号
int MAJOR(kdev_t dev);
int MINOR(kdev_t dev);

9、 内存分配头文件变更
所有的内存分配函数包含在头文件<linux/slab.h>,而原来的<linux/malloc.h>不存在
老版本:内存分配函数包含在头文件<linux/malloc.h>

10、 结构体的初试化
gcc开始采用ANSI C的struct结构体的初始化形式:
static struct some_structure = {
.field1 = value,
.field2 = value,
..
};
老版本:非标准的初试化形式
static struct some_structure = {
field1: value,
field2: value,
..
};

11、 用户模式帮助器
int call_usermodehelper(char *path, char **argv, char **envp, int wait);
新增wait参数

12、 request_module()
request_module("foo-device-%d", number);
老版本:
char module_name[32];
printf(module_name, "foo-device-%d", number);
request_module(module_name);

13、 dev_t引发的字符设备的变化
1、取主次设备号为
unsigned iminor(struct inode *inode);
unsigned imajor(struct inode *inode);
2、老的register_chrdev()用法没变,保持向后兼容,但不能访问设备号大于256的设备。
3、新的接口为
a)注册字符设备范围
int register_chrdev_region(dev_t from, unsigned count, char *name);
b)动态申请主设备号
int alloc_chrdev_region(dev_t *dev, unsigned baseminor, unsigned count, char *name);
看了这两个函数郁闷吧^_^!怎么和file_operations结构联系起来啊?别急!
c)包含 <linux/cdev.h>,利用struct cdev和file_operations连接
struct cdev *cdev_alloc(void);
void cdev_init(struct cdev *cdev, struct file_operations *fops);
int cdev_add(struct cdev *cdev, dev_t dev, unsigned count);
(分别为,申请cdev结构,和fops连接,将设备加入到系统中!好复杂啊!)
d)void cdev_del(struct cdev *cdev);
只有在cdev_add执行成功才可运行。
e)辅助函数
kobject_put(&cdev->kobj);
struct kobject *cdev_get(struct cdev *cdev);
void cdev_put(struct cdev *cdev);
这一部分变化和新增的/sys/dev有一定的关联。

14、 新增对/proc的访问操作
<linux/seq_file.h>
以前的/proc中只能得到string, seq_file操作能得到如long等多种数据。
相关函数:
static struct seq_operations 必须实现这个类似file_operations得数据中得各个成员函数。
seq_printf();
int seq_putc(struct seq_file *m, char c);
int seq_puts(struct seq_file *m, const char *s);
int seq_escape(struct seq_file *m, const char *s, const char *esc);
int seq_path(struct seq_file *m, struct vfsmount *mnt,
struct dentry *dentry, char *esc);
seq_open(file, &ct_seq_ops);
等等

15、 底层内存分配
1、<linux/malloc.h>头文件改为<linux/slab.h>
2、分配标志GFP_BUFFER被取消,取而代之的是GFP_NOIO 和 GFP_NOFS
3、新增__GFP_REPEAT,__GFP_NOFAIL,__GFP_NORETRY分配标志
4、页面分配函数alloc_pages(),get_free_page()被包含在<linux/gfp.h>中
5、对NUMA系统新增了几个函数:
a) struct page *alloc_pages_node(int node_id, unsigned int gfp_mask, unsigned int order);
b) void free_hot_page(struct page *page);
c) void free_cold_page(struct page *page);
6、 新增Memory pools
<linux/mempool.h>
mempool_t *mempool_create(int min_nr, mempool_alloc_t *alloc_fn, mempool_free_t *free_fn, void *pool_data);
void *mempool_alloc(mempool_t *pool, int gfp_mask);
void mempool_free(void *element, mempool_t *pool);
int mempool_resize(mempool_t *pool, int new_min_nr, int gfp_mask);

16、 per-CPU变量
get_cpu_var();
put_cpu_var();
void *alloc_percpu(type);
void free_percpu(const void *);
per_cpu_ptr(void *ptr, int cpu)
get_cpu_ptr(ptr)
put_cpu_ptr(ptr)
老版本使用
DEFINE_PER_CPU(type, name);
EXPORT_PER_CPU_SYMBOL(name);
EXPORT_PER_CPU_SYMBOL_GPL(name);
DECLARE_PER_CPU(type, name);
DEFINE_PER_CPU(int, mypcint);
2.6内核采用了可剥夺得调度方式这些宏都不安全。

17、 内核时间变化
1、现在的各个平台的HZ为
Alpha: 1024/1200; ARM: 100/128/200/1000; CRIS: 100; i386: 1000; IA-64: 1024; M68K: 100; M68K-nommu: 50-1000; MIPS: 100/128/1000; MIPS64: 100; PA-RISC: 100/1000; PowerPC32: 100; PowerPC64: 1000; S/390: 100; SPARC32: 100; SPARC64: 100; SuperH: 100/1000; UML: 100; v850: 24-100; x86-64: 1000.
2、由于HZ的变化,原来的jiffies计数器很快就溢出了,引入了新的计数器jiffies_64
3、#include <linux/jiffies.h>
u64 my_time = get_jiffies_64();
4、新的时间结构增加了纳秒成员变量
struct timespec current_kernel_time(void);
5、他的timer函数没变,新增
void add_timer_on(struct timer_list *timer, int cpu);
6、新增纳秒级延时函数
ndelay();
7、POSIX clocks 参考kernel/posix-timers.c

18、 工作队列(workqueue)
1、任务队列(task queue )接口函数都被取消,新增了workqueue接口函数
struct workqueue_struct *create_workqueue(const char *name);
DECLARE_WORK(name, void (*function)(void *), void *data);
INIT_WORK(struct work_struct *work,
void (*function)(void *), void *data);
PREPARE_WORK(struct work_struct *work,
void (*function)(void *), void *data);
2、申明struct work_struct结构
int queue_work(struct workqueue_struct *queue, struct work_struct *work);
int queue_delayed_work(struct workqueue_struct *queue, struct work_struct *work,
unsigned long delay);
int cancel_delayed_work(struct work_struct *work);
void flush_workqueue(struct workqueue_struct *queue);
void destroy_workqueue(struct workqueue_struct *queue);
int schedule_work(struct work_struct *work);
int schedule_delayed_work(struct work_struct *work, unsigned long delay);

19、 新增创建VFS的"libfs"
libfs给创建一个新的文件系统提供了大量的API.
主要是对struct file_system_type的实现。
参考源代码:
drivers/hotplug/pci_hotplug_core.c
drivers/usb/core/inode.c
drivers/oprofile/oprofilefs.c
fs/ramfs/inode.c
fs/nfsd/nfsctl.c (simple_fill_super() example)

20、 DMA的变化
未变化的有:
void *pci_alloc_consistent(struct pci_dev *dev, size_t size, dma_addr_t *dma_handle);
void pci_free_consistent(struct pci_dev *dev, size_t size, void *cpu_addr, dma_addr_t dma_handle);
变化的有:
1、 void *dma_alloc_coherent(struct device *dev, size_t size, dma_addr_t *dma_handle, int flag);
void dma_free_coherent(struct device *dev, size_t size, void *cpu_addr, dma_addr_t dma_handle);
2、列举了映射方向:
enum dma_data_direction {
DMA_BIDIRECTIONAL = 0,
DMA_TO_DEVICE = 1,
DMA_FROM_DEVICE = 2,
DMA_NONE = 3,
};
3、单映射
dma_addr_t dma_map_single(struct device *dev, void *addr, size_t size, enum dma_data_direction direction);
void dma_unmap_single(struct device *dev, dma_addr_t dma_addr, size_t size, enum dma_data_direction direction);
4、页面映射
dma_addr_t dma_map_page(struct device *dev, struct page *page, unsigned long offset, size_t size, enum dma_data_direction direction);
void dma_unmap_page(struct device *dev, dma_addr_t dma_addr, size_t size, enum dma_data_direction direction);
5、有关scatter/gather的函数:
int dma_map_sg(struct device *dev, struct scatterlist *sg, int nents, enum dma_data_direction direction);
void dma_unmap_sg(struct device *dev, struct scatterlist *sg, int nhwentries, enum dma_data_direction direction);
6、非一致性映射(Noncoherent DMA mappings)
void *dma_alloc_noncoherent(struct device *dev, size_t size, dma_addr_t *dma_handle, int flag);
void dma_sync_single_range(struct device *dev, dma_addr_t dma_handle, unsigned long offset, size_t size,
enum dma_data_direction direction);
void dma_free_noncoherent(struct device *dev, size_t size, void *cpu_addr, dma_addr_t dma_handle);
7、DAC (double address cycle)
int pci_dac_set_dma_mask(struct pci_dev *dev, u64 mask);
void pci_dac_dma_sync_single(struct pci_dev *dev, dma64_addr_t dma_addr, size_t len, int direction);

21、 互斥
新增seqlock主要用于:
1、少量的数据保护
2、数据比较简单(没有指针),并且使用频率很高
3、对不产生任何副作用的数据的访问
4、访问时写者不被饿死
<linux/seqlock.h>
初始化
seqlock_t lock1 = SEQLOCK_UNLOCKED;
或seqlock_t lock2; seqlock_init(&lock2);
void write_seqlock(seqlock_t *sl);
void write_sequnlock(seqlock_t *sl);
int write_tryseqlock(seqlock_t *sl);
void write_seqlock_irqsave(seqlock_t *sl, long flags);
void write_sequnlock_irqrestore(seqlock_t *sl, long flags);
void write_seqlock_irq(seqlock_t *sl);
void write_sequnlock_irq(seqlock_t *sl);
void write_seqlock_bh(seqlock_t *sl);
void write_sequnlock_bh(seqlock_t *sl);
unsigned int read_seqbegin(seqlock_t *sl);
int read_seqretry(seqlock_t *sl, unsigned int iv);
unsigned int read_seqbegin_irqsave(seqlock_t *sl, long flags);
int read_seqretry_irqrestore(seqlock_t *sl, unsigned int iv, long flags);

22、 内核可剥夺
<linux/preempt.h>
preempt_disable();
preempt_enable_no_resched();
preempt_enable_noresched();
preempt_check_resched();

23、 眠和唤醒
1、原来的函数可用,新增下列函数:
prepare_to_wait_exclusive();
prepare_to_wait();
2、等待队列的变化
typedef int (*wait_queue_func_t)(wait_queue_t *wait, unsigned mode, int sync);
void init_waitqueue_func_entry(wait_queue_t *queue, wait_queue_func_t func);

24、 新增完成事件(completion events)
<linux/completion.h>
init_completion(&my_comp);
void wait_for_completion(struct completion *comp);
void complete(struct completion *comp);
void complete_all(struct completion *comp);

25、 RCU(Read-copy-update)
rcu_read_lock();
void call_rcu(struct rcu_head *head, void (*func)(void *arg),
void *arg);

26、 中断处理
1、中断处理有返回值了。
IRQ_RETVAL(handled);
2、cli(), sti(), save_flags(), 和 restore_flags()不再有效,应该使用local_save
_flags() 或local_irq_disable()。
3、synchronize_irq()函数有改动
4、新增int can_request_irq(unsigned int irq, unsigned long flags);
5、 request_irq() 和free_irq() 从 <linux/sched.h>改到了 <linux/interrupt.h>

27、 异步I/O(AIO)
<linux/aio.h>
ssize_t (*aio_read) (struct kiocb *iocb, char __user *buffer, size_t count, loff_t pos);
ssize_t (*aio_write) (struct kiocb *iocb, const char __user *buffer, size_t count, loff_t pos);
int (*aio_fsync) (struct kiocb *, int datasync);
新增到了file_operation结构中。
is_sync_kiocb(struct kiocb *iocb);
int aio_complete(struct kiocb *iocb, long res, long res2);

28、 网络驱动
1、struct net_device *alloc_netdev(int sizeof_priv, const char *name, void (*setup)(struct net_device *));
struct net_device *alloc_etherdev(int sizeof_priv);
2、新增NAPI(New API)
void netif_rx_schedule(struct net_device *dev);
void netif_rx_complete(struct net_device *dev);
int netif_rx_ni(struct sk_buff *skb);
(老版本为netif_rx())

29、 USB驱动
老版本struct usb_driver取消了,新的结构体为
struct usb_class_driver {
char *name;
struct file_operations *fops;
mode_t mode;
int minor_base;
};
int usb_submit_urb(struct urb *urb, int mem_flags);
int (*probe) (struct usb_interface *intf,
const struct usb_device_id *id);

30、 block I/O 层
这一部分做的改动最大。不祥叙。

31、 mmap()
int remap_page_range(struct vm_area_struct *vma, unsigned long from, unsigned long to, unsigned long size, pgprot_t prot);
int io_remap_page_range(struct vm_area_struct *vma, unsigned long from, unsigned long to, unsigned long size, pgprot_t prot);
struct page *(*nopage)(struct vm_area_struct *area, unsigned long address, int *type);
int (*populate)(struct vm_area_struct *area, unsigned long address, unsigned long len, pgprot_t prot, unsigned long pgoff, int nonblock);
int install_page(struct mm_struct *mm, struct vm_area_struct *vma, unsigned long addr, struct page *page, pgprot_t prot);
struct page *vmalloc_to_page(void *address);

32、 零拷贝块I/O(Zero-copy block I/O)
struct bio *bio_map_user(struct block_device *bdev, unsigned long uaddr, unsigned int len, int write_to_vm);
void bio_unmap_user(struct bio *bio, int write_to_vm);
int get_user_pages(struct task_struct *task, struct mm_struct *mm, unsigned long start, int len, int write, int force, struct page **pages, struct vm_area_struct **vmas);

33、 高端内存操作kmaps
void *kmap_atomic(struct page *page, enum km_type type);
void kunmap_atomic(void *address, enum km_type type);
struct page *kmap_atomic_to_page(void *address);
老版本:kmap() 和 kunmap()。

34、 驱动模型
主要用于设备管理。
1、 sysfs
2、 Kobjects

推荐文章:
http:/www-900.ibm.com/developerWorks/cn/linux/kernel/l-kernel26/index.shtml
http:/www-900.ibm.com/developerWorks/cn/linux/l-inside/index.shtml

2.6里不需要再定义“__KERNEL__”和“MODULE”了。
用下面的Makefile文件编译:

代码:

    obj-m   := hello.o

    KDIR   := /lib/modules/$(shell uname -r)/build
    PWD      := $(shell pwd)
    default:
              $(MAKE) -C $(KDIR) M=$(PWD) modules

posted @ 2008-02-10 17:00 ZelluX 阅读(1747) | 评论 (1)编辑 收藏

4.2. Data Structures

The GPU Memory Model
通常使用二维的texture保存,一是因为一维texture能存放的东西很少,二是因为现在的GPU很难高效地写入一列3维texture。
Iteration
stream编程模型包含了一种隐式的流的并行遍历。    
Generalized Arrays via Address Translation
在GPGPU编程中主要使用的数据结构是随机访问的多位容器,包括稀疏/稠密数组等。每个结构定义了一个虚拟域virual grid domain和一个物理域physical grid domaiin,以及之间相互转换的address translator。

4.2.1. Dense Arrays
多维数组通常先映射到一维,然后再到二维。
4.2.2. Sparse Arrays
根据非零元素的位置和数量是否变化分两种,静态和动态。
4.2.3. Adaptive Structures

posted @ 2008-02-10 16:13 ZelluX 阅读(351) | 评论 (0)编辑 收藏

捣鼓了半天,硬是没用gcc成功编译。还是用make modules算了。
2.6内核编译系统提供了一种不同的写法。
这里obj-m是树根,hello-objs是hello的两个结点。

ifneq ($(KERNELRELEASE),)
        obj-m :
= hello.o
        hello-objs :
= start.o stop.o
else
        KERNELDIR ?
= /lib/modules/$(shell uname -r)/build
        PWD  :
= $(shell pwd)

default:
        $(MAKE) -C $(KERNELDIR) M
=$(PWD) modules

endif

posted @ 2008-02-10 12:34 ZelluX 阅读(559) | 评论 (1)编辑 收藏

4. GPGPU Techniques
4.1. Stream Operations
4.1.1. Map
Given a stream of data elements and a function, map will apply the function to every element in the stream.
4.1.2. Reduce
Sometimes a computation requires computing a smaller stream from a larger input stream, possibly to a single element stream. This type of computation is called a reduction. For example, computing the sum or maximum of all the elements in a stream.
On GPUs, reductions can be performed by alternately rendering to and reading from a pair of textures.
也就是用分治法,不断切换输入和输出数据,每次都能减少一定比例的数据规模。
4.1.3. Scatter and Gather
If the write and read operations access memory indirectly, they are called scatter and gather respectively.
4.1.4. Stream Filtering
This stream fitering operation is essentially a nonuniform reduction.
4.1.5. Sort
Classic sorting algorithms are data-dependent and generally require scatter operations.
主要的几个算法都和Sorting Network有关,还有一种adaptive sort,和原来序列的有序度相关。
4.1.6. Search
4.2. Data Structures
    

posted @ 2008-02-09 13:14 ZelluX 阅读(333) | 评论 (0)编辑 收藏

注册表
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Drivers32
新建一个字符串值
名为 wavemapper
值为 msacm32.drv

posted @ 2008-02-09 01:00 ZelluX 阅读(4959) | 评论 (14)编辑 收藏

2.4 GPU Program Flow Control
 最新的GPU支持多种形式的分支,但是由于它们的高度并行化的本质,使用这些分支的时候一定要注意。
2.4.1 Hardware Machanisms for Flow Control
 三种主要实现:
 Predication 并非真正的data-dependent branch
 MIMD branching 
 SIMD branching  同时进行的指令唯一,即各个点的分支选择应该一致
2.4.2 Moving Branching Up The Pipeline
2.4.2.1 Static Branch Resolution
 静态分析,避免循环内部的分支。这里举了一个在离散空间点格(discrete spatial grid)上解偏微分方程的例子,不过没怎么看懂,大致是把循环拆成两部分的做法。
2.4.2.2 Pre-computation
 有时候一段时间内或者几次循环中某个分支的结果会是一个常数。这时候就只要在知道结果会改变的时候重新计算即可。
2.4.2.3 Z-Cull
 现代GPU有一系列用于避免处理不会被看到的像素的技术,其中之一就是Z-cull。简单的说Z-cull把没有通过深度测试(Z轴覆盖)点直接放弃。在流体模拟中,把land-locked障碍单元的Z深度标记为0,即可跳过这些点的计算。
2.4.2.4 Data-Dependent Looping With Occlusion Queries
 同样是避免处理不可见的点的技术
 
3 Programming Systems
 GPU的架构发展非常迅速,使得profiling和tuning需要由GPU生产商解决。
3.1 High-level Shading Languages
 Cg, HLSL  和底层硬件很接近
 OpenGL Shading Language  有一些不直接映射到硬件的特性,比如整数支持
 Sh, Ashli, ...
3.2 GPGPU Languages and Libraries
 上面提到的几个语言在使用时都要求编程人员站在几何元素的视角写代码。下面的几个系统试着把一些GPGPU功能抽象出来,隐藏底层的GPU实现。
 Brook  前几星期打过交道的东东
 Scout, Glift  都没听说过。。。
3.3 Debugging Tools
 GPU的调试功能很受局限。它必须提供在某一时刻显示多个点的调试信息的功能。一种printf-style的方法是把他们直接显示在屏幕上(汗,如果是GPGPU编程岂不是花屏了 >,<)。

posted @ 2008-02-08 16:05 ZelluX 阅读(502) | 评论 (0)编辑 收藏

实验室的寒假任务 =_=
No.1
A Survey of General-Purpose Computation on Graphics Hardware
on EUROGRAPHICS 2005

1. Why GP-GPU?
1.1 Powerful and Inexpensive
高内存带宽:Nvidia GeForce 6800 Ultra - 35.2GB/sec
强大的计算能力:ATI X800 XT - 63GFLOPS, Intel Pentium4 SSE unit(3.7GHz) - 14.8GFLOPS
尖端处理科技的应用:最新公布(指该survey发布的时间)的GPU包含三亿个晶体管,由0.011微米技术制作
快速发展:GeForce 6800的throughput为5900的两倍。通常GPU的计算能力平均每年增长速度为1.7x(pixels/second)和2.3x(vertices/second),而根据摩尔定律,CPU的对应数值大概为每年1.4x。粗略的说,GPU性能每六个月增长一倍。

1.2 Flexible and Programmable

1.3 Limitations and Difficulties
GPU的强大计算性能是建立在它高度针对的架构上的,因此很多应用都不适合放到GPU上做。比如文字处理,主要包括内存通信,而且很难并行化。
如今的GPU也缺少一些基本的计算功能,比如整数运算。而且很多只支持32位浮点数(貌似最近的R670指令集可以处理double类型了),这样导致很多科学计算都没法在GPU上做。
另外即使对于适合GPU这些特性的问题,真正使用GPU做时也有不少问题。GPU的编程模型很不一样,高效的GPU编程不仅仅是说多学一门高级语言。如今要借助GPU的计算能力,需要编程人员同时掌握相应的科学计算知识和计算机图形学知识。尽管如此,GPU对性能提升的帮助还是很诱人的。

1.4 GPGPU Today
http://gpgpu.org
一些GPGPU的应用包括
Dense and sparse matrix multiplication  计算领域
Multigrid and conjugate-gradient solves for systems partial differential equations   计算领域
Ray tracing   图像处理
Photon mapping   图像处理
Fluid mechanics solvers   物理模拟
Datamining operations   数据库/数据挖掘

2. Overview of Programmable Graphics Hardware
2.1 Overview of the Graphics Pipeline
当今的GPU都采用了称为graphics pipeline的架构。pipeline被分成不同的stage,硬件上每个stage都被放到task-parallel machine organization上实现。

2.2 Programmable Hardware
显卡商们把固定功能的pipeline转化成了一个更灵活的可编程的pipeliine。主要在geometry stage和fragment stage。原来的固定的操作被用户定义的vertex program和fragment program代替
通常来说,这些可编程阶段读入一组含有限数量的 有4个32位浮点的向量 数组并输出一组含有限数量的4*32浮点向量的数组。每个可编程阶段都可以访问常数寄存器,也可以读写对应的寄存器。

2.3 Introduction to the GPU Programming Model
典型的GPGPU程序都使用了fragment processor作为计算引擎。通常的结构为:
a. 程序员确定该应用的并行部分。应用程序被分成几个独立的可并行段,每段都被看成是一个kernel,被当成fragment program实现。每个kernel的输入输出都是一个或多个数据数组,以texture形式保存在GPU内存中。用流相关的术语表述的话,这些在texture中的数据组成了stream,每个stream上的元素都要被kernel分别处理。
b. 调用kernel前要先确定计算范围,程序员可以传递点的数据给GPU。注意GPU在处理一维数组时性能有所局限。
c. rasterizer为每个像素生成一个fragment。
d. 每个fragment被同一个活动的kernel程序处理。fragment程序可以读入任意的全局内存,但只能写到rasterizer决定的frame buffer中。这块还没怎么搞懂
e. 每个fragment的输出是一个值或者向量值,可以作为作中的程序结果,也可以保存为一个texture,用于后面的计算,复杂的应用通常需要多个pipeline之间的传递(multipass)

posted @ 2008-02-07 16:31 ZelluX 阅读(745) | 评论 (1)编辑 收藏

include/linux/module.h
struct module:
struct module
{
    
// 用于在用户空间传入module对象时判断传入的结构是否有效
    unsigned long size_of_struct;    /* == sizeof(module) */
    
struct module *next;
    
// 指向本module的名称,通常内核空间里申请的name内存位置都是紧跟在module{}结构后面的
    const char *name;
    
// 本module{}结构的空间 + 紧接着这段内存申请的归module{}结构使用的一部分空间
    
// size = sizeof(struct module) + sizeof(misc data)
    unsigned long size;

    
// 模块引用计数器,还没搞清楚这里的pad是干什么用的
    
// i386中atomic_t的定义: typedef struct { volatile int counter; } atomic_t;
    union
    
{
        atomic_t usecount;
        
long pad;
    }
 uc;                /* Needs to keep its size - so says rth */

    
// 模块当前状态,已初始化/运行中/被移除/被访问过等
    unsigned long flags;        /* AUTOCLEAN et al */

    
// 定义的内核模块符号数
    unsigned nsyms;
    
// 引用的模块链表节点数,遍历模块依赖性时使用
    unsigned ndeps;

    
// 符号表
    struct module_symbol *syms;
    
// 记录依赖的其他模块的数组
    struct module_ref *deps;
    
// 记录引用该模块的其他模块的数组
    struct module_ref *refs;
    
// 初始化和删除模块时调用的函数指针
    int (*init)(void);
    
void (*cleanup)(void);
    
// 中断向量表的入口和结束位置
    const struct exception_table_entry *ex_table_start;
    
const struct exception_table_entry *ex_table_end;
#ifdef __alpha__
    unsigned 
long gp;
#endif
    
/* Members past this point are extensions to the basic
       module support and are optional.  Use mod_member_present()
       to examine them.  
*/

    
// 这两个指针维持一些模块相关信息,方便卸载后再次装载模块时的配置
    const struct module_persist *persist_start;
    
const struct module_persist *persist_end;
    
int (*can_unload)(void);
    
int runsize;            /* In modutils, not currently used */
    
const char *kallsyms_start;    /* All symbols for kernel debugging */
    
const char *kallsyms_end;
    
const char *archdata_start;    /* arch specific data for module */
    
const char *archdata_end;
    
const char *kernel_data;    /* Reserved for kernel internal use */
}
;

struct module_symbol:
保存目标代码中的内核符号,读取文件装入模块时通过这个数据结构将里面包含的符号信息读入。
struct module_symbol
{
    unsigned 
long value; // 入口地址
     const char *name;    // 内核符号名称
}
;

struct module_ref:
注意这里dep和ref记录的不对称,应该可以看成是一个ref链表吧
module{} 中的deps数组分别指向了各个依赖的module_ref{}
struct module_ref
{
    
struct module *dep;    /* "parent" pointer */
    
struct module *ref;    /* "child" pointer */
    
struct module_ref *next_ref;
}
;

struct kernel_sym:
在sys_get_kernel_syms()中用到的结构,该函数将内核符号拷贝到用户空间的kernel_sym{}中,从而可以在用户态存放模块信息。
struct kernel_sym
{
    unsigned 
long value;    // 内核符号地址
    char name[60];        /* should have been 64-sizeof(long); oh well */
}
;

module.c中的一些函数先略去了,书上蛮详细的

模块的加载和卸载
insmod的任务:
从命令行中读入模块名,确定代码所在文件的位置
计算需要的内存
执行系统调用create_module(),传递新模块的名称和大小
用QM_MODULES获得所有已经链接模块的模块名
用QM_SYMBOL获得内核符号表和已经链接到内核的模块的符号表
使用这些信息重新定位该模块文件中的代码
在用户空间分配内存,拷贝相关信息
调用sys_init_module(),传递上面创建的用户态的内存区地址
释放用户态内存,结束

rmmod的任务:
用QM_MODULES和QM_REFS取得已经链接的模块列表和依赖关系
调用delete_module

posted @ 2008-02-07 11:22 ZelluX 阅读(547) | 评论 (3)编辑 收藏

http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

居然是NPC...

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

如果一些文章的链接失效,google相应的标题应该还是很容易找到其他网站的转载的。

中断处理:
Interrupt in Linux
相当不错的中文资料

内核调度:
Inside the Linux scheduler
 
讲的是用expired/active两个数组维护的O(1)算法,大多数讲2.6内核的书上都会提到的调度算法 (2008-02-06)

Multiprocessing with the Completely Fair Scheduler
最新的2.6.23采用的CFS,还没搞懂 (2008-02-06)

http://www.ibm.com/developerworks/cn/linux/l-cn-scheduler/index.html
Linux 调度器发展简述 (2008-02-13)

内核模块:
2.6 内核中的模块注入 (2008-02-17)
http://www.linuxforum.net/forum/showflat.php?Cat=&Board=security&Number=536404&page=0&view=collapsed&sb=5&o=31&fpart

系统调用:
Linux 2.6 新增的 vsyscall 系统服务调用机制 (2008-02-18)
http://blog.csdn.net/wishfly/archive/2005/01/23/264435.aspx

Linux on-the-fly kernel patching without LKM (2008-02-19)
http://doc.bughunter.net/rootkit-backdoor/kernel-patching.html

内存管理:
http://linux-mm.org/LinuxMM
Linux-mm.org is a wiki for documenting how memory management works and for coordinating new memory management development projects. (2008-02-21)

并发同步:
http://hi.baidu.com/charleswen/blog/item/61f3e40ebc26dcce7acbe1c8.html
Linux内核中的同步和互斥分析报告 (2008-02-21)

http://www-128.ibm.com./developerworks/cn/linux/kernel/sync/index.html
Linux 2.4.x内核同步机制 (2008-02-22)

Big Picture:
http://www.linuxdriver.co.il/kernel_map
Interactive Linux kernel map (2008-02-16)
把内核中的函数相互调用做成了一张可放大缩小的地图,单击相应函数名会跳转到lxr的相应代码链接。

编程资料:
http://www.jegerlehner.ch/intel/
Intel Assembler CodeTable 80x86 (2008-02-21)

相关站点:
http://kernelnewbies.org
Linux Kernel Newbies

http://bbs4.newsmth.net/bbsdoc.php?board=KernelTech
水木KernelTech版

http://www.phrack.org
Phrack is an underground ezine made by and for hackers.
有不少和内核相关的hack资料

posted @ 2008-02-06 19:00 ZelluX 阅读(551) | 评论 (5)编辑 收藏