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