]>
Commit | Line | Data |
---|---|---|
322345fd LP |
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" | |
7e8e0422 | 23 | #include "resolved-dns-packet.h" |
322345fd | 24 | |
cbd4560e | 25 | /* Never cache more than 1K entries */ |
322345fd | 26 | #define CACHE_MAX 1024 |
cbd4560e LP |
27 | |
28 | /* We never keep any item longer than 10min in our cache */ | |
322345fd LP |
29 | #define CACHE_TTL_MAX_USEC (10 * USEC_PER_MINUTE) |
30 | ||
623a4c97 LP |
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 | LIST_FIELDS(DnsCacheItem, by_key); | |
47 | }; | |
48 | ||
322345fd LP |
49 | static void dns_cache_item_free(DnsCacheItem *i) { |
50 | if (!i) | |
51 | return; | |
52 | ||
53 | dns_resource_record_unref(i->rr); | |
7e8e0422 | 54 | dns_resource_key_unref(i->key); |
322345fd LP |
55 | free(i); |
56 | } | |
57 | ||
58 | DEFINE_TRIVIAL_CLEANUP_FUNC(DnsCacheItem*, dns_cache_item_free); | |
59 | ||
60 | static void dns_cache_item_remove_and_free(DnsCache *c, DnsCacheItem *i) { | |
61 | DnsCacheItem *first; | |
62 | ||
63 | assert(c); | |
64 | ||
65 | if (!i) | |
66 | return; | |
67 | ||
7e8e0422 LP |
68 | first = hashmap_get(c->by_key, i->key); |
69 | LIST_REMOVE(by_key, first, i); | |
322345fd LP |
70 | |
71 | if (first) | |
7e8e0422 | 72 | assert_se(hashmap_replace(c->by_key, first->key, first) >= 0); |
322345fd | 73 | else |
7e8e0422 | 74 | hashmap_remove(c->by_key, i->key); |
322345fd | 75 | |
7e8e0422 | 76 | prioq_remove(c->by_expiry, i, &i->prioq_idx); |
322345fd LP |
77 | |
78 | dns_cache_item_free(i); | |
79 | } | |
80 | ||
81 | void dns_cache_flush(DnsCache *c) { | |
82 | DnsCacheItem *i; | |
83 | ||
84 | assert(c); | |
85 | ||
7e8e0422 | 86 | while ((i = hashmap_first(c->by_key))) |
322345fd LP |
87 | dns_cache_item_remove_and_free(c, i); |
88 | ||
7e8e0422 LP |
89 | assert(hashmap_size(c->by_key) == 0); |
90 | assert(prioq_size(c->by_expiry) == 0); | |
322345fd | 91 | |
7e8e0422 LP |
92 | hashmap_free(c->by_key); |
93 | c->by_key = NULL; | |
322345fd | 94 | |
7e8e0422 LP |
95 | prioq_free(c->by_expiry); |
96 | c->by_expiry = NULL; | |
322345fd LP |
97 | } |
98 | ||
7e8e0422 | 99 | static void dns_cache_remove(DnsCache *c, DnsResourceKey *key) { |
322345fd LP |
100 | DnsCacheItem *i; |
101 | ||
102 | assert(c); | |
103 | assert(key); | |
104 | ||
7e8e0422 | 105 | while ((i = hashmap_get(c->by_key, key))) |
322345fd LP |
106 | dns_cache_item_remove_and_free(c, i); |
107 | } | |
108 | ||
109 | static void dns_cache_make_space(DnsCache *c, unsigned add) { | |
110 | assert(c); | |
111 | ||
112 | if (add <= 0) | |
113 | return; | |
114 | ||
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. */ | |
119 | ||
120 | for (;;) { | |
faa133f3 | 121 | _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL; |
322345fd LP |
122 | DnsCacheItem *i; |
123 | ||
7e8e0422 | 124 | if (prioq_size(c->by_expiry) <= 0) |
322345fd LP |
125 | break; |
126 | ||
7e8e0422 | 127 | if (prioq_size(c->by_expiry) + add < CACHE_MAX) |
322345fd LP |
128 | break; |
129 | ||
7e8e0422 | 130 | i = prioq_peek(c->by_expiry); |
cbd4560e LP |
131 | assert(i); |
132 | ||
faa133f3 | 133 | /* Take an extra reference to the key so that it |
cbd4560e | 134 | * doesn't go away in the middle of the remove call */ |
7e8e0422 | 135 | key = dns_resource_key_ref(i->key); |
faa133f3 | 136 | dns_cache_remove(c, key); |
322345fd LP |
137 | } |
138 | } | |
139 | ||
140 | void dns_cache_prune(DnsCache *c) { | |
141 | usec_t t = 0; | |
142 | ||
143 | assert(c); | |
144 | ||
145 | /* Remove all entries that are past their TTL */ | |
146 | ||
147 | for (;;) { | |
faa133f3 | 148 | _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL; |
322345fd | 149 | DnsCacheItem *i; |
322345fd | 150 | |
7e8e0422 | 151 | i = prioq_peek(c->by_expiry); |
322345fd LP |
152 | if (!i) |
153 | break; | |
154 | ||
322345fd | 155 | if (t <= 0) |
9a015429 | 156 | t = now(CLOCK_BOOTTIME); |
322345fd | 157 | |
7e8e0422 | 158 | if (i->until > t) |
322345fd LP |
159 | break; |
160 | ||
faa133f3 | 161 | /* Take an extra reference to the key so that it |
cbd4560e | 162 | * doesn't go away in the middle of the remove call */ |
7e8e0422 | 163 | key = dns_resource_key_ref(i->key); |
faa133f3 | 164 | dns_cache_remove(c, key); |
322345fd LP |
165 | } |
166 | } | |
167 | ||
168 | static int dns_cache_item_prioq_compare_func(const void *a, const void *b) { | |
322345fd LP |
169 | const DnsCacheItem *x = a, *y = b; |
170 | ||
7e8e0422 | 171 | if (x->until < y->until) |
322345fd | 172 | return -1; |
7e8e0422 | 173 | if (x->until > y->until) |
322345fd LP |
174 | return 1; |
175 | return 0; | |
176 | } | |
177 | ||
623a4c97 | 178 | static int dns_cache_init(DnsCache *c) { |
7e8e0422 LP |
179 | int r; |
180 | ||
623a4c97 LP |
181 | assert(c); |
182 | ||
7e8e0422 LP |
183 | r = prioq_ensure_allocated(&c->by_expiry, dns_cache_item_prioq_compare_func); |
184 | if (r < 0) | |
185 | return r; | |
186 | ||
187 | r = hashmap_ensure_allocated(&c->by_key, dns_resource_key_hash_func, dns_resource_key_compare_func); | |
188 | if (r < 0) | |
189 | return r; | |
190 | ||
191 | return r; | |
192 | } | |
193 | ||
194 | static int dns_cache_link_item(DnsCache *c, DnsCacheItem *i) { | |
195 | DnsCacheItem *first; | |
196 | int r; | |
197 | ||
322345fd LP |
198 | assert(c); |
199 | assert(i); | |
322345fd | 200 | |
7e8e0422 LP |
201 | r = prioq_put(c->by_expiry, i, &i->prioq_idx); |
202 | if (r < 0) | |
203 | return r; | |
322345fd | 204 | |
7e8e0422 LP |
205 | first = hashmap_get(c->by_key, i->key); |
206 | if (first) { | |
207 | LIST_PREPEND(by_key, first, i); | |
208 | assert_se(hashmap_replace(c->by_key, first->key, first) >= 0); | |
209 | } else { | |
210 | r = hashmap_put(c->by_key, i->key, i); | |
211 | if (r < 0) { | |
212 | prioq_remove(c->by_expiry, i, &i->prioq_idx); | |
213 | return r; | |
214 | } | |
322345fd LP |
215 | } |
216 | ||
7e8e0422 | 217 | return 0; |
322345fd LP |
218 | } |
219 | ||
faa133f3 LP |
220 | static DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) { |
221 | DnsCacheItem *i; | |
222 | ||
223 | assert(c); | |
224 | assert(rr); | |
225 | ||
7e8e0422 LP |
226 | LIST_FOREACH(by_key, i, hashmap_get(c->by_key, rr->key)) |
227 | if (i->rr && dns_resource_record_equal(i->rr, rr)) | |
faa133f3 LP |
228 | return i; |
229 | ||
230 | return NULL; | |
231 | } | |
232 | ||
7e8e0422 LP |
233 | static void dns_cache_item_update_positive(DnsCache *c, DnsCacheItem *i, DnsResourceRecord *rr, usec_t timestamp) { |
234 | assert(c); | |
235 | assert(i); | |
236 | assert(rr); | |
237 | ||
238 | i->type = DNS_CACHE_POSITIVE; | |
239 | ||
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 */ | |
243 | ||
244 | assert_se(hashmap_replace(c->by_key, rr->key, i) >= 0); | |
245 | } | |
246 | ||
247 | dns_resource_record_ref(rr); | |
248 | dns_resource_record_unref(i->rr); | |
249 | i->rr = rr; | |
250 | ||
251 | dns_resource_key_unref(i->key); | |
252 | i->key = dns_resource_key_ref(rr->key); | |
253 | ||
254 | i->until = timestamp + MIN(rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC); | |
255 | ||
256 | prioq_reshuffle(c->by_expiry, i, &i->prioq_idx); | |
257 | } | |
258 | ||
259 | static int dns_cache_put_positive(DnsCache *c, DnsResourceRecord *rr, usec_t timestamp) { | |
322345fd | 260 | _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL; |
7e8e0422 | 261 | DnsCacheItem *existing; |
322345fd LP |
262 | int r; |
263 | ||
264 | assert(c); | |
265 | assert(rr); | |
266 | ||
267 | /* New TTL is 0? Delete the entry... */ | |
268 | if (rr->ttl <= 0) { | |
faa133f3 | 269 | dns_cache_remove(c, rr->key); |
322345fd LP |
270 | return 0; |
271 | } | |
272 | ||
ddf16339 LP |
273 | if (rr->key->class == DNS_CLASS_ANY) |
274 | return 0; | |
275 | if (rr->key->type == DNS_TYPE_ANY) | |
276 | return 0; | |
277 | ||
322345fd LP |
278 | /* Entry exists already? Update TTL and timestamp */ |
279 | existing = dns_cache_get(c, rr); | |
280 | if (existing) { | |
7e8e0422 | 281 | dns_cache_item_update_positive(c, existing, rr, timestamp); |
322345fd LP |
282 | return 0; |
283 | } | |
284 | ||
285 | /* Otherwise, add the new RR */ | |
623a4c97 | 286 | r = dns_cache_init(c); |
322345fd LP |
287 | if (r < 0) |
288 | return r; | |
289 | ||
7e8e0422 LP |
290 | dns_cache_make_space(c, 1); |
291 | ||
292 | i = new0(DnsCacheItem, 1); | |
293 | if (!i) | |
294 | return -ENOMEM; | |
295 | ||
296 | i->type = DNS_CACHE_POSITIVE; | |
297 | i->key = dns_resource_key_ref(rr->key); | |
298 | i->rr = dns_resource_record_ref(rr); | |
299 | i->until = timestamp + MIN(i->rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC); | |
300 | i->prioq_idx = PRIOQ_IDX_NULL; | |
301 | ||
302 | r = dns_cache_link_item(c, i); | |
303 | if (r < 0) | |
304 | return r; | |
305 | ||
306 | i = NULL; | |
307 | return 0; | |
308 | } | |
309 | ||
310 | static int dns_cache_put_negative(DnsCache *c, DnsResourceKey *key, int rcode, usec_t timestamp, uint32_t soa_ttl) { | |
311 | _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL; | |
312 | int r; | |
313 | ||
314 | assert(c); | |
315 | assert(key); | |
316 | ||
317 | dns_cache_remove(c, key); | |
318 | ||
ddf16339 LP |
319 | if (key->class == DNS_CLASS_ANY) |
320 | return 0; | |
321 | if (key->type == DNS_TYPE_ANY) | |
322 | return 0; | |
323 | ||
7e8e0422 LP |
324 | if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN)) |
325 | return 0; | |
326 | ||
623a4c97 | 327 | r = dns_cache_init(c); |
322345fd LP |
328 | if (r < 0) |
329 | return r; | |
330 | ||
331 | dns_cache_make_space(c, 1); | |
332 | ||
333 | i = new0(DnsCacheItem, 1); | |
334 | if (!i) | |
335 | return -ENOMEM; | |
336 | ||
7e8e0422 LP |
337 | i->type = rcode == DNS_RCODE_SUCCESS ? DNS_CACHE_NODATA : DNS_CACHE_NXDOMAIN; |
338 | i->key = dns_resource_key_ref(key); | |
339 | i->until = timestamp + MIN(soa_ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC); | |
340 | i->prioq_idx = PRIOQ_IDX_NULL; | |
322345fd | 341 | |
7e8e0422 | 342 | r = dns_cache_link_item(c, i); |
322345fd LP |
343 | if (r < 0) |
344 | return r; | |
345 | ||
322345fd | 346 | i = NULL; |
322345fd LP |
347 | return 0; |
348 | } | |
349 | ||
d2f47562 | 350 | int dns_cache_put(DnsCache *c, DnsQuestion *q, int rcode, DnsAnswer *answer, unsigned max_rrs, usec_t timestamp) { |
7e8e0422 | 351 | unsigned i; |
322345fd LP |
352 | int r; |
353 | ||
354 | assert(c); | |
0ec7c46e | 355 | assert(q); |
322345fd | 356 | |
7e8e0422 LP |
357 | /* First, delete all matching old RRs, so that we only keep |
358 | * complete by_key in place. */ | |
359 | for (i = 0; i < q->n_keys; i++) | |
360 | dns_cache_remove(c, q->keys[i]); | |
0ec7c46e LP |
361 | |
362 | if (!answer) | |
363 | return 0; | |
364 | ||
faa133f3 LP |
365 | for (i = 0; i < answer->n_rrs; i++) |
366 | dns_cache_remove(c, answer->rrs[i]->key); | |
322345fd | 367 | |
7e8e0422 LP |
368 | /* We only care for positive replies and NXDOMAINs, on all |
369 | * other replies we will simply flush the respective entries, | |
370 | * and that's it */ | |
371 | ||
372 | if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN)) | |
373 | return 0; | |
374 | ||
375 | /* Make some space for our new entries */ | |
376 | dns_cache_make_space(c, answer->n_rrs + q->n_keys); | |
322345fd | 377 | |
7e8e0422 | 378 | if (timestamp <= 0) |
9a015429 | 379 | timestamp = now(CLOCK_BOOTTIME); |
322345fd | 380 | |
7e8e0422 | 381 | /* Second, add in positive entries for all contained RRs */ |
d2f47562 | 382 | for (i = 0; i < MIN(max_rrs, answer->n_rrs); i++) { |
7e8e0422 LP |
383 | r = dns_cache_put_positive(c, answer->rrs[i], timestamp); |
384 | if (r < 0) | |
385 | goto fail; | |
386 | } | |
387 | ||
388 | /* Third, add in negative entries for all keys with no RR */ | |
389 | for (i = 0; i < q->n_keys; i++) { | |
390 | DnsResourceRecord *soa = NULL; | |
391 | ||
392 | r = dns_answer_contains(answer, q->keys[i]); | |
393 | if (r < 0) | |
394 | goto fail; | |
395 | if (r > 0) | |
396 | continue; | |
397 | ||
398 | r = dns_answer_find_soa(answer, q->keys[i], &soa); | |
399 | if (r < 0) | |
400 | goto fail; | |
401 | if (r == 0) | |
402 | continue; | |
403 | ||
404 | r = dns_cache_put_negative(c, q->keys[i], rcode, timestamp, MIN(soa->soa.minimum, soa->ttl)); | |
322345fd LP |
405 | if (r < 0) |
406 | goto fail; | |
322345fd LP |
407 | } |
408 | ||
409 | return 0; | |
410 | ||
411 | fail: | |
412 | /* Adding all RRs failed. Let's clean up what we already | |
413 | * added, just in case */ | |
414 | ||
7e8e0422 LP |
415 | for (i = 0; i < q->n_keys; i++) |
416 | dns_cache_remove(c, q->keys[i]); | |
417 | for (i = 0; i < answer->n_rrs; i++) | |
faa133f3 | 418 | dns_cache_remove(c, answer->rrs[i]->key); |
322345fd LP |
419 | |
420 | return r; | |
421 | } | |
422 | ||
7e8e0422 | 423 | int dns_cache_lookup(DnsCache *c, DnsQuestion *q, int *rcode, DnsAnswer **ret) { |
faa133f3 LP |
424 | _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL; |
425 | unsigned i, n = 0; | |
322345fd | 426 | int r; |
7e8e0422 | 427 | bool nxdomain = false; |
322345fd LP |
428 | |
429 | assert(c); | |
faa133f3 | 430 | assert(q); |
623a4c97 | 431 | assert(rcode); |
faa133f3 | 432 | assert(ret); |
322345fd | 433 | |
faa133f3 LP |
434 | if (q->n_keys <= 0) { |
435 | *ret = NULL; | |
7e8e0422 | 436 | *rcode = 0; |
322345fd LP |
437 | return 0; |
438 | } | |
439 | ||
faa133f3 | 440 | for (i = 0; i < q->n_keys; i++) { |
322345fd LP |
441 | DnsCacheItem *j; |
442 | ||
ddf16339 LP |
443 | if (q->keys[i]->type == DNS_TYPE_ANY || |
444 | q->keys[i]->class == DNS_CLASS_ANY) { | |
445 | /* If we have ANY lookups we simply refresh */ | |
446 | *ret = NULL; | |
447 | *rcode = 0; | |
448 | return 0; | |
449 | } | |
450 | ||
7e8e0422 | 451 | j = hashmap_get(c->by_key, q->keys[i]); |
322345fd | 452 | if (!j) { |
faa133f3 LP |
453 | /* If one question cannot be answered we need to refresh */ |
454 | *ret = NULL; | |
7e8e0422 | 455 | *rcode = 0; |
faa133f3 | 456 | return 0; |
322345fd LP |
457 | } |
458 | ||
7e8e0422 LP |
459 | LIST_FOREACH(by_key, j, j) { |
460 | if (j->rr) | |
461 | n++; | |
462 | else if (j->type == DNS_CACHE_NXDOMAIN) | |
463 | nxdomain = true; | |
464 | } | |
faa133f3 LP |
465 | } |
466 | ||
7e8e0422 LP |
467 | if (n <= 0) { |
468 | *ret = NULL; | |
469 | *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS; | |
470 | return 1; | |
471 | } | |
faa133f3 LP |
472 | |
473 | answer = dns_answer_new(n); | |
474 | if (!answer) | |
475 | return -ENOMEM; | |
322345fd | 476 | |
faa133f3 LP |
477 | for (i = 0; i < q->n_keys; i++) { |
478 | DnsCacheItem *j; | |
322345fd | 479 | |
7e8e0422 LP |
480 | j = hashmap_get(c->by_key, q->keys[i]); |
481 | LIST_FOREACH(by_key, j, j) { | |
482 | if (j->rr) { | |
483 | r = dns_answer_add(answer, j->rr); | |
484 | if (r < 0) | |
485 | return r; | |
486 | } | |
322345fd LP |
487 | } |
488 | } | |
489 | ||
faa133f3 | 490 | *ret = answer; |
7e8e0422 | 491 | *rcode = DNS_RCODE_SUCCESS; |
faa133f3 LP |
492 | answer = NULL; |
493 | ||
494 | return n; | |
322345fd | 495 | } |