发表更新源码阅读笔记 / GDB 源码分析16 分钟读完 (大约2414个字)

GDB 源码分析 02：函数前导代码分析（中）

代码：gdb/prologue-value.h，gdb/prologue-value.c

上一次，我们考虑了如何对一个值进行模糊分析，接下来，我们要对一片内存的值做出模糊的估计。在有了这种估计方式之后，我们就能够将其进行真正的应用了。

首先考虑一个问题：如何记录一个内存中的数据？不要忘记，我们需要分析一个函数的前导代码，而前导代码往往做的是栈操作。那么，既然我们不能预先知道栈地址的值，我们自然就得以一个寄存器作为基地址，那么我们需要存储的就是某个地址距离基地址寄存器的偏移量；同时，内存中的对象并不自带类型，所以需要长度作为其标识；最后，我们还要记下它的值。这就是下面这个结构体想要做的事情：

1
2
3
4
5
6
struct pv_area::area_entry {
    struct area_entry *prev, *next;
    CORE_ADDR offset;
    CORE_ADDR size;
    pv_t value;
}

注意到它有两个指向前后的指针。事实上，它构成了一个环形双向链表，在后面的分析中，我们还会看到，它是以偏移量的大小进行排序的。然后就是把这个双向链表包装成一个类：

1
2
3
4
5
6
class pv_area {
private:
    int m_base_reg;
    CORE_ADDR m_addr_mask;
    struct area_entry *m_entry;
}

其中除了指向这样一个链表的指针之外，还有基地址寄存器的寄存器号，以及一个地址的掩码。看到后面之后会更容易理解这个掩码的目的，在这里我们只需要简单地认为，我们的地址空间是一个环形，前后相连即可。

接下来看类里面的三个私有成员函数：

1
2
3
4
5
6
7
8
9
10
11
void pv_area::clear_entries() {
    struct area_entry *e = m_entry;
    if (e) {
        do {
            struct area_entry *next = e.next;
            xfree(e);
            e = next;
        } while (e != m_entry);
        m_entry = 0;
    }
}

这个函数用来清空双向链表。其中比较需要注意的就是 xfree 这个函数，事实上这个函数和内存保护有关，在读到这里的时候，我们不妨将其当成一个简单的 free 函数理解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
struct pv_area::area_entry *pv_area::find_entry(CORE_ADDR offset) {
	struct area_entry *e = m_entry;
    if (!e) {
        return 0;
    }
    while (((e->next->offset - offset) & m_addr_mask) < 
           ((e->offset - offset) & m_addr_mask)) {
        e = e->next;
    }
    while (((e->prev->offset - offset) & m_addr_mask) < 
           ((e->offset - offset) & m_addr_mask)) {
        e = e->prev;
    }
    m_entry = e;
    return e;
}

这个函数用来找到在 offset 之后的第一项。如果本身这片区域一项也没有，那么就自然地返回一个空指针。而如果 offset 中一项也没有，那当然就会返回较为靠前的一项。这里需要澄清的是，因为 m_entry 指向的是环形链表中的任意一项，往后扫描和往前扫描都是必须的。最后一步将 m_entry 设为 e 就是出于局部性的假定，假定最近被访问的这项很可能再次被访问，从而提高整个数据结构的搜索效率。

在此不妨停下来思考一个问题：哪怕没有掩码的问题，是否有可能直接写成 e->next->offset < e->offset ？答案是否定的，原作者在注释中特别表明了这一点：

1
2
3
4
5
6
/*Note that, even setting aside the addr_mask stuff, we must not
  simplify this, in high school algebra fashion, to
  (e->next->offset < e->offset), because of the way < interacts
  with wrap-around.  We have to subtract offset from both sides to
  make sure both things we're comparing are on the same side of the
  discontinuity.  */

解释很清楚，在这也就不翻译了。

第三个函数就是一个判断 offset 处 size 大小的一项是否与某个 entry 重合，非常简单，直接贴代码不解释：

1
2
3
4
int pv_area::overlaps(struct area_entry *entry, CORE_ADDR offset, CORE_ADDR size) {
    return (((entry->offset - offset) & m_addr_mask) < size || 
            ((offset - entry->offset) & m_addr_mask) < entry->size);
}

接下来观察一下公有的成员函数，首先来看构建过程：

1
2
3
pv_area::pv_area(int base_reg, int addr_bit): m_base_reg(base_reg),
	m_addr_mask(((((CORE_ADDR) 1) << (addr_bit - 1)) - 1) << 1) | 1),
	m_entry(nullptr){}

非常简单的构造函数，但是这里我们就可以重新解释一下地址掩码的含义了。当我们有一个 32 bit 的地址时，自然而然地我们只希望其比较 32 bit，但是寄存器又是可以有 64 bit 的：也就是说，有一部分是需要被抛弃的。

一个很细节的问题是，为什么不把这个表达式写成 ((CORE_ADDR) 1 << addr_bit) - 1 ？注意，移位的位数与类型的宽度相同时，得到的结果是未定义的。如果采取上面代码的形式，就一定能够保证得到正确的结果。

析构函数非常简单：

1
2
3
pv_area::~pv_area() {
    clear_entries();
}

然后用了一个有趣的小技巧取消了默认析构函数和 operator=：

1
DISABLE_COPY_AND_ASSIGN(pv_area);

宏定义如下，这是为了与不同版本的 c++ 标准兼容：

1
2
3
4
5
6
7
8
9
#if defined(__cplusplus) && __cplusplus >= 201103
#define DISABLE_COPY_AND_ASSIGN(TYPE)		\
  TYPE (const TYPE&) = delete;			\
  void operator= (const TYPE &) = delete
  #else
#define DISABLE_COPY_AND_ASSIGN(TYPE)		\
  TYPE (const TYPE&);				\
  void operator= (const TYPE &)
#endif

接下来我们就要正式进行模拟存取了。下面这个成员函数用来将一个 size 大小的值 value 写入到 addr 处：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
void pv_area::store(pv_t addr, CORE_ADDR size, pv_t value) {
    if (store_would_trash(addr)) {
        clear_entries();
    } else {
        CORE_ADDR offset = addr.k;
        struct area_entry *e = find_entry(offset);
        while (e && overlaps(e, offset, size)) {
            struct area_entry *next = (e->next == e) ? 0 : e->next;
            e->prev->next = e->next;
            e->next->prev = e->prev;
            xfree(e);
            e = next;
        }
        m_entry = e;
    }
    if (value.kind == pvk_unknown) {
        return;
    } else {
        CORE_ADDR offset = addr.k;
        struct area_entry *e = XNEW(struct area_entry);
        e->offset = offset;
        e->size = size;
        e->value = value;
        if (m_entry) {
            e->prev = m_entry->prev;
            e->next = m_entry;
            e->prev->next = e->next->prev = e;
        } else {
            e->prev = e->next = e;
            m_entry = e;
        }
    }
}

这个函数稍微有点长，但是思路其实挺简单的：

  • 如果存储操作会使得我现在所有的表项都被无效化，那么直接先把表清掉；
  • 否则的话，清掉所有与这个值重合的项，因为这些项都会被覆写掉；
  • 然后，如果我需要存的值未知，那就直接返回；
  • 如果我需要存的值已知，那就创建出这一项并把它插进去。

XNEW(T) 事实上拓展到了泛型 xnew<T>() ，这个函数和前面的 xfree 一样，只需要当成一个 new 就行，暂时不需要深究；接下来需要考虑的是，什么时候我可能无效化整个表：

1
2
3
4
5
bool pv_area::store_would_trash(pv_t addr) {
    return (addr.kind == pvk_unknown ||
           addr.kind == pvk_constant ||
           (addr.kind == pvk_register && addr.reg != m_base_reg));
}

事实上说这种情况可能无效化整个表是不准确的。准确地说，是我们不能确定这次存储和我们现在的表有什么关系，为了方便起见，我们就直接认为这整个表的分析是不可能的，因而就将其抛弃了。这个函数还会被在其他地方调用，比如，考虑取一个值的问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
pv_t pv_area::fetch(pv_t addr, CORE_ADDR size) {
    if (!m_entry || store_would_trash(addr)) {
        return pv_unknown();
    } else {
        CORE_ADDR offset = addr.k;
        struct area_entry *e = find_entry(offset);
        if (e->offset == offset && e->size == size) {
            return e->value;
        } else {
            return pv_unknown();
        }
    }
}

很显然，这个函数的核心还是保守估计。需要注意的是第一行判断，如果表里没有内容，或者这个地址和表无关，那就返回未知。这里，“和表无关”才是上面那个函数真正的语义。

当然，我们可以找找我们的表中有没有关于某个寄存器值的信息：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool pv_area::find_reg(struct gdbarch *gdbarch, int reg, CORE_ADDR *offset_p) {
    struct area_entry *e = m_entry;
    if (e) {
        do {
            if (e->value.kind == pvk_register 
                && e->value.reg == reg
                && e->value.k == 0 
                && e->size == register_size(gdbarch, reg)) {
                if (offset_p) {
                    *offset_p = e->offset;
                }
                return true;
            }
            e = e->next;
        } while (e != m_entry);
    }
    return false;
}

关于 gdbarch 结构体，现在只要知道它记录了架构信息即可，register_size 则返回某种架构中某个寄存器的大小。这个函数也没什么特别的，就是一个遍历操作。

接下来有一个稍微看起来复杂点但功能很简单的函数，也是这个类的最后一个函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void pv_area::scan(void (*func)(void *closure, 
                                pv_t addr, 
                                CORE_ADDR size, 
                                pv_t value), void *closure) {
    struct area_entry *e = m_entry;
    pv_t addr;
    addr.kind = pvk_register;
    addr.reg = m_base_reg;
    if (e) {
        do {
            addr.k = e->offset;
            func(closure, addr, e->size, e->value);
            e = e->next;
        } while (e != m_entry);
    }
}

循环遍历整个表，对表中的每一项做一个自定义操作。函数指针使得整个函数看起来有些抽象，但也不难明白它的意思。

现在，我们已经获得了对一块内存区域的数据进行分析的工具，接下来，我们可以利用这些工具进行分析了。下一次将针对两种架构的整个前导代码分析过程做出解释，在那里，我们可以看见这些工具都是怎样被应用的，又能给出怎样的结果。

#
关注我

分类

最新文章

归档

标签

信息论1
复杂度1
抽象代数2
数学2
概率论1
源码阅读3
程序分析3
群论2
范畴论1
计算复杂性理论2
计算机图形学1
计算理论4
量子计算4

链接

×