// fits.c — compara best fit, worst fit, first fit y next fit sobre la misma
// lista de huecos y la misma secuencia de peticiones.
//
// Uso:   ./fits huecos peticiones
//        huecos y peticiones: listas separadas por comas (en KB, por ejemplo)
// Ejemplo (el de las diapositivas):
//   ./fits 10,20,6,14 4,8,4,16
//
// Modelo simplificado, como malloc.py de OSTEP: no hay encabezados y los
// huecos no se fusionan. Cada petición se toma del inicio del hueco elegido.
// Desempate: ante dos huecos igual de buenos, el de menor dirección.
// Next fit sigue buscando desde el hueco donde asignó la última vez.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 32

enum policy { BEST, WORST, FIRST, NEXT };
static const char *names[] = {"best", "worst", "first", "next"};

static int parse(const char *s, int *v) {
    int n = 0;
    char *copy = strdup(s);
    for (char *t = strtok(copy, ","); t != NULL && n < MAXN; t = strtok(NULL, ","))
        v[n++] = atoi(t);
    free(copy);
    return n;
}

// Devuelve el índice del hueco elegido, o -1 si ninguno alcanza.
static int choose(enum policy pol, const int *hole, int nh, int req, int last) {
    int pick = -1;
    for (int k = 0; k < nh; k++) {
        int i = (pol == NEXT) ? (last + k) % nh : k;
        if (hole[i] < req)
            continue;
        if (pol == FIRST || pol == NEXT)
            return i;
        if (pick < 0 || (pol == BEST && hole[i] < hole[pick]) ||
            (pol == WORST && hole[i] > hole[pick]))
            pick = i;
    }
    return pick;
}

static void print_holes(const int *hole, int nh) {
    printf("[");
    for (int i = 0; i < nh; i++)
        printf("%s%2d", i ? " " : "", hole[i]);
    printf("]");
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        fprintf(stderr, "uso: %s huecos peticiones   (ej: %s 10,20,6,14 4,8,4,16)\n",
                argv[0], argv[0]);
        return 1;
    }
    int init[MAXN], req[MAXN];
    int nh = parse(argv[1], init), nr = parse(argv[2], req);

    // Encabezado: una columna por petición.
    printf("huecos iniciales ");
    print_holes(init, nh);
    printf("\n\npolítica ");
    for (int r = 0; r < nr; r++)
        printf(" %3d", req[r]);
    printf("   huecos al final\n");

    for (int pol = BEST; pol <= NEXT; pol++) {
        int hole[MAXN], last = 0, fails = 0;
        memcpy(hole, init, sizeof(int) * nh);
        printf("%-8s ", names[pol]);
        for (int r = 0; r < nr; r++) {
            int i = choose(pol, hole, nh, req[r], last);
            if (i < 0) {
                printf("  --");  // ningún hueco alcanza
                fails++;
                continue;
            }
            hole[i] -= req[r];
            last = i;
            printf("  h%d", i);
        }
        printf("   ");
        print_holes(hole, nh);
        if (fails > 0)
            printf("  %d sin hueco", fails);
        printf("\n");
    }
    return 0;
}

// heapdemo.c — traza del asignador: tres malloc, tres free y una petición
// grande al final. Con -n se desactiva la fusión (coalescing).
//
// Uso: ./heapdemo [-n]
#include <stdio.h>
#include <string.h>
#include "mymalloc.h"

static void *do_malloc(const char *name, size_t size) {
    void *p = mm_malloc(size);
    if (p == NULL)
        printf("%s = malloc(%zu) -> NULL\n", name, size);
    else
        printf("%s = malloc(%zu) -> %zu (encabezado en %zu)\n",
               name, size, mm_offset(p), mm_offset(p) - 16);
    mm_dump();
    return p;
}

static void do_free(const char *name, void *p) {
    printf("free(%s)\n", name);
    mm_free(p);
    mm_dump();
}

int main(int argc, char *argv[]) {
    int coalesce = !(argc > 1 && strcmp(argv[1], "-n") == 0);
    mm_init(coalesce);
    printf("arena de %d bytes, fusión %s\n", ARENA_SIZE,
           coalesce ? "activada" : "desactivada");
    mm_dump();

    void *a = do_malloc("a", 96);
    void *b = do_malloc("b", 64);
    void *c = do_malloc("c", 32);
    do_free("b", b);
    do_free("a", a);
    do_free("c", c);
    do_malloc("d", 300);
    return 0;
}

// heaptest.c — pruebas del asignador de mymalloc.c.
// Termina con código 0 si todas pasan; assert aborta en la primera que falla.
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include "mymalloc.h"

#define FULL (ARENA_SIZE - 16)  // un solo trozo libre: toda la arena

static void test_split(void) {
    mm_init(1);
    void *a = mm_malloc(100);           // se redondea a 112
    assert(a != NULL && mm_offset(a) == 16);
    assert(mm_free_chunks() == 1);
    assert(mm_free_largest() == FULL - 112 - 16);
    mm_free(a);
    assert(mm_free_chunks() == 1 && mm_free_largest() == FULL);
}

static void test_no_tiny_chunks(void) {
    mm_init(1);
    // Pedir casi todo: el resto (16 bytes) no alcanza para nodo + datos.
    void *a = mm_malloc(FULL - 16);
    assert(a != NULL);
    assert(mm_free_chunks() == 0);      // se entregó el trozo completo
    assert(mm_malloc(1) == NULL);
    mm_free(a);
    assert(mm_free_largest() == FULL);
}

// Libera tres bloques vecinos en el orden dado y verifica que la arena
// vuelve a ser un solo trozo.
static void test_coalesce_order(int i, int j, int k) {
    mm_init(1);
    void *p[3];
    p[0] = mm_malloc(96);
    p[1] = mm_malloc(64);
    p[2] = mm_malloc(32);
    for (int n = 0; n < 3; n++)
        memset(p[n], 0xab, 32);         // el usuario escribe en sus bloques
    mm_free(p[i]);
    mm_free(p[j]);
    mm_free(p[k]);
    assert(mm_free_chunks() == 1);
    assert(mm_free_largest() == FULL);
}

static void test_without_coalesce(void) {
    mm_init(0);
    void *a = mm_malloc(96), *b = mm_malloc(64), *c = mm_malloc(32);
    mm_free(b);
    mm_free(a);
    mm_free(c);
    assert(mm_free_chunks() == 4);      // fragmentado: 96, 64, 32 y el resto
    assert(mm_malloc(300) == NULL);     // hay 448 bytes libres, pero partidos
}

static void test_first_fit(void) {
    mm_init(1);
    void *a = mm_malloc(32), *b = mm_malloc(32), *c = mm_malloc(32);
    (void)b;
    mm_free(a);
    mm_free(c);                          // c se fusiona con el resto
    void *d = mm_malloc(16);
    assert(d == a);                      // first fit: el hueco más bajo
}

static void test_magic(void) {
    mm_init(1);
    char *a = mm_malloc(64);
    assert(mm_valid(a));
    assert(!mm_valid(a + 8));            // no apunta al inicio de un bloque
    mm_free(a);
    assert(!mm_valid(a));                // magic ya fue pisado por next
}

int main(void) {
    test_split();
    test_no_tiny_chunks();
    int orders[6][3] = {{0,1,2},{0,2,1},{1,0,2},{1,2,0},{2,0,1},{2,1,0}};
    for (int n = 0; n < 6; n++)
        test_coalesce_order(orders[n][0], orders[n][1], orders[n][2]);
    test_without_coalesce();
    test_first_fit();
    test_magic();
    printf("heaptest: todas las pruebas pasaron\n");
    return 0;
}

// mymalloc.c — asignador first fit con división (splitting) y fusión
// (coalescing) sobre una arena estática de ARENA_SIZE bytes.
//
// Cada bloque asignado empieza con un encabezado de 16 bytes:
//     [ size | magic ][ ...size bytes para el usuario... ]
// Cada trozo libre empieza con un nodo de la lista libre, también de 16 bytes:
//     [ size | next  ][ ...size bytes libres... ]
// En ambos casos size cuenta solo los bytes que siguen al encabezado.
// La lista libre se mantiene ordenada por dirección para poder fusionar.
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include "mymalloc.h"

#define MAGIC 0x1234567890abcdefUL

typedef struct header {
    size_t size;   // bytes útiles del bloque
    size_t magic;  // MAGIC: sirve para detectar punteros inválidos
} header_t;

typedef struct node {
    size_t size;        // bytes libres después de este nodo
    struct node *next;  // siguiente trozo libre (por dirección)
} node_t;

static _Alignas(16) unsigned char arena[ARENA_SIZE];
static node_t *head;      // primer trozo libre
static int do_coalesce;

static size_t round_up(size_t n) {
    return (n + ALIGN - 1) & ~(size_t)(ALIGN - 1);
}

void mm_init(int coalesce) {
    head = (node_t *)arena;
    head->size = ARENA_SIZE - sizeof(node_t);
    head->next = NULL;
    do_coalesce = coalesce;
}

void *mm_malloc(size_t size) {
    if (size == 0)
        return NULL;
    size = round_up(size);

    // First fit: el primer trozo libre que alcance.
    node_t **link = &head;
    for (node_t *cur = head; cur != NULL; link = &cur->next, cur = cur->next) {
        if (cur->size < size)
            continue;
        if (cur->size >= size + sizeof(node_t) + ALIGN) {
            // División: el resto queda libre como un trozo nuevo.
            node_t *rest = (node_t *)((char *)cur + sizeof(header_t) + size);
            rest->size = cur->size - size - sizeof(node_t);
            rest->next = cur->next;
            *link = rest;
        } else {
            // El resto no alcanza para un trozo útil: se entrega completo.
            size = cur->size;
            *link = cur->next;
        }
        header_t *h = (header_t *)cur;
        h->size = size;
        h->magic = MAGIC;
        return h + 1;  // el usuario recibe la dirección después del encabezado
    }
    return NULL;  // ningún trozo alcanza
}

int mm_valid(void *ptr) {
    unsigned char *p = ptr;
    if (p < arena + sizeof(header_t) || p >= arena + ARENA_SIZE)
        return 0;
    header_t *h = (header_t *)ptr - 1;
    return h->magic == MAGIC;
}

// ¿El trozo a termina justo donde empieza b?
static int adjacent(node_t *a, node_t *b) {
    return (char *)a + sizeof(node_t) + a->size == (char *)b;
}

void mm_free(void *ptr) {
    if (ptr == NULL)
        return;
    if (!mm_valid(ptr)) {
        fprintf(stderr, "mm_free: puntero inválido %p\n", ptr);
        abort();
    }
    // free no recibe el tamaño: lo lee del encabezado, justo antes de ptr.
    header_t *h = (header_t *)ptr - 1;
    node_t *n = (node_t *)h;  // el encabezado se convierte en nodo
    n->size = h->size;        // (mismo lugar; magic se pisa con next)

    // Insertar en orden de dirección.
    node_t *prev = NULL, *cur = head;
    while (cur != NULL && cur < n) {
        prev = cur;
        cur = cur->next;
    }
    n->next = cur;
    if (prev == NULL)
        head = n;
    else
        prev->next = n;

    if (!do_coalesce)
        return;
    // Fusión con el vecino de la derecha y luego con el de la izquierda.
    if (cur != NULL && adjacent(n, cur)) {
        n->size += sizeof(node_t) + cur->size;
        n->next = cur->next;
    }
    if (prev != NULL && adjacent(prev, n)) {
        prev->size += sizeof(node_t) + n->size;
        prev->next = n->next;
    }
}

size_t mm_offset(void *ptr) {
    return (size_t)((unsigned char *)ptr - arena);
}

void mm_dump(void) {
    printf("  lista libre:");
    for (node_t *c = head; c != NULL; c = c->next)
        printf(" [%zu, size %zu]", mm_offset(c), c->size);
    printf("%s\n", head == NULL ? " (vacía)" : "");
}

size_t mm_free_chunks(void) {
    size_t n = 0;
    for (node_t *c = head; c != NULL; c = c->next)
        n++;
    return n;
}

size_t mm_free_largest(void) {
    size_t max = 0;
    for (node_t *c = head; c != NULL; c = c->next)
        if (c->size > max)
            max = c->size;
    return max;
}

// mymalloc.h — asignador first fit sobre una arena estática.
#ifndef MYMALLOC_H
#define MYMALLOC_H

#include <stddef.h>

#define ARENA_SIZE 512  // bytes de la arena (el "heap")
#define ALIGN      16   // toda petición se redondea a múltiplo de 16

void  mm_init(int coalesce);  // coalesce = 0 desactiva la fusión
void *mm_malloc(size_t size);
void  mm_free(void *ptr);
int   mm_valid(void *ptr);    // ¿ptr tiene un encabezado válido?
void  mm_dump(void);          // imprime la lista libre

// Para las pruebas: recorrer la lista libre.
size_t mm_free_chunks(void);  // cuántos trozos libres hay
size_t mm_free_largest(void); // tamaño del trozo libre más grande
size_t mm_offset(void *ptr);  // desplazamiento de ptr dentro de la arena

#endif

// ptsize.c — tamaño de una tabla de páginas lineal.
//
// Uso:   ./ptsize bits_de_dirección tamaño_página tamaño_pte
// Ejemplos:
//   ./ptsize 32 4096 4     x86 de 32 bits
//   ./ptsize 48 4096 8     x86-64 (48 bits de dirección virtual)
//   ./ptsize 39 4096 8     RISC-V Sv39, el de xv6
#include <stdio.h>
#include <stdlib.h>

static int log2_exact(unsigned long x) {
    int n = 0;
    while ((1UL << n) < x)
        n++;
    return (1UL << n) == x ? n : -1;
}

// Imprime 2^e bytes con la unidad binaria más grande que quede entera.
static void print_size(int e) {
    static const char *unit[] = {"bytes", "KiB", "MiB", "GiB", "TiB", "PiB", "EiB"};
    int u = e / 10;
    if (u > 6)
        u = 6;
    printf("2^%d bytes = %lu %s", e, 1UL << (e - 10 * u), unit[u]);
}

int main(int argc, char *argv[]) {
    if (argc != 4) {
        fprintf(stderr, "uso: %s bits_de_dirección tamaño_página tamaño_pte\n", argv[0]);
        return 1;
    }
    int va_bits = atoi(argv[1]);
    int off_bits = log2_exact(strtoul(argv[2], NULL, 0));
    int pte_bits = log2_exact(strtoul(argv[3], NULL, 0));
    if (off_bits < 0 || pte_bits < 0 || va_bits <= off_bits || va_bits > 64) {
        fprintf(stderr, "use potencias de 2 y una dirección más grande que la página\n");
        return 1;
    }
    int vpn_bits = va_bits - off_bits;
    printf("offset: %d bits, VPN: %d bits\n", off_bits, vpn_bits);
    printf("entradas: 2^%d\n", vpn_bits);
    printf("tabla:    2^%d x %s bytes = ", vpn_bits, argv[3]);
    print_size(vpn_bits + pte_bits);
    printf(" por proceso\n");
    return 0;
}

// sv39.c — las macros de paginación de xv6-riscv (kernel/riscv.h), fuera
// del kernel, para ver qué calculan con números concretos.
#include <stdio.h>
#include <stdint.h>

typedef uint64_t uint64;

// Copiadas de kernel/riscv.h
#define PGSIZE  4096 // bytes per page
#define PGSHIFT 12   // bits of offset within a page
#define PTE_V (1L << 0) // valid
#define PTE_R (1L << 1)
#define PTE_W (1L << 2)
#define PTE_X (1L << 3)
#define PTE_U (1L << 4) // user can access
#define PA2PTE(pa) ((((uint64)pa) >> 12) << 10)
#define PTE2PA(pte) (((pte) >> 10) << 12)
#define PTE_FLAGS(pte) ((pte) & 0x3FF)
#define PXMASK         0x1FF // 9 bits
#define PXSHIFT(level) (PGSHIFT + (9 * (level)))
#define PX(level, va)  ((((uint64)(va)) >> PXSHIFT(level)) & PXMASK)
#define MAXVA (1L << (9 + 9 + 9 + 12 - 1))
// Copiada de kernel/memlayout.h
#define TRAMPOLINE (MAXVA - PGSIZE)

static void show_va(const char *name, uint64 va) {
    printf("%-10s  PX(2,1,0) = %3llu %3llu %3llu  offset 0x%03llx\n", name,
           (unsigned long long)PX(2, va), (unsigned long long)PX(1, va),
           (unsigned long long)PX(0, va), (unsigned long long)(va & (PGSIZE - 1)));
}

static void show_flags(uint64 pte) {
    printf("%c%c%c%c%c", (pte & PTE_U) ? 'U' : '-', (pte & PTE_X) ? 'X' : '-',
           (pte & PTE_W) ? 'W' : '-', (pte & PTE_R) ? 'R' : '-',
           (pte & PTE_V) ? 'V' : '-');
}

int main(void) {
    show_va("0x1234", 0x1234);
    show_va("0x40201abc", 0x40201abc);
    show_va("TRAMPOLINE", TRAMPOLINE);
    printf("TRAMPOLINE = 0x%llx, MAXVA = 0x%llx\n\n",
           (unsigned long long)TRAMPOLINE, (unsigned long long)MAXVA);

    // Una PTE de hoja: página de usuario, lectura y escritura.
    uint64 pa = 0x87f42000;
    uint64 pte = PA2PTE(pa) | PTE_U | PTE_W | PTE_R | PTE_V;
    printf("pa          = 0x%llx\n", (unsigned long long)pa);
    printf("PA2PTE(pa)  = 0x%llx\n", (unsigned long long)PA2PTE(pa));
    printf("pte         = 0x%llx  ", (unsigned long long)pte);
    show_flags(pte);
    printf("\nPTE_FLAGS   = 0x%03llx\n", (unsigned long long)PTE_FLAGS(pte));
    printf("PTE2PA(pte) = 0x%llx\n", (unsigned long long)PTE2PA(pte));
    return 0;
}

// translate.c — traduce direcciones virtuales con una tabla de páginas lineal.
//
// Uso:   ./translate tamaño_página tabla dirección...
//        tabla: un PFN por página virtual, separados por comas; "-" = inválida.
//        El número de entradas debe ser potencia de 2.
// Ejemplo (el de las diapositivas): páginas de 1 KB, 16 páginas virtuales
//   ./translate 1024 5,12,-,-,30,-,-,-,-,-,-,-,29,-,-,7 0x3229 0x13ff 0x0a0f
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXPAGES 4096

static int log2_exact(unsigned long x) {
    int n = 0;
    while ((1UL << n) < x)
        n++;
    return (1UL << n) == x ? n : -1;
}

// Imprime los nbits menos significativos de x en binario.
static void print_bits(unsigned long x, int nbits) {
    for (int i = nbits - 1; i >= 0; i--)
        putchar((x >> i) & 1 ? '1' : '0');
}

int main(int argc, char *argv[]) {
    if (argc < 4) {
        fprintf(stderr, "uso: %s tamaño_página tabla dirección...\n", argv[0]);
        return 1;
    }
    unsigned long page = strtoul(argv[1], NULL, 0);
    int off_bits = log2_exact(page);
    if (off_bits < 0) {
        fprintf(stderr, "el tamaño de página debe ser potencia de 2\n");
        return 1;
    }

    // Leer la tabla de páginas: pt[vpn] = pfn, o -1 si la entrada es inválida.
    long pt[MAXPAGES];
    int npages = 0;
    long maxpfn = 0;
    char *copy = strdup(argv[2]);
    for (char *t = strtok(copy, ","); t != NULL && npages < MAXPAGES; t = strtok(NULL, ",")) {
        pt[npages] = strcmp(t, "-") == 0 ? -1 : strtol(t, NULL, 0);
        if (pt[npages] > maxpfn)
            maxpfn = pt[npages];
        npages++;
    }
    free(copy);
    int vpn_bits = log2_exact(npages);
    if (vpn_bits < 0) {
        fprintf(stderr, "el número de entradas debe ser potencia de 2\n");
        return 1;
    }
    int pfn_bits = 1;
    while ((1L << pfn_bits) <= maxpfn)
        pfn_bits++;

    printf("página de %lu bytes -> offset de %d bits\n", page, off_bits);
    printf("%d páginas virtuales -> VPN de %d bits (direcciones de %d bits)\n\n",
           npages, vpn_bits, vpn_bits + off_bits);

    for (int a = 3; a < argc; a++) {
        unsigned long va = strtoul(argv[a], NULL, 0);
        printf("VA 0x%04lx = ", va);
        if (va >> (vpn_bits + off_bits)) {
            printf("fuera del espacio de direcciones\n\n");
            continue;
        }
        // Lo mismo que hace la MMU: separar VPN y offset con shift y máscara.
        unsigned long vpn = va >> off_bits;
        unsigned long offset = va & (page - 1);
        print_bits(vpn, vpn_bits);
        printf(" | ");
        print_bits(offset, off_bits);
        printf("\n  VPN = %lu, offset = 0x%lx\n", vpn, offset);
        if (pt[vpn] < 0) {
            printf("  PTE[%lu] inválida -> excepción (fallo de segmentación)\n\n", vpn);
            continue;
        }
        unsigned long pfn = (unsigned long)pt[vpn];
        unsigned long pa = (pfn << off_bits) | offset;
        printf("  PTE[%lu]: PFN = %lu = 0x%lx\n", vpn, pfn, pfn);
        printf("  PA = ");
        print_bits(pfn, pfn_bits);
        printf(" | ");
        print_bits(offset, off_bits);
        printf(" = 0x%04lx\n\n", pa);
    }
    return 0;
}

CFLAGS = -Wall -Wextra -g
PROGS  = heapdemo heaptest fits translate ptsize sv39

all: $(PROGS)

heapdemo: heapdemo.c mymalloc.c mymalloc.h
	$(CC) $(CFLAGS) -o $@ heapdemo.c mymalloc.c

heaptest: heaptest.c mymalloc.c mymalloc.h
	$(CC) $(CFLAGS) -o $@ heaptest.c mymalloc.c

# Corre las pruebas del asignador.
test: heaptest
	./heaptest

clean:
	rm -f $(PROGS)

.PHONY: all test clean