rrl.c 33.1 KB
Newer Older
Evan Hunt's avatar
Evan Hunt committed
1
/*
2
 * Copyright (C) Internet Systems Consortium, Inc. ("ISC")
Evan Hunt's avatar
Evan Hunt committed
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.
Evan Hunt's avatar
Evan Hunt committed
10 11 12 13 14 15 16 17 18 19 20
 */

/*! \file */

/*
 * Rate limit DNS responses.
 */

/* #define ISC_LIST_CHECKINIT */

#include <config.h>
21 22

#include <inttypes.h>
23
#include <stdbool.h>
24

Evan Hunt's avatar
Evan Hunt committed
25 26 27
#include <isc/mem.h>
#include <isc/net.h>
#include <isc/netaddr.h>
28
#include <isc/print.h>
29
#include <isc/util.h>
Evan Hunt's avatar
Evan Hunt committed
30 31 32 33 34 35 36 37 38 39

#include <dns/result.h>
#include <dns/rcode.h>
#include <dns/rdatatype.h>
#include <dns/rdataclass.h>
#include <dns/log.h>
#include <dns/rrl.h>
#include <dns/view.h>

static void
40
log_end(dns_rrl_t *rrl, dns_rrl_entry_t *e, bool early,
Evan Hunt's avatar
Evan Hunt committed
41 42 43 44 45 46 47 48 49 50 51 52
	char *log_buf, unsigned int log_buf_len);

/*
 * Get a modulus for a hash function that is tolerably likely to be
 * relatively prime to most inputs.  Of course, we get a prime for for initial
 * values not larger than the square of the last prime.  We often get a prime
 * after that.
 * This works well in practice for hash tables up to at least 100
 * times the square of the last prime and better than a multiplicative hash.
 */
static int
hash_divisor(unsigned int initial) {
53
	static uint16_t primes[] = {
Evan Hunt's avatar
Evan Hunt committed
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
		  3,   5,   7,  11,  13,  17,  19,  23,  29,  31,  37,  41,
		 43,  47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97,
#if 0
		101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157,
		163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
		229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283,
		293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367,
		373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439,
		443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
		521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
		601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661,
		673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751,
		757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
		839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919,
		929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,1009,
#endif
	};
	int divisions, tries;
	unsigned int result;
73
	uint16_t *pp, p;
Evan Hunt's avatar
Evan Hunt committed
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169

	result = initial;

	if (primes[sizeof(primes)/sizeof(primes[0])-1] >= result) {
		pp = primes;
		while (*pp < result)
			++pp;
		return (*pp);
	}

	if ((result & 1) == 0)
		++result;

	divisions = 0;
	tries = 1;
	pp = primes;
	do {
		p = *pp++;
		++divisions;
		if ((result % p) == 0) {
			++tries;
			result += 2;
			pp = primes;
		}
	} while (pp < &primes[sizeof(primes) / sizeof(primes[0])]);

	if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DEBUG3))
		isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
			      DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DEBUG3,
			      "%d hash_divisor() divisions in %d tries"
			      " to get %d from %d",
			      divisions, tries, result, initial);

	return (result);
}

/*
 * Convert a timestamp to a number of seconds in the past.
 */
static inline int
delta_rrl_time(isc_stdtime_t ts, isc_stdtime_t now) {
	int delta;

	delta = now - ts;
	if (delta >= 0)
		return (delta);

	/*
	 * The timestamp is in the future.  That future might result from
	 * re-ordered requests, because we use timestamps on requests
	 * instead of consulting a clock.  Timestamps in the distant future are
	 * assumed to result from clock changes.  When the clock changes to
	 * the past, make existing timestamps appear to be in the past.
	 */
	if (delta < -DNS_RRL_MAX_TIME_TRAVEL)
		return (DNS_RRL_FOREVER);
	return (0);
}

static inline int
get_age(const dns_rrl_t *rrl, const dns_rrl_entry_t *e, isc_stdtime_t now) {
	if (!e->ts_valid)
		return (DNS_RRL_FOREVER);
	return (delta_rrl_time(e->ts + rrl->ts_bases[e->ts_gen], now));
}

static inline void
set_age(dns_rrl_t *rrl, dns_rrl_entry_t *e, isc_stdtime_t now) {
	dns_rrl_entry_t *e_old;
	unsigned int ts_gen;
	int i, ts;

	ts_gen = rrl->ts_gen;
	ts = now - rrl->ts_bases[ts_gen];
	if (ts < 0) {
		if (ts < -DNS_RRL_MAX_TIME_TRAVEL)
			ts = DNS_RRL_FOREVER;
		else
			ts = 0;
	}

	/*
	 * Make a new timestamp base if the current base is too old.
	 * All entries older than DNS_RRL_MAX_WINDOW seconds are ancient,
	 * useless history.  Their timestamps can be treated as if they are
	 * all the same.
	 * We only do arithmetic on more recent timestamps, so bases for
	 * older timestamps can be recycled provided the old timestamps are
	 * marked as ancient history.
	 * This loop is almost always very short because most entries are
	 * recycled after one second and any entries that need to be marked
	 * are older than (DNS_RRL_TS_BASES)*DNS_RRL_MAX_TS seconds.
	 */
	if (ts >= DNS_RRL_MAX_TS) {
		ts_gen = (ts_gen + 1) % DNS_RRL_TS_BASES;
		for (e_old = ISC_LIST_TAIL(rrl->lru), i = 0;
Evan Hunt's avatar
Evan Hunt committed
170 171
		     e_old != NULL && (e_old->ts_gen == ts_gen ||
				       !ISC_LINK_LINKED(e_old, hlink));
Evan Hunt's avatar
Evan Hunt committed
172 173
		     e_old = ISC_LIST_PREV(e_old, lru), ++i)
		{
174
			e_old->ts_valid = false;
Evan Hunt's avatar
Evan Hunt committed
175 176 177 178 179 180 181 182
		}
		if (i != 0)
			isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
				      DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DEBUG1,
				      "rrl new time base scanned %d entries"
				      " at %d for %d %d %d %d",
				      i, now, rrl->ts_bases[ts_gen],
				      rrl->ts_bases[(ts_gen + 1) %
Mark Andrews's avatar
Mark Andrews committed
183
					DNS_RRL_TS_BASES],
Evan Hunt's avatar
Evan Hunt committed
184
				      rrl->ts_bases[(ts_gen + 2) %
Mark Andrews's avatar
Mark Andrews committed
185
					DNS_RRL_TS_BASES],
Evan Hunt's avatar
Evan Hunt committed
186
				      rrl->ts_bases[(ts_gen + 3) %
Mark Andrews's avatar
Mark Andrews committed
187
					DNS_RRL_TS_BASES]);
Evan Hunt's avatar
Evan Hunt committed
188 189 190 191 192 193 194
		rrl->ts_gen = ts_gen;
		rrl->ts_bases[ts_gen] = now;
		ts = 0;
	}

	e->ts_gen = ts_gen;
	e->ts = ts;
195
	e->ts_valid = true;
Evan Hunt's avatar
Evan Hunt committed
196 197 198
}

static isc_result_t
199
expand_entries(dns_rrl_t *rrl, int newsize) {
Evan Hunt's avatar
Evan Hunt committed
200 201 202 203 204 205
	unsigned int bsize;
	dns_rrl_block_t *b;
	dns_rrl_entry_t *e;
	double rate;
	int i;

206
	if (rrl->num_entries + newsize >= rrl->max_entries &&
207 208
	    rrl->max_entries != 0)
	{
209 210
		newsize = rrl->max_entries - rrl->num_entries;
		if (newsize <= 0)
211
			return (ISC_R_SUCCESS);
Evan Hunt's avatar
Evan Hunt committed
212 213 214 215 216 217 218 219 220 221 222 223 224 225 226
	}

	/*
	 * Log expansions so that the user can tune max-table-size
	 * and min-table-size.
	 */
	if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DROP) &&
	    rrl->hash != NULL) {
		rate = rrl->probes;
		if (rrl->searches != 0)
			rate /= rrl->searches;
		isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
			      DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DROP,
			      "increase from %d to %d RRL entries with"
			      " %d bins; average search length %.1f",
227
			      rrl->num_entries, rrl->num_entries+newsize,
Evan Hunt's avatar
Evan Hunt committed
228 229 230
			      rrl->hash->length, rate);
	}

231
	bsize = sizeof(dns_rrl_block_t) + (newsize-1)*sizeof(dns_rrl_entry_t);
Evan Hunt's avatar
Evan Hunt committed
232 233 234 235 236 237 238 239 240 241 242 243
	b = isc_mem_get(rrl->mctx, bsize);
	if (b == NULL) {
		isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
			      DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_FAIL,
			      "isc_mem_get(%d) failed for RRL entries",
			      bsize);
		return (ISC_R_NOMEMORY);
	}
	memset(b, 0, bsize);
	b->size = bsize;

	e = b->entries;
244
	for (i = 0; i < newsize; ++i, ++e) {
Evan Hunt's avatar
Evan Hunt committed
245 246 247
		ISC_LINK_INIT(e, hlink);
		ISC_LIST_INITANDAPPEND(rrl->lru, e, lru);
	}
248
	rrl->num_entries += newsize;
Evan Hunt's avatar
Evan Hunt committed
249 250 251 252 253 254 255
	ISC_LIST_INITANDAPPEND(rrl->blocks, b, link);

	return (ISC_R_SUCCESS);
}

static inline dns_rrl_bin_t *
get_bin(dns_rrl_hash_t *hash, unsigned int hval) {
256
	INSIST(hash != NULL);
Evan Hunt's avatar
Evan Hunt committed
257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 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
	return (&hash->bins[hval % hash->length]);
}

static void
free_old_hash(dns_rrl_t *rrl) {
	dns_rrl_hash_t *old_hash;
	dns_rrl_bin_t *old_bin;
	dns_rrl_entry_t *e, *e_next;

	old_hash = rrl->old_hash;
	for (old_bin = &old_hash->bins[0];
	     old_bin < &old_hash->bins[old_hash->length];
	     ++old_bin)
	{
		for (e = ISC_LIST_HEAD(*old_bin); e != NULL; e = e_next) {
			e_next = ISC_LIST_NEXT(e, hlink);
			ISC_LINK_INIT(e, hlink);
		}
	}

	isc_mem_put(rrl->mctx, old_hash,
		    sizeof(*old_hash)
		      + (old_hash->length - 1) * sizeof(old_hash->bins[0]));
	rrl->old_hash = NULL;
}

static isc_result_t
expand_rrl_hash(dns_rrl_t *rrl, isc_stdtime_t now) {
	dns_rrl_hash_t *hash;
	int old_bins, new_bins, hsize;
	double rate;

	if (rrl->old_hash != NULL)
		free_old_hash(rrl);

	/*
	 * Most searches fail and so go to the end of the chain.
	 * Use a small hash table load factor.
	 */
	old_bins = (rrl->hash == NULL) ? 0 : rrl->hash->length;
	new_bins = old_bins/8 + old_bins;
	if (new_bins < rrl->num_entries)
		new_bins = rrl->num_entries;
	new_bins = hash_divisor(new_bins);

	hsize = sizeof(dns_rrl_hash_t) + (new_bins-1)*sizeof(hash->bins[0]);
	hash = isc_mem_get(rrl->mctx, hsize);
	if (hash == NULL) {
		isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
			      DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_FAIL,
			      "isc_mem_get(%d) failed for"
			      " RRL hash table",
			      hsize);
		return (ISC_R_NOMEMORY);
	}
	memset(hash, 0, hsize);
	hash->length = new_bins;
	rrl->hash_gen ^= 1;
	hash->gen = rrl->hash_gen;

	if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DROP) && old_bins != 0) {
		rate = rrl->probes;
		if (rrl->searches != 0)
			rate /= rrl->searches;
		isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
			      DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DROP,
			      "increase from %d to %d RRL bins for"
			      " %d entries; average search length %.1f",
			      old_bins, new_bins, rrl->num_entries, rate);
	}

	rrl->old_hash = rrl->hash;
	if (rrl->old_hash != NULL)
		rrl->old_hash->check_time = now;
	rrl->hash = hash;

	return (ISC_R_SUCCESS);
}

static void
ref_entry(dns_rrl_t *rrl, dns_rrl_entry_t *e, int probes, isc_stdtime_t now) {
	/*
	 * Make the entry most recently used.
	 */
	if (ISC_LIST_HEAD(rrl->lru) != e) {
		if (e == rrl->last_logged)
			rrl->last_logged = ISC_LIST_PREV(e, lru);
		ISC_LIST_UNLINK(rrl->lru, e, lru);
		ISC_LIST_PREPEND(rrl->lru, e, lru);
	}

	/*
	 * Expand the hash table if it is time and necessary.
	 * This will leave the newly referenced entry in a chain in the
	 * old hash table.  It will migrate to the new hash table the next
	 * time it is used or be cut loose when the old hash table is destroyed.
	 */
	rrl->probes += probes;
	++rrl->searches;
	if (rrl->searches > 100 &&
	    delta_rrl_time(rrl->hash->check_time, now) > 1) {
		if (rrl->probes/rrl->searches > 2)
			expand_rrl_hash(rrl, now);
		rrl->hash->check_time = now;
		rrl->probes = 0;
		rrl->searches = 0;
	}
}

366
static inline bool
Evan Hunt's avatar
Evan Hunt committed
367 368
key_cmp(const dns_rrl_key_t *a, const dns_rrl_key_t *b) {
	if (memcmp(a, b, sizeof(dns_rrl_key_t)) == 0)
369 370
		return (true);
	return (false);
Evan Hunt's avatar
Evan Hunt committed
371 372
}

373
static inline uint32_t
Evan Hunt's avatar
Evan Hunt committed
374
hash_key(const dns_rrl_key_t *key) {
375
	uint32_t hval;
Evan Hunt's avatar
Evan Hunt committed
376 377 378
	int i;

	hval = key->w[0];
379
	for (i = sizeof(key->w) / sizeof(key->w[0]) - 1; i >= 0; --i) {
Evan Hunt's avatar
Evan Hunt committed
380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395
		hval = key->w[i] + (hval<<1);
	}
	return (hval);
}

/*
 * Construct the hash table key.
 * Use a hash of the DNS query name to save space in the database.
 * Collisions result in legitimate rate limiting responses for one
 * query name also limiting responses for other names to the
 * same client.  This is rare and benign enough given the large
 * space costs compared to keeping the entire name in the database
 * entry or the time costs of dynamic allocation.
 */
static void
make_key(const dns_rrl_t *rrl, dns_rrl_key_t *key,
396 397
	 const isc_sockaddr_t *client_addr, dns_rdatatype_t qtype,
	 const dns_name_t *qname, dns_rdataclass_t qclass,
Evan Hunt's avatar
Evan Hunt committed
398 399 400 401 402 403 404 405 406
	 dns_rrl_rtype_t rtype)
{
	dns_name_t base;
	dns_offsets_t base_offsets;
	int labels, i;

	memset(key, 0, sizeof(*key));

	key->s.rtype = rtype;
Evan Hunt's avatar
Evan Hunt committed
407
	if (rtype == DNS_RRL_RTYPE_QUERY) {
Evan Hunt's avatar
Evan Hunt committed
408
		key->s.qtype = qtype;
Evan Hunt's avatar
Evan Hunt committed
409 410 411 412 413 414 415 416
		key->s.qclass = qclass & 0xff;
	} else if (rtype == DNS_RRL_RTYPE_REFERRAL ||
		   rtype == DNS_RRL_RTYPE_NODATA) {
		/*
		 * Because there is no qtype in the empty answer sections of
		 * referral and NODATA responses, count them as the same.
		 */
		key->s.qclass = qclass & 0xff;
Evan Hunt's avatar
Evan Hunt committed
417 418 419 420 421 422 423 424 425 426 427
	}

	if (qname != NULL && qname->labels != 0) {
		/*
		 * Ignore the first label of wildcards.
		 */
		if ((qname->attributes & DNS_NAMEATTR_WILDCARD) != 0 &&
		    (labels = dns_name_countlabels(qname)) > 1)
		{
			dns_name_init(&base, base_offsets);
			dns_name_getlabelsequence(qname, 1, labels-1, &base);
428
			key->s.qname_hash =
429
				dns_name_fullhash(&base, false);
Evan Hunt's avatar
Evan Hunt committed
430
		} else {
431
			key->s.qname_hash =
432
				dns_name_fullhash(qname, false);
Evan Hunt's avatar
Evan Hunt committed
433 434 435 436 437 438 439 440 441
		}
	}

	switch (client_addr->type.sa.sa_family) {
	case AF_INET:
		key->s.ip[0] = (client_addr->type.sin.sin_addr.s_addr &
			      rrl->ipv4_mask);
		break;
	case AF_INET6:
442
		key->s.ipv6 = true;
443 444
		memmove(key->s.ip, &client_addr->type.sin6.sin6_addr,
			sizeof(key->s.ip));
Evan Hunt's avatar
Evan Hunt committed
445 446 447 448 449 450
		for (i = 0; i < DNS_RRL_MAX_PREFIX/32; ++i)
			key->s.ip[i] &= rrl->ipv6_mask[i];
		break;
	}
}

Evan Hunt's avatar
Evan Hunt committed
451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467
static inline dns_rrl_rate_t *
get_rate(dns_rrl_t *rrl, dns_rrl_rtype_t rtype) {
	switch (rtype) {
	case DNS_RRL_RTYPE_QUERY:
		return (&rrl->responses_per_second);
	case DNS_RRL_RTYPE_REFERRAL:
		return (&rrl->referrals_per_second);
	case DNS_RRL_RTYPE_NODATA:
		return (&rrl->nodata_per_second);
	case DNS_RRL_RTYPE_NXDOMAIN:
		return (&rrl->nxdomains_per_second);
	case DNS_RRL_RTYPE_ERROR:
		return (&rrl->errors_per_second);
	case DNS_RRL_RTYPE_ALL:
		return (&rrl->all_per_second);
	default:
		INSIST(0);
Evan Hunt's avatar
Evan Hunt committed
468
	}
Evan Hunt's avatar
Evan Hunt committed
469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484
	return (NULL);
}

static int
response_balance(dns_rrl_t *rrl, const dns_rrl_entry_t *e, int age) {
	dns_rrl_rate_t *ratep;
	int balance, rate;

	if (e->key.s.rtype == DNS_RRL_RTYPE_TCP) {
		rate = 1;
	} else {
		ratep = get_rate(rrl, e->key.s.rtype);
		rate = ratep->scaled;
	}

	balance = e->responses + age * rate;
Evan Hunt's avatar
Evan Hunt committed
485 486 487 488 489 490 491 492 493 494
	if (balance > rate)
		balance = rate;
	return (balance);
}

/*
 * Search for an entry for a response and optionally create it.
 */
static dns_rrl_entry_t *
get_entry(dns_rrl_t *rrl, const isc_sockaddr_t *client_addr,
495 496
	  dns_rdataclass_t qclass, dns_rdatatype_t qtype,
	  const dns_name_t *qname, dns_rrl_rtype_t rtype, isc_stdtime_t now,
497
	  bool create, char *log_buf, unsigned int log_buf_len)
Evan Hunt's avatar
Evan Hunt committed
498 499
{
	dns_rrl_key_t key;
500
	uint32_t hval;
Evan Hunt's avatar
Evan Hunt committed
501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568
	dns_rrl_entry_t *e;
	dns_rrl_hash_t *hash;
	dns_rrl_bin_t *new_bin, *old_bin;
	int probes, age;

	make_key(rrl, &key, client_addr, qtype, qname, qclass, rtype);
	hval = hash_key(&key);

	/*
	 * Look for the entry in the current hash table.
	 */
	new_bin = get_bin(rrl->hash, hval);
	probes = 1;
	e = ISC_LIST_HEAD(*new_bin);
	while (e != NULL) {
		if (key_cmp(&e->key, &key)) {
			ref_entry(rrl, e, probes, now);
			return (e);
		}
		++probes;
		e = ISC_LIST_NEXT(e, hlink);
	}

	/*
	 * Look in the old hash table.
	 */
	if (rrl->old_hash != NULL) {
		old_bin = get_bin(rrl->old_hash, hval);
		e = ISC_LIST_HEAD(*old_bin);
		while (e != NULL) {
			if (key_cmp(&e->key, &key)) {
				ISC_LIST_UNLINK(*old_bin, e, hlink);
				ISC_LIST_PREPEND(*new_bin, e, hlink);
				e->hash_gen = rrl->hash_gen;
				ref_entry(rrl, e, probes, now);
				return (e);
			}
			e = ISC_LIST_NEXT(e, hlink);
		}

		/*
		 * Discard prevous hash table when all of its entries are old.
		 */
		age = delta_rrl_time(rrl->old_hash->check_time, now);
		if (age > rrl->window)
			free_old_hash(rrl);
	}

	if (!create)
		return (NULL);

	/*
	 * The entry does not exist, so create it by finding a free entry.
	 * Keep currently penalized and logged entries.
	 * Try to make more entries if none are idle.
	 * Steal the oldest entry if we cannot create more.
	 */
	for (e = ISC_LIST_TAIL(rrl->lru);
	     e != NULL;
	     e = ISC_LIST_PREV(e, lru))
	{
		if (!ISC_LINK_LINKED(e, hlink))
			break;
		age = get_age(rrl, e, now);
		if (age <= 1) {
			e = NULL;
			break;
		}
Evan Hunt's avatar
Evan Hunt committed
569
		if (!e->logged && response_balance(rrl, e, age) > 0)
Evan Hunt's avatar
Evan Hunt committed
570 571 572 573 574 575 576
			break;
	}
	if (e == NULL) {
		expand_entries(rrl, ISC_MIN((rrl->num_entries+1)/2, 1000));
		e = ISC_LIST_TAIL(rrl->lru);
	}
	if (e->logged)
577
		log_end(rrl, e, true, log_buf, log_buf_len);
Evan Hunt's avatar
Evan Hunt committed
578 579 580 581 582 583 584 585 586 587 588
	if (ISC_LINK_LINKED(e, hlink)) {
		if (e->hash_gen == rrl->hash_gen)
			hash = rrl->hash;
		else
			hash = rrl->old_hash;
		old_bin = get_bin(hash, hash_key(&e->key));
		ISC_LIST_UNLINK(*old_bin, e, hlink);
	}
	ISC_LIST_PREPEND(*new_bin, e, hlink);
	e->hash_gen = rrl->hash_gen;
	e->key = key;
589
	e->ts_valid = false;
Evan Hunt's avatar
Evan Hunt committed
590 591 592 593 594 595
	ref_entry(rrl, e, probes, now);
	return (e);
}

static void
debit_log(const dns_rrl_entry_t *e, int age, const char *action) {
596
	char buf[sizeof("age=2147483647")];
Evan Hunt's avatar
Evan Hunt committed
597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615
	const char *age_str;

	if (age == DNS_RRL_FOREVER) {
		age_str = "";
	} else {
		snprintf(buf, sizeof(buf), "age=%d", age);
		age_str = buf;
	}
	isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
		      DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DEBUG3,
		      "rrl %08x %6s  responses=%-3d %s",
		      hash_key(&e->key), age_str, e->responses, action);
}

static inline dns_rrl_result_t
debit_rrl_entry(dns_rrl_t *rrl, dns_rrl_entry_t *e, double qps, double scale,
		const isc_sockaddr_t *client_addr, isc_stdtime_t now,
		char *log_buf, unsigned int log_buf_len)
{
Evan Hunt's avatar
Evan Hunt committed
616 617
	int rate, new_rate, slip, new_slip, age, log_secs, min;
	dns_rrl_rate_t *ratep;
Evan Hunt's avatar
Evan Hunt committed
618 619 620 621 622 623
	dns_rrl_entry_t const *credit_e;

	/*
	 * Pick the rate counter.
	 * Optionally adjust the rate by the estimated query/second rate.
	 */
Evan Hunt's avatar
Evan Hunt committed
624 625
	ratep = get_rate(rrl, e->key.s.rtype);
	rate = ratep->r;
Evan Hunt's avatar
Evan Hunt committed
626 627 628 629 630 631 632 633 634
	if (rate == 0)
		return (DNS_RRL_RESULT_OK);

	if (scale < 1.0) {
		/*
		 * The limit for clients that have used TCP is not scaled.
		 */
		credit_e = get_entry(rrl, client_addr,
				     0, dns_rdatatype_none, NULL,
635
				     DNS_RRL_RTYPE_TCP, now, false,
Evan Hunt's avatar
Evan Hunt committed
636 637 638 639 640 641 642 643
				     log_buf, log_buf_len);
		if (credit_e != NULL) {
			age = get_age(rrl, e, now);
			if (age < rrl->window)
				scale = 1.0;
		}
	}
	if (scale < 1.0) {
644
		new_rate = (int) (rate * scale);
Evan Hunt's avatar
Evan Hunt committed
645 646
		if (new_rate < 1)
			new_rate = 1;
Evan Hunt's avatar
Evan Hunt committed
647 648 649 650 651 652 653 654
		if (ratep->scaled != new_rate) {
			isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
				      DNS_LOGMODULE_REQUEST,
				      DNS_RRL_LOG_DEBUG1,
				      "%d qps scaled %s by %.2f"
				      " from %d to %d",
				      (int)qps, ratep->str, scale,
				      rate, new_rate);
Evan Hunt's avatar
Evan Hunt committed
655
			rate = new_rate;
Evan Hunt's avatar
Evan Hunt committed
656
			ratep->scaled = rate;
Evan Hunt's avatar
Evan Hunt committed
657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714
		}
	}

	min = -rrl->window * rate;

	/*
	 * Treat time jumps into the recent past as no time.
	 * Treat entries older than the window as if they were just created
	 * Credit other entries.
	 */
	age = get_age(rrl, e, now);
	if (age > 0) {
		/*
		 * Credit tokens earned during elapsed time.
		 */
		if (age > rrl->window) {
			e->responses = rate;
			e->slip_cnt = 0;
		} else {
			e->responses += rate*age;
			if (e->responses > rate) {
				e->responses = rate;
				e->slip_cnt = 0;
			}
		}
		/*
		 * Find the seconds since last log message without overflowing
		 * small counter.  This counter is reset when an entry is
		 * created.  It is not necessarily reset when some requests
		 * are answered provided other requests continue to be dropped
		 * or slipped.  This can happen when the request rate is just
		 * at the limit.
		 */
		if (e->logged) {
			log_secs = e->log_secs;
			log_secs += age;
			if (log_secs > DNS_RRL_MAX_LOG_SECS || log_secs < 0)
				log_secs = DNS_RRL_MAX_LOG_SECS;
			e->log_secs = log_secs;
		}
	}
	set_age(rrl, e, now);

	/*
	 * Debit the entry for this response.
	 */
	if (--e->responses >= 0) {
		if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DEBUG3))
			debit_log(e, age, "");
		return (DNS_RRL_RESULT_OK);
	}

	if (e->responses < min)
		e->responses = min;

	/*
	 * Drop this response unless it should slip or leak.
	 */
Evan Hunt's avatar
Evan Hunt committed
715
	slip = rrl->slip.r;
Evan Hunt's avatar
Evan Hunt committed
716
	if (slip > 2 && scale < 1.0) {
717
		new_slip = (int) (slip * scale);
Evan Hunt's avatar
Evan Hunt committed
718 719
		if (new_slip < 2)
			new_slip = 2;
Evan Hunt's avatar
Evan Hunt committed
720 721 722 723 724 725 726 727
		if (rrl->slip.scaled != new_slip) {
			isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
				      DNS_LOGMODULE_REQUEST,
				      DNS_RRL_LOG_DEBUG1,
				      "%d qps scaled slip"
				      " by %.2f from %d to %d",
				      (int)qps, scale,
				      slip, new_slip);
Evan Hunt's avatar
Evan Hunt committed
728
			slip = new_slip;
Evan Hunt's avatar
Evan Hunt committed
729
			rrl->slip.scaled = slip;
Evan Hunt's avatar
Evan Hunt committed
730 731 732 733
		}
	}
	if (slip != 0 && e->key.s.rtype != DNS_RRL_RTYPE_ALL) {
		if (e->slip_cnt++ == 0) {
Evan Hunt's avatar
Evan Hunt committed
734 735
			if ((int) e->slip_cnt >= slip)
				e->slip_cnt = 0;
Evan Hunt's avatar
Evan Hunt committed
736 737 738
			if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DEBUG3))
				debit_log(e, age, "slip");
			return (DNS_RRL_RESULT_SLIP);
739
		} else if ((int) e->slip_cnt >= slip) {
Evan Hunt's avatar
Evan Hunt committed
740 741 742 743 744 745 746 747 748 749 750 751 752 753
			e->slip_cnt = 0;
		}
	}

	if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DEBUG3))
		debit_log(e, age, "drop");
	return (DNS_RRL_RESULT_DROP);
}

static inline dns_rrl_qname_buf_t *
get_qname(dns_rrl_t *rrl, const dns_rrl_entry_t *e) {
	dns_rrl_qname_buf_t *qbuf;

	qbuf = rrl->qnames[e->log_qname];
754
	if (qbuf == NULL || qbuf->e != e)
Evan Hunt's avatar
Evan Hunt committed
755 756 757 758 759 760 761 762 763 764 765
		return (NULL);
	return (qbuf);
}

static inline void
free_qname(dns_rrl_t *rrl, dns_rrl_entry_t *e) {
	dns_rrl_qname_buf_t *qbuf;

	qbuf = get_qname(rrl, e);
	if (qbuf != NULL) {
		qbuf->e = NULL;
766
		ISC_LIST_APPEND(rrl->qname_free, qbuf, link);
Evan Hunt's avatar
Evan Hunt committed
767 768 769 770 771 772 773 774 775
	}
}

static void
add_log_str(isc_buffer_t *lb, const char *str, unsigned int str_len) {
	isc_region_t region;

	isc_buffer_availableregion(lb, &region);
	if (str_len >= region.length) {
776
		if (region.length == 0U)
Evan Hunt's avatar
Evan Hunt committed
777 778 779
			return;
		str_len = region.length;
	}
780
	memmove(region.base, str, str_len);
Evan Hunt's avatar
Evan Hunt committed
781 782 783 784 785 786 787 788 789 790
	isc_buffer_add(lb, str_len);
}

#define ADD_LOG_CSTR(eb, s) add_log_str(eb, s, sizeof(s)-1)

/*
 * Build strings for the logs
 */
static void
make_log_buf(dns_rrl_t *rrl, dns_rrl_entry_t *e,
791 792
	     const char *str1, const char *str2, bool plural,
	     const dns_name_t *qname, bool save_qname,
Evan Hunt's avatar
Evan Hunt committed
793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831
	     dns_rrl_result_t rrl_result, isc_result_t resp_result,
	     char *log_buf, unsigned int log_buf_len)
{
	isc_buffer_t lb;
	dns_rrl_qname_buf_t *qbuf;
	isc_netaddr_t cidr;
	char strbuf[ISC_MAX(sizeof("/123"), sizeof("  (12345678)"))];
	const char *rstr;
	isc_result_t msg_result;

	if (log_buf_len <= 1) {
		if (log_buf_len == 1)
			log_buf[0] = '\0';
		return;
	}
	isc_buffer_init(&lb, log_buf, log_buf_len-1);

	if (str1 != NULL)
		add_log_str(&lb, str1, strlen(str1));
	if (str2 != NULL)
		add_log_str(&lb, str2, strlen(str2));

	switch (rrl_result) {
	case DNS_RRL_RESULT_OK:
		break;
	case DNS_RRL_RESULT_DROP:
		ADD_LOG_CSTR(&lb, "drop ");
		break;
	case DNS_RRL_RESULT_SLIP:
		ADD_LOG_CSTR(&lb, "slip ");
		break;
	default:
		INSIST(0);
		break;
	}

	switch (e->key.s.rtype) {
	case DNS_RRL_RTYPE_QUERY:
		break;
Evan Hunt's avatar
Evan Hunt committed
832 833 834 835 836
	case DNS_RRL_RTYPE_REFERRAL:
		ADD_LOG_CSTR(&lb, "referral ");
		break;
	case DNS_RRL_RTYPE_NODATA:
		ADD_LOG_CSTR(&lb, "NODATA ");
Evan Hunt's avatar
Evan Hunt committed
837 838
		break;
	case DNS_RRL_RTYPE_NXDOMAIN:
Evan Hunt's avatar
Evan Hunt committed
839
		ADD_LOG_CSTR(&lb, "NXDOMAIN ");
Evan Hunt's avatar
Evan Hunt committed
840 841 842
		break;
	case DNS_RRL_RTYPE_ERROR:
		if (resp_result == ISC_R_SUCCESS) {
Evan Hunt's avatar
Evan Hunt committed
843
			ADD_LOG_CSTR(&lb, "error ");
Evan Hunt's avatar
Evan Hunt committed
844 845
		} else {
			rstr = isc_result_totext(resp_result);
846
			add_log_str(&lb, rstr, strlen(rstr));
Evan Hunt's avatar
Evan Hunt committed
847
			ADD_LOG_CSTR(&lb, " error ");
Evan Hunt's avatar
Evan Hunt committed
848 849 850
		}
		break;
	case DNS_RRL_RTYPE_ALL:
Evan Hunt's avatar
Evan Hunt committed
851
		ADD_LOG_CSTR(&lb, "all ");
Evan Hunt's avatar
Evan Hunt committed
852 853 854 855 856 857
		break;
	default:
		INSIST(0);
	}

	if (plural)
Evan Hunt's avatar
Evan Hunt committed
858
		ADD_LOG_CSTR(&lb, "responses to ");
Evan Hunt's avatar
Evan Hunt committed
859
	else
Evan Hunt's avatar
Evan Hunt committed
860
		ADD_LOG_CSTR(&lb, "response to ");
Evan Hunt's avatar
Evan Hunt committed
861 862 863 864 865 866

	memset(&cidr, 0, sizeof(cidr));
	if (e->key.s.ipv6) {
		snprintf(strbuf, sizeof(strbuf), "/%d", rrl->ipv6_prefixlen);
		cidr.family = AF_INET6;
		memset(&cidr.type.in6, 0,  sizeof(cidr.type.in6));
867
		memmove(&cidr.type.in6, e->key.s.ip, sizeof(e->key.s.ip));
Evan Hunt's avatar
Evan Hunt committed
868 869 870 871 872 873 874 875 876 877 878
	} else {
		snprintf(strbuf, sizeof(strbuf), "/%d", rrl->ipv4_prefixlen);
		cidr.family = AF_INET;
		cidr.type.in.s_addr = e->key.s.ip[0];
	}
	msg_result = isc_netaddr_totext(&cidr, &lb);
	if (msg_result != ISC_R_SUCCESS)
		ADD_LOG_CSTR(&lb, "?");
	add_log_str(&lb, strbuf, strlen(strbuf));

	if (e->key.s.rtype == DNS_RRL_RTYPE_QUERY ||
Evan Hunt's avatar
Evan Hunt committed
879 880
	    e->key.s.rtype == DNS_RRL_RTYPE_REFERRAL ||
	    e->key.s.rtype == DNS_RRL_RTYPE_NODATA ||
Evan Hunt's avatar
Evan Hunt committed
881 882 883 884 885 886 887 888 889 890 891 892 893 894
	    e->key.s.rtype == DNS_RRL_RTYPE_NXDOMAIN) {
		qbuf = get_qname(rrl, e);
		if (save_qname && qbuf == NULL &&
		    qname != NULL && dns_name_isabsolute(qname)) {
			/*
			 * Capture the qname for the "stop limiting" message.
			 */
			qbuf = ISC_LIST_TAIL(rrl->qname_free);
			if (qbuf != NULL) {
				ISC_LIST_UNLINK(rrl->qname_free, qbuf, link);
			} else if (rrl->num_qnames < DNS_RRL_QNAMES) {
				qbuf = isc_mem_get(rrl->mctx, sizeof(*qbuf));
				if (qbuf != NULL) {
					memset(qbuf, 0, sizeof(*qbuf));
895
					ISC_LINK_INIT(qbuf, link);
Evan Hunt's avatar
Evan Hunt committed
896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920
					qbuf->index = rrl->num_qnames;
					rrl->qnames[rrl->num_qnames++] = qbuf;
				} else {
					isc_log_write(dns_lctx,
						      DNS_LOGCATEGORY_RRL,
						      DNS_LOGMODULE_REQUEST,
						      DNS_RRL_LOG_FAIL,
						      "isc_mem_get(%d)"
						      " failed for RRL qname",
						      (int)sizeof(*qbuf));
				}
			}
			if (qbuf != NULL) {
				e->log_qname = qbuf->index;
				qbuf->e = e;
				dns_fixedname_init(&qbuf->qname);
				dns_name_copy(qname,
					      dns_fixedname_name(&qbuf->qname),
					      NULL);
			}
		}
		if (qbuf != NULL)
			qname = dns_fixedname_name(&qbuf->qname);
		if (qname != NULL) {
			ADD_LOG_CSTR(&lb, " for ");
921
			(void)dns_name_totext(qname, true, &lb);
Evan Hunt's avatar
Evan Hunt committed
922 923 924 925 926
		} else {
			ADD_LOG_CSTR(&lb, " for (?)");
		}
		if (e->key.s.rtype != DNS_RRL_RTYPE_NXDOMAIN) {
			ADD_LOG_CSTR(&lb, " ");
Mark Andrews's avatar
Mark Andrews committed
927
			(void)dns_rdataclass_totext(e->key.s.qclass, &lb);
Evan Hunt's avatar
Evan Hunt committed
928 929 930 931
			if (e->key.s.rtype == DNS_RRL_RTYPE_QUERY) {
				ADD_LOG_CSTR(&lb, " ");
				(void)dns_rdatatype_totext(e->key.s.qtype, &lb);
			}
Evan Hunt's avatar
Evan Hunt committed
932 933 934 935 936 937 938 939 940 941 942 943 944
		}
		snprintf(strbuf, sizeof(strbuf), "  (%08x)",
			 e->key.s.qname_hash);
		add_log_str(&lb, strbuf, strlen(strbuf));
	}

	/*
	 * We saved room for '\0'.
	 */
	log_buf[isc_buffer_usedlength(&lb)] = '\0';
}

static void
945
log_end(dns_rrl_t *rrl, dns_rrl_entry_t *e, bool early,
Evan Hunt's avatar
Evan Hunt committed
946 947 948 949 950 951 952
	char *log_buf, unsigned int log_buf_len)
{
	if (e->logged) {
		make_log_buf(rrl, e,
			     early ? "*" : NULL,
			     rrl->log_only ? "would stop limiting "
					   : "stop limiting ",
953
			     true, NULL, false,
Evan Hunt's avatar
Evan Hunt committed
954 955 956 957 958 959
			     DNS_RRL_RESULT_OK, ISC_R_SUCCESS,
			     log_buf, log_buf_len);
		isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
			      DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DROP,
			      "%s", log_buf);
		free_qname(rrl, e);
960
		e->logged = false;
Evan Hunt's avatar
Evan Hunt committed
961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008
		--rrl->num_logged;
	}
}

/*
 * Log messages for streams that have stopped being rate limited.
 */
static void
log_stops(dns_rrl_t *rrl, isc_stdtime_t now, int limit,
	  char *log_buf, unsigned int log_buf_len)
{
	dns_rrl_entry_t *e;
	int age;

	for (e = rrl->last_logged; e != NULL; e = ISC_LIST_PREV(e, lru)) {
		if (!e->logged)
			continue;
		if (now != 0) {
			age = get_age(rrl, e, now);
			if (age < DNS_RRL_STOP_LOG_SECS ||
			    response_balance(rrl, e, age) < 0)
				break;
		}

		log_end(rrl, e, now == 0, log_buf, log_buf_len);
		if (rrl->num_logged <= 0)
			break;

		/*
		 * Too many messages could stall real work.
		 */
		if (--limit < 0) {
			rrl->last_logged = ISC_LIST_PREV(e, lru);
			return;
		}
	}
	if (e == NULL) {
		INSIST(rrl->num_logged == 0);
		rrl->log_stops_time = now;
	}
	rrl->last_logged = e;
}

/*
 * Main rate limit interface.
 */
dns_rrl_result_t
dns_rrl(dns_view_t *view,
1009
	const isc_sockaddr_t *client_addr, bool is_tcp,
Evan Hunt's avatar
Evan Hunt committed
1010
	dns_rdataclass_t qclass, dns_rdatatype_t qtype,
1011
	const dns_name_t *qname, isc_result_t resp_result, isc_stdtime_t now,
1012
	bool wouldlog, char *log_buf, unsigned int log_buf_len)
Evan Hunt's avatar
Evan Hunt committed
1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028
{
	dns_rrl_t *rrl;
	dns_rrl_rtype_t rtype;
	dns_rrl_entry_t *e;
	isc_netaddr_t netclient;
	int secs;
	double qps, scale;
	int exempt_match;
	isc_result_t result;
	dns_rrl_result_t rrl_result;

	INSIST(log_buf != NULL && log_buf_len > 0);

	rrl = view->rrl;
	if (rrl->exempt != NULL) {
		isc_netaddr_fromsockaddr(&netclient, client_addr);
1029 1030
		result = dns_acl_match(&netclient, NULL, rrl->exempt,
				       &view->aclenv, &exempt_match, NULL);
Evan Hunt's avatar
Evan Hunt committed
1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084
		if (result == ISC_R_SUCCESS && exempt_match > 0)
			return (DNS_RRL_RESULT_OK);
	}

	LOCK(&rrl->lock);

	/*
	 * Estimate total query per second rate when scaling by qps.
	 */
	if (rrl->qps_scale == 0) {
		qps = 0.0;
		scale = 1.0;
	} else {
		++rrl->qps_responses;
		secs = delta_rrl_time(rrl->qps_time, now);
		if (secs <= 0) {
			qps = rrl->qps;
		} else {
			qps = (1.0*rrl->qps_responses) / secs;
			if (secs >= rrl->window) {
				if (isc_log_wouldlog(dns_lctx,
						     DNS_RRL_LOG_DEBUG3))
					isc_log_write(dns_lctx,
						      DNS_LOGCATEGORY_RRL,
						      DNS_LOGMODULE_REQUEST,
						      DNS_RRL_LOG_DEBUG3,
						      "%d responses/%d seconds"
						      " = %d qps",
						      rrl->qps_responses, secs,
						      (int)qps);
				rrl->qps = qps;
				rrl->qps_responses = 0;
				rrl->qps_time = now;
			} else if (qps < rrl->qps) {
				qps = rrl->qps;
			}
		}
		scale = rrl->qps_scale / qps;
	}

	/*
	 * Do maintenance once per second.
	 */
	if (rrl->num_logged > 0 && rrl->log_stops_time != now)
		log_stops(rrl, now, 8, log_buf, log_buf_len);

	/*
	 * Notice TCP responses when scaling limits by qps.
	 * Do not try to rate limit TCP responses.
	 */
	if (is_tcp) {
		if (scale < 1.0) {
			e = get_entry(rrl, client_addr,
				      0, dns_rdatatype_none, NULL,
1085
				      DNS_RRL_RTYPE_TCP, now, true,
Evan Hunt's avatar
Evan Hunt committed
1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099
				      log_buf, log_buf_len);
			if (e != NULL) {
				e->responses = -(rrl->window+1);
				set_age(rrl, e, now);
			}
		}
		UNLOCK(&rrl->lock);
		return (ISC_R_SUCCESS);
	}

	/*
	 * Find the right kind of entry, creating it if necessary.
	 * If that is impossible, then nothing more can be done
	 */
Evan Hunt's avatar
Evan Hunt committed
1100 1101
	switch (resp_result) {
	case ISC_R_SUCCESS:
Evan Hunt's avatar
Evan Hunt committed
1102
		rtype = DNS_RRL_RTYPE_QUERY;
Evan Hunt's avatar
Evan Hunt committed
1103 1104 1105 1106 1107 1108 1109 1110
		break;
	case DNS_R_DELEGATION:
		rtype = DNS_RRL_RTYPE_REFERRAL;
		break;
	case DNS_R_NXRRSET:
		rtype = DNS_RRL_RTYPE_NODATA;
		break;
	case DNS_R_NXDOMAIN:
Evan Hunt's avatar
Evan Hunt committed
1111
		rtype = DNS_RRL_RTYPE_NXDOMAIN;
Evan Hunt's avatar
Evan Hunt committed
1112 1113
		break;
	default:
Evan Hunt's avatar
Evan Hunt committed
1114
		rtype = DNS_RRL_RTYPE_ERROR;
Evan Hunt's avatar
Evan Hunt committed
1115 1116
		break;
	}
Evan Hunt's avatar
Evan Hunt committed
1117
	e = get_entry(rrl, client_addr, qclass, qtype, qname, rtype,
1118
		      now, true, log_buf, log_buf_len);
Evan Hunt's avatar
Evan Hunt committed
1119 1120 1121 1122 1123 1124 1125 1126 1127 1128
	if (e == NULL) {
		UNLOCK(&rrl->lock);
		return (DNS_RRL_RESULT_OK);
	}

	if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DEBUG1)) {
		/*
		 * Do not worry about speed or releasing the lock.
		 * This message appears before messages from debit_rrl_entry().
		 */
1129 1130
		make_log_buf(rrl, e, "consider limiting ", NULL, false,
			     qname, false, DNS_RRL_RESULT_OK, resp_result,
Evan Hunt's avatar
Evan Hunt committed
1131 1132 1133 1134 1135 1136 1137 1138 1139
			     log_buf, log_buf_len);
		isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
			      DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DEBUG1,
			      "%s", log_buf);
	}

	rrl_result = debit_rrl_entry(rrl, e, qps, scale, client_addr, now,
				     log_buf, log_buf_len);

Evan Hunt's avatar
Evan Hunt committed
1140
	if (rrl->all_per_second.r != 0) {
Evan Hunt's avatar
Evan Hunt committed
1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153
		/*
		 * We must debit the all-per-second token bucket if we have
		 * an all-per-second limit for the IP address.
		 * The all-per-second limit determines the log message
		 * when both limits are hit.
		 * The response limiting must continue if the
		 * all-per-second limiting lapses.
		 */
		dns_rrl_entry_t *e_all;
		dns_rrl_result_t rrl_all_result;

		e_all = get_entry(rrl, client_addr,
				  0, dns_rdatatype_none, NULL,
1154
				  DNS_RRL_RTYPE_ALL, now, true,
Evan Hunt's avatar
Evan Hunt committed
1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165
				  log_buf, log_buf_len);
		if (e_all == NULL) {
			UNLOCK(&rrl->lock);
			return (DNS_RRL_RESULT_OK);
		}
		rrl_all_result = debit_rrl_entry(rrl, e_all, qps, scale,
						 client_addr, now,
						 log_buf, log_buf_len);
		if (rrl_all_result != DNS_RRL_RESULT_OK) {
			e = e_all;
			rrl_result = rrl_all_result;
1166
			if (isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DEBUG1)) {
Evan Hunt's avatar
Evan Hunt committed
1167 1168
				make_log_buf(rrl, e,
					     "prefer all-per-second limiting ",
1169
					     NULL, true, qname, false,
Evan Hunt's avatar
Evan Hunt committed
1170 1171 1172
					     DNS_RRL_RESULT_OK, resp_result,
					     log_buf, log_buf_len);
				isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
1173 1174
					      DNS_LOGMODULE_REQUEST,
					      DNS_RRL_LOG_DEBUG1,
Evan Hunt's avatar
Evan Hunt committed
1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191
					      "%s", log_buf);
			}
		}
	}

	if (rrl_result == DNS_RRL_RESULT_OK) {
		UNLOCK(&rrl->lock);
		return (DNS_RRL_RESULT_OK);
	}

	/*
	 * Log occassionally in the rate-limit category.
	 */
	if ((!e->logged || e->log_secs >= DNS_RRL_MAX_LOG_SECS) &&
	    isc_log_wouldlog(dns_lctx, DNS_RRL_LOG_DROP)) {
		make_log_buf(rrl, e, rrl->log_only ? "would " : NULL,
			     e->logged ? "continue limiting " : "limit ",
1192
			     true, qname, true,
Evan Hunt's avatar
Evan Hunt committed
1193 1194 1195
			     DNS_RRL_RESULT_OK, resp_result,
			     log_buf, log_buf_len);
		if (!e->logged) {
1196
			e->logged = true;
Evan Hunt's avatar
Evan Hunt committed
1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217
			if (++rrl->num_logged <= 1)
				rrl->last_logged = e;
		}
		e->log_secs = 0;

		/*
		 * Avoid holding the lock.
		 */
		if (!wouldlog) {
			UNLOCK(&rrl->lock);
			e = NULL;
		}
		isc_log_write(dns_lctx, DNS_LOGCATEGORY_RRL,
			      DNS_LOGMODULE_REQUEST, DNS_RRL_LOG_DROP,
			      "%s", log_buf);
	}

	/*
	 * Make a log message for the caller.
	 */
	if (wouldlog)
1218 1219
		make_log_buf(rrl, e,
			     rrl->log_only ? "would rate limit " : "rate limit ",
1220
			     NULL, false, qname, false,
Evan Hunt's avatar
Evan Hunt committed
1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253
			     rrl_result, resp_result, log_buf, log_buf_len);

	if (e != NULL) {
		/*
		 * Do not save the qname unless we might need it for
		 * the ending log message.
		 */
		if (!e->logged)
			free_qname(rrl, e);
		UNLOCK(&rrl->lock);
	}

	return (rrl_result);
}

void
dns_rrl_view_destroy(dns_view_t *view) {
	dns_rrl_t *rrl;
	dns_rrl_block_t *b;
	dns_rrl_hash_t *h;
	char log_buf[DNS_RRL_LOG_BUF_LEN];
	int i;

	rrl = view->rrl;
	if (rrl == NULL)
		return;
	view->rrl = NULL;

	/*
	 * Assume the caller takes care of locking the view and anything else.
	 */

	if (rrl->num_logged > 0)
1254
		log_stops(rrl, 0, INT32_MAX, log_buf, sizeof(log_buf));
Evan Hunt's avatar
Evan Hunt committed
1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320

	for (i = 0; i < DNS_RRL_QNAMES; ++i) {
		if (rrl->qnames[i] == NULL)
			break;
		isc_mem_put(rrl->mctx, rrl->qnames[i], sizeof(*rrl->qnames[i]));
	}

	if (rrl->exempt != NULL)
		dns_acl_detach(&rrl->exempt);

	DESTROYLOCK(&rrl->lock);

	while (!ISC_LIST_EMPTY(rrl->blocks)) {
		b = ISC_LIST_HEAD(rrl->blocks);
		ISC_LIST_UNLINK(rrl->blocks, b, link);
		isc_mem_put(rrl->mctx, b, b->size);
	}

	h = rrl->hash;
	if (h != NULL)
		isc_mem_put(rrl->mctx, h,
			    sizeof(*h) + (h->length - 1) * sizeof(h->bins[0]));

	h = rrl->old_hash;
	if (h != NULL)
		isc_mem_put(rrl->mctx, h,
			    sizeof(*h) + (h->length - 1) * sizeof(h->bins[0]));

	isc_mem_putanddetach(&rrl->mctx, rrl, sizeof(*rrl));
}

isc_result_t
dns_rrl_init(dns_rrl_t **rrlp, dns_view_t *view, int min_entries) {
	dns_rrl_t *rrl;
	isc_result_t result;

	*rrlp = NULL;

	rrl = isc_mem_get(view->mctx, sizeof(*rrl));
	if (rrl == NULL)
		return (ISC_R_NOMEMORY);
	memset(rrl, 0, sizeof(*rrl));
	isc_mem_attach(view->mctx, &rrl->mctx);
	result = isc_mutex_init(&rrl->lock);
	if (result != ISC_R_SUCCESS) {
		isc_mem_putanddetach(&rrl->mctx, rrl, sizeof(*rrl));
		return (result);
	}
	isc_stdtime_get(&rrl->ts_bases[0]);

	view->rrl = rrl;

	result = expand_entries(rrl, min_entries);
	if (result != ISC_R_SUCCESS) {
		dns_rrl_view_destroy(view);
		return (result);
	}
	result = expand_rrl_hash(rrl, 0);
	if (result != ISC_R_SUCCESS) {
		dns_rrl_view_destroy(view);
		return (result);
	}

	*rrlp = rrl;
	return (ISC_R_SUCCESS);
}