lsquic_attq.c revision 229fce07
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 1650aadb33SDmitri Tikhonov 1750aadb33SDmitri Tikhonov#include "lsquic.h" 1850aadb33SDmitri Tikhonov#include "lsquic_types.h" 1950aadb33SDmitri Tikhonov#include "lsquic_int_types.h" 2050aadb33SDmitri Tikhonov#include "lsquic_attq.h" 2150aadb33SDmitri Tikhonov#include "lsquic_malo.h" 2250aadb33SDmitri Tikhonov#include "lsquic_conn.h" 2350aadb33SDmitri Tikhonov 2450aadb33SDmitri Tikhonov 2550aadb33SDmitri Tikhonovstruct attq 2650aadb33SDmitri Tikhonov{ 2750aadb33SDmitri Tikhonov struct malo *aq_elem_malo; 2850aadb33SDmitri Tikhonov struct attq_elem **aq_heap; 2950aadb33SDmitri Tikhonov unsigned aq_nelem; 3050aadb33SDmitri Tikhonov unsigned aq_nalloc; 3150aadb33SDmitri Tikhonov}; 3250aadb33SDmitri Tikhonov 3350aadb33SDmitri Tikhonov 3450aadb33SDmitri Tikhonovstruct attq * 3550aadb33SDmitri Tikhonovattq_create (void) 3650aadb33SDmitri Tikhonov{ 3750aadb33SDmitri Tikhonov struct attq *q; 3850aadb33SDmitri Tikhonov struct malo *malo; 3950aadb33SDmitri Tikhonov 4050aadb33SDmitri Tikhonov malo = lsquic_malo_create(sizeof(struct attq_elem)); 4150aadb33SDmitri Tikhonov if (!malo) 4250aadb33SDmitri Tikhonov return NULL; 4350aadb33SDmitri Tikhonov 4450aadb33SDmitri Tikhonov q = calloc(1, sizeof(*q)); 4550aadb33SDmitri Tikhonov if (!q) 4650aadb33SDmitri Tikhonov { 4750aadb33SDmitri Tikhonov lsquic_malo_destroy(malo); 4850aadb33SDmitri Tikhonov return NULL; 4950aadb33SDmitri Tikhonov } 5050aadb33SDmitri Tikhonov 5150aadb33SDmitri Tikhonov q->aq_elem_malo = malo; 5250aadb33SDmitri Tikhonov return q; 5350aadb33SDmitri Tikhonov} 5450aadb33SDmitri Tikhonov 5550aadb33SDmitri Tikhonov 5650aadb33SDmitri Tikhonovvoid 5750aadb33SDmitri Tikhonovattq_destroy (struct attq *q) 5850aadb33SDmitri Tikhonov{ 5950aadb33SDmitri Tikhonov lsquic_malo_destroy(q->aq_elem_malo); 6050aadb33SDmitri Tikhonov free(q->aq_heap); 6150aadb33SDmitri Tikhonov free(q); 6250aadb33SDmitri Tikhonov} 6350aadb33SDmitri Tikhonov 6450aadb33SDmitri Tikhonov 6550aadb33SDmitri Tikhonov 6650aadb33SDmitri Tikhonov#define AE_PARENT(i) ((i - 1) / 2) 6750aadb33SDmitri Tikhonov#define AE_LCHILD(i) (2 * i + 1) 6850aadb33SDmitri Tikhonov#define AE_RCHILD(i) (2 * i + 2) 6950aadb33SDmitri Tikhonov 7050aadb33SDmitri Tikhonov 7150aadb33SDmitri Tikhonov#ifndef NDEBUG 7250aadb33SDmitri Tikhonovstatic void 7350aadb33SDmitri Tikhonovattq_verify (struct attq *q) 7450aadb33SDmitri Tikhonov{ 7550aadb33SDmitri Tikhonov unsigned i; 7650aadb33SDmitri Tikhonov 7750aadb33SDmitri Tikhonov for (i = 0; i < q->aq_nelem; ++i) 7850aadb33SDmitri Tikhonov { 7950aadb33SDmitri Tikhonov assert(q->aq_heap[i]->ae_heap_idx == i); 8050aadb33SDmitri Tikhonov if (AE_LCHILD(i) < q->aq_nelem) 8150aadb33SDmitri Tikhonov assert(q->aq_heap[i]->ae_adv_time <= 8250aadb33SDmitri Tikhonov q->aq_heap[AE_LCHILD(i)]->ae_adv_time); 8350aadb33SDmitri Tikhonov if (AE_RCHILD(i) < q->aq_nelem) 8450aadb33SDmitri Tikhonov assert(q->aq_heap[i]->ae_adv_time <= 8550aadb33SDmitri Tikhonov q->aq_heap[AE_RCHILD(i)]->ae_adv_time); 8650aadb33SDmitri Tikhonov } 8750aadb33SDmitri Tikhonov} 8850aadb33SDmitri Tikhonov#else 8950aadb33SDmitri Tikhonov#define attq_verify(q) 9050aadb33SDmitri Tikhonov#endif 9150aadb33SDmitri Tikhonov 9250aadb33SDmitri Tikhonov 9350aadb33SDmitri Tikhonovstatic void 9450aadb33SDmitri Tikhonovattq_swap (struct attq *q, unsigned a, unsigned b) 9550aadb33SDmitri Tikhonov{ 9650aadb33SDmitri Tikhonov struct attq_elem *el; 9750aadb33SDmitri Tikhonov 9850aadb33SDmitri Tikhonov el = q->aq_heap[ a ]; 9950aadb33SDmitri Tikhonov q->aq_heap[ a ] = q->aq_heap[ b ]; 10050aadb33SDmitri Tikhonov q->aq_heap[ b ] = el; 10150aadb33SDmitri Tikhonov q->aq_heap[ a ]->ae_heap_idx = a; 10250aadb33SDmitri Tikhonov q->aq_heap[ b ]->ae_heap_idx = b; 10350aadb33SDmitri Tikhonov} 10450aadb33SDmitri Tikhonov 10550aadb33SDmitri Tikhonov 10650aadb33SDmitri Tikhonovint 10750aadb33SDmitri Tikhonovattq_add (struct attq *q, struct lsquic_conn *conn, 10850aadb33SDmitri Tikhonov lsquic_time_t advisory_time) 10950aadb33SDmitri Tikhonov{ 11050aadb33SDmitri Tikhonov struct attq_elem *el, **heap; 11150aadb33SDmitri Tikhonov unsigned n, i; 11250aadb33SDmitri Tikhonov 11350aadb33SDmitri Tikhonov if (q->aq_nelem >= q->aq_nalloc) 11450aadb33SDmitri Tikhonov { 11550aadb33SDmitri Tikhonov if (q->aq_nalloc > 0) 11650aadb33SDmitri Tikhonov n = q->aq_nalloc * 2; 11750aadb33SDmitri Tikhonov else 11850aadb33SDmitri Tikhonov n = 8; 11950aadb33SDmitri Tikhonov heap = realloc(q->aq_heap, n * sizeof(q->aq_heap[0])); 12050aadb33SDmitri Tikhonov if (!heap) 12150aadb33SDmitri Tikhonov return -1; 12250aadb33SDmitri Tikhonov q->aq_heap = heap; 12350aadb33SDmitri Tikhonov q->aq_nalloc = n; 12450aadb33SDmitri Tikhonov } 12550aadb33SDmitri Tikhonov 12650aadb33SDmitri Tikhonov el = lsquic_malo_get(q->aq_elem_malo); 12750aadb33SDmitri Tikhonov if (!el) 12850aadb33SDmitri Tikhonov return -1; 12950aadb33SDmitri Tikhonov el->ae_adv_time = advisory_time; 13050aadb33SDmitri Tikhonov 13150aadb33SDmitri Tikhonov /* The only place linkage between conn and attq_elem occurs: */ 13250aadb33SDmitri Tikhonov el->ae_conn = conn; 13350aadb33SDmitri Tikhonov conn->cn_attq_elem = el; 13450aadb33SDmitri Tikhonov 13550aadb33SDmitri Tikhonov el->ae_heap_idx = q->aq_nelem; 13650aadb33SDmitri Tikhonov q->aq_heap[ q->aq_nelem++ ] = el; 13750aadb33SDmitri Tikhonov 13850aadb33SDmitri Tikhonov i = q->aq_nelem - 1; 13950aadb33SDmitri Tikhonov while (i > 0 && q->aq_heap[ AE_PARENT(i) ]->ae_adv_time >= 14050aadb33SDmitri Tikhonov q->aq_heap[ i ]->ae_adv_time) 14150aadb33SDmitri Tikhonov { 14250aadb33SDmitri Tikhonov attq_swap(q, i, AE_PARENT(i)); 14350aadb33SDmitri Tikhonov i = AE_PARENT(i); 14450aadb33SDmitri Tikhonov } 14550aadb33SDmitri Tikhonov 14650aadb33SDmitri Tikhonov attq_verify(q); 14750aadb33SDmitri Tikhonov 14850aadb33SDmitri Tikhonov return 0; 14950aadb33SDmitri Tikhonov} 15050aadb33SDmitri Tikhonov 15150aadb33SDmitri Tikhonov 15250aadb33SDmitri Tikhonovstruct lsquic_conn * 15350aadb33SDmitri Tikhonovattq_pop (struct attq *q, lsquic_time_t cutoff) 15450aadb33SDmitri Tikhonov{ 15550aadb33SDmitri Tikhonov struct lsquic_conn *conn; 15650aadb33SDmitri Tikhonov struct attq_elem *el; 15750aadb33SDmitri Tikhonov 15850aadb33SDmitri Tikhonov if (q->aq_nelem == 0) 15950aadb33SDmitri Tikhonov return NULL; 16050aadb33SDmitri Tikhonov 16150aadb33SDmitri Tikhonov el = q->aq_heap[0]; 16250aadb33SDmitri Tikhonov if (el->ae_adv_time >= cutoff) 16350aadb33SDmitri Tikhonov return NULL; 16450aadb33SDmitri Tikhonov 16550aadb33SDmitri Tikhonov conn = el->ae_conn; 16650aadb33SDmitri Tikhonov attq_remove(q, conn); 16750aadb33SDmitri Tikhonov return conn; 16850aadb33SDmitri Tikhonov} 16950aadb33SDmitri Tikhonov 17050aadb33SDmitri Tikhonov 17150aadb33SDmitri Tikhonovstatic void 17250aadb33SDmitri Tikhonovattq_heapify (struct attq *q, unsigned i) 17350aadb33SDmitri Tikhonov{ 17450aadb33SDmitri Tikhonov unsigned smallest; 17550aadb33SDmitri Tikhonov 17650aadb33SDmitri Tikhonov assert(i < q->aq_nelem); 17750aadb33SDmitri Tikhonov 17850aadb33SDmitri Tikhonov if (AE_LCHILD(i) < q->aq_nelem) 17950aadb33SDmitri Tikhonov { 18050aadb33SDmitri Tikhonov if (q->aq_heap[ AE_LCHILD(i) ]->ae_adv_time < 18150aadb33SDmitri Tikhonov q->aq_heap[ i ]->ae_adv_time) 18250aadb33SDmitri Tikhonov smallest = AE_LCHILD(i); 18350aadb33SDmitri Tikhonov else 18450aadb33SDmitri Tikhonov smallest = i; 18550aadb33SDmitri Tikhonov if (AE_RCHILD(i) < q->aq_nelem && 18650aadb33SDmitri Tikhonov q->aq_heap[ AE_RCHILD(i) ]->ae_adv_time < 18750aadb33SDmitri Tikhonov q->aq_heap[ smallest ]->ae_adv_time) 18850aadb33SDmitri Tikhonov smallest = AE_RCHILD(i); 18950aadb33SDmitri Tikhonov } 19050aadb33SDmitri Tikhonov else 19150aadb33SDmitri Tikhonov smallest = i; 19250aadb33SDmitri Tikhonov 19350aadb33SDmitri Tikhonov if (smallest != i) 19450aadb33SDmitri Tikhonov { 19550aadb33SDmitri Tikhonov attq_swap(q, smallest, i); 19650aadb33SDmitri Tikhonov attq_heapify(q, smallest); 19750aadb33SDmitri Tikhonov } 19850aadb33SDmitri Tikhonov} 19950aadb33SDmitri Tikhonov 20050aadb33SDmitri Tikhonov 20150aadb33SDmitri Tikhonovvoid 20250aadb33SDmitri Tikhonovattq_remove (struct attq *q, struct lsquic_conn *conn) 20350aadb33SDmitri Tikhonov{ 20450aadb33SDmitri Tikhonov struct attq_elem *el; 20550aadb33SDmitri Tikhonov unsigned idx; 20650aadb33SDmitri Tikhonov 20750aadb33SDmitri Tikhonov el = conn->cn_attq_elem; 20850aadb33SDmitri Tikhonov idx = el->ae_heap_idx; 20950aadb33SDmitri Tikhonov 21050aadb33SDmitri Tikhonov assert(q->aq_nelem > 0); 21150aadb33SDmitri Tikhonov assert(q->aq_heap[idx] == el); 21250aadb33SDmitri Tikhonov assert(conn->cn_attq_elem == el); 21350aadb33SDmitri Tikhonov 21450aadb33SDmitri Tikhonov conn->cn_attq_elem = NULL; 21550aadb33SDmitri Tikhonov lsquic_malo_put(el); 21650aadb33SDmitri Tikhonov 21750aadb33SDmitri Tikhonov q->aq_heap[ idx ] = q->aq_heap[ --q->aq_nelem ]; 21850aadb33SDmitri Tikhonov q->aq_heap[ idx ]->ae_heap_idx = idx; 21950aadb33SDmitri Tikhonov if (idx > 0 && q->aq_heap[ idx ]->ae_adv_time < 22050aadb33SDmitri Tikhonov q->aq_heap[ AE_PARENT(idx) ]->ae_adv_time) 22150aadb33SDmitri Tikhonov { 22250aadb33SDmitri Tikhonov do 22350aadb33SDmitri Tikhonov { 22450aadb33SDmitri Tikhonov attq_swap(q, idx, AE_PARENT(idx)); 22550aadb33SDmitri Tikhonov idx = AE_PARENT(idx); 22650aadb33SDmitri Tikhonov } 22750aadb33SDmitri Tikhonov while (idx > 0 && q->aq_heap[ idx ]->ae_adv_time < 22850aadb33SDmitri Tikhonov q->aq_heap[ AE_PARENT(idx) ]->ae_adv_time); 22950aadb33SDmitri Tikhonov } 23050aadb33SDmitri Tikhonov else if (q->aq_nelem > 1 && idx < q->aq_nelem) 23150aadb33SDmitri Tikhonov attq_heapify(q, idx); 23250aadb33SDmitri Tikhonov attq_verify(q); 23350aadb33SDmitri Tikhonov} 23450aadb33SDmitri Tikhonov 23550aadb33SDmitri Tikhonov 23650aadb33SDmitri Tikhonovunsigned 23750aadb33SDmitri Tikhonovattq_count_before (struct attq *q, lsquic_time_t cutoff) 23850aadb33SDmitri Tikhonov{ 23950aadb33SDmitri Tikhonov unsigned level, total_count, level_count, i, level_max; 24050aadb33SDmitri Tikhonov 24150aadb33SDmitri Tikhonov total_count = 0; 24250aadb33SDmitri Tikhonov for (i = 0, level = 0;; ++level) 24350aadb33SDmitri Tikhonov { 24450aadb33SDmitri Tikhonov level_count = 0; 24550aadb33SDmitri Tikhonov level_max = i + (1U << level); 24650aadb33SDmitri Tikhonov for ( ; i < level_max && i < q->aq_nelem; ++i) 24750aadb33SDmitri Tikhonov level_count += q->aq_heap[i]->ae_adv_time < cutoff; 24850aadb33SDmitri Tikhonov total_count += level_count; 24950aadb33SDmitri Tikhonov if (level_count < (1U << level)) 25050aadb33SDmitri Tikhonov return total_count; 25150aadb33SDmitri Tikhonov } 25250aadb33SDmitri Tikhonov assert(0); 25350aadb33SDmitri Tikhonov} 25450aadb33SDmitri Tikhonov 25550aadb33SDmitri Tikhonov 25650aadb33SDmitri Tikhonovconst lsquic_time_t * 25750aadb33SDmitri Tikhonovattq_next_time (struct attq *q) 25850aadb33SDmitri Tikhonov{ 25950aadb33SDmitri Tikhonov if (q->aq_nelem > 0) 26050aadb33SDmitri Tikhonov return &q->aq_heap[0]->ae_adv_time; 26150aadb33SDmitri Tikhonov else 26250aadb33SDmitri Tikhonov return NULL; 26350aadb33SDmitri Tikhonov} 264