rrl.h revision 262445 
1/*
2 * Copyright (C) 2013  Internet Systems Consortium, Inc. ("ISC")
3 *
4 * Permission to use, copy, modify, and/or distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
7 *
8 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
9 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
10 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
11 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
12 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
13 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
14 * PERFORMANCE OF THIS SOFTWARE.
15 */
16
17
18#ifndef DNS_RRL_H
19#define DNS_RRL_H 1
20
21/*
22 * Rate limit DNS responses.
23 */
24
25#include <isc/lang.h>
26
27#include <dns/fixedname.h>
28#include <dns/rdata.h>
29#include <dns/types.h>
30
31ISC_LANG_BEGINDECLS
32
33
34/*
35 * Memory allocation or other failures.
36 */
37#define DNS_RRL_LOG_FAIL	ISC_LOG_WARNING
38/*
39 * dropped or slipped responses.
40 */
41#define DNS_RRL_LOG_DROP	ISC_LOG_INFO
42/*
43 * Major events in dropping or slipping.
44 */
45#define DNS_RRL_LOG_DEBUG1	ISC_LOG_DEBUG(3)
46/*
47 * Limit computations.
48 */
49#define DNS_RRL_LOG_DEBUG2	ISC_LOG_DEBUG(4)
50/*
51 * Even less interesting.
52 */
53#define DNS_RRL_LOG_DEBUG3	ISC_LOG_DEBUG(9)
54
55
56#define DNS_RRL_LOG_ERR_LEN	64
57#define DNS_RRL_LOG_BUF_LEN	(sizeof("would continue limiting") +	\
58				 DNS_RRL_LOG_ERR_LEN +			\
59				 sizeof(" responses to ") +		\
60				 ISC_NETADDR_FORMATSIZE +		\
61				 sizeof("/128 for IN ") +		\
62				 DNS_RDATATYPE_FORMATSIZE +		\
63				 DNS_NAME_FORMATSIZE)
64
65
66typedef struct dns_rrl_hash dns_rrl_hash_t;
67
68/*
69 * Response types.
70 */
71typedef enum {
72	DNS_RRL_RTYPE_FREE = 0,
73	DNS_RRL_RTYPE_QUERY,
74	DNS_RRL_RTYPE_REFERRAL,
75	DNS_RRL_RTYPE_NODATA,
76	DNS_RRL_RTYPE_NXDOMAIN,
77	DNS_RRL_RTYPE_ERROR,
78	DNS_RRL_RTYPE_ALL,
79	DNS_RRL_RTYPE_TCP,
80} dns_rrl_rtype_t;
81
82/*
83 * A rate limit bucket key.
84 * This should be small to limit the total size of the database.
85 * The hash of the qname should be wide enough to make the probability
86 * of collisions among requests from a single IP address block less than 50%.
87 * We need a 32-bit hash value for 10000 qps (e.g. random qnames forged
88 * by attacker) to collide with legitimate qnames from the target with
89 * probability at most 1%.
90 */
91#define DNS_RRL_MAX_PREFIX  64
92typedef union dns_rrl_key dns_rrl_key_t;
93union dns_rrl_key {
94	struct {
95		isc_uint32_t	    ip[DNS_RRL_MAX_PREFIX/32];
96		isc_uint32_t	    qname_hash;
97		dns_rdatatype_t	    qtype;
98		isc_uint8_t         qclass;
99		dns_rrl_rtype_t	    rtype   :4; /* 3 bits + sign bit */
100		isc_boolean_t	    ipv6    :1;
101	} s;
102	isc_uint16_t	w[1];
103};
104
105/*
106 * A rate-limit entry.
107 * This should be small to limit the total size of the table of entries.
108 */
109typedef struct dns_rrl_entry dns_rrl_entry_t;
110typedef ISC_LIST(dns_rrl_entry_t) dns_rrl_bin_t;
111struct dns_rrl_entry {
112	ISC_LINK(dns_rrl_entry_t) lru;
113	ISC_LINK(dns_rrl_entry_t) hlink;
114	dns_rrl_key_t	key;
115# define DNS_RRL_RESPONSE_BITS	24
116	signed int	responses   :DNS_RRL_RESPONSE_BITS;
117# define DNS_RRL_QNAMES_BITS	8
118	unsigned int	log_qname   :DNS_RRL_QNAMES_BITS;
119
120# define DNS_RRL_TS_GEN_BITS	2
121	unsigned int	ts_gen	    :DNS_RRL_TS_GEN_BITS;
122	isc_boolean_t	ts_valid    :1;
123# define DNS_RRL_HASH_GEN_BITS	1
124	unsigned int	hash_gen    :DNS_RRL_HASH_GEN_BITS;
125	isc_boolean_t	logged	    :1;
126# define DNS_RRL_LOG_BITS	11
127	unsigned int	log_secs    :DNS_RRL_LOG_BITS;
128
129# define DNS_RRL_TS_BITS	12
130	unsigned int	ts	    :DNS_RRL_TS_BITS;
131
132# define DNS_RRL_MAX_SLIP	10
133	unsigned int	slip_cnt    :4;
134};
135
136#define DNS_RRL_MAX_TIME_TRAVEL	5
137#define DNS_RRL_FOREVER		(1<<DNS_RRL_TS_BITS)
138#define DNS_RRL_MAX_TS		(DNS_RRL_FOREVER - 1)
139
140#define DNS_RRL_MAX_RESPONSES	((1<<(DNS_RRL_RESPONSE_BITS-1))-1)
141#define DNS_RRL_MAX_WINDOW	3600
142#if DNS_RRL_MAX_WINDOW >= DNS_RRL_MAX_TS
143#error "DNS_RRL_MAX_WINDOW is too large"
144#endif
145#define DNS_RRL_MAX_RATE	1000
146#if DNS_RRL_MAX_RATE >= (DNS_RRL_MAX_RESPONSES / DNS_RRL_MAX_WINDOW)
147#error "DNS_RRL_MAX_rate is too large"
148#endif
149
150#if (1<<DNS_RRL_LOG_BITS) >= DNS_RRL_FOREVER
151#error DNS_RRL_LOG_BITS is too big
152#endif
153#define DNS_RRL_MAX_LOG_SECS	1800
154#if DNS_RRL_MAX_LOG_SECS >= (1<<DNS_RRL_LOG_BITS)
155#error "DNS_RRL_MAX_LOG_SECS is too large"
156#endif
157#define DNS_RRL_STOP_LOG_SECS	60
158#if DNS_RRL_STOP_LOG_SECS >= (1<<DNS_RRL_LOG_BITS)
159#error "DNS_RRL_STOP_LOG_SECS is too large"
160#endif
161
162
163/*
164 * A hash table of rate-limit entries.
165 */
166struct dns_rrl_hash {
167	isc_stdtime_t	check_time;
168	unsigned int	gen	    :DNS_RRL_HASH_GEN_BITS;
169	int		length;
170	dns_rrl_bin_t	bins[1];
171};
172
173/*
174 * A block of rate-limit entries.
175 */
176typedef struct dns_rrl_block dns_rrl_block_t;
177struct dns_rrl_block {
178	ISC_LINK(dns_rrl_block_t) link;
179	int		size;
180	dns_rrl_entry_t	entries[1];
181};
182
183/*
184 * A rate limited qname buffer.
185 */
186typedef struct dns_rrl_qname_buf dns_rrl_qname_buf_t;
187struct dns_rrl_qname_buf {
188	ISC_LINK(dns_rrl_qname_buf_t) link;
189	const dns_rrl_entry_t *e;
190	unsigned int	    index;
191	dns_fixedname_t	    qname;
192};
193
194typedef struct dns_rrl_rate dns_rrl_rate_t;
195struct dns_rrl_rate {
196	int	    r;
197	int	    scaled;
198	const char  *str;
199};
200
201/*
202 * Per-view query rate limit parameters and a pointer to database.
203 */
204typedef struct dns_rrl dns_rrl_t;
205struct dns_rrl {
206	isc_mutex_t	lock;
207	isc_mem_t	*mctx;
208
209	isc_boolean_t	log_only;
210	dns_rrl_rate_t	responses_per_second;
211	dns_rrl_rate_t	referrals_per_second;
212	dns_rrl_rate_t	nodata_per_second;
213	dns_rrl_rate_t	nxdomains_per_second;
214	dns_rrl_rate_t	errors_per_second;
215	dns_rrl_rate_t	all_per_second;
216	dns_rrl_rate_t	slip;
217	int		window;
218	double		qps_scale;
219	int		max_entries;
220
221	dns_acl_t	*exempt;
222
223	int		num_entries;
224
225	int		qps_responses;
226	isc_stdtime_t	qps_time;
227	double		qps;
228
229	unsigned int	probes;
230	unsigned int	searches;
231
232	ISC_LIST(dns_rrl_block_t) blocks;
233	ISC_LIST(dns_rrl_entry_t) lru;
234
235	dns_rrl_hash_t	*hash;
236	dns_rrl_hash_t	*old_hash;
237	unsigned int	hash_gen;
238
239	unsigned int	ts_gen;
240# define DNS_RRL_TS_BASES   (1<<DNS_RRL_TS_GEN_BITS)
241	isc_stdtime_t	ts_bases[DNS_RRL_TS_BASES];
242
243	int		ipv4_prefixlen;
244	isc_uint32_t	ipv4_mask;
245	int		ipv6_prefixlen;
246	isc_uint32_t	ipv6_mask[4];
247
248	isc_stdtime_t	log_stops_time;
249	dns_rrl_entry_t	*last_logged;
250	int		num_logged;
251	int		num_qnames;
252	ISC_LIST(dns_rrl_qname_buf_t) qname_free;
253# define DNS_RRL_QNAMES	    (1<<DNS_RRL_QNAMES_BITS)
254	dns_rrl_qname_buf_t *qnames[DNS_RRL_QNAMES];
255};
256
257typedef enum {
258	DNS_RRL_RESULT_OK,
259	DNS_RRL_RESULT_DROP,
260	DNS_RRL_RESULT_SLIP,
261} dns_rrl_result_t;
262
263dns_rrl_result_t
264dns_rrl(dns_view_t *view,
265	const isc_sockaddr_t *client_addr, isc_boolean_t is_tcp,
266	dns_rdataclass_t rdclass, dns_rdatatype_t qtype,
267	dns_name_t *qname, isc_result_t resp_result, isc_stdtime_t now,
268	isc_boolean_t wouldlog, char *log_buf, unsigned int log_buf_len);
269
270void
271dns_rrl_view_destroy(dns_view_t *view);
272
273isc_result_t
274dns_rrl_init(dns_rrl_t **rrlp, dns_view_t *view, int min_entries);
275
276ISC_LANG_ENDDECLS
277
278#endif /* DNS_RRL_H */
279