lsquic_attq.c revision 7d09751d
17d09751dSDmitri Tikhonov/* Copyright (c) 2017 - 2020 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