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