¿Un "adversario asesino" para los asignadores de memoria?

Question

Después de leer this question acerca del comportamiento aparentemente degenerado para el asignador de memoria de Windows, y recordando a this paper sobre la construcción de las entradas de peor caso para implementaciones de quicksort, comencé a preguntarme: ¿sería posible construir un programa que, dado una memoria de caja negra asignador, obliga a que asignador falle una solicitud de asignación incluso cuando todavía hay suficiente memoria disponible en el sistema? Es decir, ¿es posible tomar un asignador de memoria de caja negra y forzarlo a fallar?

Sé que esto se puede hacer asignando y liberando memoria en un patrón de tablero de ajedrez para forzar la fragmentación masiva, por lo que una solución ideal causaría una falla con el menor número total de bytes asignados en el momento de la falla . Con respecto a la publicación original que inspiró esto, en teoría podría ser posible causar una falla con cero bytes asignados si el asignador de memoria tiene una falla interna.

¿Alguna idea/idea sobre cómo hacer esto?

Answer 1

Depende de lo que quiere decir con "suficiente memoria disponible". Para una fragmentación simple "ataque":

• Hacer una squillion small asignaciones hasta que una falla [*].

• Ahora, ordénelas por orden de dirección [**].

• Gratis 100 asignaciones alternativas.

• Intento de asignar 100*small bytes.

Las posibilidades son que el asignador no podrá encontrar la memoria contigua para satisfacer eso. Si tiene un tamaño de página small, y un montón de espacio de direcciones virtuales en comparación con la memoria física, entonces podría ser capaz de reorganizar las cosas para hacerlo, pero eso requiere capacidades de la MMU sobre cualquier estrategia de antifragmentación por parte del asignador.

Si por "suficiente memoria disponible" se entiende un bloque de memoria large que anteriormente era un bloque contiguo, se ha dividido en varias asignaciones, todas liberadas desde entonces, y ahora el asignador las trata como bloques separados y así que no puede asignar large bytes, entonces no, no creo que pueda forzar a un asignador de bloques de bloques arbitrario a no fusionar bloques. Algún asignador u otro podría hacer mucho más trabajo de lo que Windows parece estar haciendo en esa otra cuestión, para garantizar que los bloques libres adyacentes siempre se fusionen.

[*] posible problema: los asignadores de memoria excesivamente comprometidos pueden no fallar, solo obtiene un segfault o su proceso se cancela. En tales sistemas, es posible que necesite realizar un seguimiento de la cantidad de memoria disponible.

[**] posible problema - en C y C++, operator< no se garantiza que funcione. Pero en casi todos los sistemas lo hace, y en C++ también hay std::less.