openvpn/fragment.c

   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-2005 OpenVPN Solutions LLC <info@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 #ifdef WIN32
  26 #include "config-win32.h"
  27 #else
  28 #include "config.h"
  29 #endif
  30
  31 #include "syshead.h"
  32
  33 #ifdef ENABLE_FRAGMENT
  34
  35 #include "misc.h"
  36 #include "fragment.h"
  37 #include "integer.h"
  38 #include "memdbg.h"
  39
  40 #define FRAG_ERR(s) { errmsg = s; goto error; }
  41
  42 static void
  43 fragment_list_buf_init (struct fragment_list *list, const struct frame *frame)
  44 {
  45   int i;
  46   for (i = 0; i < N_FRAG_BUF; ++i)
  47     list->fragments[i].buf = alloc_buf (BUF_SIZE (frame));
  48 }
  49
  50 static void
  51 fragment_list_buf_free (struct fragment_list *list)
  52 {
  53   int i;
  54   for (i = 0; i < N_FRAG_BUF; ++i)
  55     free_buf (&list->fragments[i].buf);
  56 }
  57
  58 /*
  59  * Given a sequence ID number, get a fragment buffer.  Use a sliding window,
  60  * similar to packet_id code.
  61  */
  62 static struct fragment *
  63 fragment_list_get_buf (struct fragment_list *list, int seq_id)
  64 {
  65   int diff;
  66   if (abs (diff = modulo_subtract (seq_id, list->seq_id, N_SEQ_ID)) >= N_FRAG_BUF)
  67     {
  68       int i;
  69       for (i = 0; i < N_FRAG_BUF; ++i)
  70         list->fragments[i].defined = false;
  71       list->index = 0;
  72       list->seq_id = seq_id;
  73       diff = 0;
  74     }
  75   while (diff > 0)
  76     {
  77       list->fragments[list->index = modulo_add (list->index, 1, N_FRAG_BUF)].defined = false;
  78       list->seq_id = modulo_add (list->seq_id, 1, N_SEQ_ID);
  79       --diff;
  80     }
  81   return &list->fragments[modulo_add (list->index, diff, N_FRAG_BUF)];
  82 }
  83
  84 struct fragment_master *
  85 fragment_init (struct frame *frame)
  86 {
  87   struct fragment_master *ret;
  88
  89   /* code that initializes other parts of
  90      fragment_master assume an initial CLEAR */
  91   ALLOC_OBJ_CLEAR (ret, struct fragment_master);
  92
  93   /* add in the size of our contribution to the expanded frame size */
  94   frame_add_to_extra_frame (frame, sizeof(fragment_header_type));
  95
  96   /*
  97    * Outgoing sequence ID is randomized to reduce
  98    * the probability of sequence number collisions
  99    * when openvpn sessions are restarted.  This is
 100    * not done out of any need for security, as all
 101    * fragmentation control information resides
 102    * inside of the encrypted/authenticated envelope.
 103    */
 104   ret->outgoing_seq_id = (int)get_random() & (N_SEQ_ID - 1);
 105
 106   event_timeout_init (&ret->wakeup, FRAG_WAKEUP_INTERVAL, now);
 107
 108   return ret;
 109 }
 110
 111 void
 112 fragment_free (struct fragment_master *f)
 113 {
 114   fragment_list_buf_free (&f->incoming);
 115   free_buf (&f->outgoing);
 116   free_buf (&f->outgoing_return);
 117   free (f);
 118 }
 119
 120 void
 121 fragment_frame_init (struct fragment_master *f, const struct frame *frame)
 122 {
 123   fragment_list_buf_init (&f->incoming, frame);
 124   f->outgoing = alloc_buf (BUF_SIZE (frame));
 125   f->outgoing_return = alloc_buf (BUF_SIZE (frame));
 126 }
 127
 128 /*
 129  * Accept an incoming datagram (which may be a fragment) from remote.
 130  * If the datagram is whole (i.e not a fragment), pass through.
 131  * If the datagram is a fragment, join with other fragments received so far.
 132  * If a fragment fully completes the datagram, return the datagram.
 133  */
 134 void
 135 fragment_incoming (struct fragment_master *f, struct buffer *buf,
 136                    const struct frame* frame)
 137 {
 138   const char *errmsg = NULL;
 139   fragment_header_type flags = 0;
 140   int frag_type = 0;
 141
 142   if (buf->len > 0)
 143     {
 144       /* get flags from packet head */
 145       if (!buf_read (buf, &flags, sizeof (flags)))
 146         FRAG_ERR ("flags not found in packet");
 147       flags = ntoh_fragment_header_type (flags);
 148
 149       /* get fragment type from flags */
 150       frag_type = ((flags >> FRAG_TYPE_SHIFT) & FRAG_TYPE_MASK);
 151
 152 #if 0
 153       /*
 154        * If you want to extract FRAG_EXTRA_MASK/FRAG_EXTRA_SHIFT bits,
 155        * do it here.
 156        */
 157       if (frag_type == FRAG_WHOLE || frag_type == FRAG_YES_NOTLAST)
 158         {
 159         }
 160 #endif
 161
 162       /* handle the fragment type */
 163       if (frag_type == FRAG_WHOLE)
 164         {
 165           dmsg (D_FRAG_DEBUG,
 166                "FRAG_IN buf->len=%d type=FRAG_WHOLE flags="
 167                fragment_header_format,
 168                buf->len,
 169                flags);
 170
 171           if (flags & (FRAG_SEQ_ID_MASK | FRAG_ID_MASK))
 172             FRAG_ERR ("spurrious FRAG_WHOLE flags");
 173         }
 174       else if (frag_type == FRAG_YES_NOTLAST || frag_type == FRAG_YES_LAST)
 175         {
 176           const int seq_id = ((flags >> FRAG_SEQ_ID_SHIFT) & FRAG_SEQ_ID_MASK);
 177           const int n = ((flags >> FRAG_ID_SHIFT) & FRAG_ID_MASK);
 178           const int size = ((frag_type == FRAG_YES_LAST)
 179                             ? (int)(((flags >> FRAG_SIZE_SHIFT) & FRAG_SIZE_MASK) << FRAG_SIZE_ROUND_SHIFT)
 180                             : buf->len);
 181
 182           /* get the appropriate fragment buffer based on received seq_id */
 183           struct fragment *frag = fragment_list_get_buf (&f->incoming, seq_id);
 184
 185           dmsg (D_FRAG_DEBUG,
 186                "FRAG_IN len=%d type=%d seq_id=%d frag_id=%d size=%d flags="
 187                fragment_header_format,
 188                buf->len,
 189                frag_type,
 190                seq_id,
 191                n,
 192                size,
 193                flags);
 194
 195           /* make sure that size is an even multiple of 1<<FRAG_SIZE_ROUND_SHIFT */
 196           if (size & FRAG_SIZE_ROUND_MASK)
 197             FRAG_ERR ("bad fragment size");
 198
 199           /* is this the first fragment for our sequence number? */
 200           if (!frag->defined || (frag->defined && frag->max_frag_size != size))
 201             {
 202               frag->defined = true;
 203               frag->max_frag_size = size;
 204               frag->map = 0;
 205               ASSERT (buf_init (&frag->buf, FRAME_HEADROOM_ADJ (frame, FRAME_HEADROOM_MARKER_FRAGMENT)));
 206             }
 207
 208           /* copy the data to fragment buffer */
 209           if (!buf_copy_range (&frag->buf, n * size, buf, 0, buf->len))
 210             FRAG_ERR ("fragment buffer overflow");
 211
 212           /* set elements in bit array to reflect which fragments have been received */
 213           frag->map |= (((frag_type == FRAG_YES_LAST) ? FRAG_MAP_MASK : 1) << n);
 214
 215           /* update timestamp on partially built datagram */
 216           frag->timestamp = now;
 217
 218           /* received full datagram? */
 219           if ((frag->map & FRAG_MAP_MASK) == FRAG_MAP_MASK)
 220             {
 221               frag->defined = false;
 222               *buf = frag->buf;
 223             }
 224           else
 225             {
 226               buf->len = 0;
 227             }
 228         }
 229       else if (frag_type == FRAG_TEST)
 230         {
 231           FRAG_ERR ("FRAG_TEST not implemented");
 232         }
 233       else
 234         {
 235           FRAG_ERR ("unknown fragment type");
 236         }
 237     }
 238
 239   return;
 240
 241  error:
 242   if (errmsg)
 243     msg (D_FRAG_ERRORS, "FRAG_IN error flags=" fragment_header_format ": %s", flags, errmsg);
 244   buf->len = 0;
 245   return;
 246 }
 247
 248 /* pack fragment parms into a uint32_t and prepend to buffer */
 249 static void
 250 fragment_prepend_flags (struct buffer *buf,
 251                         int type,
 252                         int seq_id,
 253                         int frag_id,
 254                         int frag_size)
 255 {
 256   fragment_header_type flags = ((type & FRAG_TYPE_MASK) << FRAG_TYPE_SHIFT)
 257     | ((seq_id & FRAG_SEQ_ID_MASK) << FRAG_SEQ_ID_SHIFT)
 258     | ((frag_id & FRAG_ID_MASK) << FRAG_ID_SHIFT);
 259
 260   if (type == FRAG_WHOLE || type == FRAG_YES_NOTLAST)
 261     {
 262       /*
 263        * If you want to set FRAG_EXTRA_MASK/FRAG_EXTRA_SHIFT bits,
 264        * do it here.
 265        */
 266       dmsg (D_FRAG_DEBUG,
 267            "FRAG_OUT len=%d type=%d seq_id=%d frag_id=%d frag_size=%d flags="
 268            fragment_header_format,
 269            buf->len, type, seq_id, frag_id, frag_size, flags);
 270     }
 271   else
 272     {
 273       flags |= (((frag_size >> FRAG_SIZE_ROUND_SHIFT) & FRAG_SIZE_MASK) << FRAG_SIZE_SHIFT);
 274
 275       dmsg (D_FRAG_DEBUG,
 276            "FRAG_OUT len=%d type=%d seq_id=%d frag_id=%d frag_size=%d flags="
 277            fragment_header_format,
 278            buf->len, type, seq_id, frag_id, frag_size, flags);
 279     }
 280
 281   flags = hton_fragment_header_type (flags);
 282   ASSERT (buf_write_prepend (buf, &flags, sizeof (flags)));
 283 }
 284
 285 /*
 286  * Without changing the number of fragments, return a possibly smaller
 287  * max fragment size that will allow for the last fragment to be of
 288  * similar size as previous fragments.
 289  */
 290 static inline int
 291 optimal_fragment_size (int len, int max_frag_size)
 292 {
 293   const int mfs_aligned = (max_frag_size & ~FRAG_SIZE_ROUND_MASK);
 294   const int div = len / mfs_aligned;
 295   const int mod = len % mfs_aligned;
 296
 297   if (div > 0 && mod > 0 && mod < mfs_aligned * 3 / 4)
 298     return min_int (mfs_aligned, (max_frag_size - ((max_frag_size - mod) / (div + 1))
 299                                   + FRAG_SIZE_ROUND_MASK) & ~FRAG_SIZE_ROUND_MASK);
 300   else
 301     return mfs_aligned;
 302 }
 303
 304 /* process an outgoing datagram, possibly breaking it up into fragments */
 305 void
 306 fragment_outgoing (struct fragment_master *f, struct buffer *buf,
 307                    const struct frame* frame)
 308 {
 309   const char *errmsg = NULL;
 310   if (buf->len > 0)
 311     {
 312       /* The outgoing buffer should be empty so we can put new data in it */
 313       if (f->outgoing.len)
 314         msg (D_FRAG_ERRORS, "FRAG: outgoing buffer is not empty, len=[%d,%d]",
 315              buf->len, f->outgoing.len);
 316       if (buf->len > PAYLOAD_SIZE_DYNAMIC(frame)) /* should we fragment? */
 317         {
 318           /*
 319            * Send the datagram as a series of 2 or more fragments.
 320            */
 321           f->outgoing_frag_size = optimal_fragment_size (buf->len, PAYLOAD_SIZE_DYNAMIC(frame));
 322           if (buf->len > f->outgoing_frag_size * MAX_FRAGS)
 323             FRAG_ERR ("too many fragments would be required to send datagram");
 324           ASSERT (buf_init (&f->outgoing, FRAME_HEADROOM (frame)));
 325           ASSERT (buf_copy (&f->outgoing, buf));
 326           f->outgoing_seq_id = modulo_add (f->outgoing_seq_id, 1, N_SEQ_ID);
 327           f->outgoing_frag_id = 0;
 328           buf->len = 0;
 329           ASSERT (fragment_ready_to_send (f, buf, frame));
 330         }
 331       else
 332         {
 333           /*
 334            * Send the datagram whole.
 335            */
 336           fragment_prepend_flags (buf,
 337                                   FRAG_WHOLE,
 338                                   0,
 339                                   0,
 340                                   0);
 341         }
 342     }
 343   return;
 344
 345  error:
 346   if (errmsg)
 347     msg (D_FRAG_ERRORS, "FRAG_OUT error, len=%d frag_size=%d MAX_FRAGS=%d: %s",
 348          buf->len, f->outgoing_frag_size, MAX_FRAGS, errmsg);
 349   buf->len = 0;
 350   return;
 351 }
 352
 353 /* return true (and set buf) if we have an outgoing fragment which is ready to send */
 354 bool
 355 fragment_ready_to_send (struct fragment_master *f, struct buffer *buf,
 356                         const struct frame* frame)
 357 {
 358   if (fragment_outgoing_defined (f))
 359     {
 360       /* get fragment size, and determine if it is the last fragment */
 361       int size = f->outgoing_frag_size;
 362       int last = false;
 363       if (f->outgoing.len <= size)
 364         {
 365           size = f->outgoing.len;
 366           last = true;
 367         }
 368
 369       /* initialize return buffer */
 370       *buf = f->outgoing_return;
 371       ASSERT (buf_init (buf, FRAME_HEADROOM (frame)));
 372       ASSERT (buf_copy_n (buf, &f->outgoing, size));
 373
 374       /* fragment flags differ based on whether or not we are sending the last fragment */
 375       fragment_prepend_flags (buf,
 376                               last ? FRAG_YES_LAST : FRAG_YES_NOTLAST,
 377                               f->outgoing_seq_id,
 378                               f->outgoing_frag_id++,
 379                               f->outgoing_frag_size);
 380
 381       ASSERT (!last || !f->outgoing.len); /* outgoing buffer length should be zero after last fragment sent */
 382
 383       return true;
 384     }
 385   else
 386     return false;
 387 }
 388
 389 static void
 390 fragment_ttl_reap (struct fragment_master *f)
 391 {
 392   int i;
 393   for (i = 0; i < N_FRAG_BUF; ++i)
 394     {
 395       struct fragment *frag = &f->incoming.fragments[i];
 396       if (frag->defined && frag->timestamp + FRAG_TTL_SEC <= now)
 397         {
 398           msg (D_FRAG_ERRORS, "FRAG TTL expired i=%d", i);
 399           frag->defined = false;
 400         }
 401     }
 402 }
 403
 404 /* called every FRAG_WAKEUP_INTERVAL seconds */
 405 void
 406 fragment_wakeup (struct fragment_master *f, struct frame *frame)
 407 {
 408   /* delete fragments with expired TTLs */
 409   fragment_ttl_reap (f);
 410 }
 411
 412 #else
 413 static void dummy(void) {}
 414 #endif