/*
  *  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"

 
 #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;

 }
 
 /* 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 = 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=%"PRIi64"\n", (int64_t)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=%"PRIi64, (int64_t)e->next_try);

             printf("\n");
         }

     }
 }
 

 #endif /* if 0 */