c - 为什么这个程序分配了8页，但只能容纳2048个8字节的节点？

Question

节点定义如下:

    struct node {
      int value;
      struct node *next;
    };

通过使用 sizeof(struct node) 我了解到一个节点是 8 个字节(在 xv6 中)。所以我使用malloc分配了一些内存空间来存储一些节点。 xv6中单个页面是4096字节，如果我有8个页面，我可以存储4096个这样的节点。然而，这不是正在发生的事情，在我 malloc 2048 个这样的节点之后，如果我 malloc 另一个，更多的页面被分配给当前进程，这是为什么？

    // Now display how many pages are allocated to the process
    // Suppose there is a system call named memcount(), it is given by
    // my professor, I wouldn't think there's any problem with that
    //
    memcount(); // which prints 3, meaning that initially, without
                // allocaing anything, 3 pages = 12288 bytes of memory allocated

    for(i = 0; i < 2048; ++i) {
      struct node *nd = (struct node *) malloc(sizeof(struct node));
    }

    memcount(); // which prints 11, so 8 more pages are allocated

    // If we allocated 1 more node
    struct node *nd = (struct node *) malloc(sizeof(struct node));
    memcount(); // which prints 19, another 8 pages are allocated

这就是我很困惑的地方，前8页不应该留很多空间吗？既然单个节点的大小只有8字节，为什么还要分配给进程更多的页面？

Answer 1

评论中已经回答了这个问题:malloc() 需要一些空间来存储，Memory 是如何使用的。

内存处理程序将堆视为单个大字节数组(因为 RAM 在大多数内存模型中都是一个大数组)。 (还有其他内存模型或者内存管理器可能会在额外的页面中存储一些数据，但是为了简单起见，我们忽略这种情况)

例如，我们可以考虑系统，其中前 4 个字节用作指针 (p0)，下一个有效 block 从此处开始，接下来的 4 个字节用作变量 ( size_t, s0) 这个 block 使用了多少字节(我们需要 2 个变量来检测 2 个 block 之间的 block 何时被释放)。下一个 block 还有一个指向下一个(下一个的下一个) block 的指针 (p1) 和一个表示 block 大小的变量 (s1)

在此 header 之后是您可以使用的数据，malloc() 返回指向此 header 后第一个字节的指针。变量 s0 将存储您请求的字节数。在一个新的malloc()之后，第一个 block 之后会创建一个新的header，p0会指向这个header:

Address:   0x10    0x14    0x18    0x1B    0x20    0x24    0x28 ...
Name:      p0      s0      value   next    p1      s1      value...
Value:     0x20    8       ??      0x28    0       8       ??

这是你分配了2个block后的情况，p1和s1是第二个block的header的变量。您只能使用变量 next 和 value。 malloc()返回的指针是0x18和0x28。

为了避免为内存处理程序使用一半的空间，您可以一步分配一个更大的数组。您可以像这样使用 struct:

struct Node_T
  {
    int values[512];
    size_t usedValues;  
    struct Node_T *next;
  }

那么你将需要 4*4 = 16 字节的总开销(包括内存处理程序的开销，并假设内存处理程序需要每个 block 8 字节的 header 和 int、指针和 size_t 是 4 个字节)。但是当您在其他值之间删除或添加一个值时，您需要额外的复制或移动开销。