lsquic_senhist.c revision c51ce338 
1/* Copyright (c) 2017 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_senhist.c -- Sent history implementation
4 */
5
6#include <assert.h>
7#include <inttypes.h>
8#include <stdio.h>
9#include <stdlib.h>
10#include <string.h>
11
12#include "lsquic_int_types.h"
13#include "lsquic_senhist.h"
14
15
16void
17lsquic_senhist_init (lsquic_senhist_t *hist)
18{
19    lsquic_packints_init(&hist->sh_pints);
20#ifndef NDEBUG
21    {
22        const char *env;
23        env = getenv("LSQUIC_REORDER_SENT");
24        if (env && atoi(env))
25            hist->sh_flags = SH_REORDER;
26        else
27            hist->sh_flags = 0;
28    }
29#endif
30}
31
32
33void
34lsquic_senhist_cleanup (lsquic_senhist_t *hist)
35{
36    lsquic_packints_cleanup(&hist->sh_pints);
37}
38
39
40/* At the time of this writing, the only reason the sequence of sent
41 * packet numbers could contain a hole is elision of stream frames from
42 * scheduled, but delayed packets.  If such packet becomes empty after
43 * elision, it is dropped from the queue.
44 */
45
46
47/* The fast insert is used in the normal case, when packets are sent
48 * out in the same order in which they are scheduled: that is, their
49 * packet numbers are always increasing.
50 */
51static int
52senhist_add_fast (lsquic_senhist_t *hist, lsquic_packno_t packno)
53{
54    struct packet_interval *pi;
55
56    pi = TAILQ_FIRST(&hist->sh_pints.pk_intervals);
57    if (pi)
58    {
59        /* Check that packet numbers are always increasing */
60        assert(packno > pi->range.high);
61        if (packno == pi->range.high + 1)
62        {
63            ++pi->range.high;
64            return 0;
65        }
66    }
67
68    pi = malloc(sizeof(*pi));
69    if (!pi)
70        return -1;
71    pi->range.high = packno;
72    pi->range.low = packno;
73    TAILQ_INSERT_HEAD(&hist->sh_pints.pk_intervals, pi, next_pi);
74    return 0;
75}
76
77
78#ifndef NDEBUG
79static int
80senhist_add_slow (lsquic_senhist_t *hist, lsquic_packno_t packno)
81{
82    switch (lsquic_packints_add(&hist->sh_pints, packno))
83    {
84    case PACKINTS_OK:
85        return 0;
86    case PACKINTS_DUP:  /* We should not generate duplicate packet numbers! */
87    default:
88        assert(0);
89    case PACKINTS_ERR:
90        return -1;
91    }
92}
93#endif
94
95
96int
97lsquic_senhist_add (lsquic_senhist_t *hist, lsquic_packno_t packno)
98{
99#ifndef NDEBUG
100    if (hist->sh_flags & SH_REORDER)
101        return senhist_add_slow(hist, packno);
102    else
103#endif
104        return senhist_add_fast(hist, packno);
105}
106
107
108int
109lsquic_senhist_sent_range (lsquic_senhist_t *hist, lsquic_packno_t low,
110                                                   lsquic_packno_t high)
111{
112    const struct lsquic_packno_range *range;
113    for (range = lsquic_packints_first(&hist->sh_pints); range;
114                            range = lsquic_packints_next(&hist->sh_pints))
115        if (range->low <= low && range->high >= high)
116            return 1;
117    return 0;
118}
119
120
121lsquic_packno_t
122lsquic_senhist_largest (lsquic_senhist_t *hist)
123{
124    const struct lsquic_packno_range *range;
125    range = lsquic_packints_first(&hist->sh_pints);
126    if (range)
127        return range->high;
128    else
129        return 0;
130}
131
132
133void
134lsquic_senhist_tostr (lsquic_senhist_t *hist, char *buf, size_t bufsz)
135{
136    const struct lsquic_packno_range *range;
137    size_t off;
138    int n;
139    for (off = 0, range = lsquic_packints_first(&hist->sh_pints);
140            range && off < bufsz;
141                off += n, range = lsquic_packints_next(&hist->sh_pints))
142    {
143        n = snprintf(buf + off, bufsz - off, "[%"PRIu64"-%"PRIu64"]",
144                                                    range->high, range->low);
145        if (n < 0 || (size_t) n >= bufsz - off)
146            break;
147    }
148    if (bufsz > 0)
149        buf[off] = '\0';
150}
151
152
153size_t
154lsquic_senhist_mem_used (const struct lsquic_senhist *hist)
155{
156    return sizeof(*hist)
157         - sizeof(hist->sh_pints)
158         + lsquic_packints_mem_used(&hist->sh_pints);
159}
160