练习17：堆和栈的内存分配

在这个练习中，你会在难度上做一个大的跳跃，并且创建出用于管理数据库的完整的小型系统。这个数据库并不实用也存储不了太多东西，然而它展示了大多数到目前为止你学到的东西。它也以更加正规的方法介绍了内存分配，以及带领你熟悉文件处理。我们使用了一些文件IO函数，但是我并不想过多解释它们，你可以先试着自己理解。

像通常一样，输入下面整个程序，并且使之正常工作，之后我们会进行讨论：

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>

#define MAX_DATA 512
#define MAX_ROWS 100

struct Address {
    int id;
    int set;
    char name[MAX_DATA];
    char email[MAX_DATA];
};

struct Database {
    struct Address rows[MAX_ROWS];
};

struct Connection {
    FILE *file;
    struct Database *db;
};

void die(const char *message)
{
    if(errno) {
        perror(message);
    } else {
        printf("ERROR: %s\n", message);
    }

    exit(1);
}

void Address_print(struct Address *addr)
{
    printf("%d %s %s\n",
            addr->id, addr->name, addr->email);
}

void Database_load(struct Connection *conn)
{
    int rc = fread(conn->db, sizeof(struct Database), 1, conn->file);
    if(rc != 1) die("Failed to load database.");
}

struct Connection *Database_open(const char *filename, char mode)
{
    struct Connection *conn = malloc(sizeof(struct Connection));
    if(!conn) die("Memory error");

    conn->db = malloc(sizeof(struct Database));
    if(!conn->db) die("Memory error");

    if(mode == 'c') {
        conn->file = fopen(filename, "w");
    } else {
        conn->file = fopen(filename, "r+");

        if(conn->file) {
            Database_load(conn);
        }
    }

    if(!conn->file) die("Failed to open the file");

    return conn;
}

void Database_close(struct Connection *conn)
{
    if(conn) {
        if(conn->file) fclose(conn->file);
        if(conn->db) free(conn->db);
        free(conn);
    }
}

void Database_write(struct Connection *conn)
{
    rewind(conn->file);

    int rc = fwrite(conn->db, sizeof(struct Database), 1, conn->file);
    if(rc != 1) die("Failed to write database.");

    rc = fflush(conn->file);
    if(rc == -1) die("Cannot flush database.");
}

void Database_create(struct Connection *conn)
{
    int i = 0;

    for(i = 0; i < MAX_ROWS; i++) {
        // make a prototype to initialize it
        struct Address addr = {.id = i, .set = 0};
        // then just assign it
        conn->db->rows[i] = addr;
    }
}

void Database_set(struct Connection *conn, int id, const char *name, const char *email)
{
    struct Address *addr = &conn->db->rows[id];
    if(addr->set) die("Already set, delete it first");

    addr->set = 1;
    // WARNING: bug, read the "How To Break It" and fix this
    char *res = strncpy(addr->name, name, MAX_DATA);
    // demonstrate the strncpy bug
    if(!res) die("Name copy failed");

    res = strncpy(addr->email, email, MAX_DATA);
    if(!res) die("Email copy failed");
}

void Database_get(struct Connection *conn, int id)
{
    struct Address *addr = &conn->db->rows[id];

    if(addr->set) {
        Address_print(addr);
    } else {
        die("ID is not set");
    }
}

void Database_delete(struct Connection *conn, int id)
{
    struct Address addr = {.id = id, .set = 0};
    conn->db->rows[id] = addr;
}

void Database_list(struct Connection *conn)
{
    int i = 0;
    struct Database *db = conn->db;

    for(i = 0; i < MAX_ROWS; i++) {
        struct Address *cur = &db->rows[i];

        if(cur->set) {
            Address_print(cur);
        }
    }
}

int main(int argc, char *argv[])
{
    if(argc < 3) die("USAGE: ex17 <dbfile> <action> [action params]");

    char *filename = argv[1];
    char action = argv[2][0];
    struct Connection *conn = Database_open(filename, action);
    int id = 0;

    if(argc > 3) id = atoi(argv[3]);
    if(id >= MAX_ROWS) die("There's not that many records.");

    switch(action) {
        case 'c':
            Database_create(conn);
            Database_write(conn);
            break;

        case 'g':
            if(argc != 4) die("Need an id to get");

            Database_get(conn, id);
            break;

        case 's':
            if(argc != 6) die("Need id, name, email to set");

            Database_set(conn, id, argv[4], argv[5]);
            Database_write(conn);
            break;

        case 'd':
            if(argc != 4) die("Need id to delete");

            Database_delete(conn, id);
            Database_write(conn);
            break;

        case 'l':
            Database_list(conn);
            break;
        default:
            die("Invalid action, only: c=create, g=get, s=set, d=del, l=list");
    }

    Database_close(conn);

    return 0;
}

在这个程序中我使用了一系列的结构来创建用于地址薄的小型数据库。其中，我是用了一些你从来没见过的东西，所以你应该逐行浏览这段代码，解释每一行做了什么，并且查询你不认识的任何函数。下面是你需要注意的几个关键部分：

#define 常量

我使用了“C预处理器”的另外一部分，来创建MAX_DATA和MAX_ROWS的设置常量。我之后会更多地讲解预处理器的功能，不过这是一个创建可靠的常量的简易方法。除此之外还有另一种方法，但是在特定场景下并不适用。

定长结构体

Address结构体接着使用这些常量来创建数据，这些数据是定长的，它们并不高效，但是便于存储和读取。Database结构体也是定长的，因为它有一个定长的Address结构体数组。这样你就可以稍后把整个数据一步写到磁盘。

出现错误时终止的die函数

在像这样的小型程序中，你可以编写一个单个函数在出现错误时杀掉程序。我把它叫做die。而且在任何失败的函数调用，或错误输出之后，它会调用exit带着错误退出程序。

用于错误报告的 errno和perror

当函数返回了一个错误时，它通常设置一个叫做errno的“外部”变量，来描述发生了什么错误。它们只是数字，所以你可以使用perror来“打印出错误信息”。

文件函数

我使用了一些新的函数，比如fopen，fread，fclose，和rewind来处理文件。这些函数中每个都作用于FILE结构体上，就像你的结构体似的，但是它由C标准库定义。

嵌套结构体指针

你应该学习这里的嵌套结构器和获取数组元素地址的用法，它读作“读取db中的conn中的rows的第i个元素，并返回地址（&）”。

译者注：这里有个更简便的写法是db->conn->row + i。

结构体原型的复制

它在Database_delete中体现得最清楚，你可以看到我是用了临时的局部Address变量，初始化了它的id和set字段，接着通过把它赋值给rows数组中的元素，简单地复制到数组中。这个小技巧确保了所有除了set和id的字段都初始化为0，而且很容易编写。顺便说一句，你不应该在这种数组复制操作中使用memcpy。现代C语言中你可以只是将一个赋值给另一个，它会自动帮你处理复制。

处理复杂参数

我执行了一些更复杂的参数解析，但是这不是处理它们的最好方法。在这本书的后面我们将会了解一些用于解析的更好方法。

将字符串转换为整数

我使用了atoi函数在命令行中接受作为id的字符串并把它转换为int id变量。去查询这个函数以及相似的函数。

在堆上分配大块数据

这个程序的要点就是在我创建Database的时候，我使用了malloc来向OS请求一块大容量的内存。稍后我会讲得更细致一些。

NULL就是0，所以可转成布尔值

在许多检查中，我简单地通过if(!ptr) die("fail!")检测了一个指针是不是NULL。这是有效的，因为NULL会被计算成假。在一些少见的系统中，NULL会储存在计算机中，并且表示为一些不是0的东西。但在C标准中，你可以把它当成0来编写代码。到目前为止，当我说“NULL就是0”的时候，我都是对一些迂腐的人说的。

你会看到什么

你应该为此花费大量时间，知道你可以测试它能正常工作了。并且你应当用Valgrind来确保你在所有地方都正确使用内存。下面是我的测试记录，并且随后使用了Valgrind来检查操作：

$ make ex17
cc -Wall -g    ex17.c   -o ex17
$ ./ex17 db.dat c
$ ./ex17 db.dat s 1 zed zed@zedshaw.com
$ ./ex17 db.dat s 2 frank frank@zedshaw.com
$ ./ex17 db.dat s 3 joe joe@zedshaw.com
$
$ ./ex17 db.dat l
1 zed zed@zedshaw.com
2 frank frank@zedshaw.com
3 joe joe@zedshaw.com
$ ./ex17 db.dat d 3
$ ./ex17 db.dat l
1 zed zed@zedshaw.com
2 frank frank@zedshaw.com
$ ./ex17 db.dat g 2
2 frank frank@zedshaw.com
$
$ valgrind --leak-check=yes ./ex17 db.dat g 2
# cut valgrind output...
$

Valgrind实际的输出没有显式，因为你应该能够发现它。

注

Vagrind可以报告出你泄露的小块内存，但是它有时会过度报告OSX内部的API。如果你发现它显示了不属于你代码中的泄露，可以忽略它们。

堆和栈的内存分配

对于现在你们这些年轻人来说，编程简直太容易了。如果你玩玩Ruby或者Python的话，只要创建对象或变量就好了，不用管它们存放在哪里。你并不关心它们是否存放在栈上或堆上。你的编程语言甚至完全不会把变量放在栈上，它们都在堆上，并且你也不知道是否是这样。

然而C完全不一样，因为它使用了CPU真实的机制来完成工作，这涉及到RAM中的一块叫做栈的区域，以及另外一块叫做堆的区域。它们的差异取决于取得储存空间的位置。

堆更容易解释，因为它就是你电脑中的剩余内存，你可以通过malloc访问它来获取更多内存，OS会使用内部函数为你注册一块内存区域，并且返回指向它的指针。当你使用完这片区域时，你应该使用free把它交还给OS，使之能被其它程序复用。如果你不这样做就会导致程序“泄露”内存，但是Valgrind会帮你监测这些内存泄露。

栈是一个特殊的内存区域，它储存了每个函数的创建的临时变量，它们对于该函数为局部变量。它的工作机制是，函数的每个函数都会“压入”栈中，并且可在函数内部使用。它是一个真正的栈数据结构，所以是后进先出的。这对于main中所有类似char section和int id的局部变量也是相同的。使用栈的优点是，当函数退出时C编译器会从栈中“弹出”所有变量来清理。这非常简单，也防止了栈上变量的内存泄露。

理清内存的最简单的方式是遵守这条原则：如果你的变量并不是从malloc中获取的，也不是从一个从malloc获取的函数中获取的，那么它在栈上。

下面是三个值得关注的关于栈和堆的主要问题：

• 如果你从malloc获取了一块内存，并且把指针放在了栈上，那么当函数退出时，指针会被弹出而丢失。
• 如果你在栈上存放了大量数据（比如大结构体和数组），那么会产生“栈溢出”并且程序会中止。这种情况下应该通过malloc放在堆上。
• 如果你获取了指向栈上变量的指针，并且将它用于传参或从函数返回，接收它的函数会产生“段错误”。因为实际的数据被弹出而消失，指针也会指向被释放的内存。

这就是我在程序中使用Database_open来分配内存或退出的原因，相应的Database_close用于释放内存。如果你创建了一个“创建”函数，它创建了一些东西，那么一个“销毁”函数可以安全地清理这些东西。这样会更容易理清内存。

最后，当一个程序退出时，OS会为你清理所有的资源，但是有时不会立即执行。一个惯用法（也是本次练习中用到的）是立即终止并且让OS清理错误。

如何使它崩溃

这个程序有很多可以使之崩溃的地方，尝试下面这些东西，同时也想出自己的办法。

• 最经典的方法是移除一些安全检查，你就可以传入任意数据。例如，第160行的检查防止你传入任何记录序号。
• 你也可以尝试弄乱数据文件。使用任何编辑器打开它并且随机修改几个字节并关闭。
• 你也可以寻找在运行中向程序传递非法参数的办法。例如将文件参数放到动作后面，就会创建一个以动作命名的文件，并且按照文件名的第一个字符执行动作。
• 这个程序中有个bug，因为strncpy有设计缺陷。查询strncpy的相关资料，然后试着弄清楚如果name或者address超过512个字节会发生什么。可以通过简单把最后一个字符设置成'\0'来修复它，你应该无论如何都这样做（这也是函数原本应该做的）。
• 在附加题中我会让你传递参数来创建任意大小的数据库。在你造成程序退出或malloc的内存不足之前，尝试找出最大的数据库尺寸是多少。

附加题

• die函数需要接收conn变量作为参数，以便执行清理并关闭它。
• 修改代码，使其接收参数作为MAX_DATA和MAX_ROWS，将它们储存在Database结构体中，并且将它们写到文件。这样就可以创建任意大小的数据库。
• 向数据库添加更多操作，比如find。
• 查询C如何打包结构体，并且试着弄清楚为什么你的文件是相应的大小。看看你是否可以计算出结构体添加一些字段之后的新大小。
• 向Address添加一些字段，使它们可被搜索。
• 编写一个shell脚本来通过以正确顺序运行命令执行自动化测试。提示：在bash顶端使用使用set -e，使之在任何命令发生错误时退出。

  译者注：使用Python编写多行脚本或许更方便一些。

• 尝试重构程序，使用单一的全局变量来储存数据库连接。这个新版本和旧版本比起来如何？
• 搜索“栈数据结构”，并且在你最喜欢的语言中实现它，然后尝试在C中实现。