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         infra->domain_rates = slabhash_create(cfg->ratelimit_slabs,
 236                 INFRA_HOST_STARTSIZE, cfg->ratelimit_size,
 237                 &rate_sizefunc, &rate_compfunc, &rate_delkeyfunc,
 238                 &rate_deldatafunc, NULL);
 239         if(!infra->domain_rates) {
 240                 infra_delete(infra);
 241                 return NULL;
 242         }
 243         /* insert config data into ratelimits */
 244         if(!infra_ratelimit_cfg_insert(infra, cfg)) {
 245                 infra_delete(infra);
 246                 return NULL;
 247         }
 248         name_tree_init_parents(&infra->domain_limits);
 249         infra_ip_ratelimit = cfg->ip_ratelimit;
 250         infra->client_ip_rates = slabhash_create(cfg->ip_ratelimit_slabs,
 251             INFRA_HOST_STARTSIZE, cfg->ip_ratelimit_size, &ip_rate_sizefunc,
 252             &ip_rate_compfunc, &ip_rate_delkeyfunc, &ip_rate_deldatafunc, NULL);
 253         if(!infra->client_ip_rates) {
 254                 infra_delete(infra);
 255                 return NULL;
 256         }
 257         return infra;
 258 }
 259
 260 /** delete domain_limit entries */
 261 static void domain_limit_free(rbnode_type* n, void* ATTR_UNUSED(arg))
 262 {
 263         if(n) {
 264                 free(((struct domain_limit_data*)n)->node.name);
 265                 free(n);
 266         }
 267 }
 268
 269 void
 270 infra_delete(struct infra_cache* infra)
 271 {
 272         if(!infra)
 273                 return;
 274         slabhash_delete(infra->hosts);
 275         slabhash_delete(infra->domain_rates);
 276         traverse_postorder(&infra->domain_limits, domain_limit_free, NULL);
 277         slabhash_delete(infra->client_ip_rates);
 278         free(infra);
 279 }
 280
 281 struct infra_cache*
 282 infra_adjust(struct infra_cache* infra, struct config_file* cfg)
 283 {
 284         size_t maxmem;
 285         if(!infra)
 286                 return infra_create(cfg);
 287         infra->host_ttl = cfg->host_ttl;
 288         maxmem = cfg->infra_cache_numhosts * (sizeof(struct infra_key)+
 289                 sizeof(struct infra_data)+INFRA_BYTES_NAME);
 290         if(maxmem != slabhash_get_size(infra->hosts) ||
 291                 cfg->infra_cache_slabs != infra->hosts->size) {
 292                 infra_delete(infra);
 293                 infra = infra_create(cfg);
 294         }
 295         return infra;
 296 }
 297
 298 /** calculate the hash value for a host key
 299  *  set use_port to a non-0 number to use the port in
 300  *  the hash calculation; 0 to ignore the port.*/
 301 static hashvalue_type
 302 hash_addr(struct sockaddr_storage* addr, socklen_t addrlen,
 303   int use_port)
 304 {
 305         hashvalue_type h = 0xab;
 306         /* select the pieces to hash, some OS have changing data inside */
 307         if(addr_is_ip6(addr, addrlen)) {
 308                 struct sockaddr_in6* in6 = (struct sockaddr_in6*)addr;
 309                 h = hashlittle(&in6->sin6_family, sizeof(in6->sin6_family), h);
 310                 if(use_port){
 311                         h = hashlittle(&in6->sin6_port, sizeof(in6->sin6_port), h);
 312                 }
 313                 h = hashlittle(&in6->sin6_addr, INET6_SIZE, h);
 314         } else {
 315                 struct sockaddr_in* in = (struct sockaddr_in*)addr;
 316                 h = hashlittle(&in->sin_family, sizeof(in->sin_family), h);
 317                 if(use_port){
 318                         h = hashlittle(&in->sin_port, sizeof(in->sin_port), h);
 319                 }
 320                 h = hashlittle(&in->sin_addr, INET_SIZE, h);
 321         }
 322         return h;
 323 }
 324
 325 /** calculate infra hash for a key */
 326 static hashvalue_type
 327 hash_infra(struct sockaddr_storage* addr, socklen_t addrlen, uint8_t* name)
 328 {
 329         return dname_query_hash(name, hash_addr(addr, addrlen, 1));
 330 }
 331
 332 /** lookup version that does not check host ttl (you check it) */
 333 struct lruhash_entry*
 334 infra_lookup_nottl(struct infra_cache* infra, struct sockaddr_storage* addr,
 335         socklen_t addrlen, uint8_t* name, size_t namelen, int wr)
 336 {
 337         struct infra_key k;
 338         k.addrlen = addrlen;
 339         memcpy(&k.addr, addr, addrlen);
 340         k.namelen = namelen;
 341         k.zonename = name;
 342         k.entry.hash = hash_infra(addr, addrlen, name);
 343         k.entry.key = (void*)&k;
 344         k.entry.data = NULL;
 345         return slabhash_lookup(infra->hosts, k.entry.hash, &k, wr);
 346 }
 347
 348 /** init the data elements */
 349 static void
 350 data_entry_init(struct infra_cache* infra, struct lruhash_entry* e,
 351         time_t timenow)
 352 {
 353         struct infra_data* data = (struct infra_data*)e->data;
 354         data->ttl = timenow + infra->host_ttl;
 355         rtt_init(&data->rtt);
 356         data->edns_version = 0;
 357         data->edns_lame_known = 0;
 358         data->probedelay = 0;
 359         data->isdnsseclame = 0;
 360         data->rec_lame = 0;
 361         data->lame_type_A = 0;
 362         data->lame_other = 0;
 363         data->timeout_A = 0;
 364         data->timeout_AAAA = 0;
 365         data->timeout_other = 0;
 366 }
 367
 368 /**
 369  * Create and init a new entry for a host
 370  * @param infra: infra structure with config parameters.
 371  * @param addr: host address.
 372  * @param addrlen: length of addr.
 373  * @param name: name of zone
 374  * @param namelen: length of name.
 375  * @param tm: time now.
 376  * @return: the new entry or NULL on malloc failure.
 377  */
 378 static struct lruhash_entry*
 379 new_entry(struct infra_cache* infra, struct sockaddr_storage* addr,
 380         socklen_t addrlen, uint8_t* name, size_t namelen, time_t tm)
 381 {
 382         struct infra_data* data;
 383         struct infra_key* key = (struct infra_key*)malloc(sizeof(*key));
 384         if(!key)
 385                 return NULL;
 386         data = (struct infra_data*)malloc(sizeof(struct infra_data));
 387         if(!data) {
 388                 free(key);
 389                 return NULL;
 390         }
 391         key->zonename = memdup(name, namelen);
 392         if(!key->zonename) {
 393                 free(key);
 394                 free(data);
 395                 return NULL;
 396         }
 397         key->namelen = namelen;
 398         lock_rw_init(&key->entry.lock);
 399         key->entry.hash = hash_infra(addr, addrlen, name);
 400         key->entry.key = (void*)key;
 401         key->entry.data = (void*)data;
 402         key->addrlen = addrlen;
 403         memcpy(&key->addr, addr, addrlen);
 404         data_entry_init(infra, &key->entry, tm);
 405         return &key->entry;
 406 }
 407
 408 int
 409 infra_host(struct infra_cache* infra, struct sockaddr_storage* addr,
 410         socklen_t addrlen, uint8_t* nm, size_t nmlen, time_t timenow,
 411         int* edns_vs, uint8_t* edns_lame_known, int* to)
 412 {
 413         struct lruhash_entry* e = infra_lookup_nottl(infra, addr, addrlen,
 414                 nm, nmlen, 0);
 415         struct infra_data* data;
 416         int wr = 0;
 417         if(e && ((struct infra_data*)e->data)->ttl < timenow) {
 418                 /* it expired, try to reuse existing entry */
 419                 int old = ((struct infra_data*)e->data)->rtt.rto;
 420                 uint8_t tA = ((struct infra_data*)e->data)->timeout_A;
 421                 uint8_t tAAAA = ((struct infra_data*)e->data)->timeout_AAAA;
 422                 uint8_t tother = ((struct infra_data*)e->data)->timeout_other;
 423                 lock_rw_unlock(&e->lock);
 424                 e = infra_lookup_nottl(infra, addr, addrlen, nm, nmlen, 1);
 425                 if(e) {
 426                         /* if its still there we have a writelock, init */
 427                         /* re-initialise */
 428                         /* do not touch lameness, it may be valid still */
 429                         data_entry_init(infra, e, timenow);
 430                         wr = 1;
 431                         /* TOP_TIMEOUT remains on reuse */
 432                         if(old >= USEFUL_SERVER_TOP_TIMEOUT) {
 433                                 ((struct infra_data*)e->data)->rtt.rto
 434                                         = USEFUL_SERVER_TOP_TIMEOUT;
 435                                 ((struct infra_data*)e->data)->timeout_A = tA;
 436                                 ((struct infra_data*)e->data)->timeout_AAAA = tAAAA;
 437                                 ((struct infra_data*)e->data)->timeout_other = tother;
 438                         }
 439                 }
 440         }
 441         if(!e) {
 442                 /* insert new entry */
 443                 if(!(e = new_entry(infra, addr, addrlen, nm, nmlen, timenow)))
 444                         return 0;
 445                 data = (struct infra_data*)e->data;
 446                 *edns_vs = data->edns_version;
 447                 *edns_lame_known = data->edns_lame_known;
 448                 *to = rtt_timeout(&data->rtt);
 449                 slabhash_insert(infra->hosts, e->hash, e, data, NULL);
 450                 return 1;
 451         }
 452         /* use existing entry */
 453         data = (struct infra_data*)e->data;
 454         *edns_vs = data->edns_version;
 455         *edns_lame_known = data->edns_lame_known;
 456         *to = rtt_timeout(&data->rtt);
 457         if(*to >= PROBE_MAXRTO && rtt_notimeout(&data->rtt)*4 <= *to) {
 458                 /* delay other queries, this is the probe query */
 459                 if(!wr) {
 460                         lock_rw_unlock(&e->lock);
 461                         e = infra_lookup_nottl(infra, addr,addrlen,nm,nmlen, 1);
 462                         if(!e) { /* flushed from cache real fast, no use to
 463                                 allocate just for the probedelay */
 464                                 return 1;
 465                         }
 466                         data = (struct infra_data*)e->data;
 467                 }
 468                 /* add 999 to round up the timeout value from msec to sec,
 469                  * then add a whole second so it is certain that this probe
 470                  * has timed out before the next is allowed */
 471                 data->probedelay = timenow + ((*to)+1999)/1000;
 472         }
 473         lock_rw_unlock(&e->lock);
 474         return 1;
 475 }
 476
 477 int
 478 infra_set_lame(struct infra_cache* infra, struct sockaddr_storage* addr,
 479         socklen_t addrlen, uint8_t* nm, size_t nmlen, time_t timenow,
 480         int dnsseclame, int reclame, uint16_t qtype)
 481 {
 482         struct infra_data* data;
 483         struct lruhash_entry* e;
 484         int needtoinsert = 0;
 485         e = infra_lookup_nottl(infra, addr, addrlen, nm, nmlen, 1);
 486         if(!e) {
 487                 /* insert it */
 488                 if(!(e = new_entry(infra, addr, addrlen, nm, nmlen, timenow))) {
 489                         log_err("set_lame: malloc failure");
 490                         return 0;
 491                 }
 492                 needtoinsert = 1;
 493         } else if( ((struct infra_data*)e->data)->ttl < timenow) {
 494                 /* expired, reuse existing entry */
 495                 data_entry_init(infra, e, timenow);
 496         }
 497         /* got an entry, now set the zone lame */
 498         data = (struct infra_data*)e->data;
 499         /* merge data (if any) */
 500         if(dnsseclame)
 501                 data->isdnsseclame = 1;
 502         if(reclame)
 503                 data->rec_lame = 1;
 504         if(!dnsseclame && !reclame && qtype == LDNS_RR_TYPE_A)
 505                 data->lame_type_A = 1;
 506         if(!dnsseclame  && !reclame && qtype != LDNS_RR_TYPE_A)
 507                 data->lame_other = 1;
 508         /* done */
 509         if(needtoinsert)
 510                 slabhash_insert(infra->hosts, e->hash, e, e->data, NULL);
 511         else    { lock_rw_unlock(&e->lock); }
 512         return 1;
 513 }
 514
 515 void
 516 infra_update_tcp_works(struct infra_cache* infra,
 517         struct sockaddr_storage* addr, socklen_t addrlen, uint8_t* nm,
 518         size_t nmlen)
 519 {
 520         struct lruhash_entry* e = infra_lookup_nottl(infra, addr, addrlen,
 521                 nm, nmlen, 1);
 522         struct infra_data* data;
 523         if(!e)
 524                 return; /* doesn't exist */
 525         data = (struct infra_data*)e->data;
 526         if(data->rtt.rto >= RTT_MAX_TIMEOUT)
 527                 /* do not disqualify this server altogether, it is better
 528                  * than nothing */
 529                 data->rtt.rto = RTT_MAX_TIMEOUT-1000;
 530         lock_rw_unlock(&e->lock);
 531 }
 532
 533 int
 534 infra_rtt_update(struct infra_cache* infra, struct sockaddr_storage* addr,
 535         socklen_t addrlen, uint8_t* nm, size_t nmlen, int qtype,
 536         int roundtrip, int orig_rtt, time_t timenow)
 537 {
 538         struct lruhash_entry* e = infra_lookup_nottl(infra, addr, addrlen,
 539                 nm, nmlen, 1);
 540         struct infra_data* data;
 541         int needtoinsert = 0;
 542         int rto = 1;
 543         if(!e) {
 544                 if(!(e = new_entry(infra, addr, addrlen, nm, nmlen, timenow)))
 545                         return 0;
 546                 needtoinsert = 1;
 547         } else if(((struct infra_data*)e->data)->ttl < timenow) {
 548                 data_entry_init(infra, e, timenow);
 549         }
 550         /* have an entry, update the rtt */
 551         data = (struct infra_data*)e->data;
 552         if(roundtrip == -1) {
 553                 rtt_lost(&data->rtt, orig_rtt);
 554                 if(qtype == LDNS_RR_TYPE_A) {
 555                         if(data->timeout_A < TIMEOUT_COUNT_MAX)
 556                                 data->timeout_A++;
 557                 } else if(qtype == LDNS_RR_TYPE_AAAA) {
 558                         if(data->timeout_AAAA < TIMEOUT_COUNT_MAX)
 559                                 data->timeout_AAAA++;
 560                 } else {
 561                         if(data->timeout_other < TIMEOUT_COUNT_MAX)
 562                                 data->timeout_other++;
 563                 }
 564         } else {
 565                 /* if we got a reply, but the old timeout was above server
 566                  * selection height, delete the timeout so the server is
 567                  * fully available again */
 568                 if(rtt_unclamped(&data->rtt) >= USEFUL_SERVER_TOP_TIMEOUT)
 569                         rtt_init(&data->rtt);
 570                 rtt_update(&data->rtt, roundtrip);
 571                 data->probedelay = 0;
 572                 if(qtype == LDNS_RR_TYPE_A)
 573                         data->timeout_A = 0;
 574                 else if(qtype == LDNS_RR_TYPE_AAAA)
 575                         data->timeout_AAAA = 0;
 576                 else    data->timeout_other = 0;
 577         }
 578         if(data->rtt.rto > 0)
 579                 rto = data->rtt.rto;
 580
 581         if(needtoinsert)
 582                 slabhash_insert(infra->hosts, e->hash, e, e->data, NULL);
 583         else    { lock_rw_unlock(&e->lock); }
 584         return rto;
 585 }
 586
 587 long long infra_get_host_rto(struct infra_cache* infra,
 588         struct sockaddr_storage* addr, socklen_t addrlen, uint8_t* nm,
 589         size_t nmlen, struct rtt_info* rtt, int* delay, time_t timenow,
 590         int* tA, int* tAAAA, int* tother)
 591 {
 592         struct lruhash_entry* e = infra_lookup_nottl(infra, addr, addrlen,
 593                 nm, nmlen, 0);
 594         struct infra_data* data;
 595         long long ttl = -2;
 596         if(!e) return -1;
 597         data = (struct infra_data*)e->data;
 598         if(data->ttl >= timenow) {
 599                 ttl = (long long)(data->ttl - timenow);
 600                 memmove(rtt, &data->rtt, sizeof(*rtt));
 601                 if(timenow < data->probedelay)
 602                         *delay = (int)(data->probedelay - timenow);
 603                 else    *delay = 0;
 604         }
 605         *tA = (int)data->timeout_A;
 606         *tAAAA = (int)data->timeout_AAAA;
 607         *tother = (int)data->timeout_other;
 608         lock_rw_unlock(&e->lock);
 609         return ttl;
 610 }
 611
 612 int
 613 infra_edns_update(struct infra_cache* infra, struct sockaddr_storage* addr,
 614         socklen_t addrlen, uint8_t* nm, size_t nmlen, int edns_version,
 615         time_t timenow)
 616 {
 617         struct lruhash_entry* e = infra_lookup_nottl(infra, addr, addrlen,
 618                 nm, nmlen, 1);
 619         struct infra_data* data;
 620         int needtoinsert = 0;
 621         if(!e) {
 622                 if(!(e = new_entry(infra, addr, addrlen, nm, nmlen, timenow)))
 623                         return 0;
 624                 needtoinsert = 1;
 625         } else if(((struct infra_data*)e->data)->ttl < timenow) {
 626                 data_entry_init(infra, e, timenow);
 627         }
 628         /* have an entry, update the rtt, and the ttl */
 629         data = (struct infra_data*)e->data;
 630         /* do not update if noEDNS and stored is yesEDNS */
 631         if(!(edns_version == -1 && (data->edns_version != -1 &&
 632                 data->edns_lame_known))) {
 633                 data->edns_version = edns_version;
 634                 data->edns_lame_known = 1;
 635         }
 636
 637         if(needtoinsert)
 638                 slabhash_insert(infra->hosts, e->hash, e, e->data, NULL);
 639         else    { lock_rw_unlock(&e->lock); }
 640         return 1;
 641 }
 642
 643 int
 644 infra_get_lame_rtt(struct infra_cache* infra,
 645         struct sockaddr_storage* addr, socklen_t addrlen,
 646         uint8_t* name, size_t namelen, uint16_t qtype,
 647         int* lame, int* dnsseclame, int* reclame, int* rtt, time_t timenow)
 648 {
 649         struct infra_data* host;
 650         struct lruhash_entry* e = infra_lookup_nottl(infra, addr, addrlen,
 651                 name, namelen, 0);
 652         if(!e)
 653                 return 0;
 654         host = (struct infra_data*)e->data;
 655         *rtt = rtt_unclamped(&host->rtt);
 656         if(host->rtt.rto >= PROBE_MAXRTO && timenow < host->probedelay
 657                 && rtt_notimeout(&host->rtt)*4 <= host->rtt.rto) {
 658                 /* single probe for this domain, and we are not probing */
 659                 /* unless the query type allows a probe to happen */
 660                 if(qtype == LDNS_RR_TYPE_A) {
 661                         if(host->timeout_A >= TIMEOUT_COUNT_MAX)
 662                                 *rtt = USEFUL_SERVER_TOP_TIMEOUT;
 663                         else    *rtt = USEFUL_SERVER_TOP_TIMEOUT-1000;
 664                 } else if(qtype == LDNS_RR_TYPE_AAAA) {
 665                         if(host->timeout_AAAA >= TIMEOUT_COUNT_MAX)
 666                                 *rtt = USEFUL_SERVER_TOP_TIMEOUT;
 667                         else    *rtt = USEFUL_SERVER_TOP_TIMEOUT-1000;
 668                 } else {
 669                         if(host->timeout_other >= TIMEOUT_COUNT_MAX)
 670                                 *rtt = USEFUL_SERVER_TOP_TIMEOUT;
 671                         else    *rtt = USEFUL_SERVER_TOP_TIMEOUT-1000;
 672                 }
 673         }
 674         if(timenow > host->ttl) {
 675                 /* expired entry */
 676                 /* see if this can be a re-probe of an unresponsive server */
 677                 /* minus 1000 because that is outside of the RTTBAND, so
 678                  * blacklisted servers stay blacklisted if this is chosen */
 679                 if(host->rtt.rto >= USEFUL_SERVER_TOP_TIMEOUT) {
 680                         lock_rw_unlock(&e->lock);
 681                         *rtt = USEFUL_SERVER_TOP_TIMEOUT-1000;
 682                         *lame = 0;
 683                         *dnsseclame = 0;
 684                         *reclame = 0;
 685                         return 1;
 686                 }
 687                 lock_rw_unlock(&e->lock);
 688                 return 0;
 689         }
 690         /* check lameness first */
 691         if(host->lame_type_A && qtype == LDNS_RR_TYPE_A) {
 692                 lock_rw_unlock(&e->lock);
 693                 *lame = 1;
 694                 *dnsseclame = 0;
 695                 *reclame = 0;
 696                 return 1;
 697         } else if(host->lame_other && qtype != LDNS_RR_TYPE_A) {
 698                 lock_rw_unlock(&e->lock);
 699                 *lame = 1;
 700                 *dnsseclame = 0;
 701                 *reclame = 0;
 702                 return 1;
 703         } else if(host->isdnsseclame) {
 704                 lock_rw_unlock(&e->lock);
 705                 *lame = 0;
 706                 *dnsseclame = 1;
 707                 *reclame = 0;
 708                 return 1;
 709         } else if(host->rec_lame) {
 710                 lock_rw_unlock(&e->lock);
 711                 *lame = 0;
 712                 *dnsseclame = 0;
 713                 *reclame = 1;
 714                 return 1;
 715         }
 716         /* no lameness for this type of query */
 717         lock_rw_unlock(&e->lock);
 718         *lame = 0;
 719         *dnsseclame = 0;
 720         *reclame = 0;
 721         return 1;
 722 }
 723
 724 int infra_find_ratelimit(struct infra_cache* infra, uint8_t* name,
 725         size_t namelen)
 726 {
 727         int labs = dname_count_labels(name);
 728         struct domain_limit_data* d = (struct domain_limit_data*)
 729                 name_tree_lookup(&infra->domain_limits, name, namelen, labs,
 730                 LDNS_RR_CLASS_IN);
 731         if(!d) return infra_dp_ratelimit;
 732
 733         if(d->node.labs == labs && d->lim != -1)
 734                 return d->lim; /* exact match */
 735
 736         /* find 'below match' */
 737         if(d->node.labs == labs)
 738                 d = (struct domain_limit_data*)d->node.parent;
 739         while(d) {
 740                 if(d->below != -1)
 741                         return d->below;
 742                 d = (struct domain_limit_data*)d->node.parent;
 743         }
 744         return infra_dp_ratelimit;
 745 }
 746
 747 size_t ip_rate_sizefunc(void* k, void* ATTR_UNUSED(d))
 748 {
 749         struct ip_rate_key* key = (struct ip_rate_key*)k;
 750         return sizeof(*key) + sizeof(struct ip_rate_data)
 751                 + lock_get_mem(&key->entry.lock);
 752 }
 753
 754 int ip_rate_compfunc(void* key1, void* key2)
 755 {
 756         struct ip_rate_key* k1 = (struct ip_rate_key*)key1;
 757         struct ip_rate_key* k2 = (struct ip_rate_key*)key2;
 758         return sockaddr_cmp_addr(&k1->addr, k1->addrlen,
 759                 &k2->addr, k2->addrlen);
 760 }
 761
 762 void ip_rate_delkeyfunc(void* k, void* ATTR_UNUSED(arg))
 763 {
 764         struct ip_rate_key* key = (struct ip_rate_key*)k;
 765         if(!key)
 766                 return;
 767         lock_rw_destroy(&key->entry.lock);
 768         free(key);
 769 }
 770
 771 /** find data item in array, for write access, caller unlocks */
 772 static struct lruhash_entry* infra_find_ratedata(struct infra_cache* infra,
 773         uint8_t* name, size_t namelen, int wr)
 774 {
 775         struct rate_key key;
 776         hashvalue_type h = dname_query_hash(name, 0xab);
 777         memset(&key, 0, sizeof(key));
 778         key.name = name;
 779         key.namelen = namelen;
 780         key.entry.hash = h;
 781         return slabhash_lookup(infra->domain_rates, h, &key, wr);
 782 }
 783
 784 /** find data item in array for ip addresses */
 785 static struct lruhash_entry* infra_find_ip_ratedata(struct infra_cache* infra,
 786         struct comm_reply* repinfo, int wr)
 787 {
 788         struct ip_rate_key key;
 789         hashvalue_type h = hash_addr(&(repinfo->addr),
 790                 repinfo->addrlen, 0);
 791         memset(&key, 0, sizeof(key));
 792         key.addr = repinfo->addr;
 793         key.addrlen = repinfo->addrlen;
 794         key.entry.hash = h;
 795         return slabhash_lookup(infra->client_ip_rates, h, &key, wr);
 796 }
 797
 798 /** create rate data item for name, number 1 in now */
 799 static void infra_create_ratedata(struct infra_cache* infra,
 800         uint8_t* name, size_t namelen, time_t timenow)
 801 {
 802         hashvalue_type h = dname_query_hash(name, 0xab);
 803         struct rate_key* k = (struct rate_key*)calloc(1, sizeof(*k));
 804         struct rate_data* d = (struct rate_data*)calloc(1, sizeof(*d));
 805         if(!k || !d) {
 806                 free(k);
 807                 free(d);
 808                 return; /* alloc failure */
 809         }
 810         k->namelen = namelen;
 811         k->name = memdup(name, namelen);
 812         if(!k->name) {
 813                 free(k);
 814                 free(d);
 815                 return; /* alloc failure */
 816         }
 817         lock_rw_init(&k->entry.lock);
 818         k->entry.hash = h;
 819         k->entry.key = k;
 820         k->entry.data = d;
 821         d->qps[0] = 1;
 822         d->timestamp[0] = timenow;
 823         slabhash_insert(infra->domain_rates, h, &k->entry, d, NULL);
 824 }
 825
 826 /** create rate data item for ip address */
 827 static void infra_ip_create_ratedata(struct infra_cache* infra,
 828         struct comm_reply* repinfo, time_t timenow)
 829 {
 830         hashvalue_type h = hash_addr(&(repinfo->addr),
 831         repinfo->addrlen, 0);
 832         struct ip_rate_key* k = (struct ip_rate_key*)calloc(1, sizeof(*k));
 833         struct ip_rate_data* d = (struct ip_rate_data*)calloc(1, sizeof(*d));
 834         if(!k || !d) {
 835                 free(k);
 836                 free(d);
 837                 return; /* alloc failure */
 838         }
 839         k->addr = repinfo->addr;
 840         k->addrlen = repinfo->addrlen;
 841         lock_rw_init(&k->entry.lock);
 842         k->entry.hash = h;
 843         k->entry.key = k;
 844         k->entry.data = d;
 845         d->qps[0] = 1;
 846         d->timestamp[0] = timenow;
 847         slabhash_insert(infra->client_ip_rates, h, &k->entry, d, NULL);
 848 }
 849
 850 /** find the second and return its rate counter, if none, remove oldest */
 851 static int* infra_rate_find_second(void* data, time_t t)
 852 {
 853         struct rate_data* d = (struct rate_data*)data;
 854         int i, oldest;
 855         for(i=0; i<RATE_WINDOW; i++) {
 856                 if(d->timestamp[i] == t)
 857                         return &(d->qps[i]);
 858         }
 859         /* remove oldest timestamp, and insert it at t with 0 qps */
 860         oldest = 0;
 861         for(i=0; i<RATE_WINDOW; i++) {
 862                 if(d->timestamp[i] < d->timestamp[oldest])
 863                         oldest = i;
 864         }
 865         d->timestamp[oldest] = t;
 866         d->qps[oldest] = 0;
 867         return &(d->qps[oldest]);
 868 }
 869
 870 int infra_rate_max(void* data, time_t now)
 871 {
 872         struct rate_data* d = (struct rate_data*)data;
 873         int i, max = 0;
 874         for(i=0; i<RATE_WINDOW; i++) {
 875                 if(now-d->timestamp[i] <= RATE_WINDOW) {
 876                         if(d->qps[i] > max)
 877                                 max = d->qps[i];
 878                 }
 879         }
 880         return max;
 881 }
 882
 883 int infra_ratelimit_inc(struct infra_cache* infra, uint8_t* name,
 884         size_t namelen, time_t timenow)
 885 {
 886         int lim, max;
 887         struct lruhash_entry* entry;
 888
 889         if(!infra_dp_ratelimit)
 890                 return 1; /* not enabled */
 891
 892         /* find ratelimit */
 893         lim = infra_find_ratelimit(infra, name, namelen);
 894         if(!lim)
 895                 return 1; /* disabled for this domain */
 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         if(!lim)
 945                 return 0; /* disabled for this domain */
 946
 947         /* find current rate */
 948         entry = infra_find_ratedata(infra, name, namelen, 0);
 949         if(!entry)
 950                 return 0; /* not cached */
 951         max = infra_rate_max(entry->data, timenow);
 952         lock_rw_unlock(&entry->lock);
 953
 954         return (max >= lim);
 955 }
 956
 957 size_t
 958 infra_get_mem(struct infra_cache* infra)
 959 {
 960         size_t s = sizeof(*infra) + slabhash_get_mem(infra->hosts);
 961         if(infra->domain_rates) s += slabhash_get_mem(infra->domain_rates);
 962         if(infra->client_ip_rates) s += slabhash_get_mem(infra->client_ip_rates);
 963         /* ignore domain_limits because walk through tree is big */
 964         return s;
 965 }
 966
 967 int infra_ip_ratelimit_inc(struct infra_cache* infra,
 968   struct comm_reply* repinfo, time_t timenow)
 969 {
 970         int max;
 971         struct lruhash_entry* entry;
 972
 973         /* not enabled */
 974         if(!infra_ip_ratelimit) {
 975                 return 1;
 976         }
 977         /* find or insert ratedata */
 978         entry = infra_find_ip_ratedata(infra, repinfo, 1);
 979         if(entry) {
 980                 int premax = infra_rate_max(entry->data, timenow);
 981                 int* cur = infra_rate_find_second(entry->data, timenow);
 982                 (*cur)++;
 983                 max = infra_rate_max(entry->data, timenow);
 984                 lock_rw_unlock(&entry->lock);
 985
 986                 if(premax < infra_ip_ratelimit && max >= infra_ip_ratelimit) {
 987                         char client_ip[128];
 988                         addr_to_str((struct sockaddr_storage *)&repinfo->addr,
 989                                 repinfo->addrlen, client_ip, sizeof(client_ip));
 990                         verbose(VERB_OPS, "ratelimit exceeded %s %d", client_ip,
 991                                 infra_ip_ratelimit);
 992                 }
 993                 return (max <= infra_ip_ratelimit);
 994         }
 995
 996         /* create */
 997         infra_ip_create_ratedata(infra, repinfo, timenow);
 998         return 1;
 999 }