Line data Source code
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"
21 : #include "feature/dircommon/fp_pair.h"
22 :
23 : /* Define fp_pair_map_t structures */
24 :
25 : struct fp_pair_map_entry_t {
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
41 18 : fp_pair_map_entries_eq(const fp_pair_map_entry_t *a,
42 : const fp_pair_map_entry_t *b)
43 : {
44 18 : 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
49 47 : fp_pair_map_entry_hash(const fp_pair_map_entry_t *a)
50 : {
51 47 : tor_assert(sizeof(a->key) == DIGEST_LEN*2);
52 47 : return (unsigned) siphash24g(&a->key, DIGEST_LEN*2);
53 : }
54 :
55 : /*
56 : * Hash table functions for fp_pair_map_t
57 : */
58 :
59 169 : HT_PROTOTYPE(fp_pair_map_impl, fp_pair_map_entry_t, node,
60 : fp_pair_map_entry_hash, fp_pair_map_entries_eq);
61 290 : HT_GENERATE2(fp_pair_map_impl, fp_pair_map_entry_t, node,
62 : fp_pair_map_entry_hash, fp_pair_map_entries_eq,
63 : 0.6, tor_reallocarray_, tor_free_);
64 :
65 : /** Constructor to create a new empty map from fp_pair_t to void *
66 : */
67 :
68 : fp_pair_map_t *
69 1 : fp_pair_map_new(void)
70 : {
71 1 : fp_pair_map_t *result;
72 :
73 1 : result = tor_malloc(sizeof(fp_pair_map_t));
74 1 : HT_INIT(fp_pair_map_impl, &result->head);
75 1 : 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 8 : fp_pair_map_set(fp_pair_map_t *map, const fp_pair_t *key, void *val)
84 : {
85 8 : fp_pair_map_entry_t *resolve;
86 8 : fp_pair_map_entry_t search;
87 8 : void *oldval;
88 :
89 8 : tor_assert(map);
90 8 : tor_assert(key);
91 8 : tor_assert(val);
92 :
93 8 : memcpy(&(search.key), key, sizeof(*key));
94 8 : resolve = HT_FIND(fp_pair_map_impl, &(map->head), &search);
95 8 : if (resolve) {
96 1 : oldval = resolve->val;
97 1 : resolve->val = val;
98 : } else {
99 7 : resolve = tor_malloc_zero(sizeof(fp_pair_map_entry_t));
100 7 : memcpy(&(resolve->key), key, sizeof(*key));
101 7 : resolve->val = val;
102 7 : HT_INSERT(fp_pair_map_impl, &(map->head), resolve);
103 7 : oldval = NULL;
104 : }
105 :
106 8 : 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 *
114 1 : fp_pair_map_set_by_digests(fp_pair_map_t *map,
115 : const char *first, const char *second,
116 : void *val)
117 : {
118 1 : fp_pair_t k;
119 :
120 1 : tor_assert(first);
121 1 : tor_assert(second);
122 :
123 1 : memcpy(k.first, first, DIGEST_LEN);
124 1 : memcpy(k.second, second, DIGEST_LEN);
125 :
126 1 : 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 12 : fp_pair_map_get(const fp_pair_map_t *map, const fp_pair_t *key)
134 : {
135 12 : fp_pair_map_entry_t *resolve;
136 12 : fp_pair_map_entry_t search;
137 12 : void *val = NULL;
138 :
139 12 : tor_assert(map);
140 12 : tor_assert(key);
141 :
142 12 : memcpy(&(search.key), key, sizeof(*key));
143 12 : resolve = HT_FIND(fp_pair_map_impl, &(map->head), &search);
144 12 : if (resolve) val = resolve->val;
145 :
146 12 : 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 *
154 1 : fp_pair_map_get_by_digests(const fp_pair_map_t *map,
155 : const char *first, const char *second)
156 : {
157 1 : fp_pair_t k;
158 :
159 1 : tor_assert(first);
160 1 : tor_assert(second);
161 :
162 1 : memcpy(k.first, first, DIGEST_LEN);
163 1 : memcpy(k.second, second, DIGEST_LEN);
164 :
165 1 : 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 *
175 2 : fp_pair_map_remove(fp_pair_map_t *map, const fp_pair_t *key)
176 : {
177 2 : fp_pair_map_entry_t *resolve;
178 2 : fp_pair_map_entry_t search;
179 2 : void *val = NULL;
180 :
181 2 : tor_assert(map);
182 2 : tor_assert(key);
183 :
184 2 : memcpy(&(search.key), key, sizeof(*key));
185 2 : resolve = HT_REMOVE(fp_pair_map_impl, &(map->head), &search);
186 2 : if (resolve) {
187 1 : val = resolve->val;
188 1 : tor_free(resolve);
189 : }
190 :
191 2 : 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 1 : fp_pair_map_free_(fp_pair_map_t *map, void (*free_val)(void*))
200 : {
201 1 : fp_pair_map_entry_t **ent, **next, *this;
202 :
203 1 : if (map) {
204 1 : for (ent = HT_START(fp_pair_map_impl, &(map->head));
205 6 : ent != NULL; ent = next) {
206 5 : this = *ent;
207 5 : next = HT_NEXT_RMV(fp_pair_map_impl, &(map->head), ent);
208 5 : if (free_val) free_val(this->val);
209 5 : tor_free(this);
210 : }
211 1 : tor_assert(HT_EMPTY(&(map->head)));
212 1 : HT_CLEAR(fp_pair_map_impl, &(map->head));
213 1 : tor_free(map);
214 : }
215 1 : }
216 :
217 : /** Return true iff map has no entries.
218 : */
219 :
220 : int
221 2 : fp_pair_map_isempty(const fp_pair_map_t *map)
222 : {
223 2 : tor_assert(map);
224 :
225 2 : return HT_EMPTY(&(map->head));
226 : }
227 :
228 : /** Return the number of items in map.
229 : */
230 :
231 : int
232 2 : fp_pair_map_size(const fp_pair_map_t *map)
233 : {
234 2 : tor_assert(map);
235 :
236 2 : return HT_SIZE(&(map->head));
237 : }
238 :
239 : /** return an iterator pointing to the start of map.
240 : */
241 :
242 : fp_pair_map_iter_t *
243 1 : fp_pair_map_iter_init(fp_pair_map_t *map)
244 : {
245 1 : tor_assert(map);
246 :
247 1 : 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 :
254 : fp_pair_map_iter_t *
255 5 : fp_pair_map_iter_next(fp_pair_map_t *map, fp_pair_map_iter_t *iter)
256 : {
257 5 : tor_assert(map);
258 5 : tor_assert(iter);
259 :
260 5 : 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 :
267 : fp_pair_map_iter_t *
268 1 : fp_pair_map_iter_next_rmv(fp_pair_map_t *map, fp_pair_map_iter_t *iter)
269 : {
270 1 : fp_pair_map_entry_t *rmv;
271 :
272 1 : tor_assert(map);
273 1 : tor_assert(iter);
274 1 : tor_assert(*iter);
275 :
276 1 : rmv = *iter;
277 1 : iter = HT_NEXT_RMV(fp_pair_map_impl, &(map->head), iter);
278 1 : tor_free(rmv);
279 :
280 1 : return iter;
281 : }
282 :
283 : /** Set *key_out and *val_out to the current entry pointed to by iter.
284 : */
285 :
286 : void
287 6 : fp_pair_map_iter_get(fp_pair_map_iter_t *iter,
288 : fp_pair_t *key_out, void **val_out)
289 : {
290 6 : tor_assert(iter);
291 6 : tor_assert(*iter);
292 :
293 6 : if (key_out) memcpy(key_out, &((*iter)->key), sizeof(fp_pair_t));
294 6 : if (val_out) *val_out = (*iter)->val;
295 6 : }
296 :
297 : /** Return true iff iter has advanced past the last entry of its map.
298 : */
299 :
300 : int
301 7 : fp_pair_map_iter_done(fp_pair_map_iter_t *iter)
302 : {
303 7 : return (iter == NULL);
304 : }
305 :
306 : /** Assert if anything has gone wrong with the internal
307 : * representation of map.
308 : */
309 :
310 : void
311 5 : fp_pair_map_assert_ok(const fp_pair_map_t *map)
312 : {
313 5 : tor_assert(!fp_pair_map_impl_HT_REP_IS_BAD_(&(map->head)));
314 5 : }
|
