1 /* $NetBSD: dict_cache.c,v 1.1.1.1 2010/06/17 18:07:12 tron Exp $ */ 2 3 /*++ 4 /* NAME 5 /* dict_cache 3 6 /* SUMMARY 7 /* External cache manager 8 /* SYNOPSIS 9 /* #include <dict_cache.h> 10 /* 11 /* DICT_CACHE *dict_cache_open(dbname, open_flags, dict_flags) 12 /* const char *dbname; 13 /* int open_flags; 14 /* int dict_flags; 15 /* 16 /* void dict_cache_close(cache) 17 /* DICT_CACHE *cache; 18 /* 19 /* const char *dict_cache_lookup(cache, cache_key) 20 /* DICT_CACHE *cache; 21 /* const char *cache_key; 22 /* 23 /* int dict_cache_update(cache, cache_key, cache_val) 24 /* DICT_CACHE *cache; 25 /* const char *cache_key; 26 /* const char *cache_val; 27 /* 28 /* int dict_cache_delete(cache, cache_key) 29 /* DICT_CACHE *cache; 30 /* const char *cache_key; 31 /* 32 /* int dict_cache_sequence(cache, first_next, cache_key, cache_val) 33 /* DICT_CACHE *cache; 34 /* int first_next; 35 /* const char **cache_key; 36 /* const char **cache_val; 37 /* AUXILIARY FUNCTIONS 38 /* void dict_cache_control(cache, name, value, ...) 39 /* DICT_CACHE *cache; 40 /* int name; 41 /* 42 /* typedef int (*DICT_CACHE_VALIDATOR_FN) (const char *cache_key, 43 /* const char *cache_val, char *context); 44 /* 45 /* const char *dict_cache_name(cache) 46 /* DICT_CACHE *cache; 47 /* DESCRIPTION 48 /* This module maintains external cache files with support 49 /* for expiration. The underlying table must implement the 50 /* "lookup", "update", "delete" and "sequence" operations. 51 /* 52 /* Although this API is similar to the one documented in 53 /* dict_open(3), there are subtle differences in the interaction 54 /* between the iterators that access all cache elements, and 55 /* other operations that access individual cache elements. 56 /* 57 /* In particular, when a "sequence" or "cleanup" operation is 58 /* in progress the cache intercepts requests to delete the 59 /* "current" entry, as this would cause some databases to 60 /* mis-behave. Instead, the cache implements a "delete behind" 61 /* strategy, and deletes such an entry after the "sequence" 62 /* or "cleanup" operation moves on to the next cache element. 63 /* The "delete behind" strategy also affects the cache lookup 64 /* and update operations as detailed below. 65 /* 66 /* dict_cache_open() is a wrapper around the dict_open() 67 /* function. It opens the specified cache and returns a handle 68 /* that must be used for subsequent access. This function does 69 /* not return in case of error. 70 /* 71 /* dict_cache_close() closes the specified cache and releases 72 /* memory that was allocated by dict_cache_open(), and terminates 73 /* any thread that was started with dict_cache_control(). 74 /* 75 /* dict_cache_lookup() looks up the specified cache entry. 76 /* The result value is a null pointer when the cache entry was 77 /* not found, or when the entry is scheduled for "delete 78 /* behind". 79 /* 80 /* dict_cache_update() updates the specified cache entry. If 81 /* the entry is scheduled for "delete behind", the delete 82 /* operation is canceled (because of this, the cache must be 83 /* opened with DICT_FLAG_DUP_REPLACE). This function does not 84 /* return in case of error. 85 /* 86 /* dict_cache_delete() removes the specified cache entry. If 87 /* this is the "current" entry of a "sequence" operation, the 88 /* entry is scheduled for "delete behind". The result value 89 /* is zero when the entry was found. 90 /* 91 /* dict_cache_sequence() iterates over the specified cache and 92 /* returns each entry in an implementation-defined order. The 93 /* result value is zero when a cache entry was found. 94 /* 95 /* Important: programs must not use both dict_cache_sequence() 96 /* and the built-in cache cleanup feature. 97 /* 98 /* dict_cache_control() provides control over the built-in 99 /* cache cleanup feature and logging. The arguments are a list 100 /* of (name, value) pairs, terminated with DICT_CACHE_CTL_END. 101 /* The following lists the names and the types of the corresponding 102 /* value arguments. 103 /* .IP "DICT_CACHE_FLAGS (int flags)" 104 /* The arguments to this command are the bit-wise OR of zero 105 /* or more of the following: 106 /* .RS 107 /* .IP DICT_CACHE_FLAG_VERBOSE 108 /* Enable verbose logging of cache activity. 109 /* .IP DICT_CACHE_FLAG_EXP_SUMMARY 110 /* Log cache statistics after each cache cleanup run. 111 /* .RE 112 /* .IP "DICT_CACHE_CTL_INTERVAL (int interval)" 113 /* The interval between cache cleanup runs. Specify a null 114 /* validator or interval to stop cache cleanup. 115 /* .IP "DICT_CACHE_CTL_VALIDATOR (DICT_CACHE_VALIDATOR_FN validator)" 116 /* An application call-back routine that returns non-zero when 117 /* a cache entry should be kept. The call-back function should 118 /* not make changes to the cache. Specify a null validator or 119 /* interval to stop cache cleanup. 120 /* .IP "DICT_CACHE_CTL_CONTEXT (char *context)" 121 /* Application context that is passed to the validator function. 122 /* .RE 123 /* .PP 124 /* dict_cache_name() returns the name of the specified cache. 125 /* 126 /* Arguments: 127 /* .IP "dbname, open_flags, dict_flags" 128 /* These are passed unchanged to dict_open(). The cache must 129 /* be opened with DICT_FLAG_DUP_REPLACE. 130 /* .IP cache 131 /* Cache handle created with dict_cache_open(). 132 /* .IP cache_key 133 /* Cache lookup key. 134 /* .IP cache_val 135 /* Information that is stored under a cache lookup key. 136 /* .IP first_next 137 /* One of DICT_SEQ_FUN_FIRST (first cache element) or 138 /* DICT_SEQ_FUN_NEXT (next cache element). 139 /* .sp 140 /* Note: there is no "stop" request. To ensure that the "delete 141 /* behind" strategy does not interfere with database access, 142 /* allow dict_cache_sequence() to run to completion. 143 /* .IP table 144 /* A bare dictonary handle. 145 /* DIAGNOSTICS 146 /* These routines terminate with a fatal run-time error 147 /* for unrecoverable database errors. This allows the 148 /* program to restart and reset the database to an 149 /* empty initial state. 150 /* BUGS 151 /* There should be a way to suspend automatic program suicide 152 /* until a cache cleanup run is completed. Some entries may 153 /* never be removed when the process max_idle time is less 154 /* than the time needed to make a full pass over the cache. 155 /* LICENSE 156 /* .ad 157 /* .fi 158 /* The Secure Mailer license must be distributed with this software. 159 /* HISTORY 160 /* .ad 161 /* .fi 162 /* A predecessor of this code was written first for the Postfix 163 /* tlsmgr(8) daemon. 164 /* AUTHOR(S) 165 /* Wietse Venema 166 /* IBM T.J. Watson Research 167 /* P.O. Box 704 168 /* Yorktown Heights, NY 10598, USA 169 /*--*/ 170 171 /* System library. */ 172 173 #include <sys_defs.h> 174 #include <string.h> 175 #include <stdlib.h> 176 177 /* Utility library. */ 178 179 #include <msg.h> 180 #include <dict.h> 181 #include <mymalloc.h> 182 #include <events.h> 183 #include <dict_cache.h> 184 185 /* Application-specific. */ 186 187 /* 188 * XXX Deleting entries while enumerating a map can he tricky. Some map 189 * types have a concept of cursor and support a "delete the current element" 190 * operation. Some map types without cursors don't behave well when the 191 * current first/next entry is deleted (example: with Berkeley DB < 2, the 192 * "next" operation produces garbage). To avoid trouble, we delete an entry 193 * after advancing the current first/next position beyond it; we use the 194 * same strategy with application requests to delete the current entry. 195 */ 196 197 /* 198 * Opaque data structure. Use dict_cache_name() to access the name of the 199 * underlying database. 200 */ 201 struct DICT_CACHE { 202 int cache_flags; /* see below */ 203 int user_flags; /* logging */ 204 DICT *db; /* database handle */ 205 206 /* Delete-behind support. */ 207 char *saved_curr_key; /* "current" cache lookup key */ 208 char *saved_curr_val; /* "current" cache lookup result */ 209 210 /* Cleanup support. */ 211 int exp_interval; /* time between cleanup runs */ 212 DICT_CACHE_VALIDATOR_FN exp_validator; /* expiration call-back */ 213 char *exp_context; /* call-back context */ 214 int retained; /* entries retained in cleanup run */ 215 int dropped; /* entries removed in cleanup run */ 216 }; 217 218 #define DC_FLAG_DEL_SAVED_CURRENT_KEY (1<<0) /* delete-behind is scheduled */ 219 220 /* 221 * Macros to make obscure code more readable. 222 */ 223 #define DC_SCHEDULE_FOR_DELETE_BEHIND(cp) \ 224 ((cp)->cache_flags |= DC_FLAG_DEL_SAVED_CURRENT_KEY) 225 226 #define DC_MATCH_SAVED_CURRENT_KEY(cp, cache_key) \ 227 ((cp)->saved_curr_key && strcmp((cp)->saved_curr_key, (cache_key)) == 0) 228 229 #define DC_IS_SCHEDULED_FOR_DELETE_BEHIND(cp) \ 230 (/* NOT: (cp)->saved_curr_key && */ \ 231 ((cp)->cache_flags & DC_FLAG_DEL_SAVED_CURRENT_KEY) != 0) 232 233 #define DC_CANCEL_DELETE_BEHIND(cp) \ 234 ((cp)->cache_flags &= ~DC_FLAG_DEL_SAVED_CURRENT_KEY) 235 236 /* 237 * Special key to store the time of the last cache cleanup run completion. 238 */ 239 #define DC_LAST_CACHE_CLEANUP_COMPLETED "_LAST_CACHE_CLEANUP_COMPLETED_" 240 241 /* dict_cache_lookup - load entry from cache */ 242 243 const char *dict_cache_lookup(DICT_CACHE *cp, const char *cache_key) 244 { 245 const char *myname = "dict_cache_lookup"; 246 const char *cache_val; 247 248 /* 249 * Search for the cache entry. Don't return an entry that is scheduled 250 * for delete-behind. 251 */ 252 if (DC_IS_SCHEDULED_FOR_DELETE_BEHIND(cp) 253 && DC_MATCH_SAVED_CURRENT_KEY(cp, cache_key)) { 254 if (cp->user_flags & DICT_CACHE_FLAG_VERBOSE) 255 msg_info("%s: key=%s (pretend not found - scheduled for deletion)", 256 myname, cache_key); 257 return (0); 258 } else { 259 cache_val = dict_get(cp->db, cache_key); 260 if (cp->user_flags & DICT_CACHE_FLAG_VERBOSE) 261 msg_info("%s: key=%s value=%s", myname, cache_key, 262 cache_val ? cache_val : "(not found)"); 263 return (cache_val); 264 } 265 } 266 267 /* dict_cache_update - save entry to cache */ 268 269 void dict_cache_update(DICT_CACHE *cp, const char *cache_key, 270 const char *cache_val) 271 { 272 const char *myname = "dict_cache_update"; 273 274 /* 275 * Store the cache entry and cancel the delete-behind operation. 276 */ 277 if (DC_IS_SCHEDULED_FOR_DELETE_BEHIND(cp) 278 && DC_MATCH_SAVED_CURRENT_KEY(cp, cache_key)) { 279 if (cp->user_flags & DICT_CACHE_FLAG_VERBOSE) 280 msg_info("%s: cancel delete-behind for key=%s", myname, cache_key); 281 DC_CANCEL_DELETE_BEHIND(cp); 282 } 283 if (cp->user_flags & DICT_CACHE_FLAG_VERBOSE) 284 msg_info("%s: key=%s value=%s", myname, cache_key, cache_val); 285 dict_put(cp->db, cache_key, cache_val); 286 } 287 288 /* dict_cache_delete - delete entry from cache */ 289 290 int dict_cache_delete(DICT_CACHE *cp, const char *cache_key) 291 { 292 const char *myname = "dict_cache_delete"; 293 int zero_means_found; 294 295 /* 296 * Delete the entry, unless we would delete the current first/next entry. 297 * In that case, schedule the "current" entry for delete-behind to avoid 298 * mis-behavior by some databases. 299 */ 300 if (DC_MATCH_SAVED_CURRENT_KEY(cp, cache_key)) { 301 DC_SCHEDULE_FOR_DELETE_BEHIND(cp); 302 if (cp->user_flags & DICT_CACHE_FLAG_VERBOSE) 303 msg_info("%s: key=%s (current entry - schedule for delete-behind)", 304 myname, cache_key); 305 zero_means_found = 0; 306 } else { 307 zero_means_found = dict_del(cp->db, cache_key); 308 if (cp->user_flags & DICT_CACHE_FLAG_VERBOSE) 309 msg_info("%s: key=%s (%s)", myname, cache_key, 310 zero_means_found == 0 ? "found" : "not found"); 311 } 312 return (zero_means_found); 313 } 314 315 /* dict_cache_sequence - look up the first/next cache entry */ 316 317 int dict_cache_sequence(DICT_CACHE *cp, int first_next, 318 const char **cache_key, 319 const char **cache_val) 320 { 321 const char *myname = "dict_cache_sequence"; 322 int zero_means_found; 323 const char *raw_cache_key; 324 const char *raw_cache_val; 325 char *previous_curr_key; 326 char *previous_curr_val; 327 328 /* 329 * Find the first or next database entry. Hide the record with the cache 330 * cleanup completion time stamp. 331 */ 332 zero_means_found = 333 dict_seq(cp->db, first_next, &raw_cache_key, &raw_cache_val); 334 if (zero_means_found == 0 335 && strcmp(raw_cache_key, DC_LAST_CACHE_CLEANUP_COMPLETED) == 0) 336 zero_means_found = 337 dict_seq(cp->db, DICT_SEQ_FUN_NEXT, &raw_cache_key, &raw_cache_val); 338 if (cp->user_flags & DICT_CACHE_FLAG_VERBOSE) 339 msg_info("%s: key=%s value=%s", myname, 340 zero_means_found == 0 ? raw_cache_key : "(not found)", 341 zero_means_found == 0 ? raw_cache_val : "(not found)"); 342 343 /* 344 * Save the current cache_key and cache_val before they are clobbered by 345 * our own delete operation below. This also prevents surprises when the 346 * application accesses the database after this function returns. 347 * 348 * We also use the saved cache_key to protect the current entry against 349 * application delete requests. 350 */ 351 previous_curr_key = cp->saved_curr_key; 352 previous_curr_val = cp->saved_curr_val; 353 if (zero_means_found == 0) { 354 cp->saved_curr_key = mystrdup(raw_cache_key); 355 cp->saved_curr_val = mystrdup(raw_cache_val); 356 } else { 357 cp->saved_curr_key = 0; 358 cp->saved_curr_val = 0; 359 } 360 361 /* 362 * Delete behind. 363 */ 364 if (DC_IS_SCHEDULED_FOR_DELETE_BEHIND(cp)) { 365 DC_CANCEL_DELETE_BEHIND(cp); 366 if (cp->user_flags & DICT_CACHE_FLAG_VERBOSE) 367 msg_info("%s: delete-behind key=%s value=%s", 368 myname, previous_curr_key, previous_curr_val); 369 if (dict_del(cp->db, previous_curr_key) != 0) 370 msg_warn("database %s: could not delete entry for %s", 371 cp->db->name, previous_curr_key); 372 } 373 374 /* 375 * Clean up previous iteration key and value. 376 */ 377 if (previous_curr_key) 378 myfree(previous_curr_key); 379 if (previous_curr_val) 380 myfree(previous_curr_val); 381 382 /* 383 * Return the result. 384 */ 385 *cache_key = (cp)->saved_curr_key; 386 *cache_val = (cp)->saved_curr_val; 387 return (zero_means_found); 388 } 389 390 /* dict_cache_delete_behind_reset - reset "delete behind" state */ 391 392 static void dict_cache_delete_behind_reset(DICT_CACHE *cp) 393 { 394 #define FREE_AND_WIPE(s) do { if (s) { myfree(s); (s) = 0; } } while (0) 395 396 DC_CANCEL_DELETE_BEHIND(cp); 397 FREE_AND_WIPE(cp->saved_curr_key); 398 FREE_AND_WIPE(cp->saved_curr_val); 399 } 400 401 /* dict_cache_clean_stat_log_reset - log and reset cache cleanup statistics */ 402 403 static void dict_cache_clean_stat_log_reset(DICT_CACHE *cp, 404 const char *full_partial) 405 { 406 if (cp->user_flags & DICT_CACHE_FLAG_STATISTICS) 407 msg_info("cache %s %s cleanup: retained=%d dropped=%d entries", 408 cp->db->name, full_partial, cp->retained, cp->dropped); 409 cp->retained = cp->dropped = 0; 410 } 411 412 /* dict_cache_clean_event - examine one cache entry */ 413 414 static void dict_cache_clean_event(int unused_event, char *cache_context) 415 { 416 const char *myname = "dict_cache_clean_event"; 417 DICT_CACHE *cp = (DICT_CACHE *) cache_context; 418 const char *cache_key; 419 const char *cache_val; 420 int next_interval; 421 VSTRING *stamp_buf; 422 int first_next; 423 424 /* 425 * We interleave cache cleanup with other processing, so that the 426 * application's service remains available, with perhaps increased 427 * latency. 428 */ 429 430 /* 431 * Start a new cache cleanup run. 432 */ 433 if (cp->saved_curr_key == 0) { 434 cp->retained = cp->dropped = 0; 435 first_next = DICT_SEQ_FUN_FIRST; 436 if (cp->user_flags & DICT_CACHE_FLAG_VERBOSE) 437 msg_info("%s: start %s cache cleanup", myname, cp->db->name); 438 } 439 440 /* 441 * Continue a cache cleanup run in progress. 442 */ 443 else { 444 first_next = DICT_SEQ_FUN_NEXT; 445 } 446 447 /* 448 * Examine one cache entry. 449 */ 450 if (dict_cache_sequence(cp, first_next, &cache_key, &cache_val) == 0) { 451 if (cp->exp_validator(cache_key, cache_val, cp->exp_context) == 0) { 452 DC_SCHEDULE_FOR_DELETE_BEHIND(cp); 453 cp->dropped++; 454 if (cp->user_flags & DICT_CACHE_FLAG_VERBOSE) 455 msg_info("%s: drop %s cache entry for %s", 456 myname, cp->db->name, cache_key); 457 } else { 458 cp->retained++; 459 if (cp->user_flags & DICT_CACHE_FLAG_VERBOSE) 460 msg_info("%s: keep %s cache entry for %s", 461 myname, cp->db->name, cache_key); 462 } 463 next_interval = 0; 464 } 465 466 /* 467 * Cache cleanup completed. Report vital statistics. 468 */ 469 else { 470 if (cp->user_flags & DICT_CACHE_FLAG_VERBOSE) 471 msg_info("%s: done %s cache cleanup scan", myname, cp->db->name); 472 dict_cache_clean_stat_log_reset(cp, "full"); 473 stamp_buf = vstring_alloc(100); 474 vstring_sprintf(stamp_buf, "%ld", (long) event_time()); 475 dict_put(cp->db, DC_LAST_CACHE_CLEANUP_COMPLETED, 476 vstring_str(stamp_buf)); 477 vstring_free(stamp_buf); 478 next_interval = cp->exp_interval; 479 } 480 event_request_timer(dict_cache_clean_event, cache_context, next_interval); 481 } 482 483 /* dict_cache_control - schedule or stop the cache cleanup thread */ 484 485 void dict_cache_control(DICT_CACHE *cp,...) 486 { 487 const char *myname = "dict_cache_control"; 488 const char *last_done; 489 time_t next_interval; 490 int cache_cleanup_is_active = (cp->exp_validator && cp->exp_interval); 491 va_list ap; 492 int name; 493 494 /* 495 * Update the control settings. 496 */ 497 va_start(ap, cp); 498 while ((name = va_arg(ap, int)) > 0) { 499 switch (name) { 500 case DICT_CACHE_CTL_END: 501 break; 502 case DICT_CACHE_CTL_FLAGS: 503 cp->user_flags = va_arg(ap, int); 504 break; 505 case DICT_CACHE_CTL_INTERVAL: 506 cp->exp_interval = va_arg(ap, int); 507 if (cp->exp_interval < 0) 508 msg_panic("%s: bad %s cache cleanup interval %d", 509 myname, cp->db->name, cp->exp_interval); 510 break; 511 case DICT_CACHE_CTL_VALIDATOR: 512 cp->exp_validator = va_arg(ap, DICT_CACHE_VALIDATOR_FN); 513 break; 514 case DICT_CACHE_CTL_CONTEXT: 515 cp->exp_context = va_arg(ap, char *); 516 break; 517 default: 518 msg_panic("%s: bad command: %d", myname, name); 519 } 520 } 521 va_end(ap); 522 523 /* 524 * Schedule the cache cleanup thread. 525 */ 526 if (cp->exp_interval && cp->exp_validator) { 527 528 /* 529 * Sanity checks. 530 */ 531 if (cache_cleanup_is_active) 532 msg_panic("%s: %s cache cleanup is already scheduled", 533 myname, cp->db->name); 534 535 /* 536 * The next start time depends on the last completion time. 537 */ 538 #define NEXT_START(last, delta) ((delta) + (unsigned long) atol(last)) 539 #define NOW (time((time_t *) 0)) /* NOT: event_time() */ 540 541 if ((last_done = dict_get(cp->db, DC_LAST_CACHE_CLEANUP_COMPLETED)) == 0 542 || (next_interval = (NEXT_START(last_done, cp->exp_interval) - NOW)) < 0) 543 next_interval = 0; 544 if (next_interval > cp->exp_interval) 545 next_interval = cp->exp_interval; 546 if ((cp->user_flags & DICT_CACHE_FLAG_VERBOSE) && next_interval > 0) 547 msg_info("%s cache cleanup will start after %ds", 548 cp->db->name, (int) next_interval); 549 event_request_timer(dict_cache_clean_event, (char *) cp, 550 (int) next_interval); 551 } 552 553 /* 554 * Cancel the cache cleanup thread. 555 */ 556 else if (cache_cleanup_is_active) { 557 if (cp->retained || cp->dropped) 558 dict_cache_clean_stat_log_reset(cp, "partial"); 559 dict_cache_delete_behind_reset(cp); 560 event_cancel_timer(dict_cache_clean_event, (char *) cp); 561 } 562 } 563 564 /* dict_cache_open - open cache file */ 565 566 DICT_CACHE *dict_cache_open(const char *dbname, int open_flags, int dict_flags) 567 { 568 DICT_CACHE *cp; 569 DICT *dict; 570 571 /* 572 * Open the database as requested. Don't attempt to second-guess the 573 * application. 574 */ 575 dict = dict_open(dbname, open_flags, dict_flags); 576 577 /* 578 * Create the DICT_CACHE object. 579 */ 580 cp = (DICT_CACHE *) mymalloc(sizeof(*cp)); 581 cp->cache_flags = 0; 582 cp->user_flags = 0; 583 cp->db = dict; 584 cp->saved_curr_key = 0; 585 cp->saved_curr_val = 0; 586 cp->exp_interval = 0; 587 cp->exp_validator = 0; 588 cp->exp_context = 0; 589 cp->retained = 0; 590 cp->dropped = 0; 591 592 return (cp); 593 } 594 595 /* dict_cache_close - close cache file */ 596 597 void dict_cache_close(DICT_CACHE *cp) 598 { 599 600 /* 601 * Destroy the DICT_CACHE object. 602 */ 603 dict_cache_control(cp, DICT_CACHE_CTL_INTERVAL, 0, DICT_CACHE_CTL_END); 604 dict_close(cp->db); 605 if (cp->saved_curr_key) 606 myfree(cp->saved_curr_key); 607 if (cp->saved_curr_val) 608 myfree(cp->saved_curr_val); 609 myfree((char *) cp); 610 } 611 612 /* dict_cache_name - get the cache name */ 613 614 const char *dict_cache_name(DICT_CACHE *cp) 615 { 616 617 /* 618 * This is used for verbose logging or warning messages, so the cost of 619 * call is only made where needed (well sort off - code that does not 620 * execute still presents overhead for the processor pipeline, processor 621 * cache, etc). 622 */ 623 return (cp->db->name); 624 } 625