CSAPP 第三章 数据结构

CSAPP 第三章 数据结构

数组 结构 联合 数据对齐 数组 感觉CSAPP这里实际上是把C语言的数组和汇编语言一起讲了. 声明一个数组T A[N]实际上的意义如下: 分配N个T类型大小的连续空间 指向这个连续空间的第一个T类型大小的指针叫做A, A中的地址就是这个数组的第一个元素. 按照索引往后查找的时候, 只需要用地址加上

  1. 数组
  2. 结构
  3. 联合
  4. 数据对齐

数组

感觉CSAPP这里实际上是把C语言的数组和汇编语言一起讲了. 声明一个数组T A[N]实际上的意义如下:
  1. 分配N个T类型大小的连续空间
  2. 指向这个连续空间的第一个T类型大小的指针叫做A, A中的地址就是这个数组的第一个元素. 按照索引往后查找的时候, 只需要用地址加上偏移量乘以T的大小, 就是索引为偏移量的元素位置.
所以使用操作数作为内存引用的方式, 就可以很方便的计算出内存地址.

练习题 3.36

数组 元素大小 整个数组的大小 起始地址 元素i
short S[7] 2 14 xs xs+2i
short *T[3] 8 24 xt xt+8i
short **U[6] 8 48 xu xu+8i
int V[8] 4 32 xv xv+4i
double *W[4] 8 32 xw xw+8i
C语言的指针运算, 可以把指针直接加上某个数值i, 而指针的实际运算, 则会加上指针的数据类型乘以i. 对于指针运算, 如果需要计算指针的地址, 可以使用leaq指令; 如果需要通过指针取数, 则需要通过mov指令等可以引用内存的指令才可以.

练习题 3.37

有short类型数组S的地址xs存放在%rdx, 整数索引存放在%rcx中. 填写下列表格, 如果是指针就存在%rax中, 如果是short数据就存在%ax中.
表达式 类型 汇编代码
S+1 short* xs+2 leaq 2(%rdx), %rax
S[3] short M[xs+2*3] movw 6(%rdx), %ax
&s[i] short* xs+2i leaq (%rdx, %rcx, 2), %rax
S[4*i + 1] short M[xs+8i+2] movw 2(%rdx, %rcx, 8), %ax
S+i-5 short* xs+2i-10 leaq -10(%rdx, %rcx, 2), %rax
这里要注意的是, 凡是索引的运算, 对应到指针上的时候, 都要乘以数据元素的大小才可以. 有了单个数组的表示方法, 对于嵌套数组比如 int Ap[5][3], 可以想象为5行3元素数组, 即5行3列, 每一行内的数据是紧接着上一行开始存放的, 即排列完A[0][0]- A[0][2]之后, 紧接着排布A[1][0] - A[1][2]. 要访问多维元素的数组元素, 就要根据数组开始时候的地址, 然后根据索引号, 先按照行号算出行的开始位置, 再根据列号计算出具体元素的位置. T D[R][C]为例, 数组起始地址为xd, T的大小是L, 要访问实际索引为 D[i][j] 的元素, 计算如下:
  1. 由于i表示行号, 所以先定位到i行的起始地址, 可以用xd加上i乘以一行的长度, 一行的长度是C * L, 则第i行的起始地址是 xd + i * C * L
  2. 之后需要根据j来定位具体元素, 所以再从起始地址加上j*L即可.
  3. 最终的地址就是 xd + i * C * L + j * L = xd + L * (i * C + j)
简单的说, 其实和一维数组没有区别, 就是从数组起始地址, 根据行和列算出要查找的元素的偏移量, 然后乘以元素长度即可.

练习 3.38 根据汇编倒推P和Q两个二维数组的列和行

long sum_element(long i, long j){
    return P[i][j] + Q[j][i];
}

i in %rdi, j in %rsi

sum_element:
    leaq   0(,%rdi, 8),  %rdx       %rdx = 8i
    subq   %rdi, %rdx               这个是计算 %rdx - i = 7i
    addq   %rsi, %rdx               这个是计算 %rdx = 7i+j
    leaq   (%rsi, %rsi, 4), %rax    %rax = 5j
    addq   %rax, %rdi               %rdi = i + 5j
    movq   Q(, %rdi, 8), %rax       取地址是 (5j+i)*8 + Q, 可见对于Q来讲, 每行元素的数量为5, 所以M = 5
    movq   P(, %rdx, 8), %rax       取地址是 (7i+j)*8 + P, 可见对于P来讲, 每行元素是7, 所以N = 7
这个练习题主要就是运用了在放大之前, 有一个乘积的肯定是用实际行号乘以每行的元素多少来计算行首偏移量, 而直接取用实际索引的, 是实际的列. 而每行数量实际上是声明里的列长度, 注意不要被绕晕了. 在实际的程序中, 往往会按照一定的规律遍历数组, 编译器对于此种数组操作, 会进行优化, 不再保存数组首地址和寄存器中保存类似i和j的值, 而是直接根据数组的长度操作指针. 变长数组在编译之前, 也会计算出数组的长度或者步长来进行优化. 在实际编写代码的时候, 也可以优先考虑将问题抽象成操作指针.

结构

结构的实现非常类似于数组, 将其中的所有对象都存放在内存连续的一段区域内. 指向结构的指针同时也是指向结构第一个字节的指针. 编译器会根据结构中的对象的长度, 来将对结构的操作转换为指针的运算. 结构的所有操作都是在编译的时候转换为地址的运算, 机器代码不会包含关于字段名称或者声明的信息. 所以在操作结构的时候, 根据与数组一样的关系, 就可以计算出需要的地址.

练习题 3.41 根据结构的声明回答问题

struct prob {
    int *p;
    struct {
        int x;
        int y;
    } s;
    struct prob *next;
};
  1. A 下列字段的偏移量是多少:
    1. p: 由于指针p是这个结构的第一个元素, 偏移量就是0
    2. s.x: 可以看到, s.x是紧接在p之后的结构内的第一个元素, 所以偏移量是8
    3. s.y: 知道了s.x的偏移量是8, x的长度是4, 所以s.y是偏移量是12
    4. next: y的偏移量是12, y的长度是4, 所以next的偏移量是16
  2. 结构所需的总字节数是 8+4+4+8 = 24字节
  3. 根据汇编代码填写C代码:
                void sp_init(struct prob *sp)
                sp in %rdi
                sp_init:
                    movl 12(%rdi), %eax     取偏移量为12的4字节值到%eax中, 偏移量12的值是y
                    movl %eax, 8(%rdi)      将y写入到偏移量为8开始的四字节中, 所以前两句是 sp->s.x = sp->s.y
                    leaq 8(%rdi), %rax      %rax中的值是 sp->s.x 的地址
                    movq %rax, (%rdi)       这其实是 sp->p = &(sp->s.x)
                    movq %rdi, 16(%rdi)     这其实是把sp->next = sp
    
    补完之后的代码是:
                void sp_init(struct prob *sp){
                    sp->s.x = sp->s.y;
                    sp->p = &(sp->s.x);
                    sp->next = sp;
                }
    

练习题 3.42 根据汇编代码写出C语言

struct ELE {
    long v;
    struct ELE *p;
}
对应的一个过程fun的汇编代码是:
long fun(struct ELE *ptr)
prt in %rdi

fun:
    movl   $0, %eax         %rax清零, 可能是为返回值做准备
    jmp    .L2              无条件跳转.L2, 可能是循环开始
  .L3:
    addq   (%rdi), %rax     将 v 加到 %rax上
    movq   8(%rdi), %rdi    将ptr->next更新到 %rdi中
  .L2:
    testq  %rdi, %rdi       无条件跳转到的标号, 进去看是测试 %rdi
    jne    .L3              如果不是0, 则跳转L3, 至此可以知道这是一个while(ptr!=0)的循环, 循环体是 L3
    rep; ret                如果测试失败, 返回此时的%rax中的0.
可见这其实是一个不断判断当前ELE是否是一个空指针, 不是空指针就累加v的值. 写成C语言如下:
long fun(struct ELE *ptr){
    long result = 0;
    while(ptr!=NULL){
        result += ptr->v;
        ptr= ptr->p;
    }
    return result;
}

联合

联合的空间始终等于其中最大的元素所占据的空间. 联合的一个优点是, 以不同的数据类型去访问数据的时候, 位级表示是一样的. 虽然这个特性看上去好像在普通编程中不太好, 但却是一些底层和系统编程的必用技巧. 使用联合的一大套路,就是结合ENUM一起使用, 来标记当前的联合应该被如何读取和解释. 这也是C语言编程的老套路了, 如果数据结构中存在很多互斥的数据,使用联合能够节省非常大的空间.

练习题 3.43 将操作写成汇编代码

已经声明了如下的类型:
typedef union {
    struct {
        long u;
        short v;
        char w;
    } t1;
    struct {
        int a[2];
        char *p;
    } t2;
} u_type;
然后有一组这个函数, 用来把dest指针的内容设置为从联合中取到的数据, 现在有如下数据想取, 根据要取的数据填写取出的类型和汇编代码:
void get(u_type *up, type *dest){
    *dest = expr;
}
这里要先分析一下联合中的内容, struct1的大小为8 + 2 + 1 = 11 , struct2的大小为4+4+8 = 16. 所以大小是16, 之后就是要看准偏移量和对齐. up in %rdi, dest in %rsi
  1. up->t1.u, 这个是取struct1的开始元素, 很显然类型是long, 指针肯定就是up, 取8个字节即可, 汇编指令是
            movq  (%rdi), %rax
            movq  %rax , (%rsi)
    
  2. up->t1.v, 这个是取t1.v, 前边有一个long元素, 很显然偏移量是8 , 类型是short ,所以可以写:
             movl $0 %eax
             movw 8(%rdi), %ax
             movw %ax, (%rsi)
    
  3. &up->t1.w, 这个是取t1.w的地址, 这里不考虑对齐, 偏移量应该是8+2 =10, 显然结果也是一个指针, 所以可以写成, 类型是char*, 也就是一个指针
            movl $0, %eax          寄存器清0
            leaq 10(%rdi), %rax
            movl %rax , (%rsi)
    
  4. up->t2.a, 这个也是取首地址, 但是类型是一个指针, 而不是数组首个元素
            movq %rdi, (%rsi)    直接把指针赋给*dest
    
  5. up->t2.a[up->t1.u], 这个实际上是先取到t2.a的地址, 然后用指针加上t1.u的值, 取其中的值, 再把值复制给指针指向的地方,最后用指针从a数组中取数, 类型是int
            movq (%rdi), %rax   把t1.u的值装入%eax
            movl (%rdi, %rax,4), %eax     把t1.u的值乘以4,加上首地址的值, 得到实际的地址值, 在取值放入%eax中
            movl %eax, (%rsi)   把%eax的值赋值给%rsi间接引用.
    
  6. *up->t2.p, 这个实际上是先取到t2.p这个指针, 然后使用间接引用, 再赋给dest. t2.p的偏移应该是8. 而类型是char
                movl $0, %eax
                movq 8(%rdi), %rax   把偏移量+8的地址放入%rax
                movb (%rax), %al     取到char*指向的字节值, 放入%ax寄存器
                movb %al , (%rsi)
    

数据对齐

X86-64虽然不需要对齐也能正常工作, 但为了提高效率, Intel建议要对齐, 原则是K字节的基本对象的地址必须是K的倍数. 有些汇编代码里的声明比如.align 8表示其后分配地址的时候都以8位倍数分配. 而且引用这些对象的指针,也必须以同样的倍数对齐.

练习 3.44 确定每个字段的偏移量, 结构总大小 和 X86-64下的对齐要求

  1. struct P1 {int i; char c; int j; char d;}, 大小分别为4,1,4,1 但要保证int j也要对齐4位, 因此实际分配的字节是4,4,4,4, 结构大小是16个字节.
  2. struct P2 {int i; char c; char d; long j;}, 大小分别是4,1,1,8, 注意8要对齐到8的倍数, 所以 可能的分配是 4,2,2,8, 这样下一个结构依然可以对齐. 两个char可以挨着,之后有两字节的空白.
  3. struct P3 {short w[3]; char c[3]}, 第一个元素是3个2字节的长度, 之后是3个1字节的长度, 注意 2的要对齐到2字节, 很显然在6个分配之后, 还有3个字节,一共9字节, 所以末尾要有一个空白字节, 结构实际长度为10字节, 这样就可以保证short以2对齐.
  4. struct P4 {short w[5]; char *c[3]}, 先是10个字节长, 然后是24个字节长的指针数组. 由于指针要8字节对齐, 之前的10字节后边要加上6个字节的空白才行, 则总长度是40字节.
  5. struct P5 {struct P3 a[2]; struct P2 t}, P3的单个长度是10, P3 a[2]长20, 而P2的长度是16, 最长对齐到8, 所以有4字节的空白, 则总长度是 20+4+16 = 40 , 这样总长度和其中的索引都是对齐到8的倍数.

练习 3.45 优化组合

struct {
    char *a;    8
    short b;    2
    double c;   8
    char d;     1
    float e;    4
    char f;     1
    long g;     8
    int h;      4
} rec
假设起始地址是xd:
  1. a的偏移量为0, 没什么问题
  2. b的偏移量是8, 跟在a后边,没有什么问题, 对齐到2了也对齐到8了
  3. c的偏移量就不能直接是10了, 否则xd+10不是8的倍数, 所以 b后边要跟6个字节的空白, 偏移量为 xd+16,就可以是8的倍数了
  4. d的偏移量跟在c之后,应该是xd+24
  5. e的偏移量很显然,也不能是xd+25, 否则不是4的倍数, 因此要补到 xd+28, 即d后边有3个空白
  6. f又是一个char , 偏移量是xd+32
  7. 到了g, 不能是xd+33, 必须补到8的倍数, 所以有7个字节的空白. 偏移量是 xd + 40
  8. 最后的h 偏移量是 xd+48, 也没有问题, 是4的倍数.
这个结构现在一共长52个字节, 但是由于要保证xd是其中最大的长度8的倍数(超过8就算8), 所以后边要补4个字节空白, 总长度实际是56字节. 其实想想也能知道,如果所有元素都是1,2,4,8这种次序, 肯定是集中排布小的字节, 再塞大的字节划算. 重新排布一下, 得到如下顺序:
struct {
    char d;     1
    char f;     1
    short b;    2
    float e;    4
    int h;      4
    char *a;    8
    double c;   8
    long g;     8
}
这样的顺序, 此时来看一下偏移量:
  1. d的偏移量是xd+0
  2. f的偏移量是xd+1,和1字节对齐,问题不大
  3. b的偏移量是xd+2,和2字节对齐
  4. e的偏移量是xd+4,和4字节对齐
  5. int的偏移量是xd+8, 也和4字节对齐
  6. a的偏移量如果不补空白,就是12, 不行,要补4字节空白, 为xd+16
  7. c就是xd+24, 没问题
  8. g是xd+32
最后来看看总的长度, 目前只补过4字节空白, 结构总长度是1+1+2+4+4+4+8+8+8 = 40字节, 正好也是8的倍数. 所以优化之后, 实际使用40个字节就能排布下原来56个字节的结构. 后来看了答案发现其实应该先排布大的,这样无需补空白就能先排满, 这里只是运气好也排到40字节. 现在就把C语言里很大一块东西看完了. 可以看到, 对于复杂的数据结构,底层一般都是依靠指针运算来进行的. 所以后边要看的就是指针的操作, 以及什么叫做缓冲区溢出.
LICENSED UNDER CC BY-NC-SA 4.0
Comment