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 */
print_neg_cache(struct val_neg_cache * neg)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 */
get_random_zone(void)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 */
get_random_data(char ** fromp,char ** top,char * zname)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 memset(labnum1, 0, sizeof(int)*10);
122 memset(labnum2, 0, sizeof(int)*10);
123
124 *fromp = buf1;
125 *top = buf2;
126 type = random()%10;
127
128 if(type == 0) {
129 /* ENT */
130 lab1 = random() %3 + 1;
131 lab2 = lab1 + random()%3 + 1;
132 for(i=0; i<lab1; i++) {
133 labnum1[i] = random()%100;
134 labnum2[i] = labnum1[i];
135 }
136 for(i=lab1; i<lab2; i++) {
137 labnum2[i] = random()%100;
138 }
139 } else if(type == 1) {
140 /* end of zone */
141 lab2 = 0;
142 lab1 = random()%3 + 1;
143 for(i=0; i<lab1; i++) {
144 labnum1[i] = random()%100;
145 }
146 } else if(type == 2) {
147 /* start of zone */
148 lab1 = 0;
149 lab2 = random()%3 + 1;
150 for(i=0; i<lab2; i++) {
151 labnum2[i] = random()%100;
152 }
153 } else {
154 /* normal item */
155 int common = random()%3;
156 lab1 = random() %3 + 1;
157 lab2 = random() %3 + 1;
158 for(i=0; i<common; i++) {
159 labnum1[i] = random()%100;
160 labnum2[i] = labnum1[i];
161 }
162 labnum1[common] = random()%100;
163 labnum2[common] = labnum1[common] + random()%20;
164 for(i=common; i<lab1; i++)
165 labnum1[i] = random()%100;
166 for(i=common; i<lab2; i++)
167 labnum2[i] = random()%100;
168 }
169
170 /* construct first */
171 p = buf1;
172 for(i=0; i<lab1; i++) {
173 snprintf(p, 256-(p-buf1), "\003%3.3d", labnum1[i]);
174 p+=4;
175 }
176 snprintf(p, 256-(p-buf1), "%s", zname);
177
178 /* construct 2nd */
179 p = buf2+2;
180 for(i=0; i<lab2; i++) {
181 snprintf(p, 256-(p-buf2)-3, "\003%3.3d", labnum2[i]);
182 p+=4;
183 }
184 snprintf(p, 256-(p-buf2)-3, "%s", zname);
185 buf2[0] = (char)(strlen(buf2+2)+1);
186 buf2[1] = 0;
187
188 if(negverbose) {
189 log_nametypeclass(0, "add from", (uint8_t*)buf1, 0, 0);
190 log_nametypeclass(0, "add to ", (uint8_t*)buf2+2, 0, 0);
191 }
192 }
193
194 /** add a random item */
add_item(struct val_neg_cache * neg)195 static void add_item(struct val_neg_cache* neg)
196 {
197 struct val_neg_zone* z;
198 struct packed_rrset_data rd;
199 struct ub_packed_rrset_key nsec;
200 size_t rr_len;
201 time_t rr_ttl;
202 uint8_t* rr_data;
203 char* zname = get_random_zone();
204 char* from, *to;
205
206 lock_basic_lock(&neg->lock);
207 if(negverbose)
208 log_nametypeclass(0, "add to zone", (uint8_t*)zname, 0, 0);
209 z = neg_find_zone(neg, (uint8_t*)zname, strlen(zname)+1,
210 LDNS_RR_CLASS_IN);
211 if(!z) {
212 z = neg_create_zone(neg, (uint8_t*)zname, strlen(zname)+1,
213 LDNS_RR_CLASS_IN);
214 }
215 unit_assert(z);
216 val_neg_zone_take_inuse(z);
217
218 /* construct random NSEC item */
219 get_random_data(&from, &to, zname);
220
221 /* create nsec and insert it */
222 memset(&rd, 0, sizeof(rd));
223 memset(&nsec, 0, sizeof(nsec));
224 nsec.rk.dname = (uint8_t*)from;
225 nsec.rk.dname_len = strlen(from)+1;
226 nsec.rk.type = htons(LDNS_RR_TYPE_NSEC);
227 nsec.rk.rrset_class = htons(LDNS_RR_CLASS_IN);
228 nsec.entry.data = &rd;
229 rd.security = sec_status_secure;
230 rd.count = 1;
231 rd.rr_len = &rr_len;
232 rr_len = 19;
233 rd.rr_ttl = &rr_ttl;
234 rr_ttl = 0;
235 rd.rr_data = &rr_data;
236 rr_data = (uint8_t*)to;
237
238 neg_insert_data(neg, z, &nsec);
239 lock_basic_unlock(&neg->lock);
240 }
241
242 /** remove a random item */
remove_item(struct val_neg_cache * neg)243 static void remove_item(struct val_neg_cache* neg)
244 {
245 int n, i;
246 struct val_neg_data* d;
247 rbnode_type* walk;
248 struct val_neg_zone* z;
249
250 lock_basic_lock(&neg->lock);
251 if(neg->tree.count == 0) {
252 lock_basic_unlock(&neg->lock);
253 return; /* nothing to delete */
254 }
255
256 /* pick a random zone */
257 walk = rbtree_first(&neg->tree); /* first highest parent, big count */
258 z = (struct val_neg_zone*)walk;
259 n = random() % (int)(z->count);
260 if(negverbose)
261 printf("neg stress delete zone %d\n", n);
262 i=0;
263 walk = rbtree_first(&neg->tree);
264 z = (struct val_neg_zone*)walk;
265 while(i!=n+1 && walk && walk != RBTREE_NULL && !z->in_use) {
266 walk = rbtree_next(walk);
267 z = (struct val_neg_zone*)walk;
268 if(z->in_use)
269 i++;
270 }
271 if(!walk || walk == RBTREE_NULL) {
272 lock_basic_unlock(&neg->lock);
273 return;
274 }
275 if(!z->in_use) {
276 lock_basic_unlock(&neg->lock);
277 return;
278 }
279 if(negverbose)
280 log_nametypeclass(0, "delete zone", z->name, 0, 0);
281
282 /* pick a random nsec item. - that is in use */
283 walk = rbtree_first(&z->tree); /* first is highest parent */
284 d = (struct val_neg_data*)walk;
285 n = random() % (int)(d->count);
286 if(negverbose)
287 printf("neg stress delete item %d\n", n);
288 i=0;
289 walk = rbtree_first(&z->tree);
290 d = (struct val_neg_data*)walk;
291 while(i!=n+1 && walk && walk != RBTREE_NULL && !d->in_use) {
292 walk = rbtree_next(walk);
293 d = (struct val_neg_data*)walk;
294 if(d->in_use)
295 i++;
296 }
297 if(!walk || walk == RBTREE_NULL) {
298 lock_basic_unlock(&neg->lock);
299 return;
300 }
301 if(d->in_use) {
302 if(negverbose)
303 log_nametypeclass(0, "neg delete item:", d->name, 0, 0);
304 neg_delete_data(neg, d);
305 }
306 lock_basic_unlock(&neg->lock);
307 }
308
309 /** sum up the zone trees */
sumtrees_all(struct val_neg_cache * neg)310 static size_t sumtrees_all(struct val_neg_cache* neg)
311 {
312 size_t res = 0;
313 struct val_neg_zone* z;
314 RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
315 res += z->tree.count;
316 }
317 return res;
318 }
319
320 /** sum up the zone trees, in_use only */
sumtrees_inuse(struct val_neg_cache * neg)321 static size_t sumtrees_inuse(struct val_neg_cache* neg)
322 {
323 size_t res = 0;
324 struct val_neg_zone* z;
325 struct val_neg_data* d;
326 RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
327 /* get count of highest parent for num in use */
328 d = (struct val_neg_data*)rbtree_first(&z->tree);
329 if(d && (rbnode_type*)d!=RBTREE_NULL)
330 res += d->count;
331 }
332 return res;
333 }
334
335 /** check if lru is still valid */
check_lru(struct val_neg_cache * neg)336 static void check_lru(struct val_neg_cache* neg)
337 {
338 struct val_neg_data* p, *np;
339 size_t num = 0;
340 size_t inuse;
341 p = neg->first;
342 while(p) {
343 if(!p->prev) {
344 unit_assert(neg->first == p);
345 }
346 np = p->next;
347 if(np) {
348 unit_assert(np->prev == p);
349 } else {
350 unit_assert(neg->last == p);
351 }
352 num++;
353 p = np;
354 }
355 inuse = sumtrees_inuse(neg);
356 if(negverbose)
357 printf("num lru %d, inuse %d, all %d\n",
358 (int)num, (int)sumtrees_inuse(neg),
359 (int)sumtrees_all(neg));
360 unit_assert( num == inuse);
361 unit_assert( inuse <= sumtrees_all(neg));
362 }
363
364 /** sum up number of items inuse in subtree */
sum_subtree_inuse(struct val_neg_zone * zone,struct val_neg_data * data)365 static int sum_subtree_inuse(struct val_neg_zone* zone,
366 struct val_neg_data* data)
367 {
368 struct val_neg_data* d;
369 int num = 0;
370 RBTREE_FOR(d, struct val_neg_data*, &zone->tree) {
371 if(dname_subdomain_c(d->name, data->name)) {
372 if(d->in_use)
373 num++;
374 }
375 }
376 return num;
377 }
378
379 /** sum up number of items inuse in subtree */
sum_zone_subtree_inuse(struct val_neg_cache * neg,struct val_neg_zone * zone)380 static int sum_zone_subtree_inuse(struct val_neg_cache* neg,
381 struct val_neg_zone* zone)
382 {
383 struct val_neg_zone* z;
384 int num = 0;
385 RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
386 if(dname_subdomain_c(z->name, zone->name)) {
387 if(z->in_use)
388 num++;
389 }
390 }
391 return num;
392 }
393
394 /** check point in data tree */
check_data(struct val_neg_zone * zone,struct val_neg_data * data)395 static void check_data(struct val_neg_zone* zone, struct val_neg_data* data)
396 {
397 unit_assert(data->count > 0);
398 if(data->parent) {
399 unit_assert(data->parent->count >= data->count);
400 if(data->parent->in_use) {
401 unit_assert(data->parent->count > data->count);
402 }
403 unit_assert(data->parent->labs == data->labs-1);
404 /* and parent must be one label shorter */
405 unit_assert(data->name[0] == (data->len-data->parent->len-1));
406 unit_assert(query_dname_compare(data->name + data->name[0]+1,
407 data->parent->name) == 0);
408 } else {
409 /* must be apex */
410 unit_assert(dname_is_root(data->name));
411 }
412 /* tree property: */
413 unit_assert(data->count == sum_subtree_inuse(zone, data));
414 }
415
416 /** check if tree of data in zone is valid */
checkzonetree(struct val_neg_zone * zone)417 static void checkzonetree(struct val_neg_zone* zone)
418 {
419 struct val_neg_data* d;
420
421 /* check all data in tree */
422 RBTREE_FOR(d, struct val_neg_data*, &zone->tree) {
423 check_data(zone, d);
424 }
425 }
426
427 /** check if negative cache is still valid */
check_zone_invariants(struct val_neg_cache * neg,struct val_neg_zone * zone)428 static void check_zone_invariants(struct val_neg_cache* neg,
429 struct val_neg_zone* zone)
430 {
431 unit_assert(zone->nsec3_hash == 0);
432 unit_assert(zone->tree.cmp == &val_neg_data_compare);
433 unit_assert(zone->count != 0);
434
435 if(zone->tree.count == 0)
436 unit_assert(!zone->in_use);
437 else {
438 if(!zone->in_use) {
439 /* details on error */
440 log_nametypeclass(0, "zone", zone->name, 0, 0);
441 log_err("inuse %d count=%d tree.count=%d",
442 zone->in_use, zone->count,
443 (int)zone->tree.count);
444 if(negverbose)
445 print_neg_cache(neg);
446 }
447 unit_assert(zone->in_use);
448 }
449
450 if(zone->parent) {
451 unit_assert(zone->parent->count >= zone->count);
452 if(zone->parent->in_use) {
453 unit_assert(zone->parent->count > zone->count);
454 }
455 unit_assert(zone->parent->labs == zone->labs-1);
456 /* and parent must be one label shorter */
457 unit_assert(zone->name[0] == (zone->len-zone->parent->len-1));
458 unit_assert(query_dname_compare(zone->name + zone->name[0]+1,
459 zone->parent->name) == 0);
460 } else {
461 /* must be apex */
462 unit_assert(dname_is_root(zone->name));
463 }
464 /* tree property: */
465 unit_assert(zone->count == sum_zone_subtree_inuse(neg, zone));
466
467 /* check structure of zone data tree */
468 checkzonetree(zone);
469 }
470
471 /** check if negative cache is still valid */
check_neg_invariants(struct val_neg_cache * neg)472 static void check_neg_invariants(struct val_neg_cache* neg)
473 {
474 struct val_neg_zone* z;
475 /* check structure of LRU list */
476 lock_basic_lock(&neg->lock);
477 check_lru(neg);
478 unit_assert(neg->max == 1024*1024);
479 unit_assert(neg->nsec3_max_iter == 1500);
480 unit_assert(neg->tree.cmp == &val_neg_zone_compare);
481
482 if(neg->tree.count == 0) {
483 /* empty */
484 unit_assert(neg->tree.count == 0);
485 unit_assert(neg->first == NULL);
486 unit_assert(neg->last == NULL);
487 unit_assert(neg->use == 0);
488 lock_basic_unlock(&neg->lock);
489 return;
490 }
491
492 unit_assert(neg->first != NULL);
493 unit_assert(neg->last != NULL);
494
495 RBTREE_FOR(z, struct val_neg_zone*, &neg->tree) {
496 check_zone_invariants(neg, z);
497 }
498 lock_basic_unlock(&neg->lock);
499 }
500
501 /** perform stress test on insert and delete in neg cache */
stress_test(struct val_neg_cache * neg)502 static void stress_test(struct val_neg_cache* neg)
503 {
504 int i;
505 if(negverbose)
506 printf("negcache test\n");
507 for(i=0; i<100; i++) {
508 if(random() % 10 < 8)
509 add_item(neg);
510 else remove_item(neg);
511 check_neg_invariants(neg);
512 }
513 /* empty it */
514 if(negverbose)
515 printf("neg stress empty\n");
516 while(neg->first) {
517 remove_item(neg);
518 check_neg_invariants(neg);
519 }
520 if(negverbose)
521 printf("neg stress emptied\n");
522 unit_assert(neg->first == NULL);
523 /* insert again */
524 for(i=0; i<100; i++) {
525 if(random() % 10 < 8)
526 add_item(neg);
527 else remove_item(neg);
528 check_neg_invariants(neg);
529 }
530 }
531
neg_test(void)532 void neg_test(void)
533 {
534 struct val_neg_cache* neg;
535 srandom(48);
536 unit_show_feature("negative cache");
537
538 /* create with defaults */
539 neg = val_neg_create(NULL, 1500);
540 unit_assert(neg);
541
542 stress_test(neg);
543
544 neg_cache_delete(neg);
545 }
546