lsquic_attq.c revision a5fa05f9 
1/* Copyright (c) 2017 - 2020 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_attq.c -- Advisory Tick Time Queue
4 *
5 * This is a collection of connections kept in a binary heap, the top
6 * element having the minimum advsory time.  To speed up removal, each
7 * element has an index it has in the heap array.  The index is updated
8 * as elements are moved around in the array when heap is updated.
9 */
10
11#include <assert.h>
12#include <stdlib.h>
13#ifdef WIN32
14#include <vc_compat.h>
15#endif
16#include <sys/queue.h>
17
18#include "lsquic.h"
19#include "lsquic_types.h"
20#include "lsquic_int_types.h"
21#include "lsquic_attq.h"
22#include "lsquic_packet_common.h"
23#include "lsquic_alarmset.h"
24#include "lsquic_malo.h"
25#include "lsquic_hash.h"
26#include "lsquic_conn.h"
27
28
29struct attq
30{
31    struct malo        *aq_elem_malo;
32    struct attq_elem  **aq_heap;
33    unsigned            aq_nelem;
34    unsigned            aq_nalloc;
35};
36
37
38struct attq *
39lsquic_attq_create (void)
40{
41    struct attq *q;
42    struct malo *malo;
43
44    malo = lsquic_malo_create(sizeof(struct attq_elem));
45    if (!malo)
46        return NULL;
47
48    q = calloc(1, sizeof(*q));
49    if (!q)
50    {
51        lsquic_malo_destroy(malo);
52        return NULL;
53    }
54
55    q->aq_elem_malo = malo;
56    return q;
57}
58
59
60void
61lsquic_attq_destroy (struct attq *q)
62{
63    lsquic_malo_destroy(q->aq_elem_malo);
64    free(q->aq_heap);
65    free(q);
66}
67
68
69
70#define AE_PARENT(i) ((i - 1) / 2)
71#define AE_LCHILD(i) (2 * i + 1)
72#define AE_RCHILD(i) (2 * i + 2)
73
74
75#if LSQUIC_EXTRA_CHECKS && !defined(NDEBUG)
76static void
77attq_verify (struct attq *q)
78{
79    unsigned i;
80
81    for (i = 0; i < q->aq_nelem; ++i)
82    {
83        assert(q->aq_heap[i]->ae_heap_idx == i);
84        if (AE_LCHILD(i) < q->aq_nelem)
85            assert(q->aq_heap[i]->ae_adv_time <=
86                        q->aq_heap[AE_LCHILD(i)]->ae_adv_time);
87        if (AE_RCHILD(i) < q->aq_nelem)
88            assert(q->aq_heap[i]->ae_adv_time <=
89                        q->aq_heap[AE_RCHILD(i)]->ae_adv_time);
90    }
91}
92#else
93#define attq_verify(q)
94#endif
95
96
97static void
98attq_swap (struct attq *q, unsigned a, unsigned b)
99{
100    struct attq_elem *el;
101
102    el = q->aq_heap[ a ];
103    q->aq_heap[ a ] = q->aq_heap[ b ];
104    q->aq_heap[ b ] = el;
105    q->aq_heap[ a ]->ae_heap_idx = a;
106    q->aq_heap[ b ]->ae_heap_idx = b;
107}
108
109
110int
111lsquic_attq_add (struct attq *q, struct lsquic_conn *conn,
112                                lsquic_time_t advisory_time, enum ae_why why)
113{
114    struct attq_elem *el, **heap;
115    unsigned n, i;
116
117    if (q->aq_nelem >= q->aq_nalloc)
118    {
119        if (q->aq_nalloc > 0)
120            n = q->aq_nalloc * 2;
121        else
122            n = 8;
123        heap = realloc(q->aq_heap, n * sizeof(q->aq_heap[0]));
124        if (!heap)
125            return -1;
126        q->aq_heap = heap;
127        q->aq_nalloc = n;
128    }
129
130    el = lsquic_malo_get(q->aq_elem_malo);
131    if (!el)
132        return -1;
133    el->ae_adv_time = advisory_time;
134    el->ae_why = why;
135
136    /* The only place linkage between conn and attq_elem occurs: */
137    el->ae_conn = conn;
138    conn->cn_attq_elem = el;
139
140    el->ae_heap_idx = q->aq_nelem;
141    q->aq_heap[ q->aq_nelem++ ] = el;
142
143    i = q->aq_nelem - 1;
144    while (i > 0 && q->aq_heap[ AE_PARENT(i) ]->ae_adv_time >=
145                                        q->aq_heap[ i ]->ae_adv_time)
146    {
147        attq_swap(q, i, AE_PARENT(i));
148        i = AE_PARENT(i);
149    }
150
151    attq_verify(q);
152
153    return 0;
154}
155
156
157struct lsquic_conn *
158lsquic_attq_pop (struct attq *q, lsquic_time_t cutoff)
159{
160    struct lsquic_conn *conn;
161    struct attq_elem *el;
162
163    if (q->aq_nelem == 0)
164        return NULL;
165
166    el = q->aq_heap[0];
167    if (el->ae_adv_time >= cutoff)
168        return NULL;
169
170    conn = el->ae_conn;
171    lsquic_attq_remove(q, conn);
172    return conn;
173}
174
175
176static void
177attq_heapify (struct attq *q, unsigned i)
178{
179    unsigned smallest;
180
181    assert(i < q->aq_nelem);
182
183    if (AE_LCHILD(i) < q->aq_nelem)
184    {
185        if (q->aq_heap[ AE_LCHILD(i) ]->ae_adv_time <
186                                    q->aq_heap[ i ]->ae_adv_time)
187            smallest = AE_LCHILD(i);
188        else
189            smallest = i;
190        if (AE_RCHILD(i) < q->aq_nelem &&
191            q->aq_heap[ AE_RCHILD(i) ]->ae_adv_time <
192                                    q->aq_heap[ smallest ]->ae_adv_time)
193            smallest = AE_RCHILD(i);
194    }
195    else
196        smallest = i;
197
198    if (smallest != i)
199    {
200        attq_swap(q, smallest, i);
201        attq_heapify(q, smallest);
202    }
203}
204
205
206void
207lsquic_attq_remove (struct attq *q, struct lsquic_conn *conn)
208{
209    struct attq_elem *el;
210    unsigned idx;
211
212    el = conn->cn_attq_elem;
213    idx = el->ae_heap_idx;
214
215    assert(q->aq_nelem > 0);
216    assert(q->aq_heap[idx] == el);
217    assert(conn->cn_attq_elem == el);
218
219    conn->cn_attq_elem = NULL;
220
221    q->aq_heap[ idx ] = q->aq_heap[ --q->aq_nelem ];
222    q->aq_heap[ idx ]->ae_heap_idx = idx;
223    if (idx > 0 && q->aq_heap[ idx ]->ae_adv_time <
224                                q->aq_heap[ AE_PARENT(idx) ]->ae_adv_time)
225    {
226        do
227        {
228            attq_swap(q, idx, AE_PARENT(idx));
229            idx = AE_PARENT(idx);
230        }
231        while (idx > 0 && q->aq_heap[ idx ]->ae_adv_time <
232                                q->aq_heap[ AE_PARENT(idx) ]->ae_adv_time);
233    }
234    else if (q->aq_nelem > 1 && idx < q->aq_nelem)
235        attq_heapify(q, idx);
236    lsquic_malo_put(el);
237    attq_verify(q);
238}
239
240
241unsigned
242lsquic_attq_count_before (struct attq *q, lsquic_time_t cutoff)
243{
244    unsigned level, total_count, level_count, i, level_max;
245
246    total_count = 0;
247    for (i = 0, level = 0;; ++level)
248    {
249        level_count = 0;
250        level_max = i + (1U << level);
251        for ( ; i < level_max && i < q->aq_nelem; ++i)
252            level_count += q->aq_heap[i]->ae_adv_time < cutoff;
253        total_count += level_count;
254        if (level_count < (1U << level))
255            return total_count;
256    }
257    assert(0);
258    return total_count;
259}
260
261
262const struct attq_elem *
263lsquic_attq_next (struct attq *q)
264{
265    if (q->aq_nelem > 0)
266        return q->aq_heap[0];
267    else
268        return NULL;
269}
270
271
272const char *
273lsquic_attq_why2str (enum ae_why why)
274{
275    switch (why)
276    {
277    case AEW_PACER:
278        return "PACER";
279    case AEW_MINI_EXPIRE:
280        return "MINI-EXPIRE";
281    default:
282        why -= N_AEWS;
283        if ((unsigned) why < (unsigned) MAX_LSQUIC_ALARMS)
284            return lsquic_alid2str[why];
285        return "UNKNOWN";
286    }
287}
288