lsquic_spi.c revision 50aadb33
150aadb33SDmitri Tikhonov/* Copyright (c) 2017 LiteSpeed Technologies Inc. See LICENSE. */ 250aadb33SDmitri Tikhonov/* 350aadb33SDmitri Tikhonov * lsquic_spi.c - implementation of Stream Priority Iterator. 450aadb33SDmitri Tikhonov */ 550aadb33SDmitri Tikhonov 650aadb33SDmitri Tikhonov#include <assert.h> 750aadb33SDmitri Tikhonov#include <inttypes.h> 850aadb33SDmitri Tikhonov#include <stdint.h> 950aadb33SDmitri Tikhonov#include <stdlib.h> 1050aadb33SDmitri Tikhonov#include <sys/queue.h> 1150aadb33SDmitri Tikhonov#include <sys/types.h> 1250aadb33SDmitri Tikhonov 1350aadb33SDmitri Tikhonov#include "lsquic_types.h" 1450aadb33SDmitri Tikhonov#include "lsquic_int_types.h" 1550aadb33SDmitri Tikhonov#include "lsquic_sfcw.h" 1650aadb33SDmitri Tikhonov#include "lsquic_stream.h" 1750aadb33SDmitri Tikhonov#include "lsquic_spi.h" 1850aadb33SDmitri Tikhonov 1950aadb33SDmitri Tikhonov#define LSQUIC_LOGGER_MODULE LSQLM_SPI 2050aadb33SDmitri Tikhonov#define LSQUIC_LOG_CONN_ID iter->spi_cid 2150aadb33SDmitri Tikhonov#include "lsquic_logger.h" 2250aadb33SDmitri Tikhonov 2350aadb33SDmitri Tikhonov#define SPI_DEBUG(fmt, a...) LSQ_DEBUG("%s: " fmt, iter->spi_name, a) 2450aadb33SDmitri Tikhonov 2550aadb33SDmitri Tikhonov#define NEXT_STREAM(stream, off) \ 2650aadb33SDmitri Tikhonov (* (struct lsquic_stream **) ((unsigned char *) (stream) + (off))) 2750aadb33SDmitri Tikhonov 2850aadb33SDmitri Tikhonov 2950aadb33SDmitri Tikhonovstatic void 3050aadb33SDmitri Tikhonovadd_stream_to_spi (struct stream_prio_iter *iter, lsquic_stream_t *stream) 3150aadb33SDmitri Tikhonov{ 3250aadb33SDmitri Tikhonov unsigned set, bit; 3350aadb33SDmitri Tikhonov set = stream->sm_priority >> 6; 3450aadb33SDmitri Tikhonov bit = stream->sm_priority & 0x3F; 3550aadb33SDmitri Tikhonov if (!(iter->spi_set[set] & (1ULL << bit))) 3650aadb33SDmitri Tikhonov { 3750aadb33SDmitri Tikhonov iter->spi_set[set] |= 1ULL << bit; 3850aadb33SDmitri Tikhonov TAILQ_INIT(&iter->spi_streams[ stream->sm_priority ]); 3950aadb33SDmitri Tikhonov } 4050aadb33SDmitri Tikhonov TAILQ_INSERT_TAIL(&iter->spi_streams[ stream->sm_priority ], 4150aadb33SDmitri Tikhonov stream, next_prio_stream); 4250aadb33SDmitri Tikhonov} 4350aadb33SDmitri Tikhonov 4450aadb33SDmitri Tikhonov 4550aadb33SDmitri Tikhonovvoid 4650aadb33SDmitri Tikhonovlsquic_spi_init_ext (struct stream_prio_iter *iter, struct lsquic_stream *first, 4750aadb33SDmitri Tikhonov struct lsquic_stream *last, uintptr_t next_ptr_offset, 4850aadb33SDmitri Tikhonov enum stream_flags onlist_mask, 4950aadb33SDmitri Tikhonov int (*filter)(void *, struct lsquic_stream *), 5050aadb33SDmitri Tikhonov void *filter_ctx, lsquic_cid_t cid, const char *name) 5150aadb33SDmitri Tikhonov{ 5250aadb33SDmitri Tikhonov struct lsquic_stream *stream; 5350aadb33SDmitri Tikhonov unsigned count; 5450aadb33SDmitri Tikhonov 5550aadb33SDmitri Tikhonov iter->spi_cid = cid; 5650aadb33SDmitri Tikhonov iter->spi_name = name ? name : "UNSET"; 5750aadb33SDmitri Tikhonov iter->spi_set[0] = 0; 5850aadb33SDmitri Tikhonov iter->spi_set[1] = 0; 5950aadb33SDmitri Tikhonov iter->spi_set[2] = 0; 6050aadb33SDmitri Tikhonov iter->spi_set[3] = 0; 6150aadb33SDmitri Tikhonov iter->spi_onlist_mask = onlist_mask; 6250aadb33SDmitri Tikhonov iter->spi_flags = 0; 6350aadb33SDmitri Tikhonov iter->spi_cur_prio = 0; 6450aadb33SDmitri Tikhonov iter->spi_prev_stream = NULL; 6550aadb33SDmitri Tikhonov iter->spi_next_stream = NULL; 6650aadb33SDmitri Tikhonov 6750aadb33SDmitri Tikhonov stream = first; 6850aadb33SDmitri Tikhonov count = 0; 6950aadb33SDmitri Tikhonov 7050aadb33SDmitri Tikhonov if (filter) 7150aadb33SDmitri Tikhonov while (1) 7250aadb33SDmitri Tikhonov { 7350aadb33SDmitri Tikhonov if (filter(filter_ctx, stream)) 7450aadb33SDmitri Tikhonov { 7550aadb33SDmitri Tikhonov add_stream_to_spi(iter, stream); 7650aadb33SDmitri Tikhonov ++count; 7750aadb33SDmitri Tikhonov } 7850aadb33SDmitri Tikhonov if (stream == last) 7950aadb33SDmitri Tikhonov break; 8050aadb33SDmitri Tikhonov stream = NEXT_STREAM(stream, next_ptr_offset); 8150aadb33SDmitri Tikhonov } 8250aadb33SDmitri Tikhonov else 8350aadb33SDmitri Tikhonov while (1) 8450aadb33SDmitri Tikhonov { 8550aadb33SDmitri Tikhonov add_stream_to_spi(iter, stream); 8650aadb33SDmitri Tikhonov ++count; 8750aadb33SDmitri Tikhonov if (stream == last) 8850aadb33SDmitri Tikhonov break; 8950aadb33SDmitri Tikhonov stream = NEXT_STREAM(stream, next_ptr_offset); 9050aadb33SDmitri Tikhonov } 9150aadb33SDmitri Tikhonov if (count > 2) 9250aadb33SDmitri Tikhonov SPI_DEBUG("initialized; # elems: %u; sets: [ %016"PRIX64", %016"PRIX64 9350aadb33SDmitri Tikhonov ", %016"PRIX64", %016"PRIX64" ]", count, iter->spi_set[0], 9450aadb33SDmitri Tikhonov iter->spi_set[1], iter->spi_set[2], iter->spi_set[3]); 9550aadb33SDmitri Tikhonov} 9650aadb33SDmitri Tikhonov 9750aadb33SDmitri Tikhonov 9850aadb33SDmitri Tikhonovstatic int 9950aadb33SDmitri Tikhonovfind_and_set_lowest_priority (struct stream_prio_iter *iter) 10050aadb33SDmitri Tikhonov{ 10150aadb33SDmitri Tikhonov unsigned set, prio; 10250aadb33SDmitri Tikhonov uint64_t mask; 10350aadb33SDmitri Tikhonov 10450aadb33SDmitri Tikhonov for (set = 0, prio = 0; set < 4; ++set, prio += 64) 10550aadb33SDmitri Tikhonov if (iter->spi_set[ set ]) 10650aadb33SDmitri Tikhonov break; 10750aadb33SDmitri Tikhonov 10850aadb33SDmitri Tikhonov if (set == 4) 10950aadb33SDmitri Tikhonov { 11050aadb33SDmitri Tikhonov //SPI_DEBUG("%s: cannot find any", __func__); 11150aadb33SDmitri Tikhonov return -1; 11250aadb33SDmitri Tikhonov } 11350aadb33SDmitri Tikhonov 11450aadb33SDmitri Tikhonov mask = iter->spi_set[set]; 11550aadb33SDmitri Tikhonov if (!(mask & ((1ULL << 32) - 1))) { prio += 32; mask >>= 32; } 11650aadb33SDmitri Tikhonov if (!(mask & ((1ULL << 16) - 1))) { prio += 16; mask >>= 16; } 11750aadb33SDmitri Tikhonov if (!(mask & ((1ULL << 8) - 1))) { prio += 8; mask >>= 8; } 11850aadb33SDmitri Tikhonov if (!(mask & ((1ULL << 4) - 1))) { prio += 4; mask >>= 4; } 11950aadb33SDmitri Tikhonov if (!(mask & ((1ULL << 2) - 1))) { prio += 2; mask >>= 2; } 12050aadb33SDmitri Tikhonov if (!(mask & ((1ULL << 1) - 1))) { prio += 1; } 12150aadb33SDmitri Tikhonov 12250aadb33SDmitri Tikhonov#ifndef NDEBUG 12350aadb33SDmitri Tikhonov unsigned bit; 12450aadb33SDmitri Tikhonov set = prio >> 6; 12550aadb33SDmitri Tikhonov bit = prio & 0x3F; 12650aadb33SDmitri Tikhonov assert(iter->spi_set[ set ] & (1ULL << bit)); 12750aadb33SDmitri Tikhonov#endif 12850aadb33SDmitri Tikhonov 12950aadb33SDmitri Tikhonov SPI_DEBUG("%s: prio %u -> %u", __func__, iter->spi_cur_prio, prio); 13050aadb33SDmitri Tikhonov iter->spi_cur_prio = prio; 13150aadb33SDmitri Tikhonov return 0; 13250aadb33SDmitri Tikhonov} 13350aadb33SDmitri Tikhonov 13450aadb33SDmitri Tikhonov 13550aadb33SDmitri Tikhonovstatic int 13650aadb33SDmitri Tikhonovfind_and_set_next_priority (struct stream_prio_iter *iter) 13750aadb33SDmitri Tikhonov{ 13850aadb33SDmitri Tikhonov unsigned set, bit, prio; 13950aadb33SDmitri Tikhonov uint64_t mask; 14050aadb33SDmitri Tikhonov 14150aadb33SDmitri Tikhonov /* Examine values in the same set first */ 14250aadb33SDmitri Tikhonov set = iter->spi_cur_prio >> 6; 14350aadb33SDmitri Tikhonov bit = iter->spi_cur_prio & 0x3F; 14450aadb33SDmitri Tikhonov prio = 64 * set; 14550aadb33SDmitri Tikhonov 14650aadb33SDmitri Tikhonov if (bit < 63) 14750aadb33SDmitri Tikhonov { 14850aadb33SDmitri Tikhonov mask = iter->spi_set[set]; 14950aadb33SDmitri Tikhonov mask &= ~((1ULL << (bit + 1)) - 1); 15050aadb33SDmitri Tikhonov if (mask) 15150aadb33SDmitri Tikhonov goto calc_priority; 15250aadb33SDmitri Tikhonov } 15350aadb33SDmitri Tikhonov 15450aadb33SDmitri Tikhonov ++set; 15550aadb33SDmitri Tikhonov prio += 64; 15650aadb33SDmitri Tikhonov for (; set < 4; ++set, prio += 64) 15750aadb33SDmitri Tikhonov if (iter->spi_set[ set ]) 15850aadb33SDmitri Tikhonov break; 15950aadb33SDmitri Tikhonov 16050aadb33SDmitri Tikhonov if (set == 4) 16150aadb33SDmitri Tikhonov { 16250aadb33SDmitri Tikhonov //SPI_DEBUG("%s: cannot find any", __func__); 16350aadb33SDmitri Tikhonov return -1; 16450aadb33SDmitri Tikhonov } 16550aadb33SDmitri Tikhonov 16650aadb33SDmitri Tikhonov mask = iter->spi_set[set]; 16750aadb33SDmitri Tikhonov 16850aadb33SDmitri Tikhonov calc_priority: 16950aadb33SDmitri Tikhonov if (!(mask & ((1ULL << 32) - 1))) { prio += 32; mask >>= 32; } 17050aadb33SDmitri Tikhonov if (!(mask & ((1ULL << 16) - 1))) { prio += 16; mask >>= 16; } 17150aadb33SDmitri Tikhonov if (!(mask & ((1ULL << 8) - 1))) { prio += 8; mask >>= 8; } 17250aadb33SDmitri Tikhonov if (!(mask & ((1ULL << 4) - 1))) { prio += 4; mask >>= 4; } 17350aadb33SDmitri Tikhonov if (!(mask & ((1ULL << 2) - 1))) { prio += 2; mask >>= 2; } 17450aadb33SDmitri Tikhonov if (!(mask & ((1ULL << 1) - 1))) { prio += 1; } 17550aadb33SDmitri Tikhonov 17650aadb33SDmitri Tikhonov#ifndef NDEBUG 17750aadb33SDmitri Tikhonov set = prio >> 6; 17850aadb33SDmitri Tikhonov bit = prio & 0x3F; 17950aadb33SDmitri Tikhonov assert(iter->spi_set[ set ] & (1ULL << bit)); 18050aadb33SDmitri Tikhonov#endif 18150aadb33SDmitri Tikhonov 18250aadb33SDmitri Tikhonov SPI_DEBUG("%s: prio %u -> %u", __func__, iter->spi_cur_prio, prio); 18350aadb33SDmitri Tikhonov iter->spi_cur_prio = prio; 18450aadb33SDmitri Tikhonov return 0; 18550aadb33SDmitri Tikhonov} 18650aadb33SDmitri Tikhonov 18750aadb33SDmitri Tikhonov 18850aadb33SDmitri Tikhonov/* Each stream returned by the iterator is processed in some fashion. If, 18950aadb33SDmitri Tikhonov * as a result of this, the stream gets taken off the original list, we 19050aadb33SDmitri Tikhonov * have to follow suit and remove it from the iterator's set of streams. 19150aadb33SDmitri Tikhonov */ 19250aadb33SDmitri Tikhonovstatic void 19350aadb33SDmitri Tikhonovmaybe_evict_prev (struct stream_prio_iter *iter) 19450aadb33SDmitri Tikhonov{ 19550aadb33SDmitri Tikhonov unsigned set, bit; 19650aadb33SDmitri Tikhonov 19750aadb33SDmitri Tikhonov if (0 == (iter->spi_prev_stream->stream_flags & iter->spi_onlist_mask)) 19850aadb33SDmitri Tikhonov { 19950aadb33SDmitri Tikhonov SPI_DEBUG("evict stream %u", iter->spi_prev_stream->id); 20050aadb33SDmitri Tikhonov TAILQ_REMOVE(&iter->spi_streams[ iter->spi_prev_prio ], 20150aadb33SDmitri Tikhonov iter->spi_prev_stream, next_prio_stream); 20250aadb33SDmitri Tikhonov if (TAILQ_EMPTY(&iter->spi_streams[ iter->spi_prev_prio ])) 20350aadb33SDmitri Tikhonov { 20450aadb33SDmitri Tikhonov set = iter->spi_prev_prio >> 6; 20550aadb33SDmitri Tikhonov bit = iter->spi_prev_prio & 0x3F; 20650aadb33SDmitri Tikhonov iter->spi_set[ set ] &= ~(1ULL << bit); 20750aadb33SDmitri Tikhonov SPI_DEBUG("priority %u now has no elements", iter->spi_prev_prio); 20850aadb33SDmitri Tikhonov } 20950aadb33SDmitri Tikhonov iter->spi_prev_stream = NULL; 21050aadb33SDmitri Tikhonov } 21150aadb33SDmitri Tikhonov} 21250aadb33SDmitri Tikhonov 21350aadb33SDmitri Tikhonov 21450aadb33SDmitri Tikhonovlsquic_stream_t * 21550aadb33SDmitri Tikhonovlsquic_spi_first (struct stream_prio_iter *iter) 21650aadb33SDmitri Tikhonov{ 21750aadb33SDmitri Tikhonov lsquic_stream_t *stream; 21850aadb33SDmitri Tikhonov unsigned set, bit; 21950aadb33SDmitri Tikhonov 22050aadb33SDmitri Tikhonov if (iter->spi_prev_stream) 22150aadb33SDmitri Tikhonov maybe_evict_prev(iter); 22250aadb33SDmitri Tikhonov 22350aadb33SDmitri Tikhonov iter->spi_cur_prio = 0; 22450aadb33SDmitri Tikhonov set = iter->spi_cur_prio >> 6; 22550aadb33SDmitri Tikhonov bit = iter->spi_cur_prio & 0x3F; 22650aadb33SDmitri Tikhonov 22750aadb33SDmitri Tikhonov if (!(iter->spi_set[set] & (1ULL << bit))) 22850aadb33SDmitri Tikhonov { 22950aadb33SDmitri Tikhonov if (0 != find_and_set_lowest_priority(iter)) 23050aadb33SDmitri Tikhonov { 23150aadb33SDmitri Tikhonov SPI_DEBUG("%s: return NULL", __func__); 23250aadb33SDmitri Tikhonov return NULL; 23350aadb33SDmitri Tikhonov } 23450aadb33SDmitri Tikhonov } 23550aadb33SDmitri Tikhonov 23650aadb33SDmitri Tikhonov stream = TAILQ_FIRST(&iter->spi_streams[ iter->spi_cur_prio ]); 23750aadb33SDmitri Tikhonov iter->spi_prev_prio = iter->spi_cur_prio; 23850aadb33SDmitri Tikhonov iter->spi_prev_stream = stream; 23950aadb33SDmitri Tikhonov iter->spi_next_stream = TAILQ_NEXT(stream, next_prio_stream); 24050aadb33SDmitri Tikhonov if (stream->id != 1 && stream->id != 3) 24150aadb33SDmitri Tikhonov SPI_DEBUG("%s: return stream %u, priority %u", __func__, stream->id, 24250aadb33SDmitri Tikhonov iter->spi_cur_prio); 24350aadb33SDmitri Tikhonov return stream; 24450aadb33SDmitri Tikhonov} 24550aadb33SDmitri Tikhonov 24650aadb33SDmitri Tikhonov 24750aadb33SDmitri Tikhonovlsquic_stream_t * 24850aadb33SDmitri Tikhonovlsquic_spi_next (struct stream_prio_iter *iter) 24950aadb33SDmitri Tikhonov{ 25050aadb33SDmitri Tikhonov lsquic_stream_t *stream; 25150aadb33SDmitri Tikhonov 25250aadb33SDmitri Tikhonov if (iter->spi_prev_stream) 25350aadb33SDmitri Tikhonov maybe_evict_prev(iter); 25450aadb33SDmitri Tikhonov 25550aadb33SDmitri Tikhonov stream = iter->spi_next_stream; 25650aadb33SDmitri Tikhonov if (stream) 25750aadb33SDmitri Tikhonov { 25850aadb33SDmitri Tikhonov assert(iter->spi_prev_prio == iter->spi_cur_prio); 25950aadb33SDmitri Tikhonov iter->spi_prev_stream = stream; 26050aadb33SDmitri Tikhonov iter->spi_next_stream = TAILQ_NEXT(stream, next_prio_stream); 26150aadb33SDmitri Tikhonov if (stream->id != 1 && stream->id != 3) 26250aadb33SDmitri Tikhonov SPI_DEBUG("%s: return stream %u, priority %u", __func__, stream->id, 26350aadb33SDmitri Tikhonov iter->spi_cur_prio); 26450aadb33SDmitri Tikhonov return stream; 26550aadb33SDmitri Tikhonov } 26650aadb33SDmitri Tikhonov 26750aadb33SDmitri Tikhonov if (iter->spi_flags & SPI_EXHAUST_PRIO) 26850aadb33SDmitri Tikhonov { 26950aadb33SDmitri Tikhonov stream = TAILQ_FIRST(&iter->spi_streams[ iter->spi_cur_prio ]); 27050aadb33SDmitri Tikhonov if (stream) 27150aadb33SDmitri Tikhonov { 27250aadb33SDmitri Tikhonov iter->spi_prev_stream = stream; 27350aadb33SDmitri Tikhonov iter->spi_next_stream = TAILQ_NEXT(stream, next_prio_stream); 27450aadb33SDmitri Tikhonov if (stream->id != 1 && stream->id != 3) 27550aadb33SDmitri Tikhonov SPI_DEBUG("%s: return stream %u, priority %u", __func__, 27650aadb33SDmitri Tikhonov stream->id, iter->spi_cur_prio); 27750aadb33SDmitri Tikhonov return stream; 27850aadb33SDmitri Tikhonov } 27950aadb33SDmitri Tikhonov else 28050aadb33SDmitri Tikhonov { 28150aadb33SDmitri Tikhonov SPI_DEBUG("%s: priority %u empty, call first again", __func__, 28250aadb33SDmitri Tikhonov iter->spi_cur_prio); 28350aadb33SDmitri Tikhonov return lsquic_spi_first(iter); 28450aadb33SDmitri Tikhonov } 28550aadb33SDmitri Tikhonov } 28650aadb33SDmitri Tikhonov 28750aadb33SDmitri Tikhonov if (0 != find_and_set_next_priority(iter)) 28850aadb33SDmitri Tikhonov { 28950aadb33SDmitri Tikhonov //SPI_DEBUG("%s: return NULL", __func__); 29050aadb33SDmitri Tikhonov return NULL; 29150aadb33SDmitri Tikhonov } 29250aadb33SDmitri Tikhonov 29350aadb33SDmitri Tikhonov stream = TAILQ_FIRST(&iter->spi_streams[ iter->spi_cur_prio ]); 29450aadb33SDmitri Tikhonov iter->spi_prev_prio = iter->spi_cur_prio; 29550aadb33SDmitri Tikhonov iter->spi_prev_stream = stream; 29650aadb33SDmitri Tikhonov iter->spi_next_stream = TAILQ_NEXT(stream, next_prio_stream); 29750aadb33SDmitri Tikhonov 29850aadb33SDmitri Tikhonov if (stream->id != 1 && stream->id != 3) 29950aadb33SDmitri Tikhonov SPI_DEBUG("%s: return stream %u, priority %u", __func__, stream->id, 30050aadb33SDmitri Tikhonov iter->spi_cur_prio); 30150aadb33SDmitri Tikhonov return stream; 30250aadb33SDmitri Tikhonov} 30350aadb33SDmitri Tikhonov 30450aadb33SDmitri Tikhonov 30550aadb33SDmitri Tikhonovvoid 30650aadb33SDmitri Tikhonovlsquic_spi_exhaust_on (struct stream_prio_iter *iter) 30750aadb33SDmitri Tikhonov{ 30850aadb33SDmitri Tikhonov SPI_DEBUG("%s: exhaust %d -> 1", __func__, 30950aadb33SDmitri Tikhonov !!(iter->spi_flags & SPI_EXHAUST_PRIO)); 31050aadb33SDmitri Tikhonov iter->spi_flags |= SPI_EXHAUST_PRIO; 31150aadb33SDmitri Tikhonov} 312