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 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 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 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 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 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 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 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 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 284 static void drop(void *data, void *unused_context) 285 { 286 myfree(data); 287 } 288 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