contrib/unbound/services/cache/infra.c

   1 /*
   2  * services/cache/infra.c - 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 #include "config.h"
  42 #include "sldns/rrdef.h"
  43 #include "sldns/str2wire.h"
  44 #include "services/cache/infra.h"
  45 #include "util/storage/slabhash.h"
  46 #include "util/storage/lookup3.h"
  47 #include "util/data/dname.h"
  48 #include "util/log.h"
  49 #include "util/net_help.h"
  50 #include "util/config_file.h"
  51 #include "iterator/iterator.h"
  52
  53 /** Timeout when only a single probe query per IP is allowed. */
  54 #define PROBE_MAXRTO 12000 /* in msec */
  55
  56 /** number of timeouts for a type when the domain can be blocked ;
  57  * even if another type has completely rtt maxed it, the different type
  58  * can do this number of packets (until those all timeout too) */
  59 #define TIMEOUT_COUNT_MAX 3
  60
  61 /** ratelimit value for delegation point */
  62 int infra_dp_ratelimit = 0;
  63
  64 /** ratelimit value for client ip addresses,
  65  *  in queries per second. */
  66 int infra_ip_ratelimit = 0;
  67
  68 size_t
  69 infra_sizefunc(void* k, void* ATTR_UNUSED(d))
  70 {
  71         struct infra_key* key = (struct infra_key*)k;
  72         return sizeof(*key) + sizeof(struct infra_data) + key->namelen
  73                 + lock_get_mem(&key->entry.lock);
  74 }
  75
  76 int
  77 infra_compfunc(void* key1, void* key2)
  78 {
  79         struct infra_key* k1 = (struct infra_key*)key1;
  80         struct infra_key* k2 = (struct infra_key*)key2;
  81         int r = sockaddr_cmp(&k1->addr, k1->addrlen, &k2->addr, k2->addrlen);
  82         if(r != 0)
  83                 return r;
  84         if(k1->namelen != k2->namelen) {
  85                 if(k1->namelen < k2->namelen)
  86                         return -1;
  87                 return 1;
  88         }
  89         return query_dname_compare(k1->zonename, k2->zonename);
  90 }
  91
  92 void
  93 infra_delkeyfunc(void* k, void* ATTR_UNUSED(arg))
  94 {
  95         struct infra_key* key = (struct infra_key*)k;
  96         if(!key)
  97                 return;
  98         lock_rw_destroy(&key->entry.lock);
  99         free(key->zonename);
 100         free(key);
 101 }
 102
 103 void
 104 infra_deldatafunc(void* d, void* ATTR_UNUSED(arg))
 105 {
 106         struct infra_data* data = (struct infra_data*)d;
 107         free(data);
 108 }
 109
 110 size_t
 111 rate_sizefunc(void* k, void* ATTR_UNUSED(d))
 112 {
 113         struct rate_key* key = (struct rate_key*)k;
 114         return sizeof(*key) + sizeof(struct rate_data) + key->namelen
 115                 + lock_get_mem(&key->entry.lock);
 116 }
 117
 118 int
 119 rate_compfunc(void* key1, void* key2)
 120 {
 121         struct rate_key* k1 = (struct rate_key*)key1;
 122         struct rate_key* k2 = (struct rate_key*)key2;
 123         if(k1->namelen != k2->namelen) {
 124                 if(k1->namelen < k2->namelen)
 125                         return -1;
 126                 return 1;
 127         }
 128         return query_dname_compare(k1->name, k2->name);
 129 }
 130
 131 void
 132 rate_delkeyfunc(void* k, void* ATTR_UNUSED(arg))
 133 {
 134         struct rate_key* key = (struct rate_key*)k;
 135         if(!key)
 136                 return;
 137         lock_rw_destroy(&key->entry.lock);
 138         free(key->name);
 139         free(key);
 140 }
 141
 142 void
 143 rate_deldatafunc(void* d, void* ATTR_UNUSED(arg))
 144 {
 145         struct rate_data* data = (struct rate_data*)d;
 146         free(data);
 147 }
 148
 149 /** find or create element in domainlimit tree */
 150 static struct domain_limit_data* domain_limit_findcreate(
 151         struct infra_cache* infra, char* name)
 152 {
 153         uint8_t* nm;
 154         int labs;
 155         size_t nmlen;
 156         struct domain_limit_data* d;
 157
 158         /* parse name */
 159         nm = sldns_str2wire_dname(name, &nmlen);
 160         if(!nm) {
 161                 log_err("could not parse %s", name);
 162                 return NULL;
 163         }
 164         labs = dname_count_labels(nm);
 165
 166         /* can we find it? */
 167         d = (struct domain_limit_data*)name_tree_find(&infra->domain_limits,
 168                 nm, nmlen, labs, LDNS_RR_CLASS_IN);
 169         if(d) {
 170                 free(nm);
 171                 return d;
 172         }
 173
 174         /* create it */
 175         d = (struct domain_limit_data*)calloc(1, sizeof(*d));
 176         if(!d) {
 177                 free(nm);
 178                 return NULL;
 179         }
 180         d->node.node.key = &d->node;
 181         d->node.name = nm;
 182         d->node.len = nmlen;
 183         d->node.labs = labs;
 184         d->node.dclass = LDNS_RR_CLASS_IN;
 185         d->lim = -1;
 186         d->below = -1;
 187         if(!name_tree_insert(&infra->domain_limits, &d->node, nm, nmlen,
 188                 labs, LDNS_RR_CLASS_IN)) {
 189                 log_err("duplicate element in domainlimit tree");
 190                 free(nm);
 191                 free(d);
 192                 return NULL;
 193         }
 194         return d;
 195 }
 196
 197 /** insert rate limit configuration into lookup tree */
 198 static int infra_ratelimit_cfg_insert(struct infra_cache* infra,
 199         struct config_file* cfg)
 200 {
 201         struct config_str2list* p;
 202         struct domain_limit_data* d;
 203         for(p = cfg->ratelimit_for_domain; p; p = p->next) {
 204                 d = domain_limit_findcreate(infra, p->str);
 205                 if(!d)
 206                         return 0;
 207                 d->lim = atoi(p->str2);
 208         }
 209         for(p = cfg->ratelimit_below_domain; p; p = p->next) {
 210                 d = domain_limit_findcreate(infra, p->str);
 211                 if(!d)
 212                         return 0;
 213                 d->below = atoi(p->str2);
 214         }
 215         return 1;
 216 }
 217
 218 struct infra_cache*
 219 infra_create(struct config_file* cfg)
 220 {
 221         struct infra_cache* infra = (struct infra_cache*)calloc(1,
 222                 sizeof(struct infra_cache));
 223         size_t maxmem = cfg->infra_cache_numhosts * (sizeof(struct infra_key)+
 224                 sizeof(struct infra_data)+INFRA_BYTES_NAME);
 225         infra->hosts = slabhash_create(cfg->infra_cache_slabs,
 226                 INFRA_HOST_STARTSIZE, maxmem, &infra_sizefunc, &infra_compfunc,
 227                 &infra_delkeyfunc, &infra_deldatafunc, NULL);
 228         if(!infra->hosts) {
 229                 free(infra);
 230                 return NULL;
 231         }
 232         infra->host_ttl = cfg->host_ttl;
 233         name_tree_init(&infra->domain_limits);
 234         infra_dp_ratelimit = cfg->ratelimit;
 235         if(cfg->ratelimit != 0) {
 236                 infra->domain_rates = slabhash_create(cfg->ratelimit_slabs,
 237                         INFRA_HOST_STARTSIZE, cfg->ratelimit_size,
 238                         &rate_sizefunc, &rate_compfunc, &rate_delkeyfunc,
 239                         &rate_deldatafunc, NULL);
 240                 if(!infra->domain_rates) {
 241                         infra_delete(infra);
 242                         return NULL;
 243                 }
 244                 /* insert config data into ratelimits */
 245                 if(!infra_ratelimit_cfg_insert(infra, cfg)) {
 246                         infra_delete(infra);
 247                         return NULL;
 248                 }
 249                 name_tree_init_parents(&infra->domain_limits);
 250         }
 251         infra_ip_ratelimit = cfg->ip_ratelimit;
 252         infra->client_ip_rates = slabhash_create(cfg->ratelimit_slabs,
 253             INFRA_HOST_STARTSIZE, cfg->ip_ratelimit_size, &ip_rate_sizefunc,
 254             &ip_rate_compfunc, &ip_rate_delkeyfunc, &ip_rate_deldatafunc, NULL);
 255         if(!infra->client_ip_rates) {
 256                 infra_delete(infra);
 257                 return NULL;
 258         }
 259         return infra;
 260 }
 261
 262 /** delete domain_limit entries */
 263 static void domain_limit_free(rbnode_type* n, void* ATTR_UNUSED(arg))
 264 {
 265         if(n) {
 266                 free(((struct domain_limit_data*)n)->node.name);
 267                 free(n);
 268         }
 269 }
 270
 271 void
 272 infra_delete(struct infra_cache* infra)
 273 {
 274         if(!infra)
 275                 return;
 276         slabhash_delete(infra->hosts);
 277         slabhash_delete(infra->domain_rates);
 278         traverse_postorder(&infra->domain_limits, domain_limit_free, NULL);
 279         slabhash_delete(infra->client_ip_rates);
 280         free(infra);
 281 }
 282
 283 struct infra_cache*
 284 infra_adjust(struct infra_cache* infra, struct config_file* cfg)
 285 {
 286         size_t maxmem;
 287         if(!infra)
 288                 return infra_create(cfg);
 289         infra->host_ttl = cfg->host_ttl;
 290         maxmem = cfg->infra_cache_numhosts * (sizeof(struct infra_key)+
 291                 sizeof(struct infra_data)+INFRA_BYTES_NAME);
 292         if(maxmem != slabhash_get_size(infra->hosts) ||
 293                 cfg->infra_cache_slabs != infra->hosts->size) {
 294                 infra_delete(infra);
 295                 infra = infra_create(cfg);
 296         }
 297         return infra;
 298 }
 299
 300 /** calculate the hash value for a host key
 301  *  set use_port to a non-0 number to use the port in
 302  *  the hash calculation; 0 to ignore the port.*/
 303 static hashvalue_type
 304 hash_addr(struct sockaddr_storage* addr, socklen_t addrlen,
 305   int use_port)
 306 {
 307         hashvalue_type h = 0xab;
 308         /* select the pieces to hash, some OS have changing data inside */
 309         if(addr_is_ip6(addr, addrlen)) {
 310                 struct sockaddr_in6* in6 = (struct sockaddr_in6*)addr;
 311                 h = hashlittle(&in6->sin6_family, sizeof(in6->sin6_family), h);
 312                 if(use_port){
 313                         h = hashlittle(&in6->sin6_port, sizeof(in6->sin6_port), h);
 314                 }
 315                 h = hashlittle(&in6->sin6_addr, INET6_SIZE, h);
 316         } else {
 317                 struct sockaddr_in* in = (struct sockaddr_in*)addr;
 318                 h = hashlittle(&in->sin_family, sizeof(in->sin_family), h);
 319                 if(use_port){
 320                         h = hashlittle(&in->sin_port, sizeof(in->sin_port), h);
 321                 }
 322                 h = hashlittle(&in->sin_addr, INET_SIZE, h);
 323         }
 324         return h;
 325 }
 326
 327 /** calculate infra hash for a key */
 328 static hashvalue_type
 329 hash_infra(struct sockaddr_storage* addr, socklen_t addrlen, uint8_t* name)
 330 {
 331         return dname_query_hash(name, hash_addr(addr, addrlen, 1));
 332 }
 333
 334 /** lookup version that does not check host ttl (you check it) */
 335 struct lruhash_entry*
 336 infra_lookup_nottl(struct infra_cache* infra, struct sockaddr_storage* addr,
 337         socklen_t addrlen, uint8_t* name, size_t namelen, int wr)
 338 {
 339         struct infra_key k;
 340         k.addrlen = addrlen;
 341         memcpy(&k.addr, addr, addrlen);
 342         k.namelen = namelen;
 343         k.zonename = name;
 344         k.entry.hash = hash_infra(addr, addrlen, name);
 345         k.entry.key = (void*)&k;
 346         k.entry.data = NULL;
 347         return slabhash_lookup(infra->hosts, k.entry.hash, &k, wr);
 348 }
 349
 350 /** init the data elements */
 351 static void
 352 data_entry_init(struct infra_cache* infra, struct lruhash_entry* e,
 353         time_t timenow)
 354 {
 355         struct infra_data* data = (struct infra_data*)e->data;
 356         data->ttl = timenow + infra->host_ttl;
 357         rtt_init(&data->rtt);
 358         data->edns_version = 0;
 359         data->edns_lame_known = 0;
 360         data->probedelay = 0;
 361         data->isdnsseclame = 0;
 362         data->rec_lame = 0;
 363         data->lame_type_A = 0;
 364         data->lame_other = 0;
 365         data->timeout_A = 0;
 366         data->timeout_AAAA = 0;
 367         data->timeout_other = 0;
 368 }
 369
 370 /**
 371  * Create and init a new entry for a host
 372  * @param infra: infra structure with config parameters.
 373  * @param addr: host address.
 374  * @param addrlen: length of addr.
 375  * @param name: name of zone
 376  * @param namelen: length of name.
 377  * @param tm: time now.
 378  * @return: the new entry or NULL on malloc failure.
 379  */
 380 static struct lruhash_entry*
 381 new_entry(struct infra_cache* infra, struct sockaddr_storage* addr,
 382         socklen_t addrlen, uint8_t* name, size_t namelen, time_t tm)
 383 {
 384         struct infra_data* data;
 385         struct infra_key* key = (struct infra_key*)malloc(sizeof(*key));
 386         if(!key)
 387                 return NULL;
 388         data = (struct infra_data*)malloc(sizeof(struct infra_data));
 389         if(!data) {
 390                 free(key);
 391                 return NULL;
 392         }
 393         key->zonename = memdup(name, namelen);
 394         if(!key->zonename) {
 395                 free(key);
 396                 free(data);
 397                 return NULL;
 398         }
 399         key->namelen = namelen;
 400         lock_rw_init(&key->entry.lock);
 401         key->entry.hash = hash_infra(addr, addrlen, name);
 402         key->entry.key = (void*)key;
 403         key->entry.data = (void*)data;
 404         key->addrlen = addrlen;
 405         memcpy(&key->addr, addr, addrlen);
 406         data_entry_init(infra, &key->entry, tm);
 407         return &key->entry;
 408 }
 409
 410 int
 411 infra_host(struct infra_cache* infra, struct sockaddr_storage* addr,
 412         socklen_t addrlen, uint8_t* nm, size_t nmlen, time_t timenow,
 413         int* edns_vs, uint8_t* edns_lame_known, int* to)
 414 {
 415         struct lruhash_entry* e = infra_lookup_nottl(infra, addr, addrlen,
 416                 nm, nmlen, 0);
 417         struct infra_data* data;
 418         int wr = 0;
 419         if(e && ((struct infra_data*)e->data)->ttl < timenow) {
 420                 /* it expired, try to reuse existing entry */
 421                 int old = ((struct infra_data*)e->data)->rtt.rto;
 422                 uint8_t tA = ((struct infra_data*)e->data)->timeout_A;
 423                 uint8_t tAAAA = ((struct infra_data*)e->data)->timeout_AAAA;
 424                 uint8_t tother = ((struct infra_data*)e->data)->timeout_other;
 425                 lock_rw_unlock(&e->lock);
 426                 e = infra_lookup_nottl(infra, addr, addrlen, nm, nmlen, 1);
 427                 if(e) {
 428                         /* if its still there we have a writelock, init */
 429                         /* re-initialise */
 430                         /* do not touch lameness, it may be valid still */
 431                         data_entry_init(infra, e, timenow);
 432                         wr = 1;
 433                         /* TOP_TIMEOUT remains on reuse */
 434                         if(old >= USEFUL_SERVER_TOP_TIMEOUT) {
 435                                 ((struct infra_data*)e->data)->rtt.rto
 436                                         = USEFUL_SERVER_TOP_TIMEOUT;
 437                                 ((struct infra_data*)e->data)->timeout_A = tA;
 438                                 ((struct infra_data*)e->data)->timeout_AAAA = tAAAA;
 439                                 ((struct infra_data*)e->data)->timeout_other = tother;
 440                         }
 441                 }
 442         }
 443         if(!e) {
 444                 /* insert new entry */
 445                 if(!(e = new_entry(infra, addr, addrlen, nm, nmlen, timenow)))
 446                         return 0;
 447                 data = (struct infra_data*)e->data;
 448                 *edns_vs = data->edns_version;
 449                 *edns_lame_known = data->edns_lame_known;
 450                 *to = rtt_timeout(&data->rtt);
 451                 slabhash_insert(infra->hosts, e->hash, e, data, NULL);
 452                 return 1;
 453         }
 454         /* use existing entry */
 455         data = (struct infra_data*)e->data;
 456         *edns_vs = data->edns_version;
 457         *edns_lame_known = data->edns_lame_known;
 458         *to = rtt_timeout(&data->rtt);
 459         if(*to >= PROBE_MAXRTO && rtt_notimeout(&data->rtt)*4 <= *to) {
 460                 /* delay other queries, this is the probe query */
 461                 if(!wr) {
 462                         lock_rw_unlock(&e->lock);
 463                         e = infra_lookup_nottl(infra, addr,addrlen,nm,nmlen, 1);
 464                         if(!e) { /* flushed from cache real fast, no use to
 465                                 allocate just for the probedelay */
 466                                 return 1;
 467                         }
 468                         data = (struct infra_data*)e->data;
 469                 }
 470                 /* add 999 to round up the timeout value from msec to sec,
 471                  * then add a whole second so it is certain that this probe
 472                  * has timed out before the next is allowed */
 473                 data->probedelay = timenow + ((*to)+1999)/1000;
 474         }
 475         lock_rw_unlock(&e->lock);
 476         return 1;
 477 }
 478
 479 int
 480 infra_set_lame(struct infra_cache* infra, struct sockaddr_storage* addr,
 481         socklen_t addrlen, uint8_t* nm, size_t nmlen, time_t timenow,
 482         int dnsseclame, int reclame, uint16_t qtype)
 483 {
 484         struct infra_data* data;
 485         struct lruhash_entry* e;
 486         int needtoinsert = 0;
 487         e = infra_lookup_nottl(infra, addr, addrlen, nm, nmlen, 1);
 488         if(!e) {
 489                 /* insert it */
 490                 if(!(e = new_entry(infra, addr, addrlen, nm, nmlen, timenow))) {
 491                         log_err("set_lame: malloc failure");
 492                         return 0;
 493                 }
 494                 needtoinsert = 1;
 495         } else if( ((struct infra_data*)e->data)->ttl < timenow) {
 496                 /* expired, reuse existing entry */
 497                 data_entry_init(infra, e, timenow);
 498         }
 499         /* got an entry, now set the zone lame */
 500         data = (struct infra_data*)e->data;
 501         /* merge data (if any) */
 502         if(dnsseclame)
 503                 data->isdnsseclame = 1;
 504         if(reclame)
 505                 data->rec_lame = 1;
 506         if(!dnsseclame && !reclame && qtype == LDNS_RR_TYPE_A)
 507                 data->lame_type_A = 1;
 508         if(!dnsseclame  && !reclame && qtype != LDNS_RR_TYPE_A)
 509                 data->lame_other = 1;
 510         /* done */
 511         if(needtoinsert)
 512                 slabhash_insert(infra->hosts, e->hash, e, e->data, NULL);
 513         else    { lock_rw_unlock(&e->lock); }
 514         return 1;
 515 }
 516
 517 void
 518 infra_update_tcp_works(struct infra_cache* infra,
 519         struct sockaddr_storage* addr, socklen_t addrlen, uint8_t* nm,
 520         size_t nmlen)
 521 {
 522         struct lruhash_entry* e = infra_lookup_nottl(infra, addr, addrlen,
 523                 nm, nmlen, 1);
 524         struct infra_data* data;
 525         if(!e)
 526                 return; /* doesn't exist */
 527         data = (struct infra_data*)e->data;
 528         if(data->rtt.rto >= RTT_MAX_TIMEOUT)
 529                 /* do not disqualify this server altogether, it is better
 530                  * than nothing */
 531                 data->rtt.rto = RTT_MAX_TIMEOUT-1000;
 532         lock_rw_unlock(&e->lock);
 533 }
 534
 535 int
 536 infra_rtt_update(struct infra_cache* infra, struct sockaddr_storage* addr,
 537         socklen_t addrlen, uint8_t* nm, size_t nmlen, int qtype,
 538         int roundtrip, int orig_rtt, time_t timenow)
 539 {
 540         struct lruhash_entry* e = infra_lookup_nottl(infra, addr, addrlen,
 541                 nm, nmlen, 1);
 542         struct infra_data* data;
 543         int needtoinsert = 0;
 544         int rto = 1;
 545         if(!e) {
 546                 if(!(e = new_entry(infra, addr, addrlen, nm, nmlen, timenow)))
 547                         return 0;
 548                 needtoinsert = 1;
 549         } else if(((struct infra_data*)e->data)->ttl < timenow) {
 550                 data_entry_init(infra, e, timenow);
 551         }
 552         /* have an entry, update the rtt */
 553         data = (struct infra_data*)e->data;
 554         if(roundtrip == -1) {
 555                 rtt_lost(&data->rtt, orig_rtt);
 556                 if(qtype == LDNS_RR_TYPE_A) {
 557                         if(data->timeout_A < TIMEOUT_COUNT_MAX)
 558                                 data->timeout_A++;
 559                 } else if(qtype == LDNS_RR_TYPE_AAAA) {
 560                         if(data->timeout_AAAA < TIMEOUT_COUNT_MAX)
 561                                 data->timeout_AAAA++;
 562                 } else {
 563                         if(data->timeout_other < TIMEOUT_COUNT_MAX)
 564                                 data->timeout_other++;
 565                 }
 566         } else {
 567                 /* if we got a reply, but the old timeout was above server
 568                  * selection height, delete the timeout so the server is
 569                  * fully available again */
 570                 if(rtt_unclamped(&data->rtt) >= USEFUL_SERVER_TOP_TIMEOUT)
 571                         rtt_init(&data->rtt);
 572                 rtt_update(&data->rtt, roundtrip);
 573                 data->probedelay = 0;
 574                 if(qtype == LDNS_RR_TYPE_A)
 575                         data->timeout_A = 0;
 576                 else if(qtype == LDNS_RR_TYPE_AAAA)
 577                         data->timeout_AAAA = 0;
 578                 else    data->timeout_other = 0;
 579         }
 580         if(data->rtt.rto > 0)
 581                 rto = data->rtt.rto;
 582
 583         if(needtoinsert)
 584                 slabhash_insert(infra->hosts, e->hash, e, e->data, NULL);
 585         else    { lock_rw_unlock(&e->lock); }
 586         return rto;
 587 }
 588
 589 long long infra_get_host_rto(struct infra_cache* infra,
 590         struct sockaddr_storage* addr, socklen_t addrlen, uint8_t* nm,
 591         size_t nmlen, struct rtt_info* rtt, int* delay, time_t timenow,
 592         int* tA, int* tAAAA, int* tother)
 593 {
 594         struct lruhash_entry* e = infra_lookup_nottl(infra, addr, addrlen,
 595                 nm, nmlen, 0);
 596         struct infra_data* data;
 597         long long ttl = -2;
 598         if(!e) return -1;
 599         data = (struct infra_data*)e->data;
 600         if(data->ttl >= timenow) {
 601                 ttl = (long long)(data->ttl - timenow);
 602                 memmove(rtt, &data->rtt, sizeof(*rtt));
 603                 if(timenow < data->probedelay)
 604                         *delay = (int)(data->probedelay - timenow);
 605                 else    *delay = 0;
 606         }
 607         *tA = (int)data->timeout_A;
 608         *tAAAA = (int)data->timeout_AAAA;
 609         *tother = (int)data->timeout_other;
 610         lock_rw_unlock(&e->lock);
 611         return ttl;
 612 }
 613
 614 int
 615 infra_edns_update(struct infra_cache* infra, struct sockaddr_storage* addr,
 616         socklen_t addrlen, uint8_t* nm, size_t nmlen, int edns_version,
 617         time_t timenow)
 618 {
 619         struct lruhash_entry* e = infra_lookup_nottl(infra, addr, addrlen,
 620                 nm, nmlen, 1);
 621         struct infra_data* data;
 622         int needtoinsert = 0;
 623         if(!e) {
 624                 if(!(e = new_entry(infra, addr, addrlen, nm, nmlen, timenow)))
 625                         return 0;
 626                 needtoinsert = 1;
 627         } else if(((struct infra_data*)e->data)->ttl < timenow) {
 628                 data_entry_init(infra, e, timenow);
 629         }
 630         /* have an entry, update the rtt, and the ttl */
 631         data = (struct infra_data*)e->data;
 632         /* do not update if noEDNS and stored is yesEDNS */
 633         if(!(edns_version == -1 && (data->edns_version != -1 &&
 634                 data->edns_lame_known))) {
 635                 data->edns_version = edns_version;
 636                 data->edns_lame_known = 1;
 637         }
 638
 639         if(needtoinsert)
 640                 slabhash_insert(infra->hosts, e->hash, e, e->data, NULL);
 641         else    { lock_rw_unlock(&e->lock); }
 642         return 1;
 643 }
 644
 645 int
 646 infra_get_lame_rtt(struct infra_cache* infra,
 647         struct sockaddr_storage* addr, socklen_t addrlen,
 648         uint8_t* name, size_t namelen, uint16_t qtype,
 649         int* lame, int* dnsseclame, int* reclame, int* rtt, time_t timenow)
 650 {
 651         struct infra_data* host;
 652         struct lruhash_entry* e = infra_lookup_nottl(infra, addr, addrlen,
 653                 name, namelen, 0);
 654         if(!e)
 655                 return 0;
 656         host = (struct infra_data*)e->data;
 657         *rtt = rtt_unclamped(&host->rtt);
 658         if(host->rtt.rto >= PROBE_MAXRTO && timenow < host->probedelay
 659                 && rtt_notimeout(&host->rtt)*4 <= host->rtt.rto) {
 660                 /* single probe for this domain, and we are not probing */
 661                 /* unless the query type allows a probe to happen */
 662                 if(qtype == LDNS_RR_TYPE_A) {
 663                         if(host->timeout_A >= TIMEOUT_COUNT_MAX)
 664                                 *rtt = USEFUL_SERVER_TOP_TIMEOUT;
 665                         else    *rtt = USEFUL_SERVER_TOP_TIMEOUT-1000;
 666                 } else if(qtype == LDNS_RR_TYPE_AAAA) {
 667                         if(host->timeout_AAAA >= TIMEOUT_COUNT_MAX)
 668                                 *rtt = USEFUL_SERVER_TOP_TIMEOUT;
 669                         else    *rtt = USEFUL_SERVER_TOP_TIMEOUT-1000;
 670                 } else {
 671                         if(host->timeout_other >= TIMEOUT_COUNT_MAX)
 672                                 *rtt = USEFUL_SERVER_TOP_TIMEOUT;
 673                         else    *rtt = USEFUL_SERVER_TOP_TIMEOUT-1000;
 674                 }
 675         }
 676         if(timenow > host->ttl) {
 677                 /* expired entry */
 678                 /* see if this can be a re-probe of an unresponsive server */
 679                 /* minus 1000 because that is outside of the RTTBAND, so
 680                  * blacklisted servers stay blacklisted if this is chosen */
 681                 if(host->rtt.rto >= USEFUL_SERVER_TOP_TIMEOUT) {
 682                         lock_rw_unlock(&e->lock);
 683                         *rtt = USEFUL_SERVER_TOP_TIMEOUT-1000;
 684                         *lame = 0;
 685                         *dnsseclame = 0;
 686                         *reclame = 0;
 687                         return 1;
 688                 }
 689                 lock_rw_unlock(&e->lock);
 690                 return 0;
 691         }
 692         /* check lameness first */
 693         if(host->lame_type_A && qtype == LDNS_RR_TYPE_A) {
 694                 lock_rw_unlock(&e->lock);
 695                 *lame = 1;
 696                 *dnsseclame = 0;
 697                 *reclame = 0;
 698                 return 1;
 699         } else if(host->lame_other && qtype != LDNS_RR_TYPE_A) {
 700                 lock_rw_unlock(&e->lock);
 701                 *lame = 1;
 702                 *dnsseclame = 0;
 703                 *reclame = 0;
 704                 return 1;
 705         } else if(host->isdnsseclame) {
 706                 lock_rw_unlock(&e->lock);
 707                 *lame = 0;
 708                 *dnsseclame = 1;
 709                 *reclame = 0;
 710                 return 1;
 711         } else if(host->rec_lame) {
 712                 lock_rw_unlock(&e->lock);
 713                 *lame = 0;
 714                 *dnsseclame = 0;
 715                 *reclame = 1;
 716                 return 1;
 717         }
 718         /* no lameness for this type of query */
 719         lock_rw_unlock(&e->lock);
 720         *lame = 0;
 721         *dnsseclame = 0;
 722         *reclame = 0;
 723         return 1;
 724 }
 725
 726 int infra_find_ratelimit(struct infra_cache* infra, uint8_t* name,
 727         size_t namelen)
 728 {
 729         int labs = dname_count_labels(name);
 730         struct domain_limit_data* d = (struct domain_limit_data*)
 731                 name_tree_lookup(&infra->domain_limits, name, namelen, labs,
 732                 LDNS_RR_CLASS_IN);
 733         if(!d) return infra_dp_ratelimit;
 734
 735         if(d->node.labs == labs && d->lim != -1)
 736                 return d->lim; /* exact match */
 737
 738         /* find 'below match' */
 739         if(d->node.labs == labs)
 740                 d = (struct domain_limit_data*)d->node.parent;
 741         while(d) {
 742                 if(d->below != -1)
 743                         return d->below;
 744                 d = (struct domain_limit_data*)d->node.parent;
 745         }
 746         return infra_dp_ratelimit;
 747 }
 748
 749 size_t ip_rate_sizefunc(void* k, void* ATTR_UNUSED(d))
 750 {
 751         struct ip_rate_key* key = (struct ip_rate_key*)k;
 752         return sizeof(*key) + sizeof(struct ip_rate_data)
 753                 + lock_get_mem(&key->entry.lock);
 754 }
 755
 756 int ip_rate_compfunc(void* key1, void* key2)
 757 {
 758         struct ip_rate_key* k1 = (struct ip_rate_key*)key1;
 759         struct ip_rate_key* k2 = (struct ip_rate_key*)key2;
 760         return sockaddr_cmp_addr(&k1->addr, k1->addrlen,
 761                 &k2->addr, k2->addrlen);
 762 }
 763
 764 void ip_rate_delkeyfunc(void* k, void* ATTR_UNUSED(arg))
 765 {
 766         struct ip_rate_key* key = (struct ip_rate_key*)k;
 767         if(!key)
 768                 return;
 769         lock_rw_destroy(&key->entry.lock);
 770         free(key);
 771 }
 772
 773 /** find data item in array, for write access, caller unlocks */
 774 static struct lruhash_entry* infra_find_ratedata(struct infra_cache* infra,
 775         uint8_t* name, size_t namelen, int wr)
 776 {
 777         struct rate_key key;
 778         hashvalue_type h = dname_query_hash(name, 0xab);
 779         memset(&key, 0, sizeof(key));
 780         key.name = name;
 781         key.namelen = namelen;
 782         key.entry.hash = h;
 783         return slabhash_lookup(infra->domain_rates, h, &key, wr);
 784 }
 785
 786 /** find data item in array for ip addresses */
 787 static struct lruhash_entry* infra_find_ip_ratedata(struct infra_cache* infra,
 788         struct comm_reply* repinfo, int wr)
 789 {
 790         struct ip_rate_key key;
 791         hashvalue_type h = hash_addr(&(repinfo->addr),
 792                 repinfo->addrlen, 0);
 793         memset(&key, 0, sizeof(key));
 794         key.addr = repinfo->addr;
 795         key.addrlen = repinfo->addrlen;
 796         key.entry.hash = h;
 797         return slabhash_lookup(infra->client_ip_rates, h, &key, wr);
 798 }
 799
 800 /** create rate data item for name, number 1 in now */
 801 static void infra_create_ratedata(struct infra_cache* infra,
 802         uint8_t* name, size_t namelen, time_t timenow)
 803 {
 804         hashvalue_type h = dname_query_hash(name, 0xab);
 805         struct rate_key* k = (struct rate_key*)calloc(1, sizeof(*k));
 806         struct rate_data* d = (struct rate_data*)calloc(1, sizeof(*d));
 807         if(!k || !d) {
 808                 free(k);
 809                 free(d);
 810                 return; /* alloc failure */
 811         }
 812         k->namelen = namelen;
 813         k->name = memdup(name, namelen);
 814         if(!k->name) {
 815                 free(k);
 816                 free(d);
 817                 return; /* alloc failure */
 818         }
 819         lock_rw_init(&k->entry.lock);
 820         k->entry.hash = h;
 821         k->entry.key = k;
 822         k->entry.data = d;
 823         d->qps[0] = 1;
 824         d->timestamp[0] = timenow;
 825         slabhash_insert(infra->domain_rates, h, &k->entry, d, NULL);
 826 }
 827
 828 /** create rate data item for ip address */
 829 static void infra_ip_create_ratedata(struct infra_cache* infra,
 830         struct comm_reply* repinfo, time_t timenow)
 831 {
 832         hashvalue_type h = hash_addr(&(repinfo->addr),
 833         repinfo->addrlen, 0);
 834         struct ip_rate_key* k = (struct ip_rate_key*)calloc(1, sizeof(*k));
 835         struct ip_rate_data* d = (struct ip_rate_data*)calloc(1, sizeof(*d));
 836         if(!k || !d) {
 837                 free(k);
 838                 free(d);
 839                 return; /* alloc failure */
 840         }
 841         k->addr = repinfo->addr;
 842         k->addrlen = repinfo->addrlen;
 843         lock_rw_init(&k->entry.lock);
 844         k->entry.hash = h;
 845         k->entry.key = k;
 846         k->entry.data = d;
 847         d->qps[0] = 1;
 848         d->timestamp[0] = timenow;
 849         slabhash_insert(infra->client_ip_rates, h, &k->entry, d, NULL);
 850 }
 851
 852 /** find the second and return its rate counter, if none, remove oldest */
 853 static int* infra_rate_find_second(void* data, time_t t)
 854 {
 855         struct rate_data* d = (struct rate_data*)data;
 856         int i, oldest;
 857         for(i=0; i<RATE_WINDOW; i++) {
 858                 if(d->timestamp[i] == t)
 859                         return &(d->qps[i]);
 860         }
 861         /* remove oldest timestamp, and insert it at t with 0 qps */
 862         oldest = 0;
 863         for(i=0; i<RATE_WINDOW; i++) {
 864                 if(d->timestamp[i] < d->timestamp[oldest])
 865                         oldest = i;
 866         }
 867         d->timestamp[oldest] = t;
 868         d->qps[oldest] = 0;
 869         return &(d->qps[oldest]);
 870 }
 871
 872 int infra_rate_max(void* data, time_t now)
 873 {
 874         struct rate_data* d = (struct rate_data*)data;
 875         int i, max = 0;
 876         for(i=0; i<RATE_WINDOW; i++) {
 877                 if(now-d->timestamp[i] <= RATE_WINDOW) {
 878                         if(d->qps[i] > max)
 879                                 max = d->qps[i];
 880                 }
 881         }
 882         return max;
 883 }
 884
 885 int infra_ratelimit_inc(struct infra_cache* infra, uint8_t* name,
 886         size_t namelen, time_t timenow)
 887 {
 888         int lim, max;
 889         struct lruhash_entry* entry;
 890
 891         if(!infra_dp_ratelimit)
 892                 return 1; /* not enabled */
 893
 894         /* find ratelimit */
 895         lim = infra_find_ratelimit(infra, name, namelen);
 896
 897         /* find or insert ratedata */
 898         entry = infra_find_ratedata(infra, name, namelen, 1);
 899         if(entry) {
 900                 int premax = infra_rate_max(entry->data, timenow);
 901                 int* cur = infra_rate_find_second(entry->data, timenow);
 902                 (*cur)++;
 903                 max = infra_rate_max(entry->data, timenow);
 904                 lock_rw_unlock(&entry->lock);
 905
 906                 if(premax < lim && max >= lim) {
 907                         char buf[257];
 908                         dname_str(name, buf);
 909                         verbose(VERB_OPS, "ratelimit exceeded %s %d", buf, lim);
 910                 }
 911                 return (max < lim);
 912         }
 913
 914         /* create */
 915         infra_create_ratedata(infra, name, namelen, timenow);
 916         return (1 < lim);
 917 }
 918
 919 void infra_ratelimit_dec(struct infra_cache* infra, uint8_t* name,
 920         size_t namelen, time_t timenow)
 921 {
 922         struct lruhash_entry* entry;
 923         int* cur;
 924         if(!infra_dp_ratelimit)
 925                 return; /* not enabled */
 926         entry = infra_find_ratedata(infra, name, namelen, 1);
 927         if(!entry) return; /* not cached */
 928         cur = infra_rate_find_second(entry->data, timenow);
 929         if((*cur) > 0)
 930                 (*cur)--;
 931         lock_rw_unlock(&entry->lock);
 932 }
 933
 934 int infra_ratelimit_exceeded(struct infra_cache* infra, uint8_t* name,
 935         size_t namelen, time_t timenow)
 936 {
 937         struct lruhash_entry* entry;
 938         int lim, max;
 939         if(!infra_dp_ratelimit)
 940                 return 0; /* not enabled */
 941
 942         /* find ratelimit */
 943         lim = infra_find_ratelimit(infra, name, namelen);
 944
 945         /* find current rate */
 946         entry = infra_find_ratedata(infra, name, namelen, 0);
 947         if(!entry)
 948                 return 0; /* not cached */
 949         max = infra_rate_max(entry->data, timenow);
 950         lock_rw_unlock(&entry->lock);
 951
 952         return (max >= lim);
 953 }
 954
 955 size_t
 956 infra_get_mem(struct infra_cache* infra)
 957 {
 958         size_t s = sizeof(*infra) + slabhash_get_mem(infra->hosts);
 959         if(infra->domain_rates) s += slabhash_get_mem(infra->domain_rates);
 960         if(infra->client_ip_rates) s += slabhash_get_mem(infra->client_ip_rates);
 961         /* ignore domain_limits because walk through tree is big */
 962         return s;
 963 }
 964
 965 int infra_ip_ratelimit_inc(struct infra_cache* infra,
 966   struct comm_reply* repinfo, time_t timenow)
 967 {
 968         int max;
 969         struct lruhash_entry* entry;
 970
 971         /* not enabled */
 972         if(!infra_ip_ratelimit) {
 973                 return 1;
 974         }
 975         /* find or insert ratedata */
 976         entry = infra_find_ip_ratedata(infra, repinfo, 1);
 977         if(entry) {
 978                 int premax = infra_rate_max(entry->data, timenow);
 979                 int* cur = infra_rate_find_second(entry->data, timenow);
 980                 (*cur)++;
 981                 max = infra_rate_max(entry->data, timenow);
 982                 lock_rw_unlock(&entry->lock);
 983
 984                 if(premax < infra_ip_ratelimit && max >= infra_ip_ratelimit) {
 985                         char client_ip[128];
 986                         addr_to_str((struct sockaddr_storage *)&repinfo->addr,
 987                                 repinfo->addrlen, client_ip, sizeof(client_ip));
 988                         verbose(VERB_OPS, "ratelimit exceeded %s %d", client_ip,
 989                                 infra_ip_ratelimit);
 990                 }
 991                 return (max <= infra_ip_ratelimit);
 992         }
 993
 994         /* create */
 995         infra_ip_create_ratedata(infra, repinfo, timenow);
 996         return 1;
 997 }