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
8 * Copyright (C) 2002-2024 OpenVPN Inc <sales@openvpn.net>
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.
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.
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.
25 * These routines implement a reliability layer on top of UDP,
26 * so that SSL/TLS can be run over UDP.
42 /* calculates test - base while allowing for base or test wraparound. test is
43 * assumed to be higher than base */
44 static inline packet_id_type
45 subtract_pid(const packet_id_type test
, const packet_id_type base
)
51 * verify that test - base < extent while allowing for base or test wraparound
54 reliable_pid_in_range1(const packet_id_type test
,
55 const packet_id_type base
,
56 const unsigned int extent
)
58 return subtract_pid(test
, base
) < extent
;
62 * verify that test < base + extent while allowing for base or test wraparound
65 reliable_pid_in_range2(const packet_id_type test
,
66 const packet_id_type base
,
67 const unsigned int extent
)
69 if (base
+ extent
>= base
)
71 if (test
< base
+ extent
)
78 if ((test
+0x80000000u
) < (base
+0x80000000u
) + extent
)
88 * verify that p1 < p2 while allowing for p1 or p2 wraparound
91 reliable_pid_min(const packet_id_type p1
,
92 const packet_id_type p2
)
94 return !reliable_pid_in_range1(p1
, p2
, 0x80000000u
);
97 /* check if a particular packet_id is present in ack */
99 reliable_ack_packet_id_present(struct reliable_ack
*ack
, packet_id_type pid
)
102 for (i
= 0; i
< ack
->len
; ++i
)
104 if (ack
->packet_id
[i
] == pid
)
112 /* get a packet_id from buf */
114 reliable_ack_read_packet_id(struct buffer
*buf
, packet_id_type
*pid
)
116 packet_id_type net_pid
;
118 if (buf_read(buf
, &net_pid
, sizeof(net_pid
)))
120 *pid
= ntohpid(net_pid
);
121 dmsg(D_REL_DEBUG
, "ACK read ID " packet_id_format
" (buf->len=%d)",
122 (packet_id_print_type
)*pid
, buf
->len
);
126 dmsg(D_REL_LOW
, "ACK read ID FAILED (buf->len=%d)", buf
->len
);
130 /* acknowledge a packet_id by adding it to a struct reliable_ack */
132 reliable_ack_acknowledge_packet_id(struct reliable_ack
*ack
, packet_id_type pid
)
134 if (!reliable_ack_packet_id_present(ack
, pid
) && ack
->len
< RELIABLE_ACK_SIZE
)
136 ack
->packet_id
[ack
->len
++] = pid
;
137 dmsg(D_REL_DEBUG
, "ACK acknowledge ID " packet_id_format
" (ack->len=%d)",
138 (packet_id_print_type
)pid
, ack
->len
);
142 dmsg(D_REL_LOW
, "ACK acknowledge ID " packet_id_format
" FAILED (ack->len=%d)",
143 (packet_id_print_type
)pid
, ack
->len
);
149 reliable_ack_read(struct reliable_ack
*ack
,
150 struct buffer
*buf
, const struct session_id
*sid
)
152 struct session_id session_id_remote
;
154 if (!reliable_ack_parse(buf
, ack
, &session_id_remote
))
159 if (ack
->len
>= 1 && (!session_id_defined(&session_id_remote
)
160 || !session_id_equal(&session_id_remote
, sid
)))
162 struct gc_arena gc
= gc_new();
164 "ACK read BAD SESSION-ID FROM REMOTE, local=%s, remote=%s",
165 session_id_print(sid
, &gc
), session_id_print(&session_id_remote
, &gc
));
173 reliable_ack_parse(struct buffer
*buf
, struct reliable_ack
*ack
,
174 struct session_id
*session_id_remote
)
179 if (!buf_read(buf
, &count
, sizeof(count
)))
183 for (int i
= 0; i
< count
; ++i
)
185 packet_id_type net_pid
;
186 if (!buf_read(buf
, &net_pid
, sizeof(net_pid
)))
190 if (ack
->len
>= RELIABLE_ACK_SIZE
)
194 packet_id_type pid
= ntohpid(net_pid
);
195 ack
->packet_id
[ack
->len
++] = pid
;
199 if (!session_id_read(session_id_remote
, buf
))
208 * Copies the first n acks from \c ack to \c ack_mru
211 copy_acks_to_mru(struct reliable_ack
*ack
, struct reliable_ack
*ack_mru
, int n
)
213 ASSERT(ack
->len
>= n
);
214 /* This loop is backward to ensure the same order as in ack */
215 for (int i
= n
-1; i
>= 0; i
--)
217 packet_id_type id
= ack
->packet_id
[i
];
219 /* Handle special case of ack_mru empty */
220 if (ack_mru
->len
== 0)
223 ack_mru
->packet_id
[0] = id
;
226 bool idfound
= false;
228 /* Move all existing entries one to the right */
229 packet_id_type move
= id
;
231 for (int j
= 0; j
< ack_mru
->len
; j
++)
233 packet_id_type tmp
= ack_mru
->packet_id
[j
];
234 ack_mru
->packet_id
[j
] = move
;
244 if (!idfound
&& ack_mru
->len
< RELIABLE_ACK_SIZE
)
246 ack_mru
->packet_id
[ack_mru
->len
] = move
;
252 /* write a packet ID acknowledgement record to buf, */
253 /* removing all acknowledged entries from ack */
255 reliable_ack_write(struct reliable_ack
*ack
,
256 struct reliable_ack
*ack_mru
,
258 const struct session_id
*sid
, int max
, bool prepend
)
270 copy_acks_to_mru(ack
, ack_mru
, n
);
272 /* Number of acks we can resend that still fit into the packet */
273 uint8_t total_acks
= min_int(max
, ack_mru
->len
);
275 sub
= buf_sub(buf
, ACK_SIZE(total_acks
), prepend
);
280 ASSERT(buf_write_u8(&sub
, total_acks
));
282 /* Write the actual acks to the packets. Since we copied the acks that
283 * are going out now already to the front of ack_mru we can fetch all
284 * acks from ack_mru */
285 for (i
= 0; i
< total_acks
; ++i
)
287 packet_id_type pid
= ack_mru
->packet_id
[i
];
288 packet_id_type net_pid
= htonpid(pid
);
289 ASSERT(buf_write(&sub
, &net_pid
, sizeof(net_pid
)));
290 dmsg(D_REL_DEBUG
, "ACK write ID " packet_id_format
" (ack->len=%d, n=%d)", (packet_id_print_type
)pid
, ack
->len
, n
);
294 ASSERT(session_id_defined(sid
));
295 ASSERT(session_id_write(sid
, &sub
));
299 for (i
= 0, j
= n
; j
< ack
->len
; )
301 ack
->packet_id
[i
++] = ack
->packet_id
[j
++];
312 /* print a reliable ACK record coming off the wire */
314 reliable_ack_print(struct buffer
*buf
, bool verbose
, struct gc_arena
*gc
)
318 struct session_id sid_ack
;
320 struct buffer out
= alloc_buf_gc(256, gc
);
322 buf_printf(&out
, "[");
323 if (!buf_read(buf
, &n_ack
, sizeof(n_ack
)))
327 for (i
= 0; i
< n_ack
; ++i
)
329 if (!buf_read(buf
, &pid
, sizeof(pid
)))
334 buf_printf(&out
, " " packet_id_format
, (packet_id_print_type
)pid
);
338 if (!session_id_read(&sid_ack
, buf
))
344 buf_printf(&out
, " sid=%s", session_id_print(&sid_ack
, gc
));
349 buf_printf(&out
, " ]");
354 * struct reliable member functions.
358 reliable_init(struct reliable
*rel
, int buf_size
, int offset
, int array_size
, bool hold
)
363 ASSERT(array_size
> 0 && array_size
<= RELIABLE_CAPACITY
);
365 rel
->size
= array_size
;
366 rel
->offset
= offset
;
367 for (i
= 0; i
< rel
->size
; ++i
)
369 struct reliable_entry
*e
= &rel
->array
[i
];
370 e
->buf
= alloc_buf(buf_size
);
371 ASSERT(buf_init(&e
->buf
, offset
));
376 reliable_free(struct reliable
*rel
)
383 for (i
= 0; i
< rel
->size
; ++i
)
385 struct reliable_entry
*e
= &rel
->array
[i
];
391 /* no active buffers? */
393 reliable_empty(const struct reliable
*rel
)
396 for (i
= 0; i
< rel
->size
; ++i
)
398 const struct reliable_entry
*e
= &rel
->array
[i
];
407 /* del acknowledged items from send buf */
409 reliable_send_purge(struct reliable
*rel
, const struct reliable_ack
*ack
)
412 for (i
= 0; i
< ack
->len
; ++i
)
414 packet_id_type pid
= ack
->packet_id
[i
];
415 for (j
= 0; j
< rel
->size
; ++j
)
417 struct reliable_entry
*e
= &rel
->array
[j
];
418 if (e
->active
&& e
->packet_id
== pid
)
421 "ACK received for pid " packet_id_format
", deleting from send buffer",
422 (packet_id_print_type
)pid
);
424 /* DEBUGGING -- how close were we timing out on ACK failure and resending? */
428 const interval_t wake
= e
->next_try
- now
;
429 msg(M_INFO
, "ACK " packet_id_format
", wake=%d", pid
, wake
);
435 else if (e
->active
&& e
->packet_id
< pid
)
437 /* We have received an ACK for a packet with a higher PID. Either
438 * we have received ACKs out of or order or the packet has been
439 * lost. We count the number of ACKs to determine if we should
440 * resend it early. */
448 /* print the current sequence of active packet IDs */
450 reliable_print_ids(const struct reliable
*rel
, struct gc_arena
*gc
)
452 struct buffer out
= alloc_buf_gc(256, gc
);
455 buf_printf(&out
, "[" packet_id_format
"]", (packet_id_print_type
)rel
->packet_id
);
456 for (i
= 0; i
< rel
->size
; ++i
)
458 const struct reliable_entry
*e
= &rel
->array
[i
];
461 buf_printf(&out
, " " packet_id_format
, (packet_id_print_type
)e
->packet_id
);
466 #endif /* ENABLE_DEBUG */
468 /* true if at least one free buffer available */
470 reliable_can_get(const struct reliable
*rel
)
472 struct gc_arena gc
= gc_new();
474 for (i
= 0; i
< rel
->size
; ++i
)
476 const struct reliable_entry
*e
= &rel
->array
[i
];
482 dmsg(D_REL_LOW
, "ACK no free receive buffer available: %s", reliable_print_ids(rel
, &gc
));
487 /* make sure that incoming packet ID isn't a replay */
489 reliable_not_replay(const struct reliable
*rel
, packet_id_type id
)
491 struct gc_arena gc
= gc_new();
493 if (reliable_pid_min(id
, rel
->packet_id
))
497 for (i
= 0; i
< rel
->size
; ++i
)
499 const struct reliable_entry
*e
= &rel
->array
[i
];
500 if (e
->active
&& e
->packet_id
== id
)
509 dmsg(D_REL_DEBUG
, "ACK " packet_id_format
" is a replay: %s", (packet_id_print_type
)id
, reliable_print_ids(rel
, &gc
));
514 /* make sure that incoming packet ID won't deadlock the receive buffer */
516 reliable_wont_break_sequentiality(const struct reliable
*rel
, packet_id_type id
)
518 struct gc_arena gc
= gc_new();
520 const int ret
= reliable_pid_in_range2(id
, rel
->packet_id
, rel
->size
);
524 dmsg(D_REL_LOW
, "ACK " packet_id_format
" breaks sequentiality: %s",
525 (packet_id_print_type
)id
, reliable_print_ids(rel
, &gc
));
528 dmsg(D_REL_DEBUG
, "ACK RWBS rel->size=%d rel->packet_id=%08x id=%08x ret=%d", rel
->size
, rel
->packet_id
, id
, ret
);
534 /* grab a free buffer */
536 reliable_get_buf(struct reliable
*rel
)
539 for (i
= 0; i
< rel
->size
; ++i
)
541 struct reliable_entry
*e
= &rel
->array
[i
];
544 ASSERT(buf_init(&e
->buf
, rel
->offset
));
552 reliable_get_num_output_sequenced_available(struct reliable
*rel
)
554 struct gc_arena gc
= gc_new();
555 packet_id_type min_id
= 0;
556 bool min_id_defined
= false;
558 /* find minimum active packet_id */
559 for (int i
= 0; i
< rel
->size
; ++i
)
561 const struct reliable_entry
*e
= &rel
->array
[i
];
564 if (!min_id_defined
|| reliable_pid_min(e
->packet_id
, min_id
))
566 min_id_defined
= true;
567 min_id
= e
->packet_id
;
575 ret
-= subtract_pid(rel
->packet_id
, min_id
);
581 /* grab a free buffer, fail if buffer clogged by unacknowledged low packet IDs */
583 reliable_get_buf_output_sequenced(struct reliable
*rel
)
585 struct gc_arena gc
= gc_new();
587 packet_id_type min_id
= 0;
588 bool min_id_defined
= false;
589 struct buffer
*ret
= NULL
;
591 /* find minimum active packet_id */
592 for (i
= 0; i
< rel
->size
; ++i
)
594 const struct reliable_entry
*e
= &rel
->array
[i
];
597 if (!min_id_defined
|| reliable_pid_min(e
->packet_id
, min_id
))
599 min_id_defined
= true;
600 min_id
= e
->packet_id
;
605 if (!min_id_defined
|| reliable_pid_in_range1(rel
->packet_id
, min_id
, rel
->size
))
607 ret
= reliable_get_buf(rel
);
611 dmsg(D_REL_LOW
, "ACK output sequence broken: %s", reliable_print_ids(rel
, &gc
));
617 /* get active buffer for next sequentially increasing key ID */
618 struct reliable_entry
*
619 reliable_get_entry_sequenced(struct reliable
*rel
)
622 for (i
= 0; i
< rel
->size
; ++i
)
624 struct reliable_entry
*e
= &rel
->array
[i
];
625 if (e
->active
&& e
->packet_id
== rel
->packet_id
)
633 /* return true if reliable_send would return a non-NULL result */
635 reliable_can_send(const struct reliable
*rel
)
637 struct gc_arena gc
= gc_new();
639 int n_active
= 0, n_current
= 0;
640 for (i
= 0; i
< rel
->size
; ++i
)
642 const struct reliable_entry
*e
= &rel
->array
[i
];
646 if (now
>= e
->next_try
|| e
->n_acks
>= N_ACK_RETRANSMIT
)
652 dmsg(D_REL_DEBUG
, "ACK reliable_can_send active=%d current=%d : %s",
655 reliable_print_ids(rel
, &gc
));
658 return n_current
> 0 && !rel
->hold
;
661 /* return next buffer to send to remote */
663 reliable_send(struct reliable
*rel
, int *opcode
)
666 struct reliable_entry
*best
= NULL
;
667 const time_t local_now
= now
;
669 for (i
= 0; i
< rel
->size
; ++i
)
671 struct reliable_entry
*e
= &rel
->array
[i
];
673 /* If N_ACK_RETRANSMIT later packets have received ACKs, we assume
674 * that the packet was lost and resend it even if the timeout has
675 * not expired yet. */
677 && (e
->n_acks
>= N_ACK_RETRANSMIT
|| local_now
>= e
->next_try
))
679 if (!best
|| reliable_pid_min(e
->packet_id
, best
->packet_id
))
687 /* exponential backoff */
688 best
->next_try
= local_now
+ best
->timeout
;
691 *opcode
= best
->opcode
;
692 dmsg(D_REL_DEBUG
, "ACK reliable_send ID " packet_id_format
" (size=%d to=%d)",
693 (packet_id_print_type
)best
->packet_id
, best
->buf
.len
,
694 (int)(best
->next_try
- local_now
));
700 /* schedule all pending packets for immediate retransmit */
702 reliable_schedule_now(struct reliable
*rel
)
705 dmsg(D_REL_DEBUG
, "ACK reliable_schedule_now");
707 for (i
= 0; i
< rel
->size
; ++i
)
709 struct reliable_entry
*e
= &rel
->array
[i
];
713 e
->timeout
= rel
->initial_timeout
;
718 /* in how many seconds should we wake up to check for timeout */
719 /* if we return BIG_TIMEOUT, nothing to wait for */
721 reliable_send_timeout(const struct reliable
*rel
)
723 struct gc_arena gc
= gc_new();
724 interval_t ret
= BIG_TIMEOUT
;
726 const time_t local_now
= now
;
728 for (i
= 0; i
< rel
->size
; ++i
)
730 const struct reliable_entry
*e
= &rel
->array
[i
];
733 if (e
->next_try
<= local_now
)
740 ret
= min_int(ret
, e
->next_try
- local_now
);
745 dmsg(D_REL_DEBUG
, "ACK reliable_send_timeout %d %s",
747 reliable_print_ids(rel
, &gc
));
754 * Enable an incoming buffer previously returned by a get function as active.
758 reliable_mark_active_incoming(struct reliable
*rel
, struct buffer
*buf
,
759 packet_id_type pid
, int opcode
)
762 for (i
= 0; i
< rel
->size
; ++i
)
764 struct reliable_entry
*e
= &rel
->array
[i
];
769 /* packets may not arrive in sequential order */
772 /* check for replay */
773 ASSERT(!reliable_pid_min(pid
, rel
->packet_id
));
779 dmsg(D_REL_DEBUG
, "ACK mark active incoming ID " packet_id_format
, (packet_id_print_type
)e
->packet_id
);
783 ASSERT(0); /* buf not found in rel */
787 * Enable an outgoing buffer previously returned by a get function as active.
791 reliable_mark_active_outgoing(struct reliable
*rel
, struct buffer
*buf
, int opcode
)
794 for (i
= 0; i
< rel
->size
; ++i
)
796 struct reliable_entry
*e
= &rel
->array
[i
];
799 /* Write mode, increment packet_id (i.e. sequence number)
800 * linearly and prepend id to packet */
801 packet_id_type net_pid
;
802 e
->packet_id
= rel
->packet_id
++;
803 net_pid
= htonpid(e
->packet_id
);
804 ASSERT(buf_write_prepend(buf
, &net_pid
, sizeof(net_pid
)));
808 e
->timeout
= rel
->initial_timeout
;
809 dmsg(D_REL_DEBUG
, "ACK mark active outgoing ID " packet_id_format
, (packet_id_print_type
)e
->packet_id
);
813 ASSERT(0); /* buf not found in rel */
816 /* delete a buffer previously activated by reliable_mark_active() */
818 reliable_mark_deleted(struct reliable
*rel
, struct buffer
*buf
)
821 for (i
= 0; i
< rel
->size
; ++i
)
823 struct reliable_entry
*e
= &rel
->array
[i
];
827 rel
->packet_id
= e
->packet_id
+ 1;
837 reliable_ack_debug_print(const struct reliable_ack
*ack
, char *desc
)
841 printf("********* struct reliable_ack %s\n", desc
);
842 for (i
= 0; i
< ack
->len
; ++i
)
844 printf(" %d: " packet_id_format
"\n", i
, (packet_id_print_type
) ack
->packet_id
[i
]);
849 reliable_debug_print(const struct reliable
*rel
, char *desc
)
854 printf("********* struct reliable %s\n", desc
);
855 printf(" initial_timeout=%d\n", (int)rel
->initial_timeout
);
856 printf(" packet_id=" packet_id_format
"\n", rel
->packet_id
);
857 printf(" now=%" PRIi64
"\n", (int64_t)now
);
858 for (i
= 0; i
< rel
->size
; ++i
)
860 const struct reliable_entry
*e
= &rel
->array
[i
];
863 printf(" %d: packet_id=" packet_id_format
" len=%d", i
, e
->packet_id
, e
->buf
.len
);
864 printf(" next_try=%" PRIi64
, (int64_t)e
->next_try
);