#include "config.h"
#include "util/log.h"
#include "util/net_help.h"
#include "util/data/packed_rrset.h"
#include "util/data/dname.h"
#include "testcode/unitmain.h"
#include "validator/val_neg.h"
#include "ldns/rrdef.h"
static int negverbose = 0;
static void print_neg_cache(struct val_neg_cache* neg)
{
char buf[1024];
struct val_neg_zone* z;
struct val_neg_data* d;
printf("neg_cache print\n");
printf("memuse %d of %d\n", (int)neg->use, (int)neg->max);
printf("maxiter %d\n", (int)neg->nsec3_max_iter);
printf("%d zones\n", (int)neg->tree.count);
RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
dname_str(z->name, buf);
printf("%24s", buf);
printf(" len=%2.2d labs=%d inuse=%d count=%d tree.count=%d\n",
(int)z->len, z->labs, (int)z->in_use, z->count,
(int)z->tree.count);
}
RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
printf("\n");
dname_print(stdout, NULL, z->name);
printf(" zone details\n");
printf("len=%2.2d labs=%d inuse=%d count=%d tree.count=%d\n",
(int)z->len, z->labs, (int)z->in_use, z->count,
(int)z->tree.count);
if(z->parent) {
printf("parent=");
dname_print(stdout, NULL, z->parent->name);
printf("\n");
} else {
printf("parent=NULL\n");
}
RBTREE_FOR(d, struct val_neg_data*, &z->tree) {
dname_str(d->name, buf);
printf("%24s", buf);
printf(" len=%2.2d labs=%d inuse=%d count=%d\n",
(int)d->len, d->labs, (int)d->in_use, d->count);
}
}
}
static char* get_random_zone(void)
{
static char zname[256];
int labels = random() % 3;
int i;
char* p = zname;
int labnum;
for(i=0; i<labels; i++) {
labnum = random()%10;
snprintf(p, 256-(p-zname), "\003%3.3d", labnum);
p+=4;
}
snprintf(p, 256-(p-zname), "\007example\003com");
return zname;
}
static void get_random_data(char** fromp, char** top, char* zname)
{
static char buf1[256], buf2[256];
int type;
int lab1, lab2;
int labnum1[10], labnum2[10];
int i;
char* p;
*fromp = buf1;
*top = buf2;
type = random()%10;
if(type == 0) {
lab1 = random() %3 + 1;
lab2 = lab1 + random()%3 + 1;
for(i=0; i<lab1; i++) {
labnum1[i] = random()%100;
labnum2[i] = labnum1[i];
}
for(i=lab1; i<lab2; i++) {
labnum2[i] = random()%100;
}
} else if(type == 1) {
lab2 = 0;
lab1 = random()%3 + 1;
for(i=0; i<lab1; i++) {
labnum1[i] = random()%100;
}
} else if(type == 2) {
lab1 = 0;
lab2 = random()%3 + 1;
for(i=0; i<lab2; i++) {
labnum2[i] = random()%100;
}
} else {
int common = random()%3;
lab1 = random() %3 + 1;
lab2 = random() %3 + 1;
for(i=0; i<common; i++) {
labnum1[i] = random()%100;
labnum2[i] = labnum1[i];
}
labnum1[common] = random()%100;
labnum2[common] = labnum1[common] + random()%20;
for(i=common; i<lab1; i++)
labnum1[i] = random()%100;
for(i=common; i<lab2; i++)
labnum2[i] = random()%100;
}
p = buf1;
for(i=0; i<lab1; i++) {
snprintf(p, 256-(p-buf1), "\003%3.3d", labnum1[i]);
p+=4;
}
snprintf(p, 256-(p-buf1), "%s", zname);
p = buf2+2;
for(i=0; i<lab2; i++) {
snprintf(p, 256-(p-buf2)-3, "\003%3.3d", labnum2[i]);
p+=4;
}
snprintf(p, 256-(p-buf2)-3, "%s", zname);
buf2[0] = (char)(strlen(buf2+2)+1);
buf2[1] = 0;
if(negverbose) {
log_nametypeclass(0, "add from", (uint8_t*)buf1, 0, 0);
log_nametypeclass(0, "add to ", (uint8_t*)buf2+2, 0, 0);
}
}
static void add_item(struct val_neg_cache* neg)
{
struct val_neg_zone* z;
struct packed_rrset_data rd;
struct ub_packed_rrset_key nsec;
size_t rr_len;
time_t rr_ttl;
uint8_t* rr_data;
char* zname = get_random_zone();
char* from, *to;
lock_basic_lock(&neg->lock);
if(negverbose)
log_nametypeclass(0, "add to zone", (uint8_t*)zname, 0, 0);
z = neg_find_zone(neg, (uint8_t*)zname, strlen(zname)+1,
LDNS_RR_CLASS_IN);
if(!z) {
z = neg_create_zone(neg, (uint8_t*)zname, strlen(zname)+1,
LDNS_RR_CLASS_IN);
}
unit_assert(z);
val_neg_zone_take_inuse(z);
get_random_data(&from, &to, zname);
memset(&rd, 0, sizeof(rd));
memset(&nsec, 0, sizeof(nsec));
nsec.rk.dname = (uint8_t*)from;
nsec.rk.dname_len = strlen(from)+1;
nsec.rk.type = htons(LDNS_RR_TYPE_NSEC);
nsec.rk.rrset_class = htons(LDNS_RR_CLASS_IN);
nsec.entry.data = &rd;
rd.security = sec_status_secure;
rd.count = 1;
rd.rr_len = &rr_len;
rr_len = 19;
rd.rr_ttl = &rr_ttl;
rr_ttl = 0;
rd.rr_data = &rr_data;
rr_data = (uint8_t*)to;
neg_insert_data(neg, z, &nsec);
lock_basic_unlock(&neg->lock);
}
static void remove_item(struct val_neg_cache* neg)
{
int n, i;
struct val_neg_data* d;
rbnode_t* walk;
struct val_neg_zone* z;
lock_basic_lock(&neg->lock);
if(neg->tree.count == 0) {
lock_basic_unlock(&neg->lock);
return;
}
walk = rbtree_first(&neg->tree);
z = (struct val_neg_zone*)walk;
n = random() % (int)(z->count);
if(negverbose)
printf("neg stress delete zone %d\n", n);
i=0;
walk = rbtree_first(&neg->tree);
z = (struct val_neg_zone*)walk;
while(i!=n+1 && walk && walk != RBTREE_NULL && !z->in_use) {
walk = rbtree_next(walk);
z = (struct val_neg_zone*)walk;
if(z->in_use)
i++;
}
if(!walk || walk == RBTREE_NULL) {
lock_basic_unlock(&neg->lock);
return;
}
if(!z->in_use) {
lock_basic_unlock(&neg->lock);
return;
}
if(negverbose)
log_nametypeclass(0, "delete zone", z->name, 0, 0);
walk = rbtree_first(&z->tree);
d = (struct val_neg_data*)walk;
n = random() % (int)(d->count);
if(negverbose)
printf("neg stress delete item %d\n", n);
i=0;
walk = rbtree_first(&z->tree);
d = (struct val_neg_data*)walk;
while(i!=n+1 && walk && walk != RBTREE_NULL && !d->in_use) {
walk = rbtree_next(walk);
d = (struct val_neg_data*)walk;
if(d->in_use)
i++;
}
if(!walk || walk == RBTREE_NULL) {
lock_basic_unlock(&neg->lock);
return;
}
if(d->in_use) {
if(negverbose)
log_nametypeclass(0, "neg delete item:", d->name, 0, 0);
neg_delete_data(neg, d);
}
lock_basic_unlock(&neg->lock);
}
static size_t sumtrees_all(struct val_neg_cache* neg)
{
size_t res = 0;
struct val_neg_zone* z;
RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
res += z->tree.count;
}
return res;
}
static size_t sumtrees_inuse(struct val_neg_cache* neg)
{
size_t res = 0;
struct val_neg_zone* z;
struct val_neg_data* d;
RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
d = (struct val_neg_data*)rbtree_first(&z->tree);
if(d && (rbnode_t*)d!=RBTREE_NULL)
res += d->count;
}
return res;
}
static void check_lru(struct val_neg_cache* neg)
{
struct val_neg_data* p, *np;
size_t num = 0;
size_t inuse;
p = neg->first;
while(p) {
if(!p->prev) {
unit_assert(neg->first == p);
}
np = p->next;
if(np) {
unit_assert(np->prev == p);
} else {
unit_assert(neg->last == p);
}
num++;
p = np;
}
inuse = sumtrees_inuse(neg);
if(negverbose)
printf("num lru %d, inuse %d, all %d\n",
(int)num, (int)sumtrees_inuse(neg),
(int)sumtrees_all(neg));
unit_assert( num == inuse);
unit_assert( inuse <= sumtrees_all(neg));
}
static int sum_subtree_inuse(struct val_neg_zone* zone,
struct val_neg_data* data)
{
struct val_neg_data* d;
int num = 0;
RBTREE_FOR(d, struct val_neg_data*, &zone->tree) {
if(dname_subdomain_c(d->name, data->name)) {
if(d->in_use)
num++;
}
}
return num;
}
static int sum_zone_subtree_inuse(struct val_neg_cache* neg,
struct val_neg_zone* zone)
{
struct val_neg_zone* z;
int num = 0;
RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
if(dname_subdomain_c(z->name, zone->name)) {
if(z->in_use)
num++;
}
}
return num;
}
static void check_data(struct val_neg_zone* zone, struct val_neg_data* data)
{
unit_assert(data->count > 0);
if(data->parent) {
unit_assert(data->parent->count >= data->count);
if(data->parent->in_use) {
unit_assert(data->parent->count > data->count);
}
unit_assert(data->parent->labs == data->labs-1);
unit_assert(data->name[0] == (data->len-data->parent->len-1));
unit_assert(query_dname_compare(data->name + data->name[0]+1,
data->parent->name) == 0);
} else {
unit_assert(dname_is_root(data->name));
}
unit_assert(data->count == sum_subtree_inuse(zone, data));
}
static void checkzonetree(struct val_neg_zone* zone)
{
struct val_neg_data* d;
RBTREE_FOR(d, struct val_neg_data*, &zone->tree) {
check_data(zone, d);
}
}
static void check_zone_invariants(struct val_neg_cache* neg,
struct val_neg_zone* zone)
{
unit_assert(zone->nsec3_hash == 0);
unit_assert(zone->tree.cmp == &val_neg_data_compare);
unit_assert(zone->count != 0);
if(zone->tree.count == 0)
unit_assert(!zone->in_use);
else {
if(!zone->in_use) {
log_nametypeclass(0, "zone", zone->name, 0, 0);
log_err("inuse %d count=%d tree.count=%d",
zone->in_use, zone->count,
(int)zone->tree.count);
if(negverbose)
print_neg_cache(neg);
}
unit_assert(zone->in_use);
}
if(zone->parent) {
unit_assert(zone->parent->count >= zone->count);
if(zone->parent->in_use) {
unit_assert(zone->parent->count > zone->count);
}
unit_assert(zone->parent->labs == zone->labs-1);
unit_assert(zone->name[0] == (zone->len-zone->parent->len-1));
unit_assert(query_dname_compare(zone->name + zone->name[0]+1,
zone->parent->name) == 0);
} else {
unit_assert(dname_is_root(zone->name));
}
unit_assert(zone->count == sum_zone_subtree_inuse(neg, zone));
checkzonetree(zone);
}
static void check_neg_invariants(struct val_neg_cache* neg)
{
struct val_neg_zone* z;
lock_basic_lock(&neg->lock);
check_lru(neg);
unit_assert(neg->max == 1024*1024);
unit_assert(neg->nsec3_max_iter == 1500);
unit_assert(neg->tree.cmp == &val_neg_zone_compare);
if(neg->tree.count == 0) {
unit_assert(neg->tree.count == 0);
unit_assert(neg->first == NULL);
unit_assert(neg->last == NULL);
unit_assert(neg->use == 0);
lock_basic_unlock(&neg->lock);
return;
}
unit_assert(neg->first != NULL);
unit_assert(neg->last != NULL);
RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
check_zone_invariants(neg, z);
}
lock_basic_unlock(&neg->lock);
}
static void stress_test(struct val_neg_cache* neg)
{
int i;
if(negverbose)
printf("negcache test\n");
for(i=0; i<100; i++) {
if(random() % 10 < 8)
add_item(neg);
else remove_item(neg);
check_neg_invariants(neg);
}
if(negverbose)
printf("neg stress empty\n");
while(neg->first) {
remove_item(neg);
check_neg_invariants(neg);
}
if(negverbose)
printf("neg stress emptied\n");
unit_assert(neg->first == NULL);
for(i=0; i<100; i++) {
if(random() % 10 < 8)
add_item(neg);
else remove_item(neg);
check_neg_invariants(neg);
}
}
void neg_test(void)
{
struct val_neg_cache* neg;
srandom(48);
unit_show_feature("negative cache");
neg = val_neg_create(NULL, 1500);
unit_assert(neg);
stress_test(neg);
neg_cache_delete(neg);
}