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 * */ 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 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 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 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 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 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 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 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 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 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