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