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