replaycache.c 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204
  1. /* Copyright (c) 2012-2013, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. /*
  4. * \file replaycache.c
  5. *
  6. * \brief Self-scrubbing replay cache for rendservice.c
  7. */
  8. #define REPLAYCACHE_PRIVATE
  9. #include "or.h"
  10. #include "replaycache.h"
  11. /** Free the replaycache r and all of its entries.
  12. */
  13. void
  14. replaycache_free(replaycache_t *r)
  15. {
  16. if (!r) {
  17. log_info(LD_BUG, "replaycache_free() called on NULL");
  18. return;
  19. }
  20. if (r->digests_seen) digestmap_free(r->digests_seen, tor_free_);
  21. tor_free(r);
  22. }
  23. /** Allocate a new, empty replay detection cache, where horizon is the time
  24. * for entries to age out and interval is the time after which the cache
  25. * should be scrubbed for old entries.
  26. */
  27. replaycache_t *
  28. replaycache_new(time_t horizon, time_t interval)
  29. {
  30. replaycache_t *r = NULL;
  31. if (horizon < 0) {
  32. log_info(LD_BUG, "replaycache_new() called with negative"
  33. " horizon parameter");
  34. goto err;
  35. }
  36. if (interval < 0) {
  37. log_info(LD_BUG, "replaycache_new() called with negative interval"
  38. " parameter");
  39. interval = 0;
  40. }
  41. r = tor_malloc(sizeof(*r));
  42. r->scrub_interval = interval;
  43. r->scrubbed = 0;
  44. r->horizon = horizon;
  45. r->digests_seen = digestmap_new();
  46. err:
  47. return r;
  48. }
  49. /** See documentation for replaycache_add_and_test()
  50. */
  51. STATIC int
  52. replaycache_add_and_test_internal(
  53. time_t present, replaycache_t *r, const void *data, size_t len,
  54. time_t *elapsed)
  55. {
  56. int rv = 0;
  57. char digest[DIGEST_LEN];
  58. time_t *access_time;
  59. /* sanity check */
  60. if (present <= 0 || !r || !data || len == 0) {
  61. log_info(LD_BUG, "replaycache_add_and_test_internal() called with stupid"
  62. " parameters; please fix this.");
  63. goto done;
  64. }
  65. /* compute digest */
  66. crypto_digest(digest, (const char *)data, len);
  67. /* check map */
  68. access_time = digestmap_get(r->digests_seen, digest);
  69. /* seen before? */
  70. if (access_time != NULL) {
  71. /*
  72. * If it's far enough in the past, no hit. If the horizon is zero, we
  73. * never expire.
  74. */
  75. if (*access_time >= present - r->horizon || r->horizon == 0) {
  76. /* replay cache hit, return 1 */
  77. rv = 1;
  78. /* If we want to output an elapsed time, do so */
  79. if (elapsed) {
  80. if (present >= *access_time) {
  81. *elapsed = present - *access_time;
  82. } else {
  83. /* We shouldn't really be seeing hits from the future, but... */
  84. *elapsed = 0;
  85. }
  86. }
  87. }
  88. /*
  89. * If it's ahead of the cached time, update
  90. */
  91. if (*access_time < present) {
  92. *access_time = present;
  93. }
  94. } else {
  95. /* No, so no hit and update the digest map with the current time */
  96. access_time = tor_malloc(sizeof(*access_time));
  97. *access_time = present;
  98. digestmap_set(r->digests_seen, digest, access_time);
  99. }
  100. /* now scrub the cache if it's time */
  101. replaycache_scrub_if_needed_internal(present, r);
  102. done:
  103. return rv;
  104. }
  105. /** See documentation for replaycache_scrub_if_needed()
  106. */
  107. STATIC void
  108. replaycache_scrub_if_needed_internal(time_t present, replaycache_t *r)
  109. {
  110. digestmap_iter_t *itr = NULL;
  111. const char *digest;
  112. void *valp;
  113. time_t *access_time;
  114. /* sanity check */
  115. if (!r || !(r->digests_seen)) {
  116. log_info(LD_BUG, "replaycache_scrub_if_needed_internal() called with"
  117. " stupid parameters; please fix this.");
  118. return;
  119. }
  120. /* scrub time yet? (scrubbed == 0 indicates never scrubbed before) */
  121. if (present - r->scrubbed < r->scrub_interval && r->scrubbed > 0) return;
  122. /* if we're never expiring, don't bother scrubbing */
  123. if (r->horizon == 0) return;
  124. /* okay, scrub time */
  125. itr = digestmap_iter_init(r->digests_seen);
  126. while (!digestmap_iter_done(itr)) {
  127. digestmap_iter_get(itr, &digest, &valp);
  128. access_time = (time_t *)valp;
  129. /* aged out yet? */
  130. if (*access_time < present - r->horizon) {
  131. /* Advance the iterator and remove this one */
  132. itr = digestmap_iter_next_rmv(r->digests_seen, itr);
  133. /* Free the value removed */
  134. tor_free(access_time);
  135. } else {
  136. /* Just advance the iterator */
  137. itr = digestmap_iter_next(r->digests_seen, itr);
  138. }
  139. }
  140. /* update scrubbed timestamp */
  141. if (present > r->scrubbed) r->scrubbed = present;
  142. }
  143. /** Test the buffer of length len point to by data against the replay cache r;
  144. * the digest of the buffer will be added to the cache at the current time,
  145. * and the function will return 1 if it was already seen within the cache's
  146. * horizon, or 0 otherwise.
  147. */
  148. int
  149. replaycache_add_and_test(replaycache_t *r, const void *data, size_t len)
  150. {
  151. return replaycache_add_and_test_internal(time(NULL), r, data, len, NULL);
  152. }
  153. /** Like replaycache_add_and_test(), but if it's a hit also return the time
  154. * elapsed since this digest was last seen.
  155. */
  156. int
  157. replaycache_add_test_and_elapsed(
  158. replaycache_t *r, const void *data, size_t len, time_t *elapsed)
  159. {
  160. return replaycache_add_and_test_internal(time(NULL), r, data, len, elapsed);
  161. }
  162. /** Scrub aged entries out of r if sufficiently long has elapsed since r was
  163. * last scrubbed.
  164. */
  165. void
  166. replaycache_scrub_if_needed(replaycache_t *r)
  167. {
  168. replaycache_scrub_if_needed_internal(time(NULL), r);
  169. }