88 	struct val_neg_cache* neg = (struct val_neg_cache*)calloc(1,   in val_neg_create()  local
89 		sizeof(*neg));  in val_neg_create()
90 	if(!neg) {  in val_neg_create()
94 	neg->nsec3_max_iter = maxiter;  in val_neg_create()
95 	neg->max = 1024*1024; /* 1 M is thousands of entries */  in val_neg_create()
96 	if(cfg) neg->max = cfg->neg_cache_size;  in val_neg_create()
97 	rbtree_init(&neg->tree, &val_neg_zone_compare);  in val_neg_create()
98 	lock_basic_init(&neg->lock);  in val_neg_create()
99 	lock_protect(&neg->lock, neg, sizeof(*neg));  in val_neg_create()
100 	return neg;  in val_neg_create()
103 size_t val_neg_get_mem(struct val_neg_cache* neg)  in val_neg_get_mem()  argument
106 	lock_basic_lock(&neg->lock);  in val_neg_get_mem()
107 	result = sizeof(*neg) + neg->use;  in val_neg_get_mem()
108 	lock_basic_unlock(&neg->lock);  in val_neg_get_mem()
133 void neg_cache_delete(struct val_neg_cache* neg)  in neg_cache_delete()  argument
135 	if(!neg) return;  in neg_cache_delete()
136 	lock_basic_destroy(&neg->lock);  in neg_cache_delete()
138 	traverse_postorder(&neg->tree, &neg_clear_zones, NULL);  in neg_cache_delete()
139 	free(neg);  in neg_cache_delete()
147 static void neg_lru_front(struct val_neg_cache* neg,   in neg_lru_front()  argument
151 	data->next = neg->first;  in neg_lru_front()
152 	if(!neg->first)  in neg_lru_front()
153 		neg->last = data;  in neg_lru_front()
154 	else	neg->first->prev = data;  in neg_lru_front()
155 	neg->first = data;  in neg_lru_front()
163 static void neg_lru_remove(struct val_neg_cache* neg,   in neg_lru_remove()  argument
168 	else	neg->first = data->next;  in neg_lru_remove()
171 	else	neg->last = data->prev;  in neg_lru_remove()
179 static void neg_lru_touch(struct val_neg_cache* neg,   in neg_lru_touch()  argument
182 	if(data == neg->first)  in neg_lru_touch()
185 	neg_lru_remove(neg, data);  in neg_lru_touch()
187 	neg_lru_front(neg, data);  in neg_lru_touch()
197 static void neg_delete_zone(struct val_neg_cache* neg, struct val_neg_zone* z)  in neg_delete_zone()  argument
217 		(void)rbtree_delete(&neg->tree, &p->node);  in neg_delete_zone()
218 		neg->use -= p->len + sizeof(*p);  in neg_delete_zone()
226 void neg_delete_data(struct val_neg_cache* neg, struct val_neg_data* el)  in neg_delete_data()  argument
237 	neg_lru_remove(neg, el);  in neg_delete_data()
238 	log_assert(neg->first != el && neg->last != el);  in neg_delete_data()
253 		neg->use -= p->len + sizeof(*p);  in neg_delete_data()
261 		neg_delete_zone(neg, z);  in neg_delete_data()
272 static void neg_make_space(struct val_neg_cache* neg, size_t need)  in neg_make_space()  argument
275 	while(neg->last && neg->max < neg->use + need) {  in neg_make_space()
276 		neg_delete_data(neg, neg->last);  in neg_make_space()
280 struct val_neg_zone* neg_find_zone(struct val_neg_cache* neg,   in neg_find_zone()  argument
292 		rbtree_search(&neg->tree, lookfor.node.key);  in neg_find_zone()
370 static struct val_neg_zone* neg_closest_zone_parent(struct val_neg_cache* neg,  in neg_closest_zone_parent()  argument
381 	if(rbtree_find_less_equal(&neg->tree, &key, &res)) {  in neg_closest_zone_parent()
530 struct val_neg_zone* neg_create_zone(struct val_neg_cache* neg,  in neg_create_zone()  argument
539 	parent = neg_closest_zone_parent(neg, nm, nm_len, labs, dclass);  in neg_create_zone()
554 		neg->use += sizeof(struct val_neg_zone) + p->len;  in neg_create_zone()
556 		(void)rbtree_insert(&neg->tree, &p->node);  in neg_create_zone()
673 static void wipeout(struct val_neg_cache* neg, struct val_neg_zone* zone,   in wipeout()  argument
743 			neg_delete_data(neg, cur);  in wipeout()
748 void neg_insert_data(struct val_neg_cache* neg,   in neg_insert_data()  argument
791 			neg->use += sizeof(struct val_neg_data) + p->len;  in neg_insert_data()
811 		neg_lru_front(neg, el);  in neg_insert_data()
814 		neg_lru_touch(neg, el);  in neg_insert_data()
823 			it <= neg->nsec3_max_iter &&  in neg_insert_data()
848 	wipeout(neg, zone, el, nsec);  in neg_insert_data()
878 void val_neg_addreply(struct val_neg_cache* neg, struct reply_info* rep)  in val_neg_addreply()  argument
908 	lock_basic_lock(&neg->lock);  in val_neg_addreply()
909 	neg_make_space(neg, need);  in val_neg_addreply()
912 	zone = neg_find_zone(neg, dname, dname_len, rrset_class);  in val_neg_addreply()
914 		if(!(zone = neg_create_zone(neg, dname, dname_len,  in val_neg_addreply()
916 			lock_basic_unlock(&neg->lock);  in val_neg_addreply()
930 		neg_insert_data(neg, zone, rep->rrsets[i]);  in val_neg_addreply()
934 		neg_delete_zone(neg, zone);  in val_neg_addreply()
936 	lock_basic_unlock(&neg->lock);  in val_neg_addreply()
968 void val_neg_addreferral(struct val_neg_cache* neg, struct reply_info* rep,  in val_neg_addreferral()  argument
991 	lock_basic_lock(&neg->lock);  in val_neg_addreferral()
992 	neg_make_space(neg, need);  in val_neg_addreferral()
995 	zone = neg_find_zone(neg, signer, signer_len, dclass);  in val_neg_addreferral()
997 		if(!(zone = neg_create_zone(neg, signer, signer_len,   in val_neg_addreferral()
999 			lock_basic_unlock(&neg->lock);  in val_neg_addreferral()
1014 		neg_insert_data(neg, zone, rep->rrsets[i]);  in val_neg_addreferral()
1018 		neg_delete_zone(neg, zone);  in val_neg_addreferral()
1020 	lock_basic_unlock(&neg->lock);  in val_neg_addreferral()
1377 val_neg_getmsg(struct val_neg_cache* neg, struct query_info* qinfo,   in val_neg_getmsg()  argument
1404 	nsec = neg_find_nsec(neg, qinfo->qname, qinfo->qname_len, qinfo->qclass,  in val_neg_getmsg()
1423 		lock_basic_lock(&neg->lock);  in val_neg_getmsg()
1424 		neg->num_neg_cache_noerror++;  in val_neg_getmsg()
1425 		lock_basic_unlock(&neg->lock);  in val_neg_getmsg()
1479 				if(!(wcrr = neg_find_nsec(neg, wc_qinfo.qname,  in val_neg_getmsg()
1507 		lock_basic_lock(&neg->lock);  in val_neg_getmsg()
1509 			neg->num_neg_cache_noerror++;  in val_neg_getmsg()
1511 			neg->num_neg_cache_nxdomain++;  in val_neg_getmsg()
1512 		lock_basic_unlock(&neg->lock);  in val_neg_getmsg()
1530 	lock_basic_lock(&neg->lock);  in val_neg_getmsg()
1531 	zone = neg_closest_zone_parent(neg, zname, zname_len, zname_labs,   in val_neg_getmsg()
1542 		lock_basic_unlock(&neg->lock);  in val_neg_getmsg()
1549 		lock_basic_unlock(&neg->lock);  in val_neg_getmsg()
1552 	lock_basic_unlock(&neg->lock);  in val_neg_getmsg()