src/resolve/resolved-dns-cache.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2014 Lennart Poettering
   7
   8   systemd is free software; you can redistribute it and/or modify it
   9   under the terms of the GNU Lesser General Public License as published by
  10   the Free Software Foundation; either version 2.1 of the License, or
  11   (at your option) any later version.
  12
  13   systemd is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   Lesser General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser General Public License
  19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  20 ***/
  21
  22 #include "alloc-util.h"
  23 #include "resolved-dns-cache.h"
  24 #include "resolved-dns-packet.h"
  25
  26 /* Never cache more than 1K entries */
  27 #define CACHE_MAX 1024
  28
  29 /* We never keep any item longer than 10min in our cache */
  30 #define CACHE_TTL_MAX_USEC (10 * USEC_PER_MINUTE)
  31
  32 typedef enum DnsCacheItemType DnsCacheItemType;
  33 typedef struct DnsCacheItem DnsCacheItem;
  34
  35 enum DnsCacheItemType {
  36         DNS_CACHE_POSITIVE,
  37         DNS_CACHE_NODATA,
  38         DNS_CACHE_NXDOMAIN,
  39 };
  40
  41 struct DnsCacheItem {
  42         DnsResourceKey *key;
  43         DnsResourceRecord *rr;
  44         usec_t until;
  45         DnsCacheItemType type;
  46         unsigned prioq_idx;
  47         int owner_family;
  48         union in_addr_union owner_address;
  49         LIST_FIELDS(DnsCacheItem, by_key);
  50 };
  51
  52 static void dns_cache_item_free(DnsCacheItem *i) {
  53         if (!i)
  54                 return;
  55
  56         dns_resource_record_unref(i->rr);
  57         dns_resource_key_unref(i->key);
  58         free(i);
  59 }
  60
  61 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsCacheItem*, dns_cache_item_free);
  62
  63 static void dns_cache_item_remove_and_free(DnsCache *c, DnsCacheItem *i) {
  64         DnsCacheItem *first;
  65
  66         assert(c);
  67
  68         if (!i)
  69                 return;
  70
  71         first = hashmap_get(c->by_key, i->key);
  72         LIST_REMOVE(by_key, first, i);
  73
  74         if (first)
  75                 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
  76         else
  77                 hashmap_remove(c->by_key, i->key);
  78
  79         prioq_remove(c->by_expiry, i, &i->prioq_idx);
  80
  81         dns_cache_item_free(i);
  82 }
  83
  84 void dns_cache_flush(DnsCache *c) {
  85         DnsCacheItem *i;
  86
  87         assert(c);
  88
  89         while ((i = hashmap_first(c->by_key)))
  90                 dns_cache_item_remove_and_free(c, i);
  91
  92         assert(hashmap_size(c->by_key) == 0);
  93         assert(prioq_size(c->by_expiry) == 0);
  94
  95         c->by_key = hashmap_free(c->by_key);
  96         c->by_expiry = prioq_free(c->by_expiry);
  97 }
  98
  99 static bool dns_cache_remove(DnsCache *c, DnsResourceKey *key) {
 100         DnsCacheItem *i;
 101         bool exist = false;
 102
 103         assert(c);
 104         assert(key);
 105
 106         while ((i = hashmap_get(c->by_key, key))) {
 107                 dns_cache_item_remove_and_free(c, i);
 108                 exist = true;
 109         }
 110
 111         return exist;
 112 }
 113
 114 static void dns_cache_make_space(DnsCache *c, unsigned add) {
 115         assert(c);
 116
 117         if (add <= 0)
 118                 return;
 119
 120         /* Makes space for n new entries. Note that we actually allow
 121          * the cache to grow beyond CACHE_MAX, but only when we shall
 122          * add more RRs to the cache than CACHE_MAX at once. In that
 123          * case the cache will be emptied completely otherwise. */
 124
 125         for (;;) {
 126                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
 127                 DnsCacheItem *i;
 128
 129                 if (prioq_size(c->by_expiry) <= 0)
 130                         break;
 131
 132                 if (prioq_size(c->by_expiry) + add < CACHE_MAX)
 133                         break;
 134
 135                 i = prioq_peek(c->by_expiry);
 136                 assert(i);
 137
 138                 /* Take an extra reference to the key so that it
 139                  * doesn't go away in the middle of the remove call */
 140                 key = dns_resource_key_ref(i->key);
 141                 dns_cache_remove(c, key);
 142         }
 143 }
 144
 145 void dns_cache_prune(DnsCache *c) {
 146         usec_t t = 0;
 147
 148         assert(c);
 149
 150         /* Remove all entries that are past their TTL */
 151
 152         for (;;) {
 153                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
 154                 DnsCacheItem *i;
 155
 156                 i = prioq_peek(c->by_expiry);
 157                 if (!i)
 158                         break;
 159
 160                 if (t <= 0)
 161                         t = now(clock_boottime_or_monotonic());
 162
 163                 if (i->until > t)
 164                         break;
 165
 166                 /* Take an extra reference to the key so that it
 167                  * doesn't go away in the middle of the remove call */
 168                 key = dns_resource_key_ref(i->key);
 169                 dns_cache_remove(c, key);
 170         }
 171 }
 172
 173 static int dns_cache_item_prioq_compare_func(const void *a, const void *b) {
 174         const DnsCacheItem *x = a, *y = b;
 175
 176         if (x->until < y->until)
 177                 return -1;
 178         if (x->until > y->until)
 179                 return 1;
 180         return 0;
 181 }
 182
 183 static int dns_cache_init(DnsCache *c) {
 184         int r;
 185
 186         assert(c);
 187
 188         r = prioq_ensure_allocated(&c->by_expiry, dns_cache_item_prioq_compare_func);
 189         if (r < 0)
 190                 return r;
 191
 192         r = hashmap_ensure_allocated(&c->by_key, &dns_resource_key_hash_ops);
 193         if (r < 0)
 194                 return r;
 195
 196         return r;
 197 }
 198
 199 static int dns_cache_link_item(DnsCache *c, DnsCacheItem *i) {
 200         DnsCacheItem *first;
 201         int r;
 202
 203         assert(c);
 204         assert(i);
 205
 206         r = prioq_put(c->by_expiry, i, &i->prioq_idx);
 207         if (r < 0)
 208                 return r;
 209
 210         first = hashmap_get(c->by_key, i->key);
 211         if (first) {
 212                 LIST_PREPEND(by_key, first, i);
 213                 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
 214         } else {
 215                 r = hashmap_put(c->by_key, i->key, i);
 216                 if (r < 0) {
 217                         prioq_remove(c->by_expiry, i, &i->prioq_idx);
 218                         return r;
 219                 }
 220         }
 221
 222         return 0;
 223 }
 224
 225 static DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) {
 226         DnsCacheItem *i;
 227
 228         assert(c);
 229         assert(rr);
 230
 231         LIST_FOREACH(by_key, i, hashmap_get(c->by_key, rr->key))
 232                 if (i->rr && dns_resource_record_equal(i->rr, rr) > 0)
 233                         return i;
 234
 235         return NULL;
 236 }
 237
 238 static void dns_cache_item_update_positive(DnsCache *c, DnsCacheItem *i, DnsResourceRecord *rr, usec_t timestamp) {
 239         assert(c);
 240         assert(i);
 241         assert(rr);
 242
 243         i->type = DNS_CACHE_POSITIVE;
 244
 245         if (!i->by_key_prev)
 246                 /* We are the first item in the list, we need to
 247                  * update the key used in the hashmap */
 248
 249                 assert_se(hashmap_replace(c->by_key, rr->key, i) >= 0);
 250
 251         dns_resource_record_ref(rr);
 252         dns_resource_record_unref(i->rr);
 253         i->rr = rr;
 254
 255         dns_resource_key_unref(i->key);
 256         i->key = dns_resource_key_ref(rr->key);
 257
 258         i->until = timestamp + MIN(rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 259
 260         prioq_reshuffle(c->by_expiry, i, &i->prioq_idx);
 261 }
 262
 263 static int dns_cache_put_positive(
 264                 DnsCache *c,
 265                 DnsResourceRecord *rr,
 266                 usec_t timestamp,
 267                 int owner_family,
 268                 const union in_addr_union *owner_address) {
 269
 270         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
 271         _cleanup_free_ char *key_str = NULL;
 272         DnsCacheItem *existing;
 273         int r;
 274
 275         assert(c);
 276         assert(rr);
 277         assert(owner_address);
 278
 279         /* New TTL is 0? Delete the entry... */
 280         if (rr->ttl <= 0) {
 281                 r = dns_resource_key_to_string(rr->key, &key_str);
 282                 if (r < 0)
 283                         return r;
 284
 285                 if (dns_cache_remove(c, rr->key))
 286                         log_debug("Removed zero TTL entry from cache: %s", key_str);
 287                 else
 288                         log_debug("Not caching zero TTL cache entry: %s", key_str);
 289
 290                 return 0;
 291         }
 292
 293         if (rr->key->class == DNS_CLASS_ANY)
 294                 return 0;
 295         if (rr->key->type == DNS_TYPE_ANY)
 296                 return 0;
 297
 298         /* Entry exists already? Update TTL and timestamp */
 299         existing = dns_cache_get(c, rr);
 300         if (existing) {
 301                 dns_cache_item_update_positive(c, existing, rr, timestamp);
 302                 return 0;
 303         }
 304
 305         /* Otherwise, add the new RR */
 306         r = dns_cache_init(c);
 307         if (r < 0)
 308                 return r;
 309
 310         dns_cache_make_space(c, 1);
 311
 312         i = new0(DnsCacheItem, 1);
 313         if (!i)
 314                 return -ENOMEM;
 315
 316         i->type = DNS_CACHE_POSITIVE;
 317         i->key = dns_resource_key_ref(rr->key);
 318         i->rr = dns_resource_record_ref(rr);
 319         i->until = timestamp + MIN(i->rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 320         i->prioq_idx = PRIOQ_IDX_NULL;
 321         i->owner_family = owner_family;
 322         i->owner_address = *owner_address;
 323
 324         r = dns_cache_link_item(c, i);
 325         if (r < 0)
 326                 return r;
 327
 328         r = dns_resource_key_to_string(i->key, &key_str);
 329         if (r < 0)
 330                 return r;
 331
 332         log_debug("Added cache entry for %s", key_str);
 333
 334         i = NULL;
 335         return 0;
 336 }
 337
 338 static int dns_cache_put_negative(
 339                 DnsCache *c,
 340                 DnsResourceKey *key,
 341                 int rcode,
 342                 usec_t timestamp,
 343                 uint32_t soa_ttl,
 344                 int owner_family,
 345                 const union in_addr_union *owner_address) {
 346
 347         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
 348         _cleanup_free_ char *key_str = NULL;
 349         int r;
 350
 351         assert(c);
 352         assert(key);
 353         assert(owner_address);
 354
 355         dns_cache_remove(c, key);
 356
 357         if (key->class == DNS_CLASS_ANY)
 358                 return 0;
 359         if (key->type == DNS_TYPE_ANY)
 360                 return 0;
 361         if (soa_ttl <= 0) {
 362                 r = dns_resource_key_to_string(key, &key_str);
 363                 if (r < 0)
 364                         return r;
 365
 366                 log_debug("Not caching negative entry with zero SOA TTL: %s", key_str);
 367
 368                 return 0;
 369         }
 370
 371         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
 372                 return 0;
 373
 374         r = dns_cache_init(c);
 375         if (r < 0)
 376                 return r;
 377
 378         dns_cache_make_space(c, 1);
 379
 380         i = new0(DnsCacheItem, 1);
 381         if (!i)
 382                 return -ENOMEM;
 383
 384         i->type = rcode == DNS_RCODE_SUCCESS ? DNS_CACHE_NODATA : DNS_CACHE_NXDOMAIN;
 385         i->key = dns_resource_key_ref(key);
 386         i->until = timestamp + MIN(soa_ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 387         i->prioq_idx = PRIOQ_IDX_NULL;
 388         i->owner_family = owner_family;
 389         i->owner_address = *owner_address;
 390
 391         r = dns_cache_link_item(c, i);
 392         if (r < 0)
 393                 return r;
 394
 395         r = dns_resource_key_to_string(i->key, &key_str);
 396         if (r < 0)
 397                 return r;
 398
 399         log_debug("Added %s cache entry for %s", i->type == DNS_CACHE_NODATA ? "NODATA" : "NXDOMAIN", key_str);
 400
 401         i = NULL;
 402         return 0;
 403 }
 404
 405 int dns_cache_put(
 406                 DnsCache *c,
 407                 DnsResourceKey *key,
 408                 int rcode,
 409                 DnsAnswer *answer,
 410                 unsigned max_rrs,
 411                 usec_t timestamp,
 412                 int owner_family,
 413                 const union in_addr_union *owner_address) {
 414
 415         DnsResourceRecord *soa = NULL;
 416         unsigned cache_keys, i;
 417         int r;
 418
 419         assert(c);
 420
 421         if (key) {
 422                 /* First, if we were passed a key, delete all matching old RRs,
 423                  * so that we only keep complete by_key in place. */
 424                 dns_cache_remove(c, key);
 425         }
 426
 427         if (!answer)
 428                 return 0;
 429
 430         for (i = 0; i < answer->n_rrs; i++)
 431                 dns_cache_remove(c, answer->items[i].rr->key);
 432
 433         /* We only care for positive replies and NXDOMAINs, on all
 434          * other replies we will simply flush the respective entries,
 435          * and that's it */
 436
 437         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
 438                 return 0;
 439
 440         cache_keys = answer->n_rrs;
 441
 442         if (key)
 443                 cache_keys ++;
 444
 445         /* Make some space for our new entries */
 446         dns_cache_make_space(c, cache_keys);
 447
 448         if (timestamp <= 0)
 449                 timestamp = now(clock_boottime_or_monotonic());
 450
 451         /* Second, add in positive entries for all contained RRs */
 452         for (i = 0; i < MIN(max_rrs, answer->n_rrs); i++) {
 453                 r = dns_cache_put_positive(c, answer->items[i].rr, timestamp, owner_family, owner_address);
 454                 if (r < 0)
 455                         goto fail;
 456         }
 457
 458         if (!key)
 459                 return 0;
 460
 461         /* Third, add in negative entries if the key has no RR */
 462         r = dns_answer_contains(answer, key);
 463         if (r < 0)
 464                 goto fail;
 465         if (r > 0)
 466                 return 0;
 467
 468         /* See https://tools.ietf.org/html/rfc2308, which
 469          * say that a matching SOA record in the packet
 470          * is used to to enable negative caching. */
 471
 472         r = dns_answer_find_soa(answer, key, &soa);
 473         if (r < 0)
 474                 goto fail;
 475         if (r == 0)
 476                 return 0;
 477
 478         /* Also, if the requested key is an alias, the negative response should
 479            be cached for each name in the redirect chain. Any CNAME record in
 480            the response is from the redirection chain, though only the final one
 481            is guaranteed to be included. This means that we cannot verify the
 482            chain and that we need to cache them all as it may be incomplete. */
 483         for (i = 0; i < answer->n_rrs; i++) {
 484                 DnsResourceRecord *answer_rr = answer->items[i].rr;
 485
 486                 if (answer_rr->key->type == DNS_TYPE_CNAME) {
 487                         _cleanup_(dns_resource_key_unrefp) DnsResourceKey *canonical_key = NULL;
 488
 489                         canonical_key = dns_resource_key_new_redirect(key, answer_rr);
 490                         if (!canonical_key)
 491                                 goto fail;
 492
 493                         /* Let's not add negative cache entries for records outside the current zone. */
 494                         if (!dns_answer_match_soa(canonical_key, soa->key))
 495                                 continue;
 496
 497                         r = dns_cache_put_negative(c, canonical_key, rcode, timestamp, MIN(soa->soa.minimum, soa->ttl), owner_family, owner_address);
 498                         if (r < 0)
 499                                 goto fail;
 500                 }
 501         }
 502
 503         r = dns_cache_put_negative(c, key, rcode, timestamp, MIN(soa->soa.minimum, soa->ttl), owner_family, owner_address);
 504         if (r < 0)
 505                 goto fail;
 506
 507         return 0;
 508
 509 fail:
 510         /* Adding all RRs failed. Let's clean up what we already
 511          * added, just in case */
 512
 513         if (key)
 514                 dns_cache_remove(c, key);
 515
 516         for (i = 0; i < answer->n_rrs; i++)
 517                 dns_cache_remove(c, answer->items[i].rr->key);
 518
 519         return r;
 520 }
 521
 522 static DnsCacheItem *dns_cache_get_by_key_follow_cname(DnsCache *c, DnsResourceKey *k) {
 523         _cleanup_(dns_resource_key_unrefp) DnsResourceKey *cname_key = NULL;
 524         DnsCacheItem *i, *j;
 525
 526         assert(c);
 527         assert(k);
 528
 529         i = hashmap_get(c->by_key, k);
 530         if (i || k->type == DNS_TYPE_CNAME)
 531                 return i;
 532
 533         /* check if we have a CNAME record instead */
 534         cname_key = dns_resource_key_new_cname(k);
 535         if (!cname_key)
 536                 return NULL;
 537
 538         j = hashmap_get(c->by_key, cname_key);
 539         if (j)
 540                 return j;
 541
 542         return i;
 543 }
 544
 545 int dns_cache_lookup(DnsCache *c, DnsResourceKey *key, int *rcode, DnsAnswer **ret) {
 546         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
 547         unsigned n = 0;
 548         int r;
 549         bool nxdomain = false;
 550         _cleanup_free_ char *key_str = NULL;
 551         DnsCacheItem *j, *first;
 552
 553         assert(c);
 554         assert(key);
 555         assert(rcode);
 556         assert(ret);
 557
 558         if (key->type == DNS_TYPE_ANY ||
 559             key->class == DNS_CLASS_ANY) {
 560
 561                 /* If we have ANY lookups we simply refresh */
 562
 563                 r = dns_resource_key_to_string(key, &key_str);
 564                 if (r < 0)
 565                         return r;
 566
 567                 log_debug("Ignoring cache for ANY lookup: %s", key_str);
 568
 569                 *ret = NULL;
 570                 *rcode = DNS_RCODE_SUCCESS;
 571                 return 0;
 572         }
 573
 574         first = dns_cache_get_by_key_follow_cname(c, key);
 575         if (!first) {
 576                 /* If one question cannot be answered we need to refresh */
 577
 578                 r = dns_resource_key_to_string(key, &key_str);
 579                 if (r < 0)
 580                         return r;
 581
 582                 log_debug("Cache miss for %s", key_str);
 583
 584                 *ret = NULL;
 585                 *rcode = DNS_RCODE_SUCCESS;
 586                 return 0;
 587         }
 588
 589         LIST_FOREACH(by_key, j, first) {
 590                 if (j->rr)
 591                         n++;
 592                 else if (j->type == DNS_CACHE_NXDOMAIN)
 593                         nxdomain = true;
 594         }
 595
 596         r = dns_resource_key_to_string(key, &key_str);
 597         if (r < 0)
 598                 return r;
 599
 600         log_debug("%s cache hit for %s",
 601                   nxdomain ? "NXDOMAIN" :
 602                      n > 0 ? "Positive" : "NODATA",
 603                   key_str);
 604
 605         if (n <= 0) {
 606                 *ret = NULL;
 607                 *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS;
 608                 return 1;
 609         }
 610
 611         answer = dns_answer_new(n);
 612         if (!answer)
 613                 return -ENOMEM;
 614
 615         LIST_FOREACH(by_key, j, first) {
 616                 if (!j->rr)
 617                         continue;
 618
 619                 r = dns_answer_add(answer, j->rr, 0);
 620                 if (r < 0)
 621                         return r;
 622         }
 623
 624         *ret = answer;
 625         *rcode = DNS_RCODE_SUCCESS;
 626         answer = NULL;
 627
 628         return n;
 629 }
 630
 631 int dns_cache_check_conflicts(DnsCache *cache, DnsResourceRecord *rr, int owner_family, const union in_addr_union *owner_address) {
 632         DnsCacheItem *i, *first;
 633         bool same_owner = true;
 634
 635         assert(cache);
 636         assert(rr);
 637
 638         dns_cache_prune(cache);
 639
 640         /* See if there's a cache entry for the same key. If there
 641          * isn't there's no conflict */
 642         first = hashmap_get(cache->by_key, rr->key);
 643         if (!first)
 644                 return 0;
 645
 646         /* See if the RR key is owned by the same owner, if so, there
 647          * isn't a conflict either */
 648         LIST_FOREACH(by_key, i, first) {
 649                 if (i->owner_family != owner_family ||
 650                     !in_addr_equal(owner_family, &i->owner_address, owner_address)) {
 651                         same_owner = false;
 652                         break;
 653                 }
 654         }
 655         if (same_owner)
 656                 return 0;
 657
 658         /* See if there's the exact same RR in the cache. If yes, then
 659          * there's no conflict. */
 660         if (dns_cache_get(cache, rr))
 661                 return 0;
 662
 663         /* There's a conflict */
 664         return 1;
 665 }
 666
 667 void dns_cache_dump(DnsCache *cache, FILE *f) {
 668         Iterator iterator;
 669         DnsCacheItem *i;
 670         int r;
 671
 672         if (!cache)
 673                 return;
 674
 675         if (!f)
 676                 f = stdout;
 677
 678         HASHMAP_FOREACH(i, cache->by_key, iterator) {
 679                 DnsCacheItem *j;
 680
 681                 LIST_FOREACH(by_key, j, i) {
 682                         _cleanup_free_ char *t = NULL;
 683
 684                         fputc('\t', f);
 685
 686                         if (j->rr) {
 687                                 r = dns_resource_record_to_string(j->rr, &t);
 688                                 if (r < 0) {
 689                                         log_oom();
 690                                         continue;
 691                                 }
 692
 693                                 fputs(t, f);
 694                                 fputc('\n', f);
 695                         } else {
 696                                 r = dns_resource_key_to_string(j->key, &t);
 697                                 if (r < 0) {
 698                                         log_oom();
 699                                         continue;
 700                                 }
 701
 702                                 fputs(t, f);
 703                                 fputs(" -- ", f);
 704                                 fputs(j->type == DNS_CACHE_NODATA ? "NODATA" : "NXDOMAIN", f);
 705                                 fputc('\n', f);
 706                         }
 707                 }
 708         }
 709 }
 710
 711 bool dns_cache_is_empty(DnsCache *cache) {
 712         if (!cache)
 713                 return true;
 714
 715         return hashmap_isempty(cache->by_key);
 716 }