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