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 1 : void StripComment(char *line) {
66 : char *comment;
67 1 : if (NULL != (comment = strchr(line, '#'))) {
68 1 : *comment = '\0';
69 : }
70 1 : }
71 :
72 1 : int LineContainsOnlyWhitespace(char *line) {
73 1 : while ('\0' != *line) {
74 1 : switch (*line) {
75 : case ' ':
76 : case '\t':
77 : case '\n':
78 1 : ++line;
79 1 : continue;
80 : default:
81 1 : return 0;
82 : }
83 : }
84 1 : return 1;
85 1 : }
86 :
87 1 : int ReadOp(struct Op *op, FILE *iob) {
88 : char line[MAX_INPUT_LINE_LENGTH];
89 1 : int line_num = 0;
90 :
91 : for (;;) {
92 1 : ++line_num;
93 1 : if (!fgets(line, sizeof line, iob)) {
94 1 : return 0;
95 : }
96 1 : StripComment(line);
97 1 : if (LineContainsOnlyWhitespace(line)) {
98 1 : 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 : if (4 == sscanf(line, "%d%u%u%d",
107 : &op->opcode, &op->first_val, &op->last_val,
108 1 : &op->expected_output)) {
109 1 : return 1;
110 : }
111 0 : fprintf(stderr, "op syntax error in line %d, ignoring\n", line_num);
112 0 : exit(1);
113 : }
114 1 : }
115 :
116 0 : void WriteOp(FILE *iob, struct Op *op) {
117 : fprintf(iob, "%d %"NACL_PRIu32" %"NACL_PRIu32" %d\n",
118 0 : 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 1 : void AddInterval(struct Op const *op) {
126 : size_t target_num;
127 :
128 1 : if (num_extant_intervals == size_extant_intervals) {
129 1 : target_num = 2 * size_extant_intervals;
130 1 : if (target_num == 0) {
131 1 : target_num = 32;
132 : }
133 : extant_intervals = (struct Op *) realloc(
134 : extant_intervals,
135 1 : target_num * sizeof *extant_intervals);
136 1 : if (NULL == extant_intervals) {
137 : NaClLog(LOG_FATAL,
138 0 : "nacl_interval_test: no memory for extant intervals\n");
139 : }
140 1 : size_extant_intervals = target_num;
141 : }
142 : NaClLog(2, ("adding at %"NACL_PRIuS" [%u,%u], size %"NACL_PRIuS"\n"),
143 : num_extant_intervals,
144 : op->first_val, op->last_val,
145 1 : size_extant_intervals);
146 1 : extant_intervals[num_extant_intervals++] = *op;
147 1 : }
148 :
149 1 : void RemoveIntervalAtIndex(size_t ix) {
150 : NaClLog(2, "removing ix %"NACL_PRIuS", contents [%u,%u]\n",
151 1 : ix, extant_intervals[ix].first_val, extant_intervals[ix].last_val);
152 1 : extant_intervals[ix] = extant_intervals[--num_extant_intervals];
153 1 : }
154 :
155 1 : void GenerateRandomOp(struct Op *op) {
156 1 : switch (rand() % 5) {
157 : case 0:
158 1 : op->opcode = OP_ADD;
159 1 : break;
160 : case 1:
161 1 : op->opcode = OP_REMOVE;
162 1 : break;
163 : case 2:
164 : case 3:
165 : case 4:
166 1 : op->opcode = OP_PROBE;
167 : break;
168 : }
169 1 : if (op->opcode == OP_REMOVE && num_extant_intervals == 0) {
170 1 : op->opcode = OP_ADD;
171 : }
172 1 : if (op->opcode != OP_REMOVE) {
173 1 : op->expected_output = -1;
174 : do {
175 1 : op->first_val = rand();
176 1 : op->last_val = op->first_val + (rand() % g_max_random_region_size);
177 1 : } while (op->first_val > op->last_val);
178 : }
179 1 : if (op->opcode == OP_ADD) {
180 1 : AddInterval(op);
181 1 : } else if (op->opcode == OP_REMOVE) {
182 1 : size_t ix = rand() % num_extant_intervals;
183 1 : op->first_val = extant_intervals[ix].first_val;
184 1 : op->last_val = extant_intervals[ix].last_val;
185 1 : op->expected_output = -1;
186 1 : RemoveIntervalAtIndex(ix);
187 : }
188 : NaClLog(3, "Gen (%d, %u, %u, %d)\n",
189 1 : op->opcode, op->first_val, op->last_val, op->expected_output);
190 1 : }
191 :
192 1 : int main(int ac, char **av) {
193 1 : int count = -1; /* until EOF if a file is specified */
194 1 : unsigned seed = (unsigned) time((time_t *) NULL);
195 1 : FILE *out_file = NULL;
196 1 : FILE *in_file = NULL;
197 : char const *default_kinds[] = {
198 1 : "NaClIntervalListMultiset",
199 1 : "NaClIntervalRangeTree",
200 : };
201 : char const *kind[MAX_INTERVAL_TREE_KINDS];
202 1 : size_t num_kinds = 0;
203 : int opt;
204 : size_t ix;
205 : int iter;
206 : struct Op oper;
207 1 : size_t error_count = 0;
208 : struct NaClIntervalMultiset *nis[MAX_INTERVAL_TREE_KINDS];
209 : int result;
210 :
211 1 : NaClPlatformInit();
212 :
213 1 : CHECK(NACL_ARRAY_SIZE(default_kinds) <= NACL_ARRAY_SIZE(kind));
214 :
215 1 : while (-1 != (opt = getopt(ac, av, "c:i:k:m:o:s:v"))) {
216 1 : switch (opt) {
217 : case 'c':
218 1 : count = strtoul(optarg, (char **) NULL, 0);
219 1 : break;
220 : case 'i':
221 1 : in_file = fopen(optarg, "r");
222 1 : 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 1 : break;
228 : case 'k':
229 1 : if (num_kinds == MAX_INTERVAL_TREE_KINDS) {
230 0 : fprintf(stderr, "too many interval tree kinds specified\n");
231 0 : return 2;
232 : }
233 1 : kind[num_kinds++] = optarg;
234 1 : 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 : fprintf(stderr,
254 : "Usage: nacl_interval_test [-s seed] [-c count]\n"
255 0 : " [-i test_input_file] [-o test_output_file]\n");
256 0 : return 4;
257 : }
258 1 : }
259 :
260 1 : 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 : }
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 1 : setvbuf(stdout, NULL, _IONBF, 0);
279 1 : setvbuf(stderr, NULL, _IONBF, 0);
280 :
281 1 : srand(seed);
282 1 : if (NULL == in_file && -1 == count) {
283 0 : count = DEFAULT_COUNT_WHEN_RANDOM;
284 : }
285 1 : if (NULL != out_file) {
286 0 : fprintf(out_file, "# seed %u\n", seed);
287 : }
288 : /* always print to stdout so test framework can capture and log it */
289 1 : if (NULL == in_file) {
290 1 : printf("# seed %u\n", seed);
291 1 : } else {
292 1 : printf("# input file used, not randomly generated test cases.\n");
293 : }
294 1 : fflush(stdout);
295 : /* ensure seed is always visible, even if setvbuf above is later deleted */
296 :
297 1 : for (ix = 0; ix < num_kinds; ++ix) {
298 1 : nis[ix] = NaClIntervalMultisetFactory(kind[ix]);
299 1 : if (NULL == nis[ix]) {
300 : fprintf(stderr,
301 0 : "NaClIntervalMultisetFactory(%s) yielded NULL\n", kind[ix]);
302 0 : return 5;
303 : }
304 1 : }
305 :
306 1 : for (iter = 0; (-1 == count) || (iter < count); ++iter) {
307 1 : if (NULL == in_file) {
308 1 : GenerateRandomOp(&oper);
309 1 : } else {
310 1 : if (!ReadOp(&oper, in_file)) {
311 1 : break;
312 : }
313 : }
314 : NaClLog(3, "Processing (%d, %u, %u, %d)\n",
315 1 : oper.opcode, oper.first_val, oper.last_val, oper.expected_output);
316 1 : for (ix = 0; ix < num_kinds; ++ix) {
317 1 : switch (oper.opcode) {
318 : case OP_ADD:
319 : (*nis[ix]->vtbl->AddInterval)(nis[ix],
320 : oper.first_val,
321 1 : oper.last_val);
322 1 : break;
323 : case OP_REMOVE:
324 : (*nis[ix]->vtbl->RemoveInterval)(nis[ix],
325 : oper.first_val,
326 1 : oper.last_val);
327 1 : break;
328 : case OP_PROBE:
329 : result = (*nis[ix]->vtbl->OverlapsWith)(nis[ix],
330 : oper.first_val,
331 1 : oper.last_val);
332 : if (oper.expected_output != -1 &&
333 1 : oper.expected_output != result) {
334 : printf("OverlapsWith(%d,%d)=%d, expected %d\n",
335 0 : oper.first_val, oper.last_val, result, oper.expected_output);
336 0 : printf("FAIL\n");
337 0 : if (0 == ++error_count) ++error_count;
338 : }
339 1 : oper.expected_output = result;
340 1 : break;
341 : default:
342 0 : WriteOp(stderr, &oper);
343 0 : NaClLog(LOG_FATAL, "nacl_interval_test: internal error\n");
344 : }
345 1 : }
346 1 : if (NULL != out_file) {
347 0 : WriteOp(out_file, &oper);
348 : }
349 1 : }
350 :
351 1 : printf("%"NACL_PRIuS" errors\n", error_count);
352 :
353 1 : for (ix = 0; ix < num_kinds; ++ix) {
354 1 : NaClIntervalMultisetDelete(nis[ix]);
355 1 : nis[ix] = NULL;
356 1 : }
357 :
358 1 : NaClPlatformFini();
359 1 : return error_count != 0;
360 1 : }
|
