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