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.

model: rename 'cyclegraph' to 'mo_graph'

This is not just an arbitrary graph with cycle-detection; it is specifically a
representation of the modification order of various atomic objects.

model: don't "leak" promises

test/Makefile: remove pointless variable

.gitignore: don't ignore /model anymore

We don't produce an executable named 'model' anymore.

Merge branch 'norris'

schedule: make print() const

Switch to using a "const_iterator" so that the whole function becomes const.

model: privatize check_current_action()

threads: correct 'swap()' documentation

Some of the swap() documentation was duplicated incorrectly. While I'm at it,
make the descriptions more clear and precise.

main, model: don't 'initialize' system_context

I was unnecessarily giving main.cc control of the system_context variable,
since I thought I needed to use getcontext() before entering the model checker.
However, the structure of the runtime scheduling is such that this
"initialization" would be obliterated by the first swapcontext() call
(switching form system-context to user-context).

So, the point is that the model-checker can just declare its own
("uninitialized") context that will be initialized as soon as the model-checker
makes a thread swap. Thus, I remove the external interface for initializing the
context (set_system_context()).

action: don't merge twice in read_from()

synchronize_with() already takes care of the clock vector merging, so don't
merge a second time.

action: rework/rename 'synchronized()' to 'synchronize_with()'

Fix some comments, names, etc.

Privatize synchronized()/synchronize_with(), since it's only intended for
within other wrapper actions performed on ModelAction.

model: remove useless return code from add_thread()

schedule, threads: update comments, const's

model: make scheduler private

To accomplish this, I needed to add one accessor method for
'get_current_thread()'.

main, model: move main execution loop into ModelChecker class

cyclegraph: improve comments, use initializer list

hashtable: document get_safe_ptr()

hashtable: rename ensureptr() to get_safe_ptr()

ensureptr() is kind of vague. This rename -- along with some better description
-- will help clarify what this function does.

hashtable: bugfix - increment size only when new bins are linked

In both put() and ensureptr(), the 'size' counter should not be incremented
until we decide if we're adding a new bin or not. When incremented improperly,
'size' ended up out of sync with the hash table; it reported a size much larger
than the actual table.

hashtable: some refactoring, signed-ness

Since 'capacity' is unsigned, so should the index that compares with it.

The (duplicated) compare/resize code can be a bit shorter and (IMO) easier to
read.

model: reformat/refactor some code

impatomic.h: fixup spacing

Tabs vs. spaces for indentation screws up this indentation, making it even
harder to read than it should be. Switch this all to spaces (for uniformity
across all editor configurations) and align things properly.

threads: trivial change

model: revert unnecessary parameter for print_summary()

CycleGraph::checkForCycles() is a cheap function; it only checks a flag status.
So we don't need to make code more complicated just to avoid calling this
function.

Effectively a revert of:
commit 7cee72d776ddfbf585038f3cad3df799e353cc11

add basic parameter handling

common: add error_msg() function

run.sh: pass command-line arguments through to test program

Once the model-checker begins handling arguments, we should pass through
arguments to the program.

.gitignore: ignore other vim swap file type

model: reformat some code

main, threads: improve comments regarding thread stepping

The comment in thread_system_next was incorrect:
"Returns the 1 if there is another step and 0 otherwise."

Add a few comments throughout to help clarify this behavior.

add a todo flag to a comment so it won't get lost... low priority item though

Makefile: fix config.h dependencies

The snapshotting code needs to be rebuilt when config.h is modified.