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_record_unrefp) DnsResourceRecord *rr = 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 RR so that the key
 114                  * doesn't go away in the middle of the remove call */
 115                 rr = dns_resource_record_ref(i->rr);
 116                 dns_cache_remove(c, &rr->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_record_unrefp) DnsResourceRecord *rr = 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 RR so that the key
 147                  * doesn't go away in the middle of the remove call */
 148                 rr = dns_resource_record_ref(i->rr);
 149                 dns_cache_remove(c, &rr->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 int dns_cache_put(DnsCache *c, DnsResourceRecord *rr, usec_t timestamp) {
 188         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
 189         DnsCacheItem *first = NULL, *existing;
 190         int r;
 191
 192         assert(c);
 193         assert(rr);
 194
 195         /* New TTL is 0? Delete the entry... */
 196         if (rr->ttl <= 0) {
 197                 dns_cache_remove(c, &rr->key);
 198                 return 0;
 199         }
 200
 201         /* Entry exists already? Update TTL and timestamp */
 202         existing = dns_cache_get(c, rr);
 203         if (existing) {
 204                 dns_cache_item_update(c, existing, rr, timestamp);
 205                 return 0;
 206         }
 207
 208         /* Otherwise, add the new RR */
 209         r = prioq_ensure_allocated(&c->expire, dns_cache_item_prioq_compare_func);
 210         if (r < 0)
 211                 return r;
 212
 213         r = hashmap_ensure_allocated(&c->rrsets, dns_resource_key_hash_func, dns_resource_key_compare_func);
 214         if (r < 0)
 215                 return r;
 216
 217         dns_cache_make_space(c, 1);
 218
 219         i = new0(DnsCacheItem, 1);
 220         if (!i)
 221                 return -ENOMEM;
 222
 223         i->rr = dns_resource_record_ref(rr);
 224         i->timestamp = timestamp;
 225         i->expire_prioq_idx = PRIOQ_IDX_NULL;
 226
 227         r = prioq_put(c->expire, i, &i->expire_prioq_idx);
 228         if (r < 0)
 229                 return r;
 230
 231         first = hashmap_get(c->rrsets, &i->rr->key);
 232         if (first) {
 233                 LIST_PREPEND(rrsets, first, i);
 234                 assert_se(hashmap_replace(c->rrsets, &first->rr->key, first) >= 0);
 235         } else {
 236                 r = hashmap_put(c->rrsets, &i->rr->key, i);
 237                 if (r < 0) {
 238                         prioq_remove(c->expire, i, &i->expire_prioq_idx);
 239                         return r;
 240                 }
 241         }
 242
 243         i = NULL;
 244
 245         return 0;
 246 }
 247
 248 int dns_cache_put_rrs(DnsCache *c, DnsResourceRecord **rrs, unsigned n_rrs, usec_t timestamp) {
 249         unsigned i, added = 0;
 250         int r;
 251
 252         assert(c);
 253
 254         if (n_rrs <= 0)
 255                 return 0;
 256
 257         assert(rrs);
 258
 259         /* First iteration, delete all matching old RRs, so that we
 260          * only keep complete rrsets in place. */
 261         for (i = 0; i < n_rrs; i++)
 262                 dns_cache_remove(c, &rrs[i]->key);
 263
 264         dns_cache_make_space(c, n_rrs);
 265
 266         /* Second iteration, add in new RRs */
 267         for (added = 0; added < n_rrs; added++) {
 268                 if (timestamp <= 0)
 269                         timestamp = now(CLOCK_MONOTONIC);
 270
 271                 r = dns_cache_put(c, rrs[added], timestamp);
 272                 if (r < 0)
 273                         goto fail;
 274
 275         }
 276
 277         return 0;
 278
 279 fail:
 280         /* Adding all RRs failed. Let's clean up what we already
 281          * added, just in case */
 282
 283         for (i = 0; i < added; i++)
 284                 dns_cache_remove(c, &rrs[i]->key);
 285
 286         return r;
 287 }
 288
 289 DnsCacheItem* dns_cache_lookup(DnsCache *c, DnsResourceKey *key) {
 290         assert(c);
 291         assert(key);
 292
 293         return hashmap_get(c->rrsets, key);
 294 }
 295
 296 DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) {
 297         DnsCacheItem *i;
 298
 299         assert(c);
 300         assert(rr);
 301
 302         LIST_FOREACH(rrsets, i, hashmap_get(c->rrsets, &rr->key))
 303                 if (dns_resource_record_equal(i->rr, rr))
 304                         return i;
 305
 306         return NULL;
 307 }
 308
 309 int dns_cache_lookup_many(DnsCache *c, DnsResourceKey *keys, unsigned n_keys, DnsResourceRecord ***rrs) {
 310         DnsResourceRecord **p = NULL;
 311         size_t allocated = 0, used = 0;
 312         unsigned i;
 313         int r;
 314
 315         assert(c);
 316         assert(rrs);
 317
 318         if (n_keys <= 0) {
 319                 *rrs = NULL;
 320                 return 0;
 321         }
 322
 323         assert(keys);
 324
 325         for (i = 0; i < n_keys; i++) {
 326                 DnsCacheItem *j;
 327
 328                 j = dns_cache_lookup(c, &keys[i]);
 329                 if (!j) {
 330                         *rrs = NULL;
 331                         r = 0;
 332                         goto fail;
 333                 }
 334
 335                 LIST_FOREACH(rrsets, j, j) {
 336
 337                         if (!GREEDY_REALLOC(p, allocated, used+1)) {
 338                                 r = -ENOMEM;
 339                                 goto fail;
 340                         }
 341
 342                         p[used++] = dns_resource_record_ref(j->rr);
 343                 }
 344         }
 345
 346         *rrs = p;
 347         return (int) used;
 348
 349 fail:
 350         dns_resource_record_freev(p, used);
 351         return r;
 352 }