src/resolve/resolved-dns-cache.c

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