/*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/ /*** This file is part of systemd. Copyright 2014 Lennart Poettering systemd is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. systemd is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with systemd; If not, see <http://www.gnu.org/licenses/>. ***/ #include "resolved-dns-cache.h" #include "resolved-dns-packet.h" /* Never cache more than 1K entries */ #define CACHE_MAX 1024 /* We never keep any item longer than 10min in our cache */ #define CACHE_TTL_MAX_USEC (10 * USEC_PER_MINUTE) typedef enum DnsCacheItemType DnsCacheItemType; typedef struct DnsCacheItem DnsCacheItem; enum DnsCacheItemType { DNS_CACHE_POSITIVE, DNS_CACHE_NODATA, DNS_CACHE_NXDOMAIN, }; struct DnsCacheItem { DnsResourceKey *key; DnsResourceRecord *rr; usec_t until; DnsCacheItemType type; unsigned prioq_idx; int owner_family; union in_addr_union owner_address; LIST_FIELDS(DnsCacheItem, by_key); }; static void dns_cache_item_free(DnsCacheItem *i) { if (!i) return; dns_resource_record_unref(i->rr); dns_resource_key_unref(i->key); free(i); } DEFINE_TRIVIAL_CLEANUP_FUNC(DnsCacheItem*, dns_cache_item_free); static void dns_cache_item_remove_and_free(DnsCache *c, DnsCacheItem *i) { DnsCacheItem *first; assert(c); if (!i) return; first = hashmap_get(c->by_key, i->key); LIST_REMOVE(by_key, first, i); if (first) assert_se(hashmap_replace(c->by_key, first->key, first) >= 0); else hashmap_remove(c->by_key, i->key); prioq_remove(c->by_expiry, i, &i->prioq_idx); dns_cache_item_free(i); } void dns_cache_flush(DnsCache *c) { DnsCacheItem *i; assert(c); while ((i = hashmap_first(c->by_key))) dns_cache_item_remove_and_free(c, i); assert(hashmap_size(c->by_key) == 0); assert(prioq_size(c->by_expiry) == 0); hashmap_free(c->by_key); c->by_key = NULL; prioq_free(c->by_expiry); c->by_expiry = NULL; } static void dns_cache_remove(DnsCache *c, DnsResourceKey *key) { DnsCacheItem *i; assert(c); assert(key); while ((i = hashmap_get(c->by_key, key))) dns_cache_item_remove_and_free(c, i); } static void dns_cache_make_space(DnsCache *c, unsigned add) { assert(c); if (add <= 0) return; /* Makes space for n new entries. Note that we actually allow * the cache to grow beyond CACHE_MAX, but only when we shall * add more RRs to the cache than CACHE_MAX at once. In that * case the cache will be emptied completely otherwise. */ for (;;) { _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL; DnsCacheItem *i; if (prioq_size(c->by_expiry) <= 0) break; if (prioq_size(c->by_expiry) + add < CACHE_MAX) break; i = prioq_peek(c->by_expiry); assert(i); /* Take an extra reference to the key so that it * doesn't go away in the middle of the remove call */ key = dns_resource_key_ref(i->key); dns_cache_remove(c, key); } } void dns_cache_prune(DnsCache *c) { usec_t t = 0; assert(c); /* Remove all entries that are past their TTL */ for (;;) { _cleanup_(dns_resource_key_unrefp) DnsResourceKey *key = NULL; DnsCacheItem *i; i = prioq_peek(c->by_expiry); if (!i) break; if (t <= 0) t = now(CLOCK_BOOTTIME); if (i->until > t) break; /* Take an extra reference to the key so that it * doesn't go away in the middle of the remove call */ key = dns_resource_key_ref(i->key); dns_cache_remove(c, key); } } static int dns_cache_item_prioq_compare_func(const void *a, const void *b) { const DnsCacheItem *x = a, *y = b; if (x->until < y->until) return -1; if (x->until > y->until) return 1; return 0; } static int dns_cache_init(DnsCache *c) { int r; assert(c); r = prioq_ensure_allocated(&c->by_expiry, dns_cache_item_prioq_compare_func); if (r < 0) return r; r = hashmap_ensure_allocated(&c->by_key, &dns_resource_key_hash_ops); if (r < 0) return r; return r; } static int dns_cache_link_item(DnsCache *c, DnsCacheItem *i) { DnsCacheItem *first; int r; assert(c); assert(i); r = prioq_put(c->by_expiry, i, &i->prioq_idx); if (r < 0) return r; first = hashmap_get(c->by_key, i->key); if (first) { LIST_PREPEND(by_key, first, i); assert_se(hashmap_replace(c->by_key, first->key, first) >= 0); } else { r = hashmap_put(c->by_key, i->key, i); if (r < 0) { prioq_remove(c->by_expiry, i, &i->prioq_idx); return r; } } return 0; } static DnsCacheItem* dns_cache_get(DnsCache *c, DnsResourceRecord *rr) { DnsCacheItem *i; assert(c); assert(rr); LIST_FOREACH(by_key, i, hashmap_get(c->by_key, rr->key)) if (i->rr && dns_resource_record_equal(i->rr, rr) > 0) return i; return NULL; } static void dns_cache_item_update_positive(DnsCache *c, DnsCacheItem *i, DnsResourceRecord *rr, usec_t timestamp) { assert(c); assert(i); assert(rr); i->type = DNS_CACHE_POSITIVE; if (!i->by_key_prev) { /* We are the first item in the list, we need to * update the key used in the hashmap */ assert_se(hashmap_replace(c->by_key, rr->key, i) >= 0); } dns_resource_record_ref(rr); dns_resource_record_unref(i->rr); i->rr = rr; dns_resource_key_unref(i->key); i->key = dns_resource_key_ref(rr->key); i->until = timestamp + MIN(rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC); prioq_reshuffle(c->by_expiry, i, &i->prioq_idx); } static int dns_cache_put_positive( DnsCache *c, DnsResourceRecord *rr, usec_t timestamp, int owner_family, const union in_addr_union *owner_address) { _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL; DnsCacheItem *existing; int r; assert(c); assert(rr); assert(owner_address); /* New TTL is 0? Delete the entry... */ if (rr->ttl <= 0) { dns_cache_remove(c, rr->key); return 0; } if (rr->key->class == DNS_CLASS_ANY) return 0; if (rr->key->type == DNS_TYPE_ANY) return 0; /* Entry exists already? Update TTL and timestamp */ existing = dns_cache_get(c, rr); if (existing) { dns_cache_item_update_positive(c, existing, rr, timestamp); return 0; } /* Otherwise, add the new RR */ r = dns_cache_init(c); if (r < 0) return r; dns_cache_make_space(c, 1); i = new0(DnsCacheItem, 1); if (!i) return -ENOMEM; i->type = DNS_CACHE_POSITIVE; i->key = dns_resource_key_ref(rr->key); i->rr = dns_resource_record_ref(rr); i->until = timestamp + MIN(i->rr->ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC); i->prioq_idx = PRIOQ_IDX_NULL; i->owner_family = owner_family; i->owner_address = *owner_address; r = dns_cache_link_item(c, i); if (r < 0) return r; i = NULL; return 0; } static int dns_cache_put_negative( DnsCache *c, DnsResourceKey *key, int rcode, usec_t timestamp, uint32_t soa_ttl, int owner_family, const union in_addr_union *owner_address) { _cleanup_(dns_cache_item_freep) DnsCacheItem *i = NULL; int r; assert(c); assert(key); assert(owner_address); dns_cache_remove(c, key); if (key->class == DNS_CLASS_ANY) return 0; if (key->type == DNS_TYPE_ANY) return 0; if (soa_ttl <= 0) return 0; if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN)) return 0; r = dns_cache_init(c); if (r < 0) return r; dns_cache_make_space(c, 1); i = new0(DnsCacheItem, 1); if (!i) return -ENOMEM; i->type = rcode == DNS_RCODE_SUCCESS ? DNS_CACHE_NODATA : DNS_CACHE_NXDOMAIN; i->key = dns_resource_key_ref(key); i->until = timestamp + MIN(soa_ttl * USEC_PER_SEC, CACHE_TTL_MAX_USEC); i->prioq_idx = PRIOQ_IDX_NULL; i->owner_family = owner_family; i->owner_address = *owner_address; r = dns_cache_link_item(c, i); if (r < 0) return r; i = NULL; return 0; } int dns_cache_put( DnsCache *c, DnsQuestion *q, int rcode, DnsAnswer *answer, unsigned max_rrs, usec_t timestamp, int owner_family, const union in_addr_union *owner_address) { unsigned i; int r; assert(c); assert(q); /* First, delete all matching old RRs, so that we only keep * complete by_key in place. */ for (i = 0; i < q->n_keys; i++) dns_cache_remove(c, q->keys[i]); if (!answer) return 0; for (i = 0; i < answer->n_rrs; i++) dns_cache_remove(c, answer->rrs[i]->key); /* We only care for positive replies and NXDOMAINs, on all * other replies we will simply flush the respective entries, * and that's it */ if (!IN_SET(rcode, DNS_RCODE_SUCCESS, DNS_RCODE_NXDOMAIN)) return 0; /* Make some space for our new entries */ dns_cache_make_space(c, answer->n_rrs + q->n_keys); if (timestamp <= 0) timestamp = now(CLOCK_BOOTTIME); /* Second, add in positive entries for all contained RRs */ for (i = 0; i < MIN(max_rrs, answer->n_rrs); i++) { r = dns_cache_put_positive(c, answer->rrs[i], timestamp, owner_family, owner_address); if (r < 0) goto fail; } /* Third, add in negative entries for all keys with no RR */ for (i = 0; i < q->n_keys; i++) { DnsResourceRecord *soa = NULL; r = dns_answer_contains(answer, q->keys[i]); if (r < 0) goto fail; if (r > 0) continue; r = dns_answer_find_soa(answer, q->keys[i], &soa); if (r < 0) goto fail; if (r == 0) continue; r = dns_cache_put_negative(c, q->keys[i], rcode, timestamp, MIN(soa->soa.minimum, soa->ttl), owner_family, owner_address); if (r < 0) goto fail; } return 0; fail: /* Adding all RRs failed. Let's clean up what we already * added, just in case */ for (i = 0; i < q->n_keys; i++) dns_cache_remove(c, q->keys[i]); for (i = 0; i < answer->n_rrs; i++) dns_cache_remove(c, answer->rrs[i]->key); return r; } int dns_cache_lookup(DnsCache *c, DnsQuestion *q, int *rcode, DnsAnswer **ret) { _cleanup_(dns_answer_unrefp) DnsAnswer *answer = NULL; unsigned i, n = 0; int r; bool nxdomain = false; assert(c); assert(q); assert(rcode); assert(ret); if (q->n_keys <= 0) { *ret = NULL; *rcode = 0; return 0; } for (i = 0; i < q->n_keys; i++) { DnsCacheItem *j; if (q->keys[i]->type == DNS_TYPE_ANY || q->keys[i]->class == DNS_CLASS_ANY) { /* If we have ANY lookups we simply refresh */ *ret = NULL; *rcode = 0; return 0; } j = hashmap_get(c->by_key, q->keys[i]); if (!j) { /* If one question cannot be answered we need to refresh */ *ret = NULL; *rcode = 0; return 0; } LIST_FOREACH(by_key, j, j) { if (j->rr) n++; else if (j->type == DNS_CACHE_NXDOMAIN) nxdomain = true; } } if (n <= 0) { *ret = NULL; *rcode = nxdomain ? DNS_RCODE_NXDOMAIN : DNS_RCODE_SUCCESS; return 1; } answer = dns_answer_new(n); if (!answer) return -ENOMEM; for (i = 0; i < q->n_keys; i++) { DnsCacheItem *j; j = hashmap_get(c->by_key, q->keys[i]); LIST_FOREACH(by_key, j, j) { if (j->rr) { r = dns_answer_add(answer, j->rr); if (r < 0) return r; } } } *ret = answer; *rcode = DNS_RCODE_SUCCESS; answer = NULL; return n; } int dns_cache_check_conflicts(DnsCache *cache, DnsResourceRecord *rr, int owner_family, const union in_addr_union *owner_address) { DnsCacheItem *i, *first; bool same_owner = true; assert(cache); assert(rr); dns_cache_prune(cache); /* See if there's a cache entry for the same key. If there * isn't there's no conflict */ first = hashmap_get(cache->by_key, rr->key); if (!first) return 0; /* See if the RR key is owned by the same owner, if so, there * isn't a conflict either */ LIST_FOREACH(by_key, i, first) { if (i->owner_family != owner_family || !in_addr_equal(owner_family, &i->owner_address, owner_address)) { same_owner = false; break; } } if (same_owner) return 0; /* See if there's the exact same RR in the cache. If yes, then * there's no conflict. */ if (dns_cache_get(cache, rr)) return 0; /* There's a conflict */ return 1; }