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         hashmap_free(c->by_key);
  95         c->by_key = NULL;
  96
  97         prioq_free(c->by_expiry);
  98         c->by_expiry = NULL;
  99 }
 100
 101 static void dns_cache_remove(DnsCache *c, DnsResourceKey *key) {
 102         DnsCacheItem *i;
 103
 104         assert(c);
 105         assert(key);
 106
 107         while ((i = hashmap_get(c->by_key, key)))
 108                 dns_cache_item_remove_and_free(c, i);
 109 }
 110
 111 static void dns_cache_make_space(DnsCache *c, unsigned add) {
 112         assert(c);
 113
 114         if (add <= 0)
 115                 return;
 116
 117         /* Makes space for n new entries. Note that we actually allow
 118          * the cache to grow beyond CACHE_MAX, but only when we shall
 119          * add more RRs to the cache than CACHE_MAX at once. In that
 120          * case the cache will be emptied completely otherwise. */
 121
 122         for (;;) {
 123                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
 124                 DnsCacheItem *i;
 125
 126                 if (prioq_size(c->by_expiry) <= 0)
 127                         break;
 128
 129                 if (prioq_size(c->by_expiry) + add < CACHE_MAX)
 130                         break;
 131
 132                 i = prioq_peek(c->by_expiry);
 133                 assert(i);
 134
 135                 /* Take an extra reference to the key so that it
 136                  * doesn't go away in the middle of the remove call */
 137                 key = dns_resource_key_ref(i->key);
 138                 dns_cache_remove(c, key);
 139         }
 140 }
 141
 142 void dns_cache_prune(DnsCache *c) {
 143         usec_t t = 0;
 144
 145         assert(c);
 146
 147         /* Remove all entries that are past their TTL */
 148
 149         for (;;) {
 150                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
 151                 DnsCacheItem *i;
 152
 153                 i = prioq_peek(c->by_expiry);
 154                 if (!i)
 155                         break;
 156
 157                 if (t <= 0)
 158                         t = now(CLOCK_BOOTTIME);
 159
 160                 if (i->until > t)
 161                         break;
 162
 163                 /* Take an extra reference to the key so that it
 164                  * doesn't go away in the middle of the remove call */
 165                 key = dns_resource_key_ref(i->key);
 166                 dns_cache_remove(c, key);
 167         }
 168 }
 169
 170 static int dns_cache_item_prioq_compare_func(const void *a, const void *b) {
 171         const DnsCacheItem *x = a, *y = b;
 172
 173         if (x->until < y->until)
 174                 return -1;
 175         if (x->until > y->until)
 176                 return 1;
 177         return 0;
 178 }
 179
 180 static int dns_cache_init(DnsCache *c) {
 181         int r;
 182
 183         assert(c);
 184
 185         r = prioq_ensure_allocated(&c->by_expiry, dns_cache_item_prioq_compare_func);
 186         if (r < 0)
 187                 return r;
 188
 189         r = hashmap_ensure_allocated(&c->by_key, dns_resource_key_hash_func, dns_resource_key_compare_func);
 190         if (r < 0)
 191                 return r;
 192
 193         return r;
 194 }
 195
 196 static int dns_cache_link_item(DnsCache *c, DnsCacheItem *i) {
 197         DnsCacheItem *first;
 198         int r;
 199
 200         assert(c);
 201         assert(i);
 202
 203         r = prioq_put(c->by_expiry, i, &i->prioq_idx);
 204         if (r < 0)
 205                 return r;
 206
 207         first = hashmap_get(c->by_key, i->key);
 208         if (first) {
 209                 LIST_PREPEND(by_key, first, i);
 210                 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
 211         } else {
 212                 r = hashmap_put(c->by_key, i->key, i);
 213                 if (r < 0) {
 214                         prioq_remove(c->by_expiry, i, &i->prioq_idx);
 215                         return r;
 216                 }
 217         }
 218
 219         return 0;
 220 }
 221
 222 static DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) {
 223         DnsCacheItem *i;
 224
 225         assert(c);
 226         assert(rr);
 227
 228         LIST_FOREACH(by_key, i, hashmap_get(c->by_key, rr->key))
 229                 if (i->rr && dns_resource_record_equal(i->rr, rr) > 0)
 230                         return i;
 231
 232         return NULL;
 233 }
 234
 235 static void dns_cache_item_update_positive(DnsCache *c, DnsCacheItem *i, DnsResourceRecord *rr, usec_t timestamp) {
 236         assert(c);
 237         assert(i);
 238         assert(rr);
 239
 240         i->type = DNS_CACHE_POSITIVE;
 241
 242         if (!i->by_key_prev) {
 243                 /* We are the first item in the list, we need to
 244                  * update the key used in the hashmap */
 245
 246                 assert_se(hashmap_replace(c->by_key, rr->key, i) >= 0);
 247         }
 248
 249         dns_resource_record_ref(rr);
 250         dns_resource_record_unref(i->rr);
 251         i->rr = rr;
 252
 253         dns_resource_key_unref(i->key);
 254         i->key = dns_resource_key_ref(rr->key);
 255
 256         i->until = timestamp + MIN(rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 257
 258         prioq_reshuffle(c->by_expiry, i, &i->prioq_idx);
 259 }
 260
 261 static int dns_cache_put_positive(
 262                 DnsCache *c,
 263                 DnsResourceRecord *rr,
 264                 usec_t timestamp,
 265                 int owner_family,
 266                 const union in_addr_union *owner_address) {
 267
 268         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
 269         DnsCacheItem *existing;
 270         int r;
 271
 272         assert(c);
 273         assert(rr);
 274         assert(owner_address);
 275
 276         /* New TTL is 0? Delete the entry... */
 277         if (rr->ttl <= 0) {
 278                 dns_cache_remove(c, rr->key);
 279                 return 0;
 280         }
 281
 282         if (rr->key->class == DNS_CLASS_ANY)
 283                 return 0;
 284         if (rr->key->type == DNS_TYPE_ANY)
 285                 return 0;
 286
 287         /* Entry exists already? Update TTL and timestamp */
 288         existing = dns_cache_get(c, rr);
 289         if (existing) {
 290                 dns_cache_item_update_positive(c, existing, rr, timestamp);
 291                 return 0;
 292         }
 293
 294         /* Otherwise, add the new RR */
 295         r = dns_cache_init(c);
 296         if (r < 0)
 297                 return r;
 298
 299         dns_cache_make_space(c, 1);
 300
 301         i = new0(DnsCacheItem, 1);
 302         if (!i)
 303                 return -ENOMEM;
 304
 305         i->type = DNS_CACHE_POSITIVE;
 306         i->key = dns_resource_key_ref(rr->key);
 307         i->rr = dns_resource_record_ref(rr);
 308         i->until = timestamp + MIN(i->rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 309         i->prioq_idx = PRIOQ_IDX_NULL;
 310         i->owner_family = owner_family;
 311         i->owner_address = *owner_address;
 312
 313         r = dns_cache_link_item(c, i);
 314         if (r < 0)
 315                 return r;
 316
 317         i = NULL;
 318         return 0;
 319 }
 320
 321 static int dns_cache_put_negative(
 322                 DnsCache *c,
 323                 DnsResourceKey *key,
 324                 int rcode,
 325                 usec_t timestamp,
 326                 uint32_t soa_ttl,
 327                 int owner_family,
 328                 const union in_addr_union *owner_address) {
 329
 330         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
 331         int r;
 332
 333         assert(c);
 334         assert(key);
 335         assert(owner_address);
 336
 337         dns_cache_remove(c, key);
 338
 339         if (key->class == DNS_CLASS_ANY)
 340                 return 0;
 341         if (key->type == DNS_TYPE_ANY)
 342                 return 0;
 343         if (soa_ttl <= 0)
 344                 return 0;
 345
 346         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
 347                 return 0;
 348
 349         r = dns_cache_init(c);
 350         if (r < 0)
 351                 return r;
 352
 353         dns_cache_make_space(c, 1);
 354
 355         i = new0(DnsCacheItem, 1);
 356         if (!i)
 357                 return -ENOMEM;
 358
 359         i->type = rcode == DNS_RCODE_SUCCESS ? DNS_CACHE_NODATA : DNS_CACHE_NXDOMAIN;
 360         i->key = dns_resource_key_ref(key);
 361         i->until = timestamp + MIN(soa_ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 362         i->prioq_idx = PRIOQ_IDX_NULL;
 363         i->owner_family = owner_family;
 364         i->owner_address = *owner_address;
 365
 366         r = dns_cache_link_item(c, i);
 367         if (r < 0)
 368                 return r;
 369
 370         i = NULL;
 371         return 0;
 372 }
 373
 374 int dns_cache_put(
 375                 DnsCache *c,
 376                 DnsQuestion *q,
 377                 int rcode,
 378                 DnsAnswer *answer,
 379                 unsigned max_rrs,
 380                 usec_t timestamp,
 381                 int owner_family,
 382                 const union in_addr_union *owner_address) {
 383
 384         unsigned i;
 385         int r;
 386
 387         assert(c);
 388         assert(q);
 389
 390         /* First, delete all matching old RRs, so that we only keep
 391          * complete by_key in place. */
 392         for (i = 0; i < q->n_keys; i++)
 393                 dns_cache_remove(c, q->keys[i]);
 394
 395         if (!answer)
 396                 return 0;
 397
 398         for (i = 0; i < answer->n_rrs; i++)
 399                 dns_cache_remove(c, answer->rrs[i]->key);
 400
 401         /* We only care for positive replies and NXDOMAINs, on all
 402          * other replies we will simply flush the respective entries,
 403          * and that's it */
 404
 405         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
 406                 return 0;
 407
 408         /* Make some space for our new entries */
 409         dns_cache_make_space(c, answer->n_rrs + q->n_keys);
 410
 411         if (timestamp <= 0)
 412                 timestamp = now(CLOCK_BOOTTIME);
 413
 414         /* Second, add in positive entries for all contained RRs */
 415         for (i = 0; i < MIN(max_rrs, answer->n_rrs); i++) {
 416                 r = dns_cache_put_positive(c, answer->rrs[i], timestamp, owner_family, owner_address);
 417                 if (r < 0)
 418                         goto fail;
 419         }
 420
 421         /* Third, add in negative entries for all keys with no RR */
 422         for (i = 0; i < q->n_keys; i++) {
 423                 DnsResourceRecord *soa = NULL;
 424
 425                 r = dns_answer_contains(answer, q->keys[i]);
 426                 if (r < 0)
 427                         goto fail;
 428                 if (r > 0)
 429                         continue;
 430
 431                 r = dns_answer_find_soa(answer, q->keys[i], &soa);
 432                 if (r < 0)
 433                         goto fail;
 434                 if (r == 0)
 435                         continue;
 436
 437                 r = dns_cache_put_negative(c, q->keys[i], rcode, timestamp, MIN(soa->soa.minimum, soa->ttl), owner_family, owner_address);
 438                 if (r < 0)
 439                         goto fail;
 440         }
 441
 442         return 0;
 443
 444 fail:
 445         /* Adding all RRs failed. Let's clean up what we already
 446          * added, just in case */
 447
 448         for (i = 0; i < q->n_keys; i++)
 449                 dns_cache_remove(c, q->keys[i]);
 450         for (i = 0; i < answer->n_rrs; i++)
 451                 dns_cache_remove(c, answer->rrs[i]->key);
 452
 453         return r;
 454 }
 455
 456 int dns_cache_lookup(DnsCache *c, DnsQuestion *q, int *rcode, DnsAnswer **ret) {
 457         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
 458         unsigned i, n = 0;
 459         int r;
 460         bool nxdomain = false;
 461
 462         assert(c);
 463         assert(q);
 464         assert(rcode);
 465         assert(ret);
 466
 467         if (q->n_keys <= 0) {
 468                 *ret = NULL;
 469                 *rcode = 0;
 470                 return 0;
 471         }
 472
 473         for (i = 0; i < q->n_keys; i++) {
 474                 DnsCacheItem *j;
 475
 476                 if (q->keys[i]->type == DNS_TYPE_ANY ||
 477                     q->keys[i]->class == DNS_CLASS_ANY) {
 478                         /* If we have ANY lookups we simply refresh */
 479                         *ret = NULL;
 480                         *rcode = 0;
 481                         return 0;
 482                 }
 483
 484                 j = hashmap_get(c->by_key, q->keys[i]);
 485                 if (!j) {
 486                         /* If one question cannot be answered we need to refresh */
 487                         *ret = NULL;
 488                         *rcode = 0;
 489                         return 0;
 490                 }
 491
 492                 LIST_FOREACH(by_key, j, j) {
 493                         if (j->rr)
 494                                 n++;
 495                         else if (j->type == DNS_CACHE_NXDOMAIN)
 496                                 nxdomain = true;
 497                 }
 498         }
 499
 500         if (n <= 0) {
 501                 *ret = NULL;
 502                 *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS;
 503                 return 1;
 504         }
 505
 506         answer = dns_answer_new(n);
 507         if (!answer)
 508                 return -ENOMEM;
 509
 510         for (i = 0; i < q->n_keys; i++) {
 511                 DnsCacheItem *j;
 512
 513                 j = hashmap_get(c->by_key, q->keys[i]);
 514                 LIST_FOREACH(by_key, j, j) {
 515                         if (j->rr) {
 516                                 r = dns_answer_add(answer, j->rr);
 517                                 if (r < 0)
 518                                         return r;
 519                         }
 520                 }
 521         }
 522
 523         *ret = answer;
 524         *rcode = DNS_RCODE_SUCCESS;
 525         answer = NULL;
 526
 527         return n;
 528 }
 529
 530 int dns_cache_check_conflicts(DnsCache *cache, DnsResourceRecord *rr, int owner_family, const union in_addr_union *owner_address) {
 531         DnsCacheItem *i, *first;
 532         bool same_owner = true;
 533
 534         assert(cache);
 535         assert(rr);
 536
 537         dns_cache_prune(cache);
 538
 539         /* See if there's a cache entry for the same key. If there
 540          * isn't there's no conflict */
 541         first = hashmap_get(cache->by_key, rr->key);
 542         if (!first)
 543                 return 0;
 544
 545         /* See if the RR key is owned by the same owner, if so, there
 546          * isn't a conflict either */
 547         LIST_FOREACH(by_key, i, first) {
 548                 if (i->owner_family != owner_family ||
 549                     !in_addr_equal(owner_family, &i->owner_address, owner_address)) {
 550                         same_owner = false;
 551                         break;
 552                 }
 553         }
 554         if (same_owner)
 555                 return 0;
 556
 557         /* See if there's the exact same RR in the cache. If yes, then
 558          * there's no conflict. */
 559         if (dns_cache_get(cache, rr))
 560                 return 0;
 561
 562         /* There's a conflict */
 563         return 1;
 564 }