1 files changed, 224 insertions, 0 deletions

diff --git a/tests/t_fdstate.c b/tests/t_fdstate.c
new file mode 100644
index 0000000..bf8724a
--- /dev/null
+++ b/tests/t_fdstate.c
@@ -0,0 +1,224 @@
+/* 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();
+}