1 : /*
2 : * Copyright (c) 2013 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 : /*
8 : * This file contains the Read-Eval-Print loop. It defines the test
9 : * language embedded in the s-expressions.
10 : */
11 :
12 : #include <ctype.h>
13 : #include <errno.h>
14 : #include <stdint.h>
15 : #include <stdio.h>
16 : #include <stdlib.h>
17 : #include <string.h>
18 : #include <pthread.h>
19 : #include <unistd.h> /* portability.h */
20 :
21 : #define MAX_THREADS 1024
22 : #define MAX_FILES 1024
23 : #define MIN_EPSILON_DELAY_NANOS 1000
24 :
25 : #include "native_client/tests/lock_manager/nacl_test_util_repl.h"
26 :
27 : #include "native_client/src/shared/platform/nacl_check.h"
28 : #include "native_client/src/shared/platform/posix/nacl_file_lock.h"
29 : #include "native_client/src/shared/platform/posix/nacl_file_lock_intern.h"
30 : #include "native_client/tests/lock_manager/nacl_test_util_sexp.h"
31 :
32 : /*
33 : * To test the NaClFileLockManager object's API, we have to invoke the
34 : * API from multiple threads -- since the NaClFileLockManagerLock
35 : * function can block -- and ensure that locking and unlocking happens
36 : * in an acceptable order. The output sequence -- "output" occurs
37 : * when a lock is taken or released, i.e., at lock state transitions
38 : * -- can be serialized, but the test will be inherently racy, e.g.,
39 : * dropping a lock in one thread while two threads are already blocked
40 : * attempting to get the lock has two valid/acceptable output
41 : * sequences. Instead of handling this, we avoid the mess: the test
42 : * driver will be multithreaded, but will (attempt to) coordinate the
43 : * threads so that only one operation is done by one thread at any
44 : * particular time slot -- the sequence of operations will be strictly
45 : * sequential. Because threads must acknowledge that they are about
46 : * to perform the requested operation before they actually do it, we
47 : * introduce a microsleep testing quantum in the execution of the test
48 : * machine, so that the next test step should not proceed prior to the
49 : * thread actually having done its task, even if the task would not
50 : * cause any events to fire.
51 : *
52 : * To handle the possibility that two or more threads will wake up at
53 : * the same time -- and as a result, output "wakeup" messages -- the
54 : * output matcher accepts a specification that is petri-net-like: the
55 : * expected output can be a list of outputs which all must occur, but
56 : * may occur in any order. To handle races, alternation must be
57 : * possible. This is done using a matcher-of-matcher that returns the
58 : * index of the matcher that succeeded, in combination with nth,
59 : * quote, and eval to run the continuation for the match. See
60 : * test_input.txt for one example.
61 : *
62 : * The lisp-like execution environment does not include any bindings
63 : * for variables, so the static vs dynamic scoping question does not
64 : * apply. If/when we include parametric matching, this will have to
65 : * be addressed, in addition to deciding on how the bound variables
66 : * are made available to the match's continuation.
67 : *
68 : * There is no garbage collection. Instead, we copy lists (too much)
69 : * to avoid leaking memory.
70 : */
71 :
72 : static int gVerbosity = 0;
73 : static int gInteractive = 0; /* do not crash on error if set */
74 : static size_t gEpsilonDelayNanos = 0;
75 :
76 : static pthread_key_t gNaClTestTsdKey;
77 :
78 : #define DPRINTF(args) \
79 : do { \
80 : if (gVerbosity > 1) { \
81 : printf args; \
82 : } \
83 : } while (0)
84 :
85 :
86 : struct ThreadState;
87 :
88 : enum EventType {
89 : kLocked = 0,
90 : kUnlocked = 1,
91 : };
92 :
93 : struct Event {
94 : struct Event *next;
95 : enum EventType type;
96 : int thread_id;
97 : int file_id;
98 : };
99 :
100 : struct WorkState {
101 : /* initialized before going threaded */
102 : size_t num_workers;
103 : struct ThreadState *workers;
104 :
105 : /* protects rest */
106 : pthread_mutex_t mu;
107 : pthread_cond_t cv;
108 :
109 : int actor_thread;
110 : #define WORK_PENDING (-1)
111 : #define WORK_ACCEPTED (-2)
112 : #define WORK_ENDED (-3)
113 : void (*action_functor)(void *functor_state);
114 : void *functor_state;
115 :
116 : struct Event *q, **qend;
117 :
118 : struct NaClFileLockManager flm;
119 : struct NaClFileLockTestInterface *test_if;
120 :
121 : void (*orig_set_identity)(struct NaClFileLockEntry *, int desc);
122 : void (*orig_take_lock)(int desc);
123 : void (*orig_drop_lock)(int desc);
124 : };
125 :
126 : /*
127 : * Error / abort handling function. We do not grab locks here, since
128 : * this may be called in an error context where the lock is already
129 : * held. Since this is a debugging aid, we tolerate the possibility
130 : * of inconsistent / undefined behavior.
131 : */
132 0 : static void NaClReplDumpWs(struct WorkState *ws) {
133 0 : struct Event *q = ws->q;
134 0 : while (NULL != q) {
135 0 : printf("event type %d, tid %d, fid %d\n",
136 : q->type, q->thread_id, q->file_id);
137 0 : q = q->next;
138 0 : }
139 0 : }
140 :
141 0 : static void crash_node(struct WorkState *ws,
142 0 : char const *reason,
143 0 : struct NaClSexpNode *n) {
144 0 : fprintf(stderr, "Runtime error: %s\n", reason);
145 0 : NaClSexpPrintNode(stderr, n);
146 0 : putc('\n', stderr);
147 0 : NaClReplDumpWs(ws);
148 0 : exit(1);
149 0 : }
150 :
151 0 : static void crash_cons(struct WorkState *ws,
152 0 : char const *reason,
153 0 : struct NaClSexpCons *c) {
154 0 : fprintf(stderr, "Runtime error: %s\n", reason);
155 0 : NaClSexpPrintCons(stderr, c);
156 0 : putc('\n', stderr);
157 0 : NaClReplDumpWs(ws);
158 0 : exit(1);
159 0 : }
160 :
161 0 : static void error_node(struct WorkState *ws,
162 0 : char const *reason,
163 0 : struct NaClSexpNode *n) {
164 0 : printf("Error: %s\n", reason);
165 0 : NaClSexpPrintNode(stdout, n);
166 0 : putchar('\n');
167 0 : NaClReplDumpWs(ws);
168 : /*
169 : * Eventually, with proper garbage collection, we may distinguish
170 : * between batch execution and interactive execution, with errors
171 : * aborting batch execution but letting errors longjmp back to the
172 : * REPL for interactive use.
173 : */
174 0 : if (!gInteractive) {
175 0 : exit(1);
176 : }
177 0 : }
178 :
179 0 : static void error_cons(struct WorkState *ws,
180 0 : char const *reason,
181 0 : struct NaClSexpCons *c) {
182 0 : printf("Error: %s\n", reason);
183 0 : NaClSexpPrintCons(stdout, c);
184 0 : putchar('\n');
185 0 : NaClReplDumpWs(ws);
186 0 : if (!gInteractive) {
187 0 : exit(1);
188 : }
189 0 : }
190 :
191 : void EventOccurred(struct ThreadState *ts, enum EventType type, int file_id);
192 :
193 : struct ThreadState {
194 : pthread_t tid;
195 : int this_thread;
196 : struct WorkState *ws;
197 : };
198 :
199 : static void NaClFileLockTestSetFileIdentityDataWrapper(
200 74 : struct NaClFileLockEntry *entry,
201 74 : int desc) {
202 74 : struct ThreadState *ts;
203 :
204 74 : ts = (struct ThreadState *) pthread_getspecific(gNaClTestTsdKey);
205 222 : CHECK(NULL != ts);
206 74 : (*ts->ws->test_if->set_identity)(ts->ws->test_if,
207 : ts->ws->orig_set_identity,
208 : entry, desc);
209 74 : }
210 :
211 30 : static void NaClFileLockTestTakeFileLockWrapper(int desc) {
212 30 : struct ThreadState *ts;
213 :
214 30 : ts = (struct ThreadState *) pthread_getspecific(gNaClTestTsdKey);
215 90 : CHECK(NULL != ts);
216 30 : if ((*ts->ws->test_if->take_lock)(ts->ws->test_if,
217 : ts->ws->orig_take_lock,
218 : ts->this_thread, desc)) {
219 30 : EventOccurred(ts, kLocked, desc);
220 30 : }
221 30 : }
222 :
223 30 : static void NaClFileLockTestDropFileLockWrapper(int desc) {
224 30 : struct ThreadState *ts;
225 :
226 30 : ts = (struct ThreadState *) pthread_getspecific(gNaClTestTsdKey);
227 90 : CHECK(NULL != ts);
228 30 : if ((*ts->ws->test_if->drop_lock)(ts->ws->test_if,
229 : ts->ws->orig_drop_lock,
230 : ts->this_thread, desc)) {
231 30 : EventOccurred(ts, kUnlocked, desc);
232 30 : }
233 30 : }
234 :
235 8 : void WorkStateCtor(struct WorkState *ws,
236 8 : struct NaClFileLockTestInterface *test_if) {
237 8 : ws->num_workers = 0; /* unknown */
238 8 : ws->workers = NULL;
239 8 : pthread_mutex_init(&ws->mu, (pthread_mutexattr_t *) NULL);
240 8 : pthread_cond_init(&ws->cv, (pthread_condattr_t *) NULL);
241 8 : ws->q = NULL;
242 8 : ws->qend = &ws->q;
243 8 : ws->actor_thread = WORK_PENDING;
244 8 : NaClFileLockManagerCtor(&ws->flm);
245 8 : ws->orig_set_identity = ws->flm.set_file_identity_data;
246 8 : ws->orig_take_lock = ws->flm.take_file_lock;
247 8 : ws->orig_drop_lock = ws->flm.drop_file_lock;
248 8 : ws->test_if = test_if;
249 8 : ws->flm.set_file_identity_data = NaClFileLockTestSetFileIdentityDataWrapper;
250 8 : ws->flm.take_file_lock = NaClFileLockTestTakeFileLockWrapper;
251 8 : ws->flm.drop_file_lock = NaClFileLockTestDropFileLockWrapper;
252 8 : }
253 :
254 8 : void WorkStateDtor(struct WorkState *ws) {
255 8 : struct Event *p;
256 8 : free(ws->workers);
257 8 : pthread_mutex_destroy(&ws->mu);
258 8 : pthread_cond_destroy(&ws->cv);
259 16 : while (NULL != (p = ws->q)) {
260 0 : ws->q = p->next;
261 0 : free(p);
262 0 : }
263 8 : NaClFileLockManagerDtor(&ws->flm);
264 8 : }
265 :
266 147 : size_t EventQueueLengthMu(struct WorkState *ws) {
267 147 : struct Event *p;
268 147 : size_t count = 0;
269 442 : for (p = ws->q; NULL != p; p = p->next) {
270 74 : ++count;
271 74 : }
272 147 : return count;
273 : }
274 :
275 60 : void EnqueueEvent(struct WorkState *ws, struct Event *ev) {
276 180 : DPRINTF(("EnqueueEvent: %d %d %d\n", ev->type, ev->thread_id, ev->file_id));
277 60 : pthread_mutex_lock(&ws->mu);
278 60 : ev->next = NULL;
279 60 : *ws->qend = ev;
280 60 : ws->qend = &ev->next;
281 60 : pthread_cond_broadcast(&ws->cv);
282 180 : DPRINTF(("EventQueueLength -> %d\n", (int) EventQueueLengthMu(ws)));
283 60 : pthread_mutex_unlock(&ws->mu);
284 60 : }
285 :
286 60 : void ComputeAbsTimeout(struct timespec *tspec, int timeout_nanoseconds) {
287 60 : struct timeval now;
288 :
289 60 : gettimeofday(&now, (struct timezone *) NULL);
290 60 : tspec->tv_sec = now.tv_sec;
291 60 : tspec->tv_nsec = now.tv_usec * 1000 + timeout_nanoseconds;
292 60 : if (tspec->tv_nsec > 1000000000) {
293 2 : ++tspec->tv_sec;
294 2 : tspec->tv_nsec -= 1000000000;
295 2 : }
296 60 : }
297 :
298 : /*
299 : * WaitForEventMu: wait for event, with a timeout. May spuriously
300 : * return without timing out. Returns 0 on timeout.
301 : */
302 68 : int WaitForEventMu(struct WorkState *ws, struct timespec *abs_timeout) {
303 68 : int timed_out_failure = 0;
304 :
305 68 : if (NULL != abs_timeout) {
306 68 : if (pthread_cond_timedwait(&ws->cv, &ws->mu, abs_timeout) == ETIMEDOUT) {
307 16 : timed_out_failure = 1;
308 16 : }
309 68 : } else {
310 0 : int err;
311 :
312 0 : if (0 != (err = pthread_cond_wait(&ws->cv, &ws->mu))) {
313 0 : fprintf(stderr, "WaitForEventMu: error %d\n", err);
314 0 : }
315 : }
316 :
317 68 : return !timed_out_failure;
318 : }
319 :
320 60 : struct Event *EventFactory(enum EventType type, int thread_id, int file_id) {
321 60 : struct Event *ev = malloc(sizeof *ev);
322 180 : CHECK(NULL != ev);
323 60 : ev->next = NULL;
324 60 : ev->type = type;
325 60 : ev->thread_id = thread_id;
326 60 : ev->file_id = file_id;
327 180 : DPRINTF(("EventFactory(%d, %d, %d)\n", type, thread_id, file_id));
328 60 : return ev;
329 : }
330 :
331 60 : void EventOccurred(struct ThreadState *ts, enum EventType type, int file_id) {
332 60 : struct Event *ev = EventFactory(type, ts->this_thread, file_id);
333 60 : EnqueueEvent(ts->ws, ev);
334 60 : }
335 :
336 60 : void EventQueueDiscardMu(struct WorkState *ws) {
337 60 : struct Event *p;
338 60 : struct Event *rest;
339 :
340 180 : DPRINTF(("EventQueueDiscardMu\n"));
341 240 : for (p = ws->q; p != NULL; p = rest) {
342 60 : rest = p->next;
343 60 : free(p);
344 60 : }
345 60 : ws->q = NULL;
346 60 : ws->qend = &ws->q;
347 60 : }
348 :
349 82 : int GetWork(struct ThreadState *ts,
350 82 : void (**functor_out)(void *functor_state),
351 82 : void **functor_state_out) {
352 82 : int actor_thread;
353 82 : int has_work;
354 :
355 246 : DPRINTF(("GetWork(%d)\n", ts->this_thread));
356 82 : pthread_mutex_lock(&ts->ws->mu);
357 710 : while (WORK_ENDED != (actor_thread = ts->ws->actor_thread) &&
358 : actor_thread != ts->this_thread) {
359 729 : DPRINTF(("GetWork(%d) waiting\n", ts->this_thread));
360 243 : pthread_cond_wait(&ts->ws->cv, &ts->ws->mu);
361 243 : }
362 82 : has_work = (actor_thread == ts->this_thread);
363 82 : if (has_work) {
364 60 : *functor_out = ts->ws->action_functor;
365 60 : *functor_state_out = ts->ws->functor_state;
366 60 : ts->ws->actor_thread = WORK_ACCEPTED;
367 60 : }
368 82 : pthread_mutex_unlock(&ts->ws->mu);
369 246 : DPRINTF(("GetWork(%d) returning %d\n", ts->this_thread, has_work));
370 82 : return has_work;
371 : }
372 :
373 60 : void PutWork(struct WorkState *ws, int actor_thread,
374 60 : void (*action_functor)(void *functor_state),
375 60 : void *functor_state) {
376 180 : DPRINTF(("PutWork(thread=%d)\n", actor_thread));
377 60 : pthread_mutex_lock(&ws->mu);
378 172 : while (ws->actor_thread != WORK_PENDING &&
379 : ws->actor_thread != WORK_ACCEPTED) {
380 0 : pthread_cond_wait(&ws->cv, &ws->mu);
381 0 : }
382 60 : ws->actor_thread = actor_thread;
383 60 : ws->action_functor = action_functor;
384 60 : ws->functor_state = functor_state;
385 60 : pthread_cond_broadcast(&ws->cv);
386 60 : pthread_mutex_unlock(&ws->mu);
387 180 : DPRINTF(("PutWork(thread=%d) done\n", actor_thread));
388 60 : }
389 :
390 0 : void WaitForWorkAcceptance(struct WorkState *ws) {
391 0 : pthread_mutex_lock(&ws->mu);
392 0 : while (ws->actor_thread != WORK_ACCEPTED) {
393 0 : pthread_cond_wait(&ws->cv, &ws->mu);
394 0 : }
395 0 : pthread_mutex_unlock(&ws->mu);
396 0 : }
397 :
398 8 : void AnnounceEndOfWork(struct WorkState *ws) {
399 24 : DPRINTF(("AnnounceEndOfWork\n"));
400 8 : pthread_mutex_lock(&ws->mu);
401 : /*
402 : * ensure all previous work is accepted, allowing for no-work programs.
403 : */
404 16 : while (ws->actor_thread != WORK_ACCEPTED &&
405 : ws->actor_thread != WORK_PENDING) {
406 0 : DPRINTF(("AnnounceEndOfWork: waiting for work to drain\n"));
407 0 : pthread_cond_wait(&ws->cv, &ws->mu);
408 0 : }
409 8 : ws->actor_thread = WORK_ENDED;
410 24 : DPRINTF(("AnnounceEndOfWork: broadcast!\n"));
411 8 : pthread_cond_broadcast(&ws->cv);
412 8 : pthread_mutex_unlock(&ws->mu);
413 8 : }
414 :
415 22 : void *ThreadFunc(void *vstate) {
416 22 : struct ThreadState *ts = (struct ThreadState *) vstate;
417 22 : void (*functor)(void *functor_state);
418 22 : void *functor_state;
419 :
420 : /* set ts in TSD */
421 22 : pthread_setspecific(gNaClTestTsdKey, ts);
422 :
423 66 : DPRINTF(("thread %d\n", ts->this_thread));
424 104 : while (GetWork(ts, &functor, &functor_state)) {
425 60 : (*functor)(functor_state);
426 60 : }
427 22 : return NULL;
428 : }
429 :
430 8 : void SpawnThreadsMu(struct WorkState *ws, size_t num_threads) {
431 8 : size_t ix;
432 8 : int err;
433 :
434 24 : CHECK(0 < num_threads);
435 8 : ws->num_workers = num_threads;
436 8 : ws->workers = malloc(num_threads * sizeof *ws->workers);
437 24 : CHECK(NULL != ws->workers);
438 :
439 60 : for (ix = 0; ix < num_threads; ++ix) {
440 22 : ws->workers[ix].this_thread = (int) ix;
441 22 : ws->workers[ix].ws = ws;
442 22 : if (0 != (err = pthread_create(&ws->workers[ix].tid,
443 : (pthread_attr_t *) NULL,
444 : ThreadFunc, (void *) &ws->workers[ix]))) {
445 0 : fprintf(stderr, "nacl_file_lock_test: pthread_create failed, %d\n", err);
446 0 : exit(1);
447 : }
448 22 : }
449 8 : }
450 :
451 : #define CHECK_PROG(ws, expr, cons) \
452 : do { \
453 : if (!(expr)) { \
454 : fprintf(stderr, \
455 : "nacl_file_lock_test: %s does not hold at program:\n", \
456 : #expr); \
457 : crash_cons(ws, "internal error", cons); \
458 : } \
459 : } while (0)
460 :
461 60 : void CheckStateMu(struct NaClSexpCons *cons, struct WorkState *ws) {
462 180 : CHECK_PROG(ws, ws->num_workers != 0, cons);
463 60 : }
464 :
465 60 : void CheckState(struct NaClSexpCons *cons, struct WorkState *ws) {
466 60 : pthread_mutex_lock(&ws->mu);
467 60 : CheckStateMu(cons, ws);
468 60 : pthread_mutex_unlock(&ws->mu);
469 60 : }
470 :
471 8 : void ReapThreads(struct WorkState *ws) {
472 8 : size_t ix;
473 :
474 8 : if (ws->num_workers > 0) {
475 60 : for (ix = 0; ix < ws->num_workers; ++ix) {
476 22 : pthread_join(ws->workers[ix].tid, (void **) NULL);
477 22 : }
478 8 : }
479 8 : }
480 :
481 : struct NaClSexpNode *Eval(struct NaClSexpNode *n, struct WorkState *ws);
482 :
483 8 : struct NaClSexpNode *SetThreadsImpl(struct NaClSexpCons *cons,
484 8 : struct WorkState *ws) {
485 8 : int num_threads;
486 :
487 8 : if (NaClSexpListLength(cons) != 2) {
488 0 : crash_cons(ws, "set-threads should have 1 argument", cons);
489 0 : }
490 8 : if (!NaClSexpIntp(cons->cdr->car)) {
491 0 : crash_cons(ws, "set-threads should have 1 numeric argument", cons);
492 0 : }
493 8 : num_threads = NaClSexpNodeToInt(cons->cdr->car);
494 8 : if (num_threads < 1) {
495 0 : crash_cons(ws, "program specifies too few threads", cons);
496 0 : }
497 8 : if (num_threads >= MAX_THREADS) {
498 0 : crash_cons(ws, "program specifies too many threads", cons);
499 0 : }
500 8 : pthread_mutex_lock(&ws->mu);
501 24 : CHECK_PROG(ws, ws->num_workers == 0, cons);
502 8 : SpawnThreadsMu(ws, num_threads);
503 8 : pthread_mutex_unlock(&ws->mu);
504 8 : return NaClSexpNodeWrapInt(num_threads);
505 : }
506 :
507 8 : struct NaClSexpNode *SetFilesImpl(struct NaClSexpCons *cons,
508 8 : struct WorkState *ws) {
509 8 : int num_files;
510 :
511 8 : if (NaClSexpListLength(cons) != 2) {
512 0 : crash_cons(ws, "set-files should have 1 argument", cons);
513 0 : }
514 8 : if (!NaClSexpIntp(cons->cdr->car)) {
515 0 : crash_cons(ws, "set-files should have 1 numeric argument", cons);
516 0 : }
517 8 : num_files = NaClSexpNodeToInt(cons->cdr->car);
518 8 : if (num_files < 1) {
519 0 : crash_cons(ws, "program specifies too few files", cons);
520 0 : }
521 8 : if (num_files >= MAX_FILES) {
522 0 : crash_cons(ws, "program specifies too many files", cons);
523 0 : }
524 :
525 8 : if (!(*ws->test_if->set_num_files)(ws->test_if, num_files)) {
526 0 : crash_cons(ws, "set-files error", cons);
527 0 : }
528 :
529 8 : return NaClSexpNodeWrapInt(num_files);
530 : }
531 :
532 4 : struct NaClSexpNode *QuoteImpl(struct NaClSexpCons *cons,
533 4 : struct WorkState *ws) {
534 8 : UNREFERENCED_PARAMETER(ws);
535 4 : if (NaClSexpListLength(cons) != 2) {
536 0 : error_cons(ws, "quote takes a single argument", cons);
537 0 : return NULL;
538 : }
539 4 : return NaClSexpDupNode(cons->cdr->car);
540 4 : }
541 :
542 0 : struct NaClSexpNode *CarImpl(struct NaClSexpCons *cons,
543 0 : struct WorkState *ws) {
544 0 : struct NaClSexpNode *p;
545 0 : struct NaClSexpCons *arg;
546 0 : struct NaClSexpNode *result = NULL;
547 0 : if (NaClSexpListLength(cons) != 2) {
548 0 : error_cons(ws, "car takes a single argument", cons);
549 0 : return NULL;
550 : }
551 0 : p = Eval(cons->cdr->car, ws);
552 0 : if (NULL == p || !NaClSexpConsp(p)) {
553 0 : error_cons(ws, "car: argument must evaluate to a list", cons);
554 0 : } else {
555 0 : arg = NaClSexpNodeToCons(p);
556 0 : if (NULL != arg) {
557 0 : result = NaClSexpDupNode(arg->car);
558 0 : }
559 : }
560 0 : return result;
561 0 : }
562 :
563 0 : struct NaClSexpNode *CdrImpl(struct NaClSexpCons *cons,
564 0 : struct WorkState *ws) {
565 0 : struct NaClSexpNode *p;
566 0 : struct NaClSexpCons *arg;
567 0 : struct NaClSexpNode *result = NULL;
568 0 : if (NaClSexpListLength(cons) != 2) {
569 0 : error_cons(ws, "cdr takes a single argument", cons);
570 0 : return NULL;
571 : }
572 0 : p = Eval(cons->cdr->car, ws);
573 0 : if (NULL == p || !NaClSexpConsp(p)) {
574 0 : error_cons(ws, "cdr: argument must evaluate to a list", cons);
575 0 : } else {
576 0 : arg = NaClSexpNodeToCons(p);
577 0 : if (NULL != arg) {
578 0 : result = NaClSexpNodeWrapCons(NaClSexpDupCons(arg->cdr));
579 0 : }
580 : }
581 0 : return result;
582 0 : }
583 :
584 0 : struct NaClSexpNode *ConsImpl(struct NaClSexpCons *cons,
585 0 : struct WorkState *ws) {
586 0 : struct NaClSexpNode *first;
587 0 : struct NaClSexpNode *second;
588 0 : struct NaClSexpNode *result = NULL;
589 :
590 0 : if (NaClSexpListLength(cons) != 3) {
591 0 : error_cons(ws, "cons take two arguments", cons);
592 0 : return NULL;
593 : }
594 0 : first = Eval(cons->cdr->car, ws);
595 0 : second = Eval(cons->cdr->cdr->car, ws);
596 0 : if (!NaClSexpConsp(second)) {
597 0 : error_cons(ws, "cons: second argument must evaluate to a list", cons);
598 0 : } else {
599 0 : result = NaClSexpNodeWrapCons(
600 0 : NaClSexpConsCons(NaClSexpDupNode(first),
601 0 : NaClSexpDupCons(NaClSexpNodeToCons(second))));
602 : }
603 0 : NaClSexpFreeNode(first);
604 0 : NaClSexpFreeNode(second);
605 0 : return result;
606 0 : }
607 :
608 0 : struct NaClSexpNode *ListImpl(struct NaClSexpCons *cons,
609 0 : struct WorkState *ws) {
610 0 : struct NaClSexpCons *result = NULL;
611 0 : struct NaClSexpCons **addpos = &result;
612 0 : struct NaClSexpCons *p;
613 :
614 0 : for (p = cons->cdr; NULL != p; p = p->cdr) {
615 0 : *addpos = NaClSexpConsWrapNode(Eval(p->car, ws));
616 0 : addpos = &((*addpos)->cdr);
617 0 : }
618 0 : return NaClSexpNodeWrapCons(result);
619 : }
620 :
621 4 : struct NaClSexpNode *NthImpl(struct NaClSexpCons *cons,
622 4 : struct WorkState *ws) {
623 4 : struct NaClSexpCons *result = NULL;
624 4 : struct NaClSexpCons *p;
625 4 : struct NaClSexpNode *arg_selector;
626 4 : struct NaClSexpNode *arg_list;
627 4 : size_t ix = 0;
628 :
629 4 : if (NaClSexpListLength(cons) != 3) {
630 0 : crash_cons(ws, "nth takes exactly two arguments", cons);
631 0 : }
632 4 : arg_selector = Eval(cons->cdr->car, ws);
633 4 : arg_list = Eval(cons->cdr->cdr->car, ws);
634 4 : if (!NaClSexpIntp(arg_selector)) {
635 0 : error_cons(ws, "nth: first arg does not evaluate to an integer", cons);
636 4 : } else if (!NaClSexpConsp(arg_list)) {
637 0 : error_cons(ws, "nth: second arg does not evaluate to a list", cons);
638 0 : } else {
639 4 : ix = NaClSexpNodeToInt(arg_selector);
640 12 : for (p = NaClSexpNodeToCons(arg_list);
641 : NULL != p && ix > 0;
642 0 : p = p->cdr, --ix) {
643 0 : continue;
644 : }
645 4 : if (ix == 0) {
646 4 : result = p;
647 4 : }
648 : }
649 12 : return NaClSexpDupNode(NULL == result ? NULL : result->car);
650 : }
651 :
652 0 : struct NaClSexpNode *AppendImpl(struct NaClSexpCons *cons,
653 0 : struct WorkState *ws) {
654 0 : struct NaClSexpNode *first = NULL;
655 0 : struct NaClSexpNode *second = NULL;
656 0 : struct NaClSexpNode *result = NULL;
657 :
658 0 : if (NaClSexpListLength(cons) != 3) {
659 0 : crash_cons(ws, "append take exactly two arguments", cons);
660 0 : }
661 0 : first = Eval(cons->cdr->car, ws);
662 0 : second = Eval(cons->cdr->cdr->car, ws);
663 0 : if (!NaClSexpConsp(first)) {
664 0 : error_cons(ws, "append: first arg does not evaluate to a list", cons);
665 0 : } else if (!NaClSexpConsp(second)) {
666 0 : error_cons(ws, "append: second arg does not evaluate to a list", cons);
667 0 : } else {
668 0 : result = NaClSexpNodeWrapCons(NaClSexpAppend(
669 0 : NaClSexpNodeToCons(first),
670 0 : NaClSexpNodeToCons(second)));
671 : }
672 0 : NaClSexpFreeNode(first);
673 0 : NaClSexpFreeNode(second);
674 0 : return result;
675 : }
676 :
677 : /*
678 : * The arithmetic functions are just for fun. And to test that the
679 : * basic evaluation framework makes sense.
680 : */
681 0 : struct NaClSexpNode *MultImpl(struct NaClSexpCons *cons,
682 0 : struct WorkState *ws) {
683 0 : int first = 1;
684 0 : int value = 0;
685 0 : struct NaClSexpNode *v = NULL;
686 0 : struct NaClSexpCons *p;
687 :
688 0 : for (p = cons->cdr; NULL != p; p = p->cdr) {
689 0 : v = Eval(p->car, ws);
690 0 : if (!NaClSexpIntp(v)) {
691 0 : error_node(ws, "argument not integral", v);
692 0 : return NULL;
693 : }
694 0 : if (first) {
695 0 : value = NaClSexpNodeToInt(v);
696 0 : first = 0;
697 0 : } else {
698 0 : value *= NaClSexpNodeToInt(v);
699 : }
700 0 : NaClSexpFreeNode(v);
701 0 : }
702 0 : return NaClSexpNodeWrapInt(value);
703 0 : }
704 :
705 0 : struct NaClSexpNode *DivImpl(struct NaClSexpCons *cons,
706 0 : struct WorkState *ws) {
707 0 : int first = 1;
708 0 : int value = 0;
709 0 : struct NaClSexpNode *v = NULL;
710 0 : struct NaClSexpCons *p;
711 :
712 0 : for (p = cons->cdr; NULL != p; p = p->cdr) {
713 0 : v = Eval(p->car, ws);
714 0 : if (!NaClSexpIntp(v)) {
715 0 : error_node(ws, "argument not integral", v);
716 0 : return NULL;
717 : }
718 0 : if (first) {
719 0 : value = NaClSexpNodeToInt(v);
720 0 : first = 0;
721 0 : } else {
722 0 : value /= NaClSexpNodeToInt(v);
723 : }
724 0 : NaClSexpFreeNode(v);
725 0 : }
726 0 : return NaClSexpNodeWrapInt(value);
727 0 : }
728 :
729 0 : struct NaClSexpNode *AddImpl(struct NaClSexpCons *cons,
730 0 : struct WorkState *ws) {
731 0 : int first = 1;
732 0 : int value = 0;
733 0 : struct NaClSexpNode *v = NULL;
734 0 : struct NaClSexpCons *p;
735 :
736 0 : for (p = cons->cdr; NULL != p; p = p->cdr) {
737 0 : v = Eval(p->car, ws);
738 0 : if (!NaClSexpIntp(v)) {
739 0 : error_node(ws, "argument not integral", v);
740 0 : return NULL;
741 : }
742 0 : if (first) {
743 0 : value = NaClSexpNodeToInt(v);
744 0 : first = 0;
745 0 : } else {
746 0 : value += NaClSexpNodeToInt(v);
747 : }
748 0 : NaClSexpFreeNode(v);
749 0 : }
750 0 : return NaClSexpNodeWrapInt(value);
751 0 : }
752 :
753 0 : struct NaClSexpNode *SubImpl(struct NaClSexpCons *cons,
754 0 : struct WorkState *ws) {
755 0 : int first = 1;
756 0 : int value = 0;
757 0 : struct NaClSexpNode *v = NULL;
758 0 : struct NaClSexpCons *p;
759 :
760 0 : for (p = cons->cdr; NULL != p; p = p->cdr) {
761 0 : v = Eval(p->car, ws);
762 0 : if (!NaClSexpIntp(v)) {
763 0 : error_node(ws, "argument not integral", v);
764 0 : return NULL;
765 : }
766 0 : if (first) {
767 0 : value = NaClSexpNodeToInt(v);
768 0 : first = 0;
769 0 : } else {
770 0 : value -= NaClSexpNodeToInt(v);
771 : }
772 0 : NaClSexpFreeNode(v);
773 0 : }
774 0 : return NaClSexpNodeWrapInt(value);
775 0 : }
776 :
777 108 : static struct NaClSexpNode *MatcherResult(int64_t matcher_position,
778 108 : uint64_t matched_bitset) {
779 324 : DPRINTF(("MatcherResult(%"NACL_PRId64", 0x%"NACL_PRIx64")\n",
780 : matcher_position, matched_bitset));
781 108 : return NaClSexpNodeWrapCons(
782 216 : NaClSexpConsCons(NaClSexpNodeWrapInt(matcher_position),
783 108 : NaClSexpConsCons(NaClSexpNodeWrapInt(matched_bitset),
784 : NULL)));
785 : }
786 :
787 140 : static int MatchResultExtract(int64_t *matcher_pos,
788 140 : uint64_t *matched_bitset,
789 140 : struct NaClSexpNode *result) {
790 140 : struct NaClSexpCons *result_cons;
791 140 : if (NULL == result) {
792 32 : return 0;
793 : }
794 324 : CHECK(NaClSexpConsp(result));
795 108 : result_cons = NaClSexpNodeToCons(result);
796 324 : CHECK(2 == NaClSexpListLength(result_cons));
797 324 : CHECK(NaClSexpIntp(result_cons->car));
798 324 : CHECK(NaClSexpIntp(result_cons->cdr->car));
799 108 : if (NULL != matcher_pos) {
800 104 : *matcher_pos = NaClSexpNodeToInt(result_cons->car);
801 104 : }
802 108 : if (NULL != matched_bitset) {
803 108 : *matched_bitset = NaClSexpNodeToInt(result_cons->cdr->car);
804 108 : }
805 108 : return 1;
806 140 : }
807 :
808 16 : struct NaClSexpNode *EpsilonMatcherImpl(struct NaClSexpCons *cons,
809 16 : struct WorkState *ws) {
810 16 : if (NaClSexpListLength(cons) != 1) {
811 0 : crash_cons(ws, "epsilon built-in should have no arguments", cons);
812 0 : }
813 48 : DPRINTF(("Epsilon\n"));
814 : /*
815 : * Check that the event queue is empty.
816 : */
817 16 : if (EventQueueLengthMu(ws) == 0) {
818 48 : DPRINTF(("epsilon: success -- empty event queue\n"));
819 16 : return MatcherResult(-1, 0);
820 : }
821 0 : DPRINTF(("epsilon: fail -- non-zero length event queue\n"));
822 0 : return NULL;
823 16 : }
824 :
825 4 : struct NaClSexpNode *PrognImpl(struct NaClSexpCons *cons,
826 4 : struct WorkState *ws) {
827 4 : struct NaClSexpNode *node;
828 4 : struct NaClSexpNode *val = NULL;
829 :
830 24 : while (NULL != (cons = cons->cdr)) {
831 16 : node = cons->car;
832 16 : if (NaClSexpConsp(node)) {
833 16 : NaClSexpFreeNode(val);
834 16 : val = Eval(node, ws);
835 16 : } else {
836 0 : crash_node(ws, "Not a list", node);
837 : }
838 16 : }
839 4 : return val;
840 : }
841 :
842 : enum WorkType {
843 : kTakeLock = 0,
844 : kDropLock = 1,
845 : };
846 :
847 : struct WorkItem {
848 : struct WorkState *ws;
849 : enum WorkType type;
850 : int desc;
851 : };
852 :
853 60 : struct WorkItem *WorkItemFactory(struct WorkState *ws,
854 60 : enum WorkType type,
855 60 : int desc) {
856 60 : struct WorkItem *wi = malloc(sizeof *wi);
857 180 : CHECK(NULL != wi);
858 60 : wi->ws = ws;
859 60 : wi->type = type;
860 60 : wi->desc = desc;
861 60 : return wi;
862 : }
863 :
864 60 : static void WorkOnWorkItem(void *functor_state) {
865 60 : struct WorkItem *wi = (struct WorkItem *) functor_state;
866 :
867 180 : DPRINTF(("WorkOnWorkItem: entered\n"));
868 120 : switch (wi->type) {
869 : case kTakeLock:
870 30 : NaClFileLockManagerLock(&wi->ws->flm, wi->desc);
871 30 : break;
872 : case kDropLock:
873 30 : NaClFileLockManagerUnlock(&wi->ws->flm, wi->desc);
874 30 : break;
875 : }
876 180 : DPRINTF(("WorkOnWorkItem: done\n"));
877 60 : free(wi);
878 60 : }
879 :
880 60 : struct NaClSexpNode *LockUnlock(struct NaClSexpCons *cons,
881 60 : struct WorkState *ws,
882 60 : enum WorkType op) {
883 60 : struct NaClSexpNode *p;
884 60 : int actor_thread;
885 60 : int file_desc;
886 :
887 60 : CheckState(cons, ws);
888 60 : if (NaClSexpListLength(cons) != 3) {
889 0 : error_cons(ws,
890 : "lock/unlock takes 2 arguments: thread-id and file-id", cons);
891 0 : return NULL;
892 : }
893 60 : p = Eval(cons->cdr->car, ws);
894 60 : if (!NaClSexpIntp(p)) {
895 0 : error_cons(ws,
896 : "lock/unlock thread-id argument evaluate to an integer", cons);
897 0 : return NULL;
898 : }
899 60 : actor_thread = NaClSexpNodeToInt(p);
900 60 : NaClSexpFreeNode(p);
901 60 : p = Eval(cons->cdr->cdr->car, ws);
902 60 : if (!NaClSexpIntp(p)) {
903 0 : error_cons(ws,
904 : "lock/unlock file-id argument evaluate to an integer", cons);
905 0 : return NULL;
906 : }
907 60 : file_desc = NaClSexpNodeToInt(p);
908 60 : NaClSexpFreeNode(p);
909 120 : PutWork(ws, actor_thread,
910 60 : WorkOnWorkItem, WorkItemFactory(ws, op, file_desc));
911 60 : return NULL;
912 60 : }
913 :
914 30 : struct NaClSexpNode *LockImpl(struct NaClSexpCons *cons, struct WorkState *ws) {
915 : /*
916 : * (lock t f) -- tell thread t to take lock f.
917 : */
918 30 : return LockUnlock(cons, ws, kTakeLock);
919 : }
920 :
921 30 : struct NaClSexpNode *UnlockImpl(struct NaClSexpCons *cons,
922 30 : struct WorkState *ws) {
923 : /*
924 : * (unlock t f) -- tell thread t to drop lock f.
925 : */
926 30 : return LockUnlock(cons, ws, kDropLock);
927 : }
928 :
929 : /*
930 : * Called by matchers, so ws->mu is held already.
931 : */
932 87 : struct NaClSexpNode *EventQueueEventMatcher(struct NaClSexpCons *cons,
933 87 : struct WorkState *ws,
934 87 : enum EventType expected_event) {
935 87 : struct NaClSexpNode *n;
936 87 : int expected_thread_id;
937 87 : int expected_file_id;
938 87 : size_t list_pos = 0;
939 87 : struct NaClSexpNode *p = NULL;
940 87 : struct Event *event_entry;
941 :
942 87 : if (NaClSexpListLength(cons) != 3) {
943 0 : error_cons(ws,
944 : "locked/unlocked takes exactly two arguments, thread_id and"
945 : " lock_id", cons);
946 0 : return NULL;
947 : }
948 87 : n = Eval(cons->cdr->car, ws);
949 87 : if (!NaClSexpIntp(n)) {
950 0 : error_cons(ws,
951 : "locked/unlocked thread_id argument must eval to an integer",
952 : cons);
953 0 : NaClSexpFreeNode(n);
954 0 : return NULL;
955 : }
956 87 : expected_thread_id = NaClSexpNodeToInt(n);
957 87 : NaClSexpFreeNode(n);
958 87 : n = Eval(cons->cdr->cdr->car, ws);
959 87 : if (!NaClSexpIntp(n)) {
960 0 : error_cons(ws,
961 : "locked/unlocked file_id argument must eval to an integer",
962 : cons);
963 0 : NaClSexpFreeNode(n);
964 0 : return NULL;
965 : }
966 87 : expected_file_id = NaClSexpNodeToInt(n);
967 87 : NaClSexpFreeNode(n);
968 :
969 261 : DPRINTF(("locked/unlocked matcher: %s, thread %d, file %d\n",
970 : (expected_event == kLocked) ? "locked" : "unlocked",
971 : expected_thread_id, expected_file_id));
972 :
973 205 : for (event_entry = ws->q;
974 : NULL != event_entry;
975 31 : ++list_pos, event_entry = event_entry->next) {
976 247 : if (event_entry->type == expected_event &&
977 : event_entry->thread_id == expected_thread_id &&
978 : event_entry->file_id == expected_file_id) {
979 72 : if (list_pos > 8 * sizeof(int64_t)) {
980 0 : crash_cons(ws, "event queue too deep", cons);
981 0 : }
982 72 : p = MatcherResult(-1, 1 << list_pos);
983 72 : break;
984 : }
985 31 : }
986 87 : return p;
987 87 : }
988 :
989 45 : struct NaClSexpNode *LockedMatcherImpl(struct NaClSexpCons *cons,
990 45 : struct WorkState *ws) {
991 : /*
992 : * (locked t f) -- look for event (kLocked t f) in event queue.
993 : */
994 45 : return EventQueueEventMatcher(cons, ws, kLocked);
995 : }
996 :
997 42 : struct NaClSexpNode *UnlockedMatcherImpl(struct NaClSexpCons *cons,
998 42 : struct WorkState *ws) {
999 : /*
1000 : * (unlocked t f) -- look for event (kUnlocked t f) in event queue.
1001 : */
1002 42 : return EventQueueEventMatcher(cons, ws, kUnlocked);
1003 : }
1004 :
1005 : struct NaClSexpNode *AllMatcherImpl(struct NaClSexpCons *cons,
1006 : struct WorkState *ws);
1007 :
1008 : struct NaClSexpNode *AnyMatcherImpl(struct NaClSexpCons *cons,
1009 : struct WorkState *ws);
1010 :
1011 : struct NaClSexpNode *Eval(struct NaClSexpNode *n,
1012 : struct WorkState *ws);
1013 :
1014 4 : struct NaClSexpNode *EvalImpl(struct NaClSexpCons *cons,
1015 4 : struct WorkState *ws) {
1016 4 : struct NaClSexpNode *n;
1017 4 : struct NaClSexpNode *eval_n;
1018 : /*
1019 : * Check that there is a single argument, the invoke Eval on it.
1020 : */
1021 4 : if (NaClSexpListLength(cons) != 2) {
1022 0 : error_cons(ws, "eval takes exactly one argument", cons);
1023 0 : return NULL;
1024 : }
1025 4 : n = Eval(cons->cdr->car, ws);
1026 4 : eval_n = Eval(n, ws);
1027 4 : NaClSexpFreeNode(n);
1028 4 : return eval_n;
1029 4 : }
1030 :
1031 : struct NaClSexpNode *MatchMatcherImpl(struct NaClSexpCons *cons,
1032 : struct WorkState *ws);
1033 :
1034 : struct SymbolTable {
1035 : char const *name;
1036 : int is_matcher;
1037 :
1038 : /*
1039 : * The |fn| member may be a built-in function, or a matcher as
1040 : * specified by |is_matcher|. If !is_matcher, then it returns an
1041 : * s-expression that is the value of the function. If it is a
1042 : * matcher, then at the lisp level the "apparent" return value is an
1043 : * integer. Internally, successful matchers return the following:
1044 : *
1045 : * ( sub-matcher-index event-pos-bitset )
1046 : *
1047 : * For non-composite matchers, sub-matcher-index is NULL. The list
1048 : * of event-pos-bitset is an integer with a non-zero bit for each
1049 : * events that were matched, with the bit position corresponding to
1050 : * their positions in the event queue. NB: it is a test
1051 : * specification error if any sub-matchers used in the (any ...)
1052 : * special form matches a subset of the events matched by another
1053 : * sub-matcher, or sub-matchers used in the (all ...) special form
1054 : * overlap.
1055 : *
1056 : * A matcher that failed to match returns NULL.
1057 : */
1058 : struct NaClSexpNode *(*fn)(struct NaClSexpCons *cons, struct WorkState *ws);
1059 : };
1060 :
1061 : struct SymbolTable g_symtab[] = {
1062 : {
1063 : "set-threads", 0, SetThreadsImpl
1064 : }, {
1065 : "set-files", 0, SetFilesImpl
1066 : }, {
1067 : "quote", 0, QuoteImpl
1068 : }, {
1069 : "car", 0, CarImpl
1070 : }, {
1071 : "cdr", 0, CdrImpl
1072 : }, {
1073 : "cons", 0, ConsImpl
1074 : }, {
1075 : "list", 0, ListImpl
1076 : }, {
1077 : "nth", 0, NthImpl
1078 : }, {
1079 : "append", 0, AppendImpl
1080 : }, {
1081 : "eval", 0, EvalImpl
1082 : }, {
1083 : "*", 0, MultImpl
1084 : }, {
1085 : "/", 0, DivImpl
1086 : }, {
1087 : "+", 0, AddImpl
1088 : }, {
1089 : "-", 0, SubImpl
1090 : }, {
1091 : "progn", 0, PrognImpl
1092 : }, {
1093 : "lock", 0, LockImpl
1094 : }, {
1095 : "unlock", 0, UnlockImpl
1096 : }, {
1097 : "match", 1, MatchMatcherImpl
1098 : }, {
1099 : "epsilon", 1, EpsilonMatcherImpl
1100 : }, {
1101 : "locked", 1, LockedMatcherImpl
1102 : }, {
1103 : "unlocked", 1, UnlockedMatcherImpl
1104 : }, {
1105 : "all", 1, AllMatcherImpl
1106 : }, {
1107 : "any", 1, AnyMatcherImpl
1108 : }
1109 : };
1110 :
1111 108 : static int CheckMatchers(struct WorkState *ws,
1112 108 : struct NaClSexpCons *matcher_list,
1113 108 : struct SymbolTable **matcher_entries) {
1114 108 : size_t mx;
1115 108 : size_t ix;
1116 108 : struct NaClSexpCons *matchers;
1117 108 : struct NaClSexpNode *cur;
1118 108 : struct NaClSexpCons *submatcher;
1119 108 : char const *submatcher_name;
1120 :
1121 361 : for (mx = 0, matchers = matcher_list;
1122 : NULL != matchers;
1123 145 : ++mx, matchers = matchers->cdr) {
1124 145 : cur = matchers->car;
1125 145 : if (!NaClSexpConsp(cur)) {
1126 0 : error_node(ws, "all: submatcher not a list", cur);
1127 0 : return 0;
1128 : }
1129 145 : submatcher = NaClSexpNodeToCons(cur);
1130 290 : if (NULL == submatcher || !NaClSexpTokenp(submatcher->car)) {
1131 0 : error_node(ws, "all: submatcher not a matcher", cur);
1132 0 : return 0;
1133 : }
1134 145 : submatcher_name = NaClSexpNodeToToken(submatcher->car);
1135 6026 : for (ix = 0; ix < sizeof g_symtab/sizeof g_symtab[0]; ++ix) {
1136 3013 : if (!strcmp(g_symtab[ix].name, submatcher_name)) {
1137 : /* found! */
1138 145 : if (!g_symtab[ix].is_matcher) {
1139 0 : error_node(ws, "all: submatcher not a matcher", cur);
1140 0 : return 0;
1141 : }
1142 : /* save pointer for later use */
1143 145 : matcher_entries[mx] = &g_symtab[ix];
1144 145 : break;
1145 : }
1146 2868 : }
1147 145 : if (ix == sizeof g_symtab/sizeof g_symtab[0]) {
1148 0 : error_node(ws, "all: submatcher not found", cur);
1149 0 : return 0;
1150 : }
1151 145 : }
1152 108 : return 1;
1153 108 : }
1154 :
1155 29 : struct NaClSexpNode *AllMatcherImpl(struct NaClSexpCons *cons,
1156 29 : struct WorkState *ws) {
1157 29 : int64_t match_index = -1;
1158 29 : uint64_t match_pos = 0;
1159 29 : size_t num_matchers = NaClSexpListLength(cons) - 1;
1160 29 : size_t mx;
1161 29 : struct NaClSexpCons *matchers;
1162 29 : struct NaClSexpNode *cur;
1163 29 : struct SymbolTable **matcher_entries = NULL;
1164 29 : struct NaClSexpNode *match_result;
1165 29 : int64_t submatch_index;
1166 29 : uint64_t submatch_pos;
1167 :
1168 29 : if (gVerbosity > 2) {
1169 0 : printf("AllMatcherImpl: %"NACL_PRIdS" submatchers\n", num_matchers);
1170 0 : }
1171 29 : if (0 == num_matchers) {
1172 0 : error_cons(ws, "all must have at least one sub-matcher", cons);
1173 0 : return NULL;
1174 : }
1175 : matcher_entries = (struct SymbolTable **)
1176 29 : malloc(num_matchers * sizeof *matcher_entries);
1177 29 : if (!CheckMatchers(ws, cons->cdr, matcher_entries)) {
1178 0 : error_cons(ws, "all: submatcher error", cons);
1179 0 : free(matcher_entries);
1180 0 : return NULL;
1181 : }
1182 : /*
1183 : * Invoke all submatchers. If any fail, we fail. Accumulate event
1184 : * queue indices.
1185 : */
1186 102 : for (mx = 0, matchers = cons->cdr;
1187 : NULL != matchers;
1188 44 : ++mx, matchers = matchers->cdr) {
1189 57 : cur = matchers->car;
1190 57 : match_result = (*matcher_entries[mx]->fn)(NaClSexpNodeToCons(cur), ws);
1191 :
1192 57 : if (gVerbosity > 2) {
1193 0 : printf("submatcher "); NaClSexpPrintNode(stdout,cur); printf(" --> ");
1194 0 : NaClSexpPrintNode(stdout, match_result);
1195 0 : printf("\n");
1196 0 : }
1197 :
1198 57 : if (!MatchResultExtract(&submatch_index, &submatch_pos, match_result)) {
1199 39 : DPRINTF(("submatcher failed\n"));
1200 13 : NaClSexpFreeNode(match_result);
1201 13 : free(matcher_entries);
1202 13 : return NULL;
1203 : }
1204 44 : NaClSexpFreeNode(match_result);
1205 :
1206 44 : if ((match_pos & submatch_pos) != 0) {
1207 0 : error_cons(ws, "all: overlapping matchers", cons);
1208 0 : free(matcher_entries);
1209 0 : return NULL;
1210 : }
1211 : /*
1212 : * Allow, for example, the (all (unlocked 0 0) (any (locked 1 0)
1213 : * (locked 2 0))) to propagate the submatch index from the (any
1214 : * ...) form up. This does not generalize to more than one (any
1215 : * ...) sub-sexpressions in the (all ...) form.
1216 : */
1217 88 : if (-1 == match_index && -1 != submatch_index) {
1218 2 : match_index = submatch_index;
1219 2 : }
1220 44 : match_pos |= submatch_pos;
1221 44 : }
1222 16 : free(matcher_entries);
1223 16 : return MatcherResult(match_index, match_pos);
1224 29 : }
1225 :
1226 8 : struct NaClSexpNode *AnyMatcherImpl(struct NaClSexpCons *cons,
1227 8 : struct WorkState *ws) {
1228 8 : uint64_t submatch_pos = 0;
1229 8 : size_t num_matchers = NaClSexpListLength(cons) - 1;
1230 8 : size_t mx;
1231 8 : struct NaClSexpCons *matchers;
1232 8 : struct NaClSexpNode *cur;
1233 8 : struct SymbolTable **matcher_entries = NULL;
1234 8 : struct NaClSexpNode *match_result = NULL;
1235 :
1236 8 : if (gVerbosity > 2) {
1237 0 : printf("AnyMatcherImpl: %"NACL_PRIdS" submatchers\n", num_matchers);
1238 0 : }
1239 8 : if (0 == num_matchers) {
1240 0 : error_cons(ws, "any must have at least one sub-matcher", cons);
1241 0 : return NULL;
1242 : }
1243 : matcher_entries = (struct SymbolTable **)
1244 8 : malloc(num_matchers * sizeof *matcher_entries);
1245 8 : if (!CheckMatchers(ws, cons->cdr, matcher_entries)) {
1246 0 : error_cons(ws, "any: submatcher error", cons);
1247 0 : free(matcher_entries);
1248 0 : return NULL;
1249 : }
1250 : /*
1251 : * Invoke all submatchers. If any succeed, we succeed.
1252 : */
1253 24 : for (mx = 0, matchers = cons->cdr;
1254 : NULL != matchers;
1255 8 : ++mx, matchers = matchers->cdr) {
1256 12 : cur = matchers->car;
1257 12 : match_result = (*matcher_entries[mx]->fn)(NaClSexpNodeToCons(cur), ws);
1258 :
1259 12 : if (gVerbosity > 2) {
1260 0 : printf("submatcher "); NaClSexpPrintNode(stdout,cur); printf(" --> ");
1261 0 : NaClSexpPrintNode(stdout, match_result);
1262 0 : printf("\n");
1263 0 : }
1264 :
1265 12 : if (MatchResultExtract((int64_t *) NULL, &submatch_pos, match_result)) {
1266 12 : DPRINTF(("submatcher succeeded\n"));
1267 4 : NaClSexpFreeNode(match_result);
1268 4 : match_result = MatcherResult(mx, submatch_pos);
1269 4 : break;
1270 : }
1271 8 : NaClSexpFreeNode(match_result);
1272 8 : }
1273 8 : free(matcher_entries);
1274 8 : return match_result;
1275 8 : }
1276 :
1277 : /*
1278 : * Single arg must be a matcher. Evaluate it. If successful, check
1279 : * that all events in the event queue were matched; if so, discard all
1280 : * events in event queue, and return the match index. If not
1281 : * successful or not all events were matched, leave the event queue
1282 : * alone and return -1. Typically returned value is used by (nth ...)
1283 : * form.
1284 : */
1285 71 : struct NaClSexpNode *MatchMatcherImpl(struct NaClSexpCons *cons,
1286 71 : struct WorkState *ws) {
1287 :
1288 71 : struct SymbolTable *matcher[1];
1289 71 : struct NaClSexpNode *result;
1290 71 : int64_t which_match;
1291 71 : uint64_t match_set;
1292 :
1293 213 : DPRINTF(("MatchMatcherImpl\n"));
1294 71 : if (NaClSexpListLength(cons) != 2) {
1295 0 : error_cons(ws, "match takes a single matcher as argument", cons);
1296 0 : return NULL;
1297 : }
1298 71 : if (!CheckMatchers(ws, cons->cdr, matcher)) {
1299 0 : error_cons(ws, "match argument should be a matcher", cons);
1300 0 : return NULL;
1301 : }
1302 71 : if (!NaClSexpConsp(cons->cdr->car)) {
1303 0 : error_cons(ws, "match argument not a list", cons);
1304 0 : return NULL;
1305 : }
1306 71 : result = (*matcher[0]->fn)(NaClSexpNodeToCons(cons->cdr->car), ws);
1307 71 : if (!MatchResultExtract(&which_match, &match_set, result)) {
1308 33 : DPRINTF(("did not match\n"));
1309 11 : NaClSexpFreeNode(result);
1310 11 : result = NULL;
1311 71 : } else if (match_set != ((((uint64_t) 1) << EventQueueLengthMu(ws)) - 1)) {
1312 : /* did not match all entries */
1313 0 : DPRINTF(("match set incomplete\n"));
1314 0 : NaClSexpFreeNode(result);
1315 0 : result = NULL;
1316 0 : } else {
1317 180 : DPRINTF(("matched all events\n"));
1318 60 : EventQueueDiscardMu(ws);
1319 60 : NaClSexpFreeNode(result);
1320 60 : result = NaClSexpNodeWrapInt(which_match);
1321 : }
1322 71 : return result;
1323 71 : }
1324 :
1325 446 : struct NaClSexpNode *Eval(struct NaClSexpNode *n, struct WorkState *ws) {
1326 446 : struct NaClSexpCons *cons;
1327 446 : size_t ix;
1328 446 : struct NaClSexpNode *car;
1329 446 : char const *token;
1330 446 : struct NaClSexpNode *val = NULL;
1331 446 : struct timespec timeout_time;
1332 446 : int wait_for_more;
1333 446 : int last_match;
1334 :
1335 446 : if (!NaClSexpConsp(n)) {
1336 : /* for now; symbol table lookup when there are symbols with values */
1337 294 : return NaClSexpDupNode(n);
1338 : }
1339 152 : cons = NaClSexpNodeToCons(n);
1340 152 : if (NULL == cons) {
1341 0 : return NaClSexpDupNode(n);
1342 : }
1343 :
1344 152 : car = cons->car;
1345 152 : if (!NaClSexpTokenp(car)) {
1346 0 : crash_cons(ws,
1347 : "nacl_file_lock_test: car of list should be a built-in function",
1348 : cons);
1349 0 : }
1350 152 : token = NaClSexpNodeToToken(car);
1351 456 : DPRINTF(("function %s\n", token));
1352 4476 : for (ix = 0; ix < sizeof g_symtab / sizeof g_symtab[0]; ++ix) {
1353 2238 : if (!strcmp(token, g_symtab[ix].name)) {
1354 152 : if (!g_symtab[ix].is_matcher) {
1355 92 : val = (*g_symtab[ix].fn)(cons, ws);
1356 92 : } else {
1357 : /*
1358 : * A "matcher" special form is a bit weird/tricky. These are
1359 : * not blocking functions, since matchers can be used in
1360 : * conjunction with other matchers in (all ...) or (any ...)
1361 : * forms. What we do is the following: we wait for events,
1362 : * and as events arrive in the event queue, we run the
1363 : * matcher, which must immediately return whether a match
1364 : * against the contents of the event queue occurred. If there
1365 : * is no match, we wait for another event, until the timeout
1366 : * occurs; if timeout occurs and the matcher did not match,
1367 : * then it is an error and we abort the test program. For the
1368 : * (all ...) form, the AllMatcherImpl (essentially AND) will
1369 : * check that all arguments are themselves matchers and run
1370 : * them to see if all succeeds, and AllMatcherImpl only
1371 : * succeeds if all succeeded. The AnyMatcherImpl (OR) will
1372 : * succeed if any of the argument matchers succeed. Matchers
1373 : * return the position in the event queue where the match
1374 : * occurred, so the composite matchers can remove the events
1375 : * appropriately. Matching and removal is done with the event
1376 : * list locked, so worker threads that wake up etc cannot add
1377 : * new events. Position is relative to the head, so even if
1378 : * this were not the case, we would not get confused about
1379 : * which event was matched.
1380 : *
1381 : * Later we may consider matchers that introduce a variable to
1382 : * be bound to an event parameter, to be used later by
1383 : * subsequent matchers. This can be used to cut down on the
1384 : * combinatoric explosion that occurs with possible futures
1385 : * when, for example, several threads might wake up when a
1386 : * lock becomes available. We need to think about scoping in
1387 : * that case.
1388 : */
1389 180 : DPRINTF(("Matcher found\n"));
1390 60 : pthread_mutex_lock(&ws->mu);
1391 60 : last_match = 0;
1392 60 : ComputeAbsTimeout(&timeout_time, gEpsilonDelayNanos);
1393 :
1394 60 : wait_for_more = 0;
1395 131 : while (!last_match) {
1396 213 : DPRINTF(("Checking EventQueueLengthMu -> %d\n",
1397 : (int) EventQueueLengthMu(ws)));
1398 85 : if (EventQueueLengthMu(ws) == 0 || wait_for_more) {
1399 204 : DPRINTF(("Waiting for event\n"));
1400 68 : if (!WaitForEventMu(ws, &timeout_time)) {
1401 48 : DPRINTF(("Event timed out\n"));
1402 16 : last_match = 1;
1403 16 : }
1404 68 : }
1405 : /*
1406 : * Run matcher on event queue; matchers are invoked while
1407 : * holding the lock.
1408 : */
1409 71 : val = (*g_symtab[ix].fn)(cons, ws);
1410 71 : if (gVerbosity > 1) {
1411 0 : printf("matcher returned: ");
1412 0 : NaClSexpPrintNode(stdout,val);
1413 0 : putchar('\n');
1414 0 : }
1415 71 : if (NULL != val) {
1416 : /* successful match! */
1417 60 : break;
1418 : }
1419 :
1420 11 : if (last_match) {
1421 0 : error_cons(ws, "match failed; timed out", cons);
1422 0 : val = NULL;
1423 0 : break;
1424 : }
1425 33 : DPRINTF(("match failed, waiting for more events\n"));
1426 11 : wait_for_more = 1;
1427 11 : }
1428 :
1429 60 : pthread_mutex_unlock(&ws->mu);
1430 : }
1431 152 : return val;
1432 : }
1433 2086 : }
1434 0 : fprintf(stderr, "No such function: %s\n", token);
1435 0 : return NULL;
1436 446 : }
1437 :
1438 8 : void ReadEvalPrintLoop(struct NaClSexpIo *input,
1439 8 : int interactive,
1440 8 : int verbosity,
1441 8 : size_t epsilon_delay_nanos,
1442 8 : struct NaClFileLockTestInterface *test_if) {
1443 8 : struct WorkState ws;
1444 8 : struct NaClSexpNode *n;
1445 8 : struct NaClSexpNode *val;
1446 8 : int err;
1447 :
1448 8 : gInteractive = interactive;
1449 8 : gVerbosity = verbosity;
1450 8 : if (epsilon_delay_nanos < MIN_EPSILON_DELAY_NANOS) {
1451 0 : epsilon_delay_nanos = MIN_EPSILON_DELAY_NANOS;
1452 0 : }
1453 8 : gEpsilonDelayNanos = epsilon_delay_nanos;
1454 :
1455 8 : err = pthread_key_create(&gNaClTestTsdKey, (void (*)(void *)) NULL);
1456 24 : CHECK(0 == err);
1457 :
1458 8 : WorkStateCtor(&ws, test_if);
1459 :
1460 136 : while (NULL != (n = NaClSexpReadSexp(input))) {
1461 120 : if (gVerbosity > 1 && n->type == kNaClSexpCons) {
1462 0 : printf("Program list length: %"NACL_PRIdS"\n",
1463 0 : NaClSexpListLength(n->u.cval));
1464 0 : }
1465 :
1466 120 : if (gVerbosity) {
1467 0 : NaClSexpPrintNode(stdout, n);
1468 0 : printf(" => ");
1469 0 : }
1470 120 : val = Eval(n, &ws);
1471 120 : NaClSexpFreeNode(n);
1472 120 : NaClSexpPrintNode(stdout, val);
1473 120 : printf("\n");
1474 120 : NaClSexpFreeNode(val);
1475 120 : }
1476 8 : AnnounceEndOfWork(&ws);
1477 8 : ReapThreads(&ws);
1478 8 : WorkStateDtor(&ws);
1479 8 : }
|
