doc: add release sequence notes

docs: move to subdirectory

model: avoid infinite loop in release_seq_head()

To understand the problem I'm solving here, note that resolve_promises()
calls ModelAction::read_from() which calls ModelChecker::release_seq_head().

Now, release_seq_head() has the basic assumption that the mo_graph
doesn't have cycles (or specifically, in this case it's important that
sequences of RMW's don't form loops in the reads-from relation).
Unfortunately, resolve_promises() can create such a cycle (by assigning
the "reads-from" value) before checking if that would create a cycle.
This will trigger a check to release_seq_head, which gets stuck in an
infinite loop...

The solution, at least for this targeted portion of code, is to:
(1) First add the relevant RMW edge, if possible
(2) If (1) didn't create mo_graph cycles:
       Then assign reads-from, check release sequences, update
       synchronization
(3) Calculate other normal mo_graph edges

This way, (2) will simply be skipped if we have cycles, avoiding the
problem.

model: bugfix - iterator naming conflict

There's already another iterator named 'it' in resolve_release_sequences().
Although this iterator probably will mask the earlier iterator (giving correct
behavior), it's probably safer to rename the later one for clarity.

model: re-check release sequences after THREAD_JOIN

If a THREAD-specific operation (from process_thread_action()) added any
synchronization, we should re-check all release sequences.

model: add current action work_queue comment

model: mutex synchronization -> re-check release sequences

All synchronization updates should generate a re-check of release sequences.
This commit corrects this for mutexes.

model: trivial - rename 'updated' -> 'update'

model: bugfix - release sequences - handle Thread completion

A completed Thread cannot generate any new writes that would break release
sequences.

model: fixup spelling (and formatting) in comments

relese -> release

model: split THREAD_* processing into process_thread_action()

The THREAD_* specific functionality can easily be in its own function.

Additionally, this patch:

* performs the trivial rearrangement of moving this code inside the
  work_queue loop, for consistency

* returns a "synchronized" status, so that THREAD_FINISH/THREAD_JOIN can be
  hooked into the work_queue update loop later

Merge branch 'norris'

model: release_seq_head - rewrite RMW recursion as loop

A bug in release sequences coce (independent of this patch) causes a huge
blowup of the recursion, yielding strange stack errors. So I address "@todo
Might it be better to make this into a loop", causing a loop of memory usage
instead. This can be triggered, for example, with:

  ./run.sh ./test/linuxrwlocks.o -e 1 -f 4 -m 1

add comments

fairness changes...
fix bug with putting enabled information in wrong place
reveals norris bug...

model: flatten "pending acquire/release sequence" structure

This structure should just be a simple flat array, so that we can simply
iterate through all acquire operations with pending release sequences. There
probably wasn't much to be saved by organizing this structure as a hash table
of lists; if so, I can add the complexity back in later.

This eliminates the need for a separate 'lazy_sync_size' count and renames
'lazy_sync_with_release' to 'pending_acq_rel_seq'.

Merge branch 'norris'

1 bugfix

model: bugfix - infinite loop in resolve_release_sequences()

comments

Merge branch 'norris'

model: fixup style

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

more documentation

model: release_seq_head: improve ordering of tests

We can get useful information from a non-write action, as long as we aren't
checking it for modification order or breaking of the release sequence.

model: release sequences: check last action in each thread

Previously, release_seq_head would only examine actions on a particular, given
object to determine a release sequence. However, we can get information
regarding the possibility of future disruptive writes by checking the clock
vector of the last action of each thread, regardless of object.

model: pad the digits in exec#.dot filenames

The generated .dot files can't be sorted alphabetically once we have double
digit executions. Make the filename use a 4-digit number, padded with zeros.

model: add const qualifiers, fixup comments

The "get_last_*" series of functions should be labeled const.

Also, some of the comments were missing/incorrect.

documentation

model: get_last_conflict - replace if/else-if block with switch

Makefile: move common Mac flags to common.mk

fix compilation (includes)

bug fixes for lock support...think it works now...

fix merge

changes

push changes

merge stuff
Merge branch 'master' into mutex

Conflicts:
model.cc
model.h

more mutex changes

support for locks...  untested, but doesn't break quick run of a sample of test cases

more bugs

fix merge bug

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

Conflicts:
model.cc

my schedule changes

merge in master

fix bug

model: replace list type with action_list_t

model: add typedef for list of release sequence heads

model: THREAD_JOIN synchronizes with THREAD_FINISH

action: THREAD_JOIN can synchronize against execution order

synchronize_with() had an assertion to ensure that synchronization never
occurred opposite the execution trace ordering. But THREAD_JOIN is a special
case, where this ordering won't break the rest of the model-checker.

ichange

model: add curr to action lists early

The current action should be added to the ModelChecker lists early within
check_current_action, so that we can have consistency throughout the function.
We only allow an isolated piece of initialization (initialize_curr_action) to
occur before this step.

model: document behavior of ModelChecker::initialize_curr_action

model: pull "may_read_from set" calculation out of initialization

The build_reads_from_past calculation shouldn't be part of the action
initialization. It requires more information from the ModelChecker.

In the future, we will assume that all check_curren_action code (after
initialization) may include the current action in the model-checker lists. So
this also fixes up the build_reads_from_past code so that it skips the current
action.

model: refactor ModelChecker::initialize_curr_action

Rewrite some logic for simplification. Just refactorization.

model: move init code to ModelChecker::initialize_curr_action

Refactoring

changes

model: pull computation out of conditional

tests: add releaseseq test

Very simple release/acquire test, with some relaxed writes thrown in. The test
is semi-useful and can certainly be tweaked a bit.

model: add some mo_graph fixup code to work_queue

The work queue has all its work items implemented now. But I haven't fully
verified that this is complete yet.

Merge branch 'norris'

Primary change: push 'add_action_to_lists()' before main work in
'check_current_action()'

cyclegraph: add ASSERT() for reflexive edges

model: add infeasibility debugging

common: print tracing info for ASSERT() failures

This adds a global model_print_summary() function, so we can view the current
ModelChecker summary info when we hit an assertion.

model: bugfix - w_modification_order handling current action

The current action should be skipped when iterating lists in
w_modification_order.

Bugfix thanks to Brian D.

model: fixup r_modification_order

Bugfix thanks to Brian D.

model: check_recency - "already_added" always true

The current action is always part of the lists now.

Bugfix thanks to Brian D.

model: bugfix get_last_seq_action()

The action lists may include the current action, which we don't want to
consider for 'get_last_seq_action()'.

Also, rewrite some of the comments for this function.

Bugfix thanks to Brian D.

more changes towards locks

Merge branch 'master' into mutex

add mutex files

add mutex files

start towards adding support for mutexes

model: fixup happens_before/reflexivity, add 'curr' to lists earlier

Some code under 'check_current_action' assumes that the current action is not
added to the ModelChecker trace/list data structures yet. However, some
features I need to add will require the current action to be in these
data structures already. So there are a few spots I need to fixup so that the
code can handle "happens_before" reflexivity properly.

This commit moves the "add_action_to_lists()" call as well as fixes up
reflexivity.

Merge branch 'norris'

model: release_seq synchronization generates mo_graph edge "work entries"

Now, when the synchronization for a ModelAction is updated while resolving
release sequences, the affected ModelAction(s) can be queued to the work_queue
for later processing (i.e., checking for mo_graph edge additions).

Note that the MOEdgeWorkEntry is not yet handled in the work_queue loop.

.gitignore: ignore .dot graph files

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

model: add work queue loop

This commit does not change the actual computations performed yet. It only
prepares a loop structure in which we could perform many different Work items,
queueing them up as they are generated.

workqueue: add work queue structures

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

model: more restructuring of read/write processing

Make a ModelChecker::process_write function, for symmetry and to shorten the
code portions where the main control flow happens.

model: remove unnecessary parameter to ModelChecker::process_read

The current Thread can be generated later.

Makefile: add PHONY targets

Just in case there ever are files named clean, mrclean, etc.

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