1 : /*
2 : * Copyright (c) 2012 The Native Client Authors. All rights reserved.
3 : * Use of this source code is governed by a BSD-style license that can be
4 : * found in the LICENSE file.
5 : */
6 :
7 : #include <stdio.h>
8 : #include <stdlib.h>
9 : #include <string.h>
10 : #include <time.h>
11 :
12 : #include "native_client/src/trusted/interval_multiset/nacl_interval_multiset.h"
13 : #include "native_client/src/trusted/interval_multiset/nacl_interval_list.h"
14 :
15 : #include "native_client/src/include/nacl_macros.h"
16 : #include "native_client/src/include/portability.h"
17 : #include "native_client/src/shared/platform/platform_init.h"
18 : #include "native_client/src/shared/platform/nacl_check.h"
19 : #include "native_client/src/shared/platform/nacl_log.h"
20 :
21 : #define MAX_INTERVAL_TREE_KINDS 8
22 : #define MAX_INPUT_LINE_LENGTH 4096
23 : #define DEFAULT_COUNT_WHEN_RANDOM 8192
24 :
25 : #define OP_ADD 0
26 : #define OP_REMOVE 1
27 : #define OP_PROBE 2
28 : /*
29 : * Input/Output format:
30 : *
31 : * If a line contains #, it and all characters following to the
32 : * newline are discarded. Lines containing only space and tabs are
33 : * ignored. (Manually generated test inputs can have comments.)
34 : * Maximum line length is MAX_INPUT_LINE_LENGTH.
35 : *
36 : * All other lines should be four integers of the form:
37 : *
38 : * op first_val last_val expected_output
39 : *
40 : * "op" specifies which virtual function to invoke and is interpreted
41 : * as per the OP_* defines above.
42 : *
43 : * For Add and Remove, "expected_output" is don't-care (ignored). For
44 : * OverlapsWith, "expected_output" is the expected return value (since
45 : * it's C-style bool, encoded as 0 or 1). When random operations are
46 : * generated, we encode "unknown" or "don't care" as -1 in
47 : * "expected_output" for use OverlapsWith, since we don't otherwise
48 : * compute separately what the expected output should be.
49 : *
50 : * For the output case, e.g., generated with randomly chosen calls and
51 : * parameters, "expected_output" is the actual return value from
52 : * OverlapsWith. An initial comment line contains the random seed
53 : * used.
54 : */
55 :
56 : uint32_t g_max_random_region_size = 8 << 20;
57 :
58 : struct Op {
59 : int opcode;
60 : uint32_t first_val;
61 : uint32_t last_val;
62 : int expected_output;
63 : };
64 :
65 7736 : void StripComment(char *line) {
66 7736 : char *comment;
67 7736 : if (NULL != (comment = strchr(line, '#'))) {
68 20 : *comment = '\0';
69 20 : }
70 7736 : }
71 :
72 7736 : int LineContainsOnlyWhitespace(char *line) {
73 15492 : while ('\0' != *line) {
74 7720 : switch (*line) {
75 : case ' ':
76 : case '\t':
77 : case '\n':
78 20 : ++line;
79 20 : continue;
80 : default:
81 7700 : return 0;
82 : }
83 : }
84 36 : return 1;
85 7736 : }
86 :
87 7704 : int ReadOp(struct Op *op, FILE *iob) {
88 7704 : char line[MAX_INPUT_LINE_LENGTH];
89 7704 : int line_num = 0;
90 :
91 7704 : for (;;) {
92 7740 : ++line_num;
93 7740 : if (!fgets(line, sizeof line, iob)) {
94 4 : return 0;
95 : }
96 7736 : StripComment(line);
97 7736 : if (LineContainsOnlyWhitespace(line)) {
98 36 : continue;
99 : }
100 : /*
101 : * we cheat -- NACL_SCNu32 macros are not defined, and we know
102 : * that the printf format specifier won't work for scanf since on
103 : * windows we use the I32 notation for windows printf, but windows
104 : * scanf doesn't understand that notation.
105 : */
106 7700 : if (4 == sscanf(line, "%d%u%u%d",
107 : &op->opcode, &op->first_val, &op->last_val,
108 : &op->expected_output)) {
109 7700 : return 1;
110 : }
111 0 : fprintf(stderr, "op syntax error in line %d, ignoring\n", line_num);
112 0 : exit(1);
113 : }
114 7704 : }
115 :
116 0 : void WriteOp(FILE *iob, struct Op *op) {
117 0 : fprintf(iob, "%d %"NACL_PRIu32" %"NACL_PRIu32" %d\n",
118 : op->opcode, op->first_val, op->last_val, op->expected_output);
119 0 : }
120 :
121 : struct Op *extant_intervals = NULL;
122 : size_t num_extant_intervals = 0;
123 : size_t size_extant_intervals = 0;
124 :
125 210276 : void AddInterval(struct Op const *op) {
126 210276 : size_t target_num;
127 :
128 210276 : if (num_extant_intervals == size_extant_intervals) {
129 9 : target_num = 2 * size_extant_intervals;
130 9 : if (target_num == 0) {
131 2 : target_num = 32;
132 2 : }
133 9 : extant_intervals = (struct Op *) realloc(
134 : extant_intervals,
135 : target_num * sizeof *extant_intervals);
136 9 : if (NULL == extant_intervals) {
137 0 : NaClLog(LOG_FATAL,
138 : "nacl_interval_test: no memory for extant intervals\n");
139 0 : }
140 9 : size_extant_intervals = target_num;
141 9 : }
142 210276 : NaClLog(2, ("adding at %"NACL_PRIuS" [%u,%u], size %"NACL_PRIuS"\n"),
143 : num_extant_intervals,
144 : op->first_val, op->last_val,
145 : size_extant_intervals);
146 210276 : extant_intervals[num_extant_intervals++] = *op;
147 210276 : }
148 :
149 210026 : void RemoveIntervalAtIndex(size_t ix) {
150 210026 : NaClLog(2, "removing ix %"NACL_PRIuS", contents [%u,%u]\n",
151 : ix, extant_intervals[ix].first_val, extant_intervals[ix].last_val);
152 210026 : extant_intervals[ix] = extant_intervals[--num_extant_intervals];
153 210026 : }
154 :
155 2100000 : void GenerateRandomOp(struct Op *op) {
156 2100000 : switch (rand() % 5) {
157 : case 0:
158 210085 : op->opcode = OP_ADD;
159 210085 : break;
160 : case 1:
161 210217 : op->opcode = OP_REMOVE;
162 210217 : break;
163 : case 2:
164 : case 3:
165 : case 4:
166 629698 : op->opcode = OP_PROBE;
167 629698 : break;
168 : }
169 1260217 : if (op->opcode == OP_REMOVE && num_extant_intervals == 0) {
170 191 : op->opcode = OP_ADD;
171 191 : }
172 1050000 : if (op->opcode != OP_REMOVE) {
173 839974 : op->expected_output = -1;
174 839974 : do {
175 839974 : op->first_val = rand();
176 839974 : op->last_val = op->first_val + (rand() % g_max_random_region_size);
177 1679948 : } while (op->first_val > op->last_val);
178 839974 : }
179 1050000 : if (op->opcode == OP_ADD) {
180 210276 : AddInterval(op);
181 1050000 : } else if (op->opcode == OP_REMOVE) {
182 210026 : size_t ix = rand() % num_extant_intervals;
183 210026 : op->first_val = extant_intervals[ix].first_val;
184 210026 : op->last_val = extant_intervals[ix].last_val;
185 210026 : op->expected_output = -1;
186 210026 : RemoveIntervalAtIndex(ix);
187 210026 : }
188 1050000 : NaClLog(3, "Gen (%d, %u, %u, %d)\n",
189 : op->opcode, op->first_val, op->last_val, op->expected_output);
190 1050000 : }
191 :
192 6 : int main(int ac, char **av) {
193 6 : int count = -1; /* until EOF if a file is specified */
194 6 : unsigned seed = (unsigned) time((time_t *) NULL);
195 6 : FILE *out_file = NULL;
196 6 : FILE *in_file = NULL;
197 6 : char const *default_kinds[] = {
198 : "NaClIntervalListMultiset",
199 : "NaClIntervalRangeTree",
200 : };
201 6 : char const *kind[MAX_INTERVAL_TREE_KINDS];
202 6 : size_t num_kinds = 0;
203 6 : int opt;
204 6 : size_t ix;
205 6 : int iter;
206 6 : struct Op oper;
207 6 : size_t error_count = 0;
208 6 : struct NaClIntervalMultiset *nis[MAX_INTERVAL_TREE_KINDS];
209 6 : int result;
210 :
211 6 : NaClPlatformInit();
212 :
213 12 : CHECK(NACL_ARRAY_SIZE(default_kinds) <= NACL_ARRAY_SIZE(kind));
214 :
215 26 : while (-1 != (opt = getopt(ac, av, "c:i:k:m:o:s:v"))) {
216 14 : switch (opt) {
217 : case 'c':
218 2 : count = strtoul(optarg, (char **) NULL, 0);
219 2 : break;
220 : case 'i':
221 4 : in_file = fopen(optarg, "r");
222 4 : if (NULL == in_file) {
223 0 : perror("nacl_interval_test");
224 0 : fprintf(stderr, "Could not open \"%s\" as input file\n", optarg);
225 0 : return 1;
226 : }
227 4 : break;
228 : case 'k':
229 8 : if (num_kinds == MAX_INTERVAL_TREE_KINDS) {
230 0 : fprintf(stderr, "too many interval tree kinds specified\n");
231 0 : return 2;
232 : }
233 8 : kind[num_kinds++] = optarg;
234 8 : break;
235 : case 'm':
236 0 : g_max_random_region_size = strtoul(optarg, (char **) NULL, 0);
237 0 : break;
238 : case 'o':
239 0 : out_file = fopen(optarg, "w");
240 0 : if (NULL == out_file) {
241 0 : perror("nacl_interval_test");
242 0 : fprintf(stderr, "Could not open \"%s\" as output file\n", optarg);
243 0 : return 3;
244 : }
245 0 : break;
246 : case 's':
247 0 : seed = strtoul(optarg, (char **) NULL, 0);
248 0 : break;
249 : case 'v':
250 0 : NaClLogIncrVerbosity();
251 0 : break;
252 : default:
253 0 : fprintf(stderr,
254 : "Usage: nacl_interval_test [-s seed] [-c count]\n"
255 : " [-i test_input_file] [-o test_output_file]\n");
256 0 : return 4;
257 : }
258 14 : }
259 :
260 6 : if (0 == num_kinds) {
261 0 : for (ix = 0; ix < NACL_ARRAY_SIZE(default_kinds); ++ix) {
262 0 : kind[ix] = default_kinds[ix];
263 0 : }
264 0 : num_kinds = NACL_ARRAY_SIZE(default_kinds);
265 0 : }
266 :
267 : /*
268 : * When there are bugs that corrupt recursive data structures and
269 : * printing them involve recursive routines that do not flush
270 : * buffers (even if line buffered, do not always output a newline),
271 : * it is a good idea to unbuffer output so that the output just
272 : * before a crash is visible. This is a general debugging strategy
273 : * -- this test code served both as a debugging aid when bringing up
274 : * new data structures and as a unit / regression test, and while
275 : * its role as a unit / regression test probably doesn't require
276 : * unbuffered output, we leave this in.
277 : */
278 6 : setvbuf(stdout, NULL, _IONBF, 0);
279 6 : setvbuf(stderr, NULL, _IONBF, 0);
280 :
281 6 : srand(seed);
282 8 : if (NULL == in_file && -1 == count) {
283 0 : count = DEFAULT_COUNT_WHEN_RANDOM;
284 0 : }
285 6 : if (NULL != out_file) {
286 0 : fprintf(out_file, "# seed %u\n", seed);
287 0 : }
288 : /* always print to stdout so test framework can capture and log it */
289 6 : if (NULL == in_file) {
290 2 : printf("# seed %u\n", seed);
291 2 : } else {
292 4 : printf("# input file used, not randomly generated test cases.\n");
293 : }
294 6 : fflush(stdout);
295 : /* ensure seed is always visible, even if setvbuf above is later deleted */
296 :
297 28 : for (ix = 0; ix < num_kinds; ++ix) {
298 8 : nis[ix] = NaClIntervalMultisetFactory(kind[ix]);
299 8 : if (NULL == nis[ix]) {
300 0 : fprintf(stderr,
301 : "NaClIntervalMultisetFactory(%s) yielded NULL\n", kind[ix]);
302 0 : return 5;
303 : }
304 8 : }
305 :
306 4223120 : for (iter = 0; (-1 == count) || (iter < count); ++iter) {
307 1057704 : if (NULL == in_file) {
308 1050000 : GenerateRandomOp(&oper);
309 1050000 : } else {
310 7704 : if (!ReadOp(&oper, in_file)) {
311 4 : break;
312 : }
313 : }
314 1057700 : NaClLog(3, "Processing (%d, %u, %u, %d)\n",
315 : oper.opcode, oper.first_val, oper.last_val, oper.expected_output);
316 6330800 : for (ix = 0; ix < num_kinds; ++ix) {
317 2107700 : switch (oper.opcode) {
318 : case OP_ADD:
319 422128 : (*nis[ix]->vtbl->AddInterval)(nis[ix],
320 : oper.first_val,
321 : oper.last_val);
322 422128 : break;
323 : case OP_REMOVE:
324 421558 : (*nis[ix]->vtbl->RemoveInterval)(nis[ix],
325 : oper.first_val,
326 : oper.last_val);
327 421558 : break;
328 : case OP_PROBE:
329 1264014 : result = (*nis[ix]->vtbl->OverlapsWith)(nis[ix],
330 : oper.first_val,
331 : oper.last_val);
332 1898330 : if (oper.expected_output != -1 &&
333 : oper.expected_output != result) {
334 0 : printf("OverlapsWith(%d,%d)=%d, expected %d\n",
335 : oper.first_val, oper.last_val, result, oper.expected_output);
336 0 : printf("FAIL\n");
337 0 : if (0 == ++error_count) ++error_count;
338 0 : }
339 1264014 : oper.expected_output = result;
340 1264014 : break;
341 : default:
342 0 : WriteOp(stderr, &oper);
343 0 : NaClLog(LOG_FATAL, "nacl_interval_test: internal error\n");
344 0 : }
345 2107700 : }
346 1057700 : if (NULL != out_file) {
347 0 : WriteOp(out_file, &oper);
348 0 : }
349 1057700 : }
350 :
351 6 : printf("%"NACL_PRIuS" errors\n", error_count);
352 :
353 28 : for (ix = 0; ix < num_kinds; ++ix) {
354 8 : NaClIntervalMultisetDelete(nis[ix]);
355 8 : nis[ix] = NULL;
356 8 : }
357 :
358 6 : NaClPlatformFini();
359 6 : return error_count != 0;
360 6 : }
|
