2016年1月19日
0x0
前些天組里老司機(jī)@梁希在jvm的項目榨干機(jī)器性能之余，為了檢查下gcc編譯器和Intel Xoen CPU的正確性，寫了一組測試代碼測試了下mfence指令的效果
`
mfence Opcode : 0F AE /6
Performs a serializing operation on all load-from-memory and store-to-memory instructions that were issued prior the MFENCE instruction. This serializing operation guarantees that every load and store instruction that precedes in program order the MFENCE instruction is globally visible before any load or store instruction that follows the MFENCE instruction is globally visible. The MFENCE instruction is ordered with respect to all load and store instructions, other MFENCE instructions, any SFENCE and LFENCE instructions, and any serializing instructions (such as the CPUID instruction).
Weakly ordered memory types can be used to achieve higher processor performance through such techniques as out-of-order issue, speculative reads, write-combining, and write-collapsing.
The degree to which a consumer of data recognizes or knows that the data is weakly ordered varies among applications and may be unknown to the producer of this data. The MFENCE instruction provides a performance-efficient way of ensuring load and store ordering between routines that produce weakly-ordered results and routines that consume that data.
It should be noted that processors are free to speculatively fetch and cache data from system memory regions that are assigned a memory-type that permits speculative reads (that is, the WB, WC, and WT memory types). The PREFETCHh instruction is considered a hint to this speculative behavior. Because this speculative fetching can occur at any time and is not tied to instruction execution, the MFENCE instruction is not ordered with respect to PREFETCHh instructions or any other speculative fetching mechanism (that is, data could be speculatively loaded into the cache just before, during, or after the execution of an MFENCE instruction).
`
簡單來說就是一個可以在CPU亂序執(zhí)行中保證真實的load/store順序的指令
0x1
老司機(jī)寫了一個小程序(注：有誤版)
// file: order.c
#define _GNU_SOURCE
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
union p64 {
int i;
char padding[64];
long align8;
};
volatile union p64 v1, v2;
int b;
void *
run1(
void *ignore)
{
for (;;) {
while (!b);
if (v1.i || v2.i) {
puts("assert error 1");
exit(-1);
}
v1.i = 1;
asm ("sfence": : :"memory");
v2.i = 1;
asm ("sfence": : :"memory");
b = 0;
}
}
intmain()
{
pthread_t p;
pthread_create(&p, NULL, run1, NULL);
int cnt = 0;
for (;; cnt++) {
v1.i = v2.i = 0;
asm ("sfence": : :"memory");
b = 1;
asm ("sfence": : :"memory");
int icnt = 0;
for (;; icnt++) {
int i1 = v1.i;
asm ("lfence": : :"memory");
int i2 = v2.i;
if (i1 && i2)
break;
if (i1 < i2) {
printf("assert error, cnt = %d, icnt = %d, i1 = %d, i2 = %d\n", cnt, icnt, i1, i2);
exit(-1);
}
}
}
return 0;
}
大概邏輯是： 一共有3個變量，v1.i, v2.i, b ,起了2個線程，一個順序?qū)懭雟1和v2，一個讀v1和v2，互相通過改變b的值來通訊，然后兩個線程不停循環(huán)。
這個程序會掛在
printf("assert error, cnt = %d, icnt = %d, i1 = %d, i2 = %d\n", cnt, icnt, i1, i2);
這條斷言上，意思是線程1在順序?qū)懭雟1和v2，但是主線程卻出現(xiàn)讀到 v1=0，v2=1的情況。
0x2
然后我?guī)兔θタ戳艘幌拢X得這種寫法甚是粗暴，于是原樣照搬了一個c++11版:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <atomic>
#include <thread>
using namespace std;
union p64 {
atomic<
int> i;
char padding[64];
long align8;
};
volatile union p64 v1, v2;
atomic<
int> b;
void *
run1()
{
int rcnt = 0;
for (;; rcnt++) {
while (!b.load());
if (v1.i.load() || v2.i.load()) {
puts("assert error 1");
exit(-1);
}
v1.i.store(1);
v2.i.store(1);
b.store(0);
}
}
intmain()
{
// init
v1.i.store(0);
v2.i.store(0);
thread t(run1);
int cnt = 0;
for (;; cnt++) {
v1.i.store(0);
v2.i.store(0);
b.store(1);
int icnt = 0;
for (;; icnt++) {
int b2 = b.load();
int i1 = v1.i.load();
// *****
int i2 = v2.i.load();
// *****
if (i1 && i2)
break;
if (i1 < i2) {
printf("assert error, cnt = %d, icnt = %d, i1 = %d, i2 = %d\n", cnt, icnt, i1, i2);
exit(-1);
}
if (i1 == 0 && i2 == 0 && b2 == 0)
break;
}
}
return 0;
}
因為是原樣照搬，所以肯定還是會掛，但是畢竟語義上更好理解了
我們先來分析一下為什么會掛
- 線程1對于v1，v2的寫入順序一定是一致的
- Memory Barrier也保證了他們寫入順序?qū)ζ渌€程的可見性（很有迷惑性的一點）
- 但是主線程卻可以讀到 v1=0,v2=1的情況
- 所以情況就是雖然順序?qū)懭肓耍莿e的線程沒有看到正確的順序？
- Intel: 并不是！
- 原因是搞錯了因果關(guān)系，他真正保證的順序是當(dāng)你讀到v2的new value的時候，那么v1也一定被寫入了。
- 解決方案就是互換上面代碼中我用**星號**標(biāo)注出的兩行
- done
在舊寫法中，掛掉的情況是線程1寫入v1 = 1，主線程讀v1，沒有讀到，那么主線程認(rèn)為v1是0，然后線程1繼續(xù)寫入v2，主線程讀到了，主線程認(rèn)為v2是1。 然后掛在了斷言上。
兩行互換后，主線程首先讀取v2，如果v2已經(jīng)是1了，那么v1也一定是1，反之亦然。
0x3
當(dāng)然，想讓跑通那個例子不需要那么多的atomic<>，精簡之后利用c++11的memory_order可以寫成如下：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <atomic>
#include <thread>
using namespace std;
union p64 {
int i;
char padding[64];
long align8;
};
volatile union p64 v1, v2;
atomic<
int> b;
// variable b as a guard
void *
run1()
{
int rcnt = 0;
for (;; rcnt++) {
while (!b.load());
if (v1.i || v2.i) {
puts("assert error 1");
exit(-1);
}
v1.i = 1;
v2.i = 1;
b.store(0, memory_order_release);
}
}
intmain()
{
// init
v1.i = 0;
v2.i = 0;
thread t(run1);
int cnt = 0;
for (;; cnt++) {
v1.i = 0;
v2.i = 0;
b.store(1, memory_order_release);
int icnt = 0;
for (;; icnt++) {
int b2 = b.load(memory_order_acquire);
if (b2 != 0) {
continue;
}
int i1 = v1.i;
int i2 = v2.i;
if (i1 && i2)
break;
if (i1 < i2) {
printf("assert error 2, cnt = %d, icnt = %d, i1 = %d, i2 = %d\n", cnt, icnt, i1, i2);
exit(-1);
}
}
}
return 0;
}
利用變量b在兩個線程之間同步，如下圖
(Thead 1)
v1.i = 1;
v2.i = 1;
b.store(0, memory_order_release) <---+
|
synchronize with b
(happend before)
|
+-----> b.load(memory_order_acquire)
i1 = v1.i
i2 = v2.i
(Thread 2)
我們查看下生成的代碼
g++ -std=c++11 -pthread -g -O2 order.cpp
v1.i = 1;
400be6: c7 05 d0 10 20 00 01 movl $0x1,0x2010d0(%rip) # 601cc0 <v1>
400bed: 00 00 00
v2.i = 1;
400bf0: c7 05 86 10 20 00 01 movl $0x1,0x201086(%rip) # 601c80 <v2>
400bf7: 00 00 00
memory_order __b = __m & __memory_order_mask;
__glibcxx_assert(__b != memory_order_acquire);
__glibcxx_assert(__b != memory_order_acq_rel);
__glibcxx_assert(__b != memory_order_consume);
__atomic_store_n(&_M_i, __i, __m);
400bfa: c7 05 5c 10 20 00 00 movl $0x0,0x20105c(%rip) # 601c60 <b>
400c01: 00 00 00
b.store(0, memory_order_release);
400a58: 8b 05 02 12 20 00 mov 0x201202(%rip),%eax # 601c60 <b>
int b2 = b.load(memory_order_consume);
if (b2 != 0) {
400a5e: 85 c0 test %eax,%eax
400a60: 75 f3 jne 400a55 <main+0x55>
continue;
}
int i1 = v1.i;
400a62: 8b 0d 58 12 20 00 mov 0x201258(%rip),%ecx # 601cc0 <v1>
int i2 = v2.i;
400a68: 44 8b 05 11 12 20 00 mov 0x201211(%rip),%r8d # 601c80 <v2>
看來Intel的Strong Memory Model已經(jīng)保證了這一點，Memory Barrier都不需要了
（雖然標(biāo)題里面有MemoryBarrier，但是內(nèi)容里面根本沒涉及的樣子。。）
posted @
2016-01-19 16:13 右席 閱讀(16776) |
評論 (1) |
編輯 收藏
2015年1月9日
序言
雖然nginx+lua開發(fā)一些小的web服務(wù)簡單快捷，但是由于種種原因，配套的工具比較缺乏，監(jiān)控工具和性能檢測工具等等。而且lua作為一種跑在虛擬機(jī)的腳本語言，雖然做的短小精悍，但是。。。功能和可調(diào)優(yōu)的空間還是欠缺了點。
前段時間使用春哥的systemtap腳本對我的lua服務(wù)做了下性能測試，這里記錄一下折騰的歷程
準(zhǔn)備
systemtap是一個性能檢測和調(diào)試跟蹤的工具，最開始是為了調(diào)試內(nèi)核被做出來的，后來添加了用戶態(tài)跟蹤的功能。
折騰記錄
春哥的腳本要求systemtap2.2以上，公司測試服務(wù)器自帶的systemtap腳本的版本那是1.6，遠(yuǎn)遠(yuǎn)不夠，所以必須手動編譯一個。下載systamtap的源碼，然后./configuare + make就可以直接編了。最開始碰到的問題是公司el5系統(tǒng)的服務(wù)器的elfutil版本太低，得自己編譯一個高版本的elfutil然后指定路徑。。。。我怕麻煩，就把一個空的測試機(jī)器重裝成el6，elfutil的版本立馬就夠了(我真是太機(jī)智了)。
順利編譯出systamtap之后(中途遇到了systemtap版本不夠新導(dǎo)致的符號找不到的bug)，就是tengine的安裝，時間都折騰在這上面了。。。我們項目用的是tengine-ads這個版本，直接用tengine缺少模塊，就請了tengine組的同學(xué)幫忙把模塊給打了進(jìn)去。由于要跟蹤lua內(nèi)部，所以自帶的luajit必須-g編譯。那邊的同學(xué)比較忙，我就只能自己要了服務(wù)器權(quán)限跑上去自己編，編了幾次之后那個測試服務(wù)器竟然磁盤滿了。。。總之就是折騰了一晚上和一早上，終于把帶debuginfo的tengine給裝上了。
效果
啟動tengine服務(wù)，把壓測程序開好，運行
./ngx-sample-lua-bt -p 29237 --luajit20 -t 200 -a '--vp 02 -R /home/wenqian.peiwq/systemtap-2.6/runtime -DSTP_NO_OVERLOAD --all-modules -DMAXSKIPPED=1024 ' > tmp.bt
采樣結(jié)束后，利用brendangregg的FlameGraph tools可以繪制棧調(diào)用的火焰圖，如下：
通過這個圖，先是立馬發(fā)現(xiàn)了一個低級錯誤。。。（上面貼的圖上已經(jīng)沒了），我有很多打印debug的語句，用了這類用法
_log.log("debug", "xxx", util.print_r(some_data))
忘記了lua的求值策略，雖然debug下的這個語句在生產(chǎn)環(huán)境中不執(zhí)行，但是由于求值策略，util.print_r(some_data)仍然會先求值，導(dǎo)致了很大的性能損失，接近1/4。
同時也發(fā)現(xiàn)了UUID的生成所占用的時間也過分的長了一些，然后重寫了這個方法，使用了resty.string庫中的random模塊(直接調(diào)用了ngx_*的C函數(shù))，然后利用systemtap對比了前后的時間，提升了360%多，可見還是很有效果的。
注:
這個項目是基于我上次手?jǐn)]的小框架dodolu，根據(jù)這次的測試結(jié)果，框架的封裝對我的項目造成的性能損失在1%以下。
posted @
2015-01-09 12:03 右席 閱讀(2356) |
評論 (0) |
編輯 收藏
2014年12月22日
背景
前段時間項目需要一個點擊服務(wù)，大致是要根據(jù)用戶請求的url及數(shù)據(jù)庫中的規(guī)則，匹配出一個結(jié)果并記錄日志。最開始是一個很小的需求，結(jié)果業(yè)務(wù)越來越復(fù)雜，業(yè)務(wù)邏輯中經(jīng)常要處理header頭和一些其他的信息，導(dǎo)致代碼越來越混亂。在一期結(jié)束之后，抽時間把這段時間的工作抽象出了一個輕量級框架，只做了適量的封裝，加入了代碼生成的模塊，可以幫助開發(fā)者迅速做出一個可用的web服務(wù)。
介紹
dodolu框架地址(Github)。
該框架只做了最小化的封裝，幾乎沒有性能損失，并提供了根據(jù)配置文件(meta.lua)，自動生成route模塊，nginx.conf配置，logger模塊的功能，減輕了開發(fā)工作量，避免重復(fù)手寫大量易錯的配置或字符串變量，有助于多人開發(fā)統(tǒng)一風(fēng)格。
詳情Github的README
功能
包括三個部分，一個是web框架，一個是代碼自動生成模塊，一個是魔改出的lua遠(yuǎn)程調(diào)試器。
web框架部分
只有1k行以下的代碼，集成了resty.template、resty.cookie、UUID生成等第三方模塊。提供request、response、context、util等庫方便開發(fā)人員使用。
代碼自動生成部分
可自動生成:
- 路由配置
- 日志記錄模塊
- nginx.conf
主要目的在于解決nginx配置與lua代碼的分離問題(在日志記錄中尤為嚴(yán)重)。
開發(fā)人員新建應(yīng)用步驟：在App文件夾下，新建lua文件，然后填入do_get()方法即可處理相應(yīng)的get請求，所有配置在meta/meta.lua里面。
一個記錄日志并返回1x1gif的例子：
-- 這個文件下面存放你的業(yè)務(wù)邏輯
-- 這個文件下面存放你的業(yè)務(wù)邏輯
local app = {}
function app.do_get(ctx)
local response = ctx.response
local request = ctx.request
local cookie = ctx.cookie
response:set_content_type("text/html")
local url = request.uri
--
do some process
------------- write log ---------------
-- my_log 日志模塊是根據(jù)meta.lua自動生成的
local logger = ctx.get_logger('my_log')
local log_data = { a = "xxx"}
logger.write(log_data, other_params
)
-------------
return empty gif -------
response:empty_gif()
response:close()
end
function app.do_post(ctx) end
function app.do_put(ctx) end
function app.do_delete(ctx) end
return app
lua遠(yuǎn)程調(diào)試器
文檔詳細(xì)見這里，這里只演示下用法：
sh debug.sh，然后運行用戶程序，成功后
Lua Remote Debugger
Run the program you wish to debug
Paused at file a.lua
Type 'help' for commands
>
下一步 n
n
Paused at file a.lua line 8
8: print("Start")
>
查看源碼 l
> l
source file: a.lua
2:
3: local tab = {
4: foo = 1,
5: bar = 2
6: }
7:
8:>> print("Start")
9:
10: local bb = require "b"
11: bb.foo()
12:
13: for i = 1, 10 do
14: print("Loop")
設(shè)置斷點 b <file>:<line> 查看 listb
> b a.lua:11
> listb
a.lua: 11
查看局部變量 local
> local
{
["tab"] = {
{
["bar"] = 2,
["foo"] = 1,
},
"table: 0x2589ee0",
},
}
查看變量 p tab
> p tab
{
["bar"] = 2,
["foo"] = 1,
}
繼續(xù)執(zhí)行，直到斷點 r
> r
Paused at file a.lua line 11
posted @
2014-12-22 18:22 右席 閱讀(3353) |
評論 (1) |
編輯 收藏
2014年7月10日
序
函數(shù)式編程語言有很多種定義，寬泛的認(rèn)為支持高階函數(shù)（higher-order function）就算函數(shù)式語言的話，大多數(shù)現(xiàn)代語言都是支持函數(shù)式編程的，例如C/C++，java，C#，lua，python，JavaScript，Scala等等。收緊一下定義的話，加入函數(shù)式語言要求的模式匹配、無副作用等要求，那么剩下的就是純函數(shù)式語言，比較常見的有Haskell，Clean等。
副作用是什么和為什么有些語言想在設(shè)計上避免副作用這個問題，google能搜出好多博文，這里就不多說了。避免副作用可以帶來一些實際的好處，比如幫你大量改寫代碼什么的（誤），而且連gcc都有 _ _ attribute _ _((pure/const))的函數(shù)擴(kuò)展嘛~。比如像erlang這種依賴于副作用編程的語言，雖然有著變量不可變這個特性，但是仍然可以讀寫process攜帶的全局變量，而且又沒有一個好的類型系統(tǒng)，所以在編譯的時候也不會怎么大改你的代碼，大多還是直譯成字節(jié)碼。
注：這篇文章不是**軟文**，不會用個g(f(x))就當(dāng)例子給大家說無副作用多么多么好，可緩存結(jié)果拉(just a lie)~原生支持并行拉(just another lie)，這些都是扯淡而且不實際的。（有機(jī)會再寫個博客專門談?wù)勥@個）
正文
首先，純函數(shù)式的語言強(qiáng)調(diào)沒有副作用，它不會改變?nèi)魏螌嶋H的東西，當(dāng)然也沒有（全局的）狀態(tài)，這樣的程序如果不配上代表副作用的輸入輸出當(dāng)然是什么都干不了的。那么如何把副作用嵌入到本不該有副作用的語言設(shè)計中那？當(dāng)然不能直接賦值，不然。。不然。。就變成命令式語言了，而且函數(shù)式語言編譯中引以為豪的各種優(yōu)化pass幾乎都不能用了。那么把有副作用的函數(shù)標(biāo)注出來？當(dāng)然是一個辦法。還有就是把副作用的表達(dá)式都包含在context中，隨著函數(shù)傳遞，保證順序而且要保證引用的唯一性。
作為純函數(shù)式語言的代表，Haskell和Clean對于副作用的設(shè)計實現(xiàn)上差別很大，下面就簡單說一下它們的實現(xiàn)，刨根究底，其實它們做的還是同一件事情。
haskell
Haskell中有一個很重要的概念：Monad，取名自范疇論，可以粗淺的認(rèn)為它就是定義了一系列的行為準(zhǔn)則（>>= , return）。Haskell中大多數(shù)語法糖都是為了這個發(fā)明來的。Haskell的標(biāo)準(zhǔn)庫中有很多關(guān)于副作用的類庫封裝，比如IORef，MVar，IOMonad等等，他們的內(nèi)部實現(xiàn)都會歸結(jié)到ST Monad（State Thread Monad）上，正是這個與forall關(guān)鍵字的結(jié)合，從而在語法上保證了副作用嵌入在（純）Haskell中的正確性。
ST Monad里面主要的定義是：
newtype ST s a = ST (STRep s a)
type STRep s a = State# s -> (# State# s, a #)
data STRef s a = STRef (MutVar# s a)
runST :: (forall s. ST s a) -> a
runSTRep :: (forall s. STRep s a) -> a
其中最關(guān)鍵的是ST s a 與 STref s a 這兩個數(shù)據(jù)結(jié)構(gòu)。
先看看這個用法，let a0 = runST $ newSTRef 0，會引發(fā)一個type error。因為runST的類型是(forall s.ST s a) -> a ，參數(shù)(newSTRef 0)的類型是forall s. ST s (STRef s Int)，最后求值后的結(jié)果是a0::STRef s Int，顯然s脫離了原本的定義域（也就是那層forall之外，forall是Haskell中提供**RankNType**的關(guān)鍵字）。從而用戶就只能使用下面的方式：
sumST :: Num a => [a] -> a
sumST xs = runST $ do
n <- newSTRef 0
forM_ xs $ \x -> do
modifySTRef n (+x)
readSTRef n
不用標(biāo)出標(biāo)出具體實現(xiàn)，大家就能看出他做的事情就是做了一層wrapper，在type checker上保證被box之后不會被用戶取出來亂改。至于如何做到destructive in-place update，這就屬于編譯器的黑魔法了，語言這層只需保證語義就好。（**注：**ghc的實現(xiàn)中，ST Monad標(biāo)準(zhǔn)庫用到了ghc的unsafe打頭的內(nèi)置函數(shù)）
Clean
Clean語言用的策略是線性類型系統(tǒng)（linear type system），是Substructural type sysytem的一種。在Curry-Howard同構(gòu)中對應(yīng)Substructrual logic。這類類型系統(tǒng)中，不但可以決定一個變量是什么類型，還可以約束被使用的次數(shù)與順序。在Mozilla出的Rust語言中，也可以看到線性類型的影子。
先舉個栗子~
transform :: (Int -> Int) *{#Int} -> *{#Int}
transform f s
| size s == 0 = s
| otherwise = if (s.[0] == 0)
{f i \\ i <-: s}
{f i \\ _ <-: s & i <- [s.[0]..]}
（不要在意奇怪的語法，｛｝里面其實就是list comprehension）
其中*就是uniqueness type的標(biāo)注，這個函數(shù)的類型用haskell寫出來就是transform :: (Int -> Int) -> *[Int] -> *[Int]。這個函數(shù)雖然沒有很好的看出uniqueness type的特性和傳播性，但是作為簡單的例子，差不多就是這么回事。
對于uniqueness type最直觀的理解就是帶有這個標(biāo)識的類型是不能參與到以后Graph Reduction中，而且會檢測會不會有多個“變量”指向他。上面這個函數(shù)中就不會存在多個[Int]及相關(guān)的副本等著被回收，而是會直接在（ReadWorld中的）內(nèi)存上更新數(shù)據(jù)。
最后
其實已經(jīng)看出，在上面Haskell與Clean的做法中，一個是利用forall關(guān)鍵字與ST Monad+編譯器黑魔法，另一個是build-in在類型系統(tǒng)中，但是本質(zhì)都是做了一件事情，就是保證RealWorld中的對象不會存在多個引用，而且在Graph Reduction中不會被編譯器搞亂順序，這樣就能融入到整個純函數(shù)式的大體系中了。
本人博客地址（http://m.shnenglu.com/pwq1989/）
posted @
2014-07-10 15:16 右席 閱讀(4460) |
評論 (1) |
編輯 收藏
摘要: 序類型系統(tǒng)在編程語言中是極為重要，不單單是提供一個類型的標(biāo)注或是方便編譯，更多時候是減少出錯的可能。當(dāng)類型系統(tǒng)強(qiáng)大到一定程度，就可以進(jìn)行所謂的“富類型編程”，比如在Haskell中只要編譯器不報錯，大致上程序也是沒什么bug的。在常用的靜態(tài)類型語言中，C++/java/C#等，雖然在新標(biāo)準(zhǔn)與新版本中支持類型的自動推導(dǎo)，但是對類型系統(tǒng)及其推導(dǎo)還是缺少更為直接的支持。很多常用語...
閱讀全文
posted @
2014-07-10 15:14 右席 閱讀(3465) |
評論 (7) |
編輯 收藏
2014年2月27日
本人博客地址：http://m.shnenglu.com/pwq1989/
昨天在知乎上看到一個評論提到了Haskell的YC實現(xiàn)，就去搜了一下，然后就看到了一個實現(xiàn)：
1 newtype Mu a = Mu (Mu a -> a)
2
3 y :: (a -> a) -> a
4 y f = (\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)
嗯，真是別扭
反觀一下其他語言的YC寫法，就貼一個lua的把
1 Y =
function (f)
2 return function(
)
3 return (
function(x)
return x(x) end)
(
function(x)
return f(
function(y)
return x(x)(y) end) end)(
)
4 end
5 end
雖然看起來很長，但是容易理解的多，用
λ表達(dá)式寫出來就是（wiki）
λf. (λx. f (x x)) (λx. f (x x))
目的就是能做出 Y f = f (Y f) 這種效果，之所以這么寫，是為了不引入名字（引入了名字是惡!）
對于Haskell這種用HM類型系統(tǒng)的語言來說，最大的問題就是不能遞歸的定義類型，同樣是靜態(tài)類型檢查，比如C#，就可以不費力的用Func和delegate做出來，haskell 額，就得扭曲的利用newtype Mu a = Mu (Mu a -> a) 來繞過類型檢查（當(dāng)然，這個在Haskell中是不可能構(gòu)造出一個實際的值的）。
看下他是怎么做的，我們來把他展開一下：
原式子：y f = (\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)
帶進(jìn)去：y f = (\x -> f . (\(Mu g) -> g) x $ x) $ Mu (\x -> f . (\(Mu g) -> g) x $ x)
再來一遍：y f = f . (\x -> f . (\(Mu g) -> g) x $ x) $ Mu (\x -> f . (\(Mu g) -> g) x $ x)
這樣子，最后那個式子的f. 后面的那部分，提取 (\x -> f . (\(Mu g) -> g) x $ x) 這個公因式 就相當(dāng)于是(\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)了（很像數(shù)學(xué)把，但也沒多大關(guān)系）
最后，就可以做出y f = f . (y f)了。
其實這個寫法最關(guān)鍵的是 newtype Mu a = Mu (Mu a -> a)的作用，他是如何繞過類型檢查，但是又不在運行期構(gòu)造一個值（想構(gòu)造也構(gòu)造不出來）。
來看下他的類型推導(dǎo)過程，y的類型是y :: (a -> a) -> a，所以里面f就是 f :: a -> a，所以f . (\(Mu g) -> g) x $ x 這個式子可以推出里面的x是 x :: Mu a 然后(\(Mu g) -> g) x 取出里面的 a，這樣就成了
f
a $ Mu a，這時候Mu a = Mu (Mu a -> a) 遞歸定義的作用就發(fā)揮了，為了類型的推導(dǎo)，繼續(xù)將那個紅色的a 推導(dǎo)成 Mu a -> a，這樣 f (Mu a -> a) 會返回一個Mu a -> a，管他叫f'把，這樣 f' (Mu a) 就返回一個 a。有根據(jù)前面的(\h -> h $ Mu h) 繼續(xù)講上面提到的a變成 Mu a -> a。就是把Mu a 喂給了 (Mu a -> a)，最后還是返回一個a。
(>_< 其實上面這段是我編出來的，我編不下去了，我不知道ghc是怎么做這個事情的，等我有生之年看完slpj-book-1987再想想)我們來應(yīng)用一下，返回一個階乘：
y (\f n -> if n <= 1 then 1 else n * f (n - 1)) 5。
不難看出，最終y的類型被特化成了 ((Int -> Int) -> (Int -> Int)) -> (Int -> Int)
posted @
2014-02-27 00:25 右席 閱讀(2290) |
評論 (5) |
編輯 收藏
2014年1月8日
本人博客地址：
http://m.shnenglu.com/pwq1989/ 今天群里姐夫推薦了個C++的Actor框架 Theron，就看了下源碼，注釋比代碼還多，業(yè)界良心。
源碼我還沒看完，就看到了他的一個叫StringPool的類，里面通過Ref來生成單例（Singleton），看了下
static void Reference();這個函數(shù)實現(xiàn)的時候，突然腦洞一開，為啥沒有Memory Barrier(
wiki)。
先貼一下他的代碼：
1 StringPool *StringPool::smInstance = 0;
2 Mutex StringPool::smReferenceMutex;
3 uint32_t StringPool::smReferenceCount = 0;
4
5
6 void StringPool::Reference()
7 {
8 Lock lock(smReferenceMutex);
9
10 // Create the singleton instance if this is the first reference.
11 if (smReferenceCount++ == 0)
12 {
13 IAllocator *const allocator(AllocatorManager::GetCache());
14 void *const memory(allocator->AllocateAligned(sizeof(StringPool), THERON_CACHELINE_ALIGNMENT));
15 smInstance = new (memory) StringPool();
16 }
17 }
我們先不討論這一段代碼，先看看下面的：
大家如果看過C++的Double Check Lock不可靠的這篇paper(
地址)，作者給出的解決方案是這樣的：
1 // First check
2 TYPE* tmp = instance_;
3 // Insert the CPU-specific memory barrier instruction
4 // to synchronize the cache lines on multi-processor.
5 asm ("memoryBarrier");
6 if (tmp == 0) {
7 // Ensure serialization (guard
8 // constructor acquires lock_).
9 Guard<LOCK> guard (lock_);
10 // Double check.
11 tmp = instance_;
12 if (tmp == 0) {
13 tmp = new TYPE;
14 // Insert the CPU-specific memory barrier instruction
15 // to synchronize the cache lines on multi-processor.
16 asm ("memoryBarrier");
17 instance_ = tmp;
18 }
19 return tmp;
其實這兩個Memory Barrier不用全屏障，第一個用讀屏障rmb()就好了。第二個需要一個寫屏障wmb()。
我們都知道m(xù)b這個東西是為了防止CPU級別的指令亂序被發(fā)明出來的，（另一個是編譯器級別的，和本篇文章沒有多大關(guān)系，有興趣大家可以去研究下），實現(xiàn)也是由平臺相關(guān)的特殊指令(mfence這樣的)組成的。
之所以要寫成這樣，第二個mb()是為了防止在構(gòu)造函數(shù)完成之前提前對目標(biāo)賦值，但ctor還沒完成，就被掛起，然后第二個線程訪問的時候，認(rèn)為已經(jīng)構(gòu)造完畢，進(jìn)而使用不完整的數(shù)據(jù)引發(fā)奇怪的錯誤。
(第一個rmb()的作用我覺得是可有可無，加上可能是為了效率把（猜），強(qiáng)制刷新讀取instance_的值，防止進(jìn)入第一個check去競爭那個鎖，不加也是不會有錯的，因為POSIX規(guī)定mutex之間必須保持內(nèi)存的可見性，所以是不需要擔(dān)心讀到臟數(shù)據(jù)) <-- 這段是個人意見，歡迎修正。
下面就是我趴了半下午才想明白的問題。。。為啥Theron中那段代碼（第一段代碼）不需要在lock中添加mb()，后來往下翻了下，發(fā)現(xiàn)StringPool的構(gòu)造函數(shù)是空的。。根本就沒有內(nèi)存的寫入，當(dāng)然就不需要wmb()了。
可見，C++的多線程編程，好難
posted @
2014-01-08 00:54 右席 閱讀(5048) |
評論 (0) |
編輯 收藏
2013年11月30日
本人博客地址：
http://m.shnenglu.com/pwq1989/上一篇對Luajit的代碼結(jié)構(gòu)和編譯過程做了簡單的描述，這一篇就講一下buildvm在第一步預(yù)處理dasc文件的過程和DynASM這個輪子。
官方連接：
http://luajit.org/dynasm.html是為了讓你更優(yōu)雅的C里面擼匯編的一個工具，我記得以前看過一個老外的blog對比過同樣功能的jit code generator的語法，Luajit的作者顯然品位還是很高的。
我們先來看看如果不用工具硬生生擼代碼的話會發(fā)生什么。
1、你往一段內(nèi)存里面寫0xB8,0x00,0x01....
2、你在文件里定義好多l(xiāng)abel，寫個copy section的宏往內(nèi)存里面復(fù)制，你還不能確定里面到底是什么。（哦。。這個的術(shù)語叫Threaded。。。）
然后再對比下
AsmJit或者
Xbyak的例子看看（他們的功能差不多），DynASM還提供了.marco實現(xiàn)，就會發(fā)現(xiàn)語法真是sweeeet~
這是我寫著玩的一個草泥馬語jit解釋器（
https://github.com/pwq1989/GMHjit）語法真是清新自然啊，如果你想看工業(yè)級的應(yīng)用，可以看看Google的Haberman寫的protobuf的upb庫，里面用DynASM進(jìn)行了jit，號稱快了多少多少（不去考證了），或者是agentzh寫的sregex正則庫，也是用它做了jit。一般來說DSL配上jit的話一定會快很多就錯不了了。
下面給一個DynASM的Demo程序（摘抄自
這個blog）
1 // DynASM directives.
2 |.arch x64
3 |.actionlist actions
4
5 // This define affects "|" DynASM lines. "Dst" must
6 // resolve to a dasm_State** that points to a dasm_State*.
7 #define Dst &state
8
9 int main(int argc, char *argv[]) {
10 if (argc < 2) {
11 fprintf(stderr, "Usage: jit1 <integer>\n");
12 return 1;
13 }
14
15 int num = atoi(argv[1]);
16 dasm_State *state;
17 initjit(&state, actions);
18
19 // Generate the code. Each line appends to a buffer in
20 // "state", but the code in this buffer is not fully linked
21 // yet because labels can be referenced before they are
22 // defined.
23 //
24 // The run-time value of C variable "num" is substituted
25 // into the immediate value of the instruction.
26 | mov eax, num
27 | ret
28
29 // Link the code and write it to executable memory.
30 int (*fptr)() = jitcode(&state);
31
32 // Call the JIT-ted function.
33 int ret = fptr();
34 assert(num == ret);
35
36 // Free the machine code.
37 free_jitcode(fptr);
38
39 return ret;
40 }
預(yù)處理之后那就會變成這樣子：
1 //|.arch x64
2 //|.actionlist actions
3 static const unsigned
char actions[4] = {
4 184,237,195,255
5 };
6 7 // []
8
9 //| mov eax, num
10 //| ret
11 dasm_put(Dst, 0, num);
dasm_put就是把num參數(shù)和actions[]一起放入了Dst（#define Dst &state）的制定的內(nèi)存中，這時候已經(jīng)是機(jī)器碼的形式了。
下面是對于acitons[]數(shù)組內(nèi)容的解釋：
184(B8)-- mov eax, [immediate] 指令的第一個字節(jié)
237 -- 內(nèi)置的標(biāo)志DASM_IMM_D, 指明應(yīng)該放入一個4字節(jié)寬度的參數(shù)，與上一條指令完成一個MOV
195(C3)-- 對應(yīng)ret指令
255 -- 內(nèi)置的標(biāo)志DASM_STOP
以上就是最簡單的例子，dasm_growpc()是內(nèi)置的函數(shù)，用來增長maxpc, 這樣在程序里面就可以方便寫出jmp => label 這樣的指令了。
由于DynASM的文檔很少，幸虧還有幾個例子，除了例子唯一能看的就是源碼了，所以在用的時候出現(xiàn)問題是很痛苦的。。當(dāng)時寫GMHjit就發(fā)現(xiàn)了蛋疼的pre-process period bug，后來繞過去了。
源碼文件有這么幾個
-- dynasm.lua
-- dynasm_proto.h
-- dynasm_*.lua
-- dynasm_*.h // * x64 x86 ppc mips arm 等target
用起來就是lua dynasm.lua a.dasm > a.h
下面就從dynasm.lua開始分析下他的源碼
入口是parseargs函數(shù)，里面給的g_opt參數(shù)賦默認(rèn)的值，一個repeat 中調(diào)用parseopt解析參數(shù)，opt_map就是option對args的函數(shù)映射。
函數(shù)wline，wcomment，wsync，wdumplines都是對輸出的目標(biāo)文件的操作。
真正的主函數(shù)是 translate，把input file變成 output file，在readfile中的doline函數(shù)是真正的處理過程，里面判斷是否是Assembler line之后Emit C code，調(diào)用dostmt(aline)。里面繼續(xù)有map_coreop[*]來處理section macro arch nop_ error_1 include if endif elseif 等關(guān)鍵字，想深入研究的可以自己去看，其中在loadarch中根據(jù)arch加載不同的lua庫
如果arch是x64的話，本質(zhì)還是require x86
來看dasm_x86.lua文件
_M.mergemaps這是關(guān)鍵的方法，設(shè)置了2個Map的元方法，然后返回，相當(dāng)于是把方法綁定在table里面?zhèn)鬟f了出去。處理后文件中關(guān)鍵的actionlist[]數(shù)組和Dasm_put(Dst, ...)的輸出就是這個lua文件的方法。
里面提供了很多dump方法，可以供我們遇到問題時候調(diào)試處理過程。
action_names就是以后生成的action_list中的內(nèi)置標(biāo)志定義，必須與dasm_x86.h中的enum定義一致。
表明了代表的參數(shù)和長度等信息。
這個文件里面所有的函數(shù)就是做了一件事，把你的 |... 這樣子的代碼處理成數(shù)組輸出到目標(biāo)文件中（我是匯編渣渣，里面貌似支持SSE2、3、4+，看不懂，等到以后看到traced jit的時候再去翻手冊把）
預(yù)處理完成之后，就是#include "dasm_x86.h"，里面有最關(guān)鍵的dasm_State結(jié)構(gòu)體的定義，幾乎里面所有的函數(shù)都是對外的API，有init,setup,free等等，除去初始化與free之外，有三個步驟是需要出現(xiàn)在你都代碼中：
1、dasm_put(Dst,...) 這個是自動生成的，不用我們操心，根據(jù)actionlist[]和運行時的參數(shù)寫入到Dst指定的內(nèi)存（Dst->section）中.
2、dasm_link() 第二個參數(shù)是返回的代碼長度大小，這個函數(shù)把section合并到一起，處理偏移等等。
3、dasm_encode() 第二個參數(shù)是一個接受encode輸出的buffer指針。
然后就可以用一個函數(shù)指針，比如聲明一個 int (*f)(*int), int ret = f(param) 直接運行剛剛生成的機(jī)器碼了。
posted @
2013-11-30 12:49 右席 閱讀(7192) |
評論 (0) |
編輯 收藏
2013年11月28日
本人博客地址：
http://m.shnenglu.com/pwq1989/第一篇對Luajit做一個大概的介紹，我目前也正在慢慢的讀通源碼中，以后發(fā)現(xiàn)了新東西就補(bǔ)充在這里。
大家可以從官網(wǎng)下載到源碼（
http://luajit.org/），也可以從Github（
https://github.com/LuaDist/luajit）down下來，順便還可以看下commit記錄。
大家對著luajit的wiki結(jié)合源碼看的話會更好些，因為。。文檔太特么少了！！
目錄結(jié)構(gòu)：
-- src
-- host
-- jit
*.c
*.h
*.dasc
等等，別的不是很重要
最開始我是從main函數(shù)開始看的，然后。。碰了一鼻子灰，后來研究下他的makefile，發(fā)現(xiàn)他是這樣子的編譯的，貼一下關(guān)鍵的msvcbuild.bat的代碼（這個更容易看懂）
1 :X64
2 minilua %DASM% -LN %DASMFLAGS% -o host\buildvm_arch.h vm_x86.dasc
3 @if errorlevel 1 goto :BAD
4
5 %LJCOMPILE% /I "." /I %DASMDIR% host\buildvm*.c
6 @if errorlevel 1 goto :BAD
7 %LJLINK% /out:buildvm.exe buildvm*.obj
8 @if errorlevel 1 goto :BAD
9 if exist buildvm.exe.manifest^
10 %LJMT% -manifest buildvm.exe.manifest -outputresource:buildvm.exe
11
12 buildvm -m peobj -o lj_vm.obj
13 @if errorlevel 1 goto :BAD
14 buildvm -m bcdef -o lj_bcdef.h %ALL_LIB%
15 @if errorlevel 1 goto :BAD
16 buildvm -m ffdef -o lj_ffdef.h %ALL_LIB%
17 @if errorlevel 1 goto :BAD
18 buildvm -m libdef -o lj_libdef.h %ALL_LIB%
19 @if errorlevel 1 goto :BAD
20 buildvm -m recdef -o lj_recdef.h %ALL_LIB%
21 @if errorlevel 1 goto :BAD
22 buildvm -m vmdef -o jit\vmdef.lua %ALL_LIB%
23 @if errorlevel 1 goto :BAD
24 buildvm -m folddef -o lj_folddef.h lj_opt_fold.c
25 @if errorlevel 1 goto :BAD
先創(chuàng)建了一個buildvm.exe的中間工具，來自動生成代碼，分別生成了
lj_vm.obj，lj_bcdef.h，lj_ffdef.h ，lj_recdef.h ，jit\vmdef.lua，lj_folddef.h， lj_libdef.h
其中l(wèi)v_vm.obj是依賴于
host\buildvm_arch.h的，這個是用DynASM預(yù)處理vm_x86.dasc生成的，這個工具的具體分析會在下一篇博客提及。
先來看下上面自動生成的代碼：
lj_bcdef.h:
1 LJ_DATADEF
const uint16_t lj_bc_ofs[] = {
2 0,
3 71,
4 142,
5 213,
6 284,
7
8 };
9
10 LJ_DATADEF
const uint16_t lj_bc_mode[] = {
11 BCDEF(BCMODE)
12 BCMODE_FF,
13 BCMODE_FF,
14 BCMODE_FF,
15 BCMODE_FF,
16 BCMODE_FF,
17
18 };
lj_bc_ofs[]可能是bc在vm代碼段中的偏移量（這個我還沒深入進(jìn)去調(diào)試一下），vm的一部分是用DynASM直接擼匯編擼出來的，wiki中也有提到下一步j(luò)it化的opcode等等。
lj_bc_mode[]的用來根據(jù)壓縮后的bytecode構(gòu)造，分離出操作數(shù)，第一行的兩個宏的定義是
#define BCMODE(name, ma, mb, mc, mm) \
(BCM##ma|(BCM##mb<<3)|(BCM##mc<<7)|(MM_##mm<<11)),
#define BCMODE_FF
0
#define BCDEF(_) \
/* Comparison ops. ORDER OPR. */ \
_(ISLT, var, ___, var, lt) \
_(ISGE, var, ___, var, lt) \
_(ISLE, var, ___, var, le) \
_(ISGT,
var,
___,
var,
le) \
...
總之就是充斥著各種拼接起來的宏
lj_ffdef.h:
1 FFDEF(assert)
2 FFDEF(type)
3 FFDEF(next)
4 FFDEF(pairs)
5 FFDEF(ipairs_aux)
6 FFDEF的定義是在
1 /* Fast function ID. */
2 typedef enum {
3 FF_LUA_ = FF_LUA, /* Lua function (must be 0). */
4 FF_C_ = FF_C, /* Regular C function (must be 1). */
5 #define FFDEF(name) FF_##name,
6 #include "lj_ffdef.h"
7 FF__MAX
8 } FastFunc;
差不多就是用FF_##name把上面的名字拼接起來，然后生成在enum里面，這樣就能當(dāng)成是數(shù)字，在數(shù)組中迅速找到入口了
vmdef.lua:
這個里面內(nèi)容就不貼了，包括bcname,irname,irfpm,irfield,ircall 的定義，在jit文件夾下面，用于調(diào)試等，比如在dump.lua中就有用到
local jit = require("jit")
assert(jit.version_num == 20002, "LuaJIT core/library version mismatch")
local jutil = require("jit.util")
local vmdef = require("jit.vmdef") // ← ← ← ←
當(dāng)你用luajit -jdump的時候，就是調(diào)用的lua的jit庫里面的lua函數(shù)
lj_recdef.h:
1 static const uint16_t recff_idmap[] = {
2 0,
3 0x0100,
4 0x0200,
5 0x0300,
6 0,
7 0,
8 0x0400,
9 10 };
11 12 static const RecordFunc recff_func[] = {
13 recff_nyi,
14 recff_c,
15 recff_assert,
16 recff_type,
17 recff_ipairs_aux,
18 19 };
其中recff_func[]是被注冊的被traced jit 跟蹤的函數(shù)，具體可是在lj_ffrecord.c里面看到
recff_idmap[]被用在lj_ffrecord_func這個函數(shù)中，有一個關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)RecordFFData，用來記錄在trace過程中被調(diào)用函數(shù)的參數(shù)和返回值個數(shù)，和一些輔助數(shù)據(jù)，opcode，literal等等。通過recff_idmap[]保存的值來區(qū)分函數(shù)（待仔細(xì)研究）
lj_folddef.h:
1 static const FoldFunc fold_func[] = {
2 fold_kfold_numarith,
3 fold_kfold_ldexp,
4 fold_kfold_fpmath,
5 fold_kfold_numpow,
6 7 };
8 9 static const uint32_t fold_hash[916] = {
10 0xffffffff,
11 0xffffffff,
12 0x5b4c8016,
13 14 };
用在FOLD optimization中，見lj_opt_fold.c，主要在
1 if ((fh & 0xffffff) == k || (fh = fold_hash[h+1], (fh & 0xffffff) == k)) {
2 ref = (IRRef)tref_ref(fold_func[fh >> 24](J));
3 if (ref != NEXTFOLD)
4 break;
5 }
是根據(jù)數(shù)組偏移獲取函數(shù)，直接執(zhí)行。
（這個Optimation略復(fù)雜，以后的博文中再說）
----------------------------------------分割線-------------------------------------------
以上就是buildvm生成代碼，在很多.c的文件中，他加入了一些無意義的MARCO，目的是為了能被buildvm識別出
下面說說src根目錄下面的文件：
lauxlib.h：
用戶開發(fā)擴(kuò)展和與C交互的時候的頭文件
lib_*.h /.c:
顧名思義，就是利用LuaAPI寫的內(nèi)部標(biāo)準(zhǔn)庫，會在方法上表明是否會被trace ( LJLIB_REC(.) )。
ljamalg.c:
文件的合并
lj_alloc.h /.c:
定制的Memory Allocator
lj_api.c:
Public Lua/C API.
lj_arch.h:
Target architecture selection
lj_jit.h:
jit編譯器里面數(shù)據(jù)結(jié)構(gòu)的定義
lj_asm.h/ .c lj_asm_*.c lj_emit_*.h lj_target_*.h/.c :
將IR編譯成Machine Code，關(guān)鍵的數(shù)據(jù)結(jié)構(gòu)ASMState，線性掃描的O(n2)分配算法
lj_bc.h/ .c：
Luajit字節(jié)碼的定義和內(nèi)存布局
lj_bcdump.c lj_bcread.c lj_bcwrite.c:
圍繞著字節(jié)碼的操作
lj_carith.c:
C實現(xiàn)的一些數(shù)字運算
lj_ccall.h/ .c lj_ccallback.h / .c :
FFI C語言函數(shù)調(diào)用和回調(diào)綁定
lj_debug.h/.c :
調(diào)試與自省用
lj_def.h:
這個很重要，重要的類型和一些宏定義在這里
lj_c*.h/ .c:
和C語言先關(guān)的，比如類型轉(zhuǎn)化，char管理，數(shù)據(jù)管理
lj_frame.h:
Luajit的棧幀管理
lj_func.h/.c:
Function handle和閉包有關(guān)的upvalue數(shù)據(jù)結(jié)構(gòu)
lj_gc.h/.c:
GC相關(guān)，GC可以看下luajit的wiki，里面涉及不少增量式GC的paper和作者的看法
lj_gdbjit.h/.c :
對gdb的支持
lj_ir*.h/.c:
SSA，IR相關(guān)（這個和bytecode還是不一樣的）操作和優(yōu)化
lj_lex.h/.c lj_parse.h/.c:
lexer和parser
lj_mcode.h/.c:
Machine Code管理
lj_opt_*.h:
各種bytecode層面上的優(yōu)化
lj_snap.h/.c:
快照支持
lj_state.h/.c:
LuaState和Stack的操作
lj_str*.h/.c lj_tab.h/.c:
原生類型string和table操作
lj_udata.h/.c:
類型user data的操作
lj_vm.h/.c lj_vmevent.h/.c:
vm的API和事件注冊（lj_vmevent_send）
lj_vmmath.h/.c：
對vm支持的math庫
lua.h:
luaState等基本的Lua結(jié)構(gòu)
lualib.h:
和Lua一樣，標(biāo)準(zhǔn)庫的API
luajit.h:
luajit 的public API
vm_*.dasc:
編譯期被DynASM預(yù)處理的源文件，下一篇講DynASM時候介紹dasc文件
wmain.c:
windows下面的main入口
和Trace相關(guān)的：
lj_crecord.h/.c ： C操作的trace record
lj_dispatch.h/.c : 指令分發(fā)，調(diào)用ASMFuction，處理指令前的hook和記錄trace用的hot count，有一個重要的數(shù)據(jù)結(jié)構(gòu) GG_State
lj_ff*.h/.c: 上面講lj_ffdef.h的時候提過，trace的時候 記錄Fast Function的調(diào)用記數(shù)
lj_trace.h/.c: trace的具體過程
lj_traceerr.h : trace error
posted @
2013-11-28 19:23 右席 閱讀(12634) |
評論 (4) |
編輯 收藏