1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
4 This file is part of systemd.
6 Copyright 2014 Lennart Poettering
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.
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.
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/>.
22 #include "resolved-dns-cache.h"
23 #include "resolved-dns-packet.h"
25 /* Never cache more than 1K entries */
26 #define CACHE_MAX 1024
28 /* We never keep any item longer than 10min in our cache */
29 #define CACHE_TTL_MAX_USEC (10 * USEC_PER_MINUTE)
31 typedef enum DnsCacheItemType DnsCacheItemType;
32 typedef struct DnsCacheItem DnsCacheItem;
34 enum DnsCacheItemType {
42 DnsResourceRecord *rr;
44 DnsCacheItemType type;
46 LIST_FIELDS(DnsCacheItem, by_key);
49 static void dns_cache_item_free(DnsCacheItem *i) {
53 dns_resource_record_unref(i->rr);
54 dns_resource_key_unref(i->key);
58 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsCacheItem*, dns_cache_item_free);
60 static void dns_cache_item_remove_and_free(DnsCache *c, DnsCacheItem *i) {
68 first = hashmap_get(c->by_key, i->key);
69 LIST_REMOVE(by_key, first, i);
72 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
74 hashmap_remove(c->by_key, i->key);
76 prioq_remove(c->by_expiry, i, &i->prioq_idx);
78 dns_cache_item_free(i);
81 void dns_cache_flush(DnsCache *c) {
86 while ((i = hashmap_first(c->by_key)))
87 dns_cache_item_remove_and_free(c, i);
89 assert(hashmap_size(c->by_key) == 0);
90 assert(prioq_size(c->by_expiry) == 0);
92 hashmap_free(c->by_key);
95 prioq_free(c->by_expiry);
99 static void dns_cache_remove(DnsCache *c, DnsResourceKey *key) {
105 while ((i = hashmap_get(c->by_key, key)))
106 dns_cache_item_remove_and_free(c, i);
109 static void dns_cache_make_space(DnsCache *c, unsigned add) {
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. */
121 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
124 if (prioq_size(c->by_expiry) <= 0)
127 if (prioq_size(c->by_expiry) + add < CACHE_MAX)
130 i = prioq_peek(c->by_expiry);
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);
140 void dns_cache_prune(DnsCache *c) {
145 /* Remove all entries that are past their TTL */
148 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
151 i = prioq_peek(c->by_expiry);
156 t = now(CLOCK_MONOTONIC);
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);
168 static int dns_cache_item_prioq_compare_func(const void *a, const void *b) {
169 const DnsCacheItem *x = a, *y = b;
171 if (x->until < y->until)
173 if (x->until > y->until)
178 static int dns_cache_init(DnsCache *c) {
183 r = prioq_ensure_allocated(&c->by_expiry, dns_cache_item_prioq_compare_func);
187 r = hashmap_ensure_allocated(&c->by_key, dns_resource_key_hash_func, dns_resource_key_compare_func);
194 static int dns_cache_link_item(DnsCache *c, DnsCacheItem *i) {
201 r = prioq_put(c->by_expiry, i, &i->prioq_idx);
205 first = hashmap_get(c->by_key, i->key);
207 LIST_PREPEND(by_key, first, i);
208 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
210 r = hashmap_put(c->by_key, i->key, i);
212 prioq_remove(c->by_expiry, i, &i->prioq_idx);
220 static DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) {
226 LIST_FOREACH(by_key, i, hashmap_get(c->by_key, rr->key))
227 if (i->rr && dns_resource_record_equal(i->rr, rr))
233 static void dns_cache_item_update_positive(DnsCache *c, DnsCacheItem *i, DnsResourceRecord *rr, usec_t timestamp) {
238 i->type = DNS_CACHE_POSITIVE;
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 */
244 assert_se(hashmap_replace(c->by_key, rr->key, i) >= 0);
247 dns_resource_record_ref(rr);
248 dns_resource_record_unref(i->rr);
251 dns_resource_key_unref(i->key);
252 i->key = dns_resource_key_ref(rr->key);
254 i->until = timestamp + MIN(rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
256 prioq_reshuffle(c->by_expiry, i, &i->prioq_idx);
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;
267 /* New TTL is 0? Delete the entry... */
269 dns_cache_remove(c, rr->key);
273 if (rr->key->class == DNS_CLASS_ANY)
275 if (rr->key->type == DNS_TYPE_ANY)
278 /* Entry exists already? Update TTL and timestamp */
279 existing = dns_cache_get(c, rr);
281 dns_cache_item_update_positive(c, existing, rr, timestamp);
285 /* Otherwise, add the new RR */
286 r = dns_cache_init(c);
290 dns_cache_make_space(c, 1);
292 i = new0(DnsCacheItem, 1);
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;
302 r = dns_cache_link_item(c, i);
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;
317 dns_cache_remove(c, key);
319 if (key->class == DNS_CLASS_ANY)
321 if (key->type == DNS_TYPE_ANY)
324 if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
327 r = dns_cache_init(c);
331 dns_cache_make_space(c, 1);
333 i = new0(DnsCacheItem, 1);
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;
342 r = dns_cache_link_item(c, i);
350 int dns_cache_put(DnsCache *c, DnsQuestion *q, int rcode, DnsAnswer *answer, unsigned max_rrs, usec_t timestamp) {
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]);
365 for (i = 0; i < answer->n_rrs; i++)
366 dns_cache_remove(c, answer->rrs[i]->key);
368 /* We only care for positive replies and NXDOMAINs, on all
369 * other replies we will simply flush the respective entries,
372 if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
375 /* Make some space for our new entries */
376 dns_cache_make_space(c, answer->n_rrs + q->n_keys);
379 timestamp = now(CLOCK_MONOTONIC);
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);
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;
392 r = dns_answer_contains(answer, q->keys[i]);
398 r = dns_answer_find_soa(answer, q->keys[i], &soa);
404 r = dns_cache_put_negative(c, q->keys[i], rcode, timestamp, MIN(soa->soa.minimum, soa->ttl));
412 /* Adding all RRs failed. Let's clean up what we already
413 * added, just in case */
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);
423 int dns_cache_lookup(DnsCache *c, DnsQuestion *q, int *rcode, DnsAnswer **ret) {
424 _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
427 bool nxdomain = false;
434 if (q->n_keys <= 0) {
440 for (i = 0; i < q->n_keys; i++) {
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 */
451 j = hashmap_get(c->by_key, q->keys[i]);
453 /* If one question cannot be answered we need to refresh */
459 LIST_FOREACH(by_key, j, j) {
462 else if (j->type == DNS_CACHE_NXDOMAIN)
469 *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS;
473 answer = dns_answer_new(n);
477 for (i = 0; i < q->n_keys; i++) {
480 j = hashmap_get(c->by_key, q->keys[i]);
481 LIST_FOREACH(by_key, j, j) {
483 r = dns_answer_add(answer, j->rr);
491 *rcode = DNS_RCODE_SUCCESS;