lsquic_senhist.c revision 50aadb33
150aadb33SDmitri Tikhonov/* Copyright (c) 2017 LiteSpeed Technologies Inc.  See LICENSE. */
250aadb33SDmitri Tikhonov/*
350aadb33SDmitri Tikhonov * lsquic_senhist.c -- Sent history implementation
450aadb33SDmitri Tikhonov */
550aadb33SDmitri Tikhonov
650aadb33SDmitri Tikhonov#include <assert.h>
750aadb33SDmitri Tikhonov#include <inttypes.h>
850aadb33SDmitri Tikhonov#include <stdio.h>
950aadb33SDmitri Tikhonov#include <stdlib.h>
1050aadb33SDmitri Tikhonov#include <string.h>
1150aadb33SDmitri Tikhonov
1250aadb33SDmitri Tikhonov#include "lsquic_int_types.h"
1350aadb33SDmitri Tikhonov#include "lsquic_senhist.h"
1450aadb33SDmitri Tikhonov
1550aadb33SDmitri Tikhonov
1650aadb33SDmitri Tikhonovvoid
1750aadb33SDmitri Tikhonovlsquic_senhist_init (lsquic_senhist_t *hist)
1850aadb33SDmitri Tikhonov{
1950aadb33SDmitri Tikhonov    lsquic_packints_init(&hist->sh_pints);
2050aadb33SDmitri Tikhonov#ifndef NDEBUG
2150aadb33SDmitri Tikhonov    {
2250aadb33SDmitri Tikhonov        const char *env;
2350aadb33SDmitri Tikhonov        env = getenv("LSQUIC_REORDER_SENT");
2450aadb33SDmitri Tikhonov        if (env && atoi(env))
2550aadb33SDmitri Tikhonov            hist->sh_flags = SH_REORDER;
2650aadb33SDmitri Tikhonov        else
2750aadb33SDmitri Tikhonov            hist->sh_flags = 0;
2850aadb33SDmitri Tikhonov    }
2950aadb33SDmitri Tikhonov#endif
3050aadb33SDmitri Tikhonov}
3150aadb33SDmitri Tikhonov
3250aadb33SDmitri Tikhonov
3350aadb33SDmitri Tikhonovvoid
3450aadb33SDmitri Tikhonovlsquic_senhist_cleanup (lsquic_senhist_t *hist)
3550aadb33SDmitri Tikhonov{
3650aadb33SDmitri Tikhonov    lsquic_packints_cleanup(&hist->sh_pints);
3750aadb33SDmitri Tikhonov}
3850aadb33SDmitri Tikhonov
3950aadb33SDmitri Tikhonov
4050aadb33SDmitri Tikhonov/* At the time of this writing, the only reason the sequence of sent
4150aadb33SDmitri Tikhonov * packet numbers could contain a hole is elision of stream frames from
4250aadb33SDmitri Tikhonov * scheduled, but delayed packets.  If such packet becomes empty after
4350aadb33SDmitri Tikhonov * elision, it is dropped from the queue.
4450aadb33SDmitri Tikhonov */
4550aadb33SDmitri Tikhonov
4650aadb33SDmitri Tikhonov
4750aadb33SDmitri Tikhonov/* The fast insert is used in the normal case, when packets are sent
4850aadb33SDmitri Tikhonov * out in the same order in which they are scheduled: that is, their
4950aadb33SDmitri Tikhonov * packet numbers are always increasing.
5050aadb33SDmitri Tikhonov */
5150aadb33SDmitri Tikhonovstatic int
5250aadb33SDmitri Tikhonovsenhist_add_fast (lsquic_senhist_t *hist, lsquic_packno_t packno)
5350aadb33SDmitri Tikhonov{
5450aadb33SDmitri Tikhonov    struct packet_interval *pi;
5550aadb33SDmitri Tikhonov
5650aadb33SDmitri Tikhonov    pi = TAILQ_FIRST(&hist->sh_pints.pk_intervals);
5750aadb33SDmitri Tikhonov    if (pi)
5850aadb33SDmitri Tikhonov    {
5950aadb33SDmitri Tikhonov        /* Check that packet numbers are always increasing */
6050aadb33SDmitri Tikhonov        assert(packno > pi->range.high);
6150aadb33SDmitri Tikhonov        if (packno == pi->range.high + 1)
6250aadb33SDmitri Tikhonov        {
6350aadb33SDmitri Tikhonov            ++pi->range.high;
6450aadb33SDmitri Tikhonov            return 0;
6550aadb33SDmitri Tikhonov        }
6650aadb33SDmitri Tikhonov    }
6750aadb33SDmitri Tikhonov
6850aadb33SDmitri Tikhonov    pi = malloc(sizeof(*pi));
6950aadb33SDmitri Tikhonov    if (!pi)
7050aadb33SDmitri Tikhonov        return -1;
7150aadb33SDmitri Tikhonov    pi->range.high = packno;
7250aadb33SDmitri Tikhonov    pi->range.low = packno;
7350aadb33SDmitri Tikhonov    TAILQ_INSERT_HEAD(&hist->sh_pints.pk_intervals, pi, next_pi);
7450aadb33SDmitri Tikhonov    return 0;
7550aadb33SDmitri Tikhonov}
7650aadb33SDmitri Tikhonov
7750aadb33SDmitri Tikhonov
7850aadb33SDmitri Tikhonov#ifndef NDEBUG
7950aadb33SDmitri Tikhonovstatic int
8050aadb33SDmitri Tikhonovsenhist_add_slow (lsquic_senhist_t *hist, lsquic_packno_t packno)
8150aadb33SDmitri Tikhonov{
8250aadb33SDmitri Tikhonov    switch (lsquic_packints_add(&hist->sh_pints, packno))
8350aadb33SDmitri Tikhonov    {
8450aadb33SDmitri Tikhonov    case PACKINTS_OK:
8550aadb33SDmitri Tikhonov        return 0;
8650aadb33SDmitri Tikhonov    case PACKINTS_DUP:  /* We should not generate duplicate packet numbers! */
8750aadb33SDmitri Tikhonov    default:
8850aadb33SDmitri Tikhonov        assert(0);
8950aadb33SDmitri Tikhonov    case PACKINTS_ERR:
9050aadb33SDmitri Tikhonov        return -1;
9150aadb33SDmitri Tikhonov    }
9250aadb33SDmitri Tikhonov}
9350aadb33SDmitri Tikhonov#endif
9450aadb33SDmitri Tikhonov
9550aadb33SDmitri Tikhonov
9650aadb33SDmitri Tikhonovint
9750aadb33SDmitri Tikhonovlsquic_senhist_add (lsquic_senhist_t *hist, lsquic_packno_t packno)
9850aadb33SDmitri Tikhonov{
9950aadb33SDmitri Tikhonov#ifndef NDEBUG
10050aadb33SDmitri Tikhonov    if (hist->sh_flags & SH_REORDER)
10150aadb33SDmitri Tikhonov        return senhist_add_slow(hist, packno);
10250aadb33SDmitri Tikhonov    else
10350aadb33SDmitri Tikhonov#endif
10450aadb33SDmitri Tikhonov        return senhist_add_fast(hist, packno);
10550aadb33SDmitri Tikhonov}
10650aadb33SDmitri Tikhonov
10750aadb33SDmitri Tikhonov
10850aadb33SDmitri Tikhonovint
10950aadb33SDmitri Tikhonovlsquic_senhist_sent_range (lsquic_senhist_t *hist, lsquic_packno_t low,
11050aadb33SDmitri Tikhonov                                                   lsquic_packno_t high)
11150aadb33SDmitri Tikhonov{
11250aadb33SDmitri Tikhonov    const struct lsquic_packno_range *range;
11350aadb33SDmitri Tikhonov    for (range = lsquic_packints_first(&hist->sh_pints); range;
11450aadb33SDmitri Tikhonov                            range = lsquic_packints_next(&hist->sh_pints))
11550aadb33SDmitri Tikhonov        if (range->low <= low && range->high >= high)
11650aadb33SDmitri Tikhonov            return 1;
11750aadb33SDmitri Tikhonov    return 0;
11850aadb33SDmitri Tikhonov}
11950aadb33SDmitri Tikhonov
12050aadb33SDmitri Tikhonov
12150aadb33SDmitri Tikhonovlsquic_packno_t
12250aadb33SDmitri Tikhonovlsquic_senhist_largest (lsquic_senhist_t *hist)
12350aadb33SDmitri Tikhonov{
12450aadb33SDmitri Tikhonov    const struct lsquic_packno_range *range;
12550aadb33SDmitri Tikhonov    range = lsquic_packints_first(&hist->sh_pints);
12650aadb33SDmitri Tikhonov    if (range)
12750aadb33SDmitri Tikhonov        return range->high;
12850aadb33SDmitri Tikhonov    else
12950aadb33SDmitri Tikhonov        return 0;
13050aadb33SDmitri Tikhonov}
13150aadb33SDmitri Tikhonov
13250aadb33SDmitri Tikhonov
13350aadb33SDmitri Tikhonovvoid
13450aadb33SDmitri Tikhonovlsquic_senhist_tostr (lsquic_senhist_t *hist, char *buf, size_t bufsz)
13550aadb33SDmitri Tikhonov{
13650aadb33SDmitri Tikhonov    const struct lsquic_packno_range *range;
13750aadb33SDmitri Tikhonov    size_t off;
13850aadb33SDmitri Tikhonov    int n;
13950aadb33SDmitri Tikhonov    for (off = 0, range = lsquic_packints_first(&hist->sh_pints);
14050aadb33SDmitri Tikhonov            range && off < bufsz;
14150aadb33SDmitri Tikhonov                off += n, range = lsquic_packints_next(&hist->sh_pints))
14250aadb33SDmitri Tikhonov    {
14350aadb33SDmitri Tikhonov        n = snprintf(buf + off, bufsz - off, "[%"PRIu64"-%"PRIu64"]",
14450aadb33SDmitri Tikhonov                                                    range->high, range->low);
14550aadb33SDmitri Tikhonov        if (n < 0 || (size_t) n >= bufsz - off)
14650aadb33SDmitri Tikhonov            break;
14750aadb33SDmitri Tikhonov    }
14850aadb33SDmitri Tikhonov    if (bufsz > 0)
14950aadb33SDmitri Tikhonov        buf[off] = '\0';
15050aadb33SDmitri Tikhonov}
151