src/feature/control/btrack_orconn_maps.c

   1 /* Copyright (c) 2007-2021, The Tor Project, Inc. */
   2 /* See LICENSE for licensing information */
   3
   4 /**
   5  * \file btrack_orconn_maps.c
   6  * \brief Hash map implementation for btrack_orconn.c
   7  *
   8  * These functions manipulate the hash maps that contain bt_orconn
   9  * objects.
  10  **/
  11
  12 #include <stdbool.h>
  13
  14 #include "core/or/or.h"
  15
  16 #include "ht.h"
  17 #include "siphash.h"
  18
  19 #define BTRACK_ORCONN_PRIVATE
  20
  21 #include "feature/control/btrack_orconn.h"
  22 #include "feature/control/btrack_orconn_maps.h"
  23 #include "lib/log/log.h"
  24
  25 static inline unsigned int
  26 bto_gid_hash_(bt_orconn_t *elm)
  27 {
  28   return (unsigned)siphash24g(&elm->gid, sizeof(elm->gid));
  29 }
  30
  31 static inline int
  32 bto_gid_eq_(bt_orconn_t *a, bt_orconn_t *b)
  33 {
  34   return a->gid == b->gid;
  35 }
  36
  37 static inline unsigned int
  38 bto_chan_hash_(bt_orconn_t *elm)
  39 {
  40   return (unsigned)siphash24g(&elm->chan, sizeof(elm->chan));
  41 }
  42
  43 static inline int
  44 bto_chan_eq_(bt_orconn_t *a, bt_orconn_t *b)
  45 {
  46   return a->chan == b->chan;
  47 }
  48
  49 HT_HEAD(bto_gid_ht, bt_orconn_t);
  50 HT_PROTOTYPE(bto_gid_ht, bt_orconn_t, node, bto_gid_hash_, bto_gid_eq_);
  51 HT_GENERATE2(bto_gid_ht, bt_orconn_t, node,
  52              bto_gid_hash_, bto_gid_eq_, 0.6,
  53              tor_reallocarray_, tor_free_);
  54 static struct bto_gid_ht *bto_gid_map;
  55
  56 HT_HEAD(bto_chan_ht, bt_orconn_t);
  57 HT_PROTOTYPE(bto_chan_ht, bt_orconn_t, chan_node, bto_chan_hash_,
  58              bto_chan_eq_);
  59 HT_GENERATE2(bto_chan_ht, bt_orconn_t, chan_node,
  60              bto_chan_hash_, bto_chan_eq_, 0.6,
  61              tor_reallocarray_, tor_free_);
  62 static struct bto_chan_ht *bto_chan_map;
  63
  64 /** Clear the GID hash map, freeing any bt_orconn_t objects that become
  65  * unreferenced */
  66 static void
  67 bto_gid_clear_map(void)
  68 {
  69   bt_orconn_t **elt, **next, *c;
  70
  71   for (elt = HT_START(bto_gid_ht, bto_gid_map);
  72        elt;
  73        elt = next) {
  74     c = *elt;
  75     next = HT_NEXT_RMV(bto_gid_ht, bto_gid_map, elt);
  76
  77     c->gid = 0;
  78     /* Don't delete if chan ID isn't zero: it's still in the chan hash map */
  79     if (!c->chan)
  80       tor_free(c);
  81   }
  82   HT_CLEAR(bto_gid_ht, bto_gid_map);
  83   tor_free(bto_gid_map);
  84 }
  85
  86 /** Clear the chan ID hash map, freeing any bt_orconn_t objects that
  87  * become unreferenced */
  88 static void
  89 bto_chan_clear_map(void)
  90 {
  91   bt_orconn_t **elt, **next, *c;
  92
  93   for (elt = HT_START(bto_chan_ht, bto_chan_map);
  94        elt;
  95        elt = next) {
  96     c = *elt;
  97     next = HT_NEXT_RMV(bto_chan_ht, bto_chan_map, elt);
  98
  99     c->chan = 0;
 100     /* Don't delete if GID isn't zero, it's still in the GID hash map */
 101     if (!c->gid)
 102       tor_free(c);
 103   }
 104   HT_CLEAR(bto_chan_ht, bto_chan_map);
 105   tor_free(bto_chan_map);
 106 }
 107
 108 /** Delete a bt_orconn from the hash maps by GID */
 109 void
 110 bto_delete(uint64_t gid)
 111 {
 112   bt_orconn_t key, *bto;
 113
 114   key.gid = gid;
 115   key.chan = 0;
 116   bto = HT_FIND(bto_gid_ht, bto_gid_map, &key);
 117   if (!bto) {
 118     /* The orconn might be unregistered because it's an EXT_OR_CONN? */
 119     log_debug(LD_BTRACK, "tried to delete unregistered ORCONN gid=%"PRIu64,
 120               gid);
 121     return;
 122   }
 123   HT_REMOVE(bto_gid_ht, bto_gid_map, &key);
 124   if (bto->chan) {
 125     key.chan = bto->chan;
 126     HT_REMOVE(bto_chan_ht, bto_chan_map, &key);
 127   }
 128   tor_free(bto);
 129 }
 130
 131 /**
 132  * Helper for bto_find_or_new().
 133  *
 134  * Update GID and chan ID of an existing bt_orconn object if needed,
 135  * given a search key previously used within bto_find_or_new().
 136  **/
 137 static bt_orconn_t *
 138 bto_update(bt_orconn_t *bto, const bt_orconn_t *key)
 139 {
 140   /* ORCONN GIDs shouldn't change once assigned */
 141   tor_assert(!bto->gid || !key->gid || bto->gid == key->gid);
 142   if (!bto->gid && key->gid) {
 143     /* Got a gid when we didn't already have one; insert into gid map */
 144     log_debug(LD_BTRACK, "ORCONN chan=%"PRIu64" newgid=%"PRIu64, key->chan,
 145               key->gid);
 146     bto->gid = key->gid;
 147     HT_INSERT(bto_gid_ht, bto_gid_map, bto);
 148   }
 149   /* association of ORCONN with channel shouldn't change */
 150   tor_assert(!bto->chan || !key->chan || bto->chan == key->chan);
 151   if (!bto->chan && key->chan) {
 152     /* Got a chan when we didn't already have one; insert into chan map */
 153     log_debug(LD_BTRACK, "ORCONN gid=%"PRIu64" newchan=%"PRIu64,
 154               bto->gid, key->chan);
 155     bto->chan = key->chan;
 156     HT_INSERT(bto_chan_ht, bto_chan_map, bto);
 157   }
 158   return bto;
 159 }
 160
 161 /** Helper for bto_find_or_new() */
 162 static bt_orconn_t *
 163 bto_new(const bt_orconn_t *key)
 164 {
 165   struct bt_orconn_t *bto = tor_malloc(sizeof(*bto));
 166
 167   bto->gid = key->gid;
 168   bto->chan = key->chan;
 169   bto->state = 0;
 170   bto->proxy_type = 0;
 171   bto->is_orig = false;
 172   bto->is_onehop = true;
 173
 174   if (bto->gid)
 175     HT_INSERT(bto_gid_ht, bto_gid_map, bto);
 176   if (bto->chan)
 177     HT_INSERT(bto_chan_ht, bto_chan_map, bto);
 178
 179   return bto;
 180 }
 181
 182 /**
 183  * Insert a new bt_orconn with the given GID and chan ID, or update
 184  * the GID and chan ID if one already exists.
 185  *
 186  * Return the found or allocated bt_orconn.
 187  **/
 188 bt_orconn_t *
 189 bto_find_or_new(uint64_t gid, uint64_t chan)
 190 {
 191   bt_orconn_t key, *bto = NULL;
 192
 193   tor_assert(gid || chan);
 194   key.gid = gid;
 195   key.chan = chan;
 196   if (key.gid)
 197     bto = HT_FIND(bto_gid_ht, bto_gid_map, &key);
 198   if (!bto && key.chan) {
 199     /* Not found by GID; look up by chan ID */
 200     bto = HT_FIND(bto_chan_ht, bto_chan_map, &key);
 201   }
 202   if (bto)
 203     return bto_update(bto, &key);
 204   else
 205     return bto_new(&key);
 206 }
 207
 208 /** Initialize the hash maps  */
 209 void
 210 bto_init_maps(void)
 211 {
 212   bto_gid_map = tor_malloc(sizeof(*bto_gid_map));
 213   HT_INIT(bto_gid_ht, bto_gid_map);
 214   bto_chan_map = tor_malloc(sizeof(*bto_chan_map));
 215   HT_INIT(bto_chan_ht, bto_chan_map);
 216 }
 217
 218 /** Clear the hash maps, freeing all associated storage */
 219 void
 220 bto_clear_maps(void)
 221 {
 222   bto_gid_clear_map();
 223   bto_chan_clear_map();
 224 }