git.meshlink.io Git - meshlink/blob - src/autoconnect.c

   1 /*
   2     autoconnect.c -- automatic connection establishment
   3     Copyright (C) 2019 Guus Sliepen <guus@meshlink.io>
   4
   5     This program is free software; you can redistribute it and/or modify
   6     it under the terms of the GNU General Public License as published by
   7     the Free Software Foundation; either version 2 of the License, or
   8     (at your option) any later version.
   9
  10     This program is distributed in the hope that it will be useful,
  11     but WITHOUT ANY WARRANTY; without even the implied warranty of
  12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13     GNU General Public License for more details.
  14
  15     You should have received a copy of the GNU General Public License along
  16     with this program; if not, write to the Free Software Foundation, Inc.,
  17     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
  18 */
  19
  20 #include "system.h"
  21
  22 #include "connection.h"
  23 #include "list.h"
  24 #include "logger.h"
  25 #include "net.h"
  26 #include "node.h"
  27 #include "xalloc.h"
  28
  29 /* Make an outgoing connection if possible */
  30 static bool make_outgoing(meshlink_handle_t *mesh, node_t *n) {
  31         if(!n || n->connection) {
  32                 return false;
  33         }
  34
  35         n->last_connect_try = mesh->loop.now.tv_sec;
  36         logger(mesh, MESHLINK_DEBUG, "Autoconnect trying to connect to %s", n->name);
  37
  38         /* check if there is already a connection attempt to this node */
  39         for list_each(outgoing_t, outgoing, mesh->outgoings) {
  40                 if(outgoing->node == n) {
  41                         logger(mesh, MESHLINK_DEBUG, "* skip autoconnect since it is an outgoing connection already");
  42                         return false;
  43                 }
  44         }
  45
  46         if(!n->status.reachable && !node_read_public_key(mesh, n)) {
  47                 logger(mesh, MESHLINK_DEBUG, "* skip autoconnect since we don't know this node's public key");
  48                 return false;
  49         }
  50
  51         logger(mesh, MESHLINK_DEBUG, "Autoconnecting to %s", n->name);
  52         outgoing_t *outgoing = xzalloc(sizeof(outgoing_t));
  53         outgoing->node = n;
  54         list_insert_tail(mesh->outgoings, outgoing);
  55         setup_outgoing_connection(mesh, outgoing);
  56         return true;
  57 }
  58
  59 /* Determine if node n is a better candidate for making an early connection to than node m. */
  60 static bool compare_candidates(node_t *n, node_t *m) {
  61         /* Check if the last connection attempt was successful */
  62         bool n_successful = n->last_successful_connection > n->last_connect_try;
  63         bool m_successful = n->last_successful_connection > n->last_connect_try;
  64
  65         if(n_successful != m_successful) {
  66                 return n_successful;
  67         } else {
  68                 if(n_successful) {
  69                         /* If both were successfully connected to, prefer the most recent one */
  70                         return n->last_successful_connection > m->last_successful_connection;
  71                 } else {
  72                         /* If the last connections were not successful, prefer the one we least recently tried to connect to. */
  73                         return n->last_connect_try < m->last_connect_try;
  74                 }
  75         }
  76 }
  77
  78 /* Try to connect to any candidate in the same or better device class. Prefer recently connected-to nodes first. */
  79 static bool make_eager_connection(meshlink_handle_t *mesh) {
  80         node_t *candidate = NULL;
  81
  82         for splay_each(node_t, n, mesh->nodes) {
  83                 if(n == mesh->self || n->devclass > mesh->devclass || n->connection || n->status.blacklisted) {
  84                         continue;
  85                 }
  86
  87                 if(!candidate) {
  88                         candidate = n;
  89                         continue;
  90                 }
  91
  92                 if(compare_candidates(n, candidate)) {
  93                         candidate = n;
  94                 }
  95         }
  96
  97         return make_outgoing(mesh, candidate);
  98 }
  99
 100 /* Try to connect to balance connections to different device classes. Prefer recently connected-to nodes first. */
 101 static bool make_better_connection(meshlink_handle_t *mesh) {
 102         const unsigned int min_connects = mesh->dev_class_traits[mesh->devclass].min_connects;
 103
 104         for(dev_class_t devclass = 0; devclass <= mesh->devclass; ++devclass) {
 105                 unsigned int connects = 0;
 106
 107                 for list_each(connection_t, c, mesh->connections) {
 108                         if(c->status.active && c->node && c->node->devclass == devclass) {
 109                                 connects += 1;
 110
 111                                 if(connects >= min_connects) {
 112                                         break;
 113                                 }
 114                         }
 115                 }
 116
 117                 if(connects >= min_connects) {
 118                         continue;
 119                 }
 120
 121                 node_t *candidate = NULL;
 122
 123                 for splay_each(node_t, n, mesh->nodes) {
 124                         if(n == mesh->self || n->devclass != devclass || n->connection || n->status.blacklisted) {
 125                                 continue;
 126                         }
 127
 128                         if(!candidate) {
 129                                 candidate = n;
 130                                 continue;
 131                         }
 132
 133                         if(compare_candidates(n, candidate)) {
 134                                 candidate = n;
 135                         }
 136                 }
 137
 138                 if(make_outgoing(mesh, candidate)) {
 139                         return true;
 140                 }
 141         }
 142
 143         return false;
 144 }
 145
 146 /* Disconnect from a random node that doesn't weaken the graph, and cancel redundant outgoings */
 147 static void disconnect_redundant(meshlink_handle_t *mesh) {
 148         int count = 0;
 149
 150         for list_each(connection_t, c, mesh->connections) {
 151                 if(!c->status.active || !c->outgoing || !c->node) {
 152                         continue;
 153                 }
 154
 155                 if(c->node->edge_tree->count < 2) {
 156                         continue;
 157                 }
 158
 159                 count++;
 160         }
 161
 162         if(!count) {
 163                 return;
 164         }
 165
 166         int r = rand() % count;
 167
 168         for list_each(connection_t, c, mesh->connections) {
 169                 if(!c->status.active || !c->outgoing || !c->node) {
 170                         continue;
 171                 }
 172
 173                 if(c->node->edge_tree->count < 2) {
 174                         continue;
 175                 }
 176
 177                 if(r--) {
 178                         continue;
 179                 }
 180
 181                 logger(mesh, MESHLINK_DEBUG, "Autodisconnecting from %s", c->name);
 182                 list_delete(mesh->outgoings, c->outgoing);
 183                 c->outgoing = NULL;
 184                 terminate_connection(mesh, c, c->status.active);
 185                 break;
 186         }
 187
 188         for list_each(outgoing_t, o, mesh->outgoings) {
 189                 if(!o->node->connection) {
 190                         list_delete_node(mesh->outgoings, node);
 191                 }
 192         }
 193 }
 194
 195 static void heal_partitions(meshlink_handle_t *mesh) {
 196         /* Select a random known node. The rationale is that if there are many
 197          * reachable nodes, and only a few unreachable nodes, we don't want all
 198          * reachable nodes to try to connect to the unreachable ones at the
 199          * same time. This way, we back off automatically. Conversely, if there
 200          * are only a few reachable nodes, and many unreachable ones, we're
 201          * going to try harder to connect to them. */
 202
 203         int r = rand() % mesh->nodes->count;
 204
 205         for splay_each(node_t, n, mesh->nodes) {
 206                 if(r--) {
 207                         continue;
 208                 }
 209
 210                 if(n == mesh->self || n->connection || n->status.reachable || n->status.blacklisted) {
 211                         return;
 212                 }
 213
 214                 /* Are we already trying to make an outgoing connection to it? If so, return. */
 215                 for list_each(outgoing_t, outgoing, mesh->outgoings) {
 216                         if(outgoing->node == n) {
 217                                 return;
 218                         }
 219                 }
 220
 221                 make_outgoing(mesh, n);
 222                 return;
 223         }
 224
 225 }
 226
 227 unsigned int do_autoconnect(meshlink_handle_t *mesh) {
 228         /* Count the number of active connections. */
 229
 230         unsigned int cur_connects = 0;
 231
 232         for list_each(connection_t, c, mesh->connections) {
 233                 if(c->status.active) {
 234                         cur_connects += 1;
 235                 }
 236         }
 237
 238         /* We don't have the minimum number of connections? Eagerly try to make a new one. */
 239
 240         const unsigned int max_connects = mesh->dev_class_traits[mesh->devclass].max_connects;
 241         const unsigned int min_connects = mesh->dev_class_traits[mesh->devclass].min_connects;
 242
 243         logger(mesh, MESHLINK_DEBUG, "do_autoconnect() %d %d %d\n", cur_connects, min_connects, max_connects);
 244
 245         if(cur_connects < min_connects) {
 246                 make_eager_connection(mesh);
 247         } else if(cur_connects < max_connects) {
 248                 /* Otherwise, try to improve. */
 249                 make_better_connection(mesh);
 250         }
 251
 252         if (cur_connects >= max_connects) {
 253                 disconnect_redundant(mesh);
 254         }
 255
 256         heal_partitions(mesh);
 257
 258         return cur_connects;
 259 }