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_MONOTONIC);
 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
 324         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
 325                 return 0;
 326
 327         r = dns_cache_init(c);
 328         if (r < 0)
 329                 return r;
 330
 331         dns_cache_make_space(c, 1);
 332
 333         i = new0(DnsCacheItem, 1);
 334         if (!i)
 335                 return -ENOMEM;
 336
 337         i->type = rcode == DNS_RCODE_SUCCESS ? DNS_CACHE_NODATA : DNS_CACHE_NXDOMAIN;
 338         i->key = dns_resource_key_ref(key);
 339         i->until = timestamp + MIN(soa_ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 340         i->prioq_idx = PRIOQ_IDX_NULL;
 341
 342         r = dns_cache_link_item(c, i);
 343         if (r < 0)
 344                 return r;
 345
 346         i = NULL;
 347         return 0;
 348 }
 349
 350 int dns_cache_put(DnsCache *c, DnsQuestion *q, int rcode, DnsAnswer *answer, unsigned max_rrs, usec_t timestamp) {
 351         unsigned i;
 352         int r;
 353
 354         assert(c);
 355         assert(answer);
 356
 357         /* First, delete all matching old RRs, so that we only keep
 358          * complete by_key in place. */
 359         for (i = 0; i < q->n_keys; i++)
 360                 dns_cache_remove(c, q->keys[i]);
 361         for (i = 0; i < answer->n_rrs; i++)
 362                 dns_cache_remove(c, answer->rrs[i]->key);
 363
 364         /* We only care for positive replies and NXDOMAINs, on all
 365          * other replies we will simply flush the respective entries,
 366          * and that's it */
 367
 368         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
 369                 return 0;
 370
 371         /* Make some space for our new entries */
 372         dns_cache_make_space(c, answer->n_rrs + q->n_keys);
 373
 374         if (timestamp <= 0)
 375                 timestamp = now(CLOCK_MONOTONIC);
 376
 377         /* Second, add in positive entries for all contained RRs */
 378         for (i = 0; i < MIN(max_rrs, answer->n_rrs); i++) {
 379                 r = dns_cache_put_positive(c, answer->rrs[i], timestamp);
 380                 if (r < 0)
 381                         goto fail;
 382         }
 383
 384         /* Third, add in negative entries for all keys with no RR */
 385         for (i = 0; i < q->n_keys; i++) {
 386                 DnsResourceRecord *soa = NULL;
 387
 388                 r = dns_answer_contains(answer, q->keys[i]);
 389                 if (r < 0)
 390                         goto fail;
 391                 if (r > 0)
 392                         continue;
 393
 394                 r = dns_answer_find_soa(answer, q->keys[i], &soa);
 395                 if (r < 0)
 396                         goto fail;
 397                 if (r == 0)
 398                         continue;
 399
 400                 r = dns_cache_put_negative(c, q->keys[i], rcode, timestamp, MIN(soa->soa.minimum, soa->ttl));
 401                 if (r < 0)
 402                         goto fail;
 403         }
 404
 405         return 0;
 406
 407 fail:
 408         /* Adding all RRs failed. Let's clean up what we already
 409          * added, just in case */
 410
 411         for (i = 0; i < q->n_keys; i++)
 412                 dns_cache_remove(c, q->keys[i]);
 413         for (i = 0; i < answer->n_rrs; i++)
 414                 dns_cache_remove(c, answer->rrs[i]->key);
 415
 416         return r;
 417 }
 418
 419 int dns_cache_lookup(DnsCache *c, DnsQuestion *q, int *rcode, DnsAnswer **ret) {
 420         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
 421         unsigned i, n = 0;
 422         int r;
 423         bool nxdomain = false;
 424
 425         assert(c);
 426         assert(q);
 427         assert(rcode);
 428         assert(ret);
 429
 430         if (q->n_keys <= 0) {
 431                 *ret = NULL;
 432                 *rcode = 0;
 433                 return 0;
 434         }
 435
 436         for (i = 0; i < q->n_keys; i++) {
 437                 DnsCacheItem *j;
 438
 439                 if (q->keys[i]->type == DNS_TYPE_ANY ||
 440                     q->keys[i]->class == DNS_CLASS_ANY) {
 441                         /* If we have ANY lookups we simply refresh */
 442                         *ret = NULL;
 443                         *rcode = 0;
 444                         return 0;
 445                 }
 446
 447                 j = hashmap_get(c->by_key, q->keys[i]);
 448                 if (!j) {
 449                         /* If one question cannot be answered we need to refresh */
 450                         *ret = NULL;
 451                         *rcode = 0;
 452                         return 0;
 453                 }
 454
 455                 LIST_FOREACH(by_key, j, j) {
 456                         if (j->rr)
 457                                 n++;
 458                         else if (j->type == DNS_CACHE_NXDOMAIN)
 459                                 nxdomain = true;
 460                 }
 461         }
 462
 463         if (n <= 0) {
 464                 *ret = NULL;
 465                 *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS;
 466                 return 1;
 467         }
 468
 469         answer = dns_answer_new(n);
 470         if (!answer)
 471                 return -ENOMEM;
 472
 473         for (i = 0; i < q->n_keys; i++) {
 474                 DnsCacheItem *j;
 475
 476                 j = hashmap_get(c->by_key, q->keys[i]);
 477                 LIST_FOREACH(by_key, j, j) {
 478                         if (j->rr) {
 479                                 r = dns_answer_add(answer, j->rr);
 480                                 if (r < 0)
 481                                         return r;
 482                         }
 483                 }
 484         }
 485
 486         *ret = answer;
 487         *rcode = DNS_RCODE_SUCCESS;
 488         answer = NULL;
 489
 490         return n;
 491 }