OpenVPN
fragment.c
Go to the documentation of this file.
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-2018 OpenVPN 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 along
20  * with this program; if not, write to the Free Software Foundation, Inc.,
21  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
22  */
23 
24 #ifdef HAVE_CONFIG_H
25 #include "config.h"
26 #elif defined(_MSC_VER)
27 #include "config-msvc.h"
28 #endif
29 
30 #include "syshead.h"
31 
32 #ifdef ENABLE_FRAGMENT
33 
34 #include "misc.h"
35 #include "fragment.h"
36 #include "integer.h"
37 #include "memdbg.h"
38 
39 #define FRAG_ERR(s) { errmsg = s; goto error; }
40 
41 static void
42 fragment_list_buf_init(struct fragment_list *list, const struct frame *frame)
43 {
44  int i;
45  for (i = 0; i < N_FRAG_BUF; ++i)
46  {
47  list->fragments[i].buf = alloc_buf(BUF_SIZE(frame));
48  }
49 }
50 
51 static void
53 {
54  int i;
55  for (i = 0; i < N_FRAG_BUF; ++i)
56  {
57  free_buf(&list->fragments[i].buf);
58  }
59 }
60 
61 /*
62  * Given a sequence ID number, get a fragment buffer. Use a sliding window,
63  * similar to packet_id code.
64  */
65 static struct fragment *
66 fragment_list_get_buf(struct fragment_list *list, int seq_id)
67 {
68  int diff;
69  if (abs(diff = modulo_subtract(seq_id, list->seq_id, N_SEQ_ID)) >= N_FRAG_BUF)
70  {
71  int i;
72  for (i = 0; i < N_FRAG_BUF; ++i)
73  {
74  list->fragments[i].defined = false;
75  }
76  list->index = 0;
77  list->seq_id = seq_id;
78  diff = 0;
79  }
80  while (diff > 0)
81  {
82  list->fragments[list->index = modulo_add(list->index, 1, N_FRAG_BUF)].defined = false;
83  list->seq_id = modulo_add(list->seq_id, 1, N_SEQ_ID);
84  --diff;
85  }
86  return &list->fragments[modulo_add(list->index, diff, N_FRAG_BUF)];
87 }
88 
89 struct fragment_master *
91 {
92  struct fragment_master *ret;
93 
94  /* code that initializes other parts of
95  * fragment_master assume an initial CLEAR */
96  ALLOC_OBJ_CLEAR(ret, struct fragment_master);
97 
98  /* add in the size of our contribution to the expanded frame size */
100 
101  /*
102  * Outgoing sequence ID is randomized to reduce
103  * the probability of sequence number collisions
104  * when openvpn sessions are restarted. This is
105  * not done out of any need for security, as all
106  * fragmentation control information resides
107  * inside of the encrypted/authenticated envelope.
108  */
109  ret->outgoing_seq_id = (int)get_random() & (N_SEQ_ID - 1);
110 
112 
113  return ret;
114 }
115 
116 void
118 {
120  free_buf(&f->outgoing);
122  free(f);
123 }
124 
125 void
127 {
128  fragment_list_buf_init(&f->incoming, frame);
129  f->outgoing = alloc_buf(BUF_SIZE(frame));
130  f->outgoing_return = alloc_buf(BUF_SIZE(frame));
131 }
132 
133 /*
134  * Accept an incoming datagram (which may be a fragment) from remote.
135  * If the datagram is whole (i.e not a fragment), pass through.
136  * If the datagram is a fragment, join with other fragments received so far.
137  * If a fragment fully completes the datagram, return the datagram.
138  */
139 void
141  const struct frame *frame)
142 {
143  const char *errmsg = NULL;
145  int frag_type = 0;
146 
147  if (buf->len > 0)
148  {
149  /* get flags from packet head */
150  if (!buf_read(buf, &flags, sizeof(flags)))
151  {
152  FRAG_ERR("flags not found in packet");
153  }
154  flags = ntoh_fragment_header_type(flags);
155 
156  /* get fragment type from flags */
157  frag_type = ((flags >> FRAG_TYPE_SHIFT) & FRAG_TYPE_MASK);
158 
159 #if 0
160  /*
161  * If you want to extract FRAG_EXTRA_MASK/FRAG_EXTRA_SHIFT bits,
162  * do it here.
163  */
164  if (frag_type == FRAG_WHOLE || frag_type == FRAG_YES_NOTLAST)
165  {
166  }
167 #endif
168 
169  /* handle the fragment type */
170  if (frag_type == FRAG_WHOLE)
171  {
173  "FRAG_IN buf->len=%d type=FRAG_WHOLE flags="
175  buf->len,
176  flags);
177 
178  if (flags & (FRAG_SEQ_ID_MASK | FRAG_ID_MASK))
179  {
180  FRAG_ERR("spurrious FRAG_WHOLE flags");
181  }
182  }
183  else if (frag_type == FRAG_YES_NOTLAST || frag_type == FRAG_YES_LAST)
184  {
185  const int seq_id = ((flags >> FRAG_SEQ_ID_SHIFT) & FRAG_SEQ_ID_MASK);
186  const int n = ((flags >> FRAG_ID_SHIFT) & FRAG_ID_MASK);
187  const int size = ((frag_type == FRAG_YES_LAST)
188  ? (int)(((flags >> FRAG_SIZE_SHIFT) & FRAG_SIZE_MASK) << FRAG_SIZE_ROUND_SHIFT)
189  : buf->len);
190 
191  /* get the appropriate fragment buffer based on received seq_id */
192  struct fragment *frag = fragment_list_get_buf(&f->incoming, seq_id);
193 
195  "FRAG_IN len=%d type=%d seq_id=%d frag_id=%d size=%d flags="
197  buf->len,
198  frag_type,
199  seq_id,
200  n,
201  size,
202  flags);
203 
204  /* make sure that size is an even multiple of 1<<FRAG_SIZE_ROUND_SHIFT */
205  if (size & FRAG_SIZE_ROUND_MASK)
206  {
207  FRAG_ERR("bad fragment size");
208  }
209 
210  /* is this the first fragment for our sequence number? */
211  if (!frag->defined || frag->max_frag_size != size)
212  {
213  frag->defined = true;
214  frag->max_frag_size = size;
215  frag->map = 0;
217  }
218 
219  /* copy the data to fragment buffer */
220  if (!buf_copy_range(&frag->buf, n * size, buf, 0, buf->len))
221  {
222  FRAG_ERR("fragment buffer overflow");
223  }
224 
225  /* set elements in bit array to reflect which fragments have been received */
226  frag->map |= (((frag_type == FRAG_YES_LAST) ? FRAG_MAP_MASK : 1) << n);
227 
228  /* update timestamp on partially built datagram */
229  frag->timestamp = now;
230 
231  /* received full datagram? */
232  if ((frag->map & FRAG_MAP_MASK) == FRAG_MAP_MASK)
233  {
234  frag->defined = false;
235  *buf = frag->buf;
236  }
237  else
238  {
239  buf->len = 0;
240  }
241  }
242  else if (frag_type == FRAG_TEST)
243  {
244  FRAG_ERR("FRAG_TEST not implemented");
245  }
246  else
247  {
248  FRAG_ERR("unknown fragment type");
249  }
250  }
251 
252  return;
253 
254 error:
255  if (errmsg)
256  {
257  msg(D_FRAG_ERRORS, "FRAG_IN error flags=" fragment_header_format ": %s", flags, errmsg);
258  }
259  buf->len = 0;
260  return;
261 }
262 
263 /* pack fragment parms into a uint32_t and prepend to buffer */
264 static void
266  int type,
267  int seq_id,
268  int frag_id,
269  int frag_size)
270 {
272  | ((seq_id & FRAG_SEQ_ID_MASK) << FRAG_SEQ_ID_SHIFT)
273  | ((frag_id & FRAG_ID_MASK) << FRAG_ID_SHIFT);
274 
275  if (type == FRAG_WHOLE || type == FRAG_YES_NOTLAST)
276  {
277  /*
278  * If you want to set FRAG_EXTRA_MASK/FRAG_EXTRA_SHIFT bits,
279  * do it here.
280  */
282  "FRAG_OUT len=%d type=%d seq_id=%d frag_id=%d frag_size=%d flags="
284  buf->len, type, seq_id, frag_id, frag_size, flags);
285  }
286  else
287  {
288  flags |= (((frag_size >> FRAG_SIZE_ROUND_SHIFT) & FRAG_SIZE_MASK) << FRAG_SIZE_SHIFT);
289 
291  "FRAG_OUT len=%d type=%d seq_id=%d frag_id=%d frag_size=%d flags="
293  buf->len, type, seq_id, frag_id, frag_size, flags);
294  }
295 
296  flags = hton_fragment_header_type(flags);
297  ASSERT(buf_write_prepend(buf, &flags, sizeof(flags)));
298 }
299 
300 /*
301  * Without changing the number of fragments, return a possibly smaller
302  * max fragment size that will allow for the last fragment to be of
303  * similar size as previous fragments.
304  */
305 static inline int
307 {
308  const int mfs_aligned = (max_frag_size & ~FRAG_SIZE_ROUND_MASK);
309  const int div = len / mfs_aligned;
310  const int mod = len % mfs_aligned;
311 
312  if (div > 0 && mod > 0 && mod < mfs_aligned * 3 / 4)
313  {
314  return min_int(mfs_aligned, (max_frag_size - ((max_frag_size - mod) / (div + 1))
316  }
317  else
318  {
319  return mfs_aligned;
320  }
321 }
322 
323 /* process an outgoing datagram, possibly breaking it up into fragments */
324 void
326  const struct frame *frame)
327 {
328  const char *errmsg = NULL;
329  if (buf->len > 0)
330  {
331  /* The outgoing buffer should be empty so we can put new data in it */
332  if (f->outgoing.len)
333  {
334  msg(D_FRAG_ERRORS, "FRAG: outgoing buffer is not empty, len=[%d,%d]",
335  buf->len, f->outgoing.len);
336  }
337  if (buf->len > PAYLOAD_SIZE_DYNAMIC(frame)) /* should we fragment? */
338  {
339  /*
340  * Send the datagram as a series of 2 or more fragments.
341  */
343  if (buf->len > f->outgoing_frag_size * MAX_FRAGS)
344  {
345  FRAG_ERR("too many fragments would be required to send datagram");
346  }
347  ASSERT(buf_init(&f->outgoing, FRAME_HEADROOM(frame)));
348  ASSERT(buf_copy(&f->outgoing, buf));
350  f->outgoing_frag_id = 0;
351  buf->len = 0;
352  ASSERT(fragment_ready_to_send(f, buf, frame));
353  }
354  else
355  {
356  /*
357  * Send the datagram whole.
358  */
360  FRAG_WHOLE,
361  0,
362  0,
363  0);
364  }
365  }
366  return;
367 
368 error:
369  if (errmsg)
370  {
371  msg(D_FRAG_ERRORS, "FRAG_OUT error, len=%d frag_size=%d MAX_FRAGS=%d: %s",
372  buf->len, f->outgoing_frag_size, MAX_FRAGS, errmsg);
373  }
374  buf->len = 0;
375  return;
376 }
377 
378 /* return true (and set buf) if we have an outgoing fragment which is ready to send */
379 bool
381  const struct frame *frame)
382 {
384  {
385  /* get fragment size, and determine if it is the last fragment */
386  int size = f->outgoing_frag_size;
387  int last = false;
388  if (f->outgoing.len <= size)
389  {
390  size = f->outgoing.len;
391  last = true;
392  }
393 
394  /* initialize return buffer */
395  *buf = f->outgoing_return;
396  ASSERT(buf_init(buf, FRAME_HEADROOM(frame)));
397  ASSERT(buf_copy_n(buf, &f->outgoing, size));
398 
399  /* fragment flags differ based on whether or not we are sending the last fragment */
402  f->outgoing_seq_id,
403  f->outgoing_frag_id++,
404  f->outgoing_frag_size);
405 
406  ASSERT(!last || !f->outgoing.len); /* outgoing buffer length should be zero after last fragment sent */
407 
408  return true;
409  }
410  else
411  {
412  return false;
413  }
414 }
415 
416 static void
418 {
419  int i;
420  for (i = 0; i < N_FRAG_BUF; ++i)
421  {
422  struct fragment *frag = &f->incoming.fragments[i];
423  if (frag->defined && frag->timestamp + FRAG_TTL_SEC <= now)
424  {
425  msg(D_FRAG_ERRORS, "FRAG TTL expired i=%d", i);
426  frag->defined = false;
427  }
428  }
429 }
430 
431 /* called every FRAG_WAKEUP_INTERVAL seconds */
432 void
434 {
435  /* delete fragments with expired TTLs */
437 }
438 
439 #else /* ifdef ENABLE_FRAGMENT */
440 static void
441 dummy(void)
442 {
443 }
444 #endif /* ifdef ENABLE_FRAGMENT */
#define FRAG_ERR(s)
Definition: fragment.c:39
#define hton_fragment_header_type(x)
Convert a fragment_header_type from host to network order.
Definition: fragment.h:194
static void fragment_ttl_reap(struct fragment_master *f)
Definition: fragment.c:417
int outgoing_seq_id
Fragment sequence ID of the current fragmented packet waiting to be sent.
Definition: fragment.h:146
void free_buf(struct buffer *buf)
Definition: buffer.c:183
int outgoing_frag_size
Size in bytes of each part to be sent, except for the last part which may be smaller.
Definition: fragment.h:157
Fragmentation and reassembly state for one VPN tunnel instance.
Definition: fragment.h:136
struct fragment_list incoming
List of structures for reassembling incoming packets.
Definition: fragment.h:179
Packet geometry parameters.
Definition: mtu.h:93
int outgoing_frag_id
The fragment ID of the next part to be sent.
Definition: fragment.h:169
#define FRAG_WAKEUP_INTERVAL
Interval in seconds between calls to wakeup code.
Definition: fragment.h:57
Structure for reassembling one incoming fragmented packet.
Definition: fragment.h:65
bool defined
Whether reassembly is currently taking place in this structure.
Definition: fragment.h:66
static int modulo_subtract(int x, int y, int mod)
Definition: integer.h:91
#define ntoh_fragment_header_type(x)
Convert a fragment_header_type from network to host order.
Definition: fragment.h:199
#define ASSERT(x)
Definition: error.h:221
struct buffer alloc_buf(size_t size)
Definition: buffer.c:62
#define MAX_FRAGS
Maximum number of fragments per packet.
Definition: fragment.h:73
static int modulo_add(int x, int y, int mod)
Definition: integer.h:106
#define fragment_header_format
Definition: common.h:60
static bool fragment_outgoing_defined(struct fragment_master *f)
Check whether a fragment_master structure contains fragments ready to be sent.
Definition: fragment.h:448
static void dummy(void)
Definition: comp-lz4.c:319
#define FRAG_SEQ_ID_SHIFT
Bit shift for fragment sequence ID.
Definition: fragment.h:231
#define FRAG_YES_LAST
Fragment type indicating packet is the last part in the sequence of parts.
Definition: fragment.h:216
bool fragment_ready_to_send(struct fragment_master *f, struct buffer *buf, const struct frame *frame)
Check whether outgoing fragments are ready to be send, and if so make one available.
Definition: fragment.c:380
#define FRAG_YES_NOTLAST
Fragment type indicating packet is part of a fragmented packet, but not the last part in the sequence...
Definition: fragment.h:211
int max_frag_size
Maximum size of each fragment.
Definition: fragment.h:69
#define FRAG_ID_SHIFT
Bit shift for fragment ID.
Definition: fragment.h:235
static void frame_add_to_extra_frame(struct frame *frame, const int increment)
Definition: mtu.h:274
#define FRAG_TYPE_MASK
Bit mask for fragment type info.
Definition: fragment.h:204
void fragment_outgoing(struct fragment_master *f, struct buffer *buf, const struct frame *frame)
Process an outgoing packet, which may or may not need to be fragmented.
Definition: fragment.c:325
static bool buf_read(struct buffer *src, void *dest, int size)
Definition: buffer.h:783
int seq_id
Highest fragmentation sequence ID of the packets currently being reassembled.
Definition: fragment.h:96
#define FRAME_HEADROOM_ADJ(f, fm)
Definition: mtu.h:188
#define FRAG_SEQ_ID_MASK
Bit mask for fragment sequence ID.
Definition: fragment.h:229
list flags
int len
Length in bytes of the actual content within the allocated memory.
Definition: buffer.h:66
#define FRAG_TYPE_SHIFT
Bit shift for fragment type info.
Definition: fragment.h:206
#define FRAG_SIZE_ROUND_SHIFT
Bit shift for fragment size rounding.
Definition: fragment.h:251
unsigned int map
Reassembly map for recording which fragments have been received.
Definition: fragment.h:74
struct event_timeout wakeup
Timeout structure used by the main event loop to know when to do fragmentation housekeeping.
Definition: fragment.h:137
#define BUF_SIZE(f)
Definition: mtu.h:194
#define FRAG_ID_MASK
Bit mask for fragment ID.
Definition: fragment.h:233
#define FRAME_HEADROOM_MARKER_FRAGMENT
Definition: mtu.h:130
void fragment_wakeup(struct fragment_master *f, struct frame *frame)
Definition: fragment.c:433
#define FRAG_SIZE_SHIFT
Bit shift for fragment size.
Definition: fragment.h:249
string f
Definition: http-client.py:6
time_t now
Definition: otime.c:36
static int optimal_fragment_size(int len, int max_frag_size)
Definition: fragment.c:306
#define ALLOC_OBJ_CLEAR(dptr, type)
Definition: buffer.h:1026
#define FRAME_HEADROOM(f)
Definition: mtu.h:187
static void fragment_list_buf_free(struct fragment_list *list)
Definition: fragment.c:52
#define FRAG_SIZE_MASK
Bit mask for fragment size.
Definition: fragment.h:247
struct fragment fragments[N_FRAG_BUF]
Array of reassembly structures, each can contain one whole packet.
Definition: fragment.h:114
#define D_FRAG_DEBUG
Definition: errlevel.h:120
List of fragment structures for reassembling multiple incoming packets concurrently.
Definition: fragment.h:95
static struct fragment * fragment_list_get_buf(struct fragment_list *list, int seq_id)
Definition: fragment.c:66
#define N_SEQ_ID
One more than the maximum fragment sequence ID, above which the IDs wrap to zero. ...
Definition: fragment.h:142
struct buffer outgoing
Buffer containing the remaining parts of the fragmented packet being sent.
Definition: fragment.h:172
int index
Index of the packet being reassembled with the highest fragmentation sequence ID into the fragment_li...
Definition: fragment.h:99
static void fragment_prepend_flags(struct buffer *buf, int type, int seq_id, int frag_id, int frag_size)
Definition: fragment.c:265
static bool buf_copy(struct buffer *dest, const struct buffer *src)
Definition: buffer.h:717
#define PAYLOAD_SIZE_DYNAMIC(f)
Definition: mtu.h:166
#define dmsg
Definition: error.h:174
static void fragment_list_buf_init(struct fragment_list *list, const struct frame *frame)
Definition: fragment.c:42
#define FRAG_MAP_MASK
Mask for reassembly map.
Definition: fragment.h:71
uint32_t fragment_header_type
Fragmentation information is stored in a 32-bit packet header.
Definition: fragment.h:190
static bool buf_copy_range(struct buffer *dest, int dest_index, const struct buffer *src, int src_index, int src_len)
Definition: buffer.h:734
static bool buf_copy_n(struct buffer *dest, struct buffer *src, int n)
Definition: buffer.h:723
#define FRAG_WHOLE
Fragment type indicating packet is whole.
Definition: fragment.h:208
#define msg
Definition: error.h:173
#define FRAG_TEST
Fragment type not implemented yet.
Definition: fragment.h:221
Wrapper structure for dynamically allocated memory.
Definition: buffer.h:60
#define buf_init(buf, offset)
Definition: buffer.h:196
static bool buf_write_prepend(struct buffer *dest, const void *src, int size)
Definition: buffer.h:684
struct buffer buf
Buffer in which received datagrams are reassembled.
Definition: fragment.h:86
void fragment_frame_init(struct fragment_master *f, const struct frame *frame)
Allocate internal packet buffers for a fragment_master structure.
Definition: fragment.c:126
static int min_int(int x, int y)
Definition: integer.h:47
void fragment_free(struct fragment_master *f)
Free a fragment_master structure and its internal packet buffers.
Definition: fragment.c:117
#define free
Definition: cmocka.c:1850
struct fragment_master * fragment_init(struct frame *frame)
Allocate and initialize a fragment_master structure.
Definition: fragment.c:90
long int get_random(void)
Definition: crypto.c:1761
#define N_FRAG_BUF
Number of packet buffers for reassembling incoming fragmented packets.
Definition: fragment.h:49
void fragment_incoming(struct fragment_master *f, struct buffer *buf, const struct frame *frame)
Process an incoming packet, which may or may not be fragmented.
Definition: fragment.c:140
#define FRAG_SIZE_ROUND_MASK
Bit mask for fragment size rounding.
Definition: fragment.h:252
Data Channel Fragmentation module header file.
#define D_FRAG_ERRORS
Definition: errlevel.h:69
struct buffer outgoing_return
Buffer used by fragment_ready_to_send() to return a part to send.
Definition: fragment.h:174
static void event_timeout_init(struct event_timeout *et, interval_t n, const time_t local_now)
Definition: interval.h:166
#define FRAG_TTL_SEC
Time-to-live in seconds for a fragment.
Definition: fragment.h:54
time_t timestamp
Timestamp for time-to-live purposes.
Definition: fragment.h:84