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: adb.c,v 1.264 2011/12/05 17:10:51 each Exp $ */
  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,
 305                                 isc_uint32_t, unsigned int);
 306 static isc_boolean_t check_expire_namehooks(dns_adbname_t *, isc_stdtime_t);
 307 static isc_boolean_t check_expire_entry(dns_adb_t *, dns_adbentry_t **,
 308                                         isc_stdtime_t);
 309 static void cancel_fetches_at_name(dns_adbname_t *);
 310 static isc_result_t dbfind_name(dns_adbname_t *, isc_stdtime_t,
 311                                 dns_rdatatype_t);
 312 static isc_result_t fetch_name(dns_adbname_t *, isc_boolean_t,
 313                                unsigned int, 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, 0, 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                     isc_uint32_t qtotal, 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                         find->qtotal += qtotal;
1472                         ev->ev_type = evtype;
1473                         ev->ev_destroy = event_free;
1474                         ev->ev_destroy_arg = find;
1475
1476                         DP(DEF_LEVEL,
1477                            "sending event %p to task %p for find %p",
1478                            ev, task, find);
1479
1480                         isc_task_sendanddetach(&task, (isc_event_t **)&ev);
1481                 } else {
1482                         DP(DEF_LEVEL, "cfan: skipping find %p", find);
1483                 }
1484
1485                 UNLOCK(&find->lock);
1486                 find = next_find;
1487         }
1488
1489         DP(ENTER_LEVEL, "EXIT clean_finds_at_name, name %p", name);
1490 }
1491
1492 static inline void
1493 check_exit(dns_adb_t *adb) {
1494         isc_event_t *event;
1495         /*
1496          * The caller must be holding the adb lock.
1497          */
1498         if (adb->shutting_down) {
1499                 /*
1500                  * If there aren't any external references either, we're
1501                  * done.  Send the control event to initiate shutdown.
1502                  */
1503                 INSIST(!adb->cevent_sent);      /* Sanity check. */
1504                 event = &adb->cevent;
1505                 isc_task_send(adb->task, &event);
1506                 adb->cevent_sent = ISC_TRUE;
1507         }
1508 }
1509
1510 static inline isc_boolean_t
1511 dec_adb_irefcnt(dns_adb_t *adb) {
1512         isc_event_t *event;
1513         isc_task_t *etask;
1514         isc_boolean_t result = ISC_FALSE;
1515
1516         LOCK(&adb->reflock);
1517
1518         INSIST(adb->irefcnt > 0);
1519         adb->irefcnt--;
1520
1521         if (adb->irefcnt == 0) {
1522                 event = ISC_LIST_HEAD(adb->whenshutdown);
1523                 while (event != NULL) {
1524                         ISC_LIST_UNLINK(adb->whenshutdown, event, ev_link);
1525                         etask = event->ev_sender;
1526                         event->ev_sender = adb;
1527                         isc_task_sendanddetach(&etask, &event);
1528                         event = ISC_LIST_HEAD(adb->whenshutdown);
1529                 }
1530         }
1531
1532         if (adb->irefcnt == 0 && adb->erefcnt == 0)
1533                 result = ISC_TRUE;
1534         UNLOCK(&adb->reflock);
1535         return (result);
1536 }
1537
1538 static inline void
1539 inc_adb_irefcnt(dns_adb_t *adb) {
1540         LOCK(&adb->reflock);
1541         adb->irefcnt++;
1542         UNLOCK(&adb->reflock);
1543 }
1544
1545 static inline void
1546 inc_adb_erefcnt(dns_adb_t *adb) {
1547         LOCK(&adb->reflock);
1548         adb->erefcnt++;
1549         UNLOCK(&adb->reflock);
1550 }
1551
1552 static inline void
1553 inc_entry_refcnt(dns_adb_t *adb, dns_adbentry_t *entry, isc_boolean_t lock) {
1554         int bucket;
1555
1556         bucket = entry->lock_bucket;
1557
1558         if (lock)
1559                 LOCK(&adb->entrylocks[bucket]);
1560
1561         entry->refcnt++;
1562
1563         if (lock)
1564                 UNLOCK(&adb->entrylocks[bucket]);
1565 }
1566
1567 static inline isc_boolean_t
1568 dec_entry_refcnt(dns_adb_t *adb, isc_boolean_t overmem, dns_adbentry_t *entry,
1569                  isc_boolean_t lock)
1570 {
1571         int bucket;
1572         isc_boolean_t destroy_entry;
1573         isc_boolean_t result = ISC_FALSE;
1574
1575         bucket = entry->lock_bucket;
1576
1577         if (lock)
1578                 LOCK(&adb->entrylocks[bucket]);
1579
1580         INSIST(entry->refcnt > 0);
1581         entry->refcnt--;
1582
1583         destroy_entry = ISC_FALSE;
1584         if (entry->refcnt == 0 &&
1585             (adb->entry_sd[bucket] || entry->expires == 0 || overmem ||
1586              (entry->flags & ENTRY_IS_DEAD) != 0)) {
1587                 destroy_entry = ISC_TRUE;
1588                 result = unlink_entry(adb, entry);
1589         }
1590
1591         if (lock)
1592                 UNLOCK(&adb->entrylocks[bucket]);
1593
1594         if (!destroy_entry)
1595                 return (result);
1596
1597         entry->lock_bucket = DNS_ADB_INVALIDBUCKET;
1598
1599         free_adbentry(adb, &entry);
1600         if (result)
1601                 result = dec_adb_irefcnt(adb);
1602
1603         return (result);
1604 }
1605
1606 static inline dns_adbname_t *
1607 new_adbname(dns_adb_t *adb, dns_name_t *dnsname) {
1608         dns_adbname_t *name;
1609
1610         name = isc_mempool_get(adb->nmp);
1611         if (name == NULL)
1612                 return (NULL);
1613
1614         dns_name_init(&name->name, NULL);
1615         if (dns_name_dup(dnsname, adb->mctx, &name->name) != ISC_R_SUCCESS) {
1616                 isc_mempool_put(adb->nmp, name);
1617                 return (NULL);
1618         }
1619         dns_name_init(&name->target, NULL);
1620         name->magic = DNS_ADBNAME_MAGIC;
1621         name->adb = adb;
1622         name->partial_result = 0;
1623         name->flags = 0;
1624         name->expire_v4 = INT_MAX;
1625         name->expire_v6 = INT_MAX;
1626         name->expire_target = INT_MAX;
1627         name->chains = 0;
1628         name->lock_bucket = DNS_ADB_INVALIDBUCKET;
1629         ISC_LIST_INIT(name->v4);
1630         ISC_LIST_INIT(name->v6);
1631         name->fetch_a = NULL;
1632         name->fetch_aaaa = NULL;
1633         name->fetch_err = FIND_ERR_UNEXPECTED;
1634         name->fetch6_err = FIND_ERR_UNEXPECTED;
1635         ISC_LIST_INIT(name->finds);
1636         ISC_LINK_INIT(name, plink);
1637
1638         LOCK(&adb->namescntlock);
1639         adb->namescnt++;
1640         if (!adb->grownames_sent && adb->excl != NULL &&
1641             adb->namescnt > (adb->nnames * 8))
1642         {
1643                 isc_event_t *event = &adb->grownames;
1644                 inc_adb_irefcnt(adb);
1645                 isc_task_send(adb->excl, &event);
1646                 adb->grownames_sent = ISC_TRUE;
1647         }
1648         UNLOCK(&adb->namescntlock);
1649
1650         return (name);
1651 }
1652
1653 static inline void
1654 free_adbname(dns_adb_t *adb, dns_adbname_t **name) {
1655         dns_adbname_t *n;
1656
1657         INSIST(name != NULL && DNS_ADBNAME_VALID(*name));
1658         n = *name;
1659         *name = NULL;
1660
1661         INSIST(!NAME_HAS_V4(n));
1662         INSIST(!NAME_HAS_V6(n));
1663         INSIST(!NAME_FETCH(n));
1664         INSIST(ISC_LIST_EMPTY(n->finds));
1665         INSIST(!ISC_LINK_LINKED(n, plink));
1666         INSIST(n->lock_bucket == DNS_ADB_INVALIDBUCKET);
1667         INSIST(n->adb == adb);
1668
1669         n->magic = 0;
1670         dns_name_free(&n->name, adb->mctx);
1671
1672         isc_mempool_put(adb->nmp, n);
1673         LOCK(&adb->namescntlock);
1674         adb->namescnt--;
1675         UNLOCK(&adb->namescntlock);
1676 }
1677
1678 static inline dns_adbnamehook_t *
1679 new_adbnamehook(dns_adb_t *adb, dns_adbentry_t *entry) {
1680         dns_adbnamehook_t *nh;
1681
1682         nh = isc_mempool_get(adb->nhmp);
1683         if (nh == NULL)
1684                 return (NULL);
1685
1686         nh->magic = DNS_ADBNAMEHOOK_MAGIC;
1687         nh->entry = entry;
1688         ISC_LINK_INIT(nh, plink);
1689
1690         return (nh);
1691 }
1692
1693 static inline void
1694 free_adbnamehook(dns_adb_t *adb, dns_adbnamehook_t **namehook) {
1695         dns_adbnamehook_t *nh;
1696
1697         INSIST(namehook != NULL && DNS_ADBNAMEHOOK_VALID(*namehook));
1698         nh = *namehook;
1699         *namehook = NULL;
1700
1701         INSIST(nh->entry == NULL);
1702         INSIST(!ISC_LINK_LINKED(nh, plink));
1703
1704         nh->magic = 0;
1705         isc_mempool_put(adb->nhmp, nh);
1706 }
1707
1708 static inline dns_adblameinfo_t *
1709 new_adblameinfo(dns_adb_t *adb, dns_name_t *qname, dns_rdatatype_t qtype) {
1710         dns_adblameinfo_t *li;
1711
1712         li = isc_mempool_get(adb->limp);
1713         if (li == NULL)
1714                 return (NULL);
1715
1716         dns_name_init(&li->qname, NULL);
1717         if (dns_name_dup(qname, adb->mctx, &li->qname) != ISC_R_SUCCESS) {
1718                 isc_mempool_put(adb->limp, li);
1719                 return (NULL);
1720         }
1721         li->magic = DNS_ADBLAMEINFO_MAGIC;
1722         li->lame_timer = 0;
1723         li->qtype = qtype;
1724         ISC_LINK_INIT(li, plink);
1725
1726         return (li);
1727 }
1728
1729 static inline void
1730 free_adblameinfo(dns_adb_t *adb, dns_adblameinfo_t **lameinfo) {
1731         dns_adblameinfo_t *li;
1732
1733         INSIST(lameinfo != NULL && DNS_ADBLAMEINFO_VALID(*lameinfo));
1734         li = *lameinfo;
1735         *lameinfo = NULL;
1736
1737         INSIST(!ISC_LINK_LINKED(li, plink));
1738
1739         dns_name_free(&li->qname, adb->mctx);
1740
1741         li->magic = 0;
1742
1743         isc_mempool_put(adb->limp, li);
1744 }
1745
1746 static inline dns_adbentry_t *
1747 new_adbentry(dns_adb_t *adb) {
1748         dns_adbentry_t *e;
1749         isc_uint32_t r;
1750
1751         e = isc_mempool_get(adb->emp);
1752         if (e == NULL)
1753                 return (NULL);
1754
1755         e->magic = DNS_ADBENTRY_MAGIC;
1756         e->lock_bucket = DNS_ADB_INVALIDBUCKET;
1757         e->refcnt = 0;
1758         e->flags = 0;
1759         isc_random_get(&r);
1760         e->srtt = (r & 0x1f) + 1;
1761         e->expires = 0;
1762         ISC_LIST_INIT(e->lameinfo);
1763         ISC_LINK_INIT(e, plink);
1764         LOCK(&adb->entriescntlock);
1765         adb->entriescnt++;
1766         if (!adb->growentries_sent && adb->growentries_sent &&
1767             adb->entriescnt > (adb->nentries * 8))
1768         {
1769                 isc_event_t *event = &adb->growentries;
1770                 inc_adb_irefcnt(adb);
1771                 isc_task_send(adb->task, &event);
1772                 adb->growentries_sent = ISC_TRUE;
1773         }
1774         UNLOCK(&adb->entriescntlock);
1775
1776         return (e);
1777 }
1778
1779 static inline void
1780 free_adbentry(dns_adb_t *adb, dns_adbentry_t **entry) {
1781         dns_adbentry_t *e;
1782         dns_adblameinfo_t *li;
1783
1784         INSIST(entry != NULL && DNS_ADBENTRY_VALID(*entry));
1785         e = *entry;
1786         *entry = NULL;
1787
1788         INSIST(e->lock_bucket == DNS_ADB_INVALIDBUCKET);
1789         INSIST(e->refcnt == 0);
1790         INSIST(!ISC_LINK_LINKED(e, plink));
1791
1792         e->magic = 0;
1793
1794         li = ISC_LIST_HEAD(e->lameinfo);
1795         while (li != NULL) {
1796                 ISC_LIST_UNLINK(e->lameinfo, li, plink);
1797                 free_adblameinfo(adb, &li);
1798                 li = ISC_LIST_HEAD(e->lameinfo);
1799         }
1800
1801         isc_mempool_put(adb->emp, e);
1802         LOCK(&adb->entriescntlock);
1803         adb->entriescnt--;
1804         UNLOCK(&adb->entriescntlock);
1805 }
1806
1807 static inline dns_adbfind_t *
1808 new_adbfind(dns_adb_t *adb) {
1809         dns_adbfind_t *h;
1810         isc_result_t result;
1811
1812         h = isc_mempool_get(adb->ahmp);
1813         if (h == NULL)
1814                 return (NULL);
1815
1816         /*
1817          * Public members.
1818          */
1819         h->magic = 0;
1820         h->adb = adb;
1821         h->partial_result = 0;
1822         h->options = 0;
1823         h->flags = 0;
1824         h->result_v4 = ISC_R_UNEXPECTED;
1825         h->result_v6 = ISC_R_UNEXPECTED;
1826         h->qtotal = 0;
1827         ISC_LINK_INIT(h, publink);
1828         ISC_LINK_INIT(h, plink);
1829         ISC_LIST_INIT(h->list);
1830         h->adbname = NULL;
1831         h->name_bucket = DNS_ADB_INVALIDBUCKET;
1832
1833         /*
1834          * private members
1835          */
1836         result = isc_mutex_init(&h->lock);
1837         if (result != ISC_R_SUCCESS) {
1838                 isc_mempool_put(adb->ahmp, h);
1839                 return (NULL);
1840         }
1841
1842         ISC_EVENT_INIT(&h->event, sizeof(isc_event_t), 0, 0, 0, NULL, NULL,
1843                        NULL, NULL, h);
1844
1845         inc_adb_irefcnt(adb);
1846         h->magic = DNS_ADBFIND_MAGIC;
1847         return (h);
1848 }
1849
1850 static inline dns_adbfetch_t *
1851 new_adbfetch(dns_adb_t *adb) {
1852         dns_adbfetch_t *f;
1853
1854         f = isc_mempool_get(adb->afmp);
1855         if (f == NULL)
1856                 return (NULL);
1857
1858         f->magic = 0;
1859         f->fetch = NULL;
1860
1861         dns_rdataset_init(&f->rdataset);
1862
1863         f->magic = DNS_ADBFETCH_MAGIC;
1864
1865         return (f);
1866 }
1867
1868 static inline void
1869 free_adbfetch(dns_adb_t *adb, dns_adbfetch_t **fetch) {
1870         dns_adbfetch_t *f;
1871
1872         INSIST(fetch != NULL && DNS_ADBFETCH_VALID(*fetch));
1873         f = *fetch;
1874         *fetch = NULL;
1875
1876         f->magic = 0;
1877
1878         if (dns_rdataset_isassociated(&f->rdataset))
1879                 dns_rdataset_disassociate(&f->rdataset);
1880
1881         isc_mempool_put(adb->afmp, f);
1882 }
1883
1884 static inline isc_boolean_t
1885 free_adbfind(dns_adb_t *adb, dns_adbfind_t **findp) {
1886         dns_adbfind_t *find;
1887
1888         INSIST(findp != NULL && DNS_ADBFIND_VALID(*findp));
1889         find = *findp;
1890         *findp = NULL;
1891
1892         INSIST(!FIND_HAS_ADDRS(find));
1893         INSIST(!ISC_LINK_LINKED(find, publink));
1894         INSIST(!ISC_LINK_LINKED(find, plink));
1895         INSIST(find->name_bucket == DNS_ADB_INVALIDBUCKET);
1896         INSIST(find->adbname == NULL);
1897
1898         find->magic = 0;
1899
1900         DESTROYLOCK(&find->lock);
1901         isc_mempool_put(adb->ahmp, find);
1902         return (dec_adb_irefcnt(adb));
1903 }
1904
1905 /*
1906  * Copy bits from the entry into the newly allocated addrinfo.  The entry
1907  * must be locked, and the reference count must be bumped up by one
1908  * if this function returns a valid pointer.
1909  */
1910 static inline dns_adbaddrinfo_t *
1911 new_adbaddrinfo(dns_adb_t *adb, dns_adbentry_t *entry, in_port_t port) {
1912         dns_adbaddrinfo_t *ai;
1913
1914         ai = isc_mempool_get(adb->aimp);
1915         if (ai == NULL)
1916                 return (NULL);
1917
1918         ai->magic = DNS_ADBADDRINFO_MAGIC;
1919         ai->sockaddr = entry->sockaddr;
1920         isc_sockaddr_setport(&ai->sockaddr, port);
1921         ai->srtt = entry->srtt;
1922         ai->flags = entry->flags;
1923         ai->entry = entry;
1924         ISC_LINK_INIT(ai, publink);
1925
1926         return (ai);
1927 }
1928
1929 static inline void
1930 free_adbaddrinfo(dns_adb_t *adb, dns_adbaddrinfo_t **ainfo) {
1931         dns_adbaddrinfo_t *ai;
1932
1933         INSIST(ainfo != NULL && DNS_ADBADDRINFO_VALID(*ainfo));
1934         ai = *ainfo;
1935         *ainfo = NULL;
1936
1937         INSIST(ai->entry == NULL);
1938         INSIST(!ISC_LINK_LINKED(ai, publink));
1939
1940         ai->magic = 0;
1941
1942         isc_mempool_put(adb->aimp, ai);
1943 }
1944
1945 /*
1946  * Search for the name.  NOTE:  The bucket is kept locked on both
1947  * success and failure, so it must always be unlocked by the caller!
1948  *
1949  * On the first call to this function, *bucketp must be set to
1950  * DNS_ADB_INVALIDBUCKET.
1951  */
1952 static inline dns_adbname_t *
1953 find_name_and_lock(dns_adb_t *adb, dns_name_t *name,
1954                    unsigned int options, int *bucketp)
1955 {
1956         dns_adbname_t *adbname;
1957         int bucket;
1958
1959         bucket = dns_name_fullhash(name, ISC_FALSE) % adb->nnames;
1960
1961         if (*bucketp == DNS_ADB_INVALIDBUCKET) {
1962                 LOCK(&adb->namelocks[bucket]);
1963                 *bucketp = bucket;
1964         } else if (*bucketp != bucket) {
1965                 UNLOCK(&adb->namelocks[*bucketp]);
1966                 LOCK(&adb->namelocks[bucket]);
1967                 *bucketp = bucket;
1968         }
1969
1970         adbname = ISC_LIST_HEAD(adb->names[bucket]);
1971         while (adbname != NULL) {
1972                 if (!NAME_DEAD(adbname)) {
1973                         if (dns_name_equal(name, &adbname->name)
1974                             && GLUEHINT_OK(adbname, options)
1975                             && STARTATZONE_MATCHES(adbname, options))
1976                                 return (adbname);
1977                 }
1978                 adbname = ISC_LIST_NEXT(adbname, plink);
1979         }
1980
1981         return (NULL);
1982 }
1983
1984 /*
1985  * Search for the address.  NOTE:  The bucket is kept locked on both
1986  * success and failure, so it must always be unlocked by the caller.
1987  *
1988  * On the first call to this function, *bucketp must be set to
1989  * DNS_ADB_INVALIDBUCKET.  This will cause a lock to occur.  On
1990  * later calls (within the same "lock path") it can be left alone, so
1991  * if this function is called multiple times locking is only done if
1992  * the bucket changes.
1993  */
1994 static inline dns_adbentry_t *
1995 find_entry_and_lock(dns_adb_t *adb, isc_sockaddr_t *addr, int *bucketp,
1996         isc_stdtime_t now)
1997 {
1998         dns_adbentry_t *entry, *entry_next;
1999         int bucket;
2000
2001         bucket = isc_sockaddr_hash(addr, ISC_TRUE) % adb->nentries;
2002
2003         if (*bucketp == DNS_ADB_INVALIDBUCKET) {
2004                 LOCK(&adb->entrylocks[bucket]);
2005                 *bucketp = bucket;
2006         } else if (*bucketp != bucket) {
2007                 UNLOCK(&adb->entrylocks[*bucketp]);
2008                 LOCK(&adb->entrylocks[bucket]);
2009                 *bucketp = bucket;
2010         }
2011
2012         /* Search the list, while cleaning up expired entries. */
2013         for (entry = ISC_LIST_HEAD(adb->entries[bucket]);
2014              entry != NULL;
2015              entry = entry_next) {
2016                 entry_next = ISC_LIST_NEXT(entry, plink);
2017                 (void)check_expire_entry(adb, &entry, now);
2018                 if (entry != NULL &&
2019                     isc_sockaddr_equal(addr, &entry->sockaddr)) {
2020                         ISC_LIST_UNLINK(adb->entries[bucket], entry, plink);
2021                         ISC_LIST_PREPEND(adb->entries[bucket], entry, plink);
2022                         return (entry);
2023                 }
2024         }
2025
2026         return (NULL);
2027 }
2028
2029 /*
2030  * Entry bucket MUST be locked!
2031  */
2032 static isc_boolean_t
2033 entry_is_lame(dns_adb_t *adb, dns_adbentry_t *entry, dns_name_t *qname,
2034               dns_rdatatype_t qtype, isc_stdtime_t now)
2035 {
2036         dns_adblameinfo_t *li, *next_li;
2037         isc_boolean_t is_bad;
2038
2039         is_bad = ISC_FALSE;
2040
2041         li = ISC_LIST_HEAD(entry->lameinfo);
2042         if (li == NULL)
2043                 return (ISC_FALSE);
2044         while (li != NULL) {
2045                 next_li = ISC_LIST_NEXT(li, plink);
2046
2047                 /*
2048                  * Has the entry expired?
2049                  */
2050                 if (li->lame_timer < now) {
2051                         ISC_LIST_UNLINK(entry->lameinfo, li, plink);
2052                         free_adblameinfo(adb, &li);
2053                 }
2054
2055                 /*
2056                  * Order tests from least to most expensive.
2057                  *
2058                  * We do not break out of the main loop here as
2059                  * we use the loop for house keeping.
2060                  */
2061                 if (li != NULL && !is_bad && li->qtype == qtype &&
2062                     dns_name_equal(qname, &li->qname))
2063                         is_bad = ISC_TRUE;
2064
2065                 li = next_li;
2066         }
2067
2068         return (is_bad);
2069 }
2070
2071 static void
2072 copy_namehook_lists(dns_adb_t *adb, dns_adbfind_t *find, dns_name_t *qname,
2073                     dns_rdatatype_t qtype, dns_adbname_t *name,
2074                     isc_stdtime_t now)
2075 {
2076         dns_adbnamehook_t *namehook;
2077         dns_adbaddrinfo_t *addrinfo;
2078         dns_adbentry_t *entry;
2079         int bucket;
2080
2081         bucket = DNS_ADB_INVALIDBUCKET;
2082
2083         if (find->options & DNS_ADBFIND_INET) {
2084                 namehook = ISC_LIST_HEAD(name->v4);
2085                 while (namehook != NULL) {
2086                         entry = namehook->entry;
2087                         bucket = entry->lock_bucket;
2088                         INSIST(bucket != DNS_ADB_INVALIDBUCKET);
2089                         LOCK(&adb->entrylocks[bucket]);
2090
2091                         if (!FIND_RETURNLAME(find)
2092                             && entry_is_lame(adb, entry, qname, qtype, now)) {
2093                                 find->options |= DNS_ADBFIND_LAMEPRUNED;
2094                                 goto nextv4;
2095                         }
2096                         addrinfo = new_adbaddrinfo(adb, entry, find->port);
2097                         if (addrinfo == NULL) {
2098                                 find->partial_result |= DNS_ADBFIND_INET;
2099                                 goto out;
2100                         }
2101                         /*
2102                          * Found a valid entry.  Add it to the find's list.
2103                          */
2104                         inc_entry_refcnt(adb, entry, ISC_FALSE);
2105                         ISC_LIST_APPEND(find->list, addrinfo, publink);
2106                         addrinfo = NULL;
2107                 nextv4:
2108                         UNLOCK(&adb->entrylocks[bucket]);
2109                         bucket = DNS_ADB_INVALIDBUCKET;
2110                         namehook = ISC_LIST_NEXT(namehook, plink);
2111                 }
2112         }
2113
2114         if (find->options & DNS_ADBFIND_INET6) {
2115                 namehook = ISC_LIST_HEAD(name->v6);
2116                 while (namehook != NULL) {
2117                         entry = namehook->entry;
2118                         bucket = entry->lock_bucket;
2119                         INSIST(bucket != DNS_ADB_INVALIDBUCKET);
2120                         LOCK(&adb->entrylocks[bucket]);
2121
2122                         if (!FIND_RETURNLAME(find)
2123                             && entry_is_lame(adb, entry, qname, qtype, now)) {
2124                                 find->options |= DNS_ADBFIND_LAMEPRUNED;
2125                                 goto nextv6;
2126                         }
2127                         addrinfo = new_adbaddrinfo(adb, entry, find->port);
2128                         if (addrinfo == NULL) {
2129                                 find->partial_result |= DNS_ADBFIND_INET6;
2130                                 goto out;
2131                         }
2132                         /*
2133                          * Found a valid entry.  Add it to the find's list.
2134                          */
2135                         inc_entry_refcnt(adb, entry, ISC_FALSE);
2136                         ISC_LIST_APPEND(find->list, addrinfo, publink);
2137                         addrinfo = NULL;
2138                 nextv6:
2139                         UNLOCK(&adb->entrylocks[bucket]);
2140                         bucket = DNS_ADB_INVALIDBUCKET;
2141                         namehook = ISC_LIST_NEXT(namehook, plink);
2142                 }
2143         }
2144
2145  out:
2146         if (bucket != DNS_ADB_INVALIDBUCKET)
2147                 UNLOCK(&adb->entrylocks[bucket]);
2148 }
2149
2150 static void
2151 shutdown_task(isc_task_t *task, isc_event_t *ev) {
2152         dns_adb_t *adb;
2153
2154         UNUSED(task);
2155
2156         adb = ev->ev_arg;
2157         INSIST(DNS_ADB_VALID(adb));
2158
2159         isc_event_free(&ev);
2160         /*
2161          * Wait for lock around check_exit() call to be released.
2162          */
2163         LOCK(&adb->lock);
2164         UNLOCK(&adb->lock);
2165         destroy(adb);
2166 }
2167
2168 /*
2169  * Name bucket must be locked; adb may be locked; no other locks held.
2170  */
2171 static isc_boolean_t
2172 check_expire_name(dns_adbname_t **namep, isc_stdtime_t now) {
2173         dns_adbname_t *name;
2174         isc_boolean_t result = ISC_FALSE;
2175
2176         INSIST(namep != NULL && DNS_ADBNAME_VALID(*namep));
2177         name = *namep;
2178
2179         if (NAME_HAS_V4(name) || NAME_HAS_V6(name))
2180                 return (result);
2181         if (NAME_FETCH(name))
2182                 return (result);
2183         if (!EXPIRE_OK(name->expire_v4, now))
2184                 return (result);
2185         if (!EXPIRE_OK(name->expire_v6, now))
2186                 return (result);
2187         if (!EXPIRE_OK(name->expire_target, now))
2188                 return (result);
2189
2190         /*
2191          * The name is empty.  Delete it.
2192          */
2193         result = kill_name(&name, DNS_EVENT_ADBEXPIRED);
2194         *namep = NULL;
2195
2196         /*
2197          * Our caller, or one of its callers, will be calling check_exit() at
2198          * some point, so we don't need to do it here.
2199          */
2200         return (result);
2201 }
2202
2203 /*%
2204  * Examine the tail entry of the LRU list to see if it expires or is stale
2205  * (unused for some period); if so, the name entry will be freed.  If the ADB
2206  * is in the overmem condition, the tail and the next to tail entries
2207  * will be unconditionally removed (unless they have an outstanding fetch).
2208  * We don't care about a race on 'overmem' at the risk of causing some
2209  * collateral damage or a small delay in starting cleanup, so we don't bother
2210  * to lock ADB (if it's not locked).
2211  *
2212  * Name bucket must be locked; adb may be locked; no other locks held.
2213  */
2214 static void
2215 check_stale_name(dns_adb_t *adb, int bucket, isc_stdtime_t now) {
2216         int victims, max_victims;
2217         dns_adbname_t *victim, *next_victim;
2218         isc_boolean_t overmem = isc_mem_isovermem(adb->mctx);
2219         int scans = 0;
2220
2221         INSIST(bucket != DNS_ADB_INVALIDBUCKET);
2222
2223         max_victims = overmem ? 2 : 1;
2224
2225         /*
2226          * We limit the number of scanned entries to 10 (arbitrary choice)
2227          * in order to avoid examining too many entries when there are many
2228          * tail entries that have fetches (this should be rare, but could
2229          * happen).
2230          */
2231         victim = ISC_LIST_TAIL(adb->names[bucket]);
2232         for (victims = 0;
2233              victim != NULL && victims < max_victims && scans < 10;
2234              victim = next_victim) {
2235                 INSIST(!NAME_DEAD(victim));
2236                 scans++;
2237                 next_victim = ISC_LIST_PREV(victim, plink);
2238                 (void)check_expire_name(&victim, now);
2239                 if (victim == NULL) {
2240                         victims++;
2241                         goto next;
2242                 }
2243
2244                 if (!NAME_FETCH(victim) &&
2245                     (overmem || victim->last_used + ADB_STALE_MARGIN <= now)) {
2246                         RUNTIME_CHECK(kill_name(&victim,
2247                                                 DNS_EVENT_ADBCANCELED) ==
2248                                       ISC_FALSE);
2249                         victims++;
2250                 }
2251
2252         next:
2253                 if (!overmem)
2254                         break;
2255         }
2256 }
2257
2258 /*
2259  * Entry bucket must be locked; adb may be locked; no other locks held.
2260  */
2261 static isc_boolean_t
2262 check_expire_entry(dns_adb_t *adb, dns_adbentry_t **entryp, isc_stdtime_t now)
2263 {
2264         dns_adbentry_t *entry;
2265         isc_boolean_t result = ISC_FALSE;
2266
2267         INSIST(entryp != NULL && DNS_ADBENTRY_VALID(*entryp));
2268         entry = *entryp;
2269
2270         if (entry->refcnt != 0)
2271                 return (result);
2272
2273         if (entry->expires == 0 || entry->expires > now)
2274                 return (result);
2275
2276         /*
2277          * The entry is not in use.  Delete it.
2278          */
2279         DP(DEF_LEVEL, "killing entry %p", entry);
2280         INSIST(ISC_LINK_LINKED(entry, plink));
2281         result = unlink_entry(adb, entry);
2282         free_adbentry(adb, &entry);
2283         if (result)
2284                 dec_adb_irefcnt(adb);
2285         *entryp = NULL;
2286         return (result);
2287 }
2288
2289 /*
2290  * ADB must be locked, and no other locks held.
2291  */
2292 static isc_boolean_t
2293 cleanup_names(dns_adb_t *adb, int bucket, isc_stdtime_t now) {
2294         dns_adbname_t *name;
2295         dns_adbname_t *next_name;
2296         isc_boolean_t result = ISC_FALSE;
2297
2298         DP(CLEAN_LEVEL, "cleaning name bucket %d", bucket);
2299
2300         LOCK(&adb->namelocks[bucket]);
2301         if (adb->name_sd[bucket]) {
2302                 UNLOCK(&adb->namelocks[bucket]);
2303                 return (result);
2304         }
2305
2306         name = ISC_LIST_HEAD(adb->names[bucket]);
2307         while (name != NULL) {
2308                 next_name = ISC_LIST_NEXT(name, plink);
2309                 INSIST(result == ISC_FALSE);
2310                 result = check_expire_namehooks(name, now);
2311                 if (!result)
2312                         result = check_expire_name(&name, now);
2313                 name = next_name;
2314         }
2315         UNLOCK(&adb->namelocks[bucket]);
2316         return (result);
2317 }
2318
2319 /*
2320  * ADB must be locked, and no other locks held.
2321  */
2322 static isc_boolean_t
2323 cleanup_entries(dns_adb_t *adb, int bucket, isc_stdtime_t now) {
2324         dns_adbentry_t *entry, *next_entry;
2325         isc_boolean_t result = ISC_FALSE;
2326
2327         DP(CLEAN_LEVEL, "cleaning entry bucket %d", bucket);
2328
2329         LOCK(&adb->entrylocks[bucket]);
2330         entry = ISC_LIST_HEAD(adb->entries[bucket]);
2331         while (entry != NULL) {
2332                 next_entry = ISC_LIST_NEXT(entry, plink);
2333                 INSIST(result == ISC_FALSE);
2334                 result = check_expire_entry(adb, &entry, now);
2335                 entry = next_entry;
2336         }
2337         UNLOCK(&adb->entrylocks[bucket]);
2338         return (result);
2339 }
2340
2341 static void
2342 destroy(dns_adb_t *adb) {
2343         adb->magic = 0;
2344
2345         isc_task_detach(&adb->task);
2346         if (adb->excl != NULL)
2347                 isc_task_detach(&adb->excl);
2348
2349         isc_mempool_destroy(&adb->nmp);
2350         isc_mempool_destroy(&adb->nhmp);
2351         isc_mempool_destroy(&adb->limp);
2352         isc_mempool_destroy(&adb->emp);
2353         isc_mempool_destroy(&adb->ahmp);
2354         isc_mempool_destroy(&adb->aimp);
2355         isc_mempool_destroy(&adb->afmp);
2356
2357         DESTROYMUTEXBLOCK(adb->entrylocks, adb->nentries);
2358         isc_mem_put(adb->mctx, adb->entries,
2359                     sizeof(*adb->entries) * adb->nentries);
2360         isc_mem_put(adb->mctx, adb->deadentries,
2361                     sizeof(*adb->deadentries) * adb->nentries);
2362         isc_mem_put(adb->mctx, adb->entrylocks,
2363                     sizeof(*adb->entrylocks) * adb->nentries);
2364         isc_mem_put(adb->mctx, adb->entry_sd,
2365                     sizeof(*adb->entry_sd) * adb->nentries);
2366         isc_mem_put(adb->mctx, adb->entry_refcnt,
2367                     sizeof(*adb->entry_refcnt) * adb->nentries);
2368
2369         DESTROYMUTEXBLOCK(adb->namelocks, adb->nnames);
2370         isc_mem_put(adb->mctx, adb->names,
2371                     sizeof(*adb->names) * adb->nnames);
2372         isc_mem_put(adb->mctx, adb->deadnames,
2373                     sizeof(*adb->deadnames) * adb->nnames);
2374         isc_mem_put(adb->mctx, adb->namelocks,
2375                     sizeof(*adb->namelocks) * adb->nnames);
2376         isc_mem_put(adb->mctx, adb->name_sd,
2377                     sizeof(*adb->name_sd) * adb->nnames);
2378         isc_mem_put(adb->mctx, adb->name_refcnt,
2379                     sizeof(*adb->name_refcnt) * adb->nnames);
2380
2381         DESTROYLOCK(&adb->reflock);
2382         DESTROYLOCK(&adb->lock);
2383         DESTROYLOCK(&adb->mplock);
2384         DESTROYLOCK(&adb->overmemlock);
2385         DESTROYLOCK(&adb->entriescntlock);
2386         DESTROYLOCK(&adb->namescntlock);
2387
2388         isc_mem_putanddetach(&adb->mctx, adb, sizeof(dns_adb_t));
2389 }
2390
2391
2392 /*
2393  * Public functions.
2394  */
2395
2396 isc_result_t
2397 dns_adb_create(isc_mem_t *mem, dns_view_t *view, isc_timermgr_t *timermgr,
2398                isc_taskmgr_t *taskmgr, dns_adb_t **newadb)
2399 {
2400         dns_adb_t *adb;
2401         isc_result_t result;
2402         unsigned int i;
2403
2404         REQUIRE(mem != NULL);
2405         REQUIRE(view != NULL);
2406         REQUIRE(timermgr != NULL); /* this is actually unused */
2407         REQUIRE(taskmgr != NULL);
2408         REQUIRE(newadb != NULL && *newadb == NULL);
2409
2410         UNUSED(timermgr);
2411
2412         adb = isc_mem_get(mem, sizeof(dns_adb_t));
2413         if (adb == NULL)
2414                 return (ISC_R_NOMEMORY);
2415
2416         /*
2417          * Initialize things here that cannot fail, and especially things
2418          * that must be NULL for the error return to work properly.
2419          */
2420         adb->magic = 0;
2421         adb->erefcnt = 1;
2422         adb->irefcnt = 0;
2423         adb->nmp = NULL;
2424         adb->nhmp = NULL;
2425         adb->limp = NULL;
2426         adb->emp = NULL;
2427         adb->ahmp = NULL;
2428         adb->aimp = NULL;
2429         adb->afmp = NULL;
2430         adb->task = NULL;
2431         adb->excl = NULL;
2432         adb->mctx = NULL;
2433         adb->view = view;
2434         adb->taskmgr = taskmgr;
2435         adb->next_cleanbucket = 0;
2436         ISC_EVENT_INIT(&adb->cevent, sizeof(adb->cevent), 0, NULL,
2437                        DNS_EVENT_ADBCONTROL, shutdown_task, adb,
2438                        adb, NULL, NULL);
2439         adb->cevent_sent = ISC_FALSE;
2440         adb->shutting_down = ISC_FALSE;
2441         ISC_LIST_INIT(adb->whenshutdown);
2442
2443         adb->nentries = nbuckets[0];
2444         adb->entriescnt = 0;
2445         adb->entries = NULL;
2446         adb->deadentries = NULL;
2447         adb->entry_sd = NULL;
2448         adb->entry_refcnt = NULL;
2449         adb->entrylocks = NULL;
2450         ISC_EVENT_INIT(&adb->growentries, sizeof(adb->growentries), 0, NULL,
2451                        DNS_EVENT_ADBGROWENTRIES, grow_entries, adb,
2452                        adb, NULL, NULL);
2453         adb->growentries_sent = ISC_FALSE;
2454
2455         adb->nnames = nbuckets[0];
2456         adb->namescnt = 0;
2457         adb->names = NULL;
2458         adb->deadnames = NULL;
2459         adb->name_sd = NULL;
2460         adb->name_refcnt = NULL;
2461         adb->namelocks = NULL;
2462         ISC_EVENT_INIT(&adb->grownames, sizeof(adb->grownames), 0, NULL,
2463                        DNS_EVENT_ADBGROWNAMES, grow_names, adb,
2464                        adb, NULL, NULL);
2465         adb->grownames_sent = ISC_FALSE;
2466
2467         result = isc_taskmgr_excltask(adb->taskmgr, &adb->excl);
2468         if (result != ISC_R_SUCCESS) {
2469                 DP(ISC_LOG_INFO, "adb: task-exclusive mode unavailable, "
2470                                  "intializing table sizes to %u\n",
2471                                  nbuckets[11]);
2472                 adb->nentries = nbuckets[11];
2473                 adb->nnames= nbuckets[11];
2474
2475         }
2476
2477         isc_mem_attach(mem, &adb->mctx);
2478
2479         result = isc_mutex_init(&adb->lock);
2480         if (result != ISC_R_SUCCESS)
2481                 goto fail0b;
2482
2483         result = isc_mutex_init(&adb->mplock);
2484         if (result != ISC_R_SUCCESS)
2485                 goto fail0c;
2486
2487         result = isc_mutex_init(&adb->reflock);
2488         if (result != ISC_R_SUCCESS)
2489                 goto fail0d;
2490
2491         result = isc_mutex_init(&adb->overmemlock);
2492         if (result != ISC_R_SUCCESS)
2493                 goto fail0e;
2494
2495         result = isc_mutex_init(&adb->entriescntlock);
2496         if (result != ISC_R_SUCCESS)
2497                 goto fail0f;
2498
2499         result = isc_mutex_init(&adb->namescntlock);
2500         if (result != ISC_R_SUCCESS)
2501                 goto fail0g;
2502
2503 #define ALLOCENTRY(adb, el) \
2504         do { \
2505                 (adb)->el = isc_mem_get((adb)->mctx, \
2506                                      sizeof(*(adb)->el) * (adb)->nentries); \
2507                 if ((adb)->el == NULL) { \
2508                         result = ISC_R_NOMEMORY; \
2509                         goto fail1; \
2510                 }\
2511         } while (0)
2512         ALLOCENTRY(adb, entries);
2513         ALLOCENTRY(adb, deadentries);
2514         ALLOCENTRY(adb, entrylocks);
2515         ALLOCENTRY(adb, entry_sd);
2516         ALLOCENTRY(adb, entry_refcnt);
2517 #undef ALLOCENTRY
2518
2519 #define ALLOCNAME(adb, el) \
2520         do { \
2521                 (adb)->el = isc_mem_get((adb)->mctx, \
2522                                      sizeof(*(adb)->el) * (adb)->nnames); \
2523                 if ((adb)->el == NULL) { \
2524                         result = ISC_R_NOMEMORY; \
2525                         goto fail1; \
2526                 }\
2527         } while (0)
2528         ALLOCNAME(adb, names);
2529         ALLOCNAME(adb, deadnames);
2530         ALLOCNAME(adb, namelocks);
2531         ALLOCNAME(adb, name_sd);
2532         ALLOCNAME(adb, name_refcnt);
2533 #undef ALLOCNAME
2534
2535         /*
2536          * Initialize the bucket locks for names and elements.
2537          * May as well initialize the list heads, too.
2538          */
2539         result = isc_mutexblock_init(adb->namelocks, adb->nnames);
2540         if (result != ISC_R_SUCCESS)
2541                 goto fail1;
2542         for (i = 0; i < adb->nnames; i++) {
2543                 ISC_LIST_INIT(adb->names[i]);
2544                 ISC_LIST_INIT(adb->deadnames[i]);
2545                 adb->name_sd[i] = ISC_FALSE;
2546                 adb->name_refcnt[i] = 0;
2547                 adb->irefcnt++;
2548         }
2549         for (i = 0; i < adb->nentries; i++) {
2550                 ISC_LIST_INIT(adb->entries[i]);
2551                 ISC_LIST_INIT(adb->deadentries[i]);
2552                 adb->entry_sd[i] = ISC_FALSE;
2553                 adb->entry_refcnt[i] = 0;
2554                 adb->irefcnt++;
2555         }
2556         result = isc_mutexblock_init(adb->entrylocks, adb->nentries);
2557         if (result != ISC_R_SUCCESS)
2558                 goto fail2;
2559
2560         /*
2561          * Memory pools
2562          */
2563 #define MPINIT(t, p, n) do { \
2564         result = isc_mempool_create(mem, sizeof(t), &(p)); \
2565         if (result != ISC_R_SUCCESS) \
2566                 goto fail3; \
2567         isc_mempool_setfreemax((p), FREE_ITEMS); \
2568         isc_mempool_setfillcount((p), FILL_COUNT); \
2569         isc_mempool_setname((p), n); \
2570         isc_mempool_associatelock((p), &adb->mplock); \
2571 } while (0)
2572
2573         MPINIT(dns_adbname_t, adb->nmp, "adbname");
2574         MPINIT(dns_adbnamehook_t, adb->nhmp, "adbnamehook");
2575         MPINIT(dns_adblameinfo_t, adb->limp, "adblameinfo");
2576         MPINIT(dns_adbentry_t, adb->emp, "adbentry");
2577         MPINIT(dns_adbfind_t, adb->ahmp, "adbfind");
2578         MPINIT(dns_adbaddrinfo_t, adb->aimp, "adbaddrinfo");
2579         MPINIT(dns_adbfetch_t, adb->afmp, "adbfetch");
2580
2581 #undef MPINIT
2582
2583         /*
2584          * Allocate an internal task.
2585          */
2586         result = isc_task_create(adb->taskmgr, 0, &adb->task);
2587         if (result != ISC_R_SUCCESS)
2588                 goto fail3;
2589
2590         isc_task_setname(adb->task, "ADB", adb);
2591
2592         /*
2593          * Normal return.
2594          */
2595         adb->magic = DNS_ADB_MAGIC;
2596         *newadb = adb;
2597         return (ISC_R_SUCCESS);
2598
2599  fail3:
2600         if (adb->task != NULL)
2601                 isc_task_detach(&adb->task);
2602
2603         /* clean up entrylocks */
2604         DESTROYMUTEXBLOCK(adb->entrylocks, adb->nentries);
2605
2606  fail2: /* clean up namelocks */
2607         DESTROYMUTEXBLOCK(adb->namelocks, adb->nnames);
2608
2609  fail1: /* clean up only allocated memory */
2610         if (adb->entries != NULL)
2611                 isc_mem_put(adb->mctx, adb->entries,
2612                             sizeof(*adb->entries) * adb->nentries);
2613         if (adb->deadentries != NULL)
2614                 isc_mem_put(adb->mctx, adb->deadentries,
2615                             sizeof(*adb->deadentries) * adb->nentries);
2616         if (adb->entrylocks != NULL)
2617                 isc_mem_put(adb->mctx, adb->entrylocks,
2618                             sizeof(*adb->entrylocks) * adb->nentries);
2619         if (adb->entry_sd != NULL)
2620                 isc_mem_put(adb->mctx, adb->entry_sd,
2621                             sizeof(*adb->entry_sd) * adb->nentries);
2622         if (adb->entry_refcnt != NULL)
2623                 isc_mem_put(adb->mctx, adb->entry_refcnt,
2624                             sizeof(*adb->entry_refcnt) * adb->nentries);
2625         if (adb->names != NULL)
2626                 isc_mem_put(adb->mctx, adb->names,
2627                             sizeof(*adb->names) * adb->nnames);
2628         if (adb->deadnames != NULL)
2629                 isc_mem_put(adb->mctx, adb->deadnames,
2630                             sizeof(*adb->deadnames) * adb->nnames);
2631         if (adb->namelocks != NULL)
2632                 isc_mem_put(adb->mctx, adb->namelocks,
2633                             sizeof(*adb->namelocks) * adb->nnames);
2634         if (adb->name_sd != NULL)
2635                 isc_mem_put(adb->mctx, adb->name_sd,
2636                             sizeof(*adb->name_sd) * adb->nnames);
2637         if (adb->name_refcnt != NULL)
2638                 isc_mem_put(adb->mctx, adb->name_refcnt,
2639                             sizeof(*adb->name_refcnt) * adb->nnames);
2640         if (adb->nmp != NULL)
2641                 isc_mempool_destroy(&adb->nmp);
2642         if (adb->nhmp != NULL)
2643                 isc_mempool_destroy(&adb->nhmp);
2644         if (adb->limp != NULL)
2645                 isc_mempool_destroy(&adb->limp);
2646         if (adb->emp != NULL)
2647                 isc_mempool_destroy(&adb->emp);
2648         if (adb->ahmp != NULL)
2649                 isc_mempool_destroy(&adb->ahmp);
2650         if (adb->aimp != NULL)
2651                 isc_mempool_destroy(&adb->aimp);
2652         if (adb->afmp != NULL)
2653                 isc_mempool_destroy(&adb->afmp);
2654
2655         DESTROYLOCK(&adb->namescntlock);
2656  fail0g:
2657         DESTROYLOCK(&adb->entriescntlock);
2658  fail0f:
2659         DESTROYLOCK(&adb->overmemlock);
2660  fail0e:
2661         DESTROYLOCK(&adb->reflock);
2662  fail0d:
2663         DESTROYLOCK(&adb->mplock);
2664  fail0c:
2665         DESTROYLOCK(&adb->lock);
2666  fail0b:
2667         isc_mem_putanddetach(&adb->mctx, adb, sizeof(dns_adb_t));
2668
2669         return (result);
2670 }
2671
2672 void
2673 dns_adb_attach(dns_adb_t *adb, dns_adb_t **adbx) {
2674
2675         REQUIRE(DNS_ADB_VALID(adb));
2676         REQUIRE(adbx != NULL && *adbx == NULL);
2677
2678         inc_adb_erefcnt(adb);
2679         *adbx = adb;
2680 }
2681
2682 void
2683 dns_adb_detach(dns_adb_t **adbx) {
2684         dns_adb_t *adb;
2685         isc_boolean_t need_exit_check;
2686
2687         REQUIRE(adbx != NULL && DNS_ADB_VALID(*adbx));
2688
2689         adb = *adbx;
2690         *adbx = NULL;
2691
2692         INSIST(adb->erefcnt > 0);
2693
2694         LOCK(&adb->reflock);
2695         adb->erefcnt--;
2696         need_exit_check = ISC_TF(adb->erefcnt == 0 && adb->irefcnt == 0);
2697         UNLOCK(&adb->reflock);
2698
2699         if (need_exit_check) {
2700                 LOCK(&adb->lock);
2701                 INSIST(adb->shutting_down);
2702                 check_exit(adb);
2703                 UNLOCK(&adb->lock);
2704         }
2705 }
2706
2707 void
2708 dns_adb_whenshutdown(dns_adb_t *adb, isc_task_t *task, isc_event_t **eventp) {
2709         isc_task_t *clone;
2710         isc_event_t *event;
2711         isc_boolean_t zeroirefcnt = ISC_FALSE;
2712
2713         /*
2714          * Send '*eventp' to 'task' when 'adb' has shutdown.
2715          */
2716
2717         REQUIRE(DNS_ADB_VALID(adb));
2718         REQUIRE(eventp != NULL);
2719
2720         event = *eventp;
2721         *eventp = NULL;
2722
2723         LOCK(&adb->lock);
2724
2725         LOCK(&adb->reflock);
2726         zeroirefcnt = ISC_TF(adb->irefcnt == 0);
2727
2728         if (adb->shutting_down && zeroirefcnt &&
2729             isc_mempool_getallocated(adb->ahmp) == 0) {
2730                 /*
2731                  * We're already shutdown.  Send the event.
2732                  */
2733                 event->ev_sender = adb;
2734                 isc_task_send(task, &event);
2735         } else {
2736                 clone = NULL;
2737                 isc_task_attach(task, &clone);
2738                 event->ev_sender = clone;
2739                 ISC_LIST_APPEND(adb->whenshutdown, event, ev_link);
2740         }
2741
2742         UNLOCK(&adb->reflock);
2743         UNLOCK(&adb->lock);
2744 }
2745
2746 void
2747 dns_adb_shutdown(dns_adb_t *adb) {
2748         isc_boolean_t need_check_exit;
2749
2750         /*
2751          * Shutdown 'adb'.
2752          */
2753
2754         LOCK(&adb->lock);
2755
2756         if (!adb->shutting_down) {
2757                 adb->shutting_down = ISC_TRUE;
2758                 isc_mem_setwater(adb->mctx, water, adb, 0, 0);
2759                 need_check_exit = shutdown_names(adb);
2760                 if (!need_check_exit)
2761                         need_check_exit = shutdown_entries(adb);
2762                 if (need_check_exit)
2763                         check_exit(adb);
2764         }
2765
2766         UNLOCK(&adb->lock);
2767 }
2768
2769 isc_result_t
2770 dns_adb_createfind(dns_adb_t *adb, isc_task_t *task, isc_taskaction_t action,
2771                    void *arg, dns_name_t *name, dns_name_t *qname,
2772                    dns_rdatatype_t qtype, unsigned int options,
2773                    isc_stdtime_t now, dns_name_t *target,
2774                    in_port_t port, dns_adbfind_t **findp)
2775 {
2776         return (dns_adb_createfind2(adb, task, action, arg, name,
2777                                     qname, qtype, options, now,
2778                                     target, port, 0, findp));
2779 }
2780
2781 isc_result_t
2782 dns_adb_createfind2(dns_adb_t *adb, isc_task_t *task, isc_taskaction_t action,
2783                     void *arg, dns_name_t *name, dns_name_t *qname,
2784                     dns_rdatatype_t qtype, unsigned int options,
2785                     isc_stdtime_t now, dns_name_t *target,
2786                     in_port_t port, unsigned int depth,
2787                     dns_adbfind_t **findp)
2788 {
2789         dns_adbfind_t *find;
2790         dns_adbname_t *adbname;
2791         int bucket;
2792         isc_boolean_t want_event, start_at_zone, alias, have_address;
2793         isc_result_t result;
2794         unsigned int wanted_addresses;
2795         unsigned int wanted_fetches;
2796         unsigned int query_pending;
2797
2798         REQUIRE(DNS_ADB_VALID(adb));
2799         if (task != NULL) {
2800                 REQUIRE(action != NULL);
2801         }
2802         REQUIRE(name != NULL);
2803         REQUIRE(qname != NULL);
2804         REQUIRE(findp != NULL && *findp == NULL);
2805         REQUIRE(target == NULL || dns_name_hasbuffer(target));
2806
2807         REQUIRE((options & DNS_ADBFIND_ADDRESSMASK) != 0);
2808
2809         result = ISC_R_UNEXPECTED;
2810         POST(result);
2811         wanted_addresses = (options & DNS_ADBFIND_ADDRESSMASK);
2812         wanted_fetches = 0;
2813         query_pending = 0;
2814         want_event = ISC_FALSE;
2815         start_at_zone = ISC_FALSE;
2816         alias = ISC_FALSE;
2817
2818         if (now == 0)
2819                 isc_stdtime_get(&now);
2820
2821         /*
2822          * XXXMLG  Move this comment somewhere else!
2823          *
2824          * Look up the name in our internal database.
2825          *
2826          * Possibilities:  Note that these are not always exclusive.
2827          *
2828          *      No name found.  In this case, allocate a new name header and
2829          *      an initial namehook or two.  If any of these allocations
2830          *      fail, clean up and return ISC_R_NOMEMORY.
2831          *
2832          *      Name found, valid addresses present.  Allocate one addrinfo
2833          *      structure for each found and append it to the linked list
2834          *      of addresses for this header.
2835          *
2836          *      Name found, queries pending.  In this case, if a task was
2837          *      passed in, allocate a job id, attach it to the name's job
2838          *      list and remember to tell the caller that there will be
2839          *      more info coming later.
2840          */
2841
2842         find = new_adbfind(adb);
2843         if (find == NULL)
2844                 return (ISC_R_NOMEMORY);
2845
2846         find->port = port;
2847
2848         /*
2849          * Remember what types of addresses we are interested in.
2850          */
2851         find->options = options;
2852         find->flags |= wanted_addresses;
2853         if (FIND_WANTEVENT(find)) {
2854                 REQUIRE(task != NULL);
2855         }
2856
2857         /*
2858          * Try to see if we know anything about this name at all.
2859          */
2860         bucket = DNS_ADB_INVALIDBUCKET;
2861         adbname = find_name_and_lock(adb, name, find->options, &bucket);
2862         INSIST(bucket != DNS_ADB_INVALIDBUCKET);
2863         if (adb->name_sd[bucket]) {
2864                 DP(DEF_LEVEL,
2865                    "dns_adb_createfind: returning ISC_R_SHUTTINGDOWN");
2866                 RUNTIME_CHECK(free_adbfind(adb, &find) == ISC_FALSE);
2867                 result = ISC_R_SHUTTINGDOWN;
2868                 goto out;
2869         }
2870
2871         /*
2872          * Nothing found.  Allocate a new adbname structure for this name.
2873          */
2874         if (adbname == NULL) {
2875                 /*
2876                  * See if there is any stale name at the end of list, and purge
2877                  * it if so.
2878                  */
2879                 check_stale_name(adb, bucket, now);
2880
2881                 adbname = new_adbname(adb, name);
2882                 if (adbname == NULL) {
2883                         RUNTIME_CHECK(free_adbfind(adb, &find) == ISC_FALSE);
2884                         result = ISC_R_NOMEMORY;
2885                         goto out;
2886                 }
2887                 link_name(adb, bucket, adbname);
2888                 if (FIND_HINTOK(find))
2889                         adbname->flags |= NAME_HINT_OK;
2890                 if (FIND_GLUEOK(find))
2891                         adbname->flags |= NAME_GLUE_OK;
2892                 if (FIND_STARTATZONE(find))
2893                         adbname->flags |= NAME_STARTATZONE;
2894         } else {
2895                 /* Move this name forward in the LRU list */
2896                 ISC_LIST_UNLINK(adb->names[bucket], adbname, plink);
2897                 ISC_LIST_PREPEND(adb->names[bucket], adbname, plink);
2898         }
2899         adbname->last_used = now;
2900
2901         /*
2902          * Expire old entries, etc.
2903          */
2904         RUNTIME_CHECK(check_expire_namehooks(adbname, now) == ISC_FALSE);
2905
2906         /*
2907          * Do we know that the name is an alias?
2908          */
2909         if (!EXPIRE_OK(adbname->expire_target, now)) {
2910                 /*
2911                  * Yes, it is.
2912                  */
2913                 DP(DEF_LEVEL,
2914                    "dns_adb_createfind: name %p is an alias (cached)",
2915                    adbname);
2916                 alias = ISC_TRUE;
2917                 goto post_copy;
2918         }
2919
2920         /*
2921          * Try to populate the name from the database and/or
2922          * start fetches.  First try looking for an A record
2923          * in the database.
2924          */
2925         if (!NAME_HAS_V4(adbname) && EXPIRE_OK(adbname->expire_v4, now)
2926             && WANT_INET(wanted_addresses)) {
2927                 result = dbfind_name(adbname, now, dns_rdatatype_a);
2928                 if (result == ISC_R_SUCCESS) {
2929                         DP(DEF_LEVEL,
2930                            "dns_adb_createfind: found A for name %p in db",
2931                            adbname);
2932                         goto v6;
2933                 }
2934
2935                 /*
2936                  * Did we get a CNAME or DNAME?
2937                  */
2938                 if (result == DNS_R_ALIAS) {
2939                         DP(DEF_LEVEL,
2940                            "dns_adb_createfind: name %p is an alias",
2941                            adbname);
2942                         alias = ISC_TRUE;
2943                         goto post_copy;
2944                 }
2945
2946                 /*
2947                  * If the name doesn't exist at all, don't bother with
2948                  * v6 queries; they won't work.
2949                  *
2950                  * If the name does exist but we didn't get our data, go
2951                  * ahead and try AAAA.
2952                  *
2953                  * If the result is neither of these, try a fetch for A.
2954                  */
2955                 if (NXDOMAIN_RESULT(result))
2956                         goto fetch;
2957                 else if (NXRRSET_RESULT(result))
2958                         goto v6;
2959
2960                 if (!NAME_FETCH_V4(adbname))
2961                         wanted_fetches |= DNS_ADBFIND_INET;
2962         }
2963
2964  v6:
2965         if (!NAME_HAS_V6(adbname) && EXPIRE_OK(adbname->expire_v6, now)
2966             && WANT_INET6(wanted_addresses)) {
2967                 result = dbfind_name(adbname, now, dns_rdatatype_aaaa);
2968                 if (result == ISC_R_SUCCESS) {
2969                         DP(DEF_LEVEL,
2970                            "dns_adb_createfind: found AAAA for name %p",
2971                            adbname);
2972                         goto fetch;
2973                 }
2974
2975                 /*
2976                  * Did we get a CNAME or DNAME?
2977                  */
2978                 if (result == DNS_R_ALIAS) {
2979                         DP(DEF_LEVEL,
2980                            "dns_adb_createfind: name %p is an alias",
2981                            adbname);
2982                         alias = ISC_TRUE;
2983                         goto post_copy;
2984                 }
2985
2986                 /*
2987                  * Listen to negative cache hints, and don't start
2988                  * another query.
2989                  */
2990                 if (NCACHE_RESULT(result) || AUTH_NX(result))
2991                         goto fetch;
2992
2993                 if (!NAME_FETCH_V6(adbname))
2994                         wanted_fetches |= DNS_ADBFIND_INET6;
2995         }
2996
2997  fetch:
2998         if ((WANT_INET(wanted_addresses) && NAME_HAS_V4(adbname)) ||
2999             (WANT_INET6(wanted_addresses) && NAME_HAS_V6(adbname)))
3000                 have_address = ISC_TRUE;
3001         else
3002                 have_address = ISC_FALSE;
3003         if (wanted_fetches != 0 &&
3004             ! (FIND_AVOIDFETCHES(find) && have_address)) {
3005                 /*
3006                  * We're missing at least one address family.  Either the
3007                  * caller hasn't instructed us to avoid fetches, or we don't
3008                  * know anything about any of the address families that would
3009                  * be acceptable so we have to launch fetches.
3010                  */
3011
3012                 if (FIND_STARTATZONE(find))
3013                         start_at_zone = ISC_TRUE;
3014
3015                 /*
3016                  * Start V4.
3017                  */
3018                 if (WANT_INET(wanted_fetches) &&
3019                     fetch_name(adbname, start_at_zone, depth,
3020                                dns_rdatatype_a) == ISC_R_SUCCESS) {
3021                         DP(DEF_LEVEL,
3022                            "dns_adb_createfind: started A fetch for name %p",
3023                            adbname);
3024                 }
3025
3026                 /*
3027                  * Start V6.
3028                  */
3029                 if (WANT_INET6(wanted_fetches) &&
3030                     fetch_name(adbname, start_at_zone, depth,
3031                                dns_rdatatype_aaaa) == ISC_R_SUCCESS) {
3032                         DP(DEF_LEVEL,
3033                            "dns_adb_createfind: "
3034                            "started AAAA fetch for name %p",
3035                            adbname);
3036                 }
3037         }
3038
3039         /*
3040          * Run through the name and copy out the bits we are
3041          * interested in.
3042          */
3043         copy_namehook_lists(adb, find, qname, qtype, adbname, now);
3044
3045  post_copy:
3046         if (NAME_FETCH_V4(adbname))
3047                 query_pending |= DNS_ADBFIND_INET;
3048         if (NAME_FETCH_V6(adbname))
3049                 query_pending |= DNS_ADBFIND_INET6;
3050
3051         /*
3052          * Attach to the name's query list if there are queries
3053          * already running, and we have been asked to.
3054          */
3055         want_event = ISC_TRUE;
3056         if (!FIND_WANTEVENT(find))
3057                 want_event = ISC_FALSE;
3058         if (FIND_WANTEMPTYEVENT(find) && FIND_HAS_ADDRS(find))
3059                 want_event = ISC_FALSE;
3060         if ((wanted_addresses & query_pending) == 0)
3061                 want_event = ISC_FALSE;
3062         if (alias)
3063                 want_event = ISC_FALSE;
3064         if (want_event) {
3065                 find->adbname = adbname;
3066                 find->name_bucket = bucket;
3067                 ISC_LIST_APPEND(adbname->finds, find, plink);
3068                 find->query_pending = (query_pending & wanted_addresses);
3069                 find->flags &= ~DNS_ADBFIND_ADDRESSMASK;
3070                 find->flags |= (find->query_pending & DNS_ADBFIND_ADDRESSMASK);
3071                 DP(DEF_LEVEL, "createfind: attaching find %p to adbname %p",
3072                    find, adbname);
3073         } else {
3074                 /*
3075                  * Remove the flag so the caller knows there will never
3076                  * be an event, and set internal flags to fake that
3077                  * the event was sent and freed, so dns_adb_destroyfind() will
3078                  * do the right thing.
3079                  */
3080                 find->query_pending = (query_pending & wanted_addresses);
3081                 find->options &= ~DNS_ADBFIND_WANTEVENT;
3082                 find->flags |= (FIND_EVENT_SENT | FIND_EVENT_FREED);
3083                 find->flags &= ~DNS_ADBFIND_ADDRESSMASK;
3084         }
3085
3086         find->partial_result |= (adbname->partial_result & wanted_addresses);
3087         if (alias) {
3088                 if (target != NULL) {
3089                         result = dns_name_copy(&adbname->target, target, NULL);
3090                         if (result != ISC_R_SUCCESS)
3091                                 goto out;
3092                 }
3093                 result = DNS_R_ALIAS;
3094         } else
3095                 result = ISC_R_SUCCESS;
3096
3097         /*
3098          * Copy out error flags from the name structure into the find.
3099          */
3100         find->result_v4 = find_err_map[adbname->fetch_err];
3101         find->result_v6 = find_err_map[adbname->fetch6_err];
3102
3103  out:
3104         if (find != NULL) {
3105                 *findp = find;
3106
3107                 if (want_event) {
3108                         isc_task_t *taskp;
3109
3110                         INSIST((find->flags & DNS_ADBFIND_ADDRESSMASK) != 0);
3111                         taskp = NULL;
3112                         isc_task_attach(task, &taskp);
3113                         find->event.ev_sender = taskp;
3114                         find->event.ev_action = action;
3115                         find->event.ev_arg = arg;
3116                 }
3117         }
3118
3119         UNLOCK(&adb->namelocks[bucket]);
3120
3121         return (result);
3122 }
3123
3124 void
3125 dns_adb_destroyfind(dns_adbfind_t **findp) {
3126         dns_adbfind_t *find;
3127         dns_adbentry_t *entry;
3128         dns_adbaddrinfo_t *ai;
3129         int bucket;
3130         dns_adb_t *adb;
3131         isc_boolean_t overmem;
3132
3133         REQUIRE(findp != NULL && DNS_ADBFIND_VALID(*findp));
3134         find = *findp;
3135         *findp = NULL;
3136
3137         LOCK(&find->lock);
3138
3139         DP(DEF_LEVEL, "dns_adb_destroyfind on find %p", find);
3140
3141         adb = find->adb;
3142         REQUIRE(DNS_ADB_VALID(adb));
3143
3144         REQUIRE(FIND_EVENTFREED(find));
3145
3146         bucket = find->name_bucket;
3147         INSIST(bucket == DNS_ADB_INVALIDBUCKET);
3148
3149         UNLOCK(&find->lock);
3150
3151         /*
3152          * The find doesn't exist on any list, and nothing is locked.
3153          * Return the find to the memory pool, and decrement the adb's
3154          * reference count.
3155          */
3156         overmem = isc_mem_isovermem(adb->mctx);
3157         ai = ISC_LIST_HEAD(find->list);
3158         while (ai != NULL) {
3159                 ISC_LIST_UNLINK(find->list, ai, publink);
3160                 entry = ai->entry;
3161                 ai->entry = NULL;
3162                 INSIST(DNS_ADBENTRY_VALID(entry));
3163                 RUNTIME_CHECK(dec_entry_refcnt(adb, overmem, entry, ISC_TRUE) ==
3164                               ISC_FALSE);
3165                 free_adbaddrinfo(adb, &ai);
3166                 ai = ISC_LIST_HEAD(find->list);
3167         }
3168
3169         /*
3170          * WARNING:  The find is freed with the adb locked.  This is done
3171          * to avoid a race condition where we free the find, some other
3172          * thread tests to see if it should be destroyed, detects it should
3173          * be, destroys it, and then we try to lock it for our check, but the
3174          * lock is destroyed.
3175          */
3176         LOCK(&adb->lock);
3177         if (free_adbfind(adb, &find))
3178                 check_exit(adb);
3179         UNLOCK(&adb->lock);
3180 }
3181
3182 void
3183 dns_adb_cancelfind(dns_adbfind_t *find) {
3184         isc_event_t *ev;
3185         isc_task_t *task;
3186         dns_adb_t *adb;
3187         int bucket;
3188         int unlock_bucket;
3189
3190         LOCK(&find->lock);
3191
3192         DP(DEF_LEVEL, "dns_adb_cancelfind on find %p", find);
3193
3194         adb = find->adb;
3195         REQUIRE(DNS_ADB_VALID(adb));
3196
3197         REQUIRE(!FIND_EVENTFREED(find));
3198         REQUIRE(FIND_WANTEVENT(find));
3199
3200         bucket = find->name_bucket;
3201         if (bucket == DNS_ADB_INVALIDBUCKET)
3202                 goto cleanup;
3203
3204         /*
3205          * We need to get the adbname's lock to unlink the find.
3206          */
3207         unlock_bucket = bucket;
3208         violate_locking_hierarchy(&find->lock, &adb->namelocks[unlock_bucket]);
3209         bucket = find->name_bucket;
3210         if (bucket != DNS_ADB_INVALIDBUCKET) {
3211                 ISC_LIST_UNLINK(find->adbname->finds, find, plink);
3212                 find->adbname = NULL;
3213                 find->name_bucket = DNS_ADB_INVALIDBUCKET;
3214         }
3215         UNLOCK(&adb->namelocks[unlock_bucket]);
3216         bucket = DNS_ADB_INVALIDBUCKET;
3217         POST(bucket);
3218
3219  cleanup:
3220
3221         if (!FIND_EVENTSENT(find)) {
3222                 ev = &find->event;
3223                 task = ev->ev_sender;
3224                 ev->ev_sender = find;
3225                 ev->ev_type = DNS_EVENT_ADBCANCELED;
3226                 ev->ev_destroy = event_free;
3227                 ev->ev_destroy_arg = find;
3228                 find->result_v4 = ISC_R_CANCELED;
3229                 find->result_v6 = ISC_R_CANCELED;
3230
3231                 DP(DEF_LEVEL, "sending event %p to task %p for find %p",
3232                    ev, task, find);
3233
3234                 isc_task_sendanddetach(&task, (isc_event_t **)&ev);
3235         }
3236
3237         UNLOCK(&find->lock);
3238 }
3239
3240 void
3241 dns_adb_dump(dns_adb_t *adb, FILE *f) {
3242         unsigned int i;
3243         isc_stdtime_t now;
3244
3245         REQUIRE(DNS_ADB_VALID(adb));
3246         REQUIRE(f != NULL);
3247
3248         /*
3249          * Lock the adb itself, lock all the name buckets, then lock all
3250          * the entry buckets.  This should put the adb into a state where
3251          * nothing can change, so we can iterate through everything and
3252          * print at our leisure.
3253          */
3254
3255         LOCK(&adb->lock);
3256         isc_stdtime_get(&now);
3257
3258         for (i = 0; i < adb->nnames; i++)
3259                 RUNTIME_CHECK(cleanup_names(adb, i, now) == ISC_FALSE);
3260         for (i = 0; i < adb->nentries; i++)
3261                 RUNTIME_CHECK(cleanup_entries(adb, i, now) == ISC_FALSE);
3262
3263         dump_adb(adb, f, ISC_FALSE, now);
3264         UNLOCK(&adb->lock);
3265 }
3266
3267 static void
3268 dump_ttl(FILE *f, const char *legend, isc_stdtime_t value, isc_stdtime_t now) {
3269         if (value == INT_MAX)
3270                 return;
3271         fprintf(f, " [%s TTL %d]", legend, value - now);
3272 }
3273
3274 static void
3275 dump_adb(dns_adb_t *adb, FILE *f, isc_boolean_t debug, isc_stdtime_t now) {
3276         unsigned int i;
3277         dns_adbname_t *name;
3278         dns_adbentry_t *entry;
3279
3280         fprintf(f, ";\n; Address database dump\n;\n");
3281         if (debug)
3282                 fprintf(f, "; addr %p, erefcnt %u, irefcnt %u, finds out %u\n",
3283                         adb, adb->erefcnt, adb->irefcnt,
3284                         isc_mempool_getallocated(adb->nhmp));
3285
3286         for (i = 0; i < adb->nnames; i++)
3287                 LOCK(&adb->namelocks[i]);
3288         for (i = 0; i < adb->nentries; i++)
3289                 LOCK(&adb->entrylocks[i]);
3290
3291         /*
3292          * Dump the names
3293          */
3294         for (i = 0; i < adb->nnames; i++) {
3295                 name = ISC_LIST_HEAD(adb->names[i]);
3296                 if (name == NULL)
3297                         continue;
3298                 if (debug)
3299                         fprintf(f, "; bucket %d\n", i);
3300                 for (;
3301                      name != NULL;
3302                      name = ISC_LIST_NEXT(name, plink))
3303                 {
3304                         if (debug)
3305                                 fprintf(f, "; name %p (flags %08x)\n",
3306                                         name, name->flags);
3307
3308                         fprintf(f, "; ");
3309                         print_dns_name(f, &name->name);
3310                         if (dns_name_countlabels(&name->target) > 0) {
3311                                 fprintf(f, " alias ");
3312                                 print_dns_name(f, &name->target);
3313                         }
3314
3315                         dump_ttl(f, "v4", name->expire_v4, now);
3316                         dump_ttl(f, "v6", name->expire_v6, now);
3317                         dump_ttl(f, "target", name->expire_target, now);
3318
3319                         fprintf(f, " [v4 %s] [v6 %s]",
3320                                 errnames[name->fetch_err],
3321                                 errnames[name->fetch6_err]);
3322
3323                         fprintf(f, "\n");
3324
3325                         print_namehook_list(f, "v4", &name->v4, debug, now);
3326                         print_namehook_list(f, "v6", &name->v6, debug, now);
3327
3328                         if (debug)
3329                                 print_fetch_list(f, name);
3330                         if (debug)
3331                                 print_find_list(f, name);
3332
3333                 }
3334         }
3335
3336         fprintf(f, ";\n; Unassociated entries\n;\n");
3337
3338         for (i = 0; i < adb->nentries; i++) {
3339                 entry = ISC_LIST_HEAD(adb->entries[i]);
3340                 while (entry != NULL) {
3341                         if (entry->refcnt == 0)
3342                                 dump_entry(f, entry, debug, now);
3343                         entry = ISC_LIST_NEXT(entry, plink);
3344                 }
3345         }
3346
3347         /*
3348          * Unlock everything
3349          */
3350         for (i = 0; i < adb->nentries; i++)
3351                 UNLOCK(&adb->entrylocks[i]);
3352         for (i = 0; i < adb->nnames; i++)
3353                 UNLOCK(&adb->namelocks[i]);
3354 }
3355
3356 static void
3357 dump_entry(FILE *f, dns_adbentry_t *entry, isc_boolean_t debug,
3358            isc_stdtime_t now)
3359 {
3360         char addrbuf[ISC_NETADDR_FORMATSIZE];
3361         char typebuf[DNS_RDATATYPE_FORMATSIZE];
3362         isc_netaddr_t netaddr;
3363         dns_adblameinfo_t *li;
3364
3365         isc_netaddr_fromsockaddr(&netaddr, &entry->sockaddr);
3366         isc_netaddr_format(&netaddr, addrbuf, sizeof(addrbuf));
3367
3368         if (debug)
3369                 fprintf(f, ";\t%p: refcnt %u\n", entry, entry->refcnt);
3370
3371         fprintf(f, ";\t%s [srtt %u] [flags %08x]",
3372                 addrbuf, entry->srtt, entry->flags);
3373         if (entry->expires != 0)
3374                 fprintf(f, " [ttl %d]", entry->expires - now);
3375         fprintf(f, "\n");
3376         for (li = ISC_LIST_HEAD(entry->lameinfo);
3377              li != NULL;
3378              li = ISC_LIST_NEXT(li, plink)) {
3379                 fprintf(f, ";\t\t");
3380                 print_dns_name(f, &li->qname);
3381                 dns_rdatatype_format(li->qtype, typebuf, sizeof(typebuf));
3382                 fprintf(f, " %s [lame TTL %d]\n", typebuf,
3383                         li->lame_timer - now);
3384         }
3385 }
3386
3387 void
3388 dns_adb_dumpfind(dns_adbfind_t *find, FILE *f) {
3389         char tmp[512];
3390         const char *tmpp;
3391         dns_adbaddrinfo_t *ai;
3392         isc_sockaddr_t *sa;
3393
3394         /*
3395          * Not used currently, in the API Just In Case we
3396          * want to dump out the name and/or entries too.
3397          */
3398
3399         LOCK(&find->lock);
3400
3401         fprintf(f, ";Find %p\n", find);
3402         fprintf(f, ";\tqpending %08x partial %08x options %08x flags %08x\n",
3403                 find->query_pending, find->partial_result,
3404                 find->options, find->flags);
3405         fprintf(f, ";\tname_bucket %d, name %p, event sender %p\n",
3406                 find->name_bucket, find->adbname, find->event.ev_sender);
3407
3408         ai = ISC_LIST_HEAD(find->list);
3409         if (ai != NULL)
3410                 fprintf(f, "\tAddresses:\n");
3411         while (ai != NULL) {
3412                 sa = &ai->sockaddr;
3413                 switch (sa->type.sa.sa_family) {
3414                 case AF_INET:
3415                         tmpp = inet_ntop(AF_INET, &sa->type.sin.sin_addr,
3416                                          tmp, sizeof(tmp));
3417                         break;
3418                 case AF_INET6:
3419                         tmpp = inet_ntop(AF_INET6, &sa->type.sin6.sin6_addr,
3420                                          tmp, sizeof(tmp));
3421                         break;
3422                 default:
3423                         tmpp = "UnkFamily";
3424                 }
3425
3426                 if (tmpp == NULL)
3427                         tmpp = "BadAddress";
3428
3429                 fprintf(f, "\t\tentry %p, flags %08x"
3430                         " srtt %u addr %s\n",
3431                         ai->entry, ai->flags, ai->srtt, tmpp);
3432
3433                 ai = ISC_LIST_NEXT(ai, publink);
3434         }
3435
3436         UNLOCK(&find->lock);
3437 }
3438
3439 static void
3440 print_dns_name(FILE *f, dns_name_t *name) {
3441         char buf[DNS_NAME_FORMATSIZE];
3442
3443         INSIST(f != NULL);
3444
3445         dns_name_format(name, buf, sizeof(buf));
3446         fprintf(f, "%s", buf);
3447 }
3448
3449 static void
3450 print_namehook_list(FILE *f, const char *legend, dns_adbnamehooklist_t *list,
3451                     isc_boolean_t debug, isc_stdtime_t now)
3452 {
3453         dns_adbnamehook_t *nh;
3454
3455         for (nh = ISC_LIST_HEAD(*list);
3456              nh != NULL;
3457              nh = ISC_LIST_NEXT(nh, plink))
3458         {
3459                 if (debug)
3460                         fprintf(f, ";\tHook(%s) %p\n", legend, nh);
3461                 dump_entry(f, nh->entry, debug, now);
3462         }
3463 }
3464
3465 static inline void
3466 print_fetch(FILE *f, dns_adbfetch_t *ft, const char *type) {
3467         fprintf(f, "\t\tFetch(%s): %p -> { fetch %p }\n",
3468                 type, ft, ft->fetch);
3469 }
3470
3471 static void
3472 print_fetch_list(FILE *f, dns_adbname_t *n) {
3473         if (NAME_FETCH_A(n))
3474                 print_fetch(f, n->fetch_a, "A");
3475         if (NAME_FETCH_AAAA(n))
3476                 print_fetch(f, n->fetch_aaaa, "AAAA");
3477 }
3478
3479 static void
3480 print_find_list(FILE *f, dns_adbname_t *name) {
3481         dns_adbfind_t *find;
3482
3483         find = ISC_LIST_HEAD(name->finds);
3484         while (find != NULL) {
3485                 dns_adb_dumpfind(find, f);
3486                 find = ISC_LIST_NEXT(find, plink);
3487         }
3488 }
3489
3490 static isc_result_t
3491 dbfind_name(dns_adbname_t *adbname, isc_stdtime_t now, dns_rdatatype_t rdtype)
3492 {
3493         isc_result_t result;
3494         dns_rdataset_t rdataset;
3495         dns_adb_t *adb;
3496         dns_fixedname_t foundname;
3497         dns_name_t *fname;
3498
3499         INSIST(DNS_ADBNAME_VALID(adbname));
3500         adb = adbname->adb;
3501         INSIST(DNS_ADB_VALID(adb));
3502         INSIST(rdtype == dns_rdatatype_a || rdtype == dns_rdatatype_aaaa);
3503
3504         dns_fixedname_init(&foundname);
3505         fname = dns_fixedname_name(&foundname);
3506         dns_rdataset_init(&rdataset);
3507
3508         if (rdtype == dns_rdatatype_a)
3509                 adbname->fetch_err = FIND_ERR_UNEXPECTED;
3510         else
3511                 adbname->fetch6_err = FIND_ERR_UNEXPECTED;
3512
3513         /*
3514          * We need to specify whether to search static-stub zones (if
3515          * configured) depending on whether this is a "start at zone" lookup,
3516          * i.e., whether it's a "bailiwick" glue.  If it's bailiwick (in which
3517          * case NAME_STARTATZONE is set) we need to stop the search at any
3518          * matching static-stub zone without looking into the cache to honor
3519          * the configuration on which server we should send queries to.
3520          */
3521         result = dns_view_find2(adb->view, &adbname->name, rdtype, now,
3522                                 NAME_GLUEOK(adbname) ? DNS_DBFIND_GLUEOK : 0,
3523                                 ISC_TF(NAME_HINTOK(adbname)),
3524                                 (adbname->flags & NAME_STARTATZONE) != 0 ?
3525                                 ISC_TRUE : ISC_FALSE,
3526                                 NULL, NULL, fname, &rdataset, NULL);
3527
3528         /* XXXVIX this switch statement is too sparse to gen a jump table. */
3529         switch (result) {
3530         case DNS_R_GLUE:
3531         case DNS_R_HINT:
3532         case ISC_R_SUCCESS:
3533                 /*
3534                  * Found in the database.  Even if we can't copy out
3535                  * any information, return success, or else a fetch
3536                  * will be made, which will only make things worse.
3537                  */
3538                 if (rdtype == dns_rdatatype_a)
3539                         adbname->fetch_err = FIND_ERR_SUCCESS;
3540                 else
3541                         adbname->fetch6_err = FIND_ERR_SUCCESS;
3542                 result = import_rdataset(adbname, &rdataset, now);
3543                 break;
3544         case DNS_R_NXDOMAIN:
3545         case DNS_R_NXRRSET:
3546                 /*
3547                  * We're authoritative and the data doesn't exist.
3548                  * Make up a negative cache entry so we don't ask again
3549                  * for a while.
3550                  *
3551                  * XXXRTH  What time should we use?  I'm putting in 30 seconds
3552                  * for now.
3553                  */
3554                 if (rdtype == dns_rdatatype_a) {
3555                         adbname->expire_v4 = now + 30;
3556                         DP(NCACHE_LEVEL,
3557                            "adb name %p: Caching auth negative entry for A",
3558                            adbname);
3559                         if (result == DNS_R_NXDOMAIN)
3560                                 adbname->fetch_err = FIND_ERR_NXDOMAIN;
3561                         else
3562                                 adbname->fetch_err = FIND_ERR_NXRRSET;
3563                 } else {
3564                         DP(NCACHE_LEVEL,
3565                            "adb name %p: Caching auth negative entry for AAAA",
3566                            adbname);
3567                         adbname->expire_v6 = now + 30;
3568                         if (result == DNS_R_NXDOMAIN)
3569                                 adbname->fetch6_err = FIND_ERR_NXDOMAIN;
3570                         else
3571                                 adbname->fetch6_err = FIND_ERR_NXRRSET;
3572                 }
3573                 break;
3574         case DNS_R_NCACHENXDOMAIN:
3575         case DNS_R_NCACHENXRRSET:
3576                 /*
3577                  * We found a negative cache entry.  Pull the TTL from it
3578                  * so we won't ask again for a while.
3579                  */
3580                 rdataset.ttl = ttlclamp(rdataset.ttl);
3581                 if (rdtype == dns_rdatatype_a) {
3582                         adbname->expire_v4 = rdataset.ttl + now;
3583                         if (result == DNS_R_NCACHENXDOMAIN)
3584                                 adbname->fetch_err = FIND_ERR_NXDOMAIN;
3585                         else
3586                                 adbname->fetch_err = FIND_ERR_NXRRSET;
3587                         DP(NCACHE_LEVEL,
3588                           "adb name %p: Caching negative entry for A (ttl %u)",
3589                            adbname, rdataset.ttl);
3590                 } else {
3591                         DP(NCACHE_LEVEL,
3592                        "adb name %p: Caching negative entry for AAAA (ttl %u)",
3593                            adbname, rdataset.ttl);
3594                         adbname->expire_v6 = rdataset.ttl + now;
3595                         if (result == DNS_R_NCACHENXDOMAIN)
3596                                 adbname->fetch6_err = FIND_ERR_NXDOMAIN;
3597                         else
3598                                 adbname->fetch6_err = FIND_ERR_NXRRSET;
3599                 }
3600                 break;
3601         case DNS_R_CNAME:
3602         case DNS_R_DNAME:
3603                 /*
3604                  * Clear the hint and glue flags, so this will match
3605                  * more often.
3606                  */
3607                 adbname->flags &= ~(DNS_ADBFIND_GLUEOK | DNS_ADBFIND_HINTOK);
3608
3609                 rdataset.ttl = ttlclamp(rdataset.ttl);
3610                 clean_target(adb, &adbname->target);
3611                 adbname->expire_target = INT_MAX;
3612                 result = set_target(adb, &adbname->name, fname, &rdataset,
3613                                     &adbname->target);
3614                 if (result == ISC_R_SUCCESS) {
3615                         result = DNS_R_ALIAS;
3616                         DP(NCACHE_LEVEL,
3617                            "adb name %p: caching alias target",
3618                            adbname);
3619                         adbname->expire_target = rdataset.ttl + now;
3620                 }
3621                 if (rdtype == dns_rdatatype_a)
3622                         adbname->fetch_err = FIND_ERR_SUCCESS;
3623                 else
3624                         adbname->fetch6_err = FIND_ERR_SUCCESS;
3625                 break;
3626         }
3627
3628         if (dns_rdataset_isassociated(&rdataset))
3629                 dns_rdataset_disassociate(&rdataset);
3630
3631         return (result);
3632 }
3633
3634 static void
3635 fetch_callback(isc_task_t *task, isc_event_t *ev) {
3636         dns_fetchevent_t *dev;
3637         dns_adbname_t *name;
3638         dns_adb_t *adb;
3639         dns_adbfetch_t *fetch;
3640         int bucket;
3641         isc_eventtype_t ev_status;
3642         isc_stdtime_t now;
3643         isc_result_t result;
3644         unsigned int address_type;
3645         isc_boolean_t want_check_exit = ISC_FALSE;
3646         isc_uint32_t qtotal = 0;
3647
3648         UNUSED(task);
3649
3650         INSIST(ev->ev_type == DNS_EVENT_FETCHDONE);
3651         dev = (dns_fetchevent_t *)ev;
3652         name = ev->ev_arg;
3653         INSIST(DNS_ADBNAME_VALID(name));
3654         adb = name->adb;
3655         INSIST(DNS_ADB_VALID(adb));
3656
3657         qtotal = dev->qtotal;
3658
3659         bucket = name->lock_bucket;
3660         LOCK(&adb->namelocks[bucket]);
3661
3662         INSIST(NAME_FETCH_A(name) || NAME_FETCH_AAAA(name));
3663         address_type = 0;
3664         if (NAME_FETCH_A(name) && (name->fetch_a->fetch == dev->fetch)) {
3665                 address_type = DNS_ADBFIND_INET;
3666                 fetch = name->fetch_a;
3667                 name->fetch_a = NULL;
3668         } else if (NAME_FETCH_AAAA(name)
3669                    && (name->fetch_aaaa->fetch == dev->fetch)) {
3670                 address_type = DNS_ADBFIND_INET6;
3671                 fetch = name->fetch_aaaa;
3672                 name->fetch_aaaa = NULL;
3673         } else
3674                 fetch = NULL;
3675
3676         INSIST(address_type != 0 && fetch != NULL);
3677
3678         dns_resolver_destroyfetch(&fetch->fetch);
3679         dev->fetch = NULL;
3680
3681         ev_status = DNS_EVENT_ADBNOMOREADDRESSES;
3682
3683         /*
3684          * Cleanup things we don't care about.
3685          */
3686         if (dev->node != NULL)
3687                 dns_db_detachnode(dev->db, &dev->node);
3688         if (dev->db != NULL)
3689                 dns_db_detach(&dev->db);
3690
3691         /*
3692          * If this name is marked as dead, clean up, throwing away
3693          * potentially good data.
3694          */
3695         if (NAME_DEAD(name)) {
3696                 free_adbfetch(adb, &fetch);
3697                 isc_event_free(&ev);
3698
3699                 want_check_exit = kill_name(&name, DNS_EVENT_ADBCANCELED);
3700
3701                 UNLOCK(&adb->namelocks[bucket]);
3702
3703                 if (want_check_exit) {
3704                         LOCK(&adb->lock);
3705                         check_exit(adb);
3706                         UNLOCK(&adb->lock);
3707                 }
3708
3709                 return;
3710         }
3711
3712         isc_stdtime_get(&now);
3713
3714         /*
3715          * If we got a negative cache response, remember it.
3716          */
3717         if (NCACHE_RESULT(dev->result)) {
3718                 dev->rdataset->ttl = ttlclamp(dev->rdataset->ttl);
3719                 if (address_type == DNS_ADBFIND_INET) {
3720                         DP(NCACHE_LEVEL, "adb fetch name %p: "
3721                            "caching negative entry for A (ttl %u)",
3722                            name, dev->rdataset->ttl);
3723                         name->expire_v4 = ISC_MIN(name->expire_v4,
3724                                                   dev->rdataset->ttl + now);
3725                         if (dev->result == DNS_R_NCACHENXDOMAIN)
3726                                 name->fetch_err = FIND_ERR_NXDOMAIN;
3727                         else
3728                                 name->fetch_err = FIND_ERR_NXRRSET;
3729                         inc_stats(adb, dns_resstatscounter_gluefetchv4fail);
3730                 } else {
3731                         DP(NCACHE_LEVEL, "adb fetch name %p: "
3732                            "caching negative entry for AAAA (ttl %u)",
3733                            name, dev->rdataset->ttl);
3734                         name->expire_v6 = ISC_MIN(name->expire_v6,
3735                                                   dev->rdataset->ttl + now);
3736                         if (dev->result == DNS_R_NCACHENXDOMAIN)
3737                                 name->fetch6_err = FIND_ERR_NXDOMAIN;
3738                         else
3739                                 name->fetch6_err = FIND_ERR_NXRRSET;
3740                         inc_stats(adb, dns_resstatscounter_gluefetchv6fail);
3741                 }
3742                 goto out;
3743         }
3744
3745         /*
3746          * Handle CNAME/DNAME.
3747          */
3748         if (dev->result == DNS_R_CNAME || dev->result == DNS_R_DNAME) {
3749                 dev->rdataset->ttl = ttlclamp(dev->rdataset->ttl);
3750                 clean_target(adb, &name->target);
3751                 name->expire_target = INT_MAX;
3752                 result = set_target(adb, &name->name,
3753                                     dns_fixedname_name(&dev->foundname),
3754                                     dev->rdataset,
3755                                     &name->target);
3756                 if (result == ISC_R_SUCCESS) {
3757                         DP(NCACHE_LEVEL,
3758                            "adb fetch name %p: caching alias target",
3759                            name);
3760                         name->expire_target = dev->rdataset->ttl + now;
3761                 }
3762                 goto check_result;
3763         }
3764
3765         /*
3766          * Did we get back junk?  If so, and there are no more fetches
3767          * sitting out there, tell all the finds about it.
3768          */
3769         if (dev->result != ISC_R_SUCCESS) {
3770                 char buf[DNS_NAME_FORMATSIZE];
3771
3772                 dns_name_format(&name->name, buf, sizeof(buf));
3773                 DP(DEF_LEVEL, "adb: fetch of '%s' %s failed: %s",
3774                    buf, address_type == DNS_ADBFIND_INET ? "A" : "AAAA",
3775                    dns_result_totext(dev->result));
3776                 /*
3777                  * Don't record a failure unless this is the initial
3778                  * fetch of a chain.
3779                  */
3780                 if (fetch->depth > 1)
3781                         goto out;
3782                 /* XXXMLG Don't pound on bad servers. */
3783                 if (address_type == DNS_ADBFIND_INET) {
3784                         name->expire_v4 = ISC_MIN(name->expire_v4, now + 300);
3785                         name->fetch_err = FIND_ERR_FAILURE;
3786                         inc_stats(adb, dns_resstatscounter_gluefetchv4fail);
3787                 } else {
3788                         name->expire_v6 = ISC_MIN(name->expire_v6, now + 300);
3789                         name->fetch6_err = FIND_ERR_FAILURE;
3790                         inc_stats(adb, dns_resstatscounter_gluefetchv6fail);
3791                 }
3792                 goto out;
3793         }
3794
3795         /*
3796          * We got something potentially useful.
3797          */
3798         result = import_rdataset(name, &fetch->rdataset, now);
3799
3800  check_result:
3801         if (result == ISC_R_SUCCESS) {
3802                 ev_status = DNS_EVENT_ADBMOREADDRESSES;
3803                 if (address_type == DNS_ADBFIND_INET)
3804                         name->fetch_err = FIND_ERR_SUCCESS;
3805                 else
3806                         name->fetch6_err = FIND_ERR_SUCCESS;
3807         }
3808
3809  out:
3810         free_adbfetch(adb, &fetch);
3811         isc_event_free(&ev);
3812
3813         clean_finds_at_name(name, ev_status, qtotal, address_type);
3814
3815         UNLOCK(&adb->namelocks[bucket]);
3816 }
3817
3818 static isc_result_t
3819 fetch_name(dns_adbname_t *adbname, isc_boolean_t start_at_zone,
3820            unsigned int depth, dns_rdatatype_t type)
3821 {
3822         isc_result_t result;
3823         dns_adbfetch_t *fetch = NULL;
3824         dns_adb_t *adb;
3825         dns_fixedname_t fixed;
3826         dns_name_t *name;
3827         dns_rdataset_t rdataset;
3828         dns_rdataset_t *nameservers;
3829         unsigned int options;
3830
3831         INSIST(DNS_ADBNAME_VALID(adbname));
3832         adb = adbname->adb;
3833         INSIST(DNS_ADB_VALID(adb));
3834
3835         INSIST((type == dns_rdatatype_a && !NAME_FETCH_V4(adbname)) ||
3836                (type == dns_rdatatype_aaaa && !NAME_FETCH_V6(adbname)));
3837
3838         adbname->fetch_err = FIND_ERR_NOTFOUND;
3839
3840         name = NULL;
3841         nameservers = NULL;
3842         dns_rdataset_init(&rdataset);
3843
3844         options = DNS_FETCHOPT_NOVALIDATE;
3845         if (start_at_zone) {
3846                 DP(ENTER_LEVEL,
3847                    "fetch_name: starting at zone for name %p",
3848                    adbname);
3849                 dns_fixedname_init(&fixed);
3850                 name = dns_fixedname_name(&fixed);
3851                 result = dns_view_findzonecut2(adb->view, &adbname->name, name,
3852                                                0, 0, ISC_TRUE, ISC_FALSE,
3853                                                &rdataset, NULL);
3854                 if (result != ISC_R_SUCCESS && result != DNS_R_HINT)
3855                         goto cleanup;
3856                 nameservers = &rdataset;
3857                 options |= DNS_FETCHOPT_UNSHARED;
3858         }
3859
3860         fetch = new_adbfetch(adb);
3861         if (fetch == NULL) {
3862                 result = ISC_R_NOMEMORY;
3863                 goto cleanup;
3864         }
3865         fetch->depth = depth;
3866
3867         result = dns_resolver_createfetch3(adb->view->resolver, &adbname->name,
3868                                            type, name, nameservers, NULL,
3869                                            NULL, 0, options, depth, adb->task,
3870                                            fetch_callback, adbname,
3871                                            &fetch->rdataset, NULL,
3872                                            &fetch->fetch);
3873         if (result != ISC_R_SUCCESS)
3874                 goto cleanup;
3875
3876         if (type == dns_rdatatype_a) {
3877                 adbname->fetch_a = fetch;
3878                 inc_stats(adb, dns_resstatscounter_gluefetchv4);
3879         } else {
3880                 adbname->fetch_aaaa = fetch;
3881                 inc_stats(adb, dns_resstatscounter_gluefetchv6);
3882         }
3883         fetch = NULL;  /* Keep us from cleaning this up below. */
3884
3885  cleanup:
3886         if (fetch != NULL)
3887                 free_adbfetch(adb, &fetch);
3888         if (dns_rdataset_isassociated(&rdataset))
3889                 dns_rdataset_disassociate(&rdataset);
3890
3891         return (result);
3892 }
3893
3894 /*
3895  * XXXMLG Needs to take a find argument and an address info, no zone or adb,
3896  * since these can be extracted from the find itself.
3897  */
3898 isc_result_t
3899 dns_adb_marklame(dns_adb_t *adb, dns_adbaddrinfo_t *addr, dns_name_t *qname,
3900                  dns_rdatatype_t qtype, isc_stdtime_t expire_time)
3901 {
3902         dns_adblameinfo_t *li;
3903         int bucket;
3904         isc_result_t result = ISC_R_SUCCESS;
3905
3906         REQUIRE(DNS_ADB_VALID(adb));
3907         REQUIRE(DNS_ADBADDRINFO_VALID(addr));
3908         REQUIRE(qname != NULL);
3909
3910         bucket = addr->entry->lock_bucket;
3911         LOCK(&adb->entrylocks[bucket]);
3912         li = ISC_LIST_HEAD(addr->entry->lameinfo);
3913         while (li != NULL &&
3914                (li->qtype != qtype || !dns_name_equal(qname, &li->qname)))
3915                 li = ISC_LIST_NEXT(li, plink);
3916         if (li != NULL) {
3917                 if (expire_time > li->lame_timer)
3918                         li->lame_timer = expire_time;
3919                 goto unlock;
3920         }
3921         li = new_adblameinfo(adb, qname, qtype);
3922         if (li == NULL) {
3923                 result = ISC_R_NOMEMORY;
3924                 goto unlock;
3925         }
3926
3927         li->lame_timer = expire_time;
3928
3929         ISC_LIST_PREPEND(addr->entry->lameinfo, li, plink);
3930  unlock:
3931         UNLOCK(&adb->entrylocks[bucket]);
3932
3933         return (result);
3934 }
3935
3936 void
3937 dns_adb_adjustsrtt(dns_adb_t *adb, dns_adbaddrinfo_t *addr,
3938                    unsigned int rtt, unsigned int factor)
3939 {
3940         int bucket;
3941         unsigned int new_srtt;
3942         isc_stdtime_t now;
3943
3944         REQUIRE(DNS_ADB_VALID(adb));
3945         REQUIRE(DNS_ADBADDRINFO_VALID(addr));
3946         REQUIRE(factor <= 10);
3947
3948         bucket = addr->entry->lock_bucket;
3949         LOCK(&adb->entrylocks[bucket]);
3950
3951         if (factor == DNS_ADB_RTTADJAGE)
3952                 new_srtt = addr->entry->srtt * 98 / 100;
3953         else
3954                 new_srtt = (addr->entry->srtt / 10 * factor)
3955                         + (rtt / 10 * (10 - factor));
3956
3957         addr->entry->srtt = new_srtt;
3958         addr->srtt = new_srtt;
3959
3960         if (addr->entry->expires == 0) {
3961                 isc_stdtime_get(&now);
3962                 addr->entry->expires = now + ADB_ENTRY_WINDOW;
3963         }
3964
3965         UNLOCK(&adb->entrylocks[bucket]);
3966 }
3967
3968 void
3969 dns_adb_changeflags(dns_adb_t *adb, dns_adbaddrinfo_t *addr,
3970                     unsigned int bits, unsigned int mask)
3971 {
3972         int bucket;
3973         isc_stdtime_t now;
3974
3975         REQUIRE(DNS_ADB_VALID(adb));
3976         REQUIRE(DNS_ADBADDRINFO_VALID(addr));
3977
3978         bucket = addr->entry->lock_bucket;
3979         LOCK(&adb->entrylocks[bucket]);
3980
3981         addr->entry->flags = (addr->entry->flags & ~mask) | (bits & mask);
3982         if (addr->entry->expires == 0) {
3983                 isc_stdtime_get(&now);
3984                 addr->entry->expires = now + ADB_ENTRY_WINDOW;
3985         }
3986
3987         /*
3988          * Note that we do not update the other bits in addr->flags with
3989          * the most recent values from addr->entry->flags.
3990          */
3991         addr->flags = (addr->flags & ~mask) | (bits & mask);
3992
3993         UNLOCK(&adb->entrylocks[bucket]);
3994 }
3995
3996 isc_result_t
3997 dns_adb_findaddrinfo(dns_adb_t *adb, isc_sockaddr_t *sa,
3998                      dns_adbaddrinfo_t **addrp, isc_stdtime_t now)
3999 {
4000         int bucket;
4001         dns_adbentry_t *entry;
4002         dns_adbaddrinfo_t *addr;
4003         isc_result_t result;
4004         in_port_t port;
4005
4006         REQUIRE(DNS_ADB_VALID(adb));
4007         REQUIRE(addrp != NULL && *addrp == NULL);
4008
4009         UNUSED(now);
4010
4011         result = ISC_R_SUCCESS;
4012         bucket = DNS_ADB_INVALIDBUCKET;
4013         entry = find_entry_and_lock(adb, sa, &bucket, now);
4014         INSIST(bucket != DNS_ADB_INVALIDBUCKET);
4015         if (adb->entry_sd[bucket]) {
4016                 result = ISC_R_SHUTTINGDOWN;
4017                 goto unlock;
4018         }
4019         if (entry == NULL) {
4020                 /*
4021                  * We don't know anything about this address.
4022                  */
4023                 entry = new_adbentry(adb);
4024                 if (entry == NULL) {
4025                         result = ISC_R_NOMEMORY;
4026                         goto unlock;
4027                 }
4028                 entry->sockaddr = *sa;
4029                 link_entry(adb, bucket, entry);
4030                 DP(ENTER_LEVEL, "findaddrinfo: new entry %p", entry);
4031         } else
4032                 DP(ENTER_LEVEL, "findaddrinfo: found entry %p", entry);
4033
4034         port = isc_sockaddr_getport(sa);
4035         addr = new_adbaddrinfo(adb, entry, port);
4036         if (addr == NULL) {
4037                 result = ISC_R_NOMEMORY;
4038         } else {
4039                 inc_entry_refcnt(adb, entry, ISC_FALSE);
4040                 *addrp = addr;
4041         }
4042
4043  unlock:
4044         UNLOCK(&adb->entrylocks[bucket]);
4045
4046         return (result);
4047 }
4048
4049 void
4050 dns_adb_freeaddrinfo(dns_adb_t *adb, dns_adbaddrinfo_t **addrp) {
4051         dns_adbaddrinfo_t *addr;
4052         dns_adbentry_t *entry;
4053         int bucket;
4054         isc_stdtime_t now;
4055         isc_boolean_t want_check_exit = ISC_FALSE;
4056         isc_boolean_t overmem;
4057
4058         REQUIRE(DNS_ADB_VALID(adb));
4059         REQUIRE(addrp != NULL);
4060         addr = *addrp;
4061         REQUIRE(DNS_ADBADDRINFO_VALID(addr));
4062         entry = addr->entry;
4063         REQUIRE(DNS_ADBENTRY_VALID(entry));
4064
4065         *addrp = NULL;
4066         overmem = isc_mem_isovermem(adb->mctx);
4067
4068         bucket = addr->entry->lock_bucket;
4069         LOCK(&adb->entrylocks[bucket]);
4070
4071         if (entry->expires == 0) {
4072                 isc_stdtime_get(&now);
4073                 entry->expires = now + ADB_ENTRY_WINDOW;
4074         }
4075
4076         want_check_exit = dec_entry_refcnt(adb, overmem, entry, ISC_FALSE);
4077
4078         UNLOCK(&adb->entrylocks[bucket]);
4079
4080         addr->entry = NULL;
4081         free_adbaddrinfo(adb, &addr);
4082
4083         if (want_check_exit) {
4084                 LOCK(&adb->lock);
4085                 check_exit(adb);
4086                 UNLOCK(&adb->lock);
4087         }
4088 }
4089
4090 void
4091 dns_adb_flush(dns_adb_t *adb) {
4092         unsigned int i;
4093
4094         INSIST(DNS_ADB_VALID(adb));
4095
4096         LOCK(&adb->lock);
4097
4098         /*
4099          * Call our cleanup routines.
4100          */
4101         for (i = 0; i < adb->nnames; i++)
4102                 RUNTIME_CHECK(cleanup_names(adb, i, INT_MAX) == ISC_FALSE);
4103         for (i = 0; i < adb->nentries; i++)
4104                 RUNTIME_CHECK(cleanup_entries(adb, i, INT_MAX) == ISC_FALSE);
4105
4106 #ifdef DUMP_ADB_AFTER_CLEANING
4107         dump_adb(adb, stdout, ISC_TRUE, INT_MAX);
4108 #endif
4109
4110         UNLOCK(&adb->lock);
4111 }
4112
4113 void
4114 dns_adb_flushname(dns_adb_t *adb, dns_name_t *name) {
4115         dns_adbname_t *adbname;
4116         dns_adbname_t *nextname;
4117         int bucket;
4118
4119         INSIST(DNS_ADB_VALID(adb));
4120
4121         LOCK(&adb->lock);
4122         bucket = dns_name_hash(name, ISC_FALSE) % adb->nnames;
4123         LOCK(&adb->namelocks[bucket]);
4124         adbname = ISC_LIST_HEAD(adb->names[bucket]);
4125         while (adbname != NULL) {
4126                 nextname = ISC_LIST_NEXT(adbname, plink);
4127                 if (!NAME_DEAD(adbname) &&
4128                     dns_name_equal(name, &adbname->name)) {
4129                         RUNTIME_CHECK(kill_name(&adbname,
4130                                                 DNS_EVENT_ADBCANCELED) ==
4131                                       ISC_FALSE);
4132                 }
4133                 adbname = nextname;
4134         }
4135         UNLOCK(&adb->namelocks[bucket]);
4136         UNLOCK(&adb->lock);
4137 }
4138
4139 static void
4140 water(void *arg, int mark) {
4141         /*
4142          * We're going to change the way to handle overmem condition: use
4143          * isc_mem_isovermem() instead of storing the state via this callback,
4144          * since the latter way tends to cause race conditions.
4145          * To minimize the change, and in case we re-enable the callback
4146          * approach, however, keep this function at the moment.
4147          */
4148
4149         dns_adb_t *adb = arg;
4150         isc_boolean_t overmem = ISC_TF(mark == ISC_MEM_HIWATER);
4151
4152         REQUIRE(DNS_ADB_VALID(adb));
4153
4154         DP(ISC_LOG_DEBUG(1),
4155            "adb reached %s water mark", overmem ? "high" : "low");
4156 }
4157
4158 void
4159 dns_adb_setadbsize(dns_adb_t *adb, size_t size) {
4160         size_t hiwater, lowater;
4161
4162         INSIST(DNS_ADB_VALID(adb));
4163
4164         if (size != 0U && size < DNS_ADB_MINADBSIZE)
4165                 size = DNS_ADB_MINADBSIZE;
4166
4167         hiwater = size - (size >> 3);   /* Approximately 7/8ths. */
4168         lowater = size - (size >> 2);   /* Approximately 3/4ths. */
4169
4170         if (size == 0U || hiwater == 0U || lowater == 0U)
4171                 isc_mem_setwater(adb->mctx, water, adb, 0, 0);
4172         else
4173                 isc_mem_setwater(adb->mctx, water, adb, hiwater, lowater);
4174 }