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