1/*
2 * validator/val_neg.h - validator aggressive negative caching functions.
3 *
4 * Copyright (c) 2008, NLnet Labs. All rights reserved.
5 *
6 * This software is open source.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
14 *
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.
18 *
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.
22 *
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.
34 */
35
36/**
37 * \file
38 *
39 * This file contains helper functions for the validator module.
40 * The functions help with aggressive negative caching.
41 * This creates new denials of existence, and proofs for absence of types
42 * from cached NSEC records.
43 */
44
45#ifndef VALIDATOR_VAL_NEG_H
46#define VALIDATOR_VAL_NEG_H
47#include "util/locks.h"
48#include "util/rbtree.h"
49struct sldns_buffer;
50struct val_neg_data;
51struct config_file;
52struct reply_info;
53struct rrset_cache;
54struct regional;
55struct query_info;
56struct dns_msg;
57struct ub_packed_rrset_key;
58
59/**
60 * The negative cache. It is shared between the threads, so locked.
61 * Kept as validator-environ-state. It refers back to the rrset cache for
62 * data elements. It can be out of date and contain conflicting data
63 * from zone content changes.
64 * It contains a tree of zones, every zone has a tree of data elements.
65 * The data elements are part of one big LRU list, with one memory counter.
66 */
67struct val_neg_cache {
68 /** the big lock on the negative cache. Because we use a rbtree
69 * for the data (quick lookup), we need a big lock */
70 lock_basic_t lock;
71 /** The zone rbtree. contents sorted canonical, type val_neg_zone */
72 rbtree_t tree;
73 /** the first in linked list of LRU of val_neg_data */
74 struct val_neg_data* first;
75 /** last in lru (least recently used element) */
76 struct val_neg_data* last;
77 /** current memory in use (bytes) */
78 size_t use;
79 /** max memory to use (bytes) */
80 size_t max;
81 /** max nsec3 iterations allowed */
82 size_t nsec3_max_iter;
83};
84
85/**
86 * Per Zone aggressive negative caching data.
87 */
88struct val_neg_zone {
89 /** rbtree node element, key is this struct: the name, class */
90 rbnode_t node;
91 /** name; the key */
92 uint8_t* name;
93 /** length of name */
94 size_t len;
95 /** labels in name */
96 int labs;
97
98 /** pointer to parent zone in the negative cache */
99 struct val_neg_zone* parent;
100
101 /** the number of elements, including this one and the ones whose
102 * parents (-parents) include this one, that are in_use
103 * No elements have a count of zero, those are removed. */
104 int count;
105
106 /** if 0: NSEC zone, else NSEC3 hash algorithm in use */
107 int nsec3_hash;
108 /** nsec3 iteration count in use */
109 size_t nsec3_iter;
110 /** nsec3 salt in use */
111 uint8_t* nsec3_salt;
112 /** length of salt in bytes */
113 size_t nsec3_saltlen;
114
115 /** tree of NSEC data for this zone, sorted canonical
116 * by NSEC owner name */
117 rbtree_t tree;
118
119 /** class of node; host order */
120 uint16_t dclass;
121 /** if this element is in use, boolean */
122 uint8_t in_use;
123};
124
125/**
126 * Data element for aggressive negative caching.
127 * The tree of these elements acts as an index onto the rrset cache.
128 * It shows the NSEC records that (may) exist and are (possibly) secure.
129 * The rbtree allows for logN search for a covering NSEC record.
130 * To make tree insertion and deletion logN too, all the parent (one label
131 * less than the name) data elements are also in the rbtree, with a usage
132 * count for every data element.
133 * There is no actual data stored in this data element, if it is in_use,
134 * then the data can (possibly) be found in the rrset cache.
135 */
136struct val_neg_data {
137 /** rbtree node element, key is this struct: the name */
138 rbnode_t node;
139 /** name; the key */
140 uint8_t* name;
141 /** length of name */
142 size_t len;
143 /** labels in name */
144 int labs;
145
146 /** pointer to parent node in the negative cache */
147 struct val_neg_data* parent;
148
149 /** the number of elements, including this one and the ones whose
150 * parents (-parents) include this one, that are in use
151 * No elements have a count of zero, those are removed. */
152 int count;
153
154 /** the zone that this denial is part of */
155 struct val_neg_zone* zone;
156
157 /** previous in LRU */
158 struct val_neg_data* prev;
159 /** next in LRU (next element was less recently used) */
160 struct val_neg_data* next;
161
162 /** if this element is in use, boolean */
163 uint8_t in_use;
164};
165
166/**
167 * Create negative cache
168 * @param cfg: config options.
169 * @param maxiter: max nsec3 iterations allowed.
170 * @return neg cache, empty or NULL on failure.
171 */
172struct val_neg_cache* val_neg_create(struct config_file* cfg, size_t maxiter);
173
174/**
175 * see how much memory is in use by the negative cache.
176 * @param neg: negative cache
177 * @return number of bytes in use.
178 */
179size_t val_neg_get_mem(struct val_neg_cache* neg);
180
181/**
182 * Destroy negative cache. There must no longer be any other threads.
183 * @param neg: negative cache.
184 */
185void neg_cache_delete(struct val_neg_cache* neg);
186
187/**
188 * Comparison function for rbtree val neg data elements
189 */
190int val_neg_data_compare(const void* a, const void* b);
191
192/**
193 * Comparison function for rbtree val neg zone elements
194 */
195int val_neg_zone_compare(const void* a, const void* b);
196
197/**
198 * Insert NSECs from this message into the negative cache for reference.
199 * @param neg: negative cache
200 * @param rep: reply with NSECs.
201 * Errors are ignored, means that storage is omitted.
202 */
203void val_neg_addreply(struct val_neg_cache* neg, struct reply_info* rep);
204
205/**
206 * Insert NSECs from this referral into the negative cache for reference.
207 * @param neg: negative cache
208 * @param rep: referral reply with NS, NSECs.
209 * @param zone: bailiwick for the referral.
210 * Errors are ignored, means that storage is omitted.
211 */
212void val_neg_addreferral(struct val_neg_cache* neg, struct reply_info* rep,
213 uint8_t* zone);
214
215/**
216 * Perform a DLV style lookup
217 * During the lookup, we could find out that data has expired. In that
218 * case the neg_cache entries are removed, and lookup fails.
219 *
220 * @param neg: negative cache.
221 * @param qname: name to look for
222 * @param len: length of qname.
223 * @param qclass: class to look in.
224 * @param rrset_cache: the rrset cache, for NSEC lookups.
225 * @param now: current time for ttl checks.
226 * @return
227 * 0 on error
228 * 0 if no proof of negative
229 * 1 if indeed negative was proven
230 * thus, qname DLV qclass does not exist.
231 */
232int val_neg_dlvlookup(struct val_neg_cache* neg, uint8_t* qname, size_t len,
233 uint16_t qclass, struct rrset_cache* rrset_cache, time_t now);
234
235/**
236 * For the given query, try to get a reply out of the negative cache.
237 * The reply still needs to be validated.
238 * @param neg: negative cache.
239 * @param qinfo: query
240 * @param region: where to allocate reply.
241 * @param rrset_cache: rrset cache.
242 * @param buf: temporary buffer.
243 * @param now: to check TTLs against.
244 * @param addsoa: if true, produce result for external consumption.
245 * if false, do not add SOA - for unbound-internal consumption.
246 * @param topname: do not look higher than this name,
247 * so that the result cannot be taken from a zone above the current
248 * trust anchor. Which could happen with multiple islands of trust.
249 * if NULL, then no trust anchor is used, but also the algorithm becomes
250 * more conservative, especially for opt-out zones, since the receiver
251 * may have a trust-anchor below the optout and thus the optout cannot
252 * be used to create a proof from the negative cache.
253 * @return a reply message if something was found.
254 * This reply may still need validation.
255 * NULL if nothing found (or out of memory).
256 */
257struct dns_msg* val_neg_getmsg(struct val_neg_cache* neg,
258 struct query_info* qinfo, struct regional* region,
259 struct rrset_cache* rrset_cache, struct sldns_buffer* buf, time_t now,
260 int addsoa, uint8_t* topname);
261
262
263/**** functions exposed for unit test ****/
264/**
265 * Insert data into the data tree of a zone
266 * Does not do locking.
267 * @param neg: negative cache
268 * @param zone: zone to insert into
269 * @param nsec: record to insert.
270 */
271void neg_insert_data(struct val_neg_cache* neg,
272 struct val_neg_zone* zone, struct ub_packed_rrset_key* nsec);
273
274/**
275 * Delete a data element from the negative cache.
276 * May delete other data elements to keep tree coherent, or
277 * only mark the element as 'not in use'.
278 * Does not do locking.
279 * @param neg: negative cache.
280 * @param el: data element to delete.
281 */
282void neg_delete_data(struct val_neg_cache* neg, struct val_neg_data* el);
283
284/**
285 * Find the given zone, from the SOA owner name and class
286 * Does not do locking.
287 * @param neg: negative cache
288 * @param nm: what to look for.
289 * @param len: length of nm
290 * @param dclass: class to look for.
291 * @return zone or NULL if not found.
292 */
293struct val_neg_zone* neg_find_zone(struct val_neg_cache* neg,
294 uint8_t* nm, size_t len, uint16_t dclass);
295
296/**
297 * Create a new zone.
298 * Does not do locking.
299 * @param neg: negative cache
300 * @param nm: what to look for.
301 * @param nm_len: length of name.
302 * @param dclass: class of zone, host order.
303 * @return zone or NULL if out of memory.
304 */
305struct val_neg_zone* neg_create_zone(struct val_neg_cache* neg,
306 uint8_t* nm, size_t nm_len, uint16_t dclass);
307
308/**
309 * take a zone into use. increases counts of parents.
310 * Does not do locking.
311 * @param zone: zone to take into use.
312 */
313void val_neg_zone_take_inuse(struct val_neg_zone* zone);
314
315#endif /* VALIDATOR_VAL_NEG_H */
2 * validator/val_neg.h - validator aggressive negative caching functions.
3 *
4 * Copyright (c) 2008, NLnet Labs. All rights reserved.
5 *
6 * This software is open source.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
14 *
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.
18 *
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.
22 *
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.
34 */
35
36/**
37 * \file
38 *
39 * This file contains helper functions for the validator module.
40 * The functions help with aggressive negative caching.
41 * This creates new denials of existence, and proofs for absence of types
42 * from cached NSEC records.
43 */
44
45#ifndef VALIDATOR_VAL_NEG_H
46#define VALIDATOR_VAL_NEG_H
47#include "util/locks.h"
48#include "util/rbtree.h"
49struct sldns_buffer;
50struct val_neg_data;
51struct config_file;
52struct reply_info;
53struct rrset_cache;
54struct regional;
55struct query_info;
56struct dns_msg;
57struct ub_packed_rrset_key;
58
59/**
60 * The negative cache. It is shared between the threads, so locked.
61 * Kept as validator-environ-state. It refers back to the rrset cache for
62 * data elements. It can be out of date and contain conflicting data
63 * from zone content changes.
64 * It contains a tree of zones, every zone has a tree of data elements.
65 * The data elements are part of one big LRU list, with one memory counter.
66 */
67struct val_neg_cache {
68 /** the big lock on the negative cache. Because we use a rbtree
69 * for the data (quick lookup), we need a big lock */
70 lock_basic_t lock;
71 /** The zone rbtree. contents sorted canonical, type val_neg_zone */
72 rbtree_t tree;
73 /** the first in linked list of LRU of val_neg_data */
74 struct val_neg_data* first;
75 /** last in lru (least recently used element) */
76 struct val_neg_data* last;
77 /** current memory in use (bytes) */
78 size_t use;
79 /** max memory to use (bytes) */
80 size_t max;
81 /** max nsec3 iterations allowed */
82 size_t nsec3_max_iter;
83};
84
85/**
86 * Per Zone aggressive negative caching data.
87 */
88struct val_neg_zone {
89 /** rbtree node element, key is this struct: the name, class */
90 rbnode_t node;
91 /** name; the key */
92 uint8_t* name;
93 /** length of name */
94 size_t len;
95 /** labels in name */
96 int labs;
97
98 /** pointer to parent zone in the negative cache */
99 struct val_neg_zone* parent;
100
101 /** the number of elements, including this one and the ones whose
102 * parents (-parents) include this one, that are in_use
103 * No elements have a count of zero, those are removed. */
104 int count;
105
106 /** if 0: NSEC zone, else NSEC3 hash algorithm in use */
107 int nsec3_hash;
108 /** nsec3 iteration count in use */
109 size_t nsec3_iter;
110 /** nsec3 salt in use */
111 uint8_t* nsec3_salt;
112 /** length of salt in bytes */
113 size_t nsec3_saltlen;
114
115 /** tree of NSEC data for this zone, sorted canonical
116 * by NSEC owner name */
117 rbtree_t tree;
118
119 /** class of node; host order */
120 uint16_t dclass;
121 /** if this element is in use, boolean */
122 uint8_t in_use;
123};
124
125/**
126 * Data element for aggressive negative caching.
127 * The tree of these elements acts as an index onto the rrset cache.
128 * It shows the NSEC records that (may) exist and are (possibly) secure.
129 * The rbtree allows for logN search for a covering NSEC record.
130 * To make tree insertion and deletion logN too, all the parent (one label
131 * less than the name) data elements are also in the rbtree, with a usage
132 * count for every data element.
133 * There is no actual data stored in this data element, if it is in_use,
134 * then the data can (possibly) be found in the rrset cache.
135 */
136struct val_neg_data {
137 /** rbtree node element, key is this struct: the name */
138 rbnode_t node;
139 /** name; the key */
140 uint8_t* name;
141 /** length of name */
142 size_t len;
143 /** labels in name */
144 int labs;
145
146 /** pointer to parent node in the negative cache */
147 struct val_neg_data* parent;
148
149 /** the number of elements, including this one and the ones whose
150 * parents (-parents) include this one, that are in use
151 * No elements have a count of zero, those are removed. */
152 int count;
153
154 /** the zone that this denial is part of */
155 struct val_neg_zone* zone;
156
157 /** previous in LRU */
158 struct val_neg_data* prev;
159 /** next in LRU (next element was less recently used) */
160 struct val_neg_data* next;
161
162 /** if this element is in use, boolean */
163 uint8_t in_use;
164};
165
166/**
167 * Create negative cache
168 * @param cfg: config options.
169 * @param maxiter: max nsec3 iterations allowed.
170 * @return neg cache, empty or NULL on failure.
171 */
172struct val_neg_cache* val_neg_create(struct config_file* cfg, size_t maxiter);
173
174/**
175 * see how much memory is in use by the negative cache.
176 * @param neg: negative cache
177 * @return number of bytes in use.
178 */
179size_t val_neg_get_mem(struct val_neg_cache* neg);
180
181/**
182 * Destroy negative cache. There must no longer be any other threads.
183 * @param neg: negative cache.
184 */
185void neg_cache_delete(struct val_neg_cache* neg);
186
187/**
188 * Comparison function for rbtree val neg data elements
189 */
190int val_neg_data_compare(const void* a, const void* b);
191
192/**
193 * Comparison function for rbtree val neg zone elements
194 */
195int val_neg_zone_compare(const void* a, const void* b);
196
197/**
198 * Insert NSECs from this message into the negative cache for reference.
199 * @param neg: negative cache
200 * @param rep: reply with NSECs.
201 * Errors are ignored, means that storage is omitted.
202 */
203void val_neg_addreply(struct val_neg_cache* neg, struct reply_info* rep);
204
205/**
206 * Insert NSECs from this referral into the negative cache for reference.
207 * @param neg: negative cache
208 * @param rep: referral reply with NS, NSECs.
209 * @param zone: bailiwick for the referral.
210 * Errors are ignored, means that storage is omitted.
211 */
212void val_neg_addreferral(struct val_neg_cache* neg, struct reply_info* rep,
213 uint8_t* zone);
214
215/**
216 * Perform a DLV style lookup
217 * During the lookup, we could find out that data has expired. In that
218 * case the neg_cache entries are removed, and lookup fails.
219 *
220 * @param neg: negative cache.
221 * @param qname: name to look for
222 * @param len: length of qname.
223 * @param qclass: class to look in.
224 * @param rrset_cache: the rrset cache, for NSEC lookups.
225 * @param now: current time for ttl checks.
226 * @return
227 * 0 on error
228 * 0 if no proof of negative
229 * 1 if indeed negative was proven
230 * thus, qname DLV qclass does not exist.
231 */
232int val_neg_dlvlookup(struct val_neg_cache* neg, uint8_t* qname, size_t len,
233 uint16_t qclass, struct rrset_cache* rrset_cache, time_t now);
234
235/**
236 * For the given query, try to get a reply out of the negative cache.
237 * The reply still needs to be validated.
238 * @param neg: negative cache.
239 * @param qinfo: query
240 * @param region: where to allocate reply.
241 * @param rrset_cache: rrset cache.
242 * @param buf: temporary buffer.
243 * @param now: to check TTLs against.
244 * @param addsoa: if true, produce result for external consumption.
245 * if false, do not add SOA - for unbound-internal consumption.
246 * @param topname: do not look higher than this name,
247 * so that the result cannot be taken from a zone above the current
248 * trust anchor. Which could happen with multiple islands of trust.
249 * if NULL, then no trust anchor is used, but also the algorithm becomes
250 * more conservative, especially for opt-out zones, since the receiver
251 * may have a trust-anchor below the optout and thus the optout cannot
252 * be used to create a proof from the negative cache.
253 * @return a reply message if something was found.
254 * This reply may still need validation.
255 * NULL if nothing found (or out of memory).
256 */
257struct dns_msg* val_neg_getmsg(struct val_neg_cache* neg,
258 struct query_info* qinfo, struct regional* region,
259 struct rrset_cache* rrset_cache, struct sldns_buffer* buf, time_t now,
260 int addsoa, uint8_t* topname);
261
262
263/**** functions exposed for unit test ****/
264/**
265 * Insert data into the data tree of a zone
266 * Does not do locking.
267 * @param neg: negative cache
268 * @param zone: zone to insert into
269 * @param nsec: record to insert.
270 */
271void neg_insert_data(struct val_neg_cache* neg,
272 struct val_neg_zone* zone, struct ub_packed_rrset_key* nsec);
273
274/**
275 * Delete a data element from the negative cache.
276 * May delete other data elements to keep tree coherent, or
277 * only mark the element as 'not in use'.
278 * Does not do locking.
279 * @param neg: negative cache.
280 * @param el: data element to delete.
281 */
282void neg_delete_data(struct val_neg_cache* neg, struct val_neg_data* el);
283
284/**
285 * Find the given zone, from the SOA owner name and class
286 * Does not do locking.
287 * @param neg: negative cache
288 * @param nm: what to look for.
289 * @param len: length of nm
290 * @param dclass: class to look for.
291 * @return zone or NULL if not found.
292 */
293struct val_neg_zone* neg_find_zone(struct val_neg_cache* neg,
294 uint8_t* nm, size_t len, uint16_t dclass);
295
296/**
297 * Create a new zone.
298 * Does not do locking.
299 * @param neg: negative cache
300 * @param nm: what to look for.
301 * @param nm_len: length of name.
302 * @param dclass: class of zone, host order.
303 * @return zone or NULL if out of memory.
304 */
305struct val_neg_zone* neg_create_zone(struct val_neg_cache* neg,
306 uint8_t* nm, size_t nm_len, uint16_t dclass);
307
308/**
309 * take a zone into use. increases counts of parents.
310 * Does not do locking.
311 * @param zone: zone to take into use.
312 */
313void val_neg_zone_take_inuse(struct val_neg_zone* zone);
314
315#endif /* VALIDATOR_VAL_NEG_H */