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         /* Entry exists already? Update TTL and timestamp */
 274         existing = dns_cache_get(c, rr);
 275         if (existing) {
 276                 dns_cache_item_update_positive(c, existing, rr, timestamp);
 277                 return 0;
 278         }
 279
 280         /* Otherwise, add the new RR */
 281         r = dns_cache_init(c);
 282         if (r < 0)
 283                 return r;
 284
 285         dns_cache_make_space(c, 1);
 286
 287         i = new0(DnsCacheItem, 1);
 288         if (!i)
 289                 return -ENOMEM;
 290
 291         i->type = DNS_CACHE_POSITIVE;
 292         i->key = dns_resource_key_ref(rr->key);
 293         i->rr = dns_resource_record_ref(rr);
 294         i->until = timestamp + MIN(i->rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 295         i->prioq_idx = PRIOQ_IDX_NULL;
 296
 297         r = dns_cache_link_item(c, i);
 298         if (r < 0)
 299                 return r;
 300
 301         i = NULL;
 302         return 0;
 303 }
 304
 305 static int dns_cache_put_negative(DnsCache *c, DnsResourceKey *key, int rcode, usec_t timestamp, uint32_t soa_ttl) {
 306         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
 307         int r;
 308
 309         assert(c);
 310         assert(key);
 311
 312         dns_cache_remove(c, key);
 313
 314         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
 315                 return 0;
 316
 317         r = dns_cache_init(c);
 318         if (r < 0)
 319                 return r;
 320
 321         dns_cache_make_space(c, 1);
 322
 323         i = new0(DnsCacheItem, 1);
 324         if (!i)
 325                 return -ENOMEM;
 326
 327         i->type = rcode == DNS_RCODE_SUCCESS ? DNS_CACHE_NODATA : DNS_CACHE_NXDOMAIN;
 328         i->key = dns_resource_key_ref(key);
 329         i->until = timestamp + MIN(soa_ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
 330         i->prioq_idx = PRIOQ_IDX_NULL;
 331
 332         r = dns_cache_link_item(c, i);
 333         if (r < 0)
 334                 return r;
 335
 336         i = NULL;
 337         return 0;
 338 }
 339
 340 int dns_cache_put(DnsCache *c, DnsQuestion *q, int rcode, DnsAnswer *answer, unsigned max_rrs, usec_t timestamp) {
 341         unsigned i;
 342         int r;
 343
 344         assert(c);
 345         assert(answer);
 346
 347         /* First, delete all matching old RRs, so that we only keep
 348          * complete by_key in place. */
 349         for (i = 0; i < q->n_keys; i++)
 350                 dns_cache_remove(c, q->keys[i]);
 351         for (i = 0; i < answer->n_rrs; i++)
 352                 dns_cache_remove(c, answer->rrs[i]->key);
 353
 354         /* We only care for positive replies and NXDOMAINs, on all
 355          * other replies we will simply flush the respective entries,
 356          * and that's it */
 357
 358         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
 359                 return 0;
 360
 361         /* Make some space for our new entries */
 362         dns_cache_make_space(c, answer->n_rrs + q->n_keys);
 363
 364         if (timestamp <= 0)
 365                 timestamp = now(CLOCK_MONOTONIC);
 366
 367         /* Second, add in positive entries for all contained RRs */
 368         for (i = 0; i < MIN(max_rrs, answer->n_rrs); i++) {
 369                 r = dns_cache_put_positive(c, answer->rrs[i], timestamp);
 370                 if (r < 0)
 371                         goto fail;
 372         }
 373
 374         /* Third, add in negative entries for all keys with no RR */
 375         for (i = 0; i < q->n_keys; i++) {
 376                 DnsResourceRecord *soa = NULL;
 377
 378                 r = dns_answer_contains(answer, q->keys[i]);
 379                 if (r < 0)
 380                         goto fail;
 381                 if (r > 0)
 382                         continue;
 383
 384                 r = dns_answer_find_soa(answer, q->keys[i], &soa);
 385                 if (r < 0)
 386                         goto fail;
 387                 if (r == 0)
 388                         continue;
 389
 390                 r = dns_cache_put_negative(c, q->keys[i], rcode, timestamp, MIN(soa->soa.minimum, soa->ttl));
 391                 if (r < 0)
 392                         goto fail;
 393         }
 394
 395         return 0;
 396
 397 fail:
 398         /* Adding all RRs failed. Let's clean up what we already
 399          * added, just in case */
 400
 401         for (i = 0; i < q->n_keys; i++)
 402                 dns_cache_remove(c, q->keys[i]);
 403         for (i = 0; i < answer->n_rrs; i++)
 404                 dns_cache_remove(c, answer->rrs[i]->key);
 405
 406         return r;
 407 }
 408
 409 int dns_cache_lookup(DnsCache *c, DnsQuestion *q, int *rcode, DnsAnswer **ret) {
 410         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
 411         unsigned i, n = 0;
 412         int r;
 413         bool nxdomain = false;
 414
 415         assert(c);
 416         assert(q);
 417         assert(rcode);
 418         assert(ret);
 419
 420         if (q->n_keys <= 0) {
 421                 *ret = NULL;
 422                 *rcode = 0;
 423                 return 0;
 424         }
 425
 426         for (i = 0; i < q->n_keys; i++) {
 427                 DnsCacheItem *j;
 428
 429                 j = hashmap_get(c->by_key, q->keys[i]);
 430                 if (!j) {
 431                         /* If one question cannot be answered we need to refresh */
 432                         *ret = NULL;
 433                         *rcode = 0;
 434                         return 0;
 435                 }
 436
 437                 LIST_FOREACH(by_key, j, j) {
 438                         if (j->rr)
 439                                 n++;
 440                         else if (j->type == DNS_CACHE_NXDOMAIN)
 441                                 nxdomain = true;
 442                 }
 443         }
 444
 445         if (n <= 0) {
 446                 *ret = NULL;
 447                 *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS;
 448                 return 1;
 449         }
 450
 451         answer = dns_answer_new(n);
 452         if (!answer)
 453                 return -ENOMEM;
 454
 455         for (i = 0; i < q->n_keys; i++) {
 456                 DnsCacheItem *j;
 457
 458                 j = hashmap_get(c->by_key, q->keys[i]);
 459                 LIST_FOREACH(by_key, j, j) {
 460                         if (j->rr) {
 461                                 r = dns_answer_add(answer, j->rr);
 462                                 if (r < 0)
 463                                         return r;
 464                         }
 465                 }
 466         }
 467
 468         *ret = answer;
 469         *rcode = DNS_RCODE_SUCCESS;
 470         answer = NULL;
 471
 472         return n;
 473 }