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