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
;
47 union in_addr_union owner_address
;
48 LIST_FIELDS(DnsCacheItem
, by_key
);
51 static void dns_cache_item_free(DnsCacheItem
*i
) {
55 dns_resource_record_unref(i
->rr
);
56 dns_resource_key_unref(i
->key
);
60 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsCacheItem
*, dns_cache_item_free
);
62 static void dns_cache_item_remove_and_free(DnsCache
*c
, DnsCacheItem
*i
) {
70 first
= hashmap_get(c
->by_key
, i
->key
);
71 LIST_REMOVE(by_key
, first
, i
);
74 assert_se(hashmap_replace(c
->by_key
, first
->key
, first
) >= 0);
76 hashmap_remove(c
->by_key
, i
->key
);
78 prioq_remove(c
->by_expiry
, i
, &i
->prioq_idx
);
80 dns_cache_item_free(i
);
83 void dns_cache_flush(DnsCache
*c
) {
88 while ((i
= hashmap_first(c
->by_key
)))
89 dns_cache_item_remove_and_free(c
, i
);
91 assert(hashmap_size(c
->by_key
) == 0);
92 assert(prioq_size(c
->by_expiry
) == 0);
94 c
->by_key
= hashmap_free(c
->by_key
);
95 c
->by_expiry
= prioq_free(c
->by_expiry
);
98 static bool 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
);
113 static void dns_cache_make_space(DnsCache
*c
, unsigned add
) {
119 /* Makes space for n new entries. Note that we actually allow
120 * the cache to grow beyond CACHE_MAX, but only when we shall
121 * add more RRs to the cache than CACHE_MAX at once. In that
122 * case the cache will be emptied completely otherwise. */
125 _cleanup_(dns_resource_key_unrefp
) DnsResourceKey
*key
= NULL
;
128 if (prioq_size(c
->by_expiry
) <= 0)
131 if (prioq_size(c
->by_expiry
) + add
< CACHE_MAX
)
134 i
= prioq_peek(c
->by_expiry
);
137 /* Take an extra reference to the key so that it
138 * doesn't go away in the middle of the remove call */
139 key
= dns_resource_key_ref(i
->key
);
140 dns_cache_remove(c
, key
);
144 void dns_cache_prune(DnsCache
*c
) {
149 /* Remove all entries that are past their TTL */
152 _cleanup_(dns_resource_key_unrefp
) DnsResourceKey
*key
= NULL
;
155 i
= prioq_peek(c
->by_expiry
);
160 t
= now(clock_boottime_or_monotonic());
165 /* Take an extra reference to the key so that it
166 * doesn't go away in the middle of the remove call */
167 key
= dns_resource_key_ref(i
->key
);
168 dns_cache_remove(c
, key
);
172 static int dns_cache_item_prioq_compare_func(const void *a
, const void *b
) {
173 const DnsCacheItem
*x
= a
, *y
= b
;
175 if (x
->until
< y
->until
)
177 if (x
->until
> y
->until
)
182 static int dns_cache_init(DnsCache
*c
) {
187 r
= prioq_ensure_allocated(&c
->by_expiry
, dns_cache_item_prioq_compare_func
);
191 r
= hashmap_ensure_allocated(&c
->by_key
, &dns_resource_key_hash_ops
);
198 static int dns_cache_link_item(DnsCache
*c
, DnsCacheItem
*i
) {
205 r
= prioq_put(c
->by_expiry
, i
, &i
->prioq_idx
);
209 first
= hashmap_get(c
->by_key
, i
->key
);
211 LIST_PREPEND(by_key
, first
, i
);
212 assert_se(hashmap_replace(c
->by_key
, first
->key
, first
) >= 0);
214 r
= hashmap_put(c
->by_key
, i
->key
, i
);
216 prioq_remove(c
->by_expiry
, i
, &i
->prioq_idx
);
224 static DnsCacheItem
* dns_cache_get(DnsCache
*c
, DnsResourceRecord
*rr
) {
230 LIST_FOREACH(by_key
, i
, hashmap_get(c
->by_key
, rr
->key
))
231 if (i
->rr
&& dns_resource_record_equal(i
->rr
, rr
) > 0)
237 static void dns_cache_item_update_positive(DnsCache
*c
, DnsCacheItem
*i
, DnsResourceRecord
*rr
, usec_t timestamp
) {
242 i
->type
= DNS_CACHE_POSITIVE
;
245 /* We are the first item in the list, we need to
246 * update the key used in the hashmap */
248 assert_se(hashmap_replace(c
->by_key
, rr
->key
, i
) >= 0);
250 dns_resource_record_ref(rr
);
251 dns_resource_record_unref(i
->rr
);
254 dns_resource_key_unref(i
->key
);
255 i
->key
= dns_resource_key_ref(rr
->key
);
257 i
->until
= timestamp
+ MIN(rr
->ttl
* USEC_PER_SEC
, CACHE_TTL_MAX_USEC
);
259 prioq_reshuffle(c
->by_expiry
, i
, &i
->prioq_idx
);
262 static int dns_cache_put_positive(
264 DnsResourceRecord
*rr
,
267 const union in_addr_union
*owner_address
) {
269 _cleanup_(dns_cache_item_freep
) DnsCacheItem
*i
= NULL
;
270 _cleanup_free_
char *key_str
= NULL
;
271 DnsCacheItem
*existing
;
276 assert(owner_address
);
278 /* New TTL is 0? Delete the entry... */
280 if (dns_cache_remove(c
, rr
->key
)) {
281 r
= dns_resource_key_to_string(rr
->key
, &key_str
);
285 log_debug("Removed zero TTL entry from cache: %s", key_str
);
291 if (rr
->key
->class == DNS_CLASS_ANY
)
293 if (rr
->key
->type
== DNS_TYPE_ANY
)
296 /* Entry exists already? Update TTL and timestamp */
297 existing
= dns_cache_get(c
, rr
);
299 dns_cache_item_update_positive(c
, existing
, rr
, timestamp
);
303 /* Otherwise, add the new RR */
304 r
= dns_cache_init(c
);
308 dns_cache_make_space(c
, 1);
310 i
= new0(DnsCacheItem
, 1);
314 i
->type
= DNS_CACHE_POSITIVE
;
315 i
->key
= dns_resource_key_ref(rr
->key
);
316 i
->rr
= dns_resource_record_ref(rr
);
317 i
->until
= timestamp
+ MIN(i
->rr
->ttl
* USEC_PER_SEC
, CACHE_TTL_MAX_USEC
);
318 i
->prioq_idx
= PRIOQ_IDX_NULL
;
319 i
->owner_family
= owner_family
;
320 i
->owner_address
= *owner_address
;
322 r
= dns_cache_link_item(c
, i
);
326 r
= dns_resource_key_to_string(i
->key
, &key_str
);
330 log_debug("Added cache entry for %s", key_str
);
336 static int dns_cache_put_negative(
343 const union in_addr_union
*owner_address
) {
345 _cleanup_(dns_cache_item_freep
) DnsCacheItem
*i
= NULL
;
346 _cleanup_free_
char *key_str
= NULL
;
351 assert(owner_address
);
353 dns_cache_remove(c
, key
);
355 if (key
->class == DNS_CLASS_ANY
)
357 if (key
->type
== DNS_TYPE_ANY
)
360 r
= dns_resource_key_to_string(key
, &key_str
);
364 log_debug("Ignored negative cache entry with zero SOA TTL: %s", key_str
);
369 if (!IN_SET(rcode
, DNS_RCODE_SUCCESS
, DNS_RCODE_NXDOMAIN
))
372 r
= dns_cache_init(c
);
376 dns_cache_make_space(c
, 1);
378 i
= new0(DnsCacheItem
, 1);
382 i
->type
= rcode
== DNS_RCODE_SUCCESS
? DNS_CACHE_NODATA
: DNS_CACHE_NXDOMAIN
;
383 i
->key
= dns_resource_key_ref(key
);
384 i
->until
= timestamp
+ MIN(soa_ttl
* USEC_PER_SEC
, CACHE_TTL_MAX_USEC
);
385 i
->prioq_idx
= PRIOQ_IDX_NULL
;
386 i
->owner_family
= owner_family
;
387 i
->owner_address
= *owner_address
;
389 r
= dns_cache_link_item(c
, i
);
393 r
= dns_resource_key_to_string(i
->key
, &key_str
);
397 log_debug("Added %s cache entry for %s", i
->type
== DNS_CACHE_NODATA
? "NODATA" : "NXDOMAIN", key_str
);
411 const union in_addr_union
*owner_address
) {
413 unsigned cache_keys
, i
;
419 /* First, if we were passed a question, delete all matching old RRs,
420 * so that we only keep complete by_key in place. */
421 for (i
= 0; i
< q
->n_keys
; i
++)
422 dns_cache_remove(c
, q
->keys
[i
]);
428 for (i
= 0; i
< answer
->n_rrs
; i
++)
429 dns_cache_remove(c
, answer
->items
[i
].rr
->key
);
431 /* We only care for positive replies and NXDOMAINs, on all
432 * other replies we will simply flush the respective entries,
435 if (!IN_SET(rcode
, DNS_RCODE_SUCCESS
, DNS_RCODE_NXDOMAIN
))
438 cache_keys
= answer
->n_rrs
;
441 cache_keys
+= q
->n_keys
;
443 /* Make some space for our new entries */
444 dns_cache_make_space(c
, cache_keys
);
447 timestamp
= now(clock_boottime_or_monotonic());
449 /* Second, add in positive entries for all contained RRs */
450 for (i
= 0; i
< MIN(max_rrs
, answer
->n_rrs
); i
++) {
451 r
= dns_cache_put_positive(c
, answer
->items
[i
].rr
, timestamp
, owner_family
, owner_address
);
459 /* Third, add in negative entries for all keys with no RR */
460 for (i
= 0; i
< q
->n_keys
; i
++) {
461 DnsResourceRecord
*soa
= NULL
;
463 r
= dns_answer_contains(answer
, q
->keys
[i
]);
469 /* See https://tools.ietf.org/html/rfc2308, which
470 * say that a matching SOA record in the packet
471 * is used to to enable negative caching. */
473 r
= dns_answer_find_soa(answer
, q
->keys
[i
], &soa
);
479 r
= dns_cache_put_negative(c
, q
->keys
[i
], rcode
, timestamp
, MIN(soa
->soa
.minimum
, soa
->ttl
), owner_family
, owner_address
);
487 /* Adding all RRs failed. Let's clean up what we already
488 * added, just in case */
491 for (i
= 0; i
< q
->n_keys
; i
++)
492 dns_cache_remove(c
, q
->keys
[i
]);
495 for (i
= 0; i
< answer
->n_rrs
; i
++)
496 dns_cache_remove(c
, answer
->items
[i
].rr
->key
);
501 int dns_cache_lookup(DnsCache
*c
, DnsResourceKey
*key
, int *rcode
, DnsAnswer
**ret
) {
502 _cleanup_(dns_answer_unrefp
) DnsAnswer
*answer
= NULL
;
505 bool nxdomain
= false;
506 _cleanup_free_
char *key_str
= NULL
;
507 DnsCacheItem
*j
, *first
;
514 if (key
->type
== DNS_TYPE_ANY
||
515 key
->class == DNS_CLASS_ANY
) {
517 /* If we have ANY lookups we simply refresh */
519 r
= dns_resource_key_to_string(key
, &key_str
);
523 log_debug("Ignoring cache for ANY lookup: %s", key_str
);
526 *rcode
= DNS_RCODE_SUCCESS
;
530 first
= hashmap_get(c
->by_key
, key
);
532 /* If one question cannot be answered we need to refresh */
534 r
= dns_resource_key_to_string(key
, &key_str
);
538 log_debug("Cache miss for %s", key_str
);
541 *rcode
= DNS_RCODE_SUCCESS
;
545 LIST_FOREACH(by_key
, j
, first
) {
548 else if (j
->type
== DNS_CACHE_NXDOMAIN
)
552 r
= dns_resource_key_to_string(key
, &key_str
);
556 log_debug("%s cache hit for %s",
557 nxdomain
? "NXDOMAIN" :
558 n
> 0 ? "Positive" : "NODATA",
563 *rcode
= nxdomain
? DNS_RCODE_NXDOMAIN
: DNS_RCODE_SUCCESS
;
567 answer
= dns_answer_new(n
);
571 LIST_FOREACH(by_key
, j
, first
) {
575 r
= dns_answer_add(answer
, j
->rr
, 0);
581 *rcode
= DNS_RCODE_SUCCESS
;
587 int dns_cache_check_conflicts(DnsCache
*cache
, DnsResourceRecord
*rr
, int owner_family
, const union in_addr_union
*owner_address
) {
588 DnsCacheItem
*i
, *first
;
589 bool same_owner
= true;
594 dns_cache_prune(cache
);
596 /* See if there's a cache entry for the same key. If there
597 * isn't there's no conflict */
598 first
= hashmap_get(cache
->by_key
, rr
->key
);
602 /* See if the RR key is owned by the same owner, if so, there
603 * isn't a conflict either */
604 LIST_FOREACH(by_key
, i
, first
) {
605 if (i
->owner_family
!= owner_family
||
606 !in_addr_equal(owner_family
, &i
->owner_address
, owner_address
)) {
614 /* See if there's the exact same RR in the cache. If yes, then
615 * there's no conflict. */
616 if (dns_cache_get(cache
, rr
))
619 /* There's a conflict */
623 void dns_cache_dump(DnsCache
*cache
, FILE *f
) {
634 HASHMAP_FOREACH(i
, cache
->by_key
, iterator
) {
637 LIST_FOREACH(by_key
, j
, i
) {
638 _cleanup_free_
char *t
= NULL
;
643 r
= dns_resource_record_to_string(j
->rr
, &t
);
652 r
= dns_resource_key_to_string(j
->key
, &t
);
660 fputs(j
->type
== DNS_CACHE_NODATA
? "NODATA" : "NXDOMAIN", f
);
667 bool dns_cache_is_empty(DnsCache
*cache
) {
671 return hashmap_isempty(cache
->by_key
);