c11tester.git
9 years agosnapshot: more renaming
Brian Norris [Thu, 3 Jan 2013 20:24:34 +0000 (12:24 -0800)]
snapshot: more renaming

9 years agosnapshot-interface: bugfix - reorder constructor params
Brian Norris [Thu, 3 Jan 2013 20:17:37 +0000 (12:17 -0800)]
snapshot-interface: bugfix - reorder constructor params

The snapshot_id should come first.

9 years agosnapshot-interface: rename, clean up
Brian Norris [Thu, 3 Jan 2013 20:14:32 +0000 (12:14 -0800)]
snapshot-interface: rename, clean up

9 years agosnapshot-interface: change hand-coded stack to vector
Brian Norris [Thu, 3 Jan 2013 19:59:13 +0000 (11:59 -0800)]
snapshot-interface: change hand-coded stack to vector

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

9 years agosnapshot: turn C++ interface into C interface
Brian Norris [Thu, 3 Jan 2013 19:37:51 +0000 (11:37 -0800)]
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).

9 years agofixup style
Brian Norris [Thu, 3 Jan 2013 18:31:00 +0000 (10:31 -0800)]
fixup style

9 years agosnapshot: more renaming
Brian Norris [Thu, 3 Jan 2013 03:18:43 +0000 (19:18 -0800)]
snapshot: more renaming

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

9 years agosnapshot: add (unused) mprot_snapshotter destructor
Brian Norris [Thu, 3 Jan 2013 03:10:28 +0000 (19:10 -0800)]
snapshot: add (unused) mprot_snapshotter destructor

9 years agosnapshot: rename HandlePF -> mprot_handle_pf
Brian Norris [Thu, 3 Jan 2013 03:07:29 +0000 (19:07 -0800)]
snapshot: rename HandlePF -> mprot_handle_pf

9 years agosnapshot: add constructor for mprot_snapshotter
Brian Norris [Thu, 3 Jan 2013 03:06:10 +0000 (19:06 -0800)]
snapshot: add constructor for mprot_snapshotter

9 years agosnapshot: separate struct SnapShot naming
Brian Norris [Thu, 3 Jan 2013 02:45:25 +0000 (18:45 -0800)]
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.

9 years agosnapshot: edit capitalization in comment
Brian Norris [Thu, 3 Jan 2013 02:33:58 +0000 (18:33 -0800)]
snapshot: edit capitalization in comment

9 years agosnapshot: combine public interfaces
Brian Norris [Thu, 3 Jan 2013 02:31:38 +0000 (18:31 -0800)]
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.

9 years agosnapshot: split up fork-based and mprotect-based snapshotting
Brian Norris [Thu, 3 Jan 2013 02:14:17 +0000 (18:14 -0800)]
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.

9 years agosnapshot: remove SSDEBUG
Brian Norris [Thu, 3 Jan 2013 01:54:45 +0000 (17:54 -0800)]
snapshot: remove SSDEBUG

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

9 years agodissolve snapshotimp.h
Brian Norris [Thu, 3 Jan 2013 01:48:28 +0000 (17:48 -0800)]
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.

9 years agomymemory/snapshot: rearrange snapshot implementation
Brian Norris [Thu, 3 Jan 2013 01:38:19 +0000 (17:38 -0800)]
mymemory/snapshot: rearrange snapshot implementation

Move some implementation details back to snapshot.cc.

9 years agosnapshotimp: move macros to fork-based
Brian Norris [Thu, 3 Jan 2013 01:21:33 +0000 (17:21 -0800)]
snapshotimp: move macros to fork-based

These macros are only used for fork-based snapshotting.

9 years agosnapshot: change 'struct SnapShotPage' to a simple typedef
Brian Norris [Thu, 3 Jan 2013 00:41:35 +0000 (16:41 -0800)]
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.

9 years agofixup style
Brian Norris [Wed, 2 Jan 2013 23:43:54 +0000 (15:43 -0800)]
fixup style

9 years agothreads: change thrd_t to store Thread pointer
Brian Norris [Thu, 20 Dec 2012 00:03:45 +0000 (16:03 -0800)]
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.

9 years agoaction: add get_thread_operand() method
Brian Norris [Wed, 19 Dec 2012 23:26:47 +0000 (15:26 -0800)]
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.

9 years agomodel: use get_thread(curr) instead of get_current_thread()
Brian Norris [Thu, 20 Dec 2012 00:50:11 +0000 (16:50 -0800)]
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.

9 years agotest: don't relay on thrd_current() returning an int
Brian Norris [Wed, 19 Dec 2012 06:48:21 +0000 (22:48 -0800)]
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.

9 years agonodestack: refactor Node constructor
Brian Norris [Wed, 19 Dec 2012 06:18:03 +0000 (22:18 -0800)]
nodestack: refactor Node constructor

9 years agoaction: fixup style
Brian Norris [Wed, 19 Dec 2012 01:31:55 +0000 (17:31 -0800)]
action: fixup style

9 years agomodel: refactor check_current_action, next thread computation
Brian Norris [Tue, 18 Dec 2012 20:46:48 +0000 (12:46 -0800)]
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.

9 years agothreads: assert completion is only called once
Brian Norris [Tue, 18 Dec 2012 22:08:19 +0000 (14:08 -0800)]
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).

9 years agothreads: assert THREAD_COMPLETED is immutable
Brian Norris [Tue, 9 Oct 2012 17:42:50 +0000 (10:42 -0700)]
threads: assert THREAD_COMPLETED is immutable

9 years agoclean up some DEBUG() messages
Brian Norris [Sat, 15 Dec 2012 01:28:40 +0000 (17:28 -0800)]
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.

9 years agonodestack: style
Brian Norris [Sat, 15 Dec 2012 00:34:20 +0000 (16:34 -0800)]
nodestack: style

9 years agonodestack: add const
Brian Norris [Sat, 15 Dec 2012 00:31:49 +0000 (16:31 -0800)]
nodestack: add const

9 years agonodestack: do not allow Node with act == NULL
Brian Norris [Sat, 15 Dec 2012 00:29:31 +0000 (16:29 -0800)]
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.

9 years agonodestack: don't create empty base node
Brian Norris [Thu, 13 Dec 2012 03:57:44 +0000 (19:57 -0800)]
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).

9 years agomodel: check for NULL parent Node
Brian Norris [Thu, 13 Dec 2012 02:29:30 +0000 (18:29 -0800)]
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.

9 years agomodel: use helper 'get_thread()'
Brian Norris [Thu, 13 Dec 2012 23:31:14 +0000 (15:31 -0800)]
model: use helper 'get_thread()'

9 years agonodestack: print extra backtracking info
Brian Norris [Thu, 13 Dec 2012 23:18:12 +0000 (15:18 -0800)]
nodestack: print extra backtracking info

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

9 years agomodel: style fixups
Brian Norris [Thu, 13 Dec 2012 23:00:29 +0000 (15:00 -0800)]
model: style fixups

9 years agomodel: add 'set_latest_backtrack()'
Brian Norris [Thu, 13 Dec 2012 22:47:59 +0000 (14:47 -0800)]
model: add 'set_latest_backtrack()'

9 years agomodel: print bug reports only for feasible executions
Brian Norris [Thu, 13 Dec 2012 08:36:04 +0000 (00:36 -0800)]
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.

9 years agotest: uninit: remove @todo (bug fixed)
Brian Norris [Thu, 13 Dec 2012 08:35:25 +0000 (00:35 -0800)]
test: uninit: remove @todo (bug fixed)

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

9 years agomodel: bugfix - mo_may_allow was too restrictive
Brian Norris [Thu, 13 Dec 2012 08:13:08 +0000 (00:13 -0800)]
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.

9 years agomodel: make dumpGraph 'const'
Brian Norris [Thu, 13 Dec 2012 08:12:28 +0000 (00:12 -0800)]
model: make dumpGraph 'const'

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

9 years agonodestack: fixup style
Brian Norris [Thu, 13 Dec 2012 07:19:15 +0000 (23:19 -0800)]
nodestack: fixup style

9 years agomodel: remove snapshotted 'nextThread'
Brian Norris [Thu, 13 Dec 2012 03:40:56 +0000 (19:40 -0800)]
model: remove snapshotted 'nextThread'

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

9 years agomodel: pass current action as function argument
Brian Norris [Thu, 13 Dec 2012 03:31:10 +0000 (19:31 -0800)]
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.

9 years agomodel: simplify take_step()
Brian Norris [Thu, 13 Dec 2012 03:25:02 +0000 (19:25 -0800)]
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.

9 years agomodel: force first thread to run immediately
Brian Norris [Thu, 13 Dec 2012 03:16:43 +0000 (19:16 -0800)]
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.

9 years agomodel: change guaranteed condition into ASSERT()
Brian Norris [Thu, 13 Dec 2012 02:27:27 +0000 (18:27 -0800)]
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.

9 years agonodestack: rename 'iter' to 'head_idx'
Brian Norris [Thu, 13 Dec 2012 02:03:23 +0000 (18:03 -0800)]
nodestack: rename 'iter' to 'head_idx'

9 years agonodestack: make 'iter' signed
Brian Norris [Thu, 13 Dec 2012 01:57:28 +0000 (17:57 -0800)]
nodestack: make 'iter' signed

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

9 years agoschedule: spacing
Brian Norris [Thu, 13 Dec 2012 01:15:46 +0000 (17:15 -0800)]
schedule: spacing

9 years agonodestack: spacing
Brian Norris [Thu, 13 Dec 2012 00:21:56 +0000 (16:21 -0800)]
nodestack: spacing

9 years agomodel: spacing
Brian Norris [Thu, 13 Dec 2012 00:07:01 +0000 (16:07 -0800)]
model: spacing

9 years agomodel: rename 'promise_index' to 'i'
Brian Norris [Wed, 12 Dec 2012 23:49:29 +0000 (15:49 -0800)]
model: rename 'promise_index' to 'i'

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

9 years agotest/uninit: add an "uninit" test
Brian Norris [Wed, 12 Dec 2012 02:38:16 +0000 (18:38 -0800)]
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.

9 years agomodel: return value from switch_to_master
Brian Norris [Wed, 12 Dec 2012 02:08:31 +0000 (18:08 -0800)]
model: return value from switch_to_master

9 years agoaction: refactor ATOMIC_READ printing
Brian Norris [Wed, 12 Dec 2012 02:05:51 +0000 (18:05 -0800)]
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.)

9 years agonodestack: add 'const'
Brian Norris [Wed, 12 Dec 2012 01:44:04 +0000 (17:44 -0800)]
nodestack: add 'const'

9 years agoimpatomic: add C++ atomic_init()
Brian Norris [Wed, 12 Dec 2012 00:16:53 +0000 (16:16 -0800)]
impatomic: add C++ atomic_init()

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

9 years agocyclegraph: uniform spacing, style
Brian Norris [Tue, 11 Dec 2012 23:22:56 +0000 (15:22 -0800)]
cyclegraph: uniform spacing, style

9 years agocyclegraph: bugfix - more SnapshotAlloc
Brian Norris [Tue, 11 Dec 2012 23:10:40 +0000 (15:10 -0800)]
cyclegraph: bugfix - more SnapshotAlloc

9 years agocommon: bugfix - always display backtrace output
Brian Norris [Tue, 11 Dec 2012 20:59:39 +0000 (12:59 -0800)]
common: bugfix - always display backtrace output

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

9 years agocyclegraph: bugfix - use model-checker's allocater for CycleNode::edges
Brian Norris [Tue, 11 Dec 2012 20:56:59 +0000 (12:56 -0800)]
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.

9 years agocyclegraph: don't export CycleNode::edges directly, use accessors
Brian Norris [Tue, 11 Dec 2012 20:55:28 +0000 (12:55 -0800)]
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.)

9 years agoinclude the correct standard headers
Brian Norris [Tue, 11 Dec 2012 19:11:45 +0000 (11:11 -0800)]
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>).

9 years agospacing
Brian Norris [Sat, 8 Dec 2012 02:40:59 +0000 (18:40 -0800)]
spacing

9 years agomodel: don't create UNINIT actions for Threads, mutexes, etc.
Brian Norris [Fri, 7 Dec 2012 06:57:02 +0000 (22:57 -0800)]
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.

9 years agoaction: add is_atomic_var()
Brian Norris [Fri, 7 Dec 2012 06:55:38 +0000 (22:55 -0800)]
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.)

9 years agomodel/action: bugfix - UNINIT actions do not have a Node
Brian Norris [Fri, 7 Dec 2012 06:53:07 +0000 (22:53 -0800)]
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.

9 years agomodel: remove old "uninitialized" bug check
Brian Norris [Fri, 7 Dec 2012 06:45:23 +0000 (22:45 -0800)]
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.

9 years agomodel: generate UNINIT actions as new atomic operations form
Brian Norris [Fri, 7 Dec 2012 06:42:10 +0000 (22:42 -0800)]
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.

9 years agoaction: move ModelAction::get_node to action.cc
Brian Norris [Fri, 7 Dec 2012 06:40:05 +0000 (22:40 -0800)]
action: move ModelAction::get_node to action.cc

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

9 years agomodel: add helper for allocating new UNINIT actions
Brian Norris [Fri, 7 Dec 2012 06:03:53 +0000 (22:03 -0800)]
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.

9 years agomymemory: add placement new
Brian Norris [Fri, 7 Dec 2012 05:50:33 +0000 (21:50 -0800)]
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).

9 years agomodel: clear a ModelAction's reads-from properly
Brian Norris [Fri, 7 Dec 2012 06:02:03 +0000 (22:02 -0800)]
model: clear a ModelAction's reads-from properly

9 years agoaction: add ATOMIC_UNINIT type
Brian Norris [Fri, 7 Dec 2012 05:12:29 +0000 (21:12 -0800)]
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.

9 years agoMakefile: build dependencies in .*.o.d files
Brian Norris [Thu, 6 Dec 2012 22:10:28 +0000 (14:10 -0800)]
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.

9 years agoMakefile: rename variable to be more clear
Brian Norris [Thu, 6 Dec 2012 22:19:45 +0000 (14:19 -0800)]
Makefile: rename variable to be more clear

9 years agomodel: refactoring + spacing
Brian Norris [Thu, 6 Dec 2012 23:30:44 +0000 (15:30 -0800)]
model: refactoring + spacing

9 years agoschedule: add is_sleep_set(thread)
Brian Norris [Thu, 6 Dec 2012 23:30:24 +0000 (15:30 -0800)]
schedule: add is_sleep_set(thread)

9 years agoschedule: add const
Brian Norris [Thu, 6 Dec 2012 23:29:26 +0000 (15:29 -0800)]
schedule: add const

9 years agothreads: add const
Brian Norris [Thu, 6 Dec 2012 23:26:30 +0000 (15:26 -0800)]
threads: add const

9 years agonotes: fence: replace variables to match 29.8
Brian Norris [Thu, 6 Dec 2012 20:13:25 +0000 (12:13 -0800)]
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).

9 years agonotes: fence: rename variables to match spec better
Brian Norris [Thu, 6 Dec 2012 19:51:15 +0000 (11:51 -0800)]
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.

9 years agonotes: fence: add release/acquire fence notes
Brian Norris [Thu, 6 Dec 2012 00:41:17 +0000 (16:41 -0800)]
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.

9 years agonotes: fence: more updates
Brian Norris [Wed, 5 Dec 2012 23:35:02 +0000 (15:35 -0800)]
notes: fence: more updates

9 years agodoc: notes: fence: update fence notes
Brian Norris [Wed, 5 Dec 2012 23:29:32 +0000 (15:29 -0800)]
doc: notes: fence: update fence notes

The backtracking and seq-cst/MO constraints are complete, but the
release/acquire, etc.

9 years agomodel: stop thread-trace search once edge is added
Brian Norris [Wed, 5 Dec 2012 20:20:31 +0000 (12:20 -0800)]
model: stop thread-trace search once edge is added

Once an edge has been added from 'act' to the current thread (or the
'rf' thread), we don't need to continue to search for more edges.

9 years agodoc: notes: add fences note
Brian Norris [Wed, 5 Dec 2012 02:23:52 +0000 (18:23 -0800)]
doc: notes: add fences note

This note is incomplete.

9 years agomodel: fix bugs in fence-acquire synchronization
Brian Norris [Wed, 5 Dec 2012 00:40:32 +0000 (16:40 -0800)]
model: fix bugs in fence-acquire synchronization

(1) In the fence-acquire search, we can't stop searching for prior loads
    when we reach the current action; we must continue to search until
    we find a *different* fence-acquire (or the beginning of the thread)

(2) The load action does not synchronize in fence-acquire
    synchronization: the fence should synchronize. This was just a typo
    (act vs. curr).

9 years agoimpatomic: move atomic_{thread,signal}_fence() to namespace std
Brian Norris [Wed, 5 Dec 2012 00:04:40 +0000 (16:04 -0800)]
impatomic: move atomic_{thread,signal}_fence() to namespace std

9 years agorun.sh: print the command that runs
Brian Norris [Tue, 4 Dec 2012 23:36:40 +0000 (15:36 -0800)]
run.sh: print the command that runs

This will help understanding typos, script bugs, etc.

9 years agomodel: add process_fence()
Brian Norris [Tue, 4 Dec 2012 02:30:18 +0000 (18:30 -0800)]
model: add process_fence()

process_fence() will only handle fence-acquire. Fence-relaxed is a
no-op; fence-release is only logged for later use; and fence-seq-cst
takes release/acquire semantics, plus some mo-graph rules which apply to
reads/reads (see {r,w}_modification_order).

9 years agomodel: distinguish between 'read' and 'acquire' in release sequences
Brian Norris [Tue, 4 Dec 2012 23:14:29 +0000 (15:14 -0800)]
model: distinguish between 'read' and 'acquire' in release sequences

When using fences, we may have a fence-acquire preceded by a non-acquire
load, where the load takes part in a "hypothetical release sequence" (as
named by Mathematizing C++). So, I add a parameter to
get_release_seq_heads() and to struct release_seq so that we record the
'acquire' operation separately from the 'read'.

For our traditional release sequences, 'acquire' and 'read' will be the
same ModelAction. But fence-acquire support will utilize distinct
actions.

9 years agomodel: add read-acquire/fence-release support
Brian Norris [Tue, 4 Dec 2012 22:08:13 +0000 (14:08 -0800)]
model: add read-acquire/fence-release support

C++ Section 29.8, statement 3: gives conditions under which a
read-acquire and fence-release might synchronize. It's easy enough to
integrate into our existing release sequence code.

9 years agoaction: add is_thread_start()
Brian Norris [Tue, 4 Dec 2012 02:29:42 +0000 (18:29 -0800)]
action: add is_thread_start()

9 years agomodel: privatize a few interfaces
Brian Norris [Tue, 4 Dec 2012 02:23:22 +0000 (18:23 -0800)]
model: privatize a few interfaces

These functions were only public for ModelAction::read_from, which has
now been internalized into ModelChecker.

9 years agomodel/action: move complicated read_from logic into model.cc
Brian Norris [Tue, 4 Dec 2012 02:14:55 +0000 (18:14 -0800)]
model/action: move complicated read_from logic into model.cc

The release sequence wrapper logic will only get more complicated, so
rather than spreading across two files and exporting more interfaces,
just integrate into ModelChecker.

9 years agomodel: record last fence-release from each thread
Brian Norris [Tue, 4 Dec 2012 00:51:43 +0000 (16:51 -0800)]
model: record last fence-release from each thread