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 i;
 415         int r;
 416
 417         assert(c);
 418         assert(q);
 419
 420         /* First, delete all matching old RRs, so that we only keep
 421          * complete by_key in place. */
 422         for (i = 0; i < q->n_keys; i++)
 423                 dns_cache_remove(c, q->keys[i]);
 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         /* Make some space for our new entries */
 439         dns_cache_make_space(c, answer->n_rrs + q->n_keys);
 440
 441         if (timestamp <= 0)
 442                 timestamp = now(clock_boottime_or_monotonic());
 443
 444         /* Second, add in positive entries for all contained RRs */
 445         for (i = 0; i < MIN(max_rrs, answer->n_rrs); i++) {
 446                 r = dns_cache_put_positive(c, answer->items[i].rr, timestamp, owner_family, owner_address);
 447                 if (r < 0)
 448                         goto fail;
 449         }
 450
 451         /* Third, add in negative entries for all keys with no RR */
 452         for (i = 0; i < q->n_keys; i++) {
 453                 DnsResourceRecord *soa = NULL;
 454
 455                 r = dns_answer_contains(answer, q->keys[i]);
 456                 if (r < 0)
 457                         goto fail;
 458                 if (r > 0)
 459                         continue;
 460
 461                 /* See https://tools.ietf.org/html/rfc2308, which
 462                  * say that a matching SOA record in the packet
 463                  * is used to to enable negative caching. */
 464
 465                 r = dns_answer_find_soa(answer, q->keys[i], &soa);
 466                 if (r < 0)
 467                         goto fail;
 468                 if (r == 0)
 469                         continue;
 470
 471                 r = dns_cache_put_negative(c, q->keys[i], rcode, timestamp, MIN(soa->soa.minimum, soa->ttl), owner_family, owner_address);
 472                 if (r < 0)
 473                         goto fail;
 474         }
 475
 476         return 0;
 477
 478 fail:
 479         /* Adding all RRs failed. Let's clean up what we already
 480          * added, just in case */
 481
 482         for (i = 0; i < q->n_keys; i++)
 483                 dns_cache_remove(c, q->keys[i]);
 484         for (i = 0; i < answer->n_rrs; i++)
 485                 dns_cache_remove(c, answer->items[i].rr->key);
 486
 487         return r;
 488 }
 489
 490 int dns_cache_lookup(DnsCache *c, DnsResourceKey *key, int *rcode, DnsAnswer **ret) {
 491         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
 492         unsigned n = 0;
 493         int r;
 494         bool nxdomain = false;
 495         _cleanup_free_ char *key_str = NULL;
 496         DnsCacheItem *j, *first;
 497
 498         assert(c);
 499         assert(key);
 500         assert(rcode);
 501         assert(ret);
 502
 503         if (key->type == DNS_TYPE_ANY ||
 504             key->class == DNS_CLASS_ANY) {
 505
 506                 /* If we have ANY lookups we simply refresh */
 507
 508                 r = dns_resource_key_to_string(key, &key_str);
 509                 if (r < 0)
 510                         return r;
 511
 512                 log_debug("Ignoring cache for ANY lookup: %s", key_str);
 513
 514                 *ret = NULL;
 515                 *rcode = DNS_RCODE_SUCCESS;
 516                 return 0;
 517         }
 518
 519         first = hashmap_get(c->by_key, key);
 520         if (!first) {
 521                 /* If one question cannot be answered we need to refresh */
 522
 523                 r = dns_resource_key_to_string(key, &key_str);
 524                 if (r < 0)
 525                         return r;
 526
 527                 log_debug("Cache miss for %s", key_str);
 528
 529                 *ret = NULL;
 530                 *rcode = DNS_RCODE_SUCCESS;
 531                 return 0;
 532         }
 533
 534         LIST_FOREACH(by_key, j, first) {
 535                 if (j->rr)
 536                         n++;
 537                 else if (j->type == DNS_CACHE_NXDOMAIN)
 538                         nxdomain = true;
 539         }
 540
 541         r = dns_resource_key_to_string(key, &key_str);
 542         if (r < 0)
 543                 return r;
 544
 545         log_debug("%s cache hit for %s",
 546                   nxdomain ? "NXDOMAIN" :
 547                      n > 0 ? "Positive" : "NODATA",
 548                   key_str);
 549
 550         if (n <= 0) {
 551                 *ret = NULL;
 552                 *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS;
 553                 return 1;
 554         }
 555
 556         answer = dns_answer_new(n);
 557         if (!answer)
 558                 return -ENOMEM;
 559
 560         LIST_FOREACH(by_key, j, first) {
 561                 if (!j->rr)
 562                         continue;
 563
 564                 r = dns_answer_add(answer, j->rr, 0);
 565                 if (r < 0)
 566                         return r;
 567         }
 568
 569         *ret = answer;
 570         *rcode = DNS_RCODE_SUCCESS;
 571         answer = NULL;
 572
 573         return n;
 574 }
 575
 576 int dns_cache_check_conflicts(DnsCache *cache, DnsResourceRecord *rr, int owner_family, const union in_addr_union *owner_address) {
 577         DnsCacheItem *i, *first;
 578         bool same_owner = true;
 579
 580         assert(cache);
 581         assert(rr);
 582
 583         dns_cache_prune(cache);
 584
 585         /* See if there's a cache entry for the same key. If there
 586          * isn't there's no conflict */
 587         first = hashmap_get(cache->by_key, rr->key);
 588         if (!first)
 589                 return 0;
 590
 591         /* See if the RR key is owned by the same owner, if so, there
 592          * isn't a conflict either */
 593         LIST_FOREACH(by_key, i, first) {
 594                 if (i->owner_family != owner_family ||
 595                     !in_addr_equal(owner_family, &i->owner_address, owner_address)) {
 596                         same_owner = false;
 597                         break;
 598                 }
 599         }
 600         if (same_owner)
 601                 return 0;
 602
 603         /* See if there's the exact same RR in the cache. If yes, then
 604          * there's no conflict. */
 605         if (dns_cache_get(cache, rr))
 606                 return 0;
 607
 608         /* There's a conflict */
 609         return 1;
 610 }