src/mesh/gnunet-service-mesh_channel.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2013 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21
  22 #include "platform.h"
  23 #include "mesh_enc.h"
  24 #include "mesh_protocol_enc.h"
  25 #include "gnunet-service-mesh_channel.h"
  26 #include "gnunet-service-mesh_local.h"
  27
  28
  29
  30 /**
  31  * All the states a connection can be in.
  32  */
  33 enum MeshChannelState
  34 {
  35   /**
  36    * Uninitialized status, should never appear in operation.
  37    */
  38   MESH_CHANNEL_NEW,
  39
  40   /**
  41    * Connection create message sent, waiting for ACK.
  42    */
  43   MESH_CHANNEL_SENT,
  44
  45   /**
  46    * Connection confirmed, ready to carry traffic..
  47    */
  48   MESH_CHANNEL_READY,
  49 };
  50
  51
  52
  53 /**
  54  * Info needed to retry a message in case it gets lost.
  55  */
  56 struct MeshReliableMessage
  57 {
  58     /**
  59      * Double linked list, FIFO style
  60      */
  61   struct MeshReliableMessage    *next;
  62   struct MeshReliableMessage    *prev;
  63
  64     /**
  65      * Type of message (payload, channel management).
  66      */
  67   int16_t type;
  68
  69     /**
  70      * Tunnel Reliability queue this message is in.
  71      */
  72   struct MeshChannelReliability  *rel;
  73
  74     /**
  75      * ID of the message (ACK needed to free)
  76      */
  77   uint32_t                      mid;
  78
  79     /**
  80      * When was this message issued (to calculate ACK delay)
  81      */
  82   struct GNUNET_TIME_Absolute   timestamp;
  83
  84   /* struct GNUNET_MESH_Data with payload */
  85 };
  86
  87
  88 /**
  89  * Info about the traffic state for a client in a channel.
  90  */
  91 struct MeshChannelReliability
  92 {
  93     /**
  94      * Channel this is about.
  95      */
  96   struct MeshChannel *ch;
  97
  98     /**
  99      * DLL of messages sent and not yet ACK'd.
 100      */
 101   struct MeshReliableMessage        *head_sent;
 102   struct MeshReliableMessage        *tail_sent;
 103
 104     /**
 105      * Messages pending to send.
 106      */
 107   unsigned int                      n_sent;
 108
 109     /**
 110      * DLL of messages received out of order.
 111      */
 112   struct MeshReliableMessage        *head_recv;
 113   struct MeshReliableMessage        *tail_recv;
 114
 115     /**
 116      * Messages received.
 117      */
 118   unsigned int                      n_recv;
 119
 120     /**
 121      * Next MID to use for outgoing traffic.
 122      */
 123   uint32_t                          mid_send;
 124
 125     /**
 126      * Next MID expected for incoming traffic.
 127      */
 128   uint32_t                          mid_recv;
 129
 130     /**
 131      * Can we send data to the client?
 132      */
 133   int                               client_ready;
 134
 135     /**
 136      * Task to resend/poll in case no ACK is received.
 137      */
 138   GNUNET_SCHEDULER_TaskIdentifier   retry_task;
 139
 140     /**
 141      * Counter for exponential backoff.
 142      */
 143   struct GNUNET_TIME_Relative       retry_timer;
 144
 145     /**
 146      * How long does it usually take to get an ACK.
 147      */
 148   struct GNUNET_TIME_Relative       expected_delay;
 149 };
 150
 151
 152 /**
 153  * Struct containing all information regarding a channel to a remote client.
 154  */
 155 struct MeshChannel
 156 {
 157     /**
 158      * Tunnel this channel is in.
 159      */
 160   struct MeshTunnel2 *t;
 161
 162     /**
 163      * Double linked list.
 164      */
 165   struct MeshChannel    *next;
 166   struct MeshChannel    *prev;
 167
 168     /**
 169      * Destination port of the channel.
 170      */
 171   uint32_t port;
 172
 173     /**
 174      * Global channel number ( < GNUNET_MESH_LOCAL_CHANNEL_ID_CLI)
 175      */
 176   MESH_ChannelNumber gid;
 177
 178     /**
 179      * Local tunnel number for root (owner) client.
 180      * ( >= GNUNET_MESH_LOCAL_CHANNEL_ID_CLI or 0 )
 181      */
 182   MESH_ChannelNumber lid_root;
 183
 184     /**
 185      * Local tunnel number for local destination clients (incoming number)
 186      * ( >= GNUNET_MESH_LOCAL_CHANNEL_ID_SERV or 0).
 187      */
 188   MESH_ChannelNumber lid_dest;
 189
 190     /**
 191      * Channel state.
 192      */
 193   enum MeshChannelState state;
 194
 195     /**
 196      * Is the tunnel bufferless (minimum latency)?
 197      */
 198   int nobuffer;
 199
 200     /**
 201      * Is the tunnel reliable?
 202      */
 203   int reliable;
 204
 205     /**
 206      * Last time the channel was used
 207      */
 208   struct GNUNET_TIME_Absolute timestamp;
 209
 210     /**
 211      * Client owner of the tunnel, if any
 212      */
 213   struct MeshClient *root;
 214
 215     /**
 216      * Client destination of the tunnel, if any.
 217      */
 218   struct MeshClient *dest;
 219
 220     /**
 221      * Flag to signal the destruction of the channel.
 222      * If this is set GNUNET_YES the channel will be destroyed
 223      * when the queue is empty.
 224      */
 225   int destroy;
 226
 227     /**
 228      * Total messages pending for this channel, payload or not.
 229      */
 230   unsigned int pending_messages;
 231
 232     /**
 233      * Reliability data.
 234      * Only present (non-NULL) at the owner of a tunnel.
 235      */
 236   struct MeshChannelReliability *root_rel;
 237
 238     /**
 239      * Reliability data.
 240      * Only present (non-NULL) at the destination of a tunnel.
 241      */
 242   struct MeshChannelReliability *dest_rel;
 243
 244 };
 245
 246
 247 /**
 248  * We have received a message out of order, or the client is not ready.
 249  * Buffer it until we receive an ACK from the client or the missing
 250  * message from the channel.
 251  *
 252  * @param msg Message to buffer (MUST be of type MESH_DATA).
 253  * @param rel Reliability data to the corresponding direction.
 254  */
 255 static void
 256 add_buffered_data (const struct GNUNET_MESH_Data *msg,
 257                    struct MeshChannelReliability *rel)
 258 {
 259   struct MeshReliableMessage *copy;
 260   struct MeshReliableMessage *prev;
 261   uint32_t mid;
 262   uint16_t size;
 263
 264   size = ntohs (msg->header.size);
 265   mid = ntohl (msg->mid);
 266
 267   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "add_buffered_data %u\n", mid);
 268
 269   copy = GNUNET_malloc (sizeof (*copy) + size);
 270   copy->mid = mid;
 271   copy->rel = rel;
 272   memcpy (&copy[1], msg, size);
 273
 274   rel->n_recv++;
 275
 276   // FIXME do something better than O(n), although n < 64...
 277   // FIXME start from the end (most messages are the latest ones)
 278   for (prev = rel->head_recv; NULL != prev; prev = prev->next)
 279   {
 280     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " prev %u\n", prev->mid);
 281     if (GMC_is_pid_bigger (prev->mid, mid))
 282     {
 283       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " bingo!\n");
 284       GNUNET_CONTAINER_DLL_insert_before (rel->head_recv, rel->tail_recv,
 285                                           prev, copy);
 286       return;
 287     }
 288   }
 289     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " insert at tail!\n");
 290     GNUNET_CONTAINER_DLL_insert_tail (rel->head_recv, rel->tail_recv, copy);
 291     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "add_buffered_data END\n");
 292 }
 293
 294
 295 /**
 296  * Send data to a client.
 297  *
 298  * If the client is ready, send directly, otherwise buffer while listening
 299  * for a local ACK.
 300  *
 301  * @param ch Channel
 302  * @param msg Message.
 303  * @param fwd Is this a fwd (root->dest) message?
 304  */
 305 static void
 306 send_client_data (struct MeshChannel *ch,
 307                   const struct GNUNET_MESH_Data *msg,
 308                   int fwd)
 309 {
 310   if (fwd)
 311   {
 312     if (ch->dest_rel->client_ready)
 313       GML_send_data (ch, msg, ch->dest, ch->lid_dest);
 314     else
 315       add_buffered_data (msg, ch->dest_rel);
 316   }
 317   else
 318   {
 319     if (ch->root_rel->client_ready)
 320       GML_send_data (ch, msg, ch->root, ch->lid_root);
 321     else
 322       add_buffered_data (msg, ch->root_rel);
 323   }
 324 }
 325
 326
 327 /**
 328  * Search for a channel among the channels for a client
 329  *
 330  * @param c the client whose channels to search in
 331  * @param chid the local id of the channel
 332  *
 333  * @return channel handler, NULL if doesn't exist
 334  */
 335 static struct MeshChannel *
 336 channel_get_by_local_id (struct MeshClient *c, MESH_ChannelNumber chid)
 337 {
 338   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "   -- get CHID %X\n", chid);
 339   if (0 == (chid & GNUNET_MESH_LOCAL_CHANNEL_ID_CLI))
 340   {
 341     GNUNET_break_op (0);
 342     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "CHID %X not a local chid\n", chid);
 343     return NULL;
 344   }
 345   if (chid >= GNUNET_MESH_LOCAL_CHANNEL_ID_SERV)
 346     return GNUNET_CONTAINER_multihashmap32_get (c->incoming_channels, chid);
 347   return GNUNET_CONTAINER_multihashmap32_get (c->own_channels, chid);
 348 }
 349
 350
 351
 352 /**
 353  * Search for a channel by global ID using full PeerIdentities.
 354  *
 355  * @param t Tunnel containing the channel.
 356  * @param chid Public channel number.
 357  *
 358  * @return channel handler, NULL if doesn't exist
 359  */
 360 static struct MeshChannel *
 361 channel_get (struct MeshTunnel2 *t, MESH_ChannelNumber chid)
 362 {
 363   struct MeshChannel *ch;
 364
 365   if (NULL == t)
 366     return NULL;
 367
 368   for (ch = t->channel_head; NULL != ch; ch = ch->next)
 369   {
 370     if (ch->gid == chid)
 371       break;
 372   }
 373
 374   return ch;
 375 }
 376
 377
 378 /**
 379  * Add a client to a channel, initializing all needed data structures.
 380  *
 381  * @param ch Channel to which add the client.
 382  * @param c Client which to add to the channel.
 383  */
 384 static void
 385 channel_add_client (struct MeshChannel *ch, struct MeshClient *c)
 386 {
 387   struct MeshTunnel2 *t = ch->t;
 388
 389   if (NULL != ch->dest)
 390   {
 391     GNUNET_break (0);
 392     return;
 393   }
 394
 395   /* Assign local id as destination */
 396   while (NULL != channel_get_by_local_id (c, t->next_local_chid))
 397     t->next_local_chid = (t->next_local_chid + 1) | GNUNET_MESH_LOCAL_CHANNEL_ID_SERV;
 398   ch->lid_dest = t->next_local_chid++;
 399   t->next_local_chid = t->next_local_chid | GNUNET_MESH_LOCAL_CHANNEL_ID_SERV;
 400
 401   /* Store in client's hashmap */
 402   if (GNUNET_OK !=
 403       GNUNET_CONTAINER_multihashmap32_put (c->incoming_channels,
 404                                            ch->lid_dest, ch,
 405                                            GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST))
 406   {
 407     GNUNET_break (0);
 408     return;
 409   }
 410
 411   GNUNET_break (NULL == ch->dest_rel);
 412   ch->dest_rel = GNUNET_new (struct MeshChannelReliability);
 413   ch->dest_rel->ch = ch;
 414   ch->dest_rel->expected_delay = MESH_RETRANSMIT_TIME;
 415
 416   ch->dest = c;
 417 }
 418
 419
 420
 421 /**
 422  * Is the root client for this channel on this peer?
 423  *
 424  * @param ch Channel.
 425  * @param fwd Is this for fwd traffic?
 426  *
 427  * @return GNUNET_YES in case it is.
 428  */
 429 static int
 430 channel_is_origin (struct MeshChannel *ch, int fwd)
 431 {
 432   struct MeshClient *c;
 433
 434   c = fwd ? ch->root : ch->dest;
 435   return NULL != c;
 436 }
 437
 438
 439 /**
 440  * Is the destination client for this channel on this peer?
 441  *
 442  * @param ch Channel.
 443  * @param fwd Is this for fwd traffic?
 444  *
 445  * @return GNUNET_YES in case it is.
 446  */
 447 static int
 448 channel_is_terminal (struct MeshChannel *ch, int fwd)
 449 {
 450   struct MeshClient *c;
 451
 452   c = fwd ? ch->dest : ch->root;
 453   return NULL != c;
 454 }
 455
 456
 457 /**
 458  * Get free buffer space towards the client on a specific channel.
 459  *
 460  * @param ch Channel.
 461  * @param fwd Is query about FWD traffic?
 462  *
 463  * @return Free buffer space [0 - 64]
 464  */
 465 static unsigned int
 466 channel_get_buffer (struct MeshChannel *ch, int fwd)
 467 {
 468   struct MeshChannelReliability *rel;
 469
 470   rel = fwd ? ch->dest_rel : ch->root_rel;
 471
 472   /* If rel is NULL it means that the end is not yet created,
 473    * most probably is a loopback channel at the point of sending
 474    * the ChannelCreate to itself.
 475    */
 476   if (NULL == rel)
 477     return 64;
 478
 479   return (64 - rel->n_recv);
 480 }
 481
 482
 483
 484
 485 /**
 486  * Destroy all reliable messages queued for a channel,
 487  * during a channel destruction.
 488  * Frees the reliability structure itself.
 489  *
 490  * @param rel Reliability data for a channel.
 491  */
 492 static void
 493 channel_rel_free_all (struct MeshChannelReliability *rel)
 494 {
 495   struct MeshReliableMessage *copy;
 496   struct MeshReliableMessage *next;
 497
 498   if (NULL == rel)
 499     return;
 500
 501   for (copy = rel->head_recv; NULL != copy; copy = next)
 502   {
 503     next = copy->next;
 504     GNUNET_CONTAINER_DLL_remove (rel->head_recv, rel->tail_recv, copy);
 505     GNUNET_free (copy);
 506   }
 507   for (copy = rel->head_sent; NULL != copy; copy = next)
 508   {
 509     next = copy->next;
 510     GNUNET_CONTAINER_DLL_remove (rel->head_sent, rel->tail_sent, copy);
 511     GNUNET_free (copy);
 512   }
 513   if (GNUNET_SCHEDULER_NO_TASK != rel->retry_task)
 514     GNUNET_SCHEDULER_cancel (rel->retry_task);
 515   GNUNET_free (rel);
 516 }
 517
 518
 519 /**
 520  * Mark future messages as ACK'd.
 521  *
 522  * @param rel Reliability data.
 523  * @param msg DataACK message with a bitfield of future ACK'd messages.
 524  */
 525 static void
 526 channel_rel_free_sent (struct MeshChannelReliability *rel,
 527                        const struct GNUNET_MESH_DataACK *msg)
 528 {
 529   struct MeshReliableMessage *copy;
 530   struct MeshReliableMessage *next;
 531   uint64_t bitfield;
 532   uint64_t mask;
 533   uint32_t mid;
 534   uint32_t target;
 535   unsigned int i;
 536
 537   bitfield = msg->futures;
 538   mid = ntohl (msg->mid);
 539   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 540               "free_sent_reliable %u %llX\n",
 541               mid, bitfield);
 542   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 543               " rel %p, head %p\n",
 544               rel, rel->head_sent);
 545   for (i = 0, copy = rel->head_sent;
 546        i < 64 && NULL != copy && 0 != bitfield;
 547        i++)
 548   {
 549     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 550                 " trying bit %u (mid %u)\n",
 551                 i, mid + i + 1);
 552     mask = 0x1LL << i;
 553     if (0 == (bitfield & mask))
 554      continue;
 555
 556     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " set!\n");
 557     /* Bit was set, clear the bit from the bitfield */
 558     bitfield &= ~mask;
 559
 560     /* The i-th bit was set. Do we have that copy? */
 561     /* Skip copies with mid < target */
 562     target = mid + i + 1;
 563     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " target %u\n", target);
 564     while (NULL != copy && GMC_is_pid_bigger (target, copy->mid))
 565      copy = copy->next;
 566
 567     /* Did we run out of copies? (previously freed, it's ok) */
 568     if (NULL == copy)
 569     {
 570      GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "run out of copies...\n");
 571      return;
 572     }
 573
 574     /* Did we overshoot the target? (previously freed, it's ok) */
 575     if (GMC_is_pid_bigger (copy->mid, target))
 576     {
 577      GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " next copy %u\n", copy->mid);
 578      continue;
 579     }
 580
 581     /* Now copy->mid == target, free it */
 582     next = copy->next;
 583     rel_message_free (copy);
 584     copy = next;
 585   }
 586   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "free_sent_reliable END\n");
 587 }
 588
 589
 590 /**
 591  * We haven't received an ACK after a certain time: restransmit the message.
 592  *
 593  * @param cls Closure (MeshReliableMessage with the message to restransmit)
 594  * @param tc TaskContext.
 595  */
 596 static void
 597 channel_retransmit_message (void *cls,
 598                             const struct GNUNET_SCHEDULER_TaskContext *tc)
 599 {
 600   struct MeshChannelReliability *rel = cls;
 601   struct MeshReliableMessage *copy;
 602   struct MeshPeerQueue *q;
 603   struct MeshChannel *ch;
 604   struct MeshConnection *c;
 605   struct GNUNET_MESH_Data *payload;
 606   struct MeshPeer *hop;
 607   int fwd;
 608
 609   rel->retry_task = GNUNET_SCHEDULER_NO_TASK;
 610   if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
 611     return;
 612
 613   ch = rel->ch;
 614   copy = rel->head_sent;
 615   if (NULL == copy)
 616   {
 617     GNUNET_break (0);
 618     return;
 619   }
 620
 621   /* Search the message to be retransmitted in the outgoing queue.
 622    * Check only the queue for the connection that is going to be used,
 623    * if the message is stuck in some other connection's queue we shouldn't
 624    * act upon it:
 625    * - cancelling it and sending the new one doesn't guarantee it's delivery,
 626    *   the old connection could be temporary stalled or the queue happened to
 627    *   be long at time of insertion.
 628    * - not sending the new one could cause terrible delays the old connection
 629    *   is stalled.
 630    */
 631   payload = (struct GNUNET_MESH_Data *) &copy[1];
 632   fwd = (rel == ch->root_rel);
 633   c = tunnel_get_connection (ch->t, fwd);
 634   hop = connection_get_hop (c, fwd);
 635   for (q = hop->queue_head; NULL != q; q = q->next)
 636   {
 637     if (ntohs (payload->header.type) == q->type && ch == q->ch)
 638     {
 639       struct GNUNET_MESH_Data *queued_data = q->cls;
 640
 641       if (queued_data->mid == payload->mid)
 642         break;
 643     }
 644   }
 645
 646   /* Message not found in the queue that we are going to use. */
 647   if (NULL == q)
 648   {
 649     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "!!! RETRANSMIT %u\n", copy->mid);
 650
 651     send_prebuilt_message_channel (&payload->header, ch, fwd);
 652     GNUNET_STATISTICS_update (stats, "# data retransmitted", 1, GNUNET_NO);
 653   }
 654   else
 655   {
 656     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "!!! ALREADY IN QUEUE %u\n", copy->mid);
 657   }
 658
 659   rel->retry_timer = GNUNET_TIME_STD_BACKOFF (rel->retry_timer);
 660   rel->retry_task = GNUNET_SCHEDULER_add_delayed (rel->retry_timer,
 661                                                   &channel_retransmit_message,
 662                                                   cls);
 663 }
 664
 665
 666 /**
 667  * Send ACK on one or more connections due to buffer space to the client.
 668  *
 669  * Iterates all connections of the tunnel and sends ACKs appropriately.
 670  *
 671  * @param ch Channel which has some free buffer space.
 672  * @param fwd Is this in for FWD traffic? (ACK goes dest->root)
 673  */
 674 static void
 675 channel_send_connections_ack (struct MeshChannel *ch,
 676                               unsigned int buffer,
 677                               int fwd)
 678 {
 679   struct MeshTunnel2 *t = ch->t;
 680   struct MeshConnection *c;
 681   struct MeshFlowControl *fc;
 682   uint32_t allowed;
 683   uint32_t to_allow;
 684   uint32_t allow_per_connection;
 685   unsigned int cs;
 686
 687   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 688               "Channel send connection %s ack on %s:%X\n",
 689               fwd ? "FWD" : "BCK", peer2s (ch->t->peer), ch->gid);
 690
 691   /* Count connections, how many messages are already allowed */
 692   for (cs = 0, allowed = 0, c = t->connection_head; NULL != c; c = c->next)
 693   {
 694     fc = fwd ? &c->fwd_fc : &c->bck_fc;
 695     if (GMC_is_pid_bigger(fc->last_pid_recv, fc->last_ack_sent))
 696     {
 697       GNUNET_break (0);
 698       continue;
 699     }
 700     allowed += fc->last_ack_sent - fc->last_pid_recv;
 701     cs++;
 702   }
 703
 704   /* Make sure there is no overflow */
 705   if (allowed > buffer)
 706   {
 707     GNUNET_break (0);
 708     return;
 709   }
 710
 711   /* Authorize connections to send more data */
 712   to_allow = buffer - allowed;
 713
 714   for (c = t->connection_head; NULL != c && to_allow > 0; c = c->next)
 715   {
 716     allow_per_connection = to_allow/cs;
 717     to_allow -= allow_per_connection;
 718     cs--;
 719     fc = fwd ? &c->fwd_fc : &c->bck_fc;
 720     if (fc->last_ack_sent - fc->last_pid_recv > 64 / 3)
 721     {
 722       continue;
 723     }
 724     connection_send_ack (c, allow_per_connection, fwd);
 725   }
 726
 727   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 728                 "Channel send connection %s ack on %s:%X\n",
 729                 fwd ? "FWD" : "BCK", peer2s (ch->t->peer), ch->gid);
 730   GNUNET_break (to_allow == 0);
 731 }
 732
 733
 734 /**
 735  * Destroy a reliable message after it has been acknowledged, either by
 736  * direct mid ACK or bitfield. Updates the appropriate data structures and
 737  * timers and frees all memory.
 738  *
 739  * @param copy Message that is no longer needed: remote peer got it.
 740  */
 741 static void
 742 rel_message_free (struct MeshReliableMessage *copy)
 743 {
 744   struct MeshChannelReliability *rel;
 745   struct GNUNET_TIME_Relative time;
 746
 747   rel = copy->rel;
 748   time = GNUNET_TIME_absolute_get_duration (copy->timestamp);
 749   rel->expected_delay.rel_value_us *= 7;
 750   rel->expected_delay.rel_value_us += time.rel_value_us;
 751   rel->expected_delay.rel_value_us /= 8;
 752   rel->n_sent--;
 753   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "!!! Freeing %u\n", copy->mid);
 754   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "    n_sent %u\n", rel->n_sent);
 755   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "!!!  took %s\n",
 756               GNUNET_STRINGS_relative_time_to_string (time, GNUNET_NO));
 757   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "!!!  new expected delay %s\n",
 758               GNUNET_STRINGS_relative_time_to_string (rel->expected_delay,
 759                                                       GNUNET_NO));
 760   rel->retry_timer = rel->expected_delay;
 761   GNUNET_CONTAINER_DLL_remove (rel->head_sent, rel->tail_sent, copy);
 762   GNUNET_free (copy);
 763 }
 764
 765
 766
 767 /**
 768  * Channel was ACK'd by remote peer, mark as ready and cancel retransmission.
 769  *
 770  * @param ch Channel to mark as ready.
 771  * @param fwd Was the CREATE message sent fwd?
 772  */
 773 static void
 774 channel_confirm (struct MeshChannel *ch, int fwd)
 775 {
 776   struct MeshChannelReliability *rel;
 777   struct MeshReliableMessage *copy;
 778   struct MeshReliableMessage *next;
 779
 780   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 781               "  channel confirm %s %s:%X\n",
 782               fwd ? "FWD" : "BCK", peer2s (ch->t->peer), ch->gid);
 783   ch->state = MESH_CHANNEL_READY;
 784
 785   rel = fwd ? ch->root_rel : ch->dest_rel;
 786   for (copy = rel->head_sent; NULL != copy; copy = next)
 787   {
 788     struct GNUNET_MessageHeader *msg;
 789
 790     next = copy->next;
 791     msg = (struct GNUNET_MessageHeader *) &copy[1];
 792     if (ntohs (msg->type) == GNUNET_MESSAGE_TYPE_MESH_CHANNEL_CREATE)
 793     {
 794       rel_message_free (copy);
 795       /* TODO return? */
 796     }
 797   }
 798   send_ack (NULL, ch, fwd);
 799 }
 800
 801
 802 /**
 803  * Save a copy to retransmit in case it gets lost.
 804  *
 805  * Initializes all needed callbacks and timers.
 806  *
 807  * @param ch Channel this message goes on.
 808  * @param msg Message to copy.
 809  * @param fwd Is this fwd traffic?
 810  */
 811 static void
 812 channel_save_copy (struct MeshChannel *ch,
 813                    const struct GNUNET_MessageHeader *msg,
 814                    int fwd)
 815 {
 816   struct MeshChannelReliability *rel;
 817   struct MeshReliableMessage *copy;
 818   uint32_t mid;
 819   uint16_t type;
 820   uint16_t size;
 821
 822   rel = fwd ? ch->root_rel : ch->dest_rel;
 823   mid = rel->mid_send;
 824   type = ntohs (msg->type);
 825   size = ntohs (msg->size);
 826
 827   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "!!! SAVE %u\n", mid);
 828   copy = GNUNET_malloc (sizeof (struct MeshReliableMessage) + size);
 829   copy->mid = mid;
 830   copy->timestamp = GNUNET_TIME_absolute_get ();
 831   copy->rel = rel;
 832   copy->type = type;
 833   memcpy (&copy[1], msg, size);
 834   rel->n_sent++;
 835   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " n_sent %u\n", rel->n_sent);
 836   GNUNET_CONTAINER_DLL_insert_tail (rel->head_sent, rel->tail_sent, copy);
 837   if (GNUNET_SCHEDULER_NO_TASK == rel->retry_task)
 838   {
 839     rel->retry_timer =
 840         GNUNET_TIME_relative_multiply (rel->expected_delay,
 841                                         MESH_RETRANSMIT_MARGIN);
 842     rel->retry_task =
 843         GNUNET_SCHEDULER_add_delayed (rel->retry_timer,
 844                                       &channel_retransmit_message,
 845                                       rel);
 846   }
 847 }
 848
 849
 850
 851 /**
 852  * Send a buffered message to the client, for in order delivery or
 853  * as result of client ACK.
 854  *
 855  * @param ch Channel on which to empty the message buffer.
 856  * @param c Client to send to.
 857  * @param rel Reliability structure to corresponding peer.
 858  *            If rel == bck_rel, this is FWD data.
 859  */
 860 static void
 861 send_client_buffered_data (struct MeshChannel *ch,
 862                                    struct MeshClient *c,
 863                                    int fwd)
 864 {
 865   struct MeshReliableMessage *copy;
 866   struct MeshChannelReliability *rel;
 867
 868   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "send_buffered_data\n");
 869   rel = fwd ? ch->dest_rel : ch->root_rel;
 870   if (GNUNET_NO == rel->client_ready)
 871   {
 872     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "client not ready\n");
 873     return;
 874   }
 875
 876   copy = rel->head_recv;
 877   /* We never buffer channel management messages */
 878   if (NULL != copy)
 879   {
 880     if (copy->mid == rel->mid_recv || GNUNET_NO == ch->reliable)
 881     {
 882       struct GNUNET_MESH_Data *msg = (struct GNUNET_MESH_Data *) &copy[1];
 883
 884       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 885                   " have %u! now expecting %u\n",
 886                   copy->mid, rel->mid_recv + 1);
 887       send_client_data (ch, msg, fwd);
 888       rel->n_recv--;
 889       rel->mid_recv++;
 890       GNUNET_CONTAINER_DLL_remove (rel->head_recv, rel->tail_recv, copy);
 891       GNUNET_free (copy);
 892     }
 893     else
 894     {
 895       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 896                   " reliable && don't have %u, next is %u\n",
 897                   rel->mid_recv,
 898                   copy->mid);
 899       return;
 900     }
 901   }
 902   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "send_buffered_data END\n");
 903 }
 904
 905
 906
 907
 908 /**
 909  * Destroy a channel and free all resources.
 910  *
 911  * @param ch Channel to destroy.
 912  */
 913 static void
 914 channel_destroy (struct MeshChannel *ch)
 915 {
 916   struct MeshClient *c;
 917
 918   if (NULL == ch)
 919     return;
 920
 921   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "destroying channel %s:%u\n",
 922               peer2s (ch->t->peer), ch->gid);
 923   channel_debug (ch);
 924
 925   c = ch->root;
 926   if (NULL != c)
 927   {
 928     if (GNUNET_YES != GNUNET_CONTAINER_multihashmap32_remove (c->own_channels,
 929                                                               ch->lid_root, ch))
 930     {
 931       GNUNET_break (0);
 932     }
 933   }
 934
 935   c = ch->dest;
 936   if (NULL != c)
 937   {
 938     if (GNUNET_YES !=
 939         GNUNET_CONTAINER_multihashmap32_remove (c->incoming_channels,
 940                                                 ch->lid_dest, ch))
 941     {
 942       GNUNET_break (0);
 943     }
 944   }
 945
 946   channel_rel_free_all (ch->root_rel);
 947   channel_rel_free_all (ch->dest_rel);
 948
 949   GNUNET_CONTAINER_DLL_remove (ch->t->channel_head, ch->t->channel_tail, ch);
 950   GNUNET_STATISTICS_update (stats, "# channels", -1, GNUNET_NO);
 951
 952   GNUNET_free (ch);
 953 }
 954
 955
 956 /**
 957  * Create a new channel.
 958  *
 959  * @param t Tunnel this channel is in.
 960  * @param owner Client that owns the channel, NULL for foreign channels.
 961  * @param lid_root Local ID for root client.
 962  *
 963  * @return A new initialized channel. NULL on error.
 964  */
 965 static struct MeshChannel *
 966 channel_new (struct MeshTunnel2 *t,
 967              struct MeshClient *owner, MESH_ChannelNumber lid_root)
 968 {
 969   struct MeshChannel *ch;
 970
 971   ch = GNUNET_new (struct MeshChannel);
 972   ch->root = owner;
 973   ch->lid_root = lid_root;
 974   ch->t = t;
 975
 976   GNUNET_STATISTICS_update (stats, "# channels", 1, GNUNET_NO);
 977
 978   if (NULL != owner)
 979   {
 980     while (NULL != channel_get (t, t->next_chid))
 981     {
 982       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Channel %u exists (%p)...\n",
 983                   t->next_chid, channel_get (t, t->next_chid));
 984       t->next_chid = (t->next_chid + 1) & ~GNUNET_MESH_LOCAL_CHANNEL_ID_CLI;
 985     }
 986     ch->gid = t->next_chid;
 987     t->next_chid = (t->next_chid + 1) & ~GNUNET_MESH_LOCAL_CHANNEL_ID_CLI;
 988
 989     if (GNUNET_OK !=
 990         GNUNET_CONTAINER_multihashmap32_put (owner->own_channels, lid_root, ch,
 991                                              GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
 992     {
 993       GNUNET_break (0);
 994       channel_destroy (ch);
 995       GNUNET_SERVER_receive_done (owner->handle, GNUNET_SYSERR);
 996       return NULL;
 997     }
 998   }
 999   GNUNET_CONTAINER_DLL_insert (t->channel_head, t->channel_tail, ch);
1000
1001   return ch;
1002 }
1003
1004
1005 /**
1006  * Set options in a channel, extracted from a bit flag field
1007  *
1008  * @param ch Channel to set options to.
1009  * @param options Bit array in host byte order.
1010  */
1011 static void
1012 channel_set_options (struct MeshChannel *ch, uint32_t options)
1013 {
1014   ch->nobuffer = (options & GNUNET_MESH_OPTION_NOBUFFER) != 0 ?
1015                  GNUNET_YES : GNUNET_NO;
1016   ch->reliable = (options & GNUNET_MESH_OPTION_RELIABLE) != 0 ?
1017                  GNUNET_YES : GNUNET_NO;
1018 }
1019
1020
1021 /**
1022  * Iterator for deleting each channel whose client endpoint disconnected.
1023  *
1024  * @param cls Closure (client that has disconnected).
1025  * @param key The local channel id (used to access the hashmap).
1026  * @param value The value stored at the key (channel to destroy).
1027  *
1028  * @return GNUNET_OK, keep iterating.
1029  */
1030 static int
1031 channel_destroy_iterator (void *cls,
1032                           uint32_t key,
1033                           void *value)
1034 {
1035   struct MeshChannel *ch = value;
1036   struct MeshClient *c = cls;
1037   struct MeshTunnel2 *t;
1038
1039   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1040               " Channel %X (%X / %X) destroy, due to client %u shutdown.\n",
1041               ch->gid, ch->lid_root, ch->lid_dest, c->id);
1042   channel_debug (ch);
1043
1044   if (c == ch->dest)
1045   {
1046     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " Client %u is destination.\n", c->id);
1047   }
1048   if (c == ch->root)
1049   {
1050     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " Client %u is owner.\n", c->id);
1051   }
1052
1053   t = ch->t;
1054   channel_send_destroy (ch);
1055   channel_destroy (ch);
1056   tunnel_destroy_if_empty (t);
1057
1058   return GNUNET_OK;
1059 }
1060
1061
1062 /**
1063  * Sends an already built message on a channel, properly registering
1064  * all used resources and encrypting the message with the tunnel's key.
1065  *
1066  * @param message Message to send. Function makes a copy of it.
1067  * @param ch Channel on which this message is transmitted.
1068  * @param fwd Is this a fwd message?
1069  */
1070 static void
1071 send (const struct GNUNET_MessageHeader *message,
1072       struct MeshChannel *ch, int fwd)
1073 {
1074   struct GNUNET_MESH_Encrypted *msg;
1075   size_t size = ntohs (message->size);
1076   char *cbuf[sizeof (struct GNUNET_MESH_Encrypted) + size];
1077   uint16_t type;
1078   uint64_t iv;
1079
1080   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Send on Channel %s:%X %s\n",
1081               peer2s (ch->t->peer), ch->gid, fwd ? "FWD" : "BCK");
1082   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  %s\n",
1083               GNUNET_MESH_DEBUG_M2S (ntohs (message->type)));
1084
1085   if (channel_is_terminal (ch, fwd) || ch->t->peer->id == myid)
1086   {
1087     handle_decrypted (ch->t, message, fwd);
1088     return;
1089   }
1090
1091   type = fwd ? GNUNET_MESSAGE_TYPE_MESH_FWD : GNUNET_MESSAGE_TYPE_MESH_BCK;
1092   iv = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_NONCE, UINT64_MAX);
1093
1094   msg = (struct GNUNET_MESH_Encrypted *) cbuf;
1095   msg->header.type = htons (type);
1096   msg->header.size = htons (sizeof (struct GNUNET_MESH_Encrypted) + size);
1097   msg->iv = GNUNET_htonll (iv);
1098   tunnel_encrypt (ch->t, &msg[1], message, size, iv, fwd);
1099   send_prebuilt_message_tunnel (msg, ch->t, ch, fwd);
1100 }
1101
1102
1103
1104 /**
1105  * Notify the destination client that a new incoming channel was created.
1106  *
1107  * @param ch Channel that was created.
1108  */
1109 void
1110 GMCH_send_channel_create (struct MeshChannel *ch)
1111 {
1112   struct GNUNET_MESH_ChannelMessage msg;
1113   struct MeshTunnel2 *t = ch->t;
1114   uint32_t opt;
1115
1116   if (NULL == ch->dest)
1117     return;
1118
1119   opt = 0;
1120   opt |= GNUNET_YES == ch->reliable ? GNUNET_MESH_OPTION_RELIABLE : 0;
1121   opt |= GNUNET_YES == ch->nobuffer ? GNUNET_MESH_OPTION_NOBUFFER : 0;
1122   GML_send_channel_create (ch->dest, ch->lid_dest, ch->port, opt,
1123                            GNUNET_PEER_resolve2 (t->peer->id));
1124
1125 }
1126
1127 /**
1128  * Notify a client that the channel is no longer valid.
1129  *
1130  * @param ch Channel that is destroyed.
1131  * @param fwd Forward notification (owner->dest)?
1132  */
1133 void
1134 GMCH_send_channel_destroy (struct MeshChannel *ch, int fwd)
1135 {
1136   struct GNUNET_MeshClient *c = fwd ? ch->dest : ch->root;
1137   uint32_t id = fwd ? ch->lid_dest : ch->lid_root;
1138
1139   if (NULL == c)
1140     return;
1141
1142   GML_send_channel_destroy (c, id);
1143 }
1144
1145
1146 /**
1147  * Send data on a channel.
1148  *
1149  * If the destination is local, send it to client, otherwise encrypt and
1150  * send to next hop.
1151  *
1152  * @param ch Channel
1153  * @param msg Message.
1154  * @param fwd Is this a fwd (root->dest) message?
1155  */
1156 void
1157 GMCH_send_data (struct MeshChannel *ch,
1158                 const struct GNUNET_MESH_Data *msg,
1159                 int fwd)
1160 {
1161 }
1162
1163
1164 /**
1165  * Send an end-to-end ACK message for the most recent in-sequence payload.
1166  *
1167  * If channel is not reliable, do nothing.
1168  *
1169  * @param ch Channel this is about.
1170  * @param fwd Is for FWD traffic? (ACK dest->owner)
1171  */
1172 static void
1173 GMCH_send_ack (struct MeshChannel *ch, int fwd)
1174 {
1175   struct GNUNET_MESH_DataACK msg;
1176   struct MeshChannelReliability *rel;
1177   struct MeshReliableMessage *copy;
1178   unsigned int delta;
1179   uint64_t mask;
1180   uint16_t type;
1181
1182   if (GNUNET_NO == ch->reliable)
1183   {
1184     return;
1185   }
1186   rel = fwd ? ch->dest_rel : ch->root_rel;
1187   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1188               "send_data_ack for %u\n",
1189               rel->mid_recv - 1);
1190
1191   type = GNUNET_MESSAGE_TYPE_MESH_DATA_ACK;
1192   msg.header.type = htons (type);
1193   msg.header.size = htons (sizeof (msg));
1194   msg.chid = htonl (ch->gid);
1195   msg.mid = htonl (rel->mid_recv - 1);
1196   msg.futures = 0;
1197   for (copy = rel->head_recv; NULL != copy; copy = copy->next)
1198   {
1199     if (copy->type != type)
1200       continue;
1201     delta = copy->mid - rel->mid_recv;
1202     if (63 < delta)
1203       break;
1204     mask = 0x1LL << delta;
1205     msg.futures |= mask;
1206     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1207                 " setting bit for %u (delta %u) (%llX) -> %llX\n",
1208                 copy->mid, delta, mask, msg.futures);
1209   }
1210   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, " final futures %llX\n", msg.futures);
1211
1212   send_prebuilt_message_channel (&msg.header, ch, fwd);
1213   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "send_data_ack END\n");
1214 }
1215
1216
1217 /**
1218  * Log channel info.
1219  *
1220  * @param ch Channel.
1221  */
1222 void
1223 GMCH_debug (struct MeshChannel *ch)
1224 {
1225   if (NULL == ch)
1226   {
1227     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "*** DEBUG NULL CHANNEL ***\n");
1228     return;
1229   }
1230   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Channel %s:%X (%p)\n",
1231               peer2s (ch->t->peer), ch->gid, ch);
1232   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  root %p/%p\n",
1233               ch->root, ch->root_rel);
1234   if (NULL != ch->root)
1235   {
1236     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  cli %u\n", ch->root->id);
1237     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  ready %s\n",
1238                 ch->root_rel->client_ready ? "YES" : "NO");
1239     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  id %X\n", ch->lid_root);
1240   }
1241   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  dest %p/%p\n",
1242               ch->dest, ch->dest_rel);
1243   if (NULL != ch->dest)
1244   {
1245     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  cli %u\n", ch->dest->id);
1246     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  ready %s\n",
1247                 ch->dest_rel->client_ready ? "YES" : "NO");
1248     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "  id %X\n", ch->lid_dest);
1249   }
1250 }
1251
1252