2 * services/cache/rrset.c - Resource record set cache.
4 * Copyright (c) 2007, NLnet Labs. All rights reserved.
6 * This software is open source.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
17 * and/or other materials provided with the distribution.
19 * Neither the name of the NLNET LABS nor the names of its contributors may
20 * be used to endorse or promote products derived from this software without
21 * specific prior written permission.
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 * This file contains the rrset cache.
42 #include "services/cache/rrset.h"
43 #include "sldns/rrdef.h"
44 #include "util/storage/slabhash.h"
45 #include "util/config_file.h"
46 #include "util/data/packed_rrset.h"
47 #include "util/data/msgreply.h"
48 #include "util/regional.h"
49 #include "util/alloc.h"
50 #include "util/net_help.h"
53 rrset_markdel(void* key)
55 struct ub_packed_rrset_key* r = (struct ub_packed_rrset_key*)key;
59 struct rrset_cache* rrset_cache_create(struct config_file* cfg,
60 struct alloc_cache* alloc)
62 size_t slabs = (cfg?cfg->rrset_cache_slabs:HASH_DEFAULT_SLABS);
63 size_t startarray = HASH_DEFAULT_STARTARRAY;
64 size_t maxmem = (cfg?cfg->rrset_cache_size:HASH_DEFAULT_MAXMEM);
66 struct rrset_cache *r = (struct rrset_cache*)slabhash_create(slabs,
67 startarray, maxmem, ub_rrset_sizefunc, ub_rrset_compare,
68 ub_rrset_key_delete, rrset_data_delete, alloc);
69 slabhash_setmarkdel(&r->table, &rrset_markdel);
73 void rrset_cache_delete(struct rrset_cache* r)
77 slabhash_delete(&r->table);
78 /* slabhash delete also does free(r), since table is first in struct*/
81 struct rrset_cache* rrset_cache_adjust(struct rrset_cache *r,
82 struct config_file* cfg, struct alloc_cache* alloc)
84 if(!r || !cfg || !slabhash_is_size(&r->table, cfg->rrset_cache_size,
85 cfg->rrset_cache_slabs))
87 rrset_cache_delete(r);
88 r = rrset_cache_create(cfg, alloc);
94 rrset_cache_touch(struct rrset_cache* r, struct ub_packed_rrset_key* key,
95 hashvalue_type hash, rrset_id_type id)
97 struct lruhash* table = slabhash_gettable(&r->table, hash);
99 * This leads to locking problems, deadlocks, if the caller is
100 * holding any other rrset lock.
101 * Because a lookup through the hashtable does:
102 * tablelock -> entrylock (for that entry caller holds)
104 * entrylock(already held) -> tablelock
105 * And if two threads do this, it results in deadlock.
106 * So, the caller must not hold entrylock.
108 lock_quick_lock(&table->lock);
109 /* we have locked the hash table, the item can still be deleted.
110 * because it could already have been reclaimed, but not yet set id=0.
111 * This is because some lruhash routines have lazy deletion.
112 * so, we must acquire a lock on the item to verify the id != 0.
113 * also, with hash not changed, we are using the right slab.
115 lock_rw_rdlock(&key->entry.lock);
116 if(key->id == id && key->entry.hash == hash) {
117 lru_touch(table, &key->entry);
119 lock_rw_unlock(&key->entry.lock);
120 lock_quick_unlock(&table->lock);
123 /** see if rrset needs to be updated in the cache */
125 need_to_update_rrset(void* nd, void* cd, time_t timenow, int equal, int ns)
127 struct packed_rrset_data* newd = (struct packed_rrset_data*)nd;
128 struct packed_rrset_data* cached = (struct packed_rrset_data*)cd;
129 /* o store if rrset has been validated
130 * everything better than bogus data
131 * secure is preferred */
132 if( newd->security == sec_status_secure &&
133 cached->security != sec_status_secure)
135 if( cached->security == sec_status_bogus &&
136 newd->security != sec_status_bogus && !equal)
138 /* o if current RRset is more trustworthy - insert it */
139 if( newd->trust > cached->trust ) {
140 /* if the cached rrset is bogus, and this one equal,
141 * do not update the TTL - let it expire. */
142 if(equal && cached->ttl >= timenow &&
143 cached->security == sec_status_bogus)
147 /* o item in cache has expired */
148 if( cached->ttl < timenow )
150 /* o same trust, but different in data - insert it */
151 if( newd->trust == cached->trust && !equal ) {
152 /* if this is type NS, do not 'stick' to owner that changes
153 * the NS RRset, but use the old TTL for the new data, and
154 * update to fetch the latest data. ttl is not expired, because
155 * that check was before this one. */
158 newd->ttl = cached->ttl;
159 for(i=0; i<(newd->count+newd->rrsig_count); i++)
160 if(newd->rr_ttl[i] > newd->ttl)
161 newd->rr_ttl[i] = newd->ttl;
168 /** Update RRSet special key ID */
170 rrset_update_id(struct rrset_ref* ref, struct alloc_cache* alloc)
172 /* this may clear the cache and invalidate lock below */
173 uint64_t newid = alloc_get_id(alloc);
174 /* obtain writelock */
175 lock_rw_wrlock(&ref->key->entry.lock);
176 /* check if it was deleted in the meantime, if so, skip update */
177 if(ref->key->id == ref->id) {
178 ref->key->id = newid;
181 lock_rw_unlock(&ref->key->entry.lock);
185 rrset_cache_update(struct rrset_cache* r, struct rrset_ref* ref,
186 struct alloc_cache* alloc, time_t timenow)
188 struct lruhash_entry* e;
189 struct ub_packed_rrset_key* k = ref->key;
190 hashvalue_type h = k->entry.hash;
191 uint16_t rrset_type = ntohs(k->rk.type);
193 log_assert(ref->id != 0 && k->id != 0);
194 log_assert(k->rk.dname != NULL);
195 /* looks up item with a readlock - no editing! */
196 if((e=slabhash_lookup(&r->table, h, k, 0)) != 0) {
197 /* return id and key as they will be used in the cache
198 * since the lruhash_insert, if item already exists, deallocs
199 * the passed key in favor of the already stored key.
200 * because of the small gap (see below) this key ptr and id
201 * may prove later to be already deleted, which is no problem
202 * as it only makes a cache miss.
204 ref->key = (struct ub_packed_rrset_key*)e->key;
205 ref->id = ref->key->id;
206 equal = rrsetdata_equal((struct packed_rrset_data*)k->entry.
207 data, (struct packed_rrset_data*)e->data);
208 if(!need_to_update_rrset(k->entry.data, e->data, timenow,
209 equal, (rrset_type==LDNS_RR_TYPE_NS))) {
210 /* cache is superior, return that value */
211 lock_rw_unlock(&e->lock);
212 ub_packed_rrset_parsedelete(k, alloc);
216 lock_rw_unlock(&e->lock);
217 /* Go on and insert the passed item.
218 * small gap here, where entry is not locked.
219 * possibly entry is updated with something else.
220 * we then overwrite that with our data.
221 * this is just too bad, its cache anyway. */
222 /* use insert to update entry to manage lruhash
223 * cache size values nicely. */
225 log_assert(ref->key->id != 0);
226 slabhash_insert(&r->table, h, &k->entry, k->entry.data, alloc);
228 /* For NSEC, NSEC3, DNAME, when rdata is updated, update
229 * the ID number so that proofs in message cache are
231 if((rrset_type == LDNS_RR_TYPE_NSEC
232 || rrset_type == LDNS_RR_TYPE_NSEC3
233 || rrset_type == LDNS_RR_TYPE_DNAME) && !equal) {
234 rrset_update_id(ref, alloc);
241 void rrset_cache_update_wildcard(struct rrset_cache* rrset_cache,
242 struct ub_packed_rrset_key* rrset, uint8_t* ce, size_t ce_len,
243 struct alloc_cache* alloc, time_t timenow)
245 struct rrset_ref ref;
246 uint8_t wc_dname[LDNS_MAX_DOMAINLEN+3];
247 rrset = packed_rrset_copy_alloc(rrset, alloc, timenow);
249 log_err("malloc failure in rrset_cache_update_wildcard");
252 /* ce has at least one label less then qname, we can therefore safely
253 * add the wildcard label. */
255 wc_dname[1] = (uint8_t)'*';
256 memmove(wc_dname+2, ce, ce_len);
258 free(rrset->rk.dname);
259 rrset->rk.dname_len = ce_len + 2;
260 rrset->rk.dname = (uint8_t*)memdup(wc_dname, rrset->rk.dname_len);
261 if(!rrset->rk.dname) {
262 alloc_special_release(alloc, rrset);
263 log_err("memdup failure in rrset_cache_update_wildcard");
267 rrset->entry.hash = rrset_key_hash(&rrset->rk);
270 /* ignore ret: if it was in the cache, ref updated */
271 (void)rrset_cache_update(rrset_cache, &ref, alloc, timenow);
274 struct ub_packed_rrset_key*
275 rrset_cache_lookup(struct rrset_cache* r, uint8_t* qname, size_t qnamelen,
276 uint16_t qtype, uint16_t qclass, uint32_t flags, time_t timenow,
279 struct lruhash_entry* e;
280 struct ub_packed_rrset_key key;
282 key.entry.key = &key;
283 key.entry.data = NULL;
284 key.rk.dname = qname;
285 key.rk.dname_len = qnamelen;
286 key.rk.type = htons(qtype);
287 key.rk.rrset_class = htons(qclass);
288 key.rk.flags = flags;
290 key.entry.hash = rrset_key_hash(&key.rk);
292 if((e = slabhash_lookup(&r->table, key.entry.hash, &key, wr))) {
294 struct packed_rrset_data* data =
295 (struct packed_rrset_data*)e->data;
296 if(timenow > data->ttl) {
297 lock_rw_unlock(&e->lock);
301 return (struct ub_packed_rrset_key*)e->key;
307 rrset_array_lock(struct rrset_ref* ref, size_t count, time_t timenow)
310 for(i=0; i<count; i++) {
311 if(i>0 && ref[i].key == ref[i-1].key)
312 continue; /* only lock items once */
313 lock_rw_rdlock(&ref[i].key->entry.lock);
314 if(ref[i].id != ref[i].key->id || timenow >
315 ((struct packed_rrset_data*)(ref[i].key->entry.data))
317 /* failure! rollback our readlocks */
318 rrset_array_unlock(ref, i+1);
326 rrset_array_unlock(struct rrset_ref* ref, size_t count)
329 for(i=0; i<count; i++) {
330 if(i>0 && ref[i].key == ref[i-1].key)
331 continue; /* only unlock items once */
332 lock_rw_unlock(&ref[i].key->entry.lock);
337 rrset_array_unlock_touch(struct rrset_cache* r, struct regional* scratch,
338 struct rrset_ref* ref, size_t count)
342 if(count > RR_COUNT_MAX || !(h = (hashvalue_type*)regional_alloc(
343 scratch, sizeof(hashvalue_type)*count))) {
344 log_warn("rrset LRU: memory allocation failed");
346 } else /* store hash values */
347 for(i=0; i<count; i++)
348 h[i] = ref[i].key->entry.hash;
350 for(i=0; i<count; i++) {
351 if(i>0 && ref[i].key == ref[i-1].key)
352 continue; /* only unlock items once */
353 lock_rw_unlock(&ref[i].key->entry.lock);
356 /* LRU touch, with no rrset locks held */
357 for(i=0; i<count; i++) {
358 if(i>0 && ref[i].key == ref[i-1].key)
359 continue; /* only touch items once */
360 rrset_cache_touch(r, ref[i].key, h[i], ref[i].id);
366 rrset_update_sec_status(struct rrset_cache* r,
367 struct ub_packed_rrset_key* rrset, time_t now)
369 struct packed_rrset_data* updata =
370 (struct packed_rrset_data*)rrset->entry.data;
371 struct lruhash_entry* e;
372 struct packed_rrset_data* cachedata;
374 /* hash it again to make sure it has a hash */
375 rrset->entry.hash = rrset_key_hash(&rrset->rk);
377 e = slabhash_lookup(&r->table, rrset->entry.hash, rrset, 1);
379 return; /* not in the cache anymore */
380 cachedata = (struct packed_rrset_data*)e->data;
381 if(!rrsetdata_equal(updata, cachedata)) {
382 lock_rw_unlock(&e->lock);
383 return; /* rrset has changed in the meantime */
385 /* update the cached rrset */
386 if(updata->security > cachedata->security) {
388 if(updata->trust > cachedata->trust)
389 cachedata->trust = updata->trust;
390 cachedata->security = updata->security;
391 /* for NS records only shorter TTLs, other types: update it */
392 if(ntohs(rrset->rk.type) != LDNS_RR_TYPE_NS ||
393 updata->ttl+now < cachedata->ttl ||
394 cachedata->ttl < now ||
395 updata->security == sec_status_bogus) {
396 cachedata->ttl = updata->ttl + now;
397 for(i=0; i<cachedata->count+cachedata->rrsig_count; i++)
398 cachedata->rr_ttl[i] = updata->rr_ttl[i]+now;
401 lock_rw_unlock(&e->lock);
405 rrset_check_sec_status(struct rrset_cache* r,
406 struct ub_packed_rrset_key* rrset, time_t now)
408 struct packed_rrset_data* updata =
409 (struct packed_rrset_data*)rrset->entry.data;
410 struct lruhash_entry* e;
411 struct packed_rrset_data* cachedata;
413 /* hash it again to make sure it has a hash */
414 rrset->entry.hash = rrset_key_hash(&rrset->rk);
416 e = slabhash_lookup(&r->table, rrset->entry.hash, rrset, 0);
418 return; /* not in the cache anymore */
419 cachedata = (struct packed_rrset_data*)e->data;
420 if(now > cachedata->ttl || !rrsetdata_equal(updata, cachedata)) {
421 lock_rw_unlock(&e->lock);
422 return; /* expired, or rrset has changed in the meantime */
424 if(cachedata->security > updata->security) {
425 updata->security = cachedata->security;
426 if(cachedata->security == sec_status_bogus) {
428 updata->ttl = cachedata->ttl - now;
429 for(i=0; i<cachedata->count+cachedata->rrsig_count; i++)
430 if(cachedata->rr_ttl[i] < now)
431 updata->rr_ttl[i] = 0;
432 else updata->rr_ttl[i] =
433 cachedata->rr_ttl[i]-now;
435 if(cachedata->trust > updata->trust)
436 updata->trust = cachedata->trust;
438 lock_rw_unlock(&e->lock);
441 void rrset_cache_remove(struct rrset_cache* r, uint8_t* nm, size_t nmlen,
442 uint16_t type, uint16_t dclass, uint32_t flags)
444 struct ub_packed_rrset_key key;
445 key.entry.key = &key;
447 key.rk.dname_len = nmlen;
448 key.rk.rrset_class = htons(dclass);
449 key.rk.type = htons(type);
450 key.rk.flags = flags;
451 key.entry.hash = rrset_key_hash(&key.rk);
452 slabhash_remove(&r->table, key.entry.hash, &key);