File: val_neg.h

package info (click to toggle)
unbound 1.6.0-2~bpo8+1
  • links: PTS, VCS
  • area: main
  • in suites: jessie-backports
  • size: 20,444 kB
  • sloc: ansic: 79,862; sh: 5,040; yacc: 1,900; makefile: 1,315; python: 1,302; perl: 141
file content (315 lines) | stat: -rw-r--r-- 10,550 bytes parent folder | download | duplicates (2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
/*
 * validator/val_neg.h - validator aggressive negative caching functions.
 *
 * Copyright (c) 2008, NLnet Labs. All rights reserved.
 *
 * This software is open source.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 * 
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 * 
 * Neither the name of the NLNET LABS nor the names of its contributors may
 * be used to endorse or promote products derived from this software without
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/**
 * \file
 *
 * This file contains helper functions for the validator module.
 * The functions help with aggressive negative caching.
 * This creates new denials of existence, and proofs for absence of types
 * from cached NSEC records.
 */

#ifndef VALIDATOR_VAL_NEG_H
#define VALIDATOR_VAL_NEG_H
#include "util/locks.h"
#include "util/rbtree.h"
struct sldns_buffer;
struct val_neg_data;
struct config_file;
struct reply_info;
struct rrset_cache;
struct regional;
struct query_info;
struct dns_msg;
struct ub_packed_rrset_key;

/**
 * The negative cache.  It is shared between the threads, so locked. 
 * Kept as validator-environ-state.  It refers back to the rrset cache for
 * data elements.  It can be out of date and contain conflicting data 
 * from zone content changes.  
 * It contains a tree of zones, every zone has a tree of data elements.
 * The data elements are part of one big LRU list, with one memory counter.
 */
struct val_neg_cache {
	/** the big lock on the negative cache.  Because we use a rbtree 
	 * for the data (quick lookup), we need a big lock */
	lock_basic_t lock;
	/** The zone rbtree. contents sorted canonical, type val_neg_zone */
	rbtree_t tree;
	/** the first in linked list of LRU of val_neg_data */
	struct val_neg_data* first;
	/** last in lru (least recently used element) */
	struct val_neg_data* last;
	/** current memory in use (bytes) */
	size_t use;
	/** max memory to use (bytes) */
	size_t max;
	/** max nsec3 iterations allowed */
	size_t nsec3_max_iter;
};

/**
 * Per Zone aggressive negative caching data.
 */
struct val_neg_zone {
	/** rbtree node element, key is this struct: the name, class */
	rbnode_t node;
	/** name; the key */
	uint8_t* name;
	/** length of name */
	size_t len;
	/** labels in name */
	int labs;

	/** pointer to parent zone in the negative cache */
	struct val_neg_zone* parent;

	/** the number of elements, including this one and the ones whose
	 * parents (-parents) include this one, that are in_use 
	 * No elements have a count of zero, those are removed. */
	int count;

	/** if 0: NSEC zone, else NSEC3 hash algorithm in use */
	int nsec3_hash;
	/** nsec3 iteration count in use */
	size_t nsec3_iter;
	/** nsec3 salt in use */
	uint8_t* nsec3_salt;
	/** length of salt in bytes */
	size_t nsec3_saltlen;

	/** tree of NSEC data for this zone, sorted canonical 
	 * by NSEC owner name */
	rbtree_t tree;

	/** class of node; host order */
	uint16_t dclass;
	/** if this element is in use, boolean */
	uint8_t in_use;
};

/**
 * Data element for aggressive negative caching.
 * The tree of these elements acts as an index onto the rrset cache.
 * It shows the NSEC records that (may) exist and are (possibly) secure.
 * The rbtree allows for logN search for a covering NSEC record.
 * To make tree insertion and deletion logN too, all the parent (one label
 * less than the name) data elements are also in the rbtree, with a usage
 * count for every data element.
 * There is no actual data stored in this data element, if it is in_use,
 * then the data can (possibly) be found in the rrset cache.
 */
struct val_neg_data {
	/** rbtree node element, key is this struct: the name */
	rbnode_t node;
	/** name; the key */
	uint8_t* name;
	/** length of name */
	size_t len;
	/** labels in name */
	int labs;

	/** pointer to parent node in the negative cache */
	struct val_neg_data* parent;

	/** the number of elements, including this one and the ones whose
	 * parents (-parents) include this one, that are in use 
	 * No elements have a count of zero, those are removed. */
	int count;

	/** the zone that this denial is part of */
	struct val_neg_zone* zone;

	/** previous in LRU */
	struct val_neg_data* prev;
	/** next in LRU (next element was less recently used) */
	struct val_neg_data* next;

	/** if this element is in use, boolean */
	uint8_t in_use;
};

/**
 * Create negative cache
 * @param cfg: config options.
 * @param maxiter: max nsec3 iterations allowed.
 * @return neg cache, empty or NULL on failure.
 */
struct val_neg_cache* val_neg_create(struct config_file* cfg, size_t maxiter);

/**
 * see how much memory is in use by the negative cache.
 * @param neg: negative cache
 * @return number of bytes in use.
 */
size_t val_neg_get_mem(struct val_neg_cache* neg);

/**
 * Destroy negative cache. There must no longer be any other threads.
 * @param neg: negative cache.
 */
void neg_cache_delete(struct val_neg_cache* neg);

/** 
 * Comparison function for rbtree val neg data elements
 */
int val_neg_data_compare(const void* a, const void* b);

/** 
 * Comparison function for rbtree val neg zone elements
 */
int val_neg_zone_compare(const void* a, const void* b);

/**
 * Insert NSECs from this message into the negative cache for reference.
 * @param neg: negative cache
 * @param rep: reply with NSECs.
 * Errors are ignored, means that storage is omitted.
 */
void val_neg_addreply(struct val_neg_cache* neg, struct reply_info* rep);

/**
 * Insert NSECs from this referral into the negative cache for reference.
 * @param neg: negative cache
 * @param rep: referral reply with NS, NSECs.
 * @param zone: bailiwick for the referral.
 * Errors are ignored, means that storage is omitted.
 */
void val_neg_addreferral(struct val_neg_cache* neg, struct reply_info* rep,
	uint8_t* zone);

/**
 * Perform a DLV style lookup
 * During the lookup, we could find out that data has expired. In that
 * case the neg_cache entries are removed, and lookup fails.
 *
 * @param neg: negative cache.
 * @param qname: name to look for
 * @param len: length of qname.
 * @param qclass: class to look in.
 * @param rrset_cache: the rrset cache, for NSEC lookups.
 * @param now: current time for ttl checks.
 * @return 
 *	0 on error
 *	0 if no proof of negative
 *	1 if indeed negative was proven
 *	  thus, qname DLV qclass does not exist.
 */
int val_neg_dlvlookup(struct val_neg_cache* neg, uint8_t* qname, size_t len,
	uint16_t qclass, struct rrset_cache* rrset_cache, time_t now);

/**
 * For the given query, try to get a reply out of the negative cache.
 * The reply still needs to be validated.
 * @param neg: negative cache.
 * @param qinfo: query
 * @param region: where to allocate reply.
 * @param rrset_cache: rrset cache.
 * @param buf: temporary buffer.
 * @param now: to check TTLs against.
 * @param addsoa: if true, produce result for external consumption.
 *	if false, do not add SOA - for unbound-internal consumption.
 * @param topname: do not look higher than this name, 
 * 	so that the result cannot be taken from a zone above the current
 * 	trust anchor.  Which could happen with multiple islands of trust.
 * 	if NULL, then no trust anchor is used, but also the algorithm becomes
 * 	more conservative, especially for opt-out zones, since the receiver
 * 	may have a trust-anchor below the optout and thus the optout cannot
 * 	be used to create a proof from the negative cache.
 * @return a reply message if something was found. 
 * 	This reply may still need validation.
 * 	NULL if nothing found (or out of memory).
 */
struct dns_msg* val_neg_getmsg(struct val_neg_cache* neg, 
	struct query_info* qinfo, struct regional* region, 
	struct rrset_cache* rrset_cache, struct sldns_buffer* buf, time_t now,
	int addsoa, uint8_t* topname);


/**** functions exposed for unit test ****/
/**
 * Insert data into the data tree of a zone
 * Does not do locking.
 * @param neg: negative cache
 * @param zone: zone to insert into
 * @param nsec: record to insert.
 */
void neg_insert_data(struct val_neg_cache* neg,
        struct val_neg_zone* zone, struct ub_packed_rrset_key* nsec);

/**
 * Delete a data element from the negative cache.
 * May delete other data elements to keep tree coherent, or
 * only mark the element as 'not in use'.
 * Does not do locking.
 * @param neg: negative cache.
 * @param el: data element to delete.
 */
void neg_delete_data(struct val_neg_cache* neg, struct val_neg_data* el);

/**
 * Find the given zone, from the SOA owner name and class
 * Does not do locking.
 * @param neg: negative cache
 * @param nm: what to look for.
 * @param len: length of nm
 * @param dclass: class to look for.
 * @return zone or NULL if not found.
 */
struct val_neg_zone* neg_find_zone(struct val_neg_cache* neg,
        uint8_t* nm, size_t len, uint16_t dclass);

/**
 * Create a new zone.
 * Does not do locking.
 * @param neg: negative cache
 * @param nm: what to look for.
 * @param nm_len: length of name.
 * @param dclass: class of zone, host order.
 * @return zone or NULL if out of memory.
 */
struct val_neg_zone* neg_create_zone(struct val_neg_cache* neg,
        uint8_t* nm, size_t nm_len, uint16_t dclass);

/**
 * take a zone into use. increases counts of parents.
 * Does not do locking.
 * @param zone: zone to take into use.
 */
void val_neg_zone_take_inuse(struct val_neg_zone* zone);

#endif /* VALIDATOR_VAL_NEG_H */