1 /* $NetBSD: ctable.c,v 1.2 2017/02/14 01:16:49 christos Exp $ */
2
3 /*++
4 /* NAME
5 /* ctable 3
6 /* SUMMARY
7 /* cache manager
8 /* SYNOPSIS
9 /* #include <ctable.h>
10 /*
11 /* CTABLE *ctable_create(limit, create, delete, context)
12 /* ssize_t limit;
13 /* void *(*create)(const char *key, void *context);
14 /* void (*delete)(void *value, void *context);
15 /* void *context;
16 /*
17 /* const void *ctable_locate(cache, key)
18 /* CTABLE *cache;
19 /* const char *key;
20 /*
21 /* const void *ctable_refresh(cache, key)
22 /* CTABLE *cache;
23 /* const char *key;
24 /*
25 /* const void *ctable_newcontext(cache, context)
26 /* CTABLE *cache;
27 /* void *context;
28 /*
29 /* void ctable_free(cache)
30 /* CTABLE *cache;
31 /*
32 /* void ctable_walk(cache, action)
33 /* CTABLE *cache;
34 /* void (*action)(const char *key, const void *value);
35 /* DESCRIPTION
36 /* This module maintains multiple caches. Cache items are purged
37 /* automatically when the number of items exceeds a configurable
38 /* limit. Caches never shrink. Each cache entry consists of a
39 /* string-valued lookup key and a generic data pointer value.
40 /*
41 /* ctable_create() creates a cache with the specified size limit, and
42 /* returns a pointer to the result. The create and delete arguments
43 /* specify pointers to call-back functions that create a value, given
44 /* a key, and delete a given value, respectively. The context argument
45 /* is passed on to the call-back routines.
46 /* The create() and delete() functions must not modify the cache.
47 /*
48 /* ctable_locate() looks up or generates the value that corresponds to
49 /* the specified key, and returns that value.
50 /*
51 /* ctable_refresh() flushes the value (if any) associated with
52 /* the specified key, and returns the same result as ctable_locate().
53 /*
54 /* ctable_newcontext() updates the context that is passed on
55 /* to call-back routines.
56 /*
57 /* ctable_free() destroys the specified cache, including its contents.
58 /*
59 /* ctable_walk() iterates over all elements in the cache, and invokes
60 /* the action function for each cache element with the corresponding
61 /* key and value as arguments. This function is useful mainly for
62 /* cache performance debugging.
63 /* Note: the action() function must not modify the cache.
64 /* DIAGNOSTICS
65 /* Fatal errors: out of memory. Panic: interface violation.
66 /* LICENSE
67 /* .ad
68 /* .fi
69 /* The Secure Mailer license must be distributed with this software.
70 /* AUTHOR(S)
71 /* Wietse Venema
72 /* IBM T.J. Watson Research
73 /* P.O. Box 704
74 /* Yorktown Heights, NY 10598, USA
75 /*--*/
76
77 /* System library. */
78
79 #include <sys_defs.h>
80 #include <stdlib.h>
81 #include <stddef.h>
82
83 /* Utility library. */
84
85 #include <msg.h>
86 #include <mymalloc.h>
87 #include <ring.h>
88 #include <htable.h>
89 #include <ctable.h>
90
91 /*
92 * Cache entries are kept in most-recently used order. We use a hash table
93 * to quickly locate cache entries.
94 */
95 #define CTABLE_ENTRY struct ctable_entry
96
97 struct ctable_entry {
98 RING ring; /* MRU linkage */
99 const char *key; /* lookup key */
100 void *value; /* corresponding value */
101 };
102
103 #define RING_TO_CTABLE_ENTRY(ring_ptr) \
104 RING_TO_APPL(ring_ptr, CTABLE_ENTRY, ring)
105 #define RING_PTR_OF(x) (&((x)->ring))
106
107 struct ctable {
108 HTABLE *table; /* table with key, ctable_entry pairs */
109 size_t limit; /* max nr of entries */
110 size_t used; /* current nr of entries */
111 CTABLE_CREATE_FN create; /* constructor */
112 CTABLE_DELETE_FN delete; /* destructor */
113 RING ring; /* MRU linkage */
114 void *context; /* application context */
115 };
116
117 #define CTABLE_MIN_SIZE 5
118
119 /* ctable_create - create empty cache */
120
ctable_create(ssize_t limit,CTABLE_CREATE_FN create,CTABLE_DELETE_FN delete,void * context)121 CTABLE *ctable_create(ssize_t limit, CTABLE_CREATE_FN create,
122 CTABLE_DELETE_FN delete, void *context)
123 {
124 CTABLE *cache = (CTABLE *) mymalloc(sizeof(CTABLE));
125 const char *myname = "ctable_create";
126
127 if (limit < 1)
128 msg_panic("%s: bad cache limit: %ld", myname, (long) limit);
129
130 cache->table = htable_create(limit);
131 cache->limit = (limit < CTABLE_MIN_SIZE ? CTABLE_MIN_SIZE : limit);
132 cache->used = 0;
133 cache->create = create;
134 cache->delete = delete;
135 ring_init(RING_PTR_OF(cache));
136 cache->context = context;
137 return (cache);
138 }
139
140 /* ctable_locate - look up or create cache item */
141
ctable_locate(CTABLE * cache,const char * key)142 const void *ctable_locate(CTABLE *cache, const char *key)
143 {
144 const char *myname = "ctable_locate";
145 CTABLE_ENTRY *entry;
146
147 /*
148 * If the entry is not in the cache, make sure there is room for a new
149 * entry and install it at the front of the MRU chain. Otherwise, move
150 * the entry to the front of the MRU chain if it is not already there.
151 * All this means that the cache never shrinks.
152 */
153 if ((entry = (CTABLE_ENTRY *) htable_find(cache->table, key)) == 0) {
154 if (cache->used >= cache->limit) {
155 entry = RING_TO_CTABLE_ENTRY(ring_pred(RING_PTR_OF(cache)));
156 if (msg_verbose)
157 msg_info("%s: purge entry key %s", myname, entry->key);
158 ring_detach(RING_PTR_OF(entry));
159 cache->delete(entry->value, cache->context);
160 htable_delete(cache->table, entry->key, (void (*) (void *)) 0);
161 } else {
162 entry = (CTABLE_ENTRY *) mymalloc(sizeof(CTABLE_ENTRY));
163 cache->used++;
164 }
165 entry->value = cache->create(key, cache->context);
166 entry->key = htable_enter(cache->table, key, (void *) entry)->key;
167 ring_append(RING_PTR_OF(cache), RING_PTR_OF(entry));
168 if (msg_verbose)
169 msg_info("%s: install entry key %s", myname, entry->key);
170 } else if (entry == RING_TO_CTABLE_ENTRY(ring_succ(RING_PTR_OF(cache)))) {
171 if (msg_verbose)
172 msg_info("%s: leave existing entry key %s", myname, entry->key);
173 } else {
174 ring_detach(RING_PTR_OF(entry));
175 ring_append(RING_PTR_OF(cache), RING_PTR_OF(entry));
176 if (msg_verbose)
177 msg_info("%s: move existing entry key %s", myname, entry->key);
178 }
179 return (entry->value);
180 }
181
182 /* ctable_refresh - page-in fresh data for given key */
183
ctable_refresh(CTABLE * cache,const char * key)184 const void *ctable_refresh(CTABLE *cache, const char *key)
185 {
186 const char *myname = "ctable_refresh";
187 CTABLE_ENTRY *entry;
188
189 /* Materialize entry if missing. */
190 if ((entry = (CTABLE_ENTRY *) htable_find(cache->table, key)) == 0)
191 return ctable_locate(cache, key);
192
193 /* Otherwise, refresh its content. */
194 cache->delete(entry->value, cache->context);
195 entry->value = cache->create(key, cache->context);
196
197 /* Update its MRU linkage. */
198 if (entry != RING_TO_CTABLE_ENTRY(ring_succ(RING_PTR_OF(cache)))) {
199 ring_detach(RING_PTR_OF(entry));
200 ring_append(RING_PTR_OF(cache), RING_PTR_OF(entry));
201 }
202 if (msg_verbose)
203 msg_info("%s: refresh entry key %s", myname, entry->key);
204 return (entry->value);
205 }
206
207 /* ctable_newcontext - update call-back context */
208
ctable_newcontext(CTABLE * cache,void * context)209 void ctable_newcontext(CTABLE *cache, void *context)
210 {
211 cache->context = context;
212 }
213
214 static CTABLE *ctable_free_cache;
215
216 /* ctable_free_callback - callback function */
217
ctable_free_callback(void * ptr)218 static void ctable_free_callback(void *ptr)
219 {
220 CTABLE_ENTRY *entry = (CTABLE_ENTRY *) ptr;
221
222 ctable_free_cache->delete(entry->value, ctable_free_cache->context);
223 myfree((void *) entry);
224 }
225
226 /* ctable_free - destroy cache and contents */
227
ctable_free(CTABLE * cache)228 void ctable_free(CTABLE *cache)
229 {
230 CTABLE *saved_cache = ctable_free_cache;
231
232 /*
233 * XXX the hash table does not pass application context so we have to
234 * store it in a global variable.
235 */
236 ctable_free_cache = cache;
237 htable_free(cache->table, ctable_free_callback);
238 myfree((void *) cache);
239 ctable_free_cache = saved_cache;
240 }
241
242 /* ctable_walk - iterate over all cache entries */
243
ctable_walk(CTABLE * cache,void (* action)(const char *,const void *))244 void ctable_walk(CTABLE *cache, void (*action) (const char *, const void *))
245 {
246 RING *entry = RING_PTR_OF(cache);
247
248 /* Walking down the MRU chain is less work than using ht_walk(). */
249
250 while ((entry = ring_succ(entry)) != RING_PTR_OF(cache))
251 action((RING_TO_CTABLE_ENTRY(entry)->key),
252 (RING_TO_CTABLE_ENTRY(entry)->value));
253 }
254
255 #ifdef TEST
256
257 /*
258 * Proof-of-concept test program. Read keys from stdin, ask for values not
259 * in cache.
260 */
261 #include <unistd.h>
262 #include <vstream.h>
263 #include <vstring.h>
264 #include <vstring_vstream.h>
265 #include <msg_vstream.h>
266
267 #define STR(x) vstring_str(x)
268
ask(const char * key,void * context)269 static void *ask(const char *key, void *context)
270 {
271 VSTRING *data_buf = (VSTRING *) context;
272
273 vstream_printf("ask: %s = ", key);
274 vstream_fflush(VSTREAM_OUT);
275 if (vstring_get_nonl(data_buf, VSTREAM_IN) == VSTREAM_EOF)
276 vstream_longjmp(VSTREAM_IN, 1);
277 if (!isatty(0)) {
278 vstream_printf("%s\n", STR(data_buf));
279 vstream_fflush(VSTREAM_OUT);
280 }
281 return (mystrdup(STR(data_buf)));
282 }
283
drop(void * data,void * unused_context)284 static void drop(void *data, void *unused_context)
285 {
286 myfree(data);
287 }
288
main(int unused_argc,char ** argv)289 int main(int unused_argc, char **argv)
290 {
291 VSTRING *key_buf;
292 VSTRING *data_buf;
293 CTABLE *cache;
294 const char *value;
295
296 msg_vstream_init(argv[0], VSTREAM_ERR);
297 key_buf = vstring_alloc(100);
298 data_buf = vstring_alloc(100);
299 cache = ctable_create(1, ask, drop, (void *) data_buf);
300 msg_verbose = 1;
301 vstream_control(VSTREAM_IN, CA_VSTREAM_CTL_EXCEPT, CA_VSTREAM_CTL_END);
302
303 if (vstream_setjmp(VSTREAM_IN) == 0) {
304 for (;;) {
305 vstream_printf("key = ");
306 vstream_fflush(VSTREAM_OUT);
307 if (vstring_get_nonl(key_buf, VSTREAM_IN) == VSTREAM_EOF)
308 vstream_longjmp(VSTREAM_IN, 1);
309 if (!isatty(0)) {
310 vstream_printf("%s\n", STR(key_buf));
311 vstream_fflush(VSTREAM_OUT);
312 }
313 value = ctable_locate(cache, STR(key_buf));
314 vstream_printf("result: %s\n", value);
315 }
316 }
317 ctable_free(cache);
318 vstring_free(key_buf);
319 vstring_free(data_buf);
320 return (0);
321 }
322
323 #endif
324