Yet Another Coder

Do Not Panic!

初始化:数组和类

前段时间有个项目,其中有一部分从磁盘读出数据的功能,我们用64块2M内存来保存读出的数据。测试的时候,发现读取速度非常之慢,与理想情况有1个数量级的差距。于是在查错调优的时候,发现了这个问题。

  • 怎么了?

2M内存在代码中用typedef一个数组来表示:

const int SIZE_OF_MEM = 2*1024*1024;
typedef char Block[SIZE_OF_MEM];

简化读取逻辑,去掉其他细节之后,得到数据块使用部分的模拟代码:

const int n = 100;
void *p[n];
for (int i = 0; i < n; ++i) { // 1
    p[i] = new Block();
}
for (int i = 0; i < 1000000 * n; ++i) { // 2
    p[i%n] = new(p[i%n]) Block(); //取余以减少测试需要的内存数量
}
for (int i = 0; i < n; ++i) {
    delete p[i];
}
return 0;

经历数次错误的怀疑/验证,通过对整体逻辑的一步步计时,最后发现中间的第二个for循环里的逻辑就是症结所在。平均每一次的new-placement耗时在毫秒级(milliseconds),大大超出预期,导致读取模型工作效率低下。

看起来数组typedef不灵光,猜测数组可能存在某些特性,导致new-placement运行效率远低于预期。换成类试试看:

const int SIZE_OF_MEM=2*1024*1024;
class Block
{
public:
    Block() {}
private:
    char data[SIZE_OF_MEM];
};

再一次计时,1,000,000次的执行时间不到200ms,看起来正常多了。

这张图对比了测试代码new-placementblock为array和class时的执行效率差异。其中,array由于耗时太久,只执行了1000次,而class执行1,000,000次。 Comparison of Array and Class

为什么定义成类比typedef的数组快这么多?看看new-placement语句的汇编代码怎么说(均为VS2008编译)。 VS2008 assembly of array and class

汇编代码清楚的显示两种定义的不同。对于数组,在new操作完成后,有memset,而对于类,则有构造函数的调用。对于2M内存,数组类型在new完成后要被初始化为0,这就是低效率的罪魁祸首。

再来看看Linux下gcc的汇编代码: linux assembly of array and class GCC和VS2008编译结果一致,看起来应该不是编译器bug,:)

  • 为什么?

找找C++标准,关于初始化的部分有这么一条:

An object whose initializer is an empty set of parentheses, i.e., (), shall be value-initialized.

什么是value-initialized?

To value-initialize an object of type T means:

  • if T is a (possibly cv-qualified) class type (Clause 9) with a user-provided constructor (12.1), then the default constructor for T is called (and the initialization is ill-formed if T has no accessible default constructor);

  • if T is a (possibly cv-qualified) non-union class type without a user-provided constructor, then the object is zero-initialized and, if T’s implicitly-declared default constructor is non-trivial, that constructor is called.

  • if T is an array type, then each element is value-initialized;

  • otherwise, the object is zero-initialized.

这种空的小括号,(),一般情况下不能用来表示初始化某个对象。但是,在少数情况下,它是合法的,上面的new就属于这些少数情况里的一个。在这种情况下,要初始化的类型又是数组,于是不幸落入第三种情况,每个元素都被初始化为0。Linux下的汇编代码清楚的表明了这个过程:

0x000000000044187c cmpq   $0x0,-0x18(%rbp)
0x0000000000441881 je     0x4418b9
0x0000000000441883 mov    -0x18(%rbp),%rax
0x0000000000441887 mov    %rax,%rsi
0x000000000044188a mov    $0x200000,%edi
0x000000000044188f callq  0x43d853 
0x0000000000441894 mov    %rax,%rdx
0x0000000000441897 test   %rdx,%rdx
0x000000000044189a je     0x4418b9
0x000000000044189c mov    $0x1fffff,%edx               //数组大小
0x00000000004418a1 jmp    0x4418ae
0x00000000004418a3 movb   $0x0,(%rax)               // 置0
0x00000000004418a6 add    $0x1,%rax                   //移动指针
0x00000000004418aa sub    $0x1,%rdx                   //数组大小减1
0x00000000004418ae cmp    $0xffffffffffffffff,%rdx    //判断是否完成全部元素置0
0x00000000004418b2 setne  %cl
0x00000000004418b5 test   %cl,%cl
0x00000000004418b7 jne    0x4418a3
0x00000000004418b9 mov    -0x18(%rbp),%rax

不同的初始化方式编译得到的汇编代码差异很大,如果在new-placement之后不写(),结果又如何?不同的优化等级会有影响么?有兴趣的可以查查标准,再自己动手试试。

缓冲区溢出和-fno-stack-protector

缓冲区溢出早在1972年就被发现,直到今天,还有很多程序员中招。用C语言不注意检查数组或者指针边界,一些C标准库里的函数使用不当,都有可能引起缓冲区溢出。

#include <stdio.h>
char *_gets(char *s)
{
    int c;
    char *dest = s;
    int gotchar=0;
    while ((c = getchar()) != '\n' && c!= EOF) {
        *dest++ = c;
        gotchar = 1;
    }

    *dest++ = '\0';
    if (c == EOF && !gotchar)
        return NULL;
    return s;
}

void echo()
{
    char buf[8];
    _gets(buf);
    puts(buf);
}

这段代码用库函数getchar()实现另一个库函数gets(),一个存在缓冲区溢出漏洞的版本_gets(),因为它没有办法确定用来保存输入的空间是否足够。如果空间足够小,像echo()里的8个字节,那么任何长度超过7个字符的输入都会导致数组越界。

_echo:
00000000000000b0    pushq   %rbp
00000000000000b1    movq    %rsp,%rbp
00000000000000b4    subq    $0x10,%rsp
00000000000000b8    leaq    __gets.eh(%rbp),%rax
00000000000000bc    movq    %rax,%rcx
00000000000000bf    movq    %rcx,%rdi
00000000000000c2    movq    %rax,0xf0(%rbp)
00000000000000c6    callq   __gets
00000000000000cb    movq    0xf0(%rbp),%rax
00000000000000cf    movq    %rax,%rdi
00000000000000d2    callq   _puts
00000000000000d7    addq    $0x10,%rsp
00000000000000db    popq    %rbp
00000000000000dc    ret

汇编代码(由i686-apple-darwin11-llvm-gcc-4.2 (GCC) 4.2.1产生)说明了栈的组织方式。

一旦越界的字符很多,就会破坏调用者中保存的状态,导致程序进入异常状态。

所谓的缓冲区溢出攻击,就是利用这种情况。输入特定的字符串给程序,内容是一些可执行代码的字节编码,让程序执行外部代码,或者覆盖返回地址,让程序跳转到攻击代码,然后,攻击者就可以为所欲为。

缓冲区溢出攻击太过普遍,以致于现代的编译器和操作系统已经实现了一些机制来最小化这种攻击。GCC会尝试加入额外的代码以检测栈是否溢出,选项-fstack-protector说明:

-fstack-protector

Emit extra code to check for buffer overflows, such as stack smashing attacks. This is done by adding a guard variable to functions with vulnerable objects. This includes functions that call alloca, and functions with buffers larger than 8 bytes. The guards are initialized when a function is entered and then checked when the function exits. If a guard check fails, an error message is printed and the program exits.

实际上,为了得到上面展示的汇编代码,要使用-fno-stack-protector选项编译源码。这次不用这个选项重新编译。

_echo:
00000000000000b0    pushq   %rbp
00000000000000b1    movq    %rsp,%rbp
00000000000000b4    subq    $0x20,%rsp
00000000000000b8    movq    ___stack_chk_guard(%rip),%rax //计算canary
00000000000000bf    movq    (%rax),%rax
00000000000000c2    movq    %rax,0xf8(%rbp)               //存到栈上,%rbp-8
00000000000000c6    leaq    0xf0(%rbp),%rax
00000000000000ca    movq    %rax,%rcx
00000000000000cd    movq    %rcx,%rdi
00000000000000d0    movq    %rax,0xe8(%rbp)
00000000000000d4    callq   __gets
00000000000000d9    movq    0xe8(%rbp),%rax
00000000000000dd    movq    %rax,%rdi
00000000000000e0    callq   _puts
00000000000000e5    movq    ___stack_chk_guard(%rip),%rax //再次计算canary
00000000000000ec    movq    (%rax),%rax
00000000000000ef    movq    0xf8(%rbp),%rcx               //取出栈上的canary
00000000000000f3    cmpq    %rcx,%rax                     //检查是否有变化
00000000000000f6    jne     0x000000fe
00000000000000f8    addq    $0x20,%rsp
00000000000000fc    popq    %rbp
00000000000000fd    ret
0000000000000fe     callq   ___stack_chk_fail              //栈破坏!

新的栈结构图

这个新的canary,就是哨兵,由程序运行时随机产生。在从函数返回之前,程序检测这个值以确认栈未被破坏,达到避免攻击的目的。

pkg_resources.DistributionNotFound

前段时间升级到Mountain Lion,之后很久没写过Python。昨天准备折腾一下才发现,我的Python竟然不工作了。python —version有输出,但pip报错:

$ pip --version
Traceback (most recent call last):
File "/usr/local/bin/pip", line 5, in <module>
from pkg_resources import load_entry_point
File "/Library/Python/2.7/site-packages/distribute-0.6.30-py2.7.egg/pkg_resources.py", line 2807, in <module>
working_set.require(__requires__)
File "/Library/Python/2.7/site-packages/distribute-0.6.30-py2.7.egg/pkg_resources.py", line 690, in require
needed = self.resolve(parse_requirements(requirements))
File "/Library/Python/2.7/site-packages/distribute-0.6.30-py2.7.egg/pkg_resources.py", line 588, in resolve
raise DistributionNotFound(req)
pkg_resources.DistributionNotFound: pip==1.0.2

google了一晚上找到了解决方案

  • 在python的setuptools页面下载对应版本的Python

  • 打开终端,运行:

    sh ./setuptools-0.6c11-py2.7.egg

  • 完成之后运行:

    easy_install -U pip

这个问题似乎是因为ML升级了Python,却没有做附带的升级site-packages工作。

标准输入/输出流的缓冲

本文内容大部分内容来自《Advanced Programming in the UNIX Environment》第5章第4节 Buffering。

题目:

下面的代码输出结果是什么?

class A
{
    private:
        int m_value;
    public:
        A(int value)
        {
            m_value = value;
        }
        void Print1()
        {
            printf("hello world");
        }
        void Print2()
        {
            printf("%d", m_value);
        }
};

int main(void)
{
    A* pA = NULL;
    pA->Print1();
    pA->Print2();

    return 0;
}

显然应该是,能正常执行Print1()而不能执行Print2(),也就是说,在程序崩溃之前至少应该能输出“hello world”。原因看这里

等一等,你可能会拷贝下来去编译执行一次,如果跟我一样在Mac下的话,你可能会发现不对劲的地方-为什么看不到Print1()的输出呢?为了确认答案,拷贝题目代码执行的结果中没有Print1()的输出,直接看到Print2()引用非法地址导致的错误:

Segmentation fault

那这是什么原因呢?

printf函数定义:

int  printf(const char * __restrict, ...)

它属于标准I/O库,标准I/O库提供了对输入输出的缓存以达到调用read和write次数最少的目的。嗯哼,“缓冲”是关键词,猜测Print1()的输出应该是被缓冲了吧。可具体是怎么缓冲的呢?

标准I/O库通过提供缓冲区,减少对于无缓冲的read和write方法的调用,增加效率。另一方面,缓冲区的存在也使得应用程序不用自己考虑最佳的读写块大小。不过,如上所见,缓冲区既是标准I/O库的便利之处,同时也是容易引起混乱的地方。标准I/O库提供三种缓冲方式:

  1. 完全缓冲,此种情形下,所有的I/O操作都在缓冲区被填满后才真正的发生;

  2. 行缓冲,只有当碰到换行符时才发生真正的I/O操作;

  3. 无缓冲,顾名思义,标准I/O库对I/O操作不做缓存。

ISO C对standard input、standard output以及standard error有以下规定:

  • 当且仅当不指向交互设备时,standard input和standard output是完全缓冲的

  • Standard error不允许完全缓冲

这个模糊不清的标准根本没说实现的时候具体应该怎么做,当standard input指向交互设备时,它应该无缓冲还是行缓冲?Standard error不允许完全缓冲,那么实现的时候采用行缓冲还是无缓冲呢?大多数的实现遵循以下原则:

  • Standard error总是实现为无缓冲流;

  • 除了standard error之外的其他流,倘若指向终端设备,则采取行缓冲。否则全部采用完全缓冲;

对默认的缓冲方式不满意的话,可以通过

void setbuf(FILE * __restrict, char * __restrict);
int  setvbuf(FILE * __restrict, char * __restrict, int, size_t);

两个函数更改缓冲区大小以及类型。

好了,既然知道内幕,现在修改main函数,把缓冲区设置成空试试

int main(void)
{
    setbuf(stdout, NULL);

    A* pA = NULL;
    pA->Print1();
    pA->Print2();

    return 0;
}

再执行,这次Print1()的输出能够正常显示。

Win2003Server的SYN Attack Protect陷阱

发现这个陷阱源于一个自己写的HTTP服务端。因为项目里要用到支持GET请求就能满足需要的HTTP服务端,图方便就用内部封的异步Socket类实现了这么个简单的服务端。没想到,就是这个简单的HTTP服务,还是出现了几次莫名其妙的问题。第一次出现在刚完成代码功能测试时,对HTTP的一知半解导致查了几天之后才发现原来是没处理HTTP头里的Keep-Alive。

最近又碰见另一个百思不得其解铃还需系铃人人得而诛之的问题,测试服务端性能时,用Apache的AB压服务器,设置的并发数稍大就只能完成一部分请求,AB的提示是“远程主机主动关闭连接”。具体来说就是,当AB参数为请求数1000,并发数200的时候,服务端能够正常完成测试;增加并发数到300,则服务端只能完成1000个请求中的300多个,客户端抓包观察到大量请求在TCP三次握手完成后立刻被RST。

用自己封装的异步Socket类写个测试客户端,循环连接服务端,产生大量连接,同样连接数也只能到300多个,其余的大量连接得到类型为WSAENETRESET的socket错误。

用来实现HTTP服务端的异步Socket类没有什么特别操作。逻辑是这样的:

  • 服务端首先产生一个Socket句柄(废话…),转为异步模式后监听端口,等待客户端连接。

  • 一旦有客户端连接,服务端调用accept得到新的Socket,加入到一个Socket集合进行统一处理。

  • 每次统一处理时,查询所有Socket的事件,对不同的事件进行不同的处理。

  • 服务端对所有的Socket句柄不主动执行关闭操作,除非调用recv时得到的长度为0,即认为是客户端主动关闭,随后服务端进入被动关闭。

应用开发出现问题的第一反应是检查自己的程序。首先怀疑是逻辑不严密,在某特殊情况下Reset客户端连接。在服务端每个可能关闭socket的地方增加日志,再用AB压一次观察输出。但服务端日志没有记录到任何异常的关闭操作,问题似乎不是服务端关闭连接导致的。

既然没有异常关闭socket的情况,那应该是其他地方出问题。考虑listen函数的backlog参数,会不会是这里的原因呢?

listen函数原型:

int listen( __in  SOCKET s,  __in  int backlog );

来看backlog参数在MSDN的说明

The maximum length of the queue of pending connections

再往下看,MSDN中对listen函数有一段这样的描述

If a connection request arrives and the queue is full, the client will receive an error with an indication of WSAECONNREFUSED.

就是说,如果客户端连接数过大,超过调用listen函数设置的backlog队列大小,新的连接会收到WSAECONNREFUSED的socket错误。但观察到的现象是客户端socket错误为WSAENETRESET,不符合文档的描述。

过了listen函数再往下看,代码进入日志能够记录的范围。上面说过,服务端没有异常关闭的操作。到这里仍然没找到原因。目前为止,最有可能的情况就是瞬间的连接数过多导致backlog满。就算是这个原因,客户端收到的也应该是WSAECONNREFUSED错误而不是观察到的WSAENETRESET错误,绕进死胡同了。就这个问题在stackoverflow发的询问帖,回复里也有人说可能是backlog满导致客户端无法连接,但却无法解释为什么收到的socket错误不是MSDN描述的WSAECONNREFUSED。

问题就这样被搁置下来,直到三天后我忙完手头的事情,用部分关键词google,得到了某个错误现象匹配度很高的搜索结果。这里是原帖,截取一段简单描述

We started getting problems when customers implemented SP1 on their Windows Server 2003 boxes. We’d see clients who thought they had successfully connected, but who would get a RESET back from the server immediately after the 3-way handshake (SYN, SYN-ACK, ACK). This seems completely broken to me.

啊哈,跟我们的问题看起来一样!他认为是Windows 2003 Server默认开启的SYN攻击保护.aspx)开关在作怪,猜想可能是SYN攻击保护机制的实现影响到Winsock的accept函数行为。正常的行为是,当backlog队列满时,三次握手中第一个SYN包就会导致服务端响应RST+ACK拒绝客户端的连接。但SYN保护机制起作用后,这个行为变成直接接受新的连接再去检查backlog队列,当发现backlog队列满时丢弃此连接。服务端此时要干掉连接就只能在已完成三次握手的连接上发送一个RST,于是客户端出现莫名其妙的WSAENETRESET错误。

这是他的问题以及猜测,能不能解决我们的问题,还要实验一下。打开注册表才发现,我们的服务器上没有他描述的HKLM\System\CurrentControlSet\Services\Tcpip\Parameters\SynAttackProtect这一项,没关系,没有我们可以创造一个,设置键值为0,重启机器(万恶的重启!)。此时再用AB去压服务端,在客户端果然抓到的RST+ACK包。用自己写的客户端测试,socket错误也由之前百思不得其解的WSAENETRESET变成WSAECONNREFUSED。

问题原因到这里基本确认,由于我们的服务端实现在接受客户端连接时速度不够快,用AB压服务端时的大量连接填满backlog队列,这些连接同时也触发服务器默认开启的SYN攻击保护机制,操作系统认为受到SYN攻击,后续的其他连接于是被重置。关于这个问题,这里也有提及。这种跟文档描述不一致的行为害苦了广大程序员,在别人2005年就受过苦之后,2010年我这个倒霉蛋又再次遇上。不过奇怪的是,网上搜索不到多少关于这个问题的中文资料,英文倒是又不少人提过。

之前在跟项目组同事的讨论原因时,也考虑过系统或者路由在应用程序之下断开连接的可能性,但是由于对操作系统环境不熟悉,不知道存在这么一个SynAttackProtect机制,影响到问题原因的确认,算是一个教训吧。虽然存在文档描述与实际行为不一致的原因,但对程序运行平台的熟悉程度还是直接影响了定位问题的速度。

顺便说一句,测试中发现,Windows 2003 Server SP2里的backlog最大值似乎是200,不过没有查过官方文档确认,纯属推测。

Nagle算法和魔兽世界的延迟

暴雪大神的《魔兽世界》从2005年4月26号公测到现在,风靡全球已有好几个春秋。还记得公测时小白一个的我打哀嚎被副本里的一个要一点点技术跳过去的平台折腾疯,无数次的跳到空中,眼看着那个台子在眼前越升越高,然后环顾四周,全是怪,挂,跑尸,复活,找路,再跳,挂…以至于我满级之后都不敢去哀嚎 : (

当然,玩了几年的wow,要说印象最深刻的嘛,当然要数游戏代理公司的小霸王服务器,以及小霸王那无敌的延迟(你肯定也这么想,哈)。曾经有一次,参加工会的BWL开荒,2号小红龙,只要开荒过这个怪的玩家,我相信你绝对不会忘记它的变态。那次开荒,变态的BOSS配合几百的延迟让全团一次次的扑地,直到身上的装备跟延迟变成一个颜色,还是没过,丧气解散,杯具!

不论是以前的九城时代,还是现在的网易时代,lag一直都是wow最大的问题,当然,大家普遍认为主要的原因在于服务器质量不靠谱,故有“小霸王”之名。但同时也要了解,暴雪一直在调整程序,以期粉丝们有更好的游戏体验。在TBC 2.3.2版本的patch说明中,就有如下与游戏体验相关的内容:

综合 * /timetest命令可显示游戏性能信息。输入/timetest 0可关闭该命令。开启此命令后,系统将在玩家下一次在飞行管理员处搭乘飞行坐骑时进行性能测试,并在着陆后显示结果数据。 * 微缩地图将不再显示带蓝色问号的任务NPC位置。 * 受到爆击后触发的效果:许多技能和天赋在2.3.0中作了改变,可以在玩家处于坐下状态时正常发挥因受到爆击而触发的效果。 * 当玩家完成了NPC给予的任务后,鼠标指向该NPC时将显示为问号,而不再是感叹号。 * 取消了公会银行的管理权限对公会会长的等级要求。公会会长将始终拥有对公会银行的完整管理权限,且此完整权限不可改变。 * 在公会银行的管理中新增了“提款:仅限于维修”功能。当公会将某层级的公会成员权限设定为此时,此阶层的成员将不能从公会银行直接提款,而只能用每天的提款额度进行直接修理。 * 玩家在受到攻击时将自动站起,即使该次攻击未能命中。 * 船只和飞艇上的乘务NPC又可以正常工作了。 * 通过禁用Nagle算法降低了网络延迟。

首先赞一下暴雪的产品态度,如果我们公司也一直致力于提高客户的使用体验,就算不能到暴雪这种程度,最起码也应该会有很好的口碑和用户忠诚度。好了,马屁拍完来研究一下这句“通过禁用Nagle算法降低了网络延迟 ”。 开始blabla之前,我先说说网络延迟的概念。不知道在其他领域是是不是有别的含义,但在我们游戏界(什么时候我算游戏界的了?-_–|||),特别是在魔兽世界,延迟指的就是痛苦,就是被别人打而无还手之力,就是剩下一滴血的时候用不了血瓶,用不了消失,用不了冰箱,It means hell!对不起,我又变态,哦,不,失态了。 正经的说,延迟在游戏中最典型最恶心的表现是,当你打算使用某个技能,游戏角色要在你按了键盘或点了鼠标后的一段时间内才能发出技能。如果你按了一系列技能的快捷键后游戏人物一点反应没有,而是要等到你倒了杯水回来的时候才突然像快进一样做出N多动作,那么恭喜你,网络延迟非常高,你的游戏人物应该大多数情况下会躺在地板上数星星。

那么这个Nagle算法是什么万恶的东东,会增加网络延迟?而且暴雪大神竟然一直到TBC才想起来关掉这玩意儿,不给力阿!话说,在很久很久以前…好吧好吧,别嘘。所谓Nagle算法,它是个根据一定的规则减少网络发送包数量的方法,进而改善了TCP/IP网络的效率。关于这个算法,《TCP/IP详解》里是这样说的

该算法要求一个TCP连接上最多只能有一个未被确认的未完成的小分组,在该分组的确认到达之前不能发送其他的小分组。相反,TCP收集这些少量的分组,并在确认到来时以一个分组的方式发出去。

在魔兽世界游戏里,我们的操作中有相当一部分的数据量是极小的,若没有Nagle算法,1个字节的数据可能也会被作为一个分组发送出去,考虑到TCP头有20字节,IP头也有20个字节,为了发送1个字节的数据产生的分组就达到41字节。这是一种极大的浪费,更为重要的是,这同时也增加了分组的数量,给客户端网络造成压力,我想这应该正是暴雪当初没关闭Nagle算法的原因。

2.3.2里的这条patch有什么神奇的作用到这已经水落石出,如果没有关闭Nagle算法,客户端的数据包可能由于数据量太小而被TCP层缓存下来,等到上一个分组的确认收到后才把所缓存的所有数据发送到服务端,从而导致客户端感觉延迟有所增加。关闭Nagle算法后,每个数据包在TCP层便不会被缓存,直接发送到服务端,改善客户端游戏体验的目的也就达到了。

其实在其他领域对Nagle算法“意见”也是很大的,比如实时性要求很高的应用,远程桌面之类的,像鼠标移动之类的小消息必须无延迟发送出去,否则客户用起来会抓狂,后果很严重!Host Requirements RFC针对TCP的Nagle算法实现这样说的

A TCP SHOULD implement the Nagle Algorithm [TCP:9] to coalesce short segments. However, there MUST be a way for an application to disable the Nagle algorithm on an individual connection.

简言之,TCP必须实现Nagle算法,但同时也要提供方法能够在某个连接上关闭此算法。

Socket用户可以通过TCP_NODELAY选项来关闭Nagle算法,这个选项在netinet/tcp.h文件中定义。

over~

C++ Exception Handling

最近刚刚读完《深度探索C++对象模型》,说来惭愧,整本书都快看完才想起来要做笔记。目前笔记只有后面三章的一些重点内容,本文是异常处理(Exception Handling)这部分内容的笔记整理。

写程序的时候,对于可能出现异常的地方,通常来说我们是这样写的:

try{
...
throw ...
} catch(...) {
//exception handling
}

当异常发生时,代码跳转到catch块,完成异常处理后退出。为了支持这个处理流程,编译器要能够在发生异常时,找到对应的catch子句。而查找catch子句时,编译器要知道函数的当前作用范围,同时还要了解抛出异常的类型,以便进行catch子句匹配(这引出了执行期类型识别的需求,即RTTI)。

详细来看看,上面这段代码大致可以分为三个部分:

  • throw子句,它抛出一个exception,可以是内置类型,也可以是用户自定义类型

  • catch子句,每个catch子句都是一个exception handler,表示其之后的代码段用来处理某种类型的exception

  • try段,内含一些程序代码,这些代码可能引发catch子句生效

当一个exception被抛出时,程序控制权从函数中释放,转而寻找一个匹配的catch子句。若不存在匹配的catch,默认的terminate()方法将被调用。而在控制权被放弃后,堆栈中的函数被poped up,函数内局部对象的析构函数在poped up之前会被调用。

当exception发生,编译系统完成下面几件必须要做的事:

1、检查发生throw exception操作的函数

2、决定throw是否是发生在一个try段内

3、如果throw发生在try段内,编译系统开始比较发生的exception的类型和catch子句中exception的类型是否吻合

4、一旦exception类型吻合,该catch子句就得到流程控制权

5、若throw并不是发生在try段内,或者没有找到吻合的catch子句,系统要做的就是,清理当前函数范围内所有局部对象,从堆栈中pop up当前函数,进入堆栈内下一个函数,继续步骤2-5

那么当一个exception被抛出后,它经历了些什么?它并没有无家可归,睡在天桥底下。抛出的exception object放在exception数据堆栈中,从throw处传递到catch子句的是这个exception object的地址。来看个例子:

catch (BaseException  newobj) {
    //do something
    throw ;
}

假设这个catch子句将收到一个DerivedException类型的exception object,DerivedException继承自BaseException。那么,由于exception类型吻合,按照上面说的步骤4,这个catch子句得到控制权。

catch子句中的newobj在收到exception时,将以抛出的exception object作为初值,像函数以传值方式传递参数一样。由于newobj是一个对象而不是指针或引用,BaseException的copy constructor将会被调用(如果存在的话),以拷贝原始exception object中属于BaseException的部分到当前的newobj中。

完成这些之后,catch子句内的代码被执行,再次抛出异常。这次抛出的是newobj还是原始的exception object?抛出的仍然是原始的exception object。newobj只是局部对象,在catch子句结束后被摧毁,任何对newobj的修改都被丢弃而不会影响到原始的exception object。这个原始的exception object将直到有一个catch子句执行完,并且不再抛出exception后,才会被摧毁。

本文内容来自《深度探索C++对象模型》第7章中的异常处理介绍。

关于C++的EH,在codeproject上有篇文章简单介绍编译系统与win32系统之间的协作关系。

that’s all, over!

Restrict关键字

看代码看到个restrict,头一次知道还有这么个关键字,在维基查到基本用法和解释。本着好记性不如烂笔头的原则,翻译这篇维基贴在这里。

在C语言的一个标准(C99)里,有一个用于修饰指针声明的关键字-restrict,它是程序员给编译器的一个意向声明,表明只有此指针或者基于此指针的某个值(比如 pointer+1)可以访问其指向的对象。这个关键字限制了指针别名(译注:即指向同一对象的不同指针),目的在于进行编译器优化。如果这个程序员没有遵守这个意向声明,并且这个对象由一个独立指针访问到的话,会造成未定义的行为。( 译注:我也没搞懂这一大段话什么意思 ^_^ 不过看下面的例子应该差不多能理解这个关键字的用法)

如果知道只有一个指针指向某个内存块的话,编译器就能进行优化,以生成更高效的代码。下面这个例子能清楚解释这一点。

void updatePtrs(size_t *ptrA, size_t *ptrB, size_t *val)
{
    *ptrA += *val;
    *ptrB += *val;
}

这段代码里面,指针ptrAptrBval可能指向同一块内存,所以编译器不能对代码进行优化。

load R1 ← *val  ; 加载val指针的
load R2 ← *ptrA ; 加载ptrA指针的值&lt;/pre&gt;
add  R2 += R1   ; 相加
set  R2 → *ptrA ; 更新ptrA指针的值
; 对ptrB指针的操作类似,注意,这里val指针被加载两次,因为ptrA有可能和val指向同一块内存
load R1 ← *val
load R2 ← *ptrB
add  R2 += R1
set  R2 → *ptrB

如果使用restrict关键字,函数声明为:

void updatePtrs(size_t *restrict ptrA, size_t *restrict ptrB, size_t *restrict val);

编译器就能知道ptrA, ptrB, val三个指针指向不同的内存块,更新其中一个不会影响到其他的,从而对代码进行优化。当然,这里要由程序员保证这三个指针不指向同一块内存。

load R1 ← *val
load R2 ← *ptrA
add  R2 += R1
set  R2 → *ptrA
;编译器知道指针val的值没有改变,所以没有重新加载它,优化了汇编代码
load R2 ← *ptrB
add  R2 += R1
set  R2 → *ptrB

还有一个例子是memcpy函数,memcpy(void*, void*, nbytes)的前两个指针参数被声明为restrict,告诉编译器两个数据块没有重叠,便于进行优化,使得memcpy的速度更快。如果程序员用相同的指针作为这两个参数的值,那么memcpy函数会产生未定义的行为。

【编程之美】数组循环移位

大概两个星期前看到个题目(还是从TopLanguage过去的):

设计一个算法,把一个含有N个元素的数组循环右移K位,要求时间复杂度为O(N),且只允许使用两个附加变量。

苦思冥想两个星期,今天写了段代码,基本实现“时间复杂度为O(N)”的要求,不过用的变量那就多了… 下面是我的杰作:

void mvArray(int *a, int k, int n)
{
    if (k % n == 0)     return ;
    int original = 0, instead = 0;
    int x = n;
    instead = a[0];
    int target = 0;
    int j = 0;
    while (x--) {
        target = target + k%n&lt; n ? j+k%n : (j+k%n)%n;
        instead = a[target];
        a[target] = a[j];
    }
}

假设有a[]={0,1,2,3,4,5,6,7,8,9}这样10个元素的数组,要求向右顺移7位。算法从数组的第一个元素开始,a[0]将移动到a[7],此时a[7]被拿出来,算出a[7]要移动到的目标位,本例中为a[4],那么a[4]的值被修改为原来a[7]的值,原来的a[4]被拿出来,继续如此循环下去。当目标位的原值与目标位即将被赋予的新值相等时,表示这一个环路已经完成全部的替换。将此次环路的开始位加1,继续下一个环路,直到达到数组元素的个数,跳出循环。此时该数组向右顺移7位的操作已经全部完成。 怎么样,是不是很复杂?连我自己都觉得复杂的不行。可就是写的这么复杂,也只完成题目一半的要求,使用的附加变量远远超过两个。 如果你有兴趣,可以自己试试写个函数出来。懒的写的就直接看下去吧,这里有一个非常优秀的解答。

void Reverse(int* arr, int b, int e)
{
    for(; b < e; b++, e--)
    {
        int temp = arr[e];
        arr[e] = arr[b];
        arr[b] = temp;
     }
}
void RightShift(int* arr, int N, int k)
{
     k %= N;
     Reverse(arr, 0, N - k - 1);
     Reverse(arr, N - k, N - 1);
     Reverse(arr, 0, N - 1);
}

这两个函数即可完成上面贴的我写的那么长一串代码的所有功能,在线性的时间内实现题中要求的右移操作,只用了1个附加变量。具体的逻辑我这里就不赘述了,直接看原文