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