Implement replaycache_t for bug 6177, and unit tests for the preceding

1 files changed, 215 insertions, 0 deletions

diff --git a/src/or/replaycache.c b/src/or/replaycache.c
new file mode 100644
index 000000000..09104a937
--- /dev/null
+++ b/src/or/replaycache.c
@@ -0,0 +1,215 @@
+ /* Copyright (c) 2012, The Tor Project, Inc. */
+ /* See LICENSE for licensing information */
+
+/*
+ * \file replaycache.c
+ *
+ * \brief Self-scrubbing replay cache for rendservice.c
+ */
+
+#define REPLAYCACHE_PRIVATE
+
+#include "or.h"
+#include "replaycache.h"
+
+/** Free the replaycache r and all of its entries.
+ */
+
+void
+replaycache_free(replaycache_t *r)
+{
+  if (!r) {
+    log_info(LD_BUG, "replaycache_free() called on NULL");
+    return;
+  }
+
+  if (r->digests_seen) digestmap_free(r->digests_seen, _tor_free);
+
+  tor_free(r);
+}
+
+/** Allocate a new, empty replay detection cache, where horizon is the time
+ * for entries to age out and interval is the time after which the cache
+ * should be scrubbed for old entries.
+ */
+
+replaycache_t *
+replaycache_new(time_t horizon, time_t interval)
+{
+  replaycache_t *r = NULL;
+
+  if (horizon < 0) {
+    log_info(LD_BUG, "replaycache_new() called with negative"
+        " horizon parameter");
+    goto err;
+  }
+
+  if (interval < 0) {
+    log_info(LD_BUG, "replaycache_new() called with negative interval"
+        " parameter");
+    interval = 0;
+  }
+
+  r = tor_malloc(sizeof(*r));
+  r->scrub_interval = interval;
+  r->scrubbed = 0;
+  r->horizon = horizon;
+  r->digests_seen = digestmap_new();
+
+ err:
+  return r;
+}
+
+/** See documentation for replaycache_add_and_test()
+ */
+
+int
+replaycache_add_and_test_internal(
+    time_t present, replaycache_t *r, const void *data, int len,
+    time_t *elapsed)
+{
+  int rv = 0;
+  char digest[DIGEST_LEN];
+  time_t *access_time;
+
+  /* sanity check */
+  if (present <= 0 || !r || !data || len <= 0) {
+    log_info(LD_BUG, "replaycache_add_and_test_internal() called with stupid"
+        " parameters; please fix this.");
+    goto done;
+  }
+
+  /* compute digest */
+  crypto_digest(digest, (const char *)data, len);
+
+  /* check map */
+  access_time = digestmap_get(r->digests_seen, digest);
+
+  /* seen before? */
+  if (access_time != NULL) {
+    /*
+     * If it's far enough in the past, no hit.  If the horizon is zero, we
+     * never expire.
+     */
+    if (*access_time >= present - r->horizon || r->horizon == 0) {
+      /* replay cache hit, return 1 */
+      rv = 1;
+      /* If we want to output an elapsed time, do so */
+      if (elapsed) {
+        if (present >= *access_time) {
+          *elapsed = present - *access_time;
+        } else {
+          /* We shouldn't really be seeing hits from the future, but... */
+          *elapsed = 0;
+        }
+      }
+    }
+    /*
+     * If it's ahead of the cached time, update
+     */
+    if (*access_time < present) {
+      *access_time = present;
+    }
+  } else {
+    /* No, so no hit and update the digest map with the current time */
+    access_time = tor_malloc(sizeof(*access_time));
+    *access_time = present;
+    digestmap_set(r->digests_seen, digest, access_time);
+  }
+
+  /* now scrub the cache if it's time */
+  replaycache_scrub_if_needed_internal(present, r);
+
+ done:
+  return rv;
+}
+
+/** See documentation for replaycache_scrub_if_needed()
+ */
+
+void
+replaycache_scrub_if_needed_internal(time_t present, replaycache_t *r)
+{
+  digestmap_iter_t *itr = NULL;
+  const char *digest;
+  void *valp;
+  time_t *access_time;
+  char scrub_this;
+
+  /* sanity check */
+  if (!r || !(r->digests_seen)) {
+    log_info(LD_BUG, "replaycache_scrub_if_needed_internal() called with"
+        " stupid parameters; please fix this.");
+    return;
+  }
+
+  /* scrub time yet? (scrubbed == 0 indicates never scrubbed before) */
+  if (present - r->scrubbed < r->scrub_interval && r->scrubbed > 0) return;
+
+  /* if we're never expiring, don't bother scrubbing */
+  if (r->horizon == 0) return;
+
+  /* okay, scrub time */
+  itr = digestmap_iter_init(r->digests_seen);
+  while (!digestmap_iter_done(itr)) {
+    scrub_this = 0;
+    digestmap_iter_get(itr, &digest, &valp);
+    access_time = (time_t *)valp;
+    if (access_time) {
+      /* aged out yet? */
+      if (*access_time < present - r->horizon) scrub_this = 1;
+    } else {
+      /* Buh? Get rid of it, anyway */
+      log_info(LD_BUG, "replaycache_scrub_if_needed_internal() saw a NULL"
+          " entry in the digestmap.");
+      scrub_this = 1;
+    }
+
+    if (scrub_this) {
+      /* Advance the iterator and remove this one */
+      itr = digestmap_iter_next_rmv(r->digests_seen, itr);
+      /* Free the value removed */
+      tor_free(access_time);
+    } else {
+      /* Just advance the iterator */
+      itr = digestmap_iter_next(r->digests_seen, itr);
+    }
+  }
+
+  /* update scrubbed timestamp */
+  if (present > r->scrubbed) r->scrubbed = present;
+}
+
+/** Test the buffer of length len point to by data against the replay cache r;
+ * the digest of the buffer will be added to the cache at the current time,
+ * and the function will return 1 if it was already seen within the cache's
+ * horizon, or 0 otherwise.
+ */
+
+int
+replaycache_add_and_test(replaycache_t *r, const void *data, int len)
+{
+  return replaycache_add_and_test_internal(time(NULL), r, data, len, NULL);
+}
+
+/** Like replaycache_add_and_test(), but if it's a hit also return the time
+ * elapsed since this digest was last seen.
+ */
+
+int
+replaycache_add_test_and_elapsed(
+    replaycache_t *r, const void *data, int len, time_t *elapsed)
+{
+  return replaycache_add_and_test_internal(time(NULL), r, data, len, elapsed);
+}
+
+/** Scrub aged entries out of r if sufficiently long has elapsed since r was
+ * last scrubbed.
+ */
+
+void
+replaycache_scrub_if_needed(replaycache_t *r)
+{
+  replaycache_scrub_if_needed_internal(time(NULL), r);
+}
+