contrib/bind9/lib/dns/adb.c

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