contrib/bind9/lib/dns/adb.c

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