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