1/*
2 * libwebsockets - small server side websockets and web server implementation
3 *
4 * Copyright (C) 2010 - 2021 Andy Green <andy@warmcat.com>
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a copy
7 * of this software and associated documentation files (the "Software"), to
8 * deal in the Software without restriction, including without limitation the
9 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10 * sell copies of the Software, and to permit persons to whom the Software is
11 * furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22 * IN THE SOFTWARE.
23 */
24
25#include "private-lib-core.h"
26
27typedef struct lws_map_hashtable {
28	struct lws_map			*map_owner; /* so items can find map */
29	lws_dll2_owner_t		ho;
30} lws_map_hashtable_t;
31
32typedef struct lws_map {
33	lws_map_info_t			info;
34
35	/* array of info.modulo x lws_map_hashtable_t overallocated */
36} lws_map_t;
37
38typedef struct lws_map_item {
39	lws_dll2_t			list; /* owned by hashtable */
40
41	size_t				keylen;
42	size_t				valuelen;
43
44	/* key then value is overallocated */
45} lws_map_item_t;
46
47/*
48 * lwsac-aware allocator
49 */
50
51void *
52lws_map_alloc_lwsac(struct lws_map *map, size_t x)
53{
54	return lwsac_use((struct lwsac **)map->info.opaque, x,
55					(size_t)map->info.aux);
56}
57
58void
59lws_map_free_lwsac(void *v)
60{
61}
62
63/*
64 * Default allocation / free if none given in info
65 */
66
67void *
68lws_map_alloc_lws_malloc(struct lws_map *mo, size_t x)
69{
70	return lws_malloc(x, __func__);
71}
72
73void
74lws_map_free_lws_free(void *v)
75{
76	lws_free(v);
77}
78
79/*
80 * This just needs to approximate a flat distribution, it's not related to
81 * security at all.
82 */
83
84lws_map_hash_t
85lws_map_hash_from_key_default(const lws_map_key_t key, size_t kl)
86{
87	lws_map_hash_t h = 0x12345678;
88	const uint8_t *u = (const uint8_t *)key;
89
90	while (kl--)
91		h = ((((h << 7) | (h >> 25)) + 0xa1b2c3d4) ^ (*u++)) ^ h;
92
93	return h;
94}
95
96int
97lws_map_compare_key_default(const lws_map_key_t key1, size_t kl1,
98			    const lws_map_value_t key2, size_t kl2)
99{
100	if (kl1 != kl2)
101		return 1;
102
103	return memcmp(key1, key2, kl1);
104}
105
106lws_map_t *
107lws_map_create(const lws_map_info_t *info)
108{
109	lws_map_t *map;
110	lws_map_alloc_t a = info->_alloc;
111	size_t modulo = info->modulo;
112	lws_map_hashtable_t *ht;
113	size_t size;
114
115	if (!a)
116		a = lws_map_alloc_lws_malloc;
117
118	if (!modulo)
119		modulo = 8;
120
121	size = sizeof(*map) + (modulo * sizeof(lws_map_hashtable_t));
122	map = lws_malloc(size, __func__);
123	if (!map)
124		return NULL;
125
126	memset(map, 0, size);
127
128	map->info = *info;
129
130	map->info._alloc = a;
131	map->info.modulo = modulo;
132	if (!info->_free)
133		map->info._free = lws_map_free_lws_free;
134	if (!info->_hash)
135		map->info._hash = lws_map_hash_from_key_default;
136	if (!info->_compare)
137		map->info._compare = lws_map_compare_key_default;
138
139	ht = (lws_map_hashtable_t *)&map[1];
140	while (modulo--)
141		ht[modulo].map_owner = map;
142
143	return map;
144}
145
146static int
147ho_free_item(struct lws_dll2 *d, void *user)
148{
149	lws_map_item_t *i = lws_container_of(d, lws_map_item_t, list);
150
151	lws_map_item_destroy(i);
152
153	return 0;
154}
155
156void
157lws_map_destroy(lws_map_t **pmap)
158{
159	lws_map_hashtable_t *ht;
160	lws_map_t *map = *pmap;
161
162	if (!map)
163		return;
164
165	/* empty out all the hashtables */
166
167	ht = (lws_map_hashtable_t *)&(map[1]);
168	while (map->info.modulo--) {
169		lws_dll2_foreach_safe(&ht->ho, ht, ho_free_item);
170		ht++;
171	}
172
173	/* free the map itself */
174
175	lws_free_set_NULL(*pmap);
176}
177
178lws_map_item_t *
179lws_map_item_create(lws_map_t *map,
180		    const lws_map_key_t key, size_t keylen,
181		    const lws_map_value_t value, size_t valuelen)
182{
183	lws_map_hashtable_t *ht;
184	lws_map_item_t *item;
185	lws_map_hash_t h;
186	size_t hti;
187	uint8_t *u;
188
189	item = lws_map_item_lookup(map, key, keylen);
190	if (item)
191		lws_map_item_destroy(item);
192
193	item = map->info._alloc(map, sizeof(*item) + keylen + valuelen);
194	if (!item)
195		return NULL;
196
197	lws_dll2_clear(&item->list);
198	item->keylen = keylen;
199	item->valuelen = valuelen;
200
201	u = (uint8_t *)&item[1];
202	memcpy(u, key, keylen);
203	u += keylen;
204	if (value)
205		memcpy(u, value, valuelen);
206
207	h = map->info._hash(key, keylen);
208
209	hti = h % map->info.modulo;
210	ht = (lws_map_hashtable_t *)&map[1];
211
212	lws_dll2_add_head(&item->list, &ht[hti].ho);
213
214	return item;
215}
216
217void
218lws_map_item_destroy(lws_map_item_t *item)
219{
220	lws_map_hashtable_t *ht = lws_container_of(item->list.owner,
221						   lws_map_hashtable_t, ho);
222
223	lws_dll2_remove(&item->list);
224	ht->map_owner->info._free(item);
225}
226
227lws_map_item_t *
228lws_map_item_lookup(lws_map_t *map, const lws_map_key_t key, size_t keylen)
229{
230	lws_map_hash_t h = map->info._hash(key, keylen);
231	lws_map_hashtable_t *ht = (lws_map_hashtable_t *)&map[1];
232
233	lws_start_foreach_dll(struct lws_dll2 *, p,
234			      ht[h % map->info.modulo].ho.head) {
235		lws_map_item_t *i = lws_container_of(p, lws_map_item_t, list);
236
237		if (!map->info._compare(key, keylen, &i[1], i->keylen))
238			return i;
239	} lws_end_foreach_dll(p);
240
241	return NULL;
242}
243
244const void *
245lws_map_item_key(lws_map_item_t *_item)
246{
247	return ((void *)&_item[1]);
248}
249
250const void *
251lws_map_item_value(lws_map_item_t *_item)
252{
253	return (void *)(((uint8_t *)&_item[1]) + _item->keylen);
254}
255
256size_t
257lws_map_item_key_len(lws_map_item_t *_item)
258{
259	return _item->keylen;
260}
261
262size_t
263lws_map_item_value_len(lws_map_item_t *_item)
264{
265	return _item->valuelen;
266}
267