fp_pair.c 7.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315
  1. /* Copyright (c) 2013-2017, The Tor Project, Inc. */
  2. /* See LICENSE for licensing information */
  3. /**
  4. * \file fp_pair.c
  5. *
  6. * \brief Manages data structures for associating pairs of fingerprints. Used
  7. * to handle combinations of identity/signing-key fingerprints for
  8. * authorities.
  9. *
  10. * This is a nice, simple, compact data structure module that handles a map
  11. * from (signing key fingerprint, identity key fingerprint) to void *. The
  12. * fingerprints here are SHA1 digests of RSA keys.
  13. *
  14. * This structure is used in directory.c and in routerlist.c for handling
  15. * handling authority certificates, since we never want more than a single
  16. * certificate for any (ID key, signing key) pair.
  17. **/
  18. #include "or.h"
  19. #include "fp_pair.h"
  20. /* Define fp_pair_map_t structures */
  21. struct fp_pair_map_entry_s {
  22. HT_ENTRY(fp_pair_map_entry_s) node;
  23. void *val;
  24. fp_pair_t key;
  25. };
  26. struct fp_pair_map_s {
  27. HT_HEAD(fp_pair_map_impl, fp_pair_map_entry_s) head;
  28. };
  29. /*
  30. * Hash function and equality checker for fp_pair_map_t
  31. */
  32. /** Compare fp_pair_entry_t objects by key value. */
  33. static inline int
  34. fp_pair_map_entries_eq(const fp_pair_map_entry_t *a,
  35. const fp_pair_map_entry_t *b)
  36. {
  37. return tor_memeq(&(a->key), &(b->key), sizeof(fp_pair_t));
  38. }
  39. /** Return a hash value for an fp_pair_entry_t. */
  40. static inline unsigned int
  41. fp_pair_map_entry_hash(const fp_pair_map_entry_t *a)
  42. {
  43. tor_assert(sizeof(a->key) == DIGEST_LEN*2);
  44. return (unsigned) siphash24g(&a->key, DIGEST_LEN*2);
  45. }
  46. /*
  47. * Hash table functions for fp_pair_map_t
  48. */
  49. HT_PROTOTYPE(fp_pair_map_impl, fp_pair_map_entry_s, node,
  50. fp_pair_map_entry_hash, fp_pair_map_entries_eq)
  51. HT_GENERATE2(fp_pair_map_impl, fp_pair_map_entry_s, node,
  52. fp_pair_map_entry_hash, fp_pair_map_entries_eq,
  53. 0.6, tor_reallocarray_, tor_free_)
  54. /** Constructor to create a new empty map from fp_pair_t to void *
  55. */
  56. fp_pair_map_t *
  57. fp_pair_map_new(void)
  58. {
  59. fp_pair_map_t *result;
  60. result = tor_malloc(sizeof(fp_pair_map_t));
  61. HT_INIT(fp_pair_map_impl, &result->head);
  62. return result;
  63. }
  64. /** Set the current value for key to val; returns the previous
  65. * value for key if one was set, or NULL if one was not.
  66. */
  67. void *
  68. fp_pair_map_set(fp_pair_map_t *map, const fp_pair_t *key, void *val)
  69. {
  70. fp_pair_map_entry_t *resolve;
  71. fp_pair_map_entry_t search;
  72. void *oldval;
  73. tor_assert(map);
  74. tor_assert(key);
  75. tor_assert(val);
  76. memcpy(&(search.key), key, sizeof(*key));
  77. resolve = HT_FIND(fp_pair_map_impl, &(map->head), &search);
  78. if (resolve) {
  79. oldval = resolve->val;
  80. resolve->val = val;
  81. } else {
  82. resolve = tor_malloc_zero(sizeof(fp_pair_map_entry_t));
  83. memcpy(&(resolve->key), key, sizeof(*key));
  84. resolve->val = val;
  85. HT_INSERT(fp_pair_map_impl, &(map->head), resolve);
  86. oldval = NULL;
  87. }
  88. return oldval;
  89. }
  90. /** Set the current value for the key (first, second) to val; returns
  91. * the previous value for key if one was set, or NULL if one was not.
  92. */
  93. void *
  94. fp_pair_map_set_by_digests(fp_pair_map_t *map,
  95. const char *first, const char *second,
  96. void *val)
  97. {
  98. fp_pair_t k;
  99. tor_assert(first);
  100. tor_assert(second);
  101. memcpy(k.first, first, DIGEST_LEN);
  102. memcpy(k.second, second, DIGEST_LEN);
  103. return fp_pair_map_set(map, &k, val);
  104. }
  105. /** Return the current value associated with key, or NULL if no value is set.
  106. */
  107. void *
  108. fp_pair_map_get(const fp_pair_map_t *map, const fp_pair_t *key)
  109. {
  110. fp_pair_map_entry_t *resolve;
  111. fp_pair_map_entry_t search;
  112. void *val = NULL;
  113. tor_assert(map);
  114. tor_assert(key);
  115. memcpy(&(search.key), key, sizeof(*key));
  116. resolve = HT_FIND(fp_pair_map_impl, &(map->head), &search);
  117. if (resolve) val = resolve->val;
  118. return val;
  119. }
  120. /** Return the current value associated the key (first, second), or
  121. * NULL if no value is set.
  122. */
  123. void *
  124. fp_pair_map_get_by_digests(const fp_pair_map_t *map,
  125. const char *first, const char *second)
  126. {
  127. fp_pair_t k;
  128. tor_assert(first);
  129. tor_assert(second);
  130. memcpy(k.first, first, DIGEST_LEN);
  131. memcpy(k.second, second, DIGEST_LEN);
  132. return fp_pair_map_get(map, &k);
  133. }
  134. /** Remove the value currently associated with key from the map.
  135. * Return the value if one was set, or NULL if there was no entry for
  136. * key. The caller must free any storage associated with the
  137. * returned value.
  138. */
  139. void *
  140. fp_pair_map_remove(fp_pair_map_t *map, const fp_pair_t *key)
  141. {
  142. fp_pair_map_entry_t *resolve;
  143. fp_pair_map_entry_t search;
  144. void *val = NULL;
  145. tor_assert(map);
  146. tor_assert(key);
  147. memcpy(&(search.key), key, sizeof(*key));
  148. resolve = HT_REMOVE(fp_pair_map_impl, &(map->head), &search);
  149. if (resolve) {
  150. val = resolve->val;
  151. tor_free(resolve);
  152. }
  153. return val;
  154. }
  155. /** Remove all entries from map, and deallocate storage for those entries.
  156. * If free_val is provided, it is invoked on every value in map.
  157. */
  158. void
  159. fp_pair_map_free_(fp_pair_map_t *map, void (*free_val)(void*))
  160. {
  161. fp_pair_map_entry_t **ent, **next, *this;
  162. if (map) {
  163. for (ent = HT_START(fp_pair_map_impl, &(map->head));
  164. ent != NULL; ent = next) {
  165. this = *ent;
  166. next = HT_NEXT_RMV(fp_pair_map_impl, &(map->head), ent);
  167. if (free_val) free_val(this->val);
  168. tor_free(this);
  169. }
  170. tor_assert(HT_EMPTY(&(map->head)));
  171. HT_CLEAR(fp_pair_map_impl, &(map->head));
  172. tor_free(map);
  173. }
  174. }
  175. /** Return true iff map has no entries.
  176. */
  177. int
  178. fp_pair_map_isempty(const fp_pair_map_t *map)
  179. {
  180. tor_assert(map);
  181. return HT_EMPTY(&(map->head));
  182. }
  183. /** Return the number of items in map.
  184. */
  185. int
  186. fp_pair_map_size(const fp_pair_map_t *map)
  187. {
  188. tor_assert(map);
  189. return HT_SIZE(&(map->head));
  190. }
  191. /** return an iterator pointing to the start of map.
  192. */
  193. fp_pair_map_iter_t *
  194. fp_pair_map_iter_init(fp_pair_map_t *map)
  195. {
  196. tor_assert(map);
  197. return HT_START(fp_pair_map_impl, &(map->head));
  198. }
  199. /** Advance iter a single step to the next entry of map, and return
  200. * its new value.
  201. */
  202. fp_pair_map_iter_t *
  203. fp_pair_map_iter_next(fp_pair_map_t *map, fp_pair_map_iter_t *iter)
  204. {
  205. tor_assert(map);
  206. tor_assert(iter);
  207. return HT_NEXT(fp_pair_map_impl, &(map->head), iter);
  208. }
  209. /** Advance iter a single step to the next entry of map, removing the current
  210. * entry, and return its new value.
  211. */
  212. fp_pair_map_iter_t *
  213. fp_pair_map_iter_next_rmv(fp_pair_map_t *map, fp_pair_map_iter_t *iter)
  214. {
  215. fp_pair_map_entry_t *rmv;
  216. tor_assert(map);
  217. tor_assert(iter);
  218. tor_assert(*iter);
  219. rmv = *iter;
  220. iter = HT_NEXT_RMV(fp_pair_map_impl, &(map->head), iter);
  221. tor_free(rmv);
  222. return iter;
  223. }
  224. /** Set *key_out and *val_out to the current entry pointed to by iter.
  225. */
  226. void
  227. fp_pair_map_iter_get(fp_pair_map_iter_t *iter,
  228. fp_pair_t *key_out, void **val_out)
  229. {
  230. tor_assert(iter);
  231. tor_assert(*iter);
  232. if (key_out) memcpy(key_out, &((*iter)->key), sizeof(fp_pair_t));
  233. if (val_out) *val_out = (*iter)->val;
  234. }
  235. /** Return true iff iter has advanced past the last entry of its map.
  236. */
  237. int
  238. fp_pair_map_iter_done(fp_pair_map_iter_t *iter)
  239. {
  240. return (iter == NULL);
  241. }
  242. /** Assert if anything has gone wrong with the internal
  243. * representation of map.
  244. */
  245. void
  246. fp_pair_map_assert_ok(const fp_pair_map_t *map)
  247. {
  248. tor_assert(!fp_pair_map_impl_HT_REP_IS_BAD_(&(map->head)));
  249. }