/* This software was written by Dirk Engling <erdgeist@erdgeist.org>
   It is considered beerware. Prost. Skol. Cheers or whatever.

   $id$ */

/* System */
#include <pthread.h>
#include <stdatomic.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

/* Opentracker */
#include "ot_fdstate.h"
#include "test.h"

/* ------------------------------------------------------- one thread first */

static void case_open_claim_release(void) {
  char     cookie[4];
  uint32_t generation;

  test_case("a descriptor taken into the table can be claimed and gives back its cookie");
  generation = fdstate_open(7, cookie, 0);
  CHECK_INT(fdstate_claim(7, generation), 1);
  CHECK_PTR(fdstate_cookie(7), cookie);
  fdstate_release(7);

  test_case("and can be claimed again once released");
  CHECK_INT(fdstate_claim(7, generation), 1);
  fdstate_release(7);
  fdstate_close(7);
}

static void case_one_holder_at_a_time(void) {
  uint32_t generation = fdstate_open(8, NULL, 0);

  test_case("a descriptor somebody holds cannot be claimed again");
  CHECK_INT(fdstate_claim(8, generation), 1);
  CHECK_INT(fdstate_claim(8, generation), 0);
  fdstate_release(8);
  CHECK_INT(fdstate_claim(8, generation), 1);
  fdstate_release(8);
  fdstate_close(8);
}

static void case_stale_generation_is_refused(void) {
  char     first[4], second[4];
  uint32_t old, new;

  test_case("a caller quoting the generation of a closed descriptor is turned away");
  old = fdstate_open(9, first, 0);
  fdstate_close(9);
  new = fdstate_open(9, second, 0);
  CHECK(old != new);
  CHECK_INT(fdstate_claim(9, old), 0);

  test_case("while the one quoting the new generation gets the new cookie");
  CHECK_INT(fdstate_claim(9, new), 1);
  CHECK_PTR(fdstate_cookie(9), second);
  fdstate_release(9);
  fdstate_close(9);
}

static void case_expiry(void) {
  uint32_t generation = fdstate_open(10, NULL, 100);

  test_case("a descriptor past its expiry is collected");
  CHECK_INT(fdstate_claim_expired(10, 99), 0);
  CHECK_INT(fdstate_claim_expired(10, 100), 1);
  fdstate_close(10);

  test_case("one that never expires is never collected");
  generation = fdstate_open(10, NULL, 0);
  CHECK_INT(fdstate_claim_expired(10, 1 << 30), 0);

  test_case("and one somebody is working on is left alone");
  fdstate_set_expiry(10, 1);
  CHECK_INT(fdstate_claim(10, generation), 1);
  CHECK_INT(fdstate_claim_expired(10, 1 << 30), 0);
  fdstate_release(10);
  CHECK_INT(fdstate_claim_expired(10, 1 << 30), 1);
  fdstate_close(10);
}

static void case_out_of_range(void) {
  test_case("a descriptor outside the table is refused rather than trusted");
  CHECK_INT(fdstate_claim(-1, 0), 0);
  CHECK_INT(fdstate_claim((int)fdstate_slots(), 0), 0);
  CHECK_INT(fdstate_claim_expired(-1, 0), 0);
  CHECK_PTR(fdstate_cookie(-1), NULL);
}

/* --------------------------------------------------------- then in anger */

/* The race this is about only exists while a descriptor is being recycled,
   so recycling is driven by work done rather than by a clock: every slot is
   given up after RECYCLE_AFTER claims, whatever the machine's speed. */

#define STRESS_SLOTS   64
#define RECYCLE_AFTER  32
#define STRESS_CLAIMS  200000
#define STRESS_GIVEUP  (STRESS_CLAIMS * 100)

static _Atomic long     stress_claims, stress_recycles, stress_violations, stress_attempts;
static _Atomic int      stress_lives[STRESS_SLOTS];
static _Atomic int      stress_live[STRESS_SLOTS];

/* Generation and cookie are published in one word so a worker can never read
   a cookie that belongs to a different generation than the one it claimed
   with. Each connection gets a cookie nobody else ever gets. */
static _Atomic uint64_t stress_conn[STRESS_SLOTS];
static _Atomic uint64_t stress_next_cookie;

#define STRESS_CONN(cookie, gen) (((uint64_t)(cookie) << 32) | (uint32_t)(gen))
#define STRESS_CONN_COOKIE(w)    ((void *)(uintptr_t)((w) >> 32))
#define STRESS_CONN_GEN(w)       ((uint32_t)(w))

static int stress_running(void) {
  return atomic_load(&stress_claims) < STRESS_CLAIMS && atomic_load(&stress_attempts) < STRESS_GIVEUP;
}

static void *stress_worker(void *arg) {
  unsigned seed = (unsigned)(uintptr_t)arg;

  while (stress_running()) {
    int      fd   = (int)(rand_r(&seed) % STRESS_SLOTS);
    uint64_t conn = atomic_load(&stress_conn[fd]);

    atomic_fetch_add(&stress_attempts, 1);
    if (!fdstate_claim(fd, STRESS_CONN_GEN(conn)))
      continue;

    if (fdstate_cookie(fd) != STRESS_CONN_COOKIE(conn))
      atomic_fetch_add(&stress_violations, 1);
    if (atomic_fetch_sub(&stress_lives[fd], 1) <= 1)
      fdstate_set_expiry(fd, 1); /* retired by its holder, as a handler would */
    if (fdstate_cookie(fd) != STRESS_CONN_COOKIE(conn))
      atomic_fetch_add(&stress_violations, 1);

    fdstate_release(fd);
    atomic_fetch_add(&stress_claims, 1);
  }
  return NULL;
}

static void *stress_keeper(void *arg) {
  (void)arg;
  while (stress_running()) {
    int fd;

    for (fd = 0; fd < STRESS_SLOTS; ++fd) {
      if (atomic_load(&stress_live[fd])) {
        if (!fdstate_claim_expired(fd, 1))
          continue;                            /* a worker has it, come back */
        fdstate_close(fd);
        atomic_store(&stress_live[fd], 0);
        atomic_fetch_add(&stress_recycles, 1);
      }
      {
        void    *cookie = (void *)(uintptr_t)(atomic_fetch_add(&stress_next_cookie, 1) + 1);
        uint32_t gen    = fdstate_open(fd, cookie, 0);

        atomic_store(&stress_lives[fd], RECYCLE_AFTER);
        atomic_store(&stress_conn[fd], STRESS_CONN((uintptr_t)cookie, gen));
        atomic_store(&stress_live[fd], 1);
      }
    }
  }
  return NULL;
}

static void case_recycling_under_load(void) {
  pthread_t worker[4], keeper;
  size_t    i;

  test_case("no worker is ever handed a connection from another generation");
  atomic_store(&stress_claims, 0);
  atomic_store(&stress_recycles, 0);
  atomic_store(&stress_violations, 0);
  atomic_store(&stress_attempts, 0);
  atomic_store(&stress_next_cookie, 0);
  /* Every slot is opened and published before any worker runs: a worker only
     ever learns of a descriptor from whoever registered it, and never
     invents a generation of its own. */
  for (i = 0; i < STRESS_SLOTS; ++i) {
    void    *cookie = (void *)(uintptr_t)(atomic_fetch_add(&stress_next_cookie, 1) + 1);
    uint32_t gen    = fdstate_open((int)i, cookie, 0);

    atomic_store(&stress_lives[i], RECYCLE_AFTER);
    atomic_store(&stress_conn[i], STRESS_CONN((uintptr_t)cookie, gen));
    atomic_store(&stress_live[i], 1);
  }

  pthread_create(&keeper, NULL, stress_keeper, NULL);
  for (i = 0; i < sizeof(worker) / sizeof(worker[0]); ++i)
    pthread_create(&worker[i], NULL, stress_worker, (void *)(uintptr_t)(i + 1));
  for (i = 0; i < sizeof(worker) / sizeof(worker[0]); ++i)
    pthread_join(worker[i], NULL);
  pthread_join(keeper, NULL);

  CHECK_INT(atomic_load(&stress_violations), 0);

  test_case("and the run actually recycled descriptors, or it proved nothing");
  CHECK(atomic_load(&stress_claims) >= STRESS_CLAIMS);
  CHECK(atomic_load(&stress_recycles) > STRESS_CLAIMS / (RECYCLE_AFTER * 4));

  for (i = 0; i < STRESS_SLOTS; ++i)
    fdstate_close((int)i);
}

void test_fdstate(void) {
  CHECK_INT(fdstate_init(), 0);
  CHECK(fdstate_slots() > STRESS_SLOTS);

  case_open_claim_release();
  case_one_holder_at_a_time();
  case_stale_generation_is_refused();
  case_expiry();
  case_out_of_range();
  case_recycling_under_load();

  fdstate_deinit();
}