model-checker.git
9 years agolittle optimizations motivated by profiling...
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

9 years agomodel: refactor the get_thread() selection
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.

9 years agorefactor DBG_ENABLED() vs. verbose
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.

9 years agomodel: add promise printing to execution summaries
Brian Norris [Mon, 4 Mar 2013 04:34:26 +0000 (20:34 -0800)]
model: add promise printing to execution summaries

9 years agonodestack: print thread status info in Node::print
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.

9 years agocyclegraph: missing form of checkReachable()
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.

9 years agomodel: rename check_deadlock() to is_circular_wait()
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.

9 years agomodel: add improved (?) deadlock detection
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.

9 years agothreads: add waiting_on()
Brian Norris [Sun, 3 Mar 2013 07:53:29 +0000 (23:53 -0800)]
threads: add waiting_on()

For use with deadlock detection

9 years agomutex: change 'islocked' to hold Thread pointer
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.

9 years agoaction: add get_mutex()
Brian Norris [Sun, 3 Mar 2013 07:24:51 +0000 (23:24 -0800)]
action: add get_mutex()

9 years agomutex: fix indentation
Brian Norris [Sun, 3 Mar 2013 06:55:51 +0000 (22:55 -0800)]
mutex: fix indentation

9 years agoaction: add get_return_value()
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.

9 years agomodel: use get_write_value()
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.

9 years agomodel: bugfix - adding a Promise reader can cause failure
Brian Norris [Sat, 2 Mar 2013 23:03:58 +0000 (15:03 -0800)]
model: bugfix - adding a Promise reader can cause failure

9 years agomodel: hack dumpGraph() bug by "leaking" promises
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.

9 years agocyclegraph: simplify resolvePromise / mergeNodes
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.

9 years agomodel: refactor process_read logic
Brian Norris [Sat, 2 Mar 2013 22:04:08 +0000 (14:04 -0800)]
model: refactor process_read logic

9 years agocheck_recency: update/add documentation comments
Brian Norris [Sat, 2 Mar 2013 20:28:26 +0000 (12:28 -0800)]
check_recency: update/add documentation comments

9 years agocheck_recency: improve templates, use when reading from Promise
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

9 years agocheck_recency: refactor some more, + include Promises
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.

9 years agocheck_recency: return a boolean status
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.

9 years agocheck_recency: only allow newer stores to "overwrite"
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.

9 years agocheck_recency: implement loops as function ModelAction::may_read_from()
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.

9 years agonodestack: add support functions for check_recency() w/ Promises
Brian Norris [Sat, 2 Mar 2013 03:06:30 +0000 (19:06 -0800)]
nodestack: add support functions for check_recency() w/ Promises

9 years agomodel: check_recency: convert a few things to ASSERT()
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.

9 years agocomments
Brian Demsky [Sat, 2 Mar 2013 02:34:07 +0000 (18:34 -0800)]
comments

9 years agomodel: check_recency: fix indentation, spelling, comments
Brian Norris [Sat, 2 Mar 2013 02:00:14 +0000 (18:00 -0800)]
model: check_recency: fix indentation, spelling, comments

9 years agoaction: bugfix - reads-from value should be VALUE_NONE for new actions
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.

9 years agomodel: fixes for future value passing
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.

9 years agomodel: we only resolve one promise at a time
Brian Norris [Sat, 2 Mar 2013 00:13:25 +0000 (16:13 -0800)]
model: we only resolve one promise at a time

9 years agomodel: fix ASSERT()
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

9 years agopromise: add 'same_value' helper, force value-checking in CycleGraph
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.

9 years agopromise: bugfix - don't check value, check location
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.

9 years agoaction: add get_write_value()
Brian Norris [Fri, 1 Mar 2013 20:32:13 +0000 (12:32 -0800)]
action: add get_write_value()

9 years agoaction: add ModelAction::get_reads_from_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.

9 years agoaction, model: add ASSERT(), not NULL checks
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.

9 years agocyclegraph/model: unify, clean up graph printing
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

9 years agonodestack: get_read_from_promise() never returns NULL
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).

9 years agomodel/schedule: comput "reduadant" measurement, print along with traces
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.

9 years agocyclegraph: clean up mo_graph dump
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.

9 years agoaction: print promise number, not just ?
Brian Norris [Thu, 28 Feb 2013 19:17:42 +0000 (11:17 -0800)]
action: print promise number, not just ?

9 years agonodestack: bugfix - clear backtracking properly
Brian Norris [Thu, 28 Feb 2013 18:30:39 +0000 (10:30 -0800)]
nodestack: bugfix - clear backtracking properly

9 years agopromise: record multiple readers in the same Promise
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.

9 years agoun-'const' some Promises
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.

9 years agonodestack: rewrite promise-resolution "counting"
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.

9 years agomodel: hook up 'read-from-promise' backtracking in ModelChecker
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.

9 years agonodestack: add read_from_promises backtracking
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.

9 years agonodestack: bugfix - rewrite 'may-read-from' and 'future values' as the same set
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.

9 years agomodel: shorten some code
Brian Norris [Thu, 28 Feb 2013 01:54:45 +0000 (17:54 -0800)]
model: shorten some code

9 years agomodel: rename 'reads_from' to 'rf'
Brian Norris [Thu, 28 Feb 2013 01:48:48 +0000 (17:48 -0800)]
model: rename 'reads_from' to 'rf'

9 years agonodestack: rename 'read_from' to 'read_from_past'
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).

9 years agomodel: don't call process_read() for 2nd half of RMW/RMWC
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.

9 years agomodel: bugfix - correct the "equality" check for RR coherence
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.

9 years agocyclegraph: bugfix - allow to compile with SUPPORT_MOD_ORDER_DUMP
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.

9 years agomodel: bugfix - correct RR coherence for Promises
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.

9 years agocyclegraph: change Promise nodes map
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.

9 years agomodel: promises: eliminate threads when they "join"
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.

9 years agoschedule: remove commented-out code
Brian Norris [Tue, 26 Feb 2013 00:23:05 +0000 (16:23 -0800)]
schedule: remove commented-out code

9 years agomodel: bugfix - only allow promise satisfaction for "compatible" threads
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.

9 years agothreads: construct Thread only with a given "parent"
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.

9 years agorepush changes
Brian Demsky [Mon, 25 Feb 2013 07:28:21 +0000 (23:28 -0800)]
repush changes

9 years agofix conflicts
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

9 years agofix norris mentioned bug
Brian Demsky [Mon, 25 Feb 2013 07:24:50 +0000 (23:24 -0800)]
fix norris mentioned bug

9 years agoRevert "fix scheduling stuff to get nice round robin scheduler behavior..."
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.

9 years agofix scheduling stuff to get nice round robin scheduler behavior...
Brian Demsky [Mon, 25 Feb 2013 04:59:46 +0000 (20:59 -0800)]
fix scheduling stuff to get nice round robin scheduler behavior...

9 years agonodestack: bugfix - reset backtracking points on diverging paths
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.

9 years agomodel: bugfix - inherit future values from previous loads
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.

9 years agonodestack: don't use C++ references
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.

9 years agomodel: correct the "no valid reads" assertion
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.

9 years agopromise: stash the whole future_value
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().

9 years agotest: fences: add simple, semi-useful fence tests
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.

9 years agotest: add double-read-fv
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.

9 years agoaction: backtrack/sleep-sets for seq-cst fences
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.

9 years agomodel: wake up pending (sleep-set) actions for fences
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.

9 years agomodel: only backtrack fences when acquire is before release
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'.

9 years agomodel: document get_last{,_fence}_conflict()
Brian Norris [Wed, 20 Feb 2013 22:58:21 +0000 (14:58 -0800)]
model: document get_last{,_fence}_conflict()

9 years agomodel: schedule appropriate fence backtracking points
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

9 years agomodel: convert while-loops to for-loops
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.

9 years agomodel: add 'const'
Brian Norris [Wed, 20 Feb 2013 02:03:56 +0000 (18:03 -0800)]
model: add 'const'

9 years agoinclude: fixup header inclusion
Brian Norris [Wed, 20 Feb 2013 23:03:24 +0000 (15:03 -0800)]
include: fixup header inclusion

9 years agodon't include action.h from model.h
Brian Norris [Wed, 20 Feb 2013 07:37:12 +0000 (23:37 -0800)]
don't include action.h from model.h

9 years agomodel/action: move action_list_t to 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

9 years agopromise: move constructor out of header
Brian Norris [Wed, 20 Feb 2013 07:29:42 +0000 (23:29 -0800)]
promise: move constructor out of header

9 years agoscheduler: refactor round-robin loop
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.

9 years agomodel: end-of-execution print
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

9 years agomodel: improve get_next_thread() comments
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."

9 years agoschedule: simplify Scheduler::select_next_thread()
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().

9 years agomodel: pull scheduler's thread selection into get_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.

9 years agoschedule: split Scheduler::next_thread() into separate functions
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 *)

9 years agomodel: factor out a 'switch_from_master()' function
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.

9 years agomodel: rework the release sequence fixups
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.

9 years agomodel: simple refactoring
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.

9 years agomodel/threads: add documentation comments
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.

9 years agomodel: fix leaking "pending actions"
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().

9 years agomodel: add 'pending' assertion
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.

9 years agomodel: stash all pending actions immediately
Brian Norris [Wed, 13 Feb 2013 01:56:13 +0000 (17:56 -0800)]
model: stash all pending actions immediately

9 years agomodel: pull 'has_asserted()' check out of take_step()
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.

9 years agothreads: bugfix - do not call thread_current() from model-checker
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.

9 years agomodel: stash actions in each thread
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.