loop_in_codes

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

#

浅析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 阅读(2925) | 评论 (1)编辑 收藏

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 阅读(4467) | 评论 (0)编辑 收藏

浅析静态库链接原理

静态库的链接基本上同链接目标文件.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 阅读(3531) | 评论 (2)编辑 收藏

理解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 阅读(4281) | 评论 (0)编辑 收藏

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 阅读(4876) | 评论 (3)编辑 收藏

基于protobuf的RPC实现

可以对照使用google protobuf RPC实现echo service一文看,细节本文不再描述。

google protobuf只负责消息的打包和解包,并不包含RPC的实现,但其包含了RPC的定义。假设有下面的RPC定义:

service MyService {
        rpc Echo(EchoReqMsg) returns(EchoRespMsg) 
    }

那么要实现这个RPC需要最少做哪些事?总结起来需要完成以下几步:

客户端

RPC客户端需要实现google::protobuf::RpcChannel。主要实现RpcChannel::CallMethod接口。客户端调用任何一个RPC接口,最终都是调用到CallMethod。这个函数的典型实现就是将RPC调用参数序列化,然后投递给网络模块进行发送。

void CallMethod(const ::google::protobuf::MethodDescriptor* method,
                  ::google::protobuf::RpcController* controller,
                  const ::google::protobuf::Message* request,
                  ::google::protobuf::Message* response,
                  ::google::protobuf::Closure* done) {
        ...
        DataBufferOutputStream outputStream(...) // 取决于你使用的网络实现
        request->SerializeToZeroCopyStream(&outputStream);
        _connection->postData(outputStream.getData(), ...
        ...
    }

服务端

服务端首先需要实现RPC接口,直接实现MyService中定义的接口:

class MyServiceImpl : public MyService {
        virtual void Echo(::google::protobuf::RpcController* controller,
            const EchoReqMsg* request,
            EchoRespMsg* response,
            ::google::protobuf::Closure* done) {
            ...
            done->Run();
        }
    }

标示service&method

基于以上,可以看出服务端根本不知道客户端想要调用哪一个RPC接口。从服务器接收到网络消息,到调用到MyServiceImpl::Echo还有很大一段距离。

解决方法就是在网络消息中带上RPC接口标识。这个标识可以直接带上service name和method name,但这种实现导致网络消息太大。另一种实现是基于service name和method name生成一个哈希值,因为接口不会太多,所以较容易找到基本不冲突的字符串哈希算法。

无论哪种方法,服务器是肯定需要建立RPC接口标识到protobuf service对象的映射的。

这里提供第三种方法:基于option的方法。

protobuf中option机制类似于这样一种机制:service&method被视为一个对象,其有很多属性,属性包含内置的,以及用户扩展的。用户扩展的就是option。每一个属性有一个值。protobuf提供访问service&method这些属性的接口。

首先扩展service&method的属性,以下定义这些属性的key:

extend google.protobuf.ServiceOptions {
      required uint32 global_service_id = 1000; 
    }
    extend google.protobuf.MethodOptions {
      required uint32 local_method_id = 1000;
    }

应用层定义service&method时可以指定以上key的值:

service MyService
    {
        option (arpc.global_service_id) = 2302; 

        rpc Echo(EchoReqMsg) returns(EchoRespMsg) 
        {
            option (arpc.local_method_id) = 1;
        }
        rpc Echo_2(EchoReqMsg) returns(EchoRespMsg) 
        {
            option (arpc.local_method_id) = 2;
        }
        ...
    }

以上相当于在整个应用中,每个service都被赋予了唯一的id,单个service中的method也有唯一的id。

然后可以通过protobuf取出以上属性值:

void CallMethod(const ::google::protobuf::MethodDescriptor* method,
                  ::google::protobuf::RpcController* controller,
                  const ::google::protobuf::Message* request,
                  ::google::protobuf::Message* response,
                  ::google::protobuf::Closure* done) {
        ...
        google::protobuf::ServiceDescriptor *service = method->service();
        uint32_t serviceId = (uint32_t)(service->options().GetExtension(global_service_id));
        uint32_t methodId = (uint32_t)(method->options().GetExtension(local_method_id));
        ...
    }

考虑到serviceId methodId的范围,可以直接打包到一个32位整数里:

uint32_t ret = (serviceId << 16) | methodId;

然后就可以把这个值作为网络消息头的一部分发送。

当然服务器端是需要建立这个标识值到service的映射的:

bool MyRPCServer::registerService(google::protobuf::Service *rpcService) {
        const google::protobuf::ServiceDescriptor = rpcService->GetDescriptor();
        int methodCnt = pSerDes->method_count();

        for (int i = 0; i < methodCnt; i++) {
            google::protobuf::MethodDescriptor *pMethodDes = pSerDes->method(i);
            uint32_t rpcCode = PacketCodeBuilder()(pMethodDes); // 计算出映射值
            _rpcCallMap[rpcCode] = make_pair(rpcService, pMethodDes); // 建立映射
        }
        return true;
    }

服务端收到RPC调用后,取出这个标识值,然后再从_rpcCallMap中取出对应的service和method,最后进行调用:

google::protobuf::Message* response = _pService->GetResponsePrototype(_pMethodDes).New();
    // 用于回应的closure
    RPCServerClosure *pClosure = new (nothrow) RPCServerClosure( 
            _channelId, _pConnection, _pReqMsg, pResMsg, _messageCodec, _version);
    RPCController *pController = pClosure->GetRpcController();
    ...
    // protobuf 生成的CallMethod,会自动调用到Echo接口
    _pService->CallMethod(_pMethodDes, pController, _pReqMsg, pResMsg, pClosure);

参考

posted @ 2014-08-31 19:40 Kevin Lynx 阅读(5948) | 评论 (0)编辑 收藏

分布式环境中的负载均衡策略

在分布式系统中相同的服务常常会部署很多台,每一台被称为一个服务节点(实例)。通过一些负载均衡策略将服务请求均匀地分布到各个节点,以实现整个系统支撑海量请求的需求。本文描述一些简单的负载均衡策略。

Round-robin

简单地轮询。记录一个选择位置,每次请求来时调整该位置到下一个节点:

curId = ++curId % nodeCnt

随机选择

随机地在所有节点中选择:

id = random(nodeCnt);

本机优先

访问后台服务的访问者可能本身是一个整合服务,或者是一个proxy,如果后台服务节点恰好有节点部署在本机的,则可以优先使用。在未找到本机节点时则可以继续走Round-robin策略:

if (node->ip() == local_ip) {
    return node;
} else {
    return roundRobin();
}

一旦遍历到本机节点,则后面的请求会一直落到本机节点。所以这里可以加上一些权重机制,仅是保证本机节点会被优先选择,但不会被一直选择。例如:

// initial
cur_weight = 100;
...
// select node
cur_weight -= 5;
if (cur_weight <= 0)
    cur_weight = 100;
if (cur_weight > 50 && node->ip() == local_ip) {
    return node;
} else {
    return roundRobin();
}

本机房优先

服务节点可能会被部署到多个机房,有时候确实是需要考虑跨机房服务。同本机优先策略类似,本机房优先则是优先考虑位于相同机房内的服务节点。该请求是从哪个机房中的前端服务发送过来的,则需要前端在请求参数中携带上机房ID。

在服务节点对应的数据结构中,也最好按照机房来组织。

本机房优先策略实际上会作为节点选择的第一道工序,它可以把非本机房的节点先过滤掉,然后再传入后面的各种节点选择策略。这里还可以考虑节点数参数,如果本机房的节点过少,则可以不使用该策略,避免流量严重不均。

Weighted Round-Robin

加权轮询。相对于普通轮询而言,该策略中每一个节点都有自己的权重,优先选择权重更大的节点。权重可以根据机器性能预先配置。摘抄一下网上的算法:

假设有一组服务器S = {S0, S1, …, Sn-1},W(Si)表示服务器Si的权值,一个
指示变量i表示上一次选择的服务器,指示变量cw表示当前调度的权值,max(S)
表示集合S中所有服务器的最大权值,gcd(S)表示集合S中所有服务器权值的最大
公约数。变量i初始化为-1,cw初始化为零。

while (true) {
  i = (i + 1) mod n;
  if (i == 0) {
     cw = cw - gcd(S); 
     if (cw <= 0) {
       cw = max(S);
       if (cw == 0)
         return NULL;
     }
  } 
  if (W(Si) >= cw) 
    return Si;
}

遍历完所有节点后权重衰减,衰减到0后重新开始。这样可以让权重更大的节点被选择得更多。

Consistent Hash

一致性哈希。一致性哈希用于在分布式环境中,分布在各个节点上的请求,不会因为新增节点(扩容)或减少节点(节点宕机)而变化。如果每个服务节点上都有自己的缓存,其保存了该节点响应请求时的回应。正常情况下,这些缓存都可以很好地被运用,也即cache命中率较高。

如果某个节点不可用了,我们的选择策略又是基于所有节点的公平选择,那么原来一直分配在节点A上请求就很可能被分配到节点B上,从而导致节点A上的缓存较难被命中。这个时候就可以运用一致性哈希来解决。

其基本思想是,在节点选择区间内,在找节点时以顺时针方向找到不小于该请求对应的哈希值的节点。在这个区间里增加很多虚拟节点,每一个虚拟节点相当于一个物理节点的引用,这样相当于把物理节点变成了一个哈希值区间。这个哈希值区间不会因为增加节点和减少节点而变化,那么对某个请求而言,它就会始终落到这个区间里,也就会始终被分配到原来的节点。

至于这个不可用的节点,其上的请求也会被均匀地分配到其他节点中。

摘抄网上的一段代码:

// 添加一个物理节点时,会随之增加很多虚拟节点
template <class Node, class Data, class Hash>
size_t HashRing<Node, Data, Hash>::AddNode(const Node& node)
{
    size_t hash;
    std::string nodestr = Stringify(node);
    for (unsigned int r = 0; r < replicas_; r++) {
        hash = hash_((nodestr + Stringify(r)).c_str());
        ring_[hash] = node;  // 物理节点和虚拟节点都保存在一个std::map中
    }
    return hash;
}

// 选择data对应的节点,data可以是请求
template <class Node, class Data, class Hash>
const Node& HashRing<Node, Data, Hash>::GetNode(const Data& data) const
{
    if (ring_.empty()) {
        throw EmptyRingException();
    }
    size_t hash = hash_(Stringify(data).c_str()); // 对请求进行哈希
    typename NodeMap::const_iterator it;
    // Look for the first node >= hash
    it = ring_.lower_bound(hash); // 找到第一个不小于请求哈希的节点
    if (it == ring_.end()) {
        // Wrapped around; get the first node
        it = ring_.begin();
    }
    return it->second;
}

参考一致性 hash 算法(consistent hashing)Consistent Hash Ring

posted @ 2014-08-26 00:11 Kevin Lynx 阅读(3487) | 评论 (0)编辑 收藏

select真的有限制吗

在刚开始学习网络编程时,似乎莫名其妙地就会被某人/某资料告诉select函数是有fd(file descriptor)数量限制的。在最近的一次记忆里还有个人笑说select只支持64个fd。我甚至还写过一篇不负责任甚至错误的博客(突破select的FD_SETSIZE限制)。有人说,直接重新定义FD_SETSIZE就可以突破这个select的限制,也有人说除了重定义这个宏之外还的重新编译内核。

事实具体是怎样的?实际上,造成这些混乱的原因恰好是不同平台对select的实现不一样。

Windows的实现

MSDN.aspx)上对select的说明:

int select(
  _In_     int nfds,
  _Inout_  fd_set *readfds,
  _Inout_  fd_set *writefds,
  _Inout_  fd_set *exceptfds,
  _In_     const struct timeval *timeout
);

nfds [in] Ignored. The nfds parameter is included only for compatibility with Berkeley sockets.

第一个参数MSDN只说没有使用,其存在仅仅是为了保持与Berkeley Socket的兼容。

The variable FD_SETSIZE determines the maximum number of descriptors in a set. (The default value of FD_SETSIZE is 64, which can be modified by defining FD_SETSIZE to another value before including Winsock2.h.) Internally, socket handles in an fd_set structure are not represented as bit flags as in Berkeley Unix.

Windows上select的实现不同于Berkeley Unix,后者使用位标志来表示socket

在MSDN的评论中有人提到:

Unlike the Linux versions of these macros which use a single calculation to set/check the fd, the Winsock versions use a loop which goes through the entire set of fds each time you call FD_SET or FD_ISSET (check out winsock2.h and you’ll see). So you might want to consider an alternative if you have thousands of sockets!

不同于Linux下处理fd_set的那些宏(FD_CLR/FD_SET之类),Windows上这些宏的实现都使用了一个循环,看看这些宏的大致实现(Winsock2.h):

#define FD_SET(fd, set) do { \
    u_int __i; \
    for (__i = 0; __i < ((fd_set FAR *)(set))->fd_count; __i++) { \
        if (((fd_set FAR *)(set))->fd_array[__i] == (fd)) { \
            break; \
        } \
    } \
    if (__i == ((fd_set FAR *)(set))->fd_count) { \
        if (((fd_set FAR *)(set))->fd_count < FD_SETSIZE) { \
            ((fd_set FAR *)(set))->fd_array[__i] = (fd); \
            ((fd_set FAR *)(set))->fd_count++; \
        } \
    } \
} while(0)

看下Winsock2.h中关于fd_set的定义:

typedef struct fd_set {
    u_int fd_count;
    SOCKET fd_array[FD_SETSIZE];
} fd_set;

再看一篇更重要的MSDN Maximum Number of Sockets Supported.aspx):

The Microsoft Winsock provider limits the maximum number of sockets supported only by available memory on the local computer. The maximum number of sockets that a Windows Sockets application can use is not affected by the manifest constant FD_SETSIZE. If an application is designed to be capable of working with more than 64 sockets using the select and WSAPoll functions, the implementor should define the manifest FD_SETSIZE in every source file before including the Winsock2.h header file.

Windows上select支持的socket数量并不受宏FD_SETSIZE的影响,而仅仅受内存的影响。如果应用程序想使用超过FD_SETSIZE的socket,仅需要重新定义FD_SETSIZE即可。

实际上稍微想想就可以明白,既然fd_set里面已经有一个socket的数量计数,那么select的实现完全可以使用这个计数,而不是FD_SETSIZE这个宏。那么结论是,select至少在Windows上并没有socket支持数量的限制。当然效率问题这里不谈。

这看起来推翻了我们一直以来没有深究的一个事实。

Linux的实现

在上面提到的MSDN中,其实已经提到了Windows与Berkeley Unix实现的不同。在select的API文档中也看到了第一个参数并没有说明其作用。看下Linux的man

nfds is the highest-numbered file descriptor in any of the three sets, plus 1.

第一个参数简单来说就是最大描述符+1。

An fd_set is a fixed size buffer. Executing FD_CLR() or FD_SET() with a value of fd that is negative or is equal to or larger than FD_SETSIZE will result in undefined behavior.

明确说了,如果调用FD_SET之类的宏fd超过了FD_SETSIZE将导致undefined behavior。也有人专门做了测试:select system call limitation in Linux。也有现实遇到的问题:socket file descriptor (1063) is larger than FD_SETSIZE (1024), you probably need to rebuild Apache with a larger FD_SETSIZE

看起来在Linux上使用select确实有FD_SETSIZE的限制。有必要看下相关的实现 fd_set.h

typedef __uint32_t      __fd_mask;

/* 32 = 2 ^ 5 */
#define __NFDBITS       (32)
#define __NFDSHIFT      (5)
#define __NFDMASK       (__NFDBITS - 1)

/*
 * Select uses bit fields of file descriptors.  These macros manipulate
 * such bit fields.  Note: FD_SETSIZE may be defined by the user.
 */

#ifndef FD_SETSIZE
#define FD_SETSIZE      256
#endif

#define __NFD_SIZE      (((FD_SETSIZE) + (__NFDBITS - 1)) / __NFDBITS)

typedef struct fd_set {
    __fd_mask       fds_bits[__NFD_SIZE];
} fd_set;

在这份实现中不同于Windows实现,它使用了位来表示fd。看下FD_SET系列宏的大致实现:

#define FD_SET(n, p)    \
   ((p)->fds_bits[(unsigned)(n) >> __NFDSHIFT] |= (1 << ((n) & __NFDMASK)))

添加一个fd到fd_set中也不是Windows的遍历,而是直接位运算。这里也有人对另一份类似实现做了剖析:linux的I/O多路转接select的fd_set数据结构和相应FD_宏的实现分析。在APUE中也提到fd_set

这种数据类型(fd_set)为每一可能的描述符保持了一位。

既然fd_set中不包含其保存了多少个fd的计数,那么select的实现里要知道自己要处理多少个fd,那只能使用FD_SETSIZE宏去做判定,但Linux的实现选用了更好的方式,即通过第一个参数让应用层告诉select需要处理的最大fd(这里不是数量)。那么其实现大概为:

for (int i = 0; i < nfds; ++i) {
    if (FD_ISSET...
       ...
}

如此看来,Linux的select实现则是受限于FD_SETSIZE的大小。这里也看到,fd_set使用位数组来保存fd,那么fd本身作为一个int数,其值就不能超过FD_SETSIZE这不仅仅是数量的限制,还是其取值的限制。实际上,Linux上fd的取值是保证了小于FD_SETSIZE的(但不是不变的)Is the value of a Linux file descriptor always smaller than the open file limits?

Each process is further limited via the setrlimit(2) RLIMIT_NOFILE per-process limit on the number of open files. 1024 is a common RLIMIT_NOFILE limit. (It’s very easy to change this limit via /etc/security/limits.conf.)

fd的取值会小于RLIMIT_NOFILE,有很多方法可以改变这个值。这个值默认情况下和FD_SETSIZE应该是一样的。这个信息告诉我们,Linux下fd的取值应该是从0开始递增的(理论上,实际上还有stdin/stdout/stderr之类的fd)。这才能保证select的那些宏可以工作。

应用层使用

标准的select用法应该大致如下:

while (true) {
    ...
    select(...)
    for-each socket {
        if (FD_ISSET(fd, set))
            ...
    }

    ...
}

即遍历目前管理的fd,通过FD_ISSET去判定当前fd是否有IO事件。因为Windows的实现FD_ISSET都是一个循环,所以有了另一种不跨平台的用法:

while (true) {
    ...
    select(. &read_sockets, &write_sockets..)
    for-each read_socket {
        use fd.fd_array[i)
    }
    ...
}

总结

  • Windows上select没有fd数量的限制,但因为使用了循环来检查,所以效率相对较低
  • Linux上selectFD_SETSIZE的限制,但其相对效率较高

posted @ 2014-06-01 23:45 Kevin Lynx 阅读(4289) | 评论 (1)编辑 收藏

Muduo源码阅读

最近简单读了下muduo的源码,本文对其主要实现/结构简单总结下。

muduo的主要源码位于net文件夹下,base文件夹是一些基础代码,不影响理解网络部分的实现。muduo主要类包括:

  • EventLoop
  • Channel
  • Poller
  • TcpConnection
  • TcpClient
  • TcpServer
  • Connector
  • Acceptor
  • EventLoopThread
  • EventLoopThreadPool

其中,Poller(及其实现类)包装了Poll/EPoll,封装了OS针对设备(fd)的操作;Channel是设备fd的包装,在muduo中主要包装socket;TcpConnection抽象一个TCP连接,无论是客户端还是服务器只要建立了网络连接就会使用TcpConnection;TcpClient/TcpServer分别抽象TCP客户端和服务器;Connector/Acceptor分别包装TCP客户端和服务器的建立连接/接受连接;EventLoop是一个主控类,是一个事件发生器,它驱动Poller产生/发现事件,然后将事件派发到Channel处理;EventLoopThread是一个带有EventLoop的线程;EventLoopThreadPool自然是一个EventLoopThread的资源池,维护一堆EventLoopThread。

阅读库源码时可以从库的接口层着手,看看关键功能是如何实现的。对于muduo而言,可以从TcpServer/TcpClient/EventLoop/TcpConnection这几个类着手。接下来看看主要功能的实现:

建立连接

    TcpClient::connect 
        -> Connector::start 
            -> EventLoop::runInLoop(Connector::startInLoop...
            -> Connector::connect             

EventLoop::runInLoop接口用于在this所在的线程运行某个函数,这个后面看下EventLoop的实现就可以了解。 网络连接的最终建立是在Connector::connect中实现,建立连接之后会创建一个Channel来代表这个socket,并且绑定事件监听接口。最后最重要的是,调用Channel::enableWritingChannel有一系列的enableXX接口,这些接口用于标识自己关心某IO事件。后面会看到他们的实现。

Connector监听的主要事件无非就是连接已建立,用它监听读数据/写数据事件也不符合设计。TcpConnection才是做这种事的。

客户端收发数据

当Connector发现连接真正建立好后,会回调到TcpClient::newConnection,在TcpClient构造函数中:

    connector_->setNewConnectionCallback(
      boost::bind(&TcpClient::newConnection, this, _1));

TcpClient::newConnection中创建一个TcpConnection来代表这个连接:

    TcpConnectionPtr conn(new TcpConnection(loop_,
                                            connName,
                                            sockfd,
                                            localAddr,
                                            peerAddr));

    conn->setConnectionCallback(connectionCallback_);
    conn->setMessageCallback(messageCallback_);
    conn->setWriteCompleteCallback(writeCompleteCallback_);
    ...
    conn->connectEstablished();

并同时设置事件回调,以上设置的回调都是应用层(即库的使用者)的接口。每一个TcpConnection都有一个Channel,毕竟每一个网络连接都对应了一个socket fd。在TcpConnection构造函数中创建了一个Channel,并设置事件回调函数。

TcpConnection::connectEstablished函数最主要的是通知Channel自己开始关心IO读取事件:

    void TcpConnection::connectEstablished()
    {
        ...
        channel_->enableReading();

这是自此我们看到的第二个Channel::enableXXX接口,这些接口是如何实现关心IO事件的呢?这个后面讲到。

muduo的数据发送都是通过TcpConnection::send完成,这个就是一般网络库中在不使用OS的异步IO情况下的实现:缓存应用层传递过来的数据,在IO设备可写的情况下尽量写入数据。这个主要实现在TcpConnection::sendInLoop中。

    TcpConnection::sendInLoop(....) {
        ...
        // if no thing in output queue, try writing directly
        if (!channel_->isWriting() && outputBuffer_.readableBytes() == 0)  // 设备可写且没有缓存时立即写入
        { 
            nwrote = sockets::write(channel_->fd(), data, len);
        }
        ...
        // 否则加入数据到缓存,等待IO可写时再写
        outputBuffer_.append(static_cast<const char*>(data)+nwrote, remaining);
        if (!channel_->isWriting())
        {
            // 注册关心IO写事件,Poller就会对写做检测
            channel_->enableWriting();
        }
        ...     
    }

当IO可写时,Channel就会回调TcpConnection::handleWrite(构造函数中注册)

    void TcpConnection::handleWrite()
    {
        ...
        if (channel_->isWriting())
        {
            ssize_t n = sockets::write(channel_->fd(),
                               outputBuffer_.peek(),
                               outputBuffer_.readableBytes());

服务器端的数据收发同客户端机制一致,不同的是连接(TcpConnection)的建立方式不同。

服务器接收连接

服务器接收连接的实现在一个网络库中比较重要。muduo中通过Acceptor类来接收连接。在TcpClient中,其Connector通过一个关心Channel可写的事件来通过连接已建立;在Acceptor中则是通过一个Channel可读的事件来表示有新的连接到来:

    Acceptor::Acceptor(....) {
        ...
        acceptChannel_.setReadCallback(
            boost::bind(&Acceptor::handleRead, this));
        ... 
    }

    void Acceptor::handleRead()
    {
        ...
        int connfd = acceptSocket_.accept(&peerAddr); // 接收连接获得一个新的socket
        if (connfd >= 0)
        {
            ...
            newConnectionCallback_(connfd, peerAddr); // 回调到TcpServer::newConnection

TcpServer::newConnection中建立一个TcpConnection,并将其附加到一个EventLoopThread中,简单来说就是给其配置一个线程:

    void TcpServer::newConnection(int sockfd, const InetAddress& peerAddr)
    {
        ...
        EventLoop* ioLoop = threadPool_->getNextLoop();
        TcpConnectionPtr conn(new TcpConnection(ioLoop,
                                                connName,
                                                sockfd,
                                                localAddr,
                                                peerAddr));
        connections_[connName] = conn;
        ...
        ioLoop->runInLoop(boost::bind(&TcpConnection::connectEstablished, conn));

IO的驱动

之前提到,一旦要关心某IO事件了,就调用Channel::enableXXX,这个如何实现的呢?

    class Channel {
        ...
        void enableReading() { events_ |= kReadEvent; update(); }
        void enableWriting() { events_ |= kWriteEvent; update(); }
       
    void Channel::update()
    {
        loop_->updateChannel(this);
    }

    void EventLoop::updateChannel(Channel* channel)
    {
        ...
        poller_->updateChannel(channel);
    }

最终调用到Poller::upateChannel。muduo中有两个Poller的实现,分别是Poll和EPoll,可以选择简单的Poll来看:

    void PollPoller::updateChannel(Channel* channel)
    {
      ...
      if (channel->index() < 0)
      {
        // a new one, add to pollfds_
        assert(channels_.find(channel->fd()) == channels_.end());
        struct pollfd pfd;
        pfd.fd = channel->fd();
        pfd.events = static_cast<short>(channel->events()); // 也就是Channel::enableXXX操作的那个events_
        pfd.revents = 0;
        pollfds_.push_back(pfd); // 加入一个新的pollfd
        int idx = static_cast<int>(pollfds_.size())-1;
        channel->set_index(idx);
        channels_[pfd.fd] = channel;

可见Poller就是把Channel关心的IO事件转换为OS提供的IO模型数据结构上。通过查看关键的pollfds_的使用,可以发现其主要是在Poller::poll接口里。这个接口会在EventLoop的主循环中不断调用:

    void EventLoop::loop()
    {
      ...
      while (!quit_)
      {
        activeChannels_.clear();
        pollReturnTime_ = poller_->poll(kPollTimeMs, &activeChannels_);
        ...
        for (ChannelList::iterator it = activeChannels_.begin();
            it != activeChannels_.end(); ++it)
        {
          currentActiveChannel_ = *it;
          currentActiveChannel_->handleEvent(pollReturnTime_); // 获得IO事件,通知各注册回调
        }

整个流程可总结为:各Channel内部会把自己关心的事件告诉给Poller,Poller由EventLoop驱动检测IO,然后返回哪些Channel发生了事件,EventLoop再驱动这些Channel调用各注册回调。

从这个过程中可以看出,EventLoop就是一个事件产生器。

线程模型

在muduo的服务器中,muduo的线程模型是怎样的呢?它如何通过线程来支撑高并发呢?其实很简单,它为每一个线程配置了一个EventLoop,这个线程同时被附加了若干个网络连接,这个EventLoop服务于这些网络连接,为这些连接收集并派发IO事件。

回到TcpServer::newConnection中:

    void TcpServer::newConnection(int sockfd, const InetAddress& peerAddr)
    {
      ...
      EventLoop* ioLoop = threadPool_->getNextLoop();
      ...
      TcpConnectionPtr conn(new TcpConnection(ioLoop, // 使用这个选择到的线程中的EventLoop
                                              connName,
                                              sockfd,
                                              localAddr,
                                              peerAddr));
      ...
      ioLoop->runInLoop(boost::bind(&TcpConnection::connectEstablished, conn));

注意TcpConnection::connectEstablished是如何通过Channel注册关心的IO事件到ioLoop的。

极端来说,muduo的每一个连接线程可以只为一个网络连接服务,这就有点类似于thread per connection模型了。

网络模型

传说中的Reactor模式,以及one loop per thread,基于EventLoop的作用,以及线程池与TcpConnection的关系,可以醍醐灌顶般理解以下这张muduo的网络模型图了:


总结

本文主要对muduo的主要结构及主要机制的实现做了描述,其他如Buffer的实现、定时器的实现大家都可以自行研究。muduo的源码很清晰,通过源码及配合陈硕博客上的内容可以学到一些网络编程方面的经验。

posted @ 2014-05-04 18:22 Kevin Lynx 阅读(13694) | 评论 (3)编辑 收藏

记一次堆栈平衡错误

最近在一个使用Visual Studio开发的C++程序中,出现了如下错误:

Run-Time Check Failure #0 - The value of ESP was not properly saved across a function call. This is usually a result of calling a function declared with one calling convention with a function pointer declared with a different calling convention.

这个错误主要指的就是函数调用堆栈不平衡。在C/C++程序中,调用一个函数前会保存当前堆栈信息,目标函数返回后会把堆栈恢复到调用前的状态。函数的参数、局部变量会影响堆栈。而函数堆栈不平衡,一般是因为函数调用方式和目标函数定义方式不一致导致,例如:

void __stdcall func(int a) {
}

int main(int argc, char* argv[]) {
    typedef void (*funcptr)(int);
    funcptr ptr = (funcptr) func;
    ptr(1); // 返回后导致堆栈不平衡
    return 0;
}

__stdcall修饰的函数,其函数参数的出栈由被调用者自己完成,而__cdecl,也就是C/C++函数的默认调用约定,则是调用者完成参数出栈。

Visual Studio在debug模式下会在我们的代码中加入不少检查代码,例如以上代码对应的汇编中,就会增加一个检查堆栈是否平衡的函数调用,当出现问题时,就会出现提示Run-Time Check Failure...这样的错误对话框:

call dword ptr [ptr]  ; ptr(1)
add  esp,4  ; cdecl方式,调用者清除参数
cmp  esi,esp  
call @ILT+1345(__RTC_CheckEsp) (0B01546h) ; 检查堆栈是否平衡

但是我们的程序不是这种低级错误。我们调用的函数是放在dll中的,调用约定显示定义为__stdcall,函数声明和实现一致。大致的结构如下:

IParser *parser = CreateParser();
parser->Begin();
...
...
parser->End();
parser->Release(); // 返回后导致堆栈不平衡

IParser的实现在一个dll里,这反而是一个误导人的信息。parser->Release返回后,堆栈不平衡,并且仅仅少了一个字节。一个字节怎么来的?

解决这个问题主要的手段就是跟反汇编,在关键位置查看寄存器和堆栈的内容。编译器生成的代码是正确的,而我们自己的代码乍看上去也没问题。最后甚至使用最傻逼的调试手段–逐行语句注释查错。

具体查错过程就不细说了。解决问题往往需要更多的冷静,和清晰的思路。最终我使用的方法是,在进入Release之前记录堆栈指针的值,堆栈指针的值会被压入堆栈,以在函数返回后从堆栈弹出,恢复堆栈指针。Release的实现很简单,就是删除一个Parser这个对象,但这个对象的析构会导致很多其他对象被析构。我就逐层地检查,是在哪个函数里改变了堆栈里的内容。

理论上,函数本身是操作不到调用者的堆栈的。而现在看来,确实是被调用函数,也就是Release改写了调用者的堆栈内容。要改变堆栈的内容,只有通过局部变量的地址才能做到。

最终,我发现在调用完以下函数后,我跟踪的堆栈地址内容发生了改变:

call llvm::RefCountedBase<clang::TargetOptions>::Release (10331117h)

因为注意到TargetOptions这个字眼,想起了在parser->Begin里有涉及到这个类的使用,类似于:

TargetOptions TO;
...
TargetInfo *TI = TargetInfo::CreateTargetInfo(m_inst.getDiagnostics(), TO);

这部分初始化代码,是直接从网上复制的,因为并不影响主要逻辑,所以从来没对这块代码深究。查看CreateTargetInfo的源码,发现这个函数将TO这个局部变量的地址保存了下来

而在Release中,则会对这个保存的临时变量进行删除操作,形如:

void Delete() const {
  assert (ref_cnt > 0 && "Reference count is already zero.");
  if (--ref_cnt == 0) delete static_cast<const Derived*>(this);
}

但是,问题并不在于对一个局部变量地址进行deletedelete在调试模式下是做了内存检测的,那会导致一种断言。

TargetOptions包含了ref_cnt这个成员。当出了Begin作用域后,parser保存的TargetOptions的地址,指向的内容(堆栈)发生了改变,也就是ref_cnt这个成员变量的值不再正常。由于一些巧合,主要是代码中各个局部变量、函数调用顺序、函数参数个数(曾尝试去除Begin的参数,可以避免错误提示),导致在调用Release前堆栈指针恰好等于之前保存的TargetOptions的地址。注意,之前保存的TargetOptions的地址,和调用Release前的堆栈指针值相同了。

而在TargetOptionsDelete函数中,进行了--ref_cnt,这个变量是TargetOptions的第一个成员,它的减1,也就导致了堆栈内容的改变。

至此,整个来龙去脉算是摸清。

posted @ 2013-08-15 23:01 Kevin Lynx 阅读(5143) | 评论 (1)编辑 收藏

仅列出标题
共12页: 1 2 3 4 5 6 7 8 9 Last