src/openvpn/reliable.c

   1 /*
   2  *  OpenVPN -- An application to securely tunnel IP networks
   3  *             over a single UDP port, with support for SSL/TLS-based
   4  *             session authentication and key exchange,
   5  *             packet encryption, packet authentication, and
   6  *             packet compression.
   7  *
   8  *  Copyright (C) 2002-2005 OpenVPN Solutions LLC <info@openvpn.net>
   9  *
  10  *  This program is free software; you can redistribute it and/or modify
  11  *  it under the terms of the GNU General Public License version 2
  12  *  as published by the Free Software Foundation.
  13  *
  14  *  This program is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  *  GNU General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU General Public License
  20  *  along with this program (see the file COPYING included with this
  21  *  distribution); if not, write to the Free Software Foundation, Inc.,
  22  *  59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  23  */
  24
  25 /*
  26  * These routines implement a reliability layer on top of UDP,
  27  * so that SSL/TLS can be run over UDP.
  28  */
  29
  30 #ifdef WIN32
  31 #include "config-win32.h"
  32 #else
  33 #include "config.h"
  34 #endif
  35
  36 #if defined(USE_CRYPTO) && defined(USE_SSL)
  37
  38 #include "syshead.h"
  39
  40 #include "buffer.h"
  41 #include "error.h"
  42 #include "common.h"
  43 #include "reliable.h"
  44
  45 #include "memdbg.h"
  46
  47 /* check if a particular packet_id is present in ack */
  48 static inline bool
  49 reliable_ack_packet_id_present (struct reliable_ack *ack, packet_id_type pid)
  50 {
  51   int i;
  52   for (i = 0; i < ack->len; ++i)
  53     if (ack->packet_id[i] == pid)
  54       return true;
  55   return false;
  56 }
  57
  58 /* get a packet_id from buf */
  59 bool
  60 reliable_ack_read_packet_id (struct buffer *buf, packet_id_type *pid)
  61 {
  62   packet_id_type net_pid;
  63
  64   if (buf_read (buf, &net_pid, sizeof (net_pid)))
  65     {
  66       *pid = ntohpid (net_pid);
  67       dmsg (D_REL_DEBUG, "ACK read ID " packet_id_format " (buf->len=%d)",
  68            (packet_id_print_type)*pid, buf->len);
  69       return true;
  70     }
  71
  72   dmsg (D_REL_LOW, "ACK read ID FAILED (buf->len=%d)", buf->len);
  73   return false;
  74 }
  75
  76 /* acknowledge a packet_id by adding it to a struct reliable_ack */
  77 bool
  78 reliable_ack_acknowledge_packet_id (struct reliable_ack *ack, packet_id_type pid)
  79 {
  80   if (!reliable_ack_packet_id_present (ack, pid) && ack->len < RELIABLE_ACK_SIZE)
  81     {
  82       ack->packet_id[ack->len++] = pid;
  83       dmsg (D_REL_DEBUG, "ACK acknowledge ID " packet_id_format " (ack->len=%d)",
  84            (packet_id_print_type)pid, ack->len);
  85       return true;
  86     }
  87
  88   dmsg (D_REL_LOW, "ACK acknowledge ID " packet_id_format " FAILED (ack->len=%d)",
  89        (packet_id_print_type)pid, ack->len);
  90   return false;
  91 }
  92
  93 /* read a packet ID acknowledgement record from buf into ack */
  94 bool
  95 reliable_ack_read (struct reliable_ack * ack,
  96                    struct buffer * buf, const struct session_id * sid)
  97 {
  98   struct gc_arena gc = gc_new ();
  99   int i;
 100   uint8_t count;
 101   packet_id_type net_pid;
 102   packet_id_type pid;
 103   struct session_id session_id_remote;
 104
 105   if (!buf_read (buf, &count, sizeof (count)))
 106     goto error;
 107   for (i = 0; i < count; ++i)
 108     {
 109       if (!buf_read (buf, &net_pid, sizeof (net_pid)))
 110         goto error;
 111       if (ack->len >= RELIABLE_ACK_SIZE)
 112         goto error;
 113       pid = ntohpid (net_pid);
 114       ack->packet_id[ack->len++] = pid;
 115     }
 116   if (count)
 117     {
 118       if (!session_id_read (&session_id_remote, buf))
 119         goto error;
 120       if (!session_id_defined (&session_id_remote) ||
 121           !session_id_equal (&session_id_remote, sid))
 122         {
 123           dmsg (D_REL_LOW,
 124                "ACK read BAD SESSION-ID FROM REMOTE, local=%s, remote=%s",
 125                session_id_print (sid, &gc), session_id_print (&session_id_remote, &gc));
 126           goto error;
 127         }
 128     }
 129   gc_free (&gc);
 130   return true;
 131
 132 error:
 133   gc_free (&gc);
 134   return false;
 135 }
 136
 137 #define ACK_SIZE(n) (sizeof (uint8_t) + ((n) ? SID_SIZE : 0) + sizeof (packet_id_type) * (n))
 138
 139 /* write a packet ID acknowledgement record to buf, */
 140 /* removing all acknowledged entries from ack */
 141 bool
 142 reliable_ack_write (struct reliable_ack * ack,
 143                     struct buffer * buf,
 144                     const struct session_id * sid, int max, bool prepend)
 145 {
 146   int i, j;
 147   uint8_t n;
 148   struct buffer sub;
 149
 150   n = ack->len;
 151   if (n > max)
 152     n = max;
 153   sub = buf_sub (buf, ACK_SIZE(n), prepend);
 154   if (!BDEF (&sub))
 155     goto error;
 156   ASSERT (buf_write (&sub, &n, sizeof (n)));
 157   for (i = 0; i < n; ++i)
 158     {
 159       packet_id_type pid = ack->packet_id[i];
 160       packet_id_type net_pid = htonpid (pid);
 161       ASSERT (buf_write (&sub, &net_pid, sizeof (net_pid)));
 162       dmsg (D_REL_DEBUG, "ACK write ID " packet_id_format " (ack->len=%d, n=%d)", (packet_id_print_type)pid, ack->len, n);
 163     }
 164   if (n)
 165     {
 166       ASSERT (session_id_defined (sid));
 167       ASSERT (session_id_write (sid, &sub));
 168       for (i = 0, j = n; j < ack->len;)
 169         ack->packet_id[i++] = ack->packet_id[j++];
 170       ack->len = i;
 171     }
 172
 173   return true;
 174
 175 error:
 176   return false;
 177 }
 178
 179 /* add to extra_frame the maximum number of bytes we will need for reliable_ack_write */
 180 void
 181 reliable_ack_adjust_frame_parameters (struct frame* frame, int max)
 182 {
 183   frame_add_to_extra_frame (frame, ACK_SIZE (max));
 184 }
 185
 186 /* print a reliable ACK record coming off the wire */
 187 const char *
 188 reliable_ack_print (struct buffer *buf, bool verbose, struct gc_arena *gc)
 189 {
 190   int i;
 191   uint8_t n_ack;
 192   struct session_id sid_ack;
 193   packet_id_type pid;
 194   struct buffer out = alloc_buf_gc (256, gc);
 195
 196   buf_printf (&out, "[");
 197   if (!buf_read (buf, &n_ack, sizeof (n_ack)))
 198     goto done;
 199   for (i = 0; i < n_ack; ++i)
 200     {
 201       if (!buf_read (buf, &pid, sizeof (pid)))
 202         goto done;
 203       pid = ntohpid (pid);
 204       buf_printf (&out, " " packet_id_format, (packet_id_print_type)pid);
 205     }
 206   if (n_ack)
 207     {
 208       if (!session_id_read (&sid_ack, buf))
 209         goto done;
 210       if (verbose)
 211         buf_printf (&out, " sid=%s", session_id_print (&sid_ack, gc));
 212     }
 213
 214  done:
 215   buf_printf (&out, " ]");
 216   return BSTR (&out);
 217 }
 218
 219 /*
 220  * struct reliable member functions.
 221  */
 222
 223 void
 224 reliable_init (struct reliable *rel, int buf_size, int offset, int array_size)
 225 {
 226   int i;
 227
 228   CLEAR (*rel);
 229   ASSERT (array_size > 0 && array_size <= RELIABLE_CAPACITY);
 230   rel->size = array_size;
 231   rel->offset = offset;
 232   for (i = 0; i < rel->size; ++i)
 233     {
 234       struct reliable_entry *e = &rel->array[i];
 235       e->buf = alloc_buf (buf_size);
 236       ASSERT (buf_init (&e->buf, offset));
 237     }
 238 }
 239
 240 void
 241 reliable_free (struct reliable *rel)
 242 {
 243   int i;
 244   for (i = 0; i < rel->size; ++i)
 245     {
 246       struct reliable_entry *e = &rel->array[i];
 247       free_buf (&e->buf);
 248     }
 249 }
 250
 251 /* no active buffers? */
 252 bool
 253 reliable_empty (const struct reliable *rel)
 254 {
 255   int i;
 256   for (i = 0; i < rel->size; ++i)
 257     {
 258       const struct reliable_entry *e = &rel->array[i];
 259       if (e->active)
 260         return false;
 261     }
 262   return true;
 263 }
 264
 265 /* del acknowledged items from send buf */
 266 void
 267 reliable_send_purge (struct reliable *rel, struct reliable_ack *ack)
 268 {
 269   int i, j;
 270   for (i = 0; i < ack->len; ++i)
 271     {
 272       packet_id_type pid = ack->packet_id[i];
 273       for (j = 0; j < rel->size; ++j)
 274         {
 275           struct reliable_entry *e = &rel->array[j];
 276           if (e->active && e->packet_id == pid)
 277             {
 278               dmsg (D_REL_DEBUG,
 279                    "ACK received for pid " packet_id_format ", deleting from send buffer",
 280                    (packet_id_print_type)pid);
 281 #if 0
 282               /* DEBUGGING -- how close were we timing out on ACK failure and resending? */
 283               {
 284                 if (e->next_try)
 285                   {
 286                     const interval_t wake = e->next_try - now;
 287                     msg (M_INFO, "ACK " packet_id_format ", wake=%d", pid, wake);
 288                   }
 289               }
 290 #endif
 291               e->active = false;
 292               break;
 293             }
 294         }
 295     }
 296 }
 297
 298 /* print the current sequence of active packet IDs */
 299 static const char *
 300 reliable_print_ids (const struct reliable *rel, struct gc_arena *gc)
 301 {
 302   struct buffer out = alloc_buf_gc (256, gc);
 303   int i;
 304
 305   buf_printf (&out, "[" packet_id_format "]", (packet_id_print_type)rel->packet_id);
 306   for (i = 0; i < rel->size; ++i)
 307     {
 308       const struct reliable_entry *e = &rel->array[i];
 309       if (e->active)
 310         buf_printf (&out, " " packet_id_format, (packet_id_print_type)e->packet_id);
 311     }
 312   return BSTR (&out);
 313 }
 314
 315 /* true if at least one free buffer available */
 316 bool
 317 reliable_can_get (const struct reliable *rel)
 318 {
 319   struct gc_arena gc = gc_new ();
 320   int i;
 321   for (i = 0; i < rel->size; ++i)
 322     {
 323       const struct reliable_entry *e = &rel->array[i];
 324       if (!e->active)
 325         return true;
 326     }
 327   dmsg (D_REL_LOW, "ACK no free receive buffer available: %s", reliable_print_ids (rel, &gc));
 328   gc_free (&gc);
 329   return false;
 330 }
 331
 332 /* make sure that incoming packet ID isn't a replay */
 333 bool
 334 reliable_not_replay (const struct reliable *rel, packet_id_type id)
 335 {
 336   struct gc_arena gc = gc_new ();
 337   int i;
 338   if (id < rel->packet_id)
 339     goto bad;
 340   for (i = 0; i < rel->size; ++i)
 341     {
 342       const struct reliable_entry *e = &rel->array[i];
 343       if (e->active && e->packet_id == id)
 344         goto bad;
 345     }
 346   gc_free (&gc);
 347   return true;
 348
 349  bad:
 350   dmsg (D_REL_DEBUG, "ACK " packet_id_format " is a replay: %s", (packet_id_print_type)id, reliable_print_ids (rel, &gc));
 351   gc_free (&gc);
 352   return false;
 353 }
 354
 355 /* make sure that incoming packet ID won't deadlock the receive buffer */
 356 bool
 357 reliable_wont_break_sequentiality (const struct reliable *rel, packet_id_type id)
 358 {
 359   struct gc_arena gc = gc_new ();
 360   int ret;
 361
 362   if ((int)id < (int)rel->packet_id + rel->size)
 363     {
 364       ret = true;
 365     }
 366   else
 367     {
 368       dmsg (D_REL_LOW, "ACK " packet_id_format " breaks sequentiality: %s",
 369            (packet_id_print_type)id, reliable_print_ids (rel, &gc));
 370       ret = false;
 371     }
 372   gc_free (&gc);
 373   return ret;
 374 }
 375
 376 /* grab a free buffer */
 377 struct buffer *
 378 reliable_get_buf (struct reliable *rel)
 379 {
 380   int i;
 381   for (i = 0; i < rel->size; ++i)
 382     {
 383       struct reliable_entry *e = &rel->array[i];
 384       if (!e->active)
 385         {
 386           ASSERT (buf_init (&e->buf, rel->offset));
 387           return &e->buf;
 388         }
 389     }
 390   return NULL;
 391 }
 392
 393 /* grab a free buffer, fail if buffer clogged by unacknowledged low packet IDs */
 394 struct buffer *
 395 reliable_get_buf_output_sequenced (struct reliable *rel)
 396 {
 397   struct gc_arena gc = gc_new ();
 398   int i;
 399   packet_id_type min_id = 0;
 400   bool min_id_defined = false;
 401   struct buffer *ret = NULL;
 402
 403   /* find minimum active packet_id */
 404   for (i = 0; i < rel->size; ++i)
 405     {
 406       const struct reliable_entry *e = &rel->array[i];
 407       if (e->active)
 408         {
 409           if (!min_id_defined || e->packet_id < min_id)
 410             {
 411               min_id_defined = true;
 412               min_id = e->packet_id;
 413             }
 414         }
 415     }
 416
 417   if (!min_id_defined || (int)(rel->packet_id - min_id) < rel->size)
 418     {
 419       ret = reliable_get_buf (rel);
 420     }
 421   else
 422     {
 423       dmsg (D_REL_LOW, "ACK output sequence broken: %s", reliable_print_ids (rel, &gc));
 424     }
 425   gc_free (&gc);
 426   return ret;
 427 }
 428
 429 /* get active buffer for next sequentially increasing key ID */
 430 struct buffer *
 431 reliable_get_buf_sequenced (struct reliable *rel)
 432 {
 433   int i;
 434   for (i = 0; i < rel->size; ++i)
 435     {
 436       struct reliable_entry *e = &rel->array[i];
 437       if (e->active && e->packet_id == rel->packet_id)
 438         {
 439           return &e->buf;
 440         }
 441     }
 442   return NULL;
 443 }
 444
 445 /* return true if reliable_send would return a non-NULL result */
 446 bool
 447 reliable_can_send (const struct reliable *rel)
 448 {
 449   struct gc_arena gc = gc_new ();
 450   int i;
 451   int n_active = 0, n_current = 0;
 452   for (i = 0; i < rel->size; ++i)
 453     {
 454       const struct reliable_entry *e = &rel->array[i];
 455       if (e->active)
 456         {
 457           ++n_active;
 458           if (now >= e->next_try)
 459             ++n_current;
 460         }
 461     }
 462   dmsg (D_REL_DEBUG, "ACK reliable_can_send active=%d current=%d : %s",
 463        n_active,
 464        n_current,
 465        reliable_print_ids (rel, &gc));
 466
 467   gc_free (&gc);
 468   return n_current > 0;
 469 }
 470
 471 /* return a unique point-in-time to trigger retry */
 472 static time_t
 473 reliable_unique_retry (struct reliable *rel, time_t retry)
 474 {
 475   int i;
 476   while (true)
 477     {
 478       for (i = 0; i < rel->size; ++i)
 479         {
 480           struct reliable_entry *e = &rel->array[i];
 481           if (e->active && e->next_try == retry)
 482             goto again;
 483         }
 484       break;
 485     again:
 486       ++retry;
 487     }
 488   return retry;
 489 }
 490
 491 /* return next buffer to send to remote */
 492 struct buffer *
 493 reliable_send (struct reliable *rel, int *opcode)
 494 {
 495   int i;
 496   struct reliable_entry *best = NULL;
 497   const time_t local_now = now;
 498
 499   for (i = 0; i < rel->size; ++i)
 500     {
 501       struct reliable_entry *e = &rel->array[i];
 502       if (e->active && local_now >= e->next_try)
 503         {
 504           if (!best || e->packet_id < best->packet_id)
 505             best = e;
 506         }
 507     }
 508   if (best)
 509     {
 510 #ifdef EXPONENTIAL_BACKOFF
 511       /* exponential backoff */
 512       best->next_try = reliable_unique_retry (rel, local_now + best->timeout);
 513       best->timeout *= 2;
 514 #else
 515       /* constant timeout, no backoff */
 516       best->next_try = local_now + best->timeout;
 517 #endif
 518       *opcode = best->opcode;
 519       dmsg (D_REL_DEBUG, "ACK reliable_send ID " packet_id_format " (size=%d to=%d)",
 520            (packet_id_print_type)best->packet_id, best->buf.len,
 521            (int)(best->next_try - local_now));
 522       return &best->buf;
 523     }
 524   return NULL;
 525 }
 526
 527 /* schedule all pending packets for immediate retransmit */
 528 void
 529 reliable_schedule_now (struct reliable *rel)
 530 {
 531   int i;
 532   dmsg (D_REL_DEBUG, "ACK reliable_schedule_now");
 533   for (i = 0; i < rel->size; ++i)
 534     {
 535       struct reliable_entry *e = &rel->array[i];
 536       if (e->active)
 537         {
 538           e->next_try = now;
 539           e->timeout = rel->initial_timeout;
 540         }
 541     }
 542 }
 543
 544 /* in how many seconds should we wake up to check for timeout */
 545 /* if we return BIG_TIMEOUT, nothing to wait for */
 546 interval_t
 547 reliable_send_timeout (const struct reliable *rel)
 548 {
 549   struct gc_arena gc = gc_new ();
 550   interval_t ret = BIG_TIMEOUT;
 551   int i;
 552   const time_t local_now = now;
 553
 554   for (i = 0; i < rel->size; ++i)
 555     {
 556       const struct reliable_entry *e = &rel->array[i];
 557       if (e->active)
 558         {
 559           if (e->next_try <= local_now)
 560             {
 561               ret = 0;
 562               break;
 563             }
 564           else
 565             {
 566               ret = min_int (ret, e->next_try - local_now);
 567             }
 568         }
 569     }
 570
 571   dmsg (D_REL_DEBUG, "ACK reliable_send_timeout %d %s",
 572        (int) ret,
 573        reliable_print_ids (rel, &gc));
 574
 575   gc_free (&gc);
 576   return ret;
 577 }
 578
 579 /*
 580  * Enable an incoming buffer previously returned by a get function as active.
 581  */
 582
 583 void
 584 reliable_mark_active_incoming (struct reliable *rel, struct buffer *buf,
 585                                packet_id_type pid, int opcode)
 586 {
 587   int i;
 588   for (i = 0; i < rel->size; ++i)
 589     {
 590       struct reliable_entry *e = &rel->array[i];
 591       if (buf == &e->buf)
 592         {
 593           e->active = true;
 594
 595           /* packets may not arrive in sequential order */
 596           e->packet_id = pid;
 597
 598           /* check for replay */
 599           ASSERT (pid >= rel->packet_id);
 600
 601           e->opcode = opcode;
 602           e->next_try = 0;
 603           e->timeout = 0;
 604           dmsg (D_REL_DEBUG, "ACK mark active incoming ID " packet_id_format, (packet_id_print_type)e->packet_id);
 605           return;
 606         }
 607     }
 608   ASSERT (0);                   /* buf not found in rel */
 609 }
 610
 611 /*
 612  * Enable an outgoing buffer previously returned by a get function as active.
 613  */
 614
 615 void
 616 reliable_mark_active_outgoing (struct reliable *rel, struct buffer *buf, int opcode)
 617 {
 618   int i;
 619   for (i = 0; i < rel->size; ++i)
 620     {
 621       struct reliable_entry *e = &rel->array[i];
 622       if (buf == &e->buf)
 623         {
 624           /* Write mode, increment packet_id (i.e. sequence number)
 625              linearly and prepend id to packet */
 626           packet_id_type net_pid;
 627           e->packet_id = rel->packet_id++;
 628           net_pid = htonpid (e->packet_id);
 629           ASSERT (buf_write_prepend (buf, &net_pid, sizeof (net_pid)));
 630           e->active = true;
 631           e->opcode = opcode;
 632           e->next_try = 0;
 633           e->timeout = rel->initial_timeout;
 634           dmsg (D_REL_DEBUG, "ACK mark active outgoing ID " packet_id_format, (packet_id_print_type)e->packet_id);
 635           return;
 636         }
 637     }
 638   ASSERT (0);                   /* buf not found in rel */
 639 }
 640
 641 /* delete a buffer previously activated by reliable_mark_active() */
 642 void
 643 reliable_mark_deleted (struct reliable *rel, struct buffer *buf, bool inc_pid)
 644 {
 645   int i;
 646   for (i = 0; i < rel->size; ++i)
 647     {
 648       struct reliable_entry *e = &rel->array[i];
 649       if (buf == &e->buf)
 650         {
 651           e->active = false;
 652           if (inc_pid)
 653             rel->packet_id = e->packet_id + 1;
 654           return;
 655         }
 656     }
 657   ASSERT (0);
 658 }
 659
 660 #if 0
 661
 662 void
 663 reliable_ack_debug_print (const struct reliable_ack *ack, char *desc)
 664 {
 665   int i;
 666
 667   printf ("********* struct reliable_ack %s\n", desc);
 668   for (i = 0; i < ack->len; ++i)
 669     {
 670       printf ("  %d: " packet_id_format "\n", i, (packet_id_print_type) ack->packet_id[i]);
 671     }
 672 }
 673
 674 void
 675 reliable_debug_print (const struct reliable *rel, char *desc)
 676 {
 677   int i;
 678   update_time ();
 679
 680   printf ("********* struct reliable %s\n", desc);
 681   printf ("  initial_timeout=%d\n", (int)rel->initial_timeout);
 682   printf ("  packet_id=" packet_id_format "\n", rel->packet_id);
 683   printf ("  now=" time_format "\n", now);
 684   for (i = 0; i < rel->size; ++i)
 685     {
 686       const struct reliable_entry *e = &rel->array[i];
 687       if (e->active)
 688         {
 689           printf ("  %d: packet_id=" packet_id_format " len=%d", i, e->packet_id, e->buf.len);
 690           printf (" next_try=" time_format, e->next_try);
 691           printf ("\n");
 692         }
 693     }
 694 }
 695
 696 #endif
 697
 698 #else
 699 static void dummy(void) {}
 700 #endif /* USE_CRYPTO && USE_SSL*/