test_purga.c revision a74702c6
1a74702c6SGeorge Wang/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc.  See LICENSE. */
25392f7a3SLiteSpeed Tech#include <assert.h>
35392f7a3SLiteSpeed Tech#include <stdlib.h>
45392f7a3SLiteSpeed Tech#include <string.h>
5fb3e20e0SDmitri Tikhonov#ifndef WIN32
65392f7a3SLiteSpeed Tech#include <unistd.h>
7fb3e20e0SDmitri Tikhonov#else
8fb3e20e0SDmitri Tikhonov#include "getopt.h"
9fb3e20e0SDmitri Tikhonov#endif
105392f7a3SLiteSpeed Tech
115392f7a3SLiteSpeed Tech#include <openssl/rand.h>
125392f7a3SLiteSpeed Tech
135392f7a3SLiteSpeed Tech#include "lsquic.h"
145392f7a3SLiteSpeed Tech#include "lsquic_int_types.h"
155392f7a3SLiteSpeed Tech#include "lsquic_logger.h"
165392f7a3SLiteSpeed Tech#include "lsquic_purga.h"
175392f7a3SLiteSpeed Tech
185392f7a3SLiteSpeed Tech#define MIN_CID_LEN 4
195392f7a3SLiteSpeed Tech
205392f7a3SLiteSpeed Techstatic int s_eight;
215392f7a3SLiteSpeed Tech
225392f7a3SLiteSpeed Techstatic void
235392f7a3SLiteSpeed Techbloom_test (unsigned count, unsigned miss_searches, unsigned hit_searches)
245392f7a3SLiteSpeed Tech{
25f07b3eaeSTyler Young#ifndef NDEBUG
265392f7a3SLiteSpeed Tech    struct purga_bloom_stats *stats;
27f07b3eaeSTyler Young#endif
28f07b3eaeSTyler Young    struct lsquic_purga *purga;
295392f7a3SLiteSpeed Tech    struct purga_el *puel;
305392f7a3SLiteSpeed Tech    lsquic_cid_t *cids, cid;
315392f7a3SLiteSpeed Tech    unsigned i, j;
325392f7a3SLiteSpeed Tech
335392f7a3SLiteSpeed Tech    cids = malloc(count * sizeof(cids[0]));
345392f7a3SLiteSpeed Tech    assert(cids);
355392f7a3SLiteSpeed Tech
365392f7a3SLiteSpeed Tech    for (i = 0; i < count; ++i)
375392f7a3SLiteSpeed Tech    {
385392f7a3SLiteSpeed Tech        cids[i].len = s_eight ? 8 : MIN_CID_LEN + rand() % (MAX_CID_LEN - MIN_CID_LEN);
395392f7a3SLiteSpeed Tech        RAND_bytes(cids[i].idbuf, cids[i].len);
405392f7a3SLiteSpeed Tech    }
415392f7a3SLiteSpeed Tech
425392f7a3SLiteSpeed Tech    purga = lsquic_purga_new(~0, NULL, NULL);
435392f7a3SLiteSpeed Tech
445392f7a3SLiteSpeed Tech    /* Add CIDs */
455392f7a3SLiteSpeed Tech    for (i = 0; i < count; ++i)
465392f7a3SLiteSpeed Tech        lsquic_purga_add(purga, &cids[i], NULL, 0, 0);
475392f7a3SLiteSpeed Tech
485392f7a3SLiteSpeed Tech    /* Check that they are all there */
495392f7a3SLiteSpeed Tech    for (i = 0; i < count; ++i)
505392f7a3SLiteSpeed Tech    {
515392f7a3SLiteSpeed Tech        puel = lsquic_purga_contains(purga, &cids[i]);
525392f7a3SLiteSpeed Tech        assert(puel);
535392f7a3SLiteSpeed Tech    }
545392f7a3SLiteSpeed Tech
555392f7a3SLiteSpeed Tech    /* Run hit searches */
565392f7a3SLiteSpeed Tech    for (i = 0; i < hit_searches; ++i)
575392f7a3SLiteSpeed Tech    {
585392f7a3SLiteSpeed Tech        j = rand() % count;
595392f7a3SLiteSpeed Tech        puel = lsquic_purga_contains(purga, &cids[j]);
605392f7a3SLiteSpeed Tech        assert(puel);
615392f7a3SLiteSpeed Tech    }
625392f7a3SLiteSpeed Tech
635392f7a3SLiteSpeed Tech    /* Generate random CIDs and check that they are not found: */
645392f7a3SLiteSpeed Tech    for (i = 0; i < miss_searches; ++i)
655392f7a3SLiteSpeed Tech    {
665392f7a3SLiteSpeed Tech        cid.len = s_eight ? 8 : MIN_CID_LEN + rand() % (MAX_CID_LEN - MIN_CID_LEN);
675392f7a3SLiteSpeed Tech        RAND_bytes(cid.idbuf, cid.len);
685392f7a3SLiteSpeed Tech        puel = lsquic_purga_contains(purga, &cid);
695392f7a3SLiteSpeed Tech        if (puel)
705392f7a3SLiteSpeed Tech        {
715392f7a3SLiteSpeed Tech            for (j = 0; j < count; ++j)
725392f7a3SLiteSpeed Tech                if (LSQUIC_CIDS_EQ(&cids[j], &cid))
735392f7a3SLiteSpeed Tech                    break;
745392f7a3SLiteSpeed Tech            assert(j < count);
755392f7a3SLiteSpeed Tech        }
765392f7a3SLiteSpeed Tech    }
775392f7a3SLiteSpeed Tech
78f07b3eaeSTyler Young#ifndef NDEBUG
795392f7a3SLiteSpeed Tech    stats = lsquic_purga_get_bloom_stats(purga);
805392f7a3SLiteSpeed Tech    LSQ_NOTICE("searches: %lu, false hits: %lu, false hit ratio: %lf",
815392f7a3SLiteSpeed Tech        stats->searches, stats->false_hits,
825392f7a3SLiteSpeed Tech        (double) stats->false_hits / (double) stats->searches);
83f07b3eaeSTyler Young#endif
845392f7a3SLiteSpeed Tech
855392f7a3SLiteSpeed Tech    lsquic_purga_destroy(purga);
865392f7a3SLiteSpeed Tech    free(cids);
875392f7a3SLiteSpeed Tech}
885392f7a3SLiteSpeed Tech
895392f7a3SLiteSpeed Tech
905392f7a3SLiteSpeed Techint
915392f7a3SLiteSpeed Techmain (int argc, char **argv)
925392f7a3SLiteSpeed Tech{
935392f7a3SLiteSpeed Tech    int opt;
945392f7a3SLiteSpeed Tech    unsigned i, per_page, bloom_ins = 0, bloom_miss_sea = 0, bloom_hit_sea = 0;
955392f7a3SLiteSpeed Tech    lsquic_cid_t cid;
965392f7a3SLiteSpeed Tech    struct lsquic_purga *purga;
975392f7a3SLiteSpeed Tech    struct purga_el *puel;
985392f7a3SLiteSpeed Tech
995392f7a3SLiteSpeed Tech    while (-1 != (opt = getopt(argc, argv, "b:h:l:s:v8")))
1005392f7a3SLiteSpeed Tech    {
1015392f7a3SLiteSpeed Tech        switch (opt)
1025392f7a3SLiteSpeed Tech        {
1035392f7a3SLiteSpeed Tech        case '8':
1045392f7a3SLiteSpeed Tech            s_eight = 1;
1055392f7a3SLiteSpeed Tech            break;
1065392f7a3SLiteSpeed Tech        case 'b':
1075392f7a3SLiteSpeed Tech            bloom_ins = atoi(optarg);
1085392f7a3SLiteSpeed Tech            break;
1095392f7a3SLiteSpeed Tech        case 's':
1105392f7a3SLiteSpeed Tech            bloom_miss_sea = atoi(optarg);
1115392f7a3SLiteSpeed Tech            break;
1125392f7a3SLiteSpeed Tech        case 'h':
1135392f7a3SLiteSpeed Tech            bloom_hit_sea = atoi(optarg);
1145392f7a3SLiteSpeed Tech            break;
1155392f7a3SLiteSpeed Tech        case 'l':
1165392f7a3SLiteSpeed Tech            lsquic_log_to_fstream(stderr, 0);
1175392f7a3SLiteSpeed Tech            lsquic_logger_lopt(optarg);
1185392f7a3SLiteSpeed Tech            break;
1195392f7a3SLiteSpeed Tech        case 'v':
1205392f7a3SLiteSpeed Tech            lsquic_log_to_fstream(stderr, 0);
1215392f7a3SLiteSpeed Tech            lsquic_logger_lopt("purga=debug");
1225392f7a3SLiteSpeed Tech            break;
1235392f7a3SLiteSpeed Tech        default:
1245392f7a3SLiteSpeed Tech            exit(EXIT_FAILURE);
1255392f7a3SLiteSpeed Tech        }
1265392f7a3SLiteSpeed Tech    }
1275392f7a3SLiteSpeed Tech
1285392f7a3SLiteSpeed Tech    if (bloom_ins)
1295392f7a3SLiteSpeed Tech    {
1305392f7a3SLiteSpeed Tech        LSQ_NOTICE("bloom test: will insert %u and search for %u missing "
1315392f7a3SLiteSpeed Tech            "and %u extant CIDs", bloom_ins, bloom_miss_sea, bloom_hit_sea);
1325392f7a3SLiteSpeed Tech        bloom_test(bloom_ins, bloom_miss_sea, bloom_hit_sea);
1335392f7a3SLiteSpeed Tech        exit(EXIT_SUCCESS);
1345392f7a3SLiteSpeed Tech    }
1355392f7a3SLiteSpeed Tech
1365392f7a3SLiteSpeed Tech    per_page = lsquic_purga_cids_per_page();
1375392f7a3SLiteSpeed Tech    purga = lsquic_purga_new(10, NULL, NULL);
1385392f7a3SLiteSpeed Tech    assert(purga);
1395392f7a3SLiteSpeed Tech
1405392f7a3SLiteSpeed Tech    cid.len = 3;
1415392f7a3SLiteSpeed Tech    for (i = 0; i < per_page; ++i)
1425392f7a3SLiteSpeed Tech    {
1435392f7a3SLiteSpeed Tech        cid.idbuf[0] = i >> 16;
1445392f7a3SLiteSpeed Tech        cid.idbuf[1] = i >> 8;
1455392f7a3SLiteSpeed Tech        cid.idbuf[2] = i;
1465392f7a3SLiteSpeed Tech        puel = lsquic_purga_add(purga, &cid, NULL, PUTY_CONN_DELETED, 20);
1475392f7a3SLiteSpeed Tech        assert(puel);
1485392f7a3SLiteSpeed Tech        puel->puel_time = ~i;
1495392f7a3SLiteSpeed Tech    }
1505392f7a3SLiteSpeed Tech
1515392f7a3SLiteSpeed Tech    for (i = 0; i < per_page; ++i)
1525392f7a3SLiteSpeed Tech    {
1535392f7a3SLiteSpeed Tech        cid.idbuf[0] = i >> 16;
1545392f7a3SLiteSpeed Tech        cid.idbuf[1] = i >> 8;
1555392f7a3SLiteSpeed Tech        cid.idbuf[2] = i;
1565392f7a3SLiteSpeed Tech        puel = lsquic_purga_contains(purga, &cid);
1575392f7a3SLiteSpeed Tech        assert(puel && PUTY_CONN_DELETED == puel->puel_type);
158a0e1aeeeSDmitri Tikhonov        assert(~i == puel->puel_time);
1595392f7a3SLiteSpeed Tech    }
1605392f7a3SLiteSpeed Tech
1615392f7a3SLiteSpeed Tech    ++cid.idbuf[1];
1625392f7a3SLiteSpeed Tech    lsquic_purga_add(purga, &cid, NULL, PUTY_CONN_DELETED, 31);
1635392f7a3SLiteSpeed Tech
1645392f7a3SLiteSpeed Tech    for (i = 0; i < per_page; ++i)
1655392f7a3SLiteSpeed Tech    {
1665392f7a3SLiteSpeed Tech        cid.idbuf[0] = i >> 16;
1675392f7a3SLiteSpeed Tech        cid.idbuf[1] = i >> 8;
1685392f7a3SLiteSpeed Tech        cid.idbuf[2] = i;
1695392f7a3SLiteSpeed Tech        puel = lsquic_purga_contains(purga, &cid);
1705392f7a3SLiteSpeed Tech        assert(!puel);
1715392f7a3SLiteSpeed Tech    }
1725392f7a3SLiteSpeed Tech
1735392f7a3SLiteSpeed Tech    ++cid.idbuf[1];
1745392f7a3SLiteSpeed Tech    puel = lsquic_purga_contains(purga, &cid);
1755392f7a3SLiteSpeed Tech    assert(puel && PUTY_CONN_DELETED == puel->puel_type);
1765392f7a3SLiteSpeed Tech
1775392f7a3SLiteSpeed Tech    lsquic_purga_destroy(purga);
1785392f7a3SLiteSpeed Tech
1795392f7a3SLiteSpeed Tech    bloom_test(20000, 200000, 2000);
1805392f7a3SLiteSpeed Tech
1815392f7a3SLiteSpeed Tech    exit(EXIT_SUCCESS);
1825392f7a3SLiteSpeed Tech}
183