Tor 0.4.9.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
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. */
40static 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. */
48static 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
59HT_PROTOTYPE(fp_pair_map_impl, fp_pair_map_entry_t, node,
61HT_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
82void *
83fp_pair_map_set(fp_pair_map_t *map, const fp_pair_t *key, void *val)
84{
85 fp_pair_map_entry_t *resolve;
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
113void *
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
132void *
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
153void *
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
174void *
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
198void
199fp_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
220int
222{
223 tor_assert(map);
224
225 return HT_EMPTY(&(map->head));
226}
227
228/** Return the number of items in map.
229 */
230
231int
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{
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
286void
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
300int
302{
303 return (iter == NULL);
304}
305
306/** Assert if anything has gone wrong with the internal
307 * representation of map.
308 */
309
310void
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
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
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_iter_t * fp_pair_map_iter_next(fp_pair_map_t *map, fp_pair_map_iter_t *iter)
Definition: fp_pair.c:255
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
int fp_pair_map_size(const fp_pair_map_t *map)
Definition: fp_pair.c:232
void * fp_pair_map_get(const fp_pair_map_t *map, const fp_pair_t *key)
Definition: fp_pair.c:133
void * fp_pair_map_remove(fp_pair_map_t *map, const fp_pair_t *key)
Definition: fp_pair.c:175
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_get_by_digests(const fp_pair_map_t *map, const char *first, const char *second)
Definition: fp_pair.c:154
void fp_pair_map_assert_ok(const fp_pair_map_t *map)
Definition: fp_pair.c:311
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
fp_pair_map_t * fp_pair_map_new(void)
Definition: fp_pair.c:69
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_reallocarray_(void *ptr, size_t sz1, size_t sz2)
Definition: malloc.c:146
void tor_free_(void *mem)
Definition: malloc.c:227
#define tor_free(p)
Definition: malloc.h:56
Master header file for Tor-specific functionality.
Definition: fp_pair.c:25
#define tor_assert(expr)
Definition: util_bug.h:103