C - 内存映射一个 B 树

Question

我正在尝试对一个巨大的文件（大约 100GB）进行内存映射，以便存储具有数十亿个键值对的 B 树。内存太小，无法将所有数据保存在内存中，因此我试图从磁盘映射文件，而不是使用 malloc I return 并增加指向映射区域的指针。

#define MEMORY_SIZE 300000000

unsigned char *mem_buffer;
void *start_ptr;

void *my_malloc(int size) {
    unsigned char *ptr = mem_buffer;
    mem_buffer += size;

    return ptr;
}

void *my_calloc(int size, int object_size) {
    unsigned char *ptr = mem_buffer;
    mem_buffer += (size * object_size);

    return ptr;
}

void init(const char *file_path) {
    int fd = open(file_path, O_RDWR, S_IREAD | S_IWRITE);

    if (fd < 0) {
        perror("Could not open file for memory mapping");
        exit(1);
    }

    start_ptr = mmap(NULL, MEMORY_SIZE, PROT_READ | PROT_WRITE, MAP_PRIVATE, fd, 0);
    mem_buffer = (unsigned char *) start_ptr;

    if (mem_buffer == MAP_FAILED) {
        perror("Could not memory map file");
        exit(1);
    }

    printf("Successfully mapped file.\n");
}

void unmap() {
    if (munmap(start_ptr, MEMORY_SIZE) < 0) {
        perror("Could not unmap file");
        exit(1);
    }

    printf("Successfully unmapped file.\n");
}

主要方法：

int main(int argc, char **argv) {

    init(argv[1]);

    unsigned char *arr = (unsigned char *) my_malloc(6);
    arr[0] = 'H';
    arr[1] = 'E';
    arr[2] = 'L';
    arr[3] = 'L';
    arr[4] = 'O';
    arr[5] = '[=11=]';

    unsigned char *arr2 = (unsigned char *) my_malloc(5);
    arr2[0] = 'M';
    arr2[1] = 'I';
    arr2[2] = 'A';
    arr2[3] = 'U';
    arr2[4] = '[=11=]';

    printf("Memory mapped string1: %s\n", arr);
    printf("Memory mapped string2: %s\n", arr2);

    struct my_btree_node *root = NULL;

    insert(&root, arr, 10);
    insert(&root, arr2, 20);

    print_tree(root, 0, false);

//  cin.ignore();

    unmap();

    return EXIT_SUCCESS;
}

问题是，如果请求的大小大于实际内存，我会收到 Cannot allocate memory（errno 是 12），如果请求 space 在映射区域之外。有人告诉我可以映射比实际内存更大的文件。

系统会自己管理文件，还是我只负责映射空闲内存量，当进一步访问时space我必须取消映射并映射到另一个偏移量。

谢谢

编辑

OS: Ubuntu 14.04 LTS x86_64

bin/washingMachine：ELF 64 位 LSB 可执行文件，x86-64，版本 1 (SYSV)，动态链接（使用共享库），适用于 GNU/Linux 2.6.24，BuildID[sha1] =9dc831c97ce41b0c6a77b639121584bf76deb47d，未剥离

Answer 1

在不知道您使用的是什么操作系统的情况下，我的最佳猜测是您的操作系统不允许无限制地过量使用内存，或者它会根据 RLIMIT_DATA ulimit 计算 MAP_PRIVATE 映射.两者都意味着您的代码无法正常工作。

你基本上用 MAP_PRIVATE 告诉 mmap 的是 "map this file, but any changes that I do in the mapped area, treat them like local memory allocations in this program"。在这种情况下映射文件的技巧是，如果运行内存不足，您允许操作系统将页面写出到磁盘。因为你告诉操作系统不允许写东西，所以它不能那样做。

解决方案是使用 MAP_SHARED，但请确保您了解 mmap 的手册页以及 MAP_SHARED 的作用。另外，请确保您只映射文件的大小，或者 ftruncate 文件的大小与您需要的一样大。

此外，请阅读 mmap 手册页中有关长度参数的信息。某些操作系统允许大小不是页面大小的倍数，但这是非常不可移植的，将您的大小四舍五入为页面大小。

Answer 2

首先，确保您在 64 位 CPU 64 位模式下运行。在 32 位 CPU 上，您的进程的地址 space 只有 2³² 字节（4 GB）大，并且没有办法容纳 100 GB一次全部进入 - 根本没有足够的地址。（此外，该地址的一大块 space 将已被其他映射使用或被内核保留。）

其次，即使映射适合地址space，也可能会出现问题。映射到您的进程的内存（这也包括例如您的程序的代码和数据段，以及共享库的同上）被分成页的单元（在 x86 上通常每个单元大 4 KB） )，其中每个页面都需要内核和 MMU 中的一些元数据。这是创建巨大内存映射时可能耗尽的另一种资源。

如 Mmap() an entire large file 中所建议，您可以尝试使用 MAP_SHARED。这可能允许内核在访问其中的页面时为映射延迟分配内存，因为它知道如果内存不足，它总是可以将页面换出到磁盘上的文件。使用 MAP_PRIVATE，内核需要在每次修改页面时分配一个新页面（因为更改不应该被执行），如果系统内存和交换耗尽，懒惰地这样做是不安全的.

当分配的内存多于物理内存时，您可能还需要将 MAP_NORESERVE 传递给 mmap()，或者将 /proc/sys/vm/overcommit_memory（参见 proc(5)）设置为 1 (由于在系统范围内，这有点难看）。

我的系统与您的系统类似，具有 8 GB RAM 和 8 GB 交换空间，仅 MAP_SHARED 就足以 mmap() 一个 40 GB 的文件。 MAP_PRIVATE 与 MAP_NORESERVE 一起工作。

如果这不起作用，那么您可能运行进入了与 MMU 相关的限制。许多现代 CPU 架构支持 huge pages，即大于默认页面大小的页面。大页面的要点是您需要更少的页面来映射相同数量的内存（假设一个大映射），这减少了元数据的数量并且可以使地址转换和上下文切换更有效。大页面的缺点是当只使用页面的一小部分时会降低映射粒度并增加浪费（内部碎片）。

配对 MAP_SHARED 和一些带有大页面的随机文件不太可能顺便工作（以防 MAP_SHARED 不足以解决问题）。该文件需要位于 hugetlbfs.

中

将 MAP_HUGETLB 传递给 mmap() 请求使用大页面分配（尽管它可能只是用于匿名映射，其中它也 seems that huge pages should be automatic on many systems nowadays). You might potentially also need to muck around with /proc/sys/vm/nr_hugepages and /proc/sys/vm/nr_overcommit_hugepages -- see this thread 和 Documentation/vm/hugetlbpage.txt 内核源文件中的文件。

顺便提一下，编写自己的内存分配器时要注意对齐问题。我希望这不会太卡，但请参阅。

附带说明一下，您从内存映射文件访问的任何内存都必须实际存在于该文件中。如果文件小于映射并且您仍希望能够访问 "extra" 内存，则可以先使用 ftruncate(2) 增大文件。（如果文件系统支持 sparse files 文件漏洞，这实际上可能不会增加它在磁盘上的大小。）

C - 内存映射一个 B 树

C - Memory map a B-Tree

c

mmap