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