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
  24 /* Never cache more than 1K entries */
  25 #define CACHE_MAX 1024
  26
  27 /* We never keep any item longer than 10min in our cache */
  28 #define CACHE_TTL_MAX_USEC (10 * USEC_PER_MINUTE)
  29
  30 static void dns_cache_item_free(DnsCacheItem *i) {
  31         if (!i)
  32                 return;
  33
  34         dns_resource_record_unref(i->rr);
  35         free(i);
  36 }
  37
  38 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsCacheItem*, dns_cache_item_free);
  39
  40 static void dns_cache_item_remove_and_free(DnsCache *c, DnsCacheItem *i) {
  41         DnsCacheItem *first;
  42
  43         assert(c);
  44
  45         if (!i)
  46                 return;
  47
  48         first = hashmap_get(c->rrsets, i->rr->key);
  49         LIST_REMOVE(rrsets, first, i);
  50
  51         if (first)
  52                 assert_se(hashmap_replace(c->rrsets, first->rr->key, first) >= 0);
  53         else
  54                 hashmap_remove(c->rrsets, i->rr->key);
  55
  56         prioq_remove(c->expire, i, &i->expire_prioq_idx);
  57
  58         dns_cache_item_free(i);
  59 }
  60
  61 void dns_cache_flush(DnsCache *c) {
  62         DnsCacheItem *i;
  63
  64         assert(c);
  65
  66         while ((i = hashmap_first(c->rrsets)))
  67                 dns_cache_item_remove_and_free(c, i);
  68
  69         assert(hashmap_size(c->rrsets) == 0);
  70         assert(prioq_size(c->expire) == 0);
  71
  72         hashmap_free(c->rrsets);
  73         c->rrsets = NULL;
  74
  75         prioq_free(c->expire);
  76         c->expire = NULL;
  77 }
  78
  79 void dns_cache_remove(DnsCache *c, DnsResourceKey *key) {
  80         DnsCacheItem *i;
  81
  82         assert(c);
  83         assert(key);
  84
  85         while ((i = hashmap_get(c->rrsets, key)))
  86                 dns_cache_item_remove_and_free(c, i);
  87 }
  88
  89 static void dns_cache_make_space(DnsCache *c, unsigned add) {
  90         assert(c);
  91
  92         if (add <= 0)
  93                 return;
  94
  95         /* Makes space for n new entries. Note that we actually allow
  96          * the cache to grow beyond CACHE_MAX, but only when we shall
  97          * add more RRs to the cache than CACHE_MAX at once. In that
  98          * case the cache will be emptied completely otherwise. */
  99
 100         for (;;) {
 101                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
 102                 DnsCacheItem *i;
 103
 104                 if (prioq_size(c->expire) <= 0)
 105                         break;
 106
 107                 if (prioq_size(c->expire) + add < CACHE_MAX)
 108                         break;
 109
 110                 i = prioq_peek(c->expire);
 111                 assert(i);
 112
 113                 /* Take an extra reference to the key so that it
 114                  * doesn't go away in the middle of the remove call */
 115                 key = dns_resource_key_ref(i->rr->key);
 116                 dns_cache_remove(c, key);
 117         }
 118 }
 119
 120 void dns_cache_prune(DnsCache *c) {
 121         usec_t t = 0;
 122
 123         assert(c);
 124
 125         /* Remove all entries that are past their TTL */
 126
 127         for (;;) {
 128                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
 129                 DnsCacheItem *i;
 130                 usec_t ttl;
 131
 132                 i = prioq_peek(c->expire);
 133                 if (!i)
 134                         break;
 135
 136                 ttl = i->rr->ttl * USEC_PER_SEC;
 137                 if (ttl > CACHE_TTL_MAX_USEC)
 138                         ttl = CACHE_TTL_MAX_USEC;
 139
 140                 if (t <= 0)
 141                         t = now(CLOCK_MONOTONIC);
 142
 143                 if (i->timestamp + ttl > t)
 144                         break;
 145
 146                 /* Take an extra reference to the key so that it
 147                  * doesn't go away in the middle of the remove call */
 148                 key = dns_resource_key_ref(i->rr->key);
 149                 dns_cache_remove(c, key);
 150         }
 151 }
 152
 153 static int dns_cache_item_prioq_compare_func(const void *a, const void *b) {
 154         usec_t t, z;
 155         const DnsCacheItem *x = a, *y = b;
 156
 157         t = x->timestamp + x->rr->ttl * USEC_PER_SEC;
 158         z = y->timestamp + y->rr->ttl * USEC_PER_SEC;
 159
 160         if (t < z)
 161                 return -1;
 162         if (t > z)
 163                 return 1;
 164         return 0;
 165 }
 166
 167 static void dns_cache_item_update(DnsCache *c, DnsCacheItem *i, DnsResourceRecord *rr, usec_t timestamp) {
 168         assert(c);
 169         assert(i);
 170         assert(rr);
 171
 172         if (!i->rrsets_prev) {
 173                 /* We are the first item in the list, we need to
 174                  * update the key used in the hashmap */
 175
 176                 assert_se(hashmap_replace(c->rrsets, rr->key, i) >= 0);
 177         }
 178
 179         dns_resource_record_ref(rr);
 180         dns_resource_record_unref(i->rr);
 181         i->rr = rr;
 182
 183         i->timestamp = timestamp;
 184         prioq_reshuffle(c->expire, i, &i->expire_prioq_idx);
 185 }
 186
 187 static DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) {
 188         DnsCacheItem *i;
 189
 190         assert(c);
 191         assert(rr);
 192
 193         LIST_FOREACH(rrsets, i, hashmap_get(c->rrsets, rr->key))
 194                 if (dns_resource_record_equal(i->rr, rr))
 195                         return i;
 196
 197         return NULL;
 198 }
 199
 200 int dns_cache_put(DnsCache *c, DnsResourceRecord *rr, usec_t timestamp) {
 201         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
 202         DnsCacheItem *first = NULL, *existing;
 203         int r;
 204
 205         assert(c);
 206         assert(rr);
 207
 208         /* New TTL is 0? Delete the entry... */
 209         if (rr->ttl <= 0) {
 210                 dns_cache_remove(c, rr->key);
 211                 return 0;
 212         }
 213
 214         /* Entry exists already? Update TTL and timestamp */
 215         existing = dns_cache_get(c, rr);
 216         if (existing) {
 217                 dns_cache_item_update(c, existing, rr, timestamp);
 218                 return 0;
 219         }
 220
 221         /* Otherwise, add the new RR */
 222         r = prioq_ensure_allocated(&c->expire, dns_cache_item_prioq_compare_func);
 223         if (r < 0)
 224                 return r;
 225
 226         r = hashmap_ensure_allocated(&c->rrsets, dns_resource_key_hash_func, dns_resource_key_compare_func);
 227         if (r < 0)
 228                 return r;
 229
 230         dns_cache_make_space(c, 1);
 231
 232         i = new0(DnsCacheItem, 1);
 233         if (!i)
 234                 return -ENOMEM;
 235
 236         i->rr = dns_resource_record_ref(rr);
 237         i->timestamp = timestamp;
 238         i->expire_prioq_idx = PRIOQ_IDX_NULL;
 239
 240         r = prioq_put(c->expire, i, &i->expire_prioq_idx);
 241         if (r < 0)
 242                 return r;
 243
 244         first = hashmap_get(c->rrsets, i->rr->key);
 245         if (first) {
 246                 LIST_PREPEND(rrsets, first, i);
 247                 assert_se(hashmap_replace(c->rrsets, first->rr->key, first) >= 0);
 248         } else {
 249                 r = hashmap_put(c->rrsets, i->rr->key, i);
 250                 if (r < 0) {
 251                         prioq_remove(c->expire, i, &i->expire_prioq_idx);
 252                         return r;
 253                 }
 254         }
 255
 256         i = NULL;
 257
 258         return 0;
 259 }
 260
 261 int dns_cache_put_answer(DnsCache *c, DnsAnswer *answer, usec_t timestamp) {
 262         unsigned i, added = 0;
 263         int r;
 264
 265         assert(c);
 266         assert(answer);
 267
 268         /* First iteration, delete all matching old RRs, so that we
 269          * only keep complete rrsets in place. */
 270         for (i = 0; i < answer->n_rrs; i++)
 271                 dns_cache_remove(c, answer->rrs[i]->key);
 272
 273         dns_cache_make_space(c, answer->n_rrs);
 274
 275         /* Second iteration, add in new RRs */
 276         for (added = 0; added < answer->n_rrs; added++) {
 277                 if (timestamp <= 0)
 278                         timestamp = now(CLOCK_MONOTONIC);
 279
 280                 r = dns_cache_put(c, answer->rrs[added], timestamp);
 281                 if (r < 0)
 282                         goto fail;
 283         }
 284
 285         return 0;
 286
 287 fail:
 288         /* Adding all RRs failed. Let's clean up what we already
 289          * added, just in case */
 290
 291         for (i = 0; i < added; i++)
 292                 dns_cache_remove(c, answer->rrs[i]->key);
 293
 294         return r;
 295 }
 296
 297 int dns_cache_lookup(DnsCache *c, DnsQuestion *q, DnsAnswer **ret) {
 298         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
 299         unsigned i, n = 0;
 300         int r;
 301
 302         assert(c);
 303         assert(q);
 304         assert(ret);
 305
 306         if (q->n_keys <= 0) {
 307                 *ret = NULL;
 308                 return 0;
 309         }
 310
 311         for (i = 0; i < q->n_keys; i++) {
 312                 DnsCacheItem *j;
 313
 314                 j = hashmap_get(c->rrsets, q->keys[i]);
 315                 if (!j) {
 316                         /* If one question cannot be answered we need to refresh */
 317                         *ret = NULL;
 318                         return 0;
 319                 }
 320
 321                 LIST_FOREACH(rrsets, j, j)
 322                         n++;
 323         }
 324
 325         assert(n > 0);
 326
 327         answer = dns_answer_new(n);
 328         if (!answer)
 329                 return -ENOMEM;
 330
 331         for (i = 0; i < q->n_keys; i++) {
 332                 DnsCacheItem *j;
 333
 334                 j = hashmap_get(c->rrsets, q->keys[i]);
 335                 LIST_FOREACH(rrsets, j, j) {
 336                         r = dns_answer_add(answer, j->rr);
 337                         if (r < 0)
 338                                 return r;
 339                 }
 340         }
 341
 342         assert(n >= answer->n_rrs);
 343
 344         *ret = answer;
 345         answer = NULL;
 346
 347         return n;
 348 }