lsquic_attq.c revision 1c9cee3e
1229fce07SDmitri Tikhonov/* Copyright (c) 2017 - 2019 LiteSpeed Technologies Inc.  See LICENSE. */
250aadb33SDmitri Tikhonov/*
350aadb33SDmitri Tikhonov * lsquic_attq.c -- Advisory Tick Time Queue
450aadb33SDmitri Tikhonov *
550aadb33SDmitri Tikhonov * This is a collection of connections kept in a binary heap, the top
650aadb33SDmitri Tikhonov * element having the minimum advsory time.  To speed up removal, each
750aadb33SDmitri Tikhonov * element has an index it has in the heap array.  The index is updated
850aadb33SDmitri Tikhonov * as elements are moved around in the array when heap is updated.
950aadb33SDmitri Tikhonov */
1050aadb33SDmitri Tikhonov
1150aadb33SDmitri Tikhonov#include <assert.h>
1250aadb33SDmitri Tikhonov#include <stdlib.h>
13461e84d8SAmol Deshpande#ifdef WIN32
14461e84d8SAmol Deshpande#include <vc_compat.h>
15461e84d8SAmol Deshpande#endif
165392f7a3SLiteSpeed Tech#include <sys/queue.h>
1750aadb33SDmitri Tikhonov
1850aadb33SDmitri Tikhonov#include "lsquic.h"
1950aadb33SDmitri Tikhonov#include "lsquic_types.h"
2050aadb33SDmitri Tikhonov#include "lsquic_int_types.h"
2150aadb33SDmitri Tikhonov#include "lsquic_attq.h"
220adf085aSDmitri Tikhonov#include "lsquic_packet_common.h"
230adf085aSDmitri Tikhonov#include "lsquic_alarmset.h"
2450aadb33SDmitri Tikhonov#include "lsquic_malo.h"
255392f7a3SLiteSpeed Tech#include "lsquic_hash.h"
2650aadb33SDmitri Tikhonov#include "lsquic_conn.h"
2750aadb33SDmitri Tikhonov
2850aadb33SDmitri Tikhonov
2950aadb33SDmitri Tikhonovstruct attq
3050aadb33SDmitri Tikhonov{
3150aadb33SDmitri Tikhonov    struct malo        *aq_elem_malo;
3250aadb33SDmitri Tikhonov    struct attq_elem  **aq_heap;
3350aadb33SDmitri Tikhonov    unsigned            aq_nelem;
3450aadb33SDmitri Tikhonov    unsigned            aq_nalloc;
3550aadb33SDmitri Tikhonov};
3650aadb33SDmitri Tikhonov
3750aadb33SDmitri Tikhonov
3850aadb33SDmitri Tikhonovstruct attq *
3950aadb33SDmitri Tikhonovattq_create (void)
4050aadb33SDmitri Tikhonov{
4150aadb33SDmitri Tikhonov    struct attq *q;
4250aadb33SDmitri Tikhonov    struct malo *malo;
4350aadb33SDmitri Tikhonov
4450aadb33SDmitri Tikhonov    malo = lsquic_malo_create(sizeof(struct attq_elem));
4550aadb33SDmitri Tikhonov    if (!malo)
4650aadb33SDmitri Tikhonov        return NULL;
4750aadb33SDmitri Tikhonov
4850aadb33SDmitri Tikhonov    q = calloc(1, sizeof(*q));
4950aadb33SDmitri Tikhonov    if (!q)
5050aadb33SDmitri Tikhonov    {
5150aadb33SDmitri Tikhonov        lsquic_malo_destroy(malo);
5250aadb33SDmitri Tikhonov        return NULL;
5350aadb33SDmitri Tikhonov    }
5450aadb33SDmitri Tikhonov
5550aadb33SDmitri Tikhonov    q->aq_elem_malo = malo;
5650aadb33SDmitri Tikhonov    return q;
5750aadb33SDmitri Tikhonov}
5850aadb33SDmitri Tikhonov
5950aadb33SDmitri Tikhonov
6050aadb33SDmitri Tikhonovvoid
6150aadb33SDmitri Tikhonovattq_destroy (struct attq *q)
6250aadb33SDmitri Tikhonov{
6350aadb33SDmitri Tikhonov    lsquic_malo_destroy(q->aq_elem_malo);
6450aadb33SDmitri Tikhonov    free(q->aq_heap);
6550aadb33SDmitri Tikhonov    free(q);
6650aadb33SDmitri Tikhonov}
6750aadb33SDmitri Tikhonov
6850aadb33SDmitri Tikhonov
6950aadb33SDmitri Tikhonov
7050aadb33SDmitri Tikhonov#define AE_PARENT(i) ((i - 1) / 2)
7150aadb33SDmitri Tikhonov#define AE_LCHILD(i) (2 * i + 1)
7250aadb33SDmitri Tikhonov#define AE_RCHILD(i) (2 * i + 2)
7350aadb33SDmitri Tikhonov
7450aadb33SDmitri Tikhonov
751c9cee3eSDmitri Tikhonov#if LSQUIC_EXTRA_CHECKS && !defined(NDEBUG)
7650aadb33SDmitri Tikhonovstatic void
7750aadb33SDmitri Tikhonovattq_verify (struct attq *q)
7850aadb33SDmitri Tikhonov{
7950aadb33SDmitri Tikhonov    unsigned i;
8050aadb33SDmitri Tikhonov
8150aadb33SDmitri Tikhonov    for (i = 0; i < q->aq_nelem; ++i)
8250aadb33SDmitri Tikhonov    {
8350aadb33SDmitri Tikhonov        assert(q->aq_heap[i]->ae_heap_idx == i);
8450aadb33SDmitri Tikhonov        if (AE_LCHILD(i) < q->aq_nelem)
8550aadb33SDmitri Tikhonov            assert(q->aq_heap[i]->ae_adv_time <=
8650aadb33SDmitri Tikhonov                        q->aq_heap[AE_LCHILD(i)]->ae_adv_time);
8750aadb33SDmitri Tikhonov        if (AE_RCHILD(i) < q->aq_nelem)
8850aadb33SDmitri Tikhonov            assert(q->aq_heap[i]->ae_adv_time <=
8950aadb33SDmitri Tikhonov                        q->aq_heap[AE_RCHILD(i)]->ae_adv_time);
9050aadb33SDmitri Tikhonov    }
9150aadb33SDmitri Tikhonov}
9250aadb33SDmitri Tikhonov#else
9350aadb33SDmitri Tikhonov#define attq_verify(q)
9450aadb33SDmitri Tikhonov#endif
9550aadb33SDmitri Tikhonov
9650aadb33SDmitri Tikhonov
9750aadb33SDmitri Tikhonovstatic void
9850aadb33SDmitri Tikhonovattq_swap (struct attq *q, unsigned a, unsigned b)
9950aadb33SDmitri Tikhonov{
10050aadb33SDmitri Tikhonov    struct attq_elem *el;
10150aadb33SDmitri Tikhonov
10250aadb33SDmitri Tikhonov    el = q->aq_heap[ a ];
10350aadb33SDmitri Tikhonov    q->aq_heap[ a ] = q->aq_heap[ b ];
10450aadb33SDmitri Tikhonov    q->aq_heap[ b ] = el;
10550aadb33SDmitri Tikhonov    q->aq_heap[ a ]->ae_heap_idx = a;
10650aadb33SDmitri Tikhonov    q->aq_heap[ b ]->ae_heap_idx = b;
10750aadb33SDmitri Tikhonov}
10850aadb33SDmitri Tikhonov
10950aadb33SDmitri Tikhonov
11050aadb33SDmitri Tikhonovint
11150aadb33SDmitri Tikhonovattq_add (struct attq *q, struct lsquic_conn *conn,
1120adf085aSDmitri Tikhonov                                lsquic_time_t advisory_time, enum ae_why why)
11350aadb33SDmitri Tikhonov{
11450aadb33SDmitri Tikhonov    struct attq_elem *el, **heap;
11550aadb33SDmitri Tikhonov    unsigned n, i;
11650aadb33SDmitri Tikhonov
11750aadb33SDmitri Tikhonov    if (q->aq_nelem >= q->aq_nalloc)
11850aadb33SDmitri Tikhonov    {
11950aadb33SDmitri Tikhonov        if (q->aq_nalloc > 0)
12050aadb33SDmitri Tikhonov            n = q->aq_nalloc * 2;
12150aadb33SDmitri Tikhonov        else
12250aadb33SDmitri Tikhonov            n = 8;
12350aadb33SDmitri Tikhonov        heap = realloc(q->aq_heap, n * sizeof(q->aq_heap[0]));
12450aadb33SDmitri Tikhonov        if (!heap)
12550aadb33SDmitri Tikhonov            return -1;
12650aadb33SDmitri Tikhonov        q->aq_heap = heap;
12750aadb33SDmitri Tikhonov        q->aq_nalloc = n;
12850aadb33SDmitri Tikhonov    }
12950aadb33SDmitri Tikhonov
13050aadb33SDmitri Tikhonov    el = lsquic_malo_get(q->aq_elem_malo);
13150aadb33SDmitri Tikhonov    if (!el)
13250aadb33SDmitri Tikhonov        return -1;
13350aadb33SDmitri Tikhonov    el->ae_adv_time = advisory_time;
1340adf085aSDmitri Tikhonov    el->ae_why = why;
13550aadb33SDmitri Tikhonov
13650aadb33SDmitri Tikhonov    /* The only place linkage between conn and attq_elem occurs: */
13750aadb33SDmitri Tikhonov    el->ae_conn = conn;
13850aadb33SDmitri Tikhonov    conn->cn_attq_elem = el;
13950aadb33SDmitri Tikhonov
14050aadb33SDmitri Tikhonov    el->ae_heap_idx = q->aq_nelem;
14150aadb33SDmitri Tikhonov    q->aq_heap[ q->aq_nelem++ ] = el;
14250aadb33SDmitri Tikhonov
14350aadb33SDmitri Tikhonov    i = q->aq_nelem - 1;
14450aadb33SDmitri Tikhonov    while (i > 0 && q->aq_heap[ AE_PARENT(i) ]->ae_adv_time >=
14550aadb33SDmitri Tikhonov                                        q->aq_heap[ i ]->ae_adv_time)
14650aadb33SDmitri Tikhonov    {
14750aadb33SDmitri Tikhonov        attq_swap(q, i, AE_PARENT(i));
14850aadb33SDmitri Tikhonov        i = AE_PARENT(i);
14950aadb33SDmitri Tikhonov    }
15050aadb33SDmitri Tikhonov
15150aadb33SDmitri Tikhonov    attq_verify(q);
15250aadb33SDmitri Tikhonov
15350aadb33SDmitri Tikhonov    return 0;
15450aadb33SDmitri Tikhonov}
15550aadb33SDmitri Tikhonov
15650aadb33SDmitri Tikhonov
15750aadb33SDmitri Tikhonovstruct lsquic_conn *
15850aadb33SDmitri Tikhonovattq_pop (struct attq *q, lsquic_time_t cutoff)
15950aadb33SDmitri Tikhonov{
16050aadb33SDmitri Tikhonov    struct lsquic_conn *conn;
16150aadb33SDmitri Tikhonov    struct attq_elem *el;
16250aadb33SDmitri Tikhonov
16350aadb33SDmitri Tikhonov    if (q->aq_nelem == 0)
16450aadb33SDmitri Tikhonov        return NULL;
16550aadb33SDmitri Tikhonov
16650aadb33SDmitri Tikhonov    el = q->aq_heap[0];
16750aadb33SDmitri Tikhonov    if (el->ae_adv_time >= cutoff)
16850aadb33SDmitri Tikhonov        return NULL;
16950aadb33SDmitri Tikhonov
17050aadb33SDmitri Tikhonov    conn = el->ae_conn;
17150aadb33SDmitri Tikhonov    attq_remove(q, conn);
17250aadb33SDmitri Tikhonov    return conn;
17350aadb33SDmitri Tikhonov}
17450aadb33SDmitri Tikhonov
17550aadb33SDmitri Tikhonov
17650aadb33SDmitri Tikhonovstatic void
17750aadb33SDmitri Tikhonovattq_heapify (struct attq *q, unsigned i)
17850aadb33SDmitri Tikhonov{
17950aadb33SDmitri Tikhonov    unsigned smallest;
18050aadb33SDmitri Tikhonov
18150aadb33SDmitri Tikhonov    assert(i < q->aq_nelem);
18250aadb33SDmitri Tikhonov
18350aadb33SDmitri Tikhonov    if (AE_LCHILD(i) < q->aq_nelem)
18450aadb33SDmitri Tikhonov    {
18550aadb33SDmitri Tikhonov        if (q->aq_heap[ AE_LCHILD(i) ]->ae_adv_time <
18650aadb33SDmitri Tikhonov                                    q->aq_heap[ i ]->ae_adv_time)
18750aadb33SDmitri Tikhonov            smallest = AE_LCHILD(i);
18850aadb33SDmitri Tikhonov        else
18950aadb33SDmitri Tikhonov            smallest = i;
19050aadb33SDmitri Tikhonov        if (AE_RCHILD(i) < q->aq_nelem &&
19150aadb33SDmitri Tikhonov            q->aq_heap[ AE_RCHILD(i) ]->ae_adv_time <
19250aadb33SDmitri Tikhonov                                    q->aq_heap[ smallest ]->ae_adv_time)
19350aadb33SDmitri Tikhonov            smallest = AE_RCHILD(i);
19450aadb33SDmitri Tikhonov    }
19550aadb33SDmitri Tikhonov    else
19650aadb33SDmitri Tikhonov        smallest = i;
19750aadb33SDmitri Tikhonov
19850aadb33SDmitri Tikhonov    if (smallest != i)
19950aadb33SDmitri Tikhonov    {
20050aadb33SDmitri Tikhonov        attq_swap(q, smallest, i);
20150aadb33SDmitri Tikhonov        attq_heapify(q, smallest);
20250aadb33SDmitri Tikhonov    }
20350aadb33SDmitri Tikhonov}
20450aadb33SDmitri Tikhonov
20550aadb33SDmitri Tikhonov
20650aadb33SDmitri Tikhonovvoid
20750aadb33SDmitri Tikhonovattq_remove (struct attq *q, struct lsquic_conn *conn)
20850aadb33SDmitri Tikhonov{
20950aadb33SDmitri Tikhonov    struct attq_elem *el;
21050aadb33SDmitri Tikhonov    unsigned idx;
21150aadb33SDmitri Tikhonov
21250aadb33SDmitri Tikhonov    el = conn->cn_attq_elem;
21350aadb33SDmitri Tikhonov    idx = el->ae_heap_idx;
21450aadb33SDmitri Tikhonov
21550aadb33SDmitri Tikhonov    assert(q->aq_nelem > 0);
21650aadb33SDmitri Tikhonov    assert(q->aq_heap[idx] == el);
21750aadb33SDmitri Tikhonov    assert(conn->cn_attq_elem == el);
21850aadb33SDmitri Tikhonov
21950aadb33SDmitri Tikhonov    conn->cn_attq_elem = NULL;
22050aadb33SDmitri Tikhonov
22150aadb33SDmitri Tikhonov    q->aq_heap[ idx ] = q->aq_heap[ --q->aq_nelem ];
22250aadb33SDmitri Tikhonov    q->aq_heap[ idx ]->ae_heap_idx = idx;
22350aadb33SDmitri Tikhonov    if (idx > 0 && q->aq_heap[ idx ]->ae_adv_time <
22450aadb33SDmitri Tikhonov                                q->aq_heap[ AE_PARENT(idx) ]->ae_adv_time)
22550aadb33SDmitri Tikhonov    {
22650aadb33SDmitri Tikhonov        do
22750aadb33SDmitri Tikhonov        {
22850aadb33SDmitri Tikhonov            attq_swap(q, idx, AE_PARENT(idx));
22950aadb33SDmitri Tikhonov            idx = AE_PARENT(idx);
23050aadb33SDmitri Tikhonov        }
23150aadb33SDmitri Tikhonov        while (idx > 0 && q->aq_heap[ idx ]->ae_adv_time <
23250aadb33SDmitri Tikhonov                                q->aq_heap[ AE_PARENT(idx) ]->ae_adv_time);
23350aadb33SDmitri Tikhonov    }
23450aadb33SDmitri Tikhonov    else if (q->aq_nelem > 1 && idx < q->aq_nelem)
23550aadb33SDmitri Tikhonov        attq_heapify(q, idx);
2365392f7a3SLiteSpeed Tech    lsquic_malo_put(el);
23750aadb33SDmitri Tikhonov    attq_verify(q);
23850aadb33SDmitri Tikhonov}
23950aadb33SDmitri Tikhonov
24050aadb33SDmitri Tikhonov
24150aadb33SDmitri Tikhonovunsigned
24250aadb33SDmitri Tikhonovattq_count_before (struct attq *q, lsquic_time_t cutoff)
24350aadb33SDmitri Tikhonov{
24450aadb33SDmitri Tikhonov    unsigned level, total_count, level_count, i, level_max;
24550aadb33SDmitri Tikhonov
24650aadb33SDmitri Tikhonov    total_count = 0;
24750aadb33SDmitri Tikhonov    for (i = 0, level = 0;; ++level)
24850aadb33SDmitri Tikhonov    {
24950aadb33SDmitri Tikhonov        level_count = 0;
25050aadb33SDmitri Tikhonov        level_max = i + (1U << level);
25150aadb33SDmitri Tikhonov        for ( ; i < level_max && i < q->aq_nelem; ++i)
25250aadb33SDmitri Tikhonov            level_count += q->aq_heap[i]->ae_adv_time < cutoff;
25350aadb33SDmitri Tikhonov        total_count += level_count;
25450aadb33SDmitri Tikhonov        if (level_count < (1U << level))
25550aadb33SDmitri Tikhonov            return total_count;
25650aadb33SDmitri Tikhonov    }
25750aadb33SDmitri Tikhonov    assert(0);
258ad08470cSDmitri Tikhonov    return total_count;
25950aadb33SDmitri Tikhonov}
26050aadb33SDmitri Tikhonov
26150aadb33SDmitri Tikhonov
2620adf085aSDmitri Tikhonovconst struct attq_elem *
2630adf085aSDmitri Tikhonovattq_next (struct attq *q)
26450aadb33SDmitri Tikhonov{
26550aadb33SDmitri Tikhonov    if (q->aq_nelem > 0)
2660adf085aSDmitri Tikhonov        return q->aq_heap[0];
26750aadb33SDmitri Tikhonov    else
26850aadb33SDmitri Tikhonov        return NULL;
26950aadb33SDmitri Tikhonov}
2700adf085aSDmitri Tikhonov
2710adf085aSDmitri Tikhonov
2720adf085aSDmitri Tikhonovconst char *
2730adf085aSDmitri Tikhonovlsquic_attq_why2str (enum ae_why why)
2740adf085aSDmitri Tikhonov{
2750adf085aSDmitri Tikhonov    switch (why)
2760adf085aSDmitri Tikhonov    {
2770adf085aSDmitri Tikhonov    case AEW_PACER:
2780adf085aSDmitri Tikhonov        return "PACER";
2790adf085aSDmitri Tikhonov    case AEW_MINI_EXPIRE:
2800adf085aSDmitri Tikhonov        return "MINI-EXPIRE";
2810adf085aSDmitri Tikhonov    default:
2820adf085aSDmitri Tikhonov        why -= N_AEWS;
2830adf085aSDmitri Tikhonov        if ((unsigned) why < (unsigned) MAX_LSQUIC_ALARMS)
2840adf085aSDmitri Tikhonov            return lsquic_alid2str[why];
2850adf085aSDmitri Tikhonov        return "UNKNOWN";
2860adf085aSDmitri Tikhonov    }
2870adf085aSDmitri Tikhonov}
288