Snowdream

http://blog.yxwang.me/

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

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

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

yifanw大牛半個月前發(fā)在c++版上的，怕以后忘了看先放在這備個忘吧

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

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

白話參考文獻(xiàn)
http://www.newsmth.net/bbscon.php?bid=335&id=250260

最近有點忙，今天總算在某個課題deadline前把論文憋出來交上去了。跑這兒來推薦兩篇上個月看到的比較有意思的paper，都比較偏理論，也很老。

今天寫介紹下第一篇，劍橋大學(xué)的A Logic of Authentication，中了SOSP '89，整理后發(fā)在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的主要工作是通過構(gòu)造一種多種類的模態(tài)邏輯(many-sorted model logic)，來檢查網(wǎng)絡(luò)中驗證協(xié)議的安全性。

基礎(chǔ)的邏輯分三部分：
原語，如驗證雙方A和B，以及服務(wù)器S，下文用P Q R泛指
密鑰，如K_ab代表a和b之間的通訊密鑰，K_a代表a的公鑰，{K_a}^{-1}代表對應(yīng)的私鑰，下文用K泛指
公式（或者陳述），用N_a, N_b等表示，下文用X Y泛指

接下來定義以下約定（constructs）
P 信任 X: 原語P完全信任X
P 看到 X: 有人發(fā)送了一條包含X的信息給P，P可以閱讀它或者重復(fù)它（當(dāng)然通常是在做了解密操作后）
P 說了 X: 原語P發(fā)送過一條包含X的信息，同時也可以確定P是相信X的正確性的
P 控制 X: P可以判定X的正確與否。例如生成密鑰的服務(wù)器通常被默認(rèn)為擁有對密鑰質(zhì)量的審核權(quán)。
X 是新鮮的: 在此之前X沒有被發(fā)送過。這個事實可以通過綁定一個時間戳或者其他只會使用一次的標(biāo)記來證明。
P <-K-> Q: P和Q可以通過共享密鑰K進(jìn)行通訊，且這個K是好的，即不會被P Q不信任的原語知道。
K-> P: P擁有K這么一個公鑰，且它對應(yīng)的解密密鑰K^{-1}不會被其他不被P信任的原語知道。
P <=X=> Q: X是一個只被P和Q或者P和Q共同信任的原語知道的陳述，只有P和Q可以通過X來相互證明它們各自的身份，X的一個例子就是密碼。
{X}_K: X是一個被K加密了的陳述
<X>_Y: 陳述X被Y所綁定，Y可以用來證明發(fā)送X的人的身份

好了，總算把這些約定列完了，然后來看看通過這些約定能推出一些什么東東：
如果 P 相信 (P <-K-> Q), 且 P 看到 {X}_K，那么 P 相信 Q 說了 X。
這個例子很簡單，既然P Q有安全的密鑰K，那么P看到通過K加密后的X肯定認(rèn)為就是Q發(fā)出的。

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

再舉一個例子
如果 P 相信 Y 是新鮮的，那么 P 相信 (X, Y) 也是新鮮的。
這里(X, Y)表示 X 和 Y 的簡單拼接，也很容易理解，既然 Y 之前沒出現(xiàn)過，那么 X 和 Y 的組合自然也沒出現(xiàn)過。

一個協(xié)議要被定義為安全，最起碼要滿足
A 相信 A <-K->B，B 相信 A <-K->B
即雙方要互相信任密鑰是安全的

再健壯一點的協(xié)議，還要滿足
A 相信 (B 相信 (A 相信 A <-K->B))，反之一樣
即A B不僅相信密鑰，也相信對方相信自己對密鑰的信任。

有了這些簡單卻強大的工具后，接下來這篇paper開始著手分析一些協(xié)議，包括Kerberos協(xié)議，Andrew Secure RPC 握手協(xié)議等，還指出了其中的一些問題和改進(jìn)措施，例如CCITT X.509 協(xié)議中可以通過重復(fù)發(fā)送一條老的信息來模仿成加密雙方中的一員。

具體的分析不貼上來了，一方面對于我這個不熟悉TeX的人來說碼公式實在麻煩，另一方面我實在困死了 =_=

建議有興趣的朋友好好看看這篇經(jīng)典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也有一篇關(guān)于如何concurrent program中發(fā)現(xiàn)隱藏的atomicity violation bugs的paper，里面提到了這篇paper

2008-11-30

OSDI '08上MSR發(fā)的paper，針對并發(fā)編程中難以發(fā)現(xiàn)的bug問題。

paper的內(nèi)容主要分兩大塊。

一是如何在發(fā)現(xiàn)bug的時候記錄下線程的運行先后(thread interleaving)，途徑是在線程API和用戶程序多寫一層wrapper functions，這里還有一些其他的問題，比如只記錄下了thread interleaving的話出現(xiàn)data race怎么解決等。

另外一塊內(nèi)容是如何遍歷出給定程序運行后所能產(chǎn)生的結(jié)果的集合，加入這個能實現(xiàn)的話那就能把所有隱藏的bug都找出來了。但是這個搜索空間很大，是 指數(shù)級的，的一個結(jié)論就是：給定一個程序有n個的線程，所有線程共完成k條指令，那么c次占先調(diào)度后線程的排列情況數(shù)的復(fù)雜度是的，所以在實現(xiàn)遍歷代碼的時候必須有效的降低k和c的值。

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

google了一堆關(guān)鍵詞后終于發(fā)現(xiàn)問題出在MTU上，至少在偶的本本上運行
sudo ifconfig eth1 mtu 1412
就沒問題了（eth1是無線網(wǎng)卡）

p.s 多謝萬熊? XD

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

  閱讀全文

Bruce Eckel的一篇日志建議把self從方法的參數(shù)列表中移除，并把它作為一個關(guān)鍵字使用。
http://www.artima.com/weblogs/viewpost.jsp?thread=239003

Guido的這篇日志說明了self作為參數(shù)是必不可少的。
http://neopythonic.blogspot.com/2008/10/why-explicit-self-has-to-stay.html

第一個原因是保證foo.meth(arg)和C.meth(foo, arg)這兩種方法調(diào)用的等價（foo是C的一個實例)，關(guān)于后者可以參見Python Reference Manual 3.4.2.3。這個原因理論上的意義比較大。

第二個原因在于通過self參數(shù)我們可以動態(tài)修改一個類的行為：

這樣類C就新增了一個meth方法，并且所有C的實例都可以通過c.meth(newval)調(diào)用這個方法。

前面兩個原因或許都可以通過一些workaround使得不使用self參數(shù)時實現(xiàn)同樣的效果，但是在存在decorator的代碼中Bruce的方法存在致命的缺陷。(關(guān)于decorator的介紹可以參見http://www.python.org/dev/peps/pep-0318/)

根據(jù)修飾對象，decorator分兩種，類方法和靜態(tài)方法。兩者在語法上沒有什么區(qū)別，但前者需要self參數(shù)，后者不需要。而Python在實 現(xiàn)上也沒有對這兩種方法加以區(qū)分。Bruce日志評論中有一些試圖解決decorator問題的方法，但這些方法都需要修改大量底層的實現(xiàn)。

最后提到了另一種語法糖實現(xiàn)，新增一個名為classmethod的decorator，為每個方法加上一個self參數(shù)，當(dāng)然這種實現(xiàn)也沒必要把self作為關(guān)鍵字使用了。不過我覺得這么做還不如每次寫類方法時手工加個self =_=

2008年評出了1998年最具影響力的PLDI論文，獲獎?wù)撐牡淖髡邔⒎謹(jǐn)?000美元的獎金（還沒一等獎學(xué)金多 -_-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實現(xiàn)closure的方式和常見的functional language不同，采用了flat closures實現(xiàn)。

“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函數(shù)x += 1對x進(jìn)行賦值，rebind了這個對象，于是Python查找x的時候只會在local environment中搜索，于是就有了UnboundLocalError。

換句話說，如果沒有修改這個值，比如b中僅僅簡單的輸出了x，程序是可以正常運行的，因為此時搜索的范圍是nearest enclosing function region。

而d方法并沒有rebind x變量，只是修改了x指向的對象的值而已。如果把賦值語句改成x = [4]，那么結(jié)果就和原來不一樣了，因為此時發(fā)生了x的rebind。

所以Python中的closure可以理解為是只讀的。

另外第二個例子也是這篇文章中提到的一種workaround：把要通過inner function修改的變量包裝到數(shù)組里，然后在inner function中訪問這個數(shù)組。

至于為什么Python中enclosed function不能修改enclosing function的binding，文中提到了主要原因還是在于Guido反對這么做。因為這樣會導(dǎo)致本應(yīng)該作為類的實例保存的對象被聲明了本地變量。

參考網(wǎng)站：http://www.python.org/dev/peps/pep-0227/

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

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

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

以Java的一個計數(shù)程序為例

這個程序的功能不用多說了，一個同步的計數(shù)程序。它的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.

初看這個程序自然是一頭霧水，不過程序的函數(shù)式風(fēng)格味還是很濃的。

前面提到，Erlang是基于message的，或者說message sending機制是包含在語言系統(tǒng)內(nèi)部的，語法就是 pid ! message

接下來再來分析這個簡單的程序。開頭兩行是模塊和函數(shù)聲明，略去。make_sequence開始這個進(jìn)程，spawn/1內(nèi)置函數(shù)創(chuàng)建一個新的進(jìn)程，并返回pid到調(diào)用者。

初始時運行的函數(shù)是sequence_loop(0)，這個函數(shù)接收兩種信息，用receive表達(dá)式聲明：如果收到形式是{From, get_next}的信息，就返回當(dāng)前的N并調(diào)用sequence_loop(N+1)，這樣下一次收到同樣的信息時就能返回N+1了；reset則等價 于Java版本中的n=0語句。

get_next/1則是發(fā)送給pid為Sequence的進(jìn)程 {self(), get_next} 這樣一個信息，上面解釋的sequence_loop/1函數(shù)收到這個信息后會返回一個 {self(), N} 的tuple給get_next/1，收到這個信息后get_next/1就能返回N這個值了。

最后reset/1函數(shù)則是發(fā)送給Sequence一個reset信息。

這個簡單的程序里能大致窺見一些Erlang的特點，尤其是它基于信息發(fā)送的本質(zhì)。

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之后發(fā)現(xiàn)是虛擬機類型設(shè)置的問題，運行xm info可以看到
xen_caps : xen-3.0-x86_32p
末尾的p表示Xen內(nèi)核開啟了PAE模式，所以載入的kernel也必須開啟PAE，在bootstrap.x86_32.S中加入PAE=yes選項即可。

09月 25, 2008
DomainU中調(diào)用do_console_io

The Definitive Guide to Xen第二章的Exercise，通過調(diào)用hypercall page中的console_io項輸出Hello World。



但是默認(rèn)選項編譯和啟動的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維護(hù)了一張shadow page table，其中映射的地址為machine address。一種比較高效的方案是設(shè)置Guest OS的page table為只讀，當(dāng)Guest OS試圖修改這個虛擬頁表時，發(fā)生page fault被Xen截獲，Xen修改shadow page table中相應(yīng)的數(shù)據(jù)（把pseudo-physical address轉(zhuǎn)化成machine address）。另外一個優(yōu)化是guest page table被修改時不修改shadow page table，只是把它放到一個待更新列表中，等Guest OS執(zhí)行了刷新tlb的指令后再一次性更新。

The Definitive Guide to Xen上還提到了另一種基于full paravirtulization和shadow page table之間的方案。Xen把Guest OS的page table置為只讀，當(dāng)Guest OS試圖修改page table時，Xen捕獲到page fault，把page directory中對應(yīng)的入口置為無效，再把page table改成可寫讓Guest OS修改。由于page directory中對應(yīng)的入口被設(shè)成無效了，下次訪問該地址時還是會發(fā)生page fault，這時候Xen再修改page directory和page table的對應(yīng)項就行了。

這種方法意味著Guest OS中內(nèi)核管理模塊直接和machine address打交道，而其他部分則仍然使用pseudo-physical address。另外這種情況下page directory不能被Guest OS修改。

另外Xen還用到了段機制，用來為Xen保留地址空間開始的64M內(nèi)存。