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 /* Entry exists already? Update TTL and timestamp */
274 existing = dns_cache_get(c, rr);
276 dns_cache_item_update_positive(c, existing, rr, timestamp);
280 /* Otherwise, add the new RR */
281 r = dns_cache_init(c);
285 dns_cache_make_space(c, 1);
287 i = new0(DnsCacheItem, 1);
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;
297 r = dns_cache_link_item(c, i);
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;
312 dns_cache_remove(c, key);
314 if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
317 r = dns_cache_init(c);
321 dns_cache_make_space(c, 1);
323 i = new0(DnsCacheItem, 1);
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;
332 r = dns_cache_link_item(c, i);
340 int dns_cache_put(DnsCache *c, DnsQuestion *q, int rcode, DnsAnswer *answer, usec_t timestamp) {
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);
354 /* We only care for positive replies and NXDOMAINs, on all
355 * other replies we will simply flush the respective entries,
358 if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
361 /* Make some space for our new entries */
362 dns_cache_make_space(c, answer->n_rrs + q->n_keys);
365 timestamp = now(CLOCK_MONOTONIC);
367 /* Second, add in positive entries for all contained RRs */
368 for (i = 0; i < answer->n_rrs; i++) {
369 r = dns_cache_put_positive(c, answer->rrs[i], timestamp);
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;
378 r = dns_answer_contains(answer, q->keys[i]);
384 r = dns_answer_find_soa(answer, q->keys[i], &soa);
390 r = dns_cache_put_negative(c, q->keys[i], rcode, timestamp, MIN(soa->soa.minimum, soa->ttl));
398 /* Adding all RRs failed. Let's clean up what we already
399 * added, just in case */
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);
409 int dns_cache_lookup(DnsCache *c, DnsQuestion *q, int *rcode, DnsAnswer **ret) {
410 _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
413 bool nxdomain = false;
420 if (q->n_keys <= 0) {
426 for (i = 0; i < q->n_keys; i++) {
429 j = hashmap_get(c->by_key, q->keys[i]);
431 /* If one question cannot be answered we need to refresh */
437 LIST_FOREACH(by_key, j, j) {
440 else if (j->type == DNS_CACHE_NXDOMAIN)
447 *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS;
451 answer = dns_answer_new(n);
455 for (i = 0; i < q->n_keys; i++) {
458 j = hashmap_get(c->by_key, q->keys[i]);
459 LIST_FOREACH(by_key, j, j) {
461 r = dns_answer_add(answer, j->rr);
469 *rcode = DNS_RCODE_SUCCESS;