1 /*
2 * testcode/unitecs.c - unit test for ecs routines.
3 *
4 * Copyright (c) 2013, 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 /**
38 * \file
39 * Calls ecs related unit tests. Exits with code 1 on a failure.
40 */
41
42 #include "config.h"
43
44 #ifdef CLIENT_SUBNET
45
46 #include "util/log.h"
47 #include "util/module.h"
48 #include "testcode/unitmain.h"
49 #include "edns-subnet/addrtree.h"
50 #include "edns-subnet/subnetmod.h"
51
52 /*
53 void printkey(addrkey_t *k, addrlen_t bits)
54 {
55 int byte;
56 int bytes = bits/8 + ((bits%8)>0);
57 char msk = 0xFF;
58 for (byte = 0; byte < bytes; byte++) {
59 //~ if (byte+1 == bytes)
60 //~ msk = 0xFF<<(8-bits%8);
61 printf("%02x ", k[byte]&msk);
62 }
63 }
64
65 void print_tree(struct addrnode* node, int indent, int maxdepth)
66 {
67 struct addredge* edge;
68 int i, s, byte;
69 if (indent == 0) printf("-----Tree-----\n");
70 if (indent > maxdepth) {
71 printf("\n");
72 return;
73 }
74 printf("[node elem:%d] (%d)\n", node->elem != NULL, node);
75 for (i = 0; i<2; i++) {
76 if (node->edge[i]) {
77 for (s = 0; s < indent; s++) printf(" ");
78 printkey(node->edge[i]->str, node->edge[i]->len);
79 printf("(len %d bits, %d bytes) ", node->edge[i]->len,
80 node->edge[i]->len/8 + ((node->edge[i]->len%8)>0));
81 print_tree(node->edge[i]->node, indent+1, maxdepth);
82 }
83 }
84 if (indent == 0) printf("-----Tree-----");
85 }
86 */
87
88 /* what should we check?
89 * X - is it balanced? (a node with 1 child should not have
90 * a node with 1 child MUST have elem
91 * child must be sub of parent
92 * edge must be longer than parent edge
93 * */
addrtree_inconsistent_subtree(struct addrtree * tree,struct addredge * parent_edge,addrlen_t depth)94 static int addrtree_inconsistent_subtree(struct addrtree* tree,
95 struct addredge* parent_edge, addrlen_t depth)
96 {
97 struct addredge* edge;
98 struct addrnode* node = parent_edge->node;
99 int childcount, i, r;
100 if (depth > tree->max_depth) return 15;
101 childcount = (node->edge[0] != NULL) + (node->edge[1] != NULL);
102 /* Only nodes with 2 children should possibly have no element. */
103 if (childcount < 2 && !node->elem) return 10;
104 for (i = 0; i<2; i++) {
105 edge = node->edge[i];
106 if (!edge) continue;
107 if (!edge->node) return 11;
108 if (!edge->str) return 12;
109 if (edge->len <= parent_edge->len) return 13;
110 if (!unittest_wrapper_addrtree_issub(parent_edge->str,
111 parent_edge->len, edge->str, edge->len, 0))
112 return 14;
113 if ((r = addrtree_inconsistent_subtree(tree, edge, depth+1)) != 0)
114 return 100+r;
115 }
116 return 0;
117 }
118
addrtree_inconsistent(struct addrtree * tree)119 static int addrtree_inconsistent(struct addrtree* tree)
120 {
121 struct addredge* edge;
122 int i, r;
123
124 if (!tree) return 0;
125 if (!tree->root) return 1;
126
127 for (i = 0; i<2; i++) {
128 edge = tree->root->edge[i];
129 if (!edge) continue;
130 if (!edge->node) return 3;
131 if (!edge->str) return 4;
132 if ((r = addrtree_inconsistent_subtree(tree, edge, 1)) != 0)
133 return r;
134 }
135 return 0;
136 }
137
randomkey(addrkey_t ** k,int maxlen)138 static addrlen_t randomkey(addrkey_t **k, int maxlen)
139 {
140 int byte;
141 int bits = rand() % maxlen;
142 int bytes = bits/8 + (bits%8>0); /*ceil*/
143 *k = (addrkey_t *) malloc(bytes * sizeof(addrkey_t));
144 for (byte = 0; byte < bytes; byte++) {
145 (*k)[byte] = (addrkey_t)(rand() & 0xFF);
146 }
147 return (addrlen_t)bits;
148 }
149
elemfree(void * envptr,void * elemptr)150 static void elemfree(void *envptr, void *elemptr)
151 {
152 struct reply_info *elem = (struct reply_info *)elemptr;
153 (void)envptr;
154 free(elem);
155 }
156
consistency_test(void)157 static void consistency_test(void)
158 {
159 addrlen_t l;
160 time_t i;
161 uint32_t count;
162 addrkey_t *k;
163 struct addrtree* t;
164 struct module_env env;
165 struct reply_info *elem;
166 time_t timenow = 0;
167 unit_show_func("edns-subnet/addrtree.h", "Tree consistency check");
168 srand(9195); /* just some value for reproducibility */
169
170 t = addrtree_create(100, &elemfree, &unittest_wrapper_subnetmod_sizefunc, &env, 0);
171 count = t->node_count;
172 unit_assert(count == 0);
173 for (i = 0; i < 1000; i++) {
174 l = randomkey(&k, 128);
175 elem = (struct reply_info *) calloc(1, sizeof(struct reply_info));
176 addrtree_insert(t, k, l, 64, elem, timenow + 10, timenow);
177 /* This should always hold because no items ever expire. They
178 * could be overwritten, though. */
179 unit_assert( count <= t->node_count );
180 count = t->node_count;
181 free(k);
182 unit_assert( !addrtree_inconsistent(t) );
183 }
184 addrtree_delete(t);
185
186 unit_show_func("edns-subnet/addrtree.h", "Tree consistency with purge");
187 t = addrtree_create(8, &elemfree, &unittest_wrapper_subnetmod_sizefunc, &env, 0);
188 unit_assert(t->node_count == 0);
189 for (i = 0; i < 1000; i++) {
190 l = randomkey(&k, 128);
191 elem = (struct reply_info *) calloc(1, sizeof(struct reply_info));
192 addrtree_insert(t, k, l, 64, elem, i + 10, i);
193 free(k);
194 unit_assert( !addrtree_inconsistent(t) );
195 }
196 addrtree_delete(t);
197
198 unit_show_func("edns-subnet/addrtree.h", "Tree consistency with limit");
199 t = addrtree_create(8, &elemfree, &unittest_wrapper_subnetmod_sizefunc, &env, 27);
200 unit_assert(t->node_count == 0);
201 for (i = 0; i < 1000; i++) {
202 l = randomkey(&k, 128);
203 elem = (struct reply_info *) calloc(1, sizeof(struct reply_info));
204 addrtree_insert(t, k, l, 64, elem, i + 10, i);
205 unit_assert( t->node_count <= 27);
206 free(k);
207 unit_assert( !addrtree_inconsistent(t) );
208 }
209 addrtree_delete(t);
210 }
211
issub_test(void)212 static void issub_test(void)
213 {
214 addrkey_t k1[] = {0x55, 0x55, 0x5A};
215 addrkey_t k2[] = {0x55, 0x5D, 0x5A};
216 unit_show_func("edns-subnet/addrtree.h", "issub");
217 unit_assert( !unittest_wrapper_addrtree_issub(k1, 24, k2, 24, 0) );
218 unit_assert( unittest_wrapper_addrtree_issub(k1, 8, k2, 16, 0) );
219 unit_assert( unittest_wrapper_addrtree_issub(k2, 12, k1, 13, 0) );
220 unit_assert( !unittest_wrapper_addrtree_issub(k1, 16, k2, 12, 0) );
221 unit_assert( unittest_wrapper_addrtree_issub(k1, 12, k2, 12, 0) );
222 unit_assert( !unittest_wrapper_addrtree_issub(k1, 13, k2, 13, 0) );
223 unit_assert( unittest_wrapper_addrtree_issub(k1, 24, k2, 24, 13) );
224 unit_assert( !unittest_wrapper_addrtree_issub(k1, 24, k2, 20, 13) );
225 unit_assert( unittest_wrapper_addrtree_issub(k1, 20, k2, 24, 13) );
226 }
227
getbit_test(void)228 static void getbit_test(void)
229 {
230 addrkey_t k1[] = {0x55, 0x55, 0x5A};
231 int i;
232 unit_show_func("edns-subnet/addrtree.h", "getbit");
233 for(i = 0; i<20; i++) {
234 unit_assert( unittest_wrapper_addrtree_getbit(k1, 20, (addrlen_t)i) == (i&1) );
235 }
236 }
237
bits_common_test(void)238 static void bits_common_test(void)
239 {
240 addrkey_t k1[] = {0x12, 0x34, 0x56, 0x78, 0x9A, 0xBC, 0xDE, 0xF0};
241 addrkey_t k2[] = {0,0,0,0,0,0,0,0};
242 addrlen_t i;
243
244 unit_show_func("edns-subnet/addrtree.h", "bits_common");
245 for(i = 0; i<64; i++) {
246 unit_assert( unittest_wrapper_addrtree_bits_common(k1, 64, k1, 64, i) == 64 );
247 }
248 for(i = 0; i<8; i++) {
249 k2[i] = k1[i]^(1<<i);
250 }
251 unit_assert( unittest_wrapper_addrtree_bits_common(k1, 64, k2, 64, 0) == 0*8+7 );
252 unit_assert( unittest_wrapper_addrtree_bits_common(k1, 64, k2, 64, 8) == 1*8+6 );
253 unit_assert( unittest_wrapper_addrtree_bits_common(k1, 64, k2, 64, 16) == 2*8+5 );
254 unit_assert( unittest_wrapper_addrtree_bits_common(k1, 64, k2, 64, 24) == 3*8+4 );
255 unit_assert( unittest_wrapper_addrtree_bits_common(k1, 64, k2, 64, 32) == 4*8+3 );
256 unit_assert( unittest_wrapper_addrtree_bits_common(k1, 64, k2, 64, 40) == 5*8+2 );
257 unit_assert( unittest_wrapper_addrtree_bits_common(k1, 64, k2, 64, 48) == 6*8+1 );
258 unit_assert( unittest_wrapper_addrtree_bits_common(k1, 64, k2, 64, 56) == 7*8+0 );
259 }
260
cmpbit_test(void)261 static void cmpbit_test(void)
262 {
263 addrkey_t k1[] = {0xA5, 0x0F};
264 addrkey_t k2[] = {0x5A, 0xF0};
265 addrlen_t i;
266
267 unit_show_func("edns-subnet/addrtree.h", "cmpbit");
268 for(i = 0; i<16; i++) {
269 unit_assert( !unittest_wrapper_addrtree_cmpbit(k1,k1,i) );
270 unit_assert( unittest_wrapper_addrtree_cmpbit(k1,k2,i) );
271 }
272 }
273
ecs_test(void)274 void ecs_test(void)
275 {
276 unit_show_feature("ecs");
277 cmpbit_test();
278 bits_common_test();
279 getbit_test();
280 issub_test();
281 consistency_test();
282 }
283 #endif /* CLIENT_SUBNET */
284
285