// deadlock.c — dos hilos, dos mutex y cuatro formas de tomarlos.
//
// Uso: ./deadlock naive    [iter]   cada hilo toma los locks en orden opuesto
//      ./deadlock ordered  [iter]   orden total: primero el de menor dirección
//      ./deadlock global   [iter]   un lock global alrededor de la adquisición
//      ./deadlock trylock  [iter]   trylock; si falla, suelta todo y reintenta
//
// Cada hilo repite `iter` veces (por omisión 100000): tomar dos locks,
// sumar, soltar. Un hilo vigilante (watchdog) revisa el avance cada 0.5 s;
// si en 2 s nadie avanzó, imprime qué lock tiene y cuál espera cada hilo
// (el grafo de espera) y termina el programa con código 0.
#define _GNU_SOURCE
#include <pthread.h>
#include <sched.h>
#include <stdatomic.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

enum mode { NAIVE, ORDERED, GLOBAL, TRYLOCK };

static pthread_mutex_t A = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t B = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t prevention = PTHREAD_MUTEX_INITIALIZER;

static enum mode mode;
static long iters = 100000;
static long counter;                    // protegido por A y B
static atomic_long progress;            // avance total, para el watchdog
static atomic_long retries;             // reintentos del modo trylock
static atomic_int done;

// Para el diagnóstico: qué lock tiene y cuál espera cada hilo.
static atomic_int holds[2] = {-1, -1};
static atomic_int wants[2] = {-1, -1};

static const char *name(pthread_mutex_t *m) { return m == &A ? "A" : "B"; }
static int id(pthread_mutex_t *m) { return m == &A ? 0 : 1; }

// Tomar m registrando la espera (solo para el diagnóstico).
static void take(int t, pthread_mutex_t *m) {
    atomic_store(&wants[t], id(m));
    pthread_mutex_lock(m);
    atomic_store(&wants[t], -1);
}

static void lock_both(int t, pthread_mutex_t *first, pthread_mutex_t *second) {
    switch (mode) {
    case NAIVE:                         // posible espera circular
        take(t, first);
        atomic_store(&holds[t], id(first));
        take(t, second);
        break;
    case ORDERED:                       // rompe la espera circular
        if (first > second) {           // comparar direcciones
            pthread_mutex_t *tmp = first;
            first = second;
            second = tmp;
        }
        take(t, first);
        atomic_store(&holds[t], id(first));
        take(t, second);
        break;
    case GLOBAL:                        // rompe retener y esperar
        pthread_mutex_lock(&prevention);
        take(t, first);
        take(t, second);
        pthread_mutex_unlock(&prevention);
        break;
    case TRYLOCK:                       // rompe "sin expropiación"
        for (;;) {
            take(t, first);
            if (pthread_mutex_trylock(second) == 0)
                break;
            pthread_mutex_unlock(first);    // soltar lo que tengo
            atomic_fetch_add(&retries, 1);
            sched_yield();                  // ceder un poco
        }
        break;
    }
    atomic_store(&holds[t], -1);
}

static void *worker(void *arg) {
    int t = (int)(long)arg;
    // El hilo 0 pide A y luego B; el hilo 1, B y luego A.
    pthread_mutex_t *first = t == 0 ? &A : &B;
    pthread_mutex_t *second = t == 0 ? &B : &A;
    for (long i = 0; i < iters; i++) {
        lock_both(t, first, second);
        counter++;                      // sección crítica
        pthread_mutex_unlock(second);
        pthread_mutex_unlock(first);
        atomic_fetch_add(&progress, 1);
    }
    return NULL;
}

static double seconds(struct timespec a, struct timespec b) {
    return (b.tv_sec - a.tv_sec) + (b.tv_nsec - a.tv_nsec) / 1e9;
}

// Revisa el avance; si se detiene 2 s, describe el ciclo y termina.
static void *watchdog(void *arg) {
    (void)arg;
    long last = -1;
    int still = 0;
    while (!atomic_load(&done)) {
        usleep(500000);
        long now = atomic_load(&progress);
        still = (now == last) ? still + 1 : 0;
        last = now;
        if (still < 4)
            continue;
        printf("watchdog: 2 s sin avance (%ld de %ld vueltas)\n",
               now, 2 * iters);
        for (int t = 0; t < 2; t++) {
            int h = atomic_load(&holds[t]), w = atomic_load(&wants[t]);
            printf("  hilo %d: tiene %s, espera %s\n", t,
                   h < 0 ? "-" : (h == 0 ? "A" : "B"),
                   w < 0 ? "-" : (w == 0 ? "A" : "B"));
        }
        int h0 = atomic_load(&holds[0]), w0 = atomic_load(&wants[0]);
        int h1 = atomic_load(&holds[1]), w1 = atomic_load(&wants[1]);
        if (h0 >= 0 && h0 == w1 && h1 >= 0 && h1 == w0)
            printf("  ciclo: H0 -> %s -> H1 -> %s -> H0: deadlock\n",
                   name(w0 == 0 ? &A : &B), name(w1 == 0 ? &A : &B));
        else
            printf("  sin ciclo en el grafo de espera\n");
        fflush(stdout);
        exit(0);                        // el deadlock era lo que queríamos ver
    }
    return NULL;
}

int main(int argc, char *argv[]) {
    const char *modes[] = {"naive", "ordered", "global", "trylock"};
    if (argc < 2) {
        fprintf(stderr, "uso: %s naive|ordered|global|trylock [iter]\n", argv[0]);
        return 1;
    }
    int found = 0;
    for (int i = 0; i < 4; i++)
        if (strcmp(argv[1], modes[i]) == 0) {
            mode = (enum mode)i;
            found = 1;
        }
    if (!found) {
        fprintf(stderr, "modo desconocido: %s\n", argv[1]);
        return 1;
    }
    if (argc > 2)
        iters = atol(argv[2]);

    struct timespec t0, t1;
    clock_gettime(CLOCK_MONOTONIC, &t0);
    pthread_t th[2], wd;
    pthread_create(&wd, NULL, watchdog, NULL);
    for (long t = 0; t < 2; t++)
        pthread_create(&th[t], NULL, worker, (void *)t);
    for (int t = 0; t < 2; t++)
        pthread_join(th[t], NULL);
    clock_gettime(CLOCK_MONOTONIC, &t1);
    atomic_store(&done, 1);
    pthread_join(wd, NULL);

    printf("%s: counter = %ld de %ld en %.3f s", modes[mode], counter,
           2 * iters, seconds(t0, t1));
    if (mode == TRYLOCK)
        printf("\n  %ld reintentos", atomic_load(&retries));
    printf("\n");
    return 0;
}