¿Malloc crea perezosamente las páginas de respaldo para una asignación en Linux (y otras plataformas)?

9. Memoria (parte de El núcleo Linux, Algunas observaciones sobre el Kernel de Linux por Andries Brouwer) es un buen documento.

Contiene los siguientes programas que demuestran el manejo de Linux de la memoria física frente a la memoria real y explica el funcionamiento interno del núcleo.

Normalmente, el primer programa de demostración obtendrá una gran cantidad de memoria antes de que malloc() devuelva NULL. El segundo programa de demostración obtendrá una cantidad mucho menor de memoria, ahora que la memoria obtenida anteriormente se utiliza realmente. El tercer programa obtendrá la misma gran cantidad que el primer programa, y luego se mata cuando quiere usar su memoria.

Programa de demostración 1: asignar memoria sin usarla.

#include <stdio.h>
#include <stdlib.h>

int main (void) {
    int n = 0;

    while (1) {
        if (malloc(1<<20) == NULL) {
                printf("malloc failure after %d MiB\n", n);
                return 0;
        }
        printf ("got %d MiB\n", ++n);
    }
}

Programa de demostración 2: asignar memoria y realmente tocar todo.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main (void) {
    int n = 0;
    char *p;

    while (1) {
        if ((p = malloc(1<<20)) == NULL) {
                printf("malloc failure after %d MiB\n", n);
                return 0;
        }
        memset (p, 0, (1<<20));
        printf ("got %d MiB\n", ++n);
    }
}

Programa de demostración 3: primero asignar, y utilizar más tarde.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define N       10000

int main (void) {
    int i, n = 0;
    char *pp[N];

    for (n = 0; n < N; n++) {
        pp[n] = malloc(1<<20);
        if (pp[n] == NULL)
            break;
    }
    printf("malloc failure after %d MiB\n", n);

    for (i = 0; i < n; i++) {
        memset (pp[i], 0, (1<<20));
        printf("%d\n", i+1);
    }

    return 0;
}

(En un sistema que funciona bien, como Solaris , los tres programas de demostración obtienen la misma cantidad de memoria y no se bloquean, pero vea malloc() devuelve NULL.)

Di esta respuesta a un post similar sobre el mismo tema:

¿Algunos repartidores son perezosos?

Esto comienza un poco fuera del tema (y luego lo vincularé a su pregunta), pero lo que está sucediendo es similar a lo que sucede cuando bifurca un proceso en Linux. Cuando se bifurca hay un mecanismo llamado copy on write que solo copia el espacio de memoria para el nuevo proceso cuando la memoria también se escribe. De esta manera, si el ejecutivo del proceso bifurcado es un nuevo programa de inmediato, entonces guardó la sobrecarga de copiar la memoria original de los programas.

Volviendo a tu pregunta, la idea es similar. Como otros han señalado, solicitar la memoria le da el espacio de memoria virtual inmediatamente, pero las páginas reales solo se asignan cuando se escriben en ellas.

¿Cuál es el propósito de esto? Básicamente hace que la memoria mallocing sea una operación de tiempo más o menos constante Big O (1) en lugar de una operación Big O (n) (similar a la forma en que el programador de Linux distribuye su trabajo en lugar de hacerlo en un gran trozo).

Para demostrar lo que quiero decir hice el siguiente experimento:

rbarnes@rbarnes-desktop:~/test_code$ time ./bigmalloc

real    0m0.005s
user    0m0.000s
sys 0m0.004s
rbarnes@rbarnes-desktop:~/test_code$ time ./deadbeef

real    0m0.558s
user    0m0.000s
sys 0m0.492s
rbarnes@rbarnes-desktop:~/test_code$ time ./justwrites

real    0m0.006s
user    0m0.000s
sys 0m0.008s

El programa bigmalloc asigna 20 millones de ints, pero no hace nada con ellos. deadbeef escribe un int a cada página que resulta en 19531 escribe y justwrites asigna 19531 ints y ceros hacia fuera. Como puede ver, deadbeef tarda unas 100 veces más en ejecutarse que bigmalloc y unas 50 veces más que sólo escribe.

#include <stdlib.h>

int main(int argc, char **argv) {

    int *big = malloc(sizeof(int)*20000000); // Allocate 80 million bytes

    return 0;
}

.

#include <stdlib.h>

int main(int argc, char **argv) {

    int *big = malloc(sizeof(int)*20000000); // Allocate 80 million bytes

    // Immediately write to each page to simulate an all-at-once allocation
    // assuming 4k page size on a 32-bit machine.

    for (int* end = big + 20000000; big < end; big += 1024)
        *big = 0xDEADBEEF;

    return 0;
}

.

#include <stdlib.h>

int main(int argc, char **argv) {

    int *big = calloc(sizeof(int), 19531); // Number of writes

    return 0;
}

Malloc asigna memoria de bloques administrados por libc. Cuando se necesita memoria adicional, la biblioteca va al núcleo usando la llamada al sistema brk.

El núcleo asigna páginas de memoria virtual al proceso de llamada. Las páginas se gestionan como parte de los recursos propios del proceso. Las páginas físicas no se asignan cuando la memoria es brk'd. Cuando el proceso accede a cualquier ubicación de memoria en una de las páginas brk'd se produce un error de página. El núcleo valida que la memoria virtual se ha asignado y procede a asignar una página física a la página virtual.

La asignación de páginas no se limita a la escritura y es bastante distinta de la copia al escribir. Cualquier acceso, lectura o escritura, resulta en un error de página y mapeo de una página física.

Tenga en cuenta que la memoria de pila se asigna automáticamente. Es decir, no se requiere un brk explícito para asignar páginas a la memoria virtual utilizada por la pila.

En Windows, las páginas están confirmadas (es decir, la memoria libre disponible se reduce), pero en realidad no se asignarán hasta que toque las páginas (ya sea de lectura o escritura).

En la mayoría de los sistemas Unix, gestiona el límite brk. La máquina virtual agrega páginas cuando es alcanzada por el procesador. Al menos Linux y BSDs hacen esto.