lsquic_stock_shi.c revision 5392f7a3
15392f7a3SLiteSpeed Tech/* Copyright (c) 2017 - 2019 LiteSpeed Technologies Inc.  See LICENSE. */
25392f7a3SLiteSpeed Tech/*
35392f7a3SLiteSpeed Tech * lsquic_stock_shi.c
45392f7a3SLiteSpeed Tech */
55392f7a3SLiteSpeed Tech
65392f7a3SLiteSpeed Tech#include <errno.h>
75392f7a3SLiteSpeed Tech#include <stdlib.h>
85392f7a3SLiteSpeed Tech#include <string.h>
95392f7a3SLiteSpeed Tech#include <sys/queue.h>
105392f7a3SLiteSpeed Tech#include <time.h>
115392f7a3SLiteSpeed Tech
125392f7a3SLiteSpeed Tech#include "lsquic.h"
135392f7a3SLiteSpeed Tech#include "lsquic_stock_shi.h"
145392f7a3SLiteSpeed Tech#include "lsquic_malo.h"
155392f7a3SLiteSpeed Tech#include "lsquic_hash.h"
165392f7a3SLiteSpeed Tech
175392f7a3SLiteSpeed Techstruct stock_shared_hash
185392f7a3SLiteSpeed Tech{
195392f7a3SLiteSpeed Tech    TAILQ_HEAD(, hash_elem)     lru_elems;
205392f7a3SLiteSpeed Tech    struct lsquic_hash         *lhash;
215392f7a3SLiteSpeed Tech    struct malo                *malo;
225392f7a3SLiteSpeed Tech};
235392f7a3SLiteSpeed Tech
245392f7a3SLiteSpeed Tech
255392f7a3SLiteSpeed Techstruct key
265392f7a3SLiteSpeed Tech{
275392f7a3SLiteSpeed Tech    void         *buf;
285392f7a3SLiteSpeed Tech    unsigned      sz;
295392f7a3SLiteSpeed Tech};
305392f7a3SLiteSpeed Tech
315392f7a3SLiteSpeed Tech
325392f7a3SLiteSpeed Techstruct hash_elem
335392f7a3SLiteSpeed Tech{
345392f7a3SLiteSpeed Tech    TAILQ_ENTRY(hash_elem)  next_lru_he;
355392f7a3SLiteSpeed Tech    struct lsquic_hash_elem lhash_elem;
365392f7a3SLiteSpeed Tech    void                   *data;
375392f7a3SLiteSpeed Tech    time_t                  expiry;         /* If not 0, the element is on LRU list */
385392f7a3SLiteSpeed Tech    struct key              key;
395392f7a3SLiteSpeed Tech    unsigned                data_sz;
405392f7a3SLiteSpeed Tech};
415392f7a3SLiteSpeed Tech
425392f7a3SLiteSpeed Tech
435392f7a3SLiteSpeed Techstatic void
445392f7a3SLiteSpeed Techfree_key_data (struct hash_elem *he)
455392f7a3SLiteSpeed Tech{
465392f7a3SLiteSpeed Tech    if (he->data_sz)
475392f7a3SLiteSpeed Tech        free(he->data);
485392f7a3SLiteSpeed Tech    free(he->key.buf);
495392f7a3SLiteSpeed Tech}
505392f7a3SLiteSpeed Tech
515392f7a3SLiteSpeed Tech
525392f7a3SLiteSpeed Techstatic void
535392f7a3SLiteSpeed Techdelete_expired_elements (struct stock_shared_hash *hash)
545392f7a3SLiteSpeed Tech{
555392f7a3SLiteSpeed Tech    struct hash_elem *he;
565392f7a3SLiteSpeed Tech    time_t now = time(NULL);
575392f7a3SLiteSpeed Tech    while ((he = TAILQ_FIRST(&hash->lru_elems)))
585392f7a3SLiteSpeed Tech    {
595392f7a3SLiteSpeed Tech        if (he->expiry < now)
605392f7a3SLiteSpeed Tech        {
615392f7a3SLiteSpeed Tech            lsquic_hash_erase(hash->lhash, &he->lhash_elem);
625392f7a3SLiteSpeed Tech            if (he->expiry)
635392f7a3SLiteSpeed Tech                TAILQ_REMOVE(&hash->lru_elems, he, next_lru_he);
645392f7a3SLiteSpeed Tech            free_key_data(he);
655392f7a3SLiteSpeed Tech            lsquic_malo_put(he);
665392f7a3SLiteSpeed Tech        }
675392f7a3SLiteSpeed Tech        else
685392f7a3SLiteSpeed Tech            break;
695392f7a3SLiteSpeed Tech    }
705392f7a3SLiteSpeed Tech}
715392f7a3SLiteSpeed Tech
725392f7a3SLiteSpeed Tech
735392f7a3SLiteSpeed Techstatic int
745392f7a3SLiteSpeed Techstock_shi_insert (void *hash_ctx, void *key, unsigned key_sz,
755392f7a3SLiteSpeed Tech                  void *data, unsigned data_sz, time_t expiry)
765392f7a3SLiteSpeed Tech{
775392f7a3SLiteSpeed Tech    struct stock_shared_hash *const hash = hash_ctx;
785392f7a3SLiteSpeed Tech    struct hash_elem *he;
795392f7a3SLiteSpeed Tech
805392f7a3SLiteSpeed Tech    /* Potential optimization: do not exire on every insert.  Use case:
815392f7a3SLiteSpeed Tech     * if many insert occur in a row, it is not efficient to perform
825392f7a3SLiteSpeed Tech     * this check every time.  Can add a counter in hash.
835392f7a3SLiteSpeed Tech     */
845392f7a3SLiteSpeed Tech    if (!TAILQ_EMPTY(&hash->lru_elems))
855392f7a3SLiteSpeed Tech        delete_expired_elements(hash);
865392f7a3SLiteSpeed Tech
875392f7a3SLiteSpeed Tech    he = lsquic_malo_get(hash->malo);
885392f7a3SLiteSpeed Tech    if (!he)
895392f7a3SLiteSpeed Tech        return -1;
905392f7a3SLiteSpeed Tech    he->key.buf = key;
915392f7a3SLiteSpeed Tech    he->key.sz  = key_sz;
925392f7a3SLiteSpeed Tech    he->data    = data;
935392f7a3SLiteSpeed Tech    he->data_sz = data_sz;
945392f7a3SLiteSpeed Tech    he->expiry = expiry;
955392f7a3SLiteSpeed Tech    memset(&he->lhash_elem, 0, sizeof(he->lhash_elem));
965392f7a3SLiteSpeed Tech    if (lsquic_hash_insert(hash->lhash, he->key.buf,
975392f7a3SLiteSpeed Tech                                            he->key.sz, he, &he->lhash_elem))
985392f7a3SLiteSpeed Tech    {
995392f7a3SLiteSpeed Tech        if (expiry)
1005392f7a3SLiteSpeed Tech            TAILQ_INSERT_TAIL(&hash->lru_elems, he, next_lru_he);
1015392f7a3SLiteSpeed Tech        return 0;
1025392f7a3SLiteSpeed Tech    }
1035392f7a3SLiteSpeed Tech    else
1045392f7a3SLiteSpeed Tech    {
1055392f7a3SLiteSpeed Tech        lsquic_malo_put(he);
1065392f7a3SLiteSpeed Tech        return -1;
1075392f7a3SLiteSpeed Tech    }
1085392f7a3SLiteSpeed Tech}
1095392f7a3SLiteSpeed Tech
1105392f7a3SLiteSpeed Tech
1115392f7a3SLiteSpeed Techstatic int
1125392f7a3SLiteSpeed Techstock_shi_lookup (void *hash_ctx, const void *key, unsigned key_sz,
1135392f7a3SLiteSpeed Tech                                  void     **data, unsigned *data_sz)
1145392f7a3SLiteSpeed Tech{
1155392f7a3SLiteSpeed Tech    struct stock_shared_hash *const hash = hash_ctx;
1165392f7a3SLiteSpeed Tech    struct hash_elem *he;
1175392f7a3SLiteSpeed Tech    struct lsquic_hash_elem *el;
1185392f7a3SLiteSpeed Tech
1195392f7a3SLiteSpeed Tech    if (!TAILQ_EMPTY(&hash->lru_elems))
1205392f7a3SLiteSpeed Tech        delete_expired_elements(hash);
1215392f7a3SLiteSpeed Tech
1225392f7a3SLiteSpeed Tech    el = lsquic_hash_find(hash->lhash, key, key_sz);
1235392f7a3SLiteSpeed Tech    if (!el)
1245392f7a3SLiteSpeed Tech        return 0;                                   /* 0: not found */
1255392f7a3SLiteSpeed Tech    he = lsquic_hashelem_getdata(el);
1265392f7a3SLiteSpeed Tech    *data    = he->data;
1275392f7a3SLiteSpeed Tech    *data_sz = he->data_sz;
1285392f7a3SLiteSpeed Tech    return 1;                                       /* 1: found */
1295392f7a3SLiteSpeed Tech}
1305392f7a3SLiteSpeed Tech
1315392f7a3SLiteSpeed Tech
1325392f7a3SLiteSpeed Techstatic int
1335392f7a3SLiteSpeed Techstock_shi_delete (void *hash_ctx, const void *key, unsigned key_sz)
1345392f7a3SLiteSpeed Tech{
1355392f7a3SLiteSpeed Tech    struct stock_shared_hash *const hash = hash_ctx;
1365392f7a3SLiteSpeed Tech    struct lsquic_hash_elem *el;
1375392f7a3SLiteSpeed Tech    struct hash_elem *he;
1385392f7a3SLiteSpeed Tech
1395392f7a3SLiteSpeed Tech    if (!TAILQ_EMPTY(&hash->lru_elems))
1405392f7a3SLiteSpeed Tech        delete_expired_elements(hash);
1415392f7a3SLiteSpeed Tech
1425392f7a3SLiteSpeed Tech    el = lsquic_hash_find(hash->lhash, key, key_sz);
1435392f7a3SLiteSpeed Tech    if (!el)
1445392f7a3SLiteSpeed Tech        return -1;
1455392f7a3SLiteSpeed Tech
1465392f7a3SLiteSpeed Tech    he = lsquic_hashelem_getdata(el);
1475392f7a3SLiteSpeed Tech    lsquic_hash_erase(hash->lhash, el);
1485392f7a3SLiteSpeed Tech    if (he->expiry)
1495392f7a3SLiteSpeed Tech        TAILQ_REMOVE(&hash->lru_elems, he, next_lru_he);
1505392f7a3SLiteSpeed Tech
1515392f7a3SLiteSpeed Tech    free_key_data(he);
1525392f7a3SLiteSpeed Tech    lsquic_malo_put(he);
1535392f7a3SLiteSpeed Tech    return 0;
1545392f7a3SLiteSpeed Tech}
1555392f7a3SLiteSpeed Tech
1565392f7a3SLiteSpeed Tech
1575392f7a3SLiteSpeed Techstruct stock_shared_hash *
1585392f7a3SLiteSpeed Techstock_shared_hash_new (void)
1595392f7a3SLiteSpeed Tech{
1605392f7a3SLiteSpeed Tech    struct malo *malo;
1615392f7a3SLiteSpeed Tech    struct stock_shared_hash *hash;
1625392f7a3SLiteSpeed Tech
1635392f7a3SLiteSpeed Tech    malo = lsquic_malo_create(sizeof(struct hash_elem));
1645392f7a3SLiteSpeed Tech    if (!malo)
1655392f7a3SLiteSpeed Tech        return NULL;
1665392f7a3SLiteSpeed Tech
1675392f7a3SLiteSpeed Tech    hash = lsquic_malo_get(malo);
1685392f7a3SLiteSpeed Tech    if (!hash)
1695392f7a3SLiteSpeed Tech    {   /* This would be really odd, but let's check this for completeness. */
1705392f7a3SLiteSpeed Tech        lsquic_malo_destroy(malo);
1715392f7a3SLiteSpeed Tech        return NULL;
1725392f7a3SLiteSpeed Tech    }
1735392f7a3SLiteSpeed Tech
1745392f7a3SLiteSpeed Tech    hash->malo = malo;
1755392f7a3SLiteSpeed Tech    hash->lhash = lsquic_hash_create();
1765392f7a3SLiteSpeed Tech    TAILQ_INIT(&hash->lru_elems);
1775392f7a3SLiteSpeed Tech    return hash;
1785392f7a3SLiteSpeed Tech}
1795392f7a3SLiteSpeed Tech
1805392f7a3SLiteSpeed Tech
1815392f7a3SLiteSpeed Techvoid
1825392f7a3SLiteSpeed Techstock_shared_hash_destroy (struct stock_shared_hash *hash)
1835392f7a3SLiteSpeed Tech{
1845392f7a3SLiteSpeed Tech    struct hash_elem *he;
1855392f7a3SLiteSpeed Tech    struct lsquic_hash_elem *el;
1865392f7a3SLiteSpeed Tech    for (el = lsquic_hash_first(hash->lhash); el;
1875392f7a3SLiteSpeed Tech                                        el = lsquic_hash_next(hash->lhash))
1885392f7a3SLiteSpeed Tech    {
1895392f7a3SLiteSpeed Tech        he = lsquic_hashelem_getdata(el);
1905392f7a3SLiteSpeed Tech        free_key_data(he);
1915392f7a3SLiteSpeed Tech        /* No need to lsquic_malo_put(he) here */
1925392f7a3SLiteSpeed Tech    }
1935392f7a3SLiteSpeed Tech    lsquic_hash_destroy(hash->lhash);
1945392f7a3SLiteSpeed Tech    lsquic_malo_destroy(hash->malo);
1955392f7a3SLiteSpeed Tech}
1965392f7a3SLiteSpeed Tech
1975392f7a3SLiteSpeed Tech
1985392f7a3SLiteSpeed Techconst struct lsquic_shared_hash_if stock_shi =
1995392f7a3SLiteSpeed Tech{
2005392f7a3SLiteSpeed Tech    .shi_insert = stock_shi_insert,
2015392f7a3SLiteSpeed Tech    .shi_delete = stock_shi_delete,
2025392f7a3SLiteSpeed Tech    .shi_lookup = stock_shi_lookup,
2035392f7a3SLiteSpeed Tech};
2045392f7a3SLiteSpeed Tech
2055392f7a3SLiteSpeed Tech
2065392f7a3SLiteSpeed Tech/* Need this to save one malloc using malo: */
2075392f7a3SLiteSpeed Techtypedef char hash_not_larger_than_hash_elem [
2085392f7a3SLiteSpeed Tech            (sizeof(struct stock_shared_hash) <= sizeof(struct hash_elem)) - 1];
209