model: record the number of feasible executions

The 'num_executions' statistic isn't quite as useful now. We want to compare
total executions to the number of feasible executions.

config: don't enable graph dumping in master repo

tabbing

(1) add actions for the fence
(2) a little more support for cyclegraph -- show rmw edges
(3) add extra documentation for norris

add support for dumping cyclegraphs as dot files...  also eliminate redundant edges to make them easier to view

bugfix: straighten out STL vector allocation (snapshotted vs. persistent)

When using a STL data structure allocated on the stack, we must make sure its
elements are allocated with the same allocator as the structure. For instance,
in a model-checking context, the stack is persistent (non-snapshotting), so any
stack-allocated std::vector should use the non-snapshotting allocator (i.e.,
MyAlloc).

At the same time, clarify CycleGraph and CycleNode classes by labelling them as
SNAPSHOTALLOC.

model: bugfix - don't clobber 'updated'

The 'updated' variable should stay 'true' even if modification orders and
promises aren't updated by the "write" checks. This could be a RMW which made
updates via the "read" checks.

Revert "Makefile: don't always rebuild make.deps"

The Makefile wasn't using its dependency generation correctly. Revert this for
now.

This reverts commit 870ba814eceb1afee4eefb17dab3980549ca73e2.

snapshot: print stack trace on segfault

common: add print_trace() for backtracing

model: trivial fixups

Makefile: don't always rebuild make.deps

The dependencies don't need to be regenerated for "make tags", "make docs",
etc.

model: simple ASSERT() bug

Don't ASSERT(rf->is_write()) until we're sure that rf is non-NULL.

main: wrap help message

model: kill unneeded local variable

The "Thread *th" variable is used only on a few control paths, and it is never
reused. Might as well just calculate it on the fly. Also, it's recalculated and
masked by another local variable at a deeper level of nesting.

spacing

Merge remote-tracking branch 'origin/makefile'

lots of debugging here... finally working with my rmw example...

Makefile: fixup Mac dependencies

Now, Mac OSX builds can just use "make", not "make mac". (This also allows
"make debug" for Mac OSX)

cleanup style

commit new test case

fix for horrible bug...  turns out that we could generate an infinite set of bad executions due to future values...
fix--don't send future values backwards until all of your promises are resolved...

missing changes

right fix for avoid rmw cycles...  bad assumption in the cyclegraph

another bug fix...

separate out rmw actions
make sure we don't insert promises twice for a node

(1) structure code a little better
(2) add startChanges to cyclegraph...  This is just to check some assertions that rollback is being used correctly and doesn't rollback unintended changes

deal with looping due to bogus future value via promise expiration
fix promise bug

fun issues...
(1) need to compute promises for rmw nodes...they could satisfy them
(2) don't call rmwedge if you don't know where you are reading from yet
(3) miscopied commit from big merge (already_added -> !already_added)
(4) avoid adding rmw edges back to itself
(5) probably worth adding a check that the execution isfeasible before sending future values
(6) resolve promises should add rmwedges when appropriate
(7) fix seq_cst to mask earlier writes..

threads, model, schedule: refactor thread joining

The Thread can hold a list of ModelAction (instead of Threads) that are waiting
for its completion. This will give the exiting Thread a better ability to
handle the event.

This also deletes Scheduler::wait, since it is no superceded by Scheduler::sleep.

model: add ModelChecker::get_thread(ModelAction *act)

Many times, I need to convert ModelAction to a Thread. Overload get_thread() to
make it easier to use.

schedule: add sleep() function

The wait() and wake() functions are not very complementary. I will be removing
wait() in favor of a simpler sleep() function, which is introduced here.

cyclegraph: add non-NULL assertions

Merge branch 'demsky'

Branch cleaned up by Brian Norris

model: cleaning up some code

model: handle RMW, unresolved reads in w_modification_order checks

model: fix the maxreads support

model: some bug fixes to the model checker

linuxrwlocks: two bug fixes; guess the model checker helps find bugs

model: bug fixes to new code

cyclegraph: support rolling back changes

model: replace action conditions with switch block

model: add check_recency()

Note the weaknesses of the code, as documented in @todo.

model: refactor "get next thread" code

get_next_replay_thread() might as well handle all the Thread decisions for the
model-checker. Refactor, and rename to get_next_thread().

model: add too_many_reads flag

nodestack: add get_read_from_size()

main: add "maxreads" parameter

main: add parameter parsing

Only has a help message for now.

model: fix release sequence with RMW, acq vs. acq/rel

Check in a bugfix from Brian D

model: maintain a count of the pending lazy synchronizations

lazy_sync_size should be the sum of the size of all the lists in
lazy_sync_with_release.

model: group snapshottable ModelChecker members in struct

These items shouldn't be reset individually, but rather should be grouped
together and allocated on the snapshotting heap. This puts us a step closer to
utilizing partial rollback within executions.

model: force THREAD_START to immediately follow THREAD_CREATE

Note that on the current userprog.c test case, this change causes more
infeasible executions to appear. This is somewhat unexpected but probably just
a result of sub-optimal scheduling.

model: fix release_seq for open-ended synchronization

This fix handles the case where a thread may not yet have synchronized in a way
that ensures no future writes may break a release sequence. If we encounter
such a thread, we can return false (uncertain) and re-check this potential
release sequence later in the execution.

model: use std::find for release sequence search

model: don't use global 'model' unnecessarily

changes

Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker

check in my stuff...

Conflicts:
model.cc
threads.h

changes

Merge branch 'norris'

Fixes up some THREAD_JOIN behavior, cleaning up a little bit of general model-checker structure.

model: complete the Thread teardown during THREAD_FINISH

model: enforce rule: current_action != NULL

Now that I've fixed THREAD_JOIN, modify the comments and safety checks.

libthreads: don't spin on THREAD_JOIN

THREAD_JOIN can now be implemented properly here. We shouldn't have to spin,
waiting for another thread to complete. This may help improve the ModelChecker
architecture, since we will never have NULL actions passed to the ModelChecker.

model: hook up THREAD_JOIN and THREAD_FINISH actions

schedule: add wait and wake functions

These functions will be used to prevent execution of threads that should be
waiting for another event (e.g., a THREAD_JOIN should cause a thread to wait
for another thread's exit).

threads: fixup THREAD_READY comment

This state will be used for more than just a context switch, so reword the
comment.

threads: add THREAD_BLOCKED state

To signal that a Thread cannot yet be added back to the Scheduler's ready list.

threads: add a wait_list

This list will contain all Threads that are waiting on the current Thread. Will
be used for Thread joins, in particular.

threads: add is_complete() helper function

action: add THREAD_FINISH action

For cleanly finalizing a thread.

snapshot-interface: debug prints: lengthen the "regionname" field

working towards making datarace detection work

bug in race detector

another example

model: document ModelChecker::check_current_action

model: check_current_action returns its 'nextThread'

To begin some code structure rearrangements, I make check_current_action()
return the 'nextThread' value as a true return value. Eventually, the
nextThread field might not be needed, and the model-checker behavior might make
more sense...

model/schedule: revise 'nextThread' data flow

The ModelChecker::nextThread field was being abused a little in my aging
design. It really should be either a private field (not accessed even via
accessors) or else just a return value / function parameter.

This commit makes a change so that nextThread is a Thread pointer and is
directly supplied to the Scheduler. If it is NULL, then the Scheduler is
allowed to pick its own Thread to run.

action: print '?' for unknown read-from-future

To provide more informative debugging traces, use a placeholder '?' as the "Rf"
value when printing a 'read' ModelAction that has no reads-from value. This
helps, for instance, when manually identifying problem points in an infeasible
execution.

model: re-check release sequences lazily

For now, I write this "lazy check" as follows:

Whenever one of the following occurs:
* a Promise is fulfilled
* a mo_graph edge is added

Then I recheck all the actions (for the relevant object location) that are
waiting in the lazy release head queue.

model: add resolve_release_sequences() function

This function can check for release sequence resolutions then propagate
synchronization and remove from the "lazy release" list. It does not add any
new mo_graph edges yet.

model: stash actions for lazy release-seq checking

Build up lists of actions to lazily check for new release sequence
developments.

model: report 'updates' when adding mo_graph edges

The rest of the model checker would like to know if any edges were added. Add a
boolean return value to report this.

model: report status of resolved promises

The rest of the model checker needs to know when promises are added, so add a
return status as a boolean.

action, clockvector: add 'has_synchronized_with()' functions

These functions will check whether a ClockVector (or corresponding ModelAction)
is *completely* synchronized with another already. This is different from
simply "happens before," because I may need to update and propagate a clock
vector after initial execution as more information becomes available, and so
this function helps determine whether a particular pair of vectors is worth
merging (and then - expensively - propagating) before actually performing the
synchronization.

[Not documented properly yet...]

action: make synchronize_with() public

action: utilize release sequence(s) for synchronization

Instead of checking only the trivial release sequence (i.e., a read-acquire
reads directly from a write-release) for establishing synchronization, make use
of the ModelChecker's more complete 'get_release_seq_head()' functionality,
then loop through all release heads and synchronize with each. This is
necessary because a read-acquire may synchronize with more than one
store-release.

Note that this step only implements support based on present knowledge. The
incomplete knowledge of the modification order, as given in mo_graph, as well
as "reading from the future" may require lazy checking.

model: add release sequence support

The ModelChecker now can find the head(s) of the release sequence(s) with which
a particular ModelAction (read-acquire) will synchronize.

The ModelChecker::release_seq_head function can locate a release sequence head
for a given ModelAction, based on information at a given moment. That is, it
knows happens-before and modification information for the present, but some
decisions may need to be made in the future as reads-from promises are
fulfilled or modification ordering is observed by future reads and writes.

Lazy checking for the latter cases has yet to be implemented.

model: change pointer spacing style

action: (assertion) disallow out-of-order synchronization

We build our ModelChecker around the assumption that synchronization never
occurs counter to the execution order. This assertion lets us know if that
fails.

model: improve some promise-related comments

action: update 'reads_from' field before synchronization

As the ModelChecker's release/acquire functionality gets more complex,
it makes more sense to assign the ModelAction::reads_from field before
checking synchronization. Currently, this makes no change in behavior.

nodestack: turn magic promise numbers into enum + typedef

Document the enum properly, since it's quite unclear what these flags really
mean.

nodestack, model: use uniform spacing, style

nodestack: don't use uint32_t

uint32_t (and similar) should only be used when an exact field-size is needed
across platforms with different integer sizes. In this case, we only need an
unsigned type, so just use unsigned int.

nodestack: remove unnecessary typedefs

These typedefs are used once or twice and don't add much meaning.

cyclegraph: add public CycleGraph::checkReachable()

The private CycleGraph::checkReachable() function can be useful externally,
when provided with two ModelActions. This implements a small wrapper for public
usage.

model: correct mo_graph comment

My understanding of the mo_graph was incorrect, due to some confusion over the
CycleGraph interfaces. Correct this.

cyclegraph: straighten out header vs. implementation vs. usage

The CycleGraph::addEdge and CycleGraph::addRMWEdge functions were a little
confusing to use, since their implementation and header prototypes had
different parameter naming. This swapped the 'to' and 'from' naming, such that
it appeared as if the addEdge() users were adding edges in the reverse
direction. The functionality was not actually incorrect, but my understanding
was...

This corrects the naming and switches the order of the arguments.

promise: rewrite into a simpler header file

Makefile: rewrite header dependencies

We shouldn't need to add new files in 3 different places. Automatically
generate most of this using GCC's '-MM' option.

model: document ModelChecker::mo_graph

The modification order graph is a complex data structure, and there are a few
pieces of high-level information that should be noted. For example, the edges
are actually directed from most recent to oldest, which is somewhat in reverse
of the usage in the literature, where

  a --mo--> b

means that a comes *before* b in the modification order. This convention can be
changed in the future, but it should be documented here.