cyclegraph: flag cycles for reflexive edges

The cyclegraph shouldn't fail (i.e., ASSERT()) when reflexive edges are
added; instead, they should be declared as cycles.

1) more comments
2) rename is_synchronizing with
3) realize that reordering is only necessary if we create a synchronization...not needed to break one...

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

changes

nodestack: destroy Nodes properly in ~NodeStack()

nodestack: use initializer list

model: remove unnecessary boolean variable

model: assign "pending" return values in release_seq_heads()

Now that the lazy pending release sequences list is improved, return
more information from release_seq_heads().

Note that this change also affects the behavior of the last double loop;
now, even after discovering write(s) from one thread that might break the
release sequence, I continue exploring other threads. This has some pros
and cons:

Con:
* may cause more work in exploring many threads without gaining any
  extra information

Pro:
* may help discover a write that *certainly* breaks the sequence,
  whereas previously, we might have exited with an uncertain status
* builds a more thorough, complete set of writes that might break the
  release sequence

The last point is the main intention, since we will require a complete
set for end-of-execution fixups. The others balance out to a net benefit
(and possibly a bugfix).

model: update pending release sequence list type

In working toward proper resolution of pending release sequences, I will
change the pending release sequence list again. This time, a single list
entry will have the ability to hold all important info regarding a
single release sequence. For now, I only utilize it to store the
'acquire' operation, so there should be no real change in behavior yet.

model: add release_seq structure definition

fix bug...can't mo_check_promises until we're done resolving promises for a write back in time

local commit...  bug that prunes too many executions

Merge branch 'master' of /home/git/model-checker

fix low hanging fruit when profiling...

dump typo was turning off optimized version of checkpointing...option 2 is by far fastest
was spending most of the time freeing an oversized hashtable

fixup more id vs. thread_id_t

action: return synchronization status for ModelAction::read_from()

The ModelChecker may need to know if any synchronization was performed in
read_from().

Note that the return status is not used yet.

action: remove clockvector flag from print() method

We don't actually need to tell ModelAction::print() when to print the
associated clock vector. The introduction of the 'print_cv' boolean flag
was to fix a separate bug that has been fixed. Now the clock vector can
be printed unconditionally, when it exists.

model: rename release_seq_head() -> release_seq_heads()

It may return multiple heads, so make it plural.

model: do not assume THREAD_FINISH is always the last action

It's possible that there will be special fixup ModelActions added, so
just use the Thread::is_complete() method to check for a completed
Thread.

fixup usage of int vs. thread_id_t

model: add const qualifier to get_thread()

model: rearrange conditionals, fixup take_step()

Merge remote-tracking branch 'origin/master'

modeltypes: move small typedefs to own header

To prevent some unnecessary inter-header dependencies, we can move some
simple typedefs to a modeltypes.h header.

model: don't include schedule.h

nodestack: move has_priority() out of header

model: move get_thread() implementations out of header

model: move get_current_thread() implementation out of header

Merge branch 'master' of /home/git/model-checker

a number of fixes to add missing mo_graph edges to speed up detection of infeasible
traces

model: update switch_to_master() comment

Makefile: eliminate malloc.c warning

malloc.c: In function ‘sys_trim’:
malloc.c:4289:20: warning: unused variable ‘newsize’ [-Wunused-variable]
malloc.c: In function ‘destroy_mspace’:
malloc.c:5452:13: warning: unused variable ‘base’ [-Wunused-variable]

mymemory: fix indentation for ModelAlloc

rename 'MyAlloc' to 'ModelAlloc'

mymemory: reword comments

snapshot: rename 'SnapShot' -> 'Snapshot'

This capitalization always messes me up

common: remove excess semicolon

mymemory: define SNAPSHOTALLOC appropriately

SNAPSHOTALLOC can be filled in with meaningful allocators, rather than
using the global default allocators.

replace malloc/calloc/free with snapshot_{malloc/calloc/free}

We need to explicitly declare when we are requesting snapshotting
memory, and we need to avoid using malloc, etc., directly. For now, this
has no functional change, as the 'snapshot_*' functions just call the
stdlib functions, but soon we may switch allocators to use a private
heap.

mymemory: make snapshot_{malloc,calloc,free} externally linkable

As we begin to use these functions, they can't be simply declared
statically in the header; they need to be linkable in hashtable.h, for
instance.

action: reword comments

Why all the ...?

extra file committed accidentally

missing change

mspace_malloc will call into mmap if it runs out of memory...  this does not play well with
snapshotting the mspace of course...

turn off the mmap option and give us a bigger heap...
add assertions to malloc/calloc/realloc if they return NULL (which is now possible with MMAP turned off)

error

random memory leak fixes and memory access fixes

model: debug print - pending release sequences

test: add a "pending release sequences" test

This helps test the end-of-execution "pending release sequence"
functionality, as well as other release-sequence-related code. It also
uncovered the regression that was just reverted prior to this.

(bug) revert JOIN/LOCK simplification

A test case throws an assertion when these changes are included. Maybe
I'll make a proper fix later, but for now, I mostly revert these.

Revert "model: remove obsolete ModelChecker::do_complete_join()"
This reverts commit cef10a2b49af5da16ffe59c5b9ddd210c668fbac.

Revert "model: unify JOIN- and LOCK-related sleep/wake code"
This reverts commit 620ae95ce4fed006d18a41b6ccfd949d7e77f677.

model: one release sequence may help resolve another

model: THREAD_FINISH triggers release sequence check

A THREAD_FINISH action may ensure that a Thread is no longer able to
break release sequences, so all pending release sequences should be
checked.

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

a bug fix

assign sequence numbers after initial processing

When re-ordering the execution of JOIN and LOCK operations (e.g., when
they attempt to execute when not enabled), the sequence numbers became
out of order. Also, RMW operations would cause sequence numbers to jump
by 2 every time.

This fix arranges initialization such that a ModelAction is only
assigned a sequence number after it passes some initial checks to ensure
that it will be executed and utilized immediately. Otherwise, it will
either be discarded or held pending until it is enabled.

action: edit some spacing

model: remove obsolete ModelChecker::do_complete_join()

This function was folded into the one place it is used, now.

model: unify JOIN- and LOCK-related sleep/wake code

We might as well use similar code paths for JOIN and LOCK operations
that must wait on another thread to re-enable it. The side benefit here
is that the JOIN action is now placed at the correct sequence point in
the execution trace.

model: refactor mutex thread-blocking code

There are a few functions that are used in suboptimal ways.

* use the ModelChecker::get_thread(ModelAction *) version of overloaded
  'get_thread()' function

* the add/remove interfaces were used inconsistently previously; for
  "waking" we directly utilized Scheduler::add_thread, whereas the
  "sleeping" case used ModelChecker::remove_thread

* use the Scheduler::sleep and Scheduler::wake functions for sleep/wake
  instead of explicitly adding/removing

action: don't print clock vector when it is invalid

Due to clock vector snapshotting, a ModelAction may hold a pointer to
an inavlid ClockVector. This fix allows callers of ModelAction::print()
to prevent it from printing a corrupted ClockVector.

small hack to optimize our common case for snapshotting and set config option to turn this back on.

hack assumes that same pages will be dirty across different executions so just copies them and doesn't reprotect them

fix bug....  not quite perfect for linux locks, but runs to completion...

Revert "model: revert broken bugfix"

This reverts commit ae7fcd2e5e499f72d9d1530bdc293f4fbc5f0644.

clockvector: snapshot the whole object

model: revert broken bugfix

This reverts parts of the following commit:

 commit 7ba211ec7d1cacbaa3ef2027f1a0f534888f1708

The bugfix broke our basic test case (userprog)

model: fix "earliest diverge" NULL pointer exception

start support for drawing execution diagrams

fix some signed/unsigned warnings

Fixed bug breaking our consolidation of future values...

Two change:
(1) Bug fix...  Check that rf is non-null before calling
r_modification

(2) Add a hook into assert mechanism for the debugger

rename MYFREE -> model_free

rename MYCALLOC -> model_calloc

rename MYMALLOC -> model_malloc

model: refactor/reword initialize_curr_action()

clockvector: snapshot our clock vectors

Clock vectors need to be snapshotted

mymemory: add placeholder "snapshot_{calloc,malloc,free}" functions

Eventually, we may want a separate heap for the model-checker's
snapshotted data (vs. user's snapshotted data), so create allocator
stubs for this. This allows us to begin annotating our malloc()'s
properly.

model: always re-calculate clock vectors

Clock vectors are mutable, via synchronization. We will need to both
snapshot and recompute clock vectors as they are generated. Right now,
we have some incorrect assumptions in place. This bugfix prevents stale
clock vectors (from previous executions) from polluting subsequent
executions.

another bug fix

bug fix...recompute promises of RMW actions at divergence points

model: utilize bad_synchronization flag

model: add "bad synchronization" flag

Can be used for aborting a trace when an incorrectly-ordered
synchronization occurs.

action: synchronize_with - return status for out-of-order synchronization

"synchronize_with()" now can return a boolean status, rather than just
using an ASSERT(). This allows synchronize_with() to be called with
actions that are against the program trace order, then return a status
to signify success/failure. This will allow, for instance, release
sequence calculations to simply abort this single execution, not the
whole model-checker.

model: remove debug print

missing commit of mo_graph changes

fix bug from moving read_from check_recency...check_recency had the assumption that the read_from field was set...

nodestack: add debug prints

model: push mo_graph cycle check into release_seq code

Release sequences traveral should only be undertaken if the mo_graph has
no cycles. Instead of just making this check a hack within
resolve_promises(), make it part of every release sequence exploration.

model: add RMW violation debug print

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