450 lines
13 KiB
C
450 lines
13 KiB
C
/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc. See LICENSE. */
|
|
#include <assert.h>
|
|
#include <inttypes.h>
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <string.h>
|
|
|
|
#ifdef WIN32
|
|
#include "vc_compat.h"
|
|
#endif
|
|
|
|
#include "lsquic_int_types.h"
|
|
#include "lsquic_rechist.h"
|
|
#include "lsquic_util.h"
|
|
|
|
|
|
static void
|
|
test4 (void)
|
|
{
|
|
lsquic_rechist_t rechist;
|
|
const struct lsquic_packno_range *range;
|
|
lsquic_packno_t packno;
|
|
|
|
lsquic_rechist_init(&rechist, 0, 0);
|
|
|
|
for (packno = 11917; packno <= 11941; ++packno)
|
|
lsquic_rechist_received(&rechist, packno, 0);
|
|
for (packno = 11946; packno <= 11994; ++packno)
|
|
lsquic_rechist_received(&rechist, packno, 0);
|
|
|
|
range = lsquic_rechist_first(&rechist);
|
|
assert(range);
|
|
assert(range->high == 11994);
|
|
assert(range->low == 11946);
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(range);
|
|
assert(range->high == 11941);
|
|
assert(range->low == 11917);
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(!range);
|
|
|
|
lsquic_rechist_received(&rechist, 11995, 0);
|
|
lsquic_rechist_received(&rechist, 11996, 0);
|
|
|
|
range = lsquic_rechist_first(&rechist);
|
|
assert(range);
|
|
assert(range->high == 11996);
|
|
assert(range->low == 11946);
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(range);
|
|
assert(range->high == 11941);
|
|
assert(range->low == 11917);
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(!range);
|
|
|
|
lsquic_rechist_received(&rechist, 11912, 0);
|
|
lsquic_rechist_stop_wait(&rechist, 11860);
|
|
|
|
range = lsquic_rechist_first(&rechist);
|
|
assert(range);
|
|
assert(range->high == 11996);
|
|
assert(range->low == 11946);
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(range);
|
|
assert(range->high == 11941);
|
|
assert(range->low == 11917);
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(range);
|
|
assert(range->high == 11912);
|
|
assert(range->low == 11912);
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(!range);
|
|
|
|
for (packno = 12169; packno <= 12193; ++packno)
|
|
lsquic_rechist_received(&rechist, packno, 0);
|
|
|
|
range = lsquic_rechist_first(&rechist);
|
|
assert(range);
|
|
assert(range->high == 12193);
|
|
assert(range->low == 12169);
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(range);
|
|
assert(range->high == 11996);
|
|
assert(range->low == 11946);
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(range);
|
|
assert(range->high == 11941);
|
|
assert(range->low == 11917);
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(range);
|
|
assert(range->high == 11912);
|
|
assert(range->low == 11912);
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(!range);
|
|
|
|
lsquic_rechist_cleanup(&rechist);
|
|
}
|
|
|
|
|
|
static void
|
|
rechist2str (lsquic_rechist_t *rechist, char *buf, size_t bufsz)
|
|
{
|
|
const struct lsquic_packno_range *range;
|
|
size_t off;
|
|
int n;
|
|
|
|
for (off = 0, range = lsquic_rechist_first(rechist);
|
|
range && off < bufsz;
|
|
off += n, range = lsquic_rechist_next(rechist))
|
|
{
|
|
n = snprintf(buf + off, bufsz - off, "[%"PRIu64"-%"PRIu64"]",
|
|
range->high, range->low);
|
|
if (n < 0 || (size_t) n >= bufsz - off)
|
|
break;
|
|
}
|
|
}
|
|
|
|
|
|
static void
|
|
test_range_copy (struct lsquic_rechist *orig, int ietf)
|
|
{
|
|
char orig_str[0x1000], new_str[0x1000];
|
|
struct lsquic_rechist new;
|
|
size_t len;
|
|
|
|
rechist2str(orig, orig_str, sizeof(orig_str));
|
|
|
|
lsquic_rechist_init(&new, ietf, 0);
|
|
lsquic_rechist_copy_ranges(&new, orig,
|
|
(const struct lsquic_packno_range * (*) (void *)) lsquic_rechist_first,
|
|
(const struct lsquic_packno_range * (*) (void *)) lsquic_rechist_next);
|
|
rechist2str(&new, new_str, sizeof(new_str));
|
|
assert(0 == strcmp(orig_str, new_str));
|
|
lsquic_rechist_cleanup(&new);
|
|
|
|
/* This tests that lower-numbered ranges do not overwrite higher-numbered
|
|
* ranges.
|
|
*/
|
|
lsquic_rechist_init(&new, ietf, 10);
|
|
lsquic_rechist_copy_ranges(&new, orig,
|
|
(const struct lsquic_packno_range * (*) (void *)) lsquic_rechist_first,
|
|
(const struct lsquic_packno_range * (*) (void *)) lsquic_rechist_next);
|
|
rechist2str(&new, new_str, sizeof(new_str));
|
|
len = strlen(new_str);
|
|
assert(0 == strncmp(orig_str, new_str, len));
|
|
lsquic_rechist_cleanup(&new);
|
|
}
|
|
|
|
|
|
static void
|
|
test5 (void)
|
|
{
|
|
lsquic_rechist_t rechist;
|
|
char buf[100];
|
|
|
|
lsquic_rechist_init(&rechist, 0, 0);
|
|
|
|
lsquic_rechist_received(&rechist, 1, 0);
|
|
/* Packet 2 omitted because it could not be decrypted */
|
|
lsquic_rechist_received(&rechist, 3, 0);
|
|
lsquic_rechist_received(&rechist, 12, 0);
|
|
|
|
rechist2str(&rechist, buf, sizeof(buf));
|
|
assert(0 == strcmp(buf, "[12-12][3-3][1-1]"));
|
|
|
|
lsquic_rechist_received(&rechist, 4, 0);
|
|
lsquic_rechist_received(&rechist, 10, 0);
|
|
|
|
rechist2str(&rechist, buf, sizeof(buf));
|
|
assert(0 == strcmp(buf, "[12-12][10-10][4-3][1-1]"));
|
|
|
|
lsquic_rechist_received(&rechist, 6, 0);
|
|
|
|
rechist2str(&rechist, buf, sizeof(buf));
|
|
assert(0 == strcmp(buf, "[12-12][10-10][6-6][4-3][1-1]"));
|
|
|
|
lsquic_rechist_received(&rechist, 7, 0);
|
|
lsquic_rechist_received(&rechist, 8, 0);
|
|
|
|
rechist2str(&rechist, buf, sizeof(buf));
|
|
assert(0 == strcmp(buf, "[12-12][10-10][8-6][4-3][1-1]"));
|
|
|
|
lsquic_rechist_received(&rechist, 9, 0);
|
|
test_range_copy(&rechist, 0);
|
|
|
|
rechist2str(&rechist, buf, sizeof(buf));
|
|
assert(0 == strcmp(buf, "[12-12][10-6][4-3][1-1]"));
|
|
|
|
lsquic_rechist_received(&rechist, 5, 0);
|
|
lsquic_rechist_received(&rechist, 11, 0);
|
|
|
|
rechist2str(&rechist, buf, sizeof(buf));
|
|
assert(0 == strcmp(buf, "[12-3][1-1]"));
|
|
|
|
lsquic_rechist_cleanup(&rechist);
|
|
}
|
|
|
|
|
|
/* Regression test for bug where rechist ends up empty (rh_used == 0)
|
|
* with invalid head entry with a self-referential next, and
|
|
* lsquic_rechist_received would follow it because it didn't check rh_used.
|
|
*/
|
|
static void
|
|
test6 (void)
|
|
{
|
|
lsquic_rechist_t rechist;
|
|
char buf[256];
|
|
long int time = 12087061905875;
|
|
unsigned i;
|
|
|
|
lsquic_rechist_init(&rechist, 0, 0);
|
|
|
|
for (i = 0; i <= 3; i++)
|
|
lsquic_rechist_received(&rechist, i, (time += (i * 10)));
|
|
lsquic_rechist_stop_wait(&rechist, 2);
|
|
|
|
lsquic_rechist_received(&rechist, 4, (time += 10));
|
|
|
|
lsquic_rechist_stop_wait(&rechist, 3);
|
|
|
|
lsquic_rechist_received(&rechist, 5, (time += 10));
|
|
|
|
lsquic_rechist_stop_wait(&rechist, 3);
|
|
|
|
lsquic_rechist_received(&rechist, 6, (time += 10));
|
|
|
|
lsquic_rechist_stop_wait(&rechist, 9);
|
|
|
|
lsquic_rechist_received(&rechist, 7, (time += 10));
|
|
lsquic_rechist_received(&rechist, 8, (time += 10));
|
|
lsquic_rechist_received(&rechist, 9, (time += 10));
|
|
|
|
rechist2str(&rechist, buf, sizeof(buf));
|
|
|
|
lsquic_rechist_cleanup(&rechist);
|
|
}
|
|
|
|
|
|
static void
|
|
test_rand_sequence (unsigned seed, unsigned max)
|
|
{
|
|
struct lsquic_rechist rechist;
|
|
const struct lsquic_packno_range *range;
|
|
lsquic_packno_t prev_low;
|
|
enum received_st st;
|
|
unsigned i, count;
|
|
|
|
lsquic_rechist_init(&rechist, 1, max);
|
|
srand(seed);
|
|
|
|
for (i = 0; i < 10000; ++i)
|
|
{
|
|
st = lsquic_rechist_received(&rechist, (unsigned) rand(), 0);
|
|
assert(st == REC_ST_OK || st == REC_ST_DUP);
|
|
}
|
|
|
|
test_range_copy(&rechist, 1);
|
|
|
|
range = lsquic_rechist_first(&rechist);
|
|
assert(range);
|
|
assert(range->high >= range->low);
|
|
prev_low = range->low;
|
|
count = 1;
|
|
|
|
while (range = lsquic_rechist_next(&rechist), range != NULL)
|
|
{
|
|
++count;
|
|
assert(range->high >= range->low);
|
|
assert(range->high < prev_low);
|
|
prev_low = range->low;
|
|
}
|
|
if (max)
|
|
assert(count <= max);
|
|
|
|
lsquic_rechist_cleanup(&rechist);
|
|
}
|
|
|
|
|
|
struct shuffle_elem {
|
|
unsigned packno;
|
|
int rand;
|
|
};
|
|
|
|
|
|
static int
|
|
comp_els (const void *a_p, const void *b_p)
|
|
{
|
|
const struct shuffle_elem *a = a_p, *b = b_p;
|
|
if (a->rand < b->rand)
|
|
return -1;
|
|
if (a->rand > b->rand)
|
|
return 1;
|
|
return (a->packno > b->packno) - (b->packno > a->packno);
|
|
}
|
|
|
|
|
|
static void
|
|
test_shuffle_1000 (unsigned seed)
|
|
{
|
|
struct lsquic_rechist rechist;
|
|
const struct lsquic_packno_range *range;
|
|
enum received_st st;
|
|
unsigned i;
|
|
struct shuffle_elem *els;
|
|
|
|
els = malloc(sizeof(els[0]) * 10000);
|
|
lsquic_rechist_init(&rechist, 1, 0);
|
|
srand(seed);
|
|
|
|
for (i = 0; i < 10000; ++i)
|
|
{
|
|
els[i].packno = i;
|
|
els[i].rand = rand();
|
|
}
|
|
|
|
qsort(els, 10000, sizeof(els[0]), comp_els);
|
|
|
|
for (i = 0; i < 10000; ++i)
|
|
{
|
|
st = lsquic_rechist_received(&rechist, els[i].packno, 0);
|
|
assert(st == REC_ST_OK || st == REC_ST_DUP);
|
|
}
|
|
test_range_copy(&rechist, 1);
|
|
|
|
range = lsquic_rechist_first(&rechist);
|
|
assert(range);
|
|
assert(range->high == 9999);
|
|
assert(range->low == 0);
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(!range);
|
|
|
|
lsquic_rechist_cleanup(&rechist);
|
|
free(els);
|
|
}
|
|
|
|
|
|
int
|
|
main (void)
|
|
{
|
|
enum received_st st;
|
|
lsquic_rechist_t rechist;
|
|
unsigned i;
|
|
const struct lsquic_packno_range *range;
|
|
|
|
lsquic_rechist_init(&rechist, 0, 0);
|
|
|
|
lsquic_time_t now = 1234;
|
|
st = lsquic_rechist_received(&rechist, 0, now);
|
|
assert(("inserting packet number zero results in error", st == REC_ST_ERR));
|
|
|
|
st = lsquic_rechist_received(&rechist, 1, now);
|
|
assert(("inserting packet number one is successful", st == REC_ST_OK));
|
|
|
|
st = lsquic_rechist_received(&rechist, 1, now);
|
|
assert(("inserting packet number one again results in duplicate error",
|
|
st == REC_ST_DUP));
|
|
|
|
range = lsquic_rechist_first(&rechist);
|
|
assert(("first range returned correctly", range));
|
|
assert(("first range low value checks out", range->low == 1));
|
|
assert(("first range high value checks out", range->high == 1));
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(("second range does not exist", !range));
|
|
|
|
for (i = 3; i <= 5; ++i)
|
|
{
|
|
st = lsquic_rechist_received(&rechist, i, now);
|
|
assert(("inserting packet", st == REC_ST_OK));
|
|
}
|
|
|
|
range = lsquic_rechist_first(&rechist);
|
|
assert(("first range returned correctly", range));
|
|
assert(("first range low value checks out", range->low == 3));
|
|
assert(("first range high value checks out", range->high == 5));
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(("second range returned correctly", range));
|
|
assert(("second range low value checks out", range->low == 1));
|
|
assert(("second range high value checks out", range->high == 1));
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(("third range does not exist", !range));
|
|
|
|
lsquic_rechist_stop_wait(&rechist, 3);
|
|
|
|
st = lsquic_rechist_received(&rechist, 1, now);
|
|
assert(("inserting packet number one is unsuccessful after cutoff 3",
|
|
st == REC_ST_DUP));
|
|
|
|
range = lsquic_rechist_first(&rechist);
|
|
assert(("first range returned correctly", range));
|
|
assert(("first range low value checks out", range->low == 3));
|
|
assert(("first range high value checks out", range->high == 5));
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(("second range does not exist", !range));
|
|
|
|
for (i = 9; i >= 7; --i)
|
|
{
|
|
st = lsquic_rechist_received(&rechist, i, now);
|
|
assert(("inserting packet", st == REC_ST_OK));
|
|
}
|
|
|
|
range = lsquic_rechist_first(&rechist);
|
|
assert(("first range returned correctly", range));
|
|
assert(("first range low value checks out", range->low == 7));
|
|
assert(("first range high value checks out", range->high == 9));
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(("second range returned correctly", range));
|
|
assert(("second range low value checks out", range->low == 3));
|
|
assert(("second range high value checks out", range->high == 5));
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(("third range does not exist", !range));
|
|
|
|
lsquic_rechist_stop_wait(&rechist, 5);
|
|
|
|
range = lsquic_rechist_first(&rechist);
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(("second range returned correctly", range));
|
|
assert(("second range low value checks out", range->low == 5));
|
|
assert(("second range high value checks out", range->high == 5));
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(("third range does not exist", !range));
|
|
|
|
lsquic_rechist_stop_wait(&rechist, 8);
|
|
|
|
range = lsquic_rechist_first(&rechist);
|
|
assert(("first range returned correctly", range));
|
|
assert(("first range low value checks out", range->low == 8));
|
|
assert(("first range high value checks out", range->high == 9));
|
|
range = lsquic_rechist_next(&rechist);
|
|
assert(("second range does not exist", !range));
|
|
|
|
lsquic_rechist_cleanup(&rechist);
|
|
|
|
test4();
|
|
|
|
test5();
|
|
|
|
test6();
|
|
|
|
for (i = 0; i < 10; ++i)
|
|
test_rand_sequence(i, 0);
|
|
|
|
for (i = 0; i < 10; ++i)
|
|
test_rand_sequence(i, 111 + i * 3 /* Just something arbitrary */);
|
|
|
|
for (i = 0; i < 10; ++i)
|
|
test_shuffle_1000(i);
|
|
|
|
return 0;
|
|
}
|