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

   1 /*
   2     net.c -- most of the network code
   3     Copyright (C) 2014 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 "utils.h"
  23 #include "conf.h"
  24 #include "connection.h"
  25 #include "graph.h"
  26 #include "logger.h"
  27 #include "meshlink_internal.h"
  28 #include "meta.h"
  29 #include "net.h"
  30 #include "netutl.h"
  31 #include "protocol.h"
  32 #include "xalloc.h"
  33
  34 #include <assert.h>
  35
  36 #if !defined(min)
  37 static const int min(int a, int b) {
  38         return a < b ? a : b;
  39 }
  40 #endif
  41
  42 /*
  43   Terminate a connection:
  44   - Mark it as inactive
  45   - Remove the edge representing this connection
  46   - Kill it with fire
  47   - Check if we need to retry making an outgoing connection
  48 */
  49 void terminate_connection(meshlink_handle_t *mesh, connection_t *c, bool report) {
  50         logger(mesh, MESHLINK_INFO, "Closing connection with %s", c->name);
  51
  52         c->status.active = false;
  53
  54         if(c->node && c->node->connection == c)
  55                 c->node->connection = NULL;
  56
  57         if(c->edge) {
  58                 if(report)
  59                         send_del_edge(mesh, mesh->everyone, c->edge);
  60
  61                 edge_del(mesh, c->edge);
  62                 c->edge = NULL;
  63
  64                 /* Run MST and SSSP algorithms */
  65
  66                 graph(mesh);
  67
  68                 /* If the node is not reachable anymore but we remember it had an edge to us, clean it up */
  69
  70                 if(report && !c->node->status.reachable) {
  71                         edge_t *e;
  72                         e = lookup_edge(c->node, mesh->self);
  73                         if(e) {
  74                                 send_del_edge(mesh, mesh->everyone, e);
  75                                 edge_del(mesh, e);
  76                         }
  77                 }
  78         }
  79
  80         outgoing_t *outgoing = c->outgoing;
  81         connection_del(mesh, c);
  82
  83         /* Check if this was our outgoing connection */
  84
  85         if(outgoing)
  86                 do_outgoing_connection(mesh, outgoing);
  87
  88 #ifndef HAVE_MINGW
  89         /* Clean up dead proxy processes */
  90
  91         while(waitpid(-1, NULL, WNOHANG) > 0);
  92 #endif
  93 }
  94
  95 /*
  96   Check if the other end is active.
  97   If we have sent packets, but didn't receive any,
  98   then possibly the other end is dead. We send a
  99   PING request over the meta connection. If the other
 100   end does not reply in time, we consider them dead
 101   and close the connection.
 102 */
 103 static void timeout_handler(event_loop_t *loop, void *data) {
 104         meshlink_handle_t *mesh = loop->data;
 105         logger(mesh, MESHLINK_DEBUG, "timeout_handler()");
 106
 107         for list_each(connection_t, c, mesh->connections) {
 108                 // Also make sure that if outstanding key requests for the UDP counterpart of a connection has timed out, we restart it.
 109                 if(c->node) {
 110                         if(c->node->status.waitingforkey && c->node->last_req_key + mesh->pingtimeout <= mesh->loop.now.tv_sec)
 111                                 send_req_key(mesh, c->node);
 112                 }
 113                 if(c->last_ping_time + mesh->pingtimeout <= mesh->loop.now.tv_sec) {
 114                         if(c->status.active) {
 115                                 if(c->status.pinged)
 116                                         logger(mesh, MESHLINK_INFO, "%s didn't respond to PING in %ld seconds", c->name, (long)mesh->loop.now.tv_sec - c->last_ping_time);
 117                                 else if(c->last_ping_time + mesh->pinginterval <= mesh->loop.now.tv_sec) {
 118                                         send_ping(mesh, c);
 119                                         continue;
 120                                 } else
 121                                         continue;
 122                         } else {
 123                                 if(c->status.connecting)
 124                                         logger(mesh, MESHLINK_WARNING, "Timeout while connecting to %s", c->name);
 125                                 else
 126                                         logger(mesh, MESHLINK_WARNING, "Timeout from %s during authentication", c->name);
 127                         }
 128                         terminate_connection(mesh, c, c->status.active);
 129                 }
 130         }
 131
 132         timeout_set(&mesh->loop, data, &(struct timeval) {
 133                 mesh->pingtimeout, rand() % 100000
 134         });
 135 }
 136
 137 // devclass asc, last_successfull_connection desc
 138 static int node_compare_devclass_asc_lsc_desc(const void *a, const void *b) {
 139         const node_t *na = a, *nb = b;
 140
 141         if(na->devclass < nb->devclass)
 142                 return -1;
 143
 144         if(na->devclass > nb->devclass)
 145                 return 1;
 146
 147         if(na->last_successfull_connection == nb->last_successfull_connection)
 148                 return 0;
 149
 150         if(na->last_successfull_connection == 0 || na->last_successfull_connection > nb->last_successfull_connection)
 151                 return -1;
 152
 153         if(nb->last_successfull_connection == 0 || na->last_successfull_connection < nb->last_successfull_connection)
 154                 return 1;
 155
 156         if(na < nb)
 157                 return -1;
 158
 159         if(na > nb)
 160                 return 1;
 161
 162         return 0;
 163 }
 164
 165 // last_successfull_connection desc
 166 static int node_compare_lsc_desc(const void *a, const void *b) {
 167         const node_t *na = a, *nb = b;
 168
 169         if(na->last_successfull_connection == nb->last_successfull_connection)
 170                 return 0;
 171
 172         if(na->last_successfull_connection == 0 || na->last_successfull_connection > nb->last_successfull_connection)
 173                 return -1;
 174
 175         if(nb->last_successfull_connection == 0 || na->last_successfull_connection < nb->last_successfull_connection)
 176                 return 1;
 177
 178         if(na < nb)
 179                 return -1;
 180
 181         if(na > nb)
 182                 return 1;
 183
 184         return 0;
 185 }
 186
 187 // devclass desc
 188 static int node_compare_devclass_desc(const void *a, const void *b) {
 189         const node_t *na = a, *nb = b;
 190
 191         if(na->devclass < nb->devclass)
 192                 return -1;
 193
 194         if(na->devclass > nb->devclass)
 195                 return 1;
 196
 197         if(na < nb)
 198                 return -1;
 199
 200         if(na > nb)
 201                 return 1;
 202
 203         return 0;
 204 }
 205
 206
 207 /*
 208
 209 autoconnect()
 210 {
 211         timeout = 5
 212
 213         // find the best one for initial connect
 214
 215         if cur < min
 216                 newcon =
 217                         first from nodes
 218                                 where dclass <= my.dclass and !connection and (timestamp - last_retry) > retry_timeout
 219                                 order by dclass asc, last_connection desc
 220                 if newcon
 221                         timeout = 0
 222                         goto connect
 223
 224
 225         // find better nodes to connect to: in case we have less than min connections within [BACKBONE, i] and there are nodes which we are not connected to within the range
 226
 227         if min <= cur < max
 228                 j = 0
 229                 for i = BACKBONE to my.dclass
 230                         j += count(from connections where node.dclass = i)
 231                         if j < min
 232                                 newcon =
 233                                         first from nodes
 234                                                 where dclass = i and !connection and (timestamp - last_retry) > retry_timeout
 235                                                 order by last_connection desc
 236                                 if newcon
 237                                         goto connect
 238                         else
 239                                 break
 240
 241
 242         // heal partitions
 243
 244         if min <= cur < max
 245                 newcon =
 246                         first from nodes
 247                                 where dclass <= my.dclass and !reachable and (timestamp - last_retry) > retry_timeout
 248                                 order by dclass asc, last_connection desc
 249                 if newcon
 250                         goto connect
 251
 252
 253         // connect
 254
 255 connect:
 256         if newcon
 257                 connect newcon
 258
 259
 260         // disconnect outgoing connections in case we have more than min connections within [BACKBONE, i] and there are nodes which we are connected to within the range [i, PORTABLE]
 261
 262         if min < cur <= max
 263                 j = 0
 264                 for i = BACKBONE to my.dclass
 265                         j += count(from connections where node.dclass = i)
 266                         if min < j
 267                                 delcon =
 268                                         first from nodes
 269                                                 where dclass >= i and outgoing_connection
 270                                                 order by dclass desc
 271                                 if disconnect
 272                                         goto disconnect
 273                                 else
 274                                         break
 275
 276
 277         // disconnect connections in case we have more than enough connections
 278
 279         if max < cur
 280                 delcon =
 281                         first from nodes
 282                                 where outgoing_connection
 283                                 order by dclass desc
 284                 goto disconnect
 285
 286         // disconnect
 287
 288 disconnect
 289         if delcon
 290                 disconnect delcon
 291
 292
 293         // next iteration
 294         next (timeout, autoconnect)
 295
 296 }
 297
 298 */
 299
 300
 301 static void periodic_handler(event_loop_t *loop, void *data) {
 302         meshlink_handle_t *mesh = loop->data;
 303
 304         /* Check if there are too many contradicting ADD_EDGE and DEL_EDGE messages.
 305            This usually only happens when another node has the same Name as this node.
 306            If so, sleep for a short while to prevent a storm of contradicting messages.
 307         */
 308
 309         if(mesh->contradicting_del_edge > 100 && mesh->contradicting_add_edge > 100) {
 310                 logger(mesh, MESHLINK_WARNING, "Possible node with same Name as us! Sleeping %d seconds.", mesh->sleeptime);
 311                 usleep(mesh->sleeptime * 1000000LL);
 312                 mesh->sleeptime *= 2;
 313                 if(mesh->sleeptime < 0)
 314                         mesh->sleeptime = 3600;
 315         } else {
 316                 mesh->sleeptime /= 2;
 317                 if(mesh->sleeptime < 10)
 318                         mesh->sleeptime = 10;
 319         }
 320
 321         mesh->contradicting_add_edge = 0;
 322         mesh->contradicting_del_edge = 0;
 323
 324         int timeout = 5;
 325
 326         /* Check if we need to make or break connections. */
 327
 328         if(mesh->nodes->count > 1) {
 329
 330                 logger(mesh, MESHLINK_DEBUG, "--- autoconnect begin ---");
 331
 332                 int retry_timeout = min(mesh->nodes->count * 5, 60);
 333
 334                 logger(mesh, MESHLINK_DEBUG, "* devclass = %d", mesh->devclass);
 335                 logger(mesh, MESHLINK_DEBUG, "* nodes = %d", mesh->nodes->count);
 336                 logger(mesh, MESHLINK_DEBUG, "* retry_timeout = %d", retry_timeout);
 337
 338
 339                 // connect disconnect nodes
 340
 341                 node_t *connect_to = NULL;
 342                 node_t *disconnect_from = NULL;
 343
 344
 345                 // get cur_connects
 346
 347                 int cur_connects = 0;
 348
 349                 for list_each(connection_t, c, mesh->connections) {
 350                         if(c->status.active)
 351                                 cur_connects += 1;
 352                 }
 353
 354                 logger(mesh, MESHLINK_DEBUG, "* cur_connects = %d", cur_connects);
 355                 logger(mesh, MESHLINK_DEBUG, "* outgoings = %d", mesh->outgoings->count);
 356
 357                 // get min_connects and max_connects
 358
 359                 assert(mesh->devclass >= 0 && mesh->devclass <= _DEV_CLASS_MAX);
 360
 361                 int min_connects = dev_class_traits[mesh->devclass].min_connects;
 362                 int max_connects = dev_class_traits[mesh->devclass].max_connects;
 363
 364                 logger(mesh, MESHLINK_DEBUG, "* min_connects = %d", min_connects);
 365                 logger(mesh, MESHLINK_DEBUG, "* max_connects = %d", max_connects);
 366
 367
 368                 // find the best one for initial connect
 369
 370                 if(cur_connects < min_connects) {
 371                         splay_tree_t *nodes = splay_alloc_tree(node_compare_devclass_asc_lsc_desc, NULL);
 372
 373                         for splay_each(node_t, n, mesh->nodes) {
 374                                 logger(mesh, MESHLINK_DEBUG, "* n->devclass = %d", n->devclass);
 375                                 if(n != mesh->self && n->devclass <= mesh->devclass && !n->connection && (n->last_connect_try == 0 || (time(NULL) - n->last_connect_try) > retry_timeout))
 376                                         splay_insert(nodes, n);
 377                         }
 378
 379                         if(nodes->head) {
 380                                 logger(mesh, MESHLINK_DEBUG, "* found best one for initial connect");
 381
 382                                 //timeout = 0;
 383                                 connect_to = (node_t *)nodes->head->data;
 384                         } else
 385                                 logger(mesh, MESHLINK_DEBUG, "* could not find node for initial connect");
 386
 387                         splay_free_tree(nodes);
 388                 }
 389
 390
 391                 // find better nodes to connect to
 392
 393                 if(!connect_to && min_connects <= cur_connects && cur_connects < max_connects) {
 394                         unsigned int connects = 0;
 395
 396                         for(int devclass = 0; devclass <= mesh->devclass; ++devclass) {
 397                                 for list_each(connection_t, c, mesh->connections) {
 398                                         if(c->status.active && c->node && c->node->devclass == devclass)
 399                                                 connects += 1;
 400                                 }
 401
 402                                 if(connects < min_connects) {
 403                                         splay_tree_t *nodes = splay_alloc_tree(node_compare_lsc_desc, NULL);
 404
 405                                         for splay_each(node_t, n, mesh->nodes) {
 406                                                 if(n != mesh->self && n->devclass == devclass && !n->connection && (n->last_connect_try == 0 || (time(NULL) - n->last_connect_try) > retry_timeout))
 407                                                         splay_insert(nodes, n);
 408                                         }
 409
 410                                         if(nodes->head) {
 411                                                 logger(mesh, MESHLINK_DEBUG, "* found better node");
 412                                                 connect_to = (node_t *)nodes->head->data;
 413
 414                                                 splay_free_tree(nodes);
 415                                                 break;
 416                                         }
 417
 418                                         splay_free_tree(nodes);
 419                                 } else
 420                                         break;
 421                         }
 422
 423                         if(!connect_to)
 424                                 logger(mesh, MESHLINK_DEBUG, "* could not find better nodes");
 425                 }
 426
 427
 428                 // heal partitions
 429
 430                 if(!connect_to && min_connects <= cur_connects && cur_connects < max_connects) {
 431                         splay_tree_t *nodes = splay_alloc_tree(node_compare_devclass_asc_lsc_desc, NULL);
 432
 433                         for splay_each(node_t, n, mesh->nodes) {
 434                                 if(n != mesh->self && n->devclass <= mesh->devclass && !n->status.reachable && (n->last_connect_try == 0 || (time(NULL) - n->last_connect_try) > retry_timeout))
 435                                         splay_insert(nodes, n);
 436                         }
 437
 438                         if(nodes->head) {
 439                                 logger(mesh, MESHLINK_DEBUG, "* try to heal partition");
 440                                 connect_to = (node_t *)nodes->head->data;
 441                         } else
 442                                 logger(mesh, MESHLINK_DEBUG, "* could not find nodes for partition healing");
 443
 444                         splay_free_tree(nodes);
 445                 }
 446
 447
 448                 // perform connect
 449
 450                 if(connect_to && !connect_to->connection) {
 451                         connect_to->last_connect_try = time(NULL);
 452
 453                         /* check if there is already a connection attempt to this node */
 454                         bool found = false;
 455                         for list_each(outgoing_t, outgoing, mesh->outgoings) {
 456                                 if(!strcmp(outgoing->name, connect_to->name)) {
 457                                         found = true;
 458                                         break;
 459                                 }
 460                         }
 461
 462                         if(!found) {
 463                                 logger(mesh, MESHLINK_DEBUG, "Autoconnecting to %s", connect_to->name);
 464                                 outgoing_t *outgoing = xzalloc(sizeof(outgoing_t));
 465                                 outgoing->mesh = mesh;
 466                                 outgoing->name = xstrdup(connect_to->name);
 467                                 list_insert_tail(mesh->outgoings, outgoing);
 468                                 setup_outgoing_connection(mesh, outgoing);
 469                         } else
 470                                 logger(mesh, MESHLINK_DEBUG, "* skip autoconnect since it is an outgoing connection already");
 471                 }
 472
 473
 474                 // disconnect suboptimal outgoing connections
 475
 476                 if(min_connects < cur_connects /*&& cur_connects <= max_connects*/) {
 477                         unsigned int connects = 0;
 478
 479                         for(int devclass = 0; devclass <= mesh->devclass; ++devclass) {
 480                                 for list_each(connection_t, c, mesh->connections) {
 481                                         if(c->status.active && c->node && c->node->devclass == devclass)
 482                                                 connects += 1;
 483                                 }
 484
 485                                 if(min_connects < connects) {
 486                                         splay_tree_t *nodes = splay_alloc_tree(node_compare_devclass_desc, NULL);
 487
 488                                         for list_each(connection_t, c, mesh->connections) {
 489                                                 if(c->outgoing && c->node && c->node->devclass >= devclass)
 490                                                         splay_insert(nodes, c->node);
 491                                         }
 492
 493                                         if(nodes->head) {
 494                                                 logger(mesh, MESHLINK_DEBUG, "* disconnect suboptimal outgoing connection");
 495                                                 disconnect_from = (node_t *)nodes->head->data;
 496                                         }
 497
 498                                         splay_free_tree(nodes);
 499                                         break;
 500                                 }
 501                         }
 502
 503                         if(!disconnect_from)
 504                                 logger(mesh, MESHLINK_DEBUG, "* no suboptimal outgoing connections");
 505                 }
 506
 507
 508                 // disconnect connections (too many connections)
 509
 510                 if(!disconnect_from && max_connects < cur_connects) {
 511                         splay_tree_t *nodes = splay_alloc_tree(node_compare_devclass_desc, NULL);
 512
 513                         for list_each(connection_t, c, mesh->connections) {
 514                                 if(c->status.active && c->node)
 515                                         splay_insert(nodes, c->node);
 516                         }
 517
 518                         if(nodes->head) {
 519                                 logger(mesh, MESHLINK_DEBUG, "* disconnect connection (too many connections)");
 520
 521                                 //timeout = 0;
 522                                 disconnect_from = (node_t *)nodes->head->data;
 523                         } else
 524                                 logger(mesh, MESHLINK_DEBUG, "* no node we want to disconnect, even though we have too many connections");
 525
 526                         splay_free_tree(nodes);
 527                 }
 528
 529
 530                 // perform disconnect
 531
 532                 if(disconnect_from && disconnect_from->connection) {
 533                         logger(mesh, MESHLINK_DEBUG, "Autodisconnecting from %s", disconnect_from->connection->name);
 534                         list_delete(mesh->outgoings, disconnect_from->connection->outgoing);
 535                         disconnect_from->connection->outgoing = NULL;
 536                         terminate_connection(mesh, disconnect_from->connection, disconnect_from->connection->status.active);
 537                 }
 538
 539
 540                 // done!
 541
 542                 logger(mesh, MESHLINK_DEBUG, "--- autoconnect end ---");
 543         }
 544
 545         timeout_set(&mesh->loop, data, &(struct timeval) {
 546                 timeout, rand() % 100000
 547         });
 548 }
 549
 550 void handle_meta_connection_data(meshlink_handle_t *mesh, connection_t *c) {
 551         if(!receive_meta(mesh, c)) {
 552                 terminate_connection(mesh, c, c->status.active);
 553                 return;
 554         }
 555 }
 556
 557 void retry(meshlink_handle_t *mesh) {
 558         /* Reset the reconnection timers for all outgoing connections */
 559         for list_each(outgoing_t, outgoing, mesh->outgoings) {
 560                 outgoing->timeout = 0;
 561                 if(outgoing->ev.cb)
 562                         timeout_set(&mesh->loop, &outgoing->ev, &(struct timeval) {
 563                         0, 0
 564                 });
 565         }
 566
 567         /* Check for outgoing connections that are in progress, and reset their ping timers */
 568         for list_each(connection_t, c, mesh->connections) {
 569                 if(c->outgoing && !c->node)
 570                         c->last_ping_time = 0;
 571         }
 572
 573         /* Kick the ping timeout handler */
 574         timeout_set(&mesh->loop, &mesh->pingtimer, &(struct timeval) {
 575                 0, 0
 576         });
 577 }
 578
 579 /*
 580   this is where it all happens...
 581 */
 582 int main_loop(meshlink_handle_t *mesh) {
 583         timeout_add(&mesh->loop, &mesh->pingtimer, timeout_handler, &mesh->pingtimer, &(struct timeval) {
 584                 mesh->pingtimeout, rand() % 100000
 585         });
 586         timeout_add(&mesh->loop, &mesh->periodictimer, periodic_handler, &mesh->periodictimer, &(struct timeval) {
 587                 0, 0
 588         });
 589
 590         //Add signal handler
 591         mesh->datafromapp.signum = 0;
 592         signal_add(&(mesh->loop), &(mesh->datafromapp), (signal_cb_t)meshlink_send_from_queue, mesh, mesh->datafromapp.signum);
 593
 594         if(!event_loop_run(&(mesh->loop), &(mesh->mesh_mutex))) {
 595                 logger(mesh, MESHLINK_ERROR, "Error while waiting for input: %s", strerror(errno));
 596                 return 1;
 597         }
 598
 599         timeout_del(&mesh->loop, &mesh->periodictimer);
 600         timeout_del(&mesh->loop, &mesh->pingtimer);
 601
 602         return 0;
 603 }