test_purga.c revision a74702c6 
1/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc.  See LICENSE. */
2#include <assert.h>
3#include <stdlib.h>
4#include <string.h>
5#ifndef WIN32
6#include <unistd.h>
7#else
8#include "getopt.h"
9#endif
10
11#include <openssl/rand.h>
12
13#include "lsquic.h"
14#include "lsquic_int_types.h"
15#include "lsquic_logger.h"
16#include "lsquic_purga.h"
17
18#define MIN_CID_LEN 4
19
20static int s_eight;
21
22static void
23bloom_test (unsigned count, unsigned miss_searches, unsigned hit_searches)
24{
25#ifndef NDEBUG
26    struct purga_bloom_stats *stats;
27#endif
28    struct lsquic_purga *purga;
29    struct purga_el *puel;
30    lsquic_cid_t *cids, cid;
31    unsigned i, j;
32
33    cids = malloc(count * sizeof(cids[0]));
34    assert(cids);
35
36    for (i = 0; i < count; ++i)
37    {
38        cids[i].len = s_eight ? 8 : MIN_CID_LEN + rand() % (MAX_CID_LEN - MIN_CID_LEN);
39        RAND_bytes(cids[i].idbuf, cids[i].len);
40    }
41
42    purga = lsquic_purga_new(~0, NULL, NULL);
43
44    /* Add CIDs */
45    for (i = 0; i < count; ++i)
46        lsquic_purga_add(purga, &cids[i], NULL, 0, 0);
47
48    /* Check that they are all there */
49    for (i = 0; i < count; ++i)
50    {
51        puel = lsquic_purga_contains(purga, &cids[i]);
52        assert(puel);
53    }
54
55    /* Run hit searches */
56    for (i = 0; i < hit_searches; ++i)
57    {
58        j = rand() % count;
59        puel = lsquic_purga_contains(purga, &cids[j]);
60        assert(puel);
61    }
62
63    /* Generate random CIDs and check that they are not found: */
64    for (i = 0; i < miss_searches; ++i)
65    {
66        cid.len = s_eight ? 8 : MIN_CID_LEN + rand() % (MAX_CID_LEN - MIN_CID_LEN);
67        RAND_bytes(cid.idbuf, cid.len);
68        puel = lsquic_purga_contains(purga, &cid);
69        if (puel)
70        {
71            for (j = 0; j < count; ++j)
72                if (LSQUIC_CIDS_EQ(&cids[j], &cid))
73                    break;
74            assert(j < count);
75        }
76    }
77
78#ifndef NDEBUG
79    stats = lsquic_purga_get_bloom_stats(purga);
80    LSQ_NOTICE("searches: %lu, false hits: %lu, false hit ratio: %lf",
81        stats->searches, stats->false_hits,
82        (double) stats->false_hits / (double) stats->searches);
83#endif
84
85    lsquic_purga_destroy(purga);
86    free(cids);
87}
88
89
90int
91main (int argc, char **argv)
92{
93    int opt;
94    unsigned i, per_page, bloom_ins = 0, bloom_miss_sea = 0, bloom_hit_sea = 0;
95    lsquic_cid_t cid;
96    struct lsquic_purga *purga;
97    struct purga_el *puel;
98
99    while (-1 != (opt = getopt(argc, argv, "b:h:l:s:v8")))
100    {
101        switch (opt)
102        {
103        case '8':
104            s_eight = 1;
105            break;
106        case 'b':
107            bloom_ins = atoi(optarg);
108            break;
109        case 's':
110            bloom_miss_sea = atoi(optarg);
111            break;
112        case 'h':
113            bloom_hit_sea = atoi(optarg);
114            break;
115        case 'l':
116            lsquic_log_to_fstream(stderr, 0);
117            lsquic_logger_lopt(optarg);
118            break;
119        case 'v':
120            lsquic_log_to_fstream(stderr, 0);
121            lsquic_logger_lopt("purga=debug");
122            break;
123        default:
124            exit(EXIT_FAILURE);
125        }
126    }
127
128    if (bloom_ins)
129    {
130        LSQ_NOTICE("bloom test: will insert %u and search for %u missing "
131            "and %u extant CIDs", bloom_ins, bloom_miss_sea, bloom_hit_sea);
132        bloom_test(bloom_ins, bloom_miss_sea, bloom_hit_sea);
133        exit(EXIT_SUCCESS);
134    }
135
136    per_page = lsquic_purga_cids_per_page();
137    purga = lsquic_purga_new(10, NULL, NULL);
138    assert(purga);
139
140    cid.len = 3;
141    for (i = 0; i < per_page; ++i)
142    {
143        cid.idbuf[0] = i >> 16;
144        cid.idbuf[1] = i >> 8;
145        cid.idbuf[2] = i;
146        puel = lsquic_purga_add(purga, &cid, NULL, PUTY_CONN_DELETED, 20);
147        assert(puel);
148        puel->puel_time = ~i;
149    }
150
151    for (i = 0; i < per_page; ++i)
152    {
153        cid.idbuf[0] = i >> 16;
154        cid.idbuf[1] = i >> 8;
155        cid.idbuf[2] = i;
156        puel = lsquic_purga_contains(purga, &cid);
157        assert(puel && PUTY_CONN_DELETED == puel->puel_type);
158        assert(~i == puel->puel_time);
159    }
160
161    ++cid.idbuf[1];
162    lsquic_purga_add(purga, &cid, NULL, PUTY_CONN_DELETED, 31);
163
164    for (i = 0; i < per_page; ++i)
165    {
166        cid.idbuf[0] = i >> 16;
167        cid.idbuf[1] = i >> 8;
168        cid.idbuf[2] = i;
169        puel = lsquic_purga_contains(purga, &cid);
170        assert(!puel);
171    }
172
173    ++cid.idbuf[1];
174    puel = lsquic_purga_contains(purga, &cid);
175    assert(puel && PUTY_CONN_DELETED == puel->puel_type);
176
177    lsquic_purga_destroy(purga);
178
179    bloom_test(20000, 200000, 2000);
180
181    exit(EXIT_SUCCESS);
182}
183