进程可以在mmappedspace的中间插入内存页吗？
Can process insert memory pages in the middle of mmapped space?
提炼场景：
用户 space 程序需要数百万页大小的结构（即大多数 Linux 系统需要 4k）。它还需要快速随机访问结构。有时程序需要在数组中间插入新的结构。顺序很重要。
struct { char data[PAGE_SIZE]; } page_sized_t;
size_t N = 1 * 1000 * 1000;
size_t X = INSERT_INDEX;
可以使用包含指向堆分配结构指针的堆分配数组来实现程序。 Insert 可以用 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]) );
...
现在我的问题是这个。就拥有一个大的内存映射区域而言，实现这样一个程序是否可行。每个结构都位于单个页面中。然后插入可以这样实现：程序可以要求内核在其他页面之间插入新页面。基本上内核完成了上一段中描述的工作。
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]) );
...
我认为使用当前的系统调用是不可能的。只能 mremap - 所以在某种程度上只能在末尾插入页面。
总结：Linux内核可以实现内存页的插入吗？使用这样的接口而不是用户 space 实现是否可行？有实现此功能的系统吗？
Program could be implemented with having an heap allocated array containing pointers to heap allocated structs. Insert could be implemented with realloc and memmove.
如果您已经有了一个指向结构的指针数组，为什么还要在内存中移动这些结构呢？只需更新指针即可。在内存中连续修改一百万个条目总是比修改一百万页 table 个条目更有效。
始终通过数组中的索引引用结构，而不是通过指针。这样您就可以始终按顺序遍历数组，即使结构在内存中不连续。
Would it be practical to implement such a program in terms of having one big mmapped region of memory.
没有。用您自己的话说，每个结构有一页。要在中间插入一个页面，页面的其余部分 table 条目需要更新。那会很慢。
如果你通过间接指针定位每个结构，即你有
struct page_sized_t **array;
那就没有真正的理由来移动内容；只需更新指针。是的，这意味着要使用 i < j 将项目 j 移动到索引 i，您需要
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 * 类型，因此这会移动指针，而不是内容。修改指针总是比修改尽可能多的页面 table 条目要快。 （即使使用大页面，根据需要将它们 coalesce/split 到普通页面所需的逻辑几乎肯定是不切实际的。您可以设计一个微基准测试，它的性能比简单的 memmove 更好（尽管如果您这样做了，我会感到惊讶），但在所有现实生活场景中，此类页面 table 恶作剧只会增加开销。
Could inserting of memory pages be implemented in Linux kernel? Would it be practical to use such an interface instead of user space implementation?
您已经可以通过 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()），否则内核可能会为其他内存分配调用提供 "hole" , 打破计划。这完全是一个用户空间问题，在单线程应用程序中应该很容易实现（因为在信号处理程序中使用任何内存分配函数都不是异步信号安全的），但对于多线程程序来说可能很难甚至不可能——甚至一些 C 库函数也做 implicit/internal 动态内存分配。
总结：
无论您在做什么，看起来您都没有使用最有效的数据结构，因此，在错误的地方寻找加速。特别是，需要 direct/random 访问内容并不意味着您应该使用线性数组。
由于您没有提供足够的信息甚至无法提出建议，我只想指出具有页面大小的结构本身就是一个不好的迹象。数据库使用索引（其中对应于单个 key/field 的值是连续的（至少在某种意义上）以便更快地访问（和整理）。因此，除非您对每个结构的访问确实确实通常需要结构中的所有数据, 你最好把它分成单独的数组。
提炼场景：
用户 space 程序需要数百万页大小的结构（即大多数 Linux 系统需要 4k）。它还需要快速随机访问结构。有时程序需要在数组中间插入新的结构。顺序很重要。
struct { char data[PAGE_SIZE]; } page_sized_t;
size_t N = 1 * 1000 * 1000;
size_t X = INSERT_INDEX;
可以使用包含指向堆分配结构指针的堆分配数组来实现程序。 Insert 可以用 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]) );
...
现在我的问题是这个。就拥有一个大的内存映射区域而言，实现这样一个程序是否可行。每个结构都位于单个页面中。然后插入可以这样实现：程序可以要求内核在其他页面之间插入新页面。基本上内核完成了上一段中描述的工作。
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]) );
...
我认为使用当前的系统调用是不可能的。只能 mremap - 所以在某种程度上只能在末尾插入页面。
总结：Linux内核可以实现内存页的插入吗？使用这样的接口而不是用户 space 实现是否可行？有实现此功能的系统吗？
Program could be implemented with having an heap allocated array containing pointers to heap allocated structs. Insert could be implemented with realloc and memmove.
如果您已经有了一个指向结构的指针数组，为什么还要在内存中移动这些结构呢？只需更新指针即可。在内存中连续修改一百万个条目总是比修改一百万页 table 个条目更有效。
始终通过数组中的索引引用结构，而不是通过指针。这样您就可以始终按顺序遍历数组，即使结构在内存中不连续。
Would it be practical to implement such a program in terms of having one big mmapped region of memory.
没有。用您自己的话说，每个结构有一页。要在中间插入一个页面，页面的其余部分 table 条目需要更新。那会很慢。
如果你通过间接指针定位每个结构，即你有
struct page_sized_t **array;
那就没有真正的理由来移动内容；只需更新指针。是的，这意味着要使用 i < j 将项目 j 移动到索引 i，您需要
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 * 类型，因此这会移动指针，而不是内容。修改指针总是比修改尽可能多的页面 table 条目要快。 （即使使用大页面，根据需要将它们 coalesce/split 到普通页面所需的逻辑几乎肯定是不切实际的。您可以设计一个微基准测试，它的性能比简单的 memmove 更好（尽管如果您这样做了，我会感到惊讶），但在所有现实生活场景中，此类页面 table 恶作剧只会增加开销。
Could inserting of memory pages be implemented in Linux kernel? Would it be practical to use such an interface instead of user space implementation?
您已经可以通过 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()），否则内核可能会为其他内存分配调用提供 "hole" , 打破计划。这完全是一个用户空间问题，在单线程应用程序中应该很容易实现（因为在信号处理程序中使用任何内存分配函数都不是异步信号安全的），但对于多线程程序来说可能很难甚至不可能——甚至一些 C 库函数也做 implicit/internal 动态内存分配。
总结：
无论您在做什么，看起来您都没有使用最有效的数据结构，因此，在错误的地方寻找加速。特别是，需要 direct/random 访问内容并不意味着您应该使用线性数组。
由于您没有提供足够的信息甚至无法提出建议，我只想指出具有页面大小的结构本身就是一个不好的迹象。数据库使用索引（其中对应于单个 key/field 的值是连续的（至少在某种意义上）以便更快地访问（和整理）。因此，除非您对每个结构的访问确实确实通常需要结构中的所有数据, 你最好把它分成单独的数组。