testcode/unitecs.c

   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