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