hs_cache.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385
  1. /* Copyright (c) 2016, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. /**
  4. * \file hs_cache.c
  5. * \brief Handle hidden service descriptor caches.
  6. **/
  7. /* For unit tests.*/
  8. #define HS_CACHE_PRIVATE
  9. #include "hs_cache.h"
  10. #include "or.h"
  11. #include "config.h"
  12. #include "hs_common.h"
  13. #include "hs_descriptor.h"
  14. #include "rendcache.h"
  15. /* Directory descriptor cache. Map indexed by blinded key. */
  16. static digest256map_t *hs_cache_v3_dir;
  17. /* Remove a given descriptor from our cache. */
  18. static void
  19. remove_v3_desc_as_dir(const hs_cache_dir_descriptor_t *desc)
  20. {
  21. tor_assert(desc);
  22. digest256map_remove(hs_cache_v3_dir, desc->key);
  23. }
  24. /* Store a given descriptor in our cache. */
  25. static void
  26. store_v3_desc_as_dir(hs_cache_dir_descriptor_t *desc)
  27. {
  28. tor_assert(desc);
  29. digest256map_set(hs_cache_v3_dir, desc->key, desc);
  30. }
  31. /* Query our cache and return the entry or NULL if not found. */
  32. static hs_cache_dir_descriptor_t *
  33. lookup_v3_desc_as_dir(const uint8_t *key)
  34. {
  35. tor_assert(key);
  36. return digest256map_get(hs_cache_v3_dir, key);
  37. }
  38. /* Free a directory descriptor object. */
  39. static void
  40. cache_dir_desc_free(hs_cache_dir_descriptor_t *desc)
  41. {
  42. if (desc == NULL) {
  43. return;
  44. }
  45. hs_desc_plaintext_data_free(desc->plaintext_data);
  46. tor_free(desc->encoded_desc);
  47. tor_free(desc);
  48. }
  49. /* Helper function: Use by the free all function using the digest256map
  50. * interface to cache entries. */
  51. static void
  52. cache_dir_desc_free_(void *ptr)
  53. {
  54. hs_cache_dir_descriptor_t *desc = ptr;
  55. cache_dir_desc_free(desc);
  56. }
  57. /* Create a new directory cache descriptor object from a encoded descriptor.
  58. * On success, return the heap-allocated cache object, otherwise return NULL if
  59. * we can't decode the descriptor. */
  60. static hs_cache_dir_descriptor_t *
  61. cache_dir_desc_new(const char *desc)
  62. {
  63. hs_cache_dir_descriptor_t *dir_desc;
  64. tor_assert(desc);
  65. dir_desc = tor_malloc_zero(sizeof(hs_cache_dir_descriptor_t));
  66. dir_desc->plaintext_data =
  67. tor_malloc_zero(sizeof(hs_desc_plaintext_data_t));
  68. dir_desc->encoded_desc = tor_strdup(desc);
  69. if (hs_desc_decode_plaintext(desc, dir_desc->plaintext_data) < 0) {
  70. log_debug(LD_DIR, "Unable to decode descriptor. Rejecting.");
  71. goto err;
  72. }
  73. /* The blinded pubkey is the indexed key. */
  74. dir_desc->key = dir_desc->plaintext_data->blinded_kp.pubkey.pubkey;
  75. dir_desc->created_ts = time(NULL);
  76. return dir_desc;
  77. err:
  78. cache_dir_desc_free(dir_desc);
  79. return NULL;
  80. }
  81. /* Return the size of a cache entry in bytes. */
  82. static size_t
  83. cache_get_entry_size(const hs_cache_dir_descriptor_t *entry)
  84. {
  85. return (sizeof(*entry) + hs_desc_plaintext_obj_size(entry->plaintext_data)
  86. + strlen(entry->encoded_desc));
  87. }
  88. /* Try to store a valid version 3 descriptor in the directory cache. Return 0
  89. * on success else a negative value is returned indicating that we have a
  90. * newer version in our cache. On error, caller is responsible to free the
  91. * given descriptor desc. */
  92. static int
  93. cache_store_v3_as_dir(hs_cache_dir_descriptor_t *desc)
  94. {
  95. hs_cache_dir_descriptor_t *cache_entry;
  96. tor_assert(desc);
  97. /* Verify if we have an entry in the cache for that key and if yes, check
  98. * if we should replace it? */
  99. cache_entry = lookup_v3_desc_as_dir(desc->key);
  100. if (cache_entry != NULL) {
  101. /* Only replace descriptor if revision-counter is greater than the one
  102. * in our cache */
  103. if (cache_entry->plaintext_data->revision_counter >=
  104. desc->plaintext_data->revision_counter) {
  105. log_info(LD_REND, "Descriptor revision counter in our cache is "
  106. "greater or equal than the one we received. "
  107. "Rejecting!");
  108. goto err;
  109. }
  110. /* We now know that the descriptor we just received is a new one so
  111. * remove the entry we currently have from our cache so we can then
  112. * store the new one. */
  113. remove_v3_desc_as_dir(cache_entry);
  114. rend_cache_decrement_allocation(cache_get_entry_size(cache_entry));
  115. cache_dir_desc_free(cache_entry);
  116. }
  117. /* Store the descriptor we just got. We are sure here that either we
  118. * don't have the entry or we have a newer descriptor and the old one
  119. * has been removed from the cache. */
  120. store_v3_desc_as_dir(desc);
  121. /* Update our total cache size with this entry for the OOM. This uses the
  122. * old HS protocol cache subsystem for which we are tied with. */
  123. rend_cache_increment_allocation(cache_get_entry_size(desc));
  124. /* XXX: Update HS statistics. We should have specific stats for v3. */
  125. return 0;
  126. err:
  127. return -1;
  128. }
  129. /* Using the query which is the base64 encoded blinded key of a version 3
  130. * descriptor, lookup in our directory cache the entry. If found, 1 is
  131. * returned and desc_out is populated with a newly allocated string being the
  132. * encoded descriptor. If not found, 0 is returned and desc_out is untouched.
  133. * On error, a negative value is returned and desc_out is untouched. */
  134. static int
  135. cache_lookup_v3_as_dir(const char *query, const char **desc_out)
  136. {
  137. int found = 0;
  138. ed25519_public_key_t blinded_key;
  139. const hs_cache_dir_descriptor_t *entry;
  140. tor_assert(query);
  141. /* Decode blinded key using the given query value. */
  142. if (ed25519_public_from_base64(&blinded_key, query) < 0) {
  143. log_info(LD_REND, "Unable to decode the v3 HSDir query %s.",
  144. safe_str_client(query));
  145. goto err;
  146. }
  147. entry = lookup_v3_desc_as_dir(blinded_key.pubkey);
  148. if (entry != NULL) {
  149. found = 1;
  150. if (desc_out) {
  151. *desc_out = entry->encoded_desc;
  152. }
  153. }
  154. return found;
  155. err:
  156. return -1;
  157. }
  158. /* Clean the v3 cache by removing any entry that has expired using the
  159. * <b>global_cutoff</b> value. If <b>global_cutoff</b> is 0, the cleaning
  160. * process will use the lifetime found in the plaintext data section. Return
  161. * the number of bytes cleaned. */
  162. STATIC size_t
  163. cache_clean_v3_as_dir(time_t now, time_t global_cutoff)
  164. {
  165. size_t bytes_removed = 0;
  166. /* Code flow error if this ever happens. */
  167. tor_assert(global_cutoff >= 0);
  168. if (!hs_cache_v3_dir) { /* No cache to clean. Just return. */
  169. return 0;
  170. }
  171. DIGEST256MAP_FOREACH_MODIFY(hs_cache_v3_dir, key,
  172. hs_cache_dir_descriptor_t *, entry) {
  173. size_t entry_size;
  174. time_t cutoff = global_cutoff;
  175. if (!cutoff) {
  176. /* Cutoff is the lifetime of the entry found in the descriptor. */
  177. cutoff = now - entry->plaintext_data->lifetime_sec;
  178. }
  179. /* If the entry has been created _after_ the cutoff, not expired so
  180. * continue to the next entry in our v3 cache. */
  181. if (entry->created_ts > cutoff) {
  182. continue;
  183. }
  184. /* Here, our entry has expired, remove and free. */
  185. MAP_DEL_CURRENT(key);
  186. entry_size = cache_get_entry_size(entry);
  187. bytes_removed += entry_size;
  188. /* Entry is not in the cache anymore, destroy it. */
  189. cache_dir_desc_free(entry);
  190. /* Update our cache entry allocation size for the OOM. */
  191. rend_cache_decrement_allocation(entry_size);
  192. /* Logging. */
  193. {
  194. char key_b64[BASE64_DIGEST256_LEN + 1];
  195. base64_encode(key_b64, sizeof(key_b64), (const char *) key,
  196. DIGEST256_LEN, 0);
  197. log_info(LD_REND, "Removing v3 descriptor '%s' from HSDir cache",
  198. safe_str_client(key_b64));
  199. }
  200. } DIGEST256MAP_FOREACH_END;
  201. return bytes_removed;
  202. }
  203. /* Given an encoded descriptor, store it in the directory cache depending on
  204. * which version it is. Return a negative value on error. On success, 0 is
  205. * returned. */
  206. int
  207. hs_cache_store_as_dir(const char *desc)
  208. {
  209. hs_cache_dir_descriptor_t *dir_desc = NULL;
  210. tor_assert(desc);
  211. /* Create a new cache object. This can fail if the descriptor plaintext data
  212. * is unparseable which in this case a log message will be triggered. */
  213. dir_desc = cache_dir_desc_new(desc);
  214. if (dir_desc == NULL) {
  215. goto err;
  216. }
  217. /* Call the right function against the descriptor version. At this point,
  218. * we are sure that the descriptor's version is supported else the
  219. * decoding would have failed. */
  220. switch (dir_desc->plaintext_data->version) {
  221. case HS_VERSION_THREE:
  222. default:
  223. if (cache_store_v3_as_dir(dir_desc) < 0) {
  224. goto err;
  225. }
  226. break;
  227. }
  228. return 0;
  229. err:
  230. cache_dir_desc_free(dir_desc);
  231. return -1;
  232. }
  233. /* Using the query, lookup in our directory cache the entry. If found, 1 is
  234. * returned and desc_out is populated with a newly allocated string being
  235. * the encoded descriptor. If not found, 0 is returned and desc_out is
  236. * untouched. On error, a negative value is returned and desc_out is
  237. * untouched. */
  238. int
  239. hs_cache_lookup_as_dir(uint32_t version, const char *query,
  240. const char **desc_out)
  241. {
  242. int found;
  243. tor_assert(query);
  244. /* This should never be called with an unsupported version. */
  245. tor_assert(hs_desc_is_supported_version(version));
  246. switch (version) {
  247. case HS_VERSION_THREE:
  248. default:
  249. found = cache_lookup_v3_as_dir(query, desc_out);
  250. break;
  251. }
  252. return found;
  253. }
  254. /* Clean all directory caches using the current time now. */
  255. void
  256. hs_cache_clean_as_dir(time_t now)
  257. {
  258. time_t cutoff;
  259. /* Start with v2 cache cleaning. */
  260. cutoff = now - rend_cache_max_entry_lifetime();
  261. rend_cache_clean_v2_descs_as_dir(cutoff);
  262. /* Now, clean the v3 cache. Set the cutoff to 0 telling the cleanup function
  263. * to compute the cutoff by itself using the lifetime value. */
  264. cache_clean_v3_as_dir(now, 0);
  265. }
  266. /* Do a round of OOM cleanup on all directory caches. Return the amount of
  267. * removed bytes. It is possible that the returned value is lower than
  268. * min_remove_bytes if the caches get emptied out so the caller should be
  269. * aware of this. */
  270. size_t
  271. hs_cache_handle_oom(time_t now, size_t min_remove_bytes)
  272. {
  273. time_t k;
  274. size_t bytes_removed = 0;
  275. /* Our OOM handler called with 0 bytes to remove is a code flow error. */
  276. tor_assert(min_remove_bytes != 0);
  277. /* The algorithm is as follow. K is the oldest expected descriptor age.
  278. *
  279. * 1) Deallocate all entries from v2 cache that are older than K hours.
  280. * 1.1) If the amount of remove bytes has been reached, stop.
  281. * 2) Deallocate all entries from v3 cache that are older than K hours
  282. * 2.1) If the amount of remove bytes has been reached, stop.
  283. * 3) Set K = K - RendPostPeriod and repeat process until K is < 0.
  284. *
  285. * This ends up being O(Kn).
  286. */
  287. /* Set K to the oldest expected age in seconds which is the maximum
  288. * lifetime of a cache entry. We'll use the v2 lifetime because it's much
  289. * bigger than the v3 thus leading to cleaning older descriptors. */
  290. k = rend_cache_max_entry_lifetime();
  291. do {
  292. time_t cutoff;
  293. /* If K becomes negative, it means we've empty the caches so stop and
  294. * return what we were able to cleanup. */
  295. if (k < 0) {
  296. break;
  297. }
  298. /* Compute a cutoff value with K and the current time. */
  299. cutoff = now - k;
  300. /* Start by cleaning the v2 cache with that cutoff. */
  301. bytes_removed += rend_cache_clean_v2_descs_as_dir(cutoff);
  302. if (bytes_removed < min_remove_bytes) {
  303. /* We haven't remove enough bytes so clean v3 cache. */
  304. bytes_removed += cache_clean_v3_as_dir(now, cutoff);
  305. /* Decrement K by a post period to shorten the cutoff. */
  306. k -= get_options()->RendPostPeriod;
  307. }
  308. } while (bytes_removed < min_remove_bytes);
  309. return bytes_removed;
  310. }
  311. /* Initialize the hidden service cache subsystem. */
  312. void
  313. hs_cache_init(void)
  314. {
  315. /* Calling this twice is very wrong code flow. */
  316. tor_assert(!hs_cache_v3_dir);
  317. hs_cache_v3_dir = digest256map_new();
  318. }
  319. /* Cleanup the hidden service cache subsystem. */
  320. void
  321. hs_cache_free_all(void)
  322. {
  323. digest256map_free(hs_cache_v3_dir, cache_dir_desc_free_);
  324. hs_cache_v3_dir = NULL;
  325. }