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