1 /* 2 * services/cache/infra.h - infrastructure cache, server rtt and capabilities 3 * 4 * Copyright (c) 2007, NLnet Labs. All rights reserved. 5 * 6 * This software is open source. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * Redistributions of source code must retain the above copyright notice, 13 * this list of conditions and the following disclaimer. 14 * 15 * Redistributions in binary form must reproduce the above copyright notice, 16 * this list of conditions and the following disclaimer in the documentation 17 * and/or other materials provided with the distribution. 18 * 19 * Neither the name of the NLNET LABS nor the names of its contributors may 20 * be used to endorse or promote products derived from this software without 21 * specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34 */ 35 36 /** 37 * \file 38 * 39 * This file contains the infrastructure cache, as well as rate limiting. 40 * Note that there are two sorts of rate-limiting here: 41 * - Pre-cache, per-query rate limiting (query ratelimits) 42 * - Post-cache, per-domain name rate limiting (infra-ratelimits) 43 */ 44 45 #ifndef SERVICES_CACHE_INFRA_H 46 #define SERVICES_CACHE_INFRA_H 47 #include "util/storage/lruhash.h" 48 #include "util/storage/dnstree.h" 49 #include "util/rtt.h" 50 #include "util/netevent.h" 51 #include "util/data/msgreply.h" 52 struct slabhash; 53 struct config_file; 54 55 /** 56 * Host information kept for every server, per zone. 57 */ 58 struct infra_key { 59 /** the host address. */ 60 struct sockaddr_storage addr; 61 /** length of addr. */ 62 socklen_t addrlen; 63 /** zone name in wireformat */ 64 uint8_t* zonename; 65 /** length of zonename */ 66 size_t namelen; 67 /** hash table entry, data of type infra_data. */ 68 struct lruhash_entry entry; 69 }; 70 71 /** 72 * Host information encompasses host capabilities and retransmission timeouts. 73 * And lameness information (notAuthoritative, noEDNS, Recursive) 74 */ 75 struct infra_data { 76 /** TTL value for this entry. absolute time. */ 77 time_t ttl; 78 79 /** time in seconds (absolute) when probing re-commences, 0 disabled */ 80 time_t probedelay; 81 /** round trip times for timeout calculation */ 82 struct rtt_info rtt; 83 84 /** edns version that the host supports, -1 means no EDNS */ 85 int edns_version; 86 /** if the EDNS lameness is already known or not. 87 * EDNS lame is when EDNS queries or replies are dropped, 88 * and cause a timeout */ 89 uint8_t edns_lame_known; 90 91 /** is the host lame (does not serve the zone authoritatively), 92 * or is the host dnssec lame (does not serve DNSSEC data) */ 93 uint8_t isdnsseclame; 94 /** is the host recursion lame (not AA, but RA) */ 95 uint8_t rec_lame; 96 /** the host is lame (not authoritative) for A records */ 97 uint8_t lame_type_A; 98 /** the host is lame (not authoritative) for other query types */ 99 uint8_t lame_other; 100 101 /** timeouts counter for type A */ 102 uint8_t timeout_A; 103 /** timeouts counter for type AAAA */ 104 uint8_t timeout_AAAA; 105 /** timeouts counter for others */ 106 uint8_t timeout_other; 107 }; 108 109 /** 110 * Infra cache 111 */ 112 struct infra_cache { 113 /** The hash table with hosts */ 114 struct slabhash* hosts; 115 /** TTL value for host information, in seconds */ 116 int host_ttl; 117 /** the hosts that are down are kept probed for recovery */ 118 int infra_keep_probing; 119 /** hash table with query rates per name: rate_key, rate_data */ 120 struct slabhash* domain_rates; 121 /** ratelimit settings for domains, struct domain_limit_data */ 122 rbtree_type domain_limits; 123 /** hash table with query rates per client ip: ip_rate_key, ip_rate_data */ 124 struct slabhash* client_ip_rates; 125 }; 126 127 /** ratelimit, unless overridden by domain_limits, 0 is off */ 128 extern int infra_dp_ratelimit; 129 130 /** 131 * ratelimit settings for domains 132 */ 133 struct domain_limit_data { 134 /** key for rbtree, must be first in struct, name of domain */ 135 struct name_tree_node node; 136 /** ratelimit for exact match with this name, -1 if not set */ 137 int lim; 138 /** ratelimit for names below this name, -1 if not set */ 139 int below; 140 }; 141 142 /** 143 * key for ratelimit lookups, a domain name 144 */ 145 struct rate_key { 146 /** lruhash key entry */ 147 struct lruhash_entry entry; 148 /** domain name in uncompressed wireformat */ 149 uint8_t* name; 150 /** length of name */ 151 size_t namelen; 152 }; 153 154 /** ip ratelimit, 0 is off */ 155 extern int infra_ip_ratelimit; 156 157 /** 158 * key for ip_ratelimit lookups, a source IP. 159 */ 160 struct ip_rate_key { 161 /** lruhash key entry */ 162 struct lruhash_entry entry; 163 /** client ip information */ 164 struct sockaddr_storage addr; 165 /** length of address */ 166 socklen_t addrlen; 167 }; 168 169 /** number of seconds to track qps rate */ 170 #define RATE_WINDOW 2 171 172 /** 173 * Data for ratelimits per domain name 174 * It is incremented when a non-cache-lookup happens for that domain name. 175 * The name is the delegation point we have for the name. 176 * If a new delegation point is found (a referral reply), the previous 177 * delegation point is decremented, and the new one is charged with the query. 178 */ 179 struct rate_data { 180 /** queries counted, for that second. 0 if not in use. */ 181 int qps[RATE_WINDOW]; 182 /** what the timestamp is of the qps array members, counter is 183 * valid for that timestamp. Usually now and now-1. */ 184 time_t timestamp[RATE_WINDOW]; 185 }; 186 187 #define ip_rate_data rate_data 188 189 /** infra host cache default hash lookup size */ 190 #define INFRA_HOST_STARTSIZE 32 191 /** bytes per zonename reserved in the hostcache, dnamelen(zonename.com.) */ 192 #define INFRA_BYTES_NAME 14 193 194 /** 195 * Create infra cache. 196 * @param cfg: config parameters or NULL for defaults. 197 * @return: new infra cache, or NULL. 198 */ 199 struct infra_cache* infra_create(struct config_file* cfg); 200 201 /** 202 * Delete infra cache. 203 * @param infra: infrastructure cache to delete. 204 */ 205 void infra_delete(struct infra_cache* infra); 206 207 /** 208 * Adjust infra cache to use updated configuration settings. 209 * This may clean the cache. Operates a bit like realloc. 210 * There may be no threading or use by other threads. 211 * @param infra: existing cache. If NULL a new infra cache is returned. 212 * @param cfg: config options. 213 * @return the new infra cache pointer or NULL on error. 214 */ 215 struct infra_cache* infra_adjust(struct infra_cache* infra, 216 struct config_file* cfg); 217 218 /** 219 * Plain find infra data function (used by the the other functions) 220 * @param infra: infrastructure cache. 221 * @param addr: host address. 222 * @param addrlen: length of addr. 223 * @param name: domain name of zone. 224 * @param namelen: length of domain name. 225 * @param wr: if true, writelock, else readlock. 226 * @return the entry, could be expired (this is not checked) or NULL. 227 */ 228 struct lruhash_entry* infra_lookup_nottl(struct infra_cache* infra, 229 struct sockaddr_storage* addr, socklen_t addrlen, uint8_t* name, 230 size_t namelen, int wr); 231 232 /** 233 * Find host information to send a packet. Creates new entry if not found. 234 * Lameness is empty. EDNS is 0 (try with first), and rtt is returned for 235 * the first message to it. 236 * Use this to send a packet only, because it also locks out others when 237 * probing is restricted. 238 * @param infra: infrastructure cache. 239 * @param addr: host address. 240 * @param addrlen: length of addr. 241 * @param name: domain name of zone. 242 * @param namelen: length of domain name. 243 * @param timenow: what time it is now. 244 * @param edns_vs: edns version it supports, is returned. 245 * @param edns_lame_known: if EDNS lame (EDNS is dropped in transit) has 246 * already been probed, is returned. 247 * @param to: timeout to use, is returned. 248 * @return: 0 on error. 249 */ 250 int infra_host(struct infra_cache* infra, struct sockaddr_storage* addr, 251 socklen_t addrlen, uint8_t* name, size_t namelen, 252 time_t timenow, int* edns_vs, uint8_t* edns_lame_known, int* to); 253 254 /** 255 * Set a host to be lame for the given zone. 256 * @param infra: infrastructure cache. 257 * @param addr: host address. 258 * @param addrlen: length of addr. 259 * @param name: domain name of zone apex. 260 * @param namelen: length of domain name. 261 * @param timenow: what time it is now. 262 * @param dnsseclame: if true the host is set dnssec lame. 263 * if false, the host is marked lame (not serving the zone). 264 * @param reclame: if true host is a recursor not AA server. 265 * if false, dnsseclame or marked lame. 266 * @param qtype: the query type for which it is lame. 267 * @return: 0 on error. 268 */ 269 int infra_set_lame(struct infra_cache* infra, 270 struct sockaddr_storage* addr, socklen_t addrlen, 271 uint8_t* name, size_t namelen, time_t timenow, int dnsseclame, 272 int reclame, uint16_t qtype); 273 274 /** 275 * Update rtt information for the host. 276 * @param infra: infrastructure cache. 277 * @param addr: host address. 278 * @param addrlen: length of addr. 279 * @param name: zone name 280 * @param namelen: zone name length 281 * @param qtype: query type. 282 * @param roundtrip: estimate of roundtrip time in milliseconds or -1 for 283 * timeout. 284 * @param orig_rtt: original rtt for the query that timed out (roundtrip==-1). 285 * ignored if roundtrip != -1. 286 * @param timenow: what time it is now. 287 * @return: 0 on error. new rto otherwise. 288 */ 289 int infra_rtt_update(struct infra_cache* infra, struct sockaddr_storage* addr, 290 socklen_t addrlen, uint8_t* name, size_t namelen, int qtype, 291 int roundtrip, int orig_rtt, time_t timenow); 292 293 /** 294 * Update information for the host, store that a TCP transaction works. 295 * @param infra: infrastructure cache. 296 * @param addr: host address. 297 * @param addrlen: length of addr. 298 * @param name: name of zone 299 * @param namelen: length of name 300 */ 301 void infra_update_tcp_works(struct infra_cache* infra, 302 struct sockaddr_storage* addr, socklen_t addrlen, 303 uint8_t* name, size_t namelen); 304 305 /** 306 * Update edns information for the host. 307 * @param infra: infrastructure cache. 308 * @param addr: host address. 309 * @param addrlen: length of addr. 310 * @param name: name of zone 311 * @param namelen: length of name 312 * @param edns_version: the version that it publishes. 313 * If it is known to support EDNS then no-EDNS is not stored over it. 314 * @param timenow: what time it is now. 315 * @return: 0 on error. 316 */ 317 int infra_edns_update(struct infra_cache* infra, 318 struct sockaddr_storage* addr, socklen_t addrlen, 319 uint8_t* name, size_t namelen, int edns_version, time_t timenow); 320 321 /** 322 * Get Lameness information and average RTT if host is in the cache. 323 * This information is to be used for server selection. 324 * @param infra: infrastructure cache. 325 * @param addr: host address. 326 * @param addrlen: length of addr. 327 * @param name: zone name. 328 * @param namelen: zone name length. 329 * @param qtype: the query to be made. 330 * @param lame: if function returns true, this returns lameness of the zone. 331 * @param dnsseclame: if function returns true, this returns if the zone 332 * is dnssec-lame. 333 * @param reclame: if function returns true, this is if it is recursion lame. 334 * @param rtt: if function returns true, this returns avg rtt of the server. 335 * The rtt value is unclamped and reflects recent timeouts. 336 * @param timenow: what time it is now. 337 * @return if found in cache, or false if not (or TTL bad). 338 */ 339 int infra_get_lame_rtt(struct infra_cache* infra, 340 struct sockaddr_storage* addr, socklen_t addrlen, 341 uint8_t* name, size_t namelen, uint16_t qtype, 342 int* lame, int* dnsseclame, int* reclame, int* rtt, time_t timenow); 343 344 /** 345 * Get additional (debug) info on timing. 346 * @param infra: infra cache. 347 * @param addr: host address. 348 * @param addrlen: length of addr. 349 * @param name: zone name 350 * @param namelen: zone name length 351 * @param rtt: the rtt_info is copied into here (caller alloced return struct). 352 * @param delay: probe delay (if any). 353 * @param timenow: what time it is now. 354 * @param tA: timeout counter on type A. 355 * @param tAAAA: timeout counter on type AAAA. 356 * @param tother: timeout counter on type other. 357 * @return TTL the infra host element is valid for. If -1: not found in cache. 358 * TTL -2: found but expired. 359 */ 360 long long infra_get_host_rto(struct infra_cache* infra, 361 struct sockaddr_storage* addr, socklen_t addrlen, uint8_t* name, 362 size_t namelen, struct rtt_info* rtt, int* delay, time_t timenow, 363 int* tA, int* tAAAA, int* tother); 364 365 /** 366 * Increment the query rate counter for a delegation point. 367 * @param infra: infra cache. 368 * @param name: zone name 369 * @param namelen: zone name length 370 * @param timenow: what time it is now. 371 * @param qinfo: for logging, query name. 372 * @param replylist: for logging, querier's address (if any). 373 * @return 1 if it could be incremented. 0 if the increment overshot the 374 * ratelimit or if in the previous second the ratelimit was exceeded. 375 * Failures like alloc failures are not returned (probably as 1). 376 */ 377 int infra_ratelimit_inc(struct infra_cache* infra, uint8_t* name, 378 size_t namelen, time_t timenow, struct query_info* qinfo, 379 struct comm_reply* replylist); 380 381 /** 382 * Decrement the query rate counter for a delegation point. 383 * Because the reply received for the delegation point was pleasant, 384 * we do not charge this delegation point with it (i.e. it was a referral). 385 * Should call it with same second as when inc() was called. 386 * @param infra: infra cache. 387 * @param name: zone name 388 * @param namelen: zone name length 389 * @param timenow: what time it is now. 390 */ 391 void infra_ratelimit_dec(struct infra_cache* infra, uint8_t* name, 392 size_t namelen, time_t timenow); 393 394 /** 395 * See if the query rate counter for a delegation point is exceeded. 396 * So, no queries are going to be allowed. 397 * @param infra: infra cache. 398 * @param name: zone name 399 * @param namelen: zone name length 400 * @param timenow: what time it is now. 401 * @return true if exceeded. 402 */ 403 int infra_ratelimit_exceeded(struct infra_cache* infra, uint8_t* name, 404 size_t namelen, time_t timenow); 405 406 /** find the maximum rate stored, not too old. 0 if no information. */ 407 int infra_rate_max(void* data, time_t now); 408 409 /** find the ratelimit in qps for a domain. 0 if no limit for domain. */ 410 int infra_find_ratelimit(struct infra_cache* infra, uint8_t* name, 411 size_t namelen); 412 413 /** Update query ratelimit hash and decide 414 * whether or not a query should be dropped. 415 * @param infra: infra cache 416 * @param repinfo: information about client 417 * @param timenow: what time it is now. 418 * @param buffer: with query for logging. 419 * @return 1 if it could be incremented. 0 if the increment overshot the 420 * ratelimit and the query should be dropped. */ 421 int infra_ip_ratelimit_inc(struct infra_cache* infra, 422 struct comm_reply* repinfo, time_t timenow, 423 struct sldns_buffer* buffer); 424 425 /** 426 * Get memory used by the infra cache. 427 * @param infra: infrastructure cache. 428 * @return memory in use in bytes. 429 */ 430 size_t infra_get_mem(struct infra_cache* infra); 431 432 /** calculate size for the hashtable, does not count size of lameness, 433 * so the hashtable is a fixed number of items */ 434 size_t infra_sizefunc(void* k, void* d); 435 436 /** compare two addresses, returns -1, 0, or +1 */ 437 int infra_compfunc(void* key1, void* key2); 438 439 /** delete key, and destroy the lock */ 440 void infra_delkeyfunc(void* k, void* arg); 441 442 /** delete data and destroy the lameness hashtable */ 443 void infra_deldatafunc(void* d, void* arg); 444 445 /** calculate size for the hashtable */ 446 size_t rate_sizefunc(void* k, void* d); 447 448 /** compare two names, returns -1, 0, or +1 */ 449 int rate_compfunc(void* key1, void* key2); 450 451 /** delete key, and destroy the lock */ 452 void rate_delkeyfunc(void* k, void* arg); 453 454 /** delete data */ 455 void rate_deldatafunc(void* d, void* arg); 456 457 /* calculate size for the client ip hashtable */ 458 size_t ip_rate_sizefunc(void* k, void* d); 459 460 /* compare two addresses */ 461 int ip_rate_compfunc(void* key1, void* key2); 462 463 /* delete key, and destroy the lock */ 464 void ip_rate_delkeyfunc(void* d, void* arg); 465 466 /* delete data */ 467 #define ip_rate_deldatafunc rate_deldatafunc 468 469 #endif /* SERVICES_CACHE_INFRA_H */ 470