lsquic_purga.c revision 5392f7a3 
1/* Copyright (c) 2017 - 2019 LiteSpeed Technologies Inc.  See LICENSE. */
2#include <errno.h>
3#include <inttypes.h>
4#include <stddef.h>
5#include <stdint.h>
6#include <stdlib.h>
7#include <string.h>
8#include <sys/queue.h>
9
10#include "lsquic.h"
11#include "lsquic_types.h"
12#include "lsquic_int_types.h"
13#include "lsquic_xxhash.h"
14#include "lsquic_purga.h"
15
16#define LSQUIC_LOGGER_MODULE LSQLM_PURGA
17#include "lsquic_logger.h"
18
19
20/* To avoid scannig the whole list of CIDs, we use a Bloom filter.
21 *
22 * The Bloom filter is constructed using a 8192-bit bit field and 6 hash
23 * functions.  With 273 elements per page, this gives us 0.004% possibility
24 * of a false positive.  In other words, when we do have to search a page
25 * for a particular CID, the chance of finding the CID is 99.99%.
26 *
27 * Quick calc:
28 *   perl -E '$k=6;$m=1<<13;$n=273;printf("%f\n", (1-exp(1)**-($k*$n/$m))**$k)'
29 *
30 * To extract 6 13-bit values from a 64-bit integer, they are overlapped:
31 *  0         10        20        30        40        50        60
32 * +----------------------------------------------------------------+
33 * |                                                                |
34 * +----------------------------------------------------------------+
35 *  1111111111111
36 *            2222222222222
37 *                      3333333333333
38 *                                4444444444444
39 *                                          5555555555555
40 *                                                    6666666666666
41 *
42 * This is not 100% kosher, but having 6 functions gives a better guarantee
43 * and it happens to work in practice.
44 */
45
46#define BLOOM_N_FUNCS 6
47#define BLOOM_SHIFT 10
48#define BLOOM_N_BITS (1 << 13)
49typedef uint64_t bloom_mask_el_t;
50#define BLOOM_SET_SHIFT 6   /* log2(sizeof(bloom_mask_el_t)) */
51#define BLOOM_BITS_PER_EL (1 << BLOOM_SET_SHIFT)
52#define BLOOM_N_MASK_ELS (BLOOM_N_BITS / BLOOM_BITS_PER_EL)
53#define BLOOM_ONE 1ull
54
55#define PURGA_ELS_PER_PAGE 273
56
57struct purga_page
58{
59    TAILQ_ENTRY(purga_page)     pupa_next;
60    lsquic_time_t               pupa_last;
61    unsigned                    pupa_count;
62    bloom_mask_el_t             pupa_mask[BLOOM_N_MASK_ELS];
63    lsquic_cid_t                pupa_cids[PURGA_ELS_PER_PAGE];
64    void *                      pupa_peer_ctx[PURGA_ELS_PER_PAGE];
65    struct purga_el             pupa_els[PURGA_ELS_PER_PAGE];
66};
67
68#define PAGE_IS_FULL(page) ((page)->pupa_count >= PURGA_ELS_PER_PAGE)
69
70TAILQ_HEAD(purga_pages, purga_page);
71
72struct lsquic_purga
73{
74    lsquic_time_t              pur_min_life;
75    lsquic_cids_update_f       pur_remove_cids;
76    void                      *pur_remove_ctx;
77    struct purga_pages         pur_pages;
78#ifndef NDEBUG
79    struct purga_bloom_stats   pur_stats;
80#endif
81};
82
83
84struct lsquic_purga *
85lsquic_purga_new (lsquic_time_t min_life, lsquic_cids_update_f remove_cids,
86                                                                void *remove_ctx)
87{
88    struct lsquic_purga *purga;
89
90    purga = calloc(1, sizeof(*purga));
91    if (!purga)
92    {
93        LSQ_WARN("cannot create purgatory: malloc failed: %s", strerror(errno));
94        return NULL;
95    }
96
97    purga->pur_min_life = min_life;
98    purga->pur_remove_cids = remove_cids;
99    purga->pur_remove_ctx = remove_ctx;
100    TAILQ_INIT(&purga->pur_pages);
101    LSQ_INFO("create purgatory, min life %"PRIu64" usec", min_life);
102
103    return purga;
104}
105
106
107static struct purga_page *
108purga_get_page (struct lsquic_purga *purga)
109{
110    struct purga_page *page;
111
112    page = TAILQ_LAST(&purga->pur_pages, purga_pages);
113    if (page && !PAGE_IS_FULL(page))
114        return page;
115
116    page = malloc(sizeof(*page));
117    if (!page)
118    {
119        LSQ_INFO("failed to allocate page: %s", strerror(errno));
120        return NULL;
121    }
122
123    page->pupa_count = 0;
124    page->pupa_last  = 0;
125    memset(page->pupa_mask, 0, sizeof(page->pupa_mask));
126    TAILQ_INSERT_TAIL(&purga->pur_pages, page, pupa_next);
127    LSQ_DEBUG("allocated new page");
128    return page;
129}
130
131
132static void
133purga_remove_cids (struct lsquic_purga *purga, struct purga_page *page)
134{
135    LSQ_DEBUG("calling remove_cids with %u CID%.*s", page->pupa_count,
136                                                page->pupa_count != 1, "s");
137    /* XXX It is interesting that pur_remove_ctx is called with peer_ctx
138     * as an argument, which should could vary (at least theoretically or
139     * in the future) by path.
140     */
141    purga->pur_remove_cids(purga->pur_remove_ctx, page->pupa_peer_ctx,
142                                        page->pupa_cids, page->pupa_count);
143}
144
145
146struct purga_el *
147lsquic_purga_add (struct lsquic_purga *purga, const lsquic_cid_t *cid,
148                    void *peer_ctx, enum purga_type putype, lsquic_time_t now)
149{
150    struct purga_page *last_page, *page;
151    uint64_t hash;
152    unsigned i, idx, set, bit;
153
154    last_page = purga_get_page(purga);
155    if (!last_page)
156        return NULL;     /* We do best effort, nothing to do if malloc fails */
157
158    idx = last_page->pupa_count++;
159    last_page->pupa_cids    [idx] = *cid;
160    last_page->pupa_peer_ctx[idx] = peer_ctx;
161    last_page->pupa_els     [idx] = (struct purga_el) {
162        .puel_type      = putype,
163    };
164
165    hash = XXH64(cid->idbuf, cid->len, 0);
166    for (i = 0; i < BLOOM_N_FUNCS; ++i)
167    {
168        bit = (unsigned) hash & (BLOOM_BITS_PER_EL - 1);
169        set = ((unsigned) hash >> BLOOM_SET_SHIFT) & (BLOOM_N_MASK_ELS - 1);
170        last_page->pupa_mask[set] |= BLOOM_ONE << bit;
171        hash >>= BLOOM_SHIFT;
172    }
173
174    LSQ_DEBUGC("added %"CID_FMT" to the set", CID_BITS(cid));
175    if (PAGE_IS_FULL(last_page))
176    {
177        LSQ_DEBUG("last page is full, set timestamp to %"PRIu64, now);
178        last_page->pupa_last = now;
179    }
180
181    while ((page = TAILQ_FIRST(&purga->pur_pages))
182                && PAGE_IS_FULL(page)
183                && page != last_page    /* This is theoretical, but still... */
184                && page->pupa_last + purga->pur_min_life < now)
185    {
186        LSQ_DEBUG("page at timestamp %"PRIu64" expired; now is %"PRIu64,
187            page->pupa_last, now);
188        TAILQ_REMOVE(&purga->pur_pages, page, pupa_next);
189        if (purga->pur_remove_cids && page->pupa_count)
190            purga_remove_cids(purga, page);
191        free(page);
192    }
193
194    return &last_page->pupa_els[idx];
195}
196
197
198struct purga_el *
199lsquic_purga_contains (struct lsquic_purga *purga, const lsquic_cid_t *cid)
200{
201    struct purga_page *page;
202    unsigned i, bit, set, hits;
203    uint64_t cid_hash, hash;
204
205    page = TAILQ_FIRST(&purga->pur_pages);
206    if (!page)
207        goto end;
208
209    cid_hash = XXH64(cid->idbuf, cid->len, 0);
210    do
211    {
212#ifndef NDEBUG
213        ++purga->pur_stats.searches;
214#endif
215        hash = cid_hash;
216        hits = 0;
217        for (i = 0; i < BLOOM_N_FUNCS; ++i)
218        {
219            bit = (unsigned) hash & (BLOOM_BITS_PER_EL - 1);
220            set = ((unsigned) hash >> BLOOM_SET_SHIFT) & (BLOOM_N_MASK_ELS - 1);
221            hits += (page->pupa_mask[set] & (BLOOM_ONE << bit)) != 0;
222            hash >>= BLOOM_SHIFT;
223        }
224        if (hits < BLOOM_N_FUNCS)
225            goto next_page;
226        for (i = 0; i < page->pupa_count; ++i)
227            if (LSQUIC_CIDS_EQ(&page->pupa_cids[i], cid))
228            {
229                LSQ_DEBUGC("found %"CID_FMT, CID_BITS(cid));
230                return &page->pupa_els[i];
231            }
232#ifndef NDEBUG
233        ++purga->pur_stats.false_hits;
234#endif
235  next_page:
236        page = TAILQ_NEXT(page, pupa_next);
237    }
238    while (page);
239
240  end:
241    LSQ_DEBUGC("%"CID_FMT" not found", CID_BITS(cid));
242    return NULL;
243}
244
245
246void
247lsquic_purga_destroy (struct lsquic_purga *purga)
248{
249    struct purga_page *page;
250
251    while ((page = TAILQ_FIRST(&purga->pur_pages)))
252    {
253        TAILQ_REMOVE(&purga->pur_pages, page, pupa_next);
254        if (purga->pur_remove_cids && page->pupa_count)
255            purga_remove_cids(purga, page);
256        free(page);
257    }
258    free(purga);
259    LSQ_INFO("destroyed");
260}
261
262
263unsigned
264lsquic_purga_cids_per_page (void)
265{
266    LSQ_DEBUG("CIDs per page: %u", PURGA_ELS_PER_PAGE);
267    return PURGA_ELS_PER_PAGE;
268}
269
270
271#ifndef NDEBUG
272struct purga_bloom_stats *
273lsquic_purga_get_bloom_stats (struct lsquic_purga *purga)
274{
275    return &purga->pur_stats;
276}
277#endif
278