动态数组的内存分配

很高兴能和 @欧阳大哥2013 继续探讨动态数组的内存分配
这种探讨充满了积极意义
否则我也许会湮没在从前的理解中坐井观天

上一文章《多态Delete动态数组》@欧阳大哥2013提出了一些独到的见解
偏听则暗 格物致知
于是我进行了下文记录的妙趣横生的探索

我的目标是找出动态数组内存分配的基本方式

首先@欧阳大哥2013提出了一个论点：
存储C++基本内置类型的动态数组不具备存储元素个数的头部
只有抽象数据类型的类对象的动态数组才有。

为了验证这个问题
我从衣柜里挖出了积灰的Macbook😂
实验平台是
X86_64+darwin17.5.0+Xcode9.3+LLVM9.1.0
这个是apple的LLVM
而opensource的LLVM目前刚刚发布6.0.0的测试版
apple的LLVM是对open source版本的深度定制
话说这一套还是我去年在nowcoder上发布上一篇文字时的装备
时光荏苒

下面写一个illustrated code

unsigned long *foo() {
    return new unsigned long[4];
}

clang是目前LLVM的前端（front end）
以前曾经用过gcc作为前端
但是后来由于效率和内存占用的角度考虑
还是让Christ Lattner写了clang华丽变身

通过clang指令可以完成编译任意过程
打开terminal 输入指令
clang -S -O2 /path/to/your/target.cpp

这样就能完成源码的编译阶段
在当前路径下生成源文件的.s汇编文件
默认是AT&T语法
可以用-masm=Intel选项输出Intel语法的汇编码
masm是Microsoft AsSeMbler的缩写(acronym)
当然 如果嫌麻烦 大家也可以在Xcode里的

Product -> Perform Action -> Assemble "YourFileName.cpp"

进行粗汇编 这样会保留非常多的“.”开头的伪指令和文本段的内容
相当于上面的指令去掉了"-O2"选项
这个选项用于删节许多冗杂指令以及优化代码结构
以下正是汇编文件的主要内容

//foo函数名最后就是一个标签而已
__Z3foov: 
        //保存一下栈底指针
    pushq   %rbp
        //当前栈顶变成新的栈底
    movq    %rsp, %rbp
        //4个unsigned long，每个8 bytes
        //存入edi寄存器，作为函数调用的第一个参数
    movl    $32, %edi
        //调用__Znam函数
    callq   __Znam
        //恢复堆栈
    popq    %rbp
        //返回值存储于rax寄存器
    retq

所分配32字节全用于存储数组元素
这个汇编结果是符合欧阳大哥和我的预期的
也就是完成了论点一半的证明：
基本内置类型的动态数组没有表明元素个数的头部
当然 大家可以使用上一篇文章中的验证方法
打印一下foo()-1的内存值看一下脏数据

这儿 出现了一个有趣的符号 —— __Znam
事实上这个名字并不陌生
在我的另一篇文章《数组名 & 指针》里
同样是探究new表达式的半亩方塘里就出现了
不过我当时并没有深究其来源
毕竟这种双下划线的函数基本都是
编译器不想让你知道的内部符号😁

既然我在用LLVM编译器
那就到LLVM的Project Subversion上checkout C++ standard library
svn co http://llvm.org/svn/llvm-project/libcxx/trunk/

每种编译器都有其自己的C++ standard library的实现
Linux下有很多朋友也会下载GCC的标准库

那么在checkout的libcxx里grep一下
$ grep "Znam" . -r -n

发现了一个引人注意的文档：

./lib/libc++abi-new-delete.exp:4:__Znam

这个exportation文档记录了一串双下划线开头的函数名
new/delete就是指的new和delete表达式
而exported类型文档的一个重要作用就是给动态链接库
Linux上应该称为Public shared object
提供外部链接的
从相同目录中的CMake文件如下内容可以看出来

if (NOT LIBCXX_ENABLE_NEW_DELETE_DEFINITIONS)
        add_link_flags("/usr/lib/libc++abi.dylib -Wl,-reexported_symbols_list,${CMAKE_CURRENT_SOURCE_DIR}/libc++abi-new-delete.exp")

这条make脚本给系统库里的原有C++ ABI的动态链接库添加了exp文件中的符号
那么线索指向了一个有趣的名词 —— ABI
说到这个词不得不提一下Chris Lattner
LLVM & Swift 之父
去年他离开苹果时还聊到
Swift的ABI还不稳定
这是Swift未来的最大变数
因为ABI是底层的桥梁
所以ABI不稳定会导致每次Swift的更新都意味着
Windows式的推倒重装
而不能像苹果安卓那样迭代升级

回到正题
C++ standard Library的ABI也许就藏着__Znam的秘密
于是再上SVN下载libcxxabi
svn co http://llvm.org/svn/llvm-project/libcxxabi/trunk/

grep一下得到以下有意思的信息：

./test/test_demangle.pass.cpp:432: {"_Znam", "operator new[](unsigned long)"},

mangle就是现代二进制应用程序常用的混淆策略
把原来程序中易于理解同样容易被骇客利用的明文符号名通过一定策略改换包装
作为一个单元测试文件，demangle意味着单元测试的时候要反混淆出原符号名
所以该文件有一个巨大的二维常字符数组作为测试用例。
const char* cases[][2]
类似于dictionary的数据结构，混淆名作key，实名作value
由此很容易推出
"_Znam"正是"operator new[](unsigned long)"的混淆名
同样的，在cases中还能找到另外几组有意思的couple

{"_Znwm", "operator new(unsigned long)"},
{"_ZdaPv", "operator delete[](void*)"},
{"_ZdlPv", "operator delete(void*)"},

相信大家都能猜出来他们的作用了
我大胆猜一下mangle的规则
首先这些mangled name都是Z开头的
其次第二个n代表了new operator
第二个字母为d则代表delete operator
第三个字母a代表了array，l代表了void*，w代表unsigned long

顺藤摸瓜，通过“operator new[](unsigned long)”来查找线索

$ grep "operator new[](" . -r -n

立刻找到了./src/stdlib_new_delete.cpp
这个巨大的目标

让我们看看这个文件里的有趣内容

// Implement all new and delete operators as weak definitions
// in this shared library, so that they can be overridden by programs
// that define non-weak copies of the functions.

_LIBCXXABI_WEAK
void *
operator new(std::size_t size) _THROW_BAD_ALLOC
{
    if (size == 0)
        size = 1;
    void* p;
    while ((p = ::malloc(size)) == 0)
    {
        // If malloc fails and there is a new_handler,
        // call it to try free up memory.
        std::new_handler nh = std::get_new_handler();
        if (nh)
            nh();
        else
#ifndef _LIBCXXABI_NO_EXCEPTIONS
            throw std::bad_alloc();
#else
            break;
#endif
    }
    return p;
}

_LIBCXXABI_WEAK
void*
operator new[](size_t size) _THROW_BAD_ALLOC
{
    return ::operator new(size);
}

整个流程很清晰
new[]事实上就是调用了
operator new(size)
而这个函数混淆之后就是上面所引用的符号
__Znwm

把测试程序里的
return unsigned long[4]
改为
return unsigned long
汇编后原来的"__Znam"就会变成"__Znwm"

有几个有意思的点：

1. 如果传入的数组长度为0，为了避免malloc(0)带来的异常，默认改为1字节长度
2. 程序员可以给异常定制new_handler
3. new的核心逻辑就是malloc
4. 如果没有预留new_handler则抛出bad_alloc异常对象

个人比较好奇的是
_LIBCXXABI_WEAK
这个宏
搜了一下发现定义如下

#if defined(_WIN32)
#define _LIBCXXABI_WEAK
#else
#define _LIBCXXABI_WEAK __attribute__((__weak__))
#endif

原来是__attribute__((__weak__))
这就和OC/Swift中的弱引用类似
避免程序因为引用一个不存在的外部符号（就像extern xxx）而崩溃
同时，当外部有相同的强引用符号将使用外部符号
我在另一篇文章里归纳了一些__atttribute__编译器指令

大家不妨注意一下代码里的LLVM作者的注释说明
简单翻译如下

在这个动态链接库里把new和delete实现为弱运算符，这样就能被程序中其他非弱引用副本覆盖重写。

显然作者的意图就是方便大家在类中或者全局作用域里定义自己的内存分配逻辑，并且重写这个默认逻辑。当然，这本身就是C++标准的new/delete运算符所规定的

另一个有趣的地方是get_new_handler()函数：

#if __APPLE__
    #include <cxxabi.h>
    // On Darwin, there are two STL shared libraries and a lower level ABI
    // shared libray.  The global holding the current new handler is
    // in the ABI library and named __cxa_new_handler.
    #define __new_handler __cxxabiapple::__cxa_new_handler
#else  // __APPLE__
    static std::new_handler __new_handler;
#endif

……
……

new_handler
get_new_handler() _NOEXCEPT
{
    return __sync_fetch_and_add(&__new_handler, (new_handler)0);
}

源码中用了一套无锁API实现了取全局new异常回调函数的原子性
这套API以__sync开头
引用代码中调用的__sync_fetch_and_add是执行类似原子性的i++操作
即自增后返回增加前的值
而这里的用法很妙，用一个0作为加数，也就是说不对函数指针做任何改动
从而取到了全局共享的__new_handler函数指针

在文件头可以看到__new_handler事实上是一个宏
真正使用的是标准库ABI的接口
原因也很有趣
因为在Darwin内核中，C++标准库被拆成了三部分：
两个标准库+一个底层ABI库
为了使得彼此之间能共用terminate/unexpected/new handler
所以就把这些全局函数指针都放在了ABI库里
代码如下

// Apple additions to support multiple STL stacks that share common 
// terminate, unexpected, and new handlers
extern void (*__cxa_terminate_handler)();
extern void (*__cxa_unexpected_handler)();
extern void (*__cxa_new_handler)();

……
……

/* The current installed new handler.  */
void (*__cxxabiapple::__cxa_new_handler)() = NULL;

而上面提及的无锁API实际上是gcc的代码
查看了gcc源码里的文档介绍：

Prior to GCC 4.7 the older __sync intrinsics were used. An example of an undefined symbol from the use of __sync_fetch_and_add on an unsupported host is a missing reference to __sync_fetch_and_add_4.
直到GCC4.7之前__sync系列内联函数一直都在使用。一些不支持这套接口的主机系统中也许会提示缺乏__sync_fetch_and_add符号，事实上只是未与__sync_fetch_and_add_4进行引用关联。

Current releases use the newer __atomic intrinsics, which are implemented by library calls if the hardware doesn't support them. Undefined references to functions like __atomic_is_lock_free should be resolved by linking to libatomic, which is usually installed alongside libstdc++.
当前的发布版本使用了更新的__atomic系列内联函数。如果硬件上无法支持这套接口，那么就会有动态库来实现它们。如果遇到“未定义的__atomic_is_lock_free函数引用”之类的问题，应当通过链接libatomic库来解析这些符号。这个库往往已经包含在libstdc++库里了。

由此可见
这套接口并非被所有系统支持
但可以在编译选项中自主选择是否编入系统库
并且事实上这套接口已经过时了
现在改用了__atomic接口
不过还是看看他的相关实现：

uint64
__sync_add_and_fetch_8 (uint64* ptr, uint64 add)
{
    int i;
    uint64 ret;
    
    i = pthread_mutex_lock (&sync_lock);
    __go_assert (i == 0);
    
    *ptr += add;
    ret = *ptr;
    
    i = pthread_mutex_unlock (&sync_lock);
    __go_assert (i == 0);
    
    return ret;
}
    

这个函数是64位的，而引文中所说的
__sync_add_and_fetch_4 是32位的
只是数据宽度有所不同
逻辑是一致的
实际上就是加了POSIX标准的互斥锁
这套接口让我想起了当年OC里常见的<libkern/OSAtomic.h>
那是OC里最常用的无锁化编程接口
uint64 __sync_add_and_fetch_8 (uint64* ptr, uint64 add)
其实基本类似于
int32_t OSAtomicAdd32Barrier( int32_t __theAmount, volatile int32_t *__theValue );

如今因为陈旧和不安全所以已经被废弃了
尤其是OSSpinLock 在具有优先级的线程队列中会造成优先级反转
OSSpinLock事实上就是在用户态执行for循环空转
而新的os_unfair_lock会退到内核态休眠等待
OSSpinLock曾经是最快的锁
毕竟不需要切换上下文空间只是原地打转
但是却会造成无序和不公平
譬如一个消费者刚刚unlock
别的消费者尚未唤醒得到资源使用权
这个资源又被刚才的消费者lock了
所以如今OSSpinLock已经被<os/lock.h>替代

<libkern/OSAtomic.h>代码里的注释也是推荐使用新的<stdatomic.h>/<atomic>库

These are deprecated legacy interfaces for atomic operations.
The C11 interfaces in <stdatomic.h> resp. C++11 interfaces in <atomic> should be used instead.

回到正题
验证完了__Znam的真身
下面看看如果在动态数组中存储抽象数据类型会如何
写一个illustrated code：

struct T {
    string s;
};

T *foo() {
    return new T[2];
}

汇编代码如下

__Z3foov:   
    pushq   %rbp
    movq    %rsp, %rbp
    movl    $56, %edi
    callq   __Znam
# rax存储了上面new运算符返回的
# 动态内存的首地址
# 把数组长度2存入首地址指向的8字节的堆中
    movq    $2, (%rax)
# 清空剩余堆内存
    movq    $0, 48(%rax)
    movq    $0, 40(%rax)
    movq    $0, 32(%rax)
    movq    $0, 24(%rax)
    movq    $0, 16(%rax)
    movq    $0, 8(%rax)
# 动态数组首地址跳过存储元素个数的堆内存
# 实际上返回的正是我们平时得到的 首元素的地址
    leaq    8(%rax), %rax
    popq    %rbp
    retq

很显然可以看出来
动态数组的头部终于出现了
我做了对照组实验

struct T {
    size_t i;
};

如果把T改写成成员只包含基本内置类型的类
也不会产生数组头部的
这种类叫做聚合类（aggregate class）
类似于一个C的结构体

自然要研究其中奥妙所在
Lippman在《inside the C++ object model》中曾聊过这个问题

Array of objects

关键内容如下：

If Point defines neither a constructor nor a destructor, then we need do no more than what is done for an array of built-in types, that is, allocate memory sufficient to store ten contiguous elements of type Point.
Point类没有自定义的构造/析构函数，所以对于这样的内置类型，我们只需要分配足够的内存空间存储10个连续的Point对象即可。

Point, however, does define a default constructor, so it must be applied to each of the elements in turn. In general, this is accomplished through one or more runtime library functions. In cfront, we used one instance of a function we named vec_new() to support creation and initialization of arrays of class objects.
但是，如果Point类定义了默认构造函数，那么编译器将对数组中的元素轮流执行这个构造函数。一般情况，这是由一个或多个运行时库函数完成的。在我写的cfront编译器中，我们使用了一个名为vector_new()的函数来完成数组中的类对象的创建和初始化。

专述new数组的内容:

new array

关键内容如下：

vec_new() is not actually invoked, since its primary function is to apply the default constructor to each element in an array of class objects. Rather, the operator new instance is invoked:
vector_new()函数不会被调用，因为它的主要功能是调用数组中每一个对象的默认构造函数。相反地，new运算符会被调用。

simple_aggr does not define either a constructor or destructor, so the allocation and deletion of the array addressed by p_aggr involves only the obtaining and release of the actual storage. This is sufficiently managed by the simpler and more efficient operators new and delete.
simple_aggr并未定义构造/析构函数，所以p_aggr所指向的数组的分配和销毁事实上只是执行了对应内存的获取和释放而已。这只需要使用更简洁高效的new/delete运算符即可。

以上两处引用都说明了一个道理
程序员需要自定义默认构造函数和析构函数才能执行vec_new()函数
于是我试着做如下实验

struct T {
    size_t s;
    T() {}
    ~T() {}
};

T *foo() {
    T *t = new T[2];
    return t;
}

以下为对应的汇编码：

__Z3foov:
    pushq   %rbp
    movq    %rsp, %rbp
# 24bytes = 8bytes elem_count + 2*8bytes elem_size
    movl    $24, %edi
    callq   __Znam
# 这里把元素个数2存入rax寄存器中存储的地址
# 这个地址就是__Znam分配的内存首地址
    movq    $2, (%rax)
# 内存首地址 + 8bytes = 返回的首元素地址
    addq    $8, %rax
    popq    %rbp
    retq

可以看到并没有vec_new()函数被调用
但是塞翁失马焉知非福
这次就生成了存储元素数量的动态数组头部
做了对照组实验
发现只需要自定义析构函数即可
并不需要自定义构造函数
也就是说去掉
T() {}
也是可以得到数组头的

这让我对Lippman所说的vec_new()函数更加着迷
于是我决定使用Xcode的指令调试俯瞰整个new流程
T *t = new T[2];
在这句代码上打断点，^+F7进入汇编指令单步调试
于是得到如下流程

libc++abi.dylib`operator new[]:
->  0x7fff718eb69b <+0>: jmp    0x7fff71909dbe            ; symbol stub for: operator new(unsigned long)

libc++abi.dylib`operator new:
->  0x7fff71909dbe <+0>: jmpq   *0x39f552e4(%rip)         ; (void *)0x00007fff718eb600: operator new(unsigned long)

libc++abi.dylib`operator new:
->  0x7fff718eb600 <+0>:  pushq  %rbp
0x7fff718eb601 <+1>:  movq   %rsp, %rbp
0x7fff718eb604 <+4>:  pushq  %rbx
0x7fff718eb605 <+5>:  pushq  %rax
; rdi存储着唯一的实参 —— 元素个数
; 对rdi寄存器进行自与运算，根据结果修改标识位
0x7fff718eb606 <+6>:  testq  %rdi, %rdi
0x7fff718eb609 <+9>:  movl   $0x1, %ebx
; rdi不为0才执行mov操作
0x7fff718eb60e <+14>: cmovneq %rdi, %rbx
; 传入的元素个数为0，那么此时rbx为1
; 传入的元素个数不为0，则rbx已经设置为传入的元素个数
0x7fff718eb612 <+18>: jmp    0x7fff718eb620            ; <+32>
; typedef void (*new_handler)();
; 调用get_new_handler()函数得到用户预设的异常处理函数
0x7fff718eb614 <+20>: callq  0x7fff71907863            ; std::get_new_handler()
; 此时rax寄存器存储get_new_handler()函数的返回值
; 即用户预设的异常处理函数，如果没有则是NULL
; 对rax寄存器进行自与运算，根据结果修改标识位
0x7fff718eb619 <+25>: testq  %rax, %rax
; 如果用户没有预设异常处理函数则跳转到bad_alloc逻辑
0x7fff718eb61c <+28>: je     0x7fff718eb634            ; <+52>
; 有预设的new_handler则调用
0x7fff718eb61e <+30>: callq  *%rax
; rdi存入元素个数作为malloc()首个也是唯一实参
0x7fff718eb620 <+32>: movq   %rbx, %rdi
0x7fff718eb623 <+35>: callq  0x7fff71909e06            ; symbol stub for: malloc
; 此时rax寄存器存储malloc()函数的返回值
; 即所分到的内存单元的首地址，若分配失败则是NULL
; 对rax寄存器进行自与运算，根据结果修改标识位
0x7fff718eb628 <+40>: testq  %rax, %rax
; 分配失败则跳转去找预设的new_handler
0x7fff718eb62b <+43>: je     0x7fff718eb614            ; <+20>
; 执行完毕恢复堆栈
0x7fff718eb62d <+45>: addq   $0x8, %rsp
0x7fff718eb631 <+49>: popq   %rbx
0x7fff718eb632 <+50>: popq   %rbp
0x7fff718eb633 <+51>: retq
; 下面是奇妙的bad_alloc逻辑
; 开始为C函数__cxa_allocate_exception()准备实参
; 第一个参数是分配要抛出的bad_alloc的大小
; __cxa_allocate_exception()会分配的动态内存大小为
; sizeof(__cxa_exception +bad_alloc)
; 返回值是后面bad_alloc对象的首地址
; 这个首地址前面存储的正是__cxa_exception对象
; 这个结构体存储了后面bad_alloc对象的header信息
0x7fff718eb634 <+52>: movl   $0x8, %edi
0x7fff718eb639 <+57>: callq  0x7fff7190713f            ; __cxa_allocate_exception
0x7fff718eb63e <+62>: movq   %rax, %rbx
0x7fff718eb641 <+65>: movq   %rbx, %rdi
; 这个构造函数std::bad_alloc::bad_alloc()没有实质内容
; 并且只是构造了个空对象bad_alloc而已
; 类声明只有两个虚函数，所以内存里只有一个虚表指针占用 8 bytes 
; 这里很有意思 可以看到构造函数虽然没有形参
; 但内部实现却是传入了其分配到的内存首地址（rdi寄存器的值）
; 这个思路是合理的 因为编译器要在这块土地上初始化对象
0x7fff718eb644 <+68>: callq  0x7fff718ebab0            ; std::bad_alloc::bad_alloc()
; 把bad_alloc的类型信息的地址作为第二个参数
; 所有bad_alloc对象共用一个typeinfo
0x7fff718eb649 <+73>: leaq   0x39f73c70(%rip), %rsi    ; typeinfo for std::bad_alloc
; 把bad_alloc的析构函数（也没有实质内容）指针作为第三个参数
0x7fff718eb650 <+80>: leaq   0x467(%rip), %rdx         ; std::bad_alloc::~bad_alloc()
; 上面得到的bad_alloc首地址作为第一个参数
0x7fff718eb657 <+87>: movq   %rbx, %rdi
; 调用__cxa_throw抛出bad_alloc异常
; 这个函数里才会构建__cxa_exception的内容
0x7fff718eb65a <+90>: callq  0x7fff719071f6            ; __cxa_throw

libsystem_malloc.dylib`malloc:
->  0x7fff7bcb84af <+0>:  pushq  %rbp
0x7fff7bcb84b0 <+1>:  movq   %rsp, %rbp
0x7fff7bcb84b3 <+4>:  pushq  %rbx
0x7fff7bcb84b4 <+5>:  pushq  %rax
0x7fff7bcb84b5 <+6>:  movq   %rdi, %rax
0x7fff7bcb84b8 <+9>:  leaq   0x38474b41(%rip), %rdi    ; virtual_default_zone
0x7fff7bcb84bf <+16>: movq   %rax, %rsi
0x7fff7bcb84c2 <+19>: callq  0x7fff7bcb9156            ; malloc_zone_malloc
0x7fff7bcb84c7 <+24>: movq   %rax, %rbx
0x7fff7bcb84ca <+27>: testq  %rbx, %rbx
0x7fff7bcb84cd <+30>: jne    0x7fff7bcb84da            ; <+43>
0x7fff7bcb84cf <+32>: callq  0x7fff7bcd133e            ; symbol stub for: __error
0x7fff7bcb84d4 <+37>: movl   $0xc, (%rax)
0x7fff7bcb84da <+43>: movq   %rbx, %rax
0x7fff7bcb84dd <+46>: addq   $0x8, %rsp
0x7fff7bcb84e1 <+50>: popq   %rbx
0x7fff7bcb84e2 <+51>: popq   %rbp
0x7fff7bcb84e3 <+52>: retq
0x7fff7bcb84e4 <+53>: nop

所以大家可以看到
主线很清晰：

operator new[](unsigned long) -> operator new(unsigned long) -> malloc(unsigned long)

并且大家可以看出来
这个虽然是Darwin自己的C++标准库，但是事实上和LLVM的实现几乎完全一致
尽管如此，我还是决定要下载Apple自己的源码看看
在苹果的开源项目(tarball)主页中可以下载到许多非常有价值的二进制项目：

• libsystem：开机启动
• dyld: 动态链接库加载
• Webkit：Safari的浏览器引擎
• libc：C Standard Library
• objc4: 相信很多朋友看过，OC的runtime
• CF：Core Foundation，这个也很常用。runloop、网络层等常用的底层库都来源于此。
• libcpp: 今天的主角，C++ Standard Library
• libcppabi: C++标准库底层接口
• libmalloc: malloc等内存分配C函数的实现
• lldb：LLVM的debugger
• llvmcore: LLVM组件核心
  ……
  除此之外，还有各种不着边际的项目，系统自带基础工具、Java，Pearl、Python、ruby……

我下载了libmalloc、libcpp、libcppabi
以上几个函数都能在这三个dylib里找到
而libcppabi实际上又已经把关键逻辑整合进了libcpp里
看代码注释可以知道
苹果这一套东西事实上是从gcc中抽象出来的
开源库里同样包含了gcc的实现libstdcxx
在关键函数operator new(unsigned long)中我做了详尽注释
所用代码都是libcpp中可以搜到的
经我比对之后确实完全一样
只贴出operator new(unsigned long)的代码

__attribute__((__weak__, __visibility__("default")))
void *
operator new(std::size_t size)
#if !__has_feature(cxx_noexcept)
    throw(std::bad_alloc)
#endif
{
    if (size == 0)
        size = 1;
    void* p;
    while ((p = ::malloc(size)) == 0)
    {
        // If malloc fails and there is a new_handler,
        // call it to try free up memory.
        std::new_handler nh = std::get_new_handler();
        if (nh)
            nh();
        else
#ifndef _LIBCPP_NO_EXCEPTIONS
            throw std::bad_alloc();
#else
            break;
#endif
    }
    return p;
}

可以和上面LLVM的对比，其实基本完全一样的
除了一些宏定义
由此联想Christ Lattner在其间的桥梁作用
所以说LLVM是苹果的嫡系毫不夸张
当然 代码里很多也是直接使用了gcc的实现
诸君有兴趣可以看看libstdcxx里的内容
实质上是大同小异的，但是libstdcxx烙上了gcc的dual licence
当然 gcc的代码完全可以在其svn下载
svn checkout svn://gcc.gnu.org/svn/gcc/trunk SomeLocalDir
所以Darwin里的libcpp可以说就是gcc+llvm的结合

还有一个要补充的就是最后throw std::bad_alloc();的逻辑
这句代码虽然简短 但是在汇编中的扩展很丰富
虽然在汇编里做了详细注释 但是不免令人迷惑
贴出关键源码供大家细细品味

class bad_alloc : public exception
{
public:
//空的内联构造函数
     __attribute__ ((__visibility__("hidden"), __always_inline__)) 
             bad_alloc() throw() {} 
//虚函数产生虚表
    virtual ~bad_alloc() throw();
    virtual const char* what() const throw();
};

     ……
     ……

extern "C" void *
__cxxabiv1::__cxa_allocate_exception(size_t thrown_size) throw()
{
  void *ret;
//分配空间 = __cxa_exception + bad_alloc
  thrown_size += sizeof (__cxa_exception);
  ret = malloc (thrown_size);

  if (! ret)
    {
     ……
     ……

      if (!ret)
    std::terminate ();
    }

//前面的__cxa_exception部分清零
//因为不会对这块内存调用构造函数
//在__cxa_throw函数里对其直接设置结构体成员
  memset (ret, 0, sizeof (__cxa_exception));
//返回的是bad_alloc的首地址
  return (void *)((char *)ret + sizeof (__cxa_exception));
}

extern "C" void
__cxxabiv1::__cxa_throw (void *obj, std::type_info *tinfo, 
             void (*dest) (void *))
{
//取得bad_alloc对象前面的__cxa_exception对象的指针
//并设置各种context和handler
  __cxa_exception *header = __get_exception_header_from_obj (obj);
  header->referenceCount = 1;
  header->exceptionType = tinfo;
  header->exceptionDestructor = dest;
  header->unexpectedHandler = __cxxabiapple::__cxa_unexpected_handler;
  header->terminateHandler = __cxxabiapple::__cxa_terminate_handler;
  __GXX_INIT_EXCEPTION_CLASS(header->unwindHeader.exception_class);
  header->unwindHeader.exception_cleanup = __gxx_exception_cleanup;

  // <rdar://problem/9073695> std::uncaught_exception() becomes true before evaluating the throw-expression rather than after
  // uncaught_exception is now set the __cxa_throw, whereas previously
  // is was set in __cxa_allocate.   See Issue 475.
  // http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#475
  __cxa_eh_globals *globals = __cxa_get_globals ();
  globals->uncaughtExceptions += 1;

#if __arm__
  _Unwind_SjLj_RaiseException (&header->unwindHeader);
#else
  _Unwind_RaiseException (&header->unwindHeader);
#endif

  // Some sort of unwinding error.  Note that terminate is a handler.
  __cxa_begin_catch (&header->unwindHeader);
  std::terminate ();
}

还有一个可以展开说的是构造函数和析构函数的隐藏形参
正如上文汇编码中std::bad_alloc()这个构造函数
其并没有形参 但是rdi寄存器里依然存入了其所分配内存空间首地址
说明首地址是个隐藏形参
做个实验：

struct T {
    size_t s;
    T() {}
    ~T() {};
};

int main(int argc, const char * argv[]) {
    T t = T();
}

看看main函数的汇编码：

Testcpp`main:
    0x100000f20 <+0>:  pushq  %rbp
    0x100000f21 <+1>:  movq   %rsp, %rbp
    0x100000f24 <+4>:  subq   $0x20, %rsp
    0x100000f28 <+8>:  leaq   -0x18(%rbp), %rax
    0x100000f2c <+12>: movl   %edi, -0x4(%rbp)
    0x100000f2f <+15>: movq   %rsi, -0x10(%rbp)
; rdi存储的正是堆栈中为8字节的t对象分配的空间首地址
    0x100000f33 <+19>: movq   %rax, %rdi
    0x100000f36 <+22>: callq  0x100000f50               ; T::T at main.cpp:14
; 可见析构函数也是一样的，以首地址为隐藏形参
    0x100000f3b <+27>: leaq   -0x18(%rbp), %rdi
    0x100000f3f <+31>: callq  0x100000f70               ; T::~T at main.cpp:15
    0x100000f44 <+36>: xorl   %eax, %eax
    0x100000f46 <+38>: addq   $0x20, %rsp
    0x100000f4a <+42>: popq   %rbp
    0x100000f4b <+43>: retq   

看到实验结果就彻底证实了隐藏形参的存在

虽然汇编码中未寻到vec_new()的踪迹
但是在libcppabi项目中却能找到相关代码
libcppabi >> src >> vec.cc 中有如下函数

  extern "C" void *
  __cxa_vec_new2(size_t element_count,
         size_t element_size,
         size_t padding_size,
         __cxa_cdtor_type constructor,
         __cxa_cdtor_type destructor,
         void *(*alloc) (size_t),
         void (*dealloc) (void *))
  {
    size_t size = element_count * element_size + padding_size;
    char *base = static_cast <char *> (alloc (size));
    if (!base)
      return base;

    if (padding_size)
      {
    base += padding_size;
    reinterpret_cast <size_t *> (base)[-1] = element_count;
#ifdef _GLIBCXX_ELTSIZE_IN_COOKIE
    reinterpret_cast <size_t *> (base)[-2] = element_size;
#endif
      }
    try
      {
    __cxa_vec_ctor(base, element_count, element_size,
               constructor, destructor);
      }
    catch (...)
      {
    {
      uncatch_exception ue;
      dealloc(base - padding_size);
    }
    throw;
      }
    return base;
  }

这个函数就是完成了Lippman在书中所描述的功能
即

1. 使用指定的内存分配函数申请内存
2. 循环调用数组中的元素的构造函数对元素进行初始化
3. 一旦遇到异常，使用指定的内存回收函数销毁内存

正是基于一种迭代器的方式
所以这个函数在数组头部多申请了
padding_size个字节用于存储元素个数
其中前size_t个字节存储element_size
后size_t个字节存储element_count
也就是说应该有 padding_size = 2 * size_t

不过很遗憾没有搜到任何对此函数的引用
这是一套函数
还有__cxa_vec_new和__cxa_vec_new3
__cxa_vec_new是一个便捷函数
实质上最后调用的是__cxa_vec_new2
而__cxa_vec_new3的内容则与__cxa_vec_new2几乎完全一样
只是其dealloc参数的形参列表不同

根据Lippman的说法，对于他设计的编译器
如果一个数组的元素所属的类定义了默认构造函数和析构函数
编译器就会在创建数组时加入这个函数以初始化数组元素

但是很可惜我并未从任何对照实验中搜到此函数
并且他也不是inline 的 所以不会是缺少符号的问题
LLVM中也有这套函数
但是他的文档中也缺乏对此函数的用法说明
按照Lippman所言
vec_new系列函数一定是要对数组中的元素施加构造函数
才会使用
从代码逻辑上我们也能清晰看到这点
那么很可能就是在某种类型的数组元素集体初始化
的过程中调用了这个C函数

如果有朋友能在留言中告诉我这套函数的用例
最好带上代码说明 将不胜感激

最后很高兴经过数日的研究终于证明了
欧阳大哥的结论是正确的
不过根据实验结果
我会把论点略微改进为：

具有自定义的析构函数的类对象构成的动态数组
会在数组前存储元素个数值
这个元素个数值消耗空间大小为sizeof(size_t)

最值得高兴的是

找到动态数组内存分配的基本方式

这个目标已经达成
多亏了欧阳大哥的不吝赐教
才有机会让我对这个流程有了更为深刻的认识

---

2018-04-15 更

欧阳大哥的idea很好
应该看一下 以变量作为元素个数
创建动态数组时的汇编表现
毕竟C++规定动态数组的个数必须为整数
但是却不必为常量表达式
写一个illustration：

struct T {
    size_t s;
    ~T() {};
};

T *foo(size_t i) {
    return new T[i];
}

int main(int argc, const char * argv[]) {
    foo(2);
}

今天偶然看到欧阳大哥写了很多汇编方面的文章
学到在Xcode中使用如下选项

Debug -> Debug Workflow -> Always show disassembly

可以很方便地在源程序代码的断点处直接进入汇编代码完成单步调试
于是得到了如下汇编代码：

Testcpp`foo:
    0x100000f10 <+0>:  pushq  %rbp
    0x100000f11 <+1>:  movq   %rsp, %rbp
; 首次默认分配的堆栈大小为36bytes，即0x20
    0x100000f14 <+4>:  subq   $0x20, %rsp
    0x100000f18 <+8>:  movq   $-0x1, %rax
; 设置element_size为8bytes
    0x100000f1f <+15>: movl   $0x8, %ecx
    0x100000f24 <+20>: movl   %ecx, %edx
    0x100000f26 <+22>: movq   %rdi, -0x8(%rbp)
    0x100000f2a <+26>: movq   -0x8(%rbp), %rdi
    0x100000f2e <+30>: movq   %rax, -0x10(%rbp)
    0x100000f32 <+34>: movq   %rdi, %rax
; 此时rax存储了element_count = 2
; rdx则存储了element_size = 8
; 相乘后则得到需要分配的总字节数16，即0x10
    0x100000f35 <+37>: mulq   %rdx
    0x100000f38 <+40>: seto   %sil
; 加上数组头所需的8字节
    0x100000f3c <+44>: addq   $0x8, %rax
    0x100000f40 <+48>: setb   %r8b
    0x100000f44 <+52>: orb    %r8b, %sil
    0x100000f47 <+55>: testb  $0x1, %sil
    0x100000f4b <+59>: movq   -0x10(%rbp), %r9
    0x100000f4f <+63>: cmovneq %r9, %rax
; 把元素个数放堆栈里暂时保存
    0x100000f53 <+67>: movq   %rdi, -0x18(%rbp)
    0x100000f57 <+71>: movq   %rax, %rdi
    0x100000f5a <+74>: callq  0x100000f9c               ; symbol stub for: operator new[](unsigned long)
; 从堆栈中取出元素个数
    0x100000f5f <+79>: movq   -0x18(%rbp), %rdi
; 元素个数存到数组头
    0x100000f63 <+83>: movq   %rdi, (%rax)
; 返回值是首元素的地址，需要8bytes offset
    0x100000f66 <+86>: addq   $0x8, %rax
    0x100000f6a <+90>: addq   $0x20, %rsp
    0x100000f6e <+94>: popq   %rbp
    0x100000f6f <+95>: retq   

即使是variable也没有出现vec_new()
想想这也是正常的vec_new()本身就是为了给数组元素
轮流执行默认初始化用的
所以不管元素个数是否确定
需要初始化的地方总会做初始化
而且Lippman在书中说这个函数是在runtime库调用的
所以未来尝试换个角度找找运行时源码可能会有意外收获

在缺少自定义析构函数的对照组实验中
事实上只是少了这段代码逻辑

; 加上数组头所需的8字节
addq   $0x8, %rax
movq   %rax, %rdi

另外还需要注意的是

T() = default;
~T() = default;

这样的写法是C++11启用的
但是编译器并不保证一定会生成默认构造/析构函数
只是在必要的时候会产生
也就是说编译出来的代码必须确实对默认构造/析构函数产生引用
编译器才会为用户插入默认构造/析构函数的声明和定义

在lldb玩汇编时常需要查看堆栈
所以就需要使用从gdb沿袭的读内存指令：
x/{count}{format}{unit} address_of_memory
unit：b – byte 1字节，h – half word 2字节，w – word 4字节，g – giant word 8字节
format：x是16进制，f是浮点，d是十进制
count：读取unit的数量
address_of_memory：可以直接输入十六进制的堆栈地址，也可以写程序中的符号名

例如：
x/8xb 0x7fff7bcb84e4 就是从这个地址开始读取 8 bytes
x/3xg 0x7fff7bcb84e4 就是从这个地址读取3个giant words
需要注意的是
X64+Darwin所使用的内存布局是小端模式
也就是说低位字节存储在低地址
所以读取bytes的时候 0x00001234 读出来就是

0x7fff7bcb84e4 : 0x34 0x12 0x00 0x00

如果你用大单位譬如word来读
那么就不必担心这个问题
依然是0x00001234