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