// ftl.c — un FTL log-structured de juguete: amplificación de escritura y desgaste.
//
// Uso: ./ftl OCUPACION [hot]
//   OCUPACION  porcentaje (10..90) de la capacidad física que ocupan los datos
//   hot        el 80 % de las escrituras va al 20 % de las páginas lógicas
//
// La SSD tiene NBLK bloques de PPB páginas. Se escriben primero todas las
// páginas lógicas y luego 20 sobrescrituras por página, al azar. Cuando quedan
// menos de GC_LOW bloques libres, el recolector (GC) elige el bloque con menos
// páginas vivas (greedy), copia esas páginas al log y borra el bloque.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NBLK 128
#define PPB 32
#define NPAGES (NBLK * PPB)
#define GC_LOW 2

static int map[NPAGES];      // página lógica -> página física (-1: nunca escrita)
static int owner[NPAGES];    // página física -> página lógica (-1: libre o muerta)
static int live[NBLK];       // páginas vivas por bloque
static int erases[NBLK];     // borrados por bloque
static int wp[NBLK];         // siguiente página libre del bloque
static int freeq[NBLK], qhead, nfree;  // cola FIFO de bloques borrados
static int active;           // bloque donde se escribe el log
static long host_writes, gc_writes;

static unsigned long long rng = 88172645463325252ULL;
static unsigned rnd(void) {   // xorshift: mismo resultado en cualquier máquina
    rng ^= rng << 13;
    rng ^= rng >> 7;
    rng ^= rng << 17;
    return (unsigned)(rng >> 11);
}

static void push_free(int b) {
    freeq[(qhead + nfree++) % NBLK] = b;
}

static int pop_free(void) {
    int b = freeq[qhead];
    qhead = (qhead + 1) % NBLK;
    nfree--;
    return b;
}

// Escribe la página lógica lpn al final del log.
static void append(int lpn) {
    if (wp[active] == PPB)
        active = pop_free();
    int ppn = active * PPB + wp[active]++;
    map[lpn] = ppn;
    owner[ppn] = lpn;
    live[active]++;
}

static void gc(void) {
    int victim = -1;
    for (int b = 0; b < NBLK; b++)        // solo bloques llenos y no activos
        if (b != active && wp[b] == PPB && (victim < 0 || live[b] < live[victim]))
            victim = b;
    if (victim < 0 || live[victim] == PPB) {
        fprintf(stderr, "sin espacio para recolectar\n");
        exit(1);
    }
    for (int i = 0; i < PPB; i++) {       // copiar las páginas vivas
        int lpn = owner[victim * PPB + i];
        if (lpn >= 0) {
            owner[victim * PPB + i] = -1;
            append(lpn);
            gc_writes++;
        }
    }
    live[victim] = 0;                     // borrar el bloque completo
    wp[victim] = 0;
    erases[victim]++;
    push_free(victim);
}

static void host_write(int lpn) {
    if (map[lpn] >= 0) {                  // la versión anterior queda muerta
        owner[map[lpn]] = -1;
        live[map[lpn] / PPB]--;
    }
    while (nfree < GC_LOW)
        gc();
    append(lpn);
    host_writes++;
}

int main(int argc, char *argv[]) {
    int util = argc > 1 ? atoi(argv[1]) : 0;
    int hot = argc > 2 && strcmp(argv[2], "hot") == 0;
    if (util < 10 || util > 90) {
        fprintf(stderr, "uso: %s OCUPACION(10..90) [hot]\n", argv[0]);
        return 1;
    }
    int nlog = NPAGES * util / 100;

    memset(map, -1, sizeof(map));
    memset(owner, -1, sizeof(owner));
    for (int b = 1; b < NBLK; b++)
        push_free(b);
    active = 0;

    for (int l = 0; l < nlog; l++)        // llenado inicial
        host_write(l);
    host_writes = gc_writes = 0;
    memset(erases, 0, sizeof(erases));

    long total = 20L * nlog;
    int nhot = nlog / 5;
    for (long i = 0; i < total; i++) {
        int lpn;
        if (hot && rnd() % 100 < 80)
            lpn = rnd() % nhot;
        else if (hot)
            lpn = nhot + rnd() % (nlog - nhot);
        else
            lpn = rnd() % nlog;
        host_write(lpn);
    }

    int emin = erases[0], emax = erases[0];
    long esum = 0;
    for (int b = 0; b < NBLK; b++) {
        if (erases[b] < emin) emin = erases[b];
        if (erases[b] > emax) emax = erases[b];
        esum += erases[b];
    }
    printf("ocupación %2d%%%s: escrituras del host %ld, copias del GC %ld\n",
           util, hot ? " (hot/cold)" : "", host_writes, gc_writes);
    printf("  amplificación de escritura = %.2f\n",
           (double)(host_writes + gc_writes) / host_writes);
    printf("  borrados por bloque: mín %d, prom %.1f, máx %d\n",
           emin, (double)esum / NBLK, emax);
    return 0;
}