深入理解计算机系统(csapp)

[wittyResry]

第九章 虚拟存储器

• 虚拟存储器是对主存的一个抽象。处理器产生的虚拟地址，在被发送到主存之前，整个地址被翻译成一个物理地址。从虚拟地址空间到物理地址空间的地址翻译要求硬件和软件相互合作。专门的硬件通过使用页表来翻译虚拟地址，而页表的内容是由操作系统提供的。
  • 虚拟存储器的作用
  • 第一，它在主存中自动缓存最近使用的磁盘上的虚拟地址空间的内容。对磁盘上页的引用会触发却也，缺页将控制转移到操作系统中的缺页处理程序。缺页处理程序将页面从磁盘拷贝到主存缓存，如果必要，将写回被驱逐出的页。
  • 第二，虚拟存储器简化了存储器的管理，进而又简化了链接、在进程间共享数据、进程的存储器分配以及程序加载。
  • 第三，虚拟存储器通过在每个页表条目中加入保护位，从而简化了存储器的保护。
  • 现代操作系统，通过将虚拟存储器片和磁盘上的文件片关联起来，这个过程称为存储器映射。存储器映射为共享数据、穿件新的进程以及加载程序提供了一种高效的机制。
  • mmap函数可以用来手工创建和删除虚拟地址空间的区域。
  • 大多数程序用来与动态存储器分配器，例如malloc，它管理了堆的区域。

    动态存储器分配

• C++中的new和delete以及C的malloc和free，使用显式分配器。
• Java和Lisp等采用隐式分配器，可以自动释放已分配的块，这个过程叫做垃圾收集。

  显式分配器的设计和实现

  malloc和free函数

• malloc当初始化的块过大时，将返回NULL。malloc不会初始化，需要重新大小，采用realloc函数。
• sbrk请求堆空间。
• mmap显示分配堆存储器，munmap显示释放堆。
• 采用MAXN的坏处，防止硬编码数组界限，提高健壮性。

不要使用:

#define MAXN 15213
int array[MAXN];

最好使用下面的方式:

int * array;
scanf("%d", &n);
array = (int *) malloc (n * sizeof(int));

碎片

• 内部碎片：例如满足对齐约束条件产生的。
• 外部碎片：例如请求6个字，而堆仍然有6个字大小，但是分布在两个空闲块中。

  隐式空闲链表

• 数据结构，malloc返回有效载荷开始处，使用29bit高位来表示块大小和3个bit位来表示是否空闲，最后还有对齐要求的填充部。
• 分配器可以通过遍历对中所有的块，从而间接地遍历整个空闲块集合。

  分配器的搜索方式

• first fit(较大的块),next fit(Donald Knuth提出，但是效果并非很好), best fit(利用率较高，但是需要对堆进行彻底地搜索)。分离式空闲链表组织。
• free可能会涉及合并相邻的空闲块
  • 立即合并：可能产生抖动，反复地合并，然后又分割。如反复地分配和释放一个3个字的块将产生大量不必要的分割和合并。
  • 推迟合并：应当了解，实际选择的是某种形式的推迟合并。
  • 释放当前的块
  • 合并下一个块：可以在常数内完成。检查下一个块是否空闲（找到下一个块，头部指向下一个），如果是，就将它的大小加到当前的块头部上。
  • 合并前面第一个块：需要搜索整个空闲链表，找到并记录前面块的位置。复杂度与堆大小呈线性关系。即使使用更好的空闲链表组织技术，搜索时间也不是常数。
  • Knuth提出边界标记方式，可以对前面块常数时间进行合并。通过检查脚部，可以判断前面一个块的位置和状态，这个脚步是在距当前块开始位置一个字的距离。

    显式空闲链表

• 采用pred和succ的双向链表组织。适用于空闲链表足够大，因为指针+头部+脚部导致了最小块大小。

  分离空闲链表

• 按照{1},{2},{3,4},{5,8},...,{1025,2048},...来分成等价类分离存储
• 分配器维护者一个空闲链表组，每个大小类一个空闲链表，按照大小升序排列。
• 当分配一n的块，就搜索相应的空闲链表，如果不匹配，就搜索下一个链表。
• 分离适配（重要的适配方式）：每个链表包含潜在大小不同的块，块大小是大小类的成员。为了分配一个块，首先对空闲链表作首次适配，查找到一个合适的块。如果找到一个，则分割它，并将剩余部分插入到适当的空闲链表中。如果找不到合适的块，那么久向操作系统请求二维的堆存储，从这个堆存储中获得一个合适的块（一般是页大小的整数倍），并将剩余部分插入到适当的大小类中。要释放一个块，我们只需合并，把结果防止到相应的空闲链表中。分离适配是一种常见的选择，如GUNmalloc采用的是这种方法。这种方法对存储器的使用有很高的利用率。搜索时间也减少了，而且，对分离空闲链表采用简单的首次适配搜索，其存储利用率近似于对整个堆的最佳适配的存储利用率。

  垃圾收集

• 垃圾收集器：动态存储分配器，自动释放程序不再需要的已分配的块。
• 在高级语言中，应用显示分配内存，但是从不进行回收内存，而是由垃圾收集器自动识别并回收内存。
• Mark&Sweep

  基础知识

• 根节点：指向对中的指针，存在于不再堆中的位置，这些位置可以是寄存器、栈里的变量，或者是虚拟存储器中读写数据区域内的全局变量。
• 堆节点：分为可达和不可达的内存块。
  • 节点p可达：存在一条从任意节点到该节点的有向路径。
  • 不可达的节点：对应于垃圾，是不能被应用再次使用。
  • 垃圾收集器维护可达图的某种表示，并通过释放不可达节点，并将它们返回给空闲链表，来定期地回收它们。
• 收集器可以按需提供它们的服务，或作为一个和应用并行的独立线程，不断更新可达图和回收垃圾。
• 将保守的垃圾收集器添加到C的malloc包中：当malloc找不到一个合适的空闲块的时候，那么就会调用垃圾收集器，希望能够回收一些垃圾到空闲链表。收集器识别出垃圾块，并且通过调用free函数将他们返回给堆。这里关键的思想是垃圾收集器代替应用去调用free。如果收集器调用后，malloc重试仍然没有合适的块，就会向操作系统要求额外的存储器资源。最后，malloc返回一个指向请求块的指针（如果成功），或者返回一个空指针（请求失败）。

  Mark&Sweep垃圾收集器

• 由标记和清除两个阶段组成

  • 标记阶段：标记处根节点的所有可达的和已分配的后继。
  • 清除阶段：释放每个被标记的已分配的块。

  typedef void * ptr;
  /**
  * Mark阶段
  * 每次对mark函数，调用标记某个跟节点的所有未标记并且可达的后继节点。在Mark阶段的末尾，任何未标记的已分配的块都被认定为是不可达的
  * ，是垃圾，可以在Sweep阶段进行清除。
  */
  void mark(ptr p) {
    if ((b = isPtr(p)) == NULL) {
        return;
    }
    //p不指向已分配未标记的块，mark函数返回。
    if (blockMarked(b)) {
        return;
    }
    //否则标记这个块，并对块中每个字递归调用它自己。
    markBlock(b);
    len = length(b);
    for (int i = 0; i < len; ++i) {
        mark(b[i]);
    }
    return;
  }
  /**
  * Sweep阶段
  * 在每个块上反复循环，释放它遇到的所有未标记的已分配的块
  */
  void sweep(ptr b, ptr end) {
    while(b < end) {
        if (blockMarked(b)) {//如果是已经标记为可达的块，去掉标记
            unmarkBlock(b);
        } else if (blockAllAllocated(b)) {//如果块是已经分配的，则进行释放该块
            free(b);
        }
        b = nexBlock(b);
    }
    reutrn;
  }

  C程序中常见的与存储有关的错误

• 错误引用坏指针

scanf("%d", val);
在这种情况下，scanf将把val的内容解释为地址：情况1，发现不可以写，程序终止；情况2，val的内容对应于虚拟存储器的某个合法的可读/写区域，于是我们就覆盖了存储器，这通常会导致灾难性的、令人困惑的后果。

• 未初始化的存储器

  • bss存储器的位置（如未初始化的全局C变量）总是被加载为零
  • 堆存储器不会被初始化为零，一个典型的错就是，没有将y设为0。或者用calloc代替malloc

  int *matvec(int **A, int *x, int n) {
    int i, j;
    int *y = (int *) malloc(n * sizeof(int));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            y[i] += A[i][j] * x[j];
        }
    }
    return y;
  }

• 栈缓冲区溢出

  • 如果一个程序不检查串的大小，就写入栈中的目标缓冲区，那么久可能造成缓冲区溢出错误，例如：

  void bufoverflow() {
    char buf[64];
    gets(buf);
    return;
  }

  • 为了解决，可以用fgets，指定输入串大小。

• 默认假设指针和它们指向的对象相同大小

  • 如果下面这段在Core i7这样的机器，其中指针大于int，有可能写到边界标记脚部，造成合并代码的时候失败，但是却没有提示明显的原因。

  int ** makeArray1(int n, int m) {
    int i;
    //这里想创建一个n个指针组成的数组，但是却将sizeof(int *)写成了sizeof(int)
    int **A = (int **) malloc (n * sizeof(int));
    for (int i = 0; i < n; ++i) {
        A[i] = (int *) malloc (m * sizeof(int));
    }
    return A;
  }

• 造成错位

  • 错位例子：

  int ** makeArray1(int n, int m) {
    int i;
    int **A = (int **) malloc (n * sizeof(int*));
    for (int i = 0; i <= n; ++i) {
        A[i] = (int *) malloc (m * sizeof(int));
    }
    return A;
  }

  • 这里创建了n长度的指针数组，但是却试图初始化n+1个元素，在这个过程中覆盖了A数组后面的某个存储器。

• 引用指针，而不是它所指向的对象。

  • *和--操作符优先级例子：

  int *binheapDelete(int ** binheap, int * size) {
    int * package = binheap[0];
    binheap[0] = binheap[*size - 1];
    *size--; /** this should be (*size)-- */
    heapify(binheap, *size, 0);
  }
  

• 误解指针运算

  • 指针运算时以它们指向的对象的大小为单位进行，而这种单位不一定是字节。

  int *search(int *p, int val) {
    while (*p && *p != val) {
        p += sizeof(int); /** this should be p++ */
    }
    return p;
  }

• 引用不存在的变量

  • 不理解栈的规则，有事会引用不合法的本地变量，如下所示：

  int *stackref() {
    int val;
    return &val;
  }

  • 这个函数返回一个指针p，指向栈里的局部变量，然后返回栈桢。尽管p仍然指向一个合法的存储器地址，但是它已经不再指向一个合法的变量了。当以后再程序中调用其他函数时，存储器将重用它们的栈桢。再后来，如果程序分配某个值给*p，那么它可能实际修改另一个函数中的条目，从而潜在地带来灾难性的、令人困惑的后果。

• 引用堆块中的数据

  • 一个相似的错误是引用已经被释放的堆块数据，如：

  int *heapref (int n, int m) {
    int i;
    int *x, int *y;
    x = (int *) malloc(n * sizeof(int));
    /** Other calls to malloc and free go here */
    free(x);
    y = (int *) malloc (m * sizeof(int));
    for (int i = 0; i < m ; ++i) {
        y[i] = x[i]++; /** Oops! x[i] is a word in a free block */
    }
  }

• 引起存储器泄露

  • 存储器泄露是缓慢的、隐性杀手，当程序员不小心忘记释放已分配块，而在堆里创建了垃圾时会发生着种问题。例如，厦门的函数分配了一个堆块x，然后不释放就返回：

  void leak(int n) {
    int *x = (int *) malloc (n * sizoef(int));
    return;
  }

  • 如果经常调用leak，那么渐渐地，队里就会充满了垃圾，在最糟糕情况下会占用整个虚拟地址空间。对于像守护进程和服务器这样的程序来说，存储器泄露是特别严重的。

[wittyResry]

第七章 链接

动态链接共享库

• 共享库和Java本地接口：Java本地接口JNI（Java Native Interface），它允许Java程序调用“本地的”C和C++函数。JNI的基本思想是将本地C函数，如foo，编译到共享库中，如foo.so。当一个正在运行的Java程序调用foo时，Java解释程序利用dlopen接口（或者其他类似接口）动态链接和加载foo.so，然后调用foo。
• 链接相关的试验

[wittyResry]

第十章 系统级IO

• I/O是在主存和外部设置（磁盘驱动器、终端和网络）之间拷贝数据的过程。
• 输入操作是从I/O设备拷贝数据到主存。
• 输出操作是从主存拷贝数据到I/O设备。

Unix I/O

• 所有的I/O设备，如磁盘、网络和终端，都被模型化为文件的方式，都被当做对相应的文件读写来进行。
• 打开文件，若返回成功，则为新文件描述符，出错为-1。

#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
int open(char *filename, int flags, mode_t mode);
//O_RDONLY:只读;O_WRONLY:只写;O_RDWR:可读写。
fd = open("foo.txt", O_RDONLY, 0);
//O_CREAT:文件不存在，创建一个空文件;O_TRUNC:文件存在，则截断它;O_APPEND:在每次写之前，设置文件位置到文件的末尾处。
fd = open("foo.txt", O_WRONLY|O_APPEND, 0);

• 打开文件的mode表示新文件的访问位权限，采用S_IRUSR,S_IWUSR,S_IXUSR 使用者的读、写、执行;S_IRGRP,S_IWGRP,S_IXGRP分组拥有者的读写执行；S_IROTH,S_IWOTH,S_IXOTH其他（任何人）能够读、写、执行。

  • 文件的访问权限被置为mode & ~umask

  umask(DEF_UMASK);
  fd = open("foo.txt", O_CREAT|O_TRUNC|O_WRONLY, DEF_MODE);

• 关闭文件，关闭一个已经关闭的文件会出错.

#include <unistd.h>
int close(int fd);

• 读和写文件，调用read和write，如：

#include <unistd.h>
//若成功则返回为读的字节数，若EOF则为0，若出错为-1。
ssize_t read(int fd, void *buf, size_t n);
//若成功则返回为写的字节数，否则出错返回-1。
ssize_t write(int fd, const void *buf, size_t n);

RIO

• RIO表示健壮的读写，包括无缓冲I/O函数和带缓冲I/O函数。

RIO的无缓冲输入输出函数

• 调用rio_readn和rio_writen，可以在存储器和文件之间传输数据。

#include <csapp.h>
//从fd的当前文件位置最多传n个字节到存储器位置usrbuf
ssize_t rio_readn(int fd, void *usrbuf, size_t n);
//从usrbuf传送n个字节到描述符fd。
ssize_t rio_writen(int fd, void *usrbuf, size_t n);

RIO带缓冲的输入输出函数

//读一个文本行，并且拷贝到存储器位置usrbuf
void rio_readinitb(rio_t *rp, int fd);
//最多读maxlen
ssize_t rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen);
//从文件rp读n个字节到存储器位置usrbuf
ssize_t rio_readnb(rio_t *rp, void *usrbuf, size_t n);

ssize_t rio_readn(int fd, void *usrbuf, size_t n) {
    size_t nleft = n;
    ssize_t nread;
    char *bufp = usrbuf;
    while (nleft > 0) {
        if ((nread = read(fd, bufp, nleft)) < 0) {
            if (errno == EINTR) {
                nread = 0; /* and call read() again*/
            } else {
                reutrn -1; /* errno set by read()*/
            }
        } else if (nread == 0) {
            break;
        }
        nleft -= nread;
        bufp += nread;
    }
    return (n - nleft);
}

ssize_t rio_writen(int fd, void *usrbuf, size_t n) {
    size_t nleft = n;
    ssize_t nwritten;
    char *bufp = usrbuf;
    while (nleft > 0) {
        if ((nwritten = write(fd, bufp, nleft)) < 0) {
            if (errno == EINTR) {
                nwritten = 0; /* and call read() again*/
            } else {
                reutrn -1; /* errno set by read()*/
            }
        }
        nleft -= nwritten;
        bufp += nwritten;
    }
    return n;
}

• rio_read 和 Unix read 有一样的语义。在出错时，它返回值-1， 并且适当地设置errno。在EOF时，返回0。

#define RIO_BUFSIZE 8192
typedef struct {
    int rio_fd;   /* Descriptor for this internal buf */
    int rio_cnt;  /* Unread bytes in internal buf */
    char *rio_bufptr; /* Next unread byte in internal buf */
    char rio_buf[RIO_BUFSIZE]; /* Internal buffer */
} riot;
static ssize_t rio_read(rio_t *rp, char *usrbuf, size_t n) {
    int cnt;
    while (rp -> rio_cnt <= 0) {
        rp -> rio_cnt = read(rp -> rio_fd, rp -> rio_buf, sizeof(rp -> rio_buf));
        if (rp -> rio_cnt < 0) {
            if (errno != EINTR) {
                return -1;
            }
        } else if (rp -> rio_cnt == 0) {
            return 0;
        } else {
            rp -> rio_bufptr = rp -> rio_buf;
        }
    }
    cnt = n;
    if (rp -> rio_cnt < 0) {
        cnt = rp -> rio_cnt;
    }
    memcpy (usrbuf, rp -> rio_bufptr, cnt);
    rp -> rio_bufptr += cnt;
    rp -> rio_cnt -= cnt;
    return cnt;
}

ssize_t rio_readnb(rio_t *rp, void *usrbuf, size_t n) {
    size_t nleft = n;
    ssize_t nread;
    char *bufp = usrbuf;
    while (nleft > 0) {
        if ((nread = rio_read(rp, bufp, nleft)) < 0) {

            if (errno == EINTR) {
                return 0;  /*Call read() again*/
            } else {
                return -1; /* errno set by read() */
            }
        } else if (nread == 0) {
            break; /* EOF */
        }
        nleft -= nread;
        bufp += nread;
    }
    return (n - nleft);
}

ssize_t rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen) {
    int n, rc;
    char c, *bufp = usrbuf;
    for (n = 1; n < maxlen; ++n) {
        if ((rc = rio_read(rp, &c, 1)) == 1) {
            *bufp++ = c;
            if (c == '\n')
                break;
        } else if (rc == 0) {
            if (n == 1) {
                return 0; /* EOF, no data read */
            } else {
                break; /* EOF, some data read */
            }
        } else {
            return -1;
        }
    }
    *bufp = 0; /*设置行结尾ASCII = '\0'*/
    return n;
}

共享文件

• 数据结构
  • 描述符表(descriptor table)：每个进程一张表，表项是进程打开的文件索引
  • 文件表（file table):所有进程共享，包括当前文件的位置，引用计数，以及指向v-node表的指针。
  • 文件表（v-node table):所有进程共享，st_mode和st_size，st_type成员。
• 多个描述符可通过不同的文件表表项来引用同一个文件。