diff options
author | Alberto Gonzalez Iniesta <agi@inittab.org> | 2012-11-05 16:28:09 +0100 |
---|---|---|
committer | Alberto Gonzalez Iniesta <agi@inittab.org> | 2012-11-05 16:28:09 +0100 |
commit | 8dd0350e1607aa30f7a043c8d5ec7a7eeb874115 (patch) | |
tree | 566d0620eb693320cb121dfd93a5675fa704a30b /reliable.c | |
parent | 349cfa7acb95abe865209a28e417ec74b56f9bba (diff) |
Imported Upstream version 2.3_rc1
Diffstat (limited to 'reliable.c')
-rw-r--r-- | reliable.c | 751 |
1 files changed, 0 insertions, 751 deletions
diff --git a/reliable.c b/reliable.c deleted file mode 100644 index 1f238cc..0000000 --- a/reliable.c +++ /dev/null @@ -1,751 +0,0 @@ -/* - * OpenVPN -- An application to securely tunnel IP networks - * over a single UDP port, with support for SSL/TLS-based - * session authentication and key exchange, - * packet encryption, packet authentication, and - * packet compression. - * - * Copyright (C) 2002-2010 OpenVPN Technologies, Inc. <sales@openvpn.net> - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License version 2 - * as published by the Free Software Foundation. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program (see the file COPYING included with this - * distribution); if not, write to the Free Software Foundation, Inc., - * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA - */ - -/* - * These routines implement a reliability layer on top of UDP, - * so that SSL/TLS can be run over UDP. - */ - -#include "syshead.h" - -#if defined(USE_CRYPTO) && defined(USE_SSL) - -#include "buffer.h" -#include "error.h" -#include "common.h" -#include "reliable.h" - -#include "memdbg.h" - -/* - * verify that test - base < extent while allowing for base or test wraparound - */ -static inline bool -reliable_pid_in_range1 (const packet_id_type test, - const packet_id_type base, - const unsigned int extent) -{ - if (test >= base) - { - if (test - base < extent) - return true; - } - else - { - if ((test+0x80000000u) - (base+0x80000000u) < extent) - return true; - } - - return false; -} - -/* - * verify that test < base + extent while allowing for base or test wraparound - */ -static inline bool -reliable_pid_in_range2 (const packet_id_type test, - const packet_id_type base, - const unsigned int extent) -{ - if (base + extent >= base) - { - if (test < base + extent) - return true; - } - else - { - if ((test+0x80000000u) < (base+0x80000000u) + extent) - return true; - } - - return false; -} - -/* - * verify that p1 < p2 while allowing for p1 or p2 wraparound - */ -static inline bool -reliable_pid_min (const packet_id_type p1, - const packet_id_type p2) -{ - return !reliable_pid_in_range1 (p1, p2, 0x80000000u); -} - -/* check if a particular packet_id is present in ack */ -static inline bool -reliable_ack_packet_id_present (struct reliable_ack *ack, packet_id_type pid) -{ - int i; - for (i = 0; i < ack->len; ++i) - if (ack->packet_id[i] == pid) - return true; - return false; -} - -/* get a packet_id from buf */ -bool -reliable_ack_read_packet_id (struct buffer *buf, packet_id_type *pid) -{ - packet_id_type net_pid; - - if (buf_read (buf, &net_pid, sizeof (net_pid))) - { - *pid = ntohpid (net_pid); - dmsg (D_REL_DEBUG, "ACK read ID " packet_id_format " (buf->len=%d)", - (packet_id_print_type)*pid, buf->len); - return true; - } - - dmsg (D_REL_LOW, "ACK read ID FAILED (buf->len=%d)", buf->len); - return false; -} - -/* acknowledge a packet_id by adding it to a struct reliable_ack */ -bool -reliable_ack_acknowledge_packet_id (struct reliable_ack *ack, packet_id_type pid) -{ - if (!reliable_ack_packet_id_present (ack, pid) && ack->len < RELIABLE_ACK_SIZE) - { - ack->packet_id[ack->len++] = pid; - dmsg (D_REL_DEBUG, "ACK acknowledge ID " packet_id_format " (ack->len=%d)", - (packet_id_print_type)pid, ack->len); - return true; - } - - dmsg (D_REL_LOW, "ACK acknowledge ID " packet_id_format " FAILED (ack->len=%d)", - (packet_id_print_type)pid, ack->len); - return false; -} - -/* read a packet ID acknowledgement record from buf into ack */ -bool -reliable_ack_read (struct reliable_ack * ack, - struct buffer * buf, const struct session_id * sid) -{ - struct gc_arena gc = gc_new (); - int i; - uint8_t count; - packet_id_type net_pid; - packet_id_type pid; - struct session_id session_id_remote; - - if (!buf_read (buf, &count, sizeof (count))) - goto error; - for (i = 0; i < count; ++i) - { - if (!buf_read (buf, &net_pid, sizeof (net_pid))) - goto error; - if (ack->len >= RELIABLE_ACK_SIZE) - goto error; - pid = ntohpid (net_pid); - ack->packet_id[ack->len++] = pid; - } - if (count) - { - if (!session_id_read (&session_id_remote, buf)) - goto error; - if (!session_id_defined (&session_id_remote) || - !session_id_equal (&session_id_remote, sid)) - { - dmsg (D_REL_LOW, - "ACK read BAD SESSION-ID FROM REMOTE, local=%s, remote=%s", - session_id_print (sid, &gc), session_id_print (&session_id_remote, &gc)); - goto error; - } - } - gc_free (&gc); - return true; - -error: - gc_free (&gc); - return false; -} - -#define ACK_SIZE(n) (sizeof (uint8_t) + ((n) ? SID_SIZE : 0) + sizeof (packet_id_type) * (n)) - -/* write a packet ID acknowledgement record to buf, */ -/* removing all acknowledged entries from ack */ -bool -reliable_ack_write (struct reliable_ack * ack, - struct buffer * buf, - const struct session_id * sid, int max, bool prepend) -{ - int i, j; - uint8_t n; - struct buffer sub; - - n = ack->len; - if (n > max) - n = max; - sub = buf_sub (buf, ACK_SIZE(n), prepend); - if (!BDEF (&sub)) - goto error; - ASSERT (buf_write (&sub, &n, sizeof (n))); - for (i = 0; i < n; ++i) - { - packet_id_type pid = ack->packet_id[i]; - packet_id_type net_pid = htonpid (pid); - ASSERT (buf_write (&sub, &net_pid, sizeof (net_pid))); - dmsg (D_REL_DEBUG, "ACK write ID " packet_id_format " (ack->len=%d, n=%d)", (packet_id_print_type)pid, ack->len, n); - } - if (n) - { - ASSERT (session_id_defined (sid)); - ASSERT (session_id_write (sid, &sub)); - for (i = 0, j = n; j < ack->len;) - ack->packet_id[i++] = ack->packet_id[j++]; - ack->len = i; - } - - return true; - -error: - return false; -} - -/* add to extra_frame the maximum number of bytes we will need for reliable_ack_write */ -void -reliable_ack_adjust_frame_parameters (struct frame* frame, int max) -{ - frame_add_to_extra_frame (frame, ACK_SIZE (max)); -} - -/* print a reliable ACK record coming off the wire */ -const char * -reliable_ack_print (struct buffer *buf, bool verbose, struct gc_arena *gc) -{ - int i; - uint8_t n_ack; - struct session_id sid_ack; - packet_id_type pid; - struct buffer out = alloc_buf_gc (256, gc); - - buf_printf (&out, "["); - if (!buf_read (buf, &n_ack, sizeof (n_ack))) - goto done; - for (i = 0; i < n_ack; ++i) - { - if (!buf_read (buf, &pid, sizeof (pid))) - goto done; - pid = ntohpid (pid); - buf_printf (&out, " " packet_id_format, (packet_id_print_type)pid); - } - if (n_ack) - { - if (!session_id_read (&sid_ack, buf)) - goto done; - if (verbose) - buf_printf (&out, " sid=%s", session_id_print (&sid_ack, gc)); - } - - done: - buf_printf (&out, " ]"); - return BSTR (&out); -} - -/* - * struct reliable member functions. - */ - -void -reliable_init (struct reliable *rel, int buf_size, int offset, int array_size, bool hold) -{ - int i; - - CLEAR (*rel); - ASSERT (array_size > 0 && array_size <= RELIABLE_CAPACITY); - rel->hold = hold; - rel->size = array_size; - rel->offset = offset; - for (i = 0; i < rel->size; ++i) - { - struct reliable_entry *e = &rel->array[i]; - e->buf = alloc_buf (buf_size); - ASSERT (buf_init (&e->buf, offset)); - } -} - -void -reliable_free (struct reliable *rel) -{ - int i; - for (i = 0; i < rel->size; ++i) - { - struct reliable_entry *e = &rel->array[i]; - free_buf (&e->buf); - } -} - -/* no active buffers? */ -bool -reliable_empty (const struct reliable *rel) -{ - int i; - for (i = 0; i < rel->size; ++i) - { - const struct reliable_entry *e = &rel->array[i]; - if (e->active) - return false; - } - return true; -} - -/* del acknowledged items from send buf */ -void -reliable_send_purge (struct reliable *rel, struct reliable_ack *ack) -{ - int i, j; - for (i = 0; i < ack->len; ++i) - { - packet_id_type pid = ack->packet_id[i]; - for (j = 0; j < rel->size; ++j) - { - struct reliable_entry *e = &rel->array[j]; - if (e->active && e->packet_id == pid) - { - dmsg (D_REL_DEBUG, - "ACK received for pid " packet_id_format ", deleting from send buffer", - (packet_id_print_type)pid); -#if 0 - /* DEBUGGING -- how close were we timing out on ACK failure and resending? */ - { - if (e->next_try) - { - const interval_t wake = e->next_try - now; - msg (M_INFO, "ACK " packet_id_format ", wake=%d", pid, wake); - } - } -#endif - e->active = false; - break; - } - } - } -} - -/* print the current sequence of active packet IDs */ -static const char * -reliable_print_ids (const struct reliable *rel, struct gc_arena *gc) -{ - struct buffer out = alloc_buf_gc (256, gc); - int i; - - buf_printf (&out, "[" packet_id_format "]", (packet_id_print_type)rel->packet_id); - for (i = 0; i < rel->size; ++i) - { - const struct reliable_entry *e = &rel->array[i]; - if (e->active) - buf_printf (&out, " " packet_id_format, (packet_id_print_type)e->packet_id); - } - return BSTR (&out); -} - -/* true if at least one free buffer available */ -bool -reliable_can_get (const struct reliable *rel) -{ - struct gc_arena gc = gc_new (); - int i; - for (i = 0; i < rel->size; ++i) - { - const struct reliable_entry *e = &rel->array[i]; - if (!e->active) - return true; - } - dmsg (D_REL_LOW, "ACK no free receive buffer available: %s", reliable_print_ids (rel, &gc)); - gc_free (&gc); - return false; -} - -/* make sure that incoming packet ID isn't a replay */ -bool -reliable_not_replay (const struct reliable *rel, packet_id_type id) -{ - struct gc_arena gc = gc_new (); - int i; - if (reliable_pid_min (id, rel->packet_id)) - goto bad; - for (i = 0; i < rel->size; ++i) - { - const struct reliable_entry *e = &rel->array[i]; - if (e->active && e->packet_id == id) - goto bad; - } - gc_free (&gc); - return true; - - bad: - dmsg (D_REL_DEBUG, "ACK " packet_id_format " is a replay: %s", (packet_id_print_type)id, reliable_print_ids (rel, &gc)); - gc_free (&gc); - return false; -} - -/* make sure that incoming packet ID won't deadlock the receive buffer */ -bool -reliable_wont_break_sequentiality (const struct reliable *rel, packet_id_type id) -{ - struct gc_arena gc = gc_new (); - - const int ret = reliable_pid_in_range2 (id, rel->packet_id, rel->size); - - if (!ret) - { - dmsg (D_REL_LOW, "ACK " packet_id_format " breaks sequentiality: %s", - (packet_id_print_type)id, reliable_print_ids (rel, &gc)); - } - - 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); - - gc_free (&gc); - return ret; -} - -/* grab a free buffer */ -struct buffer * -reliable_get_buf (struct reliable *rel) -{ - int i; - for (i = 0; i < rel->size; ++i) - { - struct reliable_entry *e = &rel->array[i]; - if (!e->active) - { - ASSERT (buf_init (&e->buf, rel->offset)); - return &e->buf; - } - } - return NULL; -} - -/* grab a free buffer, fail if buffer clogged by unacknowledged low packet IDs */ -struct buffer * -reliable_get_buf_output_sequenced (struct reliable *rel) -{ - struct gc_arena gc = gc_new (); - int i; - packet_id_type min_id = 0; - bool min_id_defined = false; - struct buffer *ret = NULL; - - /* find minimum active packet_id */ - for (i = 0; i < rel->size; ++i) - { - const struct reliable_entry *e = &rel->array[i]; - if (e->active) - { - if (!min_id_defined || reliable_pid_min (e->packet_id, min_id)) - { - min_id_defined = true; - min_id = e->packet_id; - } - } - } - - if (!min_id_defined || reliable_pid_in_range1 (rel->packet_id, min_id, rel->size)) - { - ret = reliable_get_buf (rel); - } - else - { - dmsg (D_REL_LOW, "ACK output sequence broken: %s", reliable_print_ids (rel, &gc)); - } - gc_free (&gc); - return ret; -} - -/* get active buffer for next sequentially increasing key ID */ -struct buffer * -reliable_get_buf_sequenced (struct reliable *rel) -{ - int i; - for (i = 0; i < rel->size; ++i) - { - struct reliable_entry *e = &rel->array[i]; - if (e->active && e->packet_id == rel->packet_id) - { - return &e->buf; - } - } - return NULL; -} - -/* return true if reliable_send would return a non-NULL result */ -bool -reliable_can_send (const struct reliable *rel) -{ - struct gc_arena gc = gc_new (); - int i; - int n_active = 0, n_current = 0; - for (i = 0; i < rel->size; ++i) - { - const struct reliable_entry *e = &rel->array[i]; - if (e->active) - { - ++n_active; - if (now >= e->next_try) - ++n_current; - } - } - dmsg (D_REL_DEBUG, "ACK reliable_can_send active=%d current=%d : %s", - n_active, - n_current, - reliable_print_ids (rel, &gc)); - - gc_free (&gc); - return n_current > 0 && !rel->hold; -} - -#ifdef EXPONENTIAL_BACKOFF -/* return a unique point-in-time to trigger retry */ -static time_t -reliable_unique_retry (struct reliable *rel, time_t retry) -{ - int i; - while (true) - { - for (i = 0; i < rel->size; ++i) - { - struct reliable_entry *e = &rel->array[i]; - if (e->active && e->next_try == retry) - goto again; - } - break; - again: - ++retry; - } - return retry; -} -#endif - -/* return next buffer to send to remote */ -struct buffer * -reliable_send (struct reliable *rel, int *opcode) -{ - int i; - struct reliable_entry *best = NULL; - const time_t local_now = now; - - for (i = 0; i < rel->size; ++i) - { - struct reliable_entry *e = &rel->array[i]; - if (e->active && local_now >= e->next_try) - { - if (!best || reliable_pid_min (e->packet_id, best->packet_id)) - best = e; - } - } - if (best) - { -#ifdef EXPONENTIAL_BACKOFF - /* exponential backoff */ - best->next_try = reliable_unique_retry (rel, local_now + best->timeout); - best->timeout *= 2; -#else - /* constant timeout, no backoff */ - best->next_try = local_now + best->timeout; -#endif - *opcode = best->opcode; - dmsg (D_REL_DEBUG, "ACK reliable_send ID " packet_id_format " (size=%d to=%d)", - (packet_id_print_type)best->packet_id, best->buf.len, - (int)(best->next_try - local_now)); - return &best->buf; - } - return NULL; -} - -/* schedule all pending packets for immediate retransmit */ -void -reliable_schedule_now (struct reliable *rel) -{ - int i; - dmsg (D_REL_DEBUG, "ACK reliable_schedule_now"); - rel->hold = false; - for (i = 0; i < rel->size; ++i) - { - struct reliable_entry *e = &rel->array[i]; - if (e->active) - { - e->next_try = now; - e->timeout = rel->initial_timeout; - } - } -} - -/* in how many seconds should we wake up to check for timeout */ -/* if we return BIG_TIMEOUT, nothing to wait for */ -interval_t -reliable_send_timeout (const struct reliable *rel) -{ - struct gc_arena gc = gc_new (); - interval_t ret = BIG_TIMEOUT; - int i; - const time_t local_now = now; - - for (i = 0; i < rel->size; ++i) - { - const struct reliable_entry *e = &rel->array[i]; - if (e->active) - { - if (e->next_try <= local_now) - { - ret = 0; - break; - } - else - { - ret = min_int (ret, e->next_try - local_now); - } - } - } - - dmsg (D_REL_DEBUG, "ACK reliable_send_timeout %d %s", - (int) ret, - reliable_print_ids (rel, &gc)); - - gc_free (&gc); - return ret; -} - -/* - * Enable an incoming buffer previously returned by a get function as active. - */ - -void -reliable_mark_active_incoming (struct reliable *rel, struct buffer *buf, - packet_id_type pid, int opcode) -{ - int i; - for (i = 0; i < rel->size; ++i) - { - struct reliable_entry *e = &rel->array[i]; - if (buf == &e->buf) - { - e->active = true; - - /* packets may not arrive in sequential order */ - e->packet_id = pid; - - /* check for replay */ - ASSERT (!reliable_pid_min (pid, rel->packet_id)); - - e->opcode = opcode; - e->next_try = 0; - e->timeout = 0; - dmsg (D_REL_DEBUG, "ACK mark active incoming ID " packet_id_format, (packet_id_print_type)e->packet_id); - return; - } - } - ASSERT (0); /* buf not found in rel */ -} - -/* - * Enable an outgoing buffer previously returned by a get function as active. - */ - -void -reliable_mark_active_outgoing (struct reliable *rel, struct buffer *buf, int opcode) -{ - int i; - for (i = 0; i < rel->size; ++i) - { - struct reliable_entry *e = &rel->array[i]; - if (buf == &e->buf) - { - /* Write mode, increment packet_id (i.e. sequence number) - linearly and prepend id to packet */ - packet_id_type net_pid; - e->packet_id = rel->packet_id++; - net_pid = htonpid (e->packet_id); - ASSERT (buf_write_prepend (buf, &net_pid, sizeof (net_pid))); - e->active = true; - e->opcode = opcode; - e->next_try = 0; - e->timeout = rel->initial_timeout; - dmsg (D_REL_DEBUG, "ACK mark active outgoing ID " packet_id_format, (packet_id_print_type)e->packet_id); - return; - } - } - ASSERT (0); /* buf not found in rel */ -} - -/* delete a buffer previously activated by reliable_mark_active() */ -void -reliable_mark_deleted (struct reliable *rel, struct buffer *buf, bool inc_pid) -{ - int i; - for (i = 0; i < rel->size; ++i) - { - struct reliable_entry *e = &rel->array[i]; - if (buf == &e->buf) - { - e->active = false; - if (inc_pid) - rel->packet_id = e->packet_id + 1; - return; - } - } - ASSERT (0); -} - -#if 0 - -void -reliable_ack_debug_print (const struct reliable_ack *ack, char *desc) -{ - int i; - - printf ("********* struct reliable_ack %s\n", desc); - for (i = 0; i < ack->len; ++i) - { - printf (" %d: " packet_id_format "\n", i, (packet_id_print_type) ack->packet_id[i]); - } -} - -void -reliable_debug_print (const struct reliable *rel, char *desc) -{ - int i; - update_time (); - - printf ("********* struct reliable %s\n", desc); - printf (" initial_timeout=%d\n", (int)rel->initial_timeout); - printf (" packet_id=" packet_id_format "\n", rel->packet_id); - printf (" now=" time_format "\n", now); - for (i = 0; i < rel->size; ++i) - { - const struct reliable_entry *e = &rel->array[i]; - if (e->active) - { - printf (" %d: packet_id=" packet_id_format " len=%d", i, e->packet_id, e->buf.len); - printf (" next_try=" time_format, e->next_try); - printf ("\n"); - } - } -} - -#endif - -#else -static void dummy(void) {} -#endif /* USE_CRYPTO && USE_SSL*/ |