內存分配器的「殺手對手」？

在閱讀this question關於Windows內存分配器看似簡併的行爲後，記住回到this paper關於構建快速排序實現的最壞情況輸入，我開始懷疑：是否有可能構建一個程序，給定一個黑盒內存分配器強制分配器即使在系統中仍有足夠的內存時也會失敗分配請求？也就是說，是否有可能採用黑盒內存分配器並強制其失敗？內存分配器的「殺手對手」？

我知道這可以通過在棋盤格式中分配和釋放內存來強制實現大規模碎片來完成，所以在我看來，一個理想的解決方案會導致在故障發生時分配的字節數最少而失敗。關於啓發這一點的原始帖子，如果內存分配程序存在內部錯誤，理論上可能導致分配零字節失敗。

關於如何做到這一點的任何想法/想法？

來源

2011-03-24 templatetypedef

用黑匣子指定你的意思。對手是否可以訪問分配的地址？ – 2011-03-24 21:49:05

是的，您可以查看已分配的地址，但無法確定，例如，塊大小是多少，或者塊被分組到哪些列表中。 – templatetypedef 2011-03-24 22:06:52

糟糕，一個邪惡的問題。 +1。 – 2011-03-25 01:10:39

取決於「足夠的可用內存」的含義。對於一個簡單的碎片「攻擊」：

做一個squillion small分配到一個失敗[*]。
現在，按照地址[**]的順序對它們進行排序。
免費100個備用分配。
嘗試分配100*small字節。

機會是分配器將無法找到連續的內存來滿足這一點。如果它具有small頁面大小以及與物理內存相比足夠多的虛擬地址空間，那麼它可能能夠重新安排這些操作 - 但這需要MMU在分配器的任何防碎片策略之上的功能。

如果通過「足夠的可用內存」，您的意思是以前是連續塊的內存塊已被分割成幾個分配，所有這些分配都已被釋放，現在分配器將其視爲單獨的塊，所以不能分配large字節然後不，我不認爲你可以強制一個任意的塊分配器不能合併塊。一些分配器或其他可能會做比Windows更好的工作，以保證相鄰的空閒塊總是合併在一起。

[*]可能的問題 - 過度提交的內存分配器可能不會失敗，您只會遇到段錯誤或者您的進程被終止。在這樣的系統上，您可能需要跟蹤有多少內存可用。

[**]可能的問題 - 在C和C++中，operator<不能保證工作。但是在幾乎所有的系統上，在C++中也有std::less。

來源

2011-03-24 09:47:17

內存分配器的「殺手對手」？

回答

相關問題