hs_cache.c 12 KB

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