Line data    Source code

       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          40 : bto_gid_hash_(bt_orconn_t *elm)
      27             : {
      28          40 :   return (unsigned)siphash24g(&elm->gid, sizeof(elm->gid));
      29             : }
      30             : 
      31             : static inline int
      32          18 : bto_gid_eq_(bt_orconn_t *a, bt_orconn_t *b)
      33             : {
      34          18 :   return a->gid == b->gid;
      35             : }
      36             : 
      37             : static inline unsigned int
      38          27 : bto_chan_hash_(bt_orconn_t *elm)
      39             : {
      40          27 :   return (unsigned)siphash24g(&elm->chan, sizeof(elm->chan));
      41             : }
      42             : 
      43             : static inline int
      44           9 : bto_chan_eq_(bt_orconn_t *a, bt_orconn_t *b)
      45             : {
      46           9 :   return a->chan == b->chan;
      47             : }
      48             : 
      49             : HT_HEAD(bto_gid_ht, bt_orconn_t);
      50         785 : HT_PROTOTYPE(bto_gid_ht, bt_orconn_t, node, bto_gid_hash_, bto_gid_eq_);
      51         240 : 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         759 : HT_PROTOTYPE(bto_chan_ht, bt_orconn_t, chan_node, bto_chan_hash_,
      58             :              bto_chan_eq_);
      59         240 : 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         235 : bto_gid_clear_map(void)
      68             : {
      69         235 :   bt_orconn_t **elt, **next, *c;
      70             : 
      71         235 :   for (elt = HT_START(bto_gid_ht, bto_gid_map);
      72         235 :        elt;
      73             :        elt = next) {
      74           0 :     c = *elt;
      75           0 :     next = HT_NEXT_RMV(bto_gid_ht, bto_gid_map, elt);
      76             : 
      77           0 :     c->gid = 0;
      78             :     /* Don't delete if chan ID isn't zero: it's still in the chan hash map */
      79           0 :     if (!c->chan)
      80           0 :       tor_free(c);
      81             :   }
      82         235 :   HT_CLEAR(bto_gid_ht, bto_gid_map);
      83         235 :   tor_free(bto_gid_map);
      84         235 : }
      85             : 
      86             : /** Clear the chan ID hash map, freeing any bt_orconn_t objects that
      87             :  * become unreferenced */
      88             : static void
      89         235 : bto_chan_clear_map(void)
      90             : {
      91         235 :   bt_orconn_t **elt, **next, *c;
      92             : 
      93         235 :   for (elt = HT_START(bto_chan_ht, bto_chan_map);
      94         235 :        elt;
      95             :        elt = next) {
      96           0 :     c = *elt;
      97           0 :     next = HT_NEXT_RMV(bto_chan_ht, bto_chan_map, elt);
      98             : 
      99           0 :     c->chan = 0;
     100             :     /* Don't delete if GID isn't zero, it's still in the GID hash map */
     101           0 :     if (!c->gid)
     102           0 :       tor_free(c);
     103             :   }
     104         235 :   HT_CLEAR(bto_chan_ht, bto_chan_map);
     105         235 :   tor_free(bto_chan_map);
     106         235 : }
     107             : 
     108             : /** Delete a bt_orconn from the hash maps by GID */
     109             : void
     110           5 : bto_delete(uint64_t gid)
     111             : {
     112           5 :   bt_orconn_t key, *bto;
     113             : 
     114           5 :   key.gid = gid;
     115           5 :   key.chan = 0;
     116           5 :   bto = HT_FIND(bto_gid_ht, bto_gid_map, &key);
     117           5 :   if (!bto) {
     118             :     /* The orconn might be unregistered because it's an EXT_OR_CONN? */
     119           4 :     log_debug(LD_BTRACK, "tried to delete unregistered ORCONN gid=%"PRIu64,
     120             :               gid);
     121           4 :     return;
     122             :   }
     123           1 :   HT_REMOVE(bto_gid_ht, bto_gid_map, &key);
     124           1 :   if (bto->chan) {
     125           1 :     key.chan = bto->chan;
     126           1 :     HT_REMOVE(bto_chan_ht, bto_chan_map, &key);
     127             :   }
     128           1 :   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          24 : bto_update(bt_orconn_t *bto, const bt_orconn_t *key)
     139             : {
     140             :   /* ORCONN GIDs shouldn't change once assigned */
     141          24 :   tor_assert(!bto->gid || !key->gid || bto->gid == key->gid);
     142          24 :   if (!bto->gid && key->gid) {
     143             :     /* Got a gid when we didn't already have one; insert into gid map */
     144           4 :     log_debug(LD_BTRACK, "ORCONN chan=%"PRIu64" newgid=%"PRIu64, key->chan,
     145             :               key->gid);
     146           4 :     bto->gid = key->gid;
     147           4 :     HT_INSERT(bto_gid_ht, bto_gid_map, bto);
     148             :   }
     149             :   /* association of ORCONN with channel shouldn't change */
     150          24 :   tor_assert(!bto->chan || !key->chan || bto->chan == key->chan);
     151          24 :   if (!bto->chan && key->chan) {
     152             :     /* Got a chan when we didn't already have one; insert into chan map */
     153           0 :     log_debug(LD_BTRACK, "ORCONN gid=%"PRIu64" newchan=%"PRIu64,
     154             :               bto->gid, key->chan);
     155           0 :     bto->chan = key->chan;
     156           0 :     HT_INSERT(bto_chan_ht, bto_chan_map, bto);
     157             :   }
     158          24 :   return bto;
     159             : }
     160             : 
     161             : /** Helper for bto_find_or_new() */
     162             : static bt_orconn_t *
     163           9 : bto_new(const bt_orconn_t *key)
     164             : {
     165           9 :   struct bt_orconn_t *bto = tor_malloc(sizeof(*bto));
     166             : 
     167           9 :   bto->gid = key->gid;
     168           9 :   bto->chan = key->chan;
     169           9 :   bto->state = 0;
     170           9 :   bto->proxy_type = 0;
     171           9 :   bto->is_orig = false;
     172           9 :   bto->is_onehop = true;
     173             : 
     174           9 :   if (bto->gid)
     175           5 :     HT_INSERT(bto_gid_ht, bto_gid_map, bto);
     176           9 :   if (bto->chan)
     177           9 :     HT_INSERT(bto_chan_ht, bto_chan_map, bto);
     178             : 
     179           9 :   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          33 : bto_find_or_new(uint64_t gid, uint64_t chan)
     190             : {
     191          33 :   bt_orconn_t key, *bto = NULL;
     192             : 
     193          33 :   tor_assert(gid || chan);
     194          33 :   key.gid = gid;
     195          33 :   key.chan = chan;
     196          33 :   if (key.gid)
     197          25 :     bto = HT_FIND(bto_gid_ht, bto_gid_map, &key);
     198          33 :   if (!bto && key.chan) {
     199             :     /* Not found by GID; look up by chan ID */
     200          17 :     bto = HT_FIND(bto_chan_ht, bto_chan_map, &key);
     201             :   }
     202          33 :   if (bto)
     203          24 :     return bto_update(bto, &key);
     204             :   else
     205           9 :     return bto_new(&key);
     206             : }
     207             : 
     208             : /** Initialize the hash maps  */
     209             : void
     210         244 : bto_init_maps(void)
     211             : {
     212         244 :   bto_gid_map = tor_malloc(sizeof(*bto_gid_map));
     213         244 :   HT_INIT(bto_gid_ht, bto_gid_map);
     214         244 :   bto_chan_map = tor_malloc(sizeof(*bto_chan_map));
     215         244 :   HT_INIT(bto_chan_ht, bto_chan_map);
     216         244 : }
     217             : 
     218             : /** Clear the hash maps, freeing all associated storage */
     219             : void
     220         235 : bto_clear_maps(void)
     221             : {
     222         235 :   bto_gid_clear_map();
     223         235 :   bto_chan_clear_map();
     224         235 : }