contrib/bind9/lib/dns/adb.c

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