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 "resolved-dns-cache.h"
  23 #include "resolved-dns-packet.h"
  24
  25 /* Never cache more than 1K entries */
  26 #define CACHE_MAX 1024
  27
  28 /* We never keep any item longer than 10min in our cache */
  29 #define CACHE_TTL_MAX_USEC (10 * USEC_PER_MINUTE)
  30
  31 typedef enum DnsCacheItemType DnsCacheItemType;
  32 typedef struct DnsCacheItem DnsCacheItem;
  33
  34 enum DnsCacheItemType {
  35         DNS_CACHE_POSITIVE,
  36         DNS_CACHE_NODATA,
  37         DNS_CACHE_NXDOMAIN,
  38 };
  39
  40 struct DnsCacheItem {
  41         DnsResourceKey *key;
  42         DnsResourceRecord *rr;
  43         usec_t until;
  44         DnsCacheItemType type;
  45         unsigned prioq_idx;
  46         int owner_family;
  47         union in_addr_union owner_address;
  48         LIST_FIELDS(DnsCacheItem, by_key);
  49 };
  50
  51 static void dns_cache_item_free(DnsCacheItem *i) {
  52         if (!i)
  53                 return;
  54
  55         dns_resource_record_unref(i->rr);
  56         dns_resource_key_unref(i->key);
  57         free(i);
  58 }
  59
  60 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsCacheItem*, dns_cache_item_free);
  61
  62 static void dns_cache_item_remove_and_free(DnsCache *c, DnsCacheItem *i) {
  63         DnsCacheItem *first;
  64
  65         assert(c);
  66
  67         if (!i)
  68                 return;
  69
  70         first = hashmap_get(c->by_key, i->key);
  71         LIST_REMOVE(by_key, first, i);
  72
  73         if (first)
  74                 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
  75         else
  76                 hashmap_remove(c->by_key, i->key);
  77
  78         prioq_remove(c->by_expiry, i, &i->prioq_idx);
  79
  80         dns_cache_item_free(i);
  81 }
  82
  83 void dns_cache_flush(DnsCache *c) {
  84         DnsCacheItem *i;
  85
  86         assert(c);
  87
  88         while ((i = hashmap_first(c->by_key)))
  89                 dns_cache_item_remove_and_free(c, i);
  90
  91         assert(hashmap_size(c->by_key) == 0);
  92         assert(prioq_size(c->by_expiry) == 0);
  93
  94         c->by_key = hashmap_free(c->by_key);
  95         c->by_expiry = prioq_free(c->by_expiry);
  96 }
  97
  98 static bool dns_cache_remove(DnsCache *c, DnsResourceKey *key) {
  99         DnsCacheItem *i;
 100         bool exist = false;
 101
 102         assert(c);
 103         assert(key);
 104
 105         while ((i = hashmap_get(c->by_key, key))) {
 106                 dns_cache_item_remove_and_free(c, i);
 107                 exist = true;
 108         }
 109
 110         return exist;
 111 }
 112
 113 static void dns_cache_make_space(DnsCache *c, unsigned add) {
 114         assert(c);
 115
 116         if (add <= 0)
 117                 return;
 118
 119         /* Makes space for n new entries. Note that we actually allow
 120          * the cache to grow beyond CACHE_MAX, but only when we shall
 121          * add more RRs to the cache than CACHE_MAX at once. In that
 122          * case the cache will be emptied completely otherwise. */
 123
 124         for (;;) {
 125                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
 126                 DnsCacheItem *i;
 127
 128                 if (prioq_size(c->by_expiry) <= 0)
 129                         break;
 130
 131                 if (prioq_size(c->by_expiry) + add < CACHE_MAX)
 132                         break;
 133
 134                 i = prioq_peek(c->by_expiry);
 135                 assert(i);
 136
 137                 /* Take an extra reference to the key so that it
 138                  * doesn't go away in the middle of the remove call */
 139                 key = dns_resource_key_ref(i->key);
 140                 dns_cache_remove(c, key);
 141         }
 142 }
 143
 144 void dns_cache_prune(DnsCache *c) {
 145         usec_t t = 0;
 146
 147         assert(c);
 148
 149         /* Remove all entries that are past their TTL */
 150
 151         for (;;) {
 152                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
 153                 DnsCacheItem *i;
 154
 155                 i = prioq_peek(c->by_expiry);
 156                 if (!i)
 157                         break;
 158
 159                 if (t <= 0)
 160                         t = now(clock_boottime_or_monotonic());
 161
 162                 if (i->until > t)
 163                         break;
 164
 165                 /* Take an extra reference to the key so that it
 166                  * doesn't go away in the middle of the remove call */
 167                 key = dns_resource_key_ref(i->key);
 168                 dns_cache_remove(c, key);
 169         }
 170 }
 171
 172 static int dns_cache_item_prioq_compare_func(const void *a, const void *b) {
 173         const DnsCacheItem *x = a, *y = b;
 174
 175         if (x->until < y->until)
 176                 return -1;
 177         if (x->until > y->until)
 178                 return 1;
 179         return 0;
 180 }
 181
 182 static int dns_cache_init(DnsCache *c) {
 183         int r;
 184
 185         assert(c);
 186
 187         r = prioq_ensure_allocated(&c->by_expiry, dns_cache_item_prioq_compare_func);
 188         if (r < 0)
 189                 return r;
 190
 191         r = hashmap_ensure_allocated(&c->by_key, &dns_resource_key_hash_ops);
 192         if (r < 0)
 193                 return r;
 194
 195         return r;
 196 }
 197
 198 static int dns_cache_link_item(DnsCache *c, DnsCacheItem *i) {
 199         DnsCacheItem *first;
 200         int r;
 201
 202         assert(c);
 203         assert(i);
 204
 205         r = prioq_put(c->by_expiry, i, &i->prioq_idx);
 206         if (r < 0)
 207                 return r;
 208
 209         first = hashmap_get(c->by_key, i->key);
 210         if (first) {
 211                 LIST_PREPEND(by_key, first, i);
 212                 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
 213         } else {
 214                 r = hashmap_put(c->by_key, i->key, i);
 215                 if (r < 0) {
 216                         prioq_remove(c->by_expiry, i, &i->prioq_idx);
 217                         return r;
 218                 }
 219         }
 220
 221         return 0;
 222 }
 223
 224 static DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) {
 225         DnsCacheItem *i;
 226
 227         assert(c);
 228         assert(rr);
 229
 230         LIST_FOREACH(by_key, i, hashmap_get(c->by_key, rr->key))
 231                 if (i->rr && dns_resource_record_equal(i->rr, rr) > 0)
 232                         return i;
 233
 234         return NULL;
 235 }
 236
 237 static void dns_cache_item_update_positive(DnsCache *c, DnsCacheItem *i, DnsResourceRecord *rr, usec_t timestamp) {
 238         assert(c);
 239         assert(i);
 240         assert(rr);
 241
 242         i->type = DNS_CACHE_POSITIVE;
 243
 244         if (!i->by_key_prev)
 245                 /* We are the first item in the list, we need to
 246                  * update the key used in the hashmap */
 247
 248                 assert_se(hashmap_replace(c->by_key, rr->key, i) >= 0);
 249
 250         dns_resource_record_ref(rr);
 251         dns_resource_record_unref(i->rr);
 252         i->rr = rr;
 253
 254         dns_resource_key_unref(i->key);
 255         i->key = dns_resource_key_ref(rr->key);
 256
 257         i->until = timestamp + MIN(rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 258
 259         prioq_reshuffle(c->by_expiry, i, &i->prioq_idx);
 260 }
 261
 262 static int dns_cache_put_positive(
 263                 DnsCache *c,
 264                 DnsResourceRecord *rr,
 265                 usec_t timestamp,
 266                 int owner_family,
 267                 const union in_addr_union *owner_address) {
 268
 269         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
 270         _cleanup_free_ char *key_str = NULL;
 271         DnsCacheItem *existing;
 272         int r;
 273
 274         assert(c);
 275         assert(rr);
 276         assert(owner_address);
 277
 278         /* New TTL is 0? Delete the entry... */
 279         if (rr->ttl <= 0) {
 280                 if (dns_cache_remove(c, rr->key)) {
 281                         r = dns_resource_key_to_string(rr->key, &key_str);
 282                         if (r < 0)
 283                                 return r;
 284
 285                         log_debug("Removed zero TTL entry from cache: %s", key_str);
 286                 }
 287
 288                 return 0;
 289         }
 290
 291         if (rr->key->class == DNS_CLASS_ANY)
 292                 return 0;
 293         if (rr->key->type == DNS_TYPE_ANY)
 294                 return 0;
 295
 296         /* Entry exists already? Update TTL and timestamp */
 297         existing = dns_cache_get(c, rr);
 298         if (existing) {
 299                 dns_cache_item_update_positive(c, existing, rr, timestamp);
 300                 return 0;
 301         }
 302
 303         /* Otherwise, add the new RR */
 304         r = dns_cache_init(c);
 305         if (r < 0)
 306                 return r;
 307
 308         dns_cache_make_space(c, 1);
 309
 310         i = new0(DnsCacheItem, 1);
 311         if (!i)
 312                 return -ENOMEM;
 313
 314         i->type = DNS_CACHE_POSITIVE;
 315         i->key = dns_resource_key_ref(rr->key);
 316         i->rr = dns_resource_record_ref(rr);
 317         i->until = timestamp + MIN(i->rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 318         i->prioq_idx = PRIOQ_IDX_NULL;
 319         i->owner_family = owner_family;
 320         i->owner_address = *owner_address;
 321
 322         r = dns_cache_link_item(c, i);
 323         if (r < 0)
 324                 return r;
 325
 326         r = dns_resource_key_to_string(i->key, &key_str);
 327         if (r < 0)
 328                 return r;
 329
 330         log_debug("Added cache entry for %s", key_str);
 331
 332         i = NULL;
 333         return 0;
 334 }
 335
 336 static int dns_cache_put_negative(
 337                 DnsCache *c,
 338                 DnsResourceKey *key,
 339                 int rcode,
 340                 usec_t timestamp,
 341                 uint32_t soa_ttl,
 342                 int owner_family,
 343                 const union in_addr_union *owner_address) {
 344
 345         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
 346         _cleanup_free_ char *key_str = NULL;
 347         int r;
 348
 349         assert(c);
 350         assert(key);
 351         assert(owner_address);
 352
 353         dns_cache_remove(c, key);
 354
 355         if (key->class == DNS_CLASS_ANY)
 356                 return 0;
 357         if (key->type == DNS_TYPE_ANY)
 358                 return 0;
 359         if (soa_ttl <= 0) {
 360                 r = dns_resource_key_to_string(key, &key_str);
 361                 if (r < 0)
 362                         return r;
 363
 364                 log_debug("Ignored negative cache entry with zero SOA TTL: %s", key_str);
 365
 366                 return 0;
 367         }
 368
 369         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
 370                 return 0;
 371
 372         r = dns_cache_init(c);
 373         if (r < 0)
 374                 return r;
 375
 376         dns_cache_make_space(c, 1);
 377
 378         i = new0(DnsCacheItem, 1);
 379         if (!i)
 380                 return -ENOMEM;
 381
 382         i->type = rcode == DNS_RCODE_SUCCESS ? DNS_CACHE_NODATA : DNS_CACHE_NXDOMAIN;
 383         i->key = dns_resource_key_ref(key);
 384         i->until = timestamp + MIN(soa_ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 385         i->prioq_idx = PRIOQ_IDX_NULL;
 386         i->owner_family = owner_family;
 387         i->owner_address = *owner_address;
 388
 389         r = dns_cache_link_item(c, i);
 390         if (r < 0)
 391                 return r;
 392
 393         r = dns_resource_key_to_string(i->key, &key_str);
 394         if (r < 0)
 395                 return r;
 396
 397         log_debug("Added %s cache entry for %s", i->type == DNS_CACHE_NODATA ? "NODATA" : "NXDOMAIN", key_str);
 398
 399         i = NULL;
 400         return 0;
 401 }
 402
 403 int dns_cache_put(
 404                 DnsCache *c,
 405                 DnsQuestion *q,
 406                 int rcode,
 407                 DnsAnswer *answer,
 408                 unsigned max_rrs,
 409                 usec_t timestamp,
 410                 int owner_family,
 411                 const union in_addr_union *owner_address) {
 412
 413         unsigned cache_keys, i;
 414         int r;
 415
 416         assert(c);
 417
 418         if (q) {
 419                 /* First, if we were passed a question, delete all matching old RRs,
 420                  * so that we only keep complete by_key in place. */
 421                 for (i = 0; i < q->n_keys; i++)
 422                         dns_cache_remove(c, q->keys[i]);
 423         }
 424
 425         if (!answer)
 426                 return 0;
 427
 428         for (i = 0; i < answer->n_rrs; i++)
 429                 dns_cache_remove(c, answer->items[i].rr->key);
 430
 431         /* We only care for positive replies and NXDOMAINs, on all
 432          * other replies we will simply flush the respective entries,
 433          * and that's it */
 434
 435         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
 436                 return 0;
 437
 438         cache_keys = answer->n_rrs;
 439
 440         if (q)
 441                 cache_keys += q->n_keys;
 442
 443         /* Make some space for our new entries */
 444         dns_cache_make_space(c, cache_keys);
 445
 446         if (timestamp <= 0)
 447                 timestamp = now(clock_boottime_or_monotonic());
 448
 449         /* Second, add in positive entries for all contained RRs */
 450         for (i = 0; i < MIN(max_rrs, answer->n_rrs); i++) {
 451                 r = dns_cache_put_positive(c, answer->items[i].rr, timestamp, owner_family, owner_address);
 452                 if (r < 0)
 453                         goto fail;
 454         }
 455
 456         if (!q)
 457                 return 0;
 458
 459         /* Third, add in negative entries for all keys with no RR */
 460         for (i = 0; i < q->n_keys; i++) {
 461                 DnsResourceRecord *soa = NULL;
 462
 463                 r = dns_answer_contains(answer, q->keys[i]);
 464                 if (r < 0)
 465                         goto fail;
 466                 if (r > 0)
 467                         continue;
 468
 469                 /* See https://tools.ietf.org/html/rfc2308, which
 470                  * say that a matching SOA record in the packet
 471                  * is used to to enable negative caching. */
 472
 473                 r = dns_answer_find_soa(answer, q->keys[i], &soa);
 474                 if (r < 0)
 475                         goto fail;
 476                 if (r == 0)
 477                         continue;
 478
 479                 r = dns_cache_put_negative(c, q->keys[i], rcode, timestamp, MIN(soa->soa.minimum, soa->ttl), owner_family, owner_address);
 480                 if (r < 0)
 481                         goto fail;
 482         }
 483
 484         return 0;
 485
 486 fail:
 487         /* Adding all RRs failed. Let's clean up what we already
 488          * added, just in case */
 489
 490         if (q) {
 491                 for (i = 0; i < q->n_keys; i++)
 492                         dns_cache_remove(c, q->keys[i]);
 493         }
 494
 495         for (i = 0; i < answer->n_rrs; i++)
 496                 dns_cache_remove(c, answer->items[i].rr->key);
 497
 498         return r;
 499 }
 500
 501 int dns_cache_lookup(DnsCache *c, DnsResourceKey *key, int *rcode, DnsAnswer **ret) {
 502         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
 503         unsigned n = 0;
 504         int r;
 505         bool nxdomain = false;
 506         _cleanup_free_ char *key_str = NULL;
 507         DnsCacheItem *j, *first;
 508
 509         assert(c);
 510         assert(key);
 511         assert(rcode);
 512         assert(ret);
 513
 514         if (key->type == DNS_TYPE_ANY ||
 515             key->class == DNS_CLASS_ANY) {
 516
 517                 /* If we have ANY lookups we simply refresh */
 518
 519                 r = dns_resource_key_to_string(key, &key_str);
 520                 if (r < 0)
 521                         return r;
 522
 523                 log_debug("Ignoring cache for ANY lookup: %s", key_str);
 524
 525                 *ret = NULL;
 526                 *rcode = DNS_RCODE_SUCCESS;
 527                 return 0;
 528         }
 529
 530         first = hashmap_get(c->by_key, key);
 531         if (!first) {
 532                 /* If one question cannot be answered we need to refresh */
 533
 534                 r = dns_resource_key_to_string(key, &key_str);
 535                 if (r < 0)
 536                         return r;
 537
 538                 log_debug("Cache miss for %s", key_str);
 539
 540                 *ret = NULL;
 541                 *rcode = DNS_RCODE_SUCCESS;
 542                 return 0;
 543         }
 544
 545         LIST_FOREACH(by_key, j, first) {
 546                 if (j->rr)
 547                         n++;
 548                 else if (j->type == DNS_CACHE_NXDOMAIN)
 549                         nxdomain = true;
 550         }
 551
 552         r = dns_resource_key_to_string(key, &key_str);
 553         if (r < 0)
 554                 return r;
 555
 556         log_debug("%s cache hit for %s",
 557                   nxdomain ? "NXDOMAIN" :
 558                      n > 0 ? "Positive" : "NODATA",
 559                   key_str);
 560
 561         if (n <= 0) {
 562                 *ret = NULL;
 563                 *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS;
 564                 return 1;
 565         }
 566
 567         answer = dns_answer_new(n);
 568         if (!answer)
 569                 return -ENOMEM;
 570
 571         LIST_FOREACH(by_key, j, first) {
 572                 if (!j->rr)
 573                         continue;
 574
 575                 r = dns_answer_add(answer, j->rr, 0);
 576                 if (r < 0)
 577                         return r;
 578         }
 579
 580         *ret = answer;
 581         *rcode = DNS_RCODE_SUCCESS;
 582         answer = NULL;
 583
 584         return n;
 585 }
 586
 587 int dns_cache_check_conflicts(DnsCache *cache, DnsResourceRecord *rr, int owner_family, const union in_addr_union *owner_address) {
 588         DnsCacheItem *i, *first;
 589         bool same_owner = true;
 590
 591         assert(cache);
 592         assert(rr);
 593
 594         dns_cache_prune(cache);
 595
 596         /* See if there's a cache entry for the same key. If there
 597          * isn't there's no conflict */
 598         first = hashmap_get(cache->by_key, rr->key);
 599         if (!first)
 600                 return 0;
 601
 602         /* See if the RR key is owned by the same owner, if so, there
 603          * isn't a conflict either */
 604         LIST_FOREACH(by_key, i, first) {
 605                 if (i->owner_family != owner_family ||
 606                     !in_addr_equal(owner_family, &i->owner_address, owner_address)) {
 607                         same_owner = false;
 608                         break;
 609                 }
 610         }
 611         if (same_owner)
 612                 return 0;
 613
 614         /* See if there's the exact same RR in the cache. If yes, then
 615          * there's no conflict. */
 616         if (dns_cache_get(cache, rr))
 617                 return 0;
 618
 619         /* There's a conflict */
 620         return 1;
 621 }
 622
 623 void dns_cache_dump(DnsCache *cache, FILE *f) {
 624         Iterator iterator;
 625         DnsCacheItem *i;
 626         int r;
 627
 628         if (!cache)
 629                 return;
 630
 631         if (!f)
 632                 f = stdout;
 633
 634         HASHMAP_FOREACH(i, cache->by_key, iterator) {
 635                 DnsCacheItem *j;
 636
 637                 LIST_FOREACH(by_key, j, i) {
 638                         _cleanup_free_ char *t = NULL;
 639
 640                         fputc('\t', f);
 641
 642                         if (j->rr) {
 643                                 r = dns_resource_record_to_string(j->rr, &t);
 644                                 if (r < 0) {
 645                                         log_oom();
 646                                         continue;
 647                                 }
 648
 649                                 fputs(t, f);
 650                                 fputc('\n', f);
 651                         } else {
 652                                 r = dns_resource_key_to_string(j->key, &t);
 653                                 if (r < 0) {
 654                                         log_oom();
 655                                         continue;
 656                                 }
 657
 658                                 fputs(t, f);
 659                                 fputs(" -- ", f);
 660                                 fputs(j->type == DNS_CACHE_NODATA ? "NODATA" : "NXDOMAIN", f);
 661                                 fputc('\n', f);
 662                         }
 663                 }
 664         }
 665 }
 666
 667 bool dns_cache_is_empty(DnsCache *cache) {
 668         if (!cache)
 669                 return true;
 670
 671         return hashmap_isempty(cache->by_key);
 672 }