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