Lines Matching +full:exact +full:- +full:len
2 * validator/val_neg.c - validator aggressive negative caching functions.
70 return dname_canon_lab_cmp(x->name, x->labs, y->name, y->labs, &m);
78 if(x->dclass != y->dclass) {
79 if(x->dclass < y->dclass)
80 return -1;
83 return dname_canon_lab_cmp(x->name, x->labs, y->name, y->labs, &m);
94 neg->nsec3_max_iter = maxiter;
95 neg->max = 1024*1024; /* 1 M is thousands of entries */
96 if(cfg) neg->max = cfg->neg_cache_size;
97 rbtree_init(&neg->tree, &val_neg_zone_compare);
98 lock_basic_init(&neg->lock);
99 lock_protect(&neg->lock, neg, sizeof(*neg));
106 lock_basic_lock(&neg->lock);
107 result = sizeof(*neg) + neg->use;
108 lock_basic_unlock(&neg->lock);
117 free(d->name);
127 traverse_postorder(&z->tree, &neg_clear_datas, NULL);
128 free(z->nsec3_salt);
129 free(z->name);
136 lock_basic_destroy(&neg->lock);
138 traverse_postorder(&neg->tree, &neg_clear_zones, NULL);
150 data->prev = NULL;
151 data->next = neg->first;
152 if(!neg->first)
153 neg->last = data;
154 else neg->first->prev = data;
155 neg->first = data;
166 if(data->prev)
167 data->prev->next = data->next;
168 else neg->first = data->next;
169 if(data->next)
170 data->next->prev = data->prev;
171 else neg->last = data->prev;
182 if(data == neg->first)
201 log_assert(z->in_use);
202 log_assert(z->count > 0);
203 z->in_use = 0;
208 log_assert(p->count > 0);
209 p->count --;
210 p = p->parent;
215 while(p && p->count == 0) {
216 np = p->parent;
217 (void)rbtree_delete(&neg->tree, &p->node);
218 neg->use -= p->len + sizeof(*p);
219 free(p->nsec3_salt);
220 free(p->name);
231 z = el->zone;
232 log_assert(el->in_use);
233 log_assert(el->count > 0);
234 el->in_use = 0;
238 log_assert(neg->first != el && neg->last != el);
243 log_assert(p->count > 0);
244 p->count --;
245 p = p->parent;
250 while(p && p->count == 0) {
251 np = p->parent;
252 (void)rbtree_delete(&z->tree, &p->node);
253 neg->use -= p->len + sizeof(*p);
254 free(p->name);
260 if(z->tree.count == 0) {
275 while(neg->last && neg->max < neg->use + need) {
276 neg_delete_data(neg, neg->last);
281 uint8_t* nm, size_t len, uint16_t dclass)
287 lookfor.len = len;
292 rbtree_search(&neg->tree, lookfor.node.key);
300 * @param len: length of nm
305 uint8_t* nm, size_t len, int labs)
311 lookfor.len = len;
315 rbtree_search(&zone->tree, lookfor.node.key);
327 size_t i, len, res = 0;
329 for(i=rep->an_numrrsets; i<rep->an_numrrsets+rep->ns_numrrsets; i++) {
330 if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC) {
331 d = rep->rrsets[i]->rk.dname;
332 len = rep->rrsets[i]->rk.dname_len;
333 res = sizeof(struct val_neg_data) + len;
335 log_assert(len > 1); /* not root label */
336 dname_remove_label(&d, &len);
337 res += sizeof(struct val_neg_data) + len;
347 * @param len: length of name
350 static size_t calc_zone_need(uint8_t* d, size_t len)
352 size_t res = sizeof(struct val_neg_zone) + len;
354 log_assert(len > 1); /* not root label */
355 dname_remove_label(&d, &len);
356 res += sizeof(struct val_neg_zone) + len;
378 key.len = nm_len;
381 if(rbtree_find_less_equal(&neg->tree, &key, &res)) {
382 /* exact match */
388 if(!result || result->dclass != qclass)
391 (void)dname_lab_cmp(result->name, result->labs, key.name,
394 if(result->labs <= m)
396 result = result->parent;
418 key.len = nm_len;
420 if(rbtree_find_less_equal(&zone->tree, &key, &res)) {
421 /* exact match */
430 (void)dname_lab_cmp(result->name, result->labs, key.name,
433 if(result->labs <= m)
435 result = result->parent;
457 zone->node.key = zone;
458 zone->name = memdup(nm, nm_len);
459 if(!zone->name) {
463 zone->len = nm_len;
464 zone->labs = labs;
465 zone->dclass = dclass;
467 rbtree_init(&zone->tree, &val_neg_data_compare);
487 int tolabs = parent?parent->labs:0;
491 /* this creates a 'first' to z->parent=NULL list of zones */
492 for(i=labs; i!=tolabs; i--) {
499 np = p->parent;
500 free(p->name);
509 prev->parent = zone;
520 if(!zone->in_use) {
522 zone->in_use = 1;
524 for(p=zone; p; p = p->parent) {
525 p->count++;
540 if(parent && query_dname_compare(parent->name, nm) == 0)
543 log_assert(!parent || parent->count > 0);
552 np = p->parent;
554 neg->use += sizeof(struct val_neg_zone) + p->len;
556 (void)rbtree_insert(&neg->tree, &p->node);
559 p->parent = parent;
569 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
570 if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_SOA)
571 return rep->rrsets[i];
581 if(rep->security != sec_status_secure)
583 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
584 if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC) {
585 d = (struct packed_rrset_data*)rep->rrsets[i]->
587 if(d->security == sec_status_secure)
610 el->node.key = el;
611 el->name = memdup(nm, nm_len);
612 if(!el->name) {
616 el->len = nm_len;
617 el->labs = labs;
633 int tolabs = parent?parent->labs:0;
637 /* this creates a 'first' to z->parent=NULL list of zones */
638 for(i=labs; i!=tolabs; i--) {
645 np = p->parent;
646 free(p->name);
655 prev->parent = el;
676 struct packed_rrset_data* d = (struct packed_rrset_data*)nsec->
685 if(!d || d->count == 0 || d->rr_len[0] < 2+1)
687 if(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC) {
688 end = d->rr_data[0]+2;
689 end_len = dname_valid(end, d->rr_len[0]-2);
700 if(!dname_subdomain_c(el->name, zone->name) ||
701 !dname_subdomain_c(end, zone->name))
705 if(query_dname_compare(end, zone->name) == 0) {
709 walk = rbtree_next(&el->node);
713 if(dname_canon_lab_cmp(cur->name, cur->labs,
714 el->name, el->labs, &m) <= 0) {
723 if(end && dname_canon_lab_cmp(cur->name, cur->labs,
742 if(cur->in_use)
754 uint8_t* nm = nsec->rk.dname;
755 size_t nm_len = nsec->rk.dname_len;
756 int labs = dname_count_labels(nsec->rk.dname);
758 d = (struct packed_rrset_data*)nsec->entry.data;
759 if( !(d->security == sec_status_secure ||
760 (d->security == sec_status_unchecked && d->rrsig_count > 0)))
763 nsec->rk.dname, ntohs(nsec->rk.type),
764 ntohs(nsec->rk.rrset_class));
768 if(parent && query_dname_compare(parent->name, nm) == 0) {
770 log_assert(parent->count > 0);
777 log_assert(!parent || parent->count > 0);
784 el->in_use = 0; /* set on below */
789 np = p->parent;
791 neg->use += sizeof(struct val_neg_data) + p->len;
793 p->zone = zone;
794 (void)rbtree_insert(&zone->tree, &p->node);
797 p->parent = parent;
802 if(!el->in_use) {
805 el->in_use = 1;
807 for(p=el; p; p = p->parent) {
808 p->count++;
818 if(ntohs(nsec->rk.type) == LDNS_RR_TYPE_NSEC3) {
823 it <= neg->nsec3_max_iter &&
824 (h != zone->nsec3_hash || it != zone->nsec3_iter ||
825 slen != zone->nsec3_saltlen ||
826 (slen != 0 && zone->nsec3_salt && s
827 && memcmp(zone->nsec3_salt, s, slen) != 0))) {
832 free(zone->nsec3_salt);
833 zone->nsec3_salt = sa;
834 zone->nsec3_saltlen = slen;
835 zone->nsec3_iter = it;
836 zone->nsec3_hash = h;
839 free(zone->nsec3_salt);
840 zone->nsec3_salt = NULL;
841 zone->nsec3_saltlen = 0;
842 zone->nsec3_iter = it;
843 zone->nsec3_hash = h;
859 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
860 if(ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC ||
861 ntohs(rep->rrsets[i]->rk.type) == LDNS_RR_TYPE_NSEC3) {
862 d = (struct packed_rrset_data*)rep->rrsets[i]->
865 if(d->rrsig_count != 0) {
866 val_find_rrset_signer(rep->rrsets[i],
869 *dclass = ntohs(rep->rrsets[i]->
892 dname = soa->rk.dname;
893 dname_len = soa->rk.dname_len;
894 rrset_class = ntohs(soa->rk.rrset_class);
909 lock_basic_lock(&neg->lock);
917 lock_basic_unlock(&neg->lock);
925 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
926 if(ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC)
928 if(!dname_subdomain_c(rep->rrsets[i]->rk.dname,
929 zone->name)) continue;
931 neg_insert_data(neg, zone, rep->rrsets[i]);
933 if(zone->tree.count == 0) {
937 lock_basic_unlock(&neg->lock);
944 * @param len: length of name
946 * @param data: data element, exact or smaller or NULL
947 * @return true if exact match.
950 uint8_t* qname, size_t len, int labs, struct val_neg_data** data)
956 key.len = len;
958 if(rbtree_find_less_equal(&zone->tree, &key, &r)) {
959 /* exact match */
992 lock_basic_lock(&neg->lock);
1000 lock_basic_unlock(&neg->lock);
1008 for(i=rep->an_numrrsets; i< rep->an_numrrsets+rep->ns_numrrsets; i++){
1009 if(ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC &&
1010 ntohs(rep->rrsets[i]->rk.type) != LDNS_RR_TYPE_NSEC3)
1012 if(!dname_subdomain_c(rep->rrsets[i]->rk.dname,
1013 zone->name)) continue;
1015 neg_insert_data(neg, zone, rep->rrsets[i]);
1017 if(zone->tree.count == 0) {
1021 lock_basic_unlock(&neg->lock);
1026 * None of the nsec3s in a hash-collision are allowed to have the type.
1035 int count = (int)((struct packed_rrset_data*)k->entry.data)->count;
1069 d = (struct packed_rrset_data*)k->entry.data;
1070 if(d->ttl < now) {
1071 lock_rw_unlock(&k->entry.lock);
1075 if( ! ( d->security == sec_status_secure ||
1076 (d->security == sec_status_unchecked &&
1077 d->rrsig_count > 0) ) ) {
1078 lock_rw_unlock(&k->entry.lock);
1086 lock_rw_unlock(&k->entry.lock);
1092 lock_rw_unlock(&k->entry.lock);
1120 lock_basic_lock(&neg_cache->lock);
1123 while(zone && !zone->in_use)
1124 zone = zone->parent;
1126 lock_basic_unlock(&neg_cache->lock);
1131 if(zone->nsec3_hash) {
1132 lock_basic_unlock(&neg_cache->lock);
1136 /* ignore return value, don't care if it is an exact or smaller match */
1139 lock_basic_unlock(&neg_cache->lock);
1145 if(!data->in_use) {
1147 if((rbnode_type*)data == RBTREE_NULL || !data->in_use) {
1148 lock_basic_unlock(&neg_cache->lock);
1154 if(query_dname_compare(data->name, zone->name) == 0)
1157 nsec = grab_nsec(rrset_cache, data->name, data->len, LDNS_RR_TYPE_NSEC,
1158 zone->dclass, flags, region, 0, 0, now);
1159 lock_basic_unlock(&neg_cache->lock);
1177 zone->nsec3_hash, zone->nsec3_iter, zone->nsec3_salt,
1178 zone->nsec3_saltlen, hashce, sizeof(hashce))))
1180 if(!(b32len=nsec3_hash_to_b32(hashce, celen, zone->name,
1181 zone->len, b32, sizeof(b32))))
1184 /* lookup (exact match only) */
1185 data = neg_find_data(zone, b32, b32len, zone->labs+1);
1186 if(data && data->in_use) {
1194 qlabs --;
1208 return (h == zone->nsec3_hash && it == zone->nsec3_iter &&
1209 slen == zone->nsec3_saltlen &&
1210 (slen != 0 && zone->nsec3_salt && s
1211 && memcmp(zone->nsec3_salt, s, slen) == 0));
1224 if(!(b32len=nsec3_hash_to_b32(hashnc, nclen, zone->name,
1225 zone->len, b32, maxb32)))
1227 (void)neg_closest_data(zone, b32, b32len, zone->labs+1, &data);
1228 if(!data && zone->tree.count != 0) {
1231 data = (struct val_neg_data*)rbtree_last(&zone->tree);
1233 while(data && !data->in_use)
1234 data = data->parent;
1238 nc_rrset = grab_nsec(rrset_cache, data->name, data->len,
1239 LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 0, 0, now);
1262 * can find an exact match. Remember the hashed lower name,
1269 if(!zone->nsec3_hash)
1278 ce_rrset = grab_nsec(rrset_cache, data->name, data->len,
1279 LDNS_RR_TYPE_NSEC3, zone->dclass, 0, region, 1,
1287 /* exact match, just check the type bits */
1288 /* need: -SOA, -DS, +NS */
1294 LDNS_RR_TYPE_DS, zone->dclass, region, 1)))
1302 /* optout is not allowed without knowing the trust-anchor in use,
1307 /* if there is no exact match, it must be in an optout span
1321 if(nsec3_covers(zone->name, &c, nc_rrset, 0, buf)) {
1328 LDNS_RR_TYPE_DS, zone->dclass, region, 3)))
1357 nm = zone->name;
1358 nmlen = zone->len;
1359 dclass = zone->dclass;
1362 nm = reply_nsec_signer(msg->rep, &nmlen, &dclass);
1371 lock_rw_unlock(&soa->entry.lock);
1374 lock_rw_unlock(&soa->entry.lock);
1401 if(qinfo->qtype != LDNS_RR_TYPE_DS && !cfg->aggressive_nsec)
1403 log_assert(!topname || dname_subdomain_c(qinfo->qname, topname));
1406 nsec = neg_find_nsec(neg, qinfo->qname, qinfo->qname_len, qinfo->qclass,
1415 if(qinfo->qtype == LDNS_RR_TYPE_ANY)
1417 if(!(msg = dns_msg_create(qinfo->qname, qinfo->qname_len,
1418 qinfo->qtype, qinfo->qclass, region, 2)))
1425 lock_basic_lock(&neg->lock);
1426 neg->num_neg_cache_noerror++;
1427 lock_basic_unlock(&neg->lock);
1429 } else if(nsec && val_nsec_proves_name_error(nsec, qinfo->qname)) {
1430 if(!(msg = dns_msg_create(qinfo->qname, qinfo->qname_len,
1431 qinfo->qtype, qinfo->qclass, region, 3)))
1433 if(!(ce = nsec_closest_encloser(qinfo->qname, nsec)))
1451 wc_qinfo.qtype = qinfo->qtype;
1456 qinfo->qclass, 0/*flags*/, now, 0/*read only*/))) {
1458 wcrr_data = (struct packed_rrset_data*)cache_wc->entry.data;
1459 if(!(wcrr_data->security == sec_status_secure ||
1460 (wcrr_data->security == sec_status_unchecked &&
1461 wcrr_data->rrsig_count > 0))) {
1462 lock_rw_unlock(&cache_wc->entry.lock);
1467 lock_rw_unlock(&cache_wc->entry.lock);
1470 lock_rw_unlock(&cache_wc->entry.lock);
1471 wcrr->rk.dname = qinfo->qname;
1472 wcrr->rk.dname_len = qinfo->qname_len;
1482 wc_qinfo.qname_len, qinfo->qclass,
1496 if(query_dname_compare(wcrr->rk.dname,
1497 nsec->rk.dname) != 0)
1509 lock_basic_lock(&neg->lock);
1511 neg->num_neg_cache_noerror++;
1513 neg->num_neg_cache_nxdomain++;
1514 lock_basic_unlock(&neg->lock);
1516 FLAGS_SET_RCODE(msg->rep->flags, rcode);
1521 if(qinfo->qtype != LDNS_RR_TYPE_DS){
1526 zname = qinfo->qname;
1527 zname_len = qinfo->qname_len;
1532 lock_basic_lock(&neg->lock);
1534 qinfo->qclass);
1535 while(zone && !zone->in_use)
1536 zone = zone->parent;
1538 * out of a zone that is above the last-seen key (or trust-anchor). */
1540 if(!dname_subdomain_c(zone->name, topname))
1544 lock_basic_unlock(&neg->lock);
1548 msg = neg_nsec3_proof_ds(zone, qinfo->qname, qinfo->qname_len,
1551 lock_basic_unlock(&neg->lock);
1554 lock_basic_unlock(&neg->lock);
1561 lock_basic_lock(&neg->lock);
1562 neg->max = max;
1564 lock_basic_unlock(&neg->lock);