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. 40 */ 41 42 #ifndef SERVICES_CACHE_INFRA_H 43 #define SERVICES_CACHE_INFRA_H 44 #include "util/storage/lruhash.h" 45 #include "util/storage/dnstree.h" 46 #include "util/rtt.h" 47 struct slabhash; 48 struct config_file; 49 50 /** 51 * Host information kept for every server, per zone. 52 */ 53 struct infra_key { 54 /** the host address. */ 55 struct sockaddr_storage addr; 56 /** length of addr. */ 57 socklen_t addrlen; 58 /** zone name in wireformat */ 59 uint8_t* zonename; 60 /** length of zonename */ 61 size_t namelen; 62 /** hash table entry, data of type infra_data. */ 63 struct lruhash_entry entry; 64 }; 65 66 /** 67 * Host information encompasses host capabilities and retransmission timeouts. 68 * And lameness information (notAuthoritative, noEDNS, Recursive) 69 */ 70 struct infra_data { 71 /** TTL value for this entry. absolute time. */ 72 time_t ttl; 73 74 /** time in seconds (absolute) when probing re-commences, 0 disabled */ 75 time_t probedelay; 76 /** round trip times for timeout calculation */ 77 struct rtt_info rtt; 78 79 /** edns version that the host supports, -1 means no EDNS */ 80 int edns_version; 81 /** if the EDNS lameness is already known or not. 82 * EDNS lame is when EDNS queries or replies are dropped, 83 * and cause a timeout */ 84 uint8_t edns_lame_known; 85 86 /** is the host lame (does not serve the zone authoritatively), 87 * or is the host dnssec lame (does not serve DNSSEC data) */ 88 uint8_t isdnsseclame; 89 /** is the host recursion lame (not AA, but RA) */ 90 uint8_t rec_lame; 91 /** the host is lame (not authoritative) for A records */ 92 uint8_t lame_type_A; 93 /** the host is lame (not authoritative) for other query types */ 94 uint8_t lame_other; 95 96 /** timeouts counter for type A */ 97 uint8_t timeout_A; 98 /** timeouts counter for type AAAA */ 99 uint8_t timeout_AAAA; 100 /** timeouts counter for others */ 101 uint8_t timeout_other; 102 }; 103 104 /** 105 * Infra cache 106 */ 107 struct infra_cache { 108 /** The hash table with hosts */ 109 struct slabhash* hosts; 110 /** TTL value for host information, in seconds */ 111 int host_ttl; 112 /** hash table with query rates per name: rate_key, rate_data */ 113 struct slabhash* domain_rates; 114 /** ratelimit settings for domains, struct domain_limit_data */ 115 rbtree_t domain_limits; 116 }; 117 118 /** ratelimit, unless overridden by domain_limits, 0 is off */ 119 extern int infra_dp_ratelimit; 120 121 /** 122 * ratelimit settings for domains 123 */ 124 struct domain_limit_data { 125 /** key for rbtree, must be first in struct, name of domain */ 126 struct name_tree_node node; 127 /** ratelimit for exact match with this name, -1 if not set */ 128 int lim; 129 /** ratelimit for names below this name, -1 if not set */ 130 int below; 131 }; 132 133 /** 134 * key for ratelimit lookups, a domain name 135 */ 136 struct rate_key { 137 /** lruhash key entry */ 138 struct lruhash_entry entry; 139 /** domain name in uncompressed wireformat */ 140 uint8_t* name; 141 /** length of name */ 142 size_t namelen; 143 }; 144 145 /** number of seconds to track qps rate */ 146 #define RATE_WINDOW 2 147 148 /** 149 * Data for ratelimits per domain name 150 * It is incremented when a non-cache-lookup happens for that domain name. 151 * The name is the delegation point we have for the name. 152 * If a new delegation point is found (a referral reply), the previous 153 * delegation point is decremented, and the new one is charged with the query. 154 */ 155 struct rate_data { 156 /** queries counted, for that second. 0 if not in use. */ 157 int qps[RATE_WINDOW]; 158 /** what the timestamp is of the qps array members, counter is 159 * valid for that timestamp. Usually now and now-1. */ 160 time_t timestamp[RATE_WINDOW]; 161 }; 162 163 /** infra host cache default hash lookup size */ 164 #define INFRA_HOST_STARTSIZE 32 165 /** bytes per zonename reserved in the hostcache, dnamelen(zonename.com.) */ 166 #define INFRA_BYTES_NAME 14 167 168 /** 169 * Create infra cache. 170 * @param cfg: config parameters or NULL for defaults. 171 * @return: new infra cache, or NULL. 172 */ 173 struct infra_cache* infra_create(struct config_file* cfg); 174 175 /** 176 * Delete infra cache. 177 * @param infra: infrastructure cache to delete. 178 */ 179 void infra_delete(struct infra_cache* infra); 180 181 /** 182 * Adjust infra cache to use updated configuration settings. 183 * This may clean the cache. Operates a bit like realloc. 184 * There may be no threading or use by other threads. 185 * @param infra: existing cache. If NULL a new infra cache is returned. 186 * @param cfg: config options. 187 * @return the new infra cache pointer or NULL on error. 188 */ 189 struct infra_cache* infra_adjust(struct infra_cache* infra, 190 struct config_file* cfg); 191 192 /** 193 * Plain find infra data function (used by the the other functions) 194 * @param infra: infrastructure cache. 195 * @param addr: host address. 196 * @param addrlen: length of addr. 197 * @param name: domain name of zone. 198 * @param namelen: length of domain name. 199 * @param wr: if true, writelock, else readlock. 200 * @return the entry, could be expired (this is not checked) or NULL. 201 */ 202 struct lruhash_entry* infra_lookup_nottl(struct infra_cache* infra, 203 struct sockaddr_storage* addr, socklen_t addrlen, uint8_t* name, 204 size_t namelen, int wr); 205 206 /** 207 * Find host information to send a packet. Creates new entry if not found. 208 * Lameness is empty. EDNS is 0 (try with first), and rtt is returned for 209 * the first message to it. 210 * Use this to send a packet only, because it also locks out others when 211 * probing is restricted. 212 * @param infra: infrastructure cache. 213 * @param addr: host address. 214 * @param addrlen: length of addr. 215 * @param name: domain name of zone. 216 * @param namelen: length of domain name. 217 * @param timenow: what time it is now. 218 * @param edns_vs: edns version it supports, is returned. 219 * @param edns_lame_known: if EDNS lame (EDNS is dropped in transit) has 220 * already been probed, is returned. 221 * @param to: timeout to use, is returned. 222 * @return: 0 on error. 223 */ 224 int infra_host(struct infra_cache* infra, struct sockaddr_storage* addr, 225 socklen_t addrlen, uint8_t* name, size_t namelen, 226 time_t timenow, int* edns_vs, uint8_t* edns_lame_known, int* to); 227 228 /** 229 * Set a host to be lame for the given zone. 230 * @param infra: infrastructure cache. 231 * @param addr: host address. 232 * @param addrlen: length of addr. 233 * @param name: domain name of zone apex. 234 * @param namelen: length of domain name. 235 * @param timenow: what time it is now. 236 * @param dnsseclame: if true the host is set dnssec lame. 237 * if false, the host is marked lame (not serving the zone). 238 * @param reclame: if true host is a recursor not AA server. 239 * if false, dnsseclame or marked lame. 240 * @param qtype: the query type for which it is lame. 241 * @return: 0 on error. 242 */ 243 int infra_set_lame(struct infra_cache* infra, 244 struct sockaddr_storage* addr, socklen_t addrlen, 245 uint8_t* name, size_t namelen, time_t timenow, int dnsseclame, 246 int reclame, uint16_t qtype); 247 248 /** 249 * Update rtt information for the host. 250 * @param infra: infrastructure cache. 251 * @param addr: host address. 252 * @param addrlen: length of addr. 253 * @param name: zone name 254 * @param namelen: zone name length 255 * @param qtype: query type. 256 * @param roundtrip: estimate of roundtrip time in milliseconds or -1 for 257 * timeout. 258 * @param orig_rtt: original rtt for the query that timed out (roundtrip==-1). 259 * ignored if roundtrip != -1. 260 * @param timenow: what time it is now. 261 * @return: 0 on error. new rto otherwise. 262 */ 263 int infra_rtt_update(struct infra_cache* infra, struct sockaddr_storage* addr, 264 socklen_t addrlen, uint8_t* name, size_t namelen, int qtype, 265 int roundtrip, int orig_rtt, time_t timenow); 266 267 /** 268 * Update information for the host, store that a TCP transaction works. 269 * @param infra: infrastructure cache. 270 * @param addr: host address. 271 * @param addrlen: length of addr. 272 * @param name: name of zone 273 * @param namelen: length of name 274 */ 275 void infra_update_tcp_works(struct infra_cache* infra, 276 struct sockaddr_storage* addr, socklen_t addrlen, 277 uint8_t* name, size_t namelen); 278 279 /** 280 * Update edns information for the host. 281 * @param infra: infrastructure cache. 282 * @param addr: host address. 283 * @param addrlen: length of addr. 284 * @param name: name of zone 285 * @param namelen: length of name 286 * @param edns_version: the version that it publishes. 287 * If it is known to support EDNS then no-EDNS is not stored over it. 288 * @param timenow: what time it is now. 289 * @return: 0 on error. 290 */ 291 int infra_edns_update(struct infra_cache* infra, 292 struct sockaddr_storage* addr, socklen_t addrlen, 293 uint8_t* name, size_t namelen, int edns_version, time_t timenow); 294 295 /** 296 * Get Lameness information and average RTT if host is in the cache. 297 * This information is to be used for server selection. 298 * @param infra: infrastructure cache. 299 * @param addr: host address. 300 * @param addrlen: length of addr. 301 * @param name: zone name. 302 * @param namelen: zone name length. 303 * @param qtype: the query to be made. 304 * @param lame: if function returns true, this returns lameness of the zone. 305 * @param dnsseclame: if function returns true, this returns if the zone 306 * is dnssec-lame. 307 * @param reclame: if function returns true, this is if it is recursion lame. 308 * @param rtt: if function returns true, this returns avg rtt of the server. 309 * The rtt value is unclamped and reflects recent timeouts. 310 * @param timenow: what time it is now. 311 * @return if found in cache, or false if not (or TTL bad). 312 */ 313 int infra_get_lame_rtt(struct infra_cache* infra, 314 struct sockaddr_storage* addr, socklen_t addrlen, 315 uint8_t* name, size_t namelen, uint16_t qtype, 316 int* lame, int* dnsseclame, int* reclame, int* rtt, time_t timenow); 317 318 /** 319 * Get additional (debug) info on timing. 320 * @param infra: infra cache. 321 * @param addr: host address. 322 * @param addrlen: length of addr. 323 * @param name: zone name 324 * @param namelen: zone name length 325 * @param rtt: the rtt_info is copied into here (caller alloced return struct). 326 * @param delay: probe delay (if any). 327 * @param timenow: what time it is now. 328 * @param tA: timeout counter on type A. 329 * @param tAAAA: timeout counter on type AAAA. 330 * @param tother: timeout counter on type other. 331 * @return TTL the infra host element is valid for. If -1: not found in cache. 332 * TTL -2: found but expired. 333 */ 334 long long infra_get_host_rto(struct infra_cache* infra, 335 struct sockaddr_storage* addr, socklen_t addrlen, uint8_t* name, 336 size_t namelen, struct rtt_info* rtt, int* delay, time_t timenow, 337 int* tA, int* tAAAA, int* tother); 338 339 /** 340 * Increment the query rate counter for a delegation point. 341 * @param infra: infra cache. 342 * @param name: zone name 343 * @param namelen: zone name length 344 * @param timenow: what time it is now. 345 * @return 1 if it could be incremented. 0 if the increment overshot the 346 * ratelimit or if in the previous second the ratelimit was exceeded. 347 * Failures like alloc failures are not returned (probably as 1). 348 */ 349 int infra_ratelimit_inc(struct infra_cache* infra, uint8_t* name, 350 size_t namelen, time_t timenow); 351 352 /** 353 * Decrement the query rate counter for a delegation point. 354 * Because the reply received for the delegation point was pleasant, 355 * we do not charge this delegation point with it (i.e. it was a referral). 356 * Should call it with same second as when inc() was called. 357 * @param infra: infra cache. 358 * @param name: zone name 359 * @param namelen: zone name length 360 * @param timenow: what time it is now. 361 */ 362 void infra_ratelimit_dec(struct infra_cache* infra, uint8_t* name, 363 size_t namelen, time_t timenow); 364 365 /** 366 * See if the query rate counter for a delegation point is exceeded. 367 * So, no queries are going to be allowed. 368 * @param infra: infra cache. 369 * @param name: zone name 370 * @param namelen: zone name length 371 * @param timenow: what time it is now. 372 * @return true if exceeded. 373 */ 374 int infra_ratelimit_exceeded(struct infra_cache* infra, uint8_t* name, 375 size_t namelen, time_t timenow); 376 377 /** find the maximum rate stored, not too old. 0 if no information. */ 378 int infra_rate_max(void* data, time_t now); 379 380 /** find the ratelimit in qps for a domain */ 381 int infra_find_ratelimit(struct infra_cache* infra, uint8_t* name, 382 size_t namelen); 383 384 /** 385 * Get memory used by the infra cache. 386 * @param infra: infrastructure cache. 387 * @return memory in use in bytes. 388 */ 389 size_t infra_get_mem(struct infra_cache* infra); 390 391 /** calculate size for the hashtable, does not count size of lameness, 392 * so the hashtable is a fixed number of items */ 393 size_t infra_sizefunc(void* k, void* d); 394 395 /** compare two addresses, returns -1, 0, or +1 */ 396 int infra_compfunc(void* key1, void* key2); 397 398 /** delete key, and destroy the lock */ 399 void infra_delkeyfunc(void* k, void* arg); 400 401 /** delete data and destroy the lameness hashtable */ 402 void infra_deldatafunc(void* d, void* arg); 403 404 /** calculate size for the hashtable */ 405 size_t rate_sizefunc(void* k, void* d); 406 407 /** compare two names, returns -1, 0, or +1 */ 408 int rate_compfunc(void* key1, void* key2); 409 410 /** delete key, and destroy the lock */ 411 void rate_delkeyfunc(void* k, void* arg); 412 413 /** delete data */ 414 void rate_deldatafunc(void* d, void* arg); 415 416 #endif /* SERVICES_CACHE_INFRA_H */ 417