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'.
Brian Norris [Wed, 20 Feb 2013 22:58:21 +0000 (14:58 -0800)]
model: document get_last{,_fence}_conflict()
Brian Norris [Wed, 20 Feb 2013 02:28:41 +0000 (18:28 -0800)]
model: schedule appropriate fence backtracking points
This patch calculates the most recent backtracking point which may be a
fence. We require a separate function for computing this because a fence
"conflict" is much different than other conflicts; fences do not have a
memory location, but instead, they trigger release/acquire backtracking
in the presence of other stores/loads.
Left out of this patch:
(1) Sleep-set waking: even if we backtrack, we don't yet wake up our
thread properly, yielding a "redundant" trace instead of a
productive one
(2) memory_order_seq_cst: I have yet to determine how (if at all) we
need to add additional backtracking in the presence of seq_cst
fences
(3) documentation: need to describe get_last_fence_conflict() better
Brian Norris [Thu, 21 Feb 2013 00:27:45 +0000 (16:27 -0800)]
model: convert while-loops to for-loops
Make the loop-termination condition more clear.
Brian Norris [Wed, 20 Feb 2013 02:03:56 +0000 (18:03 -0800)]
model: add 'const'
Brian Norris [Wed, 20 Feb 2013 23:03:24 +0000 (15:03 -0800)]
include: fixup header inclusion
Brian Norris [Wed, 20 Feb 2013 07:37:12 +0000 (23:37 -0800)]
don't include action.h from model.h
Brian Norris [Wed, 20 Feb 2013 07:30:31 +0000 (23:30 -0800)]
model/action: move action_list_t to model.h
action_list_t is only used by the ModelChecker class
Brian Norris [Wed, 20 Feb 2013 07:29:42 +0000 (23:29 -0800)]
promise: move constructor out of header
Brian Norris [Sat, 16 Feb 2013 02:22:49 +0000 (18:22 -0800)]
scheduler: refactor round-robin loop
This is the same computation, represented more clearly as a for loop
which, if it reaches the completion condition, means that it did not
find an enabled thread.
Brian Norris [Sat, 16 Feb 2013 02:09:03 +0000 (18:09 -0800)]
model: end-of-execution print
For readability of a "verbose" execution log (and even for the shorter,
non-verbose log), it helps to visually separate the final statistics
from any previously-printed statistics. For instance, in the following
verbose snippet from the end of an execution history, it's confusing why
there are two identical copies of the statistics:
... <other execution history> ...
Number of complete, bug-free executions: 4
Number of redundant executions: 0
Number of buggy executions: 0
Number of infeasible executions: 5
Total executions: 9
Total nodes created: 48
Execution 9:
---------------------------------------------------------------------
... <snipped trace info> ...
---------------------------------------------------------------------
Number of complete, bug-free executions: 4
Number of redundant executions: 0
Number of buggy executions: 0
Number of infeasible executions: 5
Total executions: 9
Total nodes created: 48
Brian Norris [Sat, 16 Feb 2013 02:08:09 +0000 (18:08 -0800)]
model: improve get_next_thread() comments
It's curious that get_next_thread() needs the current ModelAction as a
parameter. It helps to clarify that this argument is somwhat "optional."
Brian Norris [Fri, 15 Feb 2013 23:53:13 +0000 (15:53 -0800)]
schedule: simplify Scheduler::select_next_thread()
Now that the "select next thread" vs. "set_current_thread" is clear, we
don't actually need to set the value of 'current' in
select_next_thread().
Brian Norris [Fri, 15 Feb 2013 23:42:14 +0000 (15:42 -0800)]
model: pull scheduler's thread selection into get_next_thread()
The code makes more logical sense if ModelChecker::get_next_thread()
handles all of the thread selection decisions.
Brian Norris [Fri, 15 Feb 2013 23:33:11 +0000 (15:33 -0800)]
schedule: split Scheduler::next_thread() into separate functions
next_thread() is basically overloaded to perform two different
functions, depending on the parameters. In one case, a caller might pass
a NULL thread, which meant that Scheduler is free to select its own next
thread. In another case, a caller will pass a non-NULL thread, which
meant that the caller is simply informing the Scheduler of the next
thread to execute (i.e., which one is "currently running").
These separate functionalities are now separate functions:
Scheduler::select_next_thread()
Scheduler::set_current_thread(Thread *)
Brian Norris [Fri, 15 Feb 2013 23:19:45 +0000 (15:19 -0800)]
model: factor out a 'switch_from_master()' function
This snippet of code is important and somewhat subtle. Although we only
use it once, let's make it a function to give it a higher-level
abstraction.
Brian Norris [Fri, 15 Feb 2013 20:54:25 +0000 (12:54 -0800)]
model: rework the release sequence fixups
It makes more sense to pull the release sequence fixups out of the main
execution loop and only perform them after all other actions are
complete.
There's still some more cleanup to be done here, but it appears that
end-of-execution release sequence fixups are functional again.
Brian Norris [Fri, 15 Feb 2013 20:17:06 +0000 (12:17 -0800)]
model: simple refactoring
This condition is useless. We can just return next_thrd directly.
Brian Norris [Fri, 15 Feb 2013 19:54:11 +0000 (11:54 -0800)]
model/threads: add documentation comments
Document {get,set}_pending(), has_asserted()/set_assert(), etc.
Brian Norris [Fri, 15 Feb 2013 19:02:05 +0000 (11:02 -0800)]
model: fix leaking "pending actions"
ModelActions that are "pending" for each thread are not automatically
freed when we rollback; we keep most of the active ModelActions on the
NodeStack, then we free them from there when we explore a new branch of
the state space.
This fix causes all the pending actions to be freed on any rollback.
This is safe for now, since we always roll back to the beginning of the
execution. If we roll back to an intermediate point, though, we need to
retain those pending actions which were also pending before the rollback
point. Hence the FIXME notice included in reset_to_initial_state().
Brian Norris [Wed, 13 Feb 2013 02:12:17 +0000 (18:12 -0800)]
model: add 'pending' assertion
We don't want to clobber a pending action.
Brian Norris [Wed, 13 Feb 2013 01:56:13 +0000 (17:56 -0800)]
model: stash all pending actions immediately
Brian Norris [Wed, 13 Feb 2013 01:24:31 +0000 (17:24 -0800)]
model: pull 'has_asserted()' check out of take_step()
Checks for mid-execution assertions should occur before take_step().
This can catch a mid-step bug (e.g., data race or user-assertion) that
happens between ModelAction steps.
Brian Norris [Wed, 13 Feb 2013 00:54:38 +0000 (16:54 -0800)]
threads: bugfix - do not call thread_current() from model-checker
thread_current() was designed for use in the user context. It is not
guaranteed to provide a reliable result in the model-checker context,
since we may perform context switches as needed, such that the "last
executed user thread" may not be the thread that we are checking at the
time.
This change is made to clear up future changes that will modify the
scheduling patterns.
Brian Norris [Wed, 13 Feb 2013 00:39:33 +0000 (16:39 -0800)]
model: stash actions in each thread
We don't want a global 'current_action' for saving the next action to
run; we want to stash the 'current action' for each thread. So just use
the 'pending' action in each Thread.
Note that this kinda breaks sleep sets for now. We'll have to redo this.
Brian Norris [Wed, 13 Feb 2013 00:33:40 +0000 (16:33 -0800)]
model: return next thread from take_step()
Note that this intentionally breaks release sequence fixups for now.
Brian Norris [Wed, 19 Dec 2012 01:46:40 +0000 (17:46 -0800)]
threads/model: allocate Thread from w/in ModelChecker
It adds scheduling difficulties if we allocate/schedule a Thread from
the user-context (i.e., directly from the thrd_create() interface)
because then it is not necessarily atomic. For example, if we run a
thread up to its context switch for a THREAD_CREATE then switch to
another thread before the THREAD_CREATE is processed, then we will
already have constructed a Thread from the first thread (and prepared it
for scheduling) without processing it in the ModelChecker appropriately.
For instance, the following schedule might appear, causing problems:
TID ACTION
--- ------
...
1 ATOMIC_READ <--- Next action is THREAD_CREATE
(1) (construct Thread 3)
(1) (prepare new Thread for Scheduling)
2 ATOMIC_READ
3 THREAD_START <--- Before its CREATE event??
1 THREAD_CREATE
Note that this scheduling does not yet happen, as we always execute
the "lead-in" to THREAD_CREATE atomically. This may change, though.
Brian Norris [Thu, 14 Feb 2013 20:23:48 +0000 (12:23 -0800)]
schedule: assert that model-checker thread doesn't enter scheduler
Brian Norris [Tue, 12 Feb 2013 20:53:20 +0000 (12:53 -0800)]
model: set thread state during 'swap' calls
Rather than setting thread-state from subtle places within ModelChecker,
it makes more logical sense to set it from withing the Thread::swap
functions.
Brian Norris [Tue, 12 Feb 2013 19:48:41 +0000 (11:48 -0800)]
Merge branch 'fences'
Brian Norris [Tue, 12 Feb 2013 19:35:45 +0000 (11:35 -0800)]
promise: use id_to_int()
Brian Norris [Tue, 12 Feb 2013 18:42:17 +0000 (10:42 -0800)]
model: prune may-read-from set early
It helps to prune the may-read-from set (according to modification order
constraints) as we build it. This prevents unnecessary backtracking and
provides a significant (linear) speedup in model-checking speed.
Note that this now allows us to assume that at any point in an
execution, any selection from the may-read-from set is feasible.
Brian Norris [Tue, 12 Feb 2013 18:26:10 +0000 (10:26 -0800)]
action: bugfix - initialize member
Brian Norris [Sat, 9 Feb 2013 01:08:47 +0000 (17:08 -0800)]
model: rewrite mo_check_promises
Rather than use some special logic that was devised when we didn't
include promises in the mo-graph, we can simplify our mo_check_promises
code by querying the mo-graph for reachability. This *should* be at
least as good of a 'check' as the previous code, and much less cryptic.
Brian Norris [Sat, 9 Feb 2013 01:08:33 +0000 (17:08 -0800)]
model: remove argument from mo_check_promises
Brian Norris [Sat, 9 Feb 2013 00:34:33 +0000 (16:34 -0800)]
cyclegraph: possible optimization
Brian Norris [Fri, 8 Feb 2013 23:23:41 +0000 (15:23 -0800)]
model: rename according to the comments
The documentation mentions 'pread' and 'pwrite'. Those names aren't
actually used in the code, though, so change that.
Brian Norris [Thu, 7 Feb 2013 00:39:52 +0000 (16:39 -0800)]
model: add read-write coherence for promise nodes
Promises must be ordered after any other loads from the same thread.
Brian Norris [Thu, 7 Feb 2013 00:51:12 +0000 (16:51 -0800)]
promise: update comments/names to reflect usage
is_compatible() and is_compatible_exclusive() do not require a store as
an argument; they can just as well use a load
Brian Norris [Thu, 7 Feb 2013 00:39:15 +0000 (16:39 -0800)]
cyclegraph: expand template usage
checkReachable() and addEdge() will be used in more forms. Add template
instantiations.
Brian Norris [Wed, 6 Feb 2013 23:46:23 +0000 (15:46 -0800)]
model: refactor to use a helper function
Brian Norris [Wed, 6 Feb 2013 22:46:21 +0000 (14:46 -0800)]
cyclegraph: don't delete promise nodes
Merging can fail partway, leaving a somewhat inconsistent graph. This is
safe, since an inconsistent graph must be discarded as infeasible. But
this is a problem when dumping the modification order graph, since we
may dereference freed nodes. So for now, just don't free them.
Brian Norris [Wed, 6 Feb 2013 22:43:39 +0000 (14:43 -0800)]
cyclegraph: fixup support for dumping the modification order graph
We need to include promises in the modification order graph if we plan
on dumping it to a .dot file. This hacks it together so that it works
for now.
Brian Norris [Wed, 6 Feb 2013 22:42:00 +0000 (14:42 -0800)]
cyclegraph: mergeNodes(): return early if we violate RMW
To be consistent, and to prevent unecessary merging work, we should
simply return from the mergeNodes() function as soon as we know it has
failed.
Brian Norris [Wed, 6 Feb 2013 22:41:12 +0000 (14:41 -0800)]
cyclegraph: refactor for indentation
Brian Norris [Wed, 6 Feb 2013 22:00:05 +0000 (14:00 -0800)]
Makefile / git: cleanup generated .dot and .pdf files
Brian Norris [Wed, 6 Feb 2013 02:27:35 +0000 (18:27 -0800)]
cyclegraph: add wrappers for some common functionality
Brian Norris [Wed, 6 Feb 2013 01:45:31 +0000 (17:45 -0800)]
model: fully utilize Promise nodes in CycleGraph
We can eliminate the post-promise-resolution computations now that
mo_graph is built up to include Promise nodes.
Brian Norris [Wed, 6 Feb 2013 01:39:36 +0000 (17:39 -0800)]
model: cosmetic improvements to resolve_promises()
Rename 'resolved' to 'haveResolved', since we will use the 'resolved'
name for something else.
Brian Norris [Wed, 6 Feb 2013 01:36:05 +0000 (17:36 -0800)]
cyclegraph: move function definitions out of header
I found out how to instantiate these functions from within the
implementation file (rather than the header). I can specifically list
those implementations that I want available.
Brian Norris [Wed, 6 Feb 2013 01:13:28 +0000 (17:13 -0800)]
cyclegraph: template-ize addRMWEdge()
Brian Norris [Tue, 5 Feb 2013 22:26:24 +0000 (14:26 -0800)]
cyclegraph: bugfix - pop edges properly
Now that CycleNode's have back-edges, we need to properly remove *both*
the forward and back edges when doing roll-back.
Brian Norris [Tue, 5 Feb 2013 22:10:06 +0000 (14:10 -0800)]
model: add write-to-promise edges
Assume that any time a promise exists, is compatible with a store, and
is exclusive to the same thread as the store, that it is mod-ordered
after that store. This should never produce cycles, until we decide to
begin satisfying promises. At that point, if there's a cycle, then we
must either merge nodes (i.e., the store must satisfy that promise) or
else we discard the execution for the moment and perform the
satisfaction at a later point in the search space.
Brian Norris [Tue, 5 Feb 2013 22:03:28 +0000 (14:03 -0800)]
promise: add is_compatible_exclusive()
Check if a Promise is both compatible *and* exclusive to a particular
thread. This allows ordering optimizations when we can guarantee that a
particular thread must fulfill the promise.
Brian Norris [Tue, 5 Feb 2013 22:01:34 +0000 (14:01 -0800)]
promise: add const
Brian Norris [Tue, 5 Feb 2013 21:47:20 +0000 (13:47 -0800)]
model: utilize CycleGraph 'addEdge()' status
The mo_graph is only modified if addEdge() returns true. Utilize this
information.
Brian Norris [Tue, 5 Feb 2013 21:44:32 +0000 (13:44 -0800)]
cyclegraph: return 'added' status for addEdge()
The ModelChecker would like to know if it's adding a new edge, or just
and existing edge. If the edge is not new, then there are fewer
resulting update checks needed.
Brian Norris [Tue, 5 Feb 2013 06:50:45 +0000 (22:50 -0800)]
cyclegraph: add documentation
Brian Norris [Tue, 5 Feb 2013 01:12:11 +0000 (17:12 -0800)]
cyclegraph: bugfix - only use concrete writes to eliminate threads
Brian Norris [Tue, 5 Feb 2013 00:24:36 +0000 (16:24 -0800)]
cyclegraph: edit template for checkReachable
Brian Norris [Tue, 5 Feb 2013 00:24:21 +0000 (16:24 -0800)]
cyclegraph: edit template for addEdge
Brian Norris [Tue, 5 Feb 2013 00:22:03 +0000 (16:22 -0800)]
cyclegraph: add overloaded getNode_noCreate()
Need a generic way to map a ModelAction/Promise to a CycleNode.
Brian Norris [Sat, 2 Feb 2013 01:51:56 +0000 (17:51 -0800)]
model: add promise-node edges for 'read' actions
Brian Norris [Sat, 2 Feb 2013 01:47:57 +0000 (17:47 -0800)]
cyclegraph: template-ize checkReachable()
ModelChecker will need to query the mo_graph regarding the modification
order of promised future writes.
Brian Norris [Sat, 2 Feb 2013 00:44:22 +0000 (16:44 -0800)]
model: template-ize 'r_modification_order'
We will need to add "read modification order" edges when 'rf' is either
a ModelAction or a Promise. This function works nicely with a template.
Brian Norris [Fri, 1 Feb 2013 23:33:38 +0000 (15:33 -0800)]
action: fixup printing for RMW/RMWR
Some read actions didn't really have a correct 'value' saved in the
ModelAction. Now that we have the 'promise' recorded, always retrieve
the value from reads_from or reads_from_promise.
Brian Norris [Fri, 1 Feb 2013 23:27:32 +0000 (15:27 -0800)]
action: store Promise in ModelAction
Brian Norris [Fri, 1 Feb 2013 23:11:13 +0000 (15:11 -0800)]
cyclegraph: add full promise resolution, node merging
We now support the interfaces needed for tracking Promise constraints in
CycleGraph.
Brian Norris [Fri, 1 Feb 2013 23:09:07 +0000 (15:09 -0800)]
cyclegraph: add CycleNode::resolvePromise(), CycleNode::getPromise()
Brian Norris [Fri, 1 Feb 2013 23:07:56 +0000 (15:07 -0800)]
promise: add is_compatible()