testcode/unitneg.c

   1 /*
   2  * testcode/unitneg.c - unit test for negative cache routines.
   3  *
   4  * Copyright (c) 2008, NLnet Labs. All rights reserved.
   5  *
   6  * This software is open source.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  *
  12  * Redistributions of source code must retain the above copyright notice,
  13  * this list of conditions and the following disclaimer.
  14  *
  15  * Redistributions in binary form must reproduce the above copyright notice,
  16  * this list of conditions and the following disclaimer in the documentation
  17  * and/or other materials provided with the distribution.
  18  *
  19  * Neither the name of the NLNET LABS nor the names of its contributors may
  20  * be used to endorse or promote products derived from this software without
  21  * specific prior written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  26  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  27  * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  28  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
  29  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  30  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  31  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  32  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  33  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  34  *
  35  */
  36 /**
  37  * \file
  38  * Calls negative cache unit tests. Exits with code 1 on a failure.
  39  */
  40
  41 #include "config.h"
  42 #include "util/log.h"
  43 #include "util/net_help.h"
  44 #include "util/data/packed_rrset.h"
  45 #include "util/data/dname.h"
  46 #include "testcode/unitmain.h"
  47 #include "validator/val_neg.h"
  48 #include "sldns/rrdef.h"
  49
  50 /** verbose unit test for negative cache */
  51 static int negverbose = 0;
  52
  53 /** debug printout of neg cache */
  54 static void print_neg_cache(struct val_neg_cache* neg)
  55 {
  56         char buf[1024];
  57         struct val_neg_zone* z;
  58         struct val_neg_data* d;
  59         printf("neg_cache print\n");
  60         printf("memuse %d of %d\n", (int)neg->use, (int)neg->max);
  61         printf("maxiter %d\n", (int)neg->nsec3_max_iter);
  62         printf("%d zones\n", (int)neg->tree.count);
  63         RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
  64                 dname_str(z->name, buf);
  65                 printf("%24s", buf);
  66                 printf(" len=%2.2d labs=%d inuse=%d count=%d tree.count=%d\n",
  67                         (int)z->len, z->labs, (int)z->in_use, z->count,
  68                         (int)z->tree.count);
  69         }
  70         RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
  71                 printf("\n");
  72                 dname_print(stdout, NULL, z->name);
  73                 printf(" zone details\n");
  74                 printf("len=%2.2d labs=%d inuse=%d count=%d tree.count=%d\n",
  75                         (int)z->len, z->labs, (int)z->in_use, z->count,
  76                         (int)z->tree.count);
  77                 if(z->parent) {
  78                         printf("parent=");
  79                         dname_print(stdout, NULL, z->parent->name);
  80                         printf("\n");
  81                 } else {
  82                         printf("parent=NULL\n");
  83                 }
  84
  85                 RBTREE_FOR(d, struct val_neg_data*, &z->tree) {
  86                         dname_str(d->name, buf);
  87                         printf("%24s", buf);
  88                         printf(" len=%2.2d labs=%d inuse=%d count=%d\n",
  89                                 (int)d->len, d->labs, (int)d->in_use, d->count);
  90                 }
  91         }
  92 }
  93
  94 /** get static pointer to random zone name */
  95 static char* get_random_zone(void)
  96 {
  97         static char zname[36];
  98         int labels = random() % 3;
  99         int i;
 100         char* p = zname;
 101         int labnum;
 102
 103         for(i=0; i<labels; i++) {
 104                 labnum = random()%10;
 105                 snprintf(p, sizeof(zname)-(p-zname), "\003%3.3d", labnum);
 106                 p+=4;
 107         }
 108         snprintf(p, sizeof(zname)-(p-zname), "\007example\003com");
 109         return zname;
 110 }
 111
 112 /** get static pointer to random data names from and to */
 113 static void get_random_data(char** fromp, char** top, char* zname)
 114 {
 115         static char buf1[256], buf2[256];
 116         int type;
 117         int lab1, lab2;
 118         int labnum1[10], labnum2[10];
 119         int i;
 120         char* p;
 121
 122         *fromp = buf1;
 123         *top = buf2;
 124         type = random()%10;
 125
 126         if(type == 0) {
 127                 /* ENT */
 128                 lab1 = random() %3 + 1;
 129                 lab2 = lab1 + random()%3 + 1;
 130                 for(i=0; i<lab1; i++) {
 131                         labnum1[i] = random()%100;
 132                         labnum2[i] = labnum1[i];
 133                 }
 134                 for(i=lab1; i<lab2; i++) {
 135                         labnum2[i] = random()%100;
 136                 }
 137         } else if(type == 1) {
 138                 /* end of zone */
 139                 lab2 = 0;
 140                 lab1 = random()%3 + 1;
 141                 for(i=0; i<lab1; i++) {
 142                         labnum1[i] = random()%100;
 143                 }
 144         } else if(type == 2) {
 145                 /* start of zone */
 146                 lab1 = 0;
 147                 lab2 = random()%3 + 1;
 148                 for(i=0; i<lab2; i++) {
 149                         labnum2[i] = random()%100;
 150                 }
 151         } else {
 152                 /* normal item */
 153                 int common = random()%3;
 154                 lab1 = random() %3 + 1;
 155                 lab2 = random() %3 + 1;
 156                 for(i=0; i<common; i++) {
 157                         labnum1[i] = random()%100;
 158                         labnum2[i] = labnum1[i];
 159                 }
 160                 labnum1[common] = random()%100;
 161                 labnum2[common] = labnum1[common] + random()%20;
 162                 for(i=common; i<lab1; i++)
 163                         labnum1[i] = random()%100;
 164                 for(i=common; i<lab2; i++)
 165                         labnum2[i] = random()%100;
 166         }
 167
 168         /* construct first */
 169         p = buf1;
 170         for(i=0; i<lab1; i++) {
 171                 snprintf(p, 256-(p-buf1), "\003%3.3d", labnum1[i]);
 172                 p+=4;
 173         }
 174         snprintf(p, 256-(p-buf1), "%s", zname);
 175
 176         /* construct 2nd */
 177         p = buf2+2;
 178         for(i=0; i<lab2; i++) {
 179                 snprintf(p, 256-(p-buf2)-3, "\003%3.3d", labnum2[i]);
 180                 p+=4;
 181         }
 182         snprintf(p, 256-(p-buf2)-3, "%s", zname);
 183         buf2[0] = (char)(strlen(buf2+2)+1);
 184         buf2[1] = 0;
 185
 186         if(negverbose) {
 187                 log_nametypeclass(0, "add from", (uint8_t*)buf1, 0, 0);
 188                 log_nametypeclass(0, "add to  ", (uint8_t*)buf2+2, 0, 0);
 189         }
 190 }
 191
 192 /** add a random item */
 193 static void add_item(struct val_neg_cache* neg)
 194 {
 195         struct val_neg_zone* z;
 196         struct packed_rrset_data rd;
 197         struct ub_packed_rrset_key nsec;
 198         size_t rr_len;
 199         time_t rr_ttl;
 200         uint8_t* rr_data;
 201         char* zname = get_random_zone();
 202         char* from, *to;
 203
 204         lock_basic_lock(&neg->lock);
 205         if(negverbose)
 206                 log_nametypeclass(0, "add to zone", (uint8_t*)zname, 0, 0);
 207         z = neg_find_zone(neg, (uint8_t*)zname, strlen(zname)+1,
 208                 LDNS_RR_CLASS_IN);
 209         if(!z) {
 210                 z = neg_create_zone(neg,  (uint8_t*)zname, strlen(zname)+1,
 211                                 LDNS_RR_CLASS_IN);
 212         }
 213         unit_assert(z);
 214         val_neg_zone_take_inuse(z);
 215
 216         /* construct random NSEC item */
 217         get_random_data(&from, &to, zname);
 218
 219         /* create nsec and insert it */
 220         memset(&rd, 0, sizeof(rd));
 221         memset(&nsec, 0, sizeof(nsec));
 222         nsec.rk.dname = (uint8_t*)from;
 223         nsec.rk.dname_len = strlen(from)+1;
 224         nsec.rk.type = htons(LDNS_RR_TYPE_NSEC);
 225         nsec.rk.rrset_class = htons(LDNS_RR_CLASS_IN);
 226         nsec.entry.data = &rd;
 227         rd.security = sec_status_secure;
 228         rd.count = 1;
 229         rd.rr_len = &rr_len;
 230         rr_len = 19;
 231         rd.rr_ttl = &rr_ttl;
 232         rr_ttl = 0;
 233         rd.rr_data = &rr_data;
 234         rr_data = (uint8_t*)to;
 235
 236         neg_insert_data(neg, z, &nsec);
 237         lock_basic_unlock(&neg->lock);
 238 }
 239
 240 /** remove a random item */
 241 static void remove_item(struct val_neg_cache* neg)
 242 {
 243         int n, i;
 244         struct val_neg_data* d;
 245         rbnode_type* walk;
 246         struct val_neg_zone* z;
 247
 248         lock_basic_lock(&neg->lock);
 249         if(neg->tree.count == 0) {
 250                 lock_basic_unlock(&neg->lock);
 251                 return; /* nothing to delete */
 252         }
 253
 254         /* pick a random zone */
 255         walk = rbtree_first(&neg->tree); /* first highest parent, big count */
 256         z = (struct val_neg_zone*)walk;
 257         n = random() % (int)(z->count);
 258         if(negverbose)
 259                 printf("neg stress delete zone %d\n", n);
 260         i=0;
 261         walk = rbtree_first(&neg->tree);
 262         z = (struct val_neg_zone*)walk;
 263         while(i!=n+1 && walk && walk != RBTREE_NULL && !z->in_use) {
 264                 walk = rbtree_next(walk);
 265                 z = (struct val_neg_zone*)walk;
 266                 if(z->in_use)
 267                         i++;
 268         }
 269         if(!walk || walk == RBTREE_NULL) {
 270                 lock_basic_unlock(&neg->lock);
 271                 return;
 272         }
 273         if(!z->in_use) {
 274                 lock_basic_unlock(&neg->lock);
 275                 return;
 276         }
 277         if(negverbose)
 278                 log_nametypeclass(0, "delete zone", z->name, 0, 0);
 279
 280         /* pick a random nsec item. - that is in use */
 281         walk = rbtree_first(&z->tree); /* first is highest parent */
 282         d = (struct val_neg_data*)walk;
 283         n = random() % (int)(d->count);
 284         if(negverbose)
 285                 printf("neg stress delete item %d\n", n);
 286         i=0;
 287         walk = rbtree_first(&z->tree);
 288         d = (struct val_neg_data*)walk;
 289         while(i!=n+1 && walk && walk != RBTREE_NULL && !d->in_use) {
 290                 walk = rbtree_next(walk);
 291                 d = (struct val_neg_data*)walk;
 292                 if(d->in_use)
 293                         i++;
 294         }
 295         if(!walk || walk == RBTREE_NULL) {
 296                 lock_basic_unlock(&neg->lock);
 297                 return;
 298         }
 299         if(d->in_use) {
 300                 if(negverbose)
 301                         log_nametypeclass(0, "neg delete item:", d->name, 0, 0);
 302                 neg_delete_data(neg, d);
 303         }
 304         lock_basic_unlock(&neg->lock);
 305 }
 306
 307 /** sum up the zone trees */
 308 static size_t sumtrees_all(struct val_neg_cache* neg)
 309 {
 310         size_t res = 0;
 311         struct val_neg_zone* z;
 312         RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
 313                 res += z->tree.count;
 314         }
 315         return res;
 316 }
 317
 318 /** sum up the zone trees, in_use only */
 319 static size_t sumtrees_inuse(struct val_neg_cache* neg)
 320 {
 321         size_t res = 0;
 322         struct val_neg_zone* z;
 323         struct val_neg_data* d;
 324         RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
 325                 /* get count of highest parent for num in use */
 326                 d = (struct val_neg_data*)rbtree_first(&z->tree);
 327                 if(d && (rbnode_type*)d!=RBTREE_NULL)
 328                         res += d->count;
 329         }
 330         return res;
 331 }
 332
 333 /** check if lru is still valid */
 334 static void check_lru(struct val_neg_cache* neg)
 335 {
 336         struct val_neg_data* p, *np;
 337         size_t num = 0;
 338         size_t inuse;
 339         p = neg->first;
 340         while(p) {
 341                 if(!p->prev) {
 342                         unit_assert(neg->first == p);
 343                 }
 344                 np = p->next;
 345                 if(np) {
 346                         unit_assert(np->prev == p);
 347                 } else {
 348                         unit_assert(neg->last == p);
 349                 }
 350                 num++;
 351                 p = np;
 352         }
 353         inuse = sumtrees_inuse(neg);
 354         if(negverbose)
 355                 printf("num lru %d, inuse %d, all %d\n",
 356                         (int)num, (int)sumtrees_inuse(neg),
 357                         (int)sumtrees_all(neg));
 358         unit_assert( num == inuse);
 359         unit_assert( inuse <= sumtrees_all(neg));
 360 }
 361
 362 /** sum up number of items inuse in subtree */
 363 static int sum_subtree_inuse(struct val_neg_zone* zone,
 364         struct val_neg_data* data)
 365 {
 366         struct val_neg_data* d;
 367         int num = 0;
 368         RBTREE_FOR(d, struct val_neg_data*, &zone->tree) {
 369                 if(dname_subdomain_c(d->name, data->name)) {
 370                         if(d->in_use)
 371                                 num++;
 372                 }
 373         }
 374         return num;
 375 }
 376
 377 /** sum up number of items inuse in subtree */
 378 static int sum_zone_subtree_inuse(struct val_neg_cache* neg,
 379         struct val_neg_zone* zone)
 380 {
 381         struct val_neg_zone* z;
 382         int num = 0;
 383         RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
 384                 if(dname_subdomain_c(z->name, zone->name)) {
 385                         if(z->in_use)
 386                                 num++;
 387                 }
 388         }
 389         return num;
 390 }
 391
 392 /** check point in data tree */
 393 static void check_data(struct val_neg_zone* zone, struct val_neg_data* data)
 394 {
 395         unit_assert(data->count > 0);
 396         if(data->parent) {
 397                 unit_assert(data->parent->count >= data->count);
 398                 if(data->parent->in_use) {
 399                         unit_assert(data->parent->count > data->count);
 400                 }
 401                 unit_assert(data->parent->labs == data->labs-1);
 402                 /* and parent must be one label shorter */
 403                 unit_assert(data->name[0] == (data->len-data->parent->len-1));
 404                 unit_assert(query_dname_compare(data->name + data->name[0]+1,
 405                         data->parent->name) == 0);
 406         } else {
 407                 /* must be apex */
 408                 unit_assert(dname_is_root(data->name));
 409         }
 410         /* tree property: */
 411         unit_assert(data->count == sum_subtree_inuse(zone, data));
 412 }
 413
 414 /** check if tree of data in zone is valid */
 415 static void checkzonetree(struct val_neg_zone* zone)
 416 {
 417         struct val_neg_data* d;
 418
 419         /* check all data in tree */
 420         RBTREE_FOR(d, struct val_neg_data*, &zone->tree) {
 421                 check_data(zone, d);
 422         }
 423 }
 424
 425 /** check if negative cache is still valid */
 426 static void check_zone_invariants(struct val_neg_cache* neg,
 427         struct val_neg_zone* zone)
 428 {
 429         unit_assert(zone->nsec3_hash == 0);
 430         unit_assert(zone->tree.cmp == &val_neg_data_compare);
 431         unit_assert(zone->count != 0);
 432
 433         if(zone->tree.count == 0)
 434                 unit_assert(!zone->in_use);
 435         else {
 436                 if(!zone->in_use) {
 437                         /* details on error */
 438                         log_nametypeclass(0, "zone", zone->name, 0, 0);
 439                         log_err("inuse %d count=%d tree.count=%d",
 440                                 zone->in_use, zone->count,
 441                                 (int)zone->tree.count);
 442                         if(negverbose)
 443                                 print_neg_cache(neg);
 444                 }
 445                 unit_assert(zone->in_use);
 446         }
 447
 448         if(zone->parent) {
 449                 unit_assert(zone->parent->count >= zone->count);
 450                 if(zone->parent->in_use) {
 451                         unit_assert(zone->parent->count > zone->count);
 452                 }
 453                 unit_assert(zone->parent->labs == zone->labs-1);
 454                 /* and parent must be one label shorter */
 455                 unit_assert(zone->name[0] == (zone->len-zone->parent->len-1));
 456                 unit_assert(query_dname_compare(zone->name + zone->name[0]+1,
 457                         zone->parent->name) == 0);
 458         } else {
 459                 /* must be apex */
 460                 unit_assert(dname_is_root(zone->name));
 461         }
 462         /* tree property: */
 463         unit_assert(zone->count == sum_zone_subtree_inuse(neg, zone));
 464
 465         /* check structure of zone data tree */
 466         checkzonetree(zone);
 467 }
 468
 469 /** check if negative cache is still valid */
 470 static void check_neg_invariants(struct val_neg_cache* neg)
 471 {
 472         struct val_neg_zone* z;
 473         /* check structure of LRU list */
 474         lock_basic_lock(&neg->lock);
 475         check_lru(neg);
 476         unit_assert(neg->max == 1024*1024);
 477         unit_assert(neg->nsec3_max_iter == 1500);
 478         unit_assert(neg->tree.cmp == &val_neg_zone_compare);
 479
 480         if(neg->tree.count == 0) {
 481                 /* empty */
 482                 unit_assert(neg->tree.count == 0);
 483                 unit_assert(neg->first == NULL);
 484                 unit_assert(neg->last == NULL);
 485                 unit_assert(neg->use == 0);
 486                 lock_basic_unlock(&neg->lock);
 487                 return;
 488         }
 489
 490         unit_assert(neg->first != NULL);
 491         unit_assert(neg->last != NULL);
 492
 493         RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
 494                 check_zone_invariants(neg, z);
 495         }
 496         lock_basic_unlock(&neg->lock);
 497 }
 498
 499 /** perform stress test on insert and delete in neg cache */
 500 static void stress_test(struct val_neg_cache* neg)
 501 {
 502         int i;
 503         if(negverbose)
 504                 printf("negcache test\n");
 505         for(i=0; i<100; i++) {
 506                 if(random() % 10 < 8)
 507                         add_item(neg);
 508                 else    remove_item(neg);
 509                 check_neg_invariants(neg);
 510         }
 511         /* empty it */
 512         if(negverbose)
 513                 printf("neg stress empty\n");
 514         while(neg->first) {
 515                 remove_item(neg);
 516                 check_neg_invariants(neg);
 517         }
 518         if(negverbose)
 519                 printf("neg stress emptied\n");
 520         unit_assert(neg->first == NULL);
 521         /* insert again */
 522         for(i=0; i<100; i++) {
 523                 if(random() % 10 < 8)
 524                         add_item(neg);
 525                 else    remove_item(neg);
 526                 check_neg_invariants(neg);
 527         }
 528 }
 529
 530 void neg_test(void)
 531 {
 532         struct val_neg_cache* neg;
 533         srandom(48);
 534         unit_show_feature("negative cache");
 535
 536         /* create with defaults */
 537         neg = val_neg_create(NULL, 1500);
 538         unit_assert(neg);
 539
 540         stress_test(neg);
 541
 542         neg_cache_delete(neg);
 543 }