1386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 2386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * replay_driver.c 3386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 4386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * A driver for the replay_database implementation 5386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 6386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * David A. McGrew 7386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Cisco Systems, Inc. 8386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 9386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 10386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 11386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 12386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Copyright (c) 2001-2006, Cisco Systems, Inc. 13386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * All rights reserved. 14386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 15386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Redistribution and use in source and binary forms, with or without 16386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * modification, are permitted provided that the following conditions 17386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * are met: 18386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 19386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Redistributions of source code must retain the above copyright 20386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * notice, this list of conditions and the following disclaimer. 21386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 22386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Redistributions in binary form must reproduce the above 23386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * copyright notice, this list of conditions and the following 24386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * disclaimer in the documentation and/or other materials provided 25386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * with the distribution. 26386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 27386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * Neither the name of the Cisco Systems, Inc. nor the names of its 28386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * contributors may be used to endorse or promote products derived 29386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * from this software without specific prior written permission. 30386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 31386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 32386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 33386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 34386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 35386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, 36386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 37386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 38386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 39386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 40386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 41386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 42386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * OF THE POSSIBILITY OF SUCH DAMAGE. 43386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * 44386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 45386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 46386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#include <stdio.h> 47386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 48386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#include "rdb.h" 49386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#include "ut_sim.h" 50386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 51386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari/* 52386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * num_trials defines the number of trials that are used in the 53386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari * validation functions below 54386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari */ 55386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 56386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariunsigned num_trials = 1 << 16; 57386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 58386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 59386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritest_rdb_db(void); 60386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 61386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaridouble 62386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdb_check_adds_per_second(void); 63386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 64386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariint 65386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarimain (void) { 66386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari err_status_t err; 67386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 68386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari printf("testing anti-replay database (rdb_t)...\n"); 69386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari err = test_rdb_db(); 70386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (err) { 71386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari printf("failed\n"); 72386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari exit(1); 73386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 74386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari printf("done\n"); 75386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 76386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari printf("rdb_check/rdb_adds per second: %e\n", 77386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari rdb_check_adds_per_second()); 78386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 79386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return 0; 80386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 81386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 82386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 83386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarivoid 84386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagariprint_rdb(rdb_t *rdb) { 85386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari printf("rdb: {%u, %s}\n", rdb->window_start, v128_bit_string(&rdb->bitmask)); 86386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 87386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 88386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 89386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdb_check_add(rdb_t *rdb, uint32_t idx) { 90386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 91386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (rdb_check(rdb, idx) != err_status_ok) { 92386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari printf("rdb_check failed at index %u\n", idx); 93386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_fail; 94386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 95386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (rdb_add_index(rdb, idx) != err_status_ok) { 96386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari printf("rdb_add_index failed at index %u\n", idx); 97386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_fail; 98386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 99386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 100386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 101386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 102386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 103386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 104386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdb_check_expect_failure(rdb_t *rdb, uint32_t idx) { 105386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari err_status_t err; 106386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 107386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari err = rdb_check(rdb, idx); 108386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if ((err != err_status_replay_old) && (err != err_status_replay_fail)) { 109386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari printf("rdb_check failed at index %u (false positive)\n", idx); 110386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_fail; 111386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 112386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 113386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 114386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 115386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 116386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 117386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdb_check_unordered(rdb_t *rdb, uint32_t idx) { 118386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari err_status_t rstat; 119386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 120386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* printf("index: %u\n", idx); */ 121386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari rstat = rdb_check(rdb, idx); 122386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if ((rstat != err_status_ok) && (rstat != err_status_replay_old)) { 123386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari printf("rdb_check_unordered failed at index %u\n", idx); 124386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return rstat; 125386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 126386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 127386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 128386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 129386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarierr_status_t 130386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaritest_rdb_db() { 131386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari rdb_t rdb; 132386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari uint32_t idx, ircvd; 133386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari ut_connection utc; 134386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari err_status_t err; 135386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 136386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (rdb_init(&rdb) != err_status_ok) { 137386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari printf("rdb_init failed\n"); 138386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_init_fail; 139386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 140386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 141386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* test sequential insertion */ 142386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari for (idx=0; idx < num_trials; idx++) { 143386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari err = rdb_check_add(&rdb, idx); 144386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (err) 145386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err; 146386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 147386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 148386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* test for false positives */ 149386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari for (idx=0; idx < num_trials; idx++) { 150386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari err = rdb_check_expect_failure(&rdb, idx); 151386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (err) 152386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err; 153386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 154386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 155386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* re-initialize */ 156386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (rdb_init(&rdb) != err_status_ok) { 157386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari printf("rdb_init failed\n"); 158386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_fail; 159386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 160386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 161386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari /* test non-sequential insertion */ 162386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari ut_init(&utc); 163386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 164386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari for (idx=0; idx < num_trials; idx++) { 165386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari ircvd = ut_next_index(&utc); 166386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari err = rdb_check_unordered(&rdb, ircvd); 167386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (err) 168386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err; 169386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 170386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 171386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return err_status_ok; 172386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 173386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 174386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#include <time.h> /* for clock() */ 175386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#include <stdlib.h> /* for random() */ 176386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 177386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari#define REPLAY_NUM_TRIALS 10000000 178386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 179386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagaridouble 180386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagarirdb_check_adds_per_second(void) { 181386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari uint32_t i; 182386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari rdb_t rdb; 183386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari clock_t timer; 184386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari int failures; /* count number of failures */ 185386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 186386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (rdb_init(&rdb) != err_status_ok) { 187386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari printf("rdb_init failed\n"); 188386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari exit(1); 189386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 190386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 191386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari timer = clock(); 192386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari for(i=0; i < REPLAY_NUM_TRIALS; i+=3) { 193386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (rdb_check(&rdb, i+2) != err_status_ok) 194386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari ++failures; 195386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (rdb_add_index(&rdb, i+2) != err_status_ok) 196386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari ++failures; 197386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (rdb_check(&rdb, i+1) != err_status_ok) 198386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari ++failures; 199386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (rdb_add_index(&rdb, i+1) != err_status_ok) 200386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari ++failures; 201386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (rdb_check(&rdb, i) != err_status_ok) 202386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari ++failures; 203386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari if (rdb_add_index(&rdb, i) != err_status_ok) 204386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari ++failures; 205386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari } 206386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari timer = clock() - timer; 207386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari 208386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari return (double) CLOCKS_PER_SEC * REPLAY_NUM_TRIALS / timer; 209386ce4d9144fc190797f4e43a31aeaf76ca2e373Param Reddappagari} 210