chiark / gitweb /
resolved: DNSKEY records
[elogind.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         LIST_FIELDS(DnsCacheItem, by_key);
47 };
48
49 static void dns_cache_item_free(DnsCacheItem *i) {
50         if (!i)
51                 return;
52
53         dns_resource_record_unref(i->rr);
54         dns_resource_key_unref(i->key);
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
68         first = hashmap_get(c->by_key, i->key);
69         LIST_REMOVE(by_key, first, i);
70
71         if (first)
72                 assert_se(hashmap_replace(c->by_key, first->key, first) >= 0);
73         else
74                 hashmap_remove(c->by_key, i->key);
75
76         prioq_remove(c->by_expiry, i, &i->prioq_idx);
77
78         dns_cache_item_free(i);
79 }
80
81 void dns_cache_flush(DnsCache *c) {
82         DnsCacheItem *i;
83
84         assert(c);
85
86         while ((i = hashmap_first(c->by_key)))
87                 dns_cache_item_remove_and_free(c, i);
88
89         assert(hashmap_size(c->by_key) == 0);
90         assert(prioq_size(c->by_expiry) == 0);
91
92         hashmap_free(c->by_key);
93         c->by_key = NULL;
94
95         prioq_free(c->by_expiry);
96         c->by_expiry = NULL;
97 }
98
99 static void dns_cache_remove(DnsCache *c, DnsResourceKey *key) {
100         DnsCacheItem *i;
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 }
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 (;;) {
121                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
122                 DnsCacheItem *i;
123
124                 if (prioq_size(c->by_expiry) <= 0)
125                         break;
126
127                 if (prioq_size(c->by_expiry) + add < CACHE_MAX)
128                         break;
129
130                 i = prioq_peek(c->by_expiry);
131                 assert(i);
132
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);
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 (;;) {
148                 _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL;
149                 DnsCacheItem *i;
150
151                 i = prioq_peek(c->by_expiry);
152                 if (!i)
153                         break;
154
155                 if (t <= 0)
156                         t = now(CLOCK_BOOTTIME);
157
158                 if (i->until > t)
159                         break;
160
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);
165         }
166 }
167
168 static int dns_cache_item_prioq_compare_func(const void *a, const void *b) {
169         const DnsCacheItem *x = a, *y = b;
170
171         if (x->until < y->until)
172                 return -1;
173         if (x->until > y->until)
174                 return 1;
175         return 0;
176 }
177
178 static int dns_cache_init(DnsCache *c) {
179         int r;
180
181         assert(c);
182
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
198         assert(c);
199         assert(i);
200
201         r = prioq_put(c->by_expiry, i, &i->prioq_idx);
202         if (r < 0)
203                 return r;
204
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                 }
215         }
216
217         return 0;
218 }
219
220 static DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) {
221         DnsCacheItem *i;
222
223         assert(c);
224         assert(rr);
225
226         LIST_FOREACH(by_key, i, hashmap_get(c->by_key, rr->key))
227                 if (i->rr && dns_resource_record_equal(i->rr, rr))
228                         return i;
229
230         return NULL;
231 }
232
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) {
260         _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL;
261         DnsCacheItem *existing;
262         int r;
263
264         assert(c);
265         assert(rr);
266
267         /* New TTL is 0? Delete the entry... */
268         if (rr->ttl <= 0) {
269                 dns_cache_remove(c, rr->key);
270                 return 0;
271         }
272
273         if (rr->key->class == DNS_CLASS_ANY)
274                 return 0;
275         if (rr->key->type == DNS_TYPE_ANY)
276                 return 0;
277
278         /* Entry exists already? Update TTL and timestamp */
279         existing = dns_cache_get(c, rr);
280         if (existing) {
281                 dns_cache_item_update_positive(c, existing, rr, timestamp);
282                 return 0;
283         }
284
285         /* Otherwise, add the new RR */
286         r = dns_cache_init(c);
287         if (r < 0)
288                 return r;
289
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
319         if (key->class == DNS_CLASS_ANY)
320                 return 0;
321         if (key->type == DNS_TYPE_ANY)
322                 return 0;
323         if (soa_ttl <= 0)
324                 return 0;
325
326         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
327                 return 0;
328
329         r = dns_cache_init(c);
330         if (r < 0)
331                 return r;
332
333         dns_cache_make_space(c, 1);
334
335         i = new0(DnsCacheItem, 1);
336         if (!i)
337                 return -ENOMEM;
338
339         i->type = rcode == DNS_RCODE_SUCCESS ? DNS_CACHE_NODATA : DNS_CACHE_NXDOMAIN;
340         i->key = dns_resource_key_ref(key);
341         i->until = timestamp + MIN(soa_ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC);
342         i->prioq_idx = PRIOQ_IDX_NULL;
343
344         r = dns_cache_link_item(c, i);
345         if (r < 0)
346                 return r;
347
348         i = NULL;
349         return 0;
350 }
351
352 int dns_cache_put(DnsCache *c, DnsQuestion *q, int rcode, DnsAnswer *answer, unsigned max_rrs, usec_t timestamp) {
353         unsigned i;
354         int r;
355
356         assert(c);
357         assert(q);
358
359         /* First, delete all matching old RRs, so that we only keep
360          * complete by_key in place. */
361         for (i = 0; i < q->n_keys; i++)
362                 dns_cache_remove(c, q->keys[i]);
363
364         if (!answer)
365                 return 0;
366
367         for (i = 0; i < answer->n_rrs; i++)
368                 dns_cache_remove(c, answer->rrs[i]->key);
369
370         /* We only care for positive replies and NXDOMAINs, on all
371          * other replies we will simply flush the respective entries,
372          * and that's it */
373
374         if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN))
375                 return 0;
376
377         /* Make some space for our new entries */
378         dns_cache_make_space(c, answer->n_rrs + q->n_keys);
379
380         if (timestamp <= 0)
381                 timestamp = now(CLOCK_BOOTTIME);
382
383         /* Second, add in positive entries for all contained RRs */
384         for (i = 0; i < MIN(max_rrs, answer->n_rrs); i++) {
385                 r = dns_cache_put_positive(c, answer->rrs[i], timestamp);
386                 if (r < 0)
387                         goto fail;
388         }
389
390         /* Third, add in negative entries for all keys with no RR */
391         for (i = 0; i < q->n_keys; i++) {
392                 DnsResourceRecord *soa = NULL;
393
394                 r = dns_answer_contains(answer, q->keys[i]);
395                 if (r < 0)
396                         goto fail;
397                 if (r > 0)
398                         continue;
399
400                 r = dns_answer_find_soa(answer, q->keys[i], &soa);
401                 if (r < 0)
402                         goto fail;
403                 if (r == 0)
404                         continue;
405
406                 r = dns_cache_put_negative(c, q->keys[i], rcode, timestamp, MIN(soa->soa.minimum, soa->ttl));
407                 if (r < 0)
408                         goto fail;
409         }
410
411         return 0;
412
413 fail:
414         /* Adding all RRs failed. Let's clean up what we already
415          * added, just in case */
416
417         for (i = 0; i < q->n_keys; i++)
418                 dns_cache_remove(c, q->keys[i]);
419         for (i = 0; i < answer->n_rrs; i++)
420                 dns_cache_remove(c, answer->rrs[i]->key);
421
422         return r;
423 }
424
425 int dns_cache_lookup(DnsCache *c, DnsQuestion *q, int *rcode, DnsAnswer **ret) {
426         _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL;
427         unsigned i, n = 0;
428         int r;
429         bool nxdomain = false;
430
431         assert(c);
432         assert(q);
433         assert(rcode);
434         assert(ret);
435
436         if (q->n_keys <= 0) {
437                 *ret = NULL;
438                 *rcode = 0;
439                 return 0;
440         }
441
442         for (i = 0; i < q->n_keys; i++) {
443                 DnsCacheItem *j;
444
445                 if (q->keys[i]->type == DNS_TYPE_ANY ||
446                     q->keys[i]->class == DNS_CLASS_ANY) {
447                         /* If we have ANY lookups we simply refresh */
448                         *ret = NULL;
449                         *rcode = 0;
450                         return 0;
451                 }
452
453                 j = hashmap_get(c->by_key, q->keys[i]);
454                 if (!j) {
455                         /* If one question cannot be answered we need to refresh */
456                         *ret = NULL;
457                         *rcode = 0;
458                         return 0;
459                 }
460
461                 LIST_FOREACH(by_key, j, j) {
462                         if (j->rr)
463                                 n++;
464                         else if (j->type == DNS_CACHE_NXDOMAIN)
465                                 nxdomain = true;
466                 }
467         }
468
469         if (n <= 0) {
470                 *ret = NULL;
471                 *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS;
472                 return 1;
473         }
474
475         answer = dns_answer_new(n);
476         if (!answer)
477                 return -ENOMEM;
478
479         for (i = 0; i < q->n_keys; i++) {
480                 DnsCacheItem *j;
481
482                 j = hashmap_get(c->by_key, q->keys[i]);
483                 LIST_FOREACH(by_key, j, j) {
484                         if (j->rr) {
485                                 r = dns_answer_add(answer, j->rr);
486                                 if (r < 0)
487                                         return r;
488                         }
489                 }
490         }
491
492         *ret = answer;
493         *rcode = DNS_RCODE_SUCCESS;
494         answer = NULL;
495
496         return n;
497 }