cyclegraph: add edgeCreatesCycle() function

This is repeated code, so make it a function.

cyclegraph: add const

model: add 'add_future_value()' wrapper

Encapsulate a little logic in a function here, so we can reuse this in
other places.

model: add PendingFutureValue constructor

new test case

cyclegraph: add back edges to CycleNode

hashtable: style

cyclegraph: add putNode() helper

hashtable: style

promise: style fixup

cyclegraph: fix insignificant memory leak

cyclegraph: small cleanup

hashtable: add const

hashtable: fixup style

snapshot: more renaming

snapshot-interface: bugfix - reorder constructor params

The snapshot_id should come first.

snapshot-interface: rename, clean up

snapshot-interface: change hand-coded stack to vector

The logic, etc., is much simpler when using C++ vectors and constructors
here.

snapshot: turn C++ interface into C interface

We don't need all this 'class' structure exposed as an interface; we
only use 3 simple functions (one of which probably can be removed).

fixup style

snapshot: more renaming

addMemoryRegionToSnapShot -> snapshot_add_memory_region
rollBack                  -> snapshot_roll_back
takeSnapshot              -> take_snapshot

snapshot: add (unused) mprot_snapshotter destructor

snapshot: rename HandlePF -> mprot_handle_pf

snapshot: add constructor for mprot_snapshotter

snapshot: separate struct SnapShot naming

The "struct SnapShot snapshotrecord;" structure is very uninformative in
naming and is distinctly different for mprotect-based and fork-based
snapshotting. This renames the struct in order to more clearly separate
its usage in the different implementations.

snapshot: edit capitalization in comment

snapshot: combine public interfaces

Implement the public "API" interfaces once, with separate calls made out
to "fork_*" and "mprotect_*" versions. This should make things a little
clearer, and potentially remove the #if's eventually.

snapshot: split up fork-based and mprotect-based snapshotting

The code is kind of cluttered with #if's and intermixed implementations.
Now, snapshot.cc is split into two halves, where the first half
implements mprotect-based snapshotting and the latter half implements
fork-based snapshotting.

snapshot: remove SSDEBUG

We don't need a separate snapshotting DEBUG() macro.

dissolve snapshotimp.h

snapshotimp.h was being used as a way to expose some of the snapshotting
implementation to mymemory.cc, just for fork-based snapshotting. I've
removed that exposure, so now I can pull the entire header into
snapshot.cc.

mymemory/snapshot: rearrange snapshot implementation

Move some implementation details back to snapshot.cc.

snapshotimp: move macros to fork-based

These macros are only used for fork-based snapshotting.

snapshot: change 'struct SnapShotPage' to a simple typedef

The struct SnapShotPage was being used improperly; it was accessed as
simply an array of data, instead of explicitly accessing its member
variable (which itself was an array). So just make this more
straightforward as a typedef'd array.

This also corrects a pointer cast to use (void *) when appropriate.

fixup style

threads: change thrd_t to store Thread pointer

I need to make some bigger changes to Thread allocation, so we'll need
to modify the storage of thrd_t.

action: add get_thread_operand() method

Instead of guessing at the (type-unsafe) storage within
THREAD_{CREATE,JOIN} ModelActions, we can at least code this within a
single method. Note that this method may get more complex, particularly
for THREAD_CREATE.

model: use get_thread(curr) instead of get_current_thread()

The former is more accurate; the latter is only intended for use while
in user-thread context, where we are sure that Scheduler is in the
appropriate state.

test: don't relay on thrd_current() returning an int

The C11 spec doesn't require thrd_t to be a particular object
format/type. I will need to change this type, I think, so don't assume
it's an int.

nodestack: refactor Node constructor

action: fixup style

model: refactor check_current_action, next thread computation

Pulling the 'get_next_thread()' computation out of
check_current_action() so that I can restructure the model-checker
execution a little.

threads: assert completion is only called once

We don't need to support the case that Thread::complete() is called
multiple times. We should instead ensure (ASSERT()) that it is only
called when the Thread is not already completed (and cleaned up).

threads: assert THREAD_COMPLETED is immutable

clean up some DEBUG() messages

We were printing may_read_from info twice.

Printing the current action when we get to check_current_action() is
helpful.

Printing scheduling based on priority is also useful, as we recently had
a "bug" involving fairness/priority.

Include the file name in DEBUG() prints, since we may have the same
function names in different files/classes.

nodestack: style

nodestack: add const

nodestack: do not allow Node with act == NULL

Since I removed the root 'NULL' Node, all Nodes will have a
corresponding action. Now, just ASSERT this in the constructor.

nodestack: don't create empty base node

We don't actually need an empty base node, since the first thread will
never be backtracked. But it does mean that we no longer assume that
every newly-constructed Node has a parent.

Note that this changes the number of executions performed for some
programs. Even though the model-checker should be deterministic, this is
not a bug, AFAICT. The discrepancy seems to come from a change in
scheduling, where the scheduler order may differ after reaching a
divergence point. This is caused by the fairness support which is hacked
into Node creation, so threads may gain priority sooner in the presence
of a useless Node. In fact, before this change, (almost?) every
execution caused a thread (typically thread 1) to gain priority due to
fairness. Now, we reach this condition much more occasionally.

I made measurements of the scheduling decisions based on priority for
the execution of:

 # ./run.sh test/linuxrwlocks.o -f 10 -m 2

Previously, threads gained priority 10042 times in 7906 executions (9947
of those were for thread 1, when it would shortly become disabled).

Now, threads gain priority 68 times in 8396 executions (thread 1 never
gains priority).

model: check for NULL parent Node

I'm editing the NodeStack to eliminate the empty Node. So we should
check to ensure that the Node has a parent before using it.

model: use helper 'get_thread()'

nodestack: print extra backtracking info

If we ever use the Node::print() method, print some extra info about
backtracking.

model: style fixups

model: add 'set_latest_backtrack()'

model: print bug reports only for feasible executions

We can assert a bug (e.g., uninitialized load) without having a feasible
exeuction. If this execution is later ruled infeasible, we don't need to
print the trace info.

test: uninit: remove @todo (bug fixed)

The previous bugfix allows this example to run properly, so remove the
@todo.

model: bugfix - mo_may_allow was too restrictive

This bugfix has the same rationale as with the following commit:

commit c2d7fa973e562c194eb732d8dc58ab7659b7a2ee

We do not want the potential reader to disqualify itself from reading a
future value; previously, this was fixed only for reads (not RMW's). But
we can experience the same problem with RMW's, which are both read and
write.

So, instead of using 'act != reader' as a special case for the is_read()
case, just use it as a breaking condition in addition to

   !(reader --hb-> act)

This is really intended anyway, since our happens-before is reflexive,
whereas it is irreflexive in the specification.

model: make dumpGraph 'const'

SUPPORT_MOD_ORDER_DUMP can't compile if dumpGraph() isn't const.

nodestack: fixup style

model: remove snapshotted 'nextThread'

The 'nextThread' field is no longer needed, since I've simplified
take_step().

model: pass current action as function argument

Diminish the use of 'priv->current_action', and instead pass it to
take_step() as an argument. At the same time, it is more obvious that we
do not need to reset priv->current_action to NULL.

model: simplify take_step()

Now that priv->current_action is always non-NULL (when reaching
take_step()), we can simplify the logic a bit. Also, rename some
variables.

model: force first thread to run immediately

Forcing the first thread to run immediately yields us our first
ModelAction, so we won't have to special-case the case that
current_action == NULL.

model: change guaranteed condition into ASSERT()

This guaranteed condition should only be included as an ASSERT(). This
gives a bonus, that the code becomes a little easier to read.

nodestack: rename 'iter' to 'head_idx'

nodestack: make 'iter' signed

iter will need to be negative when we allow the NodeStack to be empty.

schedule: spacing

nodestack: spacing

model: spacing

model: rename 'promise_index' to 'i'

The fuction looks cleaner if the loop variable is just a simple 'i'
index.

test/uninit: add an "uninit" test

This is a weird example, where we don't explicitly initialize y, but
synchronization should guarantee that it is initialized.

Right now, this example has a problem where we never see flag == 2.

model: return value from switch_to_master

action: refactor ATOMIC_READ printing

For ATOMIC_READ, we don't need a special case to print VALUE_NONE,
because any action where the value isn't explicitly set (e.g., all
ATOMIC_READ actions) default to VALUE_NONE. And if this 'default'
changes in the future, we would want to print it.

(Right now it's confusing, for instance, when we have a failed promise
execution, since the model-checker trace gives no indication of what the
promised value actually *was*. This should be fixed sometime.)

nodestack: add 'const'

impatomic: add C++ atomic_init()

According to N337, C++ has a C-like atomic_init() function, which was
left out of our impatomic header.

cyclegraph: uniform spacing, style

cyclegraph: bugfix - more SnapshotAlloc

common: bugfix - always display backtrace output

The stacktrace can be hidden if it doesn't go to 'model_out', instead of
'stdout'.

cyclegraph: bugfix - use model-checker's allocater for CycleNode::edges

This vector should use our SnapshotAlloc allocator, to avoid polluting
the user's memory allocator.

This solves an annoying bug that causes us to hit an ASSERT() when a
user's threads aren't allocated in the same location every execution.

cyclegraph: don't export CycleNode::edges directly, use accessors

The CycleNode::edges vector shouldn't be accessed directly; it should be
used through accessors, to hide implementation details. (Really, there's
a bug in the CycleNode that I need to fix, so I'm fixing this first.)

include the correct standard headers

Our own headers are including several of the wrong headers in the wrong
places. Move a few to place them more closely to their actual usage
location, and remove some others that are unused (e.g., <iostream>,
<cassert>, <csignal>).

spacing

model: don't create UNINIT actions for Threads, mutexes, etc.

ModelActions may be associated with fences, mutexes, threads, etc., all
of which never hit the "uninitialized" case. So, we shouldn't create
these UNINIT actions.

action: add is_atomic_var()

To check if a ModelAction is for a C/C++ atomic variable (vs. a Thread
action, a fake ModelChecker action, a mutex, a condition variable, etc.)

model/action: bugfix - UNINIT actions do not have a Node

Fix the one place where ModelChecker looks for a Node in an UNINIT
action.

This also adds an ASSERT() within ModelAction to prevent calling
get_node() on an UNINIT action. It is technically OK to call get_node()
in this case, but most callers don't check for NULL, so it's better to
just catch the ASSERT() for this unwanted special case.

model: remove old "uninitialized" bug check

The previously-existing bug check is not fully correct and has been
replaced with explicit UNINIT actions that, when read from, trigger a
bug assertion.

model: generate UNINIT actions as new atomic operations form

The first time an atomic variable is accessed, we need to add an
appropriate UNINIT action to the ModelChecker data structures. We assign
these ModelActions to the special model-checker thread (Thread 0). Note
that these actions will *not* appear in the NodeStack and will not be
explored in check_current_action, etc.

action: move ModelAction::get_node to action.cc

This function needs to expand a bit, so move it to the implementation
file.

model: add helper for allocating new UNINIT actions

These UNINIT actions will be special; they won't enter the NodeStack,
and so they need to be snapshot-allocated. That way, they will roll-back
with the execution, instead of requiring manual deletion.

mymemory: add placement new

I will need to use the placement new operator, if I want to allocate an
object with an allocator other than the one I established (SNAPSHOTALLOC
vs. MODELALLOC).

model: clear a ModelAction's reads-from properly

action: add ATOMIC_UNINIT type

Adding a new type of "uninitialized atomic" action, to serve as a store
which, if any load is able to "see" this store, constitutes an
uninitialized load - a bug in the user program. It has to act like a
store operation, but it triggers a bug (ModelChecker::assert_bug) if any
load tries to read from it.

Makefile: build dependencies in .*.o.d files

My previous attempts at fixing dependency generation actually cause
full recompilation every time a file is changed. Apparently, it'll work
best if each target object has its own dependency file. i.e., target
'model.o' has a corresponding '.model.o.d' which holds its dependency
information.

Makefile: rename variable to be more clear

model: refactoring + spacing

schedule: add is_sleep_set(thread)

schedule: add const

threads: add const

notes: fence: replace variables to match 29.8

I had some remaining edits to do for my notes 29.8, to match back with
the specification's variables (X, Y, A, B).

notes: fence: rename variables to match spec better

Originally, I purposely renamed these since I needed to introduce more
variables than were in the spec. But it turns out I can make this match
the spec pretty well.

Now: A, B, X, and Y fulfill the same roles as in the original C++
specification statements. I only introduce my new variable as W, when
needed. This also makes sense because W is a Write.

Also, I delete an extraneous paragraph that duplicated a piece of the
spec.

notes: fence: add release/acquire fence notes

I remove the copied-and-pasted algorithm pseudocode, since I didn't feel
like it was necessary to tweak the pseudocode to include fences. I might
change my mind later.