model-checker.git
11 years agomodel: get_mutex() for locating the lock map
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.

11 years agoaction: add ModelAction::is_thread_join() helper
Brian Norris [Tue, 2 Apr 2013 23:53:52 +0000 (16:53 -0700)]
action: add ModelAction::is_thread_join() helper

11 years agomymemory: fix compiling with !USE_MPROTECT_SNAPSHOT
Brian Norris [Tue, 2 Apr 2013 23:00:30 +0000 (16:00 -0700)]
mymemory: fix compiling with !USE_MPROTECT_SNAPSHOT

11 years agonodestack: move "behaviors" increment all into Node wrapper function
Brian Norris [Thu, 28 Mar 2013 22:27:17 +0000 (15:27 -0700)]
nodestack: move "behaviors" increment all into Node wrapper function

11 years agonodestack: regroup some code
Brian Norris [Thu, 28 Mar 2013 22:21:00 +0000 (15:21 -0700)]
nodestack: regroup some code

To put "threads backtracking" code together

11 years agothreads: move circular wait check into Threads::is_waiting_on
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.

11 years agocorrect comment typo
Brian Demsky [Fri, 22 Mar 2013 23:31:47 +0000 (16:31 -0700)]
correct comment typo

11 years agocheck in insane test case...
Brian Demsky [Fri, 22 Mar 2013 23:27:37 +0000 (16:27 -0700)]
check in insane test case...

We don't support such behavior.

11 years agofix mistake in promises may allow code... need to be even more aggressive about fv
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

11 years agomain: adjust defaults again
Brian Norris [Fri, 22 Mar 2013 06:24:15 +0000 (23:24 -0700)]
main: adjust defaults again

-s 6 -S 4

11 years agoMerge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
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

11 years agomain: change default 'future delay' for promise expiration
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.

11 years agomodel: re-check pending future values whenever a promise is resolved
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.

11 years agomodel: bugfix - send future values more eagerly
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.

11 years agomodel: refactor add_future_value, add documentation
Brian Norris [Thu, 21 Mar 2013 23:24:47 +0000 (16:24 -0700)]
model: refactor add_future_value, add documentation

11 years agomodel: add 'const'
Brian Norris [Thu, 21 Mar 2013 23:17:16 +0000 (16:17 -0700)]
model: add 'const'

11 years agomodel: rename PendingFutureValue 'act' to 'reader'
Brian Norris [Thu, 21 Mar 2013 23:01:23 +0000 (16:01 -0700)]
model: rename PendingFutureValue 'act' to 'reader'

To make it more clear

11 years agomodel: rework the resolve-promise interface
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.

11 years agoadd test case...
Brian Demsky [Thu, 21 Mar 2013 22:18:30 +0000 (15:18 -0700)]
add test case...

11 years agocyclegraph: propagate RMW atomicity edges down the chain
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.

11 years agomodel: note how we support seq-cst fences
Brian Norris [Tue, 19 Mar 2013 02:23:21 +0000 (19:23 -0700)]
model: note how we support seq-cst fences

11 years agoadd our names
Brian Demsky [Tue, 19 Mar 2013 00:25:19 +0000 (17:25 -0700)]
add our names

11 years agoadd copyright message
Brian Demsky [Tue, 19 Mar 2013 00:24:27 +0000 (17:24 -0700)]
add copyright message

11 years agoMerge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
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

11 years agoupdate git repository with license... GPL v2
Brian Demsky [Mon, 18 Mar 2013 23:46:02 +0000 (16:46 -0700)]
update git repository with license...  GPL v2

11 years agotest: rmwprog: add MODEL_ASSERT
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.

11 years agofix memory leak
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...

11 years agomodel: bugfix - missing SC mo_graph edge
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.

11 years agomodel: refactor r_modification_order 'act != curr' and 'act != rf'
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).

11 years agomymemory: enforce that user allocations come from user context
Brian Norris [Sat, 9 Mar 2013 20:54:58 +0000 (12:54 -0800)]
mymemory: enforce that user allocations come from user context

11 years agomymemory, threads: add allocator specifically for Thread
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.

11 years agomodel: privatize some thread functions
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.

11 years agolitmus: wrc: add macro for memory ordering
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.

11 years agolitmus: seq-lock: add MODEL_ASSERT() for the important behavior
Brian Norris [Sat, 9 Mar 2013 00:50:51 +0000 (16:50 -0800)]
litmus: seq-lock: add MODEL_ASSERT() for the important behavior

11 years agomodel-assert: include <stdbool.h>
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.

11 years agostl - remove stale <vector> and <list> #include's
Brian Norris [Fri, 8 Mar 2013 20:35:42 +0000 (12:35 -0800)]
stl - remove stale <vector> and <list> #include's

11 years agobugfix - add stl-model.h wrappers, to provide more control over STL
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.

11 years agoRevert "switch to snapshot/modelalloc versions of stl classes"
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.

11 years agoswitch to snapshot/modelalloc versions of stl classes
Brian Demsky [Thu, 7 Mar 2013 22:49:20 +0000 (14:49 -0800)]
switch to snapshot/modelalloc versions of stl classes

11 years agoadd new option for uninitialized writes...
Brian Demsky [Thu, 7 Mar 2013 03:17:58 +0000 (19:17 -0800)]
add new option for uninitialized writes...

11 years agomodel, nodestack: bugfix - retain UNINIT actions across executions
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).

11 years agolinuxrwlocksyield: refactor
Brian Norris [Wed, 6 Mar 2013 07:05:25 +0000 (23:05 -0800)]
linuxrwlocksyield: refactor

11 years agodocumentation update
Brian Demsky [Wed, 6 Mar 2013 05:58:33 +0000 (21:58 -0800)]
documentation update

11 years agoMerge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
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

11 years agoadd destructor so the spsc-queue will compile on MAC
Brian Demsky [Wed, 6 Mar 2013 05:40:39 +0000 (21:40 -0800)]
add destructor so the spsc-queue will compile on MAC

11 years agoMerge remote 'yield' work
Brian Norris [Wed, 6 Mar 2013 03:04:57 +0000 (19:04 -0800)]
Merge remote 'yield' work

11 years agomodel: don't print 'uninitialized' ModelActions in trace output
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.

11 years agoadd yield support
Brian Demsky [Wed, 6 Mar 2013 02:35:27 +0000 (18:35 -0800)]
add yield support

11 years agoimpatomic: fences linker error
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.

11 years agoMakefile: use $+ variable
Brian Norris [Tue, 5 Mar 2013 03:51:49 +0000 (19:51 -0800)]
Makefile: use $+ variable

11 years agocyclegraph: memory "leak", fixup
Brian Norris [Tue, 5 Mar 2013 01:50:08 +0000 (17:50 -0800)]
cyclegraph: memory "leak", fixup

An insignificant memory leak.

11 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

11 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.

11 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.

11 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

11 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.

11 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.

11 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.

11 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.

11 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

11 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.

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

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

11 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.

11 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.

11 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

11 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.

11 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.

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

11 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

11 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

11 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.

11 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.

11 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.

11 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.

11 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

11 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.

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

11 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

11 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.

11 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.

11 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

11 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

11 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.

11 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.

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

11 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.

11 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.

11 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

11 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).

11 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.

11 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.

11 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 ?

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

11 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.

11 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.

11 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.

11 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.

11 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.

11 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.