// ptcalc.c — calculadora de tablas de páginas multinivel.
//
// Uso:   ./ptcalc bits_va tamaño_página tamaño_pte dirección...
//
// Con los parámetros de la máquina calcula cuántos niveles hacen falta para
// que cada nodo de la tabla quepa en una página, separa cada dirección en sus
// índices y compara cuánta memoria ocupa la tabla lineal frente a la
// multinivel si el proceso solo usa las páginas de las direcciones dadas.
//
// Ejemplos:
//   ./ptcalc 32 4096 4 0x00403A7C              x86 de 32 bits (10/10/12)
//   ./ptcalc 39 4096 8 0x80604567              RISC-V Sv39 (9/9/9/12)
//   ./ptcalc 15 32 1 0x611c                    simulador del cap. 20 (5/5/5)
#include <stdio.h>
#include <stdlib.h>

#define MAXLEVELS 8
#define MAXADDRS  64

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

static void print_size(unsigned long long bytes) {
    if (bytes >= (1ULL << 30))
        printf("%llu GB", bytes >> 30);
    else if (bytes >= (1ULL << 20))
        printf("%llu MB", bytes >> 20);
    else if (bytes >= (1ULL << 10))
        printf("%llu KB", bytes >> 10);
    else
        printf("%llu B", bytes);
}

int main(int argc, char *argv[]) {
    if (argc < 5) {
        fprintf(stderr, "uso: %s bits_va tamaño_página tamaño_pte dirección...\n", argv[0]);
        return 1;
    }
    int va_bits = atoi(argv[1]);
    unsigned long page = strtoul(argv[2], NULL, 0);
    unsigned long pte = strtoul(argv[3], NULL, 0);
    int off_bits = log2_exact(page);
    int pte_bits = log2_exact(pte);
    if (va_bits < 1 || va_bits > 64 || off_bits < 0 || pte_bits < 0 || pte > page) {
        fprintf(stderr, "parámetros inválidos (página y PTE deben ser potencias de 2)\n");
        return 1;
    }

    // Geometría: una página de tabla guarda page/pte entradas, así que cada
    // nivel consume idx_bits bits del VPN. El nivel de arriba se queda con lo
    // que sobra (puede tener menos bits).
    int vpn_bits = va_bits - off_bits;
    int idx_bits = off_bits - pte_bits;
    int levels = (vpn_bits + idx_bits - 1) / idx_bits;
    if (levels > MAXLEVELS) {
        fprintf(stderr, "demasiados niveles\n");
        return 1;
    }
    int bits[MAXLEVELS]; // bits[0] = nivel de arriba (el directorio)
    for (int l = 0; l < levels; l++)
        bits[l] = idx_bits;
    bits[0] = vpn_bits - idx_bits * (levels - 1);

    printf("VA de %d bits, páginas de %lu B, PTE de %lu B\n", va_bits, page, pte);
    printf("offset: %d bits   VPN: %d bits   %lu PTE por página\n", off_bits, vpn_bits,
           page / pte);
    printf("niveles: %d   bits por índice:", levels);
    for (int l = 0; l < levels; l++)
        printf(" %d", bits[l]);
    printf("\n");
    printf("tabla lineal: 2^%d PTE x %lu B = ", vpn_bits, pte);
    print_size((1ULL << vpn_bits) * pte);
    printf("\n\n");

    // Separar cada dirección en sus índices.
    int n = 0;
    unsigned long long vpn[MAXADDRS];
    for (int a = 4; a < argc && n < MAXADDRS; a++, n++) {
        unsigned long long va = strtoull(argv[a], NULL, 0);
        if (va_bits < 64 && (va >> va_bits) != 0) {
            fprintf(stderr, "%s no cabe en %d bits\n", argv[a], va_bits);
            return 1;
        }
        vpn[n] = va >> off_bits;
        printf("0x%llx -> ", va);
        int shift = vpn_bits;
        for (int l = 0; l < levels; l++) {
            shift -= bits[l];
            printf("L%d=0x%llx ", levels - 1 - l, (vpn[n] >> shift) & ((1ULL << bits[l]) - 1));
        }
        printf("offset=0x%llx\n", va & (page - 1));
    }

    // ¿Cuántas páginas de tabla hacen falta para mapear solo esas páginas?
    // En el nivel l hay un nodo por cada prefijo distinto del VPN de largo
    // (bits de los niveles anteriores). El directorio de arriba siempre existe.
    unsigned long long nodes = 0;
    int prefix = 0;
    for (int l = 0; l < levels; l++) {
        unsigned long long seen[MAXADDRS];
        int count = 0;
        for (int i = 0; i < n; i++) {
            unsigned long long p = prefix ? vpn[i] >> (vpn_bits - prefix) : 0;
            int dup = 0;
            for (int j = 0; j < count; j++)
                dup |= (seen[j] == p);
            if (!dup)
                seen[count++] = p;
        }
        if (count == 0)
            count = 1;
        printf("%snivel %d: %d página(s)\n", l == 0 ? "\n" : "", levels - 1 - l, count);
        nodes += count;
        prefix += bits[l];
    }
    printf("multinivel: %llu páginas x %lu B = ", nodes, page);
    print_size(nodes * page);
    printf("\n");
    printf("fallo de TLB: %d accesos a la tabla + 1 al dato = %d accesos a memoria\n",
           levels, levels + 1);
    return 0;
}

#!/bin/bash
# run-tlb.sh — ejecuta ./tlb para 1, 2, 4, ... páginas, con páginas de 4 KB
# y pidiendo páginas grandes (THP), y muestra los resultados en una tabla.
# La última columna dice cuántos KB quedaron de verdad en páginas grandes:
# una región de menos de 2 MB no puede usarlas.
#
# Uso:   ./run-tlb.sh [máximo_de_páginas]     (por defecto 32768)
set -e
MAX=${1:-32768}
ACCESSES=10000000   # accesos por medición: ~10^7 para que el reloj sea preciso

printf "%7s %10s %8s %8s %10s\n" "páginas" "memoria" "ns 4KB" "ns THP" "KB en THP"
p=1
while [ "$p" -le "$MAX" ]; do
    trials=$(( ACCESSES / p ))
    [ "$trials" -lt 10 ] && trials=10
    read -r _ small _ < <(./tlb "$p" "$trials")
    read -r _ big hugekb < <(./tlb "$p" "$trials" huge)
    printf "%7d %7d KB %8s %8s %10s\n" "$p" $(( p * 4 )) "$small" "$big" "$hugekb"
    p=$(( p * 2 ))
done

CFLAGS = -Wall -Wextra -g
PROGS  = tlb ptcalc
# Las soluciones aún no publicadas (code/.ocultos) no están en el repositorio:
# se omiten los programas sin fuente y sus líneas en las pruebas.
PROGS := $(foreach p,$(PROGS),$(if $(wildcard $(p).c),$(p)))
RUN    = $(if $(wildcard $(1).c),./$(1),@: sin $(1).c)

all: $(PROGS)

# -O2 reduce el costo del bucle; los accesos son volatile y no se eliminan.
tlb: CFLAGS += -O2

# Tabla de tiempos por acceso (tarda alrededor de un minuto).
bench: tlb
	./run-tlb.sh

clean:
	rm -f $(PROGS)

.PHONY: all bench clean