Brian Norris [Sat, 6 Apr 2013 01:42:16 +0000 (18:42 -0700)]
snapshot: cleanup/document much of fork-based snapshotting
We can consolidate much of the fork-based snapshotting "context"
variables so that they are easier to understand; we essentially only
need two types of contexts, the "shared" context used for the client
program (i.e., the model-checker) and the "private" context, which
each snapshot process uses for running and managing its state. That way,
we only have a single process using the "shared" context at a time,
while the others reside in their private context.
Additionally, I add an "exit" context, which is used just to help with
terminating processes once they have to roll back.
Otherwise, this commit contains renaming and documenting of several
fields, variables, etc.
Brian Norris [Fri, 5 Apr 2013 21:44:02 +0000 (14:44 -0700)]
snapshot: use sizeof(*fork_snap)
Brian Norris [Fri, 5 Apr 2013 21:17:42 +0000 (14:17 -0700)]
model: remove DEBUG action print
A ModelAction should only be printed at certain points, where the action
is guaranteed to be consistent (e.g., its reads_from pointer is valid).
Rather than try to position this print opportunely, just drop it; we
already print out the whole trace, which should be sufficient.
Brian Norris [Fri, 5 Apr 2013 21:02:58 +0000 (14:02 -0700)]
snapshot: clean up fork-based error handling
This is an ugly attempt at error handling. Kill the useless variables,
reword the debug prints, and use perror().
Brian Norris [Fri, 5 Apr 2013 21:01:33 +0000 (14:01 -0700)]
action: correct RF capitalization
Brian Norris [Thu, 4 Apr 2013 08:38:40 +0000 (01:38 -0700)]
model: deadlock: print the culprit thread, when known
Brian Norris [Thu, 4 Apr 2013 08:38:28 +0000 (01:38 -0700)]
datarace: use variable-argument bug-printing
Brian Norris [Thu, 4 Apr 2013 08:25:34 +0000 (01:25 -0700)]
model: add variable arguments for bug messages
Brian Norris [Thu, 4 Apr 2013 08:00:17 +0000 (01:00 -0700)]
model: proactively build/prune is_enabled() set
We should proactively check whether threads are enabled, as this allows
the model-checker to more accurately reason about backtracking, fairness
(particularly, assigning thread priorities), and sleep sets.
This commit causes changes in observed executions for many test
programs. Often, this occurs for programs where the main thread
performs a JOIN on a child thread. Previously, we would only discover
that this thread should be disabled once the scheduler attempts to
execute the JOIN ModelAction. For the period of the trace in which this
disabling isn't discovered, we may try to set backtracking points for
the main thread. These executions just turn into infeasible or
sleep-set-redundant executions anyway.
This can also affect the assertion of thread priority when assigning
backtracking points. If a thread is supposedly "enabled" (but in fact is
not), then we may prevent other threads from running because this thread has
priority. But that thread cannot run, so instead we were doing some
funky things with the remaining ("low-priority") threads.
This fix remedies these sorts of issues by precisely computing the set
of threads which are disabled, waiting on other threads/locks.
Brian Norris [Wed, 3 Apr 2013 16:44:07 +0000 (09:44 -0700)]
model: pull thread control logic out of take_step(), check_current...()
Much of the scheduling and main control loop should be handled closer to
the top-level run() method. This is a start toward putting these
decisions at the appropriate level, making things more clear. Of course,
it's not complete.
Brian Norris [Fri, 5 Apr 2013 17:27:18 +0000 (10:27 -0700)]
snapshot: kill useless macro
We're not reusing this macro, so it's better just to use the standard
perror() followed by exit().
Brian Norris [Thu, 4 Apr 2013 20:19:50 +0000 (13:19 -0700)]
context: move Mac swapcontext() to separate compilation unit
We really don't want model_swapcontext() to ever be inlined on Mac OSX,
since this could potentially cause subtle getcontext()-related bugs to
resurface. Just make it a separate compilation unit (*.cc file).
Brian Norris [Thu, 4 Apr 2013 19:55:33 +0000 (12:55 -0700)]
common: improve redirect_output() error handling
Check the return code and errno results of all system/library calls.
Also delete the extraneous 'fd' variable and use the appropriate
STDOUT_FILENO macro instead of fileno(stdout).
Brian Norris [Thu, 4 Apr 2013 19:46:13 +0000 (12:46 -0700)]
common: make model_print() use OS file descriptor, not C library FILE*
A C library FILE does buffering (and possibly other opaque operations)
that can conflict with the model-checker's methods of snapshotting
memory. Particularly, it seems like we could corrupt and drop data that
was written to model_out, if the data was large enough and buffered in
just the right way.
Really, with the presence of dprintf(), there is no reason to print to a
FILE stream; we can just use the file descriptor (either STDOUT_FILENO
or the descriptor received from dup2()).
This fixes bugs seen in verbose mode, with a lot of extra debug
printing. Some of the output was being dropped.
Brian Norris [Thu, 4 Apr 2013 17:10:32 +0000 (10:10 -0700)]
action: include reads-from-promise in HASH calculations
And include the *value*, since the same promise index can yield
different future values.
Brian Norris [Thu, 4 Apr 2013 07:16:46 +0000 (00:16 -0700)]
test: insanesync: pointer types
Atomic pointers should be stored in atomic_intptr_t/atomic_uintptr_t.
This can throw some extra warnings on 32-bit architectures.
Brian Norris [Thu, 4 Apr 2013 00:55:49 +0000 (17:55 -0700)]
model: note the DPOR addendum
To prevent having problems with this in the future.
Brian Norris [Wed, 3 Apr 2013 16:08:44 +0000 (09:08 -0700)]
model: use get_thread() helper
Brian Norris [Thu, 4 Apr 2013 02:27:06 +0000 (19:27 -0700)]
swapcontext() fix for Mac OSX
We provide our own model_swapcontext() for Mac OSX.
Brian Norris [Wed, 3 Apr 2013 01:11:49 +0000 (18:11 -0700)]
threads: remove wait_list
We can glean the "thread waiting" information without recording it
directly in a list for each thread.
Brian Norris [Wed, 3 Apr 2013 00:52:12 +0000 (17:52 -0700)]
model: use get_mutex() and get_thread_operand() helpers
Brian Norris [Wed, 3 Apr 2013 00:48:59 +0000 (17:48 -0700)]
model: kill lock_waiters_map
This information can be gleaned without the need for a hash-table of
lists.
Brian Norris [Wed, 3 Apr 2013 00:45:24 +0000 (17:45 -0700)]
model: merge duplicated code for WAIT and UNLOCK
Brian Norris [Wed, 3 Apr 2013 00:28:59 +0000 (17:28 -0700)]
test: mutextest: add thread yield point
Brian Norris [Wed, 3 Apr 2013 00:25:04 +0000 (17:25 -0700)]
model: get_mutex() for locating the lock map
The mutex can already be located via get_mutex(), so don't try to guess
whether it was store in the value or location fields of the ModelAction.
Brian Norris [Tue, 2 Apr 2013 23:53:52 +0000 (16:53 -0700)]
action: add ModelAction::is_thread_join() helper
Brian Norris [Tue, 2 Apr 2013 23:00:30 +0000 (16:00 -0700)]
mymemory: fix compiling with !USE_MPROTECT_SNAPSHOT
Brian Norris [Thu, 28 Mar 2013 22:27:17 +0000 (15:27 -0700)]
nodestack: move "behaviors" increment all into Node wrapper function
Brian Norris [Thu, 28 Mar 2013 22:21:00 +0000 (15:21 -0700)]
nodestack: regroup some code
To put "threads backtracking" code together
Brian Norris [Wed, 27 Mar 2013 20:03:43 +0000 (13:03 -0700)]
threads: move circular wait check into Threads::is_waiting_on
A Threads::is_waiting_on(Thread *) interface provides a more generic
interface, which can be useful for tasks other than just circular wait
deadlock detection.
Brian Demsky [Fri, 22 Mar 2013 23:31:47 +0000 (16:31 -0700)]
correct comment typo
Brian Demsky [Fri, 22 Mar 2013 23:27:37 +0000 (16:27 -0700)]
check in insane test case...
We don't support such behavior.
Brian Demsky [Fri, 22 Mar 2013 07:06:51 +0000 (00:06 -0700)]
fix mistake in promises may allow code... need to be even more aggressive about fv
Brian Norris [Fri, 22 Mar 2013 06:24:15 +0000 (23:24 -0700)]
main: adjust defaults again
-s 6 -S 4
Brian Norris [Fri, 22 Mar 2013 01:07:18 +0000 (18:07 -0700)]
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
Brian Norris [Fri, 22 Mar 2013 01:05:04 +0000 (18:05 -0700)]
main: change default 'future delay' for promise expiration
From 100 to 10, since 100 is kind of absurd, given the current program
length scalability.
Brian Norris [Thu, 21 Mar 2013 23:48:57 +0000 (16:48 -0700)]
model: re-check pending future values whenever a promise is resolved
This is the second part of the previous bugfix; now we must also allow
stashed pending future values to be re-checked in case a promise has
been resolved which now allows sending the value.
Brian Norris [Thu, 21 Mar 2013 23:33:04 +0000 (16:33 -0700)]
model: bugfix - send future values more eagerly
This is a bugfix to a pretty big problem with our future value pruning,
where we would hold future values as 'pending' until all pending
promises were resolved. Unfortunately, this is unsound and must be
rewritten.
Now, we allow sending some future values even in presence of promises,
if the value is being sent to a load that is later than the last time a
Promise was created. We have a pseudo-proof that this should be correct.
Brian Norris [Thu, 21 Mar 2013 23:24:47 +0000 (16:24 -0700)]
model: refactor add_future_value, add documentation
Brian Norris [Thu, 21 Mar 2013 23:17:16 +0000 (16:17 -0700)]
model: add 'const'
Brian Norris [Thu, 21 Mar 2013 23:01:23 +0000 (16:01 -0700)]
model: rename PendingFutureValue 'act' to 'reader'
To make it more clear
Brian Norris [Thu, 21 Mar 2013 22:31:34 +0000 (15:31 -0700)]
model: rework the resolve-promise interface
We don't need to pass around the promise index; just pass the Promise
pointer around.
Brian Demsky [Thu, 21 Mar 2013 22:18:30 +0000 (15:18 -0700)]
add test case...
Brian Norris [Wed, 20 Mar 2013 20:44:24 +0000 (13:44 -0700)]
cyclegraph: propagate RMW atomicity edges down the chain
When we add an edge between 'rmwnode' and 'tonode', we are trying to
ensure RMW atomicity. But 'rmwnode' may itself be read by another RMW
(or, in fact, a chain). So we must follow this chain down before
propagating the atomicity edge.
Also, we have the potential to run into the same problem in
addRMWEdge(), except that in that function, we assume that the RMW is
newly-explored and so does not yet have an outgoing RMW edge. This adds
an ASSERT() to check this property.
Brian Norris [Tue, 19 Mar 2013 02:23:21 +0000 (19:23 -0700)]
model: note how we support seq-cst fences
Brian Demsky [Tue, 19 Mar 2013 00:25:19 +0000 (17:25 -0700)]
add our names
Brian Demsky [Tue, 19 Mar 2013 00:24:27 +0000 (17:24 -0700)]
add copyright message
Brian Demsky [Mon, 18 Mar 2013 23:46:31 +0000 (16:46 -0700)]
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
Brian Demsky [Mon, 18 Mar 2013 23:46:02 +0000 (16:46 -0700)]
update git repository with license... GPL v2
Brian Norris [Fri, 15 Mar 2013 19:03:14 +0000 (12:03 -0700)]
test: rmwprog: add MODEL_ASSERT
Might as well improve this 'litmus' test.
Brian Demsky [Thu, 14 Mar 2013 22:39:14 +0000 (15:39 -0700)]
fix memory leak
when we reuse nodes in the nodestack, we will recreate yield information and leak the old array...
Brian Norris [Tue, 12 Mar 2013 17:47:41 +0000 (10:47 -0700)]
model: bugfix - missing SC mo_graph edge
We must enforce a rule such as the following, derived from C++ Section
29.3, statement 3 (second subpoint):
if is_store(X) && is_seq_cst(X) && is_store(Y) && is_load(Z) &&
is_seq_cst(Z) &&
X --sc-> Z && Y --rf-> Z && X != Y
then
X --mo-> Y
This has been checked (via manual test-case) to fix a bug which allowed
an inconsistent mo/sc/rf relationship.
Brian Norris [Mon, 11 Mar 2013 23:54:10 +0000 (16:54 -0700)]
model: refactor r_modification_order 'act != curr' and 'act != rf'
We never want to process 'curr' or 'rf' in r_modification_order, so just
factor this out to the beginning of the loop to save on code clutter
(and potential bugs).
Brian Norris [Sat, 9 Mar 2013 20:54:58 +0000 (12:54 -0800)]
mymemory: enforce that user allocations come from user context
Brian Norris [Sat, 9 Mar 2013 20:51:36 +0000 (12:51 -0800)]
mymemory, threads: add allocator specifically for Thread
clas Thread is a special exception, where user-space allocations should
happend from the model-checker context. So provide a special set of
functions to specifically differentiate these allocations.
Brian Norris [Sat, 9 Mar 2013 20:24:06 +0000 (12:24 -0800)]
model: privatize some thread functions
We never need to call ModelChecker::add_thread from outside
ModelChecker.
We really shouldn't try to call 'remove_thread' from the Thread
destructor. It's unnecessary.
Brian Norris [Sat, 9 Mar 2013 01:25:24 +0000 (17:25 -0800)]
litmus: wrc: add macro for memory ordering
For manual inspection of these tests, one might want to change the
memory-ordering for the loads/stores.
Note that this changes the default to use relaxed.
Brian Norris [Sat, 9 Mar 2013 00:50:51 +0000 (16:50 -0800)]
litmus: seq-lock: add MODEL_ASSERT() for the important behavior
Brian Norris [Fri, 8 Mar 2013 23:59:46 +0000 (15:59 -0800)]
model-assert: include <stdbool.h>
'bool' is not a built-in type in C. Include the (C99) <stdbool.h>
library.
Brian Norris [Fri, 8 Mar 2013 20:35:42 +0000 (12:35 -0800)]
stl - remove stale <vector> and <list> #include's
Brian Norris [Thu, 7 Mar 2013 22:56:51 +0000 (14:56 -0800)]
bugfix - add stl-model.h wrappers, to provide more control over STL
We need to provide an operator new/delete for our std::vector and
std::list instantiations. So we extend the base classes and add the
appropriate new/delete methods.
Brian Norris [Thu, 7 Mar 2013 22:56:22 +0000 (14:56 -0800)]
Revert "switch to snapshot/modelalloc versions of stl classes"
This reverts commit
7524803854c2de38c0311fe5037e3c17105ccfaa.
It was missing a lot of conversions, and I did duplicate work. So I'll
just check in my changes instead.
Brian Demsky [Thu, 7 Mar 2013 22:49:20 +0000 (14:49 -0800)]
switch to snapshot/modelalloc versions of stl classes
Brian Demsky [Thu, 7 Mar 2013 03:17:58 +0000 (19:17 -0800)]
add new option for uninitialized writes...
Brian Norris [Thu, 7 Mar 2013 02:40:34 +0000 (18:40 -0800)]
model, nodestack: bugfix - retain UNINIT actions across executions
Previously, we were allocating UNINIT actions as snapshotting memory,
just for ease of use. But because they may not immediately trigger a bug
(if they are a valid read-from), such actions must have a longer
lifetime - in fact, a lifetime similar to normal ModelActions.
So, we stash them in NodeStack alongside normal actions.
Also, improve a few ASSERT()'s and clarify a push_front() vs.
push_back() (the list is empty, so it doesn't matter; but it follows the
style of the rest of the lists to use push_front() here).
Brian Norris [Wed, 6 Mar 2013 07:05:25 +0000 (23:05 -0800)]
linuxrwlocksyield: refactor
Brian Demsky [Wed, 6 Mar 2013 05:58:33 +0000 (21:58 -0800)]
documentation update
Brian Demsky [Wed, 6 Mar 2013 05:41:09 +0000 (21:41 -0800)]
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
Brian Demsky [Wed, 6 Mar 2013 05:40:39 +0000 (21:40 -0800)]
add destructor so the spsc-queue will compile on MAC
Brian Norris [Wed, 6 Mar 2013 03:04:57 +0000 (19:04 -0800)]
Merge remote 'yield' work
Brian Norris [Wed, 6 Mar 2013 02:36:58 +0000 (18:36 -0800)]
model: don't print 'uninitialized' ModelActions in trace output
If we proliferate a large number of atomic objects, we can generate a
lot of fake 'uninitialized' ModelActions. Don't print these in traces,
as it just clutters the output.
Brian Demsky [Wed, 6 Mar 2013 02:35:27 +0000 (18:35 -0800)]
add yield support
Brian Norris [Wed, 6 Mar 2013 02:33:43 +0000 (18:33 -0800)]
impatomic: fences linker error
Because these functions were declared in a header (but not static), they
could get linked into multiple object files, causing linker errors. For
now, just make them 'static inline'. I'm not sure if that exactly fits
the spec, but it's close enough for now.
Brian Norris [Tue, 5 Mar 2013 03:51:49 +0000 (19:51 -0800)]
Makefile: use $+ variable
Brian Norris [Tue, 5 Mar 2013 01:50:08 +0000 (17:50 -0800)]
cyclegraph: memory "leak", fixup
An insignificant memory leak.
Brian Demsky [Tue, 5 Mar 2013 01:23:48 +0000 (17:23 -0800)]
little optimizations motivated by profiling...
1. reduce allocations of vectors for queues
2. reduce calls to checkReachable
Brian Norris [Tue, 5 Mar 2013 00:32:16 +0000 (16:32 -0800)]
model: refactor the get_thread() selection
get_thread() may or may not be called with a non-NULL 'curr' argument,
and if it non-NULL, it still may not be used. Make the logic cleaner by
pulling the 'curr'-specific functionality out to its own function.
Brian Norris [Mon, 4 Mar 2013 05:08:38 +0000 (21:08 -0800)]
refactor DBG_ENABLED() vs. verbose
Always set 'verbose' when we are compiling a DEBUG build.
Brian Norris [Mon, 4 Mar 2013 04:34:26 +0000 (20:34 -0800)]
model: add promise printing to execution summaries
Brian Norris [Mon, 4 Mar 2013 03:50:47 +0000 (19:50 -0800)]
nodestack: print thread status info in Node::print
It's useful to have sleep-set information for debugging.
Brian Norris [Mon, 4 Mar 2013 00:58:12 +0000 (16:58 -0800)]
cyclegraph: missing form of checkReachable()
I don't know how this managed to link previously.
Brian Norris [Sun, 3 Mar 2013 22:12:31 +0000 (14:12 -0800)]
model: rename check_deadlock() to is_circular_wait()
This method doesn't check all deadlock situations, just circular waits.
Brian Norris [Sun, 3 Mar 2013 07:53:58 +0000 (23:53 -0800)]
model: add improved (?) deadlock detection
This proactively detects cyclic waits in threads, using join or lock
information. It does not account for wait yet, but that is covered by
is_deadlocked(), at least in some cases.
Brian Norris [Sun, 3 Mar 2013 07:53:29 +0000 (23:53 -0800)]
threads: add waiting_on()
For use with deadlock detection
Brian Norris [Sun, 3 Mar 2013 07:37:05 +0000 (23:37 -0800)]
mutex: change 'islocked' to hold Thread pointer
We will need to know which Thread is holding the lock, so just stick it
in the mutex state.
Brian Norris [Sun, 3 Mar 2013 07:24:51 +0000 (23:24 -0800)]
action: add get_mutex()
Brian Norris [Sun, 3 Mar 2013 06:55:51 +0000 (22:55 -0800)]
mutex: fix indentation
Brian Norris [Sat, 2 Mar 2013 23:13:42 +0000 (15:13 -0800)]
action: add get_return_value()
This return value is useful for both printing (debugging) and the
model-checker process_read() function.
Brian Norris [Sat, 2 Mar 2013 23:05:44 +0000 (15:05 -0800)]
model: use get_write_value()
Same implementation for now, but it could change.
Brian Norris [Sat, 2 Mar 2013 23:03:58 +0000 (15:03 -0800)]
model: bugfix - adding a Promise reader can cause failure
Brian Norris [Sat, 2 Mar 2013 22:49:00 +0000 (14:49 -0800)]
model: hack dumpGraph() bug by "leaking" promises
It is possible to end up in an inconsistent state, where a "resolved"
promise may still be referenced if CycleGraph::resolvePromise() failed,
so don't delete 'promise'. Technically, this leaks memory within an
execution, but because it is allocated on the snapshotting heap, this
leak goes away after an execution ends. So, rather than spending more
work on "fixing" the inconsistency, just don't delete the promise yet.
This inconsistency only matters when dumping the mo_graph to file, since
it traverses all the ModelAction/Promise edges, including those that are
semi-dangling mid-merge.
Brian Norris [Sat, 2 Mar 2013 22:17:19 +0000 (14:17 -0800)]
cyclegraph: simplify resolvePromise / mergeNodes
We only ever will merge a single Promise node with a single ModelAction
node. Any other nodes will just create cycles or unresolveable promises.
So we can simplify much of the logic and avoid passing around a vector
of Promises.
Brian Norris [Sat, 2 Mar 2013 22:04:08 +0000 (14:04 -0800)]
model: refactor process_read logic
Brian Norris [Sat, 2 Mar 2013 20:28:26 +0000 (12:28 -0800)]
check_recency: update/add documentation comments
Brian Norris [Sat, 2 Mar 2013 20:17:02 +0000 (12:17 -0800)]
check_recency: improve templates, use when reading from Promise
This completes (?) the improvements to check_recency, such that it now
can force new writes to be "seen" if we are reading from an "old"
Promise too many times in a row.
mpmc-queue-noinit now runs to completion (with ASSERT() enabled):
$ time ./run.sh mpmc-queue/mpmc-queue-noinit -f 10 -m 2
+ mpmc-queue/mpmc-queue-noinit -f 10 -m 2
******* Model-checking complete: *******
Number of complete, bug-free executions: 119828
Number of redundant executions: 38743
Number of buggy executions: 0
Number of infeasible executions: 344469
Total executions: 503040
Total nodes created:
7585797
real 2m29.674s
user 2m18.269s
sys 0m10.929s
Brian Norris [Sat, 2 Mar 2013 09:02:29 +0000 (01:02 -0800)]
check_recency: refactor some more, + include Promises
check_recency *should* now prevent reading from the same Promise too
many times. Not quite getting the test results I want yet, though.
Brian Norris [Sat, 2 Mar 2013 08:26:51 +0000 (00:26 -0800)]
check_recency: return a boolean status
The output of check_recency is actually a boolean (failure => "too many
reads"), so make that explicit.
Also, rework a little more logic to make the structure a little more
obvious.
Brian Norris [Sat, 2 Mar 2013 08:04:44 +0000 (00:04 -0800)]
check_recency: only allow newer stores to "overwrite"
For a "live" memory system, we only want to force a store to appear if
it is modification-ordered after the store we're reading from.
Also, delete my old comment about reads-from feasibility.
Brian Norris [Sat, 2 Mar 2013 03:25:29 +0000 (19:25 -0800)]
check_recency: implement loops as function ModelAction::may_read_from()
This strange loop makes more sense with a name, associated with the
ModelAction class.
Brian Norris [Sat, 2 Mar 2013 03:06:30 +0000 (19:06 -0800)]
nodestack: add support functions for check_recency() w/ Promises