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 static void dns_cache_item_free(DnsCacheItem *i) {
35 dns_resource_record_unref(i->rr);
36 dns_resource_key_unref(i->key);
40 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsCacheItem*, dns_cache_item_free);
42 static void dns_cache_item_remove_and_free(DnsCache *c, DnsCacheItem *i) {
50 first = hashmap_get(c->by_key, i->key);
51 LIST_REMOVE(by_key, first, i);
54 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
56 hashmap_remove(c->by_key, i->key);
58 prioq_remove(c->by_expiry, i, &i->prioq_idx);
60 dns_cache_item_free(i);
63 void dns_cache_flush(DnsCache *c) {
68 while ((i = hashmap_first(c->by_key)))
69 dns_cache_item_remove_and_free(c, i);
71 assert(hashmap_size(c->by_key) == 0);
72 assert(prioq_size(c->by_expiry) == 0);
74 hashmap_free(c->by_key);
77 prioq_free(c->by_expiry);
81 static void dns_cache_remove(DnsCache *c, DnsResourceKey *key) {
87 while ((i = hashmap_get(c->by_key, key)))
88 dns_cache_item_remove_and_free(c, i);
91 static void dns_cache_make_space(DnsCache *c, unsigned add) {
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. */
103 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
106 if (prioq_size(c->by_expiry) <= 0)
109 if (prioq_size(c->by_expiry) + add < CACHE_MAX)
112 i = prioq_peek(c->by_expiry);
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);
122 void dns_cache_prune(DnsCache *c) {
127 /* Remove all entries that are past their TTL */
130 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
133 i = prioq_peek(c->by_expiry);
138 t = now(CLOCK_MONOTONIC);
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);
150 static int dns_cache_item_prioq_compare_func(const void *a, const void *b) {
151 const DnsCacheItem *x = a, *y = b;
153 if (x->until < y->until)
155 if (x->until > y->until)
160 static int init_cache(DnsCache *c) {
163 r = prioq_ensure_allocated(&c->by_expiry, dns_cache_item_prioq_compare_func);
167 r = hashmap_ensure_allocated(&c->by_key, dns_resource_key_hash_func, dns_resource_key_compare_func);
174 static int dns_cache_link_item(DnsCache *c, DnsCacheItem *i) {
181 r = prioq_put(c->by_expiry, i, &i->prioq_idx);
185 first = hashmap_get(c->by_key, i->key);
187 LIST_PREPEND(by_key, first, i);
188 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
190 r = hashmap_put(c->by_key, i->key, i);
192 prioq_remove(c->by_expiry, i, &i->prioq_idx);
200 static DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) {
206 LIST_FOREACH(by_key, i, hashmap_get(c->by_key, rr->key))
207 if (i->rr && dns_resource_record_equal(i->rr, rr))
213 static void dns_cache_item_update_positive(DnsCache *c, DnsCacheItem *i, DnsResourceRecord *rr, usec_t timestamp) {
218 i->type = DNS_CACHE_POSITIVE;
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 */
224 assert_se(hashmap_replace(c->by_key, rr->key, i) >= 0);
227 dns_resource_record_ref(rr);
228 dns_resource_record_unref(i->rr);
231 dns_resource_key_unref(i->key);
232 i->key = dns_resource_key_ref(rr->key);
234 i->until = timestamp + MIN(rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
236 prioq_reshuffle(c->by_expiry, i, &i->prioq_idx);
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;
247 /* New TTL is 0? Delete the entry... */
249 dns_cache_remove(c, rr->key);
253 /* Entry exists already? Update TTL and timestamp */
254 existing = dns_cache_get(c, rr);
256 dns_cache_item_update_positive(c, existing, rr, timestamp);
260 /* Otherwise, add the new RR */
265 dns_cache_make_space(c, 1);
267 i = new0(DnsCacheItem, 1);
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;
277 r = dns_cache_link_item(c, i);
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;
292 dns_cache_remove(c, key);
294 if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
301 dns_cache_make_space(c, 1);
303 i = new0(DnsCacheItem, 1);
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;
312 r = dns_cache_link_item(c, i);
320 int dns_cache_put(DnsCache *c, DnsQuestion *q, int rcode, DnsAnswer *answer, usec_t timestamp) {
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);
334 /* We only care for positive replies and NXDOMAINs, on all
335 * other replies we will simply flush the respective entries,
338 if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
341 /* Make some space for our new entries */
342 dns_cache_make_space(c, answer->n_rrs + q->n_keys);
345 timestamp = now(CLOCK_MONOTONIC);
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);
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;
358 r = dns_answer_contains(answer, q->keys[i]);
364 r = dns_answer_find_soa(answer, q->keys[i], &soa);
370 r = dns_cache_put_negative(c, q->keys[i], rcode, timestamp, MIN(soa->soa.minimum, soa->ttl));
378 /* Adding all RRs failed. Let's clean up what we already
379 * added, just in case */
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);
389 int dns_cache_lookup(DnsCache *c, DnsQuestion *q, int *rcode, DnsAnswer **ret) {
390 _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
393 bool nxdomain = false;
399 if (q->n_keys <= 0) {
405 for (i = 0; i < q->n_keys; i++) {
408 j = hashmap_get(c->by_key, q->keys[i]);
410 /* If one question cannot be answered we need to refresh */
416 LIST_FOREACH(by_key, j, j) {
419 else if (j->type == DNS_CACHE_NXDOMAIN)
426 *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS;
430 answer = dns_answer_new(n);
434 for (i = 0; i < q->n_keys; i++) {
437 j = hashmap_get(c->by_key, q->keys[i]);
438 LIST_FOREACH(by_key, j, j) {
440 r = dns_answer_add(answer, j->rr);
448 *rcode = DNS_RCODE_SUCCESS;