在Linux/C/C++中，我想要一个任意大小的缓冲区。

Question

基本上我想要一个任意大的堆栈。我知道这不可能，但我能为它分配几个 terabytes 的虚拟地址空间吗？我希望能从开头开始并向上遍历缓冲区直到需要的程度，Linux 可以按需从物理内存中调入页面。这种做法是否可行？与仅 malloc 一个缓冲区的性能相同吗？有没有一种方法可以向 Linux 发出信号，告诉他在弹出堆栈后你已经完成了内存操作？

编辑：我想要做到这一点是因为我想优化递归/并行算法，在每个调用中分配大量内存。Malloc 对我来说太慢了，我不希望所有线程在 malloc 的锁定内互相干扰。所以基本上它将是我的自己运行时堆栈与真正的堆栈（每个线程一个）。

实际上，只要运行时堆栈足够大，那就足够好了。有没有一种方法可以知道/确保堆栈的大小？在 64 位地址空间中，有足够的空间让几个线程堆栈分配 gigabytes 的数据。这可行吗？

看起来 pthread_attr_setstacksize 可以用于新线程，但如果可以从任何线程调用，那就没有什么帮助了...

- Chris

---

std::stack有什么问题吗？ - tenfour

我建议，如果您想要一个任意大的堆栈，您应该直接请求它，而不是请求您认为合适的方式。还是说有其他限制条件？ - dmckee --- ex-moderator kitten

Answer 1

如果您需要一个大的堆栈，您可以更改ulimit -s。在64位平台上，它可以非常大。

如果您使用mmap匿名空间，则实际上不会分配物理页面直到您触及它。您需要设置vm_overcommit或拥有足够的交换空间（除非您有那么多物理RAM）。当然，当您请求大量内存时，mmap匿名空间正是malloc所做的。

您可以使用madvise告诉Linux您已经完成了这些页面。如果您调用MADV_DONTNEED，那么Linux将丢弃这些页面，下次尝试访问它们时应该填充为零。

- derobert

---

那么如果我设置了vm_overcommit，然后mmap()了一太字节的匿名空间，我就可以开始使用它了吗？madvise有很多开销吗（因为它会将页面填充为零）？ - Chris

@Chris：零填充实际上是在您首次访问页面时完成的。它可以被关闭，但通常出于安全原因而执行此操作-以确保一个进程（或内核）释放的内存不能被另一个进程读取。还要记住，vm_overcommit无法防止您实际上耗尽内存（如果您没有1TB的RAM /交换空间），并且您尝试访问所有这些内容，可能的结果是SIGKILL。 - derobert

太棒了，谢谢！我看了一下madvise()函数，但似乎没有找到一种方法来告诉系统“我已经用完这些页面，如果系统需要空间，请将它们清除掉，而且不要将它们复制到交换空间中。”看起来这种操作可能不被支持... - Chris

@Chris：这就是MADV_DONTNEED的作用。假设内核回收了这些页面（如果有任何内存压力，甚至可能没有）：如果您映射了实际文件，则下次使用这些页面时，文件将被重新读取；如果您映射了匿名空间（使用MAP_ANONYMOUS），则下次读取这些页面时，它们将被填充为零（以避免暴露先前内容，物理RAM上可能最后被不同应用程序使用）。 - derobert

请注意，即使禁用了过度承诺，您仍可以使用MAP_NORESERVE标志来请求在特定映射上的过度承诺行为。 - caf

Answer 2

首先，用malloc分配这么大的内存（或者使用new，或者在栈上创建）几乎肯定会导致std::bad_alloc错误，因为你试图在连续的内存中创建它-由于碎片化，你肯定没有那么多不间断的、连续的内存。

如果你使用一个std::容器，比如一个deque或一个容器适配器，比如一个stack（任何没有连续内存的东西-即不是向量），那么它将使用可扩展的堆内存。这将避免那个bad_alloc错误。

所以，这是可能的，但不要试图使内存连续-如果你被允许使用一个std::容器/适配器。

PS：如果你需要大内存空间，你可以考虑使用动态分配缓冲区的列表（malloc的指针），这些缓冲区的大小足够大以便使用，但足够小以免触发bad_alloc异常。

- John Humphreys

---

这在64位Linux上不是真的。假设您有交换（或物理内存）来支持它，几TB的连续地址空间不是问题。 - derobert

我曾经也这样认为Windows，虽然我没有任何证据来支持它。这不是我们拥有虚拟内存的重要原因之一吗？我知道我以前在我的32位Windows机器上分配了2GB向量。 - Mooing Duck

也许，我在分配比我们工作中使用的类似Linux的安装程序上更小的空间时，遇到了几次bad_alloc。我想这比我意识到的更具平台特定性。 - John Humphreys

你可能设置了一些资源限制，或者可能关闭了vm_overcommit并且没有足够的交换空间来启用它。但是在当前64位处理器拥有的256TiB虚拟地址空间中找到几个TiB不应该很难。 - derobert

Answer 3

不要忘记，资源总是受物理限制的：宇宙中的原子数量可能是有限的...因此，任意大的缓冲区在严格意义上不能存在...

然而，您可以使用Linux mmap系统调用将文件的一部分视为虚拟内存段。如果它非常大（比RAM大），您将遇到性能问题。考虑使用madvise（和也许readahead）系统调用进行调整。

甚至使用GCC __bultin_prefetch函数可能会有用（但我确信madvise更相关）。

如果您真的有一个大小为1TB的堆栈，则调整应用程序将非常重要。学习使用oprofile。我希望您有一台强大的机器！

这对于调用堆栈来说并不足够（它可能是有限的，例如通过setrlimit...）另请参见sigaltstack（用于信号传递的堆栈）。

但你真正想要实现什么？非常大的调用堆栈对我来说似乎有些可疑...或者你的堆栈不是调用堆栈吗？

- Basile Starynkevitch

---

他根本没有提到"调用栈"这个词。只是一个栈而已。 - Mooing Duck

Answer 4

您可以使用mmap()和MAP_ANONYMOUS | MAP_NORESERVE | MAP_PRIVATE标志创建这样的分配。当您想要将其释放回系统时，请使用munmap()。

请注意，您唯一能够发现可用内存不足以满足实际使用的方法是通过您的进程接收到SIGSEGV - 但这是请求比可用内存大得多的巨大映射的必然结果。

- caf

Answer 5

Create stack using two queues in that way you can have variable length of stack, which will increase as you require.

implementing stack using two queues

initially q1 is full and q2 empty
1] tranfer elements from q1 to q2 till last element left in q1
2] loop till q2 is not empty
deque element from q2 and again push in q2 till last element is left in q2
transfer this last element in q1
reduce size of q2 by 1
3]finally q1 contains all elements in reverse order as in stack
eg

1]
q1 = 1 2 3 4
q2 =
2]
3 deques till last element left in q1
q1 = 4
q2 = 1 2 3
3]
deque and again queue q2 till last element left
q1 = 4
q2 = 3 1 2
4] deque q2 and queue q1
q1 = 4 3
q2 = 1 2
5] again
deque and queue q2 till last element left
q1= 4 3
q2= 2 1
6] queue q1
q1= 4 3 2
7] queue last element of q2 to q1
q1= 4 3 2 1 

- Infinity