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-2010 OpenVPN Technologies, Inc. <sales@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 HAVE_CONFIG_H 26#include "config.h" 27#elif defined(_MSC_VER) 28#include "config-msvc.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 42static void 43fragment_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 50static void 51fragment_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 */ 62static struct fragment * 63fragment_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 84struct fragment_master * 85fragment_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 111void 112fragment_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 120void 121fragment_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 */ 134void 135fragment_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 */ 249static void 250fragment_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 */ 290static inline int 291optimal_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 */ 305void 306fragment_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 */ 354bool 355fragment_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 389static void 390fragment_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 */ 405void 406fragment_wakeup (struct fragment_master *f, struct frame *frame) 407{ 408 /* delete fragments with expired TTLs */ 409 fragment_ttl_reap (f); 410} 411 412#else 413static void dummy(void) {} 414#endif 415