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