1/* Copyright (c) 2017 - 2022 LiteSpeed Technologies Inc.  See LICENSE. */
2/*
3 * lsquic_stock_shi.c
4 */
5
6#include <errno.h>
7#include <stdlib.h>
8#include <string.h>
9#include <sys/queue.h>
10#include <time.h>
11
12#include "lsquic.h"
13#include "lsquic_stock_shi.h"
14#include "lsquic_malo.h"
15#include "lsquic_hash.h"
16
17struct stock_shared_hash
18{
19    TAILQ_HEAD(, hash_elem)     lru_elems;
20    struct lsquic_hash         *lhash;
21    struct malo                *malo;
22};
23
24
25struct key
26{
27    void         *buf;
28    unsigned      sz;
29};
30
31
32struct hash_elem
33{
34    TAILQ_ENTRY(hash_elem)  next_lru_he;
35    struct lsquic_hash_elem lhash_elem;
36    void                   *data;
37    time_t                  expiry;         /* If not 0, the element is on LRU list */
38    struct key              key;
39    unsigned                data_sz;
40};
41
42
43static void
44free_key_data (struct hash_elem *he)
45{
46    if (he->data_sz)
47        free(he->data);
48    free(he->key.buf);
49}
50
51
52static void
53delete_expired_elements (struct stock_shared_hash *hash)
54{
55    struct hash_elem *he;
56    time_t now = time(NULL);
57    while ((he = TAILQ_FIRST(&hash->lru_elems)))
58    {
59        if (he->expiry < now)
60        {
61            lsquic_hash_erase(hash->lhash, &he->lhash_elem);
62            if (he->expiry)
63                TAILQ_REMOVE(&hash->lru_elems, he, next_lru_he);
64            free_key_data(he);
65            lsquic_malo_put(he);
66        }
67        else
68            break;
69    }
70}
71
72
73static int
74stock_shi_insert (void *hash_ctx, void *key, unsigned key_sz,
75                  void *data, unsigned data_sz, time_t expiry)
76{
77    struct stock_shared_hash *const hash = hash_ctx;
78    struct hash_elem *he;
79
80    /* Potential optimization: do not exire on every insert.  Use case:
81     * if many insert occur in a row, it is not efficient to perform
82     * this check every time.  Can add a counter in hash.
83     */
84    if (!TAILQ_EMPTY(&hash->lru_elems))
85        delete_expired_elements(hash);
86
87    he = lsquic_malo_get(hash->malo);
88    if (!he)
89        return -1;
90    he->key.buf = key;
91    he->key.sz  = key_sz;
92    he->data    = data;
93    he->data_sz = data_sz;
94    he->expiry = expiry;
95    memset(&he->lhash_elem, 0, sizeof(he->lhash_elem));
96    if (lsquic_hash_insert(hash->lhash, he->key.buf,
97                                            he->key.sz, he, &he->lhash_elem))
98    {
99        if (expiry)
100            TAILQ_INSERT_TAIL(&hash->lru_elems, he, next_lru_he);
101        return 0;
102    }
103    else
104    {
105        lsquic_malo_put(he);
106        return -1;
107    }
108}
109
110
111static int
112stock_shi_lookup (void *hash_ctx, const void *key, unsigned key_sz,
113                                  void     **data, unsigned *data_sz)
114{
115    struct stock_shared_hash *const hash = hash_ctx;
116    struct hash_elem *he;
117    struct lsquic_hash_elem *el;
118
119    if (!TAILQ_EMPTY(&hash->lru_elems))
120        delete_expired_elements(hash);
121
122    el = lsquic_hash_find(hash->lhash, key, key_sz);
123    if (!el)
124        return 0;                                   /* 0: not found */
125    he = lsquic_hashelem_getdata(el);
126    *data    = he->data;
127    *data_sz = he->data_sz;
128    return 1;                                       /* 1: found */
129}
130
131
132static int
133stock_shi_delete (void *hash_ctx, const void *key, unsigned key_sz)
134{
135    struct stock_shared_hash *const hash = hash_ctx;
136    struct lsquic_hash_elem *el;
137    struct hash_elem *he;
138
139    if (!TAILQ_EMPTY(&hash->lru_elems))
140        delete_expired_elements(hash);
141
142    el = lsquic_hash_find(hash->lhash, key, key_sz);
143    if (!el)
144        return -1;
145
146    he = lsquic_hashelem_getdata(el);
147    lsquic_hash_erase(hash->lhash, el);
148    if (he->expiry)
149        TAILQ_REMOVE(&hash->lru_elems, he, next_lru_he);
150
151    free_key_data(he);
152    lsquic_malo_put(he);
153    return 0;
154}
155
156
157struct stock_shared_hash *
158lsquic_stock_shared_hash_new (void)
159{
160    struct malo *malo;
161    struct stock_shared_hash *hash;
162
163    malo = lsquic_malo_create(sizeof(struct hash_elem));
164    if (!malo)
165        return NULL;
166
167    hash = lsquic_malo_get(malo);
168    if (!hash)
169    {   /* This would be really odd, but let's check this for completeness. */
170        lsquic_malo_destroy(malo);
171        return NULL;
172    }
173
174    hash->malo = malo;
175    hash->lhash = lsquic_hash_create();
176    TAILQ_INIT(&hash->lru_elems);
177    return hash;
178}
179
180
181void
182lsquic_stock_shared_hash_destroy (struct stock_shared_hash *hash)
183{
184    struct hash_elem *he;
185    struct lsquic_hash_elem *el;
186    for (el = lsquic_hash_first(hash->lhash); el;
187                                        el = lsquic_hash_next(hash->lhash))
188    {
189        he = lsquic_hashelem_getdata(el);
190        free_key_data(he);
191        /* No need to lsquic_malo_put(he) here */
192    }
193    lsquic_hash_destroy(hash->lhash);
194    lsquic_malo_destroy(hash->malo);
195}
196
197
198const struct lsquic_shared_hash_if stock_shi =
199{
200    .shi_insert = stock_shi_insert,
201    .shi_delete = stock_shi_delete,
202    .shi_lookup = stock_shi_lookup,
203};
204
205
206/* Need this to save one malloc using malo: */
207typedef char hash_not_larger_than_hash_elem [
208            (sizeof(struct stock_shared_hash) <= sizeof(struct hash_elem)) ? 1 : -1];
209