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
;
244 if (!i
->by_key_prev
) {
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);
251 dns_resource_record_ref(rr
);
252 dns_resource_record_unref(i
->rr
);
255 dns_resource_key_unref(i
->key
);
256 i
->key
= dns_resource_key_ref(rr
->key
);
258 i
->until
= timestamp
+ MIN(rr
->ttl
* USEC_PER_SEC
, CACHE_TTL_MAX_USEC
);
260 prioq_reshuffle(c
->by_expiry
, i
, &i
->prioq_idx
);
263 static int dns_cache_put_positive(
265 DnsResourceRecord
*rr
,
268 const union in_addr_union
*owner_address
) {
270 _cleanup_(dns_cache_item_freep
) DnsCacheItem
*i
= NULL
;
271 _cleanup_free_
char *key_str
= NULL
;
272 DnsCacheItem
*existing
;
277 assert(owner_address
);
279 /* New TTL is 0? Delete the entry... */
281 if (dns_cache_remove(c
, rr
->key
)) {
282 r
= dns_resource_key_to_string(rr
->key
, &key_str
);
286 log_debug("Removed zero TTL entry from cache: %s", key_str
);
292 if (rr
->key
->class == DNS_CLASS_ANY
)
294 if (rr
->key
->type
== DNS_TYPE_ANY
)
297 /* Entry exists already? Update TTL and timestamp */
298 existing
= dns_cache_get(c
, rr
);
300 dns_cache_item_update_positive(c
, existing
, rr
, timestamp
);
304 /* Otherwise, add the new RR */
305 r
= dns_cache_init(c
);
309 dns_cache_make_space(c
, 1);
311 i
= new0(DnsCacheItem
, 1);
315 i
->type
= DNS_CACHE_POSITIVE
;
316 i
->key
= dns_resource_key_ref(rr
->key
);
317 i
->rr
= dns_resource_record_ref(rr
);
318 i
->until
= timestamp
+ MIN(i
->rr
->ttl
* USEC_PER_SEC
, CACHE_TTL_MAX_USEC
);
319 i
->prioq_idx
= PRIOQ_IDX_NULL
;
320 i
->owner_family
= owner_family
;
321 i
->owner_address
= *owner_address
;
323 r
= dns_cache_link_item(c
, i
);
327 r
= dns_resource_key_to_string(i
->key
, &key_str
);
331 log_debug("Added cache entry for %s", key_str
);
337 static int dns_cache_put_negative(
344 const union in_addr_union
*owner_address
) {
346 _cleanup_(dns_cache_item_freep
) DnsCacheItem
*i
= NULL
;
347 _cleanup_free_
char *key_str
= NULL
;
352 assert(owner_address
);
354 dns_cache_remove(c
, key
);
356 if (key
->class == DNS_CLASS_ANY
)
358 if (key
->type
== DNS_TYPE_ANY
)
361 r
= dns_resource_key_to_string(key
, &key_str
);
365 log_debug("Ignored negative cache entry with zero SOA TTL: %s", key_str
);
370 if (!IN_SET(rcode
, DNS_RCODE_SUCCESS
, DNS_RCODE_NXDOMAIN
))
373 r
= dns_cache_init(c
);
377 dns_cache_make_space(c
, 1);
379 i
= new0(DnsCacheItem
, 1);
383 i
->type
= rcode
== DNS_RCODE_SUCCESS
? DNS_CACHE_NODATA
: DNS_CACHE_NXDOMAIN
;
384 i
->key
= dns_resource_key_ref(key
);
385 i
->until
= timestamp
+ MIN(soa_ttl
* USEC_PER_SEC
, CACHE_TTL_MAX_USEC
);
386 i
->prioq_idx
= PRIOQ_IDX_NULL
;
387 i
->owner_family
= owner_family
;
388 i
->owner_address
= *owner_address
;
390 r
= dns_cache_link_item(c
, i
);
394 r
= dns_resource_key_to_string(i
->key
, &key_str
);
398 log_debug("Added %s cache entry for %s", i
->type
== DNS_CACHE_NODATA
? "NODATA" : "NXDOMAIN", key_str
);
412 const union in_addr_union
*owner_address
) {
414 unsigned cache_keys
, i
;
420 /* First, if we were passed a question, delete all matching old RRs,
421 * so that we only keep complete by_key in place. */
422 for (i
= 0; i
< q
->n_keys
; i
++)
423 dns_cache_remove(c
, q
->keys
[i
]);
429 for (i
= 0; i
< answer
->n_rrs
; i
++)
430 dns_cache_remove(c
, answer
->items
[i
].rr
->key
);
432 /* We only care for positive replies and NXDOMAINs, on all
433 * other replies we will simply flush the respective entries,
436 if (!IN_SET(rcode
, DNS_RCODE_SUCCESS
, DNS_RCODE_NXDOMAIN
))
439 cache_keys
= answer
->n_rrs
;
442 cache_keys
+= q
->n_keys
;
444 /* Make some space for our new entries */
445 dns_cache_make_space(c
, cache_keys
);
448 timestamp
= now(clock_boottime_or_monotonic());
450 /* Second, add in positive entries for all contained RRs */
451 for (i
= 0; i
< MIN(max_rrs
, answer
->n_rrs
); i
++) {
452 r
= dns_cache_put_positive(c
, answer
->items
[i
].rr
, timestamp
, owner_family
, owner_address
);
460 /* Third, add in negative entries for all keys with no RR */
461 for (i
= 0; i
< q
->n_keys
; i
++) {
462 DnsResourceRecord
*soa
= NULL
;
464 r
= dns_answer_contains(answer
, q
->keys
[i
]);
470 /* See https://tools.ietf.org/html/rfc2308, which
471 * say that a matching SOA record in the packet
472 * is used to to enable negative caching. */
474 r
= dns_answer_find_soa(answer
, q
->keys
[i
], &soa
);
480 r
= dns_cache_put_negative(c
, q
->keys
[i
], rcode
, timestamp
, MIN(soa
->soa
.minimum
, soa
->ttl
), owner_family
, owner_address
);
488 /* Adding all RRs failed. Let's clean up what we already
489 * added, just in case */
492 for (i
= 0; i
< q
->n_keys
; i
++)
493 dns_cache_remove(c
, q
->keys
[i
]);
496 for (i
= 0; i
< answer
->n_rrs
; i
++)
497 dns_cache_remove(c
, answer
->items
[i
].rr
->key
);
502 int dns_cache_lookup(DnsCache
*c
, DnsResourceKey
*key
, int *rcode
, DnsAnswer
**ret
) {
503 _cleanup_(dns_answer_unrefp
) DnsAnswer
*answer
= NULL
;
506 bool nxdomain
= false;
507 _cleanup_free_
char *key_str
= NULL
;
508 DnsCacheItem
*j
, *first
;
515 if (key
->type
== DNS_TYPE_ANY
||
516 key
->class == DNS_CLASS_ANY
) {
518 /* If we have ANY lookups we simply refresh */
520 r
= dns_resource_key_to_string(key
, &key_str
);
524 log_debug("Ignoring cache for ANY lookup: %s", key_str
);
527 *rcode
= DNS_RCODE_SUCCESS
;
531 first
= hashmap_get(c
->by_key
, key
);
533 /* If one question cannot be answered we need to refresh */
535 r
= dns_resource_key_to_string(key
, &key_str
);
539 log_debug("Cache miss for %s", key_str
);
542 *rcode
= DNS_RCODE_SUCCESS
;
546 LIST_FOREACH(by_key
, j
, first
) {
549 else if (j
->type
== DNS_CACHE_NXDOMAIN
)
553 r
= dns_resource_key_to_string(key
, &key_str
);
557 log_debug("%s cache hit for %s",
558 nxdomain
? "NXDOMAIN" :
559 n
> 0 ? "Positive" : "NODATA",
564 *rcode
= nxdomain
? DNS_RCODE_NXDOMAIN
: DNS_RCODE_SUCCESS
;
568 answer
= dns_answer_new(n
);
572 LIST_FOREACH(by_key
, j
, first
) {
576 r
= dns_answer_add(answer
, j
->rr
, 0);
582 *rcode
= DNS_RCODE_SUCCESS
;
588 int dns_cache_check_conflicts(DnsCache
*cache
, DnsResourceRecord
*rr
, int owner_family
, const union in_addr_union
*owner_address
) {
589 DnsCacheItem
*i
, *first
;
590 bool same_owner
= true;
595 dns_cache_prune(cache
);
597 /* See if there's a cache entry for the same key. If there
598 * isn't there's no conflict */
599 first
= hashmap_get(cache
->by_key
, rr
->key
);
603 /* See if the RR key is owned by the same owner, if so, there
604 * isn't a conflict either */
605 LIST_FOREACH(by_key
, i
, first
) {
606 if (i
->owner_family
!= owner_family
||
607 !in_addr_equal(owner_family
, &i
->owner_address
, owner_address
)) {
615 /* See if there's the exact same RR in the cache. If yes, then
616 * there's no conflict. */
617 if (dns_cache_get(cache
, rr
))
620 /* There's a conflict */
624 void dns_cache_dump(DnsCache
*cache
, FILE *f
) {
635 HASHMAP_FOREACH(i
, cache
->by_key
, iterator
) {
638 LIST_FOREACH(by_key
, j
, i
) {
639 _cleanup_free_
char *t
= NULL
;
644 r
= dns_resource_record_to_string(j
->rr
, &t
);
653 r
= dns_resource_key_to_string(j
->key
, &t
);
661 fputs(j
->type
== DNS_CACHE_NODATA
? "NODATA" : "NXDOMAIN", f
);
668 bool dns_cache_is_empty(DnsCache
*cache
) {
672 return hashmap_isempty(cache
->by_key
);