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
 251         dns_resource_record_ref(rr);
 252         dns_resource_record_unref(i->rr);
 253         i->rr = rr;
 254
 255         dns_resource_key_unref(i->key);
 256         i->key = dns_resource_key_ref(rr->key);
 257
 258         i->until = timestamp + MIN(rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 259
 260         prioq_reshuffle(c->by_expiry, i, &i->prioq_idx);
 261 }
 262
 263 static int dns_cache_put_positive(
 264                 DnsCache *c,
 265                 DnsResourceRecord *rr,
 266                 usec_t timestamp,
 267                 int owner_family,
 268                 const union in_addr_union *owner_address) {
 269
 270         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
 271         _cleanup_free_ char *key_str = NULL;
 272         DnsCacheItem *existing;
 273         int r;
 274
 275         assert(c);
 276         assert(rr);
 277         assert(owner_address);
 278
 279         /* New TTL is 0? Delete the entry... */
 280         if (rr->ttl <= 0) {
 281                 if (dns_cache_remove(c, rr->key)) {
 282                         r = dns_resource_key_to_string(rr->key, &key_str);
 283                         if (r < 0)
 284                                 return r;
 285
 286                         log_debug("Removed zero TTL entry from cache: %s", key_str);
 287                 }
 288
 289                 return 0;
 290         }
 291
 292         if (rr->key->class == DNS_CLASS_ANY)
 293                 return 0;
 294         if (rr->key->type == DNS_TYPE_ANY)
 295                 return 0;
 296
 297         /* Entry exists already? Update TTL and timestamp */
 298         existing = dns_cache_get(c, rr);
 299         if (existing) {
 300                 dns_cache_item_update_positive(c, existing, rr, timestamp);
 301                 return 0;
 302         }
 303
 304         /* Otherwise, add the new RR */
 305         r = dns_cache_init(c);
 306         if (r < 0)
 307                 return r;
 308
 309         dns_cache_make_space(c, 1);
 310
 311         i = new0(DnsCacheItem, 1);
 312         if (!i)
 313                 return -ENOMEM;
 314
 315         i->type = DNS_CACHE_POSITIVE;
 316         i->key = dns_resource_key_ref(rr->key);
 317         i->rr = dns_resource_record_ref(rr);
 318         i->until = timestamp + MIN(i->rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 319         i->prioq_idx = PRIOQ_IDX_NULL;
 320         i->owner_family = owner_family;
 321         i->owner_address = *owner_address;
 322
 323         r = dns_cache_link_item(c, i);
 324         if (r < 0)
 325                 return r;
 326
 327         r = dns_resource_key_to_string(i->key, &key_str);
 328         if (r < 0)
 329                 return r;
 330
 331         log_debug("Added cache entry for %s", key_str);
 332
 333         i = NULL;
 334         return 0;
 335 }
 336
 337 static int dns_cache_put_negative(
 338                 DnsCache *c,
 339                 DnsResourceKey *key,
 340                 int rcode,
 341                 usec_t timestamp,
 342                 uint32_t soa_ttl,
 343                 int owner_family,
 344                 const union in_addr_union *owner_address) {
 345
 346         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
 347         _cleanup_free_ char *key_str = NULL;
 348         int r;
 349
 350         assert(c);
 351         assert(key);
 352         assert(owner_address);
 353
 354         dns_cache_remove(c, key);
 355
 356         if (key->class == DNS_CLASS_ANY)
 357                 return 0;
 358         if (key->type == DNS_TYPE_ANY)
 359                 return 0;
 360         if (soa_ttl <= 0) {
 361                 r = dns_resource_key_to_string(key, &key_str);
 362                 if (r < 0)
 363                         return r;
 364
 365                 log_debug("Ignored negative cache entry with zero SOA TTL: %s", key_str);
 366
 367                 return 0;
 368         }
 369
 370         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
 371                 return 0;
 372
 373         r = dns_cache_init(c);
 374         if (r < 0)
 375                 return r;
 376
 377         dns_cache_make_space(c, 1);
 378
 379         i = new0(DnsCacheItem, 1);
 380         if (!i)
 381                 return -ENOMEM;
 382
 383         i->type = rcode == DNS_RCODE_SUCCESS ? DNS_CACHE_NODATA : DNS_CACHE_NXDOMAIN;
 384         i->key = dns_resource_key_ref(key);
 385         i->until = timestamp + MIN(soa_ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 386         i->prioq_idx = PRIOQ_IDX_NULL;
 387         i->owner_family = owner_family;
 388         i->owner_address = *owner_address;
 389
 390         r = dns_cache_link_item(c, i);
 391         if (r < 0)
 392                 return r;
 393
 394         r = dns_resource_key_to_string(i->key, &key_str);
 395         if (r < 0)
 396                 return r;
 397
 398         log_debug("Added %s cache entry for %s", i->type == DNS_CACHE_NODATA ? "NODATA" : "NXDOMAIN", key_str);
 399
 400         i = NULL;
 401         return 0;
 402 }
 403
 404 int dns_cache_put(
 405                 DnsCache *c,
 406                 DnsQuestion *q,
 407                 int rcode,
 408                 DnsAnswer *answer,
 409                 unsigned max_rrs,
 410                 usec_t timestamp,
 411                 int owner_family,
 412                 const union in_addr_union *owner_address) {
 413
 414         unsigned cache_keys, i;
 415         int r;
 416
 417         assert(c);
 418
 419         if (q) {
 420                 /* First, if we were passed a question, delete all matching old RRs,
 421                  * so that we only keep complete by_key in place. */
 422                 for (i = 0; i < q->n_keys; i++)
 423                         dns_cache_remove(c, q->keys[i]);
 424         }
 425
 426         if (!answer)
 427                 return 0;
 428
 429         for (i = 0; i < answer->n_rrs; i++)
 430                 dns_cache_remove(c, answer->items[i].rr->key);
 431
 432         /* We only care for positive replies and NXDOMAINs, on all
 433          * other replies we will simply flush the respective entries,
 434          * and that's it */
 435
 436         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
 437                 return 0;
 438
 439         cache_keys = answer->n_rrs;
 440
 441         if (q)
 442                 cache_keys += q->n_keys;
 443
 444         /* Make some space for our new entries */
 445         dns_cache_make_space(c, cache_keys);
 446
 447         if (timestamp <= 0)
 448                 timestamp = now(clock_boottime_or_monotonic());
 449
 450         /* Second, add in positive entries for all contained RRs */
 451         for (i = 0; i < MIN(max_rrs, answer->n_rrs); i++) {
 452                 r = dns_cache_put_positive(c, answer->items[i].rr, timestamp, owner_family, owner_address);
 453                 if (r < 0)
 454                         goto fail;
 455         }
 456
 457         if (!q)
 458                 return 0;
 459
 460         /* Third, add in negative entries for all keys with no RR */
 461         for (i = 0; i < q->n_keys; i++) {
 462                 DnsResourceRecord *soa = NULL;
 463
 464                 r = dns_answer_contains(answer, q->keys[i]);
 465                 if (r < 0)
 466                         goto fail;
 467                 if (r > 0)
 468                         continue;
 469
 470                 /* See https://tools.ietf.org/html/rfc2308, which
 471                  * say that a matching SOA record in the packet
 472                  * is used to to enable negative caching. */
 473
 474                 r = dns_answer_find_soa(answer, q->keys[i], &soa);
 475                 if (r < 0)
 476                         goto fail;
 477                 if (r == 0)
 478                         continue;
 479
 480                 r = dns_cache_put_negative(c, q->keys[i], rcode, timestamp, MIN(soa->soa.minimum, soa->ttl), owner_family, owner_address);
 481                 if (r < 0)
 482                         goto fail;
 483         }
 484
 485         return 0;
 486
 487 fail:
 488         /* Adding all RRs failed. Let's clean up what we already
 489          * added, just in case */
 490
 491         if (q) {
 492                 for (i = 0; i < q->n_keys; i++)
 493                         dns_cache_remove(c, q->keys[i]);
 494         }
 495
 496         for (i = 0; i < answer->n_rrs; i++)
 497                 dns_cache_remove(c, answer->items[i].rr->key);
 498
 499         return r;
 500 }
 501
 502 int dns_cache_lookup(DnsCache *c, DnsResourceKey *key, int *rcode, DnsAnswer **ret) {
 503         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
 504         unsigned n = 0;
 505         int r;
 506         bool nxdomain = false;
 507         _cleanup_free_ char *key_str = NULL;
 508         DnsCacheItem *j, *first;
 509
 510         assert(c);
 511         assert(key);
 512         assert(rcode);
 513         assert(ret);
 514
 515         if (key->type == DNS_TYPE_ANY ||
 516             key->class == DNS_CLASS_ANY) {
 517
 518                 /* If we have ANY lookups we simply refresh */
 519
 520                 r = dns_resource_key_to_string(key, &key_str);
 521                 if (r < 0)
 522                         return r;
 523
 524                 log_debug("Ignoring cache for ANY lookup: %s", key_str);
 525
 526                 *ret = NULL;
 527                 *rcode = DNS_RCODE_SUCCESS;
 528                 return 0;
 529         }
 530
 531         first = hashmap_get(c->by_key, key);
 532         if (!first) {
 533                 /* If one question cannot be answered we need to refresh */
 534
 535                 r = dns_resource_key_to_string(key, &key_str);
 536                 if (r < 0)
 537                         return r;
 538
 539                 log_debug("Cache miss for %s", key_str);
 540
 541                 *ret = NULL;
 542                 *rcode = DNS_RCODE_SUCCESS;
 543                 return 0;
 544         }
 545
 546         LIST_FOREACH(by_key, j, first) {
 547                 if (j->rr)
 548                         n++;
 549                 else if (j->type == DNS_CACHE_NXDOMAIN)
 550                         nxdomain = true;
 551         }
 552
 553         r = dns_resource_key_to_string(key, &key_str);
 554         if (r < 0)
 555                 return r;
 556
 557         log_debug("%s cache hit for %s",
 558                   nxdomain ? "NXDOMAIN" :
 559                      n > 0 ? "Positive" : "NODATA",
 560                   key_str);
 561
 562         if (n <= 0) {
 563                 *ret = NULL;
 564                 *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS;
 565                 return 1;
 566         }
 567
 568         answer = dns_answer_new(n);
 569         if (!answer)
 570                 return -ENOMEM;
 571
 572         LIST_FOREACH(by_key, j, first) {
 573                 if (!j->rr)
 574                         continue;
 575
 576                 r = dns_answer_add(answer, j->rr, 0);
 577                 if (r < 0)
 578                         return r;
 579         }
 580
 581         *ret = answer;
 582         *rcode = DNS_RCODE_SUCCESS;
 583         answer = NULL;
 584
 585         return n;
 586 }
 587
 588 int dns_cache_check_conflicts(DnsCache *cache, DnsResourceRecord *rr, int owner_family, const union in_addr_union *owner_address) {
 589         DnsCacheItem *i, *first;
 590         bool same_owner = true;
 591
 592         assert(cache);
 593         assert(rr);
 594
 595         dns_cache_prune(cache);
 596
 597         /* See if there's a cache entry for the same key. If there
 598          * isn't there's no conflict */
 599         first = hashmap_get(cache->by_key, rr->key);
 600         if (!first)
 601                 return 0;
 602
 603         /* See if the RR key is owned by the same owner, if so, there
 604          * isn't a conflict either */
 605         LIST_FOREACH(by_key, i, first) {
 606                 if (i->owner_family != owner_family ||
 607                     !in_addr_equal(owner_family, &i->owner_address, owner_address)) {
 608                         same_owner = false;
 609                         break;
 610                 }
 611         }
 612         if (same_owner)
 613                 return 0;
 614
 615         /* See if there's the exact same RR in the cache. If yes, then
 616          * there's no conflict. */
 617         if (dns_cache_get(cache, rr))
 618                 return 0;
 619
 620         /* There's a conflict */
 621         return 1;
 622 }