contrib/bind9/lib/dns/acache.c

   1 /*
   2  * Copyright (C) 2004-2008, 2012, 2013, 2015  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_function(&db, sizeof(db), ISC_TRUE, NULL) % DBBUCKETS;
 476
 477         for (dbentry = ISC_LIST_HEAD(acache->dbbucket[bucket]);
 478              dbentry != NULL;
 479              dbentry = ISC_LIST_NEXT(dbentry, link)) {
 480                 if (dbentry->db == db)
 481                         break;
 482         }
 483
 484         *dbentryp = dbentry;
 485
 486         if (dbentry == NULL)
 487                 return (ISC_R_NOTFOUND);
 488         else
 489                 return (ISC_R_SUCCESS);
 490 }
 491
 492 static inline void
 493 clear_entry(dns_acache_t *acache, dns_acacheentry_t *entry) {
 494         REQUIRE(DNS_ACACHE_VALID(acache));
 495         REQUIRE(DNS_ACACHEENTRY_VALID(entry));
 496
 497         /*
 498          * The caller must be holing the entry lock.
 499          */
 500
 501         if (entry->foundname) {
 502                 dns_rdataset_t *rdataset, *rdataset_next;
 503
 504                 for (rdataset = ISC_LIST_HEAD(entry->foundname->list);
 505                      rdataset != NULL;
 506                      rdataset = rdataset_next) {
 507                         rdataset_next = ISC_LIST_NEXT(rdataset, link);
 508                         ISC_LIST_UNLINK(entry->foundname->list,
 509                                         rdataset, link);
 510                         dns_rdataset_disassociate(rdataset);
 511                         isc_mem_put(acache->mctx, rdataset, sizeof(*rdataset));
 512                 }
 513                 if (dns_name_dynamic(entry->foundname))
 514                         dns_name_free(entry->foundname, acache->mctx);
 515                 isc_mem_put(acache->mctx, entry->foundname,
 516                             sizeof(*entry->foundname));
 517                 entry->foundname = NULL;
 518         }
 519
 520         if (entry->node != NULL) {
 521                 INSIST(entry->db != NULL);
 522                 dns_db_detachnode(entry->db, &entry->node);
 523         }
 524         if (entry->version != NULL) {
 525                 INSIST(entry->db != NULL);
 526                 dns_db_closeversion(entry->db, &entry->version, ISC_FALSE);
 527         }
 528         if (entry->db != NULL)
 529                 dns_db_detach(&entry->db);
 530         if (entry->zone != NULL)
 531                 dns_zone_detach(&entry->zone);
 532
 533         if (entry->origdb != NULL)
 534                 dns_db_detach(&entry->origdb);
 535 }
 536
 537 static isc_result_t
 538 acache_cleaner_init(dns_acache_t *acache, isc_timermgr_t *timermgr,
 539                     acache_cleaner_t *cleaner)
 540 {
 541         int result;
 542
 543         ATRACE("acache cleaner init");
 544
 545         result = isc_mutex_init(&cleaner->lock);
 546         if (result != ISC_R_SUCCESS)
 547                 goto fail;
 548
 549         cleaner->increment = DNS_ACACHE_CLEANERINCREMENT;
 550         cleaner->state = cleaner_s_idle;
 551         cleaner->acache = acache;
 552         cleaner->overmem = ISC_FALSE;
 553
 554         cleaner->cleaning_timer = NULL;
 555         cleaner->resched_event = NULL;
 556         cleaner->overmem_event = NULL;
 557         cleaner->current_entry = NULL;
 558
 559         if (timermgr != NULL) {
 560                 cleaner->acache->live_cleaners++;
 561
 562                 result = isc_task_onshutdown(acache->task,
 563                                              acache_cleaner_shutdown_action,
 564                                              acache);
 565                 if (result != ISC_R_SUCCESS) {
 566                         UNEXPECTED_ERROR(__FILE__, __LINE__,
 567                                          "acache cleaner: "
 568                                          "isc_task_onshutdown() failed: %s",
 569                                          dns_result_totext(result));
 570                         goto cleanup;
 571                 }
 572
 573                 cleaner->cleaning_interval = 0; /* Initially turned off. */
 574                 isc_stdtime_get(&cleaner->last_cleanup_time);
 575                 result = isc_timer_create(timermgr, isc_timertype_inactive,
 576                                           NULL, NULL,
 577                                           acache->task,
 578                                           acache_cleaning_timer_action,
 579                                           cleaner, &cleaner->cleaning_timer);
 580                 if (result != ISC_R_SUCCESS) {
 581                         UNEXPECTED_ERROR(__FILE__, __LINE__,
 582                                          "isc_timer_create() failed: %s",
 583                                          dns_result_totext(result));
 584                         result = ISC_R_UNEXPECTED;
 585                         goto cleanup;
 586                 }
 587
 588                 cleaner->resched_event =
 589                         isc_event_allocate(acache->mctx, cleaner,
 590                                            DNS_EVENT_ACACHECLEAN,
 591                                            acache_incremental_cleaning_action,
 592                                            cleaner, sizeof(isc_event_t));
 593                 if (cleaner->resched_event == NULL) {
 594                         result = ISC_R_NOMEMORY;
 595                         goto cleanup;
 596                 }
 597
 598                 cleaner->overmem_event =
 599                         isc_event_allocate(acache->mctx, cleaner,
 600                                            DNS_EVENT_ACACHEOVERMEM,
 601                                            acache_overmem_cleaning_action,
 602                                            cleaner, sizeof(isc_event_t));
 603                 if (cleaner->overmem_event == NULL) {
 604                         result = ISC_R_NOMEMORY;
 605                         goto cleanup;
 606                 }
 607         }
 608
 609         return (ISC_R_SUCCESS);
 610
 611  cleanup:
 612         if (cleaner->overmem_event != NULL)
 613                 isc_event_free(&cleaner->overmem_event);
 614         if (cleaner->resched_event != NULL)
 615                 isc_event_free(&cleaner->resched_event);
 616         if (cleaner->cleaning_timer != NULL)
 617                 isc_timer_detach(&cleaner->cleaning_timer);
 618         cleaner->acache->live_cleaners--;
 619         DESTROYLOCK(&cleaner->lock);
 620  fail:
 621         return (result);
 622 }
 623
 624 static void
 625 begin_cleaning(acache_cleaner_t *cleaner) {
 626         dns_acacheentry_t *head;
 627         dns_acache_t *acache = cleaner->acache;
 628
 629         /*
 630          * This function does not have to lock the cleaner, since critical
 631          * parameters (except current_entry, which is locked by acache lock,)
 632          * are only used in a single task context.
 633          */
 634
 635         REQUIRE(CLEANER_IDLE(cleaner));
 636         INSIST(DNS_ACACHE_VALID(acache));
 637         INSIST(cleaner->current_entry == NULL);
 638
 639         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
 640                       DNS_LOGMODULE_ACACHE, ISC_LOG_DEBUG(1),
 641                       "begin acache cleaning, mem inuse %lu",
 642                       (unsigned long)isc_mem_inuse(cleaner->acache->mctx));
 643
 644         LOCK(&acache->lock);
 645
 646         head = ISC_LIST_HEAD(acache->entries);
 647         if (head != NULL)
 648                 dns_acache_attachentry(head, &cleaner->current_entry);
 649
 650         UNLOCK(&acache->lock);
 651
 652         if (cleaner->current_entry != NULL) {
 653                 cleaner->ncleaned = 0;
 654                 cleaner->state = cleaner_s_busy;
 655                 isc_task_send(acache->task, &cleaner->resched_event);
 656         }
 657
 658         return;
 659 }
 660
 661 static void
 662 end_cleaning(acache_cleaner_t *cleaner, isc_event_t *event) {
 663         dns_acache_t *acache = cleaner->acache;
 664
 665         REQUIRE(CLEANER_BUSY(cleaner));
 666         REQUIRE(event != NULL);
 667         REQUIRE(DNS_ACACHEENTRY_VALID(cleaner->current_entry));
 668
 669         /* No need to lock the cleaner (see begin_cleaning()). */
 670
 671         LOCK(&acache->lock);
 672
 673         /*
 674          * Even if the cleaner has the last reference to the entry, which means
 675          * the entry has been unused, it may still be linked if unlinking the
 676          * entry has been delayed due to the reference.
 677          */
 678         if (isc_refcount_current(&cleaner->current_entry->references) == 1) {
 679                 INSIST(cleaner->current_entry->callback == NULL);
 680
 681                 if (ISC_LINK_LINKED(cleaner->current_entry, link)) {
 682                         ISC_LIST_UNLINK(acache->entries,
 683                                         cleaner->current_entry, link);
 684                 }
 685         }
 686         dns_acache_detachentry(&cleaner->current_entry);
 687
 688         if (cleaner->overmem)
 689                 acache->stats.overmem++;
 690         acache->stats.cleaned += cleaner->ncleaned;
 691         acache->stats.cleaner_runs++;
 692
 693         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE, DNS_LOGMODULE_ACACHE,
 694                       ISC_LOG_NOTICE,
 695                       "acache %p stats: hits=%d misses=%d queries=%d "
 696                       "adds=%d deleted=%d "
 697                       "cleaned=%d cleaner_runs=%d overmem=%d "
 698                       "overmem_nocreates=%d nomem=%d",
 699                       acache,
 700                       acache->stats.hits, acache->stats.misses,
 701                       acache->stats.queries,
 702                       acache->stats.adds, acache->stats.deleted,
 703                       acache->stats.cleaned, acache->stats.cleaner_runs,
 704                       acache->stats.overmem, acache->stats.overmem_nocreates,
 705                       acache->stats.nomem);
 706         reset_stats(acache);
 707
 708         isc_stdtime_get(&cleaner->last_cleanup_time);
 709
 710         UNLOCK(&acache->lock);
 711
 712         dns_acache_setcleaninginterval(cleaner->acache,
 713                                        cleaner->cleaning_interval);
 714
 715         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE, DNS_LOGMODULE_ACACHE,
 716                       ISC_LOG_DEBUG(1), "end acache cleaning, "
 717                       "%lu entries cleaned, mem inuse %lu",
 718                       cleaner->ncleaned,
 719                       (unsigned long)isc_mem_inuse(cleaner->acache->mctx));
 720
 721         if (cleaner->overmem) {
 722                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
 723                               DNS_LOGMODULE_ACACHE, ISC_LOG_NOTICE,
 724                               "acache is still in overmem state "
 725                               "after cleaning");
 726         }
 727
 728         cleaner->ncleaned = 0;
 729         cleaner->state = cleaner_s_idle;
 730         cleaner->resched_event = event;
 731 }
 732
 733 /*
 734  * This is run once for every acache-cleaning-interval as defined
 735  * in named.conf.
 736  */
 737 static void
 738 acache_cleaning_timer_action(isc_task_t *task, isc_event_t *event) {
 739         acache_cleaner_t *cleaner = event->ev_arg;
 740
 741         UNUSED(task);
 742
 743         INSIST(event->ev_type == ISC_TIMEREVENT_TICK);
 744
 745         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE, DNS_LOGMODULE_ACACHE,
 746                       ISC_LOG_DEBUG(1), "acache cleaning timer fired, "
 747                       "cleaner state = %d", cleaner->state);
 748
 749         if (cleaner->state == cleaner_s_idle)
 750                 begin_cleaning(cleaner);
 751
 752         isc_event_free(&event);
 753 }
 754
 755 /* The caller must hold entry lock. */
 756 static inline isc_boolean_t
 757 entry_stale(acache_cleaner_t *cleaner, dns_acacheentry_t *entry,
 758             isc_stdtime32_t now32, unsigned int interval)
 759 {
 760         /*
 761          * If the callback has been canceled, we definitely do not need the
 762          * entry.
 763          */
 764         if (entry->callback == NULL)
 765                 return (ISC_TRUE);
 766
 767         if (interval > cleaner->cleaning_interval)
 768                 interval = cleaner->cleaning_interval;
 769
 770         if (entry->lastused + interval < now32)
 771                 return (ISC_TRUE);
 772
 773         /*
 774          * If the acache is in the overmem state, probabilistically decide if
 775          * the entry should be purged, based on the time passed from its last
 776          * use and the cleaning interval.
 777          */
 778         if (cleaner->overmem) {
 779                 unsigned int passed;
 780                 isc_uint32_t val;
 781
 782                 if (isc_serial_ge(now32, entry->lastused))
 783                         passed = now32 - entry->lastused; /* <= interval */
 784                 else
 785                         passed = 0;
 786
 787                 if (passed > interval / 2)
 788                         return (ISC_TRUE);
 789                 isc_random_get(&val);
 790                 if (passed > interval / 4)
 791                         return (ISC_TF(val % 4 == 0));
 792                 return (ISC_TF(val % 8 == 0));
 793         }
 794
 795         return (ISC_FALSE);
 796 }
 797
 798 /*
 799  * Do incremental cleaning.
 800  */
 801 static void
 802 acache_incremental_cleaning_action(isc_task_t *task, isc_event_t *event) {
 803         acache_cleaner_t *cleaner = event->ev_arg;
 804         dns_acache_t *acache = cleaner->acache;
 805         dns_acacheentry_t *entry, *next = NULL;
 806         int n_entries;
 807         isc_stdtime32_t now32, last32;
 808         isc_stdtime_t now;
 809         unsigned int interval;
 810
 811         INSIST(DNS_ACACHE_VALID(acache));
 812         INSIST(task == acache->task);
 813         INSIST(event->ev_type == DNS_EVENT_ACACHECLEAN);
 814
 815         if (cleaner->state == cleaner_s_done) {
 816                 cleaner->state = cleaner_s_busy;
 817                 end_cleaning(cleaner, event);
 818                 return;
 819         }
 820
 821         INSIST(CLEANER_BUSY(cleaner));
 822
 823         n_entries = cleaner->increment;
 824
 825         isc_stdtime_get(&now);
 826         isc_stdtime_convert32(now, &now32);
 827
 828         LOCK(&acache->lock);
 829
 830         entry = cleaner->current_entry;
 831         isc_stdtime_convert32(cleaner->last_cleanup_time, &last32);
 832         if (isc_serial_ge(now32, last32))
 833                 interval = now32 - last32;
 834         else
 835                 interval = 0;
 836
 837         while (n_entries-- > 0) {
 838                 isc_boolean_t is_stale = ISC_FALSE;
 839
 840                 INSIST(entry != NULL);
 841
 842                 next = ISC_LIST_NEXT(entry, link);
 843
 844                 ACACHE_LOCK(&acache->entrylocks[entry->locknum],
 845                             isc_rwlocktype_write);
 846
 847                 is_stale = entry_stale(cleaner, entry, now32, interval);
 848                 if (is_stale) {
 849                         ISC_LIST_UNLINK(acache->entries, entry, link);
 850                         unlink_dbentries(acache, entry);
 851                         if (entry->callback != NULL)
 852                                 (entry->callback)(entry, &entry->cbarg);
 853                         entry->callback = NULL;
 854
 855                         cleaner->ncleaned++;
 856                 }
 857
 858                 ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
 859                               isc_rwlocktype_write);
 860
 861                 if (is_stale)
 862                         dns_acache_detachentry(&entry);
 863
 864                 if (next == NULL) {
 865                         if (cleaner->overmem) {
 866                                 entry = ISC_LIST_HEAD(acache->entries);
 867                                 if (entry != NULL) {
 868                                         /*
 869                                          * If we are still in the overmem
 870                                          * state, keep cleaning.  In case we
 871                                          * exit from the loop immediately after
 872                                          * this, reset next to the head entry
 873                                          * as we'll expect it will be never
 874                                          * NULL.
 875                                          */
 876                                         isc_log_write(dns_lctx,
 877                                                       DNS_LOGCATEGORY_DATABASE,
 878                                                       DNS_LOGMODULE_ACACHE,
 879                                                       ISC_LOG_DEBUG(1),
 880                                                       "acache cleaner: "
 881                                                       "still overmem, "
 882                                                       "reset and try again");
 883                                         next = entry;
 884                                         continue;
 885                                 }
 886                         }
 887
 888                         UNLOCK(&acache->lock);
 889                         end_cleaning(cleaner, event);
 890                         return;
 891                 }
 892
 893                 entry = next;
 894         }
 895
 896         /*
 897          * We have successfully performed a cleaning increment but have
 898          * not gone through the entire cache.  Remember the entry that will
 899          * be the starting point in the next clean-up, and reschedule another
 900          * batch.  If it fails, just try to continue anyway.
 901          */
 902         INSIST(next != NULL);
 903         dns_acache_detachentry(&cleaner->current_entry);
 904         dns_acache_attachentry(next, &cleaner->current_entry);
 905
 906         UNLOCK(&acache->lock);
 907
 908         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE, DNS_LOGMODULE_ACACHE,
 909                       ISC_LOG_DEBUG(1), "acache cleaner: checked %d entries, "
 910                       "mem inuse %lu, sleeping", cleaner->increment,
 911                       (unsigned long)isc_mem_inuse(cleaner->acache->mctx));
 912
 913         isc_task_send(task, &event);
 914         INSIST(CLEANER_BUSY(cleaner));
 915
 916         return;
 917 }
 918
 919 /*
 920  * This is called when the acache either surpasses its upper limit
 921  * or shrinks beyond its lower limit.
 922  */
 923 static void
 924 acache_overmem_cleaning_action(isc_task_t *task, isc_event_t *event) {
 925         acache_cleaner_t *cleaner = event->ev_arg;
 926         isc_boolean_t want_cleaning = ISC_FALSE;
 927
 928         UNUSED(task);
 929
 930         INSIST(event->ev_type == DNS_EVENT_ACACHEOVERMEM);
 931         INSIST(cleaner->overmem_event == NULL);
 932
 933         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE, DNS_LOGMODULE_ACACHE,
 934                       ISC_LOG_DEBUG(1), "overmem_cleaning_action called, "
 935                       "overmem = %d, state = %d", cleaner->overmem,
 936                       cleaner->state);
 937
 938         LOCK(&cleaner->lock);
 939
 940         if (cleaner->overmem) {
 941                 if (cleaner->state == cleaner_s_idle)
 942                         want_cleaning = ISC_TRUE;
 943         } else {
 944                 if (cleaner->state == cleaner_s_busy)
 945                         /*
 946                          * end_cleaning() can't be called here because
 947                          * then both cleaner->overmem_event and
 948                          * cleaner->resched_event will point to this
 949                          * event.  Set the state to done, and then
 950                          * when the acache_incremental_cleaning_action() event
 951                          * is posted, it will handle the end_cleaning.
 952                          */
 953                         cleaner->state = cleaner_s_done;
 954         }
 955
 956         cleaner->overmem_event = event;
 957
 958         UNLOCK(&cleaner->lock);
 959
 960         if (want_cleaning)
 961                 begin_cleaning(cleaner);
 962 }
 963
 964 static void
 965 water(void *arg, int mark) {
 966         dns_acache_t *acache = arg;
 967         isc_boolean_t overmem = ISC_TF(mark == ISC_MEM_HIWATER);
 968
 969         REQUIRE(DNS_ACACHE_VALID(acache));
 970
 971         isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
 972                       DNS_LOGMODULE_ACACHE, ISC_LOG_DEBUG(1),
 973                       "acache memory reaches %s watermark, mem inuse %lu",
 974                       overmem ? "high" : "low",
 975                       (unsigned long)isc_mem_inuse(acache->mctx));
 976
 977         LOCK(&acache->cleaner.lock);
 978
 979         if (acache->cleaner.overmem != overmem) {
 980                 acache->cleaner.overmem = overmem;
 981
 982                 if (acache->cleaner.overmem_event != NULL)
 983                         isc_task_send(acache->task,
 984                                       &acache->cleaner.overmem_event);
 985                 isc_mem_waterack(acache->mctx, mark);
 986         }
 987
 988         UNLOCK(&acache->cleaner.lock);
 989 }
 990
 991 /*
 992  * The cleaner task is shutting down; do the necessary cleanup.
 993  */
 994 static void
 995 acache_cleaner_shutdown_action(isc_task_t *task, isc_event_t *event) {
 996         dns_acache_t *acache = event->ev_arg;
 997         isc_boolean_t should_free = ISC_FALSE;
 998
 999         INSIST(task == acache->task);
1000         INSIST(event->ev_type == ISC_TASKEVENT_SHUTDOWN);
1001         INSIST(DNS_ACACHE_VALID(acache));
1002
1003         ATRACE("acache cleaner shutdown");
1004
1005         if (CLEANER_BUSY(&acache->cleaner))
1006                 end_cleaning(&acache->cleaner, event);
1007         else
1008                 isc_event_free(&event);
1009
1010         LOCK(&acache->lock);
1011
1012         acache->live_cleaners--;
1013         INSIST(acache->live_cleaners == 0);
1014
1015         if (isc_refcount_current(&acache->refs) == 0) {
1016                 INSIST(check_noentry(acache) == ISC_TRUE);
1017                 should_free = ISC_TRUE;
1018         }
1019
1020         /*
1021          * By detaching the timer in the context of its task,
1022          * we are guaranteed that there will be no further timer
1023          * events.
1024          */
1025         if (acache->cleaner.cleaning_timer != NULL)
1026                 isc_timer_detach(&acache->cleaner.cleaning_timer);
1027
1028         /* Make sure we don't reschedule anymore. */
1029         (void)isc_task_purge(task, NULL, DNS_EVENT_ACACHECLEAN, NULL);
1030
1031         UNLOCK(&acache->lock);
1032
1033         if (should_free)
1034                 destroy(acache);
1035 }
1036
1037 /*
1038  *      Public functions.
1039  */
1040
1041 isc_result_t
1042 dns_acache_create(dns_acache_t **acachep, isc_mem_t *mctx,
1043                   isc_taskmgr_t *taskmgr, isc_timermgr_t *timermgr)
1044 {
1045         int i;
1046         isc_result_t result;
1047         dns_acache_t *acache;
1048
1049         REQUIRE(acachep != NULL && *acachep == NULL);
1050         REQUIRE(mctx != NULL);
1051         REQUIRE(taskmgr != NULL);
1052
1053         acache = isc_mem_get(mctx, sizeof(*acache));
1054         if (acache == NULL)
1055                 return (ISC_R_NOMEMORY);
1056
1057         ATRACE("create");
1058
1059         result = isc_refcount_init(&acache->refs, 1);
1060         if (result != ISC_R_SUCCESS) {
1061                 isc_mem_put(mctx, acache, sizeof(*acache));
1062                 return (result);
1063         }
1064
1065         result = isc_mutex_init(&acache->lock);
1066         if (result != ISC_R_SUCCESS) {
1067                 isc_refcount_decrement(&acache->refs, NULL);
1068                 isc_refcount_destroy(&acache->refs);
1069                 isc_mem_put(mctx, acache, sizeof(*acache));
1070                 return (result);
1071         }
1072
1073         acache->mctx = NULL;
1074         isc_mem_attach(mctx, &acache->mctx);
1075         ISC_LIST_INIT(acache->entries);
1076
1077         acache->shutting_down = ISC_FALSE;
1078
1079         acache->task = NULL;
1080         acache->entrylocks = NULL;
1081
1082         result = isc_task_create(taskmgr, 1, &acache->task);
1083         if (result != ISC_R_SUCCESS) {
1084                 UNEXPECTED_ERROR(__FILE__, __LINE__,
1085                                  "isc_task_create() failed(): %s",
1086                                  dns_result_totext(result));
1087                 result = ISC_R_UNEXPECTED;
1088                 goto cleanup;
1089         }
1090         isc_task_setname(acache->task, "acachetask", acache);
1091         ISC_EVENT_INIT(&acache->cevent, sizeof(acache->cevent), 0, NULL,
1092                        DNS_EVENT_ACACHECONTROL, shutdown_task, NULL,
1093                        NULL, NULL, NULL);
1094         acache->cevent_sent = ISC_FALSE;
1095
1096         acache->dbentries = 0;
1097         for (i = 0; i < DBBUCKETS; i++)
1098                 ISC_LIST_INIT(acache->dbbucket[i]);
1099
1100         acache->entrylocks = isc_mem_get(mctx, sizeof(*acache->entrylocks) *
1101                                          DEFAULT_ACACHE_ENTRY_LOCK_COUNT);
1102         if (acache->entrylocks == NULL) {
1103                 result = ISC_R_NOMEMORY;
1104                 goto cleanup;
1105         }
1106         for (i = 0; i < DEFAULT_ACACHE_ENTRY_LOCK_COUNT; i++) {
1107                 result = ACACHE_INITLOCK(&acache->entrylocks[i]);
1108                 if (result != ISC_R_SUCCESS) {
1109                         while (i-- > 0)
1110                                 ACACHE_DESTROYLOCK(&acache->entrylocks[i]);
1111                         isc_mem_put(mctx, acache->entrylocks,
1112                                     sizeof(*acache->entrylocks) *
1113                                     DEFAULT_ACACHE_ENTRY_LOCK_COUNT);
1114                         acache->entrylocks = NULL;
1115                         goto cleanup;
1116                 }
1117         }
1118
1119         acache->live_cleaners = 0;
1120         result = acache_cleaner_init(acache, timermgr, &acache->cleaner);
1121         if (result != ISC_R_SUCCESS)
1122                 goto cleanup;
1123
1124         acache->stats.cleaner_runs = 0;
1125         reset_stats(acache);
1126
1127         acache->magic = ACACHE_MAGIC;
1128
1129         *acachep = acache;
1130         return (ISC_R_SUCCESS);
1131
1132  cleanup:
1133         if (acache->task != NULL)
1134                 isc_task_detach(&acache->task);
1135         DESTROYLOCK(&acache->lock);
1136         isc_refcount_decrement(&acache->refs, NULL);
1137         isc_refcount_destroy(&acache->refs);
1138         if (acache->entrylocks != NULL) {
1139                 for (i = 0; i < DEFAULT_ACACHE_ENTRY_LOCK_COUNT; i++)
1140                         ACACHE_DESTROYLOCK(&acache->entrylocks[i]);
1141                 isc_mem_put(mctx, acache->entrylocks,
1142                             sizeof(*acache->entrylocks) *
1143                             DEFAULT_ACACHE_ENTRY_LOCK_COUNT);
1144         }
1145         isc_mem_put(mctx, acache, sizeof(*acache));
1146         isc_mem_detach(&mctx);
1147
1148         return (result);
1149 }
1150
1151 void
1152 dns_acache_attach(dns_acache_t *source, dns_acache_t **targetp) {
1153         REQUIRE(DNS_ACACHE_VALID(source));
1154         REQUIRE(targetp != NULL && *targetp == NULL);
1155
1156         AATRACE(source, "attach");
1157
1158         isc_refcount_increment(&source->refs, NULL);
1159
1160         *targetp = source;
1161 }
1162
1163 void
1164 dns_acache_countquerymiss(dns_acache_t *acache) {
1165         acache->stats.misses++;         /* XXXSK danger: unlocked! */
1166         acache->stats.queries++;        /* XXXSK danger: unlocked! */
1167 }
1168
1169 void
1170 dns_acache_detach(dns_acache_t **acachep) {
1171         dns_acache_t *acache;
1172         unsigned int refs;
1173         isc_boolean_t should_free = ISC_FALSE;
1174
1175         REQUIRE(acachep != NULL && DNS_ACACHE_VALID(*acachep));
1176         acache = *acachep;
1177
1178         ATRACE("detach");
1179
1180         isc_refcount_decrement(&acache->refs, &refs);
1181         if (refs == 0) {
1182                 INSIST(check_noentry(acache) == ISC_TRUE);
1183                 should_free = ISC_TRUE;
1184         }
1185
1186         *acachep = NULL;
1187
1188         /*
1189          * If we're exiting and the cleaner task exists, let it free the cache.
1190          */
1191         if (should_free && acache->live_cleaners > 0) {
1192                 isc_task_shutdown(acache->task);
1193                 should_free = ISC_FALSE;
1194         }
1195
1196         if (should_free)
1197                 destroy(acache);
1198 }
1199
1200 void
1201 dns_acache_shutdown(dns_acache_t *acache) {
1202         REQUIRE(DNS_ACACHE_VALID(acache));
1203
1204         LOCK(&acache->lock);
1205
1206         ATRACE("shutdown");
1207
1208         if (!acache->shutting_down) {
1209                 isc_event_t *event;
1210                 dns_acache_t *acache_evarg = NULL;
1211
1212                 INSIST(!acache->cevent_sent);
1213
1214                 acache->shutting_down = ISC_TRUE;
1215
1216                 isc_mem_setwater(acache->mctx, NULL, NULL, 0, 0);
1217
1218                 /*
1219                  * Self attach the object in order to prevent it from being
1220                  * destroyed while waiting for the event.
1221                  */
1222                 dns_acache_attach(acache, &acache_evarg);
1223                 event = &acache->cevent;
1224                 event->ev_arg = acache_evarg;
1225                 isc_task_send(acache->task, &event);
1226                 acache->cevent_sent = ISC_TRUE;
1227         }
1228
1229         UNLOCK(&acache->lock);
1230 }
1231
1232 isc_result_t
1233 dns_acache_setdb(dns_acache_t *acache, dns_db_t *db) {
1234         int bucket;
1235         dbentry_t *dbentry;
1236         isc_result_t result = ISC_R_SUCCESS;
1237
1238         REQUIRE(DNS_ACACHE_VALID(acache));
1239         REQUIRE(db != NULL);
1240
1241         ATRACE("setdb");
1242
1243         LOCK(&acache->lock);
1244
1245         dbentry = NULL;
1246         result = finddbent(acache, db, &dbentry);
1247         if (result == ISC_R_SUCCESS) {
1248                 result = ISC_R_EXISTS;
1249                 goto end;
1250         }
1251         result = ISC_R_SUCCESS;
1252
1253         dbentry = isc_mem_get(acache->mctx, sizeof(*dbentry));
1254         if (dbentry == NULL) {
1255                 result = ISC_R_NOMEMORY;
1256                 goto end;
1257         }
1258
1259         ISC_LINK_INIT(dbentry, link);
1260         ISC_LIST_INIT(dbentry->originlist);
1261         ISC_LIST_INIT(dbentry->referlist);
1262
1263         dbentry->db = NULL;
1264         dns_db_attach(db, &dbentry->db);
1265
1266         bucket = isc_hash_function(&db, sizeof(db), ISC_TRUE, NULL) % DBBUCKETS;
1267
1268         ISC_LIST_APPEND(acache->dbbucket[bucket], dbentry, link);
1269
1270         acache->dbentries++;
1271
1272  end:
1273         UNLOCK(&acache->lock);
1274
1275         return (result);
1276 }
1277
1278 isc_result_t
1279 dns_acache_putdb(dns_acache_t *acache, dns_db_t *db) {
1280         int bucket;
1281         isc_result_t result;
1282         dbentry_t *dbentry;
1283         dns_acacheentry_t *entry;
1284
1285         REQUIRE(DNS_ACACHE_VALID(acache));
1286         REQUIRE(db != NULL);
1287
1288         ATRACE("putdb");
1289
1290         LOCK(&acache->lock);
1291
1292         dbentry = NULL;
1293         result = finddbent(acache, db, &dbentry);
1294         if (result != ISC_R_SUCCESS) {
1295                 /*
1296                  * The entry may have not been created due to memory shortage.
1297                  */
1298                 UNLOCK(&acache->lock);
1299                 return (ISC_R_NOTFOUND);
1300         }
1301
1302         /*
1303          * Release corresponding cache entries: for each entry, release all
1304          * links the entry has, and then callback to the entry holder (if any).
1305          * If no other external references exist (this can happen if the
1306          * original holder has canceled callback,) destroy it here.
1307          */
1308         while ((entry = ISC_LIST_HEAD(dbentry->originlist)) != NULL) {
1309                 ACACHE_LOCK(&acache->entrylocks[entry->locknum],
1310                             isc_rwlocktype_write);
1311
1312                 /*
1313                  * Releasing olink first would avoid finddbent() in
1314                  * unlink_dbentries().
1315                  */
1316                 ISC_LIST_UNLINK(dbentry->originlist, entry, olink);
1317                 if (acache->cleaner.current_entry != entry)
1318                         ISC_LIST_UNLINK(acache->entries, entry, link);
1319                 unlink_dbentries(acache, entry);
1320
1321                 if (entry->callback != NULL)
1322                         (entry->callback)(entry, &entry->cbarg);
1323                 entry->callback = NULL;
1324
1325                 ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
1326                               isc_rwlocktype_write);
1327
1328                 if (acache->cleaner.current_entry != entry)
1329                         dns_acache_detachentry(&entry);
1330         }
1331         while ((entry = ISC_LIST_HEAD(dbentry->referlist)) != NULL) {
1332                 ACACHE_LOCK(&acache->entrylocks[entry->locknum],
1333                             isc_rwlocktype_write);
1334
1335                 ISC_LIST_UNLINK(dbentry->referlist, entry, rlink);
1336                 if (acache->cleaner.current_entry != entry)
1337                         ISC_LIST_UNLINK(acache->entries, entry, link);
1338                 unlink_dbentries(acache, entry);
1339
1340                 if (entry->callback != NULL)
1341                         (entry->callback)(entry, &entry->cbarg);
1342                 entry->callback = NULL;
1343
1344                 ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
1345                               isc_rwlocktype_write);
1346
1347                 if (acache->cleaner.current_entry != entry)
1348                         dns_acache_detachentry(&entry);
1349         }
1350
1351         INSIST(ISC_LIST_EMPTY(dbentry->originlist) &&
1352                ISC_LIST_EMPTY(dbentry->referlist));
1353
1354         bucket = isc_hash_function(&db, sizeof(db), ISC_TRUE, NULL) % DBBUCKETS;
1355
1356         ISC_LIST_UNLINK(acache->dbbucket[bucket], dbentry, link);
1357         dns_db_detach(&dbentry->db);
1358
1359         isc_mem_put(acache->mctx, dbentry, sizeof(*dbentry));
1360
1361         acache->dbentries--;
1362
1363         acache->stats.deleted++;
1364
1365         UNLOCK(&acache->lock);
1366
1367         return (ISC_R_SUCCESS);
1368 }
1369
1370 isc_result_t
1371 dns_acache_createentry(dns_acache_t *acache, dns_db_t *origdb,
1372                        void (*callback)(dns_acacheentry_t *, void **),
1373                        void *cbarg, dns_acacheentry_t **entryp)
1374 {
1375         dns_acacheentry_t *newentry;
1376         isc_result_t result;
1377         isc_uint32_t r;
1378
1379         REQUIRE(DNS_ACACHE_VALID(acache));
1380         REQUIRE(entryp != NULL && *entryp == NULL);
1381         REQUIRE(origdb != NULL);
1382
1383         /*
1384          * Should we exceed our memory limit for some reason (for
1385          * example, if the cleaner does not run aggressively enough),
1386          * then we will not create additional entries.
1387          *
1388          * XXXSK: It might be better to lock the acache->cleaner->lock,
1389          * but locking may be an expensive bottleneck. If we misread
1390          * the value, we will occasionally refuse to create a few
1391          * cache entries, or create a few that we should not. I do not
1392          * expect this to happen often, and it will not have very bad
1393          * effects when it does. So no lock for now.
1394          */
1395         if (acache->cleaner.overmem) {
1396                 acache->stats.overmem_nocreates++; /* XXXSK danger: unlocked! */
1397                 return (ISC_R_NORESOURCES);
1398         }
1399
1400         newentry = isc_mem_get(acache->mctx, sizeof(*newentry));
1401         if (newentry == NULL) {
1402                 acache->stats.nomem++;  /* XXXMLG danger: unlocked! */
1403                 return (ISC_R_NOMEMORY);
1404         }
1405
1406         isc_random_get(&r);
1407         newentry->locknum = r % DEFAULT_ACACHE_ENTRY_LOCK_COUNT;
1408
1409         result = isc_refcount_init(&newentry->references, 1);
1410         if (result != ISC_R_SUCCESS) {
1411                 isc_mem_put(acache->mctx, newentry, sizeof(*newentry));
1412                 return (result);
1413         };
1414
1415         ISC_LINK_INIT(newentry, link);
1416         ISC_LINK_INIT(newentry, olink);
1417         ISC_LINK_INIT(newentry, rlink);
1418
1419         newentry->acache = NULL;
1420         dns_acache_attach(acache, &newentry->acache);
1421
1422         newentry->zone = NULL;
1423         newentry->db = NULL;
1424         newentry->version = NULL;
1425         newentry->node = NULL;
1426         newentry->foundname = NULL;
1427
1428         newentry->callback = callback;
1429         newentry->cbarg = cbarg;
1430         newentry->origdb = NULL;
1431         dns_db_attach(origdb, &newentry->origdb);
1432
1433         isc_stdtime_get(&newentry->lastused);
1434
1435         newentry->magic = ACACHEENTRY_MAGIC;
1436
1437         *entryp = newentry;
1438
1439         return (ISC_R_SUCCESS);
1440 }
1441
1442 isc_result_t
1443 dns_acache_getentry(dns_acacheentry_t *entry, dns_zone_t **zonep,
1444                     dns_db_t **dbp, dns_dbversion_t **versionp,
1445                     dns_dbnode_t **nodep, dns_name_t *fname,
1446                     dns_message_t *msg, isc_stdtime_t now)
1447 {
1448         isc_result_t result = ISC_R_SUCCESS;
1449         dns_rdataset_t *erdataset;
1450         isc_stdtime32_t now32;
1451         dns_acache_t *acache;
1452         int locknum;
1453
1454         REQUIRE(DNS_ACACHEENTRY_VALID(entry));
1455         REQUIRE(zonep == NULL || *zonep == NULL);
1456         REQUIRE(dbp != NULL && *dbp == NULL);
1457         REQUIRE(versionp != NULL && *versionp == NULL);
1458         REQUIRE(nodep != NULL && *nodep == NULL);
1459         REQUIRE(fname != NULL);
1460         REQUIRE(msg != NULL);
1461         acache = entry->acache;
1462         REQUIRE(DNS_ACACHE_VALID(acache));
1463
1464         locknum = entry->locknum;
1465         ACACHE_LOCK(&acache->entrylocks[locknum], isc_rwlocktype_read);
1466
1467         isc_stdtime_convert32(now, &now32);
1468         acache_storetime(entry, now32);
1469
1470         if (entry->zone != NULL && zonep != NULL)
1471                 dns_zone_attach(entry->zone, zonep);
1472
1473         if (entry->db == NULL) {
1474                 *dbp = NULL;
1475                 *versionp = NULL;
1476         } else {
1477                 dns_db_attach(entry->db, dbp);
1478                 dns_db_attachversion(entry->db, entry->version, versionp);
1479         }
1480         if (entry->node == NULL)
1481                 *nodep = NULL;
1482         else {
1483                 dns_db_attachnode(entry->db, entry->node, nodep);
1484
1485                 INSIST(entry->foundname != NULL);
1486                 dns_name_copy(entry->foundname, fname, NULL);
1487                 for (erdataset = ISC_LIST_HEAD(entry->foundname->list);
1488                      erdataset != NULL;
1489                      erdataset = ISC_LIST_NEXT(erdataset, link)) {
1490                         dns_rdataset_t *ardataset;
1491
1492                         ardataset = NULL;
1493                         result = dns_message_gettemprdataset(msg, &ardataset);
1494                         if (result != ISC_R_SUCCESS) {
1495                                 ACACHE_UNLOCK(&acache->entrylocks[locknum],
1496                                               isc_rwlocktype_read);
1497                                 goto fail;
1498                         }
1499
1500                         /*
1501                          * XXXJT: if we simply clone the rdataset, we'll get
1502                          * lost wrt cyclic ordering.  We'll need an additional
1503                          * trick to get the latest counter from the original
1504                          * header.
1505                          */
1506                         dns_rdataset_init(ardataset);
1507                         dns_rdataset_clone(erdataset, ardataset);
1508                         ISC_LIST_APPEND(fname->list, ardataset, link);
1509                 }
1510         }
1511
1512         entry->acache->stats.hits++; /* XXXMLG danger: unlocked! */
1513         entry->acache->stats.queries++;
1514
1515         ACACHE_UNLOCK(&acache->entrylocks[locknum], isc_rwlocktype_read);
1516
1517         return (result);
1518
1519   fail:
1520         while ((erdataset = ISC_LIST_HEAD(fname->list)) != NULL) {
1521                 ISC_LIST_UNLINK(fname->list, erdataset, link);
1522                 dns_rdataset_disassociate(erdataset);
1523                 dns_message_puttemprdataset(msg, &erdataset);
1524         }
1525         if (*nodep != NULL)
1526                 dns_db_detachnode(*dbp, nodep);
1527         if (*versionp != NULL)
1528                 dns_db_closeversion(*dbp, versionp, ISC_FALSE);
1529         if (*dbp != NULL)
1530                 dns_db_detach(dbp);
1531         if (zonep != NULL && *zonep != NULL)
1532                 dns_zone_detach(zonep);
1533
1534         return (result);
1535 }
1536
1537 isc_result_t
1538 dns_acache_setentry(dns_acache_t *acache, dns_acacheentry_t *entry,
1539                     dns_zone_t *zone, dns_db_t *db, dns_dbversion_t *version,
1540                     dns_dbnode_t *node, dns_name_t *fname)
1541 {
1542         isc_result_t result;
1543         dbentry_t *odbent;
1544         dbentry_t *rdbent = NULL;
1545         isc_boolean_t close_version = ISC_FALSE;
1546         dns_acacheentry_t *dummy_entry = NULL;
1547
1548         REQUIRE(DNS_ACACHE_VALID(acache));
1549         REQUIRE(DNS_ACACHEENTRY_VALID(entry));
1550
1551         LOCK(&acache->lock);    /* XXX: need to lock it here for ordering */
1552         ACACHE_LOCK(&acache->entrylocks[entry->locknum], isc_rwlocktype_write);
1553
1554         /* Set zone */
1555         if (zone != NULL)
1556                 dns_zone_attach(zone, &entry->zone);
1557         /* Set DB */
1558         if (db != NULL)
1559                 dns_db_attach(db, &entry->db);
1560         /*
1561          * Set DB version.  If the version is not given by the caller,
1562          * which is the case for glue or cache DBs, use the current version.
1563          */
1564         if (version == NULL) {
1565                 if (db != NULL) {
1566                         dns_db_currentversion(db, &version);
1567                         close_version = ISC_TRUE;
1568                 }
1569         }
1570         if (version != NULL) {
1571                 INSIST(db != NULL);
1572                 dns_db_attachversion(db, version, &entry->version);
1573         }
1574         if (close_version)
1575                 dns_db_closeversion(db, &version, ISC_FALSE);
1576         /* Set DB node. */
1577         if (node != NULL) {
1578                 INSIST(db != NULL);
1579                 dns_db_attachnode(db, node, &entry->node);
1580         }
1581
1582         /*
1583          * Set list of the corresponding rdatasets, if given.
1584          * To minimize the overhead and memory consumption, we'll do this for
1585          * positive cache only, in which case the DB node is non NULL.
1586          * We do not want to cache incomplete information, so give up the
1587          * entire entry when a memory shortage happen during the process.
1588          */
1589         if (node != NULL) {
1590                 dns_rdataset_t *ardataset, *crdataset;
1591
1592                 entry->foundname = isc_mem_get(acache->mctx,
1593                                                sizeof(*entry->foundname));
1594
1595                 if (entry->foundname == NULL) {
1596                         result = ISC_R_NOMEMORY;
1597                         goto fail;
1598                 }
1599                 dns_name_init(entry->foundname, NULL);
1600                 result = dns_name_dup(fname, acache->mctx,
1601                                       entry->foundname);
1602                 if (result != ISC_R_SUCCESS)
1603                         goto fail;
1604
1605                 for (ardataset = ISC_LIST_HEAD(fname->list);
1606                      ardataset != NULL;
1607                      ardataset = ISC_LIST_NEXT(ardataset, link)) {
1608                         crdataset = isc_mem_get(acache->mctx,
1609                                                 sizeof(*crdataset));
1610                         if (crdataset == NULL) {
1611                                 result = ISC_R_NOMEMORY;
1612                                 goto fail;
1613                         }
1614
1615                         dns_rdataset_init(crdataset);
1616                         dns_rdataset_clone(ardataset, crdataset);
1617                         ISC_LIST_APPEND(entry->foundname->list, crdataset,
1618                                         link);
1619                 }
1620         }
1621
1622         odbent = NULL;
1623         result = finddbent(acache, entry->origdb, &odbent);
1624         if (result != ISC_R_SUCCESS)
1625                 goto fail;
1626         if (db != NULL) {
1627                 rdbent = NULL;
1628                 result = finddbent(acache, db, &rdbent);
1629                 if (result != ISC_R_SUCCESS)
1630                         goto fail;
1631         }
1632
1633         ISC_LIST_APPEND(acache->entries, entry, link);
1634         ISC_LIST_APPEND(odbent->originlist, entry, olink);
1635         if (rdbent != NULL)
1636                 ISC_LIST_APPEND(rdbent->referlist, entry, rlink);
1637
1638         /*
1639          * The additional cache needs an implicit reference to entries in its
1640          * link.
1641          */
1642         dns_acache_attachentry(entry, &dummy_entry);
1643
1644         ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
1645                       isc_rwlocktype_write);
1646
1647         acache->stats.adds++;
1648         UNLOCK(&acache->lock);
1649
1650         return (ISC_R_SUCCESS);
1651
1652  fail:
1653         clear_entry(acache, entry);
1654
1655         ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
1656                       isc_rwlocktype_write);
1657         UNLOCK(&acache->lock);
1658
1659         return (result);
1660 }
1661
1662 isc_boolean_t
1663 dns_acache_cancelentry(dns_acacheentry_t *entry) {
1664         dns_acache_t *acache;
1665         isc_boolean_t callback_active;
1666
1667         REQUIRE(DNS_ACACHEENTRY_VALID(entry));
1668
1669         acache = entry->acache;
1670
1671         INSIST(DNS_ACACHE_VALID(entry->acache));
1672
1673         LOCK(&acache->lock);
1674         ACACHE_LOCK(&acache->entrylocks[entry->locknum], isc_rwlocktype_write);
1675
1676         callback_active = ISC_TF(entry->cbarg != NULL);
1677
1678         /*
1679          * Release dependencies stored in this entry as much as possible.
1680          * The main link cannot be released, since the acache object has
1681          * a reference to this entry; the empty entry will be released in
1682          * the next cleaning action.
1683          */
1684         unlink_dbentries(acache, entry);
1685         clear_entry(entry->acache, entry);
1686
1687         entry->callback = NULL;
1688         entry->cbarg = NULL;
1689
1690         ACACHE_UNLOCK(&acache->entrylocks[entry->locknum],
1691                       isc_rwlocktype_write);
1692         UNLOCK(&acache->lock);
1693
1694         return (callback_active);
1695 }
1696
1697 void
1698 dns_acache_attachentry(dns_acacheentry_t *source,
1699                        dns_acacheentry_t **targetp)
1700 {
1701         REQUIRE(DNS_ACACHEENTRY_VALID(source));
1702         REQUIRE(targetp != NULL && *targetp == NULL);
1703
1704         isc_refcount_increment(&source->references, NULL);
1705
1706         *targetp = source;
1707 }
1708
1709 void
1710 dns_acache_detachentry(dns_acacheentry_t **entryp) {
1711         dns_acacheentry_t *entry;
1712         unsigned int refs;
1713
1714         REQUIRE(entryp != NULL && DNS_ACACHEENTRY_VALID(*entryp));
1715         entry = *entryp;
1716
1717         isc_refcount_decrement(&entry->references, &refs);
1718
1719         /*
1720          * If there are no references to the entry, the entry must have been
1721          * unlinked and can be destroyed safely.
1722          */
1723         if (refs == 0) {
1724                 INSIST(!ISC_LINK_LINKED(entry, link));
1725                 (*entryp)->acache->stats.deleted++;
1726                 destroy_entry(entry);
1727         }
1728
1729         *entryp = NULL;
1730 }
1731
1732 void
1733 dns_acache_setcleaninginterval(dns_acache_t *acache, unsigned int t) {
1734         isc_interval_t interval;
1735         isc_result_t result;
1736
1737         REQUIRE(DNS_ACACHE_VALID(acache));
1738
1739         ATRACE("dns_acache_setcleaninginterval");
1740
1741         LOCK(&acache->lock);
1742
1743         /*
1744          * It may be the case that the acache has already shut down.
1745          * If so, it has no timer.  (Not sure if this can really happen.)
1746          */
1747         if (acache->cleaner.cleaning_timer == NULL)
1748                 goto unlock;
1749
1750         acache->cleaner.cleaning_interval = t;
1751
1752         if (t == 0) {
1753                 result = isc_timer_reset(acache->cleaner.cleaning_timer,
1754                                          isc_timertype_inactive,
1755                                          NULL, NULL, ISC_TRUE);
1756         } else {
1757                 isc_interval_set(&interval, acache->cleaner.cleaning_interval,
1758                                  0);
1759                 result = isc_timer_reset(acache->cleaner.cleaning_timer,
1760                                          isc_timertype_ticker,
1761                                          NULL, &interval, ISC_FALSE);
1762         }
1763         if (result != ISC_R_SUCCESS)
1764                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
1765                               DNS_LOGMODULE_ACACHE, ISC_LOG_WARNING,
1766                               "could not set acache cleaning interval: %s",
1767                               isc_result_totext(result));
1768         else
1769                 isc_log_write(dns_lctx, DNS_LOGCATEGORY_DATABASE,
1770                               DNS_LOGMODULE_ACACHE, ISC_LOG_NOTICE,
1771                               "acache %p cleaning interval set to %d.",
1772                               acache, t);
1773
1774  unlock:
1775         UNLOCK(&acache->lock);
1776 }
1777
1778 /*
1779  * This function was derived from cache.c:dns_cache_setcachesize().  See the
1780  * function for more details about the logic.
1781  */
1782 void
1783 dns_acache_setcachesize(dns_acache_t *acache, size_t size) {
1784         size_t hiwater, lowater;
1785
1786         REQUIRE(DNS_ACACHE_VALID(acache));
1787
1788         if (size != 0U && size < DNS_ACACHE_MINSIZE)
1789                 size = DNS_ACACHE_MINSIZE;
1790
1791         hiwater = size - (size >> 3);
1792         lowater = size - (size >> 2);
1793
1794         if (size == 0U || hiwater == 0U || lowater == 0U)
1795                 isc_mem_setwater(acache->mctx, water, acache, 0, 0);
1796         else
1797                 isc_mem_setwater(acache->mctx, water, acache,
1798                                  hiwater, lowater);
1799 }