Snowdream

http://blog.yxwang.me/

寫了好幾天的代碼因為還有bug沒de掉，沒commit到svn上

然后不知怎么的在make的時候生成的kernel沒變化，于是直接make world，然后發現linux kernel目錄被清空了。。。

只能明天靠記憶慢慢補了，皚皚。

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

最近有點忙，今天總算在某個課題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

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

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

作者博客后面還新增了對它們的簡要評論

2009-01-08

今年的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的值。

問題現象：上校內、一些國內論壇時經常出現連接重置(Connect reset)錯誤，而上google baidu等網站卻沒什么問題。ping那些有問題的網站的結果很正常。

google了一堆關鍵詞后終于發現問題出在MTU上，至少在偶的本本上運行
sudo ifconfig eth1 mtu 1412
就沒問題了（eth1是無線網卡）

p.s 多謝萬熊? XD

     摘要: 發信人: linelf (水水), 信區: Real_Estate
標 題: 蘇南經濟模式興衰親歷記zz
發信站: 日月光華 (2009年01月15日20:39:22 星期四)

  閱讀全文

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參數我們可以動態修改一個類的行為：

這樣類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 =_=

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.

BBS上的一個帖子，問題是

運行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/

acm queue 9月的雜志的主題是The Concurrency Problem，力推了Erlang這個語言，其中有篇文章簡單的介紹了下這個message-oriented語言。

查了下這個名字的讀法，正確的讀法應該是air-lang，這里元音a的發音和bang中的a一樣。

文章中的第一個程序就有點令人費解，主要原因在于Erlang的語法和一般的imperative language差別很大，和functional language比較類似，但是本質上也有很大的不同。

以Java的一個計數程序為例

這個程序的功能不用多說了，一個同步的計數程序。它的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的特點，尤其是它基于信息發送的本質。

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。



但是默認選項編譯和啟動的Xen是不會保留DomainU中輸出的信息。參考drivers/char/console.c，可以看到主要有兩個選項控制了DomainU的do_console_io輸出：



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

上圖為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內存。

好不容易找到的一個php，直接貼這兒了，方便其他網友。
wordpress的wp-syntax插件用的也是geshi，所以同樣也適用于wp-syntax

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

主要的衡量標準是可讀性、是否等寬、特殊字符的辨認度（比如0和O）

依然是內網日志的匯總

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的機制

轉自偶的內網博客

Time : 2008-08-20 21:44
匯編文件中導出函數符號

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

用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)?\

發信人: 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就比較簡單了，不需要任何內嵌匯編代碼即可完成。

     摘要: 美國為什么需要這么多大學生，而中國培育出這么多優秀大學生為什么失業？難道是我們學生程度不夠？難道是我們同學不夠用功？難道是我們同學專業不對口？那我告訴所有讀者，為什么大學生就業難……   閱讀全文

用ctags -R或者ctags * -R的時候只能生成當前目錄下的tag，檢查了半天發現原來這個版本的ctags的參數順序只能老老實實的來：ctags -R *

太囧了，總歸要bs下的，雖說也有那么一點點可能是bash解析參數時的問題，不過我猜問題來源還是這個低版本的ctags = =

話說我也挺圡的，不習慣用source insight，還是喜歡用vim寫代碼

沒心思看離散，也不準備堅持看沒有荷蘭的歐洲杯決賽。閑著點好友的Q-Zone，原來Q-Zone首先會判斷你的瀏覽器，如果是Firefox它會重定向到RSS閱讀界面。

安然在開學后2個月寫的一篇日志，“記憶里的名單”，驚喜的看到有我。也列出了一張屬于我的名單。好，等待時間的遴選。

“于是想 如果有個妹妹 我要告訴她 好好放肆猖狂 做不可思議的事情 為友情和少年青澀的愛情花心思 做只是喜歡沒有功利目的的事情 這么好的年華 就是用來這樣浪費 和珍惜的~”

可惜我只保持了四五個月的這種瘋狂，現在依然糾結于功利的選擇。有時候曾想，或許那次失敗更適合我，或許我終將把這么一條平淡無奇的路走到盡頭。“表面強者”，或許還是很有道理的。

看到fofo的博的文字，“我要去杭州，把所有的事情拋掉，不管后果。這個地方太讓人壓抑，盡管有很玩得來的室友，有很好的足球隊的隊友，可以看很多以前爸媽不讓看的喜歡的書還有過米的比賽，吃的東西也都很習慣，還是會在天氣很好的星期天下午突然想起曾經在冬日的陽光照射下一家人在陽臺上圍著一張桌子吃飯的情景，還是會在一個人騎在去計算機協會的路上很難過地想著再也不會有那么四個或者五個人在一起吃完小炒放肆地在鋪滿夕陽的校園小路上勾肩搭背地行走了，還是會在一百多個人的課堂上懷念起那些艱苦卻簡單的日子里所有的笑聲，還是會在網吧包夜的時候想起初中時捏著飯錢偷偷摸摸地去電腦房玩星際……想找找朋友們，調整一下自己的心情。”

真的找不回來了。在寫這篇博文時也找不到以前寫字的感覺了。

明天離散考試，某個記錄或許將要因此打破。

不枉我周末練了那么多ZvP

不過總比分太慘了。。

     摘要: 一篇關于函數式編程的介紹，在水木Java版引起了熱烈討論。  閱讀全文

1. framwork/policies/Singleton.h
Singleton模式，可以指定相應的線程模型、創建策略和生命期控制策略。
對于全局范圍的Singleton實例，定義了若干個宏便于訪問，例如

Singleton的定義：

不知道這里的注釋Prohibited actions...this does not prevent hijacking.是什么意思，copy constructor和hijacking有什么關系呢？

另外注意這行typedef typename ThreadingModel::Lock Guard;，原來typedef還可以用在函數上。

Singleton的Instance方法用的是標準的double-checked lock方法，關于DCL可以參考這篇博文http://m.tkk7.com/zellux/archive/2008/04/07/191365.html

2. Explicit Constructors
game/WorkPacket.h中看到的語法，防止構造函數中參數的隱式轉型
比如explicit String(int n); 用String('c')聲明時就會報錯

一套基于文件系統的安全方案，主要通過隔離運行不可信任的程序、taint記錄、事故恢復。

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

出于時間考慮沒有提到paper中進程間通信的解決方法

水木上有人貼了個有趣的程序

用gcc -O2編譯運行后會不停地打印從0開始的自然數，注意如果編譯器沒有做優化的話，打印到某個數的時候肯定會發生棧溢出從而程序終止的情況，但這個程序卻能一直運行下去，說明編譯器做了尾遞歸優化。

用gcc -O2 -S生成這個程序的匯編代碼后證實了這一點。
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

睡覺去恩

P.S 點球真不是人看的

     摘要: 一篇介紹一種全新的Web架構，另一篇介紹虛擬機的探測方法  閱讀全文

     摘要: 發信人: NetMD (C++), 信區: CPlusPlus
標 題: [FAQ] C/C++中的序列點
發信站: 水木社區 (Wed Feb 7 01:13:41 2007), 站內  閱讀全文

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修改日志），所以當天的日記不會被發布。

使用的時候修改開頭幾行的配置信息即可

這書的數學分析方面有點過于簡單了，連絕對值、二維坐標系是個什么東東都會給你解釋一下，所以看起來很快。

第一章 經濟學十大原理

第二章 像經濟學家一樣思考
生產可能性邊界(production possibilites frontier)通常是凹向原點的形狀。
實證表述(positive statements)：企圖描述世界是什么的觀點。經濟學的許多內容是實證的。
規范表述(normative statements)：企圖描述世界應該是什么的觀點。

第三章 相互依賴性與貿易的好處
機會成本與比較優勢

第四章 供給與需求的市場力量

第五章 彈性及其應用
需求價格彈性 = 需求量變動百分比 / 價格變動百分比
供給價格彈性 = 供給變動百分比 / 價格變動百分比
例：由于毒品的需求缺乏彈性，禁毒引起的毒品價格提高的比例大于毒品使用減少的比例，因此禁毒會增加與毒品相關的犯罪。（短期）

第六章 供給、需求與政府政策
限制性價格上限導致短缺，限制性價格下限導致過剩。
例：最低工資法導致失業。
一旦市場達到新均衡，無論向誰征稅，都是買者與賣者分攤稅收負擔。
例：由于勞動的供給遠比勞動的需求缺乏彈性，是工人而不是企業承擔了大部分工薪稅的負擔。

發信人: 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.]

     摘要: 一種利用虛擬機進行的攻擊手段(下篇)  閱讀全文

     摘要: 一種利用虛擬機進行的攻擊手段  閱讀全文

Fight Club

1. 不能談論斗陣俱樂部。
2. 不能談論斗陣俱樂部。
3. 只要有人喊停，或者受傷，快累死了，打斗就得停。
4. 一次只能兩人打
5. 一次一場
6. 脫掉襯衫和鞋子
7. 打斗沒有時限
8. 只要你是初次參加，就一定得打。


太混亂了

秒速5センチメートル

“櫻花飄落的速度，是每秒5厘米。”

凄美無奈的故事，有點像村上的《國境以南》，只是主人公最后仍然在尋找著對方。

新海誠的動畫色彩很斑斕，很華麗。

寫到這里，千千靜聽里正好隨機播放到了那首One More Time, One More Chance，幾百分之一的概率，呵呵。

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

在機房電腦的Arch Linux上搭了個MediaWiki，作為自己的知識庫。
前幾天在水木上看到的想法，覺得這樣很有成就感，盡管現在還沒學多少東西。
一步一個腳印，慢慢擴充。

Mika的歌還真是好聽。

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了無數次后總算過了。。。

     摘要: 算法導論第27章，在并行處理的條件下高效的排序算法。  閱讀全文

因為MSN一開始會嘗試連接crl.microsoft.com，把這個網站屏蔽了就行。
在hosts文件中加入
127.0.0.1?? crl.microsoft.com

貼幾個鏈接，以后有空再看

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#

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

抽時間多做做，提高下我可憐的算法功底 >,<

~/.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
把這行注釋掉，問題解決

要提高效率果然得遠離網絡，躺床上看paper理解起來快多了
總算把晚上要講的ppt做出來了，囧

下午打球直到體力極限，一路淋雨跑回寢室，洗澡，感冒，低落。想回家。

有時候會想，幾年后，真的就要在上海這個地方工作立足嗎？

我想看一堆電影 想讀一堆書 想學C# Lisp Python 想上ACM OJ網站切題 想參加一次TopCoder比賽 想學塤 想學鋼琴 想睡覺 想看微經 想練英語 想看內核 想到處旅游

終會和現實沖突。于是我想退實驗室。幾個小時后又放棄這個決定。

終究是怕這怕那保守著緩慢前進的人。

計算機科學論壇最近舉辦了一個閱讀樣章，提交書評的活動，具體內容請見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://m.tkk7.com/zellux)

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

有點長，不過寫得很不錯

     摘要: 以下簡單的整理來自游俠 netshow論壇的帖子 部分補充  閱讀全文

     摘要: 問題：
給定n個32位無符號整數，求出其中異或結果最大的兩個整數。  閱讀全文

轉載請注明 作者 ZelluX??? http://m.tkk7.com/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://m.tkk7.com/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

?

感冒發燒。

把不應該存在的博文全刪了。

我知道我在和自己賭氣。

那又如何。

回過頭來，這兩年我所得到的，不過是可以隨手扔掉的東西。

最后，acm的那些人們加油。

翹課大半，作業一半不交一半抄，總之太不像學生了。
搞得現在Super Scalar都只知道個大概，tableaux也知其然而不知所以然。
下星期好好參與一次，上課、作業一個都不能少，恩。
至于之后么，再說咯。

沒事干找了幾個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)

這語言真不錯，不像Java那么呆，可惜不開源。
入門看的書是CLR via C#中文版，翻譯質量不錯，起碼到現在還沒覺得有必要翻一翻原版（不過為什么中文書都喜歡把“棧”叫成“堆棧”呢）。
前面幾章粗略看了下，從第四章類型基礎開始重點閱讀。
繼續漫無目的的學習感興趣的東西，學習之中經常會驚喜的發現，自己看問題的角度已經不同于之前了。

1. 類的new操作會遞歸調用該類的所有父類構造器，直到System.Object，后者的構造器只是簡單返回，用ILDasm查看MSCorLib.dll可以證實這一點。

2. is和as操作符，is類似于Java中的instanceof，as會先檢查類型，如果兼容返回該對象的引用，反之返回null。
利用as可以做到只檢驗一次對象類型，提高程序性能。這本書的很多地方都提到了性能因素。

3. 方法調用和x86上匯編語言調用機制很類似。先是參數入棧，接著返回地址入棧，返回的時候也差不多。不知道x64等寄存器較多的架構上會不會使用寄存器傳參呢，呵呵。

4. 作為方法的prologue的一部分，CLR會自動將所有局部變量初始化為null或0。感覺這個自動初始化沒什么必要，在第五章可以看到。
這里的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會提高一些性能。

接下來書上舉了個很搞的例子說明boxing和unboxing的各種情況，其實也很容易理解。