Ç - 存储器映射B树 [英] C - Memory map a B-Tree

问题描述

我试图内存，以B树存储数十亿键 - 值对映射一个巨大的文件（约100GB）。内存小的指针保存在内存中的所有数据，因此我试图从映射磁盘上的文件和，而不是使用malloc我回来，递增到映射区域。

I'm trying to memory map a huge file (approx. 100GB) in order to store a B-Tree with billions of key-value pairs. The memory is to small to keep all data in memory therefore I'm trying to map a file from disk and instead of using malloc I return and increment a pointer to the mapped region.

#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;
}

问题是，我收到无法分配内存（错误号为12 ）如果请求的尺寸比实际的内存或更大的分段故障如果请求的空间被映射的区域之外。我被告知，这是可能的映射比实际内存更大的文件。

The problem is that I receive Cannot allocate memory (errno is 12) if the requested size is bigger than the actual memory or a Segmentation fault if the requested space is outside of the mapped region. I was told that it is possible to map files bigger than the actual memory.

在该系统自行管理文件还是我负责映射只可用内存量和访问进一步的空间时，我不得不取消映射并映射到其他偏移。

Will the system manage the file by itself or am I responsible for mapping only the amount of free memory and when accessing further space I have to unmap and map to another offset.

感谢您

修改

操作系统：Ubuntu的LTS 14.04的x86_64

OS: Ubuntu 14.04 LTS x86_64

斌/洗衣机：ELF 64位LSB的可执行文件，X86-64，版本1（SYSV），动态链接（使用共享库），为GNU / Linux 2.6.24，BuildID [SHA1] = 9dc831c97ce41b0c6a77b639121584bf76deb47d，不可剥离

bin/washingMachine: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.24, BuildID[sha1]=9dc831c97ce41b0c6a77b639121584bf76deb47d, not stripped

推荐答案

首先，确保你是在64位CPU上以64位模式下运行。在32位CPU，你的进程的地址空间只有2 ³² 字节（4 GB的）大，有没有办法，以适应100 GB到所有的一次 - 有根本没有足够的地址。 （此外，该地址空间的一大块将​​已经由其他映射使用或由内核保留。）

First, make sure that you are running on a 64-bit CPU in 64-bit mode. On a 32-bit CPU, the address space of your process is only 2³² bytes (four gigabytes) large, and there's no way to fit 100 GB into that all at once -- there's simply not enough addresses. (In addition, a big chunk of that address space will already be used by other mappings or reserved by the kernel.)

第二，可能存在即使映射配合到地址空间的麻烦。被映射到进程内存（这也包括例如你的程序的code和数据段，以及同上共享库）被分裂成的页的（通常为4 KB大旺火上86台），其中每个页面需要在内核和 MMU 的一些元数据。这是可能创造巨大的内存映射时被耗尽其他资源。

Second, there might be trouble even if the mapping fits into the address space. Memory that is mapped into your process (this also includes e.g. your program's code and data segments, and ditto for shared libraries) is split up into units of pages (usually 4 KB large each on x86), where each page requires some metadata in the kernel and the MMU. This is another resource that might be exhausted when creating huge memory mappings.

如 mmap（）的整个大的文件建议，你可以尝试使用 MAP_SHARED 。这可能允许内核的映射分配内存懒洋洋地在它的网页被访问，因为它知道它总是可以在磁盘上掉了首页输出到文件中，如果有一个内存不足。随着 MAP_PRIVATE ，内核需要每一个页面被修改（因为变化不应该得到贯彻）的时间，这不会是安全的这样懒懒地分配了新的一页情况下，系统运行的内存和交换。

As suggested in Mmap() an entire large file, you could try using MAP_SHARED. That might allow the kernel to allocate memory for the mapping lazily as pages in it are accessed, since it knows it can always swap a page out to the file on disk if there's a memory shortage. With MAP_PRIVATE, the kernel needs to allocate a new page each time a page is modified (since the change should not be carried through), which would not be safe to do lazily in case the system runs out of memory and swap.

您可能还需要通过 MAP_NORESERVE 到 mmap（）的分配更多的内存比有物理内存时，或者设置的/ proc / sys目录/ VM / overcommit_memory （见 PROC（5））为1（这是一个有点丑陋由于被全系统虽然）。

You might also need to pass MAP_NORESERVE to mmap() when allocating more memory than there is physical memory, or set /proc/sys/vm/overcommit_memory (see proc(5)) to 1 (which is a bit ugly due to being system-wide though).

在我的系统，这是与8 GB的RAM和8 GB掉你类似的， MAP_SHARED 单独足以的mmap（） 40 GB的文件。 MAP_PRIVATE 与 MAP_NORESERVE 工作过一起。

On my system, which is similar to yours with 8 GB of RAM and 8 GB of swap, MAP_SHARED alone is sufficient to mmap() a 40 GB file. MAP_PRIVATE along with MAP_NORESERVE works too.

如果不工作，那么你很可能运行到一个MMU相关的限制。许多现代CPU架构支持的大内存页的，这比默认页面大小的页面。大页面的一点是，你需要更少的页面映射相同的内存量（假设大映射），从而降低了元数据的数量，可以使地址转换和上下文切换更高效。大页面的缺点是降低映射粒度，增加损耗（内部碎片）时，仅使用一个网页的一小部分。

If that doesn't work, then you're likely running into an MMU-related limit. Many modern CPU architectures support huge pages, which are pages larger than the default page size. The point of huge pages is that you need fewer pages to map the same amount of memory (assuming a large mapping), which reduces the amount of metadata and could make address translation and context switches more efficient. The downside of huge pages is decreased mapping granularity and increased wastage (internal fragmentation) when only a small portion of a page is used.

配对 MAP_SHARED ，并用大内存页一些随机的文件是不可能的方式（工作的情况下， MAP_SHARED ISN 'T不足以解决问题）。该文件将需要在 hugetlbfs的。

Pairing MAP_SHARED and some random file with huge pages is unlikely to work by the way (in case MAP_SHARED isn't enough to fix the problem). The file would need to be in a hugetlbfs.

传递 MAP_HUGETLB 到的mmap（）要求使用大内存页分配的（虽然它可能只是匿名映射，它也似乎那巨大的页面应该是自动的在许多系统上时下）。你也许有可能还需要淤泥与周围的/ proc / sys目录/ VM / nr_hugepages 和的/ proc / sys目录/ VM / nr_overcommit_hugepages - 见这个线程和
文档/ VM / hugetlbpage.txt 内核源文件。

Passing MAP_HUGETLB to mmap() requests allocation using huge pages (though it might just be for anonymous mappings, where it also 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 and the Documentation/vm/hugetlbpage.txt file in the kernel sources.

的写作时自己的内存分配器的的方式的对齐问题当心。我希望这不是太pluggish，但见这个答案。

Beware of alignment issues when writing your own memory allocator by the way. I hope this isn't too pluggish, but see this answer.

作为一个方面说明，你从一个内存映射文件访问的内存必须实际存在的文件中。如果该文件比映射小，你想成为能够仍然可以访问额外的内存，你可以先用长文件 ftruncate（2）。 （如果文件系统支持稀疏文件与文件孔这可能不会实际增加其大小要在磁盘上。 ）

As a side note, any memory you access from a memory-mapped file must actually exist in the file. If the file is smaller than the mapping and you want to be able to access the "extra" memory still, you could grow the file first using ftruncate(2). (This might not actually increase its size much on disk if the filesystem supports sparse files with file holes.)

这篇关于Ç - 存储器映射B树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！