通用内存快照裁剪压缩库Tailor介绍及源码分析（一）

背景

我们知道内存快照是治理 OOM 问题及其他类型的内存问题的重要数据源，内存快照中保存了进程虚拟机的完整的堆内存数据，很多时候也是调查其他类型异常的重要参考。但是dump出来的堆转储文件.hprof往往很大，以 LargeHeap 应用为例，其 OOM 时的内存快照大小通常在512M左右，要有效的存储和获取都是一个问题。

线下拿到hprof文件相对容易，也可以预防OOM，但覆盖的场景十分有限，很多问题往往是线上海量用户在各种场景下发生的，如何高效稳定收集到线上的内存快照，这对于一套相对完整的通用异常数据搜集系统而言是至关重要的一环。我们需要在APP中实现一套回捞机制，把线上生成的hprof文件回传到云端。然而传输过程对于数据大小是十分敏感的，首当其冲就是流量消耗问题，其次，更小的快照传输耗时更少，回传成功率也会大幅提升，所以需要对一些OOM分析无关紧要的数据进行裁剪，从而减小用于传输的hprof数据大小。内存快照是虚拟机堆内存数据的完整 copy，这其中可能包含有账号、Token、联系人、密钥以及其他可能存在隐私的图片/字符串等，隐私数据是必须要裁剪掉的，否则会存在隐私安全问题。

目前已知的裁剪方案有种：一种是已开源的 Matrix 方案，另一种是西瓜视频Android团队开源的hprof 流裁剪方案。

Matrix 方案分为两步：先通过 Debug.dumpHprofData 直接 dump 出一个完整的 hprof 文件；然后通过分析 hprof 文件分别裁剪掉数据相同的 Bitmap 对象和 String 对象。其裁剪方案存在以下问题：

原生接口直接 dump 出的 hprof 文件过大，存储问题不好解决；
裁剪过程中涉及到大文件 I/O 和 hprof 分析，对 App 性能的影响不好控制；
裁剪不彻底，快照中仍然存在大量无用数据和可能存在的隐私问题。

hprof 流裁剪则是基于 hprof 文件格式，在 hprof 文件写入过程中进行裁剪压缩，存储空间问题大幅改善，也没有大文件 I/O 和 hprof 分析过程带来的性能问题。

由西瓜Android团队开发的Tailor正是一款通用内存快照裁剪压缩工具，通过它可以在异常时直接dump出一个迷你内存快照。快照中没有任何敏感信息，更重要的是文件非常小的同时数据也相对完整，非常适合离线分析OOM及其他类型异常的调查定位。

流裁剪压缩实现原理

如果只为了治理 OOM，可以进行最大化裁剪（如byte[]、char[]、boolean[]、short[]、float[]、int[]、double[]、long[]、hprof格式裁剪），甚至可以只保留 app-heap。但作为通用异常数据，我们可能也会在必要的时候，通过回捞快照来分析非 OOM 类的异常，甚至是 native 异常。随着稳定性治理的深入，快照更多是用来分析非 OOM 异常。对于非 OOM 异常，快照的完整性尤为重要，同时非 OOM 的 crash 堆内存通常较小，最大化裁剪没有必要，综合考虑下只进行 byte[]、char[] 和 hprof 格式裁剪。

快照 dump 的过程大致可以分为 5 步，Tailor 只关注 open 和 write 环节。通过 xHook [3]（针对 Android 平台 ELF 的 PLT hook库，PLT hook 的本质是修改内存中PLT表对应的GOT条目保存的地址值, 来实现跳转到自定义函数的。在加载动态库的时候，动态库的每一个外部函数都会在PLT表中有一个条目，是一小段可执行代码，外部函数的调用都是在调用 PLT 表里的条目，然后 PLT 会无条件跳转到对应的GOT条目保存的地址。具体参见另一篇文章【动态链接中的PLT和GOT原理】）在 native 层 hook dump 过程必然会调用到的 open/write 函数，以此实现对hprof 文件写入流的代理，进而进行 hprof 流裁剪。为了进一步降低写入后的文件体积，Tailor 会在裁剪之后直接进行 zlib 流压缩。流程大致如下：

. 调用 Tailor.dumpHprofData() 时，会依次调用 nOpenProxy()、Debug.dumpHprofData()、nCloseProxy()；

. nOpenProxy 在 native 层开启对 int open(const char* __path, int __flags, ...)和 ssize_t write_proxy(int fd, const char*buffer, size_t count) 的 hook 代理；

. Debug.dumpHprofData 执行中会先调到 nOpenProxy 函数，hook 代理逻辑会过滤出目标文件的 fd；调到 write 函数时 hook 代理逻辑通过 fd 过滤出目标文件的写入数据进行裁剪压缩；

. nCloseProxy 逻辑清除之前的 hook 代理。

// isGzip 是否在裁剪之后进行zip压缩
public static synchronized void dumpHprofData(String fileName, boolean isGzip) throws IOException {
       nOpenProxy(fileName, isGzip);
       Debug.dumpHprofData(fileName);
       nCloseProxy();
}

如图所示

源码分析

当我们需要堆转储时，原本方法是调用 Debug.dumpHprofData(fileName)，现在调用Tailor.dumpHprofData(fileName, isGzip)即可。

接下来从源码看一下Tailor是如何hook 内存快照的open 和 write 来实现裁剪和压缩的。

//Tailor.java
// isGzip 是否在裁剪之后进行zip压缩
public static synchronized void dumpHprofData(String targetPath, boolean isGzip) throws IOException {
       nOpenProxy(targetPath, isGzip);
       Debug.dumpHprofData(targetPath);
       nCloseProxy();
}

堆转储开始前启用裁剪：

//xloader.cpp
void Tailor_nOpenProxy(JNIEnv* env, jobject obj, jstring name, jboolean gzip) {
    target = -1;
    reader = new ByteReader();
    writer = createWriter(env->GetStringUTFChars(name, 0), gzip);
    fill(writer, const_cast<char *>(VERSION), 18);
    LOGGER(">>> open %s", ((0 == hook()) ? "success" : "failure"));
}

创建一个ByteReader，后面会用来接收dump的字节流。根据是否需要gzip创建对应的Writer，负责将ByteReader中经过裁剪的数据写到hprof文件。

dump的默认行为是先open一个文件，然后往文件里写内存快照数据，如果我们只hook write方法，我们没法判断当前在写数据的fd就是hprof文件。

ssize_t write_proxy(int fd, const char *buffer, size_t count) {
    if (target == fd) {
        //fd是open_proxy返回的target，进行裁剪处理
        return handle(buffer, count);
    } else {
	//原样输出
        return write(fd, buffer, count);
    }
}

我们也必须hook open操作, 如果启用了裁剪，并且打开文件path和nOpenProxy传入的targetPath一致，那么就可以确定是在dump hprof文件。

int open_proxy(const char *path, int flags, mode_t mode) {
    if (writer != nullptr && strcmp(writer->name, path) == 0) {
	// w模式打开代理文件%path%.proxy
        return target = writer->proxy(flags, mode);
    } else {
	//原样打开
        return open(path, flags, mode);
    }
}

记录下打开的target。注意必须返回一个有效的fd给open调用者，这里打开的是加了.proxy后缀的hprof文件，因为我们的Writer构造函数打开了实际的hprof文件。

多个进程不能以写入模式打开同一个文件，否则打开操作就会失败，没法下一步。

堆转储完成后关闭裁剪

void Tailor_nCloseProxy(JNIEnv *env, jobject obj) {
    delete reader;
    reader = nullptr;

    delete writer;
    writer = nullptr;

    xh_core_clear();
}

释放reader和writer，并置为nullptr，在open_proxy的时候就不会走到打开代理文件了，write_proxy原样输出，相当于没有hook。

hook过程

hook 进程虚拟内存中动态链接的.so的open和write函数，替换为自定义的open_proxy和write_proxy实现。

xh_core_register负责注册需要hook的so文件和符号，通过正则表达匹配动态链接的so文件的路径名称，满足匹配的都是需要hook的。

自身这个hook库中open_proxy会调用原open函数，如果进行hook的话，就变成递归调用open_proxy了，所以必须要忽略掉，对于要忽略的hook，使用xh_core_ignore函数进行添加。

int hook() {
    int state = 0;
    state |= xh_core_register(".*\\.so$", "open", (void *) open_proxy, nullptr);
    state |= xh_core_register(".*\\.so$", "write", (void *) write_proxy, nullptr);
    state |= xh_core_ignore(".*libtailor\\.so$", "open");
    state |= xh_core_ignore(".*libtailor\\.so$", "write");
    state |= xh_core_refresh(0);
    return state;
}

1.先看一下注册逻辑

//xh_core.c
int xh_core_register(const char *pathname_regex_str, const char *symbol,
                     void *new_func, void **old_func)
{
    xh_core_hook_info_t *hi;
    regex_t              regex;

    if(NULL == pathname_regex_str || NULL == symbol || NULL == new_func) return XH_ERRNO_INVAL;

    if(xh_core_inited)
    {
        XH_LOG_ERROR("do not register hook after refresh(): %s, %s", pathname_regex_str, symbol);
        return XH_ERRNO_INVAL;
    }

    if(0 != regcomp(&regex, pathname_regex_str, REG_NOSUB)) return XH_ERRNO_INVAL;

    if(NULL == (hi = malloc(sizeof(xh_core_hook_info_t)))) return XH_ERRNO_NOMEM;
    //1. hi 保存符号
    if(NULL == (hi->symbol = strdup(symbol)))
    {
        free(hi);
        return XH_ERRNO_NOMEM;
    }
#if XH_CORE_DEBUG
    if(NULL == (hi->pathname_regex_str = strdup(pathname_regex_str)))
    {
        free(hi->symbol);
        free(hi);
        return XH_ERRNO_NOMEM;
    }
#endif
    // 2. hi 保存path 正则表达式
    hi->pathname_regex = regex;
    // 3. hi 保存新函数指针
    hi->new_func = new_func;
    // 4. hi 保存旧函数指针
    hi->old_func = old_func;
    
    pthread_mutex_lock(&xh_core_mutex);
    TAILQ_INSERT_TAIL(&xh_core_hook_info, hi, link);
    pthread_mutex_unlock(&xh_core_mutex);

    return 0;
}

主要就是最后一句TAILQ_INSERT_TAIL(&xh_core_hook_info, hi, link);

xh_core_hook_info
是一个xh_core_hook_info_queue_t 结构体类型，用于表示一个尾队列的头节点，该队列专门用于存储 xh_core_hook_info 类型的元素，这里把hi 添加到xh_core_hook_info的末尾。

static xh_core_hook_info_queue_t xh_core_hook_info = TAILQ_HEAD_INITIALIZER(xh_core_hook_info);

typedef struct xh_core_hook_info_queue {
        struct xh_core_hook_info * tqh_first; /* 指向队列中的第一个元素， 如果队列为空，则这个指针应该为 NULL。这是访问队列中第一个元素的标准方式*/
        struct xh_core_hook_info * *tqh_last; /* 它是一个指向指针的指针，指向队列中最后一个元素中的tqe_next指针。如果队列为空，这个指针可能指向 tqh_first，或者有一个特定的空值或标志来表示队列为空。这种设计允许在 O(1) 时间内向队列的末尾添加新元素，因为可以直接修改 *tqh_last 来指向新元素。*/
} xh_core_hook_info_queue_t;

通过TAILQ_HEAD_INITIALIZER宏初始化了一个空队列xh_core_hook_info

#define TAILQ_HEAD_INITIALIZER(head)                                    \
    { NULL, &(head).tqh_first }

如果队列为空，则 tqh_last 通常会指向 tqh_first 的地址，因为当队列为空时，没有元素可以指向，但我们需要一个地方来存储指向 NULL 的指针的地址，以便知道何时队列为空。

hi指针指向xh_core_hook_info_t，xh_core_hook_info_t用来存储hook信息：

typedef struct xh_core_hook_info
{
#if XH_CORE_DEBUG
    char     *pathname_regex_str;
#endif
    regex_t   pathname_regex; //hook文件的path 正则表达式
    char     *symbol;                  //hook文件中的符号名称
    void     *new_func;               //替换函数指针
    void    **old_func;                //存储原函数指针地址
    TAILQ_ENTRY(xh_core_hook_info,) link; //双向链表
} xh_core_hook_info_t;

link成员负责维系链表结构

struct {
    struct xh_core_hook_info * tqe_next;  /* 指向队列中下一个元素的指针。 */ 
    struct xh_core_hook_info * *tqe_prev; /* 指向队列中前一个元素中tqe_next指针的指针。这个设计允许在O(1)时间内从队列中移除任何节点，因为可以直接修改前一个节点的tqe_next指针，而无需遍历链表。 */ 
} link;

插入队列尾，修改link链表

#define TAILQ_INSERT_TAIL(head, elm, field) do {                        \
        TAILQ_NEXT((elm), field) = NULL;                                \
        (elm)->field.tqe_prev = (head)->tqh_last;                       \
        *(head)->tqh_last = (elm);                                      \
        (head)->tqh_last = &TAILQ_NEXT((elm), field);                   \
    } while (0)

#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)

2. 再看xhook_refresh 函数

int xh_core_refresh(int async)
{
    //init
    xh_core_init_once();
    if(!xh_core_init_ok) return XH_ERRNO_UNKNOWN;

    if(async)
    {
        //init for async
        xh_core_init_async_once();
        if(!xh_core_async_init_ok) return XH_ERRNO_UNKNOWN;
    
        //refresh async
        pthread_mutex_lock(&xh_core_mutex);
        xh_core_refresh_thread_do = 1;
        pthread_cond_signal(&xh_core_cond);
        pthread_mutex_unlock(&xh_core_mutex);
    }
    else
    {
        //refresh sync
        pthread_mutex_lock(&xh_core_refresh_mutex);
        xh_core_refresh_impl();
        pthread_mutex_unlock(&xh_core_refresh_mutex);
    }
    
    return 0;
}

核心是 xh_core_refresh_impl

这个方法比较大,下面仅保留核心的部分逻辑。

static void xh_core_refresh_impl()
{
......
//读取/proc/self/maps,获取内存映射信息
    if(NULL == (fp = fopen("/proc/self/maps", "r")))
    {
        XH_LOG_ERROR("fopen /proc/self/maps failed");
        return;
    }
	
    while(fgets(line, sizeof(line), fp))
    {
        /*
	从一行数据从分别获取addr offset 等信息
	文件中的每一行代表一个虚拟内存区域，其格式通常如下：
	7f68caa1c000-7f68cabd6000 r-xp 00000000 08:01 136253   /lib/x86_64-linux-gnu/libc-2.19.so

	所处虚拟内存地址(VMA)范围‌：起始地址-结束地址。
	VMA权限‌：表示该内存区域的访问权限，r=读，w=写,x=,s=共享,p=私有。
	偏移量‌：表示VMA对应的segment在映像文件中的偏移, 偏移值为0表示一个映射内存区域的开始。
	主设备号和次设备号‌：08:01。
	映像文件的节点号inode：136253
	映像文件的路径‌：如果是文件映射，这里会显示文件的路径名。对于匿名映射（如堆和栈）则没有路径名，比如下面这两个segment:
	0060c000-0062d000  rw-p 00000000 00:00 0   [heap]  # 堆区
	7f68cb005000-7f68cb006000 rw-p 00000000 00:00 0  # 路径为空
	*/
        if(sscanf(line, "%"PRIxPTR"-%*lx %4s %lx %*x:%*x %*d%n", &base_addr, perm, &offset, &pathname_pos) != 3) continue;

	//check permission
	if(perm[0] != 'r') continue;
	if(perm[3] != 'p') continue; //do not touch the shared memory

	//check offset
	//
	//We are trying to find ELF header in memory.
	//It can only be found at the beginning of a mapped memory regions
	//whose offset is 0.
	if(0 != offset) continue;

        ...
        //获取pathname 指针位置
        pathname = line + pathname_pos;
        pathname_len = strlen(pathname);
        ....
		// 这里是检查 pathname 是否在要hook的queue里,如果是就继续走下面
		TAILQ_FOREACH(hi, &xh_core_hook_info, link) //find hook info
        {
            if(0 == regexec(&(hi->pathname_regex), pathname, 0, NULL, 0))
            {
                TAILQ_FOREACH(ii, &xh_core_ignore_info, link) //find ignore info
                {
                    if(0 == regexec(&(ii->pathname_regex), pathname, 0, NULL, 0))
                    {
                        if(NULL == ii->symbol)
                            goto check_finished;

			//pathname和symbol在忽略队列里，不对该.so文件做hook
                        if(0 == strcmp(ii->symbol, hi->symbol)) 
                            goto check_continue;
                    }
                }

                match = 1;
            check_continue:
                break;
            }
        }
check_finished:
    if(0 == match) continue;
      ....
      //当前so需要hook，检查是否已存在对应的map info，首次检查肯定是走到else, if就先略
	mi_key.pathname = pathname;
       if(NULL != (mi = RB_FIND(xh_core_map_info_tree, &xh_core_map_info, &mi_key))) 
       {
       ......
       }
       else
       {
       //不存在创建一个新的 map info
            if(NULL == (mi = (xh_core_map_info_t *)malloc(sizeof(xh_core_map_info_t)))) continue;
            if(NULL == (mi->pathname = strdup(pathname)))
            {
                free(mi);
                continue;
            }
            mi->base_addr = base_addr;

            //repeated?
            //We only keep the first one, that is the real base address
            if(NULL != RB_INSERT(xh_core_map_info_tree, &map_info_refreshed, mi))
            {
#if XH_CORE_DEBUG
                XH_LOG_DEBUG("repeated map info when create: %s", line);
#endif
                free(mi->pathname);
                free(mi);
                continue;
            }

            //hook
            xh_core_hook(mi); //hook
       }
    }
}

xh_core_map_info_t的对象记录pathname,so基地址base_addr的信息,然后就调用到xh_core_hook, 再调用xh_core_hook_impl。

static void xh_core_hook_impl(xh_core_map_info_t *mi)
{
    //init 根据elf被加载到内存中的基地址,解析获得一个elf对象，这个elf对象协助我们在内存中定位要hook的位置，下面会进一步介绍获取逻辑。
    if(0 != xh_elf_init(&(mi->elf), mi->base_addr, mi->pathname)) return;
    
    //hook
    xh_core_hook_info_t   *hi;
    xh_core_ignore_info_t *ii;
    int ignore;
	// 这里很简单就是看一下白名单,有没有要忽略的
    TAILQ_FOREACH(hi, &xh_core_hook_info, link) //find hook info
    {
        if(0 == regexec(&(hi->pathname_regex), mi->pathname, 0, NULL, 0))
        {
            ignore = 0;
            TAILQ_FOREACH(ii, &xh_core_ignore_info, link) //find ignore info
            {
                if(0 == regexec(&(ii->pathname_regex), mi->pathname, 0, NULL, 0))
                {
                    if(NULL == ii->symbol) //ignore all symbols
                        return;

                    if(0 == strcmp(ii->symbol, hi->symbol)) //ignore the current symbol
                    {
                        ignore = 1;
                        break;
                    }
                }
            }
	  //不忽略就xh_elf_hook
            if(0 == ignore)
                xh_elf_hook(&(mi->elf), hi->symbol, hi->new_func, hi->old_func);
        }
    }
}

elf文件结构

先了解一下elf文件的基本信息，有助于理解xh_elf_init和后续的xh_elf_hook。
libtest.so 的 ELF 文件头信息：

$ llvm-readelf -h libtest.so

ELF 文件的起始处，有一个固定格式的定长的文件头（32 位架构为 52 字节，64 位架构为 64 字节）。ELF 文件头以 magic number 0x7F 0x45 0x4C 0x46 开始（其中后 3 个字节分别对应可见字符 E L F）。

ELF 文件头中包含了 SHT（section header table）和 PHT（program header table）在当前 ELF 文件中的起始位置和长度。例如，libtest.so 的 SHT 起始位置为 2980，长度 40 字节；PHT 起始位置为 52，长度 32字节。

SHT（section header table）

ELF 以 section 为单位来组织和管理各种信息。ELF 使用 SHT 来记录所有 section 的基本信息。主要包括：section 的类型、在文件中的偏移量、大小、加载到内存后的虚拟内存相对地址、内存中字节的对齐方式等。

libtest.so 的 SHT:

$ llvm-readelf -S libtest.so

PHT（program header table）

ELF 被加载到内存时，是以 segment 为单位的。一个 segment 包含了一个或多个 section。ELF 使用 PHT 来记录所有 segment 的基本信息。主要包括：segment 的类型、在文件中的偏移量、大小、加载到内存后的虚拟内存相对地址、内存中字节的对齐方式等。

libtest.so 的 PHT：

所有类型为 PT_LOAD 的 segment 都会被动态链接器（linker）映射（mmap）到内存中，这个elf文件有三个segment会被加载，segment1的Offset为0，表示elf文件从首字节开始，长度为FileSiz(0x004ec)字节的这段数据。

连接视图（Linking View）和执行视图（Execution View）

连接视图：ELF 未被加载到内存执行前，以 section 为单位的数据组织形式。
执行视图：ELF 被加载到内存后，以 segment 为单位的数据组织形式。

我们关心的 hook 操作，属于动态形式的内存操作，因此主要关心的是执行视图，即 ELF 被加载到内存后，ELF 中的数据是如何组织和存放的。

.dynamic section

这是一个十分重要和特殊的 section，其中包含了 ELF 中其他各个 section 的内存位置等信息。在执行视图中，总是会存在一个类型为 PT_DYNAMIC 的 segment，这个 segment 就包含了 .dynamic section 的内容。

无论是执行 hook 操作时，还是动态链接器执行动态链接时，都需要通过 PT_DYNAMIC segment 来找到 .dynamic section 的内存位置，再进一步读取其他各项 section 的信息。

libtest.so 的 .dynamic section：

$ llvm-readelf -d libtest.so

Dynamic section at offset 0x64c contains 28 entries:

Tag Type Name/Value

0x00000001 (NEEDED) Shared library: [liblog.so]

0x00000001 (NEEDED) Shared library: [libz.so]

0x00000001 (NEEDED) Shared library: [libc++_shared.so]

0x00000001 (NEEDED) Shared library: [libm.so]

0x00000001 (NEEDED) Shared library: [libdl.so]

0x00000001 (NEEDED) Shared library: [libc.so]

0x0000001e (FLAGS) BIND_NOW

0x6ffffffb (FLAGS_1) NOW

0x00000011 (REL) 0x364

0x00000012 (RELSZ) 32 (bytes)

0x00000013 (RELENT) 8 (bytes)

0x6ffffffa (RELCOUNT) 3

0x00000017 (JMPREL) 0x384

0x00000002 (PLTRELSZ) 24 (bytes)

0x00000003 (PLTGOT) 0x2730

0x00000014 (PLTREL) REL

0x00000006 (SYMTAB) 0x1ec

0x0000000b (SYMENT) 16 (bytes)

0x00000005 (STRTAB) 0x2ec

0x0000000a (STRSZ) 120 (bytes)

0x6ffffef5 (GNU_HASH) 0x28c

0x00000004 (HASH) 0x2ac

0x0000001a (FINI_ARRAY) 0x2644

0x0000001c (FINI_ARRAYSZ) 8 (bytes)

0x6ffffff0 (VERSYM) 0x25c

0x6ffffffe (VERNEED) 0x26c

0x6fffffff (VERNEEDNUM) 1

0x00000000 (NULL) 0x0

xh_elf_init获取elf对象信息

int xh_elf_init(xh_elf_t *self, uintptr_t base_addr, const char *pathname)
{
	...
	//always reset
memset(self, 0, sizeof(xh_elf_t));
 //elf文件路径
self->pathname = pathname; 
  //elf加载到进程虚拟内存区域中的起始地址
self->base_addr = (ElfW(Addr))base_addr;
 //ehdr是ELF头指针，指向这个地址
self->ehdr = (ElfW(Ehdr) *)base_addr; 
//elf起始地址+ELF头信息中PHT偏移值算出运行时的PHT起始地址，并将phdr指针指向这个地址，有时会有segment fault
self->phdr = (ElfW(Phdr) *)(base_addr + self->ehdr->e_phoff); 

//elf中找offset 是0的 load segment1
ElfW(Phdr) *phdr0 = xh_elf_get_first_segment_by_type_offset(self, PT_LOAD, 0);

/* 
save load bias addr
load segment1虚拟内存相对地址VirtAddr一般都是0，映射到内存中正好就是从分配的elf基地址base_addr开始，这里是针对不为0的情况， 需要使用基地址-VirtAddr进行偏差修正，segment1必须从base_addr开始，之后bias_addr + 相对偏移地址才是实际地址。
*/
if(self->base_addr < phdr0->p_vaddr) return XH_ERRNO_FORMAT;
self->bias_addr = self->base_addr - phdr0->p_vaddr;

//找 dynamic segment
ElfW(Phdr) *dhdr = xh_elf_get_first_segment_by_type(self, PT_DYNAMIC);

//解析 dynamic segment, 先找到 .dynamic section
self->dyn          = (ElfW(Dyn) *)(self->bias_addr + dhdr->p_vaddr);
...
}

解析dynamic segment

先找到 .dynamic section，然后根据.dynamic信息找出hook涉及到的sections在内存中的地址，比如下面这几个：

.rel.dyn .rel.plt包含需要重定位的符号信息，定位的内存区域就是我们要hook的地方。

查找一个符号的相关信息会在三块区域出现：.dynsym 动态符号表，.dynstr 字符表，.gnu.hash 动态链接符号散列表

.gnu.hash是用于符号表查找的一种优化结构。

0x00000011 (REL) 0x364
0x00000012 (RELSZ) 32 (bytes)
对应.rel.dyn section的内存偏移地址和文件大小：
[Nr] Name Type Address Off Size ES Flg Lk Inf Al
[ 8] .rel.dyn REL 00000364 000364 000020 08 A 2 0 4

0x00000017 (JMPREL) 0x384
0x00000002 (PLTRELSZ) 24 (bytes)
对应.rel.plt section的内存偏移地址和文件大小：
[Nr] Name Type Address Off Size ES Flg Lk Inf Al
[ 9] .rel.plt REL 00000384 000384 000018 08 AI 2 18 4

0x00000006 (SYMTAB) 0x1ec
0x00000005 (STRTAB) 0x2ec
分别对应.dynsym 和.dynstr ：
[ 2] .dynsym DYNSYM 000001ec 0001ec 000070 10 A 7 1
[ 7] .dynstr STRTAB 000002ec 0002ec 000078 00 A 0 0 1

0x6ffffef5 (GNU_HASH) 0x28
对应.gnu.hash section的内存偏移地址和文件大小：
[ 5] .gnu.hash GNU_HASH 0000028c 00028c 000020 00 A 2 0 4

查找符号和hook

int xh_elf_hook(xh_elf_t *self, const char *symbol, void *new_func, void **old_func)
{
    ...
    // 1. 根据symbol名称查找symbol索引
    // 去bucket 和chain 中找到symbol对应的索引
    //find symbol index by symbol name
    if(0 != (r = xh_elf_find_symidx_by_name(self, symbol, &symidx))) return 0;
    //2. 对.rel(a).plt对应的got位置的数据进行替换
    //replace for .rel(a).plt
    if(0 != self->relplt)
    {
        xh_elf_plain_reloc_iterator_init(&plain_iter, self->relplt, self->relplt_sz, self->is_use_rela);
        while(NULL != (rel_common = xh_elf_plain_reloc_iterator_next(&plain_iter)))
        {
            if(0 != (r = xh_elf_find_and_replace_func(self,
                                                      (self->is_use_rela ? ".rela.plt" : ".rel.plt"), 1,
                                                      symbol, new_func, old_func,
                                                      symidx, rel_common, &found))) return r;
            if(found) break;
        }
    }

    //replace for .rel(a).dyn
    if(0 != self->reldyn)
    {
        xh_elf_plain_reloc_iterator_init(&plain_iter, self->reldyn, self->reldyn_sz, self->is_use_rela);
        while(NULL != (rel_common = xh_elf_plain_reloc_iterator_next(&plain_iter)))
        {
            if(0 != (r = xh_elf_find_and_replace_func(self,
                                                      (self->is_use_rela ? ".rela.dyn" : ".rel.dyn"), 0,
                                                      symbol, new_func, old_func,
                                                      symidx, rel_common, NULL))) return r;
        }
    }

    //replace for .rel(a).android
    if(0 != self->relandroid)
    {
        xh_elf_packed_reloc_iterator_init(&packed_iter, self->relandroid, self->relandroid_sz, self->is_use_rela);
        while(NULL != (rel_common = xh_elf_packed_reloc_iterator_next(&packed_iter)))
        {
            if(0 != (r = xh_elf_find_and_replace_func(self,
                                                      (self->is_use_rela ? ".rela.android" : ".rel.android"), 0,
                                                      symbol, new_func, old_func,
                                                      symidx, rel_common, NULL))) return r;
        }
    }
    
    return 0;
}

查找符号

根据symbol名称查找symbol索引

static int xh_elf_find_symidx_by_name(xh_elf_t *self, const char *symbol, uint32_t *symidx)
{
    if(self->is_use_gnu_hash) //当存在.gnu.hash，就使用该表来检索
        return xh_elf_gnu_hash_lookup(self, symbol, symidx);
    else
        return xh_elf_hash_lookup(self, symbol, symidx);
}

static int xh_elf_gnu_hash_lookup(xh_elf_t *self, const char *symbol, uint32_t *symidx)
{
    if(0 == xh_elf_gnu_hash_lookup_def(self, symbol, symidx)) return 0;
    if(0 == xh_elf_gnu_hash_lookup_undef(self, symbol, symidx)) return 0;
    return XH_ERRNO_NOTFND;
}

大致过程是首先从.gnu.hash中进行查询，得到该符号在动态符号表.dynsym中的偏移。根据这个偏移读出一个符号，并找到这个符号的名字在字符表.dynstr中的偏移。从字符表中读出符号的名称如果与要查找的符号匹配，则找到了这个符号。

static int xh_elf_gnu_hash_lookup_def(xh_elf_t *self, const char *symbol, uint32_t *symidx)
{
//使用GNU哈希函数生成符号的32位哈希
    uint32_t hash = xh_elf_gnu_hash((uint8_t *)symbol);
    //一个掩码的尺寸，单位是位(bits)
    static uint32_t elfclass_bits = sizeof(ElfW(Addr)) * 8;
//使用布隆过滤器检查符号是否存在，计算符号应该使用第几个Bloom filter掩码word，通常gnu hash只有一个掩码，掩码包含了所有导出符号的掩码位
    size_t word = self->bloom[(hash / elfclass_bits) % self->bloom_sz];
//计算运行时符号掩码位mask
    size_t mask = 0
        | (size_t)1 << (hash % elfclass_bits)
        | (size_t)1 << ((hash >> self->bloom_shift) % elfclass_bits);
    
    //if at least one bit is not set, this symbol is surely missing
  //测试符号掩码位和word，只要一位没有匹配，查询的符号在当前elf对象中就不存在
    if((word & mask) != mask) return XH_ERRNO_NOTFND;

//bucket[n]的值i是动态符号表相同键排序的符号的最低的索引
//从此处开始递归匹配符号名称和hash值。
//ignore STN_UNDEF, self->symoffset是hash表可访问.dynsym的第一个符号的索引，小于该值就表示符号不存在
    uint32_t i = self->bucket[hash % self->bucket_cnt];
    if(i < self->symoffset) return XH_ERRNO_NOTFND;
    
    //loop through the chain
    while(1)
    {
	//.dynsym第i项在.dynstr的偏移st_name，得到名称字符串
        const char     *symname = self->strtab + self->symtab[i].st_name;
	//从哈希链取hash，因为【i】是从self->symoffset开始的，这里减掉self->symoffset从0索引
        const uint32_t  symhash = self->chain[i - self->symoffset];
        //.dynsym中的符号和查找符号的hash、名称都相同，返回索引【i】
        if((hash | (uint32_t)1) == (symhash | (uint32_t)1) && 0 == strcmp(symbol, symname))
        {
            *symidx = i;
            XH_LOG_INFO("found %s at symidx: %u (GNU_HASH DEF)\n", symbol, *symidx);
            return 0;
        }
        
        //chain ends with an element with the lowest bit set to 1
        if(symhash & (uint32_t)1) break;
        
        i++;
    }
    
    return XH_ERRNO_NOTFND;
}

.gnu.hash section

一个GNU_HASH节由四个分离的部分组成，按顺序如下：

Header 32位字数组(4条目)提供节参数：
- nbuckets：哈希桶个数
- symndx：动态符号表有dynsymcount数量的符号。symndx是动态符号表中可被访问的第一个符号的索引，从这里起我们称为符号表第二部分。这意味着有(dynsymcount-symndx)个符号可以通过哈希表访问到。
  动态符号表中的某些符号在哈希表中永远找不到，比如共享对象: 所有UNDEF符号。
- maskwords：在哈希表节的Bloom filter部分中，ELFCLASS单位大小的掩码个数（每个掩码可能为32位或64位）。这个值必须非零，同时必须是一个2的幂次数，见下面的描述。
  注意到值0可以被解释成哈希节中不存在Bloom filter。然而，GNU linkers不会做此处理——GNU哈希节永远至少包含1个掩码。
- shift2：Bloom filter使用的位移计数。
Bloom Filter：GNU_HASH sections包含一个Bloom filter。该过滤器用于快速拒绝在对象中不存在的符号查找。对ELFCLASS32对象来说，Bloom filter的掩码是32位的，ELFCLASS64则是64位。
Hash Buckets：nbuckets长度的32位哈希桶数组。
Hash Values：32位哈希链值的数组，长度为(dynsymcount-symndx)，每个符号都源自动态符号表的第二部分。

Header，哈希桶以及哈希链永远都是32位字，而Bloom filter可能是32或64位，这取决于ELF对象的类别。

Bloom Filter

GNU hash sections包含一个Bloom filter。Bloom filters是概率性的，意味着可能会错检，但是不可能误检（简单来说，就是通过布隆过滤器的不一定在hash表中，但不通过的一定不在表中）。filter用来快速拒绝不在对象中的符号名，避免更多昂贵的哈希查找操作。通常地，只有一个对象在进程中拥有给定的符号。跳过对其他所有对象的哈希操作可以显著地增快符号查询。

GNU hash使用一个k=2的Bloom filter，这意味着会有两个独立的哈希函数为每个符号所使用。单一掩码设置位的计算方法应该如下:

H1 = dl_new_hash(sym);

H2 = H1 >> shift2;

第一个哈希结果右移(shift2)产生第二个哈希。

计算Bloom filter掩码N

N = ((H1 / C) % maskwords);

C表示一个掩码的尺寸，单位是位(bits)，即32位或64位

Bloom filter掩码N的位设置如下：

BITMASK = (1 << (H1 % C)) | (1 << (H2 % C));

链接编辑器设置这些位的方法：

bloom[N] |= BITMASK;

运行时链接器使用的测试如下：

(bloom[N] & BITMASK) == BITMASK;

Hash Buckets

跟随Bloom filter的是哈希桶(nbuckets个)，以32位为单位。数组中第N位置处的值是到动态符号表最低的索引：

(dl_new_hash(symname) % nbuckets) == N

如下图.dynsym所示，动态符号表有相同的键排序（hash % nbuckets）：

N值相同的所有符号会在对应哈希链中以相同顺序排列，buckets[N]存的是链表中的第一个符号的索引，dynsym[buckets[N]]也就是哈希链中的第一个符号。

这也是代码中我们计算出查找符号所在的哈希桶，拿到起始符号索引i, 就可以递增i来遍历符号表进行比较的原因。

Hash Values

GNU hash section的最后一部分包含(dynsymcount-symndx)个32位字，每个条目都是动态符号表的导出符号。每个字的前31位包含和符号表值一致的31位值。最后一位用做阻塞位。当符号是给定哈希链中最后一个或者两个桶的边界时其置1。

为了便于理解可以看下图

下面以libtest.so为例，根据xh_elf_gnu_hash_lookup_def()展示openTest函数查找过程:

$ llvm-objdump -M intel -j .gnu.hash -s libtest.so

Contents of section .gnu.hash:

028c 01000000 05000000 01000000 1a000000 ................

029c 0808a000 05000000 4a3824d4 b787488d ........J8$...H.

nbuckets=1， symndx=5（第一个可被访问的索引符号function），maskwords=1，shift2=26， Bloom words是0xa00808(elf是32位的，所以是4字节)。

Hash Buckets 的第一项是 0x00000005，是 .dynsym的索引。只有一个hash桶，后面跟的是.dynsym从symndx项的hash。

Symbol table '.dynsym' contains 7 entries:

   Num: Value Size Type Bind Vis Ndx Name

   0: 00000000 0 NOTYPE LOCAL DEFAULT UND

   1: 00000000 0 FUNC GLOBAL DEFAULT UND __cxa_finalize@LIBC

   2: 00000000 0 FUNC GLOBAL DEFAULT UND __cxa_atexit@LIBC

   3: 00000000 0 NOTYPE GLOBAL DEFAULT UND foo

   4: 00000000 0 NOTYPE GLOBAL DEFAULT UND doo

   5: 00001590 70 FUNC GLOBAL DEFAULT 12 function

   6: 000015e0 17 FUNC GLOBAL DEFAULT 12 openTest

Contents of section .dynsym:

01ec 00000000 00000000 00000000 00000000 ................

01fc 01000000 00000000 00000000 12000000 ................

020c 10000000 00000000 00000000 12000000 ................

021c 26000000 00000000 00000000 10000000 &...............

022c 2a000000 00000000 00000000 10000000 *...............

023c 1d000000 90150000 46000000 12000c00 ........F.......

024c 2e000000 e0150000 11000000 12000c00 ................

xh_elf_gnu_hash("openTest")返回hash为0x8d4887b7，计算掩码位：

 size_t mask = 0
        | (size_t)1 << (hash % 32)
        | (size_t)1 << ((hash >> shift2) % 32);

mask = 0x800008

word = 0xa00808

(word & mask) = 0x800008 (mask)

所以可以快速判断openTest在.dynsym符号表中，继续下一步。

uint32_t i = self->bucket[hash % self->bucket_cnt];

根据hash找到对应的桶，buckets[N]就是哈希链中动态符号表相同键排序的符号的最低的索引。

这里nbuckets=1, .dynsym第二部分任何符号都在这个桶里，最低索引是5， i = bucket[0]=0x00000005也反映了这个事实。

从索引 i 开始递归匹配符号名称和hash值。

const char *symname = self->strtab + self->symtab[i].st_name;
.dynsym第5项在.dynstr的偏移0x1d即第29字节处为funtion。

Contents of section .dynstr:

02ec 005f5f63 78615f66 696e616c 697a6500 .__cxa_finalize.

02fc 5f5f6378 615f6174 65786974 0066756e __cxa_atexit.fun

030c 6374696f 6e00666f 6f00646f 6f006f70 ction.foo.doo.op

031c 656e5465 7374006c 6962632e 736f004c enTest.libc.so.L

032c 49424300 6c69626c 6f672e73 6f006c69 IBC.liblog.so.li

033c 627a2e73 6f006c69 62632b2b 5f736861 bz.so.libc++_sha

034c 7265642e 736f006c 69626d2e 736f006c red.so.libm.so.l

035c 6962646c 2e736f00 ibdl.so.

const uint32_t symhash = self->chain[i - self->symoffset];
从哈希链索引0开始取hash

第一次比较, 符号表当前符号为function, symhash=0xd424384a，都不匹配；
i++;
第二次比较，符号表当前符号为openTest, symhash=0x8d4887b7，hash=0x8d4887b7，匹配，此时i=6。

GOT表替换

根据找到的符号索引对.rel(a).plt对应的got位置的数据进行替换。
其他几个.rel(a).xxx对应的套路是一模一样的，这里分析一下rel(a).plt 替换的套路:

//replace for .rel(a).plt
if(0 != self->relplt)
{
    xh_elf_plain_reloc_iterator_init(&plain_iter, self->relplt, self->relplt_sz, self->is_use_rela);
//第一步，遍历过程中取到.rel.plt数组的一个元素rel_common
    while(NULL != (rel_common = xh_elf_plain_reloc_iterator_next(&plain_iter)))
    {
     //找到got中符号索引相同的条目记录的重定位地址addr,并进行指针替换,addr 为so的基地址+ r_offset
        if(0 != (r = xh_elf_find_and_replace_func(self,
                                                  (self->is_use_rela ? ".rela.plt" : ".rel.plt"), 1,
                                                  symbol, new_func, old_func,
                                                  symidx, rel_common, &found))) return r;
        if(found) break;
    }
}


static int xh_elf_find_and_replace_func(xh_elf_t *self, const char *section,
                                        int is_plt, const char *symbol,
                                        void *new_func, void **old_func,
                                        uint32_t symidx, void *rel_common,
                                        int *found)
{
    ElfW(Rela)    *rela;
    ElfW(Rel)     *rel;
    ElfW(Addr)     r_offset;
    size_t         r_info;
    size_t         r_sym;
    size_t         r_type;
    ElfW(Addr)     addr;
    int            r;

    if(NULL != found) *found = 0;
   //取得条目的r_info 4字节数据，对应符号索引和类型
  //取得条目的r_offset 4字节数据，对应got的偏移地址
    if(self->is_use_rela)
    {
        rela = (ElfW(Rela) *)rel_common;
        r_info = rela->r_info;
        r_offset = rela->r_offset;
    }
    else
    {
        rel = (ElfW(Rel) *)rel_common;
        r_info = rel->r_info;
        r_offset = rel->r_offset;
    }

    //check sym
   //#define ELF32_R_SYM(x) ((x) >> 8)  r_info的高三字节是符号索引，和之前找到的符号索引比较
    r_sym = XH_ELF_R_SYM(r_info);
    if(r_sym != symidx) return 0;

    //check type
   //r_info的最低字节是重定位类型, 如果是plt，针对不同的ELFCLASS，XH_ELF_R_GENERIC_JUMP_SLOT预定义为函数类型，如i686架构是R_386_JMP_SLOT， arm是R_ARM_JUMP_SLOT等
    r_type = XH_ELF_R_TYPE(r_info);
    if(is_plt && r_type != XH_ELF_R_GENERIC_JUMP_SLOT) return 0;
    if(!is_plt && (r_type != XH_ELF_R_GENERIC_GLOB_DAT && r_type != XH_ELF_R_GENERIC_ABS)) return 0;

    //we found it
//将found标记为找到
    XH_LOG_INFO("found %s at %s offset: %p\n", symbol, section, (void *)r_offset);
    if(NULL != found) *found = 1;

    //do replace
//函数实际内存地址=so的基地址+ r_offset，然后进行替换
    addr = self->bias_addr + r_offset;
    if(addr < self->base_addr) return XH_ERRNO_FORMAT;
    if(0 != (r = xh_elf_replace_function(self, symbol, addr, new_func, old_func)))
    {
        XH_LOG_ERROR("replace function failed: %s at %s\n", symbol, section);
        return r;
    }

    return 0;
}


static int xh_elf_replace_function(xh_elf_t *self, const char *symbol, ElfW(Addr) addr, void *new_func, void **old_func)
{
    void         *old_addr;
    unsigned int  old_prot = 0;
    unsigned int  need_prot = PROT_READ | PROT_WRITE;
    int           r;

    //already replaced?
    //here we assume that we always have read permission, is this a problem?
    if(*(void **)addr == new_func) return 0;

    //get old prot
    if(0 != (r = xh_util_get_addr_protect(addr, self->pathname, &old_prot)))
    {
        XH_LOG_ERROR("get addr prot failed. ret: %d", r);
        return r;
    }
    
    if(old_prot != need_prot)
    {
        //set new prot
        if(0 != (r = xh_util_set_addr_protect(addr, need_prot)))
        {
            XH_LOG_ERROR("set addr prot failed. ret: %d", r);
            return r;
        }
    }
    
    //save old func
    old_addr = *(void **)addr;
    if(NULL != old_func) *old_func = old_addr;

    //replace func
//指令替换
    *(void **)addr = new_func; //segmentation fault sometimes

    if(old_prot != need_prot)
    {
        //restore the old prot
        if(0 != (r = xh_util_set_addr_protect(addr, old_prot)))
        {
            XH_LOG_WARN("restore addr prot failed. ret: %d", r);
        }
    }
    
    //clear cache
//清除cpu 指令缓存
    xh_util_flush_instruction_cache(addr);

    XH_LOG_INFO("XH_HK_OK %p: %p -> %p %s %s\n", (void *)addr, old_addr, new_func, symbol, self->pathname);
    return 0;
}

同样的还是以libtest.so为例，展示一下GOT表的替换过程。

libtest.so 的.rel.plt section：

$ llvm-readelf -r libtest.so

Relocation section '.rel.plt' at offset 0x384 contains 4 entries:

Offset Info Type Sym. Value Symbol's Name

0000272c 00000107 R_386_JUMP_SLOT 00000000 __cxa_finalize@LIBC

00002730 00000207 R_386_JUMP_SLOT 00000000 __cxa_atexit@LIBC

00002734 00000607 R_386_JUMP_SLOT 000015e0 openTest

00002738 00000407 R_386_JUMP_SLOT 00000000 doo

每个条目8字节，前面查询openTest找到符号索引是6，遍历.rel.plt，找到第三条目匹配，Info字段高三字节索引为6，类型为需要的07（XH_ELF_R_GENERIC_JUMP_SLOT）：

00002734 00000607 R_386_JUMP_SLOT 000015e0 openTest

Offset 0x00002734就是GOT表中的位置, 打印一下.got.plt

$ llvm-objdump -M intel -j .got.plt -s libtest.so

Contents of section .got.plt:

2720 3c260000 00000000 00000000 f6150000 <&..............

2730 06160000 16160000 26160000 ........&...

地址偏移0x00002734处的值是0x1616，默认初始值是带有@plt标记的方法的第二条指令的地址，如这里的openTest@plt代码段push 0x10指令。