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

 }
 
 /* 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;
 }
 
 /* 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*/