可以处理在mmapped空间的中间插入内存页面吗？

Question

蒸馏场景：

用户空间程序需要数百万页大小的结构（即大多数Linux系统需要4k）。它也需要快速随机访问结构。有时候程序需要在数组中间插入新的结构。订单很重要。

struct { char data[PAGE_SIZE]; } page_sized_t; 
size_t N = 1 * 1000 * 1000; 
size_t X = INSERT_INDEX; 

程序可以实现一个堆分配数组包含指向堆分配结构的指针。插入可以用realloc和memmove来实现。

struct page_sized_t **array = malloc(sizeof(array[0]) * N); 
... 
array = realloc(array, sizeof(array[0]) * (N+1)); 
memmove(&array[X+1], &array[X], N-X); 
array[X] = malloc(sizeof(array[X][0])); 
... 

现在我的问题是这样的。实施这样一个程序是否具有一个大的mmap区域内存是可行的。每个结构都放在单​​页中的地方。然后插入可以这样实现：程序可以让内核在其他人之间插入新页面。基本上，内核负责完成上一段所述的工作。

struct page_sized_t *array = mmap(0, sizeof(array[0]) * N, 
            PROT_READ|PROT_WRITE, MAP_ANONYMOUS, -1, 0); 
... 
// imaginary syscall: m_insert_map(old_address, old_size, insert_address, insert_size) 
array = m_insert_map(array, sizeof(array[0]) * N, sizeof(array[0]) * X, sizeof(array[0])); 
... 

我认为，目前的系统调用是不可能的。人们只能映射 - 所以在某种程度上只能在最后插入页面。

总结：可以在Linux内核中插入内存页吗？使用这样的接口而不是用户空间实现是否可行？有没有一个系统实现了这个功能？

Answer 1

程序可以通过具有包含指向堆分配结构的指针的堆分配数组来实现。插入可以用realloc和memmove来实现。

如果你已经有了一个指向数组结构的指针数组，为什么你会把所有的结构都移到内存中呢？只需更新指针即可。在内存中连续修改数百万个条目总是比修改一百万个页面条目更有效。

始终通过数组中的索引引用结构，而不是通过指针。这样，即使结构在内存中不连续，您也可以按顺序遍历数组。

实现这样一个程序是否具有一个大的mmapped区域的内存。

否。按照您自己的说法，您每个结构都有一个页面。要在中间插入一个页面，其余的页表条目需要更新。那会很慢。

如果通过间接指针定位每个结构反正，即你有

struct page_sized_t **array; 

那么有没有真正的理由来移动内容;只是更新指针。是的，这意味着，项目j移到指数i，与i < j，你需要

struct page_sized_t *temp = array[j]; 
memmove(array + i + 1, array + 1, (j - i) * sizeof array[0]); 
array[i] = temp; 

注意array[j]是struct page_sized_t *型的，所以这四处移动指针，而不是内容。修改指针总是比修改尽可能多的页表条目快。（即使使用了大量的页面，根据需要将逻辑合并/拆分成普通页面几乎肯定是不切实际的，您可能可以设计一个比简单的移动更好的微型基准（尽管如果你这样做了，会惊讶了我的袜子），但在所有的现实生活场景，例如页表有心计只是增加开销。

可能的内存页插入在Linux内核中实现？难道是实际使用这样的接口而不是用户空间实现？

你已经可以通过mremap()做到这一点。

您使用mremap(array + index, pagesize * (size - index), pagesize * (size - index + 1), MREMAP_FIXED, array + index + 1)重新映射从插入点开始的区域。然后，您使用mremap(array, pagesize * index, pagesize * (index + 1), 0)来扩大初始部分以覆盖该孔，或者使用mmap(array + index, pagesize, PROT_READ | PROT_WRITE, MAP_PRIVATE, -1, 0)来堵塞该孔。

这是很相似，你会怎么做使用memmove()同样的事情，真的。

但是，在两次调用期间，您必须确保没有其他线程会进行新的内存分配（通过mmap()），否则内核可能会为其他内存分配调用提供“空洞”，从而破坏该方案。这完全是一个用户空间问题，在单线程应用程序中实现应该是微不足道的（因为它在信号处理程序中使用任何内存分配函数时不是异步信号安全的），但对于多线程程序可能很难甚至不可能 - 甚至一些C库函数也会执行隐式/内部动态内存分配。

总结：

不管你在做什么，它看起来像您不使用最有效的数据结构，正因为如此，正在寻找在错误的地方的加速。特别是，需要直接/随机访问内容并不意味着你应该使用线性数组。

既然你还没有提供足够的信息来提供一个手工的建议，我会指出拥有页面大小的结构本身就是一个坏迹象。数据库使用索引（其中对应于单个键/字段的值是连续的（从某种意义上说，至少）是为了更快的访问（和排序）。因此，除非您访问每个结构通常需要结构中的所有数据，否则可能会更好地将它分成独立的阵列。