1 /* 2 * testcode/unittcpreuse.c - unit test for tcp_reuse. 3 * 4 * Copyright (c) 2021, 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 * Tests the tcp_reuse functionality. 39 */ 40 41 #include "config.h" 42 #include "testcode/unitmain.h" 43 #include "util/log.h" 44 #include "util/random.h" 45 #include "services/outside_network.h" 46 47 #define MAX_TCP_WAITING_NODES 5 48 49 /** add number of new IDs to the reuse tree, randomly chosen */ 50 static void tcpid_addmore(struct reuse_tcp* reuse, 51 struct outside_network* outnet, unsigned int addnum) 52 { 53 unsigned int i; 54 struct waiting_tcp* w; 55 for(i=0; i<addnum; i++) { 56 uint16_t id = reuse_tcp_select_id(reuse, outnet); 57 unit_assert(!reuse_tcp_by_id_find(reuse, id)); 58 w = calloc(1, sizeof(*w)); 59 unit_assert(w); 60 w->id = id; 61 w->outnet = outnet; 62 w->next_waiting = (void*)reuse->pending; 63 reuse_tree_by_id_insert(reuse, w); 64 } 65 } 66 67 /** fill up the reuse ID tree and test assertions */ 68 static void tcpid_fillup(struct reuse_tcp* reuse, 69 struct outside_network* outnet) 70 { 71 int t, numtest=3; 72 for(t=0; t<numtest; t++) { 73 rbtree_init(&reuse->tree_by_id, reuse_id_cmp); 74 tcpid_addmore(reuse, outnet, 65535); 75 reuse_del_readwait(&reuse->tree_by_id); 76 } 77 } 78 79 /** test TCP ID selection */ 80 static void tcpid_test(void) 81 { 82 struct pending_tcp pend; 83 struct outside_network outnet; 84 unit_show_func("services/outside_network.c", "reuse_tcp_select_id"); 85 memset(&pend, 0, sizeof(pend)); 86 pend.reuse.pending = &pend; 87 memset(&outnet, 0, sizeof(outnet)); 88 outnet.rnd = ub_initstate(NULL); 89 rbtree_init(&pend.reuse.tree_by_id, reuse_id_cmp); 90 tcpid_fillup(&pend.reuse, &outnet); 91 ub_randfree(outnet.rnd); 92 } 93 94 /** check that the tree has present number of nodes and the LRU is linked 95 * properly. */ 96 static void check_tree_and_list(struct outside_network* outnet, int present) 97 { 98 int i; 99 struct reuse_tcp *reuse, *next_reuse; 100 unit_assert(present == (int)outnet->tcp_reuse.count); 101 if(present < 1) { 102 unit_assert(outnet->tcp_reuse_first == NULL); 103 unit_assert(outnet->tcp_reuse_last == NULL); 104 return; 105 } 106 unit_assert(outnet->tcp_reuse_first->item_on_lru_list); 107 unit_assert(!outnet->tcp_reuse_first->lru_prev); 108 reuse = outnet->tcp_reuse_first; 109 for(i=0; i<present-1; i++) { 110 unit_assert(reuse->item_on_lru_list); 111 unit_assert(reuse->lru_next); 112 unit_assert(reuse->lru_next != reuse); 113 next_reuse = reuse->lru_next; 114 unit_assert(next_reuse->lru_prev == reuse); 115 reuse = next_reuse; 116 } 117 unit_assert(!reuse->lru_next); 118 unit_assert(outnet->tcp_reuse_last->item_on_lru_list); 119 unit_assert(outnet->tcp_reuse_last == reuse); 120 } 121 122 /** creates pending_tcp. Copy of outside_network.c:create_pending_tcp without 123 * the comm_point creation */ 124 static int create_pending_tcp(struct outside_network* outnet) 125 { 126 size_t i; 127 if(outnet->num_tcp == 0) 128 return 1; /* no tcp needed, nothing to do */ 129 if(!(outnet->tcp_conns = (struct pending_tcp **)calloc( 130 outnet->num_tcp, sizeof(struct pending_tcp*)))) 131 return 0; 132 for(i=0; i<outnet->num_tcp; i++) { 133 if(!(outnet->tcp_conns[i] = (struct pending_tcp*)calloc(1, 134 sizeof(struct pending_tcp)))) 135 return 0; 136 outnet->tcp_conns[i]->next_free = outnet->tcp_free; 137 outnet->tcp_free = outnet->tcp_conns[i]; 138 } 139 return 1; 140 } 141 142 /** empty the tcp_reuse tree and LRU list */ 143 static void empty_tree(struct outside_network* outnet) 144 { 145 size_t i; 146 struct reuse_tcp* reuse; 147 reuse = outnet->tcp_reuse_first; 148 i = outnet->tcp_reuse.count; 149 while(reuse) { 150 reuse_tcp_remove_tree_list(outnet, reuse); 151 check_tree_and_list(outnet, --i); 152 reuse = outnet->tcp_reuse_first; 153 } 154 } 155 156 /** check removal of the LRU element on the given position of total elements */ 157 static void check_removal(struct outside_network* outnet, int position, int total) 158 { 159 int i; 160 struct reuse_tcp* reuse; 161 empty_tree(outnet); 162 for(i=0; i<total; i++) { 163 reuse_tcp_insert(outnet, outnet->tcp_conns[i]); 164 } 165 check_tree_and_list(outnet, total); 166 reuse = outnet->tcp_reuse_first; 167 for(i=0; i<position; i++) reuse = reuse->lru_next; 168 reuse_tcp_remove_tree_list(outnet, reuse); 169 check_tree_and_list(outnet, total-1); 170 } 171 172 /** check snipping off the last element of the LRU with total elements */ 173 static void check_snip(struct outside_network* outnet, int total) 174 { 175 int i; 176 struct reuse_tcp* reuse; 177 empty_tree(outnet); 178 for(i=0; i<total; i++) { 179 reuse_tcp_insert(outnet, outnet->tcp_conns[i]); 180 } 181 check_tree_and_list(outnet, total); 182 reuse = reuse_tcp_lru_snip(outnet); 183 while(reuse) { 184 reuse_tcp_remove_tree_list(outnet, reuse); 185 check_tree_and_list(outnet, --total); 186 reuse = reuse_tcp_lru_snip(outnet); 187 } 188 unit_assert(outnet->tcp_reuse_first == NULL); 189 unit_assert(outnet->tcp_reuse_last == NULL); 190 unit_assert(outnet->tcp_reuse.count == 0); 191 } 192 193 /** test tcp_reuse tree and LRU list functions */ 194 static void tcp_reuse_tree_list_test(void) 195 { 196 size_t i; 197 struct outside_network outnet; 198 struct reuse_tcp* reuse; 199 memset(&outnet, 0, sizeof(outnet)); 200 rbtree_init(&outnet.tcp_reuse, reuse_cmp); 201 outnet.num_tcp = 5; 202 outnet.tcp_reuse_max = outnet.num_tcp; 203 if(!create_pending_tcp(&outnet)) fatal_exit("out of memory"); 204 /* add all to the tree */ 205 unit_show_func("services/outside_network.c", "reuse_tcp_insert"); 206 for(i=0; i<outnet.num_tcp; i++) { 207 reuse_tcp_insert(&outnet, outnet.tcp_conns[i]); 208 check_tree_and_list(&outnet, i+1); 209 } 210 /* check touching */ 211 unit_show_func("services/outside_network.c", "reuse_tcp_lru_touch"); 212 for(i=0; i<outnet.tcp_reuse.count; i++) { 213 for(reuse = outnet.tcp_reuse_first; reuse->lru_next; reuse = reuse->lru_next); 214 reuse_tcp_lru_touch(&outnet, reuse); 215 check_tree_and_list(&outnet, outnet.num_tcp); 216 } 217 /* check removal */ 218 unit_show_func("services/outside_network.c", "reuse_tcp_remove_tree_list"); 219 check_removal(&outnet, 2, 5); 220 check_removal(&outnet, 1, 3); 221 check_removal(&outnet, 1, 2); 222 /* check snip */ 223 unit_show_func("services/outside_network.c", "reuse_tcp_lru_snip"); 224 check_snip(&outnet, 4); 225 226 for(i=0; i<outnet.num_tcp; i++) 227 if(outnet.tcp_conns[i]) { 228 free(outnet.tcp_conns[i]); 229 } 230 free(outnet.tcp_conns); 231 } 232 233 static void check_waiting_tcp_list(struct outside_network* outnet, 234 struct waiting_tcp* first, struct waiting_tcp* last, size_t total) 235 { 236 size_t i, j; 237 struct waiting_tcp* w = outnet->tcp_wait_first; 238 struct waiting_tcp* n = NULL; 239 if(first) unit_assert(outnet->tcp_wait_first == first); 240 if(last) unit_assert(outnet->tcp_wait_last == last && !last->next_waiting); 241 for(i=0; w; i++) { 242 unit_assert(i<total); /* otherwise we are looping */ 243 unit_assert(w->on_tcp_waiting_list); 244 n = w->next_waiting; 245 for(j=0; n; j++) { 246 unit_assert(j<total-i-1); /* otherwise we are looping */ 247 unit_assert(n != w); 248 n = n->next_waiting; 249 } 250 w = w->next_waiting; 251 } 252 } 253 254 /** clear the tcp waiting list */ 255 static void waiting_tcp_list_clear(struct outside_network* outnet) 256 { 257 struct waiting_tcp* w = outnet->tcp_wait_first, *n = NULL; 258 if(!w) return; 259 unit_assert(outnet->tcp_wait_first); 260 unit_assert(outnet->tcp_wait_last); 261 while(w) { 262 n = w->next_waiting; 263 w->on_tcp_waiting_list = 0; 264 w->next_waiting = (struct waiting_tcp*)1; /* In purpose faux value */ 265 w = n; 266 } 267 outnet->tcp_wait_first = NULL; 268 outnet->tcp_wait_last = NULL; 269 } 270 271 /** check removal of the waiting_tcp element on the given position of total 272 * elements */ 273 static void check_waiting_tcp_removal(int is_pop, 274 struct outside_network* outnet, struct waiting_tcp* store, 275 size_t position, size_t total) 276 { 277 size_t i; 278 struct waiting_tcp* w; 279 waiting_tcp_list_clear(outnet); 280 for(i=0; i<total; i++) { 281 outnet_waiting_tcp_list_add(outnet, &store[i], 0); 282 } 283 check_waiting_tcp_list(outnet, &store[0], &store[total-1], total); 284 285 if(is_pop) { 286 w = outnet_waiting_tcp_list_pop(outnet); 287 unit_assert(w); /* please clang-analyser */ 288 } else { 289 w = outnet->tcp_wait_first; 290 for(i=0; i<position; i++) { 291 unit_assert(w); /* please clang-analyser */ 292 w = w->next_waiting; 293 } 294 unit_assert(w); /* please clang-analyser */ 295 outnet_waiting_tcp_list_remove(outnet, w); 296 } 297 unit_assert(!(w->on_tcp_waiting_list || w->next_waiting)); 298 299 if(position == 0 && total == 1) { 300 /* the list should be empty */ 301 check_waiting_tcp_list(outnet, NULL, NULL, total-1); 302 } else if(position == 0) { 303 /* first element should be gone */ 304 check_waiting_tcp_list(outnet, &store[1], &store[total-1], total-1); 305 } else if(position == total - 1) { 306 /* last element should be gone */ 307 check_waiting_tcp_list(outnet, &store[0], &store[total-2], total-1); 308 } else { 309 /* an element should be gone */ 310 check_waiting_tcp_list(outnet, &store[0], &store[total-1], total-1); 311 } 312 } 313 314 static void waiting_tcp_list_test(void) 315 { 316 size_t i = 0; 317 struct outside_network outnet; 318 struct waiting_tcp* w, *t = NULL; 319 struct waiting_tcp store[MAX_TCP_WAITING_NODES]; 320 memset(&outnet, 0, sizeof(outnet)); 321 memset(&store, 0, sizeof(store)); 322 323 /* Check add first on empty list */ 324 unit_show_func("services/outside_network.c", "outnet_waiting_tcp_list_add_first"); 325 t = &store[i]; 326 outnet_waiting_tcp_list_add_first(&outnet, t, 0); 327 check_waiting_tcp_list(&outnet, t, t, 1); 328 329 /* Check add */ 330 unit_show_func("services/outside_network.c", "outnet_waiting_tcp_list_add"); 331 for(i=1; i<MAX_TCP_WAITING_NODES-1; i++) { 332 w = &store[i]; 333 outnet_waiting_tcp_list_add(&outnet, w, 0); 334 } 335 check_waiting_tcp_list(&outnet, t, w, MAX_TCP_WAITING_NODES-1); 336 337 /* Check add first on populated list */ 338 unit_show_func("services/outside_network.c", "outnet_waiting_tcp_list_add_first"); 339 w = &store[i]; 340 t = outnet.tcp_wait_last; 341 outnet_waiting_tcp_list_add_first(&outnet, w, 0); 342 check_waiting_tcp_list(&outnet, w, t, MAX_TCP_WAITING_NODES); 343 344 /* Check removal */ 345 unit_show_func("services/outside_network.c", "outnet_waiting_tcp_list_remove"); 346 check_waiting_tcp_removal(0, &outnet, store, 2, 5); 347 check_waiting_tcp_removal(0, &outnet, store, 1, 3); 348 check_waiting_tcp_removal(0, &outnet, store, 0, 2); 349 check_waiting_tcp_removal(0, &outnet, store, 1, 2); 350 check_waiting_tcp_removal(0, &outnet, store, 0, 1); 351 352 /* Check pop */ 353 unit_show_func("services/outside_network.c", "outnet_waiting_tcp_list_pop"); 354 check_waiting_tcp_removal(1, &outnet, store, 0, 3); 355 check_waiting_tcp_removal(1, &outnet, store, 0, 2); 356 check_waiting_tcp_removal(1, &outnet, store, 0, 1); 357 } 358 359 static void check_reuse_write_wait(struct reuse_tcp* reuse, 360 struct waiting_tcp* first, struct waiting_tcp* last, size_t total) 361 { 362 size_t i, j; 363 struct waiting_tcp* w = reuse->write_wait_first; 364 struct waiting_tcp* n = NULL; 365 if(first) unit_assert(reuse->write_wait_first == first && !first->write_wait_prev); 366 if(last) unit_assert(reuse->write_wait_last == last && !last->write_wait_next); 367 /* check one way */ 368 for(i=0; w; i++) { 369 unit_assert(i<total); /* otherwise we are looping */ 370 unit_assert(w->write_wait_queued); 371 n = w->write_wait_next; 372 for(j=0; n; j++) { 373 unit_assert(j<total-i-1); /* otherwise we are looping */ 374 unit_assert(n != w); 375 n = n->write_wait_next; 376 } 377 w = w->write_wait_next; 378 } 379 /* check the other way */ 380 w = reuse->write_wait_last; 381 for(i=0; w; i++) { 382 unit_assert(i<total); /* otherwise we are looping */ 383 unit_assert(w->write_wait_queued); 384 n = w->write_wait_prev; 385 for(j=0; n; j++) { 386 unit_assert(j<total-i-1); /* otherwise we are looping */ 387 unit_assert(n != w); 388 n = n->write_wait_prev; 389 } 390 w = w->write_wait_prev; 391 } 392 } 393 394 /** clear the tcp waiting list */ 395 static void reuse_write_wait_clear(struct reuse_tcp* reuse) 396 { 397 struct waiting_tcp* w = reuse->write_wait_first, *n = NULL; 398 if(!w) return; 399 unit_assert(reuse->write_wait_first); 400 unit_assert(reuse->write_wait_last); 401 while(w) { 402 n = w->write_wait_next; 403 w->write_wait_queued = 0; 404 w->write_wait_next = (struct waiting_tcp*)1; /* In purpose faux value */ 405 w->write_wait_prev = (struct waiting_tcp*)1; /* In purpose faux value */ 406 w = n; 407 } 408 reuse->write_wait_first = NULL; 409 reuse->write_wait_last = NULL; 410 } 411 412 /** check removal of the reuse_write_wait element on the given position of total 413 * elements */ 414 static void check_reuse_write_wait_removal(int is_pop, 415 struct reuse_tcp* reuse, struct waiting_tcp* store, 416 size_t position, size_t total) 417 { 418 size_t i; 419 struct waiting_tcp* w; 420 reuse_write_wait_clear(reuse); 421 for(i=0; i<total; i++) { 422 reuse_write_wait_push_back(reuse, &store[i]); 423 } 424 check_reuse_write_wait(reuse, &store[0], &store[total-1], total); 425 426 if(is_pop) { 427 w = reuse_write_wait_pop(reuse); 428 } else { 429 w = reuse->write_wait_first; 430 for(i=0; i<position; i++) w = w->write_wait_next; 431 reuse_write_wait_remove(reuse, w); 432 } 433 unit_assert(!(w->write_wait_queued || w->write_wait_next || w->write_wait_prev)); 434 435 if(position == 0 && total == 1) { 436 /* the list should be empty */ 437 check_reuse_write_wait(reuse, NULL, NULL, total-1); 438 } else if(position == 0) { 439 /* first element should be gone */ 440 check_reuse_write_wait(reuse, &store[1], &store[total-1], total-1); 441 } else if(position == total - 1) { 442 /* last element should be gone */ 443 check_reuse_write_wait(reuse, &store[0], &store[total-2], total-1); 444 } else { 445 /* an element should be gone */ 446 check_reuse_write_wait(reuse, &store[0], &store[total-1], total-1); 447 } 448 } 449 450 static void reuse_write_wait_test(void) 451 { 452 size_t i; 453 struct reuse_tcp reuse; 454 struct waiting_tcp store[MAX_TCP_WAITING_NODES]; 455 struct waiting_tcp* w; 456 memset(&reuse, 0, sizeof(reuse)); 457 memset(&store, 0, sizeof(store)); 458 459 /* Check adding */ 460 unit_show_func("services/outside_network.c", "reuse_write_wait_push_back"); 461 for(i=0; i<MAX_TCP_WAITING_NODES; i++) { 462 w = &store[i]; 463 reuse_write_wait_push_back(&reuse, w); 464 } 465 check_reuse_write_wait(&reuse, &store[0], w, MAX_TCP_WAITING_NODES); 466 467 /* Check removal */ 468 unit_show_func("services/outside_network.c", "reuse_write_wait_remove"); 469 check_reuse_write_wait_removal(0, &reuse, store, 2, 5); 470 check_reuse_write_wait_removal(0, &reuse, store, 1, 3); 471 check_reuse_write_wait_removal(0, &reuse, store, 0, 2); 472 check_reuse_write_wait_removal(0, &reuse, store, 1, 2); 473 check_reuse_write_wait_removal(0, &reuse, store, 0, 1); 474 475 /* Check pop */ 476 unit_show_func("services/outside_network.c", "reuse_write_wait_pop"); 477 check_reuse_write_wait_removal(1, &reuse, store, 0, 3); 478 check_reuse_write_wait_removal(1, &reuse, store, 0, 2); 479 check_reuse_write_wait_removal(1, &reuse, store, 0, 1); 480 } 481 482 void tcpreuse_test(void) 483 { 484 unit_show_feature("tcp_reuse"); 485 tcpid_test(); 486 tcp_reuse_tree_list_test(); 487 waiting_tcp_list_test(); 488 reuse_write_wait_test(); 489 } 490