contrib/bind9/lib/dns/adb.c

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