C - 内存映射B树

Question

我正在尝试记忆映射一个巨大的文件(大约100GB),以便存储具有数十亿个键值对的B树.内存很小,以便将所有数据保存在内存中,因此我正在尝试从磁盘映射文件而不是使用malloc我返回并递增指向映射区域的指针.

#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] = '\0';

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

    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)Segmentation fault.有人告诉我,可以映射大于实际内存的文件.

系统是自己管理文件还是我负责只映射可用内存量,当访问更多空间时我必须取消映射并映射到另一个偏移量.

谢谢

编辑

操作系统: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

首先,确保在64位模式下运行64位CPU.在一个32位CPU上,进程的地址空间只有2 ³²字节(4千兆字节),并且没有办法同时将100 GB放入其中 - 根本没有足够的地址.(此外,该地址空间的一大块将被其他映射使用或由内核保留.)

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

正如Mmap()中建议的整个大文件,您可以尝试使用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架构都支持大页面,这些页面大于默认页面大小.大页面的要点是您需要更少的页面来映射相同数量的内存(假设大型映射),这样可以减少元数据的数量,并可以提高地址转换和上下文切换的效率.当只使用一小部分页面时,大页面的缺点是减少了映射粒度和增加的浪费(内部碎片).

配对MAP_SHARED和一些带有大页面的随机文件不太可能顺便使用(如果MAP_SHARED不足以解决问题).该文件需要在hugetlbfs中.

传递MAP_HUGETLB到mmap()使用大内存页(虽然它可能只是匿名映射,它也请求分配似乎是巨大的页面应该是自动的在许多系统现在).您可能还需要使用/proc/sys/vm/nr_hugepages和/proc/sys/vm/nr_overcommit_hugepages- 查看此线程和 内核源文件中的Documentation/vm/hugetlbpage.txt文件.

顺便编写自己的内存分配器时要注意对齐问题.我希望这不是太插电,但看到这个答案.

作为旁注,您从内存映射文件访问的任何内存必须实际存在于文件中.如果文件小于映射并且您希望仍能访问"额外"内存,则可以首先使用该文件ftruncate(2).(如果文件系统支持带有文件漏洞的稀疏文件,这实际上可能不会在磁盘上大大增加它的大小.)