contrib/bind9/lib/dns/adb.c

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