contrib/unbound/validator/val_neg.h

   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 */