contrib/bind9/lib/dns/acache.c

   1 /*
   2  * Copyright (C) 2004-2008, 2012, 2013  Internet Systems Consortium, Inc. ("ISC")
   3  *
   4  * Permission to use, copy, modify, and/or distribute this software for any
   5  * purpose with or without fee is hereby granted, provided that the above
   6  * copyright notice and this permission notice appear in all copies.
   7  *
   8  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
   9  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  10  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  11  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  12  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  13  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  14  * PERFORMANCE OF THIS SOFTWARE.
  15  */
  16
  17 /* $Id: acache.c,v 1.22 2008/02/07 23:46:54 tbox Exp $ */
  18
  19 #include <config.h>
  20
  21 #include <isc/atomic.h>
  22 #include <isc/event.h>
  23 #include <isc/hash.h>
  24 #include <isc/magic.h>
  25 #include <isc/mem.h>
  26 #include <isc/mutex.h>
  27 #include <isc/random.h>
  28 #include <isc/refcount.h>
  29 #include <isc/rwlock.h>
  30 #include <isc/serial.h>
  31 #include <isc/task.h>
  32 #include <isc/time.h>
  33 #include <isc/timer.h>
  34
  35 #include <dns/acache.h>
  36 #include <dns/db.h>
  37 #include <dns/events.h>
  38 #include <dns/log.h>
  39 #include <dns/message.h>
  40 #include <dns/name.h>
  41 #include <dns/rdataset.h>
  42 #include <dns/result.h>
  43 #include <dns/zone.h>
  44
  45 #define ACACHE_MAGIC                    ISC_MAGIC('A', 'C', 'H', 'E')
  46 #define DNS_ACACHE_VALID(acache)        ISC_MAGIC_VALID(acache, ACACHE_MAGIC)
  47
  48 #define ACACHEENTRY_MAGIC               ISC_MAGIC('A', 'C', 'E', 'T')
  49 #define DNS_ACACHEENTRY_VALID(entry)    ISC_MAGIC_VALID(entry, ACACHEENTRY_MAGIC)
  50
  51 #define DBBUCKETS       67
  52
  53 #if 0
  54 #define ATRACE(m)       isc_log_write(dns_lctx, \
  55                                       DNS_LOGCATEGORY_DATABASE, \
  56                                       DNS_LOGMODULE_ACACHE, \
  57                                       ISC_LOG_DEBUG(3), \
  58                                       "acache %p: %s", acache, (m))
  59 #define AATRACE(a,m)    isc_log_write(dns_lctx, \
  60                                       DNS_LOGCATEGORY_DATABASE, \
  61                                       DNS_LOGMODULE_ACACHE, \
  62                                       ISC_LOG_DEBUG(3), \
  63                                       "acache %p: %s", (a), (m))
  64 #else
  65 #define ATRACE(m)
  66 #define AATRACE(a, m)
  67 #endif
  68
  69 /*
  70  * The following variables control incremental cleaning.
  71  * MINSIZE is how many bytes is the floor for dns_acache_setcachesize().
  72  * CLEANERINCREMENT is how many entries are examined in one pass.
  73  * (XXX simply derived from definitions in cache.c  There may be better
  74  *  constants here.)
  75  */
  76 #define DNS_ACACHE_MINSIZE              2097152U /* Bytes.  2097152 = 2 MB */
  77 #define DNS_ACACHE_CLEANERINCREMENT     1000     /* Number of entries. */
  78
  79 #define DEFAULT_ACACHE_ENTRY_LOCK_COUNT 1009     /*%< Should be prime. */
  80
  81 #if defined(ISC_RWLOCK_USEATOMIC) && defined(ISC_PLATFORM_HAVEATOMICSTORE)
  82 #define ACACHE_USE_RWLOCK 1
  83 #endif
  84
  85 #ifdef ACACHE_USE_RWLOCK
  86 #define ACACHE_INITLOCK(l)      isc_rwlock_init((l), 0, 0)
  87 #define ACACHE_DESTROYLOCK(l)   isc_rwlock_destroy(l)
  88 #define ACACHE_LOCK(l, t)       RWLOCK((l), (t))
  89 #define ACACHE_UNLOCK(l, t)     RWUNLOCK((l), (t))
  90
  91 #define acache_storetime(entry, t) \
  92         (isc_atomic_store((isc_int32_t *)&(entry)->lastused, (t)))
  93 #else
  94 #define ACACHE_INITLOCK(l)      isc_mutex_init(l)
  95 #define ACACHE_DESTROYLOCK(l)   DESTROYLOCK(l)
  96 #define ACACHE_LOCK(l, t)       LOCK(l)
  97 #define ACACHE_UNLOCK(l, t)     UNLOCK(l)
  98
  99 #define acache_storetime(entry, t) ((entry)->lastused = (t))
 100 #endif
 101
 102 /* Locked by acache lock */
 103 typedef struct dbentry {
 104         ISC_LINK(struct dbentry)        link;
 105
 106         dns_db_t                        *db;
 107         ISC_LIST(dns_acacheentry_t)     originlist;
 108         ISC_LIST(dns_acacheentry_t)     referlist;
 109 } dbentry_t;
 110
 111 typedef ISC_LIST(dbentry_t) dbentrylist_t;
 112
 113 typedef struct acache_cleaner acache_cleaner_t;
 114
 115 typedef enum {
 116         cleaner_s_idle, /* Waiting for cleaning-interval to expire. */
 117         cleaner_s_busy, /* Currently cleaning. */
 118         cleaner_s_done  /* Freed enough memory after being overmem. */
 119 } cleaner_state_t;
 120
 121 /*
 122  * Convenience macros for comprehensive assertion checking.
 123  */
 124 #define CLEANER_IDLE(c) ((c)->state == cleaner_s_idle && \
 125                          (c)->resched_event != NULL)
 126 #define CLEANER_BUSY(c) ((c)->state == cleaner_s_busy && \
 127                          (c)->resched_event == NULL)
 128
 129 struct acache_cleaner {
 130         isc_mutex_t             lock;
 131         /*
 132          * Locks overmem_event, overmem.  (See cache.c)
 133          */
 134
 135         dns_acache_t            *acache;
 136         unsigned int            cleaning_interval; /* The cleaning-interval
 137                                                       from named.conf,
 138                                                       in seconds. */
 139
 140         isc_stdtime_t           last_cleanup_time; /* The time when the last
 141                                                       cleanup task completed */
 142
 143         isc_timer_t             *cleaning_timer;
 144         isc_event_t             *resched_event; /* Sent by cleaner task to
 145                                                    itself to reschedule */
 146         isc_event_t             *overmem_event;
 147
 148         dns_acacheentry_t       *current_entry; /* The bookmark entry to
 149                                                    restart the cleaning.
 150                                                    Locked by acache lock. */
 151         int                     increment;      /* Number of entries to
 152                                                    clean in one increment */
 153
 154         unsigned long           ncleaned;       /* Number of entries cleaned
 155                                                    up (for logging purposes) */
 156         cleaner_state_t         state;          /* Idle/Busy/Done. */
 157         isc_boolean_t           overmem;        /* The acache is in an overmem
 158                                                    state. */
 159 };
 160
 161 struct dns_acachestats {
 162         unsigned int                    hits;
 163         unsigned int                    queries;
 164         unsigned int                    misses;
 165         unsigned int                    adds;
 166         unsigned int                    deleted;
 167         unsigned int                    cleaned;
 168         unsigned int                    cleaner_runs;
 169         unsigned int                    overmem;
 170         unsigned int                    overmem_nocreates;
 171         unsigned int                    nomem;
 172 };
 173
 174 /*
 175  * The actual acache object.
 176  */
 177
 178 struct dns_acache {
 179         unsigned int                    magic;
 180
 181         isc_mem_t                       *mctx;
 182         isc_refcount_t                  refs;
 183
 184 #ifdef ACACHE_USE_RWLOCK
 185         isc_rwlock_t                    *entrylocks;
 186 #else
 187         isc_mutex_t                     *entrylocks;
 188 #endif
 189
 190         isc_mutex_t                     lock;
 191
 192         int                             live_cleaners;
 193         acache_cleaner_t                cleaner;
 194         ISC_LIST(dns_acacheentry_t)     entries;
 195         unsigned int                    dbentries;
 196         dbentrylist_t                   dbbucket[DBBUCKETS];
 197
 198         isc_boolean_t                   shutting_down;
 199
 200         isc_task_t                      *task;
 201         isc_event_t                     cevent;
 202         isc_boolean_t                   cevent_sent;
 203
 204         dns_acachestats_t               stats;
 205 };
 206
 207 struct dns_acacheentry {
 208         unsigned int            magic;
 209
 210         unsigned int            locknum;
 211         isc_refcount_t          references;
 212
 213         dns_acache_t            *acache;
 214
 215         /* Data for Management of cache entries */
 216         ISC_LINK(dns_acacheentry_t) link;
 217         ISC_LINK(dns_acacheentry_t) olink;
 218         ISC_LINK(dns_acacheentry_t) rlink;
 219
 220         dns_db_t                *origdb; /* reference to the DB
 221                                             holding this entry */
 222
 223         /* Cache data */
 224         dns_zone_t              *zone;          /* zone this entry
 225                                                    belongs to */
 226         dns_db_t                *db;            /* DB this entry belongs to */
 227         dns_dbversion_t         *version;       /* the version of the DB */
 228         dns_dbnode_t            *node;          /* node this entry
 229                                                    belongs to */
 230         dns_name_t              *foundname;     /* corresponding DNS name
 231                                                    and rdataset */
 232
 233         /* Callback function and its argument */
 234         void                    (*callback)(dns_acacheentry_t *, void **);
 235         void                    *cbarg;
 236
 237         /* Timestamp of the last time this entry is referred to */
 238         isc_stdtime32_t         lastused;
 239 };
 240
 241 /*
 242  *      Internal functions (and prototypes).
 243  */
 244 static inline isc_boolean_t check_noentry(dns_acache_t *acache);
 245 static void destroy(dns_acache_t *acache);
 246 static void shutdown_entries(dns_acache_t *acache);
 247 static void shutdown_buckets(dns_acache_t *acache);
 248 static void destroy_entry(dns_acacheentry_t *ent);
 249 static inline void unlink_dbentries(dns_acache_t *acache,
 250                                     dns_acacheentry_t *ent);
 251 static inline isc_result_t finddbent(dns_acache_t *acache,
 252                                      dns_db_t *db, dbentry_t **dbentryp);
 253 static inline void clear_entry(dns_acache_t *acache, dns_acacheentry_t *entry);
 254 static isc_result_t acache_cleaner_init(dns_acache_t *acache,
 255                                         isc_timermgr_t *timermgr,
 256                                         acache_cleaner_t *cleaner);
 257 static void acache_cleaning_timer_action(isc_task_t *task, isc_event_t *event);
 258 static void acache_incremental_cleaning_action(isc_task_t *task,
 259                                                isc_event_t *event);
 260 static void acache_overmem_cleaning_action(isc_task_t *task,
 261                                            isc_event_t *event);
 262 static void acache_cleaner_shutdown_action(isc_task_t *task,
 263                                            isc_event_t *event);
 264
 265 /*
 266  * acache should be locked.  If it is not, the stats can get out of whack,
 267  * which is not a big deal for us since this is for debugging / stats
 268  */
 269 static void
 270 reset_stats(dns_acache_t *acache) {
 271         acache->stats.hits = 0;
 272         acache->stats.queries = 0;
 273         acache->stats.misses = 0;
 274         acache->stats.adds = 0;
 275         acache->stats.deleted = 0;
 276         acache->stats.cleaned = 0;
 277         acache->stats.overmem = 0;
 278         acache->stats.overmem_nocreates = 0;
 279         acache->stats.nomem = 0;
 280 }
 281
 282 /*
 283  * The acache must be locked before calling.
 284  */
 285 static inline isc_boolean_t
 286 check_noentry(dns_acache_t *acache) {
 287         if (ISC_LIST_EMPTY(acache->entries) && acache->dbentries == 0) {
 288                 return (ISC_TRUE);
 289         }
 290
 291         return (ISC_FALSE);
 292 }
 293
 294 /*
 295  * The acache must be locked before calling.
 296  */
 297 static void
 298 shutdown_entries(dns_acache_t *acache) {
 299         dns_acacheentry_t *entry, *entry_next;
 300
 301         REQUIRE(DNS_ACACHE_VALID(acache));
 302         INSIST(acache->shutting_down);
 303
 304         /*
 305          * Release the dependency of all entries, and detach them.
 306          */
 307         for (entry = ISC_LIST_HEAD(acache->entries);
 308              entry != NULL;
 309              entry = entry_next) {
 310                 entry_next = ISC_LIST_NEXT(entry, link);
 311
 312                 ACACHE_LOCK(&acache->entrylocks[entry->locknum],
 313                             isc_rwlocktype_write);
 314
 315                 /*
 316                  * If the cleaner holds this entry, it will be unlinked and
 317                  * freed in the cleaner later.
 318                  */
 319                 if (acache->cleaner.current_entry != entry)
 320                         ISC_LIST_UNLINK(acache->entries, entry, link);
 321                 unlink_dbentries(acache, entry);
 322                 if (entry->callback != NULL) {
 323                         (entry->callback)(entry, &entry->cbarg);
 324                         entry->callback = NULL;
 325                 }
 326
 327                 ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
 328                               isc_rwlocktype_write);
 329
 330                 if (acache->cleaner.current_entry != entry)
 331                         dns_acache_detachentry(&entry);
 332         }
 333 }
 334
 335 /*
 336  * The acache must be locked before calling.
 337  */
 338 static void
 339 shutdown_buckets(dns_acache_t *acache) {
 340         int i;
 341         dbentry_t *dbent;
 342
 343         REQUIRE(DNS_ACACHE_VALID(acache));
 344         INSIST(acache->shutting_down);
 345
 346         for (i = 0; i < DBBUCKETS; i++) {
 347                 while ((dbent = ISC_LIST_HEAD(acache->dbbucket[i])) != NULL) {
 348                         INSIST(ISC_LIST_EMPTY(dbent->originlist) &&
 349                                ISC_LIST_EMPTY(dbent->referlist));
 350                         ISC_LIST_UNLINK(acache->dbbucket[i], dbent, link);
 351
 352                         dns_db_detach(&dbent->db);
 353
 354                         isc_mem_put(acache->mctx, dbent, sizeof(*dbent));
 355
 356                         acache->dbentries--;
 357                 }
 358         }
 359
 360         INSIST(acache->dbentries == 0);
 361 }
 362
 363 static void
 364 shutdown_task(isc_task_t *task, isc_event_t *ev) {
 365         dns_acache_t *acache;
 366
 367         UNUSED(task);
 368
 369         acache = ev->ev_arg;
 370         INSIST(DNS_ACACHE_VALID(acache));
 371
 372         isc_event_free(&ev);
 373
 374         LOCK(&acache->lock);
 375
 376         shutdown_entries(acache);
 377         shutdown_buckets(acache);
 378
 379         UNLOCK(&acache->lock);
 380
 381         dns_acache_detach(&acache);
 382 }
 383
 384 /* The acache and the entry must be locked before calling. */
 385 static inline void
 386 unlink_dbentries(dns_acache_t *acache, dns_acacheentry_t *ent) {
 387         isc_result_t result;
 388         dbentry_t *dbent;
 389
 390         if (ISC_LINK_LINKED(ent, olink)) {
 391                 INSIST(ent->origdb != NULL);
 392                 dbent = NULL;
 393                 result = finddbent(acache, ent->origdb, &dbent);
 394                 INSIST(result == ISC_R_SUCCESS);
 395
 396                 ISC_LIST_UNLINK(dbent->originlist, ent, olink);
 397         }
 398         if (ISC_LINK_LINKED(ent, rlink)) {
 399                 INSIST(ent->db != NULL);
 400                 dbent = NULL;
 401                 result = finddbent(acache, ent->db, &dbent);
 402                 INSIST(result == ISC_R_SUCCESS);
 403
 404                 ISC_LIST_UNLINK(dbent->referlist, ent, rlink);
 405         }
 406 }
 407
 408 /* There must not be a reference to this entry. */
 409 static void
 410 destroy_entry(dns_acacheentry_t *entry) {
 411         dns_acache_t *acache;
 412
 413         REQUIRE(DNS_ACACHEENTRY_VALID(entry));
 414
 415         acache = entry->acache;
 416         REQUIRE(DNS_ACACHE_VALID(acache));
 417
 418         /*
 419          * Since there is no reference to this entry, it is safe to call
 420          * clear_entry() here.
 421          */
 422         clear_entry(acache, entry);
 423
 424         isc_mem_put(acache->mctx, entry, sizeof(*entry));
 425
 426         dns_acache_detach(&acache);
 427 }
 428
 429 static void
 430 destroy(dns_acache_t *acache) {
 431         int i;
 432
 433         REQUIRE(DNS_ACACHE_VALID(acache));
 434
 435         ATRACE("destroy");
 436
 437         isc_mem_setwater(acache->mctx, NULL, NULL, 0, 0);
 438
 439         if (acache->cleaner.overmem_event != NULL)
 440                 isc_event_free(&acache->cleaner.overmem_event);
 441
 442         if (acache->cleaner.resched_event != NULL)
 443                 isc_event_free(&acache->cleaner.resched_event);
 444
 445         if (acache->task != NULL)
 446                 isc_task_detach(&acache->task);
 447
 448         for (i = 0; i < DEFAULT_ACACHE_ENTRY_LOCK_COUNT; i++)
 449                 ACACHE_DESTROYLOCK(&acache->entrylocks[i]);
 450         isc_mem_put(acache->mctx, acache->entrylocks,
 451                     sizeof(*acache->entrylocks) *
 452                     DEFAULT_ACACHE_ENTRY_LOCK_COUNT);
 453
 454         DESTROYLOCK(&acache->cleaner.lock);
 455
 456         DESTROYLOCK(&acache->lock);
 457         acache->magic = 0;
 458
 459         isc_mem_putanddetach(&acache->mctx, acache, sizeof(*acache));
 460 }
 461
 462 static inline isc_result_t
 463 finddbent(dns_acache_t *acache, dns_db_t *db, dbentry_t **dbentryp) {
 464         int bucket;
 465         dbentry_t *dbentry;
 466
 467         REQUIRE(DNS_ACACHE_VALID(acache));
 468         REQUIRE(db != NULL);
 469         REQUIRE(dbentryp != NULL && *dbentryp == NULL);
 470
 471         /*
 472          * The caller must be holding the acache lock.
 473          */
 474
 475         bucket = isc_hash_calc((const unsigned char *)&db,
 476                                sizeof(db), ISC_TRUE) % DBBUCKETS;
 477
 478         for (dbentry = ISC_LIST_HEAD(acache->dbbucket[bucket]);
 479              dbentry != NULL;
 480              dbentry = ISC_LIST_NEXT(dbentry, link)) {
 481                 if (dbentry->db == db)
 482                         break;
 483         }
 484
 485         *dbentryp = dbentry;
 486
 487         if (dbentry == NULL)
 488                 return (ISC_R_NOTFOUND);
 489         else
 490                 return (ISC_R_SUCCESS);
 491 }
 492
 493 static inline void
 494 clear_entry(dns_acache_t *acache, dns_acacheentry_t *entry) {
 495         REQUIRE(DNS_ACACHE_VALID(acache));
 496         REQUIRE(DNS_ACACHEENTRY_VALID(entry));
 497
 498         /*
 499          * The caller must be holing the entry lock.
 500          */
 501
 502         if (entry->foundname) {
 503                 dns_rdataset_t *rdataset, *rdataset_next;
 504
 505                 for (rdataset = ISC_LIST_HEAD(entry->foundname->list);
 506                      rdataset != NULL;
 507                      rdataset = rdataset_next) {
 508                         rdataset_next = ISC_LIST_NEXT(rdataset, link);
 509                         ISC_LIST_UNLINK(entry->foundname->list,
 510                                         rdataset, link);
 511                         dns_rdataset_disassociate(rdataset);
 512                         isc_mem_put(acache->mctx, rdataset, sizeof(*rdataset));
 513                 }
 514                 if (dns_name_dynamic(entry->foundname))
 515                         dns_name_free(entry->foundname, acache->mctx);
 516                 isc_mem_put(acache->mctx, entry->foundname,
 517                             sizeof(*entry->foundname));
 518                 entry->foundname = NULL;
 519         }
 520
 521         if (entry->node != NULL) {
 522                 INSIST(entry->db != NULL);
 523                 dns_db_detachnode(entry->db, &entry->node);
 524         }
 525         if (entry->version != NULL) {
 526                 INSIST(entry->db != NULL);
 527                 dns_db_closeversion(entry->db, &entry->version, ISC_FALSE);
 528         }
 529         if (entry->db != NULL)
 530                 dns_db_detach(&entry->db);
 531         if (entry->zone != NULL)
 532                 dns_zone_detach(&entry->zone);
 533
 534         if (entry->origdb != NULL)
 535                 dns_db_detach(&entry->origdb);
 536 }
 537
 538 static isc_result_t
 539 acache_cleaner_init(dns_acache_t *acache, isc_timermgr_t *timermgr,
 540                     acache_cleaner_t *cleaner)
 541 {
 542         int result;
 543
 544         ATRACE("acache cleaner init");
 545
 546         result = isc_mutex_init(&cleaner->lock);
 547         if (result != ISC_R_SUCCESS)
 548                 goto fail;
 549
 550         cleaner->increment = DNS_ACACHE_CLEANERINCREMENT;
 551         cleaner->state = cleaner_s_idle;
 552         cleaner->acache = acache;
 553         cleaner->overmem = ISC_FALSE;
 554
 555         cleaner->cleaning_timer = NULL;
 556         cleaner->resched_event = NULL;
 557         cleaner->overmem_event = NULL;
 558         cleaner->current_entry = NULL;
 559
 560         if (timermgr != NULL) {
 561                 cleaner->acache->live_cleaners++;
 562
 563                 result = isc_task_onshutdown(acache->task,
 564                                              acache_cleaner_shutdown_action,
 565                                              acache);
 566                 if (result != ISC_R_SUCCESS) {
 567                         UNEXPECTED_ERROR(__FILE__, __LINE__,
 568                                          "acache cleaner: "
 569                                          "isc_task_onshutdown() failed: %s",
 570                                          dns_result_totext(result));
 571                         goto cleanup;
 572                 }
 573
 574                 cleaner->cleaning_interval = 0; /* Initially turned off. */
 575                 isc_stdtime_get(&cleaner->last_cleanup_time);
 576                 result = isc_timer_create(timermgr, isc_timertype_inactive,
 577                                           NULL, NULL,
 578                                           acache->task,
 579                                           acache_cleaning_timer_action,
 580                                           cleaner, &cleaner->cleaning_timer);
 581                 if (result != ISC_R_SUCCESS) {
 582                         UNEXPECTED_ERROR(__FILE__, __LINE__,
 583                                          "isc_timer_create() failed: %s",
 584                                          dns_result_totext(result));
 585                         result = ISC_R_UNEXPECTED;
 586                         goto cleanup;
 587                 }
 588
 589                 cleaner->resched_event =
 590                         isc_event_allocate(acache->mctx, cleaner,
 591                                            DNS_EVENT_ACACHECLEAN,
 592                                            acache_incremental_cleaning_action,
 593                                            cleaner, sizeof(isc_event_t));
 594                 if (cleaner->resched_event == NULL) {
 595                         result = ISC_R_NOMEMORY;
 596                         goto cleanup;
 597                 }
 598
 599                 cleaner->overmem_event =
 600                         isc_event_allocate(acache->mctx, cleaner,
 601                                            DNS_EVENT_ACACHEOVERMEM,
 602                                            acache_overmem_cleaning_action,
 603                                            cleaner, sizeof(isc_event_t));
 604                 if (cleaner->overmem_event == NULL) {
 605                         result = ISC_R_NOMEMORY;
 606                         goto cleanup;
 607                 }
 608         }
 609
 610         return (ISC_R_SUCCESS);
 611
 612  cleanup:
 613         if (cleaner->overmem_event != NULL)
 614                 isc_event_free(&cleaner->overmem_event);
 615         if (cleaner->resched_event != NULL)
 616                 isc_event_free(&cleaner->resched_event);
 617         if (cleaner->cleaning_timer != NULL)
 618                 isc_timer_detach(&cleaner->cleaning_timer);
 619         cleaner->acache->live_cleaners--;
 620         DESTROYLOCK(&cleaner->lock);
 621  fail:
 622         return (result);
 623 }
 624
 625 static void
 626 begin_cleaning(acache_cleaner_t *cleaner) {
 627         dns_acacheentry_t *head;
 628         dns_acache_t *acache = cleaner->acache;
 629
 630         /*
 631          * This function does not have to lock the cleaner, since critical
 632          * parameters (except current_entry, which is locked by acache lock,)
 633          * are only used in a single task context.
 634          */
 635
 636         REQUIRE(CLEANER_IDLE(cleaner));
 637         INSIST(DNS_ACACHE_VALID(acache));
 638         INSIST(cleaner->current_entry == NULL);
 639
 640         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
 641                       DNS_LOGMODULE_ACACHE, ISC_LOG_DEBUG(1),
 642                       "begin acache cleaning, mem inuse %lu",
 643                       (unsigned long)isc_mem_inuse(cleaner->acache->mctx));
 644
 645         LOCK(&acache->lock);
 646
 647         head = ISC_LIST_HEAD(acache->entries);
 648         if (head != NULL)
 649                 dns_acache_attachentry(head, &cleaner->current_entry);
 650
 651         UNLOCK(&acache->lock);
 652
 653         if (cleaner->current_entry != NULL) {
 654                 cleaner->ncleaned = 0;
 655                 cleaner->state = cleaner_s_busy;
 656                 isc_task_send(acache->task, &cleaner->resched_event);
 657         }
 658
 659         return;
 660 }
 661
 662 static void
 663 end_cleaning(acache_cleaner_t *cleaner, isc_event_t *event) {
 664         dns_acache_t *acache = cleaner->acache;
 665
 666         REQUIRE(CLEANER_BUSY(cleaner));
 667         REQUIRE(event != NULL);
 668         REQUIRE(DNS_ACACHEENTRY_VALID(cleaner->current_entry));
 669
 670         /* No need to lock the cleaner (see begin_cleaning()). */
 671
 672         LOCK(&acache->lock);
 673
 674         /*
 675          * Even if the cleaner has the last reference to the entry, which means
 676          * the entry has been unused, it may still be linked if unlinking the
 677          * entry has been delayed due to the reference.
 678          */
 679         if (isc_refcount_current(&cleaner->current_entry->references) == 1) {
 680                 INSIST(cleaner->current_entry->callback == NULL);
 681
 682                 if (ISC_LINK_LINKED(cleaner->current_entry, link)) {
 683                         ISC_LIST_UNLINK(acache->entries,
 684                                         cleaner->current_entry, link);
 685                 }
 686         }
 687         dns_acache_detachentry(&cleaner->current_entry);
 688
 689         if (cleaner->overmem)
 690                 acache->stats.overmem++;
 691         acache->stats.cleaned += cleaner->ncleaned;
 692         acache->stats.cleaner_runs++;
 693
 694         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE, DNS_LOGMODULE_ACACHE,
 695                       ISC_LOG_NOTICE,
 696                       "acache %p stats: hits=%d misses=%d queries=%d "
 697                       "adds=%d deleted=%d "
 698                       "cleaned=%d cleaner_runs=%d overmem=%d "
 699                       "overmem_nocreates=%d nomem=%d",
 700                       acache,
 701                       acache->stats.hits, acache->stats.misses,
 702                       acache->stats.queries,
 703                       acache->stats.adds, acache->stats.deleted,
 704                       acache->stats.cleaned, acache->stats.cleaner_runs,
 705                       acache->stats.overmem, acache->stats.overmem_nocreates,
 706                       acache->stats.nomem);
 707         reset_stats(acache);
 708
 709         isc_stdtime_get(&cleaner->last_cleanup_time);
 710
 711         UNLOCK(&acache->lock);
 712
 713         dns_acache_setcleaninginterval(cleaner->acache,
 714                                        cleaner->cleaning_interval);
 715
 716         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE, DNS_LOGMODULE_ACACHE,
 717                       ISC_LOG_DEBUG(1), "end acache cleaning, "
 718                       "%lu entries cleaned, mem inuse %lu",
 719                       cleaner->ncleaned,
 720                       (unsigned long)isc_mem_inuse(cleaner->acache->mctx));
 721
 722         if (cleaner->overmem) {
 723                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
 724                               DNS_LOGMODULE_ACACHE, ISC_LOG_NOTICE,
 725                               "acache is still in overmem state "
 726                               "after cleaning");
 727         }
 728
 729         cleaner->ncleaned = 0;
 730         cleaner->state = cleaner_s_idle;
 731         cleaner->resched_event = event;
 732 }
 733
 734 /*
 735  * This is run once for every acache-cleaning-interval as defined
 736  * in named.conf.
 737  */
 738 static void
 739 acache_cleaning_timer_action(isc_task_t *task, isc_event_t *event) {
 740         acache_cleaner_t *cleaner = event->ev_arg;
 741
 742         UNUSED(task);
 743
 744         INSIST(event->ev_type == ISC_TIMEREVENT_TICK);
 745
 746         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE, DNS_LOGMODULE_ACACHE,
 747                       ISC_LOG_DEBUG(1), "acache cleaning timer fired, "
 748                       "cleaner state = %d", cleaner->state);
 749
 750         if (cleaner->state == cleaner_s_idle)
 751                 begin_cleaning(cleaner);
 752
 753         isc_event_free(&event);
 754 }
 755
 756 /* The caller must hold entry lock. */
 757 static inline isc_boolean_t
 758 entry_stale(acache_cleaner_t *cleaner, dns_acacheentry_t *entry,
 759             isc_stdtime32_t now32, unsigned int interval)
 760 {
 761         /*
 762          * If the callback has been canceled, we definitely do not need the
 763          * entry.
 764          */
 765         if (entry->callback == NULL)
 766                 return (ISC_TRUE);
 767
 768         if (interval > cleaner->cleaning_interval)
 769                 interval = cleaner->cleaning_interval;
 770
 771         if (entry->lastused + interval < now32)
 772                 return (ISC_TRUE);
 773
 774         /*
 775          * If the acache is in the overmem state, probabilistically decide if
 776          * the entry should be purged, based on the time passed from its last
 777          * use and the cleaning interval.
 778          */
 779         if (cleaner->overmem) {
 780                 unsigned int passed;
 781                 isc_uint32_t val;
 782
 783                 if (isc_serial_ge(now32, entry->lastused))
 784                         passed = now32 - entry->lastused; /* <= interval */
 785                 else
 786                         passed = 0;
 787
 788                 if (passed > interval / 2)
 789                         return (ISC_TRUE);
 790                 isc_random_get(&val);
 791                 if (passed > interval / 4)
 792                         return (ISC_TF(val % 4 == 0));
 793                 return (ISC_TF(val % 8 == 0));
 794         }
 795
 796         return (ISC_FALSE);
 797 }
 798
 799 /*
 800  * Do incremental cleaning.
 801  */
 802 static void
 803 acache_incremental_cleaning_action(isc_task_t *task, isc_event_t *event) {
 804         acache_cleaner_t *cleaner = event->ev_arg;
 805         dns_acache_t *acache = cleaner->acache;
 806         dns_acacheentry_t *entry, *next = NULL;
 807         int n_entries;
 808         isc_stdtime32_t now32, last32;
 809         isc_stdtime_t now;
 810         unsigned int interval;
 811
 812         INSIST(DNS_ACACHE_VALID(acache));
 813         INSIST(task == acache->task);
 814         INSIST(event->ev_type == DNS_EVENT_ACACHECLEAN);
 815
 816         if (cleaner->state == cleaner_s_done) {
 817                 cleaner->state = cleaner_s_busy;
 818                 end_cleaning(cleaner, event);
 819                 return;
 820         }
 821
 822         INSIST(CLEANER_BUSY(cleaner));
 823
 824         n_entries = cleaner->increment;
 825
 826         isc_stdtime_get(&now);
 827         isc_stdtime_convert32(now, &now32);
 828
 829         LOCK(&acache->lock);
 830
 831         entry = cleaner->current_entry;
 832         isc_stdtime_convert32(cleaner->last_cleanup_time, &last32);
 833         if (isc_serial_ge(now32, last32))
 834                 interval = now32 - last32;
 835         else
 836                 interval = 0;
 837
 838         while (n_entries-- > 0) {
 839                 isc_boolean_t is_stale = ISC_FALSE;
 840
 841                 INSIST(entry != NULL);
 842
 843                 next = ISC_LIST_NEXT(entry, link);
 844
 845                 ACACHE_LOCK(&acache->entrylocks[entry->locknum],
 846                             isc_rwlocktype_write);
 847
 848                 is_stale = entry_stale(cleaner, entry, now32, interval);
 849                 if (is_stale) {
 850                         ISC_LIST_UNLINK(acache->entries, entry, link);
 851                         unlink_dbentries(acache, entry);
 852                         if (entry->callback != NULL)
 853                                 (entry->callback)(entry, &entry->cbarg);
 854                         entry->callback = NULL;
 855
 856                         cleaner->ncleaned++;
 857                 }
 858
 859                 ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
 860                               isc_rwlocktype_write);
 861
 862                 if (is_stale)
 863                         dns_acache_detachentry(&entry);
 864
 865                 if (next == NULL) {
 866                         if (cleaner->overmem) {
 867                                 entry = ISC_LIST_HEAD(acache->entries);
 868                                 if (entry != NULL) {
 869                                         /*
 870                                          * If we are still in the overmem
 871                                          * state, keep cleaning.  In case we
 872                                          * exit from the loop immediately after
 873                                          * this, reset next to the head entry
 874                                          * as we'll expect it will be never
 875                                          * NULL.
 876                                          */
 877                                         isc_log_write(dns_lctx,
 878                                                       DNS_LOGCATEGORY_DATABASE,
 879                                                       DNS_LOGMODULE_ACACHE,
 880                                                       ISC_LOG_DEBUG(1),
 881                                                       "acache cleaner: "
 882                                                       "still overmem, "
 883                                                       "reset and try again");
 884                                         next = entry;
 885                                         continue;
 886                                 }
 887                         }
 888
 889                         UNLOCK(&acache->lock);
 890                         end_cleaning(cleaner, event);
 891                         return;
 892                 }
 893
 894                 entry = next;
 895         }
 896
 897         /*
 898          * We have successfully performed a cleaning increment but have
 899          * not gone through the entire cache.  Remember the entry that will
 900          * be the starting point in the next clean-up, and reschedule another
 901          * batch.  If it fails, just try to continue anyway.
 902          */
 903         INSIST(next != NULL);
 904         dns_acache_detachentry(&cleaner->current_entry);
 905         dns_acache_attachentry(next, &cleaner->current_entry);
 906
 907         UNLOCK(&acache->lock);
 908
 909         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE, DNS_LOGMODULE_ACACHE,
 910                       ISC_LOG_DEBUG(1), "acache cleaner: checked %d entries, "
 911                       "mem inuse %lu, sleeping", cleaner->increment,
 912                       (unsigned long)isc_mem_inuse(cleaner->acache->mctx));
 913
 914         isc_task_send(task, &event);
 915         INSIST(CLEANER_BUSY(cleaner));
 916
 917         return;
 918 }
 919
 920 /*
 921  * This is called when the acache either surpasses its upper limit
 922  * or shrinks beyond its lower limit.
 923  */
 924 static void
 925 acache_overmem_cleaning_action(isc_task_t *task, isc_event_t *event) {
 926         acache_cleaner_t *cleaner = event->ev_arg;
 927         isc_boolean_t want_cleaning = ISC_FALSE;
 928
 929         UNUSED(task);
 930
 931         INSIST(event->ev_type == DNS_EVENT_ACACHEOVERMEM);
 932         INSIST(cleaner->overmem_event == NULL);
 933
 934         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE, DNS_LOGMODULE_ACACHE,
 935                       ISC_LOG_DEBUG(1), "overmem_cleaning_action called, "
 936                       "overmem = %d, state = %d", cleaner->overmem,
 937                       cleaner->state);
 938
 939         LOCK(&cleaner->lock);
 940
 941         if (cleaner->overmem) {
 942                 if (cleaner->state == cleaner_s_idle)
 943                         want_cleaning = ISC_TRUE;
 944         } else {
 945                 if (cleaner->state == cleaner_s_busy)
 946                         /*
 947                          * end_cleaning() can't be called here because
 948                          * then both cleaner->overmem_event and
 949                          * cleaner->resched_event will point to this
 950                          * event.  Set the state to done, and then
 951                          * when the acache_incremental_cleaning_action() event
 952                          * is posted, it will handle the end_cleaning.
 953                          */
 954                         cleaner->state = cleaner_s_done;
 955         }
 956
 957         cleaner->overmem_event = event;
 958
 959         UNLOCK(&cleaner->lock);
 960
 961         if (want_cleaning)
 962                 begin_cleaning(cleaner);
 963 }
 964
 965 static void
 966 water(void *arg, int mark) {
 967         dns_acache_t *acache = arg;
 968         isc_boolean_t overmem = ISC_TF(mark == ISC_MEM_HIWATER);
 969
 970         REQUIRE(DNS_ACACHE_VALID(acache));
 971
 972         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
 973                       DNS_LOGMODULE_ACACHE, ISC_LOG_DEBUG(1),
 974                       "acache memory reaches %s watermark, mem inuse %lu",
 975                       overmem ? "high" : "low",
 976                       (unsigned long)isc_mem_inuse(acache->mctx));
 977
 978         LOCK(&acache->cleaner.lock);
 979
 980         if (acache->cleaner.overmem != overmem) {
 981                 acache->cleaner.overmem = overmem;
 982
 983                 if (acache->cleaner.overmem_event != NULL)
 984                         isc_task_send(acache->task,
 985                                       &acache->cleaner.overmem_event);
 986                 isc_mem_waterack(acache->mctx, mark);
 987         }
 988
 989         UNLOCK(&acache->cleaner.lock);
 990 }
 991
 992 /*
 993  * The cleaner task is shutting down; do the necessary cleanup.
 994  */
 995 static void
 996 acache_cleaner_shutdown_action(isc_task_t *task, isc_event_t *event) {
 997         dns_acache_t *acache = event->ev_arg;
 998         isc_boolean_t should_free = ISC_FALSE;
 999
1000         INSIST(task == acache->task);
1001         INSIST(event->ev_type == ISC_TASKEVENT_SHUTDOWN);
1002         INSIST(DNS_ACACHE_VALID(acache));
1003
1004         ATRACE("acache cleaner shutdown");
1005
1006         if (CLEANER_BUSY(&acache->cleaner))
1007                 end_cleaning(&acache->cleaner, event);
1008         else
1009                 isc_event_free(&event);
1010
1011         LOCK(&acache->lock);
1012
1013         acache->live_cleaners--;
1014         INSIST(acache->live_cleaners == 0);
1015
1016         if (isc_refcount_current(&acache->refs) == 0) {
1017                 INSIST(check_noentry(acache) == ISC_TRUE);
1018                 should_free = ISC_TRUE;
1019         }
1020
1021         /*
1022          * By detaching the timer in the context of its task,
1023          * we are guaranteed that there will be no further timer
1024          * events.
1025          */
1026         if (acache->cleaner.cleaning_timer != NULL)
1027                 isc_timer_detach(&acache->cleaner.cleaning_timer);
1028
1029         /* Make sure we don't reschedule anymore. */
1030         (void)isc_task_purge(task, NULL, DNS_EVENT_ACACHECLEAN, NULL);
1031
1032         UNLOCK(&acache->lock);
1033
1034         if (should_free)
1035                 destroy(acache);
1036 }
1037
1038 /*
1039  *      Public functions.
1040  */
1041
1042 isc_result_t
1043 dns_acache_create(dns_acache_t **acachep, isc_mem_t *mctx,
1044                   isc_taskmgr_t *taskmgr, isc_timermgr_t *timermgr)
1045 {
1046         int i;
1047         isc_result_t result;
1048         dns_acache_t *acache;
1049
1050         REQUIRE(acachep != NULL && *acachep == NULL);
1051         REQUIRE(mctx != NULL);
1052         REQUIRE(taskmgr != NULL);
1053
1054         acache = isc_mem_get(mctx, sizeof(*acache));
1055         if (acache == NULL)
1056                 return (ISC_R_NOMEMORY);
1057
1058         ATRACE("create");
1059
1060         result = isc_refcount_init(&acache->refs, 1);
1061         if (result != ISC_R_SUCCESS) {
1062                 isc_mem_put(mctx, acache, sizeof(*acache));
1063                 return (result);
1064         }
1065
1066         result = isc_mutex_init(&acache->lock);
1067         if (result != ISC_R_SUCCESS) {
1068                 isc_refcount_decrement(&acache->refs, NULL);
1069                 isc_refcount_destroy(&acache->refs);
1070                 isc_mem_put(mctx, acache, sizeof(*acache));
1071                 return (result);
1072         }
1073
1074         acache->mctx = NULL;
1075         isc_mem_attach(mctx, &acache->mctx);
1076         ISC_LIST_INIT(acache->entries);
1077
1078         acache->shutting_down = ISC_FALSE;
1079
1080         acache->task = NULL;
1081         acache->entrylocks = NULL;
1082
1083         result = isc_task_create(taskmgr, 1, &acache->task);
1084         if (result != ISC_R_SUCCESS) {
1085                 UNEXPECTED_ERROR(__FILE__, __LINE__,
1086                                  "isc_task_create() failed(): %s",
1087                                  dns_result_totext(result));
1088                 result = ISC_R_UNEXPECTED;
1089                 goto cleanup;
1090         }
1091         isc_task_setname(acache->task, "acachetask", acache);
1092         ISC_EVENT_INIT(&acache->cevent, sizeof(acache->cevent), 0, NULL,
1093                        DNS_EVENT_ACACHECONTROL, shutdown_task, NULL,
1094                        NULL, NULL, NULL);
1095         acache->cevent_sent = ISC_FALSE;
1096
1097         acache->dbentries = 0;
1098         for (i = 0; i < DBBUCKETS; i++)
1099                 ISC_LIST_INIT(acache->dbbucket[i]);
1100
1101         acache->entrylocks = isc_mem_get(mctx, sizeof(*acache->entrylocks) *
1102                                          DEFAULT_ACACHE_ENTRY_LOCK_COUNT);
1103         if (acache->entrylocks == NULL) {
1104                 result = ISC_R_NOMEMORY;
1105                 goto cleanup;
1106         }
1107         for (i = 0; i < DEFAULT_ACACHE_ENTRY_LOCK_COUNT; i++) {
1108                 result = ACACHE_INITLOCK(&acache->entrylocks[i]);
1109                 if (result != ISC_R_SUCCESS) {
1110                         while (i-- > 0)
1111                                 ACACHE_DESTROYLOCK(&acache->entrylocks[i]);
1112                         isc_mem_put(mctx, acache->entrylocks,
1113                                     sizeof(*acache->entrylocks) *
1114                                     DEFAULT_ACACHE_ENTRY_LOCK_COUNT);
1115                         acache->entrylocks = NULL;
1116                         goto cleanup;
1117                 }
1118         }
1119
1120         acache->live_cleaners = 0;
1121         result = acache_cleaner_init(acache, timermgr, &acache->cleaner);
1122         if (result != ISC_R_SUCCESS)
1123                 goto cleanup;
1124
1125         acache->stats.cleaner_runs = 0;
1126         reset_stats(acache);
1127
1128         acache->magic = ACACHE_MAGIC;
1129
1130         *acachep = acache;
1131         return (ISC_R_SUCCESS);
1132
1133  cleanup:
1134         if (acache->task != NULL)
1135                 isc_task_detach(&acache->task);
1136         DESTROYLOCK(&acache->lock);
1137         isc_refcount_decrement(&acache->refs, NULL);
1138         isc_refcount_destroy(&acache->refs);
1139         if (acache->entrylocks != NULL) {
1140                 for (i = 0; i < DEFAULT_ACACHE_ENTRY_LOCK_COUNT; i++)
1141                         ACACHE_DESTROYLOCK(&acache->entrylocks[i]);
1142                 isc_mem_put(mctx, acache->entrylocks,
1143                             sizeof(*acache->entrylocks) *
1144                             DEFAULT_ACACHE_ENTRY_LOCK_COUNT);
1145         }
1146         isc_mem_put(mctx, acache, sizeof(*acache));
1147         isc_mem_detach(&mctx);
1148
1149         return (result);
1150 }
1151
1152 void
1153 dns_acache_attach(dns_acache_t *source, dns_acache_t **targetp) {
1154         REQUIRE(DNS_ACACHE_VALID(source));
1155         REQUIRE(targetp != NULL && *targetp == NULL);
1156
1157         AATRACE(source, "attach");
1158
1159         isc_refcount_increment(&source->refs, NULL);
1160
1161         *targetp = source;
1162 }
1163
1164 void
1165 dns_acache_countquerymiss(dns_acache_t *acache) {
1166         acache->stats.misses++;         /* XXXSK danger: unlocked! */
1167         acache->stats.queries++;        /* XXXSK danger: unlocked! */
1168 }
1169
1170 void
1171 dns_acache_detach(dns_acache_t **acachep) {
1172         dns_acache_t *acache;
1173         unsigned int refs;
1174         isc_boolean_t should_free = ISC_FALSE;
1175
1176         REQUIRE(acachep != NULL && DNS_ACACHE_VALID(*acachep));
1177         acache = *acachep;
1178
1179         ATRACE("detach");
1180
1181         isc_refcount_decrement(&acache->refs, &refs);
1182         if (refs == 0) {
1183                 INSIST(check_noentry(acache) == ISC_TRUE);
1184                 should_free = ISC_TRUE;
1185         }
1186
1187         *acachep = NULL;
1188
1189         /*
1190          * If we're exiting and the cleaner task exists, let it free the cache.
1191          */
1192         if (should_free && acache->live_cleaners > 0) {
1193                 isc_task_shutdown(acache->task);
1194                 should_free = ISC_FALSE;
1195         }
1196
1197         if (should_free)
1198                 destroy(acache);
1199 }
1200
1201 void
1202 dns_acache_shutdown(dns_acache_t *acache) {
1203         REQUIRE(DNS_ACACHE_VALID(acache));
1204
1205         LOCK(&acache->lock);
1206
1207         ATRACE("shutdown");
1208
1209         if (!acache->shutting_down) {
1210                 isc_event_t *event;
1211                 dns_acache_t *acache_evarg = NULL;
1212
1213                 INSIST(!acache->cevent_sent);
1214
1215                 acache->shutting_down = ISC_TRUE;
1216
1217                 isc_mem_setwater(acache->mctx, NULL, NULL, 0, 0);
1218
1219                 /*
1220                  * Self attach the object in order to prevent it from being
1221                  * destroyed while waiting for the event.
1222                  */
1223                 dns_acache_attach(acache, &acache_evarg);
1224                 event = &acache->cevent;
1225                 event->ev_arg = acache_evarg;
1226                 isc_task_send(acache->task, &event);
1227                 acache->cevent_sent = ISC_TRUE;
1228         }
1229
1230         UNLOCK(&acache->lock);
1231 }
1232
1233 isc_result_t
1234 dns_acache_setdb(dns_acache_t *acache, dns_db_t *db) {
1235         int bucket;
1236         dbentry_t *dbentry;
1237         isc_result_t result = ISC_R_SUCCESS;
1238
1239         REQUIRE(DNS_ACACHE_VALID(acache));
1240         REQUIRE(db != NULL);
1241
1242         ATRACE("setdb");
1243
1244         LOCK(&acache->lock);
1245
1246         dbentry = NULL;
1247         result = finddbent(acache, db, &dbentry);
1248         if (result == ISC_R_SUCCESS) {
1249                 result = ISC_R_EXISTS;
1250                 goto end;
1251         }
1252         result = ISC_R_SUCCESS;
1253
1254         dbentry = isc_mem_get(acache->mctx, sizeof(*dbentry));
1255         if (dbentry == NULL) {
1256                 result = ISC_R_NOMEMORY;
1257                 goto end;
1258         }
1259
1260         ISC_LINK_INIT(dbentry, link);
1261         ISC_LIST_INIT(dbentry->originlist);
1262         ISC_LIST_INIT(dbentry->referlist);
1263
1264         dbentry->db = NULL;
1265         dns_db_attach(db, &dbentry->db);
1266
1267         bucket = isc_hash_calc((const unsigned char *)&db,
1268                                sizeof(db), ISC_TRUE) % DBBUCKETS;
1269
1270         ISC_LIST_APPEND(acache->dbbucket[bucket], dbentry, link);
1271
1272         acache->dbentries++;
1273
1274  end:
1275         UNLOCK(&acache->lock);
1276
1277         return (result);
1278 }
1279
1280 isc_result_t
1281 dns_acache_putdb(dns_acache_t *acache, dns_db_t *db) {
1282         int bucket;
1283         isc_result_t result;
1284         dbentry_t *dbentry;
1285         dns_acacheentry_t *entry;
1286
1287         REQUIRE(DNS_ACACHE_VALID(acache));
1288         REQUIRE(db != NULL);
1289
1290         ATRACE("putdb");
1291
1292         LOCK(&acache->lock);
1293
1294         dbentry = NULL;
1295         result = finddbent(acache, db, &dbentry);
1296         if (result != ISC_R_SUCCESS) {
1297                 /*
1298                  * The entry may have not been created due to memory shortage.
1299                  */
1300                 UNLOCK(&acache->lock);
1301                 return (ISC_R_NOTFOUND);
1302         }
1303
1304         /*
1305          * Release corresponding cache entries: for each entry, release all
1306          * links the entry has, and then callback to the entry holder (if any).
1307          * If no other external references exist (this can happen if the
1308          * original holder has canceled callback,) destroy it here.
1309          */
1310         while ((entry = ISC_LIST_HEAD(dbentry->originlist)) != NULL) {
1311                 ACACHE_LOCK(&acache->entrylocks[entry->locknum],
1312                             isc_rwlocktype_write);
1313
1314                 /*
1315                  * Releasing olink first would avoid finddbent() in
1316                  * unlink_dbentries().
1317                  */
1318                 ISC_LIST_UNLINK(dbentry->originlist, entry, olink);
1319                 if (acache->cleaner.current_entry != entry)
1320                         ISC_LIST_UNLINK(acache->entries, entry, link);
1321                 unlink_dbentries(acache, entry);
1322
1323                 if (entry->callback != NULL)
1324                         (entry->callback)(entry, &entry->cbarg);
1325                 entry->callback = NULL;
1326
1327                 ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
1328                               isc_rwlocktype_write);
1329
1330                 if (acache->cleaner.current_entry != entry)
1331                         dns_acache_detachentry(&entry);
1332         }
1333         while ((entry = ISC_LIST_HEAD(dbentry->referlist)) != NULL) {
1334                 ACACHE_LOCK(&acache->entrylocks[entry->locknum],
1335                             isc_rwlocktype_write);
1336
1337                 ISC_LIST_UNLINK(dbentry->referlist, entry, rlink);
1338                 if (acache->cleaner.current_entry != entry)
1339                         ISC_LIST_UNLINK(acache->entries, entry, link);
1340                 unlink_dbentries(acache, entry);
1341
1342                 if (entry->callback != NULL)
1343                         (entry->callback)(entry, &entry->cbarg);
1344                 entry->callback = NULL;
1345
1346                 ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
1347                               isc_rwlocktype_write);
1348
1349                 if (acache->cleaner.current_entry != entry)
1350                         dns_acache_detachentry(&entry);
1351         }
1352
1353         INSIST(ISC_LIST_EMPTY(dbentry->originlist) &&
1354                ISC_LIST_EMPTY(dbentry->referlist));
1355
1356         bucket = isc_hash_calc((const unsigned char *)&db,
1357                                sizeof(db), ISC_TRUE) % DBBUCKETS;
1358         ISC_LIST_UNLINK(acache->dbbucket[bucket], dbentry, link);
1359         dns_db_detach(&dbentry->db);
1360
1361         isc_mem_put(acache->mctx, dbentry, sizeof(*dbentry));
1362
1363         acache->dbentries--;
1364
1365         acache->stats.deleted++;
1366
1367         UNLOCK(&acache->lock);
1368
1369         return (ISC_R_SUCCESS);
1370 }
1371
1372 isc_result_t
1373 dns_acache_createentry(dns_acache_t *acache, dns_db_t *origdb,
1374                        void (*callback)(dns_acacheentry_t *, void **),
1375                        void *cbarg, dns_acacheentry_t **entryp)
1376 {
1377         dns_acacheentry_t *newentry;
1378         isc_result_t result;
1379         isc_uint32_t r;
1380
1381         REQUIRE(DNS_ACACHE_VALID(acache));
1382         REQUIRE(entryp != NULL && *entryp == NULL);
1383         REQUIRE(origdb != NULL);
1384
1385         /*
1386          * Should we exceed our memory limit for some reason (for
1387          * example, if the cleaner does not run aggressively enough),
1388          * then we will not create additional entries.
1389          *
1390          * XXXSK: It might be better to lock the acache->cleaner->lock,
1391          * but locking may be an expensive bottleneck. If we misread
1392          * the value, we will occasionally refuse to create a few
1393          * cache entries, or create a few that we should not. I do not
1394          * expect this to happen often, and it will not have very bad
1395          * effects when it does. So no lock for now.
1396          */
1397         if (acache->cleaner.overmem) {
1398                 acache->stats.overmem_nocreates++; /* XXXSK danger: unlocked! */
1399                 return (ISC_R_NORESOURCES);
1400         }
1401
1402         newentry = isc_mem_get(acache->mctx, sizeof(*newentry));
1403         if (newentry == NULL) {
1404                 acache->stats.nomem++;  /* XXXMLG danger: unlocked! */
1405                 return (ISC_R_NOMEMORY);
1406         }
1407
1408         isc_random_get(&r);
1409         newentry->locknum = r % DEFAULT_ACACHE_ENTRY_LOCK_COUNT;
1410
1411         result = isc_refcount_init(&newentry->references, 1);
1412         if (result != ISC_R_SUCCESS) {
1413                 isc_mem_put(acache->mctx, newentry, sizeof(*newentry));
1414                 return (result);
1415         };
1416
1417         ISC_LINK_INIT(newentry, link);
1418         ISC_LINK_INIT(newentry, olink);
1419         ISC_LINK_INIT(newentry, rlink);
1420
1421         newentry->acache = NULL;
1422         dns_acache_attach(acache, &newentry->acache);
1423
1424         newentry->zone = NULL;
1425         newentry->db = NULL;
1426         newentry->version = NULL;
1427         newentry->node = NULL;
1428         newentry->foundname = NULL;
1429
1430         newentry->callback = callback;
1431         newentry->cbarg = cbarg;
1432         newentry->origdb = NULL;
1433         dns_db_attach(origdb, &newentry->origdb);
1434
1435         isc_stdtime_get(&newentry->lastused);
1436
1437         newentry->magic = ACACHEENTRY_MAGIC;
1438
1439         *entryp = newentry;
1440
1441         return (ISC_R_SUCCESS);
1442 }
1443
1444 isc_result_t
1445 dns_acache_getentry(dns_acacheentry_t *entry, dns_zone_t **zonep,
1446                     dns_db_t **dbp, dns_dbversion_t **versionp,
1447                     dns_dbnode_t **nodep, dns_name_t *fname,
1448                     dns_message_t *msg, isc_stdtime_t now)
1449 {
1450         isc_result_t result = ISC_R_SUCCESS;
1451         dns_rdataset_t *erdataset;
1452         isc_stdtime32_t now32;
1453         dns_acache_t *acache;
1454         int locknum;
1455
1456         REQUIRE(DNS_ACACHEENTRY_VALID(entry));
1457         REQUIRE(zonep == NULL || *zonep == NULL);
1458         REQUIRE(dbp != NULL && *dbp == NULL);
1459         REQUIRE(versionp != NULL && *versionp == NULL);
1460         REQUIRE(nodep != NULL && *nodep == NULL);
1461         REQUIRE(fname != NULL);
1462         REQUIRE(msg != NULL);
1463         acache = entry->acache;
1464         REQUIRE(DNS_ACACHE_VALID(acache));
1465
1466         locknum = entry->locknum;
1467         ACACHE_LOCK(&acache->entrylocks[locknum], isc_rwlocktype_read);
1468
1469         isc_stdtime_convert32(now, &now32);
1470         acache_storetime(entry, now32);
1471
1472         if (entry->zone != NULL && zonep != NULL)
1473                 dns_zone_attach(entry->zone, zonep);
1474
1475         if (entry->db == NULL) {
1476                 *dbp = NULL;
1477                 *versionp = NULL;
1478         } else {
1479                 dns_db_attach(entry->db, dbp);
1480                 dns_db_attachversion(entry->db, entry->version, versionp);
1481         }
1482         if (entry->node == NULL)
1483                 *nodep = NULL;
1484         else {
1485                 dns_db_attachnode(entry->db, entry->node, nodep);
1486
1487                 INSIST(entry->foundname != NULL);
1488                 dns_name_copy(entry->foundname, fname, NULL);
1489                 for (erdataset = ISC_LIST_HEAD(entry->foundname->list);
1490                      erdataset != NULL;
1491                      erdataset = ISC_LIST_NEXT(erdataset, link)) {
1492                         dns_rdataset_t *ardataset;
1493
1494                         ardataset = NULL;
1495                         result = dns_message_gettemprdataset(msg, &ardataset);
1496                         if (result != ISC_R_SUCCESS) {
1497                                 ACACHE_UNLOCK(&acache->entrylocks[locknum],
1498                                               isc_rwlocktype_read);
1499                                 goto fail;
1500                         }
1501
1502                         /*
1503                          * XXXJT: if we simply clone the rdataset, we'll get
1504                          * lost wrt cyclic ordering.  We'll need an additional
1505                          * trick to get the latest counter from the original
1506                          * header.
1507                          */
1508                         dns_rdataset_init(ardataset);
1509                         dns_rdataset_clone(erdataset, ardataset);
1510                         ISC_LIST_APPEND(fname->list, ardataset, link);
1511                 }
1512         }
1513
1514         entry->acache->stats.hits++; /* XXXMLG danger: unlocked! */
1515         entry->acache->stats.queries++;
1516
1517         ACACHE_UNLOCK(&acache->entrylocks[locknum], isc_rwlocktype_read);
1518
1519         return (result);
1520
1521   fail:
1522         while ((erdataset = ISC_LIST_HEAD(fname->list)) != NULL) {
1523                 ISC_LIST_UNLINK(fname->list, erdataset, link);
1524                 dns_rdataset_disassociate(erdataset);
1525                 dns_message_puttemprdataset(msg, &erdataset);
1526         }
1527         if (*nodep != NULL)
1528                 dns_db_detachnode(*dbp, nodep);
1529         if (*versionp != NULL)
1530                 dns_db_closeversion(*dbp, versionp, ISC_FALSE);
1531         if (*dbp != NULL)
1532                 dns_db_detach(dbp);
1533         if (zonep != NULL && *zonep != NULL)
1534                 dns_zone_detach(zonep);
1535
1536         return (result);
1537 }
1538
1539 isc_result_t
1540 dns_acache_setentry(dns_acache_t *acache, dns_acacheentry_t *entry,
1541                     dns_zone_t *zone, dns_db_t *db, dns_dbversion_t *version,
1542                     dns_dbnode_t *node, dns_name_t *fname)
1543 {
1544         isc_result_t result;
1545         dbentry_t *odbent;
1546         dbentry_t *rdbent = NULL;
1547         isc_boolean_t close_version = ISC_FALSE;
1548         dns_acacheentry_t *dummy_entry = NULL;
1549
1550         REQUIRE(DNS_ACACHE_VALID(acache));
1551         REQUIRE(DNS_ACACHEENTRY_VALID(entry));
1552
1553         LOCK(&acache->lock);    /* XXX: need to lock it here for ordering */
1554         ACACHE_LOCK(&acache->entrylocks[entry->locknum], isc_rwlocktype_write);
1555
1556         /* Set zone */
1557         if (zone != NULL)
1558                 dns_zone_attach(zone, &entry->zone);
1559         /* Set DB */
1560         if (db != NULL)
1561                 dns_db_attach(db, &entry->db);
1562         /*
1563          * Set DB version.  If the version is not given by the caller,
1564          * which is the case for glue or cache DBs, use the current version.
1565          */
1566         if (version == NULL) {
1567                 if (db != NULL) {
1568                         dns_db_currentversion(db, &version);
1569                         close_version = ISC_TRUE;
1570                 }
1571         }
1572         if (version != NULL) {
1573                 INSIST(db != NULL);
1574                 dns_db_attachversion(db, version, &entry->version);
1575         }
1576         if (close_version)
1577                 dns_db_closeversion(db, &version, ISC_FALSE);
1578         /* Set DB node. */
1579         if (node != NULL) {
1580                 INSIST(db != NULL);
1581                 dns_db_attachnode(db, node, &entry->node);
1582         }
1583
1584         /*
1585          * Set list of the corresponding rdatasets, if given.
1586          * To minimize the overhead and memory consumption, we'll do this for
1587          * positive cache only, in which case the DB node is non NULL.
1588          * We do not want to cache incomplete information, so give up the
1589          * entire entry when a memory shortage happen during the process.
1590          */
1591         if (node != NULL) {
1592                 dns_rdataset_t *ardataset, *crdataset;
1593
1594                 entry->foundname = isc_mem_get(acache->mctx,
1595                                                sizeof(*entry->foundname));
1596
1597                 if (entry->foundname == NULL) {
1598                         result = ISC_R_NOMEMORY;
1599                         goto fail;
1600                 }
1601                 dns_name_init(entry->foundname, NULL);
1602                 result = dns_name_dup(fname, acache->mctx,
1603                                       entry->foundname);
1604                 if (result != ISC_R_SUCCESS)
1605                         goto fail;
1606
1607                 for (ardataset = ISC_LIST_HEAD(fname->list);
1608                      ardataset != NULL;
1609                      ardataset = ISC_LIST_NEXT(ardataset, link)) {
1610                         crdataset = isc_mem_get(acache->mctx,
1611                                                 sizeof(*crdataset));
1612                         if (crdataset == NULL) {
1613                                 result = ISC_R_NOMEMORY;
1614                                 goto fail;
1615                         }
1616
1617                         dns_rdataset_init(crdataset);
1618                         dns_rdataset_clone(ardataset, crdataset);
1619                         ISC_LIST_APPEND(entry->foundname->list, crdataset,
1620                                         link);
1621                 }
1622         }
1623
1624         odbent = NULL;
1625         result = finddbent(acache, entry->origdb, &odbent);
1626         if (result != ISC_R_SUCCESS)
1627                 goto fail;
1628         if (db != NULL) {
1629                 rdbent = NULL;
1630                 result = finddbent(acache, db, &rdbent);
1631                 if (result != ISC_R_SUCCESS)
1632                         goto fail;
1633         }
1634
1635         ISC_LIST_APPEND(acache->entries, entry, link);
1636         ISC_LIST_APPEND(odbent->originlist, entry, olink);
1637         if (rdbent != NULL)
1638                 ISC_LIST_APPEND(rdbent->referlist, entry, rlink);
1639
1640         /*
1641          * The additional cache needs an implicit reference to entries in its
1642          * link.
1643          */
1644         dns_acache_attachentry(entry, &dummy_entry);
1645
1646         ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
1647                       isc_rwlocktype_write);
1648
1649         acache->stats.adds++;
1650         UNLOCK(&acache->lock);
1651
1652         return (ISC_R_SUCCESS);
1653
1654  fail:
1655         clear_entry(acache, entry);
1656
1657         ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
1658                       isc_rwlocktype_write);
1659         UNLOCK(&acache->lock);
1660
1661         return (result);
1662 }
1663
1664 isc_boolean_t
1665 dns_acache_cancelentry(dns_acacheentry_t *entry) {
1666         dns_acache_t *acache;
1667         isc_boolean_t callback_active;
1668
1669         REQUIRE(DNS_ACACHEENTRY_VALID(entry));
1670
1671         acache = entry->acache;
1672
1673         INSIST(DNS_ACACHE_VALID(entry->acache));
1674
1675         LOCK(&acache->lock);
1676         ACACHE_LOCK(&acache->entrylocks[entry->locknum], isc_rwlocktype_write);
1677
1678         callback_active = ISC_TF(entry->cbarg != NULL);
1679
1680         /*
1681          * Release dependencies stored in this entry as much as possible.
1682          * The main link cannot be released, since the acache object has
1683          * a reference to this entry; the empty entry will be released in
1684          * the next cleaning action.
1685          */
1686         unlink_dbentries(acache, entry);
1687         clear_entry(entry->acache, entry);
1688
1689         entry->callback = NULL;
1690         entry->cbarg = NULL;
1691
1692         ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
1693                       isc_rwlocktype_write);
1694         UNLOCK(&acache->lock);
1695
1696         return (callback_active);
1697 }
1698
1699 void
1700 dns_acache_attachentry(dns_acacheentry_t *source,
1701                        dns_acacheentry_t **targetp)
1702 {
1703         REQUIRE(DNS_ACACHEENTRY_VALID(source));
1704         REQUIRE(targetp != NULL && *targetp == NULL);
1705
1706         isc_refcount_increment(&source->references, NULL);
1707
1708         *targetp = source;
1709 }
1710
1711 void
1712 dns_acache_detachentry(dns_acacheentry_t **entryp) {
1713         dns_acacheentry_t *entry;
1714         unsigned int refs;
1715
1716         REQUIRE(entryp != NULL && DNS_ACACHEENTRY_VALID(*entryp));
1717         entry = *entryp;
1718
1719         isc_refcount_decrement(&entry->references, &refs);
1720
1721         /*
1722          * If there are no references to the entry, the entry must have been
1723          * unlinked and can be destroyed safely.
1724          */
1725         if (refs == 0) {
1726                 INSIST(!ISC_LINK_LINKED(entry, link));
1727                 (*entryp)->acache->stats.deleted++;
1728                 destroy_entry(entry);
1729         }
1730
1731         *entryp = NULL;
1732 }
1733
1734 void
1735 dns_acache_setcleaninginterval(dns_acache_t *acache, unsigned int t) {
1736         isc_interval_t interval;
1737         isc_result_t result;
1738
1739         REQUIRE(DNS_ACACHE_VALID(acache));
1740
1741         ATRACE("dns_acache_setcleaninginterval");
1742
1743         LOCK(&acache->lock);
1744
1745         /*
1746          * It may be the case that the acache has already shut down.
1747          * If so, it has no timer.  (Not sure if this can really happen.)
1748          */
1749         if (acache->cleaner.cleaning_timer == NULL)
1750                 goto unlock;
1751
1752         acache->cleaner.cleaning_interval = t;
1753
1754         if (t == 0) {
1755                 result = isc_timer_reset(acache->cleaner.cleaning_timer,
1756                                          isc_timertype_inactive,
1757                                          NULL, NULL, ISC_TRUE);
1758         } else {
1759                 isc_interval_set(&interval, acache->cleaner.cleaning_interval,
1760                                  0);
1761                 result = isc_timer_reset(acache->cleaner.cleaning_timer,
1762                                          isc_timertype_ticker,
1763                                          NULL, &interval, ISC_FALSE);
1764         }
1765         if (result != ISC_R_SUCCESS)
1766                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
1767                               DNS_LOGMODULE_ACACHE, ISC_LOG_WARNING,
1768                               "could not set acache cleaning interval: %s",
1769                               isc_result_totext(result));
1770         else
1771                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
1772                               DNS_LOGMODULE_ACACHE, ISC_LOG_NOTICE,
1773                               "acache %p cleaning interval set to %d.",
1774                               acache, t);
1775
1776  unlock:
1777         UNLOCK(&acache->lock);
1778 }
1779
1780 /*
1781  * This function was derived from cache.c:dns_cache_setcachesize().  See the
1782  * function for more details about the logic.
1783  */
1784 void
1785 dns_acache_setcachesize(dns_acache_t *acache, size_t size) {
1786         size_t hiwater, lowater;
1787
1788         REQUIRE(DNS_ACACHE_VALID(acache));
1789
1790         if (size != 0U && size < DNS_ACACHE_MINSIZE)
1791                 size = DNS_ACACHE_MINSIZE;
1792
1793         hiwater = size - (size >> 3);
1794         lowater = size - (size >> 2);
1795
1796         if (size == 0U || hiwater == 0U || lowater == 0U)
1797                 isc_mem_setwater(acache->mctx, water, acache, 0, 0);
1798         else
1799                 isc_mem_setwater(acache->mctx, water, acache,
1800                                  hiwater, lowater);
1801 }