loop_in_codes

低调做技术__欢迎移步我的独立博客 codemaro.com 微博 kevinlynx

2014年12月3日 #

基于内存查看STL常用容器内容

有时候在线上使用gdb调试程序core问题时,可能没有符号文件,拿到的仅是一个内存地址,如果这个指向的是一个STL对象,那么如何查看这个对象的内容呢?

只需要知道STL各个容器的数据结构实现,就可以查看其内容。本文描述了SGI STL实现中常用容器的数据结构,以及如何在gdb中查看其内容。

string

string,即basic_string bits/basic_string.h

mutable _Alloc_hider  _M_dataplus;
    ... 
      const _CharT*
      c_str() const
      { return _M_data(); }
    ...    
      _CharT*
      _M_data() const 
      { return  _M_dataplus._M_p; }

    ...
      struct _Alloc_hider : _Alloc
      {
    _Alloc_hider(_CharT* __dat, const _Alloc& __a)
    : _Alloc(__a), _M_p(__dat) { }

    _CharT* _M_p; // The actual data.
      };
   
      size_type
      length() const
      { return _M_rep()->_M_length; }

      _Rep*
      _M_rep() const
      { return &((reinterpret_cast<_Rep*> (_M_data()))[-1]); }

      ...
       struct _Rep_base
      {
    size_type       _M_length;
    size_type       _M_capacity;
    _Atomic_word        _M_refcount;
      };

      struct _Rep : _Rep_base

即,string内有一个指针,指向实际的字符串位置,这个位置前面有一个_Rep结构,其内保存了字符串的长度、可用内存以及引用计数。当我们拿到一个string对象的地址时,可以通过以下代码获取相关值:

void ds_str_i(void *p) {
        char **raw = (char**)p;
        char *s = *raw;
        size_t len = *(size_t*)(s - sizeof(size_t) * 3);
        printf("str: %s (%zd)\n", s, len);
    }

    size_t ds_str() {
        std::string s = "hello";
        ds_str_i(&s);
        return s.size();
    }

在gdb中拿到一个string的地址时,可以以下打印出该字符串及长度:

(gdb) x/1a p
0x7fffffffe3a0: 0x606028
(gdb) p (char*)0x606028
$2 = 0x606028 "hello"
(gdb) x/1dg 0x606028-24
0x606010:       5

vector

众所周知vector实现就是一块连续的内存,bits/stl_vector.h

template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
    class vector : protected _Vector_base<_Tp, _Alloc>

    ...
    template<typename _Tp, typename _Alloc>
    struct _Vector_base
    {
      typedef typename _Alloc::template rebind<_Tp>::other _Tp_alloc_type;

      struct _Vector_impl
      : public _Tp_alloc_type
      {
    _Tp*           _M_start;
    _Tp*           _M_finish;
    _Tp*           _M_end_of_storage;
    _Vector_impl(_Tp_alloc_type const& __a)
    : _Tp_alloc_type(__a), _M_start(0), _M_finish(0), _M_end_of_storage(0)
    { }
      };


      _Vector_impl _M_impl;

可以看出sizeof(vector<xxx>)=24,其内也就是3个指针,_M_start指向首元素地址,_M_finish指向最后一个节点+1,_M_end_of_storage是可用空间最后的位置。

iterator
      end()
      { return iterator (this->_M_impl._M_finish); }
      const_iterator
      ...
      begin() const
      { return const_iterator (this->_M_impl._M_start); }
      ...
      size_type
      capacity() const
      { return size_type(const_iterator(this->_M_impl._M_end_of_storage)
             - begin()); }

可以通过代码从一个vector对象地址输出其信息:

template <typename T>
    void ds_vec_i(void *p) {
        T *start = *(T**)p;
        T *finish = *(T**)((char*)p + sizeof(void*));
        T *end_storage = *(T**)((char*)p + 2 * sizeof(void*));
        printf("vec size: %ld, avaiable size: %ld\n", finish - start, end_storage - start); 
    }

    size_t ds_vec() {
        std::vector<int> vec;
        vec.push_back(0x11);
        vec.push_back(0x22);
        vec.push_back(0x33);
        ds_vec_i<int>(&vec);
        return vec.size();
    }

使用gdb输出一个vector中的内容:

(gdb) p p
$3 = (void *) 0x7fffffffe380
(gdb) x/1a p
0x7fffffffe380: 0x606080
(gdb) x/3xw 0x606080
0x606080:       0x00000011      0x00000022      0x00000033

list

众所周知list被实现为一个链表。准确来说是一个双向链表。list本身是一个特殊节点,其代表end,其指向的下一个元素才是list真正的第一个节点:

bits/stl_list.h

bool
      empty() const
      { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }

      const_iterator
      begin() const
      { return const_iterator(this->_M_impl._M_node._M_next); }

      iterator
      end()
      { return iterator(&this->_M_impl._M_node); }

      ...

    struct _List_node_base
    {
        _List_node_base* _M_next;   ///< Self-explanatory
        _List_node_base* _M_prev;   ///< Self-explanatory
        ...
    };
         
    template<typename _Tp>
    struct _List_node : public _List_node_base
    {
      _Tp _M_data;                ///< User's data.
    };
      
    template<typename _Tp, typename _Alloc>
    class _List_base
    {
        ...
      struct _List_impl
      : public _Node_alloc_type
      {
    _List_node_base _M_node;
        ...
      };

      _List_impl _M_impl;

          
    template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
    class list : protected _List_base<_Tp, _Alloc>

所以sizeof(list<xx>)=16,两个指针。每一个真正的节点首先是包含两个指针,然后是元素内容(_List_node)。

通过代码输出list的内容:

#define NEXT(ptr, T) do { \
        void *n = *(char**)ptr; \
        T val = *(T*)((char**)ptr + 2); \
        printf("list item %p val: 0x%x\n", ptr, val); \
        ptr = n; \
    } while (0)

    template <typename T>
    void ds_list_i(void *p) {
        void *ptr = *(char**)p;

        NEXT(ptr, T);
        NEXT(ptr, T);
        NEXT(ptr, T);
    }

    size_t ds_list() {
        std::list<int> lst;
        lst.push_back(0x11);
        lst.push_back(0x22);
        lst.push_back(0x33);
        ds_list_i<int>(&lst);
        return lst.size();
    }

在gdb中可以以下方式遍历该list:

(gdb) p p
$4 = (void *) 0x7fffffffe390
(gdb) x/1a p
0x7fffffffe390: 0x606080
(gdb) x/1xw 0x606080+16         # 元素1 
0x606090:       0x00000011
(gdb) x/1a 0x606080
0x606080:       0x6060a0
(gdb) x/1xw 0x6060a0+16         # 元素2
0x6060b0:       0x00000022

map

map使用的是红黑树实现,实际使用的是stl_tree.h实现:

bits/stl_map.h

typedef _Rb_tree<key_type, value_type, _Select1st<value_type>,
               key_compare, _Pair_alloc_type> _Rep_type;
    ...
     _Rep_type _M_t;
    ... 

      iterator
      begin()
      { return _M_t.begin(); }

bits/stl_tree.h

struct _Rb_tree_node_base
      {
        typedef _Rb_tree_node_base* _Base_ptr;
        typedef const _Rb_tree_node_base* _Const_Base_ptr;

        _Rb_tree_color  _M_color;
        _Base_ptr       _M_parent;
        _Base_ptr       _M_left;
        _Base_ptr       _M_right;
        
        ...
      };

    template<typename _Val>
    struct _Rb_tree_node : public _Rb_tree_node_base
    {
      typedef _Rb_tree_node<_Val>* _Link_type;
      _Val _M_value_field;
    };


    template<typename _Key_compare,
           bool _Is_pod_comparator = std::__is_pod<_Key_compare>::__value>
        struct _Rb_tree_impl : public _Node_allocator
        {
      _Key_compare      _M_key_compare;
      _Rb_tree_node_base    _M_header;
      size_type         _M_node_count; // Keeps track of size of tree.
      ...
        }
    
    _Rb_tree_impl<_Compare> _M_impl;
    ...

      iterator
      begin()
      {
    return iterator(static_cast<_Link_type>
            (this->_M_impl._M_header._M_left));
      }

所以可以看出,大部分时候(取决于_M_key_compare) sizeof(map<xx>)=48,主要的元素是:

_Rb_tree_color  _M_color; // 节点颜色
        _Base_ptr       _M_parent; // 父节点
        _Base_ptr       _M_left; // 左节点
        _Base_ptr       _M_right; // 右节点
        _Val            _M_value_field // 同list中节点技巧一致,后面是实际的元素

同list中的实现一致,map本身作为一个节点,其不是一个存储数据的节点,

_Rb_tree::end

iterator
      end()
      { return iterator(static_cast<_Link_type>(&this->_M_impl._M_header)); }

由于节点值在_Rb_tree_node_base后,所以任意时候拿到节点就可以偏移这个结构体拿到节点值,节点的值是一个pair,包含了key和value。

在gdb中打印以下map的内容:

size_t ds_map() {
        std::map<std::string, int> imap;
        imap["abc"] = 0xbbb;
        return imap.size();
    }
(gdb) p/x &imap
$7 = 0x7fffffffe370
(gdb) x/1a (char*)&imap+24       # _M_left 真正的节点
0x7fffffffe388: 0x606040          
(gdb) x/1xw 0x606040+32+8        # 偏移32字节是节点值的地址,再偏移8则是value的地址
0x606068:       0x00000bbb
(gdb) p *(char**)(0x606040+32)   # 偏移32字节是string的地址
$8 = 0x606028 "abc"

或者很多时候没有必要这么装逼+蛋疼:

(gdb) p *(char**)(imap._M_t._M_impl._M_header._M_left+1)
$9 = 0x606028 "abc"
(gdb) x/1xw (char*)(imap._M_t._M_impl._M_header._M_left+1)+8
0x606068:       0x00000bbb

posted @ 2014-12-03 22:08 Kevin Lynx 阅读(710) | 评论 (2)编辑 收藏

2014年11月4日 #

linux动态库的种种要点

linux下使用动态库,基本用起来还是很容易。但如果我们的程序中大量使用动态库来实现各种框架/插件,那么就会遇到一些坑,掌握这些坑才有利于程序更稳健地运行。

本篇先谈谈动态库符号方面的问题。

测试代码可以在github上找到

符号查找

一个应用程序test会链接一个动态库libdy.so,如果一个符号,例如函数callfn定义于libdy.so中,test要使用该函数,简单地声明即可:

// dy.cpp libdy.so
void callfn() {
    ...
}

// main.cpp test
extern void callfn();

callfn();

在链接test的时候,链接器会统一进行检查。

同样,在libdy.so中有相同的规则,它可以使用一个外部的符号,在它被链接/载入进一个可执行程序时才会进行符号存在与否的检查。这个符号甚至可以定义在test中,形成一种双向依赖,或定义在其他动态库中:

// dy.cpp libdy.so
extern void mfunc();

mfunc();

// main.cpp test
void mfunc() {
    ...
}

在生成libdy.so时mfunc可以找不到,此时mfunc为未定义:

$ nm libdy.so | grep mfun
U _Z5mfuncv

但在libdy.so被链接进test时则会进行检查,试着把mfunc函数的定义去掉,就会得到一个链接错误:

./libdy.so: undefined reference to `mfunc()'

同样,如果我们动态载入libdy.so,此时当然可以链接通过,但是在载入时同样得到找不到符号的错误:

#ifdef DY_LOAD
    void *dp = dlopen("./libdy.so", RTLD_LAZY);
    typedef void (*callfn)();
    callfn f = (callfn) dlsym(dp, "callfn");
    f();
    dlclose(dp);
#else
    callfn();
#endif

得到错误:

./test: symbol lookup error: ./libdy.so: undefined symbol: _Z5mfuncv

结论:基于以上,我们知道,如果一个动态库依赖了一些外部符号,这些外部符号可以位于其他动态库甚至应用程序中。我们可以再链接这个动态库的时候就把依赖的其他库也链接上,或者推迟到链接应用程序时再链接。而动态加载的库,则要保证在加载该库时,进程中加载的其他动态库里已经存在该符号。

例如,通过LD_PRELOAD环境变量可以让一个进程先加载指定的动态库,上面那个动态加载启动失败的例子,可以通过预先加载包含mfunc符号的动态库解决:

$ LD_PRELOAD=libmfun.so ./test
...

但是如果这个符号存在于可执行程序中则不行:

$ nm test | grep mfunc
0000000000400a00 T _Z5mfuncv
$ nm test | grep mfunc
0000000000400a00 T _Z5mfuncv
$ ./test
...
./test: symbol lookup error: ./libdy.so: undefined symbol: _Z5mfuncv

符号覆盖

前面主要讲的是符号缺少的情况,如果同一个符号存在多分,则更能引发问题。这里谈到的符号都是全局符号,一个进程中某个全局符号始终是全局唯一的。为了保证这一点,在链接或动态载入动态库时,就会出现忽略重复符号的情况。

这里就不提同一个链接单位(如可执行程序、动态库)里符号重复的问题了

函数

当动态库和libdy.so可执行程序test中包含同名的函数时会怎样?根据是否动态加载情况还有所不同。

当直接链接动态库时,libdy.so和test都会链接包含func函数的fun.o,为了区分,我把func按照条件编译得到不同的版本:

// fun.cpp
#ifdef V2
extern "C" void func() {
    printf("func v2\n");
}
#else
extern "C" void func() {
    printf("func v1\n");
}
#endif

// Makefile
test: libdy obj.o mainfn
    g++ -g -Wall -c fun.cpp -o fun.o # 编译为fun.o
    g++ -g -Wall -c main.cpp #-DDY_LOAD
    g++ -g -Wall -o test main.o obj.o fun.o -ldl mfun.o -ldy -L.

libdy: obj
    g++ -Wall -fPIC -c fun.cpp -DV2 -o fun-dy.o  # 定义V2宏,编译为fun-dy.o
    g++ -Wall -fPIC -shared -o libdy.so dy.cpp -g obj.o fun-dy.o

这样,test中的func就会输出func v1;libdy.so中的func就会输出func v2。test和libdy.o确实都有func符号:

$ nm libdy.so | grep func
0000000000000a60 T func

$nm test | grep func
0000000000400a80 T func

在test和libdy.so中都会调用func函数:

// main.cpp test
int main(int argc, char **argv) {
    func();
    ...
    callfn(); // 调用libdy.so中的函数
    ...
}

// dy.cpp libdy.so
extern "C" void callfn() {
    ... 
    printf("callfn\n");
    func();
    ...
}

运行后发现,都调用的是同一个func

$ ./test
...
func v1
...
callfn
func v1

结论,直接链接动态库时,整个程序运行的时候符号会发生覆盖,只有一个符号被使用。在实践中,如果程序和链接的动态库都依赖了一个静态库,而后他们链接的这个静态库版本不同,则很有可能因为符号发生了覆盖而导致问题。(静态库同普通的.o性质一样,参考浅析静态库链接原理)

更复杂的情况中,多个动态库和程序都有相同的符号,情况也是一样,会发生符号覆盖。如果程序里没有这个符号,而多个动态库里有相同的符号,也会覆盖。

但是对于动态载入的情况则不同,同样的libdy.so我们在test中不链接,而是动态载入:

int main(int argc, char **argv) {
    func();
#ifdef DY_LOAD
    void *dp = dlopen("./libdy.so", RTLD_LAZY);
    typedef void (*callfn)();
    callfn f = (callfn) dlsym(dp, "callfn");
    f();
    func();
    dlclose(dp);
#else
    callfn();
#endif
    return 0;
}

运行得到:

$ ./test
func v1
...
callfn
func v2
func v1

都正确地调用到各自链接的func

结论,实践中,动态载入的动态库一般会作为插件使用,那么其同程序链接不同版本的静态库(相同符号不同实现),是没有问题的。

变量

变量本质上也是符号(symbol),但其处理规则和函数还有点不一样(是不是有点想吐槽了)。

// object.h
class Object {
public:
    Object() {
#ifdef DF
        s = malloc(32);
        printf("s addr %p\n", s);
#endif
        printf("ctor %p\n", this);
    }

    ~Object() {
        printf("dtor %p\n", this);
#ifdef DF
        printf("s addr %p\n", s);
        free(s);
#endif
    }

    void *s;
};

extern Object g_obj;

我们的程序test和动态库libdy.so都会链接object.o。首先测试test链接libdy.so,test和libdy.so中都会有g_obj这个符号:

// B g_obj 表示g_obj位于BSS段,未初始化段

$ nm test | grep g_obj
0000000000400a14 t _GLOBAL__I_g_obj
00000000006012c8 B g_obj
$ nm libdy.so | grep g_obj
000000000000097c t _GLOBAL__I_g_obj
0000000000200f30 B g_obj

运行:

$ ./test
ctor 0x6012c8
ctor 0x6012c8
...
dtor 0x6012c8
dtor 0x6012c8

g_obj被构造了两次,但地址一样。全局变量只有一个实例,似乎在情理之中。

动态载入libdy.so,变量地址还是相同的:

$ ./test
ctor 0x6012a8
...
ctor 0x6012a8
...
dtor 0x6012a8
dtor 0x6012a8

结论,不同于函数,全局变量符号重复时,不论动态库是动态载入还是直接链接,变量始终只有一个。

但诡异的情况是,对象被构造和析构了两次。构造两次倒无所谓,浪费点空间,但是析构两次就有问题。因为析构时都操作的是同一个对象,那么如果这个对象内部有分配的内存,那就会对这块内存造成double free,因为指针相同。打开DF宏实验下:

$ ./test
s addr 0x20de010
ctor 0x6012b8
s addr 0x20de040
ctor 0x6012b8
...
dtor 0x6012b8
s addr 0x20de040
dtor 0x6012b8
s addr 0x20de040

因为析构的两次都是同一个对象,所以其成员s指向的内存被释放了两次,从而产生了double free,让程序coredump了。

总结,全局变量符号重复时,始终会只使用一个,并且会被初始化/释放两次,是一种较危险的情况,应当避免在使用动态库的过程中使用全局变量。

posted @ 2014-11-04 00:55 Kevin Lynx 阅读(1346) | 评论 (0)编辑 收藏

2014年10月19日 #

图解zookeeper FastLeader选举算法

zookeeper配置为集群模式时,在启动或异常情况时会选举出一个实例作为Leader。其默认选举算法为FastLeaderElection

不知道zookeeper的可以考虑这样一个问题:某个服务可以配置为多个实例共同构成一个集群对外提供服务。其每一个实例本地都存有冗余数据,每一个实例都可以直接对外提供读写服务。在这个集群中为了保证数据的一致性,需要有一个Leader来协调一些事务。那么问题来了:如何确定哪一个实例是Leader呢?

问题的难点在于:

  • 没有一个仲裁者来选定Leader
  • 每一个实例本地可能已经存在数据,不确定哪个实例上的数据是最新的

分布式选举算法正是用来解决这个问题的。

本文基于zookeeper 3.4.6 的源码进行分析。FastLeaderElection算法的源码全部位于FastLeaderElection.java文件中,其对外接口为FastLeaderElection.lookForLeader,该接口是一个同步接口,直到选举结束才会返回。同样由于网上已有类似文章,所以我就从图示的角度来阐述。阅读一些其他文章有利于获得初步印象:

主要流程

阅读代码和以上推荐文章可以把整个流程梳理清楚。实现上,包括了一个消息处理主循环,也是选举的主要逻辑,以及一个消息发送队列处理线程和消息解码线程。主要流程可概括为下图:

fle-flow.png

推荐对照着推荐的文章及代码理解,不赘述。

我们从感性上来理解这个算法。

每一个节点,相当于一个选民,他们都有自己的推荐人,最开始他们都推荐自己。谁更适合成为Leader有一个简单的规则,例如sid够大(配置)、持有的数据够新(zxid够大)。每个选民都告诉其他选民自己目前的推荐人是谁,类似于出去搞宣传拉拢其他选民。每一个选民发现有比自己更适合的人时就转而推荐这个更适合的人。最后,大部分人意见一致时,就可以结束选举。

就这么简单。总体上有一种不断演化逼近结果的感觉。

当然,会有些特殊情况的处理。例如总共3个选民,1和2已经确定3是Leader,但3还不知情,此时就走入LEADING/FOLLOWING的分支,选民3只是接收结果。

代码中不是所有逻辑都在这个大流程中完成的。在接收消息线程中,还可能单独地回应某个节点(WorkerReceiver.run):

recv.png

从这里可以看出,当某个节点已经确定选举结果不再处于LOOKING状态时,其收到LOOKING消息时都会直接回应选举的最终结果。结合上面那个比方,相当于某次选举结束了,这个时候来了选民4又发起一次新的选举,那么其他选民就直接告诉它当前的Leader情况。相当于,在这个集群主从已经就绪的情况下,又开启了一个实例,这个实例就会直接使用当前的选举结果。

状态转换

每个节点上有一些关键的数据结构:

  • 当前推荐人,初始推荐自己,每次收到其他更好的推荐人时就更新
  • 其他人的投票集合,用于确定何时选举结束

每次推荐人更新时就会进行广播,正是这个不断地广播驱动整个算法趋向于结果。假设有3个节点A/B/C,其都还没有数据,按照sid关系为C>B>A,那么按照规则,C更可能成为Leader,其各个节点的状态转换为:

state.png

图中,v(A)表示当前推荐人为A;r[]表示收到的投票集合。

可以看看当其他节点已经确定投票结果时,即不再是LOOKING时的状态:

state-ret.png

代码中有一个特殊的投票集合outofelection,我理解为选举已结束的那些投票,这些投票仅用于表征选举结果。

当一个新启动的节点加入集群时,它对集群内其他节点发出投票请求,而其他节点已不处于LOOKING状态,此时其他节点回应选举结果,该节点收集这些结果到outofelection中,最终在收到合法LEADER消息且这些选票也构成选举结束条件时,该节点就结束自己的选举行为。注意到代码中会logicalclock = n.electionEpoch;更新选举轮数

posted @ 2014-10-19 15:58 Kevin Lynx 阅读(769) | 评论 (0)编辑 收藏

2014年10月15日 #

图解分布式一致性协议Paxos

Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢?

<分布式系统的事务处理>

Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。

<大规模分布式存储系统>

理解了这两个分布式协议之后(Paxos/2PC),学习其他分布式协议会变得相当容易。

学习Paxos算法有两部分:a) 算法的原理/证明;b) 算法的理解/运作。

理解这个算法的运作过程其实基本就可以用于工程实践。而且理解这个过程相对来说也容易得多。

网上我觉得讲Paxos讲的好的属于这篇:paxos图解Paxos算法详解,我这里就结合wiki上的实例进一步阐述。一些paxos基础通过这里提到的两篇文章,以及wiki上的内容基本可以理解。

算法内容

Paxos在原作者的《Paxos Made Simple》中内容是比较精简的:

Phase 1

(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.

(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered pro-posal (if any) that it has accepted.

Phase 2

(a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v , where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.

(b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

借用paxos图解文中的流程图可概括为:

实例及详解

Paxos中有三类角色ProposerAcceptorLearner,主要交互过程在ProposerAcceptor之间。

ProposerAcceptor之间的交互主要有4类消息通信,如下图:

这4类消息对应于paxos算法的两个阶段4个过程:

  • phase 1
    • a) proposer向网络内超过半数的acceptor发送prepare消息
    • b) acceptor正常情况下回复promise消息
  • phase 2
    • a) 在有足够多acceptor回复promise消息时,proposer发送accept消息
    • b) 正常情况下acceptor回复accepted消息

因为在整个过程中可能有其他proposer针对同一件事情发出以上请求,所以在每个过程中都会有些特殊情况处理,这也是为了达成一致性所做的事情。如果在整个过程中没有其他proposer来竞争,那么这个操作的结果就是确定无异议的。但是如果有其他proposer的话,情况就不一样了。

paxos中文wiki上的例子为例。简单来说该例子以若干个议员提议税收,确定最终通过的法案税收比例。

以下图中基本只画出proposer与一个acceptor的交互。时间标志T2总是在T1后面。propose number简称N。

情况之一如下图:

A3在T1发出accepted给A1,然后在T2收到A5的prepare,在T3的时候A1才通知A5最终结果(税率10%)。这里会有两种情况:

  • A5发来的N5小于A1发出去的N1,那么A3直接拒绝(reject)A5
  • A5发来的N5大于A1发出去的N1,那么A3回复promise,但带上A1的(N1, 10%)

这里可以与paxos流程图对应起来,更好理解。acceptor会记录(MaxN, AcceptN, AcceptV)

A5在收到promise后,后续的流程可以顺利进行。但是发出accept时,因为收到了(AcceptN, AcceptV),所以会取最大的AcceptN对应的AcceptV,例子中也就是A1的10%作为AcceptV。如果在收到promise时没有发现有其他已记录的AcceptV,则其值可以由自己决定。

针对以上A1和A5冲突的情况,最终A1和A5都会广播接受的值为10%。

其实4个过程中对于acceptor而言,在回复promise和accepted时由于都可能因为其他proposer的介入而导致特殊处理。所以基本上看在这两个时间点收到其他proposer的请求时就可以了解整个算法了。例如在回复promise时则可能因为proposer发来的N不够大而reject:

如果在发accepted消息时,对其他更大N的proposer发出过promise,那么也会reject该proposer发出的accept,如图:

这个对应于Phase 2 b):

it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

总结

Leslie Lamport没有用数学描述Paxos,但是他用英文阐述得很清晰。将Paxos的两个Phase的内容理解清楚,整个算法过程还是不复杂的。

至于Paxos中一直提到的一个全局唯一且递增的proposer number,其如何实现,引用如下:

如何产生唯一的编号呢?在《Paxos made simple》中提到的是让所有的Proposer都从不相交的数据集合中进行选择,例如系统有5个Proposer,则可为每一个Proposer分配一个标识j(0~4),则每一个proposer每次提出决议的编号可以为5*i + j(i可以用来表示提出议案的次数)

参考文档

posted @ 2014-10-15 22:45 Kevin Lynx 阅读(876) | 评论 (3)编辑 收藏

2014年10月12日 #

淘宝分布式配置管理服务Diamond

在一个分布式环境中,同类型的服务往往会部署很多实例。这些实例使用了一些配置,为了更好地维护这些配置就产生了配置管理服务。通过这个服务可以轻松地管理这些应用服务的配置问题。应用场景可概括为:

zookeeper的一种应用就是分布式配置管理(基于ZooKeeper的配置信息存储方案的设计与实现)。百度也有类似的实现:disconf

Diamond则是淘宝开源的一种分布式配置管理服务的实现。Diamond本质上是一个Java写的Web应用,其对外提供接口都是基于HTTP协议的,在阅读代码时可以从实现各个接口的controller入手。

分布式配置管理

分布式配置管理的本质基本上就是一种推送-订阅模式的运用。配置的应用方是订阅者,配置管理服务则是推送方。概括为下图:

其中,客户端包括管理人员publish数据到配置管理服务,可以理解为添加/更新数据;配置管理服务notify数据到订阅者,可以理解为推送。

配置管理服务往往会封装一个客户端库,应用方则是基于该库与配置管理服务进行交互。在实际实现时,客户端库可能是主动拉取(pull)数据,但对于应用方而言,一般是一种事件通知方式。

Diamond中的数据是简单的key-value结构。应用方订阅数据则是基于key来订阅,未订阅的数据当然不会被推送。数据从类型上又划分为聚合和非聚合。因为数据推送者可能很多,在整个分布式环境中,可能有多个推送者在推送相同key的数据,这些数据如果是聚合的,那么所有这些推送者推送的数据会被合并在一起;反之如果是非聚合的,则会出现覆盖。

数据的来源可能是人工通过管理端录入,也可能是其他服务通过配置管理服务的推送接口自动录入。

架构及实现

Diamond服务是一个集群,是一个去除了单点的协作集群。如图:

图中可分为以下部分讲解:

服务之间同步

Diamond服务集群每一个实例都可以对外完整地提供服务,那么意味着每个实例上都有整个集群维护的数据。Diamond有两种方式保证这一点:

  • 任何一个实例都有其他实例的地址;任何一个实例上的数据变更时,都会将改变的数据同步到mysql上,然后通知其他所有实例从mysql上进行一次数据拉取(DumpService::dump),这个过程只拉取改变了的数据
  • 任何一个实例启动后都会以较长的时间间隔(几小时),从mysql进行一次全量的数据拉取(DumpAllProcessor)

实现上为了一致性,通知其他实例实际上也包含自己。以服务器收到添加聚合数据为例,处理过程大致为:

DatumController::addDatum // /datum.do?method=addDatum
    PersistService::addAggrConfigInfo 
    MergeDatumService::addMergeTask // 添加一个MergeDataTask,异步处理

MergeTaskProcessor::process
    PersistService::insertOrUpdate
        EventDispatcher.fireEvent(new ConfigDataChangeEvent // 派发一个ConfigDataChangeEvent事件

NotifyService::onEvent // 接收事件并处理
    TaskManager::addTask(..., new NotifyTask // 由此,当数据发生变动,则最终创建了一个NoticyTask

// NotifyTask同样异步处理
NotifyTaskProcessor::process
    foreach server in serverList // 包含自己
        notifyToDump // 调用 /notify.do?method=notifyConfigInfo 从mysql更新变动的数据

虽然Diamond去除了单点问题,不过问题都下降到了mysql上。但由于其作为配置管理的定位,其数据量就mysql的应用而言算小的了,所以可以一定程度上保证整个服务的可用性。

数据一致性

由于Diamond服务器没有master,任何一个实例都可以读写数据,那么针对同一个key的数据则可能面临冲突。这里应该是通过mysql来保证数据的一致性。每一次客户端请求写数据时,Diamond都将写请求投递给mysql,然后通知集群内所有Diamond实例(包括自己)从mysql拉取数据。当然,拉取数据则可能不是每一次写入都能拉出来,也就是最终一致性。

Diamond中没有把数据放入内存,但会放到本地文件。对于客户端的读操作而言,则是直接返回本地文件里的数据。

服务实例列表

Diamond服务实例列表是一份静态数据,直接将每个实例的地址存放在一个web server上。无论是Diamond服务还是客户端都从该web server上取出实例列表。

对于客户端而言,当其取出了该列表后,则是随机选择一个节点(ServerListManager.java),以后的请求都会发往该节点。

数据同步

客户端库中以固定时间间隔从服务器拉取数据(ClientWorker::ClientWorkerClientWorker::checkServerConfigInfo)。只有应用方关心的数据才可能被拉取。另外,为了数据推送的及时,Diamond还使用了一种long polling的技术,其实也是为了突破HTTP协议的局限性。如果整个服务是基于TCP的自定义协议,客户端与服务器保持长连接则没有这些问题

数据的变更

Diamond中很多操作都会检查数据是否发生了变化。标识数据变化则是基于数据对应的MD5值来实现的。

容灾

在整个Diamond系统中,几个角色为了提高容灾性,都有自己的缓存,概括为下图:

每一个角色出问题时,都可以尽量保证客户端对应用层提供服务。

参考文档

posted @ 2014-10-12 12:57 Kevin Lynx 阅读(724) | 评论 (3)编辑 收藏

2014年10月7日 #

浅析glibc中thread tls的一处bug

最早的时候是在程序初始化过程中开启了一个timer(timer_create),这个timer第一次触发的时间较短时就会引起程序core掉,core的位置也是不定的。使用valgrind可以发现有错误的内存写入:

==31676== Invalid write of size 8
==31676==    at 0x37A540F852: _dl_allocate_tls_init (in /lib64/ld-2.5.so)
==31676==    by 0x4E26BD3: pthread_create@@GLIBC_2.2.5 (in /lib64/libpthread-2.5.so)
==31676==    by 0x76E0B00: timer_helper_thread (in /lib64/librt-2.5.so)
==31676==    by 0x4E2673C: start_thread (in /lib64/libpthread-2.5.so)
==31676==    by 0x58974BC: clone (in /lib64/libc-2.5.so)
==31676==  Address 0xf84dbd0 is 0 bytes after a block of size 336 alloc'd
==31676==    at 0x4A05430: calloc (vg_replace_malloc.c:418)
==31676==    by 0x37A5410082: _dl_allocate_tls (in /lib64/ld-2.5.so)
==31676==    by 0x4E26EB8: pthread_create@@GLIBC_2.2.5 (in /lib64/libpthread-2.5.so)
==31676==    by 0x76E0B00: timer_helper_thread (in /lib64/librt-2.5.so)
==31676==    by 0x4E2673C: start_thread (in /lib64/libpthread-2.5.so)
==31676==    by 0x58974BC: clone (in /lib64/libc-2.5.so)

google _dl_allocate_tls_init 相关发现一个glibc的bug Bug 13862 和我的情况有点类似。本文就此bug及tls相关实现做一定阐述。

需要查看glibc的源码,如何确认使用的glibc的版本,可以这样:

$ /lib/libc.so.6
GNU C Library stable release version 2.5, by Roland McGrath et al.
...

为了方便,还可以直接在(glibc Cross Reference)[http://osxr.org/glibc/source/?v=glibc-2.17]网页上进行查看,版本不同,但影响不大。

BUG描述

要重现13862 BUG作者提到要满足以下条件:

The use of a relatively large number of dynamic libraries, loaded at runtime using dlopen.

The use of thread-local-storage within those libraries.

A thread exiting prior to the number of loaded libraries increasing a significant amount, followed by a new thread being created after the number of libraries has increased.

简单来说,就是在加载一大堆包含TLS变量的动态库的过程中,开启了一个线程,这个线程退出后又开启了另一个线程。

这和我们的问题场景很相似。不同的是我们使用的是timer,但timer在触发时也是开启新的线程,并且这个线程会立刻退出:

/nptl/sysdeps/unix/sysv/linux/timer_routines.c

timer_helper_thread(...)  // 用于检测定时器触发的辅助线程
{
    ...
      pthread_t th;
      (void) pthread_create (&th, &tk->attr, timer_sigev_thread, // 开启一个新线程调用用户注册的定时器函数
                 td);
    ...
}

要重现此BUG可以使用我的实验代码 thread-tls,或者使用Bug 13862 中的附件

TLS相关实现

可以顺着_dl_allocate_tls_init函数的实现查看相关联的部分代码。该函数遍历所有加载的包含TLS变量的模块,初始化一个线程的TLS数据结构。

每一个线程都有自己的堆栈空间,其中单独存储了各个模块的TLS变量,从而实现TLS变量在每一个线程中都有单独的拷贝。TLS与线程的关联关系可以查看下图:

应用层使用的pthread_t实际是个pthread对象的地址。创建线程时线程的堆栈空间和pthread结构是一块连续的内存。但这个地址并不指向这块内存的首地址。相关代码:/nptl/allocatestack.c allocate_stack,该函数分配线程的堆栈内存。

pthread第一个成员是tcbhead_ttcbhead_tdtv指向了一个dtv_t数组,该数组的大小随着当前程序载入的模块多少而动态变化。每一个模块被载入时,都有一个l_tls_modid,其直接作为dtv_t数组的下标索引。tcbhead_t中的dtv实际指向的是dtv_t第二个元素,第一个元素用于记录整个dtv_t数组有多少元素,第二个元素也做特殊使用,从第三个元素开始,才是用于存储TLS变量。

一个dtv_t存储的是一个模块中所有TLS变量的地址,当然这些TLS变量都会被放在连续的内存空间里。dtv_t::pointer::val正是用于指向这块内存的指针。对于非动态加载的模块它指向的是线程堆栈的位置;否则指向动态分配的内存位置。

以上结构用代码描述为,

union dtv_t {
    size_t counter;
    struct {
        void *val; /* point to tls variable memory */
        bool is_static;
    } pointer;
};
 
struct tcbhead_t {
    void *tcb;
    dtv_t *dtv; /* point to a dtv_t array */
    void *padding[22]; /* other members i don't care */
};

struct pthread {
    tcbhead_t tcb;
    /* more members i don't care */
};

dtv是一个用于以模块为单位存储TLS变量的数组

实际代码参看 /nptl/descr.h 及 nptl/sysdeps/x86_64/tls.h。

实验

使用g++ -o thread -g -Wall -lpthread -ldl thread.cpp编译代码,即在创建线程前加载了一个.so:

Breakpoint 1, dump_pthread (id=1084229952) at thread.cpp:40
40          printf("pthread %p, dtv %p\n", pd, dtv);
(gdb) set $dtv=pd->tcb.dtv
(gdb) p $dtv[-1]
$1 = {counter = 17, pointer = {val = 0x11, is_static = false}}
(gdb) p $dtv[3]
$2 = {counter = 18446744073709551615, pointer = {val = 0xffffffffffffffff, is_static = false}}

dtv[3]对应着动态加载的模块,is_static=falseval被初始化为-1:

/elf/dl-tls.c _dl_allocate_tls_init

if (map->l_tls_offset == NO_TLS_OFFSET
   || map->l_tls_offset == FORCED_DYNAMIC_TLS_OFFSET)
 {
   /* For dynamically loaded modules we simply store
      the value indicating deferred allocation.  */
   dtv[map->l_tls_modid].pointer.val = TLS_DTV_UNALLOCATED;
   dtv[map->l_tls_modid].pointer.is_static = false;
   continue;
 }

dtv数组大小之所以为17,可以参看代码 /elf/dl-tls.c allocate_dtv

// dl_tls_max_dtv_idx 随着载入模块的增加而增加,载入1个.so则是1 

dtv_length = GL(dl_tls_max_dtv_idx) + DTV_SURPLUS; // DTV_SURPLUS 14
dtv = calloc (dtv_length + 2, sizeof (dtv_t));
if (dtv != NULL)
 {
   /* This is the initial length of the dtv.  */
   dtv[0].counter = dtv_length;

继续上面的实验,当调用到.so中的function时,其TLS被初始化,此时dtv[3]val指向初始化后的TLS变量地址:

68          fn();
(gdb)
0x601808, 0x601804, 0x601800
72          return 0;
(gdb) p $dtv[3]
$3 = {counter = 6297600, pointer = {val = 0x601800, is_static = false}}
(gdb) x/3xw 0x601800
0x601800:       0x55667788      0xaabbccdd      0x11223344

这个时候还可以看看dtv[1]中的内容,正是指向了pthread前面的内存位置:

(gdb) p $dtv[1]
$5 = {counter = 1084229936, pointer = {val = 0x40a00930, is_static = true}}
(gdb) p/x tid
$7 = 0x40a00940

结论:

  • 线程中TLS变量的存储是以模块为单位的

so模块加载

这里也并不太需要查看dlopen等具体实现,由于使用__thread来定义TLS变量,整个实现涉及到ELF加载器的一些细节,深入下去内容较多。这里直接通过实验的手段来了解一些实现即可。

上文已经看到,在创建线程前如果动态加载了.so,dtv数组的大小是会随之增加的。如果是在线程创建后再载入.so呢?

使用g++ -o thread -g -Wall -lpthread -ldl thread.cpp -DTEST_DTV_EXPAND -DSO_CNT=1编译程序,调试得到:

73          load_sos();
(gdb)
0x601e78, 0x601e74, 0x601e70

Breakpoint 1, dump_pthread (id=1084229952) at thread.cpp:44
44          printf("pthread %p, dtv %p\n", pd, dtv);
(gdb) p $dtv[-1]
$3 = {counter = 17, pointer = {val = 0x11, is_static = false}}
(gdb) p $dtv[4]
$4 = {counter = 6299248, pointer = {val = 0x601e70, is_static = false}}

在新载入了.so时,dtv数组大小并没有新增,dtv[4]直接被拿来使用。

因为dtv初始大小为16,那么当载入的.so超过这个数字的时候会怎样?

使用g++ -o thread -g -Wall -lpthread -ldl thread.cpp -DTEST_DTV_EXPAND编译程序:

...
pthread 0x40a00940, dtv 0x6016a0
...
Breakpoint 1, dump_pthread (id=1084229952) at thread.cpp:44
44          printf("pthread %p, dtv %p\n", pd, dtv);
(gdb) p dtv
$2 = (dtv_t *) 0x6078a0
(gdb) p dtv[-1]
$3 = {counter = 32, pointer = {val = 0x20, is_static = false}}
(gdb) p dtv[5]
$4 = {counter = 6300896, pointer = {val = 0x6024e0, is_static = false}}

可以看出,dtv被重新分配了内存(0x6016a0 -> 0x6078a0)并做了扩大。

以上得出结论:

  • 创建线程前dtv的大小会根据载入模块数量决定
  • 创建线程后新载入的模块会动态扩展dtv的大小(必要的时候)

pthread堆栈重用

allocate_stack中分配线程堆栈时,有一个从缓存中取的操作:

allocate_stack(..) {
    ...
    pd = get_cached_stack (&size, &mem);
    ...
}
/* Get a stack frame from the cache.  We have to match by size since
   some blocks might be too small or far too large.  */
get_cached_stack(...) {
    ...
    list_for_each (entry, &stack_cache) // 根据size从stack_cache中取
    { ... }
    ...
    /* Clear the DTV.  */
    dtv_t *dtv = GET_DTV (TLS_TPADJ (result));
    for (size_t cnt = 0; cnt < dtv[-1].counter; ++cnt)
        if (! dtv[1 + cnt].pointer.is_static
                && dtv[1 + cnt].pointer.val != TLS_DTV_UNALLOCATED)
            free (dtv[1 + cnt].pointer.val);
    memset (dtv, '\0', (dtv[-1].counter + 1) * sizeof (dtv_t));

    /* Re-initialize the TLS.  */
    _dl_allocate_tls_init (TLS_TPADJ (result));
}

get_cached_stack会把取出的pthread中的dtv重新初始化。注意 _dl_allocate_tls_init 中是根据模块列表来初始化dtv数组的。

实验

当一个线程退出后,它就可能被当做cache被get_cached_stack取出复用。

使用g++ -o thread -g -Wall -lpthread -ldl thread.cpp -DTEST_CACHE_STACK编译程序,运行:

$ ./thread
..
pthread 0x413c9940, dtv 0x1be46a0
... 
pthread 0x413c9940, dtv 0x1be46a0

回顾BUG

当新创建的线程复用了之前退出的线程堆栈时,由于在_dl_allocate_tls_init中初始化dtv数组时是根据当前载入的模块数量而定。如果在这个时候模块数已经超过了这个复用的dtv数组大小,那么就会出现写入非法的内存。使用valgrind检测就会得到本文开头提到的结果。

由于dtv数组大小通常会稍微大点,所以在新加载的模块数量不够多时程序还不会有问题。可以通过控制测试程序中SO_CNT的大小看看dtv中内容的变化。

另外,我查看了下glibc的更新历史,到目前为止(2.20)这个BUG还没有修复。

参考文档

posted @ 2014-10-07 21:38 Kevin Lynx 阅读(627) | 评论 (1)编辑 收藏

2014年9月21日 #

zookeeper节点数与watch的性能测试

zookeeper中节点数量理论上仅受限于内存,但一个节点下的子节点数量受限于request/response 1M数据 (size of data / number of znodes)

zookeeper的watch机制用于数据变更时zookeeper的主动通知。watch可以被附加到每一个节点上,那么如果一个应用有10W个节点,那zookeeper中就可能有10W个watch(甚至更多)。每一次在zookeeper完成改写节点的操作时就会检测是否有对应的watch,有的话则会通知到watch。Zookeeper-Watcher机制与异步调用原理

本文将关注以下内容:

  • zookeeper的性能是否会受节点数量的影响
  • zookeeper的性能是否会受watch数量的影响

测试方法

在3台机器上分别部署一个zookeeper,版本为3.4.3,机器配置:

Intel(R) Xeon(R) CPU E5-2430 0 @ 2.20GHz

16G

java version "1.6.0_32"
Java(TM) SE Runtime Environment (build 1.6.0_32-b05)
OpenJDK (Taobao) 64-Bit Server VM (build 20.0-b12-internal, mixed mode)

大部分实验JVM堆大小使用默认,也就是1/4 RAM

java -XX:+PrintFlagsFinal -version | grep HeapSize

测试客户端使用zk-smoketest,针对watch的测试则是我自己写的。基于zk-smoketest我写了些脚本可以自动跑数据并提取结果,相关脚本可以在这里找到:https://github.com/kevinlynx/zk-benchmark

测试结果

节点数对读写性能的影响

测试最大10W个节点,度量1秒内操作数(ops):

可见节点数的增加并不会对zookeeper读写性能造成影响。

节点数据大小对读写性能的影响

这个网上其实已经有公认的结论。本身单个节点数据越大,对网络方面的吞吐就会造成影响,所以其数据越大读写性能越低也在预料之中。

写数据会在zookeeper集群内进行同步,所以其速度整体会比读数据更慢。该实验需要把超时时间进行一定上调,同时我也把JVM最大堆大小调整到8G。

测试结果很明显,节点数据大小会严重影响zookeeper效率。

watch对读写性能的影响

zk-smoketest自带的latency测试有个参数--watch_multiple用来指定watch的数量,但其实仅是指定客户端的数量,在server端通过echo whcp | nc 127.0.0.1 4181会发现实际每个节点还是只有一个watch。

在我写的测试中,则是通过创建多个客户端来模拟单个节点上的多个watch。这也更符合实际应用。同时对节点的写也是在另一个独立的客户端中,这样可以避免zookeeper client的实现对测试带来的干扰。

每一次完整的测试,首先是对每个节点添加节点数据的watch,然后在另一个客户端中对这些节点进行数据改写,收集这些改写操作的耗时,以确定添加的watch对这些写操作带来了多大的影响。

图中,0 watch表示没有对节点添加watch;1 watch表示有一个客户端对每个节点进行了watch;3 watch表示有其他3个客户端对每个节点进行了watch;依次类推。

可见,watch对写操作还是有较大影响的,毕竟需要进行网络传输。同样,这里也显示出整个zookeeper的watch数量同节点数量一样对整体性能没有影响。

总体结论

  • 对单个节点的操作并不会因为zookeeper中节点的总数而受到影响
  • 数据大小对zookeeper的性能有较大影响,性能和内存都会
  • 单个节点上独立session的watch数对性能有一定影响

posted @ 2014-09-21 20:56 Kevin Lynx 阅读(654) | 评论 (0)编辑 收藏

2014年9月15日 #

浅析静态库链接原理

静态库的链接基本上同链接目标文件.obj/.o相同,但也有些不同的地方。本文简要描述linux下静态库在链接过程中的一些细节。

静态库文件格式

静态库远远不同于动态库,不涉及到符号重定位之类的问题。静态库本质上只是将一堆目标文件进行打包而已。静态库没有标准,不同的linux下都会有些细微的差别。大致的格式wiki上描述的较清楚:

Global header
-----------------        +-------------------------------
File header 1       ---> | File name
File content 1  |        | File modification timestamp 
-----------------        | Owner ID
File header 2            | Group ID
File content 2           | File mode
-----------------        | File size in bytes
...                      | File magic
                         +-------------------------------

File header很多字段都是以ASCII码表示,所以可以用文本编辑器打开。

静态库本质上就是使用ar命令打包一堆.o文件。我们甚至可以用ar随意打包一些文件:

$ echo 'hello' > a.txt && echo 'world' > b.txt
$ ar -r test.a a.txt b.txt
$ cat test.a
!<arch>
a.txt/          1410628755  60833 100   100644  6         `
hello
b.txt/          1410628755  60833 100   100644  6         `
world

链接过程

链接器在链接静态库时,同链接一般的.o基本相似。链接过程大致可以归纳下图:

总结为:

  • 所有传入链接器的.o都会被链接进最终的可执行程序;链接.o时,会将.o中的global symbolunresolved symbol放入一个临时表
  • 如果多个.o定义了相同的global symbol,那么就会得到多重定义的链接错误
  • 如果链接结束了,unresolved symbol表不为空,那么就会得到符号未定义的链接错误
  • .a静态库处理本质上就是处理其中的每一个.o,不同的是,如果某个.o中没有一个符号属于unresolved symbol表,也就是链接器此时怀疑该.o没有必要,那么其就会被忽略

可以通过一些代码来展示以上过程。在开发C++程序时,可以利用文件静态变量会先于main之前执行做一些可能利于程序结构的事情。如果某个.o(包含静态库中打包的.o)被链接进程序,那么其文件静态变量就会先于main初始化。

// test.cpp
#include <stdio.h>

class Test {
public:
    Test() {
        printf("Test ctor\n");
    }
};

static Test s_test;

// lib.cpp
#include <stdio.h>

class Lib {
public:
    Lib() {
        printf("Lib ctor\n");
    }
};

static Lib s_lib;

// main.cpp
#include <stdio.h>

int main() {
    printf("main\n");
    return 0;
}

以上代码main.cpp中未引用任何test.cpp``lib.cpp中的符号:

$ g++ -o test test.o lib.o main.o
$ ./test
Lib ctor
Test ctor
main

生成的可执行程序执行如预期,其链接了test.o``lib.o。但是如果把lib.o以静态库的形式进行链接,情况就不一样了:为了做对比,基于以上的代码再加一个文件,及修改main.cpp

// libfn.cpp
int sum(int a, int b) {
    return a + b;
}

// main.cpp
#include <stdio.h>

int main() {
    printf("main\n");
    extern int sum(int, int);
    printf("sum: %d\n", sum(2, 3));
    return 0;
}

libfn.olib.o创建为静态库:

$ ar -r libfn.a libfn.o lib.o
$ g++ -o test main.o test.o -lfn -L.
$ ./test
Test ctor
main
sum: 5

因为lib.o没有被链接,导致其文件静态变量也未得到初始化。

调整链接顺序,可以进一步检验前面的链接过程:

# 将libfn.a的链接放在main.o前面

$ g++ -o test test.o -lfn main.o  -L.
main.o: In function `main':
main.cpp:(.text+0x19): undefined reference to `sum(int, int)'
collect2: ld returned 1 exit status

这个问题遇到得比较多,也有点让人觉得莫名其妙。其原因就在于链接器在链接libfn.a的时候,发现libfn.o依然没有被之前链接的*.o引用到,也就是没有任何符号在unresolved symbol table,所以libfn.o也被忽略。

一些实践

在实际开发中还会遇到一些静态库相关的问题。

链接顺序问题

前面的例子已经展示了这个问题。调整库的链接顺序可以解决大部分问题,但当静态库之间存在环形依赖时,则无法通过调整顺序来解决。

-whole-archive

-whole-archive选项告诉链接器把静态库中的所有.o都进行链接,针对以上例子:

$ g++ -o test -L. test.o -Wl,--whole-archive -lfn main.o -Wl,--no-whole-archive
$ ./test
Lib ctor
Test ctor
main
sum: 5

lib.o也被链接了进来。-Wl选项告诉gcc将其作为链接器参数传入;之所以在命令行结尾加上--no-whole-archive是为了告诉编译器不要链接gcc默认的库

可以看出这个方法还是有点暴力了。

–start-group

格式为:

--start-group archives --end-group

位于--start-group --end-group中的所有静态库将被反复搜索,而不是默认的只搜索一次,直到不再有新的unresolved symbol产生为止。也就是说,出现在这里的.o如果发现有unresolved symbol,则可能回到之前的静态库中继续搜索。

$ g++ -o test -L. test.o -Wl,--start-group -lfn main.o -Wl,--end-group
$ ./test
Test ctor
main
sum: 5

查看ldd关于该参数的man page还可以一窥链接过程的细节:

The specified archives are searched repeatedly until no new undefined references are created. Normally, an archive is searched only once in the order that it is specified on the command line. If a symbol in that archive is needed to resolve an undefined symbol referred to by an object in an archive that appears later on the command line, the linker would not be able to resolve that reference. By grouping the archives, they all be searched repeatedly until all possible references are resolved.

嵌套静态库

由于ar创建静态库时本质上只是对文件进行打包,所以甚至可以创建一个嵌套的静态库,从而测试链接器是否会递归处理静态库中的.o

$ ar -r libfn.a libfn.o
$ ar -r liboutfn.a libfn.a lib.o
$ g++ -o test -L. test.o main.o -loutfn
main.o: In function `main':
main.cpp:(.text+0x19): undefined reference to `sum(int, int)'
collect2: ld returned 1 exit status

可见链接器并不会递归处理静态库中的文件

之所以要提到嵌套静态库这个问题,是因为我发现很多时候我们喜欢为一个静态库工程链接其他静态库。当然,这里的链接并非真正的链接(仅是打包),这个过程当然可以聪明到将其他静态库里的.o提取出来然后打包到新的静态库。

如果我们使用的是类似scons这种封装更高的依赖项管理工具,那么它是否会这样干呢?

基于之前的例子,我们使用scons来创建liboutfn.a

# Sconstruct
StaticLibrary('liboutfn.a', ['libfn.a', 'lib.o'])

使用文本编辑器打开liboutfn.a就可以看到其内容,或者使用:

$ ar -tv liboutfn.a
rw-r--r-- 60833/100   1474 Sep 14 02:59 2014 libfn.a
rw-r--r-- 60833/100   2448 Sep 14 02:16 2014 lib.o

可见scons也只是单纯地打包。所以,在scons中构建一个静态库时,再链接其他静态库是没有意义的

参考文档

posted @ 2014-09-15 22:47 Kevin Lynx 阅读(964) | 评论 (2)编辑 收藏

2014年9月9日 #

理解git常用命令原理

git不同于类似SVN这种版本管理系统,虽然熟悉常用的操作就可以满足大部分需求,但为了在遇到麻烦时不至于靠蛮力去尝试,了解git的原理还是很有必要。

文件

通过git管理的文件版本信息全部存放在根目录.git下,稍微看下:

$ ls .git
COMMIT_EDITMSG HEAD branches description index logs packed-refs
FETCH_HEAD ORIG_HEAD config hooks info objects refs

git除了提供给我们平时常用的一些命令之外,还有很多底层命令,可以用于查看以上部分文件表示的东西。

三个区域/三类对象

理解git里的三个区域概念非常重要。git里很多常用的命令都是围绕着这三个区域来做的。它们分别为:

  • working directory,也就是你所操作的那些文件
  • history,你所提交的所有记录,文件历史内容等等。git是个分布式版本管理系统,在你本地有项目的所有历史提交记录;文件历史记录;提交日志等等。
  • stage(index),暂存区域,本质上是个文件,也就是.git/index

git中还有三类常用对象(实际不止三种),理解这三类对象也很重要。分别为:

  • blob,用于表示一个文件
  • tree,用于表示一个目录,索引到若干文件或子目录
  • commit,用于表示一次提交(commit)

所有对象都会以文件的形式保存在.git/objects目录,一个对象一个文件。

接下来把上面所有的内容关联起来。做以下操作:

$ mkdir test && cd test
$ git init
$ ls -a .git/objects # 没有文件
. .. info pack
$ touch readme # working directory里增加了一个readme文件
$ git add readme # 添加一个文件到stage区域
$ git ls-files --stage # 这个命令可以查看stage区域里的内容,可以看到有readme
100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 0 readme
$ ls -a .git/objects # 同时.git/objects增加了一个e6的目录
. .. e6 info pack
$ ls -a .git/objects/e6/ # e6目录下增加了一个文件
. .. 9de29bb2d1d6434b8b29ae775ad8c2e48c5391

上面的操作展示了git中三个区域三个对象的部分关联关系。git中每个对象都以一个40个字符长度的SHA-1哈希值为标识,以这40个字符的前2个字符作为文件夹,以后38个字符为文件名。

基于以上继续操作:

$ git commit -m 'first commit' # commit会将stage里标识的文件提交到history区域
[master (root-commit) 8bf6969] first commit
0 files changed, 0 insertions(+), 0 deletions(-)
create mode 100644 readme
$ ls -a .git/objects # 增加了2个文件,也就是2个对象
. .. 8b e6 e8 info pack
$ git ls-files --stage # stage仅表示当前被版本管理的文件,所以内容不变
100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 0 readme
# git cat-file 命令可以用于查看.git/objects下的文件,意即可用于查看对象
$ git cat-file -t e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 # 这个是之前git add readme产生的文件对象 blob
blob
# 同样我们来查看git commit -m后新增的两个对象
$ ls .git/objects/8b/
f696927c17526eb8f0c6dae8badb968a001ed0
$ git cat-file -t 8bf696927c17526eb8f0c6dae8badb968a001ed0 # 记得带上8b这个文件夹名,才算一个完整的对象ID。这是一个commit对象
commit
$ ls .git/objects/e8
0ad49ace82167de62e498622d70377d913c79e
$ git cat-file -t e80ad49ace82167de62e498622d70377d913c79e # tree对象
tree

区域和对象如何交互的可以用下图描述:

通过git cat-file -p可以查看对象的更多描述,git cat-file -t仅获取对象的类型。做以下操作获得更深的认识:

# 这个commit对象记录了提交者的信息,还包括指向的tree对象
$ git cat-file -p 8bf696927c17526eb8f0c6dae8badb968a001ed0
tree e80ad49ace82167de62e498622d70377d913c79e
author Kevin Lynx <kevinlynx@gmail.com> 1410090424 +0800
committer Kevin Lynx <kevinlynx@gmail.com> 1410090424 +0800
first commit
# 查看tree对象可以看出tree指向的blob对象
$ git cat-file -p e80ad49ace82167de62e498622d70377d913c79e
100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 readme

即使是已经被版本管理的文件,发生改动后(正常改动或合并)都使用git add来重新mark它。创建第二次提交进一步认识:

$ echo 'hello git' > readme
$ touch install
$ git ls-files --stage # 不使用git add,暂存区域内容没变
100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 0 readme
# 此时stage里内容未变,提示no changes added to commit
$ git commit
# On branch master
# Changed but not updated:
# (use "git add <file>..." to update what will be committed)
# (use "git checkout -- <file>..." to discard changes in working directory)
#
# modified: readme
#
# Untracked files:
# (use "git add <file>..." to include in what will be committed)
#
# install
no changes added to commit (use "git add" and/or "git commit -a")
$ git add readme
$ ls .git/objects/ # git add之后.git/objects下新增文件
8b 8d e6 e8 info pack
$ ls .git/objects/8d/
0e41234f24b6da002d962a26c2495ea16a425f
$ git cat-file -p 8d0e41234f24b6da002d962a26c2495ea16a425f # 查看该新增对象
hello git
# 这个时候还可以在提交前撤销git add readme
$ git reset readme # 从history到stage
Unstaged changes after reset:
M readme
$ cat readme
hello git
$ git checkout readme # 从stage到working directory
$ cat readme # 没有内容,回到第一个版本
$ git add install # 添加新创建的文件
$ git ls-files --stage # stage中的内容是最新的readme和新添加的install
100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 0 install
100644 8d0e41234f24b6da002d962a26c2495ea16a425f 0 readme
$ ls .git/objects/
8b 8d e6 e8 info pack

以上,发现一个有趣的现象:新加的install文件的SHA-1哈希值和之前的readme相同,这是因为这2个文件都是空的,内容相同。继续:

$ git commit -m 'second commit'
$ ls .git/objects/ # 提交后新增2个对象
45 72 8b 8d e6 e8 info pack
$ ls .git/objects/72/
b94e949c5fca6092cc74c751a7bb35ee71c283
$ git cat-file -p 72b94e949c5fca6092cc74c751a7bb35ee71c283
tree 45cf0bd049d7eea4558b14f33a894db27c7c1130 # 新创建的tree对象
parent 8bf696927c17526eb8f0c6dae8badb968a001ed0 # commit对象有parent,正是上一次提交
author Kevin Lynx <kevinlynx@gmail.com> 1410094456 +0800
committer Kevin Lynx <kevinlynx@gmail.com> 1410094456 +0800
second commit
# 新创建的tree对象指向了2个文件
$ git cat-file -p 45cf0bd049d7eea4558b14f33a894db27c7c1130
100644 blob e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 install
100644 blob 8d0e41234f24b6da002d962a26c2495ea16a425f readme

需要注意,有时候我们使用git commit -a,它会直接将已经加入版本管理的文件一起提交,从而跳过了git add这个过程。同git很多操作一样,它只是一个快捷操作。

总结

从上面的内容其实已经可以看出git的优势所在,它可以完全不需要服务器就完成一个版本控制系统的所有事情。在.git文件中它记录了所有的文件的所有历史提交,记录了每一次提交的信息。

git的常用操作中还会涉及到分支、远端仓库等,空了再写。

参考文档

posted @ 2014-09-09 21:35 Kevin Lynx 阅读(779) | 评论 (0)编辑 收藏

2014年9月2日 #

C/C++中手动获取调用堆栈

当我们的程序core掉之后,如果能获取到core时的函数调用堆栈将非常有利于定位问题。在Windows下可以使用SEH机制;在Linux下通过gdb使用coredump文件即可。

但有时候由于某些错误导致堆栈被破坏,发生拿不到调用堆栈的情况。

一些基础预备知识本文不再详述,可以参考以下文章:

需要知道的信息:

  • 函数调用对应的call指令本质上是先压入下一条指令的地址到堆栈,然后跳转到目标函数地址
  • 函数返回指令ret则是从堆栈取出一个地址,然后跳转到该地址
  • EBP寄存器始终指向当前执行函数相关信息(局部变量)所在栈中的位置,ESP则始终指向栈顶
  • 每一个函数入口都会保存调用者的EBP值,在出口处都会重设EBP值,从而实现函数调用的现场保存及现场恢复
  • 64位机器增加了不少寄存器,从而使得函数调用的参数大部分时候可以通过寄存器传递;同时寄存器名字发生改变,例如EBP变为RBP

在函数调用中堆栈的情况可用下图说明:

将代码对应起来:

    void g() {
        int *p = 0;
        long a = 0x1234;
        printf("%p %x\n", &a, a);
        printf("%p %x\n", &p, p);
        f();
        *p = 1;
    }
    void b(int argc, char **argv) {
        printf("%p %p\n", &argc, &argv);
        g();
    }
    int main(int argc, char **argv) {
        b(argc, argv);
        return 0;
    }

在函数g()中断点,看看堆栈中的内容(64位机器):

(gdb) p $rbp
$2 = (void *) 0x7fffffffe370
(gdb) p &p
$3 = (int **) 0x7fffffffe368
(gdb) p $rsp
$4 = (void *) 0x7fffffffe360
(gdb) x/8ag $rbp-16
0x7fffffffe360: 0x1234  0x0
0x7fffffffe370: 0x7fffffffe390  0x400631 <b(int, char**)+43>
0x7fffffffe380: 0x7fffffffe498  0x1a561cbc0
0x7fffffffe390: 0x7fffffffe3b0  0x40064f <main(int, char**)+27>

对应的堆栈图:

可以看看例子中0x400631 <b(int, char**)+43>0x40064f <main(int, char**)+27>中的代码:

(gdb) disassemble 0x400631
...
0x0000000000400627 <b(int, char**)+33>: callq  0x400468 <printf@plt>
0x000000000040062c <b(int, char**)+38>: callq  0x4005ae <g()>
0x0000000000400631 <b(int, char**)+43>: leaveq                           # call的下一条指令
...
(gdb) disassemble 0x40064f
... 
0x000000000040063f <main(int, char**)+11>:      mov    %rsi,-0x10(%rbp)
0x0000000000400643 <main(int, char**)+15>:      mov    -0x10(%rbp),%rsi
0x0000000000400647 <main(int, char**)+19>:      mov    -0x4(%rbp),%edi
0x000000000040064a <main(int, char**)+22>:      callq  0x400606 <b(int, char**)>
0x000000000040064f <main(int, char**)+27>:      mov    $0x0,%eax         # call的下一条指令
...

顺带一提,每个函数入口和出口,对应的设置RBP代码为:

(gdb) disassemble g
...
0x00000000004005ae <g()+0>:     push   %rbp               # 保存调用者的RBP到堆栈
0x00000000004005af <g()+1>:     mov    %rsp,%rbp          # 设置自己的RBP
...
0x0000000000400603 <g()+85>:    leaveq                    # 等同于:movq %rbp, %rsp
                                                          #         popq %rbp
0x0000000000400604 <g()+86>:    retq                      

由以上可见,通过当前的RSP或RBP就可以找到调用堆栈中所有函数的RBP;找到了RBP就可以找到函数地址。因为,任何时候的RBP指向的堆栈位置就是上一个函数的RBP;而任何时候RBP所在堆栈中的前一个位置就是函数返回地址。

由此我们可以自己构建一个导致gdb无法取得调用堆栈的例子:

    void f() {
        long *p = 0;
        p = (long*) (&p + 1); // 取得g()的RBP
        *p = 0;  // 破坏g()的RBP
    }
    void g() {
        int *p = 0;
        long a = 0x1234;
        printf("%p %x\n", &a, a);
        printf("%p %x\n", &p, p);
        f();
        *p = 1; // 写0地址导致一次core
    }
    void b(int argc, char **argv) {
        printf("%p %p\n", &argc, &argv);
        g();
    }
    int main(int argc, char **argv) {
        b(argc, argv);
        return 0;
    }

使用gdb运行该程序:

Program received signal SIGSEGV, Segmentation fault.
g () at ebp.c:37
37          *p = 1;
(gdb) bt
Cannot access memory at address 0x8
(gdb) p $rbp
$1 = (void *) 0x0

bt无法获取堆栈,在函数g()中RBP被改写为0,gdb从0偏移一个地址长度即0x8,尝试从0x8内存位置获取函数地址,然后提示Cannot access memory at address 0x8

RBP出现了问题,我们就可以通过RSP来手动获取调用堆栈。因为RSP是不会被破坏的,要通过RSP获取调用堆栈则需要偏移一些局部变量所占的空间:

(gdb) p $rsp
$2 = (void *) 0x7fffffffe360
(gdb) x/8ag $rsp+16             # g()中局部变量占16字节
0x7fffffffe370: 0x7fffffffe390  0x400631 <b(int, char**)+43>
0x7fffffffe380: 0x7fffffffe498  0x1a561cbc0
0x7fffffffe390: 0x7fffffffe3b0  0x40064f <main(int, char**)+27>
0x7fffffffe3a0: 0x7fffffffe498  0x100000000

基于以上就可以手工找到调用堆栈:

g()
0x400631 <b(int, char**)+43>
0x40064f <main(int, char**)+27>

上面的例子本质上也是破坏堆栈,并且仅仅破坏了保存了的RBP。在实际情况中,堆栈可能会被破坏得更多,则可能导致手动定位也较困难。

堆栈被破坏还可能导致更多的问题,例如覆盖了函数返回地址,则会导致RIP错误;例如堆栈的不平衡。导致堆栈被破坏的原因也有很多,例如局部数组越界;delete/free栈上对象等

omit-frame-pointer

使用RBP获取调用堆栈相对比较容易。但现在编译器都可以设置不使用RBP(gcc使用-fomit-frame-pointer,msvc使用/Oy),对于函数而言不设置其RBP意味着可以节省若干条指令。在函数内部则完全使用RSP的偏移来定位局部变量,包括嵌套作用域里的局部变量,即使程序实际运行时不会进入这个作用域。

例如:

    void f2() {
        int a = 0x1234;
        if (a > 0) {
            int b = 0xff;
            b = a;
        }
    }

gcc中使用-fomit-frame-pointer生成的代码为:

(gdb) disassemble f2
Dump of assembler code for function f2:
0x00000000004004a5 <f2+0>:      movl   $0x1234,-0x8(%rsp)    # int a = 0x1234
0x00000000004004ad <f2+8>:      cmpl   $0x0,-0x8(%rsp)       
0x00000000004004b2 <f2+13>:     jle    0x4004c4 <f2+31>      
0x00000000004004b4 <f2+15>:     movl   $0xff,-0x4(%rsp)      # int b = 0xff
0x00000000004004bc <f2+23>:     mov    -0x8(%rsp),%eax
0x00000000004004c0 <f2+27>:     mov    %eax,-0x4(%rsp)
0x00000000004004c4 <f2+31>:     retq

可以发现f2()没有操作RBP之类的指令了。

posted @ 2014-09-02 22:14 Kevin Lynx 阅读(1349) | 评论 (3)编辑 收藏

仅列出标题  下一页