]> git.ipfire.org Git - thirdparty/systemd.git/blob - src/resolve/resolved-dns-cache.c
ef6b69c768e64a06332496e81063c67bf7fcc426
[thirdparty/systemd.git] / src / resolve / resolved-dns-cache.c
1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
2
3 /***
4 This file is part of systemd.
5
6 Copyright 2014 Lennart Poettering
7
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.
12
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.
17
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/>.
20 ***/
21
22 #include "resolved-dns-cache.h"
23 #include "resolved-dns-packet.h"
24
25 /* Never cache more than 1K entries */
26 #define CACHE_MAX 1024
27
28 /* We never keep any item longer than 10min in our cache */
29 #define CACHE_TTL_MAX_USEC (10 * USEC_PER_MINUTE)
30
31 typedef enum DnsCacheItemType DnsCacheItemType;
32 typedef struct DnsCacheItem DnsCacheItem;
33
34 enum DnsCacheItemType {
35 DNS_CACHE_POSITIVE,
36 DNS_CACHE_NODATA,
37 DNS_CACHE_NXDOMAIN,
38 };
39
40 struct DnsCacheItem {
41 DnsResourceKey *key;
42 DnsResourceRecord *rr;
43 usec_t until;
44 DnsCacheItemType type;
45 unsigned prioq_idx;
46 int owner_family;
47 union in_addr_union owner_address;
48 LIST_FIELDS(DnsCacheItem, by_key);
49 };
50
51 static void dns_cache_item_free(DnsCacheItem *i) {
52 if (!i)
53 return;
54
55 dns_resource_record_unref(i->rr);
56 dns_resource_key_unref(i->key);
57 free(i);
58 }
59
60 DEFINE_TRIVIAL_CLEANUP_FUNC(DnsCacheItem*, dns_cache_item_free);
61
62 static void dns_cache_item_remove_and_free(DnsCache *c, DnsCacheItem *i) {
63 DnsCacheItem *first;
64
65 assert(c);
66
67 if (!i)
68 return;
69
70 first = hashmap_get(c->by_key, i->key);
71 LIST_REMOVE(by_key, first, i);
72
73 if (first)
74 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
75 else
76 hashmap_remove(c->by_key, i->key);
77
78 prioq_remove(c->by_expiry, i, &i->prioq_idx);
79
80 dns_cache_item_free(i);
81 }
82
83 void dns_cache_flush(DnsCache *c) {
84 DnsCacheItem *i;
85
86 assert(c);
87
88 while ((i = hashmap_first(c->by_key)))
89 dns_cache_item_remove_and_free(c, i);
90
91 assert(hashmap_size(c->by_key) == 0);
92 assert(prioq_size(c->by_expiry) == 0);
93
94 c->by_key = hashmap_free(c->by_key);
95 c->by_expiry = prioq_free(c->by_expiry);
96 }
97
98 static bool dns_cache_remove(DnsCache *c, DnsResourceKey *key) {
99 DnsCacheItem *i;
100 bool exist = false;
101
102 assert(c);
103 assert(key);
104
105 while ((i = hashmap_get(c->by_key, key))) {
106 dns_cache_item_remove_and_free(c, i);
107 exist = true;
108 }
109
110 return exist;
111 }
112
113 static void dns_cache_make_space(DnsCache *c, unsigned add) {
114 assert(c);
115
116 if (add <= 0)
117 return;
118
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. */
123
124 for (;;) {
125 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
126 DnsCacheItem *i;
127
128 if (prioq_size(c->by_expiry) <= 0)
129 break;
130
131 if (prioq_size(c->by_expiry) + add < CACHE_MAX)
132 break;
133
134 i = prioq_peek(c->by_expiry);
135 assert(i);
136
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);
141 }
142 }
143
144 void dns_cache_prune(DnsCache *c) {
145 usec_t t = 0;
146
147 assert(c);
148
149 /* Remove all entries that are past their TTL */
150
151 for (;;) {
152 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
153 DnsCacheItem *i;
154
155 i = prioq_peek(c->by_expiry);
156 if (!i)
157 break;
158
159 if (t <= 0)
160 t = now(clock_boottime_or_monotonic());
161
162 if (i->until > t)
163 break;
164
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);
169 }
170 }
171
172 static int dns_cache_item_prioq_compare_func(const void *a, const void *b) {
173 const DnsCacheItem *x = a, *y = b;
174
175 if (x->until < y->until)
176 return -1;
177 if (x->until > y->until)
178 return 1;
179 return 0;
180 }
181
182 static int dns_cache_init(DnsCache *c) {
183 int r;
184
185 assert(c);
186
187 r = prioq_ensure_allocated(&c->by_expiry, dns_cache_item_prioq_compare_func);
188 if (r < 0)
189 return r;
190
191 r = hashmap_ensure_allocated(&c->by_key, &dns_resource_key_hash_ops);
192 if (r < 0)
193 return r;
194
195 return r;
196 }
197
198 static int dns_cache_link_item(DnsCache *c, DnsCacheItem *i) {
199 DnsCacheItem *first;
200 int r;
201
202 assert(c);
203 assert(i);
204
205 r = prioq_put(c->by_expiry, i, &i->prioq_idx);
206 if (r < 0)
207 return r;
208
209 first = hashmap_get(c->by_key, i->key);
210 if (first) {
211 LIST_PREPEND(by_key, first, i);
212 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
213 } else {
214 r = hashmap_put(c->by_key, i->key, i);
215 if (r < 0) {
216 prioq_remove(c->by_expiry, i, &i->prioq_idx);
217 return r;
218 }
219 }
220
221 return 0;
222 }
223
224 static DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) {
225 DnsCacheItem *i;
226
227 assert(c);
228 assert(rr);
229
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)
232 return i;
233
234 return NULL;
235 }
236
237 static void dns_cache_item_update_positive(DnsCache *c, DnsCacheItem *i, DnsResourceRecord *rr, usec_t timestamp) {
238 assert(c);
239 assert(i);
240 assert(rr);
241
242 i->type = DNS_CACHE_POSITIVE;
243
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 */
247
248 assert_se(hashmap_replace(c->by_key, rr->key, i) >= 0);
249 }
250
251 dns_resource_record_ref(rr);
252 dns_resource_record_unref(i->rr);
253 i->rr = rr;
254
255 dns_resource_key_unref(i->key);
256 i->key = dns_resource_key_ref(rr->key);
257
258 i->until = timestamp + MIN(rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
259
260 prioq_reshuffle(c->by_expiry, i, &i->prioq_idx);
261 }
262
263 static int dns_cache_put_positive(
264 DnsCache *c,
265 DnsResourceRecord *rr,
266 usec_t timestamp,
267 int owner_family,
268 const union in_addr_union *owner_address) {
269
270 _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
271 _cleanup_free_ char *key_str = NULL;
272 DnsCacheItem *existing;
273 int r;
274
275 assert(c);
276 assert(rr);
277 assert(owner_address);
278
279 /* New TTL is 0? Delete the entry... */
280 if (rr->ttl <= 0) {
281 if (dns_cache_remove(c, rr->key)) {
282 r = dns_resource_key_to_string(rr->key, &key_str);
283 if (r < 0)
284 return r;
285
286 log_debug("Removed zero TTL entry from cache: %s", key_str);
287 }
288
289 return 0;
290 }
291
292 if (rr->key->class == DNS_CLASS_ANY)
293 return 0;
294 if (rr->key->type == DNS_TYPE_ANY)
295 return 0;
296
297 /* Entry exists already? Update TTL and timestamp */
298 existing = dns_cache_get(c, rr);
299 if (existing) {
300 dns_cache_item_update_positive(c, existing, rr, timestamp);
301 return 0;
302 }
303
304 /* Otherwise, add the new RR */
305 r = dns_cache_init(c);
306 if (r < 0)
307 return r;
308
309 dns_cache_make_space(c, 1);
310
311 i = new0(DnsCacheItem, 1);
312 if (!i)
313 return -ENOMEM;
314
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;
322
323 r = dns_cache_link_item(c, i);
324 if (r < 0)
325 return r;
326
327 r = dns_resource_key_to_string(i->key, &key_str);
328 if (r < 0)
329 return r;
330
331 log_debug("Added cache entry for %s", key_str);
332
333 i = NULL;
334 return 0;
335 }
336
337 static int dns_cache_put_negative(
338 DnsCache *c,
339 DnsResourceKey *key,
340 int rcode,
341 usec_t timestamp,
342 uint32_t soa_ttl,
343 int owner_family,
344 const union in_addr_union *owner_address) {
345
346 _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
347 _cleanup_free_ char *key_str = NULL;
348 int r;
349
350 assert(c);
351 assert(key);
352 assert(owner_address);
353
354 dns_cache_remove(c, key);
355
356 if (key->class == DNS_CLASS_ANY)
357 return 0;
358 if (key->type == DNS_TYPE_ANY)
359 return 0;
360 if (soa_ttl <= 0) {
361 r = dns_resource_key_to_string(key, &key_str);
362 if (r < 0)
363 return r;
364
365 log_debug("Ignored negative cache entry with zero SOA TTL: %s", key_str);
366
367 return 0;
368 }
369
370 if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
371 return 0;
372
373 r = dns_cache_init(c);
374 if (r < 0)
375 return r;
376
377 dns_cache_make_space(c, 1);
378
379 i = new0(DnsCacheItem, 1);
380 if (!i)
381 return -ENOMEM;
382
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;
389
390 r = dns_cache_link_item(c, i);
391 if (r < 0)
392 return r;
393
394 r = dns_resource_key_to_string(i->key, &key_str);
395 if (r < 0)
396 return r;
397
398 log_debug("Added %s cache entry for %s", i->type == DNS_CACHE_NODATA ? "NODATA" : "NXDOMAIN", key_str);
399
400 i = NULL;
401 return 0;
402 }
403
404 int dns_cache_put(
405 DnsCache *c,
406 DnsQuestion *q,
407 int rcode,
408 DnsAnswer *answer,
409 unsigned max_rrs,
410 usec_t timestamp,
411 int owner_family,
412 const union in_addr_union *owner_address) {
413
414 unsigned cache_keys, i;
415 int r;
416
417 assert(c);
418
419 if (q) {
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]);
424 }
425
426 if (!answer)
427 return 0;
428
429 for (i = 0; i < answer->n_rrs; i++)
430 dns_cache_remove(c, answer->items[i].rr->key);
431
432 /* We only care for positive replies and NXDOMAINs, on all
433 * other replies we will simply flush the respective entries,
434 * and that's it */
435
436 if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
437 return 0;
438
439 cache_keys = answer->n_rrs;
440
441 if (q)
442 cache_keys += q->n_keys;
443
444 /* Make some space for our new entries */
445 dns_cache_make_space(c, cache_keys);
446
447 if (timestamp <= 0)
448 timestamp = now(clock_boottime_or_monotonic());
449
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);
453 if (r < 0)
454 goto fail;
455 }
456
457 if (!q)
458 return 0;
459
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;
463
464 r = dns_answer_contains(answer, q->keys[i]);
465 if (r < 0)
466 goto fail;
467 if (r > 0)
468 continue;
469
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. */
473
474 r = dns_answer_find_soa(answer, q->keys[i], &soa);
475 if (r < 0)
476 goto fail;
477 if (r == 0)
478 continue;
479
480 r = dns_cache_put_negative(c, q->keys[i], rcode, timestamp, MIN(soa->soa.minimum, soa->ttl), owner_family, owner_address);
481 if (r < 0)
482 goto fail;
483 }
484
485 return 0;
486
487 fail:
488 /* Adding all RRs failed. Let's clean up what we already
489 * added, just in case */
490
491 if (q) {
492 for (i = 0; i < q->n_keys; i++)
493 dns_cache_remove(c, q->keys[i]);
494 }
495
496 for (i = 0; i < answer->n_rrs; i++)
497 dns_cache_remove(c, answer->items[i].rr->key);
498
499 return r;
500 }
501
502 int dns_cache_lookup(DnsCache *c, DnsResourceKey *key, int *rcode, DnsAnswer **ret) {
503 _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
504 unsigned n = 0;
505 int r;
506 bool nxdomain = false;
507 _cleanup_free_ char *key_str = NULL;
508 DnsCacheItem *j, *first;
509
510 assert(c);
511 assert(key);
512 assert(rcode);
513 assert(ret);
514
515 if (key->type == DNS_TYPE_ANY ||
516 key->class == DNS_CLASS_ANY) {
517
518 /* If we have ANY lookups we simply refresh */
519
520 r = dns_resource_key_to_string(key, &key_str);
521 if (r < 0)
522 return r;
523
524 log_debug("Ignoring cache for ANY lookup: %s", key_str);
525
526 *ret = NULL;
527 *rcode = DNS_RCODE_SUCCESS;
528 return 0;
529 }
530
531 first = hashmap_get(c->by_key, key);
532 if (!first) {
533 /* If one question cannot be answered we need to refresh */
534
535 r = dns_resource_key_to_string(key, &key_str);
536 if (r < 0)
537 return r;
538
539 log_debug("Cache miss for %s", key_str);
540
541 *ret = NULL;
542 *rcode = DNS_RCODE_SUCCESS;
543 return 0;
544 }
545
546 LIST_FOREACH(by_key, j, first) {
547 if (j->rr)
548 n++;
549 else if (j->type == DNS_CACHE_NXDOMAIN)
550 nxdomain = true;
551 }
552
553 r = dns_resource_key_to_string(key, &key_str);
554 if (r < 0)
555 return r;
556
557 log_debug("%s cache hit for %s",
558 nxdomain ? "NXDOMAIN" :
559 n > 0 ? "Positive" : "NODATA",
560 key_str);
561
562 if (n <= 0) {
563 *ret = NULL;
564 *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS;
565 return 1;
566 }
567
568 answer = dns_answer_new(n);
569 if (!answer)
570 return -ENOMEM;
571
572 LIST_FOREACH(by_key, j, first) {
573 if (!j->rr)
574 continue;
575
576 r = dns_answer_add(answer, j->rr, 0);
577 if (r < 0)
578 return r;
579 }
580
581 *ret = answer;
582 *rcode = DNS_RCODE_SUCCESS;
583 answer = NULL;
584
585 return n;
586 }
587
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;
591
592 assert(cache);
593 assert(rr);
594
595 dns_cache_prune(cache);
596
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);
600 if (!first)
601 return 0;
602
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)) {
608 same_owner = false;
609 break;
610 }
611 }
612 if (same_owner)
613 return 0;
614
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))
618 return 0;
619
620 /* There's a conflict */
621 return 1;
622 }
623
624 void dns_cache_dump(DnsCache *cache, FILE *f) {
625 Iterator iterator;
626 DnsCacheItem *i;
627 int r;
628
629 if (!cache)
630 return;
631
632 if (!f)
633 f = stdout;
634
635 HASHMAP_FOREACH(i, cache->by_key, iterator) {
636 DnsCacheItem *j;
637
638 LIST_FOREACH(by_key, j, i) {
639 _cleanup_free_ char *t = NULL;
640
641 fputc('\t', f);
642
643 if (j->rr) {
644 r = dns_resource_record_to_string(j->rr, &t);
645 if (r < 0) {
646 log_oom();
647 continue;
648 }
649
650 fputs(t, f);
651 fputc('\n', f);
652 } else {
653 r = dns_resource_key_to_string(j->key, &t);
654 if (r < 0) {
655 log_oom();
656 continue;
657 }
658
659 fputs(t, f);
660 fputs(" -- ", f);
661 fputs(j->type == DNS_CACHE_NODATA ? "NODATA" : "NXDOMAIN", f);
662 fputc('\n', f);
663 }
664 }
665 }
666 }
667
668 bool dns_cache_is_empty(DnsCache *cache) {
669 if (!cache)
670 return true;
671
672 return hashmap_isempty(cache->by_key);
673 }