source: mainline/uspace/srv/net/tcp/seq_no.c@ ca48672

/*
 * 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;
}

/**
 * @}
 */