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
Brian Norris [Sat, 2 Mar 2013 02:49:29 +0000 (18:49 -0800)]
model: check_recency: convert a few things to ASSERT()
At least for now, just to make sure my reasoning is correct.
Brian Demsky [Sat, 2 Mar 2013 02:34:07 +0000 (18:34 -0800)]
comments
Brian Norris [Sat, 2 Mar 2013 02:00:14 +0000 (18:00 -0800)]
model: check_recency: fix indentation, spelling, comments
Brian Norris [Sat, 2 Mar 2013 00:45:52 +0000 (16:45 -0800)]
action: bugfix - reads-from value should be VALUE_NONE for new actions
If a new read action hasn't had a chance to choose a valid reads-from or
reads-from-promise, it can have "no" value. This only occurs if we are
terminating an infeasible execution, where there were no valid reads to
read from.
This bug was triggering faults only for verbose printing, were we would
print the status of an incomplete read.
Brian Norris [Sat, 2 Mar 2013 00:19:10 +0000 (16:19 -0800)]
model: fixes for future value passing
For one, we don't want to 'add_future_value()' when w_modification_order
is called anywhere besides process_write(). Also, we want to filter out
potential future values based on the existence of a Promise that this
write must resolve. So pass a vector parameter to w_modification_order
for recording future values only when (and where) we want them.
Brian Norris [Sat, 2 Mar 2013 00:13:25 +0000 (16:13 -0800)]
model: we only resolve one promise at a time
Brian Norris [Fri, 1 Mar 2013 23:01:47 +0000 (15:01 -0800)]
model: fix ASSERT()
Apparently this ASSERT() is still not good. ASSERT() was triggered, for
example, with:
$ ./run.sh test/linuxrwlocks.o -f 4 -m 1
Brian Norris [Fri, 1 Mar 2013 21:11:27 +0000 (13:11 -0800)]
promise: add 'same_value' helper, force value-checking in CycleGraph
This fixes a potential bug, in which a write could merge with a
different promised value. It's unclear whether this ever manifested
itself, since I believe we had some implicit logic that would ensure
that this did not happen.
Brian Norris [Fri, 1 Mar 2013 21:07:56 +0000 (13:07 -0800)]
promise: bugfix - don't check value, check location
I changed a line previously and didn't even notice that I wasn't
matching the comment anymore! Of course, the comment was correct, and my
code was wrong.
Brian Norris [Fri, 1 Mar 2013 20:32:13 +0000 (12:32 -0800)]
action: add get_write_value()
Brian Norris [Fri, 1 Mar 2013 20:30:41 +0000 (12:30 -0800)]
action: add ModelAction::get_reads_from_value()
We can always get our 'read' value from reads_from or
reads_from_promise, so make it accessible via a function.
Brian Norris [Fri, 1 Mar 2013 07:51:55 +0000 (23:51 -0800)]
action, model: add ASSERT(), not NULL checks
These should never be called with NULL. Don't make them a real
conditional.
Brian Norris [Fri, 1 Mar 2013 07:24:20 +0000 (23:24 -0800)]
cyclegraph/model: unify, clean up graph printing
This fixes several things:
1) The rf edges now are directed properly
2) Read-from-promises show up in the graph
3) ModelChecker uses the same code as CycleGraph for printing a
CycleNode or graph edge
4) Graphs are more readable; I put a large weight on the
sequenced-before edges, causing graphviz to try to make these edges
"shorter, straighter and more vertical" [1]
5) Use the 'SnapshotAlloc' STL allocator for CycleGraph::nodeList
[1] http://www.graphviz.org/doc/info/attrs.html#d:weight
Brian Norris [Fri, 1 Mar 2013 06:46:25 +0000 (22:46 -0800)]
nodestack: get_read_from_promise() never returns NULL
If the read_from_promise_idx is out of bounds, this is an error. We
should not return NULL (and in fact, our caller never expects us to
return NULL).
Brian Norris [Thu, 28 Feb 2013 20:23:51 +0000 (12:23 -0800)]
model/schedule: comput "reduadant" measurement, print along with traces
This will help debuggability. For instance, it will be more obvious that
right now, the 'deadlock.c' test is completing executions as "redundant"
when in fact they should be deadlocks.
Brian Norris [Thu, 28 Feb 2013 19:42:30 +0000 (11:42 -0800)]
cyclegraph: clean up mo_graph dump
Promises should show up with their promise number (or promise "index").
We can also make the edge printing into a generic function.
Brian Norris [Thu, 28 Feb 2013 19:17:42 +0000 (11:17 -0800)]
action: print promise number, not just ?
Brian Norris [Thu, 28 Feb 2013 18:30:39 +0000 (10:30 -0800)]
nodestack: bugfix - clear backtracking properly
Brian Norris [Wed, 27 Feb 2013 23:13:17 +0000 (15:13 -0800)]
promise: record multiple readers in the same Promise
This requires more adjustments throughout ModelChecker.
Brian Norris [Wed, 27 Feb 2013 22:45:11 +0000 (14:45 -0800)]
un-'const' some Promises
I need to modify this Promise sometimes, so don't make it const
everywhere.
Brian Norris [Wed, 27 Feb 2013 02:42:51 +0000 (18:42 -0800)]
nodestack: rewrite promise-resolution "counting"
We don't need to perform a full check of all possible combinations of
Promises to resolve; we only perform 0 or 1 resolution.
Brian Norris [Wed, 27 Feb 2013 00:15:50 +0000 (16:15 -0800)]
model: hook up 'read-from-promise' backtracking in ModelChecker
Now we iterate over the read-from-promise set. Some things are still
missing.
Brian Norris [Tue, 26 Feb 2013 19:13:10 +0000 (11:13 -0800)]
nodestack: add read_from_promises backtracking
This is just the basic framework for now. I still need to hook it up for
actual use in ModelChecker.
Brian Norris [Thu, 28 Feb 2013 02:48:46 +0000 (18:48 -0800)]
nodestack: bugfix - rewrite 'may-read-from' and 'future values' as the same set
There were some subtle bugs that appeared because of the difficulty in
iterating over two separate sets that represent the "read from" set for
a particular read. Now, we expose an interface where there's just a
single pair of functions 'increment_read_from()' and
'read_from_empty()', for iterating over this set, along with a
flag-check 'get_read_from_status()', so that we know where to grab
values from (get_read_from_past() or get_future_value()).
This also does a lot of code moving and documentation in nodestack.cc,
for better readability and organization.
Brian Norris [Thu, 28 Feb 2013 01:54:45 +0000 (17:54 -0800)]
model: shorten some code
Brian Norris [Thu, 28 Feb 2013 01:48:48 +0000 (17:48 -0800)]
model: rename 'reads_from' to 'rf'
Brian Norris [Thu, 28 Feb 2013 01:30:24 +0000 (17:30 -0800)]
nodestack: rename 'read_from' to 'read_from_past'
One step of re-architecting the reads-from set in NodeStack (i.e.,
read from past + promised future values + future values).
Brian Norris [Thu, 28 Feb 2013 00:36:24 +0000 (16:36 -0800)]
model: don't call process_read() for 2nd half of RMW/RMWC
We don't need to call process_read() for the second half of an RMW or
RMWC ModelAction. Anyway, it does next-to-nothing when
'second_part_of_rmw' is true.
Brian Norris [Wed, 27 Feb 2013 23:42:17 +0000 (15:42 -0800)]
model: bugfix - correct the "equality" check for RR coherence
I made a typo when adding this RR coherence edge.
Brian Norris [Wed, 27 Feb 2013 23:43:21 +0000 (15:43 -0800)]
cyclegraph: bugfix - allow to compile with SUPPORT_MOD_ORDER_DUMP
I missed an include that is only used for the mod-order dump support
code.
Brian Norris [Wed, 27 Feb 2013 00:39:09 +0000 (16:39 -0800)]
model: bugfix - correct RR coherence for Promises
We should not skip a read just because it has an unresolved promises;
the CycleGraph can now support read-read coherence edges between any
combination of Promise and ModelAction.
Brian Norris [Tue, 26 Feb 2013 23:59:00 +0000 (15:59 -0800)]
cyclegraph: change Promise nodes map
Map from Promises to Nodes, not ModelAction (readers) to Nodes. This
will make it cleaner when more than one reader maps to the same promise
Node.
Brian Norris [Tue, 26 Feb 2013 01:04:13 +0000 (17:04 -0800)]
model: promises: eliminate threads when they "join"
A thread that joins with another thread can no longer satisfy a promise
from that thread.
Brian Norris [Tue, 26 Feb 2013 00:23:05 +0000 (16:23 -0800)]
schedule: remove commented-out code
Brian Norris [Tue, 26 Feb 2013 00:11:54 +0000 (16:11 -0800)]
model: bugfix - only allow promise satisfaction for "compatible" threads
I overlooked updating the 'compute_promises()' function when modifying
promises such that they are only resolved by a limited set of threads.
This allows compute_promises() to properly prune out those promises
which are not satisfiable by the current thread.
At the same time, move the act->is_read() check to be an ASSERT(), since
we should never see a promise generated by a non-read ModelAction.
Brian Norris [Mon, 25 Feb 2013 23:15:28 +0000 (15:15 -0800)]
threads: construct Thread only with a given "parent"
The Thread constructor really doesn't need to call thread_current(),
since it will always be called from model-checker context. Clean up the
use of default "parent_thrd" parameter and just pass NULL when we have
no parent.
Brian Demsky [Mon, 25 Feb 2013 07:28:21 +0000 (23:28 -0800)]
repush changes
Brian Demsky [Mon, 25 Feb 2013 07:25:59 +0000 (23:25 -0800)]
fix conflicts
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
Conflicts:
schedule.cc
Brian Demsky [Mon, 25 Feb 2013 07:24:50 +0000 (23:24 -0800)]
fix norris mentioned bug
Brian Norris [Mon, 25 Feb 2013 05:38:21 +0000 (21:38 -0800)]
Revert "fix scheduling stuff to get nice round robin scheduler behavior..."
This reverts commit
30999f20b8426081e676adfc76d1c4af7b941e8e.
This commit triggers assertions and therefore cannot be used:
$ ./run.sh test/rmwprog.o
+ test/rmwprog.o
Error: assertion failed in model.cc at line 2424
stack trace:
./libmodel.so : ModelChecker::resolve_promises(ModelAction*)+0x3bd
./libmodel.so : ModelChecker::process_write(ModelAction*)+0x21
./libmodel.so : ModelChecker::check_current_action(ModelAction*)+0x42b
./libmodel.so : ModelChecker::take_step(ModelAction*)+0x39
./libmodel.so : ModelChecker::run()+0xa5
./libmodel.so : ()+0x1a3a3
./libmodel.so : ()+0x1e786
./libmodel.so : main()+0x3c
/lib/x86_64-linux-gnu/libc.so.6 : __libc_start_main()+0xed
test/rmwprog.o() [0x400789]
Execution 11: INFEASIBLE: [unresolved promise]
---------------------------------------------------------------------
( 0) Thread: 0 Action: uninitialized MO: relaxed Loc: 0x601078 Value: 0 CV: ( 0, 0)
( 1) Thread: 1 Action: thread start MO: seq_cst Loc: 0x7f6cd2016898 Value: 0xdeadbeef CV: ( 0, 1)
( 2) Thread: 1 Action: init atomic MO: relaxed Loc: 0x601078 Value: 0 CV: ( 0, 2)
( 3) Thread: 1 Action: thread create MO: seq_cst Loc: 0x7f6cd1410590 Value: 0x7f6cd1410560 CV: ( 0, 3)
( 4) Thread: 2 Action: thread start MO: seq_cst Loc: 0x7f6cd2016e08 Value: 0xdeadbeef CV: ( 0, 3, 4)
( 5) Thread: 2 Action: atomic rmw MO: relaxed Loc: 0x601078 Value: 0x1 Rf: 9 CV: ( 0, 3, 5)
( 6) Thread: 1 Action: thread create MO: seq_cst Loc: 0x7f6cd14105a0 Value: 0x7f6cd1410560 CV: ( 0, 6, 0)
( 7) Thread: 3 Action: thread start MO: seq_cst Loc: 0x7f6cd2017338 Value: 0xdeadbeef CV: ( 0, 6, 0, 7)
( 8) Thread: 2 Action: atomic rmw MO: relaxed Loc: 0x601078 Value: 0x2 Rf: 5 CV: ( 0, 3, 8, 0)
( 9) Thread: 3 Action: atomic rmw MO: relaxed Loc: 0x601078 Value: 0 Rf: 2 CV: ( 0, 6, 0, 9)
HASH
1973598524
---------------------------------------------------------------------
Add breakpoint to line 50 in file common.cc.
Brian Demsky [Mon, 25 Feb 2013 04:59:46 +0000 (20:59 -0800)]
fix scheduling stuff to get nice round robin scheduler behavior...
Brian Norris [Sat, 23 Feb 2013 03:01:13 +0000 (19:01 -0800)]
nodestack: bugfix - reset backtracking points on diverging paths
Any time we diverge to a new execution path, we should reset the
backtracking information (i.e., which threads have executed and which
still must be backtracked) for the last node in the stack. We cannot
retain the "explored children" state after we have performed different
read-from or future-value divergence in the same node.
Brian Norris [Sat, 23 Feb 2013 00:39:54 +0000 (16:39 -0800)]
model: bugfix - inherit future values from previous loads
Once a future value is observed once, it should be available for
observation by other loads. Previously, we assume that a future value
will be passed to each load that may observe it. However, as
exemplified in the double-read-fv.c test, this may not be possible when
there are no other feasible stores from which to read.
Thus, when building an initial 'may-read-from' set, we should build a
set of inherited future values as well.
Brian Norris [Sat, 23 Feb 2013 00:34:37 +0000 (16:34 -0800)]
nodestack: don't use C++ references
Just pass-by-value, since the reference can obfuscate the lifetime of,
for example, an automatic variable.
Brian Norris [Sat, 23 Feb 2013 00:12:34 +0000 (16:12 -0800)]
model: correct the "no valid reads" assertion
There are "no valid reads" only if there are no valid prior reads-from
candidates AND no potential values.
Brian Norris [Sat, 23 Feb 2013 00:04:51 +0000 (16:04 -0800)]
promise: stash the whole future_value
We may need to generate a new Promise from the same future_value, so
stash the whole struct and expose it via get_fv().
Brian Norris [Fri, 22 Feb 2013 07:18:18 +0000 (23:18 -0800)]
test: fences: add simple, semi-useful fence tests
Note that due to the quirks discovered in double-read-fv, we don't see
all the expected behaviors in the fences2 test.
Brian Norris [Fri, 22 Feb 2013 07:17:21 +0000 (23:17 -0800)]
test: add double-read-fv
This test fails (!) because we never see r1 = r2 = 42.
Brian Norris [Fri, 22 Feb 2013 17:42:00 +0000 (09:42 -0800)]
action: backtrack/sleep-sets for seq-cst fences
We now backtrack (and wake up sleep-set actions) on all pairs of seq-cst
operations such that at least one of the operations is a write or fence.
Brian Norris [Fri, 22 Feb 2013 07:07:55 +0000 (23:07 -0800)]
model: wake up pending (sleep-set) actions for fences
This completes fence backtracking properly by waking up actions when the
appropriate fence interactions occur. This is a little more complicated
than the simple "could_synchronize()" test, since fence synchronization
can involve interaction of more than two actions.
So, pull the complexity of the "should we wake a thread up" computation
into its own function.
Brian Norris [Thu, 21 Feb 2013 19:59:50 +0000 (11:59 -0800)]
model: only backtrack fences when acquire is before release
Because there are up to 4 actions involved in this search for a
"conflict" (load, fence-acquire, fence-release, store), I overlooked the
fact that we only need to backtrack when the release comes after acquire
in the execution order. This fix skips past the 'release' action before
we begin searching for the 'acquire'.