1238106Sdes/* 2238106Sdes * validator/val_neg.h - validator aggressive negative caching functions. 3238106Sdes * 4238106Sdes * Copyright (c) 2008, NLnet Labs. All rights reserved. 5238106Sdes * 6238106Sdes * This software is open source. 7238106Sdes * 8238106Sdes * Redistribution and use in source and binary forms, with or without 9238106Sdes * modification, are permitted provided that the following conditions 10238106Sdes * are met: 11238106Sdes * 12238106Sdes * Redistributions of source code must retain the above copyright notice, 13238106Sdes * this list of conditions and the following disclaimer. 14238106Sdes * 15238106Sdes * Redistributions in binary form must reproduce the above copyright notice, 16238106Sdes * this list of conditions and the following disclaimer in the documentation 17238106Sdes * and/or other materials provided with the distribution. 18238106Sdes * 19238106Sdes * Neither the name of the NLNET LABS nor the names of its contributors may 20238106Sdes * be used to endorse or promote products derived from this software without 21238106Sdes * specific prior written permission. 22238106Sdes * 23238106Sdes * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 24269257Sdes * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 25269257Sdes * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 26269257Sdes * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 27269257Sdes * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 28269257Sdes * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 29269257Sdes * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 30269257Sdes * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 31269257Sdes * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 32269257Sdes * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 33269257Sdes * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34238106Sdes */ 35238106Sdes 36238106Sdes/** 37238106Sdes * \file 38238106Sdes * 39238106Sdes * This file contains helper functions for the validator module. 40238106Sdes * The functions help with aggressive negative caching. 41294190Sdes * This creates new denials of existence, and proofs for absence of types 42238106Sdes * from cached NSEC records. 43238106Sdes */ 44238106Sdes 45238106Sdes#ifndef VALIDATOR_VAL_NEG_H 46238106Sdes#define VALIDATOR_VAL_NEG_H 47238106Sdes#include "util/locks.h" 48238106Sdes#include "util/rbtree.h" 49269257Sdesstruct sldns_buffer; 50238106Sdesstruct val_neg_data; 51238106Sdesstruct config_file; 52238106Sdesstruct reply_info; 53238106Sdesstruct rrset_cache; 54238106Sdesstruct regional; 55238106Sdesstruct query_info; 56238106Sdesstruct dns_msg; 57238106Sdesstruct ub_packed_rrset_key; 58238106Sdes 59238106Sdes/** 60238106Sdes * The negative cache. It is shared between the threads, so locked. 61238106Sdes * Kept as validator-environ-state. It refers back to the rrset cache for 62238106Sdes * data elements. It can be out of date and contain conflicting data 63238106Sdes * from zone content changes. 64238106Sdes * It contains a tree of zones, every zone has a tree of data elements. 65238106Sdes * The data elements are part of one big LRU list, with one memory counter. 66238106Sdes */ 67238106Sdesstruct val_neg_cache { 68238106Sdes /** the big lock on the negative cache. Because we use a rbtree 69238106Sdes * for the data (quick lookup), we need a big lock */ 70238106Sdes lock_basic_t lock; 71238106Sdes /** The zone rbtree. contents sorted canonical, type val_neg_zone */ 72238106Sdes rbtree_t tree; 73238106Sdes /** the first in linked list of LRU of val_neg_data */ 74238106Sdes struct val_neg_data* first; 75238106Sdes /** last in lru (least recently used element) */ 76238106Sdes struct val_neg_data* last; 77238106Sdes /** current memory in use (bytes) */ 78238106Sdes size_t use; 79238106Sdes /** max memory to use (bytes) */ 80238106Sdes size_t max; 81238106Sdes /** max nsec3 iterations allowed */ 82238106Sdes size_t nsec3_max_iter; 83238106Sdes}; 84238106Sdes 85238106Sdes/** 86238106Sdes * Per Zone aggressive negative caching data. 87238106Sdes */ 88238106Sdesstruct val_neg_zone { 89238106Sdes /** rbtree node element, key is this struct: the name, class */ 90238106Sdes rbnode_t node; 91238106Sdes /** name; the key */ 92238106Sdes uint8_t* name; 93238106Sdes /** length of name */ 94238106Sdes size_t len; 95238106Sdes /** labels in name */ 96238106Sdes int labs; 97238106Sdes 98238106Sdes /** pointer to parent zone in the negative cache */ 99238106Sdes struct val_neg_zone* parent; 100238106Sdes 101238106Sdes /** the number of elements, including this one and the ones whose 102238106Sdes * parents (-parents) include this one, that are in_use 103238106Sdes * No elements have a count of zero, those are removed. */ 104238106Sdes int count; 105238106Sdes 106238106Sdes /** if 0: NSEC zone, else NSEC3 hash algorithm in use */ 107238106Sdes int nsec3_hash; 108238106Sdes /** nsec3 iteration count in use */ 109238106Sdes size_t nsec3_iter; 110238106Sdes /** nsec3 salt in use */ 111238106Sdes uint8_t* nsec3_salt; 112238106Sdes /** length of salt in bytes */ 113238106Sdes size_t nsec3_saltlen; 114238106Sdes 115238106Sdes /** tree of NSEC data for this zone, sorted canonical 116238106Sdes * by NSEC owner name */ 117238106Sdes rbtree_t tree; 118238106Sdes 119238106Sdes /** class of node; host order */ 120238106Sdes uint16_t dclass; 121238106Sdes /** if this element is in use, boolean */ 122238106Sdes uint8_t in_use; 123238106Sdes}; 124238106Sdes 125238106Sdes/** 126238106Sdes * Data element for aggressive negative caching. 127238106Sdes * The tree of these elements acts as an index onto the rrset cache. 128238106Sdes * It shows the NSEC records that (may) exist and are (possibly) secure. 129238106Sdes * The rbtree allows for logN search for a covering NSEC record. 130238106Sdes * To make tree insertion and deletion logN too, all the parent (one label 131238106Sdes * less than the name) data elements are also in the rbtree, with a usage 132238106Sdes * count for every data element. 133238106Sdes * There is no actual data stored in this data element, if it is in_use, 134238106Sdes * then the data can (possibly) be found in the rrset cache. 135238106Sdes */ 136238106Sdesstruct val_neg_data { 137238106Sdes /** rbtree node element, key is this struct: the name */ 138238106Sdes rbnode_t node; 139238106Sdes /** name; the key */ 140238106Sdes uint8_t* name; 141238106Sdes /** length of name */ 142238106Sdes size_t len; 143238106Sdes /** labels in name */ 144238106Sdes int labs; 145238106Sdes 146238106Sdes /** pointer to parent node in the negative cache */ 147238106Sdes struct val_neg_data* parent; 148238106Sdes 149238106Sdes /** the number of elements, including this one and the ones whose 150238106Sdes * parents (-parents) include this one, that are in use 151238106Sdes * No elements have a count of zero, those are removed. */ 152238106Sdes int count; 153238106Sdes 154238106Sdes /** the zone that this denial is part of */ 155238106Sdes struct val_neg_zone* zone; 156238106Sdes 157238106Sdes /** previous in LRU */ 158238106Sdes struct val_neg_data* prev; 159238106Sdes /** next in LRU (next element was less recently used) */ 160238106Sdes struct val_neg_data* next; 161238106Sdes 162238106Sdes /** if this element is in use, boolean */ 163238106Sdes uint8_t in_use; 164238106Sdes}; 165238106Sdes 166238106Sdes/** 167238106Sdes * Create negative cache 168238106Sdes * @param cfg: config options. 169238106Sdes * @param maxiter: max nsec3 iterations allowed. 170238106Sdes * @return neg cache, empty or NULL on failure. 171238106Sdes */ 172238106Sdesstruct val_neg_cache* val_neg_create(struct config_file* cfg, size_t maxiter); 173238106Sdes 174238106Sdes/** 175238106Sdes * see how much memory is in use by the negative cache. 176238106Sdes * @param neg: negative cache 177238106Sdes * @return number of bytes in use. 178238106Sdes */ 179238106Sdessize_t val_neg_get_mem(struct val_neg_cache* neg); 180238106Sdes 181238106Sdes/** 182238106Sdes * Destroy negative cache. There must no longer be any other threads. 183238106Sdes * @param neg: negative cache. 184238106Sdes */ 185238106Sdesvoid neg_cache_delete(struct val_neg_cache* neg); 186238106Sdes 187238106Sdes/** 188238106Sdes * Comparison function for rbtree val neg data elements 189238106Sdes */ 190238106Sdesint val_neg_data_compare(const void* a, const void* b); 191238106Sdes 192238106Sdes/** 193238106Sdes * Comparison function for rbtree val neg zone elements 194238106Sdes */ 195238106Sdesint val_neg_zone_compare(const void* a, const void* b); 196238106Sdes 197238106Sdes/** 198238106Sdes * Insert NSECs from this message into the negative cache for reference. 199238106Sdes * @param neg: negative cache 200238106Sdes * @param rep: reply with NSECs. 201238106Sdes * Errors are ignored, means that storage is omitted. 202238106Sdes */ 203238106Sdesvoid val_neg_addreply(struct val_neg_cache* neg, struct reply_info* rep); 204238106Sdes 205238106Sdes/** 206238106Sdes * Insert NSECs from this referral into the negative cache for reference. 207238106Sdes * @param neg: negative cache 208238106Sdes * @param rep: referral reply with NS, NSECs. 209238106Sdes * @param zone: bailiwick for the referral. 210238106Sdes * Errors are ignored, means that storage is omitted. 211238106Sdes */ 212238106Sdesvoid val_neg_addreferral(struct val_neg_cache* neg, struct reply_info* rep, 213238106Sdes uint8_t* zone); 214238106Sdes 215238106Sdes/** 216238106Sdes * Perform a DLV style lookup 217238106Sdes * During the lookup, we could find out that data has expired. In that 218238106Sdes * case the neg_cache entries are removed, and lookup fails. 219238106Sdes * 220238106Sdes * @param neg: negative cache. 221238106Sdes * @param qname: name to look for 222238106Sdes * @param len: length of qname. 223238106Sdes * @param qclass: class to look in. 224238106Sdes * @param rrset_cache: the rrset cache, for NSEC lookups. 225238106Sdes * @param now: current time for ttl checks. 226238106Sdes * @return 227238106Sdes * 0 on error 228238106Sdes * 0 if no proof of negative 229238106Sdes * 1 if indeed negative was proven 230238106Sdes * thus, qname DLV qclass does not exist. 231238106Sdes */ 232238106Sdesint val_neg_dlvlookup(struct val_neg_cache* neg, uint8_t* qname, size_t len, 233269257Sdes uint16_t qclass, struct rrset_cache* rrset_cache, time_t now); 234238106Sdes 235238106Sdes/** 236238106Sdes * For the given query, try to get a reply out of the negative cache. 237238106Sdes * The reply still needs to be validated. 238238106Sdes * @param neg: negative cache. 239238106Sdes * @param qinfo: query 240238106Sdes * @param region: where to allocate reply. 241238106Sdes * @param rrset_cache: rrset cache. 242238106Sdes * @param buf: temporary buffer. 243238106Sdes * @param now: to check TTLs against. 244238106Sdes * @param addsoa: if true, produce result for external consumption. 245238106Sdes * if false, do not add SOA - for unbound-internal consumption. 246238106Sdes * @param topname: do not look higher than this name, 247238106Sdes * so that the result cannot be taken from a zone above the current 248238106Sdes * trust anchor. Which could happen with multiple islands of trust. 249238106Sdes * if NULL, then no trust anchor is used, but also the algorithm becomes 250238106Sdes * more conservative, especially for opt-out zones, since the receiver 251238106Sdes * may have a trust-anchor below the optout and thus the optout cannot 252238106Sdes * be used to create a proof from the negative cache. 253238106Sdes * @return a reply message if something was found. 254238106Sdes * This reply may still need validation. 255238106Sdes * NULL if nothing found (or out of memory). 256238106Sdes */ 257238106Sdesstruct dns_msg* val_neg_getmsg(struct val_neg_cache* neg, 258238106Sdes struct query_info* qinfo, struct regional* region, 259269257Sdes struct rrset_cache* rrset_cache, struct sldns_buffer* buf, time_t now, 260238106Sdes int addsoa, uint8_t* topname); 261238106Sdes 262238106Sdes 263238106Sdes/**** functions exposed for unit test ****/ 264238106Sdes/** 265238106Sdes * Insert data into the data tree of a zone 266238106Sdes * Does not do locking. 267238106Sdes * @param neg: negative cache 268238106Sdes * @param zone: zone to insert into 269238106Sdes * @param nsec: record to insert. 270238106Sdes */ 271238106Sdesvoid neg_insert_data(struct val_neg_cache* neg, 272238106Sdes struct val_neg_zone* zone, struct ub_packed_rrset_key* nsec); 273238106Sdes 274238106Sdes/** 275238106Sdes * Delete a data element from the negative cache. 276238106Sdes * May delete other data elements to keep tree coherent, or 277238106Sdes * only mark the element as 'not in use'. 278238106Sdes * Does not do locking. 279238106Sdes * @param neg: negative cache. 280238106Sdes * @param el: data element to delete. 281238106Sdes */ 282238106Sdesvoid neg_delete_data(struct val_neg_cache* neg, struct val_neg_data* el); 283238106Sdes 284238106Sdes/** 285238106Sdes * Find the given zone, from the SOA owner name and class 286238106Sdes * Does not do locking. 287238106Sdes * @param neg: negative cache 288238106Sdes * @param nm: what to look for. 289238106Sdes * @param len: length of nm 290238106Sdes * @param dclass: class to look for. 291238106Sdes * @return zone or NULL if not found. 292238106Sdes */ 293238106Sdesstruct val_neg_zone* neg_find_zone(struct val_neg_cache* neg, 294238106Sdes uint8_t* nm, size_t len, uint16_t dclass); 295238106Sdes 296238106Sdes/** 297238106Sdes * Create a new zone. 298238106Sdes * Does not do locking. 299238106Sdes * @param neg: negative cache 300238106Sdes * @param nm: what to look for. 301238106Sdes * @param nm_len: length of name. 302238106Sdes * @param dclass: class of zone, host order. 303238106Sdes * @return zone or NULL if out of memory. 304238106Sdes */ 305238106Sdesstruct val_neg_zone* neg_create_zone(struct val_neg_cache* neg, 306238106Sdes uint8_t* nm, size_t nm_len, uint16_t dclass); 307238106Sdes 308238106Sdes/** 309238106Sdes * take a zone into use. increases counts of parents. 310238106Sdes * Does not do locking. 311238106Sdes * @param zone: zone to take into use. 312238106Sdes */ 313238106Sdesvoid val_neg_zone_take_inuse(struct val_neg_zone* zone); 314238106Sdes 315238106Sdes#endif /* VALIDATOR_VAL_NEG_H */ 316