lsquic_attq.c revision 5392f7a3 
1/* Copyright (c) 2017 - 2019 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_malo.h"
23#include "lsquic_hash.h"
24#include "lsquic_conn.h"
25
26
27struct attq
28{
29    struct malo        *aq_elem_malo;
30    struct attq_elem  **aq_heap;
31    unsigned            aq_nelem;
32    unsigned            aq_nalloc;
33};
34
35
36struct attq *
37attq_create (void)
38{
39    struct attq *q;
40    struct malo *malo;
41
42    malo = lsquic_malo_create(sizeof(struct attq_elem));
43    if (!malo)
44        return NULL;
45
46    q = calloc(1, sizeof(*q));
47    if (!q)
48    {
49        lsquic_malo_destroy(malo);
50        return NULL;
51    }
52
53    q->aq_elem_malo = malo;
54    return q;
55}
56
57
58void
59attq_destroy (struct attq *q)
60{
61    lsquic_malo_destroy(q->aq_elem_malo);
62    free(q->aq_heap);
63    free(q);
64}
65
66
67
68#define AE_PARENT(i) ((i - 1) / 2)
69#define AE_LCHILD(i) (2 * i + 1)
70#define AE_RCHILD(i) (2 * i + 2)
71
72
73#ifndef NDEBUG
74static void
75attq_verify (struct attq *q)
76{
77    unsigned i;
78
79    for (i = 0; i < q->aq_nelem; ++i)
80    {
81        assert(q->aq_heap[i]->ae_heap_idx == i);
82        if (AE_LCHILD(i) < q->aq_nelem)
83            assert(q->aq_heap[i]->ae_adv_time <=
84                        q->aq_heap[AE_LCHILD(i)]->ae_adv_time);
85        if (AE_RCHILD(i) < q->aq_nelem)
86            assert(q->aq_heap[i]->ae_adv_time <=
87                        q->aq_heap[AE_RCHILD(i)]->ae_adv_time);
88    }
89}
90#else
91#define attq_verify(q)
92#endif
93
94
95static void
96attq_swap (struct attq *q, unsigned a, unsigned b)
97{
98    struct attq_elem *el;
99
100    el = q->aq_heap[ a ];
101    q->aq_heap[ a ] = q->aq_heap[ b ];
102    q->aq_heap[ b ] = el;
103    q->aq_heap[ a ]->ae_heap_idx = a;
104    q->aq_heap[ b ]->ae_heap_idx = b;
105}
106
107
108int
109attq_add (struct attq *q, struct lsquic_conn *conn,
110                                            lsquic_time_t advisory_time)
111{
112    struct attq_elem *el, **heap;
113    unsigned n, i;
114
115    if (q->aq_nelem >= q->aq_nalloc)
116    {
117        if (q->aq_nalloc > 0)
118            n = q->aq_nalloc * 2;
119        else
120            n = 8;
121        heap = realloc(q->aq_heap, n * sizeof(q->aq_heap[0]));
122        if (!heap)
123            return -1;
124        q->aq_heap = heap;
125        q->aq_nalloc = n;
126    }
127
128    el = lsquic_malo_get(q->aq_elem_malo);
129    if (!el)
130        return -1;
131    el->ae_adv_time = advisory_time;
132
133    /* The only place linkage between conn and attq_elem occurs: */
134    el->ae_conn = conn;
135    conn->cn_attq_elem = el;
136
137    el->ae_heap_idx = q->aq_nelem;
138    q->aq_heap[ q->aq_nelem++ ] = el;
139
140    i = q->aq_nelem - 1;
141    while (i > 0 && q->aq_heap[ AE_PARENT(i) ]->ae_adv_time >=
142                                        q->aq_heap[ i ]->ae_adv_time)
143    {
144        attq_swap(q, i, AE_PARENT(i));
145        i = AE_PARENT(i);
146    }
147
148    attq_verify(q);
149
150    return 0;
151}
152
153
154struct lsquic_conn *
155attq_pop (struct attq *q, lsquic_time_t cutoff)
156{
157    struct lsquic_conn *conn;
158    struct attq_elem *el;
159
160    if (q->aq_nelem == 0)
161        return NULL;
162
163    el = q->aq_heap[0];
164    if (el->ae_adv_time >= cutoff)
165        return NULL;
166
167    conn = el->ae_conn;
168    attq_remove(q, conn);
169    return conn;
170}
171
172
173static void
174attq_heapify (struct attq *q, unsigned i)
175{
176    unsigned smallest;
177
178    assert(i < q->aq_nelem);
179
180    if (AE_LCHILD(i) < q->aq_nelem)
181    {
182        if (q->aq_heap[ AE_LCHILD(i) ]->ae_adv_time <
183                                    q->aq_heap[ i ]->ae_adv_time)
184            smallest = AE_LCHILD(i);
185        else
186            smallest = i;
187        if (AE_RCHILD(i) < q->aq_nelem &&
188            q->aq_heap[ AE_RCHILD(i) ]->ae_adv_time <
189                                    q->aq_heap[ smallest ]->ae_adv_time)
190            smallest = AE_RCHILD(i);
191    }
192    else
193        smallest = i;
194
195    if (smallest != i)
196    {
197        attq_swap(q, smallest, i);
198        attq_heapify(q, smallest);
199    }
200}
201
202
203void
204attq_remove (struct attq *q, struct lsquic_conn *conn)
205{
206    struct attq_elem *el;
207    unsigned idx;
208
209    el = conn->cn_attq_elem;
210    idx = el->ae_heap_idx;
211
212    assert(q->aq_nelem > 0);
213    assert(q->aq_heap[idx] == el);
214    assert(conn->cn_attq_elem == el);
215
216    conn->cn_attq_elem = NULL;
217
218    q->aq_heap[ idx ] = q->aq_heap[ --q->aq_nelem ];
219    q->aq_heap[ idx ]->ae_heap_idx = idx;
220    if (idx > 0 && q->aq_heap[ idx ]->ae_adv_time <
221                                q->aq_heap[ AE_PARENT(idx) ]->ae_adv_time)
222    {
223        do
224        {
225            attq_swap(q, idx, AE_PARENT(idx));
226            idx = AE_PARENT(idx);
227        }
228        while (idx > 0 && q->aq_heap[ idx ]->ae_adv_time <
229                                q->aq_heap[ AE_PARENT(idx) ]->ae_adv_time);
230    }
231    else if (q->aq_nelem > 1 && idx < q->aq_nelem)
232        attq_heapify(q, idx);
233    lsquic_malo_put(el);
234    attq_verify(q);
235}
236
237
238unsigned
239attq_count_before (struct attq *q, lsquic_time_t cutoff)
240{
241    unsigned level, total_count, level_count, i, level_max;
242
243    total_count = 0;
244    for (i = 0, level = 0;; ++level)
245    {
246        level_count = 0;
247        level_max = i + (1U << level);
248        for ( ; i < level_max && i < q->aq_nelem; ++i)
249            level_count += q->aq_heap[i]->ae_adv_time < cutoff;
250        total_count += level_count;
251        if (level_count < (1U << level))
252            return total_count;
253    }
254    assert(0);
255}
256
257
258const lsquic_time_t *
259attq_next_time (struct attq *q)
260{
261    if (q->aq_nelem > 0)
262        return &q->aq_heap[0]->ae_adv_time;
263    else
264        return NULL;
265}
266