Ejercicios de Gestión de Memoria Dinámica

(ej_b2_c05b_02)=
### Ejercicio 2.05b.02 - Dirección de Crecimiento del Stack ⭐⭐☆☆☆

:::{exercise}
:label: ej_b2_c05b_02_crecimiento_stack
:enumerator: mem-layout-2

Implementá una función que detecte empíricamente si la pila (*stack*) crece hacia direcciones descendentes o ascendentes mediante dos marcos de llamada anidados.

**Nivel de Bloom:** Nivel 3 (Aplicación) y Nivel 4 (Análisis).  
**Conceptos requeridos:** Pila de llamadas en memoria (*call stack*), paso por referencia, comparación de punteros y marcos de activación.  
**Techo conceptual:** Prohibido el uso de optimizaciones de compilador agresivas que eliminen el marco de pila (*tail call optimization*).

#### Contrato de la Función
- **Firma:** `bool stack_crece_hacia_abajo(void);`
- **Precondiciones:** Ninguna.
- **Postcondiciones:** Retorna `true` si la variable local del marco anidado reside en una dirección menor que la del marco llamador.

#### Tabla de Vectores de Prueba Obligatorios

| Arquitectura Típica | Comportamiento | Retorno Esperado | Justificación Técnica |
| :--- | :--- | :--- | :--- |
| **x86 / x86_64 / ARM64** | Marco anidado en dirección menor | `true` | Modelo de stack descendente estándar |

(ej_b2_c05b_03)=
### Ejercicio 2.05b.03 - b.3 - Tamaño de Página del Sistema ⭐⭐☆☆☆

Escribir un programa que use `sysconf(_SC_PAGESIZE)` (en sistemas POSIX) para
obtener el tamaño de página del sistema. Luego, alojar varios bloques de memoria
de diferentes tamaños y analizar cuánta memoria física se está usando realmente.

:::{note} Memoria Virtual

Recordá que el sistema operativo asigna memoria en múltiplos del tamaño de
página, típicamente 4 KB. Una asignación de 100 bytes puede consumir 4 KB de
memoria física.

(ej_b2_c05b_05)=
### Ejercicio 2.05b.05 - b.5 - Manejo de Errores en Cadena ⭐⭐⭐☆☆

Escribir una función que aloje múltiples estructuras anidadas:

```{code-block} c
:linenos:
struct persona_t
{
    char *nombre;
    char *apellido;
    struct direccion_t *direccion;
};
struct direccion_t
{
    char *calle;
    char *ciudad;
};
```
<!-- {code-block} c -->

La función debe manejar correctamente fallos de `malloc` en cualquier paso,
liberando todo lo previamente asignado antes de retornar `NULL`.

(ej_b2_c05b_06)=
### Ejercicio 2.05b.06 - b.6 - Pool de Memoria Simple ⭐☆☆☆☆

Implementar un pool de memoria básico que preasigne un bloque grande y
distribuya bloques pequeños de tamaño fijo desde él.

```{code-block} c
:linenos:
typedef struct
{
    void *bloque_base;
    size_t tamano_total;
    size_t tamano_bloque;
    size_t bloques_usados;
    bool *mapa_uso;
} pool_t;
pool_t *pool_crear(size_t n_bloques, size_t tamano_bloque);
void *pool_alojar(pool_t *pool);
void pool_liberar(pool_t *pool, void *ptr);
void pool_destruir(pool_t *pool);
```
<!-- {code-block} c -->

**Ventaja:** Reduce la fragmentación y overhead de múltiples `malloc`/`free`.

## Errores Comunes y Detección

(ej_b2_c05b_07)=
### Ejercicio 2.05b.07 - b.7 - Double Free ⭐⭐☆☆☆

Escribir un programa que deliberadamente cometa el error de double free:

```{code-block} c
:linenos:
int main()
{
    int *ptr = malloc(sizeof(int) * 10);
    *ptr = 42;
    free(ptr);
    free(ptr); // ERROR: double free
    return 0;
}
```
<!-- {code-block} c -->

Compilar con AddressSanitizer (`gcc -fsanitize=address`) y observar el error
detectado.

(ej_b2_c05b_08)=
### Ejercicio 2.05b.08 - b.8 - Use After Free ⭐⭐☆☆☆

Crear un programa que cometa use-after-free:

```{code-block} c
:linenos:
int main()
{
    int *arr = malloc(sizeof(int) * 5);
    arr[0] = 100;
    free(arr);
    printf("%d\n", arr[0]); // ERROR: use after free
    return 0;
}
```
<!-- {code-block} c -->

Ejecutar con Valgrind: `valgrind --leak-check=full ./programa`

(ej_b2_c05b_09)=
### Ejercicio 2.05b.09 - b.9 - Memory Leak Complejo ⭐⭐⭐⭐☆

Crear un programa con un leak no trivial:

```{code-block} c
:linenos:
struct nodo_t
{
    int dato;
    struct nodo_t *siguiente;
};
void agregar_nodo(struct nodo_t **cabeza, int valor)
{
    struct nodo_t *nuevo = malloc(sizeof(struct nodo_t));
    nuevo->dato = valor;
    nuevo->siguiente = *cabeza;
    *cabeza = nuevo;
}
int main()
{
    struct nodo_t *lista = NULL;
    for (int i = 0; i < 100; i++)
    {
        agregar_nodo(&lista, i);
    }
    // FALTA: liberar todos los nodos
    return 0;
}
```
<!-- {code-block} c -->

Detectar con Valgrind el leak de 100 nodos. Luego implementar una función
`liberar_lista` que corrija el problema.

(ej_b2_c05b_10)=
### Ejercicio 2.05b.10 - b.10 - Buffer Overflow en Heap ⭐⭐☆☆☆

Demostrar un buffer overflow en memoria dinámica:

```{code-block} c
:linenos:
int main()
{
    char *buffer = malloc(10);
    strcpy(buffer, "Esta cadena es mucho más larga que 10 bytes"); // OVERFLOW
    printf("%s\n", buffer);
    free(buffer);
    return 0;
}
```
<!-- {code-block} c -->

Compilar con `-fsanitize=address` y observar la detección del
heap-buffer-overflow.

## Estrategias de Realocación

(ej_b2_c05b_11)=
### Ejercicio 2.05b.11 - b.11 - Vector con Estrategia de Crecimiento ⭐⭐☆☆☆

Implementar un vector dinámico con diferentes estrategias de crecimiento:
- **Lineal**: incrementar en un valor fijo (ej. +10)
- **Geométrico**: duplicar la capacidad (factor 2)
- **Fibonacci**: crecer según la secuencia de Fibonacci

Comparar el número de `realloc` realizados al insertar 10,000 elementos.

(ej_b2_c05b_12)=
### Ejercicio 2.05b.12 - b.12 - Shrinking Inteligente ⭐⭐☆☆☆

Implementar un vector que no solo crece, sino que también reduce su capacidad
cuando el tamaño cae por debajo de 1/4 de la capacidad. Esto evita el overhead
de memoria manteniendo estabilidad.

```{code-block} c
:linenos:
void vector_pop(vector_t *v)
{
    if (v->size == 0)
        return;
    v->size--;
    // Si size < capacity/4 y capacity > MIN_CAPACITY, reducir a la mitad
    if (v->size > 0 && v->size < v->capacity / 4 && v->capacity > 16)
    {
        v->capacity /= 2;
        v->datos = realloc(v->datos, v->capacity * sizeof(int));
    }
}
```
<!-- {code-block} c -->

(ej_b2_c05b_13)=
### Ejercicio 2.05b.13 - b.13 - Realloc Fallido ⭐⭐☆☆☆

Escribir una función que maneje correctamente el fallo de `realloc`:

```{code-block} c
:linenos:
bool vector_push(vector_t *v, int dato)
{
    if (v->size == v->capacity)
    {
        size_t nueva_capacidad = v->capacity * 2;
        int *nuevo_bloque = realloc(v->datos, nueva_capacidad * sizeof(int));
        if (nuevo_bloque == NULL)
        {
            return false; // Fallo, pero v->datos sigue válido
        }
        v->datos = nuevo_bloque;
        v->capacity = nueva_capacidad;
    }
    v->datos[v->size++] = dato;
    return true;
}
```
<!-- {code-block} c -->

:::{important} Manejo de `realloc`

Nunca asignés directamente `ptr = realloc(ptr, size)`. Si falla, perdés el
puntero original y tenés un leak. Usá un puntero temporal como en el ejemplo.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define N 1000
int main()
{
    void *ptrs[N];
    // Alojar muchos bloques pequeños
    for (int i = 0; i < N; i++)
    {
        ptrs[i] = malloc(64);
    }
    // Liberar bloques alternados
    for (int i = 0; i < N; i += 2)
    {
        free(ptrs[i]);
        ptrs[i] = NULL;
    }
    // Intentar alojar un bloque grande
    void *grande = malloc(64 * (N / 2));
    if (grande == NULL)
    {
        printf("No se pudo alojar bloque grande debido a fragmentación\n");
    }
    else
    {
        printf("Bloque grande asignado exitosamente\n");
        free(grande);
    }
    // Liberar bloques restantes
    for (int i = 1; i < N; i += 2)
    {
        free(ptrs[i]);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <malloc.h>
int main()
{
    size_t tamaños[] = {1, 8, 16, 32, 64, 100, 128, 256, 512, 1024};
    for (size_t i = 0; i < sizeof(tamaños) / sizeof(tamaños[0]); i++)
    {
        void *ptr = malloc(tamaños[i]);
        size_t real = malloc_usable_size(ptr);
        printf(
            "Solicitado: %5zu bytes -> Real: %5zu bytes (%.1f%% overhead)\n",
            tamaños[i], real, 100.0 * (real - tamaños[i]) / tamaños[i]);
        free(ptr);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define SIZE (100 * 1024 * 1024) // 100M enteros
int main()
{
    int *arr = malloc(SIZE * sizeof(int));
    // Secuencial
    clock_t inicio = clock();
    for (size_t i = 0; i < SIZE; i++)
    {
        arr[i] = i;
    }
    clock_t fin = clock();
    printf("Secuencial: %.3f ms\n", 1000.0 * (fin - inicio) / CLOCKS_PER_SEC);
    // Aleatorio
    inicio = clock();
    for (size_t i = 0; i < SIZE; i++)
    {
        size_t idx = rand() % SIZE;
        arr[idx] = i;
    }
    fin = clock();
    printf("Aleatorio: %.3f ms\n", 1000.0 * (fin - inicio) / CLOCKS_PER_SEC);
    free(arr);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
struct sin_padding
{
    char a;   // 1 byte
    int b;    // 4 bytes
    char c;   // 1 byte
    double d; // 8 bytes
};
struct con_padding
{
    char a;   // 1 byte + 3 padding
    int b;    // 4 bytes
    char c;   // 1 byte + 7 padding
    double d; // 8 bytes
};
int main()
{
    printf("Tamaño sin optimizar: %zu bytes\n", sizeof(struct sin_padding));
    printf("Tamaño con padding: %zu bytes\n", sizeof(struct con_padding));
    // Imprimir offsets de cada campo
    struct con_padding s;
    printf("Offset de 'a': %zu\n", offsetof(struct con_padding, a));
    printf("Offset de 'b': %zu\n", offsetof(struct con_padding, b));
    printf("Offset de 'c': %zu\n", offsetof(struct con_padding, c));
    printf("Offset de 'd': %zu\n", offsetof(struct con_padding, d));
    return 0;
}

1
2
3
4
5
6
7
8
9
10
void *malloc_alineado(size_t size, size_t alineacion)
{
    void *ptr = NULL;
    // posix_memalign requiere que alineacion sea potencia de 2
    if (posix_memalign(&ptr, alineacion, size) != 0)
    {
        return NULL;
    }
    return ptr;
}

1
2
3
4
5
6
7
8
9
10
11
12
.PHONY: valgrind
valgrind: programa
	valgrind --leak-check=full \
	         --show-leak-kinds=all \
	         --track-origins=yes \
	         --verbose \
	         ./programa

.PHONY: asan
asan:
	$(CC) -fsanitize=address -g -o programa programa.c
	./programa

{
   leak_ignorado_libc
   Memcheck:Leak
   ...
   obj:/lib/x86_64-linux-gnu/libc-*.so
}

1
2
3
4
5
6
7
8
9
10
11
12
13
void *debug_malloc(size_t size, const char *archivo, int linea)
{
    void *ptr = malloc(size);
    printf("[MALLOC] %zu bytes en %p (%s:%d)\n", size, ptr, archivo, linea);
    return ptr;
}
void debug_free(void *ptr, const char *archivo, int linea)
{
    printf("[FREE] %p (%s:%d)\n", ptr, archivo, linea);
    free(ptr);
}
#define malloc(size) debug_malloc(size, __FILE__, __LINE__)
#define free(ptr) debug_free(ptr, __FILE__, __LINE__)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// El llamador es responsable de liberar la memoria retornada
char *construir_mensaje(const char *usuario)
{
    size_t len = strlen("Hola, ") + strlen(usuario) + 2;
    char *msg = malloc(len);
    if (msg == NULL)
    {
        return NULL;
    }
    snprintf(msg, len, "Hola, %s", usuario);
    return msg;
}
int main()
{
    char *mensaje = construir_mensaje("Alumno");
    if (mensaje != NULL)
    {
        printf("%s\n", mensaje);
        free(mensaje); // ¡El main debe liberar!
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct resultado_t
{
    int *datos;
    size_t tamano;
};
struct resultado_t procesar_numeros(int *entrada, size_t n)
{
    struct resultado_t res = {NULL, 0};
    res.datos = malloc(n * sizeof(int));
    if (res.datos == NULL)
    {
        return res;
    }
    for (size_t i = 0; i < n; i++)
    {
        res.datos[i] = entrada[i] * 2;
    }
    res.tamano = n;
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int procesar_archivo(const char *ruta)
{
    FILE *archivo = NULL;
    char *buffer = NULL;
    int resultado = -1;
    archivo = fopen(ruta, "r");
    if (archivo == NULL)
    {
        goto cleanup;
    }
    buffer = malloc(1024);
    if (buffer == NULL)
    {
        goto cleanup;
    }
    // ... procesamiento ...
    resultado = 0; // éxito
cleanup:
    if (buffer != NULL)
    {
        free(buffer);
    }
    if (archivo != NULL)
    {
        fclose(archivo);
    }
    return resultado;
}