contrib/bind9/lib/dns/adb.c

   1 /*
   2  * Copyright (C) 2004-2012  Internet Systems Consortium, Inc. ("ISC")
   3  * Copyright (C) 1999-2003  Internet Software Consortium.
   4  *
   5  * Permission to use, copy, modify, and/or distribute this software for any
   6  * purpose with or without fee is hereby granted, provided that the above
   7  * copyright notice and this permission notice appear in all copies.
   8  *
   9  * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
  10  * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  11  * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
  12  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
  13  * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  14  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  15  * PERFORMANCE OF THIS SOFTWARE.
  16  */
  17
  18 /* $Id$ */
  19
  20 /*! \file
  21  *
  22  * \note
  23  * In finds, if task == NULL, no events will be generated, and no events
  24  * have been sent.  If task != NULL but taskaction == NULL, an event has been
  25  * posted but not yet freed.  If neither are NULL, no event was posted.
  26  *
  27  */
  28
  29 #include <config.h>
  30
  31 #include <limits.h>
  32
  33 #include <isc/mutexblock.h>
  34 #include <isc/netaddr.h>
  35 #include <isc/random.h>
  36 #include <isc/stats.h>
  37 #include <isc/string.h>         /* Required for HP/UX (and others?) */
  38 #include <isc/task.h>
  39 #include <isc/util.h>
  40
  41 #include <dns/adb.h>
  42 #include <dns/db.h>
  43 #include <dns/events.h>
  44 #include <dns/log.h>
  45 #include <dns/rdata.h>
  46 #include <dns/rdataset.h>
  47 #include <dns/rdatastruct.h>
  48 #include <dns/rdatatype.h>
  49 #include <dns/resolver.h>
  50 #include <dns/result.h>
  51 #include <dns/stats.h>
  52
  53 #define DNS_ADB_MAGIC             ISC_MAGIC('D', 'a', 'd', 'b')
  54 #define DNS_ADB_VALID(x)          ISC_MAGIC_VALID(x, DNS_ADB_MAGIC)
  55 #define DNS_ADBNAME_MAGIC         ISC_MAGIC('a', 'd', 'b', 'N')
  56 #define DNS_ADBNAME_VALID(x)      ISC_MAGIC_VALID(x, DNS_ADBNAME_MAGIC)
  57 #define DNS_ADBNAMEHOOK_MAGIC     ISC_MAGIC('a', 'd', 'N', 'H')
  58 #define DNS_ADBNAMEHOOK_VALID(x)  ISC_MAGIC_VALID(x, DNS_ADBNAMEHOOK_MAGIC)
  59 #define DNS_ADBLAMEINFO_MAGIC     ISC_MAGIC('a', 'd', 'b', 'Z')
  60 #define DNS_ADBLAMEINFO_VALID(x)  ISC_MAGIC_VALID(x, DNS_ADBLAMEINFO_MAGIC)
  61 #define DNS_ADBENTRY_MAGIC        ISC_MAGIC('a', 'd', 'b', 'E')
  62 #define DNS_ADBENTRY_VALID(x)     ISC_MAGIC_VALID(x, DNS_ADBENTRY_MAGIC)
  63 #define DNS_ADBFETCH_MAGIC        ISC_MAGIC('a', 'd', 'F', '4')
  64 #define DNS_ADBFETCH_VALID(x)     ISC_MAGIC_VALID(x, DNS_ADBFETCH_MAGIC)
  65 #define DNS_ADBFETCH6_MAGIC       ISC_MAGIC('a', 'd', 'F', '6')
  66 #define DNS_ADBFETCH6_VALID(x)    ISC_MAGIC_VALID(x, DNS_ADBFETCH6_MAGIC)
  67
  68 /*!
  69  * For type 3 negative cache entries, we will remember that the address is
  70  * broken for this long.  XXXMLG This is also used for actual addresses, too.
  71  * The intent is to keep us from constantly asking about A/AAAA records
  72  * if the zone has extremely low TTLs.
  73  */
  74 #define ADB_CACHE_MINIMUM       10      /*%< seconds */
  75 #define ADB_CACHE_MAXIMUM       86400   /*%< seconds (86400 = 24 hours) */
  76 #define ADB_ENTRY_WINDOW        1800    /*%< seconds */
  77
  78 /*%
  79  * The period in seconds after which an ADB name entry is regarded as stale
  80  * and forced to be cleaned up.
  81  * TODO: This should probably be configurable at run-time.
  82  */
  83 #ifndef ADB_STALE_MARGIN
  84 #define ADB_STALE_MARGIN        1800
  85 #endif
  86
  87 #define FREE_ITEMS              64      /*%< free count for memory pools */
  88 #define FILL_COUNT              16      /*%< fill count for memory pools */
  89
  90 #define DNS_ADB_INVALIDBUCKET (-1)      /*%< invalid bucket address */
  91
  92 #define DNS_ADB_MINADBSIZE      (1024*1024)     /*%< 1 Megabyte */
  93
  94 typedef ISC_LIST(dns_adbname_t) dns_adbnamelist_t;
  95 typedef struct dns_adbnamehook dns_adbnamehook_t;
  96 typedef ISC_LIST(dns_adbnamehook_t) dns_adbnamehooklist_t;
  97 typedef struct dns_adblameinfo dns_adblameinfo_t;
  98 typedef ISC_LIST(dns_adbentry_t) dns_adbentrylist_t;
  99 typedef struct dns_adbfetch dns_adbfetch_t;
 100 typedef struct dns_adbfetch6 dns_adbfetch6_t;
 101
 102 /*% dns adb structure */
 103 struct dns_adb {
 104         unsigned int                    magic;
 105
 106         isc_mutex_t                     lock;
 107         isc_mutex_t                     reflock; /*%< Covers irefcnt, erefcnt */
 108         isc_mutex_t                     overmemlock; /*%< Covers overmem */
 109         isc_mem_t                      *mctx;
 110         dns_view_t                     *view;
 111
 112         isc_taskmgr_t                  *taskmgr;
 113         isc_task_t                     *task;
 114
 115         isc_interval_t                  tick_interval;
 116         int                             next_cleanbucket;
 117
 118         unsigned int                    irefcnt;
 119         unsigned int                    erefcnt;
 120
 121         isc_mutex_t                     mplock;
 122         isc_mempool_t                  *nmp;    /*%< dns_adbname_t */
 123         isc_mempool_t                  *nhmp;   /*%< dns_adbnamehook_t */
 124         isc_mempool_t                  *limp;   /*%< dns_adblameinfo_t */
 125         isc_mempool_t                  *emp;    /*%< dns_adbentry_t */
 126         isc_mempool_t                  *ahmp;   /*%< dns_adbfind_t */
 127         isc_mempool_t                  *aimp;   /*%< dns_adbaddrinfo_t */
 128         isc_mempool_t                  *afmp;   /*%< dns_adbfetch_t */
 129
 130         /*!
 131          * Bucketized locks and lists for names.
 132          *
 133          * XXXRTH  Have a per-bucket structure that contains all of these?
 134          */
 135         unsigned int                    nnames;
 136         isc_mutex_t                     namescntlock;
 137         unsigned int                    namescnt;
 138         dns_adbnamelist_t               *names;
 139         dns_adbnamelist_t               *deadnames;
 140         isc_mutex_t                     *namelocks;
 141         isc_boolean_t                   *name_sd;
 142         unsigned int                    *name_refcnt;
 143
 144         /*!
 145          * Bucketized locks and lists for entries.
 146          *
 147          * XXXRTH  Have a per-bucket structure that contains all of these?
 148          */
 149         unsigned int                    nentries;
 150         isc_mutex_t                     entriescntlock;
 151         unsigned int                    entriescnt;
 152         dns_adbentrylist_t              *entries;
 153         dns_adbentrylist_t              *deadentries;
 154         isc_mutex_t                     *entrylocks;
 155         isc_boolean_t                   *entry_sd; /*%< shutting down */
 156         unsigned int                    *entry_refcnt;
 157
 158         isc_event_t                     cevent;
 159         isc_boolean_t                   cevent_sent;
 160         isc_boolean_t                   shutting_down;
 161         isc_eventlist_t                 whenshutdown;
 162         isc_event_t                     growentries;
 163         isc_boolean_t                   growentries_sent;
 164         isc_event_t                     grownames;
 165         isc_boolean_t                   grownames_sent;
 166 };
 167
 168 /*
 169  * XXXMLG  Document these structures.
 170  */
 171
 172 /*% dns_adbname structure */
 173 struct dns_adbname {
 174         unsigned int                    magic;
 175         dns_name_t                      name;
 176         dns_adb_t                      *adb;
 177         unsigned int                    partial_result;
 178         unsigned int                    flags;
 179         int                             lock_bucket;
 180         dns_name_t                      target;
 181         isc_stdtime_t                   expire_target;
 182         isc_stdtime_t                   expire_v4;
 183         isc_stdtime_t                   expire_v6;
 184         unsigned int                    chains;
 185         dns_adbnamehooklist_t           v4;
 186         dns_adbnamehooklist_t           v6;
 187         dns_adbfetch_t                 *fetch_a;
 188         dns_adbfetch_t                 *fetch_aaaa;
 189         unsigned int                    fetch_err;
 190         unsigned int                    fetch6_err;
 191         dns_adbfindlist_t               finds;
 192         /* for LRU-based management */
 193         isc_stdtime_t                   last_used;
 194
 195         ISC_LINK(dns_adbname_t)         plink;
 196 };
 197
 198 /*% The adbfetch structure */
 199 struct dns_adbfetch {
 200         unsigned int                    magic;
 201         dns_fetch_t                    *fetch;
 202         dns_rdataset_t                  rdataset;
 203 };
 204
 205 /*%
 206  * This is a small widget that dangles off a dns_adbname_t.  It contains a
 207  * pointer to the address information about this host, and a link to the next
 208  * namehook that will contain the next address this host has.
 209  */
 210 struct dns_adbnamehook {
 211         unsigned int                    magic;
 212         dns_adbentry_t                 *entry;
 213         ISC_LINK(dns_adbnamehook_t)     plink;
 214 };
 215
 216 /*%
 217  * This is a small widget that holds qname-specific information about an
 218  * address.  Currently limited to lameness, but could just as easily be
 219  * extended to other types of information about zones.
 220  */
 221 struct dns_adblameinfo {
 222         unsigned int                    magic;
 223
 224         dns_name_t                      qname;
 225         dns_rdatatype_t                 qtype;
 226         isc_stdtime_t                   lame_timer;
 227
 228         ISC_LINK(dns_adblameinfo_t)     plink;
 229 };
 230
 231 /*%
 232  * An address entry.  It holds quite a bit of information about addresses,
 233  * including edns state (in "flags"), rtt, and of course the address of
 234  * the host.
 235  */
 236 struct dns_adbentry {
 237         unsigned int                    magic;
 238
 239         int                             lock_bucket;
 240         unsigned int                    refcnt;
 241
 242         unsigned int                    flags;
 243         unsigned int                    srtt;
 244         isc_sockaddr_t                  sockaddr;
 245
 246         isc_stdtime_t                   expires;
 247         /*%<
 248          * A nonzero 'expires' field indicates that the entry should
 249          * persist until that time.  This allows entries found
 250          * using dns_adb_findaddrinfo() to persist for a limited time
 251          * even though they are not necessarily associated with a
 252          * name.
 253          */
 254
 255         ISC_LIST(dns_adblameinfo_t)     lameinfo;
 256         ISC_LINK(dns_adbentry_t)        plink;
 257
 258 };
 259
 260 /*
 261  * Internal functions (and prototypes).
 262  */
 263 static inline dns_adbname_t *new_adbname(dns_adb_t *, dns_name_t *);
 264 static inline void free_adbname(dns_adb_t *, dns_adbname_t **);
 265 static inline dns_adbnamehook_t *new_adbnamehook(dns_adb_t *,
 266                                                  dns_adbentry_t *);
 267 static inline void free_adbnamehook(dns_adb_t *, dns_adbnamehook_t **);
 268 static inline dns_adblameinfo_t *new_adblameinfo(dns_adb_t *, dns_name_t *,
 269                                                  dns_rdatatype_t);
 270 static inline void free_adblameinfo(dns_adb_t *, dns_adblameinfo_t **);
 271 static inline dns_adbentry_t *new_adbentry(dns_adb_t *);
 272 static inline void free_adbentry(dns_adb_t *, dns_adbentry_t **);
 273 static inline dns_adbfind_t *new_adbfind(dns_adb_t *);
 274 static inline isc_boolean_t free_adbfind(dns_adb_t *, dns_adbfind_t **);
 275 static inline dns_adbaddrinfo_t *new_adbaddrinfo(dns_adb_t *, dns_adbentry_t *,
 276                                                  in_port_t);
 277 static inline dns_adbfetch_t *new_adbfetch(dns_adb_t *);
 278 static inline void free_adbfetch(dns_adb_t *, dns_adbfetch_t **);
 279 static inline dns_adbname_t *find_name_and_lock(dns_adb_t *, dns_name_t *,
 280                                                 unsigned int, int *);
 281 static inline dns_adbentry_t *find_entry_and_lock(dns_adb_t *,
 282                                                   isc_sockaddr_t *, int *,
 283                                                   isc_stdtime_t);
 284 static void dump_adb(dns_adb_t *, FILE *, isc_boolean_t debug, isc_stdtime_t);
 285 static void print_dns_name(FILE *, dns_name_t *);
 286 static void print_namehook_list(FILE *, const char *legend,
 287                                 dns_adbnamehooklist_t *list,
 288                                 isc_boolean_t debug,
 289                                 isc_stdtime_t now);
 290 static void print_find_list(FILE *, dns_adbname_t *);
 291 static void print_fetch_list(FILE *, dns_adbname_t *);
 292 static inline isc_boolean_t dec_adb_irefcnt(dns_adb_t *);
 293 static inline void inc_adb_irefcnt(dns_adb_t *);
 294 static inline void inc_adb_erefcnt(dns_adb_t *);
 295 static inline void inc_entry_refcnt(dns_adb_t *, dns_adbentry_t *,
 296                                     isc_boolean_t);
 297 static inline isc_boolean_t dec_entry_refcnt(dns_adb_t *, isc_boolean_t,
 298                                              dns_adbentry_t *, isc_boolean_t);
 299 static inline void violate_locking_hierarchy(isc_mutex_t *, isc_mutex_t *);
 300 static isc_boolean_t clean_namehooks(dns_adb_t *, dns_adbnamehooklist_t *);
 301 static void clean_target(dns_adb_t *, dns_name_t *);
 302 static void clean_finds_at_name(dns_adbname_t *, isc_eventtype_t,
 303                                 unsigned int);
 304 static isc_boolean_t check_expire_namehooks(dns_adbname_t *, isc_stdtime_t);
 305 static isc_boolean_t check_expire_entry(dns_adb_t *, dns_adbentry_t **,
 306                                         isc_stdtime_t);
 307 static void cancel_fetches_at_name(dns_adbname_t *);
 308 static isc_result_t dbfind_name(dns_adbname_t *, isc_stdtime_t,
 309                                 dns_rdatatype_t);
 310 static isc_result_t fetch_name(dns_adbname_t *, isc_boolean_t,
 311                                dns_rdatatype_t);
 312 static inline void check_exit(dns_adb_t *);
 313 static void destroy(dns_adb_t *);
 314 static isc_boolean_t shutdown_names(dns_adb_t *);
 315 static isc_boolean_t shutdown_entries(dns_adb_t *);
 316 static inline void link_name(dns_adb_t *, int, dns_adbname_t *);
 317 static inline isc_boolean_t unlink_name(dns_adb_t *, dns_adbname_t *);
 318 static inline void link_entry(dns_adb_t *, int, dns_adbentry_t *);
 319 static inline isc_boolean_t unlink_entry(dns_adb_t *, dns_adbentry_t *);
 320 static isc_boolean_t kill_name(dns_adbname_t **, isc_eventtype_t);
 321 static void water(void *, int);
 322 static void dump_entry(FILE *, dns_adbentry_t *, isc_boolean_t, isc_stdtime_t);
 323
 324 /*
 325  * MUST NOT overlap DNS_ADBFIND_* flags!
 326  */
 327 #define FIND_EVENT_SENT         0x40000000
 328 #define FIND_EVENT_FREED        0x80000000
 329 #define FIND_EVENTSENT(h)       (((h)->flags & FIND_EVENT_SENT) != 0)
 330 #define FIND_EVENTFREED(h)      (((h)->flags & FIND_EVENT_FREED) != 0)
 331
 332 #define NAME_NEEDS_POKE         0x80000000
 333 #define NAME_IS_DEAD            0x40000000
 334 #define NAME_HINT_OK            DNS_ADBFIND_HINTOK
 335 #define NAME_GLUE_OK            DNS_ADBFIND_GLUEOK
 336 #define NAME_STARTATZONE        DNS_ADBFIND_STARTATZONE
 337 #define NAME_DEAD(n)            (((n)->flags & NAME_IS_DEAD) != 0)
 338 #define NAME_NEEDSPOKE(n)       (((n)->flags & NAME_NEEDS_POKE) != 0)
 339 #define NAME_GLUEOK(n)          (((n)->flags & NAME_GLUE_OK) != 0)
 340 #define NAME_HINTOK(n)          (((n)->flags & NAME_HINT_OK) != 0)
 341
 342 /*
 343  * Private flag(s) for entries.
 344  * MUST NOT overlap FCTX_ADDRINFO_xxx and DNS_FETCHOPT_NOEDNS0.
 345  */
 346 #define ENTRY_IS_DEAD           0x80000000
 347
 348 /*
 349  * To the name, address classes are all that really exist.  If it has a
 350  * V6 address it doesn't care if it came from a AAAA query.
 351  */
 352 #define NAME_HAS_V4(n)          (!ISC_LIST_EMPTY((n)->v4))
 353 #define NAME_HAS_V6(n)          (!ISC_LIST_EMPTY((n)->v6))
 354 #define NAME_HAS_ADDRS(n)       (NAME_HAS_V4(n) || NAME_HAS_V6(n))
 355
 356 /*
 357  * Fetches are broken out into A and AAAA types.  In some cases,
 358  * however, it makes more sense to test for a particular class of fetches,
 359  * like V4 or V6 above.
 360  * Note: since we have removed the support of A6 in adb, FETCH_A and FETCH_AAAA
 361  * are now equal to FETCH_V4 and FETCH_V6, respectively.
 362  */
 363 #define NAME_FETCH_A(n)         ((n)->fetch_a != NULL)
 364 #define NAME_FETCH_AAAA(n)      ((n)->fetch_aaaa != NULL)
 365 #define NAME_FETCH_V4(n)        (NAME_FETCH_A(n))
 366 #define NAME_FETCH_V6(n)        (NAME_FETCH_AAAA(n))
 367 #define NAME_FETCH(n)           (NAME_FETCH_V4(n) || NAME_FETCH_V6(n))
 368
 369 /*
 370  * Find options and tests to see if there are addresses on the list.
 371  */
 372 #define FIND_WANTEVENT(fn)      (((fn)->options & DNS_ADBFIND_WANTEVENT) != 0)
 373 #define FIND_WANTEMPTYEVENT(fn) (((fn)->options & DNS_ADBFIND_EMPTYEVENT) != 0)
 374 #define FIND_AVOIDFETCHES(fn)   (((fn)->options & DNS_ADBFIND_AVOIDFETCHES) \
 375                                  != 0)
 376 #define FIND_STARTATZONE(fn)    (((fn)->options & DNS_ADBFIND_STARTATZONE) \
 377                                  != 0)
 378 #define FIND_HINTOK(fn)         (((fn)->options & DNS_ADBFIND_HINTOK) != 0)
 379 #define FIND_GLUEOK(fn)         (((fn)->options & DNS_ADBFIND_GLUEOK) != 0)
 380 #define FIND_HAS_ADDRS(fn)      (!ISC_LIST_EMPTY((fn)->list))
 381 #define FIND_RETURNLAME(fn)     (((fn)->options & DNS_ADBFIND_RETURNLAME) != 0)
 382
 383 /*
 384  * These are currently used on simple unsigned ints, so they are
 385  * not really associated with any particular type.
 386  */
 387 #define WANT_INET(x)            (((x) & DNS_ADBFIND_INET) != 0)
 388 #define WANT_INET6(x)           (((x) & DNS_ADBFIND_INET6) != 0)
 389
 390 #define EXPIRE_OK(exp, now)     ((exp == INT_MAX) || (exp < now))
 391
 392 /*
 393  * Find out if the flags on a name (nf) indicate if it is a hint or
 394  * glue, and compare this to the appropriate bits set in o, to see if
 395  * this is ok.
 396  */
 397 #define GLUE_OK(nf, o) (!NAME_GLUEOK(nf) || (((o) & DNS_ADBFIND_GLUEOK) != 0))
 398 #define HINT_OK(nf, o) (!NAME_HINTOK(nf) || (((o) & DNS_ADBFIND_HINTOK) != 0))
 399 #define GLUEHINT_OK(nf, o) (GLUE_OK(nf, o) || HINT_OK(nf, o))
 400 #define STARTATZONE_MATCHES(nf, o) (((nf)->flags & NAME_STARTATZONE) == \
 401                                     ((o) & DNS_ADBFIND_STARTATZONE))
 402
 403 #define ENTER_LEVEL             ISC_LOG_DEBUG(50)
 404 #define EXIT_LEVEL              ENTER_LEVEL
 405 #define CLEAN_LEVEL             ISC_LOG_DEBUG(100)
 406 #define DEF_LEVEL               ISC_LOG_DEBUG(5)
 407 #define NCACHE_LEVEL            ISC_LOG_DEBUG(20)
 408
 409 #define NCACHE_RESULT(r)        ((r) == DNS_R_NCACHENXDOMAIN || \
 410                                  (r) == DNS_R_NCACHENXRRSET)
 411 #define AUTH_NX(r)              ((r) == DNS_R_NXDOMAIN || \
 412                                  (r) == DNS_R_NXRRSET)
 413 #define NXDOMAIN_RESULT(r)      ((r) == DNS_R_NXDOMAIN || \
 414                                  (r) == DNS_R_NCACHENXDOMAIN)
 415 #define NXRRSET_RESULT(r)       ((r) == DNS_R_NCACHENXRRSET || \
 416                                  (r) == DNS_R_NXRRSET || \
 417                                  (r) == DNS_R_HINTNXRRSET)
 418
 419 /*
 420  * Error state rankings.
 421  */
 422
 423 #define FIND_ERR_SUCCESS                0  /* highest rank */
 424 #define FIND_ERR_CANCELED               1
 425 #define FIND_ERR_FAILURE                2
 426 #define FIND_ERR_NXDOMAIN               3
 427 #define FIND_ERR_NXRRSET                4
 428 #define FIND_ERR_UNEXPECTED             5
 429 #define FIND_ERR_NOTFOUND               6
 430 #define FIND_ERR_MAX                    7
 431
 432 static const char *errnames[] = {
 433         "success",
 434         "canceled",
 435         "failure",
 436         "nxdomain",
 437         "nxrrset",
 438         "unexpected",
 439         "not_found"
 440 };
 441
 442 #define NEWERR(old, new)        (ISC_MIN((old), (new)))
 443
 444 static isc_result_t find_err_map[FIND_ERR_MAX] = {
 445         ISC_R_SUCCESS,
 446         ISC_R_CANCELED,
 447         ISC_R_FAILURE,
 448         DNS_R_NXDOMAIN,
 449         DNS_R_NXRRSET,
 450         ISC_R_UNEXPECTED,
 451         ISC_R_NOTFOUND          /* not YET found */
 452 };
 453
 454 static void
 455 DP(int level, const char *format, ...) ISC_FORMAT_PRINTF(2, 3);
 456
 457 static void
 458 DP(int level, const char *format, ...) {
 459         va_list args;
 460
 461         va_start(args, format);
 462         isc_log_vwrite(dns_lctx,
 463                        DNS_LOGCATEGORY_DATABASE, DNS_LOGMODULE_ADB,
 464                        level, format, args);
 465         va_end(args);
 466 }
 467
 468 /*%
 469  * Increment resolver-related statistics counters.
 470  */
 471 static inline void
 472 inc_stats(dns_adb_t *adb, isc_statscounter_t counter) {
 473         if (adb->view->resstats != NULL)
 474                 isc_stats_increment(adb->view->resstats, counter);
 475 }
 476
 477 static inline dns_ttl_t
 478 ttlclamp(dns_ttl_t ttl) {
 479         if (ttl < ADB_CACHE_MINIMUM)
 480                 ttl = ADB_CACHE_MINIMUM;
 481         if (ttl > ADB_CACHE_MAXIMUM)
 482                 ttl = ADB_CACHE_MAXIMUM;
 483
 484         return (ttl);
 485 }
 486
 487 /*
 488  * Hashing is most efficient if the number of buckets is prime.
 489  * The sequence below is the closest previous primes to 2^n and
 490  * 1.5 * 2^n, for values of n from 10 to 28.  (The tables will
 491  * no longer grow beyond 2^28 entries.)
 492  */
 493 static const unsigned nbuckets[] = { 1021, 1531, 2039, 3067, 4093, 6143,
 494                                      8191, 12281, 16381, 24571, 32749,
 495                                      49193, 65521, 98299, 131071, 199603,
 496                                      262139, 393209, 524287, 768431, 1048573,
 497                                      1572853, 2097143, 3145721, 4194301,
 498                                      6291449, 8388593, 12582893, 16777213,
 499                                      25165813, 33554393, 50331599, 67108859,
 500                                      100663291, 134217689, 201326557,
 501                                      268535431, 0 };
 502
 503 static void
 504 grow_entries(isc_task_t *task, isc_event_t *ev) {
 505         dns_adb_t *adb;
 506         dns_adbentry_t *e;
 507         dns_adbentrylist_t *newdeadentries = NULL;
 508         dns_adbentrylist_t *newentries = NULL;
 509         isc_boolean_t *newentry_sd = NULL;
 510         isc_mutex_t *newentrylocks = NULL;
 511         isc_result_t result;
 512         unsigned int *newentry_refcnt = NULL;
 513         unsigned int i, n, bucket;
 514
 515         adb = ev->ev_arg;
 516         INSIST(DNS_ADB_VALID(adb));
 517
 518         isc_event_free(&ev);
 519
 520         isc_task_beginexclusive(task);
 521
 522         i = 0;
 523         while (nbuckets[i] != 0 && adb->nentries >= nbuckets[i])
 524                 i++;
 525         if (nbuckets[i] != 0)
 526                 n = nbuckets[i];
 527         else
 528                 goto done;
 529
 530         DP(ISC_LOG_INFO, "adb: grow_entries to %u starting", n);
 531
 532         /*
 533          * Are we shutting down?
 534          */
 535         for (i = 0; i < adb->nentries; i++)
 536                 if (adb->entry_sd[i])
 537                         goto cleanup;
 538
 539         /*
 540          * Grab all the resources we need.
 541          */
 542         newentries = isc_mem_get(adb->mctx, sizeof(*newentries) * n);
 543         newdeadentries = isc_mem_get(adb->mctx, sizeof(*newdeadentries) * n);
 544         newentrylocks = isc_mem_get(adb->mctx, sizeof(*newentrylocks) * n);
 545         newentry_sd = isc_mem_get(adb->mctx, sizeof(*newentry_sd) * n);
 546         newentry_refcnt = isc_mem_get(adb->mctx, sizeof(*newentry_refcnt) * n);
 547         if (newentries == NULL || newdeadentries == NULL ||
 548             newentrylocks == NULL || newentry_sd == NULL ||
 549             newentry_refcnt == NULL)
 550                 goto cleanup;
 551
 552         /*
 553          * Initialise the new resources.
 554          */
 555         result = isc_mutexblock_init(newentrylocks, n);
 556         if (result != ISC_R_SUCCESS)
 557                 goto cleanup;
 558
 559         for (i = 0; i < n; i++) {
 560                 ISC_LIST_INIT(newentries[i]);
 561                 ISC_LIST_INIT(newdeadentries[i]);
 562                 newentry_sd[i] = ISC_FALSE;
 563                 newentry_refcnt[i] = 0;
 564                 adb->irefcnt++;
 565         }
 566
 567         /*
 568          * Move entries to new arrays.
 569          */
 570         for (i = 0; i < adb->nentries; i++) {
 571                 e = ISC_LIST_HEAD(adb->entries[i]);
 572                 while (e != NULL) {
 573                         ISC_LIST_UNLINK(adb->entries[i], e, plink);
 574                         bucket = isc_sockaddr_hash(&e->sockaddr, ISC_TRUE) % n;
 575                         e->lock_bucket = bucket;
 576                         ISC_LIST_APPEND(newentries[bucket], e, plink);
 577                         INSIST(adb->entry_refcnt[i] > 0);
 578                         adb->entry_refcnt[i]--;
 579                         newentry_refcnt[bucket]++;
 580                         e = ISC_LIST_HEAD(adb->entries[i]);
 581                 }
 582                 e = ISC_LIST_HEAD(adb->deadentries[i]);
 583                 while (e != NULL) {
 584                         ISC_LIST_UNLINK(adb->deadentries[i], e, plink);
 585                         bucket = isc_sockaddr_hash(&e->sockaddr, ISC_TRUE) % n;
 586                         e->lock_bucket = bucket;
 587                         ISC_LIST_APPEND(newdeadentries[bucket], e, plink);
 588                         INSIST(adb->entry_refcnt[i] > 0);
 589                         adb->entry_refcnt[i]--;
 590                         newentry_refcnt[bucket]++;
 591                         e = ISC_LIST_HEAD(adb->deadentries[i]);
 592                 }
 593                 INSIST(adb->entry_refcnt[i] == 0);
 594                 adb->irefcnt--;
 595         }
 596
 597         /*
 598          * Cleanup old resources.
 599          */
 600         DESTROYMUTEXBLOCK(adb->entrylocks, adb->nentries);
 601         isc_mem_put(adb->mctx, adb->entries,
 602                     sizeof(*adb->entries) * adb->nentries);
 603         isc_mem_put(adb->mctx, adb->deadentries,
 604                     sizeof(*adb->deadentries) * adb->nentries);
 605         isc_mem_put(adb->mctx, adb->entrylocks,
 606                     sizeof(*adb->entrylocks) * adb->nentries);
 607         isc_mem_put(adb->mctx, adb->entry_sd,
 608                     sizeof(*adb->entry_sd) * adb->nentries);
 609         isc_mem_put(adb->mctx, adb->entry_refcnt,
 610                     sizeof(*adb->entry_refcnt) * adb->nentries);
 611
 612         /*
 613          * Install new resources.
 614          */
 615         adb->entries = newentries;
 616         adb->deadentries = newdeadentries;
 617         adb->entrylocks = newentrylocks;
 618         adb->entry_sd = newentry_sd;
 619         adb->entry_refcnt = newentry_refcnt;
 620         adb->nentries = n;
 621
 622         /*
 623          * Only on success do we set adb->growentries_sent to ISC_FALSE.
 624          * This will prevent us being continuously being called on error.
 625          */
 626         adb->growentries_sent = ISC_FALSE;
 627         goto done;
 628
 629  cleanup:
 630         if (newentries != NULL)
 631                 isc_mem_put(adb->mctx, newentries,
 632                             sizeof(*newentries) * n);
 633         if (newdeadentries != NULL)
 634                 isc_mem_put(adb->mctx, newdeadentries,
 635                             sizeof(*newdeadentries) * n);
 636         if (newentrylocks != NULL)
 637                 isc_mem_put(adb->mctx, newentrylocks,
 638                             sizeof(*newentrylocks) * n);
 639         if (newentry_sd != NULL)
 640                 isc_mem_put(adb->mctx, newentry_sd,
 641                             sizeof(*newentry_sd) * n);
 642         if (newentry_refcnt != NULL)
 643                 isc_mem_put(adb->mctx, newentry_refcnt,
 644                              sizeof(*newentry_refcnt) * n);
 645  done:
 646         isc_task_endexclusive(task);
 647
 648         LOCK(&adb->lock);
 649         if (dec_adb_irefcnt(adb))
 650                 check_exit(adb);
 651         UNLOCK(&adb->lock);
 652         DP(ISC_LOG_INFO, "adb: grow_entries finished");
 653 }
 654
 655 static void
 656 grow_names(isc_task_t *task, isc_event_t *ev) {
 657         dns_adb_t *adb;
 658         dns_adbname_t *name;
 659         dns_adbnamelist_t *newdeadnames = NULL;
 660         dns_adbnamelist_t *newnames = NULL;
 661         isc_boolean_t *newname_sd = NULL;
 662         isc_mutex_t *newnamelocks = NULL;
 663         isc_result_t result;
 664         unsigned int *newname_refcnt = NULL;
 665         unsigned int i, n, bucket;
 666
 667         adb = ev->ev_arg;
 668         INSIST(DNS_ADB_VALID(adb));
 669
 670         isc_event_free(&ev);
 671
 672         isc_task_beginexclusive(task);
 673
 674         i = 0;
 675         while (nbuckets[i] != 0 && adb->nnames >= nbuckets[i])
 676                 i++;
 677         if (nbuckets[i] != 0)
 678                 n = nbuckets[i];
 679         else
 680                 goto done;
 681
 682         DP(ISC_LOG_INFO, "adb: grow_names to %u starting", n);
 683
 684         /*
 685          * Are we shutting down?
 686          */
 687         for (i = 0; i < adb->nnames; i++)
 688                 if (adb->name_sd[i])
 689                         goto cleanup;
 690
 691         /*
 692          * Grab all the resources we need.
 693          */
 694         newnames = isc_mem_get(adb->mctx, sizeof(*newnames) * n);
 695         newdeadnames = isc_mem_get(adb->mctx, sizeof(*newdeadnames) * n);
 696         newnamelocks = isc_mem_get(adb->mctx, sizeof(*newnamelocks) * n);
 697         newname_sd = isc_mem_get(adb->mctx, sizeof(*newname_sd) * n);
 698         newname_refcnt = isc_mem_get(adb->mctx, sizeof(*newname_refcnt) * n);
 699         if (newnames == NULL || newdeadnames == NULL ||
 700             newnamelocks == NULL || newname_sd == NULL ||
 701             newname_refcnt == NULL)
 702                 goto cleanup;
 703
 704         /*
 705          * Initialise the new resources.
 706          */
 707         result = isc_mutexblock_init(newnamelocks, n);
 708         if (result != ISC_R_SUCCESS)
 709                 goto cleanup;
 710
 711         for (i = 0; i < n; i++) {
 712                 ISC_LIST_INIT(newnames[i]);
 713                 ISC_LIST_INIT(newdeadnames[i]);
 714                 newname_sd[i] = ISC_FALSE;
 715                 newname_refcnt[i] = 0;
 716                 adb->irefcnt++;
 717         }
 718
 719         /*
 720          * Move names to new arrays.
 721          */
 722         for (i = 0; i < adb->nnames; i++) {
 723                 name = ISC_LIST_HEAD(adb->names[i]);
 724                 while (name != NULL) {
 725                         ISC_LIST_UNLINK(adb->names[i], name, plink);
 726                         bucket = dns_name_fullhash(&name->name, ISC_TRUE) % n;
 727                         name->lock_bucket = bucket;
 728                         ISC_LIST_APPEND(newnames[bucket], name, plink);
 729                         INSIST(adb->name_refcnt[i] > 0);
 730                         adb->name_refcnt[i]--;
 731                         newname_refcnt[bucket]++;
 732                         name = ISC_LIST_HEAD(adb->names[i]);
 733                 }
 734                 name = ISC_LIST_HEAD(adb->deadnames[i]);
 735                 while (name != NULL) {
 736                         ISC_LIST_UNLINK(adb->deadnames[i], name, plink);
 737                         bucket = dns_name_fullhash(&name->name, ISC_TRUE) % n;
 738                         name->lock_bucket = bucket;
 739                         ISC_LIST_APPEND(newdeadnames[bucket], name, plink);
 740                         INSIST(adb->name_refcnt[i] > 0);
 741                         adb->name_refcnt[i]--;
 742                         newname_refcnt[bucket]++;
 743                         name = ISC_LIST_HEAD(adb->deadnames[i]);
 744                 }
 745                 INSIST(adb->name_refcnt[i] == 0);
 746                 adb->irefcnt--;
 747         }
 748
 749         /*
 750          * Cleanup old resources.
 751          */
 752         DESTROYMUTEXBLOCK(adb->namelocks, adb->nnames);
 753         isc_mem_put(adb->mctx, adb->names,
 754                     sizeof(*adb->names) * adb->nnames);
 755         isc_mem_put(adb->mctx, adb->deadnames,
 756                     sizeof(*adb->deadnames) * adb->nnames);
 757         isc_mem_put(adb->mctx, adb->namelocks,
 758                     sizeof(*adb->namelocks) * adb->nnames);
 759         isc_mem_put(adb->mctx, adb->name_sd,
 760                     sizeof(*adb->name_sd) * adb->nnames);
 761         isc_mem_put(adb->mctx, adb->name_refcnt,
 762                     sizeof(*adb->name_refcnt) * adb->nnames);
 763
 764         /*
 765          * Install new resources.
 766          */
 767         adb->names = newnames;
 768         adb->deadnames = newdeadnames;
 769         adb->namelocks = newnamelocks;
 770         adb->name_sd = newname_sd;
 771         adb->name_refcnt = newname_refcnt;
 772         adb->nnames = n;
 773
 774         /*
 775          * Only on success do we set adb->grownames_sent to ISC_FALSE.
 776          * This will prevent us being continuously being called on error.
 777          */
 778         adb->grownames_sent = ISC_FALSE;
 779         goto done;
 780
 781  cleanup:
 782         if (newnames != NULL)
 783                 isc_mem_put(adb->mctx, newnames, sizeof(*newnames) * n);
 784         if (newdeadnames != NULL)
 785                 isc_mem_put(adb->mctx, newdeadnames, sizeof(*newdeadnames) * n);
 786         if (newnamelocks != NULL)
 787                 isc_mem_put(adb->mctx, newnamelocks, sizeof(*newnamelocks) * n);
 788         if (newname_sd != NULL)
 789                 isc_mem_put(adb->mctx, newname_sd, sizeof(*newname_sd) * n);
 790         if (newname_refcnt != NULL)
 791                 isc_mem_put(adb->mctx, newname_refcnt,
 792                              sizeof(*newname_refcnt) * n);
 793  done:
 794         isc_task_endexclusive(task);
 795
 796         LOCK(&adb->lock);
 797         if (dec_adb_irefcnt(adb))
 798                 check_exit(adb);
 799         UNLOCK(&adb->lock);
 800         DP(ISC_LOG_INFO, "adb: grow_names finished");
 801 }
 802
 803 /*
 804  * Requires the adbname bucket be locked and that no entry buckets be locked.
 805  *
 806  * This code handles A and AAAA rdatasets only.
 807  */
 808 static isc_result_t
 809 import_rdataset(dns_adbname_t *adbname, dns_rdataset_t *rdataset,
 810                 isc_stdtime_t now)
 811 {
 812         isc_result_t result;
 813         dns_adb_t *adb;
 814         dns_adbnamehook_t *nh;
 815         dns_adbnamehook_t *anh;
 816         dns_rdata_t rdata = DNS_RDATA_INIT;
 817         struct in_addr ina;
 818         struct in6_addr in6a;
 819         isc_sockaddr_t sockaddr;
 820         dns_adbentry_t *foundentry;  /* NO CLEAN UP! */
 821         int addr_bucket;
 822         isc_boolean_t new_addresses_added;
 823         dns_rdatatype_t rdtype;
 824         unsigned int findoptions;
 825         dns_adbnamehooklist_t *hookhead;
 826
 827         INSIST(DNS_ADBNAME_VALID(adbname));
 828         adb = adbname->adb;
 829         INSIST(DNS_ADB_VALID(adb));
 830
 831         rdtype = rdataset->type;
 832         INSIST((rdtype == dns_rdatatype_a) || (rdtype == dns_rdatatype_aaaa));
 833         if (rdtype == dns_rdatatype_a)
 834                 findoptions = DNS_ADBFIND_INET;
 835         else
 836                 findoptions = DNS_ADBFIND_INET6;
 837
 838         addr_bucket = DNS_ADB_INVALIDBUCKET;
 839         new_addresses_added = ISC_FALSE;
 840
 841         nh = NULL;
 842         result = dns_rdataset_first(rdataset);
 843         while (result == ISC_R_SUCCESS) {
 844                 dns_rdata_reset(&rdata);
 845                 dns_rdataset_current(rdataset, &rdata);
 846                 if (rdtype == dns_rdatatype_a) {
 847                         INSIST(rdata.length == 4);
 848                         memcpy(&ina.s_addr, rdata.data, 4);
 849                         isc_sockaddr_fromin(&sockaddr, &ina, 0);
 850                         hookhead = &adbname->v4;
 851                 } else {
 852                         INSIST(rdata.length == 16);
 853                         memcpy(in6a.s6_addr, rdata.data, 16);
 854                         isc_sockaddr_fromin6(&sockaddr, &in6a, 0);
 855                         hookhead = &adbname->v6;
 856                 }
 857
 858                 INSIST(nh == NULL);
 859                 nh = new_adbnamehook(adb, NULL);
 860                 if (nh == NULL) {
 861                         adbname->partial_result |= findoptions;
 862                         result = ISC_R_NOMEMORY;
 863                         goto fail;
 864                 }
 865
 866                 foundentry = find_entry_and_lock(adb, &sockaddr, &addr_bucket,
 867                                                  now);
 868                 if (foundentry == NULL) {
 869                         dns_adbentry_t *entry;
 870
 871                         entry = new_adbentry(adb);
 872                         if (entry == NULL) {
 873                                 adbname->partial_result |= findoptions;
 874                                 result = ISC_R_NOMEMORY;
 875                                 goto fail;
 876                         }
 877
 878                         entry->sockaddr = sockaddr;
 879                         entry->refcnt = 1;
 880
 881                         nh->entry = entry;
 882
 883                         link_entry(adb, addr_bucket, entry);
 884                 } else {
 885                         for (anh = ISC_LIST_HEAD(*hookhead);
 886                              anh != NULL;
 887                              anh = ISC_LIST_NEXT(anh, plink))
 888                                 if (anh->entry == foundentry)
 889                                         break;
 890                         if (anh == NULL) {
 891                                 foundentry->refcnt++;
 892                                 nh->entry = foundentry;
 893                         } else
 894                                 free_adbnamehook(adb, &nh);
 895                 }
 896
 897                 new_addresses_added = ISC_TRUE;
 898                 if (nh != NULL)
 899                         ISC_LIST_APPEND(*hookhead, nh, plink);
 900                 nh = NULL;
 901                 result = dns_rdataset_next(rdataset);
 902         }
 903
 904  fail:
 905         if (nh != NULL)
 906                 free_adbnamehook(adb, &nh);
 907
 908         if (addr_bucket != DNS_ADB_INVALIDBUCKET)
 909                 UNLOCK(&adb->entrylocks[addr_bucket]);
 910
 911         if (rdataset->trust == dns_trust_glue ||
 912             rdataset->trust == dns_trust_additional)
 913                 rdataset->ttl = ADB_CACHE_MINIMUM;
 914         else if (rdataset->trust == dns_trust_ultimate)
 915                 rdataset->ttl = 0;
 916         else
 917                 rdataset->ttl = ttlclamp(rdataset->ttl);
 918
 919         if (rdtype == dns_rdatatype_a) {
 920                 DP(NCACHE_LEVEL, "expire_v4 set to MIN(%u,%u) import_rdataset",
 921                    adbname->expire_v4, now + rdataset->ttl);
 922                 adbname->expire_v4 = ISC_MIN(adbname->expire_v4,
 923                                              now + rdataset->ttl);
 924         } else {
 925                 DP(NCACHE_LEVEL, "expire_v6 set to MIN(%u,%u) import_rdataset",
 926                    adbname->expire_v6, now + rdataset->ttl);
 927                 adbname->expire_v6 = ISC_MIN(adbname->expire_v6,
 928                                              now + rdataset->ttl);
 929         }
 930
 931         if (new_addresses_added) {
 932                 /*
 933                  * Lie a little here.  This is more or less so code that cares
 934                  * can find out if any new information was added or not.
 935                  */
 936                 return (ISC_R_SUCCESS);
 937         }
 938
 939         return (result);
 940 }
 941
 942 /*
 943  * Requires the name's bucket be locked.
 944  */
 945 static isc_boolean_t
 946 kill_name(dns_adbname_t **n, isc_eventtype_t ev) {
 947         dns_adbname_t *name;
 948         isc_boolean_t result = ISC_FALSE;
 949         isc_boolean_t result4, result6;
 950         int bucket;
 951         dns_adb_t *adb;
 952
 953         INSIST(n != NULL);
 954         name = *n;
 955         *n = NULL;
 956         INSIST(DNS_ADBNAME_VALID(name));
 957         adb = name->adb;
 958         INSIST(DNS_ADB_VALID(adb));
 959
 960         DP(DEF_LEVEL, "killing name %p", name);
 961
 962         /*
 963          * If we're dead already, just check to see if we should go
 964          * away now or not.
 965          */
 966         if (NAME_DEAD(name) && !NAME_FETCH(name)) {
 967                 result = unlink_name(adb, name);
 968                 free_adbname(adb, &name);
 969                 if (result)
 970                         result = dec_adb_irefcnt(adb);
 971                 return (result);
 972         }
 973
 974         /*
 975          * Clean up the name's various lists.  These two are destructive
 976          * in that they will always empty the list.
 977          */
 978         clean_finds_at_name(name, ev, DNS_ADBFIND_ADDRESSMASK);
 979         result4 = clean_namehooks(adb, &name->v4);
 980         result6 = clean_namehooks(adb, &name->v6);
 981         clean_target(adb, &name->target);
 982         result = ISC_TF(result4 || result6);
 983
 984         /*
 985          * If fetches are running, cancel them.  If none are running, we can
 986          * just kill the name here.
 987          */
 988         if (!NAME_FETCH(name)) {
 989                 INSIST(result == ISC_FALSE);
 990                 result = unlink_name(adb, name);
 991                 free_adbname(adb, &name);
 992                 if (result)
 993                         result = dec_adb_irefcnt(adb);
 994         } else {
 995                 cancel_fetches_at_name(name);
 996                 if (!NAME_DEAD(name)) {
 997                         bucket = name->lock_bucket;
 998                         ISC_LIST_UNLINK(adb->names[bucket], name, plink);
 999                         ISC_LIST_APPEND(adb->deadnames[bucket], name, plink);
1000                         name->flags |= NAME_IS_DEAD;
1001                 }
1002         }
1003         return (result);
1004 }
1005
1006 /*
1007  * Requires the name's bucket be locked and no entry buckets be locked.
1008  */
1009 static isc_boolean_t
1010 check_expire_namehooks(dns_adbname_t *name, isc_stdtime_t now) {
1011         dns_adb_t *adb;
1012         isc_boolean_t result4 = ISC_FALSE;
1013         isc_boolean_t result6 = ISC_FALSE;
1014
1015         INSIST(DNS_ADBNAME_VALID(name));
1016         adb = name->adb;
1017         INSIST(DNS_ADB_VALID(adb));
1018
1019         /*
1020          * Check to see if we need to remove the v4 addresses
1021          */
1022         if (!NAME_FETCH_V4(name) && EXPIRE_OK(name->expire_v4, now)) {
1023                 if (NAME_HAS_V4(name)) {
1024                         DP(DEF_LEVEL, "expiring v4 for name %p", name);
1025                         result4 = clean_namehooks(adb, &name->v4);
1026                         name->partial_result &= ~DNS_ADBFIND_INET;
1027                 }
1028                 name->expire_v4 = INT_MAX;
1029                 name->fetch_err = FIND_ERR_UNEXPECTED;
1030         }
1031
1032         /*
1033          * Check to see if we need to remove the v6 addresses
1034          */
1035         if (!NAME_FETCH_V6(name) && EXPIRE_OK(name->expire_v6, now)) {
1036                 if (NAME_HAS_V6(name)) {
1037                         DP(DEF_LEVEL, "expiring v6 for name %p", name);
1038                         result6 = clean_namehooks(adb, &name->v6);
1039                         name->partial_result &= ~DNS_ADBFIND_INET6;
1040                 }
1041                 name->expire_v6 = INT_MAX;
1042                 name->fetch6_err = FIND_ERR_UNEXPECTED;
1043         }
1044
1045         /*
1046          * Check to see if we need to remove the alias target.
1047          */
1048         if (EXPIRE_OK(name->expire_target, now)) {
1049                 clean_target(adb, &name->target);
1050                 name->expire_target = INT_MAX;
1051         }
1052         return (ISC_TF(result4 || result6));
1053 }
1054
1055 /*
1056  * Requires the name's bucket be locked.
1057  */
1058 static inline void
1059 link_name(dns_adb_t *adb, int bucket, dns_adbname_t *name) {
1060         INSIST(name->lock_bucket == DNS_ADB_INVALIDBUCKET);
1061
1062         ISC_LIST_PREPEND(adb->names[bucket], name, plink);
1063         name->lock_bucket = bucket;
1064         adb->name_refcnt[bucket]++;
1065 }
1066
1067 /*
1068  * Requires the name's bucket be locked.
1069  */
1070 static inline isc_boolean_t
1071 unlink_name(dns_adb_t *adb, dns_adbname_t *name) {
1072         int bucket;
1073         isc_boolean_t result = ISC_FALSE;
1074
1075         bucket = name->lock_bucket;
1076         INSIST(bucket != DNS_ADB_INVALIDBUCKET);
1077
1078         if (NAME_DEAD(name))
1079                 ISC_LIST_UNLINK(adb->deadnames[bucket], name, plink);
1080         else
1081                 ISC_LIST_UNLINK(adb->names[bucket], name, plink);
1082         name->lock_bucket = DNS_ADB_INVALIDBUCKET;
1083         INSIST(adb->name_refcnt[bucket] > 0);
1084         adb->name_refcnt[bucket]--;
1085         if (adb->name_sd[bucket] && adb->name_refcnt[bucket] == 0)
1086                 result = ISC_TRUE;
1087         return (result);
1088 }
1089
1090 /*
1091  * Requires the entry's bucket be locked.
1092  */
1093 static inline void
1094 link_entry(dns_adb_t *adb, int bucket, dns_adbentry_t *entry) {
1095         int i;
1096         dns_adbentry_t *e;
1097
1098         if (isc_mem_isovermem(adb->mctx)) {
1099                 for (i = 0; i < 2; i++) {
1100                         e = ISC_LIST_TAIL(adb->entries[bucket]);
1101                         if (e == NULL)
1102                                 break;
1103                         if (e->refcnt == 0) {
1104                                 unlink_entry(adb, e);
1105                                 free_adbentry(adb, &e);
1106                                 continue;
1107                         }
1108                         INSIST((e->flags & ENTRY_IS_DEAD) == 0);
1109                         e->flags |= ENTRY_IS_DEAD;
1110                         ISC_LIST_UNLINK(adb->entries[bucket], e, plink);
1111                         ISC_LIST_PREPEND(adb->deadentries[bucket], e, plink);
1112                 }
1113         }
1114
1115         ISC_LIST_PREPEND(adb->entries[bucket], entry, plink);
1116         entry->lock_bucket = bucket;
1117         adb->entry_refcnt[bucket]++;
1118 }
1119
1120 /*
1121  * Requires the entry's bucket be locked.
1122  */
1123 static inline isc_boolean_t
1124 unlink_entry(dns_adb_t *adb, dns_adbentry_t *entry) {
1125         int bucket;
1126         isc_boolean_t result = ISC_FALSE;
1127
1128         bucket = entry->lock_bucket;
1129         INSIST(bucket != DNS_ADB_INVALIDBUCKET);
1130
1131         if ((entry->flags & ENTRY_IS_DEAD) != 0)
1132                 ISC_LIST_UNLINK(adb->deadentries[bucket], entry, plink);
1133         else
1134                 ISC_LIST_UNLINK(adb->entries[bucket], entry, plink);
1135         entry->lock_bucket = DNS_ADB_INVALIDBUCKET;
1136         INSIST(adb->entry_refcnt[bucket] > 0);
1137         adb->entry_refcnt[bucket]--;
1138         if (adb->entry_sd[bucket] && adb->entry_refcnt[bucket] == 0)
1139                 result = ISC_TRUE;
1140         return (result);
1141 }
1142
1143 static inline void
1144 violate_locking_hierarchy(isc_mutex_t *have, isc_mutex_t *want) {
1145         if (isc_mutex_trylock(want) != ISC_R_SUCCESS) {
1146                 UNLOCK(have);
1147                 LOCK(want);
1148                 LOCK(have);
1149         }
1150 }
1151
1152 /*
1153  * The ADB _MUST_ be locked before calling.  Also, exit conditions must be
1154  * checked after calling this function.
1155  */
1156 static isc_boolean_t
1157 shutdown_names(dns_adb_t *adb) {
1158         unsigned int bucket;
1159         isc_boolean_t result = ISC_FALSE;
1160         dns_adbname_t *name;
1161         dns_adbname_t *next_name;
1162
1163         for (bucket = 0; bucket < adb->nnames; bucket++) {
1164                 LOCK(&adb->namelocks[bucket]);
1165                 adb->name_sd[bucket] = ISC_TRUE;
1166
1167                 name = ISC_LIST_HEAD(adb->names[bucket]);
1168                 if (name == NULL) {
1169                         /*
1170                          * This bucket has no names.  We must decrement the
1171                          * irefcnt ourselves, since it will not be
1172                          * automatically triggered by a name being unlinked.
1173                          */
1174                         INSIST(result == ISC_FALSE);
1175                         result = dec_adb_irefcnt(adb);
1176                 } else {
1177                         /*
1178                          * Run through the list.  For each name, clean up finds
1179                          * found there, and cancel any fetches running.  When
1180                          * all the fetches are canceled, the name will destroy
1181                          * itself.
1182                          */
1183                         while (name != NULL) {
1184                                 next_name = ISC_LIST_NEXT(name, plink);
1185                                 INSIST(result == ISC_FALSE);
1186                                 result = kill_name(&name,
1187                                                    DNS_EVENT_ADBSHUTDOWN);
1188                                 name = next_name;
1189                         }
1190                 }
1191
1192                 UNLOCK(&adb->namelocks[bucket]);
1193         }
1194         return (result);
1195 }
1196
1197 /*
1198  * The ADB _MUST_ be locked before calling.  Also, exit conditions must be
1199  * checked after calling this function.
1200  */
1201 static isc_boolean_t
1202 shutdown_entries(dns_adb_t *adb) {
1203         unsigned int bucket;
1204         isc_boolean_t result = ISC_FALSE;
1205         dns_adbentry_t *entry;
1206         dns_adbentry_t *next_entry;
1207
1208         for (bucket = 0; bucket < adb->nentries; bucket++) {
1209                 LOCK(&adb->entrylocks[bucket]);
1210                 adb->entry_sd[bucket] = ISC_TRUE;
1211
1212                 entry = ISC_LIST_HEAD(adb->entries[bucket]);
1213                 if (adb->entry_refcnt[bucket] == 0) {
1214                         /*
1215                          * This bucket has no entries.  We must decrement the
1216                          * irefcnt ourselves, since it will not be
1217                          * automatically triggered by an entry being unlinked.
1218                          */
1219                         result = dec_adb_irefcnt(adb);
1220                 } else {
1221                         /*
1222                          * Run through the list.  Cleanup any entries not
1223                          * associated with names, and which are not in use.
1224                          */
1225                         while (entry != NULL) {
1226                                 next_entry = ISC_LIST_NEXT(entry, plink);
1227                                 if (entry->refcnt == 0 &&
1228                                     entry->expires != 0) {
1229                                         result = unlink_entry(adb, entry);
1230                                         free_adbentry(adb, &entry);
1231                                         if (result)
1232                                                 result = dec_adb_irefcnt(adb);
1233                                 }
1234                                 entry = next_entry;
1235                         }
1236                 }
1237
1238                 UNLOCK(&adb->entrylocks[bucket]);
1239         }
1240         return (result);
1241 }
1242
1243 /*
1244  * Name bucket must be locked
1245  */
1246 static void
1247 cancel_fetches_at_name(dns_adbname_t *name) {
1248         if (NAME_FETCH_A(name))
1249             dns_resolver_cancelfetch(name->fetch_a->fetch);
1250
1251         if (NAME_FETCH_AAAA(name))
1252             dns_resolver_cancelfetch(name->fetch_aaaa->fetch);
1253 }
1254
1255 /*
1256  * Assumes the name bucket is locked.
1257  */
1258 static isc_boolean_t
1259 clean_namehooks(dns_adb_t *adb, dns_adbnamehooklist_t *namehooks) {
1260         dns_adbentry_t *entry;
1261         dns_adbnamehook_t *namehook;
1262         int addr_bucket;
1263         isc_boolean_t result = ISC_FALSE;
1264         isc_boolean_t overmem = isc_mem_isovermem(adb->mctx);
1265
1266         addr_bucket = DNS_ADB_INVALIDBUCKET;
1267         namehook = ISC_LIST_HEAD(*namehooks);
1268         while (namehook != NULL) {
1269                 INSIST(DNS_ADBNAMEHOOK_VALID(namehook));
1270
1271                 /*
1272                  * Clean up the entry if needed.
1273                  */
1274                 entry = namehook->entry;
1275                 if (entry != NULL) {
1276                         INSIST(DNS_ADBENTRY_VALID(entry));
1277
1278                         if (addr_bucket != entry->lock_bucket) {
1279                                 if (addr_bucket != DNS_ADB_INVALIDBUCKET)
1280                                         UNLOCK(&adb->entrylocks[addr_bucket]);
1281                                 addr_bucket = entry->lock_bucket;
1282                                 LOCK(&adb->entrylocks[addr_bucket]);
1283                         }
1284
1285                         result = dec_entry_refcnt(adb, overmem, entry,
1286                                                   ISC_FALSE);
1287                 }
1288
1289                 /*
1290                  * Free the namehook
1291                  */
1292                 namehook->entry = NULL;
1293                 ISC_LIST_UNLINK(*namehooks, namehook, plink);
1294                 free_adbnamehook(adb, &namehook);
1295
1296                 namehook = ISC_LIST_HEAD(*namehooks);
1297         }
1298
1299         if (addr_bucket != DNS_ADB_INVALIDBUCKET)
1300                 UNLOCK(&adb->entrylocks[addr_bucket]);
1301         return (result);
1302 }
1303
1304 static void
1305 clean_target(dns_adb_t *adb, dns_name_t *target) {
1306         if (dns_name_countlabels(target) > 0) {
1307                 dns_name_free(target, adb->mctx);
1308                 dns_name_init(target, NULL);
1309         }
1310 }
1311
1312 static isc_result_t
1313 set_target(dns_adb_t *adb, dns_name_t *name, dns_name_t *fname,
1314            dns_rdataset_t *rdataset, dns_name_t *target)
1315 {
1316         isc_result_t result;
1317         dns_namereln_t namereln;
1318         unsigned int nlabels;
1319         int order;
1320         dns_rdata_t rdata = DNS_RDATA_INIT;
1321         dns_fixedname_t fixed1, fixed2;
1322         dns_name_t *prefix, *new_target;
1323
1324         REQUIRE(dns_name_countlabels(target) == 0);
1325
1326         if (rdataset->type == dns_rdatatype_cname) {
1327                 dns_rdata_cname_t cname;
1328
1329                 /*
1330                  * Copy the CNAME's target into the target name.
1331                  */
1332                 result = dns_rdataset_first(rdataset);
1333                 if (result != ISC_R_SUCCESS)
1334                         return (result);
1335                 dns_rdataset_current(rdataset, &rdata);
1336                 result = dns_rdata_tostruct(&rdata, &cname, NULL);
1337                 if (result != ISC_R_SUCCESS)
1338                         return (result);
1339                 result = dns_name_dup(&cname.cname, adb->mctx, target);
1340                 dns_rdata_freestruct(&cname);
1341                 if (result != ISC_R_SUCCESS)
1342                         return (result);
1343         } else {
1344                 dns_rdata_dname_t dname;
1345
1346                 INSIST(rdataset->type == dns_rdatatype_dname);
1347                 namereln = dns_name_fullcompare(name, fname, &order, &nlabels);
1348                 INSIST(namereln == dns_namereln_subdomain);
1349                 /*
1350                  * Get the target name of the DNAME.
1351                  */
1352                 result = dns_rdataset_first(rdataset);
1353                 if (result != ISC_R_SUCCESS)
1354                         return (result);
1355                 dns_rdataset_current(rdataset, &rdata);
1356                 result = dns_rdata_tostruct(&rdata, &dname, NULL);
1357                 if (result != ISC_R_SUCCESS)
1358                         return (result);
1359                 /*
1360                  * Construct the new target name.
1361                  */
1362                 dns_fixedname_init(&fixed1);
1363                 prefix = dns_fixedname_name(&fixed1);
1364                 dns_fixedname_init(&fixed2);
1365                 new_target = dns_fixedname_name(&fixed2);
1366                 dns_name_split(name, nlabels, prefix, NULL);
1367                 result = dns_name_concatenate(prefix, &dname.dname, new_target,
1368                                               NULL);
1369                 dns_rdata_freestruct(&dname);
1370                 if (result != ISC_R_SUCCESS)
1371                         return (result);
1372                 result = dns_name_dup(new_target, adb->mctx, target);
1373                 if (result != ISC_R_SUCCESS)
1374                         return (result);
1375         }
1376
1377         return (ISC_R_SUCCESS);
1378 }
1379
1380 /*
1381  * Assumes nothing is locked, since this is called by the client.
1382  */
1383 static void
1384 event_free(isc_event_t *event) {
1385         dns_adbfind_t *find;
1386
1387         INSIST(event != NULL);
1388         find = event->ev_destroy_arg;
1389         INSIST(DNS_ADBFIND_VALID(find));
1390
1391         LOCK(&find->lock);
1392         find->flags |= FIND_EVENT_FREED;
1393         event->ev_destroy_arg = NULL;
1394         UNLOCK(&find->lock);
1395 }
1396
1397 /*
1398  * Assumes the name bucket is locked.
1399  */
1400 static void
1401 clean_finds_at_name(dns_adbname_t *name, isc_eventtype_t evtype,
1402                     unsigned int addrs)
1403 {
1404         isc_event_t *ev;
1405         isc_task_t *task;
1406         dns_adbfind_t *find;
1407         dns_adbfind_t *next_find;
1408         isc_boolean_t process;
1409         unsigned int wanted, notify;
1410
1411         DP(ENTER_LEVEL,
1412            "ENTER clean_finds_at_name, name %p, evtype %08x, addrs %08x",
1413            name, evtype, addrs);
1414
1415         find = ISC_LIST_HEAD(name->finds);
1416         while (find != NULL) {
1417                 LOCK(&find->lock);
1418                 next_find = ISC_LIST_NEXT(find, plink);
1419
1420                 process = ISC_FALSE;
1421                 wanted = find->flags & DNS_ADBFIND_ADDRESSMASK;
1422                 notify = wanted & addrs;
1423
1424                 switch (evtype) {
1425                 case DNS_EVENT_ADBMOREADDRESSES:
1426                         DP(ISC_LOG_DEBUG(3), "DNS_EVENT_ADBMOREADDRESSES");
1427                         if ((notify) != 0) {
1428                                 find->flags &= ~addrs;
1429                                 process = ISC_TRUE;
1430                         }
1431                         break;
1432                 case DNS_EVENT_ADBNOMOREADDRESSES:
1433                         DP(ISC_LOG_DEBUG(3), "DNS_EVENT_ADBNOMOREADDRESSES");
1434                         find->flags &= ~addrs;
1435                         wanted = find->flags & DNS_ADBFIND_ADDRESSMASK;
1436                         if (wanted == 0)
1437                                 process = ISC_TRUE;
1438                         break;
1439                 default:
1440                         find->flags &= ~addrs;
1441                         process = ISC_TRUE;
1442                 }
1443
1444                 if (process) {
1445                         DP(DEF_LEVEL, "cfan: processing find %p", find);
1446                         /*
1447                          * Unlink the find from the name, letting the caller
1448                          * call dns_adb_destroyfind() on it to clean it up
1449                          * later.
1450                          */
1451                         ISC_LIST_UNLINK(name->finds, find, plink);
1452                         find->adbname = NULL;
1453                         find->name_bucket = DNS_ADB_INVALIDBUCKET;
1454
1455                         INSIST(!FIND_EVENTSENT(find));
1456
1457                         ev = &find->event;
1458                         task = ev->ev_sender;
1459                         ev->ev_sender = find;
1460                         find->result_v4 = find_err_map[name->fetch_err];
1461                         find->result_v6 = find_err_map[name->fetch6_err];
1462                         ev->ev_type = evtype;
1463                         ev->ev_destroy = event_free;
1464                         ev->ev_destroy_arg = find;
1465
1466                         DP(DEF_LEVEL,
1467                            "sending event %p to task %p for find %p",
1468                            ev, task, find);
1469
1470                         isc_task_sendanddetach(&task, (isc_event_t **)&ev);
1471                 } else {
1472                         DP(DEF_LEVEL, "cfan: skipping find %p", find);
1473                 }
1474
1475                 UNLOCK(&find->lock);
1476                 find = next_find;
1477         }
1478
1479         DP(ENTER_LEVEL, "EXIT clean_finds_at_name, name %p", name);
1480 }
1481
1482 static inline void
1483 check_exit(dns_adb_t *adb) {
1484         isc_event_t *event;
1485         /*
1486          * The caller must be holding the adb lock.
1487          */
1488         if (adb->shutting_down) {
1489                 /*
1490                  * If there aren't any external references either, we're
1491                  * done.  Send the control event to initiate shutdown.
1492                  */
1493                 INSIST(!adb->cevent_sent);      /* Sanity check. */
1494                 event = &adb->cevent;
1495                 isc_task_send(adb->task, &event);
1496                 adb->cevent_sent = ISC_TRUE;
1497         }
1498 }
1499
1500 static inline isc_boolean_t
1501 dec_adb_irefcnt(dns_adb_t *adb) {
1502         isc_event_t *event;
1503         isc_task_t *etask;
1504         isc_boolean_t result = ISC_FALSE;
1505
1506         LOCK(&adb->reflock);
1507
1508         INSIST(adb->irefcnt > 0);
1509         adb->irefcnt--;
1510
1511         if (adb->irefcnt == 0) {
1512                 event = ISC_LIST_HEAD(adb->whenshutdown);
1513                 while (event != NULL) {
1514                         ISC_LIST_UNLINK(adb->whenshutdown, event, ev_link);
1515                         etask = event->ev_sender;
1516                         event->ev_sender = adb;
1517                         isc_task_sendanddetach(&etask, &event);
1518                         event = ISC_LIST_HEAD(adb->whenshutdown);
1519                 }
1520         }
1521
1522         if (adb->irefcnt == 0 && adb->erefcnt == 0)
1523                 result = ISC_TRUE;
1524         UNLOCK(&adb->reflock);
1525         return (result);
1526 }
1527
1528 static inline void
1529 inc_adb_irefcnt(dns_adb_t *adb) {
1530         LOCK(&adb->reflock);
1531         adb->irefcnt++;
1532         UNLOCK(&adb->reflock);
1533 }
1534
1535 static inline void
1536 inc_adb_erefcnt(dns_adb_t *adb) {
1537         LOCK(&adb->reflock);
1538         adb->erefcnt++;
1539         UNLOCK(&adb->reflock);
1540 }
1541
1542 static inline void
1543 inc_entry_refcnt(dns_adb_t *adb, dns_adbentry_t *entry, isc_boolean_t lock) {
1544         int bucket;
1545
1546         bucket = entry->lock_bucket;
1547
1548         if (lock)
1549                 LOCK(&adb->entrylocks[bucket]);
1550
1551         entry->refcnt++;
1552
1553         if (lock)
1554                 UNLOCK(&adb->entrylocks[bucket]);
1555 }
1556
1557 static inline isc_boolean_t
1558 dec_entry_refcnt(dns_adb_t *adb, isc_boolean_t overmem, dns_adbentry_t *entry,
1559                  isc_boolean_t lock)
1560 {
1561         int bucket;
1562         isc_boolean_t destroy_entry;
1563         isc_boolean_t result = ISC_FALSE;
1564
1565         bucket = entry->lock_bucket;
1566
1567         if (lock)
1568                 LOCK(&adb->entrylocks[bucket]);
1569
1570         INSIST(entry->refcnt > 0);
1571         entry->refcnt--;
1572
1573         destroy_entry = ISC_FALSE;
1574         if (entry->refcnt == 0 &&
1575             (adb->entry_sd[bucket] || entry->expires == 0 || overmem ||
1576              (entry->flags & ENTRY_IS_DEAD) != 0)) {
1577                 destroy_entry = ISC_TRUE;
1578                 result = unlink_entry(adb, entry);
1579         }
1580
1581         if (lock)
1582                 UNLOCK(&adb->entrylocks[bucket]);
1583
1584         if (!destroy_entry)
1585                 return (result);
1586
1587         entry->lock_bucket = DNS_ADB_INVALIDBUCKET;
1588
1589         free_adbentry(adb, &entry);
1590         if (result)
1591                 result = dec_adb_irefcnt(adb);
1592
1593         return (result);
1594 }
1595
1596 static inline dns_adbname_t *
1597 new_adbname(dns_adb_t *adb, dns_name_t *dnsname) {
1598         dns_adbname_t *name;
1599
1600         name = isc_mempool_get(adb->nmp);
1601         if (name == NULL)
1602                 return (NULL);
1603
1604         dns_name_init(&name->name, NULL);
1605         if (dns_name_dup(dnsname, adb->mctx, &name->name) != ISC_R_SUCCESS) {
1606                 isc_mempool_put(adb->nmp, name);
1607                 return (NULL);
1608         }
1609         dns_name_init(&name->target, NULL);
1610         name->magic = DNS_ADBNAME_MAGIC;
1611         name->adb = adb;
1612         name->partial_result = 0;
1613         name->flags = 0;
1614         name->expire_v4 = INT_MAX;
1615         name->expire_v6 = INT_MAX;
1616         name->expire_target = INT_MAX;
1617         name->chains = 0;
1618         name->lock_bucket = DNS_ADB_INVALIDBUCKET;
1619         ISC_LIST_INIT(name->v4);
1620         ISC_LIST_INIT(name->v6);
1621         name->fetch_a = NULL;
1622         name->fetch_aaaa = NULL;
1623         name->fetch_err = FIND_ERR_UNEXPECTED;
1624         name->fetch6_err = FIND_ERR_UNEXPECTED;
1625         ISC_LIST_INIT(name->finds);
1626         ISC_LINK_INIT(name, plink);
1627
1628         LOCK(&adb->namescntlock);
1629         adb->namescnt++;
1630         if (!adb->grownames_sent && adb->namescnt > (adb->nnames * 8)) {
1631                 isc_event_t *event = &adb->grownames;
1632                 inc_adb_irefcnt(adb);
1633                 isc_task_send(adb->task, &event);
1634                 adb->grownames_sent = ISC_TRUE;
1635         }
1636         UNLOCK(&adb->namescntlock);
1637
1638         return (name);
1639 }
1640
1641 static inline void
1642 free_adbname(dns_adb_t *adb, dns_adbname_t **name) {
1643         dns_adbname_t *n;
1644
1645         INSIST(name != NULL && DNS_ADBNAME_VALID(*name));
1646         n = *name;
1647         *name = NULL;
1648
1649         INSIST(!NAME_HAS_V4(n));
1650         INSIST(!NAME_HAS_V6(n));
1651         INSIST(!NAME_FETCH(n));
1652         INSIST(ISC_LIST_EMPTY(n->finds));
1653         INSIST(!ISC_LINK_LINKED(n, plink));
1654         INSIST(n->lock_bucket == DNS_ADB_INVALIDBUCKET);
1655         INSIST(n->adb == adb);
1656
1657         n->magic = 0;
1658         dns_name_free(&n->name, adb->mctx);
1659
1660         isc_mempool_put(adb->nmp, n);
1661         LOCK(&adb->namescntlock);
1662         adb->namescnt--;
1663         UNLOCK(&adb->namescntlock);
1664 }
1665
1666 static inline dns_adbnamehook_t *
1667 new_adbnamehook(dns_adb_t *adb, dns_adbentry_t *entry) {
1668         dns_adbnamehook_t *nh;
1669
1670         nh = isc_mempool_get(adb->nhmp);
1671         if (nh == NULL)
1672                 return (NULL);
1673
1674         nh->magic = DNS_ADBNAMEHOOK_MAGIC;
1675         nh->entry = entry;
1676         ISC_LINK_INIT(nh, plink);
1677
1678         return (nh);
1679 }
1680
1681 static inline void
1682 free_adbnamehook(dns_adb_t *adb, dns_adbnamehook_t **namehook) {
1683         dns_adbnamehook_t *nh;
1684
1685         INSIST(namehook != NULL && DNS_ADBNAMEHOOK_VALID(*namehook));
1686         nh = *namehook;
1687         *namehook = NULL;
1688
1689         INSIST(nh->entry == NULL);
1690         INSIST(!ISC_LINK_LINKED(nh, plink));
1691
1692         nh->magic = 0;
1693         isc_mempool_put(adb->nhmp, nh);
1694 }
1695
1696 static inline dns_adblameinfo_t *
1697 new_adblameinfo(dns_adb_t *adb, dns_name_t *qname, dns_rdatatype_t qtype) {
1698         dns_adblameinfo_t *li;
1699
1700         li = isc_mempool_get(adb->limp);
1701         if (li == NULL)
1702                 return (NULL);
1703
1704         dns_name_init(&li->qname, NULL);
1705         if (dns_name_dup(qname, adb->mctx, &li->qname) != ISC_R_SUCCESS) {
1706                 isc_mempool_put(adb->limp, li);
1707                 return (NULL);
1708         }
1709         li->magic = DNS_ADBLAMEINFO_MAGIC;
1710         li->lame_timer = 0;
1711         li->qtype = qtype;
1712         ISC_LINK_INIT(li, plink);
1713
1714         return (li);
1715 }
1716
1717 static inline void
1718 free_adblameinfo(dns_adb_t *adb, dns_adblameinfo_t **lameinfo) {
1719         dns_adblameinfo_t *li;
1720
1721         INSIST(lameinfo != NULL && DNS_ADBLAMEINFO_VALID(*lameinfo));
1722         li = *lameinfo;
1723         *lameinfo = NULL;
1724
1725         INSIST(!ISC_LINK_LINKED(li, plink));
1726
1727         dns_name_free(&li->qname, adb->mctx);
1728
1729         li->magic = 0;
1730
1731         isc_mempool_put(adb->limp, li);
1732 }
1733
1734 static inline dns_adbentry_t *
1735 new_adbentry(dns_adb_t *adb) {
1736         dns_adbentry_t *e;
1737         isc_uint32_t r;
1738
1739         e = isc_mempool_get(adb->emp);
1740         if (e == NULL)
1741                 return (NULL);
1742
1743         e->magic = DNS_ADBENTRY_MAGIC;
1744         e->lock_bucket = DNS_ADB_INVALIDBUCKET;
1745         e->refcnt = 0;
1746         e->flags = 0;
1747         isc_random_get(&r);
1748         e->srtt = (r & 0x1f) + 1;
1749         e->expires = 0;
1750         ISC_LIST_INIT(e->lameinfo);
1751         ISC_LINK_INIT(e, plink);
1752         LOCK(&adb->entriescntlock);
1753         adb->entriescnt++;
1754         if (!adb->growentries_sent &&
1755             adb->entriescnt > (adb->nentries * 8)) {
1756                 isc_event_t *event = &adb->growentries;
1757                 inc_adb_irefcnt(adb);
1758                 isc_task_send(adb->task, &event);
1759                 adb->growentries_sent = ISC_TRUE;
1760         }
1761         UNLOCK(&adb->entriescntlock);
1762
1763         return (e);
1764 }
1765
1766 static inline void
1767 free_adbentry(dns_adb_t *adb, dns_adbentry_t **entry) {
1768         dns_adbentry_t *e;
1769         dns_adblameinfo_t *li;
1770
1771         INSIST(entry != NULL && DNS_ADBENTRY_VALID(*entry));
1772         e = *entry;
1773         *entry = NULL;
1774
1775         INSIST(e->lock_bucket == DNS_ADB_INVALIDBUCKET);
1776         INSIST(e->refcnt == 0);
1777         INSIST(!ISC_LINK_LINKED(e, plink));
1778
1779         e->magic = 0;
1780
1781         li = ISC_LIST_HEAD(e->lameinfo);
1782         while (li != NULL) {
1783                 ISC_LIST_UNLINK(e->lameinfo, li, plink);
1784                 free_adblameinfo(adb, &li);
1785                 li = ISC_LIST_HEAD(e->lameinfo);
1786         }
1787
1788         isc_mempool_put(adb->emp, e);
1789         LOCK(&adb->entriescntlock);
1790         adb->entriescnt--;
1791         UNLOCK(&adb->entriescntlock);
1792 }
1793
1794 static inline dns_adbfind_t *
1795 new_adbfind(dns_adb_t *adb) {
1796         dns_adbfind_t *h;
1797         isc_result_t result;
1798
1799         h = isc_mempool_get(adb->ahmp);
1800         if (h == NULL)
1801                 return (NULL);
1802
1803         /*
1804          * Public members.
1805          */
1806         h->magic = 0;
1807         h->adb = adb;
1808         h->partial_result = 0;
1809         h->options = 0;
1810         h->flags = 0;
1811         h->result_v4 = ISC_R_UNEXPECTED;
1812         h->result_v6 = ISC_R_UNEXPECTED;
1813         ISC_LINK_INIT(h, publink);
1814         ISC_LINK_INIT(h, plink);
1815         ISC_LIST_INIT(h->list);
1816         h->adbname = NULL;
1817         h->name_bucket = DNS_ADB_INVALIDBUCKET;
1818
1819         /*
1820          * private members
1821          */
1822         result = isc_mutex_init(&h->lock);
1823         if (result != ISC_R_SUCCESS) {
1824                 isc_mempool_put(adb->ahmp, h);
1825                 return (NULL);
1826         }
1827
1828         ISC_EVENT_INIT(&h->event, sizeof(isc_event_t), 0, 0, 0, NULL, NULL,
1829                        NULL, NULL, h);
1830
1831         inc_adb_irefcnt(adb);
1832         h->magic = DNS_ADBFIND_MAGIC;
1833         return (h);
1834 }
1835
1836 static inline dns_adbfetch_t *
1837 new_adbfetch(dns_adb_t *adb) {
1838         dns_adbfetch_t *f;
1839
1840         f = isc_mempool_get(adb->afmp);
1841         if (f == NULL)
1842                 return (NULL);
1843
1844         f->magic = 0;
1845         f->fetch = NULL;
1846
1847         dns_rdataset_init(&f->rdataset);
1848
1849         f->magic = DNS_ADBFETCH_MAGIC;
1850
1851         return (f);
1852 }
1853
1854 static inline void
1855 free_adbfetch(dns_adb_t *adb, dns_adbfetch_t **fetch) {
1856         dns_adbfetch_t *f;
1857
1858         INSIST(fetch != NULL && DNS_ADBFETCH_VALID(*fetch));
1859         f = *fetch;
1860         *fetch = NULL;
1861
1862         f->magic = 0;
1863
1864         if (dns_rdataset_isassociated(&f->rdataset))
1865                 dns_rdataset_disassociate(&f->rdataset);
1866
1867         isc_mempool_put(adb->afmp, f);
1868 }
1869
1870 static inline isc_boolean_t
1871 free_adbfind(dns_adb_t *adb, dns_adbfind_t **findp) {
1872         dns_adbfind_t *find;
1873
1874         INSIST(findp != NULL && DNS_ADBFIND_VALID(*findp));
1875         find = *findp;
1876         *findp = NULL;
1877
1878         INSIST(!FIND_HAS_ADDRS(find));
1879         INSIST(!ISC_LINK_LINKED(find, publink));
1880         INSIST(!ISC_LINK_LINKED(find, plink));
1881         INSIST(find->name_bucket == DNS_ADB_INVALIDBUCKET);
1882         INSIST(find->adbname == NULL);
1883
1884         find->magic = 0;
1885
1886         DESTROYLOCK(&find->lock);
1887         isc_mempool_put(adb->ahmp, find);
1888         return (dec_adb_irefcnt(adb));
1889 }
1890
1891 /*
1892  * Copy bits from the entry into the newly allocated addrinfo.  The entry
1893  * must be locked, and the reference count must be bumped up by one
1894  * if this function returns a valid pointer.
1895  */
1896 static inline dns_adbaddrinfo_t *
1897 new_adbaddrinfo(dns_adb_t *adb, dns_adbentry_t *entry, in_port_t port) {
1898         dns_adbaddrinfo_t *ai;
1899
1900         ai = isc_mempool_get(adb->aimp);
1901         if (ai == NULL)
1902                 return (NULL);
1903
1904         ai->magic = DNS_ADBADDRINFO_MAGIC;
1905         ai->sockaddr = entry->sockaddr;
1906         isc_sockaddr_setport(&ai->sockaddr, port);
1907         ai->srtt = entry->srtt;
1908         ai->flags = entry->flags;
1909         ai->entry = entry;
1910         ISC_LINK_INIT(ai, publink);
1911
1912         return (ai);
1913 }
1914
1915 static inline void
1916 free_adbaddrinfo(dns_adb_t *adb, dns_adbaddrinfo_t **ainfo) {
1917         dns_adbaddrinfo_t *ai;
1918
1919         INSIST(ainfo != NULL && DNS_ADBADDRINFO_VALID(*ainfo));
1920         ai = *ainfo;
1921         *ainfo = NULL;
1922
1923         INSIST(ai->entry == NULL);
1924         INSIST(!ISC_LINK_LINKED(ai, publink));
1925
1926         ai->magic = 0;
1927
1928         isc_mempool_put(adb->aimp, ai);
1929 }
1930
1931 /*
1932  * Search for the name.  NOTE:  The bucket is kept locked on both
1933  * success and failure, so it must always be unlocked by the caller!
1934  *
1935  * On the first call to this function, *bucketp must be set to
1936  * DNS_ADB_INVALIDBUCKET.
1937  */
1938 static inline dns_adbname_t *
1939 find_name_and_lock(dns_adb_t *adb, dns_name_t *name,
1940                    unsigned int options, int *bucketp)
1941 {
1942         dns_adbname_t *adbname;
1943         int bucket;
1944
1945         bucket = dns_name_fullhash(name, ISC_FALSE) % adb->nnames;
1946
1947         if (*bucketp == DNS_ADB_INVALIDBUCKET) {
1948                 LOCK(&adb->namelocks[bucket]);
1949                 *bucketp = bucket;
1950         } else if (*bucketp != bucket) {
1951                 UNLOCK(&adb->namelocks[*bucketp]);
1952                 LOCK(&adb->namelocks[bucket]);
1953                 *bucketp = bucket;
1954         }
1955
1956         adbname = ISC_LIST_HEAD(adb->names[bucket]);
1957         while (adbname != NULL) {
1958                 if (!NAME_DEAD(adbname)) {
1959                         if (dns_name_equal(name, &adbname->name)
1960                             && GLUEHINT_OK(adbname, options)
1961                             && STARTATZONE_MATCHES(adbname, options))
1962                                 return (adbname);
1963                 }
1964                 adbname = ISC_LIST_NEXT(adbname, plink);
1965         }
1966
1967         return (NULL);
1968 }
1969
1970 /*
1971  * Search for the address.  NOTE:  The bucket is kept locked on both
1972  * success and failure, so it must always be unlocked by the caller.
1973  *
1974  * On the first call to this function, *bucketp must be set to
1975  * DNS_ADB_INVALIDBUCKET.  This will cause a lock to occur.  On
1976  * later calls (within the same "lock path") it can be left alone, so
1977  * if this function is called multiple times locking is only done if
1978  * the bucket changes.
1979  */
1980 static inline dns_adbentry_t *
1981 find_entry_and_lock(dns_adb_t *adb, isc_sockaddr_t *addr, int *bucketp,
1982         isc_stdtime_t now)
1983 {
1984         dns_adbentry_t *entry, *entry_next;
1985         int bucket;
1986
1987         bucket = isc_sockaddr_hash(addr, ISC_TRUE) % adb->nentries;
1988
1989         if (*bucketp == DNS_ADB_INVALIDBUCKET) {
1990                 LOCK(&adb->entrylocks[bucket]);
1991                 *bucketp = bucket;
1992         } else if (*bucketp != bucket) {
1993                 UNLOCK(&adb->entrylocks[*bucketp]);
1994                 LOCK(&adb->entrylocks[bucket]);
1995                 *bucketp = bucket;
1996         }
1997
1998         /* Search the list, while cleaning up expired entries. */
1999         for (entry = ISC_LIST_HEAD(adb->entries[bucket]);
2000              entry != NULL;
2001              entry = entry_next) {
2002                 entry_next = ISC_LIST_NEXT(entry, plink);
2003                 (void)check_expire_entry(adb, &entry, now);
2004                 if (entry != NULL &&
2005                     isc_sockaddr_equal(addr, &entry->sockaddr)) {
2006                         ISC_LIST_UNLINK(adb->entries[bucket], entry, plink);
2007                         ISC_LIST_PREPEND(adb->entries[bucket], entry, plink);
2008                         return (entry);
2009                 }
2010         }
2011
2012         return (NULL);
2013 }
2014
2015 /*
2016  * Entry bucket MUST be locked!
2017  */
2018 static isc_boolean_t
2019 entry_is_lame(dns_adb_t *adb, dns_adbentry_t *entry, dns_name_t *qname,
2020               dns_rdatatype_t qtype, isc_stdtime_t now)
2021 {
2022         dns_adblameinfo_t *li, *next_li;
2023         isc_boolean_t is_bad;
2024
2025         is_bad = ISC_FALSE;
2026
2027         li = ISC_LIST_HEAD(entry->lameinfo);
2028         if (li == NULL)
2029                 return (ISC_FALSE);
2030         while (li != NULL) {
2031                 next_li = ISC_LIST_NEXT(li, plink);
2032
2033                 /*
2034                  * Has the entry expired?
2035                  */
2036                 if (li->lame_timer < now) {
2037                         ISC_LIST_UNLINK(entry->lameinfo, li, plink);
2038                         free_adblameinfo(adb, &li);
2039                 }
2040
2041                 /*
2042                  * Order tests from least to most expensive.
2043                  *
2044                  * We do not break out of the main loop here as
2045                  * we use the loop for house keeping.
2046                  */
2047                 if (li != NULL && !is_bad && li->qtype == qtype &&
2048                     dns_name_equal(qname, &li->qname))
2049                         is_bad = ISC_TRUE;
2050
2051                 li = next_li;
2052         }
2053
2054         return (is_bad);
2055 }
2056
2057 static void
2058 copy_namehook_lists(dns_adb_t *adb, dns_adbfind_t *find, dns_name_t *qname,
2059                     dns_rdatatype_t qtype, dns_adbname_t *name,
2060                     isc_stdtime_t now)
2061 {
2062         dns_adbnamehook_t *namehook;
2063         dns_adbaddrinfo_t *addrinfo;
2064         dns_adbentry_t *entry;
2065         int bucket;
2066
2067         bucket = DNS_ADB_INVALIDBUCKET;
2068
2069         if (find->options & DNS_ADBFIND_INET) {
2070                 namehook = ISC_LIST_HEAD(name->v4);
2071                 while (namehook != NULL) {
2072                         entry = namehook->entry;
2073                         bucket = entry->lock_bucket;
2074                         LOCK(&adb->entrylocks[bucket]);
2075
2076                         if (!FIND_RETURNLAME(find)
2077                             && entry_is_lame(adb, entry, qname, qtype, now)) {
2078                                 find->options |= DNS_ADBFIND_LAMEPRUNED;
2079                                 goto nextv4;
2080                         }
2081                         addrinfo = new_adbaddrinfo(adb, entry, find->port);
2082                         if (addrinfo == NULL) {
2083                                 find->partial_result |= DNS_ADBFIND_INET;
2084                                 goto out;
2085                         }
2086                         /*
2087                          * Found a valid entry.  Add it to the find's list.
2088                          */
2089                         inc_entry_refcnt(adb, entry, ISC_FALSE);
2090                         ISC_LIST_APPEND(find->list, addrinfo, publink);
2091                         addrinfo = NULL;
2092                 nextv4:
2093                         UNLOCK(&adb->entrylocks[bucket]);
2094                         bucket = DNS_ADB_INVALIDBUCKET;
2095                         namehook = ISC_LIST_NEXT(namehook, plink);
2096                 }
2097         }
2098
2099         if (find->options & DNS_ADBFIND_INET6) {
2100                 namehook = ISC_LIST_HEAD(name->v6);
2101                 while (namehook != NULL) {
2102                         entry = namehook->entry;
2103                         bucket = entry->lock_bucket;
2104                         LOCK(&adb->entrylocks[bucket]);
2105
2106                         if (!FIND_RETURNLAME(find)
2107                             && entry_is_lame(adb, entry, qname, qtype, now)) {
2108                                 find->options |= DNS_ADBFIND_LAMEPRUNED;
2109                                 goto nextv6;
2110                         }
2111                         addrinfo = new_adbaddrinfo(adb, entry, find->port);
2112                         if (addrinfo == NULL) {
2113                                 find->partial_result |= DNS_ADBFIND_INET6;
2114                                 goto out;
2115                         }
2116                         /*
2117                          * Found a valid entry.  Add it to the find's list.
2118                          */
2119                         inc_entry_refcnt(adb, entry, ISC_FALSE);
2120                         ISC_LIST_APPEND(find->list, addrinfo, publink);
2121                         addrinfo = NULL;
2122                 nextv6:
2123                         UNLOCK(&adb->entrylocks[bucket]);
2124                         bucket = DNS_ADB_INVALIDBUCKET;
2125                         namehook = ISC_LIST_NEXT(namehook, plink);
2126                 }
2127         }
2128
2129  out:
2130         if (bucket != DNS_ADB_INVALIDBUCKET)
2131                 UNLOCK(&adb->entrylocks[bucket]);
2132 }
2133
2134 static void
2135 shutdown_task(isc_task_t *task, isc_event_t *ev) {
2136         dns_adb_t *adb;
2137
2138         UNUSED(task);
2139
2140         adb = ev->ev_arg;
2141         INSIST(DNS_ADB_VALID(adb));
2142
2143         isc_event_free(&ev);
2144         /*
2145          * Wait for lock around check_exit() call to be released.
2146          */
2147         LOCK(&adb->lock);
2148         UNLOCK(&adb->lock);
2149         destroy(adb);
2150 }
2151
2152 /*
2153  * Name bucket must be locked; adb may be locked; no other locks held.
2154  */
2155 static isc_boolean_t
2156 check_expire_name(dns_adbname_t **namep, isc_stdtime_t now) {
2157         dns_adbname_t *name;
2158         isc_boolean_t result = ISC_FALSE;
2159
2160         INSIST(namep != NULL && DNS_ADBNAME_VALID(*namep));
2161         name = *namep;
2162
2163         if (NAME_HAS_V4(name) || NAME_HAS_V6(name))
2164                 return (result);
2165         if (NAME_FETCH(name))
2166                 return (result);
2167         if (!EXPIRE_OK(name->expire_v4, now))
2168                 return (result);
2169         if (!EXPIRE_OK(name->expire_v6, now))
2170                 return (result);
2171         if (!EXPIRE_OK(name->expire_target, now))
2172                 return (result);
2173
2174         /*
2175          * The name is empty.  Delete it.
2176          */
2177         result = kill_name(&name, DNS_EVENT_ADBEXPIRED);
2178         *namep = NULL;
2179
2180         /*
2181          * Our caller, or one of its callers, will be calling check_exit() at
2182          * some point, so we don't need to do it here.
2183          */
2184         return (result);
2185 }
2186
2187 /*%
2188  * Examine the tail entry of the LRU list to see if it expires or is stale
2189  * (unused for some period); if so, the name entry will be freed.  If the ADB
2190  * is in the overmem condition, the tail and the next to tail entries
2191  * will be unconditionally removed (unless they have an outstanding fetch).
2192  * We don't care about a race on 'overmem' at the risk of causing some
2193  * collateral damage or a small delay in starting cleanup, so we don't bother
2194  * to lock ADB (if it's not locked).
2195  *
2196  * Name bucket must be locked; adb may be locked; no other locks held.
2197  */
2198 static void
2199 check_stale_name(dns_adb_t *adb, int bucket, isc_stdtime_t now) {
2200         int victims, max_victims;
2201         dns_adbname_t *victim, *next_victim;
2202         isc_boolean_t overmem = isc_mem_isovermem(adb->mctx);
2203         int scans = 0;
2204
2205         INSIST(bucket != DNS_ADB_INVALIDBUCKET);
2206
2207         max_victims = overmem ? 2 : 1;
2208
2209         /*
2210          * We limit the number of scanned entries to 10 (arbitrary choice)
2211          * in order to avoid examining too many entries when there are many
2212          * tail entries that have fetches (this should be rare, but could
2213          * happen).
2214          */
2215         victim = ISC_LIST_TAIL(adb->names[bucket]);
2216         for (victims = 0;
2217              victim != NULL && victims < max_victims && scans < 10;
2218              victim = next_victim) {
2219                 INSIST(!NAME_DEAD(victim));
2220                 scans++;
2221                 next_victim = ISC_LIST_PREV(victim, plink);
2222                 (void)check_expire_name(&victim, now);
2223                 if (victim == NULL) {
2224                         victims++;
2225                         goto next;
2226                 }
2227
2228                 if (!NAME_FETCH(victim) &&
2229                     (overmem || victim->last_used + ADB_STALE_MARGIN <= now)) {
2230                         RUNTIME_CHECK(kill_name(&victim,
2231                                                 DNS_EVENT_ADBCANCELED) ==
2232                                       ISC_FALSE);
2233                         victims++;
2234                 }
2235
2236         next:
2237                 if (!overmem)
2238                         break;
2239         }
2240 }
2241
2242 /*
2243  * Entry bucket must be locked; adb may be locked; no other locks held.
2244  */
2245 static isc_boolean_t
2246 check_expire_entry(dns_adb_t *adb, dns_adbentry_t **entryp, isc_stdtime_t now)
2247 {
2248         dns_adbentry_t *entry;
2249         isc_boolean_t result = ISC_FALSE;
2250
2251         INSIST(entryp != NULL && DNS_ADBENTRY_VALID(*entryp));
2252         entry = *entryp;
2253
2254         if (entry->refcnt != 0)
2255                 return (result);
2256
2257         if (entry->expires == 0 || entry->expires > now)
2258                 return (result);
2259
2260         /*
2261          * The entry is not in use.  Delete it.
2262          */
2263         DP(DEF_LEVEL, "killing entry %p", entry);
2264         INSIST(ISC_LINK_LINKED(entry, plink));
2265         result = unlink_entry(adb, entry);
2266         free_adbentry(adb, &entry);
2267         if (result)
2268                 dec_adb_irefcnt(adb);
2269         *entryp = NULL;
2270         return (result);
2271 }
2272
2273 /*
2274  * ADB must be locked, and no other locks held.
2275  */
2276 static isc_boolean_t
2277 cleanup_names(dns_adb_t *adb, int bucket, isc_stdtime_t now) {
2278         dns_adbname_t *name;
2279         dns_adbname_t *next_name;
2280         isc_boolean_t result = ISC_FALSE;
2281
2282         DP(CLEAN_LEVEL, "cleaning name bucket %d", bucket);
2283
2284         LOCK(&adb->namelocks[bucket]);
2285         if (adb->name_sd[bucket]) {
2286                 UNLOCK(&adb->namelocks[bucket]);
2287                 return (result);
2288         }
2289
2290         name = ISC_LIST_HEAD(adb->names[bucket]);
2291         while (name != NULL) {
2292                 next_name = ISC_LIST_NEXT(name, plink);
2293                 INSIST(result == ISC_FALSE);
2294                 result = check_expire_namehooks(name, now);
2295                 if (!result)
2296                         result = check_expire_name(&name, now);
2297                 name = next_name;
2298         }
2299         UNLOCK(&adb->namelocks[bucket]);
2300         return (result);
2301 }
2302
2303 /*
2304  * ADB must be locked, and no other locks held.
2305  */
2306 static isc_boolean_t
2307 cleanup_entries(dns_adb_t *adb, int bucket, isc_stdtime_t now) {
2308         dns_adbentry_t *entry, *next_entry;
2309         isc_boolean_t result = ISC_FALSE;
2310
2311         DP(CLEAN_LEVEL, "cleaning entry bucket %d", bucket);
2312
2313         LOCK(&adb->entrylocks[bucket]);
2314         entry = ISC_LIST_HEAD(adb->entries[bucket]);
2315         while (entry != NULL) {
2316                 next_entry = ISC_LIST_NEXT(entry, plink);
2317                 INSIST(result == ISC_FALSE);
2318                 result = check_expire_entry(adb, &entry, now);
2319                 entry = next_entry;
2320         }
2321         UNLOCK(&adb->entrylocks[bucket]);
2322         return (result);
2323 }
2324
2325 static void
2326 destroy(dns_adb_t *adb) {
2327         adb->magic = 0;
2328
2329         isc_task_detach(&adb->task);
2330
2331         isc_mempool_destroy(&adb->nmp);
2332         isc_mempool_destroy(&adb->nhmp);
2333         isc_mempool_destroy(&adb->limp);
2334         isc_mempool_destroy(&adb->emp);
2335         isc_mempool_destroy(&adb->ahmp);
2336         isc_mempool_destroy(&adb->aimp);
2337         isc_mempool_destroy(&adb->afmp);
2338
2339         DESTROYMUTEXBLOCK(adb->entrylocks, adb->nentries);
2340         isc_mem_put(adb->mctx, adb->entries,
2341                     sizeof(*adb->entries) * adb->nentries);
2342         isc_mem_put(adb->mctx, adb->deadentries,
2343                     sizeof(*adb->deadentries) * adb->nentries);
2344         isc_mem_put(adb->mctx, adb->entrylocks,
2345                     sizeof(*adb->entrylocks) * adb->nentries);
2346         isc_mem_put(adb->mctx, adb->entry_sd,
2347                     sizeof(*adb->entry_sd) * adb->nentries);
2348         isc_mem_put(adb->mctx, adb->entry_refcnt,
2349                     sizeof(*adb->entry_refcnt) * adb->nentries);
2350
2351         DESTROYMUTEXBLOCK(adb->namelocks, adb->nnames);
2352         isc_mem_put(adb->mctx, adb->names,
2353                     sizeof(*adb->names) * adb->nnames);
2354         isc_mem_put(adb->mctx, adb->deadnames,
2355                     sizeof(*adb->deadnames) * adb->nnames);
2356         isc_mem_put(adb->mctx, adb->namelocks,
2357                     sizeof(*adb->namelocks) * adb->nnames);
2358         isc_mem_put(adb->mctx, adb->name_sd,
2359                     sizeof(*adb->name_sd) * adb->nnames);
2360         isc_mem_put(adb->mctx, adb->name_refcnt,
2361                     sizeof(*adb->name_refcnt) * adb->nnames);
2362
2363         DESTROYLOCK(&adb->reflock);
2364         DESTROYLOCK(&adb->lock);
2365         DESTROYLOCK(&adb->mplock);
2366         DESTROYLOCK(&adb->overmemlock);
2367         DESTROYLOCK(&adb->entriescntlock);
2368         DESTROYLOCK(&adb->namescntlock);
2369
2370         isc_mem_putanddetach(&adb->mctx, adb, sizeof(dns_adb_t));
2371 }
2372
2373
2374 /*
2375  * Public functions.
2376  */
2377
2378 isc_result_t
2379 dns_adb_create(isc_mem_t *mem, dns_view_t *view, isc_timermgr_t *timermgr,
2380                isc_taskmgr_t *taskmgr, dns_adb_t **newadb)
2381 {
2382         dns_adb_t *adb;
2383         isc_result_t result;
2384         unsigned int i;
2385
2386         REQUIRE(mem != NULL);
2387         REQUIRE(view != NULL);
2388         REQUIRE(timermgr != NULL); /* this is actually unused */
2389         REQUIRE(taskmgr != NULL);
2390         REQUIRE(newadb != NULL && *newadb == NULL);
2391
2392         UNUSED(timermgr);
2393
2394         adb = isc_mem_get(mem, sizeof(dns_adb_t));
2395         if (adb == NULL)
2396                 return (ISC_R_NOMEMORY);
2397
2398         /*
2399          * Initialize things here that cannot fail, and especially things
2400          * that must be NULL for the error return to work properly.
2401          */
2402         adb->magic = 0;
2403         adb->erefcnt = 1;
2404         adb->irefcnt = 0;
2405         adb->nmp = NULL;
2406         adb->nhmp = NULL;
2407         adb->limp = NULL;
2408         adb->emp = NULL;
2409         adb->ahmp = NULL;
2410         adb->aimp = NULL;
2411         adb->afmp = NULL;
2412         adb->task = NULL;
2413         adb->mctx = NULL;
2414         adb->view = view;
2415         adb->taskmgr = taskmgr;
2416         adb->next_cleanbucket = 0;
2417         ISC_EVENT_INIT(&adb->cevent, sizeof(adb->cevent), 0, NULL,
2418                        DNS_EVENT_ADBCONTROL, shutdown_task, adb,
2419                        adb, NULL, NULL);
2420         adb->cevent_sent = ISC_FALSE;
2421         adb->shutting_down = ISC_FALSE;
2422         ISC_LIST_INIT(adb->whenshutdown);
2423
2424         adb->nentries = nbuckets[0];
2425         adb->entriescnt = 0;
2426         adb->entries = NULL;
2427         adb->deadentries = NULL;
2428         adb->entry_sd = NULL;
2429         adb->entry_refcnt = NULL;
2430         adb->entrylocks = NULL;
2431         ISC_EVENT_INIT(&adb->growentries, sizeof(adb->growentries), 0, NULL,
2432                        DNS_EVENT_ADBGROWENTRIES, grow_entries, adb,
2433                        adb, NULL, NULL);
2434         adb->growentries_sent = ISC_FALSE;
2435
2436         adb->nnames = nbuckets[0];
2437         adb->namescnt = 0;
2438         adb->names = NULL;
2439         adb->deadnames = NULL;
2440         adb->name_sd = NULL;
2441         adb->name_refcnt = NULL;
2442         adb->namelocks = NULL;
2443         ISC_EVENT_INIT(&adb->grownames, sizeof(adb->grownames), 0, NULL,
2444                        DNS_EVENT_ADBGROWNAMES, grow_names, adb,
2445                        adb, NULL, NULL);
2446         adb->grownames_sent = ISC_FALSE;
2447
2448         isc_mem_attach(mem, &adb->mctx);
2449
2450         result = isc_mutex_init(&adb->lock);
2451         if (result != ISC_R_SUCCESS)
2452                 goto fail0b;
2453
2454         result = isc_mutex_init(&adb->mplock);
2455         if (result != ISC_R_SUCCESS)
2456                 goto fail0c;
2457
2458         result = isc_mutex_init(&adb->reflock);
2459         if (result != ISC_R_SUCCESS)
2460                 goto fail0d;
2461
2462         result = isc_mutex_init(&adb->overmemlock);
2463         if (result != ISC_R_SUCCESS)
2464                 goto fail0e;
2465
2466         result = isc_mutex_init(&adb->entriescntlock);
2467         if (result != ISC_R_SUCCESS)
2468                 goto fail0f;
2469
2470         result = isc_mutex_init(&adb->namescntlock);
2471         if (result != ISC_R_SUCCESS)
2472                 goto fail0g;
2473
2474 #define ALLOCENTRY(adb, el) \
2475         do { \
2476                 (adb)->el = isc_mem_get((adb)->mctx, \
2477                                      sizeof(*(adb)->el) * (adb)->nentries); \
2478                 if ((adb)->el == NULL) { \
2479                         result = ISC_R_NOMEMORY; \
2480                         goto fail1; \
2481                 }\
2482         } while (0)
2483         ALLOCENTRY(adb, entries);
2484         ALLOCENTRY(adb, deadentries);
2485         ALLOCENTRY(adb, entrylocks);
2486         ALLOCENTRY(adb, entry_sd);
2487         ALLOCENTRY(adb, entry_refcnt);
2488 #undef ALLOCENTRY
2489
2490 #define ALLOCNAME(adb, el) \
2491         do { \
2492                 (adb)->el = isc_mem_get((adb)->mctx, \
2493                                      sizeof(*(adb)->el) * (adb)->nnames); \
2494                 if ((adb)->el == NULL) { \
2495                         result = ISC_R_NOMEMORY; \
2496                         goto fail1; \
2497                 }\
2498         } while (0)
2499         ALLOCNAME(adb, names);
2500         ALLOCNAME(adb, deadnames);
2501         ALLOCNAME(adb, namelocks);
2502         ALLOCNAME(adb, name_sd);
2503         ALLOCNAME(adb, name_refcnt);
2504 #undef ALLOCNAME
2505
2506         /*
2507          * Initialize the bucket locks for names and elements.
2508          * May as well initialize the list heads, too.
2509          */
2510         result = isc_mutexblock_init(adb->namelocks, adb->nnames);
2511         if (result != ISC_R_SUCCESS)
2512                 goto fail1;
2513         for (i = 0; i < adb->nnames; i++) {
2514                 ISC_LIST_INIT(adb->names[i]);
2515                 ISC_LIST_INIT(adb->deadnames[i]);
2516                 adb->name_sd[i] = ISC_FALSE;
2517                 adb->name_refcnt[i] = 0;
2518                 adb->irefcnt++;
2519         }
2520         for (i = 0; i < adb->nentries; i++) {
2521                 ISC_LIST_INIT(adb->entries[i]);
2522                 ISC_LIST_INIT(adb->deadentries[i]);
2523                 adb->entry_sd[i] = ISC_FALSE;
2524                 adb->entry_refcnt[i] = 0;
2525                 adb->irefcnt++;
2526         }
2527         result = isc_mutexblock_init(adb->entrylocks, adb->nentries);
2528         if (result != ISC_R_SUCCESS)
2529                 goto fail2;
2530
2531         /*
2532          * Memory pools
2533          */
2534 #define MPINIT(t, p, n) do { \
2535         result = isc_mempool_create(mem, sizeof(t), &(p)); \
2536         if (result != ISC_R_SUCCESS) \
2537                 goto fail3; \
2538         isc_mempool_setfreemax((p), FREE_ITEMS); \
2539         isc_mempool_setfillcount((p), FILL_COUNT); \
2540         isc_mempool_setname((p), n); \
2541         isc_mempool_associatelock((p), &adb->mplock); \
2542 } while (0)
2543
2544         MPINIT(dns_adbname_t, adb->nmp, "adbname");
2545         MPINIT(dns_adbnamehook_t, adb->nhmp, "adbnamehook");
2546         MPINIT(dns_adblameinfo_t, adb->limp, "adblameinfo");
2547         MPINIT(dns_adbentry_t, adb->emp, "adbentry");
2548         MPINIT(dns_adbfind_t, adb->ahmp, "adbfind");
2549         MPINIT(dns_adbaddrinfo_t, adb->aimp, "adbaddrinfo");
2550         MPINIT(dns_adbfetch_t, adb->afmp, "adbfetch");
2551
2552 #undef MPINIT
2553
2554         /*
2555          * Allocate an internal task.
2556          */
2557         result = isc_task_create(adb->taskmgr, 0, &adb->task);
2558         if (result != ISC_R_SUCCESS)
2559                 goto fail3;
2560         isc_task_setname(adb->task, "ADB", adb);
2561
2562         /*
2563          * Normal return.
2564          */
2565         adb->magic = DNS_ADB_MAGIC;
2566         *newadb = adb;
2567         return (ISC_R_SUCCESS);
2568
2569  fail3:
2570         if (adb->task != NULL)
2571                 isc_task_detach(&adb->task);
2572
2573         /* clean up entrylocks */
2574         DESTROYMUTEXBLOCK(adb->entrylocks, adb->nentries);
2575
2576  fail2: /* clean up namelocks */
2577         DESTROYMUTEXBLOCK(adb->namelocks, adb->nnames);
2578
2579  fail1: /* clean up only allocated memory */
2580         if (adb->entries != NULL)
2581                 isc_mem_put(adb->mctx, adb->entries,
2582                             sizeof(*adb->entries) * adb->nentries);
2583         if (adb->deadentries != NULL)
2584                 isc_mem_put(adb->mctx, adb->deadentries,
2585                             sizeof(*adb->deadentries) * adb->nentries);
2586         if (adb->entrylocks != NULL)
2587                 isc_mem_put(adb->mctx, adb->entrylocks,
2588                             sizeof(*adb->entrylocks) * adb->nentries);
2589         if (adb->entry_sd != NULL)
2590                 isc_mem_put(adb->mctx, adb->entry_sd,
2591                             sizeof(*adb->entry_sd) * adb->nentries);
2592         if (adb->entry_refcnt != NULL)
2593                 isc_mem_put(adb->mctx, adb->entry_refcnt,
2594                             sizeof(*adb->entry_refcnt) * adb->nentries);
2595         if (adb->names != NULL)
2596                 isc_mem_put(adb->mctx, adb->names,
2597                             sizeof(*adb->names) * adb->nnames);
2598         if (adb->deadnames != NULL)
2599                 isc_mem_put(adb->mctx, adb->deadnames,
2600                             sizeof(*adb->deadnames) * adb->nnames);
2601         if (adb->namelocks != NULL)
2602                 isc_mem_put(adb->mctx, adb->namelocks,
2603                             sizeof(*adb->namelocks) * adb->nnames);
2604         if (adb->name_sd != NULL)
2605                 isc_mem_put(adb->mctx, adb->name_sd,
2606                             sizeof(*adb->name_sd) * adb->nnames);
2607         if (adb->name_refcnt != NULL)
2608                 isc_mem_put(adb->mctx, adb->name_refcnt,
2609                             sizeof(*adb->name_refcnt) * adb->nnames);
2610         if (adb->nmp != NULL)
2611                 isc_mempool_destroy(&adb->nmp);
2612         if (adb->nhmp != NULL)
2613                 isc_mempool_destroy(&adb->nhmp);
2614         if (adb->limp != NULL)
2615                 isc_mempool_destroy(&adb->limp);
2616         if (adb->emp != NULL)
2617                 isc_mempool_destroy(&adb->emp);
2618         if (adb->ahmp != NULL)
2619                 isc_mempool_destroy(&adb->ahmp);
2620         if (adb->aimp != NULL)
2621                 isc_mempool_destroy(&adb->aimp);
2622         if (adb->afmp != NULL)
2623                 isc_mempool_destroy(&adb->afmp);
2624
2625         DESTROYLOCK(&adb->namescntlock);
2626  fail0g:
2627         DESTROYLOCK(&adb->entriescntlock);
2628  fail0f:
2629         DESTROYLOCK(&adb->overmemlock);
2630  fail0e:
2631         DESTROYLOCK(&adb->reflock);
2632  fail0d:
2633         DESTROYLOCK(&adb->mplock);
2634  fail0c:
2635         DESTROYLOCK(&adb->lock);
2636  fail0b:
2637         isc_mem_putanddetach(&adb->mctx, adb, sizeof(dns_adb_t));
2638
2639         return (result);
2640 }
2641
2642 void
2643 dns_adb_attach(dns_adb_t *adb, dns_adb_t **adbx) {
2644
2645         REQUIRE(DNS_ADB_VALID(adb));
2646         REQUIRE(adbx != NULL && *adbx == NULL);
2647
2648         inc_adb_erefcnt(adb);
2649         *adbx = adb;
2650 }
2651
2652 void
2653 dns_adb_detach(dns_adb_t **adbx) {
2654         dns_adb_t *adb;
2655         isc_boolean_t need_exit_check;
2656
2657         REQUIRE(adbx != NULL && DNS_ADB_VALID(*adbx));
2658
2659         adb = *adbx;
2660         *adbx = NULL;
2661
2662         INSIST(adb->erefcnt > 0);
2663
2664         LOCK(&adb->reflock);
2665         adb->erefcnt--;
2666         need_exit_check = ISC_TF(adb->erefcnt == 0 && adb->irefcnt == 0);
2667         UNLOCK(&adb->reflock);
2668
2669         if (need_exit_check) {
2670                 LOCK(&adb->lock);
2671                 INSIST(adb->shutting_down);
2672                 check_exit(adb);
2673                 UNLOCK(&adb->lock);
2674         }
2675 }
2676
2677 void
2678 dns_adb_whenshutdown(dns_adb_t *adb, isc_task_t *task, isc_event_t **eventp) {
2679         isc_task_t *clone;
2680         isc_event_t *event;
2681         isc_boolean_t zeroirefcnt = ISC_FALSE;
2682
2683         /*
2684          * Send '*eventp' to 'task' when 'adb' has shutdown.
2685          */
2686
2687         REQUIRE(DNS_ADB_VALID(adb));
2688         REQUIRE(eventp != NULL);
2689
2690         event = *eventp;
2691         *eventp = NULL;
2692
2693         LOCK(&adb->lock);
2694
2695         LOCK(&adb->reflock);
2696         zeroirefcnt = ISC_TF(adb->irefcnt == 0);
2697
2698         if (adb->shutting_down && zeroirefcnt &&
2699             isc_mempool_getallocated(adb->ahmp) == 0) {
2700                 /*
2701                  * We're already shutdown.  Send the event.
2702                  */
2703                 event->ev_sender = adb;
2704                 isc_task_send(task, &event);
2705         } else {
2706                 clone = NULL;
2707                 isc_task_attach(task, &clone);
2708                 event->ev_sender = clone;
2709                 ISC_LIST_APPEND(adb->whenshutdown, event, ev_link);
2710         }
2711
2712         UNLOCK(&adb->reflock);
2713         UNLOCK(&adb->lock);
2714 }
2715
2716 void
2717 dns_adb_shutdown(dns_adb_t *adb) {
2718         isc_boolean_t need_check_exit;
2719
2720         /*
2721          * Shutdown 'adb'.
2722          */
2723
2724         LOCK(&adb->lock);
2725
2726         if (!adb->shutting_down) {
2727                 adb->shutting_down = ISC_TRUE;
2728                 isc_mem_setwater(adb->mctx, water, adb, 0, 0);
2729                 need_check_exit = shutdown_names(adb);
2730                 if (!need_check_exit)
2731                         need_check_exit = shutdown_entries(adb);
2732                 if (need_check_exit)
2733                         check_exit(adb);
2734         }
2735
2736         UNLOCK(&adb->lock);
2737 }
2738
2739 isc_result_t
2740 dns_adb_createfind(dns_adb_t *adb, isc_task_t *task, isc_taskaction_t action,
2741                    void *arg, dns_name_t *name, dns_name_t *qname,
2742                    dns_rdatatype_t qtype, unsigned int options,
2743                    isc_stdtime_t now, dns_name_t *target,
2744                    in_port_t port, dns_adbfind_t **findp)
2745 {
2746         dns_adbfind_t *find;
2747         dns_adbname_t *adbname;
2748         int bucket;
2749         isc_boolean_t want_event, start_at_zone, alias, have_address;
2750         isc_result_t result;
2751         unsigned int wanted_addresses;
2752         unsigned int wanted_fetches;
2753         unsigned int query_pending;
2754
2755         REQUIRE(DNS_ADB_VALID(adb));
2756         if (task != NULL) {
2757                 REQUIRE(action != NULL);
2758         }
2759         REQUIRE(name != NULL);
2760         REQUIRE(qname != NULL);
2761         REQUIRE(findp != NULL && *findp == NULL);
2762         REQUIRE(target == NULL || dns_name_hasbuffer(target));
2763
2764         REQUIRE((options & DNS_ADBFIND_ADDRESSMASK) != 0);
2765
2766         result = ISC_R_UNEXPECTED;
2767         POST(result);
2768         wanted_addresses = (options & DNS_ADBFIND_ADDRESSMASK);
2769         wanted_fetches = 0;
2770         query_pending = 0;
2771         want_event = ISC_FALSE;
2772         start_at_zone = ISC_FALSE;
2773         alias = ISC_FALSE;
2774
2775         if (now == 0)
2776                 isc_stdtime_get(&now);
2777
2778         /*
2779          * XXXMLG  Move this comment somewhere else!
2780          *
2781          * Look up the name in our internal database.
2782          *
2783          * Possibilities:  Note that these are not always exclusive.
2784          *
2785          *      No name found.  In this case, allocate a new name header and
2786          *      an initial namehook or two.  If any of these allocations
2787          *      fail, clean up and return ISC_R_NOMEMORY.
2788          *
2789          *      Name found, valid addresses present.  Allocate one addrinfo
2790          *      structure for each found and append it to the linked list
2791          *      of addresses for this header.
2792          *
2793          *      Name found, queries pending.  In this case, if a task was
2794          *      passed in, allocate a job id, attach it to the name's job
2795          *      list and remember to tell the caller that there will be
2796          *      more info coming later.
2797          */
2798
2799         find = new_adbfind(adb);
2800         if (find == NULL)
2801                 return (ISC_R_NOMEMORY);
2802
2803         find->port = port;
2804
2805         /*
2806          * Remember what types of addresses we are interested in.
2807          */
2808         find->options = options;
2809         find->flags |= wanted_addresses;
2810         if (FIND_WANTEVENT(find)) {
2811                 REQUIRE(task != NULL);
2812         }
2813
2814         /*
2815          * Try to see if we know anything about this name at all.
2816          */
2817         bucket = DNS_ADB_INVALIDBUCKET;
2818         adbname = find_name_and_lock(adb, name, find->options, &bucket);
2819         INSIST(bucket != DNS_ADB_INVALIDBUCKET);
2820         if (adb->name_sd[bucket]) {
2821                 DP(DEF_LEVEL,
2822                    "dns_adb_createfind: returning ISC_R_SHUTTINGDOWN");
2823                 RUNTIME_CHECK(free_adbfind(adb, &find) == ISC_FALSE);
2824                 result = ISC_R_SHUTTINGDOWN;
2825                 goto out;
2826         }
2827
2828         /*
2829          * Nothing found.  Allocate a new adbname structure for this name.
2830          */
2831         if (adbname == NULL) {
2832                 /*
2833                  * See if there is any stale name at the end of list, and purge
2834                  * it if so.
2835                  */
2836                 check_stale_name(adb, bucket, now);
2837
2838                 adbname = new_adbname(adb, name);
2839                 if (adbname == NULL) {
2840                         RUNTIME_CHECK(free_adbfind(adb, &find) == ISC_FALSE);
2841                         result = ISC_R_NOMEMORY;
2842                         goto out;
2843                 }
2844                 link_name(adb, bucket, adbname);
2845                 if (FIND_HINTOK(find))
2846                         adbname->flags |= NAME_HINT_OK;
2847                 if (FIND_GLUEOK(find))
2848                         adbname->flags |= NAME_GLUE_OK;
2849                 if (FIND_STARTATZONE(find))
2850                         adbname->flags |= NAME_STARTATZONE;
2851         } else {
2852                 /* Move this name forward in the LRU list */
2853                 ISC_LIST_UNLINK(adb->names[bucket], adbname, plink);
2854                 ISC_LIST_PREPEND(adb->names[bucket], adbname, plink);
2855         }
2856         adbname->last_used = now;
2857
2858         /*
2859          * Expire old entries, etc.
2860          */
2861         RUNTIME_CHECK(check_expire_namehooks(adbname, now) == ISC_FALSE);
2862
2863         /*
2864          * Do we know that the name is an alias?
2865          */
2866         if (!EXPIRE_OK(adbname->expire_target, now)) {
2867                 /*
2868                  * Yes, it is.
2869                  */
2870                 DP(DEF_LEVEL,
2871                    "dns_adb_createfind: name %p is an alias (cached)",
2872                    adbname);
2873                 alias = ISC_TRUE;
2874                 goto post_copy;
2875         }
2876
2877         /*
2878          * Try to populate the name from the database and/or
2879          * start fetches.  First try looking for an A record
2880          * in the database.
2881          */
2882         if (!NAME_HAS_V4(adbname) && EXPIRE_OK(adbname->expire_v4, now)
2883             && WANT_INET(wanted_addresses)) {
2884                 result = dbfind_name(adbname, now, dns_rdatatype_a);
2885                 if (result == ISC_R_SUCCESS) {
2886                         DP(DEF_LEVEL,
2887                            "dns_adb_createfind: found A for name %p in db",
2888                            adbname);
2889                         goto v6;
2890                 }
2891
2892                 /*
2893                  * Did we get a CNAME or DNAME?
2894                  */
2895                 if (result == DNS_R_ALIAS) {
2896                         DP(DEF_LEVEL,
2897                            "dns_adb_createfind: name %p is an alias",
2898                            adbname);
2899                         alias = ISC_TRUE;
2900                         goto post_copy;
2901                 }
2902
2903                 /*
2904                  * If the name doesn't exist at all, don't bother with
2905                  * v6 queries; they won't work.
2906                  *
2907                  * If the name does exist but we didn't get our data, go
2908                  * ahead and try AAAA.
2909                  *
2910                  * If the result is neither of these, try a fetch for A.
2911                  */
2912                 if (NXDOMAIN_RESULT(result))
2913                         goto fetch;
2914                 else if (NXRRSET_RESULT(result))
2915                         goto v6;
2916
2917                 if (!NAME_FETCH_V4(adbname))
2918                         wanted_fetches |= DNS_ADBFIND_INET;
2919         }
2920
2921  v6:
2922         if (!NAME_HAS_V6(adbname) && EXPIRE_OK(adbname->expire_v6, now)
2923             && WANT_INET6(wanted_addresses)) {
2924                 result = dbfind_name(adbname, now, dns_rdatatype_aaaa);
2925                 if (result == ISC_R_SUCCESS) {
2926                         DP(DEF_LEVEL,
2927                            "dns_adb_createfind: found AAAA for name %p",
2928                            adbname);
2929                         goto fetch;
2930                 }
2931
2932                 /*
2933                  * Did we get a CNAME or DNAME?
2934                  */
2935                 if (result == DNS_R_ALIAS) {
2936                         DP(DEF_LEVEL,
2937                            "dns_adb_createfind: name %p is an alias",
2938                            adbname);
2939                         alias = ISC_TRUE;
2940                         goto post_copy;
2941                 }
2942
2943                 /*
2944                  * Listen to negative cache hints, and don't start
2945                  * another query.
2946                  */
2947                 if (NCACHE_RESULT(result) || AUTH_NX(result))
2948                         goto fetch;
2949
2950                 if (!NAME_FETCH_V6(adbname))
2951                         wanted_fetches |= DNS_ADBFIND_INET6;
2952         }
2953
2954  fetch:
2955         if ((WANT_INET(wanted_addresses) && NAME_HAS_V4(adbname)) ||
2956             (WANT_INET6(wanted_addresses) && NAME_HAS_V6(adbname)))
2957                 have_address = ISC_TRUE;
2958         else
2959                 have_address = ISC_FALSE;
2960         if (wanted_fetches != 0 &&
2961             ! (FIND_AVOIDFETCHES(find) && have_address)) {
2962                 /*
2963                  * We're missing at least one address family.  Either the
2964                  * caller hasn't instructed us to avoid fetches, or we don't
2965                  * know anything about any of the address families that would
2966                  * be acceptable so we have to launch fetches.
2967                  */
2968
2969                 if (FIND_STARTATZONE(find))
2970                         start_at_zone = ISC_TRUE;
2971
2972                 /*
2973                  * Start V4.
2974                  */
2975                 if (WANT_INET(wanted_fetches) &&
2976                     fetch_name(adbname, start_at_zone,
2977                                dns_rdatatype_a) == ISC_R_SUCCESS) {
2978                         DP(DEF_LEVEL,
2979                            "dns_adb_createfind: started A fetch for name %p",
2980                            adbname);
2981                 }
2982
2983                 /*
2984                  * Start V6.
2985                  */
2986                 if (WANT_INET6(wanted_fetches) &&
2987                     fetch_name(adbname, start_at_zone,
2988                                dns_rdatatype_aaaa) == ISC_R_SUCCESS) {
2989                         DP(DEF_LEVEL,
2990                            "dns_adb_createfind: "
2991                            "started AAAA fetch for name %p",
2992                            adbname);
2993                 }
2994         }
2995
2996         /*
2997          * Run through the name and copy out the bits we are
2998          * interested in.
2999          */
3000         copy_namehook_lists(adb, find, qname, qtype, adbname, now);
3001
3002  post_copy:
3003         if (NAME_FETCH_V4(adbname))
3004                 query_pending |= DNS_ADBFIND_INET;
3005         if (NAME_FETCH_V6(adbname))
3006                 query_pending |= DNS_ADBFIND_INET6;
3007
3008         /*
3009          * Attach to the name's query list if there are queries
3010          * already running, and we have been asked to.
3011          */
3012         want_event = ISC_TRUE;
3013         if (!FIND_WANTEVENT(find))
3014                 want_event = ISC_FALSE;
3015         if (FIND_WANTEMPTYEVENT(find) && FIND_HAS_ADDRS(find))
3016                 want_event = ISC_FALSE;
3017         if ((wanted_addresses & query_pending) == 0)
3018                 want_event = ISC_FALSE;
3019         if (alias)
3020                 want_event = ISC_FALSE;
3021         if (want_event) {
3022                 find->adbname = adbname;
3023                 find->name_bucket = bucket;
3024                 ISC_LIST_APPEND(adbname->finds, find, plink);
3025                 find->query_pending = (query_pending & wanted_addresses);
3026                 find->flags &= ~DNS_ADBFIND_ADDRESSMASK;
3027                 find->flags |= (find->query_pending & DNS_ADBFIND_ADDRESSMASK);
3028                 DP(DEF_LEVEL, "createfind: attaching find %p to adbname %p",
3029                    find, adbname);
3030         } else {
3031                 /*
3032                  * Remove the flag so the caller knows there will never
3033                  * be an event, and set internal flags to fake that
3034                  * the event was sent and freed, so dns_adb_destroyfind() will
3035                  * do the right thing.
3036                  */
3037                 find->query_pending = (query_pending & wanted_addresses);
3038                 find->options &= ~DNS_ADBFIND_WANTEVENT;
3039                 find->flags |= (FIND_EVENT_SENT | FIND_EVENT_FREED);
3040                 find->flags &= ~DNS_ADBFIND_ADDRESSMASK;
3041         }
3042
3043         find->partial_result |= (adbname->partial_result & wanted_addresses);
3044         if (alias) {
3045                 if (target != NULL) {
3046                         result = dns_name_copy(&adbname->target, target, NULL);
3047                         if (result != ISC_R_SUCCESS)
3048                                 goto out;
3049                 }
3050                 result = DNS_R_ALIAS;
3051         } else
3052                 result = ISC_R_SUCCESS;
3053
3054         /*
3055          * Copy out error flags from the name structure into the find.
3056          */
3057         find->result_v4 = find_err_map[adbname->fetch_err];
3058         find->result_v6 = find_err_map[adbname->fetch6_err];
3059
3060  out:
3061         if (find != NULL) {
3062                 *findp = find;
3063
3064                 if (want_event) {
3065                         isc_task_t *taskp;
3066
3067                         INSIST((find->flags & DNS_ADBFIND_ADDRESSMASK) != 0);
3068                         taskp = NULL;
3069                         isc_task_attach(task, &taskp);
3070                         find->event.ev_sender = taskp;
3071                         find->event.ev_action = action;
3072                         find->event.ev_arg = arg;
3073                 }
3074         }
3075
3076         UNLOCK(&adb->namelocks[bucket]);
3077
3078         return (result);
3079 }
3080
3081 void
3082 dns_adb_destroyfind(dns_adbfind_t **findp) {
3083         dns_adbfind_t *find;
3084         dns_adbentry_t *entry;
3085         dns_adbaddrinfo_t *ai;
3086         int bucket;
3087         dns_adb_t *adb;
3088         isc_boolean_t overmem;
3089
3090         REQUIRE(findp != NULL && DNS_ADBFIND_VALID(*findp));
3091         find = *findp;
3092         *findp = NULL;
3093
3094         LOCK(&find->lock);
3095
3096         DP(DEF_LEVEL, "dns_adb_destroyfind on find %p", find);
3097
3098         adb = find->adb;
3099         REQUIRE(DNS_ADB_VALID(adb));
3100
3101         REQUIRE(FIND_EVENTFREED(find));
3102
3103         bucket = find->name_bucket;
3104         INSIST(bucket == DNS_ADB_INVALIDBUCKET);
3105
3106         UNLOCK(&find->lock);
3107
3108         /*
3109          * The find doesn't exist on any list, and nothing is locked.
3110          * Return the find to the memory pool, and decrement the adb's
3111          * reference count.
3112          */
3113         overmem = isc_mem_isovermem(adb->mctx);
3114         ai = ISC_LIST_HEAD(find->list);
3115         while (ai != NULL) {
3116                 ISC_LIST_UNLINK(find->list, ai, publink);
3117                 entry = ai->entry;
3118                 ai->entry = NULL;
3119                 INSIST(DNS_ADBENTRY_VALID(entry));
3120                 RUNTIME_CHECK(dec_entry_refcnt(adb, overmem, entry, ISC_TRUE) ==
3121                               ISC_FALSE);
3122                 free_adbaddrinfo(adb, &ai);
3123                 ai = ISC_LIST_HEAD(find->list);
3124         }
3125
3126         /*
3127          * WARNING:  The find is freed with the adb locked.  This is done
3128          * to avoid a race condition where we free the find, some other
3129          * thread tests to see if it should be destroyed, detects it should
3130          * be, destroys it, and then we try to lock it for our check, but the
3131          * lock is destroyed.
3132          */
3133         LOCK(&adb->lock);
3134         if (free_adbfind(adb, &find))
3135                 check_exit(adb);
3136         UNLOCK(&adb->lock);
3137 }
3138
3139 void
3140 dns_adb_cancelfind(dns_adbfind_t *find) {
3141         isc_event_t *ev;
3142         isc_task_t *task;
3143         dns_adb_t *adb;
3144         int bucket;
3145         int unlock_bucket;
3146
3147         LOCK(&find->lock);
3148
3149         DP(DEF_LEVEL, "dns_adb_cancelfind on find %p", find);
3150
3151         adb = find->adb;
3152         REQUIRE(DNS_ADB_VALID(adb));
3153
3154         REQUIRE(!FIND_EVENTFREED(find));
3155         REQUIRE(FIND_WANTEVENT(find));
3156
3157         bucket = find->name_bucket;
3158         if (bucket == DNS_ADB_INVALIDBUCKET)
3159                 goto cleanup;
3160
3161         /*
3162          * We need to get the adbname's lock to unlink the find.
3163          */
3164         unlock_bucket = bucket;
3165         violate_locking_hierarchy(&find->lock, &adb->namelocks[unlock_bucket]);
3166         bucket = find->name_bucket;
3167         if (bucket != DNS_ADB_INVALIDBUCKET) {
3168                 ISC_LIST_UNLINK(find->adbname->finds, find, plink);
3169                 find->adbname = NULL;
3170                 find->name_bucket = DNS_ADB_INVALIDBUCKET;
3171         }
3172         UNLOCK(&adb->namelocks[unlock_bucket]);
3173         bucket = DNS_ADB_INVALIDBUCKET;
3174         POST(bucket);
3175
3176  cleanup:
3177
3178         if (!FIND_EVENTSENT(find)) {
3179                 ev = &find->event;
3180                 task = ev->ev_sender;
3181                 ev->ev_sender = find;
3182                 ev->ev_type = DNS_EVENT_ADBCANCELED;
3183                 ev->ev_destroy = event_free;
3184                 ev->ev_destroy_arg = find;
3185                 find->result_v4 = ISC_R_CANCELED;
3186                 find->result_v6 = ISC_R_CANCELED;
3187
3188                 DP(DEF_LEVEL, "sending event %p to task %p for find %p",
3189                    ev, task, find);
3190
3191                 isc_task_sendanddetach(&task, (isc_event_t **)&ev);
3192         }
3193
3194         UNLOCK(&find->lock);
3195 }
3196
3197 void
3198 dns_adb_dump(dns_adb_t *adb, FILE *f) {
3199         unsigned int i;
3200         isc_stdtime_t now;
3201
3202         REQUIRE(DNS_ADB_VALID(adb));
3203         REQUIRE(f != NULL);
3204
3205         /*
3206          * Lock the adb itself, lock all the name buckets, then lock all
3207          * the entry buckets.  This should put the adb into a state where
3208          * nothing can change, so we can iterate through everything and
3209          * print at our leisure.
3210          */
3211
3212         LOCK(&adb->lock);
3213         isc_stdtime_get(&now);
3214
3215         for (i = 0; i < adb->nnames; i++)
3216                 RUNTIME_CHECK(cleanup_names(adb, i, now) == ISC_FALSE);
3217         for (i = 0; i < adb->nentries; i++)
3218                 RUNTIME_CHECK(cleanup_entries(adb, i, now) == ISC_FALSE);
3219
3220         dump_adb(adb, f, ISC_FALSE, now);
3221         UNLOCK(&adb->lock);
3222 }
3223
3224 static void
3225 dump_ttl(FILE *f, const char *legend, isc_stdtime_t value, isc_stdtime_t now) {
3226         if (value == INT_MAX)
3227                 return;
3228         fprintf(f, " [%s TTL %d]", legend, value - now);
3229 }
3230
3231 static void
3232 dump_adb(dns_adb_t *adb, FILE *f, isc_boolean_t debug, isc_stdtime_t now) {
3233         unsigned int i;
3234         dns_adbname_t *name;
3235         dns_adbentry_t *entry;
3236
3237         fprintf(f, ";\n; Address database dump\n;\n");
3238         if (debug)
3239                 fprintf(f, "; addr %p, erefcnt %u, irefcnt %u, finds out %u\n",
3240                         adb, adb->erefcnt, adb->irefcnt,
3241                         isc_mempool_getallocated(adb->nhmp));
3242
3243         for (i = 0; i < adb->nnames; i++)
3244                 LOCK(&adb->namelocks[i]);
3245         for (i = 0; i < adb->nentries; i++)
3246                 LOCK(&adb->entrylocks[i]);
3247
3248         /*
3249          * Dump the names
3250          */
3251         for (i = 0; i < adb->nnames; i++) {
3252                 name = ISC_LIST_HEAD(adb->names[i]);
3253                 if (name == NULL)
3254                         continue;
3255                 if (debug)
3256                         fprintf(f, "; bucket %d\n", i);
3257                 for (;
3258                      name != NULL;
3259                      name = ISC_LIST_NEXT(name, plink))
3260                 {
3261                         if (debug)
3262                                 fprintf(f, "; name %p (flags %08x)\n",
3263                                         name, name->flags);
3264
3265                         fprintf(f, "; ");
3266                         print_dns_name(f, &name->name);
3267                         if (dns_name_countlabels(&name->target) > 0) {
3268                                 fprintf(f, " alias ");
3269                                 print_dns_name(f, &name->target);
3270                         }
3271
3272                         dump_ttl(f, "v4", name->expire_v4, now);
3273                         dump_ttl(f, "v6", name->expire_v6, now);
3274                         dump_ttl(f, "target", name->expire_target, now);
3275
3276                         fprintf(f, " [v4 %s] [v6 %s]",
3277                                 errnames[name->fetch_err],
3278                                 errnames[name->fetch6_err]);
3279
3280                         fprintf(f, "\n");
3281
3282                         print_namehook_list(f, "v4", &name->v4, debug, now);
3283                         print_namehook_list(f, "v6", &name->v6, debug, now);
3284
3285                         if (debug)
3286                                 print_fetch_list(f, name);
3287                         if (debug)
3288                                 print_find_list(f, name);
3289
3290                 }
3291         }
3292
3293         fprintf(f, ";\n; Unassociated entries\n;\n");
3294
3295         for (i = 0; i < adb->nentries; i++) {
3296                 entry = ISC_LIST_HEAD(adb->entries[i]);
3297                 while (entry != NULL) {
3298                         if (entry->refcnt == 0)
3299                                 dump_entry(f, entry, debug, now);
3300                         entry = ISC_LIST_NEXT(entry, plink);
3301                 }
3302         }
3303
3304         /*
3305          * Unlock everything
3306          */
3307         for (i = 0; i < adb->nentries; i++)
3308                 UNLOCK(&adb->entrylocks[i]);
3309         for (i = 0; i < adb->nnames; i++)
3310                 UNLOCK(&adb->namelocks[i]);
3311 }
3312
3313 static void
3314 dump_entry(FILE *f, dns_adbentry_t *entry, isc_boolean_t debug,
3315            isc_stdtime_t now)
3316 {
3317         char addrbuf[ISC_NETADDR_FORMATSIZE];
3318         char typebuf[DNS_RDATATYPE_FORMATSIZE];
3319         isc_netaddr_t netaddr;
3320         dns_adblameinfo_t *li;
3321
3322         isc_netaddr_fromsockaddr(&netaddr, &entry->sockaddr);
3323         isc_netaddr_format(&netaddr, addrbuf, sizeof(addrbuf));
3324
3325         if (debug)
3326                 fprintf(f, ";\t%p: refcnt %u\n", entry, entry->refcnt);
3327
3328         fprintf(f, ";\t%s [srtt %u] [flags %08x]",
3329                 addrbuf, entry->srtt, entry->flags);
3330         if (entry->expires != 0)
3331                 fprintf(f, " [ttl %d]", entry->expires - now);
3332         fprintf(f, "\n");
3333         for (li = ISC_LIST_HEAD(entry->lameinfo);
3334              li != NULL;
3335              li = ISC_LIST_NEXT(li, plink)) {
3336                 fprintf(f, ";\t\t");
3337                 print_dns_name(f, &li->qname);
3338                 dns_rdatatype_format(li->qtype, typebuf, sizeof(typebuf));
3339                 fprintf(f, " %s [lame TTL %d]\n", typebuf,
3340                         li->lame_timer - now);
3341         }
3342 }
3343
3344 void
3345 dns_adb_dumpfind(dns_adbfind_t *find, FILE *f) {
3346         char tmp[512];
3347         const char *tmpp;
3348         dns_adbaddrinfo_t *ai;
3349         isc_sockaddr_t *sa;
3350
3351         /*
3352          * Not used currently, in the API Just In Case we
3353          * want to dump out the name and/or entries too.
3354          */
3355
3356         LOCK(&find->lock);
3357
3358         fprintf(f, ";Find %p\n", find);
3359         fprintf(f, ";\tqpending %08x partial %08x options %08x flags %08x\n",
3360                 find->query_pending, find->partial_result,
3361                 find->options, find->flags);
3362         fprintf(f, ";\tname_bucket %d, name %p, event sender %p\n",
3363                 find->name_bucket, find->adbname, find->event.ev_sender);
3364
3365         ai = ISC_LIST_HEAD(find->list);
3366         if (ai != NULL)
3367                 fprintf(f, "\tAddresses:\n");
3368         while (ai != NULL) {
3369                 sa = &ai->sockaddr;
3370                 switch (sa->type.sa.sa_family) {
3371                 case AF_INET:
3372                         tmpp = inet_ntop(AF_INET, &sa->type.sin.sin_addr,
3373                                          tmp, sizeof(tmp));
3374                         break;
3375                 case AF_INET6:
3376                         tmpp = inet_ntop(AF_INET6, &sa->type.sin6.sin6_addr,
3377                                          tmp, sizeof(tmp));
3378                         break;
3379                 default:
3380                         tmpp = "UnkFamily";
3381                 }
3382
3383                 if (tmpp == NULL)
3384                         tmpp = "BadAddress";
3385
3386                 fprintf(f, "\t\tentry %p, flags %08x"
3387                         " srtt %u addr %s\n",
3388                         ai->entry, ai->flags, ai->srtt, tmpp);
3389
3390                 ai = ISC_LIST_NEXT(ai, publink);
3391         }
3392
3393         UNLOCK(&find->lock);
3394 }
3395
3396 static void
3397 print_dns_name(FILE *f, dns_name_t *name) {
3398         char buf[DNS_NAME_FORMATSIZE];
3399
3400         INSIST(f != NULL);
3401
3402         dns_name_format(name, buf, sizeof(buf));
3403         fprintf(f, "%s", buf);
3404 }
3405
3406 static void
3407 print_namehook_list(FILE *f, const char *legend, dns_adbnamehooklist_t *list,
3408                     isc_boolean_t debug, isc_stdtime_t now)
3409 {
3410         dns_adbnamehook_t *nh;
3411
3412         for (nh = ISC_LIST_HEAD(*list);
3413              nh != NULL;
3414              nh = ISC_LIST_NEXT(nh, plink))
3415         {
3416                 if (debug)
3417                         fprintf(f, ";\tHook(%s) %p\n", legend, nh);
3418                 dump_entry(f, nh->entry, debug, now);
3419         }
3420 }
3421
3422 static inline void
3423 print_fetch(FILE *f, dns_adbfetch_t *ft, const char *type) {
3424         fprintf(f, "\t\tFetch(%s): %p -> { fetch %p }\n",
3425                 type, ft, ft->fetch);
3426 }
3427
3428 static void
3429 print_fetch_list(FILE *f, dns_adbname_t *n) {
3430         if (NAME_FETCH_A(n))
3431                 print_fetch(f, n->fetch_a, "A");
3432         if (NAME_FETCH_AAAA(n))
3433                 print_fetch(f, n->fetch_aaaa, "AAAA");
3434 }
3435
3436 static void
3437 print_find_list(FILE *f, dns_adbname_t *name) {
3438         dns_adbfind_t *find;
3439
3440         find = ISC_LIST_HEAD(name->finds);
3441         while (find != NULL) {
3442                 dns_adb_dumpfind(find, f);
3443                 find = ISC_LIST_NEXT(find, plink);
3444         }
3445 }
3446
3447 static isc_result_t
3448 dbfind_name(dns_adbname_t *adbname, isc_stdtime_t now, dns_rdatatype_t rdtype)
3449 {
3450         isc_result_t result;
3451         dns_rdataset_t rdataset;
3452         dns_adb_t *adb;
3453         dns_fixedname_t foundname;
3454         dns_name_t *fname;
3455
3456         INSIST(DNS_ADBNAME_VALID(adbname));
3457         adb = adbname->adb;
3458         INSIST(DNS_ADB_VALID(adb));
3459         INSIST(rdtype == dns_rdatatype_a || rdtype == dns_rdatatype_aaaa);
3460
3461         dns_fixedname_init(&foundname);
3462         fname = dns_fixedname_name(&foundname);
3463         dns_rdataset_init(&rdataset);
3464
3465         if (rdtype == dns_rdatatype_a)
3466                 adbname->fetch_err = FIND_ERR_UNEXPECTED;
3467         else
3468                 adbname->fetch6_err = FIND_ERR_UNEXPECTED;
3469
3470         /*
3471          * We need to specify whether to search static-stub zones (if
3472          * configured) depending on whether this is a "start at zone" lookup,
3473          * i.e., whether it's a "bailiwick" glue.  If it's bailiwick (in which
3474          * case NAME_STARTATZONE is set) we need to stop the search at any
3475          * matching static-stub zone without looking into the cache to honor
3476          * the configuration on which server we should send queries to.
3477          */
3478         result = dns_view_find2(adb->view, &adbname->name, rdtype, now,
3479                                 NAME_GLUEOK(adbname) ? DNS_DBFIND_GLUEOK : 0,
3480                                 ISC_TF(NAME_HINTOK(adbname)),
3481                                 (adbname->flags & NAME_STARTATZONE) != 0 ?
3482                                 ISC_TRUE : ISC_FALSE,
3483                                 NULL, NULL, fname, &rdataset, NULL);
3484
3485         /* XXXVIX this switch statement is too sparse to gen a jump table. */
3486         switch (result) {
3487         case DNS_R_GLUE:
3488         case DNS_R_HINT:
3489         case ISC_R_SUCCESS:
3490                 /*
3491                  * Found in the database.  Even if we can't copy out
3492                  * any information, return success, or else a fetch
3493                  * will be made, which will only make things worse.
3494                  */
3495                 if (rdtype == dns_rdatatype_a)
3496                         adbname->fetch_err = FIND_ERR_SUCCESS;
3497                 else
3498                         adbname->fetch6_err = FIND_ERR_SUCCESS;
3499                 result = import_rdataset(adbname, &rdataset, now);
3500                 break;
3501         case DNS_R_NXDOMAIN:
3502         case DNS_R_NXRRSET:
3503                 /*
3504                  * We're authoritative and the data doesn't exist.
3505                  * Make up a negative cache entry so we don't ask again
3506                  * for a while.
3507                  *
3508                  * XXXRTH  What time should we use?  I'm putting in 30 seconds
3509                  * for now.
3510                  */
3511                 if (rdtype == dns_rdatatype_a) {
3512                         adbname->expire_v4 = now + 30;
3513                         DP(NCACHE_LEVEL,
3514                            "adb name %p: Caching auth negative entry for A",
3515                            adbname);
3516                         if (result == DNS_R_NXDOMAIN)
3517                                 adbname->fetch_err = FIND_ERR_NXDOMAIN;
3518                         else
3519                                 adbname->fetch_err = FIND_ERR_NXRRSET;
3520                 } else {
3521                         DP(NCACHE_LEVEL,
3522                            "adb name %p: Caching auth negative entry for AAAA",
3523                            adbname);
3524                         adbname->expire_v6 = now + 30;
3525                         if (result == DNS_R_NXDOMAIN)
3526                                 adbname->fetch6_err = FIND_ERR_NXDOMAIN;
3527                         else
3528                                 adbname->fetch6_err = FIND_ERR_NXRRSET;
3529                 }
3530                 break;
3531         case DNS_R_NCACHENXDOMAIN:
3532         case DNS_R_NCACHENXRRSET:
3533                 /*
3534                  * We found a negative cache entry.  Pull the TTL from it
3535                  * so we won't ask again for a while.
3536                  */
3537                 rdataset.ttl = ttlclamp(rdataset.ttl);
3538                 if (rdtype == dns_rdatatype_a) {
3539                         adbname->expire_v4 = rdataset.ttl + now;
3540                         if (result == DNS_R_NCACHENXDOMAIN)
3541                                 adbname->fetch_err = FIND_ERR_NXDOMAIN;
3542                         else
3543                                 adbname->fetch_err = FIND_ERR_NXRRSET;
3544                         DP(NCACHE_LEVEL,
3545                           "adb name %p: Caching negative entry for A (ttl %u)",
3546                            adbname, rdataset.ttl);
3547                 } else {
3548                         DP(NCACHE_LEVEL,
3549                        "adb name %p: Caching negative entry for AAAA (ttl %u)",
3550                            adbname, rdataset.ttl);
3551                         adbname->expire_v6 = rdataset.ttl + now;
3552                         if (result == DNS_R_NCACHENXDOMAIN)
3553                                 adbname->fetch6_err = FIND_ERR_NXDOMAIN;
3554                         else
3555                                 adbname->fetch6_err = FIND_ERR_NXRRSET;
3556                 }
3557                 break;
3558         case DNS_R_CNAME:
3559         case DNS_R_DNAME:
3560                 /*
3561                  * Clear the hint and glue flags, so this will match
3562                  * more often.
3563                  */
3564                 adbname->flags &= ~(DNS_ADBFIND_GLUEOK | DNS_ADBFIND_HINTOK);
3565
3566                 rdataset.ttl = ttlclamp(rdataset.ttl);
3567                 clean_target(adb, &adbname->target);
3568                 adbname->expire_target = INT_MAX;
3569                 result = set_target(adb, &adbname->name, fname, &rdataset,
3570                                     &adbname->target);
3571                 if (result == ISC_R_SUCCESS) {
3572                         result = DNS_R_ALIAS;
3573                         DP(NCACHE_LEVEL,
3574                            "adb name %p: caching alias target",
3575                            adbname);
3576                         adbname->expire_target = rdataset.ttl + now;
3577                 }
3578                 if (rdtype == dns_rdatatype_a)
3579                         adbname->fetch_err = FIND_ERR_SUCCESS;
3580                 else
3581                         adbname->fetch6_err = FIND_ERR_SUCCESS;
3582                 break;
3583         }
3584
3585         if (dns_rdataset_isassociated(&rdataset))
3586                 dns_rdataset_disassociate(&rdataset);
3587
3588         return (result);
3589 }
3590
3591 static void
3592 fetch_callback(isc_task_t *task, isc_event_t *ev) {
3593         dns_fetchevent_t *dev;
3594         dns_adbname_t *name;
3595         dns_adb_t *adb;
3596         dns_adbfetch_t *fetch;
3597         int bucket;
3598         isc_eventtype_t ev_status;
3599         isc_stdtime_t now;
3600         isc_result_t result;
3601         unsigned int address_type;
3602         isc_boolean_t want_check_exit = ISC_FALSE;
3603
3604         UNUSED(task);
3605
3606         INSIST(ev->ev_type == DNS_EVENT_FETCHDONE);
3607         dev = (dns_fetchevent_t *)ev;
3608         name = ev->ev_arg;
3609         INSIST(DNS_ADBNAME_VALID(name));
3610         adb = name->adb;
3611         INSIST(DNS_ADB_VALID(adb));
3612
3613         bucket = name->lock_bucket;
3614         LOCK(&adb->namelocks[bucket]);
3615
3616         INSIST(NAME_FETCH_A(name) || NAME_FETCH_AAAA(name));
3617         address_type = 0;
3618         if (NAME_FETCH_A(name) && (name->fetch_a->fetch == dev->fetch)) {
3619                 address_type = DNS_ADBFIND_INET;
3620                 fetch = name->fetch_a;
3621                 name->fetch_a = NULL;
3622         } else if (NAME_FETCH_AAAA(name)
3623                    && (name->fetch_aaaa->fetch == dev->fetch)) {
3624                 address_type = DNS_ADBFIND_INET6;
3625                 fetch = name->fetch_aaaa;
3626                 name->fetch_aaaa = NULL;
3627         } else
3628                 fetch = NULL;
3629
3630         INSIST(address_type != 0 && fetch != NULL);
3631
3632         dns_resolver_destroyfetch(&fetch->fetch);
3633         dev->fetch = NULL;
3634
3635         ev_status = DNS_EVENT_ADBNOMOREADDRESSES;
3636
3637         /*
3638          * Cleanup things we don't care about.
3639          */
3640         if (dev->node != NULL)
3641                 dns_db_detachnode(dev->db, &dev->node);
3642         if (dev->db != NULL)
3643                 dns_db_detach(&dev->db);
3644
3645         /*
3646          * If this name is marked as dead, clean up, throwing away
3647          * potentially good data.
3648          */
3649         if (NAME_DEAD(name)) {
3650                 free_adbfetch(adb, &fetch);
3651                 isc_event_free(&ev);
3652
3653                 want_check_exit = kill_name(&name, DNS_EVENT_ADBCANCELED);
3654
3655                 UNLOCK(&adb->namelocks[bucket]);
3656
3657                 if (want_check_exit) {
3658                         LOCK(&adb->lock);
3659                         check_exit(adb);
3660                         UNLOCK(&adb->lock);
3661                 }
3662
3663                 return;
3664         }
3665
3666         isc_stdtime_get(&now);
3667
3668         /*
3669          * If we got a negative cache response, remember it.
3670          */
3671         if (NCACHE_RESULT(dev->result)) {
3672                 dev->rdataset->ttl = ttlclamp(dev->rdataset->ttl);
3673                 if (address_type == DNS_ADBFIND_INET) {
3674                         DP(NCACHE_LEVEL, "adb fetch name %p: "
3675                            "caching negative entry for A (ttl %u)",
3676                            name, dev->rdataset->ttl);
3677                         name->expire_v4 = ISC_MIN(name->expire_v4,
3678                                                   dev->rdataset->ttl + now);
3679                         if (dev->result == DNS_R_NCACHENXDOMAIN)
3680                                 name->fetch_err = FIND_ERR_NXDOMAIN;
3681                         else
3682                                 name->fetch_err = FIND_ERR_NXRRSET;
3683                         inc_stats(adb, dns_resstatscounter_gluefetchv4fail);
3684                 } else {
3685                         DP(NCACHE_LEVEL, "adb fetch name %p: "
3686                            "caching negative entry for AAAA (ttl %u)",
3687                            name, dev->rdataset->ttl);
3688                         name->expire_v6 = ISC_MIN(name->expire_v6,
3689                                                   dev->rdataset->ttl + now);
3690                         if (dev->result == DNS_R_NCACHENXDOMAIN)
3691                                 name->fetch6_err = FIND_ERR_NXDOMAIN;
3692                         else
3693                                 name->fetch6_err = FIND_ERR_NXRRSET;
3694                         inc_stats(adb, dns_resstatscounter_gluefetchv6fail);
3695                 }
3696                 goto out;
3697         }
3698
3699         /*
3700          * Handle CNAME/DNAME.
3701          */
3702         if (dev->result == DNS_R_CNAME || dev->result == DNS_R_DNAME) {
3703                 dev->rdataset->ttl = ttlclamp(dev->rdataset->ttl);
3704                 clean_target(adb, &name->target);
3705                 name->expire_target = INT_MAX;
3706                 result = set_target(adb, &name->name,
3707                                     dns_fixedname_name(&dev->foundname),
3708                                     dev->rdataset,
3709                                     &name->target);
3710                 if (result == ISC_R_SUCCESS) {
3711                         DP(NCACHE_LEVEL,
3712                            "adb fetch name %p: caching alias target",
3713                            name);
3714                         name->expire_target = dev->rdataset->ttl + now;
3715                 }
3716                 goto check_result;
3717         }
3718
3719         /*
3720          * Did we get back junk?  If so, and there are no more fetches
3721          * sitting out there, tell all the finds about it.
3722          */
3723         if (dev->result != ISC_R_SUCCESS) {
3724                 char buf[DNS_NAME_FORMATSIZE];
3725
3726                 dns_name_format(&name->name, buf, sizeof(buf));
3727                 DP(DEF_LEVEL, "adb: fetch of '%s' %s failed: %s",
3728                    buf, address_type == DNS_ADBFIND_INET ? "A" : "AAAA",
3729                    dns_result_totext(dev->result));
3730                 /* XXXMLG Don't pound on bad servers. */
3731                 if (address_type == DNS_ADBFIND_INET) {
3732                         name->expire_v4 = ISC_MIN(name->expire_v4, now + 300);
3733                         name->fetch_err = FIND_ERR_FAILURE;
3734                         inc_stats(adb, dns_resstatscounter_gluefetchv4fail);
3735                 } else {
3736                         name->expire_v6 = ISC_MIN(name->expire_v6, now + 300);
3737                         name->fetch6_err = FIND_ERR_FAILURE;
3738                         inc_stats(adb, dns_resstatscounter_gluefetchv6fail);
3739                 }
3740                 goto out;
3741         }
3742
3743         /*
3744          * We got something potentially useful.
3745          */
3746         result = import_rdataset(name, &fetch->rdataset, now);
3747
3748  check_result:
3749         if (result == ISC_R_SUCCESS) {
3750                 ev_status = DNS_EVENT_ADBMOREADDRESSES;
3751                 if (address_type == DNS_ADBFIND_INET)
3752                         name->fetch_err = FIND_ERR_SUCCESS;
3753                 else
3754                         name->fetch6_err = FIND_ERR_SUCCESS;
3755         }
3756
3757  out:
3758         free_adbfetch(adb, &fetch);
3759         isc_event_free(&ev);
3760
3761         clean_finds_at_name(name, ev_status, address_type);
3762
3763         UNLOCK(&adb->namelocks[bucket]);
3764 }
3765
3766 static isc_result_t
3767 fetch_name(dns_adbname_t *adbname,
3768            isc_boolean_t start_at_zone,
3769            dns_rdatatype_t type)
3770 {
3771         isc_result_t result;
3772         dns_adbfetch_t *fetch = NULL;
3773         dns_adb_t *adb;
3774         dns_fixedname_t fixed;
3775         dns_name_t *name;
3776         dns_rdataset_t rdataset;
3777         dns_rdataset_t *nameservers;
3778         unsigned int options;
3779
3780         INSIST(DNS_ADBNAME_VALID(adbname));
3781         adb = adbname->adb;
3782         INSIST(DNS_ADB_VALID(adb));
3783
3784         INSIST((type == dns_rdatatype_a && !NAME_FETCH_V4(adbname)) ||
3785                (type == dns_rdatatype_aaaa && !NAME_FETCH_V6(adbname)));
3786
3787         adbname->fetch_err = FIND_ERR_NOTFOUND;
3788
3789         name = NULL;
3790         nameservers = NULL;
3791         dns_rdataset_init(&rdataset);
3792
3793         options = DNS_FETCHOPT_NOVALIDATE;
3794         if (start_at_zone) {
3795                 DP(ENTER_LEVEL,
3796                    "fetch_name: starting at zone for name %p",
3797                    adbname);
3798                 dns_fixedname_init(&fixed);
3799                 name = dns_fixedname_name(&fixed);
3800                 result = dns_view_findzonecut2(adb->view, &adbname->name, name,
3801                                                0, 0, ISC_TRUE, ISC_FALSE,
3802                                                &rdataset, NULL);
3803                 if (result != ISC_R_SUCCESS && result != DNS_R_HINT)
3804                         goto cleanup;
3805                 nameservers = &rdataset;
3806                 options |= DNS_FETCHOPT_UNSHARED;
3807         }
3808
3809         fetch = new_adbfetch(adb);
3810         if (fetch == NULL) {
3811                 result = ISC_R_NOMEMORY;
3812                 goto cleanup;
3813         }
3814
3815         result = dns_resolver_createfetch(adb->view->resolver, &adbname->name,
3816                                           type, name, nameservers, NULL,
3817                                           options, adb->task, fetch_callback,
3818                                           adbname, &fetch->rdataset, NULL,
3819                                           &fetch->fetch);
3820         if (result != ISC_R_SUCCESS)
3821                 goto cleanup;
3822
3823         if (type == dns_rdatatype_a) {
3824                 adbname->fetch_a = fetch;
3825                 inc_stats(adb, dns_resstatscounter_gluefetchv4);
3826         } else {
3827                 adbname->fetch_aaaa = fetch;
3828                 inc_stats(adb, dns_resstatscounter_gluefetchv6);
3829         }
3830         fetch = NULL;  /* Keep us from cleaning this up below. */
3831
3832  cleanup:
3833         if (fetch != NULL)
3834                 free_adbfetch(adb, &fetch);
3835         if (dns_rdataset_isassociated(&rdataset))
3836                 dns_rdataset_disassociate(&rdataset);
3837
3838         return (result);
3839 }
3840
3841 /*
3842  * XXXMLG Needs to take a find argument and an address info, no zone or adb,
3843  * since these can be extracted from the find itself.
3844  */
3845 isc_result_t
3846 dns_adb_marklame(dns_adb_t *adb, dns_adbaddrinfo_t *addr, dns_name_t *qname,
3847                  dns_rdatatype_t qtype, isc_stdtime_t expire_time)
3848 {
3849         dns_adblameinfo_t *li;
3850         int bucket;
3851         isc_result_t result = ISC_R_SUCCESS;
3852
3853         REQUIRE(DNS_ADB_VALID(adb));
3854         REQUIRE(DNS_ADBADDRINFO_VALID(addr));
3855         REQUIRE(qname != NULL);
3856
3857         bucket = addr->entry->lock_bucket;
3858         LOCK(&adb->entrylocks[bucket]);
3859         li = ISC_LIST_HEAD(addr->entry->lameinfo);
3860         while (li != NULL &&
3861                (li->qtype != qtype || !dns_name_equal(qname, &li->qname)))
3862                 li = ISC_LIST_NEXT(li, plink);
3863         if (li != NULL) {
3864                 if (expire_time > li->lame_timer)
3865                         li->lame_timer = expire_time;
3866                 goto unlock;
3867         }
3868         li = new_adblameinfo(adb, qname, qtype);
3869         if (li == NULL) {
3870                 result = ISC_R_NOMEMORY;
3871                 goto unlock;
3872         }
3873
3874         li->lame_timer = expire_time;
3875
3876         ISC_LIST_PREPEND(addr->entry->lameinfo, li, plink);
3877  unlock:
3878         UNLOCK(&adb->entrylocks[bucket]);
3879
3880         return (result);
3881 }
3882
3883 void
3884 dns_adb_adjustsrtt(dns_adb_t *adb, dns_adbaddrinfo_t *addr,
3885                    unsigned int rtt, unsigned int factor)
3886 {
3887         int bucket;
3888         unsigned int new_srtt;
3889         isc_stdtime_t now;
3890
3891         REQUIRE(DNS_ADB_VALID(adb));
3892         REQUIRE(DNS_ADBADDRINFO_VALID(addr));
3893         REQUIRE(factor <= 10);
3894
3895         bucket = addr->entry->lock_bucket;
3896         LOCK(&adb->entrylocks[bucket]);
3897
3898         if (factor == DNS_ADB_RTTADJAGE)
3899                 new_srtt = addr->entry->srtt * 98 / 100;
3900         else
3901                 new_srtt = (addr->entry->srtt / 10 * factor)
3902                         + (rtt / 10 * (10 - factor));
3903
3904         addr->entry->srtt = new_srtt;
3905         addr->srtt = new_srtt;
3906
3907         isc_stdtime_get(&now);
3908         addr->entry->expires = now + ADB_ENTRY_WINDOW;
3909
3910         UNLOCK(&adb->entrylocks[bucket]);
3911 }
3912
3913 void
3914 dns_adb_changeflags(dns_adb_t *adb, dns_adbaddrinfo_t *addr,
3915                     unsigned int bits, unsigned int mask)
3916 {
3917         int bucket;
3918
3919         REQUIRE(DNS_ADB_VALID(adb));
3920         REQUIRE(DNS_ADBADDRINFO_VALID(addr));
3921
3922         bucket = addr->entry->lock_bucket;
3923         LOCK(&adb->entrylocks[bucket]);
3924
3925         addr->entry->flags = (addr->entry->flags & ~mask) | (bits & mask);
3926         /*
3927          * Note that we do not update the other bits in addr->flags with
3928          * the most recent values from addr->entry->flags.
3929          */
3930         addr->flags = (addr->flags & ~mask) | (bits & mask);
3931
3932         UNLOCK(&adb->entrylocks[bucket]);
3933 }
3934
3935 isc_result_t
3936 dns_adb_findaddrinfo(dns_adb_t *adb, isc_sockaddr_t *sa,
3937                      dns_adbaddrinfo_t **addrp, isc_stdtime_t now)
3938 {
3939         int bucket;
3940         dns_adbentry_t *entry;
3941         dns_adbaddrinfo_t *addr;
3942         isc_result_t result;
3943         in_port_t port;
3944
3945         REQUIRE(DNS_ADB_VALID(adb));
3946         REQUIRE(addrp != NULL && *addrp == NULL);
3947
3948         UNUSED(now);
3949
3950         result = ISC_R_SUCCESS;
3951         bucket = DNS_ADB_INVALIDBUCKET;
3952         entry = find_entry_and_lock(adb, sa, &bucket, now);
3953         INSIST(bucket != DNS_ADB_INVALIDBUCKET);
3954         if (adb->entry_sd[bucket]) {
3955                 result = ISC_R_SHUTTINGDOWN;
3956                 goto unlock;
3957         }
3958         if (entry == NULL) {
3959                 /*
3960                  * We don't know anything about this address.
3961                  */
3962                 entry = new_adbentry(adb);
3963                 if (entry == NULL) {
3964                         result = ISC_R_NOMEMORY;
3965                         goto unlock;
3966                 }
3967                 entry->sockaddr = *sa;
3968                 link_entry(adb, bucket, entry);
3969                 DP(ENTER_LEVEL, "findaddrinfo: new entry %p", entry);
3970         } else
3971                 DP(ENTER_LEVEL, "findaddrinfo: found entry %p", entry);
3972
3973         port = isc_sockaddr_getport(sa);
3974         addr = new_adbaddrinfo(adb, entry, port);
3975         if (addr == NULL) {
3976                 result = ISC_R_NOMEMORY;
3977         } else {
3978                 inc_entry_refcnt(adb, entry, ISC_FALSE);
3979                 *addrp = addr;
3980         }
3981
3982  unlock:
3983         UNLOCK(&adb->entrylocks[bucket]);
3984
3985         return (result);
3986 }
3987
3988 void
3989 dns_adb_freeaddrinfo(dns_adb_t *adb, dns_adbaddrinfo_t **addrp) {
3990         dns_adbaddrinfo_t *addr;
3991         dns_adbentry_t *entry;
3992         int bucket;
3993         isc_stdtime_t now;
3994         isc_boolean_t want_check_exit = ISC_FALSE;
3995         isc_boolean_t overmem;
3996
3997         REQUIRE(DNS_ADB_VALID(adb));
3998         REQUIRE(addrp != NULL);
3999         addr = *addrp;
4000         REQUIRE(DNS_ADBADDRINFO_VALID(addr));
4001         entry = addr->entry;
4002         REQUIRE(DNS_ADBENTRY_VALID(entry));
4003
4004         isc_stdtime_get(&now);
4005
4006         *addrp = NULL;
4007         overmem = isc_mem_isovermem(adb->mctx);
4008
4009         bucket = addr->entry->lock_bucket;
4010         LOCK(&adb->entrylocks[bucket]);
4011
4012         entry->expires = now + ADB_ENTRY_WINDOW;
4013
4014         want_check_exit = dec_entry_refcnt(adb, overmem, entry, ISC_FALSE);
4015
4016         UNLOCK(&adb->entrylocks[bucket]);
4017
4018         addr->entry = NULL;
4019         free_adbaddrinfo(adb, &addr);
4020
4021         if (want_check_exit) {
4022                 LOCK(&adb->lock);
4023                 check_exit(adb);
4024                 UNLOCK(&adb->lock);
4025         }
4026 }
4027
4028 void
4029 dns_adb_flush(dns_adb_t *adb) {
4030         unsigned int i;
4031
4032         INSIST(DNS_ADB_VALID(adb));
4033
4034         LOCK(&adb->lock);
4035
4036         /*
4037          * Call our cleanup routines.
4038          */
4039         for (i = 0; i < adb->nnames; i++)
4040                 RUNTIME_CHECK(cleanup_names(adb, i, INT_MAX) == ISC_FALSE);
4041         for (i = 0; i < adb->nentries; i++)
4042                 RUNTIME_CHECK(cleanup_entries(adb, i, INT_MAX) == ISC_FALSE);
4043
4044 #ifdef DUMP_ADB_AFTER_CLEANING
4045         dump_adb(adb, stdout, ISC_TRUE, INT_MAX);
4046 #endif
4047
4048         UNLOCK(&adb->lock);
4049 }
4050
4051 void
4052 dns_adb_flushname(dns_adb_t *adb, dns_name_t *name) {
4053         dns_adbname_t *adbname;
4054         dns_adbname_t *nextname;
4055         int bucket;
4056
4057         INSIST(DNS_ADB_VALID(adb));
4058
4059         LOCK(&adb->lock);
4060         bucket = dns_name_hash(name, ISC_FALSE) % adb->nnames;
4061         LOCK(&adb->namelocks[bucket]);
4062         adbname = ISC_LIST_HEAD(adb->names[bucket]);
4063         while (adbname != NULL) {
4064                 nextname = ISC_LIST_NEXT(adbname, plink);
4065                 if (!NAME_DEAD(adbname) &&
4066                     dns_name_equal(name, &adbname->name)) {
4067                         RUNTIME_CHECK(kill_name(&adbname,
4068                                                 DNS_EVENT_ADBCANCELED) ==
4069                                       ISC_FALSE);
4070                 }
4071                 adbname = nextname;
4072         }
4073         UNLOCK(&adb->namelocks[bucket]);
4074         UNLOCK(&adb->lock);
4075 }
4076
4077 static void
4078 water(void *arg, int mark) {
4079         /*
4080          * We're going to change the way to handle overmem condition: use
4081          * isc_mem_isovermem() instead of storing the state via this callback,
4082          * since the latter way tends to cause race conditions.
4083          * To minimize the change, and in case we re-enable the callback
4084          * approach, however, keep this function at the moment.
4085          */
4086
4087         dns_adb_t *adb = arg;
4088         isc_boolean_t overmem = ISC_TF(mark == ISC_MEM_HIWATER);
4089
4090         REQUIRE(DNS_ADB_VALID(adb));
4091
4092         DP(ISC_LOG_DEBUG(1),
4093            "adb reached %s water mark", overmem ? "high" : "low");
4094 }
4095
4096 void
4097 dns_adb_setadbsize(dns_adb_t *adb, isc_uint32_t size) {
4098         isc_uint32_t hiwater;
4099         isc_uint32_t lowater;
4100
4101         INSIST(DNS_ADB_VALID(adb));
4102
4103         if (size != 0 && size < DNS_ADB_MINADBSIZE)
4104                 size = DNS_ADB_MINADBSIZE;
4105
4106         hiwater = size - (size >> 3);   /* Approximately 7/8ths. */
4107         lowater = size - (size >> 2);   /* Approximately 3/4ths. */
4108
4109         if (size == 0 || hiwater == 0 || lowater == 0)
4110                 isc_mem_setwater(adb->mctx, water, adb, 0, 0);
4111         else
4112                 isc_mem_setwater(adb->mctx, water, adb, hiwater, lowater);
4113 }