xref: /aosp_15_r20/external/libwebsockets/lib/misc/cache-ttl/heap.c (revision 1c60b9aca93fdbc9b5f19b2d2194c91294b22281)
1*1c60b9acSAndroid Build Coastguard Worker /*
2*1c60b9acSAndroid Build Coastguard Worker  * libwebsockets - small server side websockets and web server implementation
3*1c60b9acSAndroid Build Coastguard Worker  *
4*1c60b9acSAndroid Build Coastguard Worker  * Copyright (C) 2010 - 2021 Andy Green <[email protected]>
5*1c60b9acSAndroid Build Coastguard Worker  *
6*1c60b9acSAndroid Build Coastguard Worker  * Permission is hereby granted, free of charge, to any person obtaining a copy
7*1c60b9acSAndroid Build Coastguard Worker  * of this software and associated documentation files (the "Software"), to
8*1c60b9acSAndroid Build Coastguard Worker  * deal in the Software without restriction, including without limitation the
9*1c60b9acSAndroid Build Coastguard Worker  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10*1c60b9acSAndroid Build Coastguard Worker  * sell copies of the Software, and to permit persons to whom the Software is
11*1c60b9acSAndroid Build Coastguard Worker  * furnished to do so, subject to the following conditions:
12*1c60b9acSAndroid Build Coastguard Worker  *
13*1c60b9acSAndroid Build Coastguard Worker  * The above copyright notice and this permission notice shall be included in
14*1c60b9acSAndroid Build Coastguard Worker  * all copies or substantial portions of the Software.
15*1c60b9acSAndroid Build Coastguard Worker  *
16*1c60b9acSAndroid Build Coastguard Worker  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17*1c60b9acSAndroid Build Coastguard Worker  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18*1c60b9acSAndroid Build Coastguard Worker  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19*1c60b9acSAndroid Build Coastguard Worker  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20*1c60b9acSAndroid Build Coastguard Worker  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21*1c60b9acSAndroid Build Coastguard Worker  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22*1c60b9acSAndroid Build Coastguard Worker  * IN THE SOFTWARE.
23*1c60b9acSAndroid Build Coastguard Worker  */
24*1c60b9acSAndroid Build Coastguard Worker 
25*1c60b9acSAndroid Build Coastguard Worker #include <private-lib-core.h>
26*1c60b9acSAndroid Build Coastguard Worker #include "private-lib-misc-cache-ttl.h"
27*1c60b9acSAndroid Build Coastguard Worker 
28*1c60b9acSAndroid Build Coastguard Worker #if defined(write)
29*1c60b9acSAndroid Build Coastguard Worker #undef write
30*1c60b9acSAndroid Build Coastguard Worker #endif
31*1c60b9acSAndroid Build Coastguard Worker 
32*1c60b9acSAndroid Build Coastguard Worker static void
33*1c60b9acSAndroid Build Coastguard Worker update_sul(lws_cache_ttl_lru_t_heap_t *cache);
34*1c60b9acSAndroid Build Coastguard Worker 
35*1c60b9acSAndroid Build Coastguard Worker static int
36*1c60b9acSAndroid Build Coastguard Worker lws_cache_heap_invalidate(struct lws_cache_ttl_lru *_c, const char *key);
37*1c60b9acSAndroid Build Coastguard Worker 
38*1c60b9acSAndroid Build Coastguard Worker static int
sort_expiry(const lws_dll2_t * a,const lws_dll2_t * b)39*1c60b9acSAndroid Build Coastguard Worker sort_expiry(const lws_dll2_t *a, const lws_dll2_t *b)
40*1c60b9acSAndroid Build Coastguard Worker {
41*1c60b9acSAndroid Build Coastguard Worker 	const lws_cache_ttl_item_heap_t
42*1c60b9acSAndroid Build Coastguard Worker 		*c = lws_container_of(a, lws_cache_ttl_item_heap_t, list_expiry),
43*1c60b9acSAndroid Build Coastguard Worker 		*d = lws_container_of(b, lws_cache_ttl_item_heap_t, list_expiry);
44*1c60b9acSAndroid Build Coastguard Worker 
45*1c60b9acSAndroid Build Coastguard Worker 	if (c->expiry > d->expiry)
46*1c60b9acSAndroid Build Coastguard Worker 		return 1;
47*1c60b9acSAndroid Build Coastguard Worker 	if (c->expiry < d->expiry)
48*1c60b9acSAndroid Build Coastguard Worker 		return -1;
49*1c60b9acSAndroid Build Coastguard Worker 
50*1c60b9acSAndroid Build Coastguard Worker 	return 0;
51*1c60b9acSAndroid Build Coastguard Worker }
52*1c60b9acSAndroid Build Coastguard Worker 
53*1c60b9acSAndroid Build Coastguard Worker static void
_lws_cache_heap_item_destroy(lws_cache_ttl_lru_t_heap_t * cache,lws_cache_ttl_item_heap_t * item)54*1c60b9acSAndroid Build Coastguard Worker _lws_cache_heap_item_destroy(lws_cache_ttl_lru_t_heap_t *cache,
55*1c60b9acSAndroid Build Coastguard Worker 			     lws_cache_ttl_item_heap_t *item)
56*1c60b9acSAndroid Build Coastguard Worker {
57*1c60b9acSAndroid Build Coastguard Worker 	lwsl_cache("%s: %s (%s)\n", __func__, cache->cache.info.name,
58*1c60b9acSAndroid Build Coastguard Worker 			(const char *)&item[1] + item->size);
59*1c60b9acSAndroid Build Coastguard Worker 
60*1c60b9acSAndroid Build Coastguard Worker 	lws_dll2_remove(&item->list_expiry);
61*1c60b9acSAndroid Build Coastguard Worker 	lws_dll2_remove(&item->list_lru);
62*1c60b9acSAndroid Build Coastguard Worker 
63*1c60b9acSAndroid Build Coastguard Worker 	cache->cache.current_footprint -= item->size;
64*1c60b9acSAndroid Build Coastguard Worker 
65*1c60b9acSAndroid Build Coastguard Worker 	update_sul(cache);
66*1c60b9acSAndroid Build Coastguard Worker 
67*1c60b9acSAndroid Build Coastguard Worker 	if (cache->cache.info.cb)
68*1c60b9acSAndroid Build Coastguard Worker 		cache->cache.info.cb((void *)((uint8_t *)&item[1]), item->size);
69*1c60b9acSAndroid Build Coastguard Worker 
70*1c60b9acSAndroid Build Coastguard Worker 	lws_free(item);
71*1c60b9acSAndroid Build Coastguard Worker }
72*1c60b9acSAndroid Build Coastguard Worker 
73*1c60b9acSAndroid Build Coastguard Worker static void
lws_cache_heap_item_destroy(lws_cache_ttl_lru_t_heap_t * cache,lws_cache_ttl_item_heap_t * item,int parent_too)74*1c60b9acSAndroid Build Coastguard Worker lws_cache_heap_item_destroy(lws_cache_ttl_lru_t_heap_t *cache,
75*1c60b9acSAndroid Build Coastguard Worker 			    lws_cache_ttl_item_heap_t *item, int parent_too)
76*1c60b9acSAndroid Build Coastguard Worker {
77*1c60b9acSAndroid Build Coastguard Worker 	struct lws_cache_ttl_lru *backing = &cache->cache;
78*1c60b9acSAndroid Build Coastguard Worker 	const char *tag = ((const char *)&item[1]) + item->size;
79*1c60b9acSAndroid Build Coastguard Worker 
80*1c60b9acSAndroid Build Coastguard Worker 	/*
81*1c60b9acSAndroid Build Coastguard Worker 	 * We're destroying a normal item?
82*1c60b9acSAndroid Build Coastguard Worker 	 */
83*1c60b9acSAndroid Build Coastguard Worker 
84*1c60b9acSAndroid Build Coastguard Worker 	if (*tag == META_ITEM_LEADING)
85*1c60b9acSAndroid Build Coastguard Worker 		/* no, nothing to check here then */
86*1c60b9acSAndroid Build Coastguard Worker 		goto post;
87*1c60b9acSAndroid Build Coastguard Worker 
88*1c60b9acSAndroid Build Coastguard Worker 	if (backing->info.parent)
89*1c60b9acSAndroid Build Coastguard Worker 		backing = backing->info.parent;
90*1c60b9acSAndroid Build Coastguard Worker 
91*1c60b9acSAndroid Build Coastguard Worker 	/*
92*1c60b9acSAndroid Build Coastguard Worker 	 * We need to check any cached meta-results from lookups that
93*1c60b9acSAndroid Build Coastguard Worker 	 * include this normal item, and if any, invalidate the meta-results
94*1c60b9acSAndroid Build Coastguard Worker 	 * since they have to be recalculated before being used again.
95*1c60b9acSAndroid Build Coastguard Worker 	 */
96*1c60b9acSAndroid Build Coastguard Worker 
97*1c60b9acSAndroid Build Coastguard Worker 	lws_start_foreach_dll_safe(struct lws_dll2 *, d, d1,
98*1c60b9acSAndroid Build Coastguard Worker 				   cache->items_lru.head) {
99*1c60b9acSAndroid Build Coastguard Worker 		lws_cache_ttl_item_heap_t *i = lws_container_of(d,
100*1c60b9acSAndroid Build Coastguard Worker 						lws_cache_ttl_item_heap_t,
101*1c60b9acSAndroid Build Coastguard Worker 						list_lru);
102*1c60b9acSAndroid Build Coastguard Worker 		const char *iname = ((const char *)&item[1]) + item->size;
103*1c60b9acSAndroid Build Coastguard Worker 		uint8_t *pay = (uint8_t *)&item[1], *end = pay + item->size;
104*1c60b9acSAndroid Build Coastguard Worker 
105*1c60b9acSAndroid Build Coastguard Worker 		if (*iname == META_ITEM_LEADING) {
106*1c60b9acSAndroid Build Coastguard Worker 			size_t taglen = strlen(iname);
107*1c60b9acSAndroid Build Coastguard Worker 
108*1c60b9acSAndroid Build Coastguard Worker 			/*
109*1c60b9acSAndroid Build Coastguard Worker 			 * If the item about to be destroyed makes an
110*1c60b9acSAndroid Build Coastguard Worker 			 * appearance on the meta results list, we must kill
111*1c60b9acSAndroid Build Coastguard Worker 			 * the meta result item to force recalc next time
112*1c60b9acSAndroid Build Coastguard Worker 			 */
113*1c60b9acSAndroid Build Coastguard Worker 
114*1c60b9acSAndroid Build Coastguard Worker 			while (pay < end) {
115*1c60b9acSAndroid Build Coastguard Worker 				uint32_t tlen = lws_ser_ru32be(pay + 4);
116*1c60b9acSAndroid Build Coastguard Worker 
117*1c60b9acSAndroid Build Coastguard Worker 				if (tlen == taglen &&
118*1c60b9acSAndroid Build Coastguard Worker 				    !strcmp((const char *)pay + 8, iname)) {
119*1c60b9acSAndroid Build Coastguard Worker #if defined(_DEBUG)
120*1c60b9acSAndroid Build Coastguard Worker 					/*
121*1c60b9acSAndroid Build Coastguard Worker 					 * Sanity check that the item tag is
122*1c60b9acSAndroid Build Coastguard Worker 					 * really a match for that meta results
123*1c60b9acSAndroid Build Coastguard Worker 					 * item
124*1c60b9acSAndroid Build Coastguard Worker 					 */
125*1c60b9acSAndroid Build Coastguard Worker 
126*1c60b9acSAndroid Build Coastguard Worker 					assert (!backing->info.ops->tag_match(
127*1c60b9acSAndroid Build Coastguard Worker 						 backing, iname + 1, tag, 1));
128*1c60b9acSAndroid Build Coastguard Worker #endif
129*1c60b9acSAndroid Build Coastguard Worker 					_lws_cache_heap_item_destroy(cache, i);
130*1c60b9acSAndroid Build Coastguard Worker 					break;
131*1c60b9acSAndroid Build Coastguard Worker 				}
132*1c60b9acSAndroid Build Coastguard Worker 				pay += 8 + tlen + 1;
133*1c60b9acSAndroid Build Coastguard Worker 			}
134*1c60b9acSAndroid Build Coastguard Worker 
135*1c60b9acSAndroid Build Coastguard Worker #if defined(_DEBUG)
136*1c60b9acSAndroid Build Coastguard Worker 			/*
137*1c60b9acSAndroid Build Coastguard Worker 			 * Sanity check that the item tag really isn't a match
138*1c60b9acSAndroid Build Coastguard Worker 			 * for that meta results item
139*1c60b9acSAndroid Build Coastguard Worker 			 */
140*1c60b9acSAndroid Build Coastguard Worker 
141*1c60b9acSAndroid Build Coastguard Worker 			assert (backing->info.ops->tag_match(backing, iname + 1,
142*1c60b9acSAndroid Build Coastguard Worker 							  tag, 1));
143*1c60b9acSAndroid Build Coastguard Worker #endif
144*1c60b9acSAndroid Build Coastguard Worker 		}
145*1c60b9acSAndroid Build Coastguard Worker 
146*1c60b9acSAndroid Build Coastguard Worker 	} lws_end_foreach_dll_safe(d, d1);
147*1c60b9acSAndroid Build Coastguard Worker 
148*1c60b9acSAndroid Build Coastguard Worker post:
149*1c60b9acSAndroid Build Coastguard Worker 	_lws_cache_heap_item_destroy(cache, item);
150*1c60b9acSAndroid Build Coastguard Worker }
151*1c60b9acSAndroid Build Coastguard Worker 
152*1c60b9acSAndroid Build Coastguard Worker static void
lws_cache_item_evict_lru(lws_cache_ttl_lru_t_heap_t * cache)153*1c60b9acSAndroid Build Coastguard Worker lws_cache_item_evict_lru(lws_cache_ttl_lru_t_heap_t *cache)
154*1c60b9acSAndroid Build Coastguard Worker {
155*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_item_heap_t *ei;
156*1c60b9acSAndroid Build Coastguard Worker 
157*1c60b9acSAndroid Build Coastguard Worker 	if (!cache->items_lru.head)
158*1c60b9acSAndroid Build Coastguard Worker 		return;
159*1c60b9acSAndroid Build Coastguard Worker 
160*1c60b9acSAndroid Build Coastguard Worker 	ei = lws_container_of(cache->items_lru.head,
161*1c60b9acSAndroid Build Coastguard Worker 			      lws_cache_ttl_item_heap_t, list_lru);
162*1c60b9acSAndroid Build Coastguard Worker 
163*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_heap_item_destroy(cache, ei, 0);
164*1c60b9acSAndroid Build Coastguard Worker }
165*1c60b9acSAndroid Build Coastguard Worker 
166*1c60b9acSAndroid Build Coastguard Worker /*
167*1c60b9acSAndroid Build Coastguard Worker  * We need to weed out expired entries in the backing file
168*1c60b9acSAndroid Build Coastguard Worker  */
169*1c60b9acSAndroid Build Coastguard Worker 
170*1c60b9acSAndroid Build Coastguard Worker static void
expiry_cb(lws_sorted_usec_list_t * sul)171*1c60b9acSAndroid Build Coastguard Worker expiry_cb(lws_sorted_usec_list_t *sul)
172*1c60b9acSAndroid Build Coastguard Worker {
173*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_lru_t_heap_t *cache = lws_container_of(sul,
174*1c60b9acSAndroid Build Coastguard Worker 					lws_cache_ttl_lru_t_heap_t, cache.sul);
175*1c60b9acSAndroid Build Coastguard Worker 	lws_usec_t now = lws_now_usecs();
176*1c60b9acSAndroid Build Coastguard Worker 
177*1c60b9acSAndroid Build Coastguard Worker 	lwsl_cache("%s: %s\n", __func__, cache->cache.info.name);
178*1c60b9acSAndroid Build Coastguard Worker 
179*1c60b9acSAndroid Build Coastguard Worker 	while (cache->items_expiry.head) {
180*1c60b9acSAndroid Build Coastguard Worker 		lws_cache_ttl_item_heap_t *item;
181*1c60b9acSAndroid Build Coastguard Worker 
182*1c60b9acSAndroid Build Coastguard Worker 		item = lws_container_of(cache->items_expiry.head,
183*1c60b9acSAndroid Build Coastguard Worker 					lws_cache_ttl_item_heap_t, list_expiry);
184*1c60b9acSAndroid Build Coastguard Worker 
185*1c60b9acSAndroid Build Coastguard Worker 		if (item->expiry > now)
186*1c60b9acSAndroid Build Coastguard Worker 			return;
187*1c60b9acSAndroid Build Coastguard Worker 
188*1c60b9acSAndroid Build Coastguard Worker 		lws_cache_heap_item_destroy(cache, item, 1);
189*1c60b9acSAndroid Build Coastguard Worker 	}
190*1c60b9acSAndroid Build Coastguard Worker }
191*1c60b9acSAndroid Build Coastguard Worker 
192*1c60b9acSAndroid Build Coastguard Worker /*
193*1c60b9acSAndroid Build Coastguard Worker  * Let's figure out what the earliest next expiry is
194*1c60b9acSAndroid Build Coastguard Worker  */
195*1c60b9acSAndroid Build Coastguard Worker 
196*1c60b9acSAndroid Build Coastguard Worker static int
earliest_expiry(lws_cache_ttl_lru_t_heap_t * cache,lws_usec_t * pearliest)197*1c60b9acSAndroid Build Coastguard Worker earliest_expiry(lws_cache_ttl_lru_t_heap_t *cache, lws_usec_t *pearliest)
198*1c60b9acSAndroid Build Coastguard Worker {
199*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_item_heap_t *item;
200*1c60b9acSAndroid Build Coastguard Worker 
201*1c60b9acSAndroid Build Coastguard Worker 	if (!cache->items_expiry.head)
202*1c60b9acSAndroid Build Coastguard Worker 		return 1;
203*1c60b9acSAndroid Build Coastguard Worker 
204*1c60b9acSAndroid Build Coastguard Worker 	item = lws_container_of(cache->items_expiry.head,
205*1c60b9acSAndroid Build Coastguard Worker 				lws_cache_ttl_item_heap_t, list_expiry);
206*1c60b9acSAndroid Build Coastguard Worker 
207*1c60b9acSAndroid Build Coastguard Worker 	*pearliest = item->expiry;
208*1c60b9acSAndroid Build Coastguard Worker 
209*1c60b9acSAndroid Build Coastguard Worker 	return 0;
210*1c60b9acSAndroid Build Coastguard Worker }
211*1c60b9acSAndroid Build Coastguard Worker 
212*1c60b9acSAndroid Build Coastguard Worker static void
update_sul(lws_cache_ttl_lru_t_heap_t * cache)213*1c60b9acSAndroid Build Coastguard Worker update_sul(lws_cache_ttl_lru_t_heap_t *cache)
214*1c60b9acSAndroid Build Coastguard Worker {
215*1c60b9acSAndroid Build Coastguard Worker 	lws_usec_t earliest;
216*1c60b9acSAndroid Build Coastguard Worker 
217*1c60b9acSAndroid Build Coastguard Worker 	/* weed out any newly-expired */
218*1c60b9acSAndroid Build Coastguard Worker 	expiry_cb(&cache->cache.sul);
219*1c60b9acSAndroid Build Coastguard Worker 
220*1c60b9acSAndroid Build Coastguard Worker 	/* figure out the next soonest expiring item */
221*1c60b9acSAndroid Build Coastguard Worker 	if (earliest_expiry(cache, &earliest)) {
222*1c60b9acSAndroid Build Coastguard Worker 		lws_sul_cancel(&cache->cache.sul);
223*1c60b9acSAndroid Build Coastguard Worker 		return;
224*1c60b9acSAndroid Build Coastguard Worker 	}
225*1c60b9acSAndroid Build Coastguard Worker 
226*1c60b9acSAndroid Build Coastguard Worker 	lwsl_debug("%s: setting exp %llu\n", __func__,
227*1c60b9acSAndroid Build Coastguard Worker 			(unsigned long long)earliest);
228*1c60b9acSAndroid Build Coastguard Worker 
229*1c60b9acSAndroid Build Coastguard Worker 	if (earliest)
230*1c60b9acSAndroid Build Coastguard Worker 		lws_cache_schedule(&cache->cache, expiry_cb, earliest);
231*1c60b9acSAndroid Build Coastguard Worker }
232*1c60b9acSAndroid Build Coastguard Worker 
233*1c60b9acSAndroid Build Coastguard Worker static lws_cache_ttl_item_heap_t *
lws_cache_heap_specific(lws_cache_ttl_lru_t_heap_t * cache,const char * specific_key)234*1c60b9acSAndroid Build Coastguard Worker lws_cache_heap_specific(lws_cache_ttl_lru_t_heap_t *cache,
235*1c60b9acSAndroid Build Coastguard Worker 			const char *specific_key)
236*1c60b9acSAndroid Build Coastguard Worker {
237*1c60b9acSAndroid Build Coastguard Worker 	lws_start_foreach_dll(struct lws_dll2 *, d, cache->items_lru.head) {
238*1c60b9acSAndroid Build Coastguard Worker 		lws_cache_ttl_item_heap_t *item = lws_container_of(d,
239*1c60b9acSAndroid Build Coastguard Worker 						lws_cache_ttl_item_heap_t,
240*1c60b9acSAndroid Build Coastguard Worker 						list_lru);
241*1c60b9acSAndroid Build Coastguard Worker 		const char *iname = ((const char *)&item[1]) + item->size;
242*1c60b9acSAndroid Build Coastguard Worker 
243*1c60b9acSAndroid Build Coastguard Worker 		if (!strcmp(specific_key, iname))
244*1c60b9acSAndroid Build Coastguard Worker 			return item;
245*1c60b9acSAndroid Build Coastguard Worker 
246*1c60b9acSAndroid Build Coastguard Worker 	} lws_end_foreach_dll(d);
247*1c60b9acSAndroid Build Coastguard Worker 
248*1c60b9acSAndroid Build Coastguard Worker 	return NULL;
249*1c60b9acSAndroid Build Coastguard Worker }
250*1c60b9acSAndroid Build Coastguard Worker 
251*1c60b9acSAndroid Build Coastguard Worker static int
lws_cache_heap_tag_match(struct lws_cache_ttl_lru * cache,const char * wc,const char * tag,char lookup_rules)252*1c60b9acSAndroid Build Coastguard Worker lws_cache_heap_tag_match(struct lws_cache_ttl_lru *cache, const char *wc,
253*1c60b9acSAndroid Build Coastguard Worker 				const char *tag, char lookup_rules)
254*1c60b9acSAndroid Build Coastguard Worker {
255*1c60b9acSAndroid Build Coastguard Worker 	return lws_strcmp_wildcard(wc, strlen(wc), tag, strlen(tag));
256*1c60b9acSAndroid Build Coastguard Worker }
257*1c60b9acSAndroid Build Coastguard Worker 
258*1c60b9acSAndroid Build Coastguard Worker static int
lws_cache_heap_lookup(struct lws_cache_ttl_lru * _c,const char * wildcard_key,lws_dll2_owner_t * results_owner)259*1c60b9acSAndroid Build Coastguard Worker lws_cache_heap_lookup(struct lws_cache_ttl_lru *_c, const char *wildcard_key,
260*1c60b9acSAndroid Build Coastguard Worker 		      lws_dll2_owner_t *results_owner)
261*1c60b9acSAndroid Build Coastguard Worker {
262*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_lru_t_heap_t *cache = (lws_cache_ttl_lru_t_heap_t *)_c;
263*1c60b9acSAndroid Build Coastguard Worker 	size_t sklen = strlen(wildcard_key);
264*1c60b9acSAndroid Build Coastguard Worker 
265*1c60b9acSAndroid Build Coastguard Worker 	lws_start_foreach_dll(struct lws_dll2 *, d, cache->items_lru.head) {
266*1c60b9acSAndroid Build Coastguard Worker 		lws_cache_ttl_item_heap_t *item = lws_container_of(d,
267*1c60b9acSAndroid Build Coastguard Worker 						lws_cache_ttl_item_heap_t,
268*1c60b9acSAndroid Build Coastguard Worker 						list_lru);
269*1c60b9acSAndroid Build Coastguard Worker 		const char *iname = ((const char *)&item[1]) + item->size;
270*1c60b9acSAndroid Build Coastguard Worker 
271*1c60b9acSAndroid Build Coastguard Worker 		if (!lws_strcmp_wildcard(wildcard_key, sklen, iname,
272*1c60b9acSAndroid Build Coastguard Worker 					 strlen(iname))) {
273*1c60b9acSAndroid Build Coastguard Worker 			size_t ilen = strlen(iname);
274*1c60b9acSAndroid Build Coastguard Worker 			lws_cache_match_t *m;
275*1c60b9acSAndroid Build Coastguard Worker 			char hit = 0;
276*1c60b9acSAndroid Build Coastguard Worker 
277*1c60b9acSAndroid Build Coastguard Worker 			/*
278*1c60b9acSAndroid Build Coastguard Worker 			 * It musn't already be on the list from an earlier
279*1c60b9acSAndroid Build Coastguard Worker 			 * cache level
280*1c60b9acSAndroid Build Coastguard Worker 			 */
281*1c60b9acSAndroid Build Coastguard Worker 
282*1c60b9acSAndroid Build Coastguard Worker 			lws_start_foreach_dll(struct lws_dll2 *, e,
283*1c60b9acSAndroid Build Coastguard Worker 					results_owner->head) {
284*1c60b9acSAndroid Build Coastguard Worker 				lws_cache_match_t *i = lws_container_of(e,
285*1c60b9acSAndroid Build Coastguard Worker 							lws_cache_match_t, list);
286*1c60b9acSAndroid Build Coastguard Worker 				if (i->tag_size == ilen &&
287*1c60b9acSAndroid Build Coastguard Worker 				    !strcmp(iname, ((const char *)&i[1]))) {
288*1c60b9acSAndroid Build Coastguard Worker 					hit = 1;
289*1c60b9acSAndroid Build Coastguard Worker 					break;
290*1c60b9acSAndroid Build Coastguard Worker 				}
291*1c60b9acSAndroid Build Coastguard Worker 			} lws_end_foreach_dll(e);
292*1c60b9acSAndroid Build Coastguard Worker 
293*1c60b9acSAndroid Build Coastguard Worker 			if (!hit) {
294*1c60b9acSAndroid Build Coastguard Worker 
295*1c60b9acSAndroid Build Coastguard Worker 				/*
296*1c60b9acSAndroid Build Coastguard Worker 				 * it's unique, instantiate a record for it
297*1c60b9acSAndroid Build Coastguard Worker 				 */
298*1c60b9acSAndroid Build Coastguard Worker 
299*1c60b9acSAndroid Build Coastguard Worker 				m = lws_fi(&_c->info.cx->fic,
300*1c60b9acSAndroid Build Coastguard Worker 					   "cache_lookup_oom") ? NULL :
301*1c60b9acSAndroid Build Coastguard Worker 					lws_malloc(sizeof(*m) + ilen + 1,
302*1c60b9acSAndroid Build Coastguard Worker 						   __func__);
303*1c60b9acSAndroid Build Coastguard Worker 				if (!m) {
304*1c60b9acSAndroid Build Coastguard Worker 					lws_cache_clear_matches(results_owner);
305*1c60b9acSAndroid Build Coastguard Worker 					return 1;
306*1c60b9acSAndroid Build Coastguard Worker 				}
307*1c60b9acSAndroid Build Coastguard Worker 
308*1c60b9acSAndroid Build Coastguard Worker 				memset(&m->list, 0, sizeof(m->list));
309*1c60b9acSAndroid Build Coastguard Worker 				m->tag_size = ilen;
310*1c60b9acSAndroid Build Coastguard Worker 				memcpy(&m[1], iname, ilen + 1);
311*1c60b9acSAndroid Build Coastguard Worker 
312*1c60b9acSAndroid Build Coastguard Worker 				lws_dll2_add_tail(&m->list, results_owner);
313*1c60b9acSAndroid Build Coastguard Worker 			}
314*1c60b9acSAndroid Build Coastguard Worker 		}
315*1c60b9acSAndroid Build Coastguard Worker 
316*1c60b9acSAndroid Build Coastguard Worker 	} lws_end_foreach_dll(d);
317*1c60b9acSAndroid Build Coastguard Worker 
318*1c60b9acSAndroid Build Coastguard Worker 	return 0;
319*1c60b9acSAndroid Build Coastguard Worker }
320*1c60b9acSAndroid Build Coastguard Worker 
321*1c60b9acSAndroid Build Coastguard Worker static int
lws_cache_heap_write(struct lws_cache_ttl_lru * _c,const char * specific_key,const uint8_t * source,size_t size,lws_usec_t expiry,void ** ppvoid)322*1c60b9acSAndroid Build Coastguard Worker lws_cache_heap_write(struct lws_cache_ttl_lru *_c, const char *specific_key,
323*1c60b9acSAndroid Build Coastguard Worker 		     const uint8_t *source, size_t size, lws_usec_t expiry,
324*1c60b9acSAndroid Build Coastguard Worker 		     void **ppvoid)
325*1c60b9acSAndroid Build Coastguard Worker {
326*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_lru_t_heap_t *cache = (lws_cache_ttl_lru_t_heap_t *)_c;
327*1c60b9acSAndroid Build Coastguard Worker 	struct lws_cache_ttl_lru *backing = _c;
328*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_item_heap_t *item, *ei;
329*1c60b9acSAndroid Build Coastguard Worker 	size_t kl = strlen(specific_key);
330*1c60b9acSAndroid Build Coastguard Worker 	char *p;
331*1c60b9acSAndroid Build Coastguard Worker 
332*1c60b9acSAndroid Build Coastguard Worker 	lwsl_cache("%s: %s: len %d\n", __func__, _c->info.name, (int)size);
333*1c60b9acSAndroid Build Coastguard Worker 
334*1c60b9acSAndroid Build Coastguard Worker 	/*
335*1c60b9acSAndroid Build Coastguard Worker 	 * Is this new tag going to invalidate any existing cached meta-results?
336*1c60b9acSAndroid Build Coastguard Worker 	 *
337*1c60b9acSAndroid Build Coastguard Worker 	 * If so, let's destroy any of those first to recover the heap
338*1c60b9acSAndroid Build Coastguard Worker 	 */
339*1c60b9acSAndroid Build Coastguard Worker 
340*1c60b9acSAndroid Build Coastguard Worker 	if (backing->info.parent)
341*1c60b9acSAndroid Build Coastguard Worker 		backing = backing->info.parent;
342*1c60b9acSAndroid Build Coastguard Worker 
343*1c60b9acSAndroid Build Coastguard Worker 	lws_start_foreach_dll_safe(struct lws_dll2 *, d, d1,
344*1c60b9acSAndroid Build Coastguard Worker 				   cache->items_lru.head) {
345*1c60b9acSAndroid Build Coastguard Worker 		lws_cache_ttl_item_heap_t *i = lws_container_of(d,
346*1c60b9acSAndroid Build Coastguard Worker 						lws_cache_ttl_item_heap_t,
347*1c60b9acSAndroid Build Coastguard Worker 						list_lru);
348*1c60b9acSAndroid Build Coastguard Worker 		const char *iname = ((const char *)&i[1]) + i->size;
349*1c60b9acSAndroid Build Coastguard Worker 
350*1c60b9acSAndroid Build Coastguard Worker 		if (*iname == META_ITEM_LEADING) {
351*1c60b9acSAndroid Build Coastguard Worker 
352*1c60b9acSAndroid Build Coastguard Worker 			/*
353*1c60b9acSAndroid Build Coastguard Worker 			 * If the item about to be added would match any cached
354*1c60b9acSAndroid Build Coastguard Worker 			 * results from before it was added, we have to
355*1c60b9acSAndroid Build Coastguard Worker 			 * invalidate them.  To check this, we have to use the
356*1c60b9acSAndroid Build Coastguard Worker 			 * matching rules at the backing store level
357*1c60b9acSAndroid Build Coastguard Worker 			 */
358*1c60b9acSAndroid Build Coastguard Worker 
359*1c60b9acSAndroid Build Coastguard Worker 			if (!strcmp(iname + 1, specific_key))
360*1c60b9acSAndroid Build Coastguard Worker 				_lws_cache_heap_item_destroy(cache, i);
361*1c60b9acSAndroid Build Coastguard Worker 		}
362*1c60b9acSAndroid Build Coastguard Worker 
363*1c60b9acSAndroid Build Coastguard Worker 	} lws_end_foreach_dll_safe(d, d1);
364*1c60b9acSAndroid Build Coastguard Worker 
365*1c60b9acSAndroid Build Coastguard Worker 
366*1c60b9acSAndroid Build Coastguard Worker 	/*
367*1c60b9acSAndroid Build Coastguard Worker 	 * Keep us under the limit if possible... note this will always allow
368*1c60b9acSAndroid Build Coastguard Worker 	 * caching a single large item even if it is above the limits
369*1c60b9acSAndroid Build Coastguard Worker 	 */
370*1c60b9acSAndroid Build Coastguard Worker 
371*1c60b9acSAndroid Build Coastguard Worker 	while ((cache->cache.info.max_footprint &&
372*1c60b9acSAndroid Build Coastguard Worker 	        cache->cache.current_footprint + size >
373*1c60b9acSAndroid Build Coastguard Worker 					     cache->cache.info.max_footprint) ||
374*1c60b9acSAndroid Build Coastguard Worker 	       (cache->cache.info.max_items &&
375*1c60b9acSAndroid Build Coastguard Worker 		cache->items_lru.count + 1 > cache->cache.info.max_items))
376*1c60b9acSAndroid Build Coastguard Worker 		lws_cache_item_evict_lru(cache);
377*1c60b9acSAndroid Build Coastguard Worker 
378*1c60b9acSAndroid Build Coastguard Worker 	/* remove any existing entry of the same key */
379*1c60b9acSAndroid Build Coastguard Worker 
380*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_heap_invalidate(&cache->cache, specific_key);
381*1c60b9acSAndroid Build Coastguard Worker 
382*1c60b9acSAndroid Build Coastguard Worker 	item = lws_fi(&_c->info.cx->fic, "cache_write_oom") ? NULL :
383*1c60b9acSAndroid Build Coastguard Worker 			lws_malloc(sizeof(*item) + kl + 1u + size, __func__);
384*1c60b9acSAndroid Build Coastguard Worker 	if (!item)
385*1c60b9acSAndroid Build Coastguard Worker 		return 1;
386*1c60b9acSAndroid Build Coastguard Worker 
387*1c60b9acSAndroid Build Coastguard Worker 	cache->cache.current_footprint += item->size;
388*1c60b9acSAndroid Build Coastguard Worker 
389*1c60b9acSAndroid Build Coastguard Worker 	/* only need to zero down our item object */
390*1c60b9acSAndroid Build Coastguard Worker 	memset(item, 0, sizeof(*item));
391*1c60b9acSAndroid Build Coastguard Worker 
392*1c60b9acSAndroid Build Coastguard Worker 	p = (char *)&item[1];
393*1c60b9acSAndroid Build Coastguard Worker 	if (ppvoid)
394*1c60b9acSAndroid Build Coastguard Worker 		*ppvoid = p;
395*1c60b9acSAndroid Build Coastguard Worker 
396*1c60b9acSAndroid Build Coastguard Worker 	/* copy the payload into place */
397*1c60b9acSAndroid Build Coastguard Worker 	if (source)
398*1c60b9acSAndroid Build Coastguard Worker 		memcpy(p, source, size);
399*1c60b9acSAndroid Build Coastguard Worker 
400*1c60b9acSAndroid Build Coastguard Worker 	/* copy the key string into place, with terminating NUL */
401*1c60b9acSAndroid Build Coastguard Worker 	memcpy(p + size, specific_key, kl + 1);
402*1c60b9acSAndroid Build Coastguard Worker 
403*1c60b9acSAndroid Build Coastguard Worker 	item->expiry = expiry;
404*1c60b9acSAndroid Build Coastguard Worker 	item->key_len = kl;
405*1c60b9acSAndroid Build Coastguard Worker 	item->size = size;
406*1c60b9acSAndroid Build Coastguard Worker 
407*1c60b9acSAndroid Build Coastguard Worker 	if (expiry) {
408*1c60b9acSAndroid Build Coastguard Worker 		/* adding to expiry is optional, on nonzero expiry */
409*1c60b9acSAndroid Build Coastguard Worker 		lws_dll2_add_sorted(&item->list_expiry, &cache->items_expiry,
410*1c60b9acSAndroid Build Coastguard Worker 				    sort_expiry);
411*1c60b9acSAndroid Build Coastguard Worker 		ei = lws_container_of(cache->items_expiry.head,
412*1c60b9acSAndroid Build Coastguard Worker 				      lws_cache_ttl_item_heap_t, list_expiry);
413*1c60b9acSAndroid Build Coastguard Worker 		lwsl_debug("%s: setting exp %llu\n", __func__,
414*1c60b9acSAndroid Build Coastguard Worker 						(unsigned long long)ei->expiry);
415*1c60b9acSAndroid Build Coastguard Worker 		lws_cache_schedule(&cache->cache, expiry_cb, ei->expiry);
416*1c60b9acSAndroid Build Coastguard Worker 	}
417*1c60b9acSAndroid Build Coastguard Worker 
418*1c60b9acSAndroid Build Coastguard Worker 	/* always add outselves to head of lru list */
419*1c60b9acSAndroid Build Coastguard Worker 	lws_dll2_add_head(&item->list_lru, &cache->items_lru);
420*1c60b9acSAndroid Build Coastguard Worker 
421*1c60b9acSAndroid Build Coastguard Worker 	return 0;
422*1c60b9acSAndroid Build Coastguard Worker }
423*1c60b9acSAndroid Build Coastguard Worker 
424*1c60b9acSAndroid Build Coastguard Worker static int
lws_cache_heap_get(struct lws_cache_ttl_lru * _c,const char * specific_key,const void ** pdata,size_t * psize)425*1c60b9acSAndroid Build Coastguard Worker lws_cache_heap_get(struct lws_cache_ttl_lru *_c, const char *specific_key,
426*1c60b9acSAndroid Build Coastguard Worker 		   const void **pdata, size_t *psize)
427*1c60b9acSAndroid Build Coastguard Worker {
428*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_lru_t_heap_t *cache = (lws_cache_ttl_lru_t_heap_t *)_c;
429*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_item_heap_t *item;
430*1c60b9acSAndroid Build Coastguard Worker 
431*1c60b9acSAndroid Build Coastguard Worker 	item = lws_cache_heap_specific(cache, specific_key);
432*1c60b9acSAndroid Build Coastguard Worker 	if (!item)
433*1c60b9acSAndroid Build Coastguard Worker 		return 1;
434*1c60b9acSAndroid Build Coastguard Worker 
435*1c60b9acSAndroid Build Coastguard Worker 	/* we are using it, move it to lru head */
436*1c60b9acSAndroid Build Coastguard Worker 	lws_dll2_remove(&item->list_lru);
437*1c60b9acSAndroid Build Coastguard Worker 	lws_dll2_add_head(&item->list_lru, &cache->items_lru);
438*1c60b9acSAndroid Build Coastguard Worker 
439*1c60b9acSAndroid Build Coastguard Worker 	if (pdata) {
440*1c60b9acSAndroid Build Coastguard Worker 		*pdata = (const void *)&item[1];
441*1c60b9acSAndroid Build Coastguard Worker 		*psize = item->size;
442*1c60b9acSAndroid Build Coastguard Worker 	}
443*1c60b9acSAndroid Build Coastguard Worker 
444*1c60b9acSAndroid Build Coastguard Worker 	return 0;
445*1c60b9acSAndroid Build Coastguard Worker }
446*1c60b9acSAndroid Build Coastguard Worker 
447*1c60b9acSAndroid Build Coastguard Worker static int
lws_cache_heap_invalidate(struct lws_cache_ttl_lru * _c,const char * specific_key)448*1c60b9acSAndroid Build Coastguard Worker lws_cache_heap_invalidate(struct lws_cache_ttl_lru *_c, const char *specific_key)
449*1c60b9acSAndroid Build Coastguard Worker {
450*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_lru_t_heap_t *cache = (lws_cache_ttl_lru_t_heap_t *)_c;
451*1c60b9acSAndroid Build Coastguard Worker 	struct lws_cache_ttl_lru *backing = _c;
452*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_item_heap_t *item;
453*1c60b9acSAndroid Build Coastguard Worker 	const void *user;
454*1c60b9acSAndroid Build Coastguard Worker 	size_t size;
455*1c60b9acSAndroid Build Coastguard Worker 
456*1c60b9acSAndroid Build Coastguard Worker 	if (lws_cache_heap_get(_c, specific_key, &user, &size))
457*1c60b9acSAndroid Build Coastguard Worker 		return 0;
458*1c60b9acSAndroid Build Coastguard Worker 
459*1c60b9acSAndroid Build Coastguard Worker 	if (backing->info.parent)
460*1c60b9acSAndroid Build Coastguard Worker 		backing = backing->info.parent;
461*1c60b9acSAndroid Build Coastguard Worker 
462*1c60b9acSAndroid Build Coastguard Worker 	item = (lws_cache_ttl_item_heap_t *)(((uint8_t *)user) - sizeof(*item));
463*1c60b9acSAndroid Build Coastguard Worker 
464*1c60b9acSAndroid Build Coastguard Worker 	/*
465*1c60b9acSAndroid Build Coastguard Worker 	 * We must invalidate any cached results that would have included this
466*1c60b9acSAndroid Build Coastguard Worker 	 */
467*1c60b9acSAndroid Build Coastguard Worker 
468*1c60b9acSAndroid Build Coastguard Worker 	lws_start_foreach_dll_safe(struct lws_dll2 *, d, d1,
469*1c60b9acSAndroid Build Coastguard Worker 				   cache->items_lru.head) {
470*1c60b9acSAndroid Build Coastguard Worker 		lws_cache_ttl_item_heap_t *i = lws_container_of(d,
471*1c60b9acSAndroid Build Coastguard Worker 						lws_cache_ttl_item_heap_t,
472*1c60b9acSAndroid Build Coastguard Worker 						list_lru);
473*1c60b9acSAndroid Build Coastguard Worker 		const char *iname = ((const char *)&i[1]) + i->size;
474*1c60b9acSAndroid Build Coastguard Worker 
475*1c60b9acSAndroid Build Coastguard Worker 		if (*iname == META_ITEM_LEADING) {
476*1c60b9acSAndroid Build Coastguard Worker 
477*1c60b9acSAndroid Build Coastguard Worker 			/*
478*1c60b9acSAndroid Build Coastguard Worker 			 * If the item about to be added would match any cached
479*1c60b9acSAndroid Build Coastguard Worker 			 * results from before it was added, we have to
480*1c60b9acSAndroid Build Coastguard Worker 			 * invalidate them.  To check this, we have to use the
481*1c60b9acSAndroid Build Coastguard Worker 			 * matching rules at the backing store level
482*1c60b9acSAndroid Build Coastguard Worker 			 */
483*1c60b9acSAndroid Build Coastguard Worker 
484*1c60b9acSAndroid Build Coastguard Worker 			if (!backing->info.ops->tag_match(backing, iname + 1,
485*1c60b9acSAndroid Build Coastguard Worker 							  specific_key, 1))
486*1c60b9acSAndroid Build Coastguard Worker 				_lws_cache_heap_item_destroy(cache, i);
487*1c60b9acSAndroid Build Coastguard Worker 		}
488*1c60b9acSAndroid Build Coastguard Worker 
489*1c60b9acSAndroid Build Coastguard Worker 	} lws_end_foreach_dll_safe(d, d1);
490*1c60b9acSAndroid Build Coastguard Worker 
491*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_heap_item_destroy(cache, item, 0);
492*1c60b9acSAndroid Build Coastguard Worker 
493*1c60b9acSAndroid Build Coastguard Worker 	return 0;
494*1c60b9acSAndroid Build Coastguard Worker }
495*1c60b9acSAndroid Build Coastguard Worker 
496*1c60b9acSAndroid Build Coastguard Worker static struct lws_cache_ttl_lru *
lws_cache_heap_create(const struct lws_cache_creation_info * info)497*1c60b9acSAndroid Build Coastguard Worker lws_cache_heap_create(const struct lws_cache_creation_info *info)
498*1c60b9acSAndroid Build Coastguard Worker {
499*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_lru_t_heap_t *cache;
500*1c60b9acSAndroid Build Coastguard Worker 
501*1c60b9acSAndroid Build Coastguard Worker 	assert(info->cx);
502*1c60b9acSAndroid Build Coastguard Worker 	assert(info->name);
503*1c60b9acSAndroid Build Coastguard Worker 
504*1c60b9acSAndroid Build Coastguard Worker 	cache = lws_fi(&info->cx->fic, "cache_createfail") ? NULL :
505*1c60b9acSAndroid Build Coastguard Worker 					lws_zalloc(sizeof(*cache), __func__);
506*1c60b9acSAndroid Build Coastguard Worker 	if (!cache)
507*1c60b9acSAndroid Build Coastguard Worker 		return NULL;
508*1c60b9acSAndroid Build Coastguard Worker 
509*1c60b9acSAndroid Build Coastguard Worker 	cache->cache.info = *info;
510*1c60b9acSAndroid Build Coastguard Worker 	if (info->parent)
511*1c60b9acSAndroid Build Coastguard Worker 		info->parent->child = &cache->cache;
512*1c60b9acSAndroid Build Coastguard Worker 
513*1c60b9acSAndroid Build Coastguard Worker 	// lwsl_cache("%s: create %s\n", __func__, info->name);
514*1c60b9acSAndroid Build Coastguard Worker 
515*1c60b9acSAndroid Build Coastguard Worker 	return (struct lws_cache_ttl_lru *)cache;
516*1c60b9acSAndroid Build Coastguard Worker }
517*1c60b9acSAndroid Build Coastguard Worker 
518*1c60b9acSAndroid Build Coastguard Worker static int
destroy_dll(struct lws_dll2 * d,void * user)519*1c60b9acSAndroid Build Coastguard Worker destroy_dll(struct lws_dll2 *d, void *user)
520*1c60b9acSAndroid Build Coastguard Worker {
521*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_lru_t *_c = (struct lws_cache_ttl_lru *)user;
522*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_lru_t_heap_t *cache = (lws_cache_ttl_lru_t_heap_t *)_c;
523*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_item_heap_t *item =
524*1c60b9acSAndroid Build Coastguard Worker 		       lws_container_of(d, lws_cache_ttl_item_heap_t, list_lru);
525*1c60b9acSAndroid Build Coastguard Worker 
526*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_heap_item_destroy(cache, item, 0);
527*1c60b9acSAndroid Build Coastguard Worker 
528*1c60b9acSAndroid Build Coastguard Worker 	return 0;
529*1c60b9acSAndroid Build Coastguard Worker }
530*1c60b9acSAndroid Build Coastguard Worker 
531*1c60b9acSAndroid Build Coastguard Worker static int
lws_cache_heap_expunge(struct lws_cache_ttl_lru * _c)532*1c60b9acSAndroid Build Coastguard Worker lws_cache_heap_expunge(struct lws_cache_ttl_lru *_c)
533*1c60b9acSAndroid Build Coastguard Worker {
534*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_lru_t_heap_t *cache = (lws_cache_ttl_lru_t_heap_t *)_c;
535*1c60b9acSAndroid Build Coastguard Worker 
536*1c60b9acSAndroid Build Coastguard Worker 	lws_dll2_foreach_safe(&cache->items_lru, cache, destroy_dll);
537*1c60b9acSAndroid Build Coastguard Worker 
538*1c60b9acSAndroid Build Coastguard Worker 	return 0;
539*1c60b9acSAndroid Build Coastguard Worker }
540*1c60b9acSAndroid Build Coastguard Worker 
541*1c60b9acSAndroid Build Coastguard Worker static void
lws_cache_heap_destroy(struct lws_cache_ttl_lru ** _cache)542*1c60b9acSAndroid Build Coastguard Worker lws_cache_heap_destroy(struct lws_cache_ttl_lru **_cache)
543*1c60b9acSAndroid Build Coastguard Worker {
544*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_lru_t *c = *_cache;
545*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_lru_t_heap_t *cache = (lws_cache_ttl_lru_t_heap_t *)c;
546*1c60b9acSAndroid Build Coastguard Worker 
547*1c60b9acSAndroid Build Coastguard Worker 	if (!cache)
548*1c60b9acSAndroid Build Coastguard Worker 		return;
549*1c60b9acSAndroid Build Coastguard Worker 
550*1c60b9acSAndroid Build Coastguard Worker 	lws_sul_cancel(&c->sul);
551*1c60b9acSAndroid Build Coastguard Worker 
552*1c60b9acSAndroid Build Coastguard Worker 	lws_dll2_foreach_safe(&cache->items_lru, cache, destroy_dll);
553*1c60b9acSAndroid Build Coastguard Worker 
554*1c60b9acSAndroid Build Coastguard Worker 	lws_free_set_NULL(*_cache);
555*1c60b9acSAndroid Build Coastguard Worker }
556*1c60b9acSAndroid Build Coastguard Worker 
557*1c60b9acSAndroid Build Coastguard Worker #if defined(_DEBUG)
558*1c60b9acSAndroid Build Coastguard Worker static int
dump_dll(struct lws_dll2 * d,void * user)559*1c60b9acSAndroid Build Coastguard Worker dump_dll(struct lws_dll2 *d, void *user)
560*1c60b9acSAndroid Build Coastguard Worker {
561*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_item_heap_t *item =
562*1c60b9acSAndroid Build Coastguard Worker 		       lws_container_of(d, lws_cache_ttl_item_heap_t, list_lru);
563*1c60b9acSAndroid Build Coastguard Worker 
564*1c60b9acSAndroid Build Coastguard Worker 	lwsl_cache("  %s: size %d, exp %llu\n",
565*1c60b9acSAndroid Build Coastguard Worker 		   (const char *)&item[1] + item->size,
566*1c60b9acSAndroid Build Coastguard Worker 		   (int)item->size, (unsigned long long)item->expiry);
567*1c60b9acSAndroid Build Coastguard Worker 
568*1c60b9acSAndroid Build Coastguard Worker 	lwsl_hexdump_cache((const char *)&item[1], item->size);
569*1c60b9acSAndroid Build Coastguard Worker 
570*1c60b9acSAndroid Build Coastguard Worker 	return 0;
571*1c60b9acSAndroid Build Coastguard Worker }
572*1c60b9acSAndroid Build Coastguard Worker 
573*1c60b9acSAndroid Build Coastguard Worker static void
lws_cache_heap_debug_dump(struct lws_cache_ttl_lru * _c)574*1c60b9acSAndroid Build Coastguard Worker lws_cache_heap_debug_dump(struct lws_cache_ttl_lru *_c)
575*1c60b9acSAndroid Build Coastguard Worker {
576*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_lru_t_heap_t *cache = (lws_cache_ttl_lru_t_heap_t *)_c;
577*1c60b9acSAndroid Build Coastguard Worker #if !defined(LWS_WITH_NO_LOGS)
578*1c60b9acSAndroid Build Coastguard Worker 	lws_cache_ttl_item_heap_t *item = NULL;
579*1c60b9acSAndroid Build Coastguard Worker 
580*1c60b9acSAndroid Build Coastguard Worker 	lws_dll2_t *d = cache->items_expiry.head;
581*1c60b9acSAndroid Build Coastguard Worker 
582*1c60b9acSAndroid Build Coastguard Worker 	if (d)
583*1c60b9acSAndroid Build Coastguard Worker 		item = lws_container_of(d, lws_cache_ttl_item_heap_t,
584*1c60b9acSAndroid Build Coastguard Worker 						list_expiry);
585*1c60b9acSAndroid Build Coastguard Worker 
586*1c60b9acSAndroid Build Coastguard Worker 	lwsl_cache("%s: %s: items %d, earliest %llu\n", __func__,
587*1c60b9acSAndroid Build Coastguard Worker 			cache->cache.info.name, (int)cache->items_lru.count,
588*1c60b9acSAndroid Build Coastguard Worker 			item ? (unsigned long long)item->expiry : 0ull);
589*1c60b9acSAndroid Build Coastguard Worker #endif
590*1c60b9acSAndroid Build Coastguard Worker 
591*1c60b9acSAndroid Build Coastguard Worker 	lws_dll2_foreach_safe(&cache->items_lru, cache, dump_dll);
592*1c60b9acSAndroid Build Coastguard Worker }
593*1c60b9acSAndroid Build Coastguard Worker #endif
594*1c60b9acSAndroid Build Coastguard Worker 
595*1c60b9acSAndroid Build Coastguard Worker const struct lws_cache_ops lws_cache_ops_heap = {
596*1c60b9acSAndroid Build Coastguard Worker 	.create			= lws_cache_heap_create,
597*1c60b9acSAndroid Build Coastguard Worker 	.destroy		= lws_cache_heap_destroy,
598*1c60b9acSAndroid Build Coastguard Worker 	.expunge		= lws_cache_heap_expunge,
599*1c60b9acSAndroid Build Coastguard Worker 
600*1c60b9acSAndroid Build Coastguard Worker 	.write			= lws_cache_heap_write,
601*1c60b9acSAndroid Build Coastguard Worker 	.tag_match		= lws_cache_heap_tag_match,
602*1c60b9acSAndroid Build Coastguard Worker 	.lookup			= lws_cache_heap_lookup,
603*1c60b9acSAndroid Build Coastguard Worker 	.invalidate		= lws_cache_heap_invalidate,
604*1c60b9acSAndroid Build Coastguard Worker 	.get			= lws_cache_heap_get,
605*1c60b9acSAndroid Build Coastguard Worker #if defined(_DEBUG)
606*1c60b9acSAndroid Build Coastguard Worker 	.debug_dump		= lws_cache_heap_debug_dump,
607*1c60b9acSAndroid Build Coastguard Worker #endif
608*1c60b9acSAndroid Build Coastguard Worker };
609