| /* |
| * 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-2018 OpenVPN 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; if not, write to the Free Software Foundation, Inc., |
| * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. |
| */ |
| |
| /* |
| * These routines implement a reliability layer on top of UDP, |
| * so that SSL/TLS can be run over UDP. |
| */ |
| |
| #ifdef HAVE_CONFIG_H |
| #include "config.h" |
| #elif defined(_MSC_VER) |
| #include "config-msvc.h" |
| #endif |
| |
| #include "syshead.h" |
| |
| #ifdef ENABLE_CRYPTO |
| |
| #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 /* ifdef EXPONENTIAL_BACKOFF */ |
| |
| /* 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 /* if 0 */ |
| |
| #else /* ifdef ENABLE_CRYPTO */ |
| static void |
| dummy(void) |
| { |
| } |
| #endif /* ENABLE_CRYPTO */ |
