1 /*
2 * random-test.c: Test delta generation and application using random data.
3 *
4 * ====================================================================
5 * Licensed to the Apache Software Foundation (ASF) under one
6 * or more contributor license agreements. See the NOTICE file
7 * distributed with this work for additional information
8 * regarding copyright ownership. The ASF licenses this file
9 * to you under the Apache License, Version 2.0 (the
10 * "License"); you may not use this file except in compliance
11 * with the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing,
16 * software distributed under the License is distributed on an
17 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18 * KIND, either express or implied. See the License for the
19 * specific language governing permissions and limitations
20 * under the License.
21 * ====================================================================
22 */
23
24
25 #include <assert.h>
26
27 #define APR_WANT_STDIO
28 #define APR_WANT_STRFUNC
29 #include <apr_want.h>
30 #include <apr_general.h>
31 #include <apr_getopt.h>
32 #include <apr_file_io.h>
33
34 #include "../svn_test.h"
35
36 #include "svn_delta.h"
37 #include "svn_pools.h"
38 #include "svn_error.h"
39
40 #include "../../libsvn_delta/delta.h"
41 #include "delta-window-test.h"
42
43
44 #define DEFAULT_ITERATIONS 60
45 #define DEFAULT_MAXLEN (100 * 1024)
46 #define DEFAULT_DUMP_FILES 0
47 #define DEFAULT_PRINT_WINDOWS 0
48 #define SEEDS 50
49 #define MAXSEQ 100
50
51
52 /* Initialize parameters for the random tests. */
53 extern int test_argc;
54 extern const char **test_argv;
55
init_params(apr_uint32_t * seed,apr_uint32_t * maxlen,int * iterations,int * dump_files,int * print_windows,const char ** random_bytes,apr_size_t * bytes_range,apr_pool_t * pool)56 static void init_params(apr_uint32_t *seed,
57 apr_uint32_t *maxlen, int *iterations,
58 int *dump_files, int *print_windows,
59 const char **random_bytes,
60 apr_size_t *bytes_range,
61 apr_pool_t *pool)
62 {
63 apr_getopt_t *opt;
64 char optch;
65 const char *opt_arg;
66 apr_status_t status;
67
68 *seed = (apr_uint32_t) apr_time_now();
69 *maxlen = DEFAULT_MAXLEN;
70 *iterations = DEFAULT_ITERATIONS;
71 *dump_files = DEFAULT_DUMP_FILES;
72 *print_windows = DEFAULT_PRINT_WINDOWS;
73 *random_bytes = NULL;
74 *bytes_range = 256;
75
76 apr_getopt_init(&opt, pool, test_argc, test_argv);
77 while (APR_SUCCESS
78 == (status = apr_getopt(opt, "s:l:n:r:FW", &optch, &opt_arg)))
79 {
80 switch (optch)
81 {
82 case 's':
83 *seed = (apr_uint32_t) atol(opt_arg);
84 break;
85 case 'l':
86 *maxlen = atoi(opt_arg);
87 break;
88 case 'n':
89 *iterations = atoi(opt_arg);
90 break;
91 case 'r':
92 *random_bytes = opt_arg + 1;
93 *bytes_range = strlen(*random_bytes);
94 break;
95 case 'F':
96 *dump_files = !*dump_files;
97 break;
98 case 'W':
99 *print_windows = !*print_windows;
100 break;
101 }
102 }
103 }
104
105
106 /* Open a temporary file. */
107 static apr_file_t *
open_tempfile(const char * name_template,apr_pool_t * pool)108 open_tempfile(const char *name_template, apr_pool_t *pool)
109 {
110 apr_status_t apr_err;
111 apr_file_t *fp = NULL;
112 char *templ = (char *)apr_pstrdup(
113 pool, svn_test_data_path(
114 name_template ? name_template : "tempfile_XXXXXX", pool));
115
116 apr_err = apr_file_mktemp(&fp, templ, 0, pool);
117 assert(apr_err == 0);
118 assert(fp != NULL);
119 return fp;
120 }
121
122 /* Rewind the file pointer */
rewind_file(apr_file_t * fp)123 static void rewind_file(apr_file_t *fp)
124 {
125 apr_off_t offset = 0;
126 #ifndef NDEBUG
127 apr_status_t apr_err =
128 #endif
129 apr_file_seek(fp, APR_SET, &offset);
130 assert(apr_err == 0);
131 assert(offset == 0);
132 }
133
134
135 static void
dump_file_contents(apr_file_t * fp)136 dump_file_contents(apr_file_t *fp)
137 {
138 static char file_buffer[10240];
139 apr_size_t length = sizeof file_buffer;
140 fputs("--------\n", stdout);
141 do
142 {
143 apr_file_read_full(fp, file_buffer, sizeof file_buffer, &length);
144 fwrite(file_buffer, 1, length, stdout);
145 }
146 while (length == sizeof file_buffer);
147 putc('\n', stdout);
148 rewind_file(fp);
149 }
150
151 /* Generate a temporary file containing sort-of random data. Diffs
152 between files of random data tend to be pretty boring, so we try to
153 make sure there are a bunch of common substrings between two runs
154 of this function with the same seedbase. */
155 static apr_file_t *
generate_random_file(apr_uint32_t maxlen,apr_uint32_t subseed_base,apr_uint32_t * seed,const char * random_bytes,apr_size_t bytes_range,int dump_files,apr_pool_t * pool)156 generate_random_file(apr_uint32_t maxlen,
157 apr_uint32_t subseed_base,
158 apr_uint32_t *seed,
159 const char *random_bytes,
160 apr_size_t bytes_range,
161 int dump_files,
162 apr_pool_t *pool)
163 {
164 static char file_buffer[10240];
165 char *buf = file_buffer;
166 char *const end = buf + sizeof file_buffer;
167
168 apr_uint32_t len, seqlen;
169 apr_file_t *fp;
170 unsigned long r;
171
172 fp = open_tempfile("random_XXXXXX", pool);
173 len = svn_test_rand(seed) % maxlen; /* We might go over this by a bit. */
174 while (len > 0)
175 {
176 /* Generate a pseudo-random sequence of up to MAXSEQ bytes,
177 where the seed is in the range [seedbase..seedbase+MAXSEQ-1].
178 (Use our own pseudo-random number generator here to avoid
179 clobbering the seed of the libc random number generator.) */
180
181 seqlen = svn_test_rand(seed) % MAXSEQ;
182 if (seqlen > len) seqlen = len;
183 len -= seqlen;
184 r = subseed_base + svn_test_rand(seed) % SEEDS;
185 while (seqlen-- > 0)
186 {
187 const int ch = (random_bytes
188 ? (unsigned)random_bytes[r % bytes_range]
189 : (int)(r % bytes_range));
190 if (buf == end)
191 {
192 apr_size_t ignore_length;
193 apr_file_write_full(fp, file_buffer, sizeof file_buffer,
194 &ignore_length);
195 buf = file_buffer;
196 }
197
198 *buf++ = (char)ch;
199 r = r * 1103515245 + 12345;
200 }
201 }
202
203 if (buf > file_buffer)
204 {
205 apr_size_t ignore_length;
206 apr_file_write_full(fp, file_buffer, buf - file_buffer, &ignore_length);
207 }
208 rewind_file(fp);
209
210 if (dump_files)
211 dump_file_contents(fp);
212
213 return fp;
214 }
215
216 /* Compare two open files. The file positions may change. */
217 static svn_error_t *
compare_files(apr_file_t * f1,apr_file_t * f2,int dump_files)218 compare_files(apr_file_t *f1, apr_file_t *f2, int dump_files)
219 {
220 static char file_buffer_1[10240];
221 static char file_buffer_2[10240];
222
223 char *c1, *c2;
224 apr_off_t pos = 0;
225 apr_size_t len1, len2;
226
227 rewind_file(f1);
228 rewind_file(f2);
229
230 if (dump_files)
231 dump_file_contents(f2);
232
233 do
234 {
235 apr_file_read_full(f1, file_buffer_1, sizeof file_buffer_1, &len1);
236 apr_file_read_full(f2, file_buffer_2, sizeof file_buffer_2, &len2);
237
238 for (c1 = file_buffer_1, c2 = file_buffer_2;
239 c1 < file_buffer_1 + len1 && c2 < file_buffer_2 + len2;
240 ++c1, ++c2, ++pos)
241 {
242 if (*c1 != *c2)
243 return svn_error_createf(SVN_ERR_TEST_FAILED, NULL,
244 "mismatch at position %"APR_OFF_T_FMT,
245 pos);
246 }
247
248 if (len1 != len2)
249 return svn_error_createf(SVN_ERR_TEST_FAILED, NULL,
250 "unequal file sizes at position"
251 " %"APR_OFF_T_FMT, pos);
252 }
253 while (len1 == sizeof file_buffer_1);
254 return SVN_NO_ERROR;
255 }
256
257
258 static apr_file_t *
copy_tempfile(apr_file_t * fp,apr_pool_t * pool)259 copy_tempfile(apr_file_t *fp, apr_pool_t *pool)
260 {
261 static char file_buffer[10240];
262 apr_file_t *newfp;
263 apr_size_t length1, length2;
264
265 newfp = open_tempfile("copy_XXXXXX", pool);
266
267 rewind_file(fp);
268 do
269 {
270 apr_file_read_full(fp, file_buffer, sizeof file_buffer, &length1);
271 apr_file_write_full(newfp, file_buffer, length1, &length2);
272 assert(length1 == length2);
273 }
274 while (length1 == sizeof file_buffer);
275
276 rewind_file(fp);
277 rewind_file(newfp);
278 return newfp;
279 }
280
281
282
283 /* (Note: *LAST_SEED is an output parameter.) */
284 static svn_error_t *
do_random_test(apr_pool_t * pool,apr_uint32_t * last_seed)285 do_random_test(apr_pool_t *pool,
286 apr_uint32_t *last_seed)
287 {
288 apr_uint32_t seed, maxlen;
289 apr_size_t bytes_range;
290 int i, iterations, dump_files, print_windows;
291 const char *random_bytes;
292
293 /* Initialize parameters and print out the seed in case we dump core
294 or something. */
295 init_params(&seed, &maxlen, &iterations, &dump_files, &print_windows,
296 &random_bytes, &bytes_range, pool);
297
298 for (i = 0; i < iterations; i++)
299 {
300 /* Generate source and target for the delta and its application. */
301 apr_uint32_t subseed_base = svn_test_rand((*last_seed = seed, &seed));
302 apr_file_t *source = generate_random_file(maxlen, subseed_base, &seed,
303 random_bytes, bytes_range,
304 dump_files, pool);
305 apr_file_t *target = generate_random_file(maxlen, subseed_base, &seed,
306 random_bytes, bytes_range,
307 dump_files, pool);
308 apr_file_t *source_copy = copy_tempfile(source, pool);
309 apr_file_t *target_regen = open_tempfile(NULL, pool);
310
311 svn_txdelta_stream_t *txdelta_stream;
312 svn_txdelta_window_handler_t handler;
313 svn_stream_t *stream;
314 void *handler_baton;
315
316 /* Set up a four-stage pipeline: create a delta, convert it to
317 svndiff format, parse it back into delta format, and apply it
318 to a copy of the source file to see if we get the same target
319 back. */
320 apr_pool_t *delta_pool = svn_pool_create(pool);
321
322 /* Make stage 4: apply the text delta. */
323 svn_txdelta_apply(svn_stream_from_aprfile(source_copy, delta_pool),
324 svn_stream_from_aprfile(target_regen, delta_pool),
325 NULL, NULL, delta_pool, &handler, &handler_baton);
326
327 /* Make stage 3: reparse the text delta. */
328 stream = svn_txdelta_parse_svndiff(handler, handler_baton, TRUE,
329 delta_pool);
330
331 /* Make stage 2: encode the text delta in svndiff format using
332 varying svndiff versions and compression levels. */
333 svn_txdelta_to_svndiff3(&handler, &handler_baton, stream, i % 3,
334 i % 10, delta_pool);
335
336 /* Make stage 1: create the text delta. */
337 svn_txdelta2(&txdelta_stream,
338 svn_stream_from_aprfile(source, delta_pool),
339 svn_stream_from_aprfile(target, delta_pool),
340 FALSE,
341 delta_pool);
342
343 SVN_ERR(svn_txdelta_send_txstream(txdelta_stream,
344 handler,
345 handler_baton,
346 delta_pool));
347
348 svn_pool_destroy(delta_pool);
349
350 SVN_ERR(compare_files(target, target_regen, dump_files));
351
352 apr_file_close(source);
353 apr_file_close(target);
354 apr_file_close(source_copy);
355 apr_file_close(target_regen);
356 }
357
358 return SVN_NO_ERROR;
359 }
360
361 /* Implements svn_test_driver_t. */
362 static svn_error_t *
random_test(apr_pool_t * pool)363 random_test(apr_pool_t *pool)
364 {
365 apr_uint32_t seed;
366 svn_error_t *err = do_random_test(pool, &seed);
367 if (err)
368 fprintf(stderr, "SEED: %lu\n", (unsigned long)seed);
369 return err;
370 }
371
372
373
374 /* (Note: *LAST_SEED is an output parameter.) */
375 static svn_error_t *
do_random_combine_test(apr_pool_t * pool,apr_uint32_t * last_seed)376 do_random_combine_test(apr_pool_t *pool,
377 apr_uint32_t *last_seed)
378 {
379 apr_uint32_t seed, maxlen;
380 apr_size_t bytes_range;
381 int i, iterations, dump_files, print_windows;
382 const char *random_bytes;
383
384 /* Initialize parameters and print out the seed in case we dump core
385 or something. */
386 init_params(&seed, &maxlen, &iterations, &dump_files, &print_windows,
387 &random_bytes, &bytes_range, pool);
388
389 for (i = 0; i < iterations; i++)
390 {
391 /* Generate source and target for the delta and its application. */
392 apr_uint32_t subseed_base = svn_test_rand((*last_seed = seed, &seed));
393 apr_file_t *source = generate_random_file(maxlen, subseed_base, &seed,
394 random_bytes, bytes_range,
395 dump_files, pool);
396 apr_file_t *middle = generate_random_file(maxlen, subseed_base, &seed,
397 random_bytes, bytes_range,
398 dump_files, pool);
399 apr_file_t *target = generate_random_file(maxlen, subseed_base, &seed,
400 random_bytes, bytes_range,
401 dump_files, pool);
402 apr_file_t *source_copy = copy_tempfile(source, pool);
403 apr_file_t *middle_copy = copy_tempfile(middle, pool);
404 apr_file_t *target_regen = open_tempfile(NULL, pool);
405
406 svn_txdelta_stream_t *txdelta_stream_A;
407 svn_txdelta_stream_t *txdelta_stream_B;
408 svn_txdelta_window_handler_t handler;
409 svn_stream_t *stream;
410 void *handler_baton;
411
412 /* Set up a four-stage pipeline: create two deltas, combine them
413 and convert the result to svndiff format, parse that back
414 into delta format, and apply it to a copy of the source file
415 to see if we get the same target back. */
416 apr_pool_t *delta_pool = svn_pool_create(pool);
417
418 /* Make stage 4: apply the text delta. */
419 svn_txdelta_apply(svn_stream_from_aprfile(source_copy, delta_pool),
420 svn_stream_from_aprfile(target_regen, delta_pool),
421 NULL, NULL, delta_pool, &handler, &handler_baton);
422
423 /* Make stage 3: reparse the text delta. */
424 stream = svn_txdelta_parse_svndiff(handler, handler_baton, TRUE,
425 delta_pool);
426
427 /* Make stage 2: encode the text delta in svndiff format using
428 varying svndiff versions and compression levels. */
429 svn_txdelta_to_svndiff3(&handler, &handler_baton, stream, i % 3,
430 i % 10, delta_pool);
431
432 /* Make stage 1: create the text deltas. */
433
434 svn_txdelta2(&txdelta_stream_A,
435 svn_stream_from_aprfile(source, delta_pool),
436 svn_stream_from_aprfile(middle, delta_pool),
437 FALSE,
438 delta_pool);
439
440 svn_txdelta2(&txdelta_stream_B,
441 svn_stream_from_aprfile(middle_copy, delta_pool),
442 svn_stream_from_aprfile(target, delta_pool),
443 FALSE,
444 delta_pool);
445
446 {
447 svn_txdelta_window_t *window_A;
448 svn_txdelta_window_t *window_B;
449 svn_txdelta_window_t *composite;
450 apr_pool_t *wpool = svn_pool_create(delta_pool);
451
452 do
453 {
454 SVN_ERR(svn_txdelta_next_window(&window_A, txdelta_stream_A,
455 wpool));
456 if (print_windows)
457 delta_window_print(window_A, "A ", stdout);
458 SVN_ERR(svn_txdelta_next_window(&window_B, txdelta_stream_B,
459 wpool));
460 if (print_windows)
461 delta_window_print(window_B, "B ", stdout);
462 if (!window_B)
463 break;
464 assert(window_A != NULL || window_B->src_ops == 0);
465 if (window_B->src_ops == 0)
466 {
467 composite = window_B;
468 composite->sview_len = 0;
469 }
470 else
471 composite = svn_txdelta_compose_windows(window_A, window_B,
472 wpool);
473 if (print_windows)
474 delta_window_print(composite, "AB", stdout);
475
476 /* The source view length should not be 0 if there are
477 source copy ops in the window. */
478 if (composite
479 && composite->sview_len == 0 && composite->src_ops > 0)
480 return svn_error_create
481 (SVN_ERR_FS_GENERAL, NULL,
482 "combined delta window is inconsistent");
483
484 SVN_ERR(handler(composite, handler_baton));
485 svn_pool_clear(wpool);
486 }
487 while (composite != NULL);
488 svn_pool_destroy(wpool);
489 }
490
491 svn_pool_destroy(delta_pool);
492
493 SVN_ERR(compare_files(target, target_regen, dump_files));
494
495 apr_file_close(source);
496 apr_file_close(middle);
497 apr_file_close(target);
498 apr_file_close(source_copy);
499 apr_file_close(middle_copy);
500 apr_file_close(target_regen);
501 }
502
503 return SVN_NO_ERROR;
504 }
505
506 /* Implements svn_test_driver_t. */
507 static svn_error_t *
random_combine_test(apr_pool_t * pool)508 random_combine_test(apr_pool_t *pool)
509 {
510 apr_uint32_t seed;
511 svn_error_t *err = do_random_combine_test(pool, &seed);
512 if (err)
513 fprintf(stderr, "SEED: %lu\n", (unsigned long)seed);
514 return err;
515 }
516
517
518 /* (Note: *LAST_SEED is an output parameter.) */
519 static svn_error_t *
do_random_txdelta_to_svndiff_stream_test(apr_pool_t * pool,apr_uint32_t * last_seed)520 do_random_txdelta_to_svndiff_stream_test(apr_pool_t *pool,
521 apr_uint32_t *last_seed)
522 {
523 apr_uint32_t seed;
524 apr_uint32_t maxlen;
525 apr_size_t bytes_range;
526 int i;
527 int iterations;
528 int dump_files;
529 int print_windows;
530 const char *random_bytes;
531 apr_pool_t *iterpool;
532
533 /* Initialize parameters and print out the seed in case we dump core
534 or something. */
535 init_params(&seed, &maxlen, &iterations, &dump_files, &print_windows,
536 &random_bytes, &bytes_range, pool);
537
538 iterpool = svn_pool_create(pool);
539 for (i = 0; i < iterations; i++)
540 {
541 apr_uint32_t subseed_base;
542 apr_file_t *source;
543 apr_file_t *target;
544 apr_file_t *source_copy;
545 apr_file_t *new_target;
546 svn_txdelta_stream_t *txstream;
547 svn_stream_t *delta_stream;
548 svn_txdelta_window_handler_t handler;
549 void *handler_baton;
550 svn_stream_t *push_stream;
551
552 svn_pool_clear(iterpool);
553
554 /* Generate source and target for the delta and its application. */
555 *last_seed = seed;
556 subseed_base = svn_test_rand(&seed);
557 source = generate_random_file(maxlen, subseed_base, &seed,
558 random_bytes, bytes_range,
559 dump_files, iterpool);
560 target = generate_random_file(maxlen, subseed_base, &seed,
561 random_bytes, bytes_range,
562 dump_files, iterpool);
563 source_copy = copy_tempfile(source, iterpool);
564 new_target = open_tempfile(NULL, iterpool);
565
566 /* Create a txdelta stream that turns the source into target;
567 turn it into a generic readable svn_stream_t. */
568 svn_txdelta2(&txstream,
569 svn_stream_from_aprfile2(source, TRUE, iterpool),
570 svn_stream_from_aprfile2(target, TRUE, iterpool),
571 FALSE, iterpool);
572 delta_stream = svn_txdelta_to_svndiff_stream(txstream, i % 3, i % 10,
573 iterpool);
574
575 /* Apply it to a copy of the source file to see if we get the
576 same target back. */
577 svn_txdelta_apply(svn_stream_from_aprfile2(source_copy, TRUE, iterpool),
578 svn_stream_from_aprfile2(new_target, TRUE, iterpool),
579 NULL, NULL, iterpool, &handler, &handler_baton);
580 push_stream = svn_txdelta_parse_svndiff(handler, handler_baton, TRUE,
581 iterpool);
582 SVN_ERR(svn_stream_copy3(delta_stream, push_stream, NULL, NULL,
583 iterpool));
584
585 SVN_ERR(compare_files(target, new_target, dump_files));
586
587 apr_file_close(source);
588 apr_file_close(target);
589 apr_file_close(source_copy);
590 apr_file_close(new_target);
591 }
592 svn_pool_destroy(iterpool);
593
594 return SVN_NO_ERROR;
595 }
596
597 /* Implements svn_test_driver_t. */
598 static svn_error_t *
random_txdelta_to_svndiff_stream_test(apr_pool_t * pool)599 random_txdelta_to_svndiff_stream_test(apr_pool_t *pool)
600 {
601 apr_uint32_t seed;
602 svn_error_t *err = do_random_txdelta_to_svndiff_stream_test(pool, &seed);
603 if (err)
604 fprintf(stderr, "SEED: %lu\n", (unsigned long)seed);
605 return err;
606 }
607
608 /* Change to 1 to enable the unit test for the delta combiner's range index: */
609 #if 0
610 #include "range-index-test.h"
611 #endif
612
613
614
615 /* The test table. */
616
617 static int max_threads = 1;
618
619 static struct svn_test_descriptor_t test_funcs[] =
620 {
621 SVN_TEST_NULL,
622 SVN_TEST_PASS2(random_test,
623 "random delta test"),
624 SVN_TEST_PASS2(random_combine_test,
625 "random combine delta test"),
626 SVN_TEST_PASS2(random_txdelta_to_svndiff_stream_test,
627 "random txdelta to svndiff stream test"),
628 #ifdef SVN_RANGE_INDEX_TEST_H
629 SVN_TEST_PASS2(random_range_index_test,
630 "random range index test"),
631 #endif
632 SVN_TEST_NULL
633 };
634
635 SVN_TEST_MAIN
636