【UCB CS61C】Lecture 4 - C Memory Management Usage

本文章系计算机体系结构课程 UCB CS61C: Great Ideas in Computer Architecture 的学习笔记。

C 的内存布局（Memory Layout）

• 程序的地址空间（address space）包括 4 个区域：
• • 栈（stack）：向低地址扩展，包含局部变量和函数帧（function frame，存储函数调用相关信息）
• • 堆（heap）：向高地址扩展，可以动态调整空间大小，通过 malloc() 等函数申请内存，通过 free() 等函数释放，通过指针的方式访问
• • 静态数据（static data）：主要存放全局变量和静态变量，内存在整个程序运行生命周期中保持恒定
• • 代码（code）：程序载入和启动的区域，程序运行期间不会改变
• 操作系统利用虚拟内存技术¹阻止堆、栈之间的访问，确保数据不被破坏。
• 在函数外部声明的变量将会存储至静态数据区，而在函数内部声明的变量将会存储至栈中。
• • 当程序运行时，main() 函数会在调用栈（callback stack）中创建一个函数帧。
• • main() 函数返回（return）时会释放所有栈中数据，使得栈的空间布局复原。
• 动态分配的内存位于堆中。

栈（Stack）

• 栈由栈帧（stack frame）组成，每一个栈帧包含了一个函数或过程（procedure）的所有局部变量，是一个连续的内存块。
• 一个栈帧包含：
• • 调用函数的位置
• • 函数参数
• • 局部变量的空间
• 栈指针（stack pointer，SP）指向最低与当前地址的栈内位置。
• 随着函数不断被调用，栈帧进栈，栈指针从上往下移动；当函数停止调用时，栈指针会从下往上移动，直到栈指针指向栈底，复原到函数帧创建前的布局，类似于栈帧出栈。在这个过程中，只是栈指针在移动，栈帧里面的数据并没有被清空。
• 栈遵循后进先出（LIFO，last in first out）的原则，递归地弹出每一个栈帧。
• ⚠️ 不要从函数返回局部变量的指针，它可能会指向任意数据。编译器会以 warnings 警告，请不要忽略！

静态数据（Static Data）

• 静态数据是存放静态变量的区域：
• • 存储的数据不会受到函数调用的影响。
• • 字符串字面量（string literals）属于静态数据，通过类似 char * str = "hi"; 来声明，而 char str[] = "hi"; 这样的声明会存放到栈中。
• 技术上来说，静态数据可以分为两个部分：只读段和读写段，以便实际上修改某些值。

代码（Code）

• 实质上是程序代码的副本，无法更改且一般只读。

寻址（Addressing）

地址（Address）

• 一个地址的大小（指针的大小）以字节为单位，取决于架构。例如，对于 32 位操作系统，共有 2³² 个可能的地址。
• 按字节寻址（byte-addressed）：每个地址指向一个唯一的字节。
• 按字寻址（word-addressed）：每个地址指向一个唯一的单词。

字节序（Endianness）

• 大端序（Big Endian）存储按升序内存地址排列的降序数值显著性²（numerical significance，数值结果的精确性和可靠性），即数据的字节由高到低排序，对应着存放的内存地址由低到高排序。

• 小端序（Little Endian）存储按降序内存地址排列的升序数值显著性，即数据的字节由低到高排序，对应着存放的内存地址由高到低排序。
• 字节序是指数据在内存中的存放顺序而不是数字表示，仅适用于占用多个字节的值。
• 寄存器（register）本身并没有字节序的概念，它是CPU内部的高速存储单元，用于暂时存放指令、数据和地址。它们通常是固定大小的、以整个数据单元（32 位或 64 位），而不是以字节为单位，也不关心数据的字节序。
• 一个单字节的数据（例如任意一个字符）、数组和指针既有大端序又有小端序。

动态内存分配

堆

• 我们有时候需要在编译时间内持久稳定、同时未知大小的内存用来存放输入文件、用户交互等数据，但是由于栈帧不具有持久性存储，函数返回时会清除内存，从而数据被弃用或者覆盖，因此栈并不能解决这一问题。
• 动态内存分配通过堆（heap）来实现，比栈更持久，它将数据保留在函数调用之外。
• 堆和栈分别从内存的两端开始分配，逐渐向中间扩展；堆通常从低地址向高地址增长。

sizeof()

• 返回一个以字符大小为单位的变量或类型所占内存大小的整数。
• sizeof(char) 的结果始终为 1！
• 一般情况下，字符所占用内存的大小为 1 字节，实际上 sizeof 返回变量或类型大小的字节数。
• 无法通过直接对整个数组使用 sizeof() 运算符来获取该数组的长度，
• 对于一个数组 a ，若满足在同一函数中定义且在栈上分配，sizeof(a) 将返回填充数组所需的字节数，那么我们可以通过 sizeof(a) / sizeof(array_typename) 来求出数组的长度；否则，将返回对应类型的指针大小。

内存分配的实现

• 申请内存的3 个函数：malloc() 、calloc() 和 realloc() 。

malloc(n)

• 接受一个所需连续内存块字节大小的参数 n 并分配（内存块不一定相邻），这一内存实际上尚未初始化，包含内存垃圾，无法保证实际存储在其中的内容。
• 返回一个指向被分配内存块首端的指针，分配失败时返回 NULL ，因此使用时需要随时检查内存分配是否成功。
• 通常用于数组或结构体，同时使用 sizeof() 以及强制转换是一个好的实践，sizeof() 可以使得代码适用于多个架构，而 malloc() 返回 void * 类型，强制转换将会确保指针类型的正确性。例如，我们需要为一个含有 n 个元素的 int 数组分配内存：

int *p = (int *) malloc(n * sizeof(int));

free(p)

• 接受一个指向被分配内存块首端的指针的参数 p，释放整个内存块。
• p 必须是 malloc() 等内存申请函数的返回值，否则会抛出系统异常（System Exception）。
• 不能对已释放的内存块使用 free() ，会造成重复释放错误（double free error），导致系统安全漏洞；对于非堆的内存使用也是不被允许的未定义行为；建议使用独立的指针，避免使用指针运算，以确保原始地址不丢失。

calloc()

void *calloc(size_t nmemb, size_t size)

• 接受两个参数，nmemb 是成员或元素的数量，size 是每个成员或元素的大小。
• 类似于 malloc() ，但是 calloc() 将数组的每个元素初始化为 0。

int *p = (int *) calloc(5, sizeof(int));

realloc()

void *realloc(void *ptr, size_t size)

• 接受一个已经存在的数据的指针的参数，重新分配该内存块的大小，会根据实际需求调整内存大小。
• 返回可能指向新位置的指针，若重新分配失败，则返回原地址。

简单示例

#include <stdlib.h>typedef struct {int x;int y;
} point;point *rect;if (!(rect = (point *) malloc(2 * sizeof(point)) {  //检查是否返回 NULLprintf("Out of memory!\n");exit(1);
}free(rect);

内存有关的错误

• 段错误（segmentation fault）：正在运行的 Unix 程序试图访问未分配给它的内存，并因此终止，通常还会生成核心转储（core dump，提供了程序崩溃时的完整状态）。
• 总线错误（bus error）：在执行机器语言指令时发生的一个致命失败，由处理器在其总线上检测到异常情况引起。
• • 无效的地址对齐（在奇数地址访问多字节数）、访问一个不对应任何设备的物理地址，或其他特定于设备的硬件错误。

常见内存问题

• 使用未初始化的值

void foo(int *p) {int j;*p = j;   // j 未初始化（垃圾），被拷贝至 *p
}void bar() {int i = 10;foo(&i);printf("i = %d\n", i);   //使用包含垃圾的 i
}

• 使用未拥有的内存：
• • 使用 NULL 或垃圾数据作为指针

typedef struct node {struct node* next;int val;
} Node;int findLastNodeValue(Node* head) {while (head->next != NULL)  //如果 head 为空，则会弹出段错误而不给出任何部分的提示head = head->next;return head->val;
}

• • 试图访问已经被释放的栈或堆分配的变量

char *append(const char* s1, const char *s2) {const int MAXSIZE = 128;char result[MAXSIZE];   //函数内部定义、在栈上分配的局部数组int i = 0, j = 0;for (; i < MAXSIZE - 1 && j < strlen(s1); i++, j++)result[i] = s1[j];for (; i < MAXSIZE - 1 && j < strlen(s2); i++, j++)result[i] = s2[j];return result;   //函数返回后，指向栈的指针不再有效
}

返回指向数组 result 的指针是不安全的，指向的内存不再有效，会导致未定义行为。要解决这个问题，可以使用动态内存分配来确保返回的指针指向的是有效的内存：

char *result = malloc(MAXSIZE);
if (result == NULL)return NULL;     //检查内存分配失败的情况

• • 对于栈或堆的数组超出范围的引用

void StringManipulate() {const char *name = "Safety Critical";char *str = malloc(sizeof(char) * 10);strncpy(str, name, 10);str[10] = '\0';   //写入超出数组边界的部分printf("%s\n", str);  //读取超出数组边界的部分
}

• 释放无效的内存

typedef struct {char *name;int age;
} Profile;Profile *person = (Profile *) malloc(sizeof(Profile));
char *name = getName();
person->name = malloc(sizeof(char) * strlen(name));  //没有为空终止符分配空间，应为 (strlen(name) + 1)
strcpy(person->name, name);
//一系列没有 bug 的操作
free(person);
free(person->name);  //访问已经被释放的内存地址，这一步应当与上一步调换顺序

void FreeMemX () {int fnh = 0;free(&fnh);   //试图释放一个栈变量，这是不正确的，我们应该释放 malloc() 动态分配的内存
}void FreeMemY() {int *fum = malloc(4 * sizeof(int));free(fum + 1);   //释放内存块中间的部分而不是首端，这是不正确的free(fum);free(fum);       //重复释放内存
}

• 内存泄漏

int *pi;
void foo () {pi = (int *) malloc(8 * sizeof(int));    //已经将旧指针覆盖了，无法再释放原来声明 int 指针的 4 * sizeof(int) 字节的内存free(pi);
}void main() {pi = (int *) malloc(4 * sizeof(int));foo();   // foo() 造成内存泄漏
}

• • 经验法则（Rule of Thumb）：malloc() 多于 free() 意味着内存泄漏。
• • 更改指针时，应确保提前复制一个副本进行操作，以便后续进行内存管理。例如，直接对动态分配的指针 plk 操作 plk++ 会丧失对原有内存的访问权，从而导致内存泄漏。
• • 我们可以使用调试工具 $Valgrind$ 来实时查找内存错误；$Valgrind$ 跟踪每个取消引用和内存分配的行为，会降低程序的运行速度。请注意，这并不能保证找到所有的内存错误，因此我们必须规范自身的代码写作习惯。
• 缓冲区溢出（buffer overflow）：程序试图将更多的数据写入缓冲区（如数组或内存块）时，超出其实际分配的内存大小，会导致巨大的安全漏洞，常被利用于越狱 iPhone 等黑客手段。

char buffer[1024];  //预留了 1 kb 字符的空间int foo (char *str) {strcpy(buffer, str);  //如果我们输入超过 1 kb 的字符，将会出现缓冲区溢出的问题
}

C 字符串标准库的修订

对此，C 对 #include <string.h> 的库函数进行修订来解决一些安全问题：

• int strnlen(char *string, size_t n); - 类似于 strlen() 函数，但接受一个参数 n ，用于限制计算的最大字符数，会在达到指定的最大长度时停止计数，从而避免读取未定义的内存区域。
• int strncmp(char *str1, char *str2, size_t n); - 类似于 strcmp() 函数，用于比较部分字符串，适用于需要限制比较长度或不确定字符串长度的情况，常用于处理字符串输入或避免某些类型的错误。
• int strncpy(char *dst, char *src, size_t n); - 将字符串 src 的前 n 个字节的数据复制到 dst 的内存中。

因此，我们可以使用一种更安全的方式复制数组，从而避免缓冲区溢出等重大安全漏洞：

#define ARR_LEN 1024;
char buffer[ARR_LEN];int foo (char *str) {strncpy(buffer, str, ARR_LEN);
}

创建一个简单的 C 链表

创建链表中节点的结构体：

struct Node {char *value;struct Node *next;
} node;

为链表编写 addNode() 节点添加函数（从首端添加）：

node *addNode (char *s, node *list) {node *new = (node *) malloc(sizeof(NodeStruct));new->value = (char *) malloc(strlen(s) + 1);    //注意空终止符strcpy(new->value, s);new->next = list;return new;
}

删除、释放第一个节点的函数 deleteNode() ：

node  *deleteNode (node *list) {node *temp = list->next;free(list);return temp;
}

---

1. 该技术使得应用程序认为其拥有连续的可用的内存（通常是一个连续完整的地址空间）——而实际上——通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。 ↩︎

2. 在计算机科学和数值计算领域，数值显著性指的是数值结果的精确性和可靠性。它涉及到如何处理和表示数字，以确保计算结果在数值上是稳定和准确的。数值显著性通常与精度（Precision，数值表示中有效数字的位数）、舍入误差（Rounding Error，由于有限精度产生的实际数值和计算机表示的数值之间可能存在的差异）、截断误差（Truncation Error，由于近似或截断某些数值或计算过程而引入的误差）、数值稳定性（Numerical Stability，算法在输入数据的微小变化下，输出结果的变化程度）和条件数（Condition Number，衡量函数对输入误差的敏感度的指标，一个函数的条件数越大，输入数据的微小变化可能导致输出结果的较大变化，表明该函数在数值上是不稳定的）这些方面有关。 ↩︎