posts - 9,  comments - 19,  trackbacks - 0
  2016年1月19日

0x0

前些天组里老司机@梁希在jvm的项目榨干机器性能之余,为了检查下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乱序执行中保证真实的load/store顺序的指令

0x1
老司机写了一个小程序(注:有误版)
// 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; 
    }
}

int
main()
{
    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.iv2.ib ,起了2个线程,一个顺序写入v1和v2,一个读v1和v2,互相通过改变b的值来通讯,然后两个线程不停循环。

这个程序会挂在
printf("assert error, cnt = %d, icnt = %d, i1 = %d, i2 = %d\n", cnt, icnt, i1, i2); 
这条断言上,意思是线程1在顺序写入v1和v2,但是主线程却出现读到 v1=0,v2=1的情况。

0x2

然后我帮忙去看了一下,觉得这种写法甚是粗暴,于是原样照搬了一个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);
    }
}

int
main()
{
    // 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也保证了他们写入顺序对其他线程的可见性(很有迷惑性的一点)
  • 但是主线程却可以读到 v1=0,v2=1的情况
  • 所以情况就是虽然顺序写入了,但是别的线程没有看到正确的顺序?
  • Intel: 并不是!
  • 原因是搞错了因果关系,他真正保证的顺序是当你读到v2的new value的时候,那么v1也一定被写入了。
  • 解决方案就是互换上面代码中我用**星号**标注出的两行
  • done

在旧写法中,挂掉的情况是线程1写入v1 = 1,主线程读v1,没有读到,那么主线程认为v1是0,然后线程1继续写入v2,主线程读到了,主线程认为v2是1。 然后挂在了断言上。

两行互换后,主线程首先读取v2,如果v2已经是1了,那么v1也一定是1,反之亦然。

0x3

当然,想让跑通那个例子不需要那么多的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);
    }
}
int
main()
{
    // 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已经保证了这一点,Memory Barrier都不需要了

(虽然标题里面有MemoryBarrier,但是内容里面根本没涉及的样子。。)

posted @ 2016-01-19 16:13 右席 阅读(16709) | 评论 (1)编辑 收藏
  2015年1月9日

序言

虽然nginx+lua开发一些小的web服务简单快捷,但是由于种种原因,配套的工具比较缺乏,监控工具和性能检测工具等等。而且lua作为一种跑在虚拟机的脚本语言,虽然做的短小精悍,但是。。。功能和可调优的空间还是欠缺了点。

前段时间使用春哥的systemtap脚本对我的lua服务做了下性能测试,这里记录一下折腾的历程

准备

systemtap是一个性能检测和调试跟踪的工具,最开始是为了调试内核被做出来的,后来添加了用户态跟踪的功能。

折腾记录

春哥的脚本要求systemtap2.2以上,公司测试服务器自带的systemtap脚本的版本那是1.6,远远不够,所以必须手动编译一个。下载systamtap的源码,然后./configuare + make就可以直接编了。最开始碰到的问题是公司el5系统的服务器的elfutil版本太低,得自己编译一个高版本的elfutil然后指定路径。。。。我怕麻烦,就把一个空的测试机器重装成el6,elfutil的版本立马就够了(我真是太机智了)。

顺利编译出systamtap之后(中途遇到了systemtap版本不够新导致的符号找不到的bug),就是tengine的安装,时间都折腾在这上面了。。。我们项目用的是tengine-ads这个版本,直接用tengine缺少模块,就请了tengine组的同学帮忙把模块给打了进去。由于要跟踪lua内部,所以自带的luajit必须-g编译。那边的同学比较忙,我就只能自己要了服务器权限跑上去自己编,编了几次之后那个测试服务器竟然磁盘满了。。。总之就是折腾了一晚上和一早上,终于把带debuginfo的tengine给装上了。

效果

启动tengine服务,把压测程序开好,运行

./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 

采样结束后,利用brendangregg的FlameGraph tools可以绘制栈调用的火焰图,如下:

flamegraph

通过这个图,先是立马发现了一个低级错误。。。(上面贴的图上已经没了),我有很多打印debug的语句,用了这类用法

_log.log("debug", "xxx", util.print_r(some_data)) 

忘记了lua的求值策略,虽然debug下的这个语句在生产环境中不执行,但是由于求值策略,util.print_r(some_data)仍然会先求值,导致了很大的性能损失,接近1/4。

同时也发现了UUID的生成所占用的时间也过分的长了一些,然后重写了这个方法,使用了resty.string库中的random模块(直接调用了ngx_*的C函数),然后利用systemtap对比了前后的时间,提升了360%多,可见还是很有效果的。

注:

这个项目是基于我上次手撸的小框架dodolu,根据这次的测试结果,框架的封装对我的项目造成的性能损失在1%以下。

posted @ 2015-01-09 12:03 右席 阅读(2295) | 评论 (0)编辑 收藏
  2014年12月22日

背景

前段时间项目需要一个点击服务,大致是要根据用户请求的url及数据库中的规则,匹配出一个结果并记录日志。最开始是一个很小的需求,结果业务越来越复杂,业务逻辑中经常要处理header头和一些其他的信息,导致代码越来越混乱。在一期结束之后,抽时间把这段时间的工作抽象出了一个轻量级框架,只做了适量的封装,加入了代码生成的模块,可以帮助开发者迅速做出一个可用的web服务。

介绍

dodolu框架地址(Github)。

该框架只做了最小化的封装,几乎没有性能损失,并提供了根据配置文件(meta.lua),自动生成route模块,nginx.conf配置,logger模块的功能,减轻了开发工作量,避免重复手写大量易错的配置或字符串变量,有助于多人开发统一风格。

详情Github的README

功能

包括三个部分,一个是web框架,一个是代码自动生成模块,一个是魔改出的lua远程调试器

web框架部分

只有1k行以下的代码,集成了resty.template、resty.cookie、UUID生成等第三方模块。提供request、response、context、util等库方便开发人员使用。

代码自动生成部分

可自动生成:

  1. 路由配置
  2. 日志记录模块
  3. nginx.conf

主要目的在于解决nginx配置与lua代码的分离问题(在日志记录中尤为严重)。

开发人员新建应用步骤:在App文件夹下,新建lua文件,然后填入do_get()方法即可处理相应的get请求,所有配置在meta/meta.lua里面。

一个记录日志并返回1x1gif的例子:

-- 这个文件下面存放你的业务逻辑
-- 这个文件下面存放你的业务逻辑
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 日志模块是根据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远程调试器

文档详细见这里,这里只演示下用法:
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")


设置断点   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,
}
继续执行,直到断点  r
> r Paused at file a.lua line 11


posted @ 2014-12-22 18:22 右席 阅读(3249) | 评论 (1)编辑 收藏
  2014年7月10日

函数式编程语言有很多种定义,宽泛的认为支持高阶函数(higher-order function)就算函数式语言的话,大多数现代语言都是支持函数式编程的,例如C/C++,java,C#,lua,python,JavaScript,Scala等等。收紧一下定义的话,加入函数式语言要求的模式匹配、无副作用等要求,那么剩下的就是纯函数式语言,比较常见的有Haskell,Clean等。

副作用是什么和为什么有些语言想在设计上避免副作用这个问题,google能搜出好多博文,这里就不多说了。避免副作用可以带来一些实际的好处,比如帮你大量改写代码什么的(误),而且连gcc都有 _ _ attribute _ _((pure/const))的函数扩展嘛~。比如像erlang这种依赖于副作用编程的语言,虽然有着变量不可变这个特性,但是仍然可以读写process携带的全局变量,而且又没有一个好的类型系统,所以在编译的时候也不会怎么大改你的代码,大多还是直译成字节码。

注:这篇文章不是**软文**,不会用个g(f(x))就当例子给大家说无副作用多么多么好,可缓存结果拉(just a lie)~原生支持并行拉(just another lie),这些都是扯淡而且不实际的。(有机会再写个博客专门谈谈这个)

正文

首先,纯函数式的语言强调没有副作用,它不会改变任何实际的东西,当然也没有(全局的)状态,这样的程序如果不配上代表副作用的输入输出当然是什么都干不了的。那么如何把副作用嵌入到本不该有副作用的语言设计中那?当然不能直接赋值,不然。。不然。。就变成命令式语言了,而且函数式语言编译中引以为豪的各种优化pass几乎都不能用了。那么把有副作用的函数标注出来?当然是一个办法。还有就是把副作用的表达式都包含在context中,随着函数传递,保证顺序而且要保证引用的唯一性。

作为纯函数式语言的代表,Haskell和Clean对于副作用的设计实现上差别很大,下面就简单说一下它们的实现,刨根究底,其实它们做的还是同一件事情。

haskell

Haskell中有一个很重要的概念:Monad,取名自范畴论,可以粗浅的认为它就是定义了一系列的行为准则(>>= , return)。Haskell中大多数语法糖都是为了这个发明来的。Haskell的标准库中有很多关于副作用的类库封装,比如IORef,MVar,IOMonad等等,他们的内部实现都会归结到ST Monad(State Thread Monad)上,正是这个与forall关键字的结合,从而在语法上保证了副作用嵌入在(纯)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

其中最关键的是ST s a 与 STref s a 这两个数据结构。

先看看这个用法,let a0 = runST $ newSTRef 0,会引发一个type error。因为runST的类型是(forall s.ST s a) -> a ,参数(newSTRef 0)的类型是forall s. ST s (STRef s Int),最后求值后的结果是a0::STRef s Int,显然s脱离了原本的定义域(也就是那层forall之外,forall是Haskell中提供**RankNType**的关键字)。从而用户就只能使用下面的方式:

sumST :: Num a => [a] -> a
sumST xs = runST $ do          
    n <- newSTRef 0             
    forM_ xs $ \x -> do        
    modifySTRef n (+x)     
    readSTRef n     

不用标出标出具体实现,大家就能看出他做的事情就是做了一层wrapper,在type checker上保证被box之后不会被用户取出来乱改。至于如何做到destructive in-place update,这就属于编译器的黑魔法了,语言这层只需保证语义就好。(**注:**ghc的实现中,ST Monad标准库用到了ghc的unsafe打头的内置函数)

Clean

Clean语言用的策略是线性类型系统(linear type system),是Substructural type sysytem的一种。在Curry-Howard同构中对应Substructrual logic。这类类型系统中,不但可以决定一个变量是什么类型,还可以约束被使用的次数与顺序。在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的标注,这个函数的类型用haskell写出来就是transform :: (Int -> Int) -> *[Int] -> *[Int]。这个函数虽然没有很好的看出uniqueness type的特性和传播性,但是作为简单的例子,差不多就是这么回事。
对于uniqueness type最直观的理解就是带有这个标识的类型是不能参与到以后Graph Reduction中,而且会检测会不会有多个“变量”指向他。上面这个函数中就不会存在多个[Int]及相关的副本等着被回收,而是会直接在(ReadWorld中的)内存上更新数据。

最后

其实已经看出,在上面Haskell与Clean的做法中,一个是利用forall关键字与ST Monad+编译器黑魔法,另一个是build-in在类型系统中,但是本质都是做了一件事情,就是保证RealWorld中的对象不会存在多个引用,而且在Graph Reduction中不会被编译器搞乱顺序,这样就能融入到整个纯函数式的大体系中了。


本人博客地址(http://www.cppblog.com/pwq1989/)
posted @ 2014-07-10 15:16 右席 阅读(4396) | 评论 (1)编辑 收藏
     摘要: 序类型系统在编程语言中是极为重要,不单单是提供一个类型的标注或是方便编译,更多时候是减少出错的可能。当类型系统强大到一定程度,就可以进行所谓的“富类型编程”,比如在Haskell中只要编译器不报错,大致上程序也是没什么bug的。在常用的静态类型语言中,C++/java/C#等,虽然在新标准与新版本中支持类型的自动推导,但是对类型系统及其推导还是缺少更为直接的支持。很多常用语...  阅读全文
posted @ 2014-07-10 15:14 右席 阅读(3293) | 评论 (7)编辑 收藏
  2014年2月27日
本人博客地址:http://www.cppblog.com/pwq1989/ 

昨天在知乎上看到一个评论提到了Haskell的YC实现,就去搜了一下,然后就看到了一个实现:
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
虽然看起来很长,但是容易理解的多,用λ表达式写出来就是(wiki
λf. (λx. f (x x)) (λx. f (x x))
目的就是能做出 Y f = f (Y f) 这种效果,之所以这么写,是为了不引入名字(引入了名字是恶!)

对于Haskell这种用HM类型系统的语言来说,最大的问题就是不能递归的定义类型,同样是静态类型检查,比如C#,就可以不费力的用Func和delegate做出来,haskell 额,就得扭曲的利用newtype Mu a = Mu (Mu a -> a) 来绕过类型检查(当然,这个在Haskell中是不可能构造出一个实际的值的)。

看下他是怎么做的,我们来把他展开一下:
原式子:y f = (\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)
带进去: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) 这个公因式 就相当于是(\h -> h $ Mu h) (\x -> f . (\(Mu g) -> g) x $ x)了(很像数学把,但也没多大关系)
最后,就可以做出y f = f . (y f)了。

其实这个写法最关键的是 newtype Mu a = Mu (Mu a -> a)的作用,他是如何绕过类型检查,但是又不在运行期构造一个值(想构造也构造不出来)。

来看下他的类型推导过程,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) 递归定义的作用就发挥了,为了类型的推导,继续将那个红色的a 推导成 Mu a -> a,这样 f (Mu a -> a) 会返回一个Mu a -> a,管他叫f'把,这样 f' (Mu a) 就返回一个 a。有根据前面的(\h -> h $ Mu h) 继续讲上面提到的a变成 Mu a -> a。就是把Mu a 喂给了 (Mu a -> a),最后还是返回一个a。
(>_< 其实上面这段是我编出来的,我编不下去了,我不知道ghc是怎么做这个事情的,等我有生之年看完slpj-book-1987再想想)

我们来应用一下,返回一个阶乘:
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 右席 阅读(2183) | 评论 (5)编辑 收藏
  2014年1月8日
本人博客地址:http://www.cppblog.com/pwq1989/ 


今天群里姐夫推荐了个C++的Actor框架 Theron,就看了下源码,注释比代码还多,业界良心。

源码我还没看完,就看到了他的一个叫StringPool的类,里面通过Ref来生成单例(Singleton),看了下
static void Reference();这个函数实现的时候,突然脑洞一开,为啥没有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()。

我们都知道mb这个东西是为了防止CPU级别的指令乱序被发明出来的,(另一个是编译器级别的,和本篇文章没有多大关系,有兴趣大家可以去研究下),实现也是由平台相关的特殊指令(mfence这样的)组成的。

之所以要写成这样,第二个mb()是为了防止在构造函数完成之前提前对目标赋值,但ctor还没完成,就被挂起,然后第二个线程访问的时候,认为已经构造完毕,进而使用不完整的数据引发奇怪的错误。

(第一个rmb()的作用我觉得是可有可无,加上可能是为了效率把(猜),强制刷新读取instance_的值,防止进入第一个check去竞争那个锁,不加也是不会有错的,因为POSIX规定mutex之间必须保持内存的可见性,所以是不需要担心读到脏数据) <-- 这段是个人意见,欢迎修正。

下面就是我趴了半下午才想明白的问题。。。为啥Theron中那段代码(第一段代码)不需要在lock中添加mb(),后来往下翻了下,发现StringPool的构造函数是空的。。根本就没有内存的写入,当然就不需要wmb()了。


可见,C++的多线程编程,好难
posted @ 2014-01-08 00:54 右席 阅读(4925) | 评论 (0)编辑 收藏
  2013年11月30日
本人博客地址:http://www.cppblog.com/pwq1989/

上一篇对Luajit的代码结构和编译过程做了简单的描述,这一篇就讲一下buildvm在第一步预处理dasc文件的过程和DynASM这个轮子。

官方连接:http://luajit.org/dynasm.html

是为了让你更优雅的C里面撸汇编的一个工具,我记得以前看过一个老外的blog对比过同样功能的jit code generator的语法,Luajit的作者显然品位还是很高的。

我们先来看看如果不用工具硬生生撸代码的话会发生什么。
1、你往一段内存里面写0xB8,0x00,0x01....
2、你在文件里定义好多label,写个copy section的宏往内存里面复制,你还不能确定里面到底是什么。(哦。。这个的术语叫Threaded。。。)

然后再对比下AsmJit或者Xbyak的例子看看(他们的功能差不多),DynASM还提供了.marco实现,就会发现语法真是sweeeet~

这是我写着玩的一个草泥马语jit解释器(https://github.com/pwq1989/GMHjit)语法真是清新自然啊,如果你想看工业级的应用,可以看看Google的Haberman写的protobuf的upb库,里面用DynASM进行了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 }

预处理之后那就会变成这样子:
 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参数和actions[]一起放入了Dst(#define Dst &state)的制定的内存中,这时候已经是机器码的形式了。
下面是对于acitons[]数组内容的解释:
184(B8)-- mov eax, [immediate] 指令的第一个字节
237       -- 内置的标志DASM_IMM_D, 指明应该放入一个4字节宽度的参数,与上一条指令完成一个MOV
195(C3)-- 对应ret指令
255       -- 内置的标志DASM_STOP

以上就是最简单的例子,dasm_growpc()是内置的函数,用来增长maxpc, 这样在程序里面就可以方便写出jmp => label 这样的指令了。

由于DynASM的文档很少,幸亏还有几个例子,除了例子唯一能看的就是源码了,所以在用的时候出现问题是很痛苦的。。当时写GMHjit就发现了蛋疼的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函数,里面给的g_opt参数赋默认的值,一个repeat 中调用parseopt解析参数,opt_map就是option对args的函数映射。

函数wline,wcomment,wsync,wdumplines都是对输出的目标文件的操作。

真正的主函数是 translate,把input file变成 output file,在readfile中的doline函数是真正的处理过程,里面判断是否是Assembler line之后Emit C code,调用dostmt(aline)。里面继续有map_coreop[*]来处理section macro arch nop_ error_1 include  if endif elseif 等关键字,想深入研究的可以自己去看,其中在loadarch中根据arch加载不同的lua库

如果arch是x64的话,本质还是require x86
来看dasm_x86.lua文件

_M.mergemaps这是关键的方法,设置了2个Map的元方法,然后返回,相当于是把方法绑定在table里面传递了出去。处理后文件中关键的actionlist[]数组和Dasm_put(Dst, ...)的输出就是这个lua文件的方法。
里面提供了很多dump方法,可以供我们遇到问题时候调试处理过程。

action_names就是以后生成的action_list中的内置标志定义,必须与dasm_x86.h中的enum定义一致。
表明了代表的参数和长度等信息。
这个文件里面所有的函数就是做了一件事,把你的 |...  这样子的代码处理成数组输出到目标文件中(我是汇编渣渣,里面貌似支持SSE2、3、4+,看不懂,等到以后看到traced jit的时候再去翻手册把)

预处理完成之后,就是#include "dasm_x86.h",里面有最关键的dasm_State结构体的定义,几乎里面所有的函数都是对外的API,有init,setup,free等等,除去初始化与free之外,有三个步骤是需要出现在你都代码中:
1、dasm_put(Dst,...) 这个是自动生成的,不用我们操心,根据actionlist[]和运行时的参数写入到Dst指定的内存(Dst->section)中.
2、dasm_link() 第二个参数是返回的代码长度大小,这个函数把section合并到一起,处理偏移等等。
3、dasm_encode() 第二个参数是一个接受encode输出的buffer指针。

然后就可以用一个函数指针,比如声明一个 int (*f)(*int), int ret = f(param) 直接运行刚刚生成的机器码了。






posted @ 2013-11-30 12:49 右席 阅读(6899) | 评论 (0)编辑 收藏
  2013年11月28日
本人博客地址:http://www.cppblog.com/pwq1989/

第一篇对Luajit做一个大概的介绍,我目前也正在慢慢的读通源码中,以后发现了新东西就补充在这里。

大家可以从官网下载到源码(http://luajit.org/),也可以从Github(https://github.com/LuaDist/luajit)down下来,顺便还可以看下commit记录。

大家对着luajit的wiki结合源码看的话会更好些,因为。。文档太特么少了!!

目录结构:
-- src
    -- host
    -- jit
    *.c
    *.h
    *.dasc
等等,别的不是很重要

最开始我是从main函数开始看的,然后。。碰了一鼻子灰,后来研究下他的makefile,发现他是这样子的编译的,贴一下关键的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

先创建了一个buildvm.exe的中间工具,来自动生成代码,分别生成了lj_vm.obj,lj_bcdef.h,lj_ffdef.h ,lj_recdef.h ,jit\vmdef.lua,lj_folddef.h, lj_libdef.h

其中lv_vm.obj是依赖于host\buildvm_arch.h的,这个是用DynASM预处理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代码段中的偏移量(这个我还没深入进去调试一下),vm的一部分是用DynASM直接撸汇编撸出来的,wiki中也有提到下一步jit化的opcode等等。
lj_bc_mode[]的用来根据压缩后的bytecode构造,分离出操作数,第一行的两个宏的定义是
#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里面,这样就能当成是数字,在数组中迅速找到入口了

vmdef.lua:
这个里面内容就不贴了,包括bcname,irname,irfpm,irfield,ircall 的定义,在jit文件夹下面,用于调试等,比如在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")  // ← ← ← ←

当你用luajit -jdump的时候,就是调用的lua的jit库里面的lua函数

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 跟踪的函数,具体可是在lj_ffrecord.c里面看到
recff_idmap[]被用在lj_ffrecord_func这个函数中,有一个关键的数据结构RecordFFData,用来记录在trace过程中被调用函数的参数和返回值个数,和一些辅助数据,opcode,literal等等。通过recff_idmap[]保存的值来区分函数(待仔细研究)


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     }
是根据数组偏移获取函数,直接执行。
(这个Optimation略复杂,以后的博文中再说)

----------------------------------------分割线-------------------------------------------

以上就是buildvm生成代码,在很多.c的文件中,他加入了一些无意义的MARCO,目的是为了能被buildvm识别出

下面说说src根目录下面的文件:

lauxlib.h:
用户开发扩展和与C交互的时候的头文件

lib_*.h /.c:
顾名思义,就是利用LuaAPI写的内部标准库,会在方法上表明是否会被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编译器里面数据结构的定义

lj_asm.h/ .c  lj_asm_*.c lj_emit_*.h lj_target_*.h/.c :
将IR编译成Machine Code,关键的数据结构ASMState,线性扫描的O(n2)分配算法

lj_bc.h/ .c:
Luajit字节码的定义和内存布局

lj_bcdump.c lj_bcread.c  lj_bcwrite.c:
围绕着字节码的操作

lj_carith.c:
C实现的一些数字运算

lj_ccall.h/ .c  lj_ccallback.h / .c :
FFI C语言函数调用和回调绑定

lj_debug.h/.c :
调试与自省用

lj_def.h:
这个很重要,重要的类型和一些宏定义在这里

lj_c*.h/ .c:
和C语言先关的,比如类型转化,char管理,数据管理

lj_frame.h:
Luajit的栈帧管理

lj_func.h/.c:
Function handle和闭包有关的upvalue数据结构

lj_gc.h/.c:
GC相关,GC可以看下luajit的wiki,里面涉及不少增量式GC的paper和作者的看法

lj_gdbjit.h/.c :
对gdb的支持

lj_ir*.h/.c:
SSA,IR相关(这个和bytecode还是不一样的)操作和优化

lj_lex.h/.c  lj_parse.h/.c:
lexer和parser

lj_mcode.h/.c:
Machine Code管理

lj_opt_*.h:
各种bytecode层面上的优化

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结构

lualib.h:
和Lua一样,标准库的API

luajit.h:
luajit 的public API

vm_*.dasc:
编译期被DynASM预处理的源文件,下一篇讲DynASM时候介绍dasc文件

wmain.c:
windows下面的main入口

和Trace相关的:
lj_crecord.h/.c  : C操作的trace record
lj_dispatch.h/.c :  指令分发,调用ASMFuction,处理指令前的hook和记录trace用的hot count,有一个重要的数据结构 GG_State
lj_ff*.h/.c: 上面讲lj_ffdef.h的时候提过,trace的时候 记录Fast Function的调用记数
lj_trace.h/.c: trace的具体过程
lj_traceerr.h : trace error
posted @ 2013-11-28 19:23 右席 阅读(12384) | 评论 (4)编辑 收藏
仅列出标题