adb.c 123 KB
Newer Older
Michael Graff's avatar
Michael Graff committed
1
/*
2
 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
3
 *
4 5 6
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
7 8 9
 *
 * See the COPYRIGHT file distributed with this work for additional
 * information regarding copyright ownership.
Michael Graff's avatar
Michael Graff committed
10 11
 */

12
/*! \file
13
 *
14
 * \note
15
 * In finds, if task == NULL, no events will be generated, and no events
16
 * have been sent.  If task != NULL but taskaction == NULL, an event has been
Bob Halley's avatar
Bob Halley committed
17
 * posted but not yet freed.  If neither are NULL, no event was posted.
18 19 20
 *
 */

21
#include <inttypes.h>
22
#include <limits.h>
23
#include <stdbool.h>
24

25
#include <isc/mutexblock.h>
26
#include <isc/netaddr.h>
27
#include <isc/print.h>
Michael Graff's avatar
Michael Graff committed
28
#include <isc/random.h>
29
#include <isc/stats.h>
30
#include <isc/string.h> /* Required for HP/UX (and others?) */
31
#include <isc/task.h>
Michael Graff's avatar
Michael Graff committed
32
#include <isc/util.h>
Michael Graff's avatar
Michael Graff committed
33

Michael Graff's avatar
Michael Graff committed
34
#include <dns/adb.h>
Michael Graff's avatar
Michael Graff committed
35
#include <dns/db.h>
36
#include <dns/events.h>
37
#include <dns/log.h>
Michael Graff's avatar
Michael Graff committed
38 39
#include <dns/rdata.h>
#include <dns/rdataset.h>
40
#include <dns/rdatastruct.h>
41
#include <dns/rdatatype.h>
Michael Graff's avatar
fix  
Michael Graff committed
42
#include <dns/resolver.h>
43
#include <dns/result.h>
44
#include <dns/stats.h>
45

Evan Hunt's avatar
Evan Hunt committed
46 47 48 49 50
#define DNS_ADB_MAGIC		 ISC_MAGIC('D', 'a', 'd', 'b')
#define DNS_ADB_VALID(x)	 ISC_MAGIC_VALID(x, DNS_ADB_MAGIC)
#define DNS_ADBNAME_MAGIC	 ISC_MAGIC('a', 'd', 'b', 'N')
#define DNS_ADBNAME_VALID(x)	 ISC_MAGIC_VALID(x, DNS_ADBNAME_MAGIC)
#define DNS_ADBNAMEHOOK_MAGIC	 ISC_MAGIC('a', 'd', 'N', 'H')
51
#define DNS_ADBNAMEHOOK_VALID(x) ISC_MAGIC_VALID(x, DNS_ADBNAMEHOOK_MAGIC)
Evan Hunt's avatar
Evan Hunt committed
52
#define DNS_ADBLAMEINFO_MAGIC	 ISC_MAGIC('a', 'd', 'b', 'Z')
53
#define DNS_ADBLAMEINFO_VALID(x) ISC_MAGIC_VALID(x, DNS_ADBLAMEINFO_MAGIC)
Evan Hunt's avatar
Evan Hunt committed
54 55 56 57 58 59
#define DNS_ADBENTRY_MAGIC	 ISC_MAGIC('a', 'd', 'b', 'E')
#define DNS_ADBENTRY_VALID(x)	 ISC_MAGIC_VALID(x, DNS_ADBENTRY_MAGIC)
#define DNS_ADBFETCH_MAGIC	 ISC_MAGIC('a', 'd', 'F', '4')
#define DNS_ADBFETCH_VALID(x)	 ISC_MAGIC_VALID(x, DNS_ADBFETCH_MAGIC)
#define DNS_ADBFETCH6_MAGIC	 ISC_MAGIC('a', 'd', 'F', '6')
#define DNS_ADBFETCH6_VALID(x)	 ISC_MAGIC_VALID(x, DNS_ADBFETCH6_MAGIC)
60

61
/*!
62
 * For type 3 negative cache entries, we will remember that the address is
63
 * broken for this long.  XXXMLG This is also used for actual addresses, too.
64
 * The intent is to keep us from constantly asking about A/AAAA records
65
 * if the zone has extremely low TTLs.
66
 */
67 68
#define ADB_CACHE_MINIMUM 10	/*%< seconds */
#define ADB_CACHE_MAXIMUM 86400 /*%< seconds (86400 = 24 hours) */
Evan Hunt's avatar
Evan Hunt committed
69
#define ADB_ENTRY_WINDOW  1800	/*%< seconds */
70

71 72 73 74 75 76
/*%
 * The period in seconds after which an ADB name entry is regarded as stale
 * and forced to be cleaned up.
 * TODO: This should probably be configurable at run-time.
 */
#ifndef ADB_STALE_MARGIN
77
#define ADB_STALE_MARGIN 1800
78
#endif /* ifndef ADB_STALE_MARGIN */
Michael Graff's avatar
Michael Graff committed
79

80 81
#define FREE_ITEMS 64 /*%< free count for memory pools */
#define FILL_COUNT 16 /*%< fill count for memory pools */
82

83
#define DNS_ADB_INVALIDBUCKET (-1) /*%< invalid bucket address */
Michael Graff's avatar
Michael Graff committed
84

85
#define DNS_ADB_MINADBSIZE (1024U * 1024U) /*%< 1 Megabyte */
86

87
typedef ISC_LIST(dns_adbname_t) dns_adbnamelist_t;
Michael Graff's avatar
Michael Graff committed
88
typedef struct dns_adbnamehook dns_adbnamehook_t;
Michael Graff's avatar
Michael Graff committed
89
typedef ISC_LIST(dns_adbnamehook_t) dns_adbnamehooklist_t;
90
typedef struct dns_adblameinfo dns_adblameinfo_t;
91
typedef ISC_LIST(dns_adbentry_t) dns_adbentrylist_t;
Evan Hunt's avatar
Evan Hunt committed
92
typedef struct dns_adbfetch dns_adbfetch_t;
Bob Halley's avatar
Bob Halley committed
93
typedef struct dns_adbfetch6 dns_adbfetch6_t;
Michael Graff's avatar
Michael Graff committed
94

95
/*% dns adb structure */
Michael Graff's avatar
Michael Graff committed
96
struct dns_adb {
97
	unsigned int magic;
98

99 100 101
	isc_mutex_t lock;
	isc_mutex_t reflock;	 /*%< Covers irefcnt, erefcnt */
	isc_mutex_t overmemlock; /*%< Covers overmem */
Evan Hunt's avatar
Evan Hunt committed
102
	isc_mem_t *mctx;
103
	dns_view_t *view;
104

105
	isc_taskmgr_t *taskmgr;
Evan Hunt's avatar
Evan Hunt committed
106 107
	isc_task_t *task;
	isc_task_t *excl;
Automatic Updater's avatar
Automatic Updater committed
108

109
	isc_interval_t tick_interval;
Evan Hunt's avatar
Evan Hunt committed
110
	int next_cleanbucket;
Automatic Updater's avatar
Automatic Updater committed
111

112 113
	unsigned int irefcnt;
	unsigned int erefcnt;
Automatic Updater's avatar
Automatic Updater committed
114

Evan Hunt's avatar
Evan Hunt committed
115
	isc_mutex_t mplock;
116 117 118 119 120 121 122
	isc_mempool_t *nmp;  /*%< dns_adbname_t */
	isc_mempool_t *nhmp; /*%< dns_adbnamehook_t */
	isc_mempool_t *limp; /*%< dns_adblameinfo_t */
	isc_mempool_t *emp;  /*%< dns_adbentry_t */
	isc_mempool_t *ahmp; /*%< dns_adbfind_t */
	isc_mempool_t *aimp; /*%< dns_adbaddrinfo_t */
	isc_mempool_t *afmp; /*%< dns_adbfetch_t */
Automatic Updater's avatar
Automatic Updater committed
123 124 125 126 127 128

	/*!
	 * Bucketized locks and lists for names.
	 *
	 * XXXRTH  Have a per-bucket structure that contains all of these?
	 */
Evan Hunt's avatar
Evan Hunt committed
129 130 131
	unsigned int nnames;
	isc_mutex_t namescntlock;
	unsigned int namescnt;
132 133
	dns_adbnamelist_t *names;
	dns_adbnamelist_t *deadnames;
Evan Hunt's avatar
Evan Hunt committed
134 135 136
	isc_mutex_t *namelocks;
	bool *name_sd;
	unsigned int *name_refcnt;
Automatic Updater's avatar
Automatic Updater committed
137 138

	/*!
139
	 * Bucketized locks and lists for entries.
Automatic Updater's avatar
Automatic Updater committed
140 141 142
	 *
	 * XXXRTH  Have a per-bucket structure that contains all of these?
	 */
Evan Hunt's avatar
Evan Hunt committed
143 144 145
	unsigned int nentries;
	isc_mutex_t entriescntlock;
	unsigned int entriescnt;
146 147
	dns_adbentrylist_t *entries;
	dns_adbentrylist_t *deadentries;
Evan Hunt's avatar
Evan Hunt committed
148 149 150
	isc_mutex_t *entrylocks;
	bool *entry_sd; /*%< shutting down */
	unsigned int *entry_refcnt;
151

Evan Hunt's avatar
Evan Hunt committed
152 153 154
	isc_event_t cevent;
	bool cevent_out;
	bool shutting_down;
155
	isc_eventlist_t whenshutdown;
Evan Hunt's avatar
Evan Hunt committed
156 157 158 159
	isc_event_t growentries;
	bool growentries_sent;
	isc_event_t grownames;
	bool grownames_sent;
160 161 162

	uint32_t quota;
	uint32_t atr_freq;
Evan Hunt's avatar
Evan Hunt committed
163 164 165
	double atr_low;
	double atr_high;
	double atr_discount;
Michael Graff's avatar
Michael Graff committed
166 167
};

Bob Halley's avatar
Bob Halley committed
168 169 170 171
/*
 * XXXMLG  Document these structures.
 */

172
/*% dns_adbname structure */
Michael Graff's avatar
Michael Graff committed
173
struct dns_adbname {
Evan Hunt's avatar
Evan Hunt committed
174 175 176 177 178 179 180 181 182 183 184
	unsigned int magic;
	dns_name_t name;
	dns_adb_t *adb;
	unsigned int partial_result;
	unsigned int flags;
	int lock_bucket;
	dns_name_t target;
	isc_stdtime_t expire_target;
	isc_stdtime_t expire_v4;
	isc_stdtime_t expire_v6;
	unsigned int chains;
185 186
	dns_adbnamehooklist_t v4;
	dns_adbnamehooklist_t v6;
Evan Hunt's avatar
Evan Hunt committed
187 188 189 190 191
	dns_adbfetch_t *fetch_a;
	dns_adbfetch_t *fetch_aaaa;
	unsigned int fetch_err;
	unsigned int fetch6_err;
	dns_adbfindlist_t finds;
Automatic Updater's avatar
Automatic Updater committed
192
	/* for LRU-based management */
193
	isc_stdtime_t last_used;
Automatic Updater's avatar
Automatic Updater committed
194

195
	ISC_LINK(dns_adbname_t) plink;
Michael Graff's avatar
Michael Graff committed
196 197
};

198
/*% The adbfetch structure */
Michael Graff's avatar
Michael Graff committed
199
struct dns_adbfetch {
Evan Hunt's avatar
Evan Hunt committed
200 201
	unsigned int magic;
	dns_fetch_t *fetch;
202
	dns_rdataset_t rdataset;
Evan Hunt's avatar
Evan Hunt committed
203
	unsigned int depth;
Michael Graff's avatar
Michael Graff committed
204 205
};

206
/*%
Michael Graff's avatar
Michael Graff committed
207 208 209 210 211
 * This is a small widget that dangles off a dns_adbname_t.  It contains a
 * pointer to the address information about this host, and a link to the next
 * namehook that will contain the next address this host has.
 */
struct dns_adbnamehook {
Evan Hunt's avatar
Evan Hunt committed
212
	unsigned int magic;
213 214
	dns_adbentry_t *entry;
	ISC_LINK(dns_adbnamehook_t) plink;
Michael Graff's avatar
Michael Graff committed
215 216
};

217
/*%
218
 * This is a small widget that holds qname-specific information about an
Michael Graff's avatar
Michael Graff committed
219 220 221
 * address.  Currently limited to lameness, but could just as easily be
 * extended to other types of information about zones.
 */
222
struct dns_adblameinfo {
223
	unsigned int magic;
Michael Graff's avatar
Michael Graff committed
224

Evan Hunt's avatar
Evan Hunt committed
225
	dns_name_t qname;
226
	dns_rdatatype_t qtype;
Evan Hunt's avatar
Evan Hunt committed
227
	isc_stdtime_t lame_timer;
Michael Graff's avatar
Michael Graff committed
228

229
	ISC_LINK(dns_adblameinfo_t) plink;
Michael Graff's avatar
Michael Graff committed
230 231
};

232
/*%
Michael Graff's avatar
Michael Graff committed
233
 * An address entry.  It holds quite a bit of information about addresses,
234 235
 * including edns state (in "flags"), rtt, and of course the address of
 * the host.
Michael Graff's avatar
Michael Graff committed
236
 */
Michael Graff's avatar
Michael Graff committed
237
struct dns_adbentry {
238 239
	unsigned int magic;

Evan Hunt's avatar
Evan Hunt committed
240
	int lock_bucket;
241 242 243
	unsigned int refcnt;
	unsigned int nh;

Evan Hunt's avatar
Evan Hunt committed
244 245 246 247 248
	unsigned int flags;
	unsigned int srtt;
	uint16_t udpsize;
	unsigned int completed;
	unsigned int timeouts;
249 250 251 252 253
	unsigned char plain;
	unsigned char plainto;
	unsigned char edns;
	unsigned char to4096; /* Our max. */

Evan Hunt's avatar
Evan Hunt committed
254
	uint8_t mode;
255 256
	atomic_uint_fast32_t quota;
	atomic_uint_fast32_t active;
Evan Hunt's avatar
Evan Hunt committed
257
	double atr;
Evan Hunt's avatar
Evan Hunt committed
258

259 260 261 262
	/*
	 * Allow for encapsulated IPv4/IPv6 UDP packet over ethernet.
	 * Ethernet 1500 - IP(20) - IP6(40) - UDP(8) = 1432.
	 */
Evan Hunt's avatar
Evan Hunt committed
263 264 265
	unsigned char to1432; /* Ethernet */
	unsigned char to1232; /* IPv6 nofrag */
	unsigned char to512;  /* plain DNS */
266 267
	isc_sockaddr_t sockaddr;
	unsigned char *cookie;
Evan Hunt's avatar
Evan Hunt committed
268
	uint16_t cookielen;
269 270 271

	isc_stdtime_t expires;
	isc_stdtime_t lastage;
Automatic Updater's avatar
Automatic Updater committed
272 273 274 275 276 277 278 279
	/*%<
	 * A nonzero 'expires' field indicates that the entry should
	 * persist until that time.  This allows entries found
	 * using dns_adb_findaddrinfo() to persist for a limited time
	 * even though they are not necessarily associated with a
	 * name.
	 */

280 281
	ISC_LIST(dns_adblameinfo_t) lameinfo;
	ISC_LINK(dns_adbentry_t) plink;
Michael Graff's avatar
Michael Graff committed
282 283
};

Michael Graff's avatar
Michael Graff committed
284
/*
285 286
 * Internal functions (and prototypes).
 */
Ondřej Surý's avatar
Ondřej Surý committed
287 288 289 290 291 292 293 294
static inline dns_adbname_t *
new_adbname(dns_adb_t *, const dns_name_t *);
static inline void
free_adbname(dns_adb_t *, dns_adbname_t **);
static inline dns_adbnamehook_t *
new_adbnamehook(dns_adb_t *, dns_adbentry_t *);
static inline void
free_adbnamehook(dns_adb_t *, dns_adbnamehook_t **);
295 296
static inline dns_adblameinfo_t *
new_adblameinfo(dns_adb_t *, const dns_name_t *, dns_rdatatype_t);
Ondřej Surý's avatar
Ondřej Surý committed
297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314
static inline void
free_adblameinfo(dns_adb_t *, dns_adblameinfo_t **);
static inline dns_adbentry_t *
new_adbentry(dns_adb_t *);
static inline void
free_adbentry(dns_adb_t *, dns_adbentry_t **);
static inline dns_adbfind_t *
new_adbfind(dns_adb_t *);
static inline bool
free_adbfind(dns_adb_t *, dns_adbfind_t **);
static inline dns_adbaddrinfo_t *
new_adbaddrinfo(dns_adb_t *, dns_adbentry_t *, in_port_t);
static inline dns_adbfetch_t *
new_adbfetch(dns_adb_t *);
static inline void
free_adbfetch(dns_adb_t *, dns_adbfetch_t **);
static inline dns_adbname_t *
find_name_and_lock(dns_adb_t *, const dns_name_t *, unsigned int, int *);
315 316
static inline dns_adbentry_t *
find_entry_and_lock(dns_adb_t *, const isc_sockaddr_t *, int *, isc_stdtime_t);
Ondřej Surý's avatar
Ondřej Surý committed
317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385
static void
dump_adb(dns_adb_t *, FILE *, bool debug, isc_stdtime_t);
static void
print_dns_name(FILE *, const dns_name_t *);
static void
print_namehook_list(FILE *, const char *legend, dns_adb_t *adb,
		    dns_adbnamehooklist_t *list, bool debug, isc_stdtime_t now);
static void
print_find_list(FILE *, dns_adbname_t *);
static void
print_fetch_list(FILE *, dns_adbname_t *);
static inline bool
dec_adb_irefcnt(dns_adb_t *);
static inline void
inc_adb_irefcnt(dns_adb_t *);
static inline void
inc_adb_erefcnt(dns_adb_t *);
static inline void
inc_entry_refcnt(dns_adb_t *, dns_adbentry_t *, bool);
static inline bool
dec_entry_refcnt(dns_adb_t *, bool, dns_adbentry_t *, bool);
static inline void
violate_locking_hierarchy(isc_mutex_t *, isc_mutex_t *);
static bool
clean_namehooks(dns_adb_t *, dns_adbnamehooklist_t *);
static void
clean_target(dns_adb_t *, dns_name_t *);
static void
clean_finds_at_name(dns_adbname_t *, isc_eventtype_t, unsigned int);
static bool
check_expire_namehooks(dns_adbname_t *, isc_stdtime_t);
static bool
check_expire_entry(dns_adb_t *, dns_adbentry_t **, isc_stdtime_t);
static void
cancel_fetches_at_name(dns_adbname_t *);
static isc_result_t
dbfind_name(dns_adbname_t *, isc_stdtime_t, dns_rdatatype_t);
static isc_result_t
fetch_name(dns_adbname_t *, bool, unsigned int, isc_counter_t *qc,
	   dns_rdatatype_t);
static inline void
check_exit(dns_adb_t *);
static void
destroy(dns_adb_t *);
static bool
shutdown_names(dns_adb_t *);
static bool
shutdown_entries(dns_adb_t *);
static inline void
link_name(dns_adb_t *, int, dns_adbname_t *);
static inline bool
unlink_name(dns_adb_t *, dns_adbname_t *);
static inline void
link_entry(dns_adb_t *, int, dns_adbentry_t *);
static inline bool
unlink_entry(dns_adb_t *, dns_adbentry_t *);
static bool
kill_name(dns_adbname_t **, isc_eventtype_t);
static void
water(void *, int);
static void
dump_entry(FILE *, dns_adb_t *, dns_adbentry_t *, bool, isc_stdtime_t);
static void
adjustsrtt(dns_adbaddrinfo_t *addr, unsigned int rtt, unsigned int factor,
	   isc_stdtime_t now);
static void
shutdown_task(isc_task_t *task, isc_event_t *ev);
static void
log_quota(dns_adbentry_t *entry, const char *fmt, ...) ISC_FORMAT_PRINTF(2, 3);
Michael Graff's avatar
Michael Graff committed
386

387 388 389
/*
 * MUST NOT overlap DNS_ADBFIND_* flags!
 */
Evan Hunt's avatar
Evan Hunt committed
390 391 392
#define FIND_EVENT_SENT	   0x40000000
#define FIND_EVENT_FREED   0x80000000
#define FIND_EVENTSENT(h)  (((h)->flags & FIND_EVENT_SENT) != 0)
393 394
#define FIND_EVENTFREED(h) (((h)->flags & FIND_EVENT_FREED) != 0)

Evan Hunt's avatar
Evan Hunt committed
395 396 397 398 399 400
#define NAME_NEEDS_POKE	  0x80000000
#define NAME_IS_DEAD	  0x40000000
#define NAME_HINT_OK	  DNS_ADBFIND_HINTOK
#define NAME_GLUE_OK	  DNS_ADBFIND_GLUEOK
#define NAME_STARTATZONE  DNS_ADBFIND_STARTATZONE
#define NAME_DEAD(n)	  (((n)->flags & NAME_IS_DEAD) != 0)
401
#define NAME_NEEDSPOKE(n) (((n)->flags & NAME_NEEDS_POKE) != 0)
Evan Hunt's avatar
Evan Hunt committed
402 403
#define NAME_GLUEOK(n)	  (((n)->flags & NAME_GLUE_OK) != 0)
#define NAME_HINTOK(n)	  (((n)->flags & NAME_HINT_OK) != 0)
404

405 406 407 408
/*
 * Private flag(s) for entries.
 * MUST NOT overlap FCTX_ADDRINFO_xxx and DNS_FETCHOPT_NOEDNS0.
 */
409
#define ENTRY_IS_DEAD 0x00400000
410

411 412
/*
 * To the name, address classes are all that really exist.  If it has a
413
 * V6 address it doesn't care if it came from a AAAA query.
414
 */
Evan Hunt's avatar
Evan Hunt committed
415 416
#define NAME_HAS_V4(n)	  (!ISC_LIST_EMPTY((n)->v4))
#define NAME_HAS_V6(n)	  (!ISC_LIST_EMPTY((n)->v6))
417
#define NAME_HAS_ADDRS(n) (NAME_HAS_V4(n) || NAME_HAS_V6(n))
Michael Graff's avatar
Michael Graff committed
418

419
/*
420
 * Fetches are broken out into A and AAAA types.  In some cases,
421 422
 * however, it makes more sense to test for a particular class of fetches,
 * like V4 or V6 above.
423 424
 * Note: since we have removed the support of A6 in adb, FETCH_A and FETCH_AAAA
 * are now equal to FETCH_V4 and FETCH_V6, respectively.
425
 */
Evan Hunt's avatar
Evan Hunt committed
426
#define NAME_FETCH_A(n)	   ((n)->fetch_a != NULL)
427
#define NAME_FETCH_AAAA(n) ((n)->fetch_aaaa != NULL)
Evan Hunt's avatar
Evan Hunt committed
428 429 430
#define NAME_FETCH_V4(n)   (NAME_FETCH_A(n))
#define NAME_FETCH_V6(n)   (NAME_FETCH_AAAA(n))
#define NAME_FETCH(n)	   (NAME_FETCH_V4(n) || NAME_FETCH_V6(n))
431

432 433 434
/*
 * Find options and tests to see if there are addresses on the list.
 */
Evan Hunt's avatar
Evan Hunt committed
435
#define FIND_WANTEVENT(fn)	(((fn)->options & DNS_ADBFIND_WANTEVENT) != 0)
436
#define FIND_WANTEMPTYEVENT(fn) (((fn)->options & DNS_ADBFIND_EMPTYEVENT) != 0)
Evan Hunt's avatar
Evan Hunt committed
437 438 439 440 441 442
#define FIND_AVOIDFETCHES(fn)	(((fn)->options & DNS_ADBFIND_AVOIDFETCHES) != 0)
#define FIND_STARTATZONE(fn)	(((fn)->options & DNS_ADBFIND_STARTATZONE) != 0)
#define FIND_HINTOK(fn)		(((fn)->options & DNS_ADBFIND_HINTOK) != 0)
#define FIND_GLUEOK(fn)		(((fn)->options & DNS_ADBFIND_GLUEOK) != 0)
#define FIND_HAS_ADDRS(fn)	(!ISC_LIST_EMPTY((fn)->list))
#define FIND_RETURNLAME(fn)	(((fn)->options & DNS_ADBFIND_RETURNLAME) != 0)
443
#define FIND_NOFETCH(fn)	(((fn)->options & DNS_ADBFIND_NOFETCH) != 0)
Bob Halley's avatar
Bob Halley committed
444

445 446 447 448
/*
 * These are currently used on simple unsigned ints, so they are
 * not really associated with any particular type.
 */
Evan Hunt's avatar
Evan Hunt committed
449
#define WANT_INET(x)  (((x)&DNS_ADBFIND_INET) != 0)
450
#define WANT_INET6(x) (((x)&DNS_ADBFIND_INET6) != 0)
451

452
#define EXPIRE_OK(exp, now) ((exp == INT_MAX) || (exp < now))
453

454 455 456 457 458
/*
 * Find out if the flags on a name (nf) indicate if it is a hint or
 * glue, and compare this to the appropriate bits set in o, to see if
 * this is ok.
 */
Evan Hunt's avatar
Evan Hunt committed
459 460
#define GLUE_OK(nf, o)	   (!NAME_GLUEOK(nf) || (((o)&DNS_ADBFIND_GLUEOK) != 0))
#define HINT_OK(nf, o)	   (!NAME_HINTOK(nf) || (((o)&DNS_ADBFIND_HINTOK) != 0))
461
#define GLUEHINT_OK(nf, o) (GLUE_OK(nf, o) || HINT_OK(nf, o))
462 463 464
#define STARTATZONE_MATCHES(nf, o) \
	(((nf)->flags & NAME_STARTATZONE) == ((o)&DNS_ADBFIND_STARTATZONE))

Evan Hunt's avatar
Evan Hunt committed
465 466 467 468
#define ENTER_LEVEL  ISC_LOG_DEBUG(50)
#define EXIT_LEVEL   ENTER_LEVEL
#define CLEAN_LEVEL  ISC_LOG_DEBUG(100)
#define DEF_LEVEL    ISC_LOG_DEBUG(5)
469 470 471 472 473 474 475 476 477 478
#define NCACHE_LEVEL ISC_LOG_DEBUG(20)

#define NCACHE_RESULT(r) \
	((r) == DNS_R_NCACHENXDOMAIN || (r) == DNS_R_NCACHENXRRSET)
#define AUTH_NX(r) ((r) == DNS_R_NXDOMAIN || (r) == DNS_R_NXRRSET)
#define NXDOMAIN_RESULT(r) \
	((r) == DNS_R_NXDOMAIN || (r) == DNS_R_NCACHENXDOMAIN)
#define NXRRSET_RESULT(r)                                      \
	((r) == DNS_R_NCACHENXRRSET || (r) == DNS_R_NXRRSET || \
	 (r) == DNS_R_HINTNXRRSET)
479

Michael Graff's avatar
Michael Graff committed
480 481 482 483
/*
 * Error state rankings.
 */

Evan Hunt's avatar
Evan Hunt committed
484 485 486 487 488
#define FIND_ERR_SUCCESS    0 /* highest rank */
#define FIND_ERR_CANCELED   1
#define FIND_ERR_FAILURE    2
#define FIND_ERR_NXDOMAIN   3
#define FIND_ERR_NXRRSET    4
489
#define FIND_ERR_UNEXPECTED 5
Evan Hunt's avatar
Evan Hunt committed
490 491
#define FIND_ERR_NOTFOUND   6
#define FIND_ERR_MAX	    7
492 493 494 495

static const char *errnames[] = { "success",  "canceled", "failure",
				  "nxdomain", "nxrrset",  "unexpected",
				  "not_found" };
496

497
#define NEWERR(old, new) (ISC_MIN((old), (new)))
Michael Graff's avatar
Michael Graff committed
498 499

static isc_result_t find_err_map[FIND_ERR_MAX] = {
500 501
	ISC_R_SUCCESS, ISC_R_CANCELED,	 ISC_R_FAILURE, DNS_R_NXDOMAIN,
	DNS_R_NXRRSET, ISC_R_UNEXPECTED, ISC_R_NOTFOUND /* not YET found */
Michael Graff's avatar
Michael Graff committed
502
};
503

Ondřej Surý's avatar
Ondřej Surý committed
504 505
static void
DP(int level, const char *format, ...) ISC_FORMAT_PRINTF(2, 3);
506

507
static void
Evan Hunt's avatar
Evan Hunt committed
508
DP(int level, const char *format, ...) {
Automatic Updater's avatar
Automatic Updater committed
509
	va_list args;
510

Automatic Updater's avatar
Automatic Updater committed
511
	va_start(args, format);
512
	isc_log_vwrite(dns_lctx, DNS_LOGCATEGORY_DATABASE, DNS_LOGMODULE_ADB,
Automatic Updater's avatar
Automatic Updater committed
513 514
		       level, format, args);
	va_end(args);
515 516
}

517 518 519 520
/*%
 * Increment resolver-related statistics counters.
 */
static inline void
Evan Hunt's avatar
Evan Hunt committed
521
inc_stats(dns_adb_t *adb, isc_statscounter_t counter) {
522
	if (adb->view->resstats != NULL) {
523
		isc_stats_increment(adb->view->resstats, counter);
524
	}
525 526
}

527 528 529 530
/*%
 * Set adb-related statistics counters.
 */
static inline void
Evan Hunt's avatar
Evan Hunt committed
531
set_adbstat(dns_adb_t *adb, uint64_t val, isc_statscounter_t counter) {
532
	if (adb->view->adbstats != NULL) {
533
		isc_stats_set(adb->view->adbstats, val, counter);
534
	}
535 536 537
}

static inline void
Evan Hunt's avatar
Evan Hunt committed
538
dec_adbstats(dns_adb_t *adb, isc_statscounter_t counter) {
539
	if (adb->view->adbstats != NULL) {
540
		isc_stats_decrement(adb->view->adbstats, counter);
541
	}
542 543 544
}

static inline void
Evan Hunt's avatar
Evan Hunt committed
545
inc_adbstats(dns_adb_t *adb, isc_statscounter_t counter) {
546
	if (adb->view->adbstats != NULL) {
547
		isc_stats_increment(adb->view->adbstats, counter);
548
	}
549 550
}

551
static inline dns_ttl_t
Evan Hunt's avatar
Evan Hunt committed
552
ttlclamp(dns_ttl_t ttl) {
553
	if (ttl < ADB_CACHE_MINIMUM) {
Automatic Updater's avatar
Automatic Updater committed
554
		ttl = ADB_CACHE_MINIMUM;
555 556
	}
	if (ttl > ADB_CACHE_MAXIMUM) {
Automatic Updater's avatar
Automatic Updater committed
557
		ttl = ADB_CACHE_MAXIMUM;
558
	}
559

Automatic Updater's avatar
Automatic Updater committed
560
	return (ttl);
561 562
}

563 564 565 566 567 568
/*
 * Hashing is most efficient if the number of buckets is prime.
 * The sequence below is the closest previous primes to 2^n and
 * 1.5 * 2^n, for values of n from 10 to 28.  (The tables will
 * no longer grow beyond 2^28 entries.)
 */
569 570 571 572 573 574 575 576 577
static const unsigned nbuckets[] = {
	1021,	   1531,     2039,     3067,	  4093,	     6143,
	8191,	   12281,    16381,    24571,	  32749,     49193,
	65521,	   98299,    131071,   199603,	  262139,    393209,
	524287,	   768431,   1048573,  1572853,	  2097143,   3145721,
	4194301,   6291449,  8388593,  12582893,  16777213,  25165813,
	33554393,  50331599, 67108859, 100663291, 134217689, 201326557,
	268535431, 0
};
578 579

static void
Evan Hunt's avatar
Evan Hunt committed
580 581 582
grow_entries(isc_task_t *task, isc_event_t *ev) {
	dns_adb_t *adb;
	dns_adbentry_t *e;
583 584
	dns_adbentrylist_t *newdeadentries = NULL;
	dns_adbentrylist_t *newentries = NULL;
Evan Hunt's avatar
Evan Hunt committed
585 586 587 588 589
	bool *newentry_sd = NULL;
	isc_mutex_t *newentrylocks = NULL;
	isc_result_t result;
	unsigned int *newentry_refcnt = NULL;
	unsigned int i, n, bucket;
Automatic Updater's avatar
Automatic Updater committed
590

591 592 593 594 595
	adb = ev->ev_arg;
	INSIST(DNS_ADB_VALID(adb));

	isc_event_free(&ev);

596
	result = isc_task_beginexclusive(task);
597
	if (result != ISC_R_SUCCESS) {
598
		goto check_exit;
599
	}
600 601

	i = 0;
602
	while (nbuckets[i] != 0 && adb->nentries >= nbuckets[i]) {
603
		i++;
604 605
	}
	if (nbuckets[i] != 0) {
606
		n = nbuckets[i];
607
	} else {
608
		goto done;
609
	}
610 611 612 613 614 615

	DP(ISC_LOG_INFO, "adb: grow_entries to %u starting", n);

	/*
	 * Are we shutting down?
	 */
616 617
	for (i = 0; i < adb->nentries; i++) {
		if (adb->entry_sd[i]) {
618 619
			goto cleanup;

620 621 622
			/*
			 * Grab all the resources we need.
			 */
623 624 625
		}
	}

626 627 628 629 630 631 632 633 634 635
	/*
	 * Grab all the resources we need.
	 */
	newentries = isc_mem_get(adb->mctx, sizeof(*newentries) * n);
	newdeadentries = isc_mem_get(adb->mctx, sizeof(*newdeadentries) * n);
	newentrylocks = isc_mem_get(adb->mctx, sizeof(*newentrylocks) * n);
	newentry_sd = isc_mem_get(adb->mctx, sizeof(*newentry_sd) * n);
	newentry_refcnt = isc_mem_get(adb->mctx, sizeof(*newentry_refcnt) * n);
	if (newentries == NULL || newdeadentries == NULL ||
	    newentrylocks == NULL || newentry_sd == NULL ||
Evan Hunt's avatar
Evan Hunt committed
636 637
	    newentry_refcnt == NULL)
	{
638
		goto cleanup;
639
	}
640 641 642 643

	/*
	 * Initialise the new resources.
	 */
644
	isc_mutexblock_init(newentrylocks, n);
645 646 647 648

	for (i = 0; i < n; i++) {
		ISC_LIST_INIT(newentries[i]);
		ISC_LIST_INIT(newdeadentries[i]);
649
		newentry_sd[i] = false;
650 651 652 653 654 655 656 657 658 659 660
		newentry_refcnt[i] = 0;
		adb->irefcnt++;
	}

	/*
	 * Move entries to new arrays.
	 */
	for (i = 0; i < adb->nentries; i++) {
		e = ISC_LIST_HEAD(adb->entries[i]);
		while (e != NULL) {
			ISC_LIST_UNLINK(adb->entries[i], e, plink);
661
			bucket = isc_sockaddr_hash(&e->sockaddr, true) % n;
662 663 664 665 666 667 668 669 670 671
			e->lock_bucket = bucket;
			ISC_LIST_APPEND(newentries[bucket], e, plink);
			INSIST(adb->entry_refcnt[i] > 0);
			adb->entry_refcnt[i]--;
			newentry_refcnt[bucket]++;
			e = ISC_LIST_HEAD(adb->entries[i]);
		}
		e = ISC_LIST_HEAD(adb->deadentries[i]);
		while (e != NULL) {
			ISC_LIST_UNLINK(adb->deadentries[i], e, plink);
672
			bucket = isc_sockaddr_hash(&e->sockaddr, true) % n;
673 674 675 676 677 678 679 680 681 682 683 684 685 686
			e->lock_bucket = bucket;
			ISC_LIST_APPEND(newdeadentries[bucket], e, plink);
			INSIST(adb->entry_refcnt[i] > 0);
			adb->entry_refcnt[i]--;
			newentry_refcnt[bucket]++;
			e = ISC_LIST_HEAD(adb->deadentries[i]);
		}
		INSIST(adb->entry_refcnt[i] == 0);
		adb->irefcnt--;
	}

	/*
	 * Cleanup old resources.
	 */
687
	isc_mutexblock_destroy(adb->entrylocks, adb->nentries);
688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708
	isc_mem_put(adb->mctx, adb->entries,
		    sizeof(*adb->entries) * adb->nentries);
	isc_mem_put(adb->mctx, adb->deadentries,
		    sizeof(*adb->deadentries) * adb->nentries);
	isc_mem_put(adb->mctx, adb->entrylocks,
		    sizeof(*adb->entrylocks) * adb->nentries);
	isc_mem_put(adb->mctx, adb->entry_sd,
		    sizeof(*adb->entry_sd) * adb->nentries);
	isc_mem_put(adb->mctx, adb->entry_refcnt,
		    sizeof(*adb->entry_refcnt) * adb->nentries);

	/*
	 * Install new resources.
	 */
	adb->entries = newentries;
	adb->deadentries = newdeadentries;
	adb->entrylocks = newentrylocks;
	adb->entry_sd = newentry_sd;
	adb->entry_refcnt = newentry_refcnt;
	adb->nentries = n;

709 710
	set_adbstat(adb, adb->nentries, dns_adbstats_nentries);

711
	/*
712
	 * Only on success do we set adb->growentries_sent to false.
713 714
	 * This will prevent us being continuously being called on error.
	 */
715
	adb->growentries_sent = false;
716 717
	goto done;

718
cleanup:
719
	if (newentries != NULL) {
720
		isc_mem_put(adb->mctx, newentries, sizeof(*newentries) * n);
721 722
	}
	if (newdeadentries != NULL) {
723 724
		isc_mem_put(adb->mctx, newdeadentries,
			    sizeof(*newdeadentries) * n);
725 726
	}
	if (newentrylocks != NULL) {
727 728
		isc_mem_put(adb->mctx, newentrylocks,
			    sizeof(*newentrylocks) * n);
729 730
	}
	if (newentry_sd != NULL) {
731
		isc_mem_put(adb->mctx, newentry_sd, sizeof(*newentry_sd) * n);
732 733
	}
	if (newentry_refcnt != NULL) {
734
		isc_mem_put(adb->mctx, newentry_refcnt,
735
			    sizeof(*newentry_refcnt) * n);
736
	}
737
done:
738 739
	isc_task_endexclusive(task);

740
check_exit:
Automatic Updater's avatar
Automatic Updater committed
741
	LOCK(&adb->lock);
742
	if (dec_adb_irefcnt(adb)) {
Automatic Updater's avatar
Automatic Updater committed
743
		check_exit(adb);
744
	}
Automatic Updater's avatar
Automatic Updater committed
745
	UNLOCK(&adb->lock);
746 747 748 749
	DP(ISC_LOG_INFO, "adb: grow_entries finished");
}

static void
Evan Hunt's avatar
Evan Hunt committed
750 751 752
grow_names(isc_task_t *task, isc_event_t *ev) {
	dns_adb_t *adb;
	dns_adbname_t *name;
753 754
	dns_adbnamelist_t *newdeadnames = NULL;
	dns_adbnamelist_t *newnames = NULL;
Evan Hunt's avatar
Evan Hunt committed
755 756 757 758
	bool *newname_sd = NULL;
	isc_mutex_t *newnamelocks = NULL;
	isc_result_t result;
	unsigned int *newname_refcnt = NULL;
759 760
	unsigned int i, n;
	unsigned int bucket;
Automatic Updater's avatar
Automatic Updater committed
761

762 763 764 765 766
	adb = ev->ev_arg;
	INSIST(DNS_ADB_VALID(adb));

	isc_event_free(&ev);

767
	result = isc_task_beginexclusive(task);
768
	if (result != ISC_R_SUCCESS) {
769
		goto check_exit;
770
	}
771 772

	i = 0;
773
	while (nbuckets[i] != 0 && adb->nnames >= nbuckets[i]) {
774
		i++;
775 776
	}
	if (nbuckets[i] != 0) {
777
		n = nbuckets[i];
778
	} else {
779
		goto done;
780
	}
781 782 783 784 785 786

	DP(ISC_LOG_INFO, "adb: grow_names to %u starting", n);

	/*
	 * Are we shutting down?
	 */
787 788
	for (i = 0; i < adb->nnames; i++) {
		if (adb->name_sd[i]) {
789 790
			goto cleanup;

791 792 793
			/*
			 * Grab all the resources we need.
			 */
794 795 796
		}
	}

797 798 799 800 801 802 803 804
	/*
	 * Grab all the resources we need.
	 */
	newnames = isc_mem_get(adb->mctx, sizeof(*newnames) * n);
	newdeadnames = isc_mem_get(adb->mctx, sizeof(*newdeadnames) * n);
	newnamelocks = isc_mem_get(adb->mctx, sizeof(*newnamelocks) * n);
	newname_sd = isc_mem_get(adb->mctx, sizeof(*newname_sd) * n);
	newname_refcnt = isc_mem_get(adb->mctx, sizeof(*newname_refcnt) * n);
805
	if (newnames == NULL || newdeadnames == NULL || newnamelocks == NULL ||
Evan Hunt's avatar
Evan Hunt committed
806 807
	    newname_sd == NULL || newname_refcnt == NULL)
	{
808
		goto cleanup;
809
	}
810 811 812 813

	/*
	 * Initialise the new resources.
	 */
814
	isc_mutexblock_init(newnamelocks, n);
815 816 817 818

	for (i = 0; i < n; i++) {
		ISC_LIST_INIT(newnames[i]);
		ISC_LIST_INIT(newdeadnames[i]);
819
		newname_sd[i] = false;
820 821 822 823 824 825 826 827 828 829 830
		newname_refcnt[i] = 0;
		adb->irefcnt++;
	}

	/*
	 * Move names to new arrays.
	 */
	for (i = 0; i < adb->nnames; i++) {
		name = ISC_LIST_HEAD(adb->names[i]);
		while (name != NULL) {
			ISC_LIST_UNLINK(adb->names[i], name, plink);
831
			bucket = dns_name_fullhash(&name->name, true) % n;
832 833 834 835 836 837 838 839 840 841
			name->lock_bucket = bucket;
			ISC_LIST_APPEND(newnames[bucket], name, plink);
			INSIST(adb->name_refcnt[i] > 0);
			adb->name_refcnt[i]--;
			newname_refcnt[bucket]++;
			name = ISC_LIST_HEAD(adb->names[i]);
		}
		name = ISC_LIST_HEAD(adb->deadnames[i]);
		while (name != NULL) {
			ISC_LIST_UNLINK(adb->deadnames[i], name, plink);
842
			bucket = dns_name_fullhash(&name->name, true) % n;
843 844 845 846 847 848 849 850 851 852 853 854 855 856
			name->lock_bucket = bucket;
			ISC_LIST_APPEND(newdeadnames[bucket], name, plink);
			INSIST(adb->name_refcnt[i] > 0);
			adb->name_refcnt[i]--;
			newname_refcnt[bucket]++;
			name = ISC_LIST_HEAD(adb->deadnames[i]);
		}
		INSIST(adb->name_refcnt[i] == 0);
		adb->irefcnt--;
	}

	/*
	 * Cleanup old resources.
	 */
857
	isc_mutexblock_destroy(adb->namelocks, adb->nnames);
858
	isc_mem_put(adb->mctx, adb->names, sizeof(*adb->names) * adb->nnames);
859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877
	isc_mem_put(adb->mctx, adb->deadnames,
		    sizeof(*adb->deadnames) * adb->nnames);
	isc_mem_put(adb->mctx, adb->namelocks,
		    sizeof(*adb->namelocks) * adb->nnames);
	isc_mem_put(adb->mctx, adb->name_sd,
		    sizeof(*adb->name_sd) * adb->nnames);
	isc_mem_put(adb->mctx, adb->name_refcnt,
		    sizeof(*adb->name_refcnt) * adb->nnames);

	/*
	 * Install new resources.
	 */
	adb->names = newnames;
	adb->deadnames = newdeadnames;
	adb->namelocks = newnamelocks;
	adb->name_sd = newname_sd;
	adb->name_refcnt = newname_refcnt;
	adb->nnames = n;

878 879
	set_adbstat(adb, adb->nnames, dns_adbstats_nnames);

880
	/*
881
	 * Only on success do we set adb->grownames_sent to false.
882 883
	 * This will prevent us being continuously being called on error.
	 */
884
	adb->grownames_sent = false;
885 886
	goto done;

887
cleanup:
888
	if (newnames != NULL) {
889
		isc_mem_put(adb->mctx, newnames, sizeof(*newnames) * n);
890 891
	}
	if (newdeadnames != NULL) {
892
		isc_mem_put(adb->mctx, newdeadnames, sizeof(*newdeadnames) * n);
893 894
	}
	if (newnamelocks != NULL) {
895
		isc_mem_put(adb->mctx, newnamelocks, sizeof(*newnamelocks) * n);
896 897
	}
	if (newname_sd != NULL) {
898
		isc_mem_put(adb->mctx, newname_sd, sizeof(*newname_sd) * n);
899 900
	}
	if (newname_refcnt != NULL) {
901
		isc_mem_put(adb->mctx, newname_refcnt,
902
			    sizeof(*newname_refcnt) * n);
903
	}
904
done:
905 906
	isc_task_endexclusive(task);

907
check_exit:
Automatic Updater's avatar
Automatic Updater committed
908
	LOCK(&adb->lock);
909
	if (dec_adb_irefcnt(adb)) {
Automatic Updater's avatar
Automatic Updater committed
910
		check_exit(adb);
911
	}
Automatic Updater's avatar
Automatic Updater committed
912
	UNLOCK(&adb->lock);
913 914 915
	DP(ISC_LOG_INFO, "adb: grow_names finished");
}

916 917
/*
 * Requires the adbname bucket be locked and that no entry buckets be locked.
918 919
 *
 * This code handles A and AAAA rdatasets only.
920 921
 */
static isc_result_t
922
import_rdataset(dns_adbname_t *adbname, dns_rdataset_t *rdataset,
Evan Hunt's avatar
Evan Hunt committed
923 924 925 926 927 928 929 930 931 932 933 934 935 936
		isc_stdtime_t now) {
	isc_result_t result;
	dns_adb_t *adb;
	dns_adbnamehook_t *nh;
	dns_adbnamehook_t *anh;
	dns_rdata_t rdata = DNS_RDATA_INIT;
	struct in_addr ina;
	struct in6_addr in6a;
	isc_sockaddr_t sockaddr;
	dns_adbentry_t *foundentry; /* NO CLEAN UP! */
	int addr_bucket;
	bool new_addresses_added;
	dns_rdatatype_t rdtype;
	unsigned int findoptions;
937
	dns_adbnamehooklist_t *hookhead;
Automatic Updater's avatar
Automatic Updater committed
938 939 940 941 942 943 944

	INSIST(DNS_ADBNAME_VALID(adbname));
	adb = adbname->adb;
	INSIST(DNS_ADB_VALID(adb));

	rdtype = rdataset->type;
	INSIST((rdtype == dns_rdatatype_a) || (rdtype == dns_rdatatype_aaaa));
945
	if (rdtype == dns_rdatatype_a) {
Automatic Updater's avatar
Automatic Updater committed
946
		findoptions = DNS_ADBFIND_INET;
947
	} else {
Automatic Updater's avatar
Automatic Updater committed
948
		findoptions = DNS_ADBFIND_INET6;
949
	}
Automatic Updater's avatar
Automatic Updater committed
950 951

	addr_bucket = DNS_ADB_INVALIDBUCKET;
952
	new_addresses_added = false;
Automatic Updater's avatar
Automatic Updater committed
953 954 955 956 957 958 959 960

	nh = NULL;
	result = dns_rdataset_first(rdataset);
	while (result == ISC_R_SUCCESS) {
		dns_rdata_reset(&rdata);
		dns_rdataset_current(rdataset, &rdata);
		if (rdtype == dns_rdatatype_a) {
			INSIST(rdata.length == 4);
961
			memmove(&ina.s_addr, rdata.data, 4);
Automatic Updater's avatar
Automatic Updater committed
962
			isc_sockaddr_fromin(&sockaddr, &ina, 0);