src/resolve/resolved-dns-cache.c

   1 /***
   2   This file is part of systemd.
   3
   4   Copyright 2014 Lennart Poettering
   5
   6   systemd is free software; you can redistribute it and/or modify it
   7   under the terms of the GNU Lesser General Public License as published by
   8   the Free Software Foundation; either version 2.1 of the License, or
   9   (at your option) any later version.
  10
  11   systemd is distributed in the hope that it will be useful, but
  12   WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14   Lesser General Public License for more details.
  15
  16   You should have received a copy of the GNU Lesser General Public License
  17   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  18 ***/
  19
  20 #include <net/if.h>
  21
  22 #include "af-list.h"
  23 #include "alloc-util.h"
  24 #include "dns-domain.h"
  25 #include "resolved-dns-answer.h"
  26 #include "resolved-dns-cache.h"
  27 #include "resolved-dns-packet.h"
  28 #include "string-util.h"
  29
  30 /* Never cache more than 4K entries. RFC 1536, Section 5 suggests to
  31  * leave DNS caches unbounded, but that's crazy. */
  32 #define CACHE_MAX 4096
  33
  34 /* We never keep any item longer than 2h in our cache */
  35 #define CACHE_TTL_MAX_USEC (2 * USEC_PER_HOUR)
  36
  37 /* How long to cache strange rcodes, i.e. rcodes != SUCCESS and != NXDOMAIN (specifically: that's only SERVFAIL for
  38  * now) */
  39 #define CACHE_TTL_STRANGE_RCODE_USEC (30 * USEC_PER_SEC)
  40
  41 typedef enum DnsCacheItemType DnsCacheItemType;
  42 typedef struct DnsCacheItem DnsCacheItem;
  43
  44 enum DnsCacheItemType {
  45         DNS_CACHE_POSITIVE,
  46         DNS_CACHE_NODATA,
  47         DNS_CACHE_NXDOMAIN,
  48         DNS_CACHE_RCODE,      /* "strange" RCODE (effective only SERVFAIL for now) */
  49 };
  50
  51 struct DnsCacheItem {
  52         DnsCacheItemType type;
  53         DnsResourceKey *key;
  54         DnsResourceRecord *rr;
  55         int rcode;
  56
  57         usec_t until;
  58         bool authenticated:1;
  59         bool shared_owner:1;
  60
  61         int ifindex;
  62         int owner_family;
  63         union in_addr_union owner_address;
  64
  65         unsigned prioq_idx;
  66         LIST_FIELDS(DnsCacheItem, by_key);
  67 };
  68
  69 static const char *dns_cache_item_type_to_string(DnsCacheItem *item) {
  70         assert(item);
  71
  72         switch (item->type) {
  73
  74         case DNS_CACHE_POSITIVE:
  75                 return "POSITIVE";
  76
  77         case DNS_CACHE_NODATA:
  78                 return "NODATA";
  79
  80         case DNS_CACHE_NXDOMAIN:
  81                 return "NXDOMAIN";
  82
  83         case DNS_CACHE_RCODE:
  84                 return dns_rcode_to_string(item->rcode);
  85         }
  86
  87         return NULL;
  88 }
  89
  90 static void dns_cache_item_free(DnsCacheItem *i) {
  91         if (!i)
  92                 return;
  93
  94         dns_resource_record_unref(i->rr);
  95         dns_resource_key_unref(i->key);
  96         free(i);
  97 }
  98
  99 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsCacheItem*, dns_cache_item_free);
 100
 101 static void dns_cache_item_unlink_and_free(DnsCache *c, DnsCacheItem *i) {
 102         DnsCacheItem *first;
 103
 104         assert(c);
 105
 106         if (!i)
 107                 return;
 108
 109         first = hashmap_get(c->by_key, i->key);
 110         LIST_REMOVE(by_key, first, i);
 111
 112         if (first)
 113                 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
 114         else
 115                 hashmap_remove(c->by_key, i->key);
 116
 117         prioq_remove(c->by_expiry, i, &i->prioq_idx);
 118
 119         dns_cache_item_free(i);
 120 }
 121
 122 static bool dns_cache_remove_by_rr(DnsCache *c, DnsResourceRecord *rr) {
 123         DnsCacheItem *first, *i;
 124         int r;
 125
 126         first = hashmap_get(c->by_key, rr->key);
 127         LIST_FOREACH(by_key, i, first) {
 128                 r = dns_resource_record_equal(i->rr, rr);
 129                 if (r < 0)
 130                         return r;
 131                 if (r > 0) {
 132                         dns_cache_item_unlink_and_free(c, i);
 133                         return true;
 134                 }
 135         }
 136
 137         return false;
 138 }
 139
 140 static bool dns_cache_remove_by_key(DnsCache *c, DnsResourceKey *key) {
 141         DnsCacheItem *first, *i, *n;
 142
 143         assert(c);
 144         assert(key);
 145
 146         first = hashmap_remove(c->by_key, key);
 147         if (!first)
 148                 return false;
 149
 150         LIST_FOREACH_SAFE(by_key, i, n, first) {
 151                 prioq_remove(c->by_expiry, i, &i->prioq_idx);
 152                 dns_cache_item_free(i);
 153         }
 154
 155         return true;
 156 }
 157
 158 void dns_cache_flush(DnsCache *c) {
 159         DnsResourceKey *key;
 160
 161         assert(c);
 162
 163         while ((key = hashmap_first_key(c->by_key)))
 164                 dns_cache_remove_by_key(c, key);
 165
 166         assert(hashmap_size(c->by_key) == 0);
 167         assert(prioq_size(c->by_expiry) == 0);
 168
 169         c->by_key = hashmap_free(c->by_key);
 170         c->by_expiry = prioq_free(c->by_expiry);
 171 }
 172
 173 static void dns_cache_make_space(DnsCache *c, unsigned add) {
 174         assert(c);
 175
 176         if (add <= 0)
 177                 return;
 178
 179         /* Makes space for n new entries. Note that we actually allow
 180          * the cache to grow beyond CACHE_MAX, but only when we shall
 181          * add more RRs to the cache than CACHE_MAX at once. In that
 182          * case the cache will be emptied completely otherwise. */
 183
 184         for (;;) {
 185                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
 186                 DnsCacheItem *i;
 187
 188                 if (prioq_size(c->by_expiry) <= 0)
 189                         break;
 190
 191                 if (prioq_size(c->by_expiry) + add < CACHE_MAX)
 192                         break;
 193
 194                 i = prioq_peek(c->by_expiry);
 195                 assert(i);
 196
 197                 /* Take an extra reference to the key so that it
 198                  * doesn't go away in the middle of the remove call */
 199                 key = dns_resource_key_ref(i->key);
 200                 dns_cache_remove_by_key(c, key);
 201         }
 202 }
 203
 204 void dns_cache_prune(DnsCache *c) {
 205         usec_t t = 0;
 206
 207         assert(c);
 208
 209         /* Remove all entries that are past their TTL */
 210
 211         for (;;) {
 212                 DnsCacheItem *i;
 213                 char key_str[DNS_RESOURCE_KEY_STRING_MAX];
 214
 215                 i = prioq_peek(c->by_expiry);
 216                 if (!i)
 217                         break;
 218
 219                 if (t <= 0)
 220                         t = now(clock_boottime_or_monotonic());
 221
 222                 if (i->until > t)
 223                         break;
 224
 225                 /* Depending whether this is an mDNS shared entry
 226                  * either remove only this one RR or the whole RRset */
 227                 log_debug("Removing %scache entry for %s (expired "USEC_FMT"s ago)",
 228                           i->shared_owner ? "shared " : "",
 229                           dns_resource_key_to_string(i->key, key_str, sizeof key_str),
 230                           (t - i->until) / USEC_PER_SEC);
 231
 232                 if (i->shared_owner)
 233                         dns_cache_item_unlink_and_free(c, i);
 234                 else {
 235                         _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
 236
 237                         /* Take an extra reference to the key so that it
 238                          * doesn't go away in the middle of the remove call */
 239                         key = dns_resource_key_ref(i->key);
 240                         dns_cache_remove_by_key(c, key);
 241                 }
 242         }
 243 }
 244
 245 static int dns_cache_item_prioq_compare_func(const void *a, const void *b) {
 246         const DnsCacheItem *x = a, *y = b;
 247
 248         if (x->until < y->until)
 249                 return -1;
 250         if (x->until > y->until)
 251                 return 1;
 252         return 0;
 253 }
 254
 255 static int dns_cache_init(DnsCache *c) {
 256         int r;
 257
 258         assert(c);
 259
 260         r = prioq_ensure_allocated(&c->by_expiry, dns_cache_item_prioq_compare_func);
 261         if (r < 0)
 262                 return r;
 263
 264         r = hashmap_ensure_allocated(&c->by_key, &dns_resource_key_hash_ops);
 265         if (r < 0)
 266                 return r;
 267
 268         return r;
 269 }
 270
 271 static int dns_cache_link_item(DnsCache *c, DnsCacheItem *i) {
 272         DnsCacheItem *first;
 273         int r;
 274
 275         assert(c);
 276         assert(i);
 277
 278         r = prioq_put(c->by_expiry, i, &i->prioq_idx);
 279         if (r < 0)
 280                 return r;
 281
 282         first = hashmap_get(c->by_key, i->key);
 283         if (first) {
 284                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *k = NULL;
 285
 286                 /* Keep a reference to the original key, while we manipulate the list. */
 287                 k = dns_resource_key_ref(first->key);
 288
 289                 /* Now, try to reduce the number of keys we keep */
 290                 dns_resource_key_reduce(&first->key, &i->key);
 291
 292                 if (first->rr)
 293                         dns_resource_key_reduce(&first->rr->key, &i->key);
 294                 if (i->rr)
 295                         dns_resource_key_reduce(&i->rr->key, &i->key);
 296
 297                 LIST_PREPEND(by_key, first, i);
 298                 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
 299         } else {
 300                 r = hashmap_put(c->by_key, i->key, i);
 301                 if (r < 0) {
 302                         prioq_remove(c->by_expiry, i, &i->prioq_idx);
 303                         return r;
 304                 }
 305         }
 306
 307         return 0;
 308 }
 309
 310 static DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) {
 311         DnsCacheItem *i;
 312
 313         assert(c);
 314         assert(rr);
 315
 316         LIST_FOREACH(by_key, i, hashmap_get(c->by_key, rr->key))
 317                 if (i->rr && dns_resource_record_equal(i->rr, rr) > 0)
 318                         return i;
 319
 320         return NULL;
 321 }
 322
 323 static usec_t calculate_until(DnsResourceRecord *rr, uint32_t nsec_ttl, usec_t timestamp, bool use_soa_minimum) {
 324         uint32_t ttl;
 325         usec_t u;
 326
 327         assert(rr);
 328
 329         ttl = MIN(rr->ttl, nsec_ttl);
 330         if (rr->key->type == DNS_TYPE_SOA && use_soa_minimum) {
 331                 /* If this is a SOA RR, and it is requested, clamp to
 332                  * the SOA's minimum field. This is used when we do
 333                  * negative caching, to determine the TTL for the
 334                  * negative caching entry.  See RFC 2308, Section
 335                  * 5. */
 336
 337                 if (ttl > rr->soa.minimum)
 338                         ttl = rr->soa.minimum;
 339         }
 340
 341         u = ttl * USEC_PER_SEC;
 342         if (u > CACHE_TTL_MAX_USEC)
 343                 u = CACHE_TTL_MAX_USEC;
 344
 345         if (rr->expiry != USEC_INFINITY) {
 346                 usec_t left;
 347
 348                 /* Make use of the DNSSEC RRSIG expiry info, if we
 349                  * have it */
 350
 351                 left = LESS_BY(rr->expiry, now(CLOCK_REALTIME));
 352                 if (u > left)
 353                         u = left;
 354         }
 355
 356         return timestamp + u;
 357 }
 358
 359 static void dns_cache_item_update_positive(
 360                 DnsCache *c,
 361                 DnsCacheItem *i,
 362                 DnsResourceRecord *rr,
 363                 bool authenticated,
 364                 bool shared_owner,
 365                 usec_t timestamp,
 366                 int ifindex,
 367                 int owner_family,
 368                 const union in_addr_union *owner_address) {
 369
 370         assert(c);
 371         assert(i);
 372         assert(rr);
 373         assert(owner_address);
 374
 375         i->type = DNS_CACHE_POSITIVE;
 376
 377         if (!i->by_key_prev)
 378                 /* We are the first item in the list, we need to
 379                  * update the key used in the hashmap */
 380
 381                 assert_se(hashmap_replace(c->by_key, rr->key, i) >= 0);
 382
 383         dns_resource_record_ref(rr);
 384         dns_resource_record_unref(i->rr);
 385         i->rr = rr;
 386
 387         dns_resource_key_unref(i->key);
 388         i->key = dns_resource_key_ref(rr->key);
 389
 390         i->until = calculate_until(rr, (uint32_t) -1, timestamp, false);
 391         i->authenticated = authenticated;
 392         i->shared_owner = shared_owner;
 393
 394         i->ifindex = ifindex;
 395
 396         i->owner_family = owner_family;
 397         i->owner_address = *owner_address;
 398
 399         prioq_reshuffle(c->by_expiry, i, &i->prioq_idx);
 400 }
 401
 402 static int dns_cache_put_positive(
 403                 DnsCache *c,
 404                 DnsResourceRecord *rr,
 405                 bool authenticated,
 406                 bool shared_owner,
 407                 usec_t timestamp,
 408                 int ifindex,
 409                 int owner_family,
 410                 const union in_addr_union *owner_address) {
 411
 412         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
 413         DnsCacheItem *existing;
 414         char key_str[DNS_RESOURCE_KEY_STRING_MAX], ifname[IF_NAMESIZE];
 415         int r, k;
 416
 417         assert(c);
 418         assert(rr);
 419         assert(owner_address);
 420
 421         /* Never cache pseudo RRs */
 422         if (dns_class_is_pseudo(rr->key->class))
 423                 return 0;
 424         if (dns_type_is_pseudo(rr->key->type))
 425                 return 0;
 426
 427         /* New TTL is 0? Delete this specific entry... */
 428         if (rr->ttl <= 0) {
 429                 k = dns_cache_remove_by_rr(c, rr);
 430                 log_debug("%s: %s",
 431                           k > 0 ? "Removed zero TTL entry from cache" : "Not caching zero TTL cache entry",
 432                           dns_resource_key_to_string(rr->key, key_str, sizeof key_str));
 433                 return 0;
 434         }
 435
 436         /* Entry exists already? Update TTL, timestamp and owner */
 437         existing = dns_cache_get(c, rr);
 438         if (existing) {
 439                 dns_cache_item_update_positive(
 440                                 c,
 441                                 existing,
 442                                 rr,
 443                                 authenticated,
 444                                 shared_owner,
 445                                 timestamp,
 446                                 ifindex,
 447                                 owner_family,
 448                                 owner_address);
 449                 return 0;
 450         }
 451
 452         /* Otherwise, add the new RR */
 453         r = dns_cache_init(c);
 454         if (r < 0)
 455                 return r;
 456
 457         dns_cache_make_space(c, 1);
 458
 459         i = new0(DnsCacheItem, 1);
 460         if (!i)
 461                 return -ENOMEM;
 462
 463         i->type = DNS_CACHE_POSITIVE;
 464         i->key = dns_resource_key_ref(rr->key);
 465         i->rr = dns_resource_record_ref(rr);
 466         i->until = calculate_until(rr, (uint32_t) -1, timestamp, false);
 467         i->authenticated = authenticated;
 468         i->shared_owner = shared_owner;
 469         i->ifindex = ifindex;
 470         i->owner_family = owner_family;
 471         i->owner_address = *owner_address;
 472         i->prioq_idx = PRIOQ_IDX_NULL;
 473
 474         r = dns_cache_link_item(c, i);
 475         if (r < 0)
 476                 return r;
 477
 478         if (log_get_max_level() >= LOG_DEBUG) {
 479                 _cleanup_free_ char *t = NULL;
 480
 481                 (void) in_addr_to_string(i->owner_family, &i->owner_address, &t);
 482
 483                 log_debug("Added positive %s%s cache entry for %s "USEC_FMT"s on %s/%s/%s",
 484                           i->authenticated ? "authenticated" : "unauthenticated",
 485                           i->shared_owner ? " shared" : "",
 486                           dns_resource_key_to_string(i->key, key_str, sizeof key_str),
 487                           (i->until - timestamp) / USEC_PER_SEC,
 488                           i->ifindex == 0 ? "*" : strna(if_indextoname(i->ifindex, ifname)),
 489                           af_to_name_short(i->owner_family),
 490                           strna(t));
 491         }
 492
 493         i = NULL;
 494         return 0;
 495 }
 496
 497 static int dns_cache_put_negative(
 498                 DnsCache *c,
 499                 DnsResourceKey *key,
 500                 int rcode,
 501                 bool authenticated,
 502                 uint32_t nsec_ttl,
 503                 usec_t timestamp,
 504                 DnsResourceRecord *soa,
 505                 int owner_family,
 506                 const union in_addr_union *owner_address) {
 507
 508         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
 509         char key_str[DNS_RESOURCE_KEY_STRING_MAX];
 510         int r;
 511
 512         assert(c);
 513         assert(key);
 514         assert(owner_address);
 515
 516         /* Never cache pseudo RR keys. DNS_TYPE_ANY is particularly
 517          * important to filter out as we use this as a pseudo-type for
 518          * NXDOMAIN entries */
 519         if (dns_class_is_pseudo(key->class))
 520                 return 0;
 521         if (dns_type_is_pseudo(key->type))
 522                 return 0;
 523
 524         if (IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN)) {
 525                 if (!soa)
 526                         return 0;
 527
 528                 /* For negative replies, check if we have a TTL of a SOA */
 529                 if (nsec_ttl <= 0 || soa->soa.minimum <= 0 || soa->ttl <= 0) {
 530                         log_debug("Not caching negative entry with zero SOA/NSEC/NSEC3 TTL: %s",
 531                                   dns_resource_key_to_string(key, key_str, sizeof key_str));
 532                         return 0;
 533                 }
 534         } else if (rcode != DNS_RCODE_SERVFAIL)
 535                 return 0;
 536
 537         r = dns_cache_init(c);
 538         if (r < 0)
 539                 return r;
 540
 541         dns_cache_make_space(c, 1);
 542
 543         i = new0(DnsCacheItem, 1);
 544         if (!i)
 545                 return -ENOMEM;
 546
 547         i->type =
 548                 rcode == DNS_RCODE_SUCCESS ? DNS_CACHE_NODATA :
 549                 rcode == DNS_RCODE_NXDOMAIN ? DNS_CACHE_NXDOMAIN : DNS_CACHE_RCODE;
 550         i->until =
 551                 i->type == DNS_CACHE_RCODE ? timestamp + CACHE_TTL_STRANGE_RCODE_USEC :
 552                 calculate_until(soa, nsec_ttl, timestamp, true);
 553         i->authenticated = authenticated;
 554         i->owner_family = owner_family;
 555         i->owner_address = *owner_address;
 556         i->prioq_idx = PRIOQ_IDX_NULL;
 557         i->rcode = rcode;
 558
 559         if (i->type == DNS_CACHE_NXDOMAIN) {
 560                 /* NXDOMAIN entries should apply equally to all types, so we use ANY as
 561                  * a pseudo type for this purpose here. */
 562                 i->key = dns_resource_key_new(key->class, DNS_TYPE_ANY, dns_resource_key_name(key));
 563                 if (!i->key)
 564                         return -ENOMEM;
 565
 566                 /* Make sure to remove any previous entry for this
 567                  * specific ANY key. (For non-ANY keys the cache data
 568                  * is already cleared by the caller.) Note that we
 569                  * don't bother removing positive or NODATA cache
 570                  * items in this case, because it would either be slow
 571                  * or require explicit indexing by name */
 572                 dns_cache_remove_by_key(c, key);
 573         } else
 574                 i->key = dns_resource_key_ref(key);
 575
 576         r = dns_cache_link_item(c, i);
 577         if (r < 0)
 578                 return r;
 579
 580         log_debug("Added %s cache entry for %s "USEC_FMT"s",
 581                   dns_cache_item_type_to_string(i),
 582                   dns_resource_key_to_string(i->key, key_str, sizeof key_str),
 583                   (i->until - timestamp) / USEC_PER_SEC);
 584
 585         i = NULL;
 586         return 0;
 587 }
 588
 589 static void dns_cache_remove_previous(
 590                 DnsCache *c,
 591                 DnsResourceKey *key,
 592                 DnsAnswer *answer) {
 593
 594         DnsResourceRecord *rr;
 595         DnsAnswerFlags flags;
 596
 597         assert(c);
 598
 599         /* First, if we were passed a key (i.e. on LLMNR/DNS, but
 600          * not on mDNS), delete all matching old RRs, so that we only
 601          * keep complete by_key in place. */
 602         if (key)
 603                 dns_cache_remove_by_key(c, key);
 604
 605         /* Second, flush all entries matching the answer, unless this
 606          * is an RR that is explicitly marked to be "shared" between
 607          * peers (i.e. mDNS RRs without the flush-cache bit set). */
 608         DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
 609                 if ((flags & DNS_ANSWER_CACHEABLE) == 0)
 610                         continue;
 611
 612                 if (flags & DNS_ANSWER_SHARED_OWNER)
 613                         continue;
 614
 615                 dns_cache_remove_by_key(c, rr->key);
 616         }
 617 }
 618
 619 static bool rr_eligible(DnsResourceRecord *rr) {
 620         assert(rr);
 621
 622         /* When we see an NSEC/NSEC3 RR, we'll only cache it if it is from the lower zone, not the upper zone, since
 623          * that's where the interesting bits are (with exception of DS RRs). Of course, this way we cannot derive DS
 624          * existence from any cached NSEC/NSEC3, but that should be fine. */
 625
 626         switch (rr->key->type) {
 627
 628         case DNS_TYPE_NSEC:
 629                 return !bitmap_isset(rr->nsec.types, DNS_TYPE_NS) ||
 630                         bitmap_isset(rr->nsec.types, DNS_TYPE_SOA);
 631
 632         case DNS_TYPE_NSEC3:
 633                 return !bitmap_isset(rr->nsec3.types, DNS_TYPE_NS) ||
 634                         bitmap_isset(rr->nsec3.types, DNS_TYPE_SOA);
 635
 636         default:
 637                 return true;
 638         }
 639 }
 640
 641 int dns_cache_put(
 642                 DnsCache *c,
 643                 DnsResourceKey *key,
 644                 int rcode,
 645                 DnsAnswer *answer,
 646                 bool authenticated,
 647                 uint32_t nsec_ttl,
 648                 usec_t timestamp,
 649                 int owner_family,
 650                 const union in_addr_union *owner_address) {
 651
 652         DnsResourceRecord *soa = NULL, *rr;
 653         bool weird_rcode = false;
 654         DnsAnswerFlags flags;
 655         unsigned cache_keys;
 656         int r, ifindex;
 657
 658         assert(c);
 659         assert(owner_address);
 660
 661         dns_cache_remove_previous(c, key, answer);
 662
 663         /* We only care for positive replies and NXDOMAINs, on all other replies we will simply flush the respective
 664          * entries, and that's it. (Well, with one further exception: since some DNS zones (akamai!) return SERVFAIL
 665          * consistently for some lookups, and forwarders tend to propagate that we'll cache that too, but only for a
 666          * short time.) */
 667
 668         if (IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN)) {
 669
 670                 if (dns_answer_size(answer) <= 0) {
 671                         char key_str[DNS_RESOURCE_KEY_STRING_MAX];
 672
 673                         log_debug("Not caching negative entry without a SOA record: %s",
 674                                   dns_resource_key_to_string(key, key_str, sizeof key_str));
 675                         return 0;
 676                 }
 677
 678         } else {
 679                 /* Only cache SERVFAIL as "weird" rcode for now. We can add more later, should that turn out to be
 680                  * beneficial. */
 681                 if (rcode != DNS_RCODE_SERVFAIL)
 682                         return 0;
 683
 684                 weird_rcode = true;
 685         }
 686
 687         cache_keys = dns_answer_size(answer);
 688         if (key)
 689                 cache_keys++;
 690
 691         /* Make some space for our new entries */
 692         dns_cache_make_space(c, cache_keys);
 693
 694         if (timestamp <= 0)
 695                 timestamp = now(clock_boottime_or_monotonic());
 696
 697         /* Second, add in positive entries for all contained RRs */
 698         DNS_ANSWER_FOREACH_FULL(rr, ifindex, flags, answer) {
 699                 if ((flags & DNS_ANSWER_CACHEABLE) == 0)
 700                         continue;
 701
 702                 r = rr_eligible(rr);
 703                 if (r < 0)
 704                         return r;
 705                 if (r == 0)
 706                         continue;
 707
 708                 r = dns_cache_put_positive(
 709                                 c,
 710                                 rr,
 711                                 flags & DNS_ANSWER_AUTHENTICATED,
 712                                 flags & DNS_ANSWER_SHARED_OWNER,
 713                                 timestamp,
 714                                 ifindex,
 715                                 owner_family, owner_address);
 716                 if (r < 0)
 717                         goto fail;
 718         }
 719
 720         if (!key) /* mDNS doesn't know negative caching, really */
 721                 return 0;
 722
 723         /* Third, add in negative entries if the key has no RR */
 724         r = dns_answer_match_key(answer, key, NULL);
 725         if (r < 0)
 726                 goto fail;
 727         if (r > 0)
 728                 return 0;
 729
 730         /* But not if it has a matching CNAME/DNAME (the negative
 731          * caching will be done on the canonical name, not on the
 732          * alias) */
 733         r = dns_answer_find_cname_or_dname(answer, key, NULL, NULL);
 734         if (r < 0)
 735                 goto fail;
 736         if (r > 0)
 737                 return 0;
 738
 739         /* See https://tools.ietf.org/html/rfc2308, which say that a matching SOA record in the packet is used to
 740          * enable negative caching. We apply one exception though: if we are about to cache a weird rcode we do so
 741          * regardless of a SOA. */
 742         r = dns_answer_find_soa(answer, key, &soa, &flags);
 743         if (r < 0)
 744                 goto fail;
 745         if (r == 0 && !weird_rcode)
 746                 return 0;
 747         if (r > 0) {
 748                 /* Refuse using the SOA data if it is unsigned, but the key is
 749                  * signed */
 750                 if (authenticated && (flags & DNS_ANSWER_AUTHENTICATED) == 0)
 751                         return 0;
 752         }
 753
 754         r = dns_cache_put_negative(
 755                         c,
 756                         key,
 757                         rcode,
 758                         authenticated,
 759                         nsec_ttl,
 760                         timestamp,
 761                         soa,
 762                         owner_family, owner_address);
 763         if (r < 0)
 764                 goto fail;
 765
 766         return 0;
 767
 768 fail:
 769         /* Adding all RRs failed. Let's clean up what we already
 770          * added, just in case */
 771
 772         if (key)
 773                 dns_cache_remove_by_key(c, key);
 774
 775         DNS_ANSWER_FOREACH_FLAGS(rr, flags, answer) {
 776                 if ((flags & DNS_ANSWER_CACHEABLE) == 0)
 777                         continue;
 778
 779                 dns_cache_remove_by_key(c, rr->key);
 780         }
 781
 782         return r;
 783 }
 784
 785 static DnsCacheItem *dns_cache_get_by_key_follow_cname_dname_nsec(DnsCache *c, DnsResourceKey *k) {
 786         DnsCacheItem *i;
 787         const char *n;
 788         int r;
 789
 790         assert(c);
 791         assert(k);
 792
 793         /* If we hit some OOM error, or suchlike, we don't care too
 794          * much, after all this is just a cache */
 795
 796         i = hashmap_get(c->by_key, k);
 797         if (i)
 798                 return i;
 799
 800         n = dns_resource_key_name(k);
 801
 802         /* Check if we have an NXDOMAIN cache item for the name, notice that we use
 803          * the pseudo-type ANY for NXDOMAIN cache items. */
 804         i = hashmap_get(c->by_key, &DNS_RESOURCE_KEY_CONST(k->class, DNS_TYPE_ANY, n));
 805         if (i && i->type == DNS_CACHE_NXDOMAIN)
 806                 return i;
 807
 808         if (dns_type_may_redirect(k->type)) {
 809                 /* Check if we have a CNAME record instead */
 810                 i = hashmap_get(c->by_key, &DNS_RESOURCE_KEY_CONST(k->class, DNS_TYPE_CNAME, n));
 811                 if (i)
 812                         return i;
 813
 814                 /* OK, let's look for cached DNAME records. */
 815                 for (;;) {
 816                         if (isempty(n))
 817                                 return NULL;
 818
 819                         i = hashmap_get(c->by_key, &DNS_RESOURCE_KEY_CONST(k->class, DNS_TYPE_DNAME, n));
 820                         if (i)
 821                                 return i;
 822
 823                         /* Jump one label ahead */
 824                         r = dns_name_parent(&n);
 825                         if (r <= 0)
 826                                 return NULL;
 827                 }
 828         }
 829
 830         if (k->type != DNS_TYPE_NSEC) {
 831                 /* Check if we have an NSEC record instead for the name. */
 832                 i = hashmap_get(c->by_key, &DNS_RESOURCE_KEY_CONST(k->class, DNS_TYPE_NSEC, n));
 833                 if (i)
 834                         return i;
 835         }
 836
 837         return NULL;
 838 }
 839
 840 int dns_cache_lookup(DnsCache *c, DnsResourceKey *key, bool clamp_ttl, int *rcode, DnsAnswer **ret, bool *authenticated) {
 841         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
 842         char key_str[DNS_RESOURCE_KEY_STRING_MAX];
 843         unsigned n = 0;
 844         int r;
 845         bool nxdomain = false;
 846         DnsCacheItem *j, *first, *nsec = NULL;
 847         bool have_authenticated = false, have_non_authenticated = false;
 848         usec_t current;
 849         int found_rcode = -1;
 850
 851         assert(c);
 852         assert(key);
 853         assert(rcode);
 854         assert(ret);
 855         assert(authenticated);
 856
 857         if (key->type == DNS_TYPE_ANY || key->class == DNS_CLASS_ANY) {
 858                 /* If we have ANY lookups we don't use the cache, so
 859                  * that the caller refreshes via the network. */
 860
 861                 log_debug("Ignoring cache for ANY lookup: %s",
 862                           dns_resource_key_to_string(key, key_str, sizeof key_str));
 863
 864                 c->n_miss++;
 865
 866                 *ret = NULL;
 867                 *rcode = DNS_RCODE_SUCCESS;
 868                 *authenticated = false;
 869
 870                 return 0;
 871         }
 872
 873         first = dns_cache_get_by_key_follow_cname_dname_nsec(c, key);
 874         if (!first) {
 875                 /* If one question cannot be answered we need to refresh */
 876
 877                 log_debug("Cache miss for %s",
 878                           dns_resource_key_to_string(key, key_str, sizeof key_str));
 879
 880                 c->n_miss++;
 881
 882                 *ret = NULL;
 883                 *rcode = DNS_RCODE_SUCCESS;
 884                 *authenticated = false;
 885
 886                 return 0;
 887         }
 888
 889         LIST_FOREACH(by_key, j, first) {
 890                 if (j->rr) {
 891                         if (j->rr->key->type == DNS_TYPE_NSEC)
 892                                 nsec = j;
 893
 894                         n++;
 895                 } else if (j->type == DNS_CACHE_NXDOMAIN)
 896                         nxdomain = true;
 897                 else if (j->type == DNS_CACHE_RCODE)
 898                         found_rcode = j->rcode;
 899
 900                 if (j->authenticated)
 901                         have_authenticated = true;
 902                 else
 903                         have_non_authenticated = true;
 904         }
 905
 906         if (found_rcode >= 0) {
 907                 log_debug("RCODE %s cache hit for %s",
 908                           dns_rcode_to_string(found_rcode),
 909                           dns_resource_key_to_string(key, key_str, sizeof(key_str)));
 910
 911                 *ret = NULL;
 912                 *rcode = found_rcode;
 913                 *authenticated = false;
 914
 915                 c->n_hit++;
 916                 return 1;
 917         }
 918
 919         if (nsec && !IN_SET(key->type, DNS_TYPE_NSEC, DNS_TYPE_DS)) {
 920                 /* Note that we won't derive information for DS RRs from an NSEC, because we only cache NSEC RRs from
 921                  * the lower-zone of a zone cut, but the DS RRs are on the upper zone. */
 922
 923                 log_debug("NSEC NODATA cache hit for %s",
 924                           dns_resource_key_to_string(key, key_str, sizeof key_str));
 925
 926                 /* We only found an NSEC record that matches our name.
 927                  * If it says the type doesn't exist report
 928                  * NODATA. Otherwise report a cache miss. */
 929
 930                 *ret = NULL;
 931                 *rcode = DNS_RCODE_SUCCESS;
 932                 *authenticated = nsec->authenticated;
 933
 934                 if (!bitmap_isset(nsec->rr->nsec.types, key->type) &&
 935                     !bitmap_isset(nsec->rr->nsec.types, DNS_TYPE_CNAME) &&
 936                     !bitmap_isset(nsec->rr->nsec.types, DNS_TYPE_DNAME)) {
 937                         c->n_hit++;
 938                         return 1;
 939                 }
 940
 941                 c->n_miss++;
 942                 return 0;
 943         }
 944
 945         log_debug("%s cache hit for %s",
 946                   n > 0    ? "Positive" :
 947                   nxdomain ? "NXDOMAIN" : "NODATA",
 948                   dns_resource_key_to_string(key, key_str, sizeof key_str));
 949
 950         if (n <= 0) {
 951                 c->n_hit++;
 952
 953                 *ret = NULL;
 954                 *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS;
 955                 *authenticated = have_authenticated && !have_non_authenticated;
 956                 return 1;
 957         }
 958
 959         answer = dns_answer_new(n);
 960         if (!answer)
 961                 return -ENOMEM;
 962
 963         if (clamp_ttl)
 964                 current = now(clock_boottime_or_monotonic());
 965
 966         LIST_FOREACH(by_key, j, first) {
 967                 _cleanup_(dns_resource_record_unrefp) DnsResourceRecord *rr = NULL;
 968
 969                 if (!j->rr)
 970                         continue;
 971
 972                 if (clamp_ttl) {
 973                         rr = dns_resource_record_ref(j->rr);
 974
 975                         r = dns_resource_record_clamp_ttl(&rr, LESS_BY(j->until, current) / USEC_PER_SEC);
 976                         if (r < 0)
 977                                 return r;
 978                 }
 979
 980                 r = dns_answer_add(answer, rr ?: j->rr, j->ifindex, j->authenticated ? DNS_ANSWER_AUTHENTICATED : 0);
 981                 if (r < 0)
 982                         return r;
 983         }
 984
 985         c->n_hit++;
 986
 987         *ret = answer;
 988         *rcode = DNS_RCODE_SUCCESS;
 989         *authenticated = have_authenticated && !have_non_authenticated;
 990         answer = NULL;
 991
 992         return n;
 993 }
 994
 995 int dns_cache_check_conflicts(DnsCache *cache, DnsResourceRecord *rr, int owner_family, const union in_addr_union *owner_address) {
 996         DnsCacheItem *i, *first;
 997         bool same_owner = true;
 998
 999         assert(cache);
1000         assert(rr);
1001
1002         dns_cache_prune(cache);
1003
1004         /* See if there's a cache entry for the same key. If there
1005          * isn't there's no conflict */
1006         first = hashmap_get(cache->by_key, rr->key);
1007         if (!first)
1008                 return 0;
1009
1010         /* See if the RR key is owned by the same owner, if so, there
1011          * isn't a conflict either */
1012         LIST_FOREACH(by_key, i, first) {
1013                 if (i->owner_family != owner_family ||
1014                     !in_addr_equal(owner_family, &i->owner_address, owner_address)) {
1015                         same_owner = false;
1016                         break;
1017                 }
1018         }
1019         if (same_owner)
1020                 return 0;
1021
1022         /* See if there's the exact same RR in the cache. If yes, then
1023          * there's no conflict. */
1024         if (dns_cache_get(cache, rr))
1025                 return 0;
1026
1027         /* There's a conflict */
1028         return 1;
1029 }
1030
1031 int dns_cache_export_shared_to_packet(DnsCache *cache, DnsPacket *p) {
1032         unsigned ancount = 0;
1033         Iterator iterator;
1034         DnsCacheItem *i;
1035         int r;
1036
1037         assert(cache);
1038         assert(p);
1039
1040         HASHMAP_FOREACH(i, cache->by_key, iterator) {
1041                 DnsCacheItem *j;
1042
1043                 LIST_FOREACH(by_key, j, i) {
1044                         if (!j->rr)
1045                                 continue;
1046
1047                         if (!j->shared_owner)
1048                                 continue;
1049
1050                         r = dns_packet_append_rr(p, j->rr, 0, NULL, NULL);
1051                         if (r == -EMSGSIZE && p->protocol == DNS_PROTOCOL_MDNS) {
1052                                 /* For mDNS, if we're unable to stuff all known answers into the given packet,
1053                                  * allocate a new one, push the RR into that one and link it to the current one.
1054                                  */
1055
1056                                 DNS_PACKET_HEADER(p)->ancount = htobe16(ancount);
1057                                 ancount = 0;
1058
1059                                 r = dns_packet_new_query(&p->more, p->protocol, 0, true);
1060                                 if (r < 0)
1061                                         return r;
1062
1063                                 /* continue with new packet */
1064                                 p = p->more;
1065                                 r = dns_packet_append_rr(p, j->rr, 0, NULL, NULL);
1066                         }
1067
1068                         if (r < 0)
1069                                 return r;
1070
1071                         ancount++;
1072                 }
1073         }
1074
1075         DNS_PACKET_HEADER(p)->ancount = htobe16(ancount);
1076
1077         return 0;
1078 }
1079
1080 void dns_cache_dump(DnsCache *cache, FILE *f) {
1081         Iterator iterator;
1082         DnsCacheItem *i;
1083
1084         if (!cache)
1085                 return;
1086
1087         if (!f)
1088                 f = stdout;
1089
1090         HASHMAP_FOREACH(i, cache->by_key, iterator) {
1091                 DnsCacheItem *j;
1092
1093                 LIST_FOREACH(by_key, j, i) {
1094
1095                         fputc('\t', f);
1096
1097                         if (j->rr) {
1098                                 const char *t;
1099                                 t = dns_resource_record_to_string(j->rr);
1100                                 if (!t) {
1101                                         log_oom();
1102                                         continue;
1103                                 }
1104
1105                                 fputs(t, f);
1106                                 fputc('\n', f);
1107                         } else {
1108                                 char key_str[DNS_RESOURCE_KEY_STRING_MAX];
1109
1110                                 fputs(dns_resource_key_to_string(j->key, key_str, sizeof key_str), f);
1111                                 fputs(" -- ", f);
1112                                 fputs(dns_cache_item_type_to_string(j), f);
1113                                 fputc('\n', f);
1114                         }
1115                 }
1116         }
1117 }
1118
1119 bool dns_cache_is_empty(DnsCache *cache) {
1120         if (!cache)
1121                 return true;
1122
1123         return hashmap_isempty(cache->by_key);
1124 }
1125
1126 unsigned dns_cache_size(DnsCache *cache) {
1127         if (!cache)
1128                 return 0;
1129
1130         return hashmap_size(cache->by_key);
1131 }