src/resolve/resolved-dns-cache.c

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