1b7579f77SDag-Erling Smørgrav /* 2b7579f77SDag-Erling Smørgrav * validator/val_neg.c - validator aggressive negative caching functions. 3b7579f77SDag-Erling Smørgrav * 4b7579f77SDag-Erling Smørgrav * Copyright (c) 2008, NLnet Labs. All rights reserved. 5b7579f77SDag-Erling Smørgrav * 6b7579f77SDag-Erling Smørgrav * This software is open source. 7b7579f77SDag-Erling Smørgrav * 8b7579f77SDag-Erling Smørgrav * Redistribution and use in source and binary forms, with or without 9b7579f77SDag-Erling Smørgrav * modification, are permitted provided that the following conditions 10b7579f77SDag-Erling Smørgrav * are met: 11b7579f77SDag-Erling Smørgrav * 12b7579f77SDag-Erling Smørgrav * Redistributions of source code must retain the above copyright notice, 13b7579f77SDag-Erling Smørgrav * this list of conditions and the following disclaimer. 14b7579f77SDag-Erling Smørgrav * 15b7579f77SDag-Erling Smørgrav * Redistributions in binary form must reproduce the above copyright notice, 16b7579f77SDag-Erling Smørgrav * this list of conditions and the following disclaimer in the documentation 17b7579f77SDag-Erling Smørgrav * and/or other materials provided with the distribution. 18b7579f77SDag-Erling Smørgrav * 19b7579f77SDag-Erling Smørgrav * Neither the name of the NLNET LABS nor the names of its contributors may 20b7579f77SDag-Erling Smørgrav * be used to endorse or promote products derived from this software without 21b7579f77SDag-Erling Smørgrav * specific prior written permission. 22b7579f77SDag-Erling Smørgrav * 23b7579f77SDag-Erling Smørgrav * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 2417d15b25SDag-Erling Smørgrav * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2517d15b25SDag-Erling Smørgrav * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2617d15b25SDag-Erling Smørgrav * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2717d15b25SDag-Erling Smørgrav * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2817d15b25SDag-Erling Smørgrav * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 2917d15b25SDag-Erling Smørgrav * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 3017d15b25SDag-Erling Smørgrav * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 3117d15b25SDag-Erling Smørgrav * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 3217d15b25SDag-Erling Smørgrav * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 3317d15b25SDag-Erling Smørgrav * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 34b7579f77SDag-Erling Smørgrav */ 35b7579f77SDag-Erling Smørgrav 36b7579f77SDag-Erling Smørgrav /** 37b7579f77SDag-Erling Smørgrav * \file 38b7579f77SDag-Erling Smørgrav * 39b7579f77SDag-Erling Smørgrav * This file contains helper functions for the validator module. 40b7579f77SDag-Erling Smørgrav * The functions help with aggressive negative caching. 4105ab2901SDag-Erling Smørgrav * This creates new denials of existence, and proofs for absence of types 42b7579f77SDag-Erling Smørgrav * from cached NSEC records. 43b7579f77SDag-Erling Smørgrav */ 44b7579f77SDag-Erling Smørgrav #include "config.h" 45b7579f77SDag-Erling Smørgrav #ifdef HAVE_OPENSSL_SSL_H 46b7579f77SDag-Erling Smørgrav #include "openssl/ssl.h" 478ed2b524SDag-Erling Smørgrav #define NSEC3_SHA_LEN SHA_DIGEST_LENGTH 488ed2b524SDag-Erling Smørgrav #else 498ed2b524SDag-Erling Smørgrav #define NSEC3_SHA_LEN 20 50b7579f77SDag-Erling Smørgrav #endif 51b7579f77SDag-Erling Smørgrav #include "validator/val_neg.h" 52b7579f77SDag-Erling Smørgrav #include "validator/val_nsec.h" 53b7579f77SDag-Erling Smørgrav #include "validator/val_nsec3.h" 54b7579f77SDag-Erling Smørgrav #include "validator/val_utils.h" 55b7579f77SDag-Erling Smørgrav #include "util/data/dname.h" 56b7579f77SDag-Erling Smørgrav #include "util/data/msgreply.h" 57b7579f77SDag-Erling Smørgrav #include "util/log.h" 58b7579f77SDag-Erling Smørgrav #include "util/net_help.h" 59b7579f77SDag-Erling Smørgrav #include "util/config_file.h" 60b7579f77SDag-Erling Smørgrav #include "services/cache/rrset.h" 61b7579f77SDag-Erling Smørgrav #include "services/cache/dns.h" 6209a3aaf3SDag-Erling Smørgrav #include "sldns/rrdef.h" 6309a3aaf3SDag-Erling Smørgrav #include "sldns/sbuffer.h" 64b7579f77SDag-Erling Smørgrav 65b7579f77SDag-Erling Smørgrav int val_neg_data_compare(const void* a, const void* b) 66b7579f77SDag-Erling Smørgrav { 67b7579f77SDag-Erling Smørgrav struct val_neg_data* x = (struct val_neg_data*)a; 68b7579f77SDag-Erling Smørgrav struct val_neg_data* y = (struct val_neg_data*)b; 69b7579f77SDag-Erling Smørgrav int m; 70b7579f77SDag-Erling Smørgrav return dname_canon_lab_cmp(x->name, x->labs, y->name, y->labs, &m); 71b7579f77SDag-Erling Smørgrav } 72b7579f77SDag-Erling Smørgrav 73b7579f77SDag-Erling Smørgrav int val_neg_zone_compare(const void* a, const void* b) 74b7579f77SDag-Erling Smørgrav { 75b7579f77SDag-Erling Smørgrav struct val_neg_zone* x = (struct val_neg_zone*)a; 76b7579f77SDag-Erling Smørgrav struct val_neg_zone* y = (struct val_neg_zone*)b; 77b7579f77SDag-Erling Smørgrav int m; 78b7579f77SDag-Erling Smørgrav if(x->dclass != y->dclass) { 79b7579f77SDag-Erling Smørgrav if(x->dclass < y->dclass) 80b7579f77SDag-Erling Smørgrav return -1; 81b7579f77SDag-Erling Smørgrav return 1; 82b7579f77SDag-Erling Smørgrav } 83b7579f77SDag-Erling Smørgrav return dname_canon_lab_cmp(x->name, x->labs, y->name, y->labs, &m); 84b7579f77SDag-Erling Smørgrav } 85b7579f77SDag-Erling Smørgrav 86b7579f77SDag-Erling Smørgrav struct val_neg_cache* val_neg_create(struct config_file* cfg, size_t maxiter) 87b7579f77SDag-Erling Smørgrav { 88b7579f77SDag-Erling Smørgrav struct val_neg_cache* neg = (struct val_neg_cache*)calloc(1, 89b7579f77SDag-Erling Smørgrav sizeof(*neg)); 90b7579f77SDag-Erling Smørgrav if(!neg) { 91b7579f77SDag-Erling Smørgrav log_err("Could not create neg cache: out of memory"); 92b7579f77SDag-Erling Smørgrav return NULL; 93b7579f77SDag-Erling Smørgrav } 94b7579f77SDag-Erling Smørgrav neg->nsec3_max_iter = maxiter; 95b7579f77SDag-Erling Smørgrav neg->max = 1024*1024; /* 1 M is thousands of entries */ 96b7579f77SDag-Erling Smørgrav if(cfg) neg->max = cfg->neg_cache_size; 97b7579f77SDag-Erling Smørgrav rbtree_init(&neg->tree, &val_neg_zone_compare); 98b7579f77SDag-Erling Smørgrav lock_basic_init(&neg->lock); 99b7579f77SDag-Erling Smørgrav lock_protect(&neg->lock, neg, sizeof(*neg)); 100b7579f77SDag-Erling Smørgrav return neg; 101b7579f77SDag-Erling Smørgrav } 102b7579f77SDag-Erling Smørgrav 103b7579f77SDag-Erling Smørgrav size_t val_neg_get_mem(struct val_neg_cache* neg) 104b7579f77SDag-Erling Smørgrav { 105b7579f77SDag-Erling Smørgrav size_t result; 106b7579f77SDag-Erling Smørgrav lock_basic_lock(&neg->lock); 107b7579f77SDag-Erling Smørgrav result = sizeof(*neg) + neg->use; 108b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 109b7579f77SDag-Erling Smørgrav return result; 110b7579f77SDag-Erling Smørgrav } 111b7579f77SDag-Erling Smørgrav 112b7579f77SDag-Erling Smørgrav /** clear datas on cache deletion */ 113b7579f77SDag-Erling Smørgrav static void 114b7579f77SDag-Erling Smørgrav neg_clear_datas(rbnode_t* n, void* ATTR_UNUSED(arg)) 115b7579f77SDag-Erling Smørgrav { 116b7579f77SDag-Erling Smørgrav struct val_neg_data* d = (struct val_neg_data*)n; 117b7579f77SDag-Erling Smørgrav free(d->name); 118b7579f77SDag-Erling Smørgrav free(d); 119b7579f77SDag-Erling Smørgrav } 120b7579f77SDag-Erling Smørgrav 121b7579f77SDag-Erling Smørgrav /** clear zones on cache deletion */ 122b7579f77SDag-Erling Smørgrav static void 123b7579f77SDag-Erling Smørgrav neg_clear_zones(rbnode_t* n, void* ATTR_UNUSED(arg)) 124b7579f77SDag-Erling Smørgrav { 125b7579f77SDag-Erling Smørgrav struct val_neg_zone* z = (struct val_neg_zone*)n; 126b7579f77SDag-Erling Smørgrav /* delete all the rrset entries in the tree */ 127b7579f77SDag-Erling Smørgrav traverse_postorder(&z->tree, &neg_clear_datas, NULL); 128b7579f77SDag-Erling Smørgrav free(z->nsec3_salt); 129b7579f77SDag-Erling Smørgrav free(z->name); 130b7579f77SDag-Erling Smørgrav free(z); 131b7579f77SDag-Erling Smørgrav } 132b7579f77SDag-Erling Smørgrav 133b7579f77SDag-Erling Smørgrav void neg_cache_delete(struct val_neg_cache* neg) 134b7579f77SDag-Erling Smørgrav { 135b7579f77SDag-Erling Smørgrav if(!neg) return; 136b7579f77SDag-Erling Smørgrav lock_basic_destroy(&neg->lock); 137b7579f77SDag-Erling Smørgrav /* delete all the zones in the tree */ 138b7579f77SDag-Erling Smørgrav traverse_postorder(&neg->tree, &neg_clear_zones, NULL); 139b7579f77SDag-Erling Smørgrav free(neg); 140b7579f77SDag-Erling Smørgrav } 141b7579f77SDag-Erling Smørgrav 142b7579f77SDag-Erling Smørgrav /** 143b7579f77SDag-Erling Smørgrav * Put data element at the front of the LRU list. 144b7579f77SDag-Erling Smørgrav * @param neg: negative cache with LRU start and end. 145b7579f77SDag-Erling Smørgrav * @param data: this data is fronted. 146b7579f77SDag-Erling Smørgrav */ 147b7579f77SDag-Erling Smørgrav static void neg_lru_front(struct val_neg_cache* neg, 148b7579f77SDag-Erling Smørgrav struct val_neg_data* data) 149b7579f77SDag-Erling Smørgrav { 150b7579f77SDag-Erling Smørgrav data->prev = NULL; 151b7579f77SDag-Erling Smørgrav data->next = neg->first; 152b7579f77SDag-Erling Smørgrav if(!neg->first) 153b7579f77SDag-Erling Smørgrav neg->last = data; 154b7579f77SDag-Erling Smørgrav else neg->first->prev = data; 155b7579f77SDag-Erling Smørgrav neg->first = data; 156b7579f77SDag-Erling Smørgrav } 157b7579f77SDag-Erling Smørgrav 158b7579f77SDag-Erling Smørgrav /** 159b7579f77SDag-Erling Smørgrav * Remove data element from LRU list. 160b7579f77SDag-Erling Smørgrav * @param neg: negative cache with LRU start and end. 161b7579f77SDag-Erling Smørgrav * @param data: this data is removed from the list. 162b7579f77SDag-Erling Smørgrav */ 163b7579f77SDag-Erling Smørgrav static void neg_lru_remove(struct val_neg_cache* neg, 164b7579f77SDag-Erling Smørgrav struct val_neg_data* data) 165b7579f77SDag-Erling Smørgrav { 166b7579f77SDag-Erling Smørgrav if(data->prev) 167b7579f77SDag-Erling Smørgrav data->prev->next = data->next; 168b7579f77SDag-Erling Smørgrav else neg->first = data->next; 169b7579f77SDag-Erling Smørgrav if(data->next) 170b7579f77SDag-Erling Smørgrav data->next->prev = data->prev; 171b7579f77SDag-Erling Smørgrav else neg->last = data->prev; 172b7579f77SDag-Erling Smørgrav } 173b7579f77SDag-Erling Smørgrav 174b7579f77SDag-Erling Smørgrav /** 175b7579f77SDag-Erling Smørgrav * Touch LRU for data element, put it at the start of the LRU list. 176b7579f77SDag-Erling Smørgrav * @param neg: negative cache with LRU start and end. 177b7579f77SDag-Erling Smørgrav * @param data: this data is used. 178b7579f77SDag-Erling Smørgrav */ 179b7579f77SDag-Erling Smørgrav static void neg_lru_touch(struct val_neg_cache* neg, 180b7579f77SDag-Erling Smørgrav struct val_neg_data* data) 181b7579f77SDag-Erling Smørgrav { 182b7579f77SDag-Erling Smørgrav if(data == neg->first) 183b7579f77SDag-Erling Smørgrav return; /* nothing to do */ 184b7579f77SDag-Erling Smørgrav /* remove from current lru position */ 185b7579f77SDag-Erling Smørgrav neg_lru_remove(neg, data); 186b7579f77SDag-Erling Smørgrav /* add at front */ 187b7579f77SDag-Erling Smørgrav neg_lru_front(neg, data); 188b7579f77SDag-Erling Smørgrav } 189b7579f77SDag-Erling Smørgrav 190b7579f77SDag-Erling Smørgrav /** 191b7579f77SDag-Erling Smørgrav * Delete a zone element from the negative cache. 192b7579f77SDag-Erling Smørgrav * May delete other zone elements to keep tree coherent, or 193b7579f77SDag-Erling Smørgrav * only mark the element as 'not in use'. 194b7579f77SDag-Erling Smørgrav * @param neg: negative cache. 195b7579f77SDag-Erling Smørgrav * @param z: zone element to delete. 196b7579f77SDag-Erling Smørgrav */ 197b7579f77SDag-Erling Smørgrav static void neg_delete_zone(struct val_neg_cache* neg, struct val_neg_zone* z) 198b7579f77SDag-Erling Smørgrav { 199b7579f77SDag-Erling Smørgrav struct val_neg_zone* p, *np; 200b7579f77SDag-Erling Smørgrav if(!z) return; 201b7579f77SDag-Erling Smørgrav log_assert(z->in_use); 202b7579f77SDag-Erling Smørgrav log_assert(z->count > 0); 203b7579f77SDag-Erling Smørgrav z->in_use = 0; 204b7579f77SDag-Erling Smørgrav 205b7579f77SDag-Erling Smørgrav /* go up the tree and reduce counts */ 206b7579f77SDag-Erling Smørgrav p = z; 207b7579f77SDag-Erling Smørgrav while(p) { 208b7579f77SDag-Erling Smørgrav log_assert(p->count > 0); 209b7579f77SDag-Erling Smørgrav p->count --; 210b7579f77SDag-Erling Smørgrav p = p->parent; 211b7579f77SDag-Erling Smørgrav } 212b7579f77SDag-Erling Smørgrav 213b7579f77SDag-Erling Smørgrav /* remove zones with zero count */ 214b7579f77SDag-Erling Smørgrav p = z; 215b7579f77SDag-Erling Smørgrav while(p && p->count == 0) { 216b7579f77SDag-Erling Smørgrav np = p->parent; 217b7579f77SDag-Erling Smørgrav (void)rbtree_delete(&neg->tree, &p->node); 218b7579f77SDag-Erling Smørgrav neg->use -= p->len + sizeof(*p); 219b7579f77SDag-Erling Smørgrav free(p->nsec3_salt); 220b7579f77SDag-Erling Smørgrav free(p->name); 221b7579f77SDag-Erling Smørgrav free(p); 222b7579f77SDag-Erling Smørgrav p = np; 223b7579f77SDag-Erling Smørgrav } 224b7579f77SDag-Erling Smørgrav } 225b7579f77SDag-Erling Smørgrav 226b7579f77SDag-Erling Smørgrav void neg_delete_data(struct val_neg_cache* neg, struct val_neg_data* el) 227b7579f77SDag-Erling Smørgrav { 228b7579f77SDag-Erling Smørgrav struct val_neg_zone* z; 229b7579f77SDag-Erling Smørgrav struct val_neg_data* p, *np; 230b7579f77SDag-Erling Smørgrav if(!el) return; 231b7579f77SDag-Erling Smørgrav z = el->zone; 232b7579f77SDag-Erling Smørgrav log_assert(el->in_use); 233b7579f77SDag-Erling Smørgrav log_assert(el->count > 0); 234b7579f77SDag-Erling Smørgrav el->in_use = 0; 235b7579f77SDag-Erling Smørgrav 236b7579f77SDag-Erling Smørgrav /* remove it from the lru list */ 237b7579f77SDag-Erling Smørgrav neg_lru_remove(neg, el); 238b7579f77SDag-Erling Smørgrav 239b7579f77SDag-Erling Smørgrav /* go up the tree and reduce counts */ 240b7579f77SDag-Erling Smørgrav p = el; 241b7579f77SDag-Erling Smørgrav while(p) { 242b7579f77SDag-Erling Smørgrav log_assert(p->count > 0); 243b7579f77SDag-Erling Smørgrav p->count --; 244b7579f77SDag-Erling Smørgrav p = p->parent; 245b7579f77SDag-Erling Smørgrav } 246b7579f77SDag-Erling Smørgrav 247b7579f77SDag-Erling Smørgrav /* delete 0 count items from tree */ 248b7579f77SDag-Erling Smørgrav p = el; 249b7579f77SDag-Erling Smørgrav while(p && p->count == 0) { 250b7579f77SDag-Erling Smørgrav np = p->parent; 251b7579f77SDag-Erling Smørgrav (void)rbtree_delete(&z->tree, &p->node); 252b7579f77SDag-Erling Smørgrav neg->use -= p->len + sizeof(*p); 253b7579f77SDag-Erling Smørgrav free(p->name); 254b7579f77SDag-Erling Smørgrav free(p); 255b7579f77SDag-Erling Smørgrav p = np; 256b7579f77SDag-Erling Smørgrav } 257b7579f77SDag-Erling Smørgrav 258b7579f77SDag-Erling Smørgrav /* check if the zone is now unused */ 259b7579f77SDag-Erling Smørgrav if(z->tree.count == 0) { 260b7579f77SDag-Erling Smørgrav neg_delete_zone(neg, z); 261b7579f77SDag-Erling Smørgrav } 262b7579f77SDag-Erling Smørgrav } 263b7579f77SDag-Erling Smørgrav 264b7579f77SDag-Erling Smørgrav /** 265b7579f77SDag-Erling Smørgrav * Create more space in negative cache 266b7579f77SDag-Erling Smørgrav * The oldest elements are deleted until enough space is present. 267b7579f77SDag-Erling Smørgrav * Empty zones are deleted. 268b7579f77SDag-Erling Smørgrav * @param neg: negative cache. 269b7579f77SDag-Erling Smørgrav * @param need: how many bytes are needed. 270b7579f77SDag-Erling Smørgrav */ 271b7579f77SDag-Erling Smørgrav static void neg_make_space(struct val_neg_cache* neg, size_t need) 272b7579f77SDag-Erling Smørgrav { 273b7579f77SDag-Erling Smørgrav /* delete elements until enough space or its empty */ 274b7579f77SDag-Erling Smørgrav while(neg->last && neg->max < neg->use + need) { 275b7579f77SDag-Erling Smørgrav neg_delete_data(neg, neg->last); 276b7579f77SDag-Erling Smørgrav } 277b7579f77SDag-Erling Smørgrav } 278b7579f77SDag-Erling Smørgrav 279b7579f77SDag-Erling Smørgrav struct val_neg_zone* neg_find_zone(struct val_neg_cache* neg, 280b7579f77SDag-Erling Smørgrav uint8_t* nm, size_t len, uint16_t dclass) 281b7579f77SDag-Erling Smørgrav { 282b7579f77SDag-Erling Smørgrav struct val_neg_zone lookfor; 283b7579f77SDag-Erling Smørgrav struct val_neg_zone* result; 284b7579f77SDag-Erling Smørgrav lookfor.node.key = &lookfor; 285b7579f77SDag-Erling Smørgrav lookfor.name = nm; 286b7579f77SDag-Erling Smørgrav lookfor.len = len; 287b7579f77SDag-Erling Smørgrav lookfor.labs = dname_count_labels(lookfor.name); 288b7579f77SDag-Erling Smørgrav lookfor.dclass = dclass; 289b7579f77SDag-Erling Smørgrav 290b7579f77SDag-Erling Smørgrav result = (struct val_neg_zone*) 291b7579f77SDag-Erling Smørgrav rbtree_search(&neg->tree, lookfor.node.key); 292b7579f77SDag-Erling Smørgrav return result; 293b7579f77SDag-Erling Smørgrav } 294b7579f77SDag-Erling Smørgrav 295b7579f77SDag-Erling Smørgrav /** 296b7579f77SDag-Erling Smørgrav * Find the given data 297b7579f77SDag-Erling Smørgrav * @param zone: negative zone 298b7579f77SDag-Erling Smørgrav * @param nm: what to look for. 299b7579f77SDag-Erling Smørgrav * @param len: length of nm 300b7579f77SDag-Erling Smørgrav * @param labs: labels in nm 301b7579f77SDag-Erling Smørgrav * @return data or NULL if not found. 302b7579f77SDag-Erling Smørgrav */ 303b7579f77SDag-Erling Smørgrav static struct val_neg_data* neg_find_data(struct val_neg_zone* zone, 304b7579f77SDag-Erling Smørgrav uint8_t* nm, size_t len, int labs) 305b7579f77SDag-Erling Smørgrav { 306b7579f77SDag-Erling Smørgrav struct val_neg_data lookfor; 307b7579f77SDag-Erling Smørgrav struct val_neg_data* result; 308b7579f77SDag-Erling Smørgrav lookfor.node.key = &lookfor; 309b7579f77SDag-Erling Smørgrav lookfor.name = nm; 310b7579f77SDag-Erling Smørgrav lookfor.len = len; 311b7579f77SDag-Erling Smørgrav lookfor.labs = labs; 312b7579f77SDag-Erling Smørgrav 313b7579f77SDag-Erling Smørgrav result = (struct val_neg_data*) 314b7579f77SDag-Erling Smørgrav rbtree_search(&zone->tree, lookfor.node.key); 315b7579f77SDag-Erling Smørgrav return result; 316b7579f77SDag-Erling Smørgrav } 317b7579f77SDag-Erling Smørgrav 318b7579f77SDag-Erling Smørgrav /** 319b7579f77SDag-Erling Smørgrav * Calculate space needed for the data and all its parents 320b7579f77SDag-Erling Smørgrav * @param rep: NSEC entries. 321b7579f77SDag-Erling Smørgrav * @return size. 322b7579f77SDag-Erling Smørgrav */ 323b7579f77SDag-Erling Smørgrav static size_t calc_data_need(struct reply_info* rep) 324b7579f77SDag-Erling Smørgrav { 325b7579f77SDag-Erling Smørgrav uint8_t* d; 326b7579f77SDag-Erling Smørgrav size_t i, len, res = 0; 327b7579f77SDag-Erling Smørgrav 328b7579f77SDag-Erling Smørgrav for(i=rep->an_numrrsets; i<rep->an_numrrsets+rep->ns_numrrsets; i++) { 329b7579f77SDag-Erling Smørgrav if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC) { 330b7579f77SDag-Erling Smørgrav d = rep->rrsets[i]->rk.dname; 331b7579f77SDag-Erling Smørgrav len = rep->rrsets[i]->rk.dname_len; 332b7579f77SDag-Erling Smørgrav res = sizeof(struct val_neg_data) + len; 333b7579f77SDag-Erling Smørgrav while(!dname_is_root(d)) { 334b7579f77SDag-Erling Smørgrav log_assert(len > 1); /* not root label */ 335b7579f77SDag-Erling Smørgrav dname_remove_label(&d, &len); 336b7579f77SDag-Erling Smørgrav res += sizeof(struct val_neg_data) + len; 337b7579f77SDag-Erling Smørgrav } 338b7579f77SDag-Erling Smørgrav } 339b7579f77SDag-Erling Smørgrav } 340b7579f77SDag-Erling Smørgrav return res; 341b7579f77SDag-Erling Smørgrav } 342b7579f77SDag-Erling Smørgrav 343b7579f77SDag-Erling Smørgrav /** 344b7579f77SDag-Erling Smørgrav * Calculate space needed for zone and all its parents 345b7579f77SDag-Erling Smørgrav * @param d: name of zone 346b7579f77SDag-Erling Smørgrav * @param len: length of name 347b7579f77SDag-Erling Smørgrav * @return size. 348b7579f77SDag-Erling Smørgrav */ 349b7579f77SDag-Erling Smørgrav static size_t calc_zone_need(uint8_t* d, size_t len) 350b7579f77SDag-Erling Smørgrav { 351b7579f77SDag-Erling Smørgrav size_t res = sizeof(struct val_neg_zone) + len; 352b7579f77SDag-Erling Smørgrav while(!dname_is_root(d)) { 353b7579f77SDag-Erling Smørgrav log_assert(len > 1); /* not root label */ 354b7579f77SDag-Erling Smørgrav dname_remove_label(&d, &len); 355b7579f77SDag-Erling Smørgrav res += sizeof(struct val_neg_zone) + len; 356b7579f77SDag-Erling Smørgrav } 357b7579f77SDag-Erling Smørgrav return res; 358b7579f77SDag-Erling Smørgrav } 359b7579f77SDag-Erling Smørgrav 360b7579f77SDag-Erling Smørgrav /** 361b7579f77SDag-Erling Smørgrav * Find closest existing parent zone of the given name. 362b7579f77SDag-Erling Smørgrav * @param neg: negative cache. 363b7579f77SDag-Erling Smørgrav * @param nm: name to look for 364b7579f77SDag-Erling Smørgrav * @param nm_len: length of nm 365b7579f77SDag-Erling Smørgrav * @param labs: labelcount of nm. 366b7579f77SDag-Erling Smørgrav * @param qclass: class. 367b7579f77SDag-Erling Smørgrav * @return the zone or NULL if none found. 368b7579f77SDag-Erling Smørgrav */ 369b7579f77SDag-Erling Smørgrav static struct val_neg_zone* neg_closest_zone_parent(struct val_neg_cache* neg, 370b7579f77SDag-Erling Smørgrav uint8_t* nm, size_t nm_len, int labs, uint16_t qclass) 371b7579f77SDag-Erling Smørgrav { 372b7579f77SDag-Erling Smørgrav struct val_neg_zone key; 373b7579f77SDag-Erling Smørgrav struct val_neg_zone* result; 374b7579f77SDag-Erling Smørgrav rbnode_t* res = NULL; 375b7579f77SDag-Erling Smørgrav key.node.key = &key; 376b7579f77SDag-Erling Smørgrav key.name = nm; 377b7579f77SDag-Erling Smørgrav key.len = nm_len; 378b7579f77SDag-Erling Smørgrav key.labs = labs; 379b7579f77SDag-Erling Smørgrav key.dclass = qclass; 380b7579f77SDag-Erling Smørgrav if(rbtree_find_less_equal(&neg->tree, &key, &res)) { 381b7579f77SDag-Erling Smørgrav /* exact match */ 382b7579f77SDag-Erling Smørgrav result = (struct val_neg_zone*)res; 383b7579f77SDag-Erling Smørgrav } else { 384b7579f77SDag-Erling Smørgrav /* smaller element (or no element) */ 385b7579f77SDag-Erling Smørgrav int m; 386b7579f77SDag-Erling Smørgrav result = (struct val_neg_zone*)res; 387b7579f77SDag-Erling Smørgrav if(!result || result->dclass != qclass) 388b7579f77SDag-Erling Smørgrav return NULL; 389b7579f77SDag-Erling Smørgrav /* count number of labels matched */ 390b7579f77SDag-Erling Smørgrav (void)dname_lab_cmp(result->name, result->labs, key.name, 391b7579f77SDag-Erling Smørgrav key.labs, &m); 392b7579f77SDag-Erling Smørgrav while(result) { /* go up until qname is subdomain of stub */ 393b7579f77SDag-Erling Smørgrav if(result->labs <= m) 394b7579f77SDag-Erling Smørgrav break; 395b7579f77SDag-Erling Smørgrav result = result->parent; 396b7579f77SDag-Erling Smørgrav } 397b7579f77SDag-Erling Smørgrav } 398b7579f77SDag-Erling Smørgrav return result; 399b7579f77SDag-Erling Smørgrav } 400b7579f77SDag-Erling Smørgrav 401b7579f77SDag-Erling Smørgrav /** 402b7579f77SDag-Erling Smørgrav * Find closest existing parent data for the given name. 403b7579f77SDag-Erling Smørgrav * @param zone: to look in. 404b7579f77SDag-Erling Smørgrav * @param nm: name to look for 405b7579f77SDag-Erling Smørgrav * @param nm_len: length of nm 406b7579f77SDag-Erling Smørgrav * @param labs: labelcount of nm. 407b7579f77SDag-Erling Smørgrav * @return the data or NULL if none found. 408b7579f77SDag-Erling Smørgrav */ 409b7579f77SDag-Erling Smørgrav static struct val_neg_data* neg_closest_data_parent( 410b7579f77SDag-Erling Smørgrav struct val_neg_zone* zone, uint8_t* nm, size_t nm_len, int labs) 411b7579f77SDag-Erling Smørgrav { 412b7579f77SDag-Erling Smørgrav struct val_neg_data key; 413b7579f77SDag-Erling Smørgrav struct val_neg_data* result; 414b7579f77SDag-Erling Smørgrav rbnode_t* res = NULL; 415b7579f77SDag-Erling Smørgrav key.node.key = &key; 416b7579f77SDag-Erling Smørgrav key.name = nm; 417b7579f77SDag-Erling Smørgrav key.len = nm_len; 418b7579f77SDag-Erling Smørgrav key.labs = labs; 419b7579f77SDag-Erling Smørgrav if(rbtree_find_less_equal(&zone->tree, &key, &res)) { 420b7579f77SDag-Erling Smørgrav /* exact match */ 421b7579f77SDag-Erling Smørgrav result = (struct val_neg_data*)res; 422b7579f77SDag-Erling Smørgrav } else { 423b7579f77SDag-Erling Smørgrav /* smaller element (or no element) */ 424b7579f77SDag-Erling Smørgrav int m; 425b7579f77SDag-Erling Smørgrav result = (struct val_neg_data*)res; 426b7579f77SDag-Erling Smørgrav if(!result) 427b7579f77SDag-Erling Smørgrav return NULL; 428b7579f77SDag-Erling Smørgrav /* count number of labels matched */ 429b7579f77SDag-Erling Smørgrav (void)dname_lab_cmp(result->name, result->labs, key.name, 430b7579f77SDag-Erling Smørgrav key.labs, &m); 431b7579f77SDag-Erling Smørgrav while(result) { /* go up until qname is subdomain of stub */ 432b7579f77SDag-Erling Smørgrav if(result->labs <= m) 433b7579f77SDag-Erling Smørgrav break; 434b7579f77SDag-Erling Smørgrav result = result->parent; 435b7579f77SDag-Erling Smørgrav } 436b7579f77SDag-Erling Smørgrav } 437b7579f77SDag-Erling Smørgrav return result; 438b7579f77SDag-Erling Smørgrav } 439b7579f77SDag-Erling Smørgrav 440b7579f77SDag-Erling Smørgrav /** 441b7579f77SDag-Erling Smørgrav * Create a single zone node 442b7579f77SDag-Erling Smørgrav * @param nm: name for zone (copied) 443b7579f77SDag-Erling Smørgrav * @param nm_len: length of name 444b7579f77SDag-Erling Smørgrav * @param labs: labels in name. 445b7579f77SDag-Erling Smørgrav * @param dclass: class of zone, host order. 446b7579f77SDag-Erling Smørgrav * @return new zone or NULL on failure 447b7579f77SDag-Erling Smørgrav */ 448b7579f77SDag-Erling Smørgrav static struct val_neg_zone* neg_setup_zone_node( 449b7579f77SDag-Erling Smørgrav uint8_t* nm, size_t nm_len, int labs, uint16_t dclass) 450b7579f77SDag-Erling Smørgrav { 451b7579f77SDag-Erling Smørgrav struct val_neg_zone* zone = 452b7579f77SDag-Erling Smørgrav (struct val_neg_zone*)calloc(1, sizeof(*zone)); 453b7579f77SDag-Erling Smørgrav if(!zone) { 454b7579f77SDag-Erling Smørgrav return NULL; 455b7579f77SDag-Erling Smørgrav } 456b7579f77SDag-Erling Smørgrav zone->node.key = zone; 457b7579f77SDag-Erling Smørgrav zone->name = memdup(nm, nm_len); 458b7579f77SDag-Erling Smørgrav if(!zone->name) { 459b7579f77SDag-Erling Smørgrav free(zone); 460b7579f77SDag-Erling Smørgrav return NULL; 461b7579f77SDag-Erling Smørgrav } 462b7579f77SDag-Erling Smørgrav zone->len = nm_len; 463b7579f77SDag-Erling Smørgrav zone->labs = labs; 464b7579f77SDag-Erling Smørgrav zone->dclass = dclass; 465b7579f77SDag-Erling Smørgrav 466b7579f77SDag-Erling Smørgrav rbtree_init(&zone->tree, &val_neg_data_compare); 467b7579f77SDag-Erling Smørgrav return zone; 468b7579f77SDag-Erling Smørgrav } 469b7579f77SDag-Erling Smørgrav 470b7579f77SDag-Erling Smørgrav /** 471b7579f77SDag-Erling Smørgrav * Create a linked list of parent zones, starting at longname ending on 472b7579f77SDag-Erling Smørgrav * the parent (can be NULL, creates to the root). 473b7579f77SDag-Erling Smørgrav * @param nm: name for lowest in chain 474b7579f77SDag-Erling Smørgrav * @param nm_len: length of name 475b7579f77SDag-Erling Smørgrav * @param labs: labels in name. 476b7579f77SDag-Erling Smørgrav * @param dclass: class of zone. 477b7579f77SDag-Erling Smørgrav * @param parent: NULL for to root, else so it fits under here. 478b7579f77SDag-Erling Smørgrav * @return zone; a chain of zones and their parents up to the parent. 479b7579f77SDag-Erling Smørgrav * or NULL on malloc failure 480b7579f77SDag-Erling Smørgrav */ 481b7579f77SDag-Erling Smørgrav static struct val_neg_zone* neg_zone_chain( 482b7579f77SDag-Erling Smørgrav uint8_t* nm, size_t nm_len, int labs, uint16_t dclass, 483b7579f77SDag-Erling Smørgrav struct val_neg_zone* parent) 484b7579f77SDag-Erling Smørgrav { 485b7579f77SDag-Erling Smørgrav int i; 486b7579f77SDag-Erling Smørgrav int tolabs = parent?parent->labs:0; 487b7579f77SDag-Erling Smørgrav struct val_neg_zone* zone, *prev = NULL, *first = NULL; 488b7579f77SDag-Erling Smørgrav 489b7579f77SDag-Erling Smørgrav /* create the new subtree, i is labelcount of current creation */ 490b7579f77SDag-Erling Smørgrav /* this creates a 'first' to z->parent=NULL list of zones */ 491b7579f77SDag-Erling Smørgrav for(i=labs; i!=tolabs; i--) { 492b7579f77SDag-Erling Smørgrav /* create new item */ 493b7579f77SDag-Erling Smørgrav zone = neg_setup_zone_node(nm, nm_len, i, dclass); 494b7579f77SDag-Erling Smørgrav if(!zone) { 495b7579f77SDag-Erling Smørgrav /* need to delete other allocations in this routine!*/ 496b7579f77SDag-Erling Smørgrav struct val_neg_zone* p=first, *np; 497b7579f77SDag-Erling Smørgrav while(p) { 498b7579f77SDag-Erling Smørgrav np = p->parent; 499b7579f77SDag-Erling Smørgrav free(p->name); 50017d15b25SDag-Erling Smørgrav free(p); 501b7579f77SDag-Erling Smørgrav p = np; 502b7579f77SDag-Erling Smørgrav } 503b7579f77SDag-Erling Smørgrav return NULL; 504b7579f77SDag-Erling Smørgrav } 505b7579f77SDag-Erling Smørgrav if(i == labs) { 506b7579f77SDag-Erling Smørgrav first = zone; 507b7579f77SDag-Erling Smørgrav } else { 508b7579f77SDag-Erling Smørgrav prev->parent = zone; 509b7579f77SDag-Erling Smørgrav } 510b7579f77SDag-Erling Smørgrav /* prepare for next name */ 511b7579f77SDag-Erling Smørgrav prev = zone; 512b7579f77SDag-Erling Smørgrav dname_remove_label(&nm, &nm_len); 513b7579f77SDag-Erling Smørgrav } 514b7579f77SDag-Erling Smørgrav return first; 515b7579f77SDag-Erling Smørgrav } 516b7579f77SDag-Erling Smørgrav 517b7579f77SDag-Erling Smørgrav void val_neg_zone_take_inuse(struct val_neg_zone* zone) 518b7579f77SDag-Erling Smørgrav { 519b7579f77SDag-Erling Smørgrav if(!zone->in_use) { 520b7579f77SDag-Erling Smørgrav struct val_neg_zone* p; 521b7579f77SDag-Erling Smørgrav zone->in_use = 1; 522b7579f77SDag-Erling Smørgrav /* increase usage count of all parents */ 523b7579f77SDag-Erling Smørgrav for(p=zone; p; p = p->parent) { 524b7579f77SDag-Erling Smørgrav p->count++; 525b7579f77SDag-Erling Smørgrav } 526b7579f77SDag-Erling Smørgrav } 527b7579f77SDag-Erling Smørgrav } 528b7579f77SDag-Erling Smørgrav 529b7579f77SDag-Erling Smørgrav struct val_neg_zone* neg_create_zone(struct val_neg_cache* neg, 530b7579f77SDag-Erling Smørgrav uint8_t* nm, size_t nm_len, uint16_t dclass) 531b7579f77SDag-Erling Smørgrav { 532b7579f77SDag-Erling Smørgrav struct val_neg_zone* zone; 533b7579f77SDag-Erling Smørgrav struct val_neg_zone* parent; 534b7579f77SDag-Erling Smørgrav struct val_neg_zone* p, *np; 535b7579f77SDag-Erling Smørgrav int labs = dname_count_labels(nm); 536b7579f77SDag-Erling Smørgrav 537b7579f77SDag-Erling Smørgrav /* find closest enclosing parent zone that (still) exists */ 538b7579f77SDag-Erling Smørgrav parent = neg_closest_zone_parent(neg, nm, nm_len, labs, dclass); 539b7579f77SDag-Erling Smørgrav if(parent && query_dname_compare(parent->name, nm) == 0) 540b7579f77SDag-Erling Smørgrav return parent; /* already exists, weird */ 541b7579f77SDag-Erling Smørgrav /* if parent exists, it is in use */ 542b7579f77SDag-Erling Smørgrav log_assert(!parent || parent->count > 0); 543b7579f77SDag-Erling Smørgrav zone = neg_zone_chain(nm, nm_len, labs, dclass, parent); 544b7579f77SDag-Erling Smørgrav if(!zone) { 545b7579f77SDag-Erling Smørgrav return NULL; 546b7579f77SDag-Erling Smørgrav } 547b7579f77SDag-Erling Smørgrav 548b7579f77SDag-Erling Smørgrav /* insert the list of zones into the tree */ 549b7579f77SDag-Erling Smørgrav p = zone; 550b7579f77SDag-Erling Smørgrav while(p) { 551b7579f77SDag-Erling Smørgrav np = p->parent; 552b7579f77SDag-Erling Smørgrav /* mem use */ 553b7579f77SDag-Erling Smørgrav neg->use += sizeof(struct val_neg_zone) + p->len; 554b7579f77SDag-Erling Smørgrav /* insert in tree */ 555b7579f77SDag-Erling Smørgrav (void)rbtree_insert(&neg->tree, &p->node); 556b7579f77SDag-Erling Smørgrav /* last one needs proper parent pointer */ 557b7579f77SDag-Erling Smørgrav if(np == NULL) 558b7579f77SDag-Erling Smørgrav p->parent = parent; 559b7579f77SDag-Erling Smørgrav p = np; 560b7579f77SDag-Erling Smørgrav } 561b7579f77SDag-Erling Smørgrav return zone; 562b7579f77SDag-Erling Smørgrav } 563b7579f77SDag-Erling Smørgrav 564b7579f77SDag-Erling Smørgrav /** find zone name of message, returns the SOA record */ 565b7579f77SDag-Erling Smørgrav static struct ub_packed_rrset_key* reply_find_soa(struct reply_info* rep) 566b7579f77SDag-Erling Smørgrav { 567b7579f77SDag-Erling Smørgrav size_t i; 568b7579f77SDag-Erling Smørgrav for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 569b7579f77SDag-Erling Smørgrav if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_SOA) 570b7579f77SDag-Erling Smørgrav return rep->rrsets[i]; 571b7579f77SDag-Erling Smørgrav } 572b7579f77SDag-Erling Smørgrav return NULL; 573b7579f77SDag-Erling Smørgrav } 574b7579f77SDag-Erling Smørgrav 575b7579f77SDag-Erling Smørgrav /** see if the reply has NSEC records worthy of caching */ 576b7579f77SDag-Erling Smørgrav static int reply_has_nsec(struct reply_info* rep) 577b7579f77SDag-Erling Smørgrav { 578b7579f77SDag-Erling Smørgrav size_t i; 579b7579f77SDag-Erling Smørgrav struct packed_rrset_data* d; 580b7579f77SDag-Erling Smørgrav if(rep->security != sec_status_secure) 581b7579f77SDag-Erling Smørgrav return 0; 582b7579f77SDag-Erling Smørgrav for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 583b7579f77SDag-Erling Smørgrav if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC) { 584b7579f77SDag-Erling Smørgrav d = (struct packed_rrset_data*)rep->rrsets[i]-> 585b7579f77SDag-Erling Smørgrav entry.data; 586b7579f77SDag-Erling Smørgrav if(d->security == sec_status_secure) 587b7579f77SDag-Erling Smørgrav return 1; 588b7579f77SDag-Erling Smørgrav } 589b7579f77SDag-Erling Smørgrav } 590b7579f77SDag-Erling Smørgrav return 0; 591b7579f77SDag-Erling Smørgrav } 592b7579f77SDag-Erling Smørgrav 593b7579f77SDag-Erling Smørgrav 594b7579f77SDag-Erling Smørgrav /** 595b7579f77SDag-Erling Smørgrav * Create single node of data element. 596b7579f77SDag-Erling Smørgrav * @param nm: name (copied) 597b7579f77SDag-Erling Smørgrav * @param nm_len: length of name 598b7579f77SDag-Erling Smørgrav * @param labs: labels in name. 599b7579f77SDag-Erling Smørgrav * @return element with name nm, or NULL malloc failure. 600b7579f77SDag-Erling Smørgrav */ 601b7579f77SDag-Erling Smørgrav static struct val_neg_data* neg_setup_data_node( 602b7579f77SDag-Erling Smørgrav uint8_t* nm, size_t nm_len, int labs) 603b7579f77SDag-Erling Smørgrav { 604b7579f77SDag-Erling Smørgrav struct val_neg_data* el; 605b7579f77SDag-Erling Smørgrav el = (struct val_neg_data*)calloc(1, sizeof(*el)); 606b7579f77SDag-Erling Smørgrav if(!el) { 607b7579f77SDag-Erling Smørgrav return NULL; 608b7579f77SDag-Erling Smørgrav } 609b7579f77SDag-Erling Smørgrav el->node.key = el; 610b7579f77SDag-Erling Smørgrav el->name = memdup(nm, nm_len); 611b7579f77SDag-Erling Smørgrav if(!el->name) { 612b7579f77SDag-Erling Smørgrav free(el); 613b7579f77SDag-Erling Smørgrav return NULL; 614b7579f77SDag-Erling Smørgrav } 615b7579f77SDag-Erling Smørgrav el->len = nm_len; 616b7579f77SDag-Erling Smørgrav el->labs = labs; 617b7579f77SDag-Erling Smørgrav return el; 618b7579f77SDag-Erling Smørgrav } 619b7579f77SDag-Erling Smørgrav 620b7579f77SDag-Erling Smørgrav /** 621b7579f77SDag-Erling Smørgrav * Create chain of data element and parents 622b7579f77SDag-Erling Smørgrav * @param nm: name 623b7579f77SDag-Erling Smørgrav * @param nm_len: length of name 624b7579f77SDag-Erling Smørgrav * @param labs: labels in name. 625b7579f77SDag-Erling Smørgrav * @param parent: up to where to make, if NULL up to root label. 626b7579f77SDag-Erling Smørgrav * @return lowest element with name nm, or NULL malloc failure. 627b7579f77SDag-Erling Smørgrav */ 628b7579f77SDag-Erling Smørgrav static struct val_neg_data* neg_data_chain( 629b7579f77SDag-Erling Smørgrav uint8_t* nm, size_t nm_len, int labs, struct val_neg_data* parent) 630b7579f77SDag-Erling Smørgrav { 631b7579f77SDag-Erling Smørgrav int i; 632b7579f77SDag-Erling Smørgrav int tolabs = parent?parent->labs:0; 633b7579f77SDag-Erling Smørgrav struct val_neg_data* el, *first = NULL, *prev = NULL; 634b7579f77SDag-Erling Smørgrav 635b7579f77SDag-Erling Smørgrav /* create the new subtree, i is labelcount of current creation */ 636b7579f77SDag-Erling Smørgrav /* this creates a 'first' to z->parent=NULL list of zones */ 637b7579f77SDag-Erling Smørgrav for(i=labs; i!=tolabs; i--) { 638b7579f77SDag-Erling Smørgrav /* create new item */ 639b7579f77SDag-Erling Smørgrav el = neg_setup_data_node(nm, nm_len, i); 640b7579f77SDag-Erling Smørgrav if(!el) { 641b7579f77SDag-Erling Smørgrav /* need to delete other allocations in this routine!*/ 642b7579f77SDag-Erling Smørgrav struct val_neg_data* p = first, *np; 643b7579f77SDag-Erling Smørgrav while(p) { 644b7579f77SDag-Erling Smørgrav np = p->parent; 645b7579f77SDag-Erling Smørgrav free(p->name); 64617d15b25SDag-Erling Smørgrav free(p); 647b7579f77SDag-Erling Smørgrav p = np; 648b7579f77SDag-Erling Smørgrav } 649b7579f77SDag-Erling Smørgrav return NULL; 650b7579f77SDag-Erling Smørgrav } 651b7579f77SDag-Erling Smørgrav if(i == labs) { 652b7579f77SDag-Erling Smørgrav first = el; 653b7579f77SDag-Erling Smørgrav } else { 654b7579f77SDag-Erling Smørgrav prev->parent = el; 655b7579f77SDag-Erling Smørgrav } 656b7579f77SDag-Erling Smørgrav 657b7579f77SDag-Erling Smørgrav /* prepare for next name */ 658b7579f77SDag-Erling Smørgrav prev = el; 659b7579f77SDag-Erling Smørgrav dname_remove_label(&nm, &nm_len); 660b7579f77SDag-Erling Smørgrav } 661b7579f77SDag-Erling Smørgrav return first; 662b7579f77SDag-Erling Smørgrav } 663b7579f77SDag-Erling Smørgrav 664b7579f77SDag-Erling Smørgrav /** 665b7579f77SDag-Erling Smørgrav * Remove NSEC records between start and end points. 666b7579f77SDag-Erling Smørgrav * By walking the tree, the tree is sorted canonically. 667b7579f77SDag-Erling Smørgrav * @param neg: negative cache. 668b7579f77SDag-Erling Smørgrav * @param zone: the zone 669b7579f77SDag-Erling Smørgrav * @param el: element to start walking at. 670b7579f77SDag-Erling Smørgrav * @param nsec: the nsec record with the end point 671b7579f77SDag-Erling Smørgrav */ 672b7579f77SDag-Erling Smørgrav static void wipeout(struct val_neg_cache* neg, struct val_neg_zone* zone, 673b7579f77SDag-Erling Smørgrav struct val_neg_data* el, struct ub_packed_rrset_key* nsec) 674b7579f77SDag-Erling Smørgrav { 675b7579f77SDag-Erling Smørgrav struct packed_rrset_data* d = (struct packed_rrset_data*)nsec-> 676b7579f77SDag-Erling Smørgrav entry.data; 677b7579f77SDag-Erling Smørgrav uint8_t* end; 678b7579f77SDag-Erling Smørgrav size_t end_len; 679b7579f77SDag-Erling Smørgrav int end_labs, m; 680b7579f77SDag-Erling Smørgrav rbnode_t* walk, *next; 681b7579f77SDag-Erling Smørgrav struct val_neg_data* cur; 682b7579f77SDag-Erling Smørgrav uint8_t buf[257]; 683b7579f77SDag-Erling Smørgrav /* get endpoint */ 684b7579f77SDag-Erling Smørgrav if(!d || d->count == 0 || d->rr_len[0] < 2+1) 685b7579f77SDag-Erling Smørgrav return; 686b7579f77SDag-Erling Smørgrav if(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC) { 687b7579f77SDag-Erling Smørgrav end = d->rr_data[0]+2; 688b7579f77SDag-Erling Smørgrav end_len = dname_valid(end, d->rr_len[0]-2); 689b7579f77SDag-Erling Smørgrav end_labs = dname_count_labels(end); 690b7579f77SDag-Erling Smørgrav } else { 691b7579f77SDag-Erling Smørgrav /* NSEC3 */ 692b7579f77SDag-Erling Smørgrav if(!nsec3_get_nextowner_b32(nsec, 0, buf, sizeof(buf))) 693b7579f77SDag-Erling Smørgrav return; 694b7579f77SDag-Erling Smørgrav end = buf; 695b7579f77SDag-Erling Smørgrav end_labs = dname_count_size_labels(end, &end_len); 696b7579f77SDag-Erling Smørgrav } 697b7579f77SDag-Erling Smørgrav 698b7579f77SDag-Erling Smørgrav /* sanity check, both owner and end must be below the zone apex */ 699b7579f77SDag-Erling Smørgrav if(!dname_subdomain_c(el->name, zone->name) || 700b7579f77SDag-Erling Smørgrav !dname_subdomain_c(end, zone->name)) 701b7579f77SDag-Erling Smørgrav return; 702b7579f77SDag-Erling Smørgrav 703b7579f77SDag-Erling Smørgrav /* detect end of zone NSEC ; wipe until the end of zone */ 704b7579f77SDag-Erling Smørgrav if(query_dname_compare(end, zone->name) == 0) { 705b7579f77SDag-Erling Smørgrav end = NULL; 706b7579f77SDag-Erling Smørgrav } 707b7579f77SDag-Erling Smørgrav 708b7579f77SDag-Erling Smørgrav walk = rbtree_next(&el->node); 709b7579f77SDag-Erling Smørgrav while(walk && walk != RBTREE_NULL) { 710b7579f77SDag-Erling Smørgrav cur = (struct val_neg_data*)walk; 711b7579f77SDag-Erling Smørgrav /* sanity check: must be larger than start */ 712b7579f77SDag-Erling Smørgrav if(dname_canon_lab_cmp(cur->name, cur->labs, 713b7579f77SDag-Erling Smørgrav el->name, el->labs, &m) <= 0) { 714b7579f77SDag-Erling Smørgrav /* r == 0 skip original record. */ 715b7579f77SDag-Erling Smørgrav /* r < 0 too small! */ 716b7579f77SDag-Erling Smørgrav walk = rbtree_next(walk); 717b7579f77SDag-Erling Smørgrav continue; 718b7579f77SDag-Erling Smørgrav } 719b7579f77SDag-Erling Smørgrav /* stop at endpoint, also data at empty nonterminals must be 720b7579f77SDag-Erling Smørgrav * removed (no NSECs there) so everything between 721b7579f77SDag-Erling Smørgrav * start and end */ 722b7579f77SDag-Erling Smørgrav if(end && dname_canon_lab_cmp(cur->name, cur->labs, 723b7579f77SDag-Erling Smørgrav end, end_labs, &m) >= 0) { 724b7579f77SDag-Erling Smørgrav break; 725b7579f77SDag-Erling Smørgrav } 726b7579f77SDag-Erling Smørgrav /* this element has to be deleted, but we cannot do it 727b7579f77SDag-Erling Smørgrav * now, because we are walking the tree still ... */ 728b7579f77SDag-Erling Smørgrav /* get the next element: */ 729b7579f77SDag-Erling Smørgrav next = rbtree_next(walk); 730b7579f77SDag-Erling Smørgrav /* now delete the original element, this may trigger 731b7579f77SDag-Erling Smørgrav * rbtree rebalances, but really, the next element is 732b7579f77SDag-Erling Smørgrav * the one we need. 733b7579f77SDag-Erling Smørgrav * But it may trigger delete of other data and the 734b7579f77SDag-Erling Smørgrav * entire zone. However, if that happens, this is done 735b7579f77SDag-Erling Smørgrav * by deleting the *parents* of the element for deletion, 736b7579f77SDag-Erling Smørgrav * and maybe also the entire zone if it is empty. 737b7579f77SDag-Erling Smørgrav * But parents are smaller in canonical compare, thus, 738b7579f77SDag-Erling Smørgrav * if a larger element exists, then it is not a parent, 739b7579f77SDag-Erling Smørgrav * it cannot get deleted, the zone cannot get empty. 740b7579f77SDag-Erling Smørgrav * If the next==NULL, then zone can be empty. */ 741b7579f77SDag-Erling Smørgrav if(cur->in_use) 742b7579f77SDag-Erling Smørgrav neg_delete_data(neg, cur); 743b7579f77SDag-Erling Smørgrav walk = next; 744b7579f77SDag-Erling Smørgrav } 745b7579f77SDag-Erling Smørgrav } 746b7579f77SDag-Erling Smørgrav 747b7579f77SDag-Erling Smørgrav void neg_insert_data(struct val_neg_cache* neg, 748b7579f77SDag-Erling Smørgrav struct val_neg_zone* zone, struct ub_packed_rrset_key* nsec) 749b7579f77SDag-Erling Smørgrav { 750b7579f77SDag-Erling Smørgrav struct packed_rrset_data* d; 751b7579f77SDag-Erling Smørgrav struct val_neg_data* parent; 752b7579f77SDag-Erling Smørgrav struct val_neg_data* el; 753b7579f77SDag-Erling Smørgrav uint8_t* nm = nsec->rk.dname; 754b7579f77SDag-Erling Smørgrav size_t nm_len = nsec->rk.dname_len; 755b7579f77SDag-Erling Smørgrav int labs = dname_count_labels(nsec->rk.dname); 756b7579f77SDag-Erling Smørgrav 757b7579f77SDag-Erling Smørgrav d = (struct packed_rrset_data*)nsec->entry.data; 758b7579f77SDag-Erling Smørgrav if( !(d->security == sec_status_secure || 759b7579f77SDag-Erling Smørgrav (d->security == sec_status_unchecked && d->rrsig_count > 0))) 760b7579f77SDag-Erling Smørgrav return; 761b7579f77SDag-Erling Smørgrav log_nametypeclass(VERB_ALGO, "negcache rr", 762b7579f77SDag-Erling Smørgrav nsec->rk.dname, ntohs(nsec->rk.type), 763b7579f77SDag-Erling Smørgrav ntohs(nsec->rk.rrset_class)); 764b7579f77SDag-Erling Smørgrav 765b7579f77SDag-Erling Smørgrav /* find closest enclosing parent data that (still) exists */ 766b7579f77SDag-Erling Smørgrav parent = neg_closest_data_parent(zone, nm, nm_len, labs); 767b7579f77SDag-Erling Smørgrav if(parent && query_dname_compare(parent->name, nm) == 0) { 768b7579f77SDag-Erling Smørgrav /* perfect match already exists */ 769b7579f77SDag-Erling Smørgrav log_assert(parent->count > 0); 770b7579f77SDag-Erling Smørgrav el = parent; 771b7579f77SDag-Erling Smørgrav } else { 772b7579f77SDag-Erling Smørgrav struct val_neg_data* p, *np; 773b7579f77SDag-Erling Smørgrav 774b7579f77SDag-Erling Smørgrav /* create subtree for perfect match */ 775b7579f77SDag-Erling Smørgrav /* if parent exists, it is in use */ 776b7579f77SDag-Erling Smørgrav log_assert(!parent || parent->count > 0); 777b7579f77SDag-Erling Smørgrav 778b7579f77SDag-Erling Smørgrav el = neg_data_chain(nm, nm_len, labs, parent); 779b7579f77SDag-Erling Smørgrav if(!el) { 780b7579f77SDag-Erling Smørgrav log_err("out of memory inserting NSEC negative cache"); 781b7579f77SDag-Erling Smørgrav return; 782b7579f77SDag-Erling Smørgrav } 783b7579f77SDag-Erling Smørgrav el->in_use = 0; /* set on below */ 784b7579f77SDag-Erling Smørgrav 785b7579f77SDag-Erling Smørgrav /* insert the list of zones into the tree */ 786b7579f77SDag-Erling Smørgrav p = el; 787b7579f77SDag-Erling Smørgrav while(p) { 788b7579f77SDag-Erling Smørgrav np = p->parent; 789b7579f77SDag-Erling Smørgrav /* mem use */ 790b7579f77SDag-Erling Smørgrav neg->use += sizeof(struct val_neg_data) + p->len; 791b7579f77SDag-Erling Smørgrav /* insert in tree */ 792b7579f77SDag-Erling Smørgrav p->zone = zone; 793b7579f77SDag-Erling Smørgrav (void)rbtree_insert(&zone->tree, &p->node); 794b7579f77SDag-Erling Smørgrav /* last one needs proper parent pointer */ 795b7579f77SDag-Erling Smørgrav if(np == NULL) 796b7579f77SDag-Erling Smørgrav p->parent = parent; 797b7579f77SDag-Erling Smørgrav p = np; 798b7579f77SDag-Erling Smørgrav } 799b7579f77SDag-Erling Smørgrav } 800b7579f77SDag-Erling Smørgrav 801b7579f77SDag-Erling Smørgrav if(!el->in_use) { 802b7579f77SDag-Erling Smørgrav struct val_neg_data* p; 803b7579f77SDag-Erling Smørgrav 804b7579f77SDag-Erling Smørgrav el->in_use = 1; 805b7579f77SDag-Erling Smørgrav /* increase usage count of all parents */ 806b7579f77SDag-Erling Smørgrav for(p=el; p; p = p->parent) { 807b7579f77SDag-Erling Smørgrav p->count++; 808b7579f77SDag-Erling Smørgrav } 809b7579f77SDag-Erling Smørgrav 810b7579f77SDag-Erling Smørgrav neg_lru_front(neg, el); 811b7579f77SDag-Erling Smørgrav } else { 812b7579f77SDag-Erling Smørgrav /* in use, bring to front, lru */ 813b7579f77SDag-Erling Smørgrav neg_lru_touch(neg, el); 814b7579f77SDag-Erling Smørgrav } 815b7579f77SDag-Erling Smørgrav 816b7579f77SDag-Erling Smørgrav /* if nsec3 store last used parameters */ 817b7579f77SDag-Erling Smørgrav if(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC3) { 818b7579f77SDag-Erling Smørgrav int h; 819b7579f77SDag-Erling Smørgrav uint8_t* s; 820b7579f77SDag-Erling Smørgrav size_t slen, it; 821b7579f77SDag-Erling Smørgrav if(nsec3_get_params(nsec, 0, &h, &it, &s, &slen) && 822b7579f77SDag-Erling Smørgrav it <= neg->nsec3_max_iter && 823b7579f77SDag-Erling Smørgrav (h != zone->nsec3_hash || it != zone->nsec3_iter || 824b7579f77SDag-Erling Smørgrav slen != zone->nsec3_saltlen || 825b7579f77SDag-Erling Smørgrav memcmp(zone->nsec3_salt, s, slen) != 0)) { 826*f61ef7f6SDag-Erling Smørgrav 827*f61ef7f6SDag-Erling Smørgrav if(slen > 0) { 828b7579f77SDag-Erling Smørgrav uint8_t* sa = memdup(s, slen); 829b7579f77SDag-Erling Smørgrav if(sa) { 830b7579f77SDag-Erling Smørgrav free(zone->nsec3_salt); 831b7579f77SDag-Erling Smørgrav zone->nsec3_salt = sa; 832b7579f77SDag-Erling Smørgrav zone->nsec3_saltlen = slen; 833b7579f77SDag-Erling Smørgrav zone->nsec3_iter = it; 834*f61ef7f6SDag-Erling Smørgrav zone->nsec3_hash = h; 835*f61ef7f6SDag-Erling Smørgrav } 836*f61ef7f6SDag-Erling Smørgrav } else { 837*f61ef7f6SDag-Erling Smørgrav free(zone->nsec3_salt); 838*f61ef7f6SDag-Erling Smørgrav zone->nsec3_salt = NULL; 839*f61ef7f6SDag-Erling Smørgrav zone->nsec3_saltlen = 0; 840*f61ef7f6SDag-Erling Smørgrav zone->nsec3_iter = it; 841*f61ef7f6SDag-Erling Smørgrav zone->nsec3_hash = h; 842b7579f77SDag-Erling Smørgrav } 843b7579f77SDag-Erling Smørgrav } 844b7579f77SDag-Erling Smørgrav } 845b7579f77SDag-Erling Smørgrav 846b7579f77SDag-Erling Smørgrav /* wipe out the cache items between NSEC start and end */ 847b7579f77SDag-Erling Smørgrav wipeout(neg, zone, el, nsec); 848b7579f77SDag-Erling Smørgrav } 849b7579f77SDag-Erling Smørgrav 850b7579f77SDag-Erling Smørgrav void val_neg_addreply(struct val_neg_cache* neg, struct reply_info* rep) 851b7579f77SDag-Erling Smørgrav { 852b7579f77SDag-Erling Smørgrav size_t i, need; 853b7579f77SDag-Erling Smørgrav struct ub_packed_rrset_key* soa; 854b7579f77SDag-Erling Smørgrav struct val_neg_zone* zone; 855b7579f77SDag-Erling Smørgrav /* see if secure nsecs inside */ 856b7579f77SDag-Erling Smørgrav if(!reply_has_nsec(rep)) 857b7579f77SDag-Erling Smørgrav return; 858b7579f77SDag-Erling Smørgrav /* find the zone name in message */ 859b7579f77SDag-Erling Smørgrav soa = reply_find_soa(rep); 860b7579f77SDag-Erling Smørgrav if(!soa) 861b7579f77SDag-Erling Smørgrav return; 862b7579f77SDag-Erling Smørgrav 863b7579f77SDag-Erling Smørgrav log_nametypeclass(VERB_ALGO, "negcache insert for zone", 864b7579f77SDag-Erling Smørgrav soa->rk.dname, LDNS_RR_TYPE_SOA, ntohs(soa->rk.rrset_class)); 865b7579f77SDag-Erling Smørgrav 866b7579f77SDag-Erling Smørgrav /* ask for enough space to store all of it */ 867b7579f77SDag-Erling Smørgrav need = calc_data_need(rep) + 868b7579f77SDag-Erling Smørgrav calc_zone_need(soa->rk.dname, soa->rk.dname_len); 869b7579f77SDag-Erling Smørgrav lock_basic_lock(&neg->lock); 870b7579f77SDag-Erling Smørgrav neg_make_space(neg, need); 871b7579f77SDag-Erling Smørgrav 872b7579f77SDag-Erling Smørgrav /* find or create the zone entry */ 873b7579f77SDag-Erling Smørgrav zone = neg_find_zone(neg, soa->rk.dname, soa->rk.dname_len, 874b7579f77SDag-Erling Smørgrav ntohs(soa->rk.rrset_class)); 875b7579f77SDag-Erling Smørgrav if(!zone) { 876b7579f77SDag-Erling Smørgrav if(!(zone = neg_create_zone(neg, soa->rk.dname, 877b7579f77SDag-Erling Smørgrav soa->rk.dname_len, ntohs(soa->rk.rrset_class)))) { 878b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 879b7579f77SDag-Erling Smørgrav log_err("out of memory adding negative zone"); 880b7579f77SDag-Erling Smørgrav return; 881b7579f77SDag-Erling Smørgrav } 882b7579f77SDag-Erling Smørgrav } 883b7579f77SDag-Erling Smørgrav val_neg_zone_take_inuse(zone); 884b7579f77SDag-Erling Smørgrav 885b7579f77SDag-Erling Smørgrav /* insert the NSECs */ 886b7579f77SDag-Erling Smørgrav for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 887b7579f77SDag-Erling Smørgrav if(ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC) 888b7579f77SDag-Erling Smørgrav continue; 889b7579f77SDag-Erling Smørgrav if(!dname_subdomain_c(rep->rrsets[i]->rk.dname, 890b7579f77SDag-Erling Smørgrav zone->name)) continue; 891b7579f77SDag-Erling Smørgrav /* insert NSEC into this zone's tree */ 892b7579f77SDag-Erling Smørgrav neg_insert_data(neg, zone, rep->rrsets[i]); 893b7579f77SDag-Erling Smørgrav } 894b7579f77SDag-Erling Smørgrav if(zone->tree.count == 0) { 895b7579f77SDag-Erling Smørgrav /* remove empty zone if inserts failed */ 896b7579f77SDag-Erling Smørgrav neg_delete_zone(neg, zone); 897b7579f77SDag-Erling Smørgrav } 898b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 899b7579f77SDag-Erling Smørgrav } 900b7579f77SDag-Erling Smørgrav 901b7579f77SDag-Erling Smørgrav /** 902b7579f77SDag-Erling Smørgrav * Lookup closest data record. For NSEC denial. 903b7579f77SDag-Erling Smørgrav * @param zone: zone to look in 904b7579f77SDag-Erling Smørgrav * @param qname: name to look for. 905b7579f77SDag-Erling Smørgrav * @param len: length of name 906b7579f77SDag-Erling Smørgrav * @param labs: labels in name 907b7579f77SDag-Erling Smørgrav * @param data: data element, exact or smaller or NULL 908b7579f77SDag-Erling Smørgrav * @return true if exact match. 909b7579f77SDag-Erling Smørgrav */ 910b7579f77SDag-Erling Smørgrav static int neg_closest_data(struct val_neg_zone* zone, 911b7579f77SDag-Erling Smørgrav uint8_t* qname, size_t len, int labs, struct val_neg_data** data) 912b7579f77SDag-Erling Smørgrav { 913b7579f77SDag-Erling Smørgrav struct val_neg_data key; 914b7579f77SDag-Erling Smørgrav rbnode_t* r; 915b7579f77SDag-Erling Smørgrav key.node.key = &key; 916b7579f77SDag-Erling Smørgrav key.name = qname; 917b7579f77SDag-Erling Smørgrav key.len = len; 918b7579f77SDag-Erling Smørgrav key.labs = labs; 919b7579f77SDag-Erling Smørgrav if(rbtree_find_less_equal(&zone->tree, &key, &r)) { 920b7579f77SDag-Erling Smørgrav /* exact match */ 921b7579f77SDag-Erling Smørgrav *data = (struct val_neg_data*)r; 922b7579f77SDag-Erling Smørgrav return 1; 923b7579f77SDag-Erling Smørgrav } else { 924b7579f77SDag-Erling Smørgrav /* smaller match */ 925b7579f77SDag-Erling Smørgrav *data = (struct val_neg_data*)r; 926b7579f77SDag-Erling Smørgrav return 0; 927b7579f77SDag-Erling Smørgrav } 928b7579f77SDag-Erling Smørgrav } 929b7579f77SDag-Erling Smørgrav 930b7579f77SDag-Erling Smørgrav int val_neg_dlvlookup(struct val_neg_cache* neg, uint8_t* qname, size_t len, 93117d15b25SDag-Erling Smørgrav uint16_t qclass, struct rrset_cache* rrset_cache, time_t now) 932b7579f77SDag-Erling Smørgrav { 933b7579f77SDag-Erling Smørgrav /* lookup closest zone */ 934b7579f77SDag-Erling Smørgrav struct val_neg_zone* zone; 935b7579f77SDag-Erling Smørgrav struct val_neg_data* data; 936b7579f77SDag-Erling Smørgrav int labs; 937b7579f77SDag-Erling Smørgrav struct ub_packed_rrset_key* nsec; 938b7579f77SDag-Erling Smørgrav struct packed_rrset_data* d; 939b7579f77SDag-Erling Smørgrav uint32_t flags; 940b7579f77SDag-Erling Smørgrav uint8_t* wc; 941b7579f77SDag-Erling Smørgrav struct query_info qinfo; 942b7579f77SDag-Erling Smørgrav if(!neg) return 0; 943b7579f77SDag-Erling Smørgrav 944b7579f77SDag-Erling Smørgrav log_nametypeclass(VERB_ALGO, "negcache dlvlookup", qname, 945b7579f77SDag-Erling Smørgrav LDNS_RR_TYPE_DLV, qclass); 946b7579f77SDag-Erling Smørgrav 947b7579f77SDag-Erling Smørgrav labs = dname_count_labels(qname); 948b7579f77SDag-Erling Smørgrav lock_basic_lock(&neg->lock); 949b7579f77SDag-Erling Smørgrav zone = neg_closest_zone_parent(neg, qname, len, labs, qclass); 950b7579f77SDag-Erling Smørgrav while(zone && !zone->in_use) 951b7579f77SDag-Erling Smørgrav zone = zone->parent; 952b7579f77SDag-Erling Smørgrav if(!zone) { 953b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 954b7579f77SDag-Erling Smørgrav return 0; 955b7579f77SDag-Erling Smørgrav } 956b7579f77SDag-Erling Smørgrav log_nametypeclass(VERB_ALGO, "negcache zone", zone->name, 0, 957b7579f77SDag-Erling Smørgrav zone->dclass); 958b7579f77SDag-Erling Smørgrav 959b7579f77SDag-Erling Smørgrav /* DLV is defined to use NSEC only */ 960b7579f77SDag-Erling Smørgrav if(zone->nsec3_hash) { 961b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 962b7579f77SDag-Erling Smørgrav return 0; 963b7579f77SDag-Erling Smørgrav } 964b7579f77SDag-Erling Smørgrav 965b7579f77SDag-Erling Smørgrav /* lookup closest data record */ 966b7579f77SDag-Erling Smørgrav (void)neg_closest_data(zone, qname, len, labs, &data); 967b7579f77SDag-Erling Smørgrav while(data && !data->in_use) 968b7579f77SDag-Erling Smørgrav data = data->parent; 969b7579f77SDag-Erling Smørgrav if(!data) { 970b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 971b7579f77SDag-Erling Smørgrav return 0; 972b7579f77SDag-Erling Smørgrav } 973b7579f77SDag-Erling Smørgrav log_nametypeclass(VERB_ALGO, "negcache rr", data->name, 974b7579f77SDag-Erling Smørgrav LDNS_RR_TYPE_NSEC, zone->dclass); 975b7579f77SDag-Erling Smørgrav 976b7579f77SDag-Erling Smørgrav /* lookup rrset in rrset cache */ 977b7579f77SDag-Erling Smørgrav flags = 0; 978b7579f77SDag-Erling Smørgrav if(query_dname_compare(data->name, zone->name) == 0) 979b7579f77SDag-Erling Smørgrav flags = PACKED_RRSET_NSEC_AT_APEX; 980b7579f77SDag-Erling Smørgrav nsec = rrset_cache_lookup(rrset_cache, data->name, data->len, 981b7579f77SDag-Erling Smørgrav LDNS_RR_TYPE_NSEC, zone->dclass, flags, now, 0); 982b7579f77SDag-Erling Smørgrav 983b7579f77SDag-Erling Smørgrav /* check if secure and TTL ok */ 984b7579f77SDag-Erling Smørgrav if(!nsec) { 985b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 986b7579f77SDag-Erling Smørgrav return 0; 987b7579f77SDag-Erling Smørgrav } 988b7579f77SDag-Erling Smørgrav d = (struct packed_rrset_data*)nsec->entry.data; 989b7579f77SDag-Erling Smørgrav if(!d || now > d->ttl) { 990b7579f77SDag-Erling Smørgrav lock_rw_unlock(&nsec->entry.lock); 991b7579f77SDag-Erling Smørgrav /* delete data record if expired */ 992b7579f77SDag-Erling Smørgrav neg_delete_data(neg, data); 993b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 994b7579f77SDag-Erling Smørgrav return 0; 995b7579f77SDag-Erling Smørgrav } 996b7579f77SDag-Erling Smørgrav if(d->security != sec_status_secure) { 997b7579f77SDag-Erling Smørgrav lock_rw_unlock(&nsec->entry.lock); 998b7579f77SDag-Erling Smørgrav neg_delete_data(neg, data); 999b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 1000b7579f77SDag-Erling Smørgrav return 0; 1001b7579f77SDag-Erling Smørgrav } 1002b7579f77SDag-Erling Smørgrav verbose(VERB_ALGO, "negcache got secure rrset"); 1003b7579f77SDag-Erling Smørgrav 1004b7579f77SDag-Erling Smørgrav /* check NSEC security */ 1005b7579f77SDag-Erling Smørgrav /* check if NSEC proves no DLV type exists */ 1006b7579f77SDag-Erling Smørgrav /* check if NSEC proves NXDOMAIN for qname */ 1007b7579f77SDag-Erling Smørgrav qinfo.qname = qname; 1008b7579f77SDag-Erling Smørgrav qinfo.qtype = LDNS_RR_TYPE_DLV; 1009b7579f77SDag-Erling Smørgrav qinfo.qclass = qclass; 1010b7579f77SDag-Erling Smørgrav if(!nsec_proves_nodata(nsec, &qinfo, &wc) && 1011b7579f77SDag-Erling Smørgrav !val_nsec_proves_name_error(nsec, qname)) { 1012b7579f77SDag-Erling Smørgrav /* the NSEC is not a denial for the DLV */ 1013b7579f77SDag-Erling Smørgrav lock_rw_unlock(&nsec->entry.lock); 1014b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 1015b7579f77SDag-Erling Smørgrav verbose(VERB_ALGO, "negcache not proven"); 1016b7579f77SDag-Erling Smørgrav return 0; 1017b7579f77SDag-Erling Smørgrav } 1018b7579f77SDag-Erling Smørgrav /* so the NSEC was a NODATA proof, or NXDOMAIN proof. */ 1019b7579f77SDag-Erling Smørgrav 1020b7579f77SDag-Erling Smørgrav /* no need to check for wildcard NSEC; no wildcards in DLV repos */ 1021b7579f77SDag-Erling Smørgrav /* no need to lookup SOA record for client; no response message */ 1022b7579f77SDag-Erling Smørgrav 1023b7579f77SDag-Erling Smørgrav lock_rw_unlock(&nsec->entry.lock); 1024b7579f77SDag-Erling Smørgrav /* if OK touch the LRU for neg_data element */ 1025b7579f77SDag-Erling Smørgrav neg_lru_touch(neg, data); 1026b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 1027b7579f77SDag-Erling Smørgrav verbose(VERB_ALGO, "negcache DLV denial proven"); 1028b7579f77SDag-Erling Smørgrav return 1; 1029b7579f77SDag-Erling Smørgrav } 1030b7579f77SDag-Erling Smørgrav 1031b7579f77SDag-Erling Smørgrav /** see if the reply has signed NSEC records and return the signer */ 1032b7579f77SDag-Erling Smørgrav static uint8_t* reply_nsec_signer(struct reply_info* rep, size_t* signer_len, 1033b7579f77SDag-Erling Smørgrav uint16_t* dclass) 1034b7579f77SDag-Erling Smørgrav { 1035b7579f77SDag-Erling Smørgrav size_t i; 1036b7579f77SDag-Erling Smørgrav struct packed_rrset_data* d; 1037b7579f77SDag-Erling Smørgrav uint8_t* s; 1038b7579f77SDag-Erling Smørgrav for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 1039b7579f77SDag-Erling Smørgrav if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC || 1040b7579f77SDag-Erling Smørgrav ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC3) { 1041b7579f77SDag-Erling Smørgrav d = (struct packed_rrset_data*)rep->rrsets[i]-> 1042b7579f77SDag-Erling Smørgrav entry.data; 1043b7579f77SDag-Erling Smørgrav /* return first signer name of first NSEC */ 1044b7579f77SDag-Erling Smørgrav if(d->rrsig_count != 0) { 1045b7579f77SDag-Erling Smørgrav val_find_rrset_signer(rep->rrsets[i], 1046b7579f77SDag-Erling Smørgrav &s, signer_len); 1047b7579f77SDag-Erling Smørgrav if(s && *signer_len) { 1048b7579f77SDag-Erling Smørgrav *dclass = ntohs(rep->rrsets[i]-> 1049b7579f77SDag-Erling Smørgrav rk.rrset_class); 1050b7579f77SDag-Erling Smørgrav return s; 1051b7579f77SDag-Erling Smørgrav } 1052b7579f77SDag-Erling Smørgrav } 1053b7579f77SDag-Erling Smørgrav } 1054b7579f77SDag-Erling Smørgrav } 1055b7579f77SDag-Erling Smørgrav return 0; 1056b7579f77SDag-Erling Smørgrav } 1057b7579f77SDag-Erling Smørgrav 1058b7579f77SDag-Erling Smørgrav void val_neg_addreferral(struct val_neg_cache* neg, struct reply_info* rep, 1059b7579f77SDag-Erling Smørgrav uint8_t* zone_name) 1060b7579f77SDag-Erling Smørgrav { 1061b7579f77SDag-Erling Smørgrav size_t i, need; 1062b7579f77SDag-Erling Smørgrav uint8_t* signer; 1063b7579f77SDag-Erling Smørgrav size_t signer_len; 1064b7579f77SDag-Erling Smørgrav uint16_t dclass; 1065b7579f77SDag-Erling Smørgrav struct val_neg_zone* zone; 1066b7579f77SDag-Erling Smørgrav /* no SOA in this message, find RRSIG over NSEC's signer name. 1067b7579f77SDag-Erling Smørgrav * note the NSEC records are maybe not validated yet */ 1068b7579f77SDag-Erling Smørgrav signer = reply_nsec_signer(rep, &signer_len, &dclass); 1069b7579f77SDag-Erling Smørgrav if(!signer) 1070b7579f77SDag-Erling Smørgrav return; 1071b7579f77SDag-Erling Smørgrav if(!dname_subdomain_c(signer, zone_name)) { 1072b7579f77SDag-Erling Smørgrav /* the signer is not in the bailiwick, throw it out */ 1073b7579f77SDag-Erling Smørgrav return; 1074b7579f77SDag-Erling Smørgrav } 1075b7579f77SDag-Erling Smørgrav 1076b7579f77SDag-Erling Smørgrav log_nametypeclass(VERB_ALGO, "negcache insert referral ", 1077b7579f77SDag-Erling Smørgrav signer, LDNS_RR_TYPE_NS, dclass); 1078b7579f77SDag-Erling Smørgrav 1079b7579f77SDag-Erling Smørgrav /* ask for enough space to store all of it */ 1080b7579f77SDag-Erling Smørgrav need = calc_data_need(rep) + calc_zone_need(signer, signer_len); 1081b7579f77SDag-Erling Smørgrav lock_basic_lock(&neg->lock); 1082b7579f77SDag-Erling Smørgrav neg_make_space(neg, need); 1083b7579f77SDag-Erling Smørgrav 1084b7579f77SDag-Erling Smørgrav /* find or create the zone entry */ 1085b7579f77SDag-Erling Smørgrav zone = neg_find_zone(neg, signer, signer_len, dclass); 1086b7579f77SDag-Erling Smørgrav if(!zone) { 1087b7579f77SDag-Erling Smørgrav if(!(zone = neg_create_zone(neg, signer, signer_len, 1088b7579f77SDag-Erling Smørgrav dclass))) { 1089b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 1090b7579f77SDag-Erling Smørgrav log_err("out of memory adding negative zone"); 1091b7579f77SDag-Erling Smørgrav return; 1092b7579f77SDag-Erling Smørgrav } 1093b7579f77SDag-Erling Smørgrav } 1094b7579f77SDag-Erling Smørgrav val_neg_zone_take_inuse(zone); 1095b7579f77SDag-Erling Smørgrav 1096b7579f77SDag-Erling Smørgrav /* insert the NSECs */ 1097b7579f77SDag-Erling Smørgrav for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){ 1098b7579f77SDag-Erling Smørgrav if(ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC && 1099b7579f77SDag-Erling Smørgrav ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC3) 1100b7579f77SDag-Erling Smørgrav continue; 1101b7579f77SDag-Erling Smørgrav if(!dname_subdomain_c(rep->rrsets[i]->rk.dname, 1102b7579f77SDag-Erling Smørgrav zone->name)) continue; 1103b7579f77SDag-Erling Smørgrav /* insert NSEC into this zone's tree */ 1104b7579f77SDag-Erling Smørgrav neg_insert_data(neg, zone, rep->rrsets[i]); 1105b7579f77SDag-Erling Smørgrav } 1106b7579f77SDag-Erling Smørgrav if(zone->tree.count == 0) { 1107b7579f77SDag-Erling Smørgrav /* remove empty zone if inserts failed */ 1108b7579f77SDag-Erling Smørgrav neg_delete_zone(neg, zone); 1109b7579f77SDag-Erling Smørgrav } 1110b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 1111b7579f77SDag-Erling Smørgrav } 1112b7579f77SDag-Erling Smørgrav 1113b7579f77SDag-Erling Smørgrav /** 1114b7579f77SDag-Erling Smørgrav * Check that an NSEC3 rrset does not have a type set. 1115b7579f77SDag-Erling Smørgrav * None of the nsec3s in a hash-collision are allowed to have the type. 1116b7579f77SDag-Erling Smørgrav * (since we do not know which one is the nsec3 looked at, flags, ..., we 1117b7579f77SDag-Erling Smørgrav * ignore the cached item and let it bypass negative caching). 1118b7579f77SDag-Erling Smørgrav * @param k: the nsec3 rrset to check. 1119b7579f77SDag-Erling Smørgrav * @param t: type to check 1120b7579f77SDag-Erling Smørgrav * @return true if no RRs have the type. 1121b7579f77SDag-Erling Smørgrav */ 1122b7579f77SDag-Erling Smørgrav static int nsec3_no_type(struct ub_packed_rrset_key* k, uint16_t t) 1123b7579f77SDag-Erling Smørgrav { 1124b7579f77SDag-Erling Smørgrav int count = (int)((struct packed_rrset_data*)k->entry.data)->count; 1125b7579f77SDag-Erling Smørgrav int i; 1126b7579f77SDag-Erling Smørgrav for(i=0; i<count; i++) 1127b7579f77SDag-Erling Smørgrav if(nsec3_has_type(k, i, t)) 1128b7579f77SDag-Erling Smørgrav return 0; 1129b7579f77SDag-Erling Smørgrav return 1; 1130b7579f77SDag-Erling Smørgrav } 1131b7579f77SDag-Erling Smørgrav 1132b7579f77SDag-Erling Smørgrav /** 1133b7579f77SDag-Erling Smørgrav * See if rrset exists in rrset cache. 1134b7579f77SDag-Erling Smørgrav * If it does, the bit is checked, and if not expired, it is returned 1135b7579f77SDag-Erling Smørgrav * allocated in region. 1136b7579f77SDag-Erling Smørgrav * @param rrset_cache: rrset cache 1137b7579f77SDag-Erling Smørgrav * @param qname: to lookup rrset name 1138b7579f77SDag-Erling Smørgrav * @param qname_len: length of qname. 1139b7579f77SDag-Erling Smørgrav * @param qtype: type of rrset to lookup, host order 1140b7579f77SDag-Erling Smørgrav * @param qclass: class of rrset to lookup, host order 1141b7579f77SDag-Erling Smørgrav * @param flags: flags for rrset to lookup 1142b7579f77SDag-Erling Smørgrav * @param region: where to alloc result 1143b7579f77SDag-Erling Smørgrav * @param checkbit: if true, a bit in the nsec typemap is checked for absence. 1144b7579f77SDag-Erling Smørgrav * @param checktype: which bit to check 1145b7579f77SDag-Erling Smørgrav * @param now: to check ttl against 1146b7579f77SDag-Erling Smørgrav * @return rrset or NULL 1147b7579f77SDag-Erling Smørgrav */ 1148b7579f77SDag-Erling Smørgrav static struct ub_packed_rrset_key* 1149b7579f77SDag-Erling Smørgrav grab_nsec(struct rrset_cache* rrset_cache, uint8_t* qname, size_t qname_len, 1150b7579f77SDag-Erling Smørgrav uint16_t qtype, uint16_t qclass, uint32_t flags, 1151b7579f77SDag-Erling Smørgrav struct regional* region, int checkbit, uint16_t checktype, 115217d15b25SDag-Erling Smørgrav time_t now) 1153b7579f77SDag-Erling Smørgrav { 1154b7579f77SDag-Erling Smørgrav struct ub_packed_rrset_key* r, *k = rrset_cache_lookup(rrset_cache, 1155b7579f77SDag-Erling Smørgrav qname, qname_len, qtype, qclass, flags, now, 0); 1156b7579f77SDag-Erling Smørgrav struct packed_rrset_data* d; 1157b7579f77SDag-Erling Smørgrav if(!k) return NULL; 1158b7579f77SDag-Erling Smørgrav d = (struct packed_rrset_data*)k->entry.data; 1159b7579f77SDag-Erling Smørgrav if(d->ttl < now) { 1160b7579f77SDag-Erling Smørgrav lock_rw_unlock(&k->entry.lock); 1161b7579f77SDag-Erling Smørgrav return NULL; 1162b7579f77SDag-Erling Smørgrav } 1163b7579f77SDag-Erling Smørgrav /* only secure or unchecked records that have signatures. */ 1164b7579f77SDag-Erling Smørgrav if( ! ( d->security == sec_status_secure || 1165b7579f77SDag-Erling Smørgrav (d->security == sec_status_unchecked && 1166b7579f77SDag-Erling Smørgrav d->rrsig_count > 0) ) ) { 1167b7579f77SDag-Erling Smørgrav lock_rw_unlock(&k->entry.lock); 1168b7579f77SDag-Erling Smørgrav return NULL; 1169b7579f77SDag-Erling Smørgrav } 1170b7579f77SDag-Erling Smørgrav /* check if checktype is absent */ 1171b7579f77SDag-Erling Smørgrav if(checkbit && ( 1172b7579f77SDag-Erling Smørgrav (qtype == LDNS_RR_TYPE_NSEC && nsec_has_type(k, checktype)) || 1173b7579f77SDag-Erling Smørgrav (qtype == LDNS_RR_TYPE_NSEC3 && !nsec3_no_type(k, checktype)) 1174b7579f77SDag-Erling Smørgrav )) { 1175b7579f77SDag-Erling Smørgrav lock_rw_unlock(&k->entry.lock); 1176b7579f77SDag-Erling Smørgrav return NULL; 1177b7579f77SDag-Erling Smørgrav } 1178b7579f77SDag-Erling Smørgrav /* looks OK! copy to region and return it */ 1179b7579f77SDag-Erling Smørgrav r = packed_rrset_copy_region(k, region, now); 1180b7579f77SDag-Erling Smørgrav /* if it failed, we return the NULL */ 1181b7579f77SDag-Erling Smørgrav lock_rw_unlock(&k->entry.lock); 1182b7579f77SDag-Erling Smørgrav return r; 1183b7579f77SDag-Erling Smørgrav } 1184b7579f77SDag-Erling Smørgrav 1185b7579f77SDag-Erling Smørgrav /** find nsec3 closest encloser in neg cache */ 1186b7579f77SDag-Erling Smørgrav static struct val_neg_data* 1187b7579f77SDag-Erling Smørgrav neg_find_nsec3_ce(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len, 118817d15b25SDag-Erling Smørgrav int qlabs, sldns_buffer* buf, uint8_t* hashnc, size_t* nclen) 1189b7579f77SDag-Erling Smørgrav { 1190b7579f77SDag-Erling Smørgrav struct val_neg_data* data; 11918ed2b524SDag-Erling Smørgrav uint8_t hashce[NSEC3_SHA_LEN]; 1192b7579f77SDag-Erling Smørgrav uint8_t b32[257]; 1193b7579f77SDag-Erling Smørgrav size_t celen, b32len; 1194b7579f77SDag-Erling Smørgrav 1195b7579f77SDag-Erling Smørgrav *nclen = 0; 1196b7579f77SDag-Erling Smørgrav while(qlabs > 0) { 1197b7579f77SDag-Erling Smørgrav /* hash */ 1198b7579f77SDag-Erling Smørgrav if(!(celen=nsec3_get_hashed(buf, qname, qname_len, 1199b7579f77SDag-Erling Smørgrav zone->nsec3_hash, zone->nsec3_iter, zone->nsec3_salt, 1200b7579f77SDag-Erling Smørgrav zone->nsec3_saltlen, hashce, sizeof(hashce)))) 1201b7579f77SDag-Erling Smørgrav return NULL; 1202b7579f77SDag-Erling Smørgrav if(!(b32len=nsec3_hash_to_b32(hashce, celen, zone->name, 1203b7579f77SDag-Erling Smørgrav zone->len, b32, sizeof(b32)))) 1204b7579f77SDag-Erling Smørgrav return NULL; 1205b7579f77SDag-Erling Smørgrav 1206b7579f77SDag-Erling Smørgrav /* lookup (exact match only) */ 1207b7579f77SDag-Erling Smørgrav data = neg_find_data(zone, b32, b32len, zone->labs+1); 1208b7579f77SDag-Erling Smørgrav if(data && data->in_use) { 1209b7579f77SDag-Erling Smørgrav /* found ce match! */ 1210b7579f77SDag-Erling Smørgrav return data; 1211b7579f77SDag-Erling Smørgrav } 1212b7579f77SDag-Erling Smørgrav 1213b7579f77SDag-Erling Smørgrav *nclen = celen; 1214b7579f77SDag-Erling Smørgrav memmove(hashnc, hashce, celen); 1215b7579f77SDag-Erling Smørgrav dname_remove_label(&qname, &qname_len); 1216b7579f77SDag-Erling Smørgrav qlabs --; 1217b7579f77SDag-Erling Smørgrav } 1218b7579f77SDag-Erling Smørgrav return NULL; 1219b7579f77SDag-Erling Smørgrav } 1220b7579f77SDag-Erling Smørgrav 1221b7579f77SDag-Erling Smørgrav /** check nsec3 parameters on nsec3 rrset with current zone values */ 1222b7579f77SDag-Erling Smørgrav static int 1223b7579f77SDag-Erling Smørgrav neg_params_ok(struct val_neg_zone* zone, struct ub_packed_rrset_key* rrset) 1224b7579f77SDag-Erling Smørgrav { 1225b7579f77SDag-Erling Smørgrav int h; 1226b7579f77SDag-Erling Smørgrav uint8_t* s; 1227b7579f77SDag-Erling Smørgrav size_t slen, it; 1228b7579f77SDag-Erling Smørgrav if(!nsec3_get_params(rrset, 0, &h, &it, &s, &slen)) 1229b7579f77SDag-Erling Smørgrav return 0; 1230b7579f77SDag-Erling Smørgrav return (h == zone->nsec3_hash && it == zone->nsec3_iter && 1231b7579f77SDag-Erling Smørgrav slen == zone->nsec3_saltlen && 1232b7579f77SDag-Erling Smørgrav memcmp(zone->nsec3_salt, s, slen) == 0); 1233b7579f77SDag-Erling Smørgrav } 1234b7579f77SDag-Erling Smørgrav 1235b7579f77SDag-Erling Smørgrav /** get next closer for nsec3 proof */ 1236b7579f77SDag-Erling Smørgrav static struct ub_packed_rrset_key* 1237b7579f77SDag-Erling Smørgrav neg_nsec3_getnc(struct val_neg_zone* zone, uint8_t* hashnc, size_t nclen, 1238b7579f77SDag-Erling Smørgrav struct rrset_cache* rrset_cache, struct regional* region, 123917d15b25SDag-Erling Smørgrav time_t now, uint8_t* b32, size_t maxb32) 1240b7579f77SDag-Erling Smørgrav { 1241b7579f77SDag-Erling Smørgrav struct ub_packed_rrset_key* nc_rrset; 1242b7579f77SDag-Erling Smørgrav struct val_neg_data* data; 1243b7579f77SDag-Erling Smørgrav size_t b32len; 1244b7579f77SDag-Erling Smørgrav 1245b7579f77SDag-Erling Smørgrav if(!(b32len=nsec3_hash_to_b32(hashnc, nclen, zone->name, 1246b7579f77SDag-Erling Smørgrav zone->len, b32, maxb32))) 1247b7579f77SDag-Erling Smørgrav return NULL; 1248b7579f77SDag-Erling Smørgrav (void)neg_closest_data(zone, b32, b32len, zone->labs+1, &data); 1249b7579f77SDag-Erling Smørgrav if(!data && zone->tree.count != 0) { 1250b7579f77SDag-Erling Smørgrav /* could be before the first entry ; return the last 1251b7579f77SDag-Erling Smørgrav * entry (possibly the rollover nsec3 at end) */ 1252b7579f77SDag-Erling Smørgrav data = (struct val_neg_data*)rbtree_last(&zone->tree); 1253b7579f77SDag-Erling Smørgrav } 1254b7579f77SDag-Erling Smørgrav while(data && !data->in_use) 1255b7579f77SDag-Erling Smørgrav data = data->parent; 1256b7579f77SDag-Erling Smørgrav if(!data) 1257b7579f77SDag-Erling Smørgrav return NULL; 1258b7579f77SDag-Erling Smørgrav /* got a data element in tree, grab it */ 1259b7579f77SDag-Erling Smørgrav nc_rrset = grab_nsec(rrset_cache, data->name, data->len, 1260b7579f77SDag-Erling Smørgrav LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 0, 0, now); 1261b7579f77SDag-Erling Smørgrav if(!nc_rrset) 1262b7579f77SDag-Erling Smørgrav return NULL; 1263b7579f77SDag-Erling Smørgrav if(!neg_params_ok(zone, nc_rrset)) 1264b7579f77SDag-Erling Smørgrav return NULL; 1265b7579f77SDag-Erling Smørgrav return nc_rrset; 1266b7579f77SDag-Erling Smørgrav } 1267b7579f77SDag-Erling Smørgrav 1268b7579f77SDag-Erling Smørgrav /** neg cache nsec3 proof procedure*/ 1269b7579f77SDag-Erling Smørgrav static struct dns_msg* 1270b7579f77SDag-Erling Smørgrav neg_nsec3_proof_ds(struct val_neg_zone* zone, uint8_t* qname, size_t qname_len, 127117d15b25SDag-Erling Smørgrav int qlabs, sldns_buffer* buf, struct rrset_cache* rrset_cache, 127217d15b25SDag-Erling Smørgrav struct regional* region, time_t now, uint8_t* topname) 1273b7579f77SDag-Erling Smørgrav { 1274b7579f77SDag-Erling Smørgrav struct dns_msg* msg; 1275b7579f77SDag-Erling Smørgrav struct val_neg_data* data; 12768ed2b524SDag-Erling Smørgrav uint8_t hashnc[NSEC3_SHA_LEN]; 1277b7579f77SDag-Erling Smørgrav size_t nclen; 1278b7579f77SDag-Erling Smørgrav struct ub_packed_rrset_key* ce_rrset, *nc_rrset; 1279b7579f77SDag-Erling Smørgrav struct nsec3_cached_hash c; 1280b7579f77SDag-Erling Smørgrav uint8_t nc_b32[257]; 1281b7579f77SDag-Erling Smørgrav 1282b7579f77SDag-Erling Smørgrav /* for NSEC3 ; determine the closest encloser for which we 1283b7579f77SDag-Erling Smørgrav * can find an exact match. Remember the hashed lower name, 1284b7579f77SDag-Erling Smørgrav * since that is the one we need a closest match for. 1285b7579f77SDag-Erling Smørgrav * If we find a match straight away, then it becomes NODATA. 1286b7579f77SDag-Erling Smørgrav * Otherwise, NXDOMAIN or if OPTOUT, an insecure delegation. 1287b7579f77SDag-Erling Smørgrav * Also check that parameters are the same on closest encloser 1288b7579f77SDag-Erling Smørgrav * and on closest match. 1289b7579f77SDag-Erling Smørgrav */ 1290b7579f77SDag-Erling Smørgrav if(!zone->nsec3_hash) 1291b7579f77SDag-Erling Smørgrav return NULL; /* not nsec3 zone */ 1292b7579f77SDag-Erling Smørgrav 1293b7579f77SDag-Erling Smørgrav if(!(data=neg_find_nsec3_ce(zone, qname, qname_len, qlabs, buf, 1294b7579f77SDag-Erling Smørgrav hashnc, &nclen))) { 1295b7579f77SDag-Erling Smørgrav return NULL; 1296b7579f77SDag-Erling Smørgrav } 1297b7579f77SDag-Erling Smørgrav 1298b7579f77SDag-Erling Smørgrav /* grab the ce rrset */ 1299b7579f77SDag-Erling Smørgrav ce_rrset = grab_nsec(rrset_cache, data->name, data->len, 1300b7579f77SDag-Erling Smørgrav LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 1, 1301b7579f77SDag-Erling Smørgrav LDNS_RR_TYPE_DS, now); 1302b7579f77SDag-Erling Smørgrav if(!ce_rrset) 1303b7579f77SDag-Erling Smørgrav return NULL; 1304b7579f77SDag-Erling Smørgrav if(!neg_params_ok(zone, ce_rrset)) 1305b7579f77SDag-Erling Smørgrav return NULL; 1306b7579f77SDag-Erling Smørgrav 1307b7579f77SDag-Erling Smørgrav if(nclen == 0) { 1308b7579f77SDag-Erling Smørgrav /* exact match, just check the type bits */ 1309b7579f77SDag-Erling Smørgrav /* need: -SOA, -DS, +NS */ 1310b7579f77SDag-Erling Smørgrav if(nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_SOA) || 1311b7579f77SDag-Erling Smørgrav nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_DS) || 1312b7579f77SDag-Erling Smørgrav !nsec3_has_type(ce_rrset, 0, LDNS_RR_TYPE_NS)) 1313b7579f77SDag-Erling Smørgrav return NULL; 1314b7579f77SDag-Erling Smørgrav if(!(msg = dns_msg_create(qname, qname_len, 1315b7579f77SDag-Erling Smørgrav LDNS_RR_TYPE_DS, zone->dclass, region, 1))) 1316b7579f77SDag-Erling Smørgrav return NULL; 1317b7579f77SDag-Erling Smørgrav /* TTL reduced in grab_nsec */ 1318b7579f77SDag-Erling Smørgrav if(!dns_msg_authadd(msg, region, ce_rrset, 0)) 1319b7579f77SDag-Erling Smørgrav return NULL; 1320b7579f77SDag-Erling Smørgrav return msg; 1321b7579f77SDag-Erling Smørgrav } 1322b7579f77SDag-Erling Smørgrav 1323b7579f77SDag-Erling Smørgrav /* optout is not allowed without knowing the trust-anchor in use, 1324b7579f77SDag-Erling Smørgrav * otherwise the optout could spoof away that anchor */ 1325b7579f77SDag-Erling Smørgrav if(!topname) 1326b7579f77SDag-Erling Smørgrav return NULL; 1327b7579f77SDag-Erling Smørgrav 1328b7579f77SDag-Erling Smørgrav /* if there is no exact match, it must be in an optout span 1329b7579f77SDag-Erling Smørgrav * (an existing DS implies an NSEC3 must exist) */ 1330b7579f77SDag-Erling Smørgrav nc_rrset = neg_nsec3_getnc(zone, hashnc, nclen, rrset_cache, 1331b7579f77SDag-Erling Smørgrav region, now, nc_b32, sizeof(nc_b32)); 1332b7579f77SDag-Erling Smørgrav if(!nc_rrset) 1333b7579f77SDag-Erling Smørgrav return NULL; 1334b7579f77SDag-Erling Smørgrav if(!neg_params_ok(zone, nc_rrset)) 1335b7579f77SDag-Erling Smørgrav return NULL; 1336b7579f77SDag-Erling Smørgrav if(!nsec3_has_optout(nc_rrset, 0)) 1337b7579f77SDag-Erling Smørgrav return NULL; 1338b7579f77SDag-Erling Smørgrav c.hash = hashnc; 1339b7579f77SDag-Erling Smørgrav c.hash_len = nclen; 1340b7579f77SDag-Erling Smørgrav c.b32 = nc_b32+1; 1341b7579f77SDag-Erling Smørgrav c.b32_len = (size_t)nc_b32[0]; 1342b7579f77SDag-Erling Smørgrav if(nsec3_covers(zone->name, &c, nc_rrset, 0, buf)) { 1343b7579f77SDag-Erling Smørgrav /* nc_rrset covers the next closer name. 1344b7579f77SDag-Erling Smørgrav * ce_rrset equals a closer encloser. 1345b7579f77SDag-Erling Smørgrav * nc_rrset is optout. 1346b7579f77SDag-Erling Smørgrav * No need to check wildcard for type DS */ 1347b7579f77SDag-Erling Smørgrav /* capacity=3: ce + nc + soa(if needed) */ 1348b7579f77SDag-Erling Smørgrav if(!(msg = dns_msg_create(qname, qname_len, 1349b7579f77SDag-Erling Smørgrav LDNS_RR_TYPE_DS, zone->dclass, region, 3))) 1350b7579f77SDag-Erling Smørgrav return NULL; 1351b7579f77SDag-Erling Smørgrav /* now=0 because TTL was reduced in grab_nsec */ 1352b7579f77SDag-Erling Smørgrav if(!dns_msg_authadd(msg, region, ce_rrset, 0)) 1353b7579f77SDag-Erling Smørgrav return NULL; 1354b7579f77SDag-Erling Smørgrav if(!dns_msg_authadd(msg, region, nc_rrset, 0)) 1355b7579f77SDag-Erling Smørgrav return NULL; 1356b7579f77SDag-Erling Smørgrav return msg; 1357b7579f77SDag-Erling Smørgrav } 1358b7579f77SDag-Erling Smørgrav return NULL; 1359b7579f77SDag-Erling Smørgrav } 1360b7579f77SDag-Erling Smørgrav 1361b7579f77SDag-Erling Smørgrav /** 1362b7579f77SDag-Erling Smørgrav * Add SOA record for external responses. 1363b7579f77SDag-Erling Smørgrav * @param rrset_cache: to look into. 1364b7579f77SDag-Erling Smørgrav * @param now: current time. 1365b7579f77SDag-Erling Smørgrav * @param region: where to perform the allocation 1366b7579f77SDag-Erling Smørgrav * @param msg: current msg with NSEC. 1367b7579f77SDag-Erling Smørgrav * @param zone: val_neg_zone if we have one. 1368b7579f77SDag-Erling Smørgrav * @return false on lookup or alloc failure. 1369b7579f77SDag-Erling Smørgrav */ 137017d15b25SDag-Erling Smørgrav static int add_soa(struct rrset_cache* rrset_cache, time_t now, 1371b7579f77SDag-Erling Smørgrav struct regional* region, struct dns_msg* msg, struct val_neg_zone* zone) 1372b7579f77SDag-Erling Smørgrav { 1373b7579f77SDag-Erling Smørgrav struct ub_packed_rrset_key* soa; 1374b7579f77SDag-Erling Smørgrav uint8_t* nm; 1375b7579f77SDag-Erling Smørgrav size_t nmlen; 1376b7579f77SDag-Erling Smørgrav uint16_t dclass; 1377b7579f77SDag-Erling Smørgrav if(zone) { 1378b7579f77SDag-Erling Smørgrav nm = zone->name; 1379b7579f77SDag-Erling Smørgrav nmlen = zone->len; 1380b7579f77SDag-Erling Smørgrav dclass = zone->dclass; 1381b7579f77SDag-Erling Smørgrav } else { 1382b7579f77SDag-Erling Smørgrav /* Assumes the signer is the zone SOA to add */ 1383b7579f77SDag-Erling Smørgrav nm = reply_nsec_signer(msg->rep, &nmlen, &dclass); 1384b7579f77SDag-Erling Smørgrav if(!nm) 1385b7579f77SDag-Erling Smørgrav return 0; 1386b7579f77SDag-Erling Smørgrav } 1387b7579f77SDag-Erling Smørgrav soa = rrset_cache_lookup(rrset_cache, nm, nmlen, LDNS_RR_TYPE_SOA, 1388b7579f77SDag-Erling Smørgrav dclass, PACKED_RRSET_SOA_NEG, now, 0); 1389b7579f77SDag-Erling Smørgrav if(!soa) 1390b7579f77SDag-Erling Smørgrav return 0; 1391b7579f77SDag-Erling Smørgrav if(!dns_msg_authadd(msg, region, soa, now)) { 1392b7579f77SDag-Erling Smørgrav lock_rw_unlock(&soa->entry.lock); 1393b7579f77SDag-Erling Smørgrav return 0; 1394b7579f77SDag-Erling Smørgrav } 1395b7579f77SDag-Erling Smørgrav lock_rw_unlock(&soa->entry.lock); 1396b7579f77SDag-Erling Smørgrav return 1; 1397b7579f77SDag-Erling Smørgrav } 1398b7579f77SDag-Erling Smørgrav 1399b7579f77SDag-Erling Smørgrav struct dns_msg* 1400b7579f77SDag-Erling Smørgrav val_neg_getmsg(struct val_neg_cache* neg, struct query_info* qinfo, 1401b7579f77SDag-Erling Smørgrav struct regional* region, struct rrset_cache* rrset_cache, 140217d15b25SDag-Erling Smørgrav sldns_buffer* buf, time_t now, int addsoa, uint8_t* topname) 1403b7579f77SDag-Erling Smørgrav { 1404b7579f77SDag-Erling Smørgrav struct dns_msg* msg; 1405b7579f77SDag-Erling Smørgrav struct ub_packed_rrset_key* rrset; 1406b7579f77SDag-Erling Smørgrav uint8_t* zname; 1407b7579f77SDag-Erling Smørgrav size_t zname_len; 1408b7579f77SDag-Erling Smørgrav int zname_labs; 1409b7579f77SDag-Erling Smørgrav struct val_neg_zone* zone; 1410b7579f77SDag-Erling Smørgrav 1411b7579f77SDag-Erling Smørgrav /* only for DS queries */ 1412b7579f77SDag-Erling Smørgrav if(qinfo->qtype != LDNS_RR_TYPE_DS) 1413b7579f77SDag-Erling Smørgrav return NULL; 1414b7579f77SDag-Erling Smørgrav log_assert(!topname || dname_subdomain_c(qinfo->qname, topname)); 1415b7579f77SDag-Erling Smørgrav 1416b7579f77SDag-Erling Smørgrav /* see if info from neg cache is available 1417b7579f77SDag-Erling Smørgrav * For NSECs, because there is no optout; a DS next to a delegation 1418b7579f77SDag-Erling Smørgrav * always has exactly an NSEC for it itself; check its DS bit. 1419b7579f77SDag-Erling Smørgrav * flags=0 (not the zone apex). 1420b7579f77SDag-Erling Smørgrav */ 1421b7579f77SDag-Erling Smørgrav rrset = grab_nsec(rrset_cache, qinfo->qname, qinfo->qname_len, 1422b7579f77SDag-Erling Smørgrav LDNS_RR_TYPE_NSEC, qinfo->qclass, 0, region, 1, 1423b7579f77SDag-Erling Smørgrav qinfo->qtype, now); 1424b7579f77SDag-Erling Smørgrav if(rrset) { 1425b7579f77SDag-Erling Smørgrav /* return msg with that rrset */ 1426b7579f77SDag-Erling Smørgrav if(!(msg = dns_msg_create(qinfo->qname, qinfo->qname_len, 1427b7579f77SDag-Erling Smørgrav qinfo->qtype, qinfo->qclass, region, 2))) 1428b7579f77SDag-Erling Smørgrav return NULL; 1429b7579f77SDag-Erling Smørgrav /* TTL already subtracted in grab_nsec */ 1430b7579f77SDag-Erling Smørgrav if(!dns_msg_authadd(msg, region, rrset, 0)) 1431b7579f77SDag-Erling Smørgrav return NULL; 1432b7579f77SDag-Erling Smørgrav if(addsoa && !add_soa(rrset_cache, now, region, msg, NULL)) 1433b7579f77SDag-Erling Smørgrav return NULL; 1434b7579f77SDag-Erling Smørgrav return msg; 1435b7579f77SDag-Erling Smørgrav } 1436b7579f77SDag-Erling Smørgrav 1437b7579f77SDag-Erling Smørgrav /* check NSEC3 neg cache for type DS */ 1438b7579f77SDag-Erling Smørgrav /* need to look one zone higher for DS type */ 1439b7579f77SDag-Erling Smørgrav zname = qinfo->qname; 1440b7579f77SDag-Erling Smørgrav zname_len = qinfo->qname_len; 1441b7579f77SDag-Erling Smørgrav dname_remove_label(&zname, &zname_len); 1442b7579f77SDag-Erling Smørgrav zname_labs = dname_count_labels(zname); 1443b7579f77SDag-Erling Smørgrav 1444b7579f77SDag-Erling Smørgrav /* lookup closest zone */ 1445b7579f77SDag-Erling Smørgrav lock_basic_lock(&neg->lock); 1446b7579f77SDag-Erling Smørgrav zone = neg_closest_zone_parent(neg, zname, zname_len, zname_labs, 1447b7579f77SDag-Erling Smørgrav qinfo->qclass); 1448b7579f77SDag-Erling Smørgrav while(zone && !zone->in_use) 1449b7579f77SDag-Erling Smørgrav zone = zone->parent; 1450b7579f77SDag-Erling Smørgrav /* check that the zone is not too high up so that we do not pick data 1451b7579f77SDag-Erling Smørgrav * out of a zone that is above the last-seen key (or trust-anchor). */ 1452b7579f77SDag-Erling Smørgrav if(zone && topname) { 1453b7579f77SDag-Erling Smørgrav if(!dname_subdomain_c(zone->name, topname)) 1454b7579f77SDag-Erling Smørgrav zone = NULL; 1455b7579f77SDag-Erling Smørgrav } 1456b7579f77SDag-Erling Smørgrav if(!zone) { 1457b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 1458b7579f77SDag-Erling Smørgrav return NULL; 1459b7579f77SDag-Erling Smørgrav } 1460b7579f77SDag-Erling Smørgrav 1461b7579f77SDag-Erling Smørgrav msg = neg_nsec3_proof_ds(zone, qinfo->qname, qinfo->qname_len, 1462b7579f77SDag-Erling Smørgrav zname_labs+1, buf, rrset_cache, region, now, topname); 1463b7579f77SDag-Erling Smørgrav if(msg && addsoa && !add_soa(rrset_cache, now, region, msg, zone)) { 1464b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 1465b7579f77SDag-Erling Smørgrav return NULL; 1466b7579f77SDag-Erling Smørgrav } 1467b7579f77SDag-Erling Smørgrav lock_basic_unlock(&neg->lock); 1468b7579f77SDag-Erling Smørgrav return msg; 1469b7579f77SDag-Erling Smørgrav } 1470