/* * Copyright (c) 2011 Jiri Svoboda * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * * - Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * - Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * - The name of the author may not be used to endorse or promote products * derived from this software without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ /** @addtogroup tcp * @{ */ /** * @file Sequence number computations */ #include <assert.h> #include <stdbool.h> #include <stdint.h> #include "seq_no.h" #include "tcp_type.h" /** a <= b < c modulo sequence space */ static bool seq_no_le_lt(uint32_t a, uint32_t b, uint32_t c) { if (a <= c) { return (a <= b) && (b < c); } else { return (b < c) || (a <= b); } } /** a < b <= c modulo sequence space */ static bool seq_no_lt_le(uint32_t a, uint32_t b, uint32_t c) { if (a <= c) { return (a < b) && (b <= c); } else { return (b <= c) || (a < b); } } /** Determine wheter ack is acceptable (new acknowledgement) */ bool seq_no_ack_acceptable(tcp_conn_t *conn, uint32_t seg_ack) { /* SND.UNA < SEG.ACK <= SND.NXT */ return seq_no_lt_le(conn->snd_una, seg_ack, conn->snd_nxt); } /** Determine wheter ack is duplicate. * * ACK is duplicate if it refers to a sequence number that has * aleady been acked (SEG.ACK <= SND.UNA). */ bool seq_no_ack_duplicate(tcp_conn_t *conn, uint32_t seg_ack) { uint32_t diff; /* * There does not seem to be a three-point comparison * equivalent of SEG.ACK < SND.UNA. Thus we do it * on a best-effort basis, based on the difference. * [-2^31, 0) means less-than, 0 means equal, [0, 2^31) * means greater-than. Less-than or equal means duplicate. */ diff = seg_ack - conn->snd_una; return diff == 0 || (diff & (0x1 << 31)) != 0; } /** Determine if sequence number is in receive window. */ bool seq_no_in_rcv_wnd(tcp_conn_t *conn, uint32_t sn) { return seq_no_le_lt(conn->rcv_nxt, sn, conn->rcv_nxt + conn->rcv_wnd); } /** Determine segment has new window update. * * Window update is new if either SND.WL1 < SEG.SEQ or * (SND.WL1 = SEG.SEQ and SND.WL2 <= SEG.ACK). */ bool seq_no_new_wnd_update(tcp_conn_t *conn, tcp_segment_t *seg) { bool n_seq, n_ack; assert(seq_no_segment_acceptable(conn, seg)); /* * We make use of the fact that the peer should not ACK anything * beyond our send window (we surely haven't sent that yet) * as we should have filtered those acks out. * We use SND.UNA+SND.WND as the third point of comparison. */ n_seq = seq_no_lt_le(conn->snd_wl1, seg->seq, conn->snd_una + conn->snd_wnd); n_ack = conn->snd_wl1 == seg->seq && seq_no_le_lt(conn->snd_wl2, seg->ack, conn->snd_una + conn->snd_wnd + 1); return n_seq || n_ack; } /** Determine if segment is ready for processing. * * Assuming segment is acceptable, a segment is ready if it intersects * RCV.NXT, that is we can process it immediately. */ bool seq_no_segment_ready(tcp_conn_t *conn, tcp_segment_t *seg) { assert(seq_no_segment_acceptable(conn, seg)); return seq_no_le_lt(seg->seq, conn->rcv_nxt, seg->seq + seg->len + 1); } /** Determine whether segment is fully acked. * * @param conn Connection * @param seg Segment * @param ack Last received ACK (i.e. SND.UNA) * * @return @c true if segment is fully acked, @c false otherwise */ bool seq_no_segment_acked(tcp_conn_t *conn, tcp_segment_t *seg, uint32_t ack) { assert(seg->len > 0); return seq_no_lt_le(seg->seq, seg->seq + seg->len, ack); } /** Determine whether initial SYN is acked. * * @param conn Connection * @return @c true if initial SYN is acked, @c false otherwise */ bool seq_no_syn_acked(tcp_conn_t *conn) { return seq_no_lt_le(conn->iss, conn->snd_una, conn->snd_nxt); } /** Determine whether segment overlaps the receive window. * * @param conn Connection * @param seg Segment * @return @c true if segment overlaps the receive window, @c false otherwise */ bool seq_no_segment_acceptable(tcp_conn_t *conn, tcp_segment_t *seg) { bool b_in, e_in; bool wb_in, we_in; /* Beginning of segment is inside window */ b_in = seq_no_le_lt(conn->rcv_nxt, seg->seq, conn->rcv_nxt + conn->rcv_wnd); /* End of segment is inside window */ e_in = seq_no_le_lt(conn->rcv_nxt, seg->seq + seg->len - 1, conn->rcv_nxt + conn->rcv_wnd); /* Beginning of window is inside segment */ wb_in = seq_no_le_lt(seg->seq, conn->rcv_nxt, seg->seq + seg->len); /* End of window is inside segment */ we_in = seq_no_le_lt(seg->seq, conn->rcv_nxt + conn->rcv_wnd - 1, seg->seq + seg->len); if (seg->len == 0 && conn->rcv_wnd == 0) { return seg->seq == conn->rcv_nxt; } else if (seg->len == 0 && conn->rcv_wnd != 0) { return b_in; } else if (seg->len > 0 && conn->rcv_wnd == 0) { return false; } else { return b_in || e_in || wb_in || we_in; } } /** Determine size that control bits occupy in sequence space. * * @param ctrl Control bits combination * @return Number of sequence space units occupied */ uint32_t seq_no_control_len(tcp_control_t ctrl) { uint32_t len = 0; if ((ctrl & CTL_SYN) != 0) ++len; if ((ctrl & CTL_FIN) != 0) ++len; return len; } /** Calculate the amount of trim needed to fit segment in receive window. * * @param conn Connection * @param seg Segment * @param left Place to store number of units to trim at the beginning * @param right Place to store number of units to trim at the end */ void seq_no_seg_trim_calc(tcp_conn_t *conn, tcp_segment_t *seg, uint32_t *left, uint32_t *right) { assert(seq_no_segment_acceptable(conn, seg)); /* * If RCV.NXT is between SEG.SEQ and RCV.NXT+RCV.WND, then * left trim amount is positive */ if (seq_no_lt_le(seg->seq, conn->rcv_nxt, conn->rcv_nxt + conn->rcv_wnd)) { *left = conn->rcv_nxt - seg->seq; } else { *left = 0; } /* * If SEG.SEQ+SEG.LEN is between SEG.SEQ and RCV.NXT+RCV.WND, * then right trim is zero. */ if (seq_no_lt_le(seg->seq - 1, seg->seq + seg->len, conn->rcv_nxt + conn->rcv_wnd)) { *right = 0; } else { *right = (seg->seq + seg->len) - (conn->rcv_nxt + conn->rcv_wnd); } } /** Segment order comparison. * * Compare sequence order of two acceptable segments. * * @param conn Connection * @param sa Segment A * @param sb Segment B * * @return -1, 0, 1, resp. if A < B, A == B, A > B in terms * of sequence order of the beginning of the segment. */ int seq_no_seg_cmp(tcp_conn_t *conn, tcp_segment_t *sa, tcp_segment_t *sb) { assert(seq_no_segment_acceptable(conn, sa)); assert(seq_no_segment_acceptable(conn, sb)); if (seq_no_lt_le(sa->seq, sb->seq, conn->rcv_nxt + conn->rcv_wnd)) return -1; if (seq_no_lt_le(sb->seq, sa->seq, conn->rcv_nxt + conn->rcv_wnd)) return +1; assert(sa->seq == sb->seq); return 0; } /** * @} */