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