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-2026 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, see <https://www.gnu.org/licenses/>.
21 */
22
23#ifdef HAVE_CONFIG_H
24#include "config.h"
25#endif
26
27#include "syshead.h"
28
29#ifdef ENABLE_FRAGMENT
30
31#include "crypto.h"
32#include "misc.h"
33#include "fragment.h"
34#include "integer.h"
35#include "memdbg.h"
36
37#define FRAG_ERR(s) \
38 { \
39 errmsg = s; \
40 goto error; \
41 }
42
43#if defined(__GNUC__) || defined(__clang__)
44#pragma GCC diagnostic push
45#pragma GCC diagnostic ignored "-Wsign-conversion"
46#endif
47
48static void
49fragment_list_buf_init(struct fragment_list *list, const struct frame *frame)
50{
51 int i;
52 for (i = 0; i < N_FRAG_BUF; ++i)
53 {
55 }
56}
57
58static void
60{
61 int i;
62 for (i = 0; i < N_FRAG_BUF; ++i)
63 {
64 free_buf(&list->fragments[i].buf);
65 }
66}
67
68/*
69 * Given a sequence ID number, get a fragment buffer. Use a sliding window,
70 * similar to packet_id code.
71 */
72static struct fragment *
73fragment_list_get_buf(struct fragment_list *list, int seq_id)
74{
75 int diff;
76 if (abs(diff = modulo_subtract(seq_id, list->seq_id, N_SEQ_ID)) >= N_FRAG_BUF)
77 {
78 int i;
79 for (i = 0; i < N_FRAG_BUF; ++i)
80 {
81 list->fragments[i].defined = false;
82 }
83 list->index = 0;
84 list->seq_id = seq_id;
85 diff = 0;
86 }
87 while (diff > 0)
88 {
89 list->fragments[list->index = modulo_add(list->index, 1, N_FRAG_BUF)].defined = false;
90 list->seq_id = modulo_add(list->seq_id, 1, N_SEQ_ID);
91 --diff;
92 }
93 return &list->fragments[modulo_add(list->index, diff, N_FRAG_BUF)];
94}
95
96struct fragment_master *
98{
99 struct fragment_master *ret;
100
101 /* code that initializes other parts of
102 * fragment_master assume an initial CLEAR */
103 ALLOC_OBJ_CLEAR(ret, struct fragment_master);
104
105 /*
106 * Outgoing sequence ID is randomized to reduce
107 * the probability of sequence number collisions
108 * when openvpn sessions are restarted. This is
109 * not done out of any need for security, as all
110 * fragmentation control information resides
111 * inside of the encrypted/authenticated envelope.
112 */
113 ret->outgoing_seq_id = (int)get_random() & (N_SEQ_ID - 1);
114
116
117 return ret;
118}
119
120void
122{
124 free_buf(&f->outgoing);
126 free(f);
127}
128
129void
136
137/*
138 * Accept an incoming datagram (which may be a fragment) from remote.
139 * If the datagram is whole (i.e not a fragment), pass through.
140 * If the datagram is a fragment, join with other fragments received so far.
141 * If a fragment fully completes the datagram, return the datagram.
142 */
143void
144fragment_incoming(struct fragment_master *f, struct buffer *buf, const struct frame *frame)
145{
146 const char *errmsg = NULL;
147 fragment_header_type flags = 0;
148 int frag_type = 0;
149
150 if (buf->len > 0)
151 {
152 /* get flags from packet head */
153 if (!buf_read(buf, &flags, sizeof(flags)))
154 {
155 FRAG_ERR("flags not found in packet");
156 }
157 flags = ntoh_fragment_header_type(flags);
158
159 /* get fragment type from flags */
160 frag_type = ((flags >> FRAG_TYPE_SHIFT) & FRAG_TYPE_MASK);
161
162#if 0
163 /*
164 * If you want to extract FRAG_EXTRA_MASK/FRAG_EXTRA_SHIFT bits,
165 * do it here.
166 */
167 if (frag_type == FRAG_WHOLE || frag_type == FRAG_YES_NOTLAST)
168 {
169 }
170#endif
171
172 /* handle the fragment type */
173 if (frag_type == FRAG_WHOLE)
174 {
175 dmsg(D_FRAG_DEBUG, "FRAG_IN buf->len=%d type=FRAG_WHOLE flags=" fragment_header_format,
176 buf->len, flags);
177
178 if (flags & (FRAG_SEQ_ID_MASK | FRAG_ID_MASK))
179 {
180 FRAG_ERR("spurious 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 =
188 ((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
195 dmsg(
197 "FRAG_IN len=%d type=%d seq_id=%d frag_id=%d size=%d flags=" fragment_header_format,
198 buf->len, frag_type, seq_id, n, size, 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
250error:
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 */
260static void
261fragment_prepend_flags(struct buffer *buf, int type, int seq_id, int frag_id, int frag_size)
262{
264 | ((seq_id & FRAG_SEQ_ID_MASK) << FRAG_SEQ_ID_SHIFT)
265 | ((frag_id & FRAG_ID_MASK) << FRAG_ID_SHIFT);
266
267 if (type == FRAG_WHOLE || type == FRAG_YES_NOTLAST)
268 {
269 /*
270 * If you want to set FRAG_EXTRA_MASK/FRAG_EXTRA_SHIFT bits,
271 * do it here.
272 */
273 dmsg(
275 "FRAG_OUT len=%d type=%d seq_id=%d frag_id=%d frag_size=%d flags=" fragment_header_format,
276 buf->len, type, seq_id, frag_id, frag_size, flags);
277 }
278 else
279 {
280 flags |= (((frag_size >> FRAG_SIZE_ROUND_SHIFT) & FRAG_SIZE_MASK) << FRAG_SIZE_SHIFT);
281
282 dmsg(
284 "FRAG_OUT len=%d type=%d seq_id=%d frag_id=%d frag_size=%d flags=" fragment_header_format,
285 buf->len, type, seq_id, frag_id, frag_size, flags);
286 }
287
288 flags = hton_fragment_header_type(flags);
289 ASSERT(buf_write_prepend(buf, &flags, sizeof(flags)));
290}
291
292#if defined(__GNUC__) || defined(__clang__)
293#pragma GCC diagnostic pop
294#endif
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 */
301static 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,
311 (max_frag_size - ((max_frag_size - mod) / (div + 1)) + FRAG_SIZE_ROUND_MASK)
313 }
314 else
315 {
316 return mfs_aligned;
317 }
318}
319
320/* process an outgoing datagram, possibly breaking it up into fragments */
321void
322fragment_outgoing(struct fragment_master *f, struct buffer *buf, 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]", buf->len,
331 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 */
340 {
341 FRAG_ERR("too many fragments would be required to send datagram");
342 }
346 f->outgoing_frag_id = 0;
347 buf->len = 0;
349 }
350 else
351 {
352 /*
353 * Send the datagram whole.
354 */
356 }
357 }
358 return;
359
360error:
361 if (errmsg)
362 {
363 msg(D_FRAG_ERRORS, "FRAG_OUT error, len=%d frag_size=%d MAX_FRAGS=%d: %s", buf->len,
364 f->outgoing_frag_size, MAX_FRAGS, errmsg);
365 }
366 buf->len = 0;
367 return;
368}
369
370/* return true (and set buf) if we have an outgoing fragment which is ready to send */
371bool
372fragment_ready_to_send(struct fragment_master *f, struct buffer *buf, const struct frame *frame)
373{
375 {
376 /* get fragment size, and determine if it is the last fragment */
377 int size = f->outgoing_frag_size;
378 int last = false;
379 if (f->outgoing.len <= size)
380 {
381 size = f->outgoing.len;
382 last = true;
383 }
384
385 /* initialize return buffer */
386 *buf = f->outgoing_return;
388 ASSERT(buf_copy_n(buf, &f->outgoing, size));
389
390 /* fragment flags differ based on whether or not we are sending the last fragment */
393
394 ASSERT(!last
395 || !f->outgoing
396 .len); /* outgoing buffer length should be zero after last fragment sent */
397
398 return true;
399 }
400 else
401 {
402 return false;
403 }
404}
405
406static void
408{
409 int i;
410 for (i = 0; i < N_FRAG_BUF; ++i)
411 {
412 struct fragment *frag = &f->incoming.fragments[i];
413 if (frag->defined && frag->timestamp + FRAG_TTL_SEC <= now)
414 {
415 msg(D_FRAG_ERRORS, "FRAG TTL expired i=%d", i);
416 frag->defined = false;
417 }
418 }
419}
420
421/* called every FRAG_WAKEUP_INTERVAL seconds */
422void
424{
425 /* delete fragments with expired TTLs */
427}
428#endif /* ifdef ENABLE_FRAGMENT */
void free_buf(struct buffer *buf)
Free the memory allocated for a buffer.
Definition buffer.c:174
struct buffer alloc_buf(size_t size)
Allocate a buffer of the given size.
Definition buffer.c:60
static bool buf_copy(struct buffer *dest, const struct buffer *src)
Copy the content of one buffer to the end of another.
Definition buffer.h:1347
static bool buf_write_prepend(struct buffer *dest, const void *src, int size)
Prepend data to a buffer.
Definition buffer.h:1268
static bool buf_copy_n(struct buffer *dest, struct buffer *src, int n)
Read n bytes from src and append them to dest.
Definition buffer.h:1365
static bool buf_read(struct buffer *src, void *dest, int size)
Read bytes from the front of a buffer into a caller-supplied destination.
Definition buffer.h:1456
static bool buf_copy_range(struct buffer *dest, int dest_index, const struct buffer *src, int src_index, int src_len)
Copy a range of bytes from one buffer into a specific position in another.
Definition buffer.h:1392
#define ALLOC_OBJ_CLEAR(dptr, type)
Allocate and zero-initialise memory for a single object of the given type.
Definition buffer.h:2036
#define buf_init(buf, offset)
Definition buffer.h:364
#define fragment_header_format
Definition common.h:52
int64_t get_random(void)
an analogue to the random() function, but use prng_bytes and also int64_t instead of long to avoid LL...
Definition crypto.c:1703
Data Channel Cryptography Module.
#define D_FRAG_ERRORS
Definition errlevel.h:67
#define D_FRAG_DEBUG
Definition errlevel.h:121
static void fragment_ttl_reap(struct fragment_master *f)
Definition fragment.c:407
static void fragment_prepend_flags(struct buffer *buf, int type, int seq_id, int frag_id, int frag_size)
Definition fragment.c:261
#define FRAG_ERR(s)
Definition fragment.c:37
static struct fragment * fragment_list_get_buf(struct fragment_list *list, int seq_id)
Definition fragment.c:73
static int optimal_fragment_size(int len, int max_frag_size)
Definition fragment.c:302
static void fragment_list_buf_free(struct fragment_list *list)
Definition fragment.c:59
static void fragment_list_buf_init(struct fragment_list *list, const struct frame *frame)
Definition fragment.c:49
Data Channel Fragmentation module header file.
#define MAX_FRAGS
Maximum number of fragments per packet.
Definition fragment.h:73
#define N_SEQ_ID
One more than the maximum fragment sequence ID, above which the IDs wrap to zero.
Definition fragment.h:144
#define FRAG_MAP_MASK
Mask for reassembly map.
Definition fragment.h:71
#define FRAG_SIZE_MASK
Bit mask for fragment size.
Definition fragment.h:231
#define hton_fragment_header_type(x)
Convert a fragment_header_type from host to network order.
Definition fragment.h:194
#define FRAG_TTL_SEC
Time-to-live in seconds for a fragment.
Definition fragment.h:53
#define FRAG_SEQ_ID_SHIFT
Bit shift for fragment sequence ID.
Definition fragment.h:216
#define FRAG_SEQ_ID_MASK
Bit mask for fragment sequence ID.
Definition fragment.h:215
#define FRAG_SIZE_ROUND_MASK
Bit mask for fragment size rounding.
Definition fragment.h:234
uint32_t fragment_header_type
Fragmentation information is stored in a 32-bit packet header.
Definition fragment.h:191
#define FRAG_TYPE_SHIFT
Bit shift for fragment type info.
Definition fragment.h:203
void fragment_frame_init(struct fragment_master *f, const struct frame *frame)
Allocate internal packet buffers for a fragment_master structure.
Definition fragment.c:130
#define FRAG_TEST
Fragment type not implemented yet.
Definition fragment.h:211
static bool fragment_outgoing_defined(struct fragment_master *f)
Check whether a fragment_master structure contains fragments ready to be sent.
Definition fragment.h:428
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:322
#define FRAG_YES_LAST
Fragment type indicating packet is the last part in the sequence of parts.
Definition fragment.h:209
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:144
#define FRAG_WHOLE
Fragment type indicating packet is whole.
Definition fragment.h:205
#define FRAG_ID_SHIFT
Bit shift for fragment ID.
Definition fragment.h:219
#define FRAG_SIZE_ROUND_SHIFT
Bit shift for fragment size rounding.
Definition fragment.h:233
#define FRAG_TYPE_MASK
Bit mask for fragment type info.
Definition fragment.h:202
#define N_FRAG_BUF
Number of packet buffers for reassembling incoming fragmented packets.
Definition fragment.h:48
#define FRAG_WAKEUP_INTERVAL
Interval in seconds between calls to wakeup code.
Definition fragment.h:56
void fragment_wakeup(struct fragment_master *f, struct frame *frame)
Definition fragment.c:423
struct fragment_master * fragment_init(struct frame *frame)
Allocate and initialize a fragment_master structure.
Definition fragment.c:97
#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:206
void fragment_free(struct fragment_master *f)
Free a fragment_master structure and its internal packet buffers.
Definition fragment.c:121
#define ntoh_fragment_header_type(x)
Convert a fragment_header_type from network to host order.
Definition fragment.h:198
#define FRAG_ID_MASK
Bit mask for fragment ID.
Definition fragment.h:218
#define FRAG_SIZE_SHIFT
Bit shift for fragment size.
Definition fragment.h:232
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:372
static int min_int(int x, int y)
Definition integer.h:105
static int modulo_subtract(int x, int y, int mod)
Definition integer.h:170
static int modulo_add(int x, int y, int mod)
Definition integer.h:185
static void event_timeout_init(struct event_timeout *et, interval_t n, const time_t last)
Initialises a timer struct.
Definition interval.h:172
#define BUF_SIZE(f)
Definition mtu.h:188
#define dmsg(flags,...)
Definition error.h:164
#define msg(flags,...)
Definition error.h:152
#define ASSERT(x)
Definition error.h:221
time_t now
Definition otime.c:33
Wrapper structure for dynamically allocated memory.
Definition buffer.h:71
int len
Length in bytes of the actual content within the allocated memory.
Definition buffer.h:76
List of fragment structures for reassembling multiple incoming packets concurrently.
Definition fragment.h:96
int seq_id
Highest fragmentation sequence ID of the packets currently being reassembled.
Definition fragment.h:100
int index
Index of the packet being reassembled with the highest fragmentation sequence ID into the fragment_li...
Definition fragment.h:105
struct fragment fragments[N_FRAG_BUF]
Array of reassembly structures, each can contain one whole packet.
Definition fragment.h:117
Fragmentation and reassembly state for one VPN tunnel instance.
Definition fragment.h:140
struct buffer outgoing
Buffer containing the remaining parts of the fragmented packet being sent.
Definition fragment.h:172
int outgoing_frag_id
The fragment ID of the next part to be sent.
Definition fragment.h:169
struct event_timeout wakeup
Timeout structure used by the main event loop to know when to do fragmentation housekeeping.
Definition fragment.h:141
struct fragment_list incoming
List of structures for reassembling incoming packets.
Definition fragment.h:179
int outgoing_seq_id
Fragment sequence ID of the current fragmented packet waiting to be sent.
Definition fragment.h:148
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
struct buffer outgoing_return
Buffer used by fragment_ready_to_send() to return a part to send.
Definition fragment.h:174
Structure for reassembling one incoming fragmented packet.
Definition fragment.h:65
int max_frag_size
Maximum size of each fragment.
Definition fragment.h:69
unsigned int map
Reassembly map for recording which fragments have been received.
Definition fragment.h:74
bool defined
Whether reassembly is currently taking place in this structure.
Definition fragment.h:66
time_t timestamp
Timestamp for time-to-live purposes.
Definition fragment.h:84
struct buffer buf
Buffer in which received datagrams are reassembled.
Definition fragment.h:86
Packet geometry parameters.
Definition mtu.h:113
struct frame::@074234134026241341315172337061247271261307273127 buf
int headroom
the headroom in the buffer, this is choosen to allow all potential header to be added before the pack...
Definition mtu.h:124
int max_fragment_size
The maximum size of a fragment.
Definition mtu.h:140