Memoria dinámica

En la semana 3 dibujamos los marcos de la pila, y en la semana 4 les agregamos flechas: los punteros. Con eso ya podemos describir con precisión dos límites que venimos arrastrando. struct image reserva siempre 64 x 64 píxeles: una imagen de 3 x 2 desperdicia casi todo, y una de 96 x 28 no se puede cargar. Y en la semana 4 vieron que una función no puede devolver la dirección de una local, porque su marco desaparece al retornar.

Los dos límites tienen la misma causa: todo lo que hemos guardado vive en la pila, y la pila tiene reglas fijas. Hoy agregamos una tercera zona al modelo de entornos, el heap. Ahí se pide memoria mientras el programa corre, del tamaño que haga falta, y dura hasta que alguien la libera. Ese “alguien” es la parte difícil. C no libera nada por ustedes, así que cada bloque necesita un owner, la palabra inglesa para quien tiene algo como suyo: aquí, la parte del programa que responde por liberarlo. Por eso, la mitad de este capítulo trata de cómo se equivoca uno, y de dos herramientas que encuentran esos errores: ASan y valgrind.

Al terminar, el módulo de imágenes dejará de tener tamaño máximo.

Ruta de lectura.

• Antes de clase (15 a 20 minutos, obligatoria): la introducción, Lo que la pila no puede y El heap en el modelo de entornos.
• En clase: malloc y sizeof, Revisar el resultado, Ownership, Errores típicos, y cómo leer un informe de ASan, Valgrind, y un error que ASan no ve y calloc y realloc.
• Después de clase: El módulo de imágenes, sin límite y El laboratorio, paso a paso. Luego el Resumen y los Ejercicios. Para ir más allá: los últimos ejercicios del capítulo.

Código. Los programas de este capítulo están en code/week-05. Dentro del entorno del curso, entren a esa carpeta y corran make para compilar los ejemplos y make test para comprobarlos. Los comandos de este capítulo se corren desde ahí. Los programas de errors/ tienen errores a propósito y se compilan a mano, como se muestra en cada caso.

Lo que la pila no puede

La pila resuelve bien casi todo lo que hemos hecho. Crear y destruir un marco no cuesta casi nada, y nadie tiene que acordarse de liberarlo. Pero tiene tres límites.

El tamaño debe conocerse al escribir el programa. En Introducción a la Computación, un programa que leía n números declaraba un arreglo con un tamaño máximo constante, porque int values[n] con un n leído es una característica opcional de C17 y no se puede revisar si falló. Por eso en este curso, el tamaño de un arreglo sigue siendo una constante.

La pila es pequeña. Este programa solo declara un arreglo grande, de 16 MB:

#define SIZE 4000000

int main(void) {
    int values[SIZE];

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/big_local.c -o build/big_local
$ build/big_local
AddressSanitizer:DEADLYSIGNAL
=================================================================
==98==ERROR: AddressSanitizer: stack-overflow on address 0xffffcc009260 (pc 0xaaaabcd30ff0 bp 0xffffccf4b8c0 sp 0xffffcc009260 T0)
    #0 0xaaaabcd30ff0 in main errors/big_local.c:6
...
SUMMARY: AddressSanitizer: stack-overflow errors/big_local.c:6 in main

El tamaño máximo de la pila depende del sistema. En el entorno del curso son 8 MB. No hay forma de preguntar en el programa si la declaración cabrá: el programa simplemente cae.

Una local muere con su marco. Este error ya lo conocen de la semana 4. gcc lo detecta en un caso tan directo:

int *range_local(int first) {
    int block[4];
    for (int i = 0; i < 4; i++) {
        block[i] = first + i;
    }
    return block;
}

$ gcc -Wall -Wextra -std=c17 -g errors/local_address.c -o build/local_address
errors/local_address.c: In function 'range_local':
errors/local_address.c:9:12: warning: function returns address of local variable [-Wreturn-local-addr]
    9 |     return block;
      |            ^~~~~

Lo que falta es una memoria con otras reglas: de cualquier tamaño, que se pida al ejecutar, y que no dependa de ningún marco.

El heap en el modelo de entornos

El heap es una zona de memoria aparte de la pila. Funciona con dos operaciones de la biblioteca estándar, declaradas en <stdlib.h>:

• malloc(n) reserva un bloque de n bytes y devuelve su dirección.
• free(p) libera el bloque cuyo inicio es p.

A la memoria que se pide así, al ejecutar, se le llama memoria dinámica (dynamic memory). Un bloque tiene tres diferencias con una variable local:

• No tiene nombre. Solo se llega a él por su dirección, guardada en algún puntero.
• Su tamaño puede salir de un cálculo. Se decide al ejecutar.
• Su tiempo de vida no depende de ningún marco. Vive desde malloc hasta free, aunque la función que lo reservó ya haya retornado.

El modelo crece con dos reglas, que se suman a las cuatro de la semana 3:

Cómo se dibuja

Sigamos range_block.c. El heap va aparte, debajo de la pila, y los bloques no llevan nombre. Un puntero es una flecha, igual que en la semana 4.

int *range_new(int first, int n) {
    int *block = malloc(n * sizeof *block);
    if (block == NULL) {
        return NULL;
    }
    for (int i = 0; i < n; i++) {
        block[i] = first + i;
    }
    return block;
}

main llama a range_new(10, 4). Sigamos el bloque desde malloc hasta free:

Al retornar, el marco de range_new desaparece, y block con él. El bloque no: la regla 4 solo habla de marcos. La dirección que devuelve return llega a numbers, y la flecha sigue llegando al mismo lugar.

Por eso esto funciona, y range_local no:

$ build/range_block
10 11 12 13 

Después de free(numbers), el bloque desaparece y la flecha queda apuntando a algo que ya no existe. Se le llama puntero colgante (dangling pointer). Según la regla 6, numbers sigue guardando la misma dirección. Si main no vuelve a usarlo, no hay ningún problema.

Idea clave. La pila se administra sola, y sigue el orden de las llamadas. El heap lo administran ustedes, y un bloque vive exactamente lo que ustedes decidan: ni más, ni menos.

malloc y sizeof

malloc recibe bytes. Esta es su firma:

void *malloc(size_t size);

Tiene dos cosas que no han visto:

• size_t es el tipo sin signo con que C mide tamaños, el mismo que devuelve sizeof. Por eso sizeof se escribe con %zu. Con un int positivo no hay problema, porque se convierte solo. Un int negativo se convierte en un número enorme, así que revisen n antes de reservar.
• void * es un puntero sin tipo: una dirección de la que no se sabe qué hay ahí. No se puede seguir con *, pero en C se convierte solo al asignarlo a un int * o a cualquier otro puntero. Por eso no hace falta escribir un cast delante de malloc.

Entonces, ¿qué hace int *p = malloc(10);? Reserva 10 bytes, no 10 enteros. Con enteros de 4 bytes, eso alcanza para dos y medio.

int *p = malloc(10);
if (p == NULL) {
    return 1;
}

for (int i = 0; i < 10; i++) {
    p[i] = i;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/short_block.c -o build/short_block
$ build/short_block
=================================================================
==109==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x502000000018 at pc 0xaaaabe76112c bp 0xffffe8dbcf80 sp 0xffffe8dbcf98
WRITE of size 4 at 0x502000000018 thread T0
    #0 0xaaaabe761128 in main errors/short_block.c:12
...
0x50200000001a is located 0 bytes after 10-byte region [0x502000000010,0x50200000001a)

p[0] y p[1] caben, y p[2] ya se sale. Más adelante aprenderemos a leer este informe completo. Sin -fsanitize, el programa escribe fuera del bloque sin que nadie lo note, y solo cae más tarde, en otra línea. En el entorno del curso, cae dentro de printf, que reserva memoria para sí misma, y el mensaje no dice nada de p:

$ gcc -Wall -Wextra -std=c17 -g -O0 errors/short_block.c -o build/short_block_plain
$ build/short_block_plain
malloc(): corrupted top size

La forma correcta multiplica la cantidad por el tamaño de cada elemento:

int *values = malloc(n * sizeof *values);

sizeof *values es “cuánto mide lo que values apunta”. sizeof no evalúa su operando, solo mira su tipo, así que usar *values aquí es seguro, aunque values todavía no tenga valor. Tiene una ventaja sobre sizeof(int): si mañana el arreglo pasa a ser de double, esa línea sigue correcta sin tocarla.

Hay que distinguir el tamaño del puntero del tamaño de lo que apunta:

$ build/sizes
sizeof(int)          = 4
sizeof p  (puntero)  = 8
sizeof *p (un int)   = 4
sizeof q  (puntero)  = 8
sizeof *q (un point) = 8
10 enteros           = 40 bytes

Error común. Escribir malloc(sizeof p) en lugar de malloc(sizeof *p). Eso reserva lo que mide un puntero, 8 bytes en este entorno, sea cual sea el tamaño del struct. Y sizeof tampoco les dirá cuánto mide un bloque: dado un puntero, responde lo que mide el puntero. El tamaño del bloque lo tienen que guardar ustedes, en una variable o en un campo.

Con esto, el problema de leer n números queda resuelto, sin máximo:

int *values = malloc(n * sizeof *values);
if (values == NULL) {
    fprintf(stderr, "No hay memoria para %d números\n", n);
    return 1;
}

$ echo 3 10 20 30 | build/reverse_numbers
30 20 10 

Revisar el resultado

malloc puede fallar. Cuando no puede reservar el bloque, devuelve NULL, el puntero nulo de la semana 4. Seguir ese NULL es comportamiento indefinido, por lo que todo malloc se revisa, igual que fopen y scanf.

no_memory.c pide un bloque imposible, para ver el aviso:

size_t huge = SIZE_MAX / 2;

char *block = malloc(huge);
if (block == NULL) {
    printf("malloc devolvió NULL: no hay memoria\n");
    return 1;
}

Con sanitizers pasa algo distinto de lo que dice el estándar. ASan no deja que un pedido imposible llegue a devolver NULL: detiene el programa y lo reporta. Por eso make compila este ejemplo sin sanitizers.

$ build/no_memory
malloc devolvió NULL: no hay memoria

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined no_memory.c -o build/no_memory_san
$ build/no_memory_san
=================================================================
...
SUMMARY: AddressSanitizer: allocation-size-too-big ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69 in malloc

En C. Que malloc devuelva una dirección no siempre significa que la memoria física ya exista. En Linux, el sistema suele prometer más memoria de la que tiene, y solo la entrega cuando el programa la usa. Si se acaba en ese momento, el sistema puede cerrar el programa. Revisar malloc sigue siendo obligatorio: es lo único que el lenguaje les permite hacer, y atrapa los pedidos imposibles, como un tamaño mal calculado.

Qué hacer cuando falla

Lo correcto depende de quién falla. main puede avisar y terminar. Una función de biblioteca, como range_new, no debe decidir por los demás: libera lo que ya reservó y devuelve NULL, y quien la llamó decide. Es la misma forma de trabajar de image_load, que no imprime nada cuando no puede abrir un archivo.

Liberar: free

free tiene tres reglas, y las tres importan:

1. Recibe exactamente la dirección que dio malloc, no otra dentro del bloque.
2. Un bloque se libera una sola vez.
3. free(NULL) no hace nada. Es legal, y por eso se puede liberar sin preguntar antes:

if (p == NULL || q == NULL) {
    free(p);
    free(q);
    return 1;
}

Ese caso, de sizes.c, muestra por qué conviene: si solo falló q, p igual se libera, y si falló p, el free sobre NULL no hace nada.

Ownership

Cuando una función devuelve un bloque, aparece una pregunta que el compilador no revisa: ¿quién lo libera? Si nadie, hay una fuga de memoria. Si dos, se libera dos veces.

La regla del curso es simple: cada bloque tiene exactamente un owner, la parte del programa responsable de liberarlo. El owner puede cambiar, pero tiene que haber uno solo en cada momento, y la firma, con su comentario, debe decir quién es. A esa relación entre un bloque y su owner se le llama ownership.

range_new, al comienzo del capítulo, entrega el bloque a quien llama:

// Devuelve un bloque nuevo con first, first + 1, ... (n elementos), o NULL si no hay
// memoria. Quien llama es owner del bloque, y debe liberarlo con free.
int *range_new(int first, int n) {

C no tiene una forma de decir esto en el tipo. int * es igual para un bloque que hay que liberar y para uno que no. Por eso el comentario es parte de la interfaz, no un adorno.

Tres firmas, tres respuestas

Las tres funciones de strings_owner.c trabajan con cadenas, y cada una da una respuesta distinta:

// Devuelve una cadena nueva con text en mayúsculas, o NULL si no hay memoria.
// Quien llama es owner del resultado, y debe liberarlo con free.
char *upper_copy(const char *text) {

// Cambia text en su lugar. El owner de text sigue siendo quien llama.
void upper_in_place(char *text) {

// Devuelve una de las dos cadenas que recibió. No hay memoria nueva: no se libera.
const char *longer_of(const char *a, const char *b) {

El const del tipo que se devuelve ayuda: free no acepta un const char * sin un aviso del compilador. Y la primera función muestra el detalle más repetido de este tema:

char *copy = malloc(strlen(text) + 1);
if (copy == NULL) {
    return NULL;
}

strlen no cuenta el '\0'. Una cadena de n letras ocupa n + 1 bytes. Sin ese + 1, se escribe un byte fuera del bloque.

$ build/strings_owner
PARADERO
RUTA
Arequipa

Error común. Perder la dirección que hay que liberar. printf("%s\n", upper_copy("hola")); funciona y deja una fuga: el resultado se imprime y nadie guardó el puntero. Lo que una función le entrega a quien llama se guarda en una variable, y esa variable es la que llega a free.

Un struct que es owner de un bloque

Un struct puede tener un puntero a un bloque. Así es un estudiante con un nombre de cualquier largo:

struct student {
    int code;
    char *name;
};

Crear uno requiere dos bloques, y cualquiera de los dos malloc puede fallar. Si falla el segundo, el primero ya está reservado y hay que liberarlo antes de retornar:

struct student *s = malloc(sizeof *s);
if (s == NULL) {
    return NULL;
}

s->name = malloc(strlen(name) + 1);
if (s->name == NULL) {
    free(s);
    return NULL;
}

Liberarlo también tiene un orden. Primero el nombre y después el struct, porque si se libera primero el struct, leer s->name ya sería un acceso a un bloque liberado. Y conviene imitar a free: que NULL no haga nada.

void student_free(struct student *s) {
    if (s == NULL) {
        return;
    }
    free(s->name);
    free(s);
}

main         ana = ●──┐
                      │
heap                  └──> [ code = 101  name = ●──]──> [ 'A' 'n' 'a' '\0' ]

Este par, una función que crea y una que destruye, es la forma en que este curso maneja cualquier dato con bloques adentro. Quien usa student_new no necesita saber cuántos bloques hay. Solo necesita llamar a student_free.

Copiar un struct no copia sus bloques

En la semana 3 vimos que un struct se copia completo, aunque tenga un arreglo adentro. Sigue siendo cierto. Pero “completo” significa sus campos, y el campo name es un puntero: se copia la flecha, no lo que apunta.

struct student shallow = *ana;
shallow.name[0] = 'E';
printf("%s %s\n", ana->name, shallow.name);
printf("mismo bloque: %d\n", ana->name == shallow.name);

$ build/student
Ena Ena
mismo bloque: 1

Los dos apuntan al mismo bloque, y por eso el cambio se ve en ambos. A esto se le llama una copia superficial. Peor aún: hay dos punteros y un solo bloque. Si cada uno se creyera owner, ese bloque se liberaría dos veces. Una copia profunda reserva un bloque propio para la copia y copia ahí el contenido, y cada struct queda como owner del suyo.

Idea clave. Hay muchos punteros posibles a un bloque, pero un solo owner. Los demás solo lo toman prestado, y no pueden usarlo después de que el owner lo libere.

Errores típicos, y cómo leer un informe de ASan

Hay cuatro errores que se repiten, y el compilador casi nunca los ve. Para esto sirve ASan (AddressSanitizer), la parte de -fsanitize=address que han estado usando desde el curso anterior. Agrega al programa revisiones en cada acceso a memoria, rodea cada bloque de zonas vigiladas, y demora en reutilizar lo liberado para poder reconocerlo.

Usar después de liberar

int *p = malloc(10 * sizeof *p);
if (p == NULL) {
    return 1;
}

p[0] = 7;
free(p);
printf("%d\n", *p);

Sin sanitizers, el programa termina como si nada, y escribe un número que no es el 7, distinto en cada corrida:

$ gcc -Wall -Wextra -std=c17 -g -O0 errors/use_after_free.c -o build/use_after_free_plain 2>/dev/null
$ build/use_after_free_plain
-1431294438

Ese espacio dejó de ser de ustedes, y la biblioteca ya lo usó para sus propias anotaciones. En otro programa, ahí podría seguir el valor anterior, y todo parecería correcto. Con ASan:

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/use_after_free.c -o build/use_after_free 2>/dev/null
$ build/use_after_free
=================================================================
==132==ERROR: AddressSanitizer: heap-use-after-free on address 0x504000000010 at pc 0xaaaab74b0f34 bp 0xffffed9339b0 sp 0xffffed9339c8
READ of size 4 at 0x504000000010 thread T0
    #0 0xaaaab74b0f30 in main errors/use_after_free.c:13
...
0x504000000010 is located 0 bytes inside of 40-byte region [0x504000000010,0x504000000038)
freed by thread T0 here:
    #0 0xffff98e692b4 in free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:52
    #1 0xaaaab74b0ea8 in main errors/use_after_free.c:12
...
previously allocated by thread T0 here:
    #0 0xffff98e6a400 in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69
    #1 0xaaaab74b0df4 in main errors/use_after_free.c:6
...
SUMMARY: AddressSanitizer: heap-use-after-free errors/use_after_free.c:13 in main

El informe es largo, pero siempre se lee igual. Las direcciones y el número entre == cambian en cada corrida, así que no hay que memorizarlos. Lean en este orden:

1. El tipo de error, después de AddressSanitizer:. Aquí, heap-use-after-free.
2. El acceso: READ of size 4. Se intentó leer 4 bytes, un int.
3. Dónde pasó: la primera línea de la pila con un archivo de ustedes, errors/use_after_free.c:13. Las líneas que vienen de asan_malloc_linux.cpp o de libc no son suyas: sáltenlas.
4. Qué bloque era: 40-byte region. Son los 40 bytes de los 10 enteros, y el acceso fue 0 bytes inside, al inicio.
5. La historia del bloque: freed by ... use_after_free.c:12, y previously allocated by ... use_after_free.c:6.

La línea 5 es la que más ayuda en un programa grande: el acceso y el free pueden estar en funciones muy lejanas, y ASan da las dos. Noten que esas pilas se leen de arriba hacia abajo, la más reciente primero, igual que backtrace en gdb.

gcc a veces lo avisa al compilar, como en este caso tan directo, donde el free y el uso están en líneas seguidas:

$ gcc -Wall -Wextra -std=c17 -g errors/use_after_free.c -o build/use_after_free_warn
errors/use_after_free.c: In function 'main':
errors/use_after_free.c:13:5: warning: pointer 'p' used after 'free' [-Wuse-after-free]

No cuenten con eso. En cuanto el free queda dentro de otra función, normalmente deja de avisar.

Liberar dos veces

Este suele ser un problema de ownership, no de distracción. Aquí, show_and_free se cree owner de lo que recibe, y main también:

void show_and_free(int *values, int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", values[i]);
    }
    printf("\n");
    free(values);
}

show_and_free(values, 3);
free(values);

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/double_free.c -o build/double_free
$ build/double_free
0 0 0 
=================================================================
==143==ERROR: AddressSanitizer: attempting double-free on 0x502000000010 in thread T0:
    #0 0xffffac7192b4 in free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:52
    #1 0xaaaadaca10bc in main errors/double_free.c:20
...
0x502000000010 is located 0 bytes inside of 12-byte region [0x502000000010,0x50200000001c)
freed by thread T0 here:
    #0 0xffffac7192b4 in free ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:52
    #1 0xaaaadaca106c in show_and_free errors/double_free.c:10
    #2 0xaaaadaca10b4 in main errors/double_free.c:19

La corrección no es borrar un free al azar. Es decidir quién es el owner. Una función que se llama show no debería liberar nada: que main, que reservó, sea quien libere. Esa decisión cambia el nombre y el comentario de la función, no solo una línea.

Un primo de este error es liberar algo que no es un inicio de bloque. Por ejemplo, en errors/free_middle.c, se hace values++ y luego free(values). ASan responde attempting free on address which was not malloc()-ed, y añade dónde está esa dirección: 4 bytes inside of 16-byte region.

Salirse del bloque

Es el error de siempre, ahora en el heap:

int n = 4;
int *values = malloc(n * sizeof *values);
if (values == NULL) {
    return 1;
}

for (int i = 0; i <= n; i++) {
    values[i] = i * i;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/off_by_one.c -o build/off_by_one
$ build/off_by_one
=================================================================
==154==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x502000000020 at pc 0xaaaacd8b1230 bp 0xfffff5cee6a0 sp 0xfffff5cee6b8
WRITE of size 4 at 0x502000000020 thread T0
    #0 0xaaaacd8b122c in main errors/off_by_one.c:13
...
0x502000000020 is located 0 bytes after 16-byte region [0x502000000010,0x502000000020)
allocated by thread T0 here:
    #0 0xffffa516a400 in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69
    #1 0xaaaacd8b1104 in main errors/off_by_one.c:7

0 bytes after 16-byte region lo dice todo: el acceso cae justo después del último byte. Es el índice 4 de un bloque de 4 enteros.

La fuga de memoria

Una fuga de memoria (memory leak) es un bloque reservado que ya nadie puede liberar, porque se perdió su dirección. No hay un acceso inválido, y el programa da el resultado correcto. Aquí, cada vuelta reserva un bloque y pierde el anterior:

for (int round = 0; round < 3; round++) {
    int *numbers = range_new(round, 10);
    if (numbers == NULL) {
        return 1;
    }
    printf("%d\n", numbers[9]);
}

ASan incluye un detector de fugas, LeakSanitizer, que corre al terminar el programa. Por eso la salida aparece completa y el informe llega después:

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/leak.c -o build/leak
$ build/leak
9
10
11

=================================================================
==120==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 120 byte(s) in 3 object(s) allocated from:
    #0 0xffff96f9a400 in malloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:69
    #1 0xaaaac84b10c4 in range_new errors/leak.c:6
    #2 0xaaaac84b124c in main errors/leak.c:18
...
SUMMARY: AddressSanitizer: 120 byte(s) leaked in 3 allocation(s).

Lean este informe con cuidado. Dice dónde se reservó lo perdido, porque es lo único que sabe. No sabe dónde debía liberarse, ni si fue culpa de quien reservó o de quien recibió. Eso lo deciden ustedes, preguntándose quién era el owner. La línea errors/leak.c:6 está dentro de range_new, y esa función está bien. El error está en main.

¿Importa una fuga, si al terminar el programa el sistema recupera toda su memoria? En este ejemplo, nada grave pasa. Pero un programa que corre por semanas, o un ciclo que procesa miles de imágenes, se queda sin memoria poco a poco. En este curso, el código termina sin fugas, y las pruebas lo comprueban.

Resumen de los informes

Error común. Corregir el síntoma y no la causa. Si ASan dice que un bloque se usó después de liberarlo, borrar el free hace callar a ASan, pero deja una fuga. Antes de tocar nada, dibujen el bloque y digan quién era su owner.

Valgrind, y un error que ASan no ve

Valgrind es otra herramienta, con otro método: no cambia la compilación, sino que ejecuta el programa dentro de una CPU simulada, vigilando cada byte. Se usa sobre un programa compilado sin sanitizers, porque las dos herramientas no se pueden combinar:

$ gcc -Wall -Wextra -std=c17 -g -O0 errors/use_after_free.c -o build/use_after_free_vg 2>/dev/null
$ valgrind --leak-check=full build/use_after_free_vg
==42== Memcheck, a memory error detector
...
==42== Command: build/use_after_free_vg
==42== 
==42== Invalid read of size 4
==42==    at 0x108868: main (use_after_free.c:13)
==42==  Address 0x4a7f040 is 0 bytes inside a block of size 40 free'd
==42==    at 0x48884F8: free (vg_replace_malloc.c:989)
==42==    by 0x108863: main (use_after_free.c:12)
==42==  Block was alloc'd at
==42==    at 0x488545C: malloc (vg_replace_malloc.c:446)
==42==    by 0x108837: main (use_after_free.c:6)
==42== 
7
==42== 
==42== HEAP SUMMARY:
==42==     in use at exit: 0 bytes in 0 blocks
...
==42== All heap blocks were freed -- no leaks are possible
==42== 
...
==42== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

Tiene la misma información, en otro formato: Invalid read of size 4, en qué línea, y la historia del bloque (free'd, alloc'd). Hay dos diferencias que se notan. El número entre == es el del proceso, y aparece en cada línea que escribe valgrind; lo que no lo tiene, como el 7, lo escribió el programa. Y el programa siguió corriendo después del error, e incluso escribió un 7. ASan se detiene en el primer error. Valgrind los junta todos y da el total en ERROR SUMMARY.

Para las fugas, usen --leak-check=full, que da la pila de cada una:

$ gcc -Wall -Wextra -std=c17 -g -O0 errors/leak.c -o build/leak_vg
$ valgrind --leak-check=full build/leak_vg
...
==33== HEAP SUMMARY:
==33==     in use at exit: 120 bytes in 3 blocks
...
==33== 120 bytes in 3 blocks are definitely lost in loss record 1 of 1
==33==    at 0x488545C: malloc (vg_replace_malloc.c:446)
==33==    by 0x108803: range_new (leak.c:6)
==33==    by 0x108887: main (leak.c:18)
==33== 
==33== LEAK SUMMARY:
==33==    definitely lost: 120 bytes in 3 blocks
==33==    indirectly lost: 0 bytes in 0 blocks
==33==      possibly lost: 0 bytes in 0 blocks
==33==    still reachable: 0 bytes in 0 blocks

definitely lost es la fuga que ya conocen: nadie tiene la dirección. indirectly lost es un bloque al que solo se llegaba por otro bloque perdido, como el nombre de un struct student del que se perdió el puntero. Corrijan el directo, y normalmente el indirecto desaparece con él. El ejercicio 6 les pide verlo.

El total de total heap usage, que aquí recortamos, también cuenta memoria que printf reserva para sí misma, así que puede ser mayor que lo que el programa pide. No se preocupen por eso.

En C. Valgrind devuelve el código de salida del programa, aunque encuentre errores. En una prueba automática se agrega --error-exitcode=1, para que los errores se noten como un fallo. Las pruebas de este curso lo hacen así.

Leer sin haber escrito

Si un bloque de malloc trae basura, ¿qué pasa si se lee antes de escribir? Este es un error que ASan no ve:

int *counts = malloc(3 * sizeof *counts);
if (counts == NULL) {
    return 1;
}

counts[0] = 5;
counts[2] = 5;
if (counts[1] > 0) {
    printf("hay datos\n");
} else {
    printf("no hay datos\n");
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/uninit_read.c -o build/uninit_read
$ build/uninit_read
no hay datos

ASan no reporta nada, porque el acceso está dentro del bloque. Valgrind sí lleva la cuenta de qué bytes se escribieron alguna vez:

$ gcc -Wall -Wextra -std=c17 -g -O0 errors/uninit_read.c -o build/uninit_read_vg
$ valgrind --track-origins=yes build/uninit_read_vg
...
==69== Conditional jump or move depends on uninitialised value(s)
==69==    at 0x10887C: main (uninit_read.c:13)
==69==  Uninitialised value was created by a heap allocation
==69==    at 0x488545C: malloc (vg_replace_malloc.c:446)
==69==    by 0x108837: main (uninit_read.c:6)

Noten cuándo avisa: no al copiar el valor, sino al decidir con él, en el if. Copiar basura todavía no cambia nada de lo que el programa hace, y decidir sí. --track-origins=yes agrega de dónde salió esa basura.

Y un error que valgrind no ve

Valgrind vigila los bloques del heap, pero no conoce los arreglos locales. Salirse de uno cae en otra parte de la pila, que también es memoria válida para él.

int values[4] = {1, 2, 3, 4};
int total = 0;
for (int i = 0; i <= 4; i++) {
    total = total + values[i];
}

$ gcc -Wall -Wextra -std=c17 -g -O0 errors/local_overflow.c -o build/local_overflow_vg
$ valgrind build/local_overflow_vg
...
==78== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/local_overflow.c -o build/local_overflow
$ build/local_overflow
errors/local_overflow.c:8:31: runtime error: index 4 out of bounds for type 'int [4]'
...
==188==ERROR: AddressSanitizer: stack-buffer-overflow on address 0xffff87300030 at pc 0xaaaabea81478 bp 0xffffd6a31ac0 sp 0xffffd6a31ad8

Por eso conviene conocer las dos:

Ninguna de las dos prueba que un programa está bien. Solo revisan los caminos que ejecutaron: una fuga en una rama que no corrió no aparece en el informe. Por eso importa también probar los caminos de error, y lo hacemos en el laboratorio.

calloc y realloc

calloc: un bloque en cero

calloc(n, size) reserva n elementos de size bytes cada uno, y deja todos sus bytes en cero. Para un contador, es justo lo que hace falta:

int n = 5;
int *counts = calloc(n, sizeof *counts);
if (counts == NULL) {
    return 1;
}

$ build/calloc_zero
0 0 1 0 0 

Tiene una segunda ventaja. La multiplicación de malloc(n * size) la hacen ustedes, y podría no caber en un size_t. calloc recibe los dos números por separado y revisa ese caso: si el total no cabe, devuelve NULL.

realloc: cambiar el tamaño

realloc(p, n) cambia el tamaño del bloque p a n bytes, y conserva su contenido hasta donde alcance. Lo nuevo viene con basura. Puede crecer en su lugar, si hay espacio libre detrás. Si no, reserva otro bloque, copia los datos y libera el viejo. Por eso devuelve una dirección, que puede ser distinta de la que recibió.

Esto tiene tres consecuencias:

Un realloc invalida los demás punteros al bloque. No importa cuál de los dos casos ocurra: como no se sabe, se trata como si se hubiera mudado.

int *first = values;

int *bigger = realloc(values, 100000 * sizeof *values);
if (bigger == NULL) {
    free(values);
    return 1;
}
values = bigger;

printf("%d\n", *first);

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/stale_pointer.c -o build/stale_pointer 2>/dev/null
$ build/stale_pointer
=================================================================
==199==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000010 at pc 0xaaaabd040e5c bp 0xfffffb3d4ac0 sp 0xfffffb3d4ad8
READ of size 4 at 0x502000000010 thread T0
    #0 0xaaaabd040e58 in main errors/stale_pointer.c:19
...
freed by thread T0 here:
    #0 0xffff8e7594cc in realloc ../../../../src/libsanitizer/asan/asan_malloc_linux.cpp:85
    #1 0xaaaabd040da8 in main errors/stale_pointer.c:12

Fíjense en freed by: quien liberó fue realloc.

Si falla, el bloque viejo sigue vivo. realloc devuelve NULL, y no toca el bloque original, que todavía tiene owner. De ahí sale el error más clásico del tema:

p = realloc(p, huge);

Si realloc falla, p queda en NULL, y esa era la única copia de la dirección del bloque. Ya nadie puede liberarlo. Valgrind lo muestra:

$ gcc -Wall -Wextra -std=c17 -g -O0 errors/realloc_lost.c -o build/realloc_lost_vg
$ valgrind --leak-check=full build/realloc_lost_vg
...
realloc devolvió NULL
...
==87== 40 bytes in 1 blocks are definitely lost in loss record 1 of 1
==87==    at 0x488545C: malloc (vg_replace_malloc.c:446)
==87==    by 0x10887F: main (realloc_lost.c:9)

ASan, igual que antes, se detiene ante un pedido imposible. Si se le pide que deje a realloc devolver NULL, encuentra la misma fuga:

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined errors/realloc_lost.c -o build/realloc_lost
$ ASAN_OPTIONS=allocator_may_return_null=1 build/realloc_lost
...
realloc devolvió NULL
...
Direct leak of 40 byte(s) in 1 object(s) allocated from:

La forma correcta guarda el resultado en otra variable y solo lo adopta si salió bien:

int *bigger = realloc(values, 4 * sizeof *values);
if (bigger == NULL) {
    // values sigue siendo válido: su owner todavía debe liberarlo.
    free(values);
    return 1;
}
values = bigger;

realloc(NULL, n) funciona como malloc(n). Por eso un arreglo puede empezar vacío, con su puntero en NULL, sin un caso especial. No usen realloc(p, 0): lo que hace depende de la implementación.

Cuánto crecer

Un arreglo que crece tiene dos números: la capacidad, cuántos elementos caben, y la cuenta, cuántos hay. La misma distinción de capacidad y longitud del vector de Introducción a la Computación, ahora sin máximo:

algoritmo agregar(arreglo, valor)
    si cuenta = capacidad entonces
        pedir un bloque más grande con realloc
        si no se pudo entonces
            devolver falso
        fin si
    fin si
    arreglo[cuenta] ← valor
    cuenta ← cuenta + 1
    devolver verdadero
fin algoritmo

¿Cuánto más grande? Cada realloc puede copiar todo el bloque, así que conviene llamarlo poco. growth_count.c agrega 20000 enteros con dos reglas, y cuenta las llamadas:

$ build/growth_count
de uno en uno: 20000 llamadas
duplicando:    16 llamadas

Duplicar la capacidad desperdicia, a lo sumo, un poco menos de la mitad del bloque, y a cambio casi nunca hay que llamar a realloc. Es la regla que usa el laboratorio.

El módulo de imágenes, sin límite

Con todo esto podemos cambiar struct image. Los píxeles salen del struct, y pasan a un bloque propio:

struct image {
    int width;
    int height;
    int max_value;
    int *pixels;
};

El bloque es uno solo, con todas las filas seguidas. Por eso ya no se escribe pixels[y][x], sino pixels[y * width + x]: la misma cuenta que ya hacía image_from_values en la semana 3 para leer su arreglo de valores. El y * width salta las filas anteriores, y el x avanza dentro de la fila.

Copiar un struct image ya no copia la imagen. Y mide mucho menos que los 16396 bytes de la semana 3 (el número exacto depende del sistema):

$ build/image_size
sizeof(struct image) = 24

La interfaz también cambia, y ahora dice quién es el owner:

// Las tres funciones siguientes devuelven una imagen nueva. Quien llama es su owner y
// debe liberarla con image_free. Si algo falla, devuelven NULL y no queda nada reservado.

La imagen inválida, con width igual a 0, ya no hace falta: un error ahora se avisa con NULL.

“Sin máximo” no significa sin revisar

Antes, el tope de 64 protegía de muchas cosas sin que lo notáramos. Sin él, hay que pensar en una imagen de 50000 x 50000. Son 2500 millones de píxeles, y width * height no cabe en un int: multiplicarlos es overflow, que es comportamiento indefinido. La revisión tiene que ser antes de multiplicar, con una división que no se puede pasar de rango:

static int valid_size(int width, int height, int max_value) {
    return width >= 1 && height >= 1 && width <= INT_MAX / height
        && max_value >= 1 && max_value <= IMAGE_MAX_VALUE;
}

Y el archivo puede mentir. Un archivo de pocos bytes puede decir que mide 40000 x 40000: un tamaño válido, de 6.4 GB. Por eso image_load no llena la imagen antes de leerla, y por eso read_number ahora rechaza un número que no cabe en un int, en lugar de aceptar solo hasta 100000.

Un programa que ya funciona

Con el módulo terminado, image_demo carga range.pgm, de 96 x 28, que en la semana 3 no cabía:

96 x 28, de 20 a 250, promedio 81.5
                                                                                                
                                                                    *********                   
                                                                *****************               
                                                              ******%%%%%%%%%******             
                                                             *****%%%%%%%%%%%%%*****            
............................................................****%%%%%%%%%%%%%%%%%****...........

El código de esta semana

make test compila los ejemplos y corre tres grupos de pruebas. test_examples.py comprueba lo que escribe cada programa, y que cada uno de errors/ produce el informe que dice este capítulo. test_notes.py vuelve a correr los comandos de este capítulo y compara: los informes de ASan y valgrind, sin las direcciones ni los números de proceso. test_lab.py prueba el laboratorio.

El laboratorio, paso a paso

Los archivos de partida están en code/week-05/lab, y su README.md dice qué pide cada parte. make test-lab lo comprueba todo: falla hasta que terminen. Las pruebas corren con sanitizers, así que una fuga las hace fallar, aunque el resultado sea correcto. Aquí están las ideas, no el código.

Sesión 1: imágenes y cadenas

image_allocate, image_new e image_free. image_from_values, que ya está hecha, muestra la forma: pide la imagen a image_allocate, y si un valor está mal, libera lo que tenía y devuelve NULL. Fíjense en que usa image_free, no dos free. image_allocate reserva los dos bloques, igual que student_new. Al pedir los píxeles, conviertan a size_t antes de multiplicar: así toda la cuenta se hace en size_t. Sin esa conversión, width * height se calcula en int, y solo cabe porque valid_size ya lo revisó.

read_image. El encabezado ya está leído. Falta reservar y leer. El camino difícil es el de error: si un píxel falta o está fuera de rango, ya hay dos bloques reservados, y image_load debe cerrar el archivo. Una imagen de 3 x 2 sin su último píxel es la prueba clave. Para eso sirve que las pruebas corran con LeakSanitizer.

str_duplicate y str_concat. Recuerden el + 1, y piensen cuánto debe medir el bloque de str_concat. strcpy copia hasta el '\0', y strcat podría servir, pero también pueden usar strcpy dos veces, con aritmética de punteros. Prueben con cadenas vacías, a cada lado.

¿Por qué no usar strdup? Porque no es parte de C17. Viene de POSIX, y con -std=c17 gcc no la declara:

$ gcc -Wall -Wextra -std=c17 -g -c errors/strdup_c17.c -o build/strdup_c17.o
...
errors/strdup_c17.c:7:18: error: implicit declaration of function 'strdup'; did you mean 'strcmp'? [-Wimplicit-function-declaration]

Sesión 2: cacería y arreglo que crece

La cacería. Son cinco programas, con cinco clases distintas de error, y todos compilan sin advertencias. El método importa más que el resultado: correr las dos herramientas, leer el informe en el orden de este capítulo, dibujar el bloque, escribir qué pasó, y recién entonces corregir. Un programa puede pasar una herramienta y fallar con la otra. Y una corrección tiene que dejar la salida que el programa buscaba: borrar un free hace callar a un informe, pero las pruebas comprueban lo que escribe el programa.

int_array. Empiecen por int_array_new e int_array_push, con el pseudocódigo de arriba y el patrón de realloc_grow.c. count y capacity son size_t, como el resultado de sizeof. Las pruebas hacen fallar a realloc a propósito, y comprueban que el arreglo conserve sus datos.

int_array_read_file. Un archivo con un entero por línea. Ya lo saben leer, con fgets y sscanf, como en la semana 2. La diferencia es que ahora no hay máximo de líneas. Cierren el archivo en todos los caminos. Una línea mala debe devolver NULL sin dejar nada reservado.

Resumen

• La pila no puede con tres cosas: tamaños que se conocen al ejecutar, datos grandes y datos que deben sobrevivir a una función. Para eso está el heap.
• malloc(n) reserva n bytes y devuelve la dirección de un bloque sin nombre, con basura adentro. Se escribe malloc(n * sizeof *p). Todo malloc se revisa: si falla, devuelve NULL.
• free(p) recibe la dirección exacta que dio malloc, una sola vez. No cambia p. free(NULL) no hace nada.
• En el modelo, los bloques van aparte de los marcos, y sobreviven al retornar.
• Cada bloque tiene un owner, que debe liberarlo, y la firma con su comentario dice quién es. Lo que tiene bloques adentro se crea con una función y se destruye con otra, como student_new y student_free.
• Copiar un struct copia sus punteros, no los bloques que apuntan: es una copia superficial.
• Los errores típicos son fuga, usar después de liberar, liberar dos veces y salirse del bloque. Un informe se lee así: tipo de error, acceso, línea, bloque e historia del bloque.
• Un informe de fuga dice dónde se reservó el bloque, no dónde debía liberarse.
• ASan se compila en el programa, ve los arreglos locales y se detiene en el primer error. Valgrind corre sin sanitizers, con -g -O0, ve los valores sin inicializar y sigue corriendo. Ninguna revisa lo que no se ejecutó.
• calloc reserva en cero. realloc conserva el contenido, y puede mudar el bloque, así que invalida los demás punteros. Nunca escriban p = realloc(p, n): si falla, se pierde el bloque.
• Un arreglo que crece tiene capacidad y cuenta, y conviene duplicar la capacidad.
• “Sin máximo” no significa sin revisar: width * height se comprueba antes de multiplicar.

Ejercicios

Dibujen primero y ejecuten después. Todo malloc se revisa, y todo programa termina sin fugas: compruébenlo con ASan o con valgrind.

1. ¿Cuántos bytes pide cada línea? ¿Cuántos double caben en cada bloque? Compruébenlo con sizeof.

   a) double *a = malloc(10);
   b) double *b = malloc(10 * sizeof(double));
   c) double *c = malloc(10 * sizeof *c);
   d) double *d = malloc(10 * sizeof d);

2. Sin compilar, dibujen el modelo en las líneas 3 y 5, y digan si este programa tiene algún error. ¿Y si se borra la línea 4?

   1  int main(void) {
   2      int *a = malloc(2 * sizeof *a);
   3      int *b = a;
   4      free(a);
   5      a = NULL;
   6      return 0;
   7  }

3. Escriban double *average_each(const int *values, int n), que devuelva un bloque nuevo con n promedios acumulados: el elemento i es el promedio de los primeros i + 1 valores. Escriban en un comentario quién es el owner. Pruébenla con assert y con valgrind.

4. Clasifiquen cada firma según la tabla de ownership. Para cada una, escriban el comentario que debería llevar, y digan si hay más de una respuesta razonable.

   a) char *str_trim(const char *text);
   b) void str_reverse(char *text);
   c) const char *route_name(const struct route *r);
   d) struct image *image_copy(const struct image *img);

5. Sin correrlos, digan qué error tiene cada fragmento, y qué tipo de informe darían ASan y valgrind. Luego compruébenlo.

   a) char *s = malloc(strlen("Lima")); strcpy(s, "Lima"); free(s);
   b) int *p = malloc(8); free(p); p = malloc(8);
   c) int *p = calloc(4, sizeof *p); int x = p[4]; free(p);
   d) int *p = malloc(4 * sizeof *p); p[0] = 1; if (p[1] == 0) { printf("cero\n"); } free(p);
   e) int local = 5; int *p = &local; free(p);

6. En student.c, cambien main para que no llame a student_free. Corran valgrind con --leak-check=full. ¿Qué bloque está definitely lost y cuál indirectly lost, y por qué? Ahora liberen solo el struct, con free(ana). ¿Cómo cambia el informe?

7. Escriban struct student *student_copy(const struct student *s), que haga una copia profunda. Comprueben, con el mismo código de student.c, que ahora cambiar el nombre de la copia no cambia el original. ¿Qué debe pasar en cada camino de error? Para hacer fallar a malloc a propósito no basta un nombre largo: ¿cómo lo harían?

8. Escriban struct image *image_crop(const struct image *img, int left, int top, int width, int height), que devuelva una imagen nueva. Decidan qué pasa si el rectángulo no cabe. Comparen con el crop de la semana 3: ¿qué se volvió más fácil, y qué nueva obligación tiene quien la llama?

9. Escriban int box_blur(struct image *img, int radius), con las reglas de la semana 3. Trabaja sobre un bloque temporal, y devuelve 1 si pudo y 0 si no hubo memoria. ¿Quién es el owner de ese bloque? Decidan qué hace la función con img si no hay memoria, y comprueben con una imagen de 96 x 28 que termina sin fugas.

10. En el laboratorio, int_array_push duplica la capacidad. Cámbienla para que crezca de 10 en 10, y cuenten las llamadas a realloc para 100, 1000 y 10000 elementos. Hagan lo mismo con la regla de duplicar. Si cada llamada copiara todo el bloque, ¿cuántos enteros se copiarían en total, en cada caso?

11. Un archivo de 30 bytes dice ser una imagen de 40000 x 40000. Según lo que escribieron en read_image, ¿cuánta memoria pide image_load, y cuánto trabajo hace antes de notar que faltan datos? ¿Cambiaría algo si read_image llamara a image_new? ¿Debería el módulo poner un máximo? Den un argumento a favor y otro en contra. No lo prueben con ASan en una máquina compartida: lean el código.

12. Escriban char *read_line(FILE *file), que lea una línea de cualquier largo y devuelva un bloque nuevo sin el salto de línea, o NULL si ya no quedan líneas o no hay memoria. Usen fgetc y un bloque que crece. Quien llama es el owner. ¿Qué pasa con la última línea, si el archivo no termina en salto de línea? Úsenla para escribir un programa que invierta las líneas de un archivo. Ahora hay dos niveles de ownership: el arreglo de líneas y cada línea.