课程主页：https://courses.cs.washington.edu/courses/cse351/16sp/

课程资料：

实验部分：https://github.com/vuquangtrong/HW-SW_Interface_Course

实验说明：https://courses.cs.washington.edu/courses/cse351/13sp/lab-0.html

课件：http://academictorrents.com/details/b63a566df824b39740eb9754e4fe4c0140306f4b

课程视频：https://www.bilibili.com/video/BV1Zt411s7Gg?from=search&seid=8781593976070799647

这次回顾第六部分，这部分介绍了数组和结构。

第6节：数组和结构

数组分配和内存访问

数组分配

基本原则

  • T A [L];
  • 上述声明表示数据类型为T，长度为L的数组
  • 内存中是L*sizeof(T)个字节的连续分配区域

数组存取

基本原则

  • T A [L];
  • 上述声明表示数据类型为T，长度为L的数组
  • A可以被视为指向数组第一个元素的指针，类型为$\text{T}^{\star}$

多维或嵌套数组

多维（嵌套）数组
  • 声明
    • T A [R] [C];
    • 数据类型为T的2D数组
    • R行，C列
    • 类型T元素需要K个字节
  • 数组大小
    • $\text{R} \times \text{C} \times \text{K}$字节
  • 内存安排
    • 按行排列

嵌套数组例子
#define PCOUNT 4
zip_dig pgh[PCOUNT] = 
  {{1, 5, 2, 0, 6},
   {1, 5, 2, 1, 3 },
   {1, 5, 2, 1, 7 },
   {1, 5, 2, 2, 1 }};

内存中的结果

  • “zip_dig pgh [4]”等价于“int pgh [4] [5]”
    • 变量pgh：4个元素的数组，内存中连续分配
    • 每个元素都是5个int的数组，内存中连续分配
  • 内存中所有元素都是按行排列
嵌套数组读取
嵌套数组行的读取
  • 行向量
    • A[i]是C个元素的数组
    • 类型T的每个元素需要K个字节
    • 起始地址为$\text{A} + \text{i} \times(\text{C} \times \text{K})$

例如$\text{int A[R][C]}$

考虑如下代码

int *get_pgh_zip(int index)
{
  return pgh[index];
}
# %rdi = index
leaq (%rdi,%rdi,4),%rax	# 5 * index
leaq pgh(,%rax,4),%rax	# pgh + (20 * index)
  • 行向量
    • pgh[index]是5个整数的数组
    • 起始地址$\text{pgh + 20} \times \text{index}$
  • 机器码
    • 计算并返回地址
    • 计算方式为$\text{pgh} + 4 \times (\text{index} + 4 \times \text{index})$
嵌套数组元素访问
  • 数组元素
    • A[i][j]是类型T的元素，需要K个字节
    • 地址为$\text{A + i} \times \text{(C} \times \text{K)} + \text{j} \times \text{K} = \text{A} + (\text{i} \times \text{C} + \text{j})\times \text{K}$

例如$\text{int A[R][C]}$

考虑如下代码

int get_pgh_digit
  (int index, int dig)
{
  return pgh[index][dig];
}
leaq	(%rdi,%rdi,4), %rax	# 5*index
addl	%rax, %rsi	# 5*index+dig
movl	pgh(,%rsi,4), %eax	# M[pgh + 4*(5*index+dig)]
  • 数组元素
    • pgh[index] [dig]是int
    • 地址：$\text{pgh + 20} \times \text{index + 4} \times \text{dig = pgh + 4} \times \text{(5} \times\text{index + dig)}$

多级数组

多级数组例子
zip_dig cmu = { 1, 5, 2, 1, 3 };
zip_dig mit = { 0, 2, 1, 3, 9 };
zip_dig ucb = { 9, 4, 7, 2, 0 };

#define UCOUNT 3
int *univ[UCOUNT] = {mit, cmu, ucb};
  • 变量univ表示由3个元素组成的数组
  • 每个元素都是一个指针
    • 8字节
  • 每个指针都指向int数组

多级数组读取
int get_univ_digit
  (size_t index, size_t digit)
{
  return univ[index][digit];
}
salq    $2, %rsi            # 4*digit
addq    univ(,%rdi,8), %rsi # p = univ[index] + 4*digit
movl    (%rsi), %eax        # return *p
ret
  • 计算方式
    • 元素访问$\text{Mem[Mem[univ + 8} \times \text{index] + 4} \times \text{digit]}$
    • 必须做两次内存读取
      • 首先获取指向行数组的指针
      • 然后访问数组中的元素

内存中的结构

结构表示
struct rec {
    int a[4];
    size_t i;
    struct rec *next;
};

  • 结构表示为内存块
    • 足够容纳所有的字段
  • 根据声明的顺序安排字段
    • 即使另一个排序可以产生更紧凑的表示
  • 编译器确定整体大小+字段位置
    • 机器级程序不了解源代码中的结构

结构与对齐

struct S1 {
  char c;
  int i[2];
  double v;
} *p;
  • 没有对齐的数据

  • 对齐的数据
    • 原始数据类型需要K个字节
    • 地址必须是K的倍数

对齐原则
  • 对齐数据
    • 原始数据类型需要K个字节
    • 地址必须是K的倍数
    • 在某些机器上是必需的； x86-64上被建议使用
  • 对齐数据的动机
    • 通过（对齐的）4或8个字节的块访问内存（取决于系统）
    • 加载或存储跨越四字边界的数据效率低下
    • 当数据跨越2页时，虚拟内存会更复杂
  • 编译器
    • 在结构中插入间隙以确保正确对齐字段
对齐的特定情况（x86-64）
  • 1个字节：char，…
    • 地址无限制
  • 2个字节：short，…
    • 地址的最低1位必须为$0_2$
  • 4个字节：int，float等
    • 地址的最低2位必须为$00_2$
  • 8个字节：double，long，char *，…
    • 地址的最低3位必须为$000_2$
  • 16个字节：long double（Linux上的GCC）
    • 地址的最低4位必须为$0000_2$
节省空间

  • 将较大的数据放在前面

    struct S4 {
  char c;
  int i;
  char d;
} *p;
    struct S5 {
  int i;
  char c;
  char d;
} *p;

  • 有效位数($K=4$)

补充：缓冲溢出

内存布局

x86-64 Linux内存布局
  • 堆栈
    • 运行时的堆栈（限制为8MB）
    • 例如，局部变量
  • 堆
    • 根据需要动态分配
    • 调用malloc(), calloc(), new()时使用
  • 数据
    • 静态分配的数据
    • 例如，全局变量，静态变量，字符串常量
  • 文本/共享库
    • 可执行机器指令
    • 只读

例子

/* Echo Line */
void echo()
{
    char buf[4]; /* Way too small! */
    gets(buf);
    puts(buf);
}

void call_echo() {
	echo();
}
unix>./bufdemo-nsp
Type a string:012345678901234567890123
012345678901234567890123
unix>./bufdemo-nsp
Type a string:0123456789012345678901234
Segmentation Fault

反汇编的结果为如下：

echo:

00000000004006cf <echo>:
    4006cf: 48 83 ec 18 		sub $0x18,%rsp
    4006d3: 48 89 e7 			mov %rsp,%rdi
    4006d6: e8 a5 ff ff ff 		callq 400680 <gets>
    4006db: 48 89 e7 			mov %rsp,%rdi
    4006de: e8 3d fe ff ff 		callq 400520 <puts@plt>
    4006e3: 48 83 c4 18 		add $0x18,%rsp
    4006e7: c3 				    retq

call_echo:

4006e8: 48 83 ec 08 			sub $0x8,%rsp
    4006ec: b8 00 00 00 00 		 mov $0x0,%eax
    4006f1: e8 d9 ff ff ff 		 callq 4006cf <echo>
    4006f6: 48 83 c4 08 		 add $0x8,%rsp
    4006fa: c3 				    retq

在调用gets函数之前，栈的布局如下：

如果运行如下命令：

unix>./bufdemo-nsp
Type a string:012345678901234567890123
012345678901234567890123

那么布局如下：

如果运行如下命令：

unix>./bufdemo-nsp
Type a string:0123456789012345678901234
Segmentation Fault

那么布局如下：

如果运行如下命令：

unix>./bufdemo-nsp
Type a string:012345678901234567890123
012345678901234567890123

那么布局如下：

此时会返回到其他的位置，例如：

. . .
400600:	mov    %rsp,%rbp
400603:	mov    %rax,%rdx
400606:	shr    $0x3f,%rdx
40060a:	add    %rdx,%rax
40060d:	sar    %rax
400610:	jne    400614
400612:	pop    %rbp
400613:	retq

这样就会产生安全问题，例如代码注入攻击，缓冲区溢出错误可使远程计算机在受害计算机上执行任意代码。

如何处理缓存区溢出攻击

  • 避免溢出漏洞
  • 采用系统级保护

更详细的部分见：

https://doraemonzzz.com/2020/06/03/CMU%2015-213%20Intro%20to%20Computer%20Systems%20Lecture%209/

避免溢出漏洞
/* Echo Line */
void echo()
{
    char buf[4]; /* Way too small! */
    fgets(buf, 4, stdin);
    puts(buf);
}

例如在之前代码中限制输入字符的数量。

系统级保护

  • 堆栈随机偏移

    • 在程序开始时，在堆栈上分配随机数量的空间

    • 移位整个程序的堆栈地址

    • 使黑客很难预测插入代码的开始

    • 例如5次执行内存分配代码的结果

      local 0x7ffe4d3be87c 0x7fff75a4f9fc 0x7ffeadb7c80c 0x7ffeaea2fdac 0x7ffcd452017c

    • 程序每次执行时都会重新定位堆栈

  • 不可执行的代码段
    • 在传统的x86中，可以将内存区域标记为“只读”或“可写”
      • 可以执行任何可读的
    • X86-64添加了明确的“执行”权限
    • 堆栈标记为不可执行