OLD | NEW |
| (Empty) |
1 /* | |
2 * rdbx_driver.c | |
3 * | |
4 * driver for the rdbx implementation (replay database with extended range) | |
5 * | |
6 * David A. McGrew | |
7 * Cisco Systems, Inc. | |
8 */ | |
9 | |
10 /* | |
11 * | |
12 * Copyright (c) 2001-2006, Cisco Systems, Inc. | |
13 * All rights reserved. | |
14 * | |
15 * Redistribution and use in source and binary forms, with or without | |
16 * modification, are permitted provided that the following conditions | |
17 * are met: | |
18 * | |
19 * Redistributions of source code must retain the above copyright | |
20 * notice, this list of conditions and the following disclaimer. | |
21 * | |
22 * Redistributions in binary form must reproduce the above | |
23 * copyright notice, this list of conditions and the following | |
24 * disclaimer in the documentation and/or other materials provided | |
25 * with the distribution. | |
26 * | |
27 * Neither the name of the Cisco Systems, Inc. nor the names of its | |
28 * contributors may be used to endorse or promote products derived | |
29 * from this software without specific prior written permission. | |
30 * | |
31 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
32 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
33 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS | |
34 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE | |
35 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, | |
36 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES | |
37 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR | |
38 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
39 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
40 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
41 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | |
42 * OF THE POSSIBILITY OF SUCH DAMAGE. | |
43 * | |
44 */ | |
45 | |
46 #ifdef HAVE_CONFIG_H | |
47 #include <config.h> | |
48 #endif | |
49 | |
50 #include <stdio.h> /* for printf() */ | |
51 #include "getopt_s.h" /* for local getopt() */ | |
52 | |
53 #include "rdbx.h" | |
54 | |
55 #ifdef ROC_TEST | |
56 #error "rdbx_t won't work with ROC_TEST - bitmask same size as seq_median" | |
57 #endif | |
58 | |
59 #include "ut_sim.h" | |
60 | |
61 err_status_t | |
62 test_replay_dbx(int num_trials, unsigned long ws); | |
63 | |
64 double | |
65 rdbx_check_adds_per_second(int num_trials, unsigned long ws); | |
66 | |
67 void | |
68 usage(char *prog_name) { | |
69 printf("usage: %s [ -t | -v ]\n", prog_name); | |
70 exit(255); | |
71 } | |
72 | |
73 int | |
74 main (int argc, char *argv[]) { | |
75 double rate; | |
76 err_status_t status; | |
77 int q; | |
78 unsigned do_timing_test = 0; | |
79 unsigned do_validation = 0; | |
80 | |
81 /* process input arguments */ | |
82 while (1) { | |
83 q = getopt_s(argc, argv, "tv"); | |
84 if (q == -1) | |
85 break; | |
86 switch (q) { | |
87 case 't': | |
88 do_timing_test = 1; | |
89 break; | |
90 case 'v': | |
91 do_validation = 1; | |
92 break; | |
93 default: | |
94 usage(argv[0]); | |
95 } | |
96 } | |
97 | |
98 printf("rdbx (replay database w/ extended range) test driver\n" | |
99 "David A. McGrew\n" | |
100 "Cisco Systems, Inc.\n"); | |
101 | |
102 if (!do_validation && !do_timing_test) | |
103 usage(argv[0]); | |
104 | |
105 if (do_validation) { | |
106 printf("testing rdbx_t (ws=128)...\n"); | |
107 | |
108 status = test_replay_dbx(1 << 12, 128); | |
109 if (status) { | |
110 printf("failed\n"); | |
111 exit(1); | |
112 } | |
113 printf("passed\n"); | |
114 | |
115 printf("testing rdbx_t (ws=1024)...\n"); | |
116 | |
117 status = test_replay_dbx(1 << 12, 1024); | |
118 if (status) { | |
119 printf("failed\n"); | |
120 exit(1); | |
121 } | |
122 printf("passed\n"); | |
123 } | |
124 | |
125 if (do_timing_test) { | |
126 rate = rdbx_check_adds_per_second(1 << 18, 128); | |
127 printf("rdbx_check/replay_adds per second (ws=128): %e\n", rate); | |
128 rate = rdbx_check_adds_per_second(1 << 18, 1024); | |
129 printf("rdbx_check/replay_adds per second (ws=1024): %e\n", rate); | |
130 } | |
131 | |
132 return 0; | |
133 } | |
134 | |
135 void | |
136 print_rdbx(rdbx_t *rdbx) { | |
137 char buf[2048]; | |
138 printf("rdbx: {%llu, %s}\n", | |
139 (unsigned long long)(rdbx->index), | |
140 bitvector_bit_string(&rdbx->bitmask, buf, sizeof(buf)) | |
141 ); | |
142 } | |
143 | |
144 | |
145 /* | |
146 * rdbx_check_add(rdbx, idx) checks a known-to-be-good idx against | |
147 * rdbx, then adds it. if a failure is detected (i.e., the check | |
148 * indicates that the value is already in rdbx) then | |
149 * err_status_algo_fail is returned. | |
150 * | |
151 */ | |
152 | |
153 err_status_t | |
154 rdbx_check_add(rdbx_t *rdbx, uint32_t idx) { | |
155 int delta; | |
156 xtd_seq_num_t est; | |
157 | |
158 delta = index_guess(&rdbx->index, &est, idx); | |
159 | |
160 if (rdbx_check(rdbx, delta) != err_status_ok) { | |
161 printf("replay_check failed at index %u\n", idx); | |
162 return err_status_algo_fail; | |
163 } | |
164 | |
165 /* | |
166 * in practice, we'd authenticate the packet containing idx, using | |
167 * the estimated value est, at this point | |
168 */ | |
169 | |
170 if (rdbx_add_index(rdbx, delta) != err_status_ok) { | |
171 printf("rdbx_add_index failed at index %u\n", idx); | |
172 return err_status_algo_fail; | |
173 } | |
174 | |
175 return err_status_ok; | |
176 } | |
177 | |
178 /* | |
179 * rdbx_check_expect_failure(rdbx_t *rdbx, uint32_t idx) | |
180 * | |
181 * checks that a sequence number idx is in the replay database | |
182 * and thus will be rejected | |
183 */ | |
184 | |
185 err_status_t | |
186 rdbx_check_expect_failure(rdbx_t *rdbx, uint32_t idx) { | |
187 int delta; | |
188 xtd_seq_num_t est; | |
189 err_status_t status; | |
190 | |
191 delta = index_guess(&rdbx->index, &est, idx); | |
192 | |
193 status = rdbx_check(rdbx, delta); | |
194 if (status == err_status_ok) { | |
195 printf("delta: %d ", delta); | |
196 printf("replay_check failed at index %u (false positive)\n", idx); | |
197 return err_status_algo_fail; | |
198 } | |
199 | |
200 return err_status_ok; | |
201 } | |
202 | |
203 err_status_t | |
204 rdbx_check_add_unordered(rdbx_t *rdbx, uint32_t idx) { | |
205 int delta; | |
206 xtd_seq_num_t est; | |
207 err_status_t rstat; | |
208 | |
209 delta = index_guess(&rdbx->index, &est, idx); | |
210 | |
211 rstat = rdbx_check(rdbx, delta); | |
212 if ((rstat != err_status_ok) && (rstat != err_status_replay_old)) { | |
213 printf("replay_check_add_unordered failed at index %u\n", idx); | |
214 return err_status_algo_fail; | |
215 } | |
216 if (rstat == err_status_replay_old) { | |
217 return err_status_ok; | |
218 } | |
219 if (rdbx_add_index(rdbx, delta) != err_status_ok) { | |
220 printf("rdbx_add_index failed at index %u\n", idx); | |
221 return err_status_algo_fail; | |
222 } | |
223 | |
224 return err_status_ok; | |
225 } | |
226 | |
227 err_status_t | |
228 test_replay_dbx(int num_trials, unsigned long ws) { | |
229 rdbx_t rdbx; | |
230 uint32_t idx, ircvd; | |
231 ut_connection utc; | |
232 err_status_t status; | |
233 int num_fp_trials; | |
234 | |
235 status = rdbx_init(&rdbx, ws); | |
236 if (status) { | |
237 printf("replay_init failed with error code %d\n", status); | |
238 exit(1); | |
239 } | |
240 | |
241 /* | |
242 * test sequential insertion | |
243 */ | |
244 printf("\ttesting sequential insertion..."); | |
245 for (idx=0; (int) idx < num_trials; idx++) { | |
246 status = rdbx_check_add(&rdbx, idx); | |
247 if (status) | |
248 return status; | |
249 } | |
250 printf("passed\n"); | |
251 | |
252 /* | |
253 * test for false positives by checking all of the index | |
254 * values which we've just added | |
255 * | |
256 * note that we limit the number of trials here, since allowing the | |
257 * rollover counter to roll over would defeat this test | |
258 */ | |
259 num_fp_trials = num_trials % 0x10000; | |
260 if (num_fp_trials == 0) { | |
261 printf("warning: no false positive tests performed\n"); | |
262 } | |
263 printf("\ttesting for false positives..."); | |
264 for (idx=0; (int) idx < num_fp_trials; idx++) { | |
265 status = rdbx_check_expect_failure(&rdbx, idx); | |
266 if (status) | |
267 return status; | |
268 } | |
269 printf("passed\n"); | |
270 | |
271 /* re-initialize */ | |
272 rdbx_dealloc(&rdbx); | |
273 | |
274 if (rdbx_init(&rdbx, ws) != err_status_ok) { | |
275 printf("replay_init failed\n"); | |
276 return err_status_init_fail; | |
277 } | |
278 | |
279 /* | |
280 * test non-sequential insertion | |
281 * | |
282 * this test covers only fase negatives, since the values returned | |
283 * by ut_next_index(...) are distinct | |
284 */ | |
285 ut_init(&utc); | |
286 | |
287 printf("\ttesting non-sequential insertion..."); | |
288 for (idx=0; (int) idx < num_trials; idx++) { | |
289 ircvd = ut_next_index(&utc); | |
290 status = rdbx_check_add_unordered(&rdbx, ircvd); | |
291 if (status) | |
292 return status; | |
293 status = rdbx_check_expect_failure(&rdbx, ircvd); | |
294 if (status) | |
295 return status; | |
296 } | |
297 printf("passed\n"); | |
298 | |
299 /* re-initialize */ | |
300 rdbx_dealloc(&rdbx); | |
301 | |
302 if (rdbx_init(&rdbx, ws) != err_status_ok) { | |
303 printf("replay_init failed\n"); | |
304 return err_status_init_fail; | |
305 } | |
306 | |
307 /* | |
308 * test insertion with large gaps. | |
309 * check for false positives for each insertion. | |
310 */ | |
311 printf("\ttesting insertion with large gaps..."); | |
312 for (idx=0, ircvd=0; (int) idx < num_trials; idx++, ircvd += (1 << (rand() % 1
2))) { | |
313 status = rdbx_check_add(&rdbx, ircvd); | |
314 if (status) | |
315 return status; | |
316 status = rdbx_check_expect_failure(&rdbx, ircvd); | |
317 if (status) | |
318 return status; | |
319 } | |
320 printf("passed\n"); | |
321 | |
322 rdbx_dealloc(&rdbx); | |
323 | |
324 return err_status_ok; | |
325 } | |
326 | |
327 | |
328 | |
329 #include <time.h> /* for clock() */ | |
330 #include <stdlib.h> /* for random() */ | |
331 | |
332 double | |
333 rdbx_check_adds_per_second(int num_trials, unsigned long ws) { | |
334 uint32_t i; | |
335 int delta; | |
336 rdbx_t rdbx; | |
337 xtd_seq_num_t est; | |
338 clock_t timer; | |
339 int failures; /* count number of failures */ | |
340 | |
341 if (rdbx_init(&rdbx, ws) != err_status_ok) { | |
342 printf("replay_init failed\n"); | |
343 exit(1); | |
344 } | |
345 | |
346 failures = 0; | |
347 timer = clock(); | |
348 for(i=0; (int) i < num_trials; i++) { | |
349 | |
350 delta = index_guess(&rdbx.index, &est, i); | |
351 | |
352 if (rdbx_check(&rdbx, delta) != err_status_ok) | |
353 ++failures; | |
354 else | |
355 if (rdbx_add_index(&rdbx, delta) != err_status_ok) | |
356 ++failures; | |
357 } | |
358 timer = clock() - timer; | |
359 | |
360 printf("number of failures: %d \n", failures); | |
361 | |
362 rdbx_dealloc(&rdbx); | |
363 | |
364 return (double) CLOCKS_PER_SEC * num_trials / timer; | |
365 } | |
366 | |
OLD | NEW |