contrib/bind9/lib/dns/adb.c

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