contrib/bind9/lib/dns/include/dns/rrl.h

   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
  31 ISC_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
  66 typedef struct dns_rrl_hash dns_rrl_hash_t;
  67
  68 /*
  69  * Response types.
  70  */
  71 typedef 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
  92 typedef union dns_rrl_key dns_rrl_key_t;
  93 union 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  */
 109 typedef struct dns_rrl_entry dns_rrl_entry_t;
 110 typedef ISC_LIST(dns_rrl_entry_t) dns_rrl_bin_t;
 111 struct 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  */
 166 struct 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  */
 176 typedef struct dns_rrl_block dns_rrl_block_t;
 177 struct 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  */
 186 typedef struct dns_rrl_qname_buf dns_rrl_qname_buf_t;
 187 struct 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
 194 typedef struct dns_rrl_rate dns_rrl_rate_t;
 195 struct 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  */
 204 typedef struct dns_rrl dns_rrl_t;
 205 struct 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
 257 typedef enum {
 258         DNS_RRL_RESULT_OK,
 259         DNS_RRL_RESULT_DROP,
 260         DNS_RRL_RESULT_SLIP,
 261 } dns_rrl_result_t;
 262
 263 dns_rrl_result_t
 264 dns_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
 270 void
 271 dns_rrl_view_destroy(dns_view_t *view);
 272
 273 isc_result_t
 274 dns_rrl_init(dns_rrl_t **rrlp, dns_view_t *view, int min_entries);
 275
 276 ISC_LANG_ENDDECLS
 277
 278 #endif /* DNS_RRL_H */