contrib/bind9/lib/dns/adb.c

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