C程序设计语言-第8章UNIX系统接口

C程序设计语言系列文章链接：

第8章 UNIX系统接口

UNIX操作系统通过一系列的系统调用提供服务，这些系统调用实际上是操作系统内的函数，它们可以被用户程序调用。本章将介绍如何在C语言程序中使用一些重要的系统调用。如果读者使用的是UNIX，本章将会对你有直接的帮助，这是因为，我们经常需要借助于系统调用以获得最高的效率，或者访问标准库中没有的某些功能。但是，即使读者是在其他操作系统上使用C语言，本章的例子也将会帮助你对C语言程序设计有更深入的了解。不同系统中的代码具有相似性，只是一些细节上有区别而已。因为ANSI C标准函数库是以UNIX系统为基础建立起来的，所以，学习本章中的程序还将有助于更好地理解标准库。

本章的内容包括3个主要部分：输入/输出、文件系统和存储分配。其中，前两部分的内容要求读者对UNIX系统的外部特性有一定的了解。

第7章介绍的输入/输出接口对任何操作系统都是一样的。在任何特定的系统中，标准库函数的实现必须通过宿主系统提供的功能来实现。接下来的几节将介绍UNIX系统中用于输入和输出的系统调用，并介绍如何通过它们实现标准库。

8.1 文件描述符

在UNIX操作系统中，所有的外围设备（包括键盘和显示器）都被看做是文件系统中的文件，因此，所有的输入/输出都要通过读文件或写文件完成。也就是说，通过一个单一的接口就可以处理外围设备和程序之间的所有通信。

通常情况下，在读或写文件之前，必须先将这个意图通知系统，该过程称为打开文件。如果是写一个文件，则可能需要先创建该文件，也可能需要丢弃该文件中原先已存在的内容。系统检查你的权力（该文件是否存在？是否有访问它的权限？），如果一切正常，操作系统将向程序返回一个小的非负整数，该整数称为文件描述符。任何时候对文件的输入/输出都是通过文件描述符标识文件，而不是通过文件名标识文件。（文件描述符类似于标准库中的文件指针或MS-DOS中的文件句柄。）系统负责维护已打开文件的所有信息，用户程序只能通过文件描述符引用文件。

因为大多数的输入/输出是通过键盘和显示器来实现的，为了方便起见，UNIX对此做了特别的安排。当命令解释程序（即“shell”）运行一个程序的时候，它将打开3个文件，对应的文件描述符分别为0、1、2，依次表示标准输入、标准输出和标准错误。如果程序从文件0中读，对1和2进行写，就可以进行输入/输出而不必关心打开文件的问题。

程序的使用者可通过<和>重定向程序的I/O：

prog <输入文件名 >输出文件名

这种情况下，shell把文件描述符0和1的默认赋值改变为指定的文件。通常，文件描述符2仍与显示器相关联，这样，出错信息会输出到显式器上。与管道相关的输入/输出也有类似的特性。在任何情况下，文件赋值的改变都不是由程序完成的，而是由shell完成的。

8.2 低级I/O————read和write

输入和输出是通过read和write系统调用实现的。在C语言程序中，可以通过函数read和write访问这两个系统调用。这两个函数中，第一个参数是文件描述符，第二个参数是程序中存放读或写的数据的字符数组，第三个参数是要传输的字节数。

1
2

int n_read = read(int fd, char *buf, int n);
int n_written = write(int fd, char *buf, int n);

每个调用返回实际传输的字节数。在读文件时，函数的返回值可能会小于请求的字节数。如果返回值为0，则表示已到达文件的结尾；如果返回值为-1，则表示发生了某种错误。在写文件时，返回值是实际写入的字节数。如果返回值与请求写入的字节数不相等，则说明发生了错误。

在一次调用中，读出或写入的数据的字节数可以为任意大小。最常用的值为1，即每次读出或写入1个字符（无缓冲），或是类似于1024或4096这样的与外围设备的物理块大小相应的值。用更大的值调用该函数可以获得更高的效率，因为系统调用的次数减少了。

结合以上的讨论，我们可以编写一个简单的程序，将输入复制到输出，这与第1章中的复制程序在功能上相同。程序可以将任意输入复制到任意输出，因为输入/输出可以重定向到任何文件或设备。

#include "syscalls.h"

main() {   /* 将输入复制到输出 */
    char buf[BUFSIZE];
    int n;

    while ((n = read(0, buf, BUFSIZE)) > 0)
        write(1, buf, n);
    return 0;
}

我们已经将系统调用的函数原型集中放在一个头文件syscalls.h中，因此，本章中的程序都将包含该头文件。不过，该文件的名字不是标准的。

参数BUFSIZE也已经在syscalls.h头文件中定义。对于所使用的操作系统来说，该值是一个较合适的数值。如果文件大小不是BUFSIZE的倍数，则对read的某次调用会返回一个较小的字节数，write再按这个字节数写，此后再调用read将返回0。

为了更好地掌握有关概念，下面来说明如何用read和write构造类似于getchar、putchar等的高级函数。例如，以下是getchar函数的一个版本，它通过每次从标准输入读入一个字符来实现无缓冲输入。

#include "syscalls.h"

/* getchar函数：无缓冲的单字符输入 */
int getchar(void) {
    char c;

    return (read(0, &c, 1) == 1) ? (unsigned char) c : EOF;
}

其中，c必须是一个char类型的变量，因为read函数需要一个字符指针类型的参数（&c）。在返回语句中将c转换为unsigned char类型可以消除符号扩展问题。

getchar的第二个版本一次读入一组字符，但每次只输出一个字符。

#include "syscalls.h"

/* getchar函数：简单的带缓冲区的版本 */
int getchar(void) {
    static char buf[BUFSIZE];
    static char *bufp = buf;
    static int n = 0;

    if (n == 0) {  /* 缓冲区为空 */
        n = read(0, buf, sizeof buf);
        bufp = buf;
    }
    return (--n >= 0) ? (unsigned char) *bufp++ : EOF;
}

如果要在包含头文件<stdio.h>的情况下编译这些版本的getchar函数，就有必要用#undef预处理指令取消名字getchar的宏定义，因为在头文件中，getchar是以宏方式实现的。

8.3 open、creat、close和unlink

除了默认的标准输入、标准输出和标准错误文件外，其他文件都必须在读或写之前显式地打开。系统调用open和creat用于实现该功能。

open和第7章讨论的fopen很相似，不同的是，前者返回一个文件描述符，它仅仅只是一个int类型的数值，而后者返回一个文件指针。如果发生错误，open将返回-1。

#include <fcntl.h>

int fd;
int open(char *name, int flags, int perms);

fd = open(name, flags, perms);

与fopen一样，参数name是一个包含文件名的字符串。第二个参数flags是一个int类型的值，它说明以何种方式打开文件，主要的几个值如下所示：

1
2
3

O_RDONLY     以只读方式打开文件
O_WRONLY     以只写方式打开文件
O_RDWR       以读写方式打开文件

在System V UNIX系统中，这些常量在头文件<fcntl.h>中定义，而在Berkeley(BSD)版本中则在<sys/file.h>中定义。

可以使用下列语句打开一个文件以执行读操作：

fd = open(name, O_RDONLY, 0);

在本章的讨论中，open的参数perms的值始终为0。

如果用open打开一个不存在的文件，则将导致错误。可以使用creat系统调用创建新文件或覆盖已有的旧文件，如下所示：

1
2
3

int creat(char *name, int perms);

fd = creat(name, perms);

如果creat成功地创建了文件，它将返回一个文件描述符，否则返回-1。如果此文件已存在，creat将把该文件的长度截断为0，从而丢弃原先已有的内容。使用creat创建一个已存在的文件不会导致错误。

如果要创建的文件不存在，则creat用参数perms指定的权限创建文件。在UNIX文件系统中，每个文件对应一个9比特的权限信息，它们分别控制文件的所有者、所有者组和其他成员对文件的读、写和执行访问。因此，通过一个3位的八进制数就可方便地说明不同的权限，例如，0755说明文件的所有者可以对它进行读、写和执行操作，而所有者组和其他成员只能进行读和执行操作。

下面通过一个简化的UNIX程序cp说明creat的用法。该程序将一个文件赋值到另一个文件。我们编写的这个版本仅仅只能复制一个文件，不允许用目录作为第二个参数，并且，目标文件的权限不是通过复制获得的，而是重新定义的。

#include <stdio.h>
#include <fcntl.h>
#include "syscalls.h"
#define PERMS  0666   /* 对于所有者、所有者组和其他成员均可填写 */

void error(char *, ...);

/* cp函数：将f1复制到f2 */
main(int argc, char *argv[]) {
    int f1, f2, n;
    char buf[BUFSIZE];

    if (argc != 3)
        error("Usage: cp from to");
    if ((f1 = open(argv[1], O_RDONLY, 0)) == -1)
        error("cp: can't open %s", argv[1]);
    if ((f2 = creat(argv[2], PERMS)) == -1)
        error("cp: can't create %s, mode %03o",
            argv[2], PERMS);
    while ((n = read(f1, buf, BUFSIZE)) > 0)
        if (write(f2, buf, n) != n)
            error("cp: write error on file %s", argv[2]);
    return 0;
}

该程序创建的输出文件具有固定的权限0666。利用8.6节中将要讨论的stat系统调用，可以获得一个已存在文件的模式，并将此模式赋值给它的副本。

注意，函数error类似于函数printf，在调用时可带变长参数表。下面通过error函数的实现说明如何使用printf函数家族的另一个成员vprintf。标准库函数vprintf函数与printf函数类似，所不同的是，它用一个参数取代了变长参数表，且此参数通过调用va_start宏进行初始化。同样，vfprintf和vsprintf函数分别与fprintf和sprintf函数类似。

#include <stdio.h>
#include <stdarg.h>

/* error函数：打印一个出错信息，然后终止 */
void error(char *fmt, ...) {
    va_list args;

    va_start(args, fmt);
    fprintf(stderr, "error: ");
    vfprintf(stderr, fmt, args);
    fprintf(stderr, "\n");
    va_end(args);
    exit(1);
}

一个程序同时打开的文件数是有限制的（通常为20）。相应地，如果一个程序需要同时处理许多文件，那么它必须重用文件描述符。函数close(int fd)用来断开文件描述符和已打开文件之间的连接，并释放此文件描述符，以供其他文件使用。close函数与标准库中的fclose函数相对应，但它不需要清洗（flush）缓冲区。如果程序通过exit函数退出或从主程序中返回，所有打开的文件将被关闭。

函数unlink(char*name)将文件name从文件系统中删除，它对应于标准库函数remove。

练习801 用read、write、open和close系统调用代替标准库中功能等价的函数，重写第7章的cat程序，并通过实验比较两个版本的相对执行速度。

8.4 随机访问————lseek

输入/输出通常是顺序进行的：每次调用read和write进行读写的位置紧跟在前一次操作的位置之后。但是，有时候需要以任意顺序访问文件，系统调用lseek可以在文件中任意移动位置而不实际读写任何数据：

long lseek(int fd, long offset, int origin);

将文件描述符为fd的文件的当前位置设置为offset，其中，offset是相对于origin指定的位置而言的。随后进行的读写操作将从此位置开始。origin的值可以为0、1或2，分别用于指定offset从文件开始、从当前位置或从文件结束处开始算起。例如，为了向一个文件的尾部添加内容（在UNIX shell程序中使用重定向符>>或在系统调用fopen中使用参数“a”），则在写操作之前必须使用下列系统调用找到文件的末尾：

lseek(fd, 0L, 2);

若要返回文件的开始处（即反绕），则可以使用下列调用：

lseek(fd, 0L, 0);

请注意，参数0L也可写为(long)0，或仅仅写为0，但是系统调用lseek的声明必须保持一致。

使用lseek系统调用时，可以将文件视为一个大数组，其代价是访问速度会慢一些。例如，下面的函数将从文件的任意位置读入任意数目的字节，它返回读入的字节数，若发生错误，则返回-1。

#include "syscalls.h"

/* get函数：从pos位置处读入n个字节 */
int get(int fd, long pos, char *buf, int n) {
    if (lseek(fd, pos, 0) >= 0)   /* 移动到位置pos处 */
        return read(fd, buf, n);
    else
        return -1;
}

lseek系统调用返回一个long类型的值，此值表示文件的新位置，若发生错误，则返回-1。标准库函数fseek与系统调用lseek类似，所不同的是，前者的第一个参数是FILE *类型，且在发生错误时返回一个非0值。

8.5 实例————fopen和getc函数的实现

下面以标准库函数fopen和getc的一种实现方法为例来说明如何将这些系统调用结合起来使用。

我们回忆一下，标准库中的文件不是通过文件描述符描述的，而是使用文件指针描述的。文件指针是一个指向包含文件各种信息的结构的指针，该结构包含下列内容：一个指向缓冲区的指针，通过它可以一次读入文件的一大块内容；一个记录缓冲区中剩余的字符数的计数器；一个指向缓冲区中下一个字符的指针；文件描述符；描述读/写模式的标志；描述错误状态的标志等。

描述文件的数据结构包含在头文件<stdio.h>中，任何需要使用标准输入/输出库中函数的程序都必须在源文件中包含这个头文件（通过#include指令包含头文件）。此文件也被库中的其他函数包含。在下面这段典型的<stdio.h>代码段中，只供标准库中其他函数所使用的名字以下划线开始，因此一般不会与用户程序中的名字冲突。所有的标准库函数都遵循该约定。

#define NULL      0
#define EOF       (-1)
#define BUFSIZ    1024
#define OPEN_MAX  20    /* 一次最多可打开的文件数 */

typedef struct _iobuf {
    int cnt;            /* 剩余的字符数 */
    char *ptr;          /* 下一个字符的位置 */
    char *base;         /* 缓冲区的位置 */
    int flag;           /* 文件访问模式 */
    int fd;             /* 文件描述符 */
} FILE;
extern FILE _iob[OPEN_MAX];

#define stdin   (&_iob[0])
#define stdout  (&_iob[1])
#define stderr  (&_iob[2])

enum _flags {
    _READ   = 01,     /* 以读方式打开文件 */
    _WRITE  = 02,     /* 以写方式打开文件 */
    _UNBUF  = 04,     /* 不对文件进行缓冲 */
    _EOF    = 010,    /* 已到文件的末尾 */
    _ERR    = 020     /* 该文件发生错误 */
};

int _fillbuf(FILE *);
int _flushbuf(int, FILE *);

#define feof(p)      (((p)->flag & _EOF) != 0)
#define ferror(p)    (((p)->flag & _ERR) != 0)
#define fileno(p)    ((p)->fd)

#define getc(p)   (--(p)->cnt >= 0 \
                ? (unsigned char) *(p)->ptr++ : _fillbuf(p))
#define putc(x,p) (--(p)->cnt >= 0 \
                ? *(p)->ptr++ = (x) : _flushbuf((x),p))

#define getchar()  getc(stdin)
#define putchar(x) putc((x), stdout)

宏getc一般先将计数器减1，将指针移动到下一个位置，然后返回字符。（前面讲过，一个长的#define语句可用反斜杠分成几行。）但是，如果计数值变为负值，getc就调用函数_fillbuf填充缓冲区，重新初始化结构的内容，并返回一个字符。返回的字符为unsigned类型，以确保所有的字符为正值。

尽管在这里我们并不想讨论一些细节，但程序中还是给出了putc函数的定义，以表明它的操作与getc函数非常类似，当缓冲区满时，它将调用函数_flushbuf。此外，我们还在其中包含了访问错误输出、文件结束状态和文件描述符的宏。

下面我们来着手编写函数fopen。fopen函数的主要功能是打开文件，定位到合适的位置，设置标志位以指示相应的状态。它不分配任何缓冲区空间，缓冲区的分配是在第一次读文件时由函数_fillbuf完成的。

#include <fcntl.h>
#include "syscalls.h"
#define PERMS  0666   /* 所有者、所有者组和其他成员都可以读写 */

/* fopen函数：打开文件，并返回文件指针 */
FILE *fopen(char *name, char *mode) {
    int fd;
    FILE *fp;

    if (*mode != 'r' && *mode != 'w' && *mode != 'a')
        return NULL;
    for (fp = _iob; fp < _iob + OPEN_MAX; fp++)
        if ((fp->flag & (_READ | _WRITE)) == 0)
            break;       /* 寻找一个空闲位 */
    if (fp >= _iob + OPEN_MAX)    /* 没有空闲位置 */
        return NULL;

    if (*mode == 'w')
        fd = creat(name, PERMS);
    else if (*mode == 'a') {
        if ((fd = open(name, O_WRONLY, 0)) == -1)
            f = creat(name, PERMS);
        lseek(fd, 0L, 2);
    } else
        fd = open(name, O_RDONLY, 0);
    if (fd == -1)
        return NULL;
    fp->fd = fd;
    fp->cnt = 0;
    fp->base = NULL;
    fp->flag = (*mode == 'r') ? _READ : _WRITE;
    return fp;
}

该版本的fopen函数没有涉及标准C的所有访问模式，但是，加入这些模式并不需要增加多少代码。特别是，该版本的fopen不能识别表示二进制访问方式的b标志，这是因为，在UNIX系统中这种方式是没有意义的。同时，它也不能识别允许同时进行读和写的+标志。

对于某一特定的文件，第一次调用getc函数时计数值为0，这样就必须调用一次函数_filebuf。如果_fillbuf发现文件不是以读方式打开的，它将立即返回EOF；否则，它将试图分配一个缓冲区（如果读操作是以缓冲方式进行的话）。

建立缓冲区后，_fillbuf调用read填充此缓冲区，设置计数值和指针，并返回缓冲区中的第一个字符。随后进行的_fillbuf调用会发现缓冲区已经分配。

#include "syscalls.h"

/* _fillbuf函数：分配并填充输入缓冲区 */

int _fillbuf(FILE *fp) {
    int bufsize;

    if ((fp->flag&(_READ|_EOF|_ERR)) != _READ)
        return EOF;
    bufsize = (fp->flag & _UNBUF) ? 1 : BUFSIZE;
    if (fp->base == NULL)   /* 还未分配缓冲区 */
        if ((fp->base = (char *) malloc(bufsize)) == NULL)
            return EOF;     /* 不能分配缓冲区 */
    fp->ptr = fp->base;
    fp->cnt = read(fp->fd, fp->ptr, bufsize);
    if (--fp->cnt < 0) {
        if (fp->cnt == -1)
            fp->flag |= _EOF;
        else
            fp->flag |= _ERR;
        fp->cnt = 0;
        return EOF;
    }
    return (unsigned char) *fp->ptr++;
}

最后一件事情便是如何执行这些函数。我们必须定义和初始化数组_iob中的stdin、stdout和stderr值：

FILE _iob[OPEN_MAX] = {    /* stdin, stdout, stderr; */
    { 0, (char *) 0, (char *) 0, _READ,  0},
    { 0, (char *) 0, (char *) 0, _WRITE, 1},
    { 0, (char *) 0, (char *) 0, _WRITE | _UNBUF, 2}
};

该结构中flag部分的初值表明，将对stdin执行读操作、对stdout执行写操作、对stderr执行缓冲方式的写操作。

练习8-2 用字段代替显式的按位操作，重写fopen和_fillbuf函数。比较相应代码的长度和执行速度。

练习8-3 设计并编写函数_flushbuf、fflush和fclose。

练习8-4 标准库函数

int fseek(FILE *fp, long offset, int origin)

类似于函数lseek，所不同的是，该函数中的fp是一个文件指针而不是文件描述符，且返回值是一个int类型的状态而非位置值。编写函数fseek，并确保该函数与库中其他函数使用的缓冲能够协同工作。

8.6 实例————目录列表

我们常常还需要对文件系统执行另一种操作，以获得文件的有关信息，而不是读取文件的具体内容。目录列表程序便是其中的一个例子，比如UNIX命令ls，它打印一个目录中的文件名以及其他一些可选信息，如文件长度、访问权限等等。MS-DOS操作系统中的dir命令也有类似的功能。

由于UNIX中的目录就是一种文件，因此，ls只需要读此文件就可获得所有的文件名。但是，如果需要获取文件的其他信息，比如长度等，就需要使用系统调用。在其他一些系统中，甚至获取文件名也需要使用系统调用，例如在MS-DOS系统中即如此。无论实现方式是否同具体的系统有关，我们需要提供一种与系统无关的访问文件信息的途径。

以下将通过程序fsize说明这一点。fsize程序是ls程序的一个特殊形式，它打印命令行参数表中指定的所有文件的长度。如果其中一个文件是目录，则fsize程序将对此目录递归调用自身。如果命令行中没有任何参数，则fsize程序处理当前目录。

我们首先回顾UNIX文件系统的结构。在UNIX系统中，目录就是文件，它包含了一个文件名列表和一些指示文件位置的信息。“位置”是一个指向其他表（即i结点表）的索引。文件的i结点是存放除文件名以外的所有文件信息的地方。目录项通常仅包含两个条目：文件名和i结点编号。

遗憾的是，在不同版本的系统中，目录的格式和确切的内容是不一样的。因此，为了分离出不可移植的部分，我们把任务分成两部分。外层定义了一个称为Dirent的结构和3个函数opendir、readdir和closedir，它们提供与系统无关的对目录项中的名字和i结点编号的访问。我们将利用此接口编写fsize程序，然后说明如何在与Version 7和System V UNIX系统的目录结构相同的系统上实现这些函数。其他情况留作练习。

结构Dirent包含i结点编号和文件名。文件名的最大长度由NAME_MAX设定，NAME_MAX的值由系统决定。opendir返回一个指向称为DIR的结构的指针，该结构与结构FILE类似，它将被readdir和closedir使用。所有这些信息存放在头文件dirent.h中。

#define NAME_MAX   14  /* 最长文件名：由具体的系统决定 */

typedef struct {       /* 可移植的目录项 */
    long  ino;               /* i结点编号 */
    char name[NAME_MAX+1];   /* 文件名加结束符'\0' */
} Dirent;

typedef struct {       /* 最小的DIR：无缓冲等特性 */
    int  fd;                 /* 目录的文件描述符 */
    Dirent d;                /* 目录项 */
} DIR;

DIR *opendir(char *dirname);
Dirent *readdir(DIR *dfd);
void closedir(DIR *dfd);

系统调用stat以文件名作为参数，返回文件的i结点中的所有信息；若出错，则返回-1。如下所示：

char *name;
struct stat stbuf;
int stat(char *, struct stat *);

stat(name, &stbuf);

它用文件name的i结点信息填充结构stbuf。头文件<sys/stat.h>中包含了描述stat的返回值的结构。该结构的一个典型形式如下所示：

struct stat {    /* 由stat返回的i结点信息 */
    dev_t    st_dev;     /* i结点设备 */
    ino_t    st_ino;     /* i结点编号 */
    short    st_mode;    /* 模式位 */
    short    st_nlink;   /* 文件的总的链接数 */
    short    st_uid;     /* 所有者的用户id */
    short    st_gid;     /* 所有者的组id */
    dev_t    st_rdev;    /* 用于特殊的文件 */
    off_t    st_size;    /* 用字符数表示的文件长度 */
    time_t   st_atime;   /* 上一次访问的时间 */
    time_t   st_mtime;   /* 上一次修改的时间 */
    time_t   st_ctime;   /* 上一次改变i结点的时间 */
};

该结构中大部分的值已在注释中进行了解释。dev_t和ino_t等类型在头文件<sys/types.h>中定义。程序中必须包含此文件。

st_mode项包含了描述文件的一系列标志，这些标志在<sys/stat.h>中定义。我们只需要处理文件类型的有关部分：

#define S_IFMT  0160000       /* 文件的类型 */
#define S_IFDIR 0040000       /* 目录 */
#define S_IFCHR 0020000       /* 特殊字符 */
#define S_IFBLK 0060000       /* 特殊块 */
#define S_IFREG 0100000       /* 普通 */

/* ... */

下面我们来着手编写程序fsize。如果由stat调用获得的模式说明某文件不是一个目录，就很容易获得该文件的长度，并直接输出。但是，如果文件是一个目录，则必须逐个处理目录中的文件。由于该目录可能包含子目录，因此该目录是递归的。

主程序main处理命令行参数，并将每个参数传递给函数fsize。

#include <stdio.h>
#include <string.h>
#include "syscalls.h"
#include <fcntl.h>         /* 读写标志 */
#include <sys/types.h>     /* 类型定义 */
#include <sys/stat.h>      /* stat返回的结构 */
#include "dirent.h"

void fsize(char *);

/* 打印文件长度 */
main(int argc, char **argv) {
    if (argc == 1)       /* 默认为当前目录 */
        fsize(".");
    else
        while(--argc > 0)
            fsize(*++argv);
    return 0;
}

函数fsize打印文件的长度。但是，如果此文件是一个目录，则fsize首先调用dirwalk函数处理它所包含的所有文件。注意如何使用文件<sys/stat.h>中的标志名S_IFMT和S_IFDIR来判定文件是不是一个目录。括号是必须的，因为&运算符的优先级低于==运算符的优先级。

int stat(char *, struct stat *);
void dirwalk(char *, void (*fcn)(char *));

/* fsize函数：打印文件name的长度 */
void fsize(char *name) {
    struct stat stbuf;

    if (stat(name, &stbuf) == -1) {
        fprintf(stderr, "fsize: can't access %s\n", name);
        return;
    }
    if ((stbuf.st_mode & S_IFMT) == S_IFDIR)
        dirwalk(name, fsize);
    printf("%8ld %s\n", stbuf.st_size, name);
}

函数dirwalk是一个通用的函数，它对目录中每个文件都调用函数fcn一次。它首先打开目录，循环遍历其中的每个文件，并对每个文件调用函数，然后关闭目录返回。因为fsize函数对每个目录都要调用dirwalk函数，所有这两个函数是互相递归调用的。

#define MAX_SIZE 1024

/* dirwalk函数：对dir中的所有文件调用函数fcn */
void dirwalk(char *dir, void (*fcn)(char *)) {
    char name[MAX_PATH];
    Dirent *dp;
    DIR *dfd;

    if ((dfd = opendif(dir)) == NULL) {
        fprintf(stderr, "dirwalk: can't open %s\n", dir);
        return;
    }
    while((dp = readdir(dfd)) != NULL){
        if (strcmp(dp->name, ".") == 0
         || strcmp(dp->name, "..") == 0)
            continue;   /* 跳过自身和父目录 */
        if (strlen(dir)+strlen(dp->name)+2 > sizeof(name))
            fprintf(stderr, "dirwalk: name %s/%s too long\n",
                dir, dp->name);
        else {
            sprintf(name, "%s/%s", dir, dp->name);
            (*fcn)(name);
        }
    }
    closedir(dfd);
}

每次调用readdir都将返回一个指针，它指向下一个文件的信息。如果目录中已没有待处理的文件，该函数将返回NULL。每个目录都包含自身“.”和父目录“..”的项目，在处理时必须跳过它们，否则将会导致无限循环。

到现在这一步为止，代码与目录的格式无关。下一步要做的事情就是在某个具体的系统上提供一个opendir、readdir和closedir的最简单版本。以下的函数适用于Version 7和System V UNIX系统，它们使用了头文件<sys/dir.h>中的目录信息，如下所示：

#ifndef DIRSIZ
#define DIRSIZ  14
#endif
struct direct {  /* 目录项 */
    ino_t d_ino;            /* i结点编号 */
    char  d_name[DIRSIZ];   /* 长文件名不包括'\0' */
};

某些版本的系统支持更长的文件名和更复杂的目录结构。

类型ino_t是使用typedef定义的类型，它用于描述i结点表的索引。在我们通常使用的系统中，此类型为unsigned short，但是这种信息不应在程序中使用。因为在不同的系统中该类型可能不同，所以使用typedef定义更好一些。所有的“系统”类型可以在文件<sys/types.h>中找到。

opendir函数首先打开目录，验证此文件是一个目录（调用系统调用fstat，它与stat类似，但它以文件描述符作为参数），然后分配一个目录结构，并保存信息：

int fstat(int fd, struct stat *);

/* opendir函数：打开目录供函数readdir使用 */
DIR *opendir(char *dirname) {
    int fd;
    struct stat stbuf;
    DIR *dp;

    if ((fd = open(dirname, O_RDONLY, 0)) == -1
      || fstat(fd, &stbuf) == -1
      || (stbuf.st_mode & S_IFMT) != S_IFDIR
      || (dp = (DIR *) malloc(sizeof(DIR))) == NULL)
        return NULL;
    dp->fd = fd;
    return dp;
}

closedir函数用于关闭目录文件并释放内存空间：

/* closedir函数：关闭由opendir打开的目录 */
void closedir(DIR *dp) {
    if (dp) {
        close(dp->fd);
        free(dp);
    }
}

最后，函数readdir使用read系统调用读取每个目录项。如果某个目录位置当前没有使用（因为删除了一个文件），则它的i节点编号为0，并跳过该位置。否则，将i结点编号和目录名放在一个static类型的结构中，并给用户返回一个指向此结构的指针。每次调用readdir函数将覆盖前一次调用获得的信息。

#include <sys/dir.h>    /* 本地目录结构 */

/* readdir函数：按顺序读取目录项 */
Dirent *readdir(DIR *dp) {
    struct dirent dirbuf;    /* 本地目录结构 */
    static Dirent d;         /* 返回：可移植的结构 */

    while (read(dp->fd, (char *) &dirbuf, sizeof(dirbuf))
                    == sizeof(dirbuf)) {
        if (dirbuf.d_ino == 0)     /* 目录位置未使用 */
            continue;
        d.ino = dirbuf.d_ino;
        strncpy(d.name, dirbuf.d_name, DIRSIZ);
        d.name[DIRSIZ] = '\0';     /* 添加终止符 */
        return &d;
    }
    return NULL;
}

尽管false程序非常特殊，但是它的确说明了一些重要的思想。首先，许多程序并不是“系统程序”，它们仅仅使用由操作系统维护的信息。对于这样的程序，很重要的一点是，信息的表示仅出现的标准头文件中，使用它们的程序只需要在文件中包含这些头文件即可，而不需要包含相应的声明。其次，有可能为与系统相关的对象创建一个与系统无关的接口。标准库中的函数就是很好的例子。

练习8-5 修改fsize程序，打印i结点项中包含的其他信息。

8.7 实例————存储分配程序

我们在第5章给出了一个功能有限的面向栈的存储分配程序。本节将要编写的版本没有限制，可以以任意次序调用malloc和free。malloc在必要时调用操作系统以获取更多的存储空间。这些程序说明了通过一种与系统无关的方式编写与系统有关的代码时应考虑的问题，同时也展示了结构、联合和typedef的实际应用。

malloc并不是从一个在编译时就确定的固定大小的数组中分配存储空间，而是在需要时向操作系统申请空间。因为程序中的某些地方可能不通过malloc调用申请空间（也就是说，通过其他方式申请空间），所以，malloc管理的空间不一定是连续的。这样，空闲存储空间与空闲块链表的方式组织，每个块包含一个长度、一个指向下一块的指针以及一个指向自身存储空间的指针。这些块按照存储地址的升序组织，最后一块（最高地址）指向第一块（参见图8.1）。

图 8-1

由malloc控制的空闲空间
            v
            +-------------------------------------------------+
            v +---++----------------++--------------++---++--+|
-----+------+-^-+-v^-+------+------+v^+-----+------+v^-+-v^-+v^+-----
.....|using |   |    |using |using |  |.....|using |   |    |  |.....
-----+------+---+----+------+------+--+-----+------+---+----+--+-----

             [      ]  由malloc控制的已经使用的空间
             [using ]  不是由malloc控制的空间
             [......]  空闲链表

当有申请请求时，malloc将扫描空闲块链表，直到找到一个足够大的块为止。该算法称为“首次适应”（first fit）；与之相对的算法是“最佳适应”（best fit），它寻找满足条件的最小快。如果该块恰好与请求的大小相符合，则将它从链表中移走并返回给用户。如果该块太大，则将它分成两部分：大小合适的块返回给用户，剩下的部分留在空闲块链表中。如果找不到一个足够大的块，则向操作系统申请一个大块并加入到空闲块链表中。

释放过程也是首次搜索空闲块链表，以找到可以插入被释放块的合适位置。如果与被释放块相邻的任一边是一个空闲块，则将这两个块合成一个更大的块，这样存储空间不会有太多的碎片。因为空闲块链表是以地址的递增顺序链接在一起的，所以很容易判断相邻的块是否空闲。

我们在第5章中曾提出了这样的问题，即确保由malloc函数返回的存储空间满足将要保存的对象的对齐要求。虽然机器类型各异，但是，每个特定的机器都有一个最受限的类型：如果最受限的类型可以存储在某个特定的地址中，则其他所有的类型也可以存放在此地址中。在某些机器中，最受限的类型是double类型；而在另外一些机器中，最受限的类型是int或long类型。

空闲块包含一个指向链表中下一个块的指针、一个块大小的记录和一个指向空闲空间本身的指针。位于块开始处的控制信息称为“头部”。为了简化块的对齐，所有块的大小都必须是头部大小的整数倍，且头部已正确地对齐。这是通过一个联合实现的，该联合包含所需的头部结构以及一个对齐要求最受限的类型的实例，在下面这段程序中，我们假定long类型为最受限的类型：

typedef long Align;    /* 按照long类型的边界对齐 */

union header {         /* 块的头部 */
    struct {
        union header *ptr;   /* 空闲块链表中的下一块 */
        unsigned size;       /* 本块的大小 */
    } s;
    Align x;           /* 强制块的对齐 */
};

typedef union header Header;

在该联合中，Align字段永远不会被调用，它仅仅用于强制每个头部在最坏的情况下满足对齐要求。

在malloc函数中，请求的长度（以字符为单位）将被舍入，以保证它是头部大小的整数倍。实际分配的块将多包含一个单元，用于头部本身。实际分配的块的大小将被记录在头部的size字段中。malloc函数返回的指针将指向空闲空间，而不是块的头部。用户可对获得的存储空间进行任何操作，但是，如果在分配的存储空间之外写入数据，则可能会破坏块链表。图8-2表示由malloc返回的块。

图8-2 malloc返回的块

 +-->指向下一个空闲块
+|--+----+---------------------------------
|   |size| 
+---+----+--------------------------------
         +-<-------返回给用户的地址

其中的size字段是必需的，因为由malloc函数控制的块不一定是连续的，这样就不可能通过指针算术运算计算其大小。

变量base表示空闲块链表的头部。第一次调用malloc函数时，freep为NULL，系统将创建一个退化的空闲块链表，它只包含一个大小为0的块，且该块指向它自己。任何情况下，当请求空闲空间时，都将搜索空闲块链表。搜索从上一次找到空闲块的地方（freep）开始。该策略可以保证链表是均匀的。如果找到的块太大，则将其尾部返回给用户，这样，初始块的头部只需要修改size字段即可。在任何情况下，返回给用户的指针都指向块内的空闲存储空间，即比指向头部的指针大一个单元。

static Header base;          /* 从空链表开始 */
static Header *freep = NULL;  /* 空闲链表的初始指针 */

/* malloc函数：通过存储分配函数 */
void *malloc(unsigned nbytes) {
    Header *p, *prevp;
    Header *morecore(unsigned);
    unsigned nunits;

    nunits = (nbytes+sizeof(Header)-1)/sizeof(Header) + 1;
    if ((prevp = freep) == NULL) { /* 没有空闲链表 */
        base.s.ptr = freep = prevp = &base;
        base.s.size = 0;
    }
    for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
        if (p->s.size >= nunits) {    /* 足够大 */
            if (p->s.size == nunits)   /* 正好 */
                prevp->s.ptr = p->s.ptr;
            } else {                  /* 分配末尾部分 */
                p->s.size -= nunits;
                p += p->s.size;
                p->s.size = nunits;
            }
            freep = prevp;
            return (void *)(p+1);
        }
        if (p == freep)     /* 闭环的空闲链表 */
            if ((p = morecore(nunits)) == NULL)
                return NULL;     /* 没有剩余的存储空间 */
    }
}

函数morecore用于向操作系统请求存储空间，其实现细节因系统的不同而不同。因为向系统请求存储空间是一个开销很大的操作，因此，我们不希望每次调用malloc函数时都执行该操作，基于这个考虑，morecore函数请求至少NALLOC个单元。这个较大的块将根据需要分成较小的块。在设置完size字段之后，morecore函数调用free函数把多余的存储空间插入到空闲区域中。

UNIX系统调用sbrk(n)返回一个指针，该指针指向n个字节的存储空间。如果没有空闲空间，尽量返回NULL可能更好一些，但sbrk调用返回-1。必须将-1强制转换为char *类型，以便与返回值进行比较。而且，强制类型转换使得该函数不会受不同机器中指针表示的不同的影响。但是，这里仍然假定，由sbrk调用返回的指向不同块的多个指针之间可以进行有意义的比较。ANSI标准并没有保证这一点，它只允许指向同一个数组的指针间的比较。因此，只有在一般指针间的比较操作有意义的机器上，该版本的malloc函数才能够移植。

#define NALLOC 1024    /* 最小申请单元数 */

/* morecore函数：向系统申请更多的存储空间 */
static Header *morecore(unsigned nu) {
    char *p, *sbrk(int);
    Header *up;

    if (nu < NALLOC)
        nu = NALLOC;
    cp = sbrk(nu * sizeof(Header));
    if (cp == (char *) -1)    /* 没有空间 */
        return NULL;
    up = (Header *) cp;
    up->s.size = nu;
    free((void *)(up+1));
    return freep;
}

我们最后来看一下free函数。它从freep指向的地址开始，逐个扫描空间块链表，寻找可以插入空闲块的地方。该位置可能在两个空闲块之间，也可能在链表的末尾。在任何一种情况下，如果被释放的块与另一空闲块相邻，则将这两个块合并起来。合并两个块的操作很简单，只需要设置指针指向正确的位置，并设置正确的块大小就可以了。

/* free函数：将块ap放入空闲块链表中 */
void free(void *ap) {
    Header *bp, *p;

    bp = (Header *)ap - 1;    /* 指向块头 */
    for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
        if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
            break;   /* 被释放的块在链表的开头或末尾 */

    if (bp + bp->s.size == p->s.ptr) {  /* 与上一相邻块合并 */
        bp->s.size += p->s.ptr->s.size;
        bp->s.ptr = p->s.ptr->s.ptr;
    } else {
        bp->s.ptr = p->s.ptr;
    }
    if (p + p->s.size == bp) {
        p->s.size += bp->s.size;    /* 与下一相邻块合并 */
        p->s.ptr = bp->s.ptr;
    } else
        p->s.ptr = bp;
    freep = p;
}

虽然存储分配从本质上是与机器相关的，但是，以上的代码说明了如何控制与具体机器相关的部分，并将这部分程序控制到最少量。typedef和union的使用解决了地址的对齐（假定sbrk返回的是合适的指针）问题。类型的强制转换使得指针的转换是显式进行的，这样做甚至可以处理设计不够好的系统接口问题。虽然这里所讲的内容只涉及到存储分配，但是，这种通用方法也适用于其他情况。

练习8-6 标准库函数calloc(n,size)返回一个指针，它指向n个长度为size的对象，且所有分配的存储空间都被初始化为0。通过调用或修改malloc函数来实现calloc函数。

练习8-7 malloc接收对存储空间的请求时，并不检查请求长度的合理性；而free则认为被释放的块包含一个有效的长度字段。改进这些函数，使它们具有错误检查的功能。

联系8-8 编写函数bfree(p,n)，释放一个包含n个字符的任意块p，并将它放入由malloc和free维护的空闲块链表中。通过使用bfree，用户可以在任意时刻向空闲块链表中添加一个静态或外部数组。

专题: C程序设计语言

本文发表于 2022-09-13，最后修改于 2022-09-13。

本站永久域名「 jiavvc.top 」，也可搜索「后浪笔记一零二四」找到我。

上一篇 « C程序设计语言-附录A参考手册下一篇 » C程序设计语言-第7章输入与输出