fp_pair.c (7337B)
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 fp_pair_map_entries_eq(const fp_pair_map_entry_t *a, 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 49 fp_pair_map_entry_hash(const fp_pair_map_entry_t *a) 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, 60 fp_pair_map_entry_hash, fp_pair_map_entries_eq); 61 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 fp_pair_map_new(void) 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 * 114 fp_pair_map_set_by_digests(fp_pair_map_t *map, 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 * 154 fp_pair_map_get_by_digests(const fp_pair_map_t *map, 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 * 175 fp_pair_map_remove(fp_pair_map_t *map, const fp_pair_t *key) 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 221 fp_pair_map_isempty(const fp_pair_map_t *map) 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 232 fp_pair_map_size(const fp_pair_map_t *map) 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 242 fp_pair_map_iter_t * 243 fp_pair_map_iter_init(fp_pair_map_t *map) 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 254 fp_pair_map_iter_t * 255 fp_pair_map_iter_next(fp_pair_map_t *map, fp_pair_map_iter_t *iter) 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 267 fp_pair_map_iter_t * 268 fp_pair_map_iter_next_rmv(fp_pair_map_t *map, fp_pair_map_iter_t *iter) 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 287 fp_pair_map_iter_get(fp_pair_map_iter_t *iter, 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 301 fp_pair_map_iter_done(fp_pair_map_iter_t *iter) 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 311 fp_pair_map_assert_ok(const fp_pair_map_t *map) 312 { 313 tor_assert(!fp_pair_map_impl_HT_REP_IS_BAD_(&(map->head))); 314 }