9 years agomodel: remove ModelChecker::is_infeasible_ignoreRMW()
Brian Norris [Fri, 25 Jan 2013 01:18:06 +0000 (17:18 -0800)]
model: remove ModelChecker::is_infeasible_ignoreRMW()

We don't make any special exceptions for this condition anymore, so drop
the function.

9 years agomodel: add immediate future value for RMW reordering
Brian Norris [Thu, 10 Jan 2013 01:39:24 +0000 (17:39 -0800)]
model: add immediate future value for RMW reordering

When RMW atomicity would otherwise rule an execution infeasible, we may
need to pass a future value back 'immediately,' to allow the
model-checker to effectively reorder the RMW's. For such cases, we don't
wait for all current promises to be resolved.

9 years agocyclegraph: detect cycles immediately
Brian Norris [Wed, 9 Jan 2013 23:26:47 +0000 (15:26 -0800)]
cyclegraph: detect cycles immediately

Previously, we have used a special case in CycleGraph to delay detection
of a mo-cycle (actually, an RMW atomicity violation) long enough so that
a RMW can "reorder" across another RMW by passing its future value.
Unfortunately, this only works some of the time, as the execution
*may or may not* be a feasible prefix which allows the sending of the
future value.

Instead, we need to pull this special case out of CycleGraph and (in
subsequent commits) will add a more proper solution in model.cc.

9 years agopromise: bugfix - a disabled thread should not be eliminated
Brian Norris [Thu, 24 Jan 2013 03:00:49 +0000 (19:00 -0800)]
promise: bugfix - a disabled thread should not be eliminated

Because we now only consider a subset of threads for satisfying
promises, we can have a disabled thread that still may satisfy a
promise; it could simply synchronize with another unrelated thread, then
continue to generate a write that can resolve the promise.

As a side effect, this change makes "has_failed()" much simpler.

9 years agomodel: modify promises on THREAD_{CREATE,FINISH}
Brian Norris [Thu, 24 Jan 2013 02:47:53 +0000 (18:47 -0800)]
model: modify promises on THREAD_{CREATE,FINISH}

When a thread is created it *must* pass its promise satisfiability to
its children.

When a thread finishes, we should remove it from all promises. This can
help prune a search early, if some read was depending only on the
finishing thread: we can then declare an unresolved promise.

9 years agopromise: associate Promises with a set of threads
Brian Norris [Thu, 24 Jan 2013 02:43:14 +0000 (18:43 -0800)]
promise: associate Promises with a set of threads

A Promise can be associated with a set of threads, so that we can
perform elimination more efficiently and precisely.

9 years agoaction: record future value
Brian Norris [Thu, 24 Jan 2013 02:05:28 +0000 (18:05 -0800)]
action: record future value

Future values don't currently show up in ModelAction (e.g., when
printing). We should set the value when we choose to read from a future

9 years agofuture_value: add thread ID parameter
Brian Norris [Thu, 24 Jan 2013 01:33:23 +0000 (17:33 -0800)]
future_value: add thread ID parameter

This just records the parameter for now, and makes it a distinction
between future values. Shouldn't affect model-checker behavior, except
for the introduction of extra future values: one for each thread which
writes the same value.

We calculate whether the writing thread exists at the time of the future
value and if not, find an ancestor thread which does.

9 years agonodestack: pass 'struct future_value' to add_future_value()
Brian Norris [Thu, 24 Jan 2013 01:24:11 +0000 (17:24 -0800)]
nodestack: pass 'struct future_value' to add_future_value()

This makes more sense than passing individual parameters. This way, we
construct our future_value in ModelChecker, then simply pass it to the

9 years agomodel: add const to get_thread(ModelAction *act)
Brian Norris [Thu, 24 Jan 2013 01:21:19 +0000 (17:21 -0800)]
model: add const to get_thread(ModelAction *act)

9 years agomodel: fixup indentation, spelling in comment
Brian Norris [Thu, 24 Jan 2013 01:02:46 +0000 (17:02 -0800)]
model: fixup indentation, spelling in comment

9 years agomodel: style
Brian Norris [Thu, 24 Jan 2013 00:51:39 +0000 (16:51 -0800)]
model: style

9 years agomodel: remove local variable
Brian Norris [Thu, 24 Jan 2013 00:34:00 +0000 (16:34 -0800)]
model: remove local variable

9 years agopromise: SnapshotAlloc for vector
Brian Norris [Wed, 23 Jan 2013 20:56:01 +0000 (12:56 -0800)]
promise: SnapshotAlloc for vector

We must ensure that any new memory allocated by the model-checker uses
our private snapshotting heap, not the user program's heap.

9 years agopromise: refactor has_failed()
Brian Norris [Wed, 23 Jan 2013 20:50:57 +0000 (12:50 -0800)]
promise: refactor has_failed()

has_failed() can simply call the thread_is_eliminated() function which
does much of the same computation already. We can drop the
'((int)i != promise_tid)' clause, since the 'promise_tid' thread must
already be eliminated.

9 years agopromise: move thread_is_eliminated()
Brian Norris [Wed, 23 Jan 2013 20:49:01 +0000 (12:49 -0800)]
promise: move thread_is_eliminated()

Should be in the implementation file, not the header.

9 years agopromise: rename has_sync_thread() -> thread_is_eliminated()
Brian Norris [Wed, 23 Jan 2013 20:36:28 +0000 (12:36 -0800)]
promise: rename has_sync_thread() -> thread_is_eliminated()

This function doesn't actually check for synchronization; there are
numerous ways to be eliminated.

9 years agopromise: rename check_promise() -> has_failed()
Brian Norris [Wed, 23 Jan 2013 19:53:33 +0000 (11:53 -0800)]
promise: rename check_promise() -> has_failed()

The name "check_promise" doesn't really tell what this function is
doing. It is actually checking if the promise is unresolvable.

9 years agopromise: refactor eliminate_thread()/check_promise()
Brian Norris [Wed, 23 Jan 2013 19:49:01 +0000 (11:49 -0800)]
promise: refactor eliminate_thread()/check_promise()

eliminate_thread() and check_promise() have near-duplicate code, for
checking if the promise has failed. This change makes them consistent
(check_promise() now knows to eliminate its own thread immediately) and
allows one function to simply call the other.

9 years agopromise: rename increment_threads() -> eliminate_thread()
Brian Norris [Wed, 23 Jan 2013 19:38:43 +0000 (11:38 -0800)]
promise: rename increment_threads() -> eliminate_thread()

This function name really doesn't describe what it does, in my opinion.
Update the name and add a description.

9 years agonodestack: add const
Brian Norris [Wed, 23 Jan 2013 19:10:20 +0000 (11:10 -0800)]
nodestack: add const

9 years agopromise: construct with a 'future_value' struct
Brian Norris [Wed, 23 Jan 2013 19:04:59 +0000 (11:04 -0800)]
promise: construct with a 'future_value' struct

Don't pass a bunch of parameters individually; just pass the struct.

9 years agonodestack/promise: move future_value struct, update headers
Brian Norris [Wed, 23 Jan 2013 19:02:38 +0000 (11:02 -0800)]
nodestack/promise: move future_value struct, update headers

struct future_value will be used more closely with class Promise, so put
it in the promise.h header. This requires some updates to other header

9 years agonodestack: pass writer ModelAction to add_future_value()
Brian Norris [Wed, 23 Jan 2013 18:43:48 +0000 (10:43 -0800)]
nodestack: pass writer ModelAction to add_future_value()

NodeStack will have to know a little more about who wrote the future
value, so just pass the ModelAction as a parameter.

9 years agonodestack: eliminate get_future_value_expiration()
Brian Norris [Wed, 23 Jan 2013 18:41:23 +0000 (10:41 -0800)]
nodestack: eliminate get_future_value_expiration()

We don't need separate accessors for each member of 'struct
future_value'. Just pass the entire struct.

9 years agonodestack: remove extra blank lines
Brian Norris [Wed, 23 Jan 2013 18:30:46 +0000 (10:30 -0800)]
nodestack: remove extra blank lines

9 years agoremove #include <list>
Brian Norris [Wed, 23 Jan 2013 18:17:44 +0000 (10:17 -0800)]
remove #include <list>

STL lists aren't used here anymore.

9 years agonodestack: improve debug print() method
Brian Norris [Wed, 23 Jan 2013 00:49:11 +0000 (16:49 -0800)]
nodestack: improve debug print() method

Print the contents of the future values and may-read-from set, if we're
printing the NodeStack for debugging purposes.

9 years agofix bug in promise handling code...
Brian Demsky [Wed, 23 Jan 2013 00:31:16 +0000 (16:31 -0800)]
fix bug in promise handling code...

if any promise for a thread resolved, we assumed that the corresponding
write happened after all promises for that threads...clearly doesn't
need to be the case...

[Brian Norris:] This fixes some bugs where we don't see all the expected
behaviors: e.g., with

  ./run.sh test/rmwprog.o -- 3

Now we see all 20 behaviors.

9 years agopromise: fixup style
Brian Norris [Wed, 23 Jan 2013 00:24:44 +0000 (16:24 -0800)]
promise: fixup style

9 years agotest: rmwprog: support command-line argument
Brian Norris [Tue, 22 Jan 2013 19:08:06 +0000 (11:08 -0800)]
test: rmwprog: support command-line argument

This test can easily be extended to allow more than 2 atomic increments
per thread. For instance, it's interesting to see the model-checker
behavior for 4 increments per thread. Now, you can do this with a simple
numeric command-line argument that gets passed to the user program.

Example - run rmwprog with 4 increments per thread, viewing the
execution traces verbosely:

  ./run.sh test/rmwprog.o -v -- 4

9 years agonodestack: improve debug prints
Brian Norris [Sat, 19 Jan 2013 00:43:02 +0000 (16:43 -0800)]
nodestack: improve debug prints

9 years agoschedule: improve scheduler printing
Brian Norris [Sat, 19 Jan 2013 00:38:55 +0000 (16:38 -0800)]
schedule: improve scheduler printing

Print more detailed, informative info about the Scheduler, still on a
single line.

9 years agoschedule: allow Schedule::print() even in non-DEBUG build
Brian Norris [Sat, 19 Jan 2013 00:30:26 +0000 (16:30 -0800)]
schedule: allow Schedule::print() even in non-DEBUG build

For instance, printing from w/in gdb

9 years agomodel: bugfix - sleep sets are NOT directly compatible with DPOR
Brian Norris [Thu, 17 Jan 2013 01:42:57 +0000 (17:42 -0800)]
model: bugfix - sleep sets are NOT directly compatible with DPOR

We failed to incorporate changes from the POPL'05 DPOR paper's addendum,
preventing us from seeing all behaviors in some test programs. This
fixes that.

9 years agolitmus: iriw: allow command-line switch 's' for seq_cst
Brian Norris [Wed, 16 Jan 2013 08:24:48 +0000 (00:24 -0800)]
litmus: iriw: allow command-line switch 's' for seq_cst

The IRIW litmus test fails if we make it seq_cst; we don't see all 15
potential behaviors. Run with:

  # release/acquire litmus test
  ./run.sh test/litmus/iriw.o -v

  # seq_cst litmus test
  ./run.sh test/litmus/iriw.o -v -- s

9 years agolitmus: iriw: use release/acquire, not release/relaxed
Brian Norris [Wed, 16 Jan 2013 07:57:45 +0000 (23:57 -0800)]
litmus: iriw: use release/acquire, not release/relaxed

9 years agotests: litmus: link up Makefile properly
Brian Norris [Wed, 16 Jan 2013 07:43:44 +0000 (23:43 -0800)]
tests: litmus: link up Makefile properly

Now this builds the litmus tests properly.

9 years agotest: litmus: add litmus tests from Nitpicking C++
Brian Norris [Tue, 15 Jan 2013 20:44:47 +0000 (12:44 -0800)]
test: litmus: add litmus tests from Nitpicking C++

This adds most of the litmus tests from Nitpicking C++ Concurrency. Note
that it leaves out the 'consume' tests (replacing it with the
also-mentioned release/acquire test). It doesn't test the seq_cst
results, although I could provide command-line switches to do so...

9 years agotest: Makefile: add $(BASE) variable
Brian Norris [Tue, 15 Jan 2013 20:30:33 +0000 (12:30 -0800)]
test: Makefile: add $(BASE) variable

Makes this Makefile a little more flexible

9 years agomodel: reformat execution trace prints
Brian Norris [Thu, 10 Jan 2013 18:54:02 +0000 (10:54 -0800)]
model: reformat execution trace prints

Bring the "INFEASIBLE" message together with the "Execution #" message,
to make the log more compact and readable (e.g., grep for "Execution"
will give you some regularly-patterned, useful information).

9 years agomodel: spelling mistake
Brian Norris [Thu, 10 Jan 2013 01:50:57 +0000 (17:50 -0800)]
model: spelling mistake

9 years agomodel: fixup "infeasible" messages
Brian Norris [Wed, 9 Jan 2013 23:54:04 +0000 (15:54 -0800)]
model: fixup "infeasible" messages

These messages should be much more compact and targeted. Currently, we
either get no infeasibility messages (when verbose=0) or we get messages
every time is_infeasible() is executed. Neither is helpful for debugging,
since the infeasibility may be temporary, as we choose a new path for
execution on the fly. So instead, just print the infeasibility message
at the end of infeasible executions.

Also, rather than spread the messages across multiple lines, just put
them together into a single string.

9 years agocyclegraph: add documentation
Brian Norris [Wed, 9 Jan 2013 22:07:07 +0000 (14:07 -0800)]
cyclegraph: add documentation

9 years agocyclegraph: remove redundant code
Brian Norris [Wed, 9 Jan 2013 21:47:57 +0000 (13:47 -0800)]
cyclegraph: remove redundant code

The edgeCreatesCycle() function can simply be reduced to
checkReachable(), since checkReachable() will detect "to == from".

9 years agocyclegraph: add edgeCreatesCycle() function
Brian Norris [Wed, 9 Jan 2013 00:40:29 +0000 (16:40 -0800)]
cyclegraph: add edgeCreatesCycle() function

This is repeated code, so make it a function.

9 years agocyclegraph: add const
Brian Norris [Wed, 9 Jan 2013 00:29:17 +0000 (16:29 -0800)]
cyclegraph: add const

9 years agomodel: add 'add_future_value()' wrapper
Brian Norris [Tue, 8 Jan 2013 02:22:57 +0000 (18:22 -0800)]
model: add 'add_future_value()' wrapper

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

9 years agomodel: add PendingFutureValue constructor
Brian Norris [Tue, 8 Jan 2013 01:38:25 +0000 (17:38 -0800)]
model: add PendingFutureValue constructor

9 years agonew test case
Brian Demsky [Tue, 8 Jan 2013 00:55:00 +0000 (16:55 -0800)]
new test case

9 years agocyclegraph: add back edges to CycleNode
Brian Norris [Fri, 4 Jan 2013 19:05:10 +0000 (11:05 -0800)]
cyclegraph: add back edges to CycleNode

9 years agohashtable: style
Brian Norris [Fri, 4 Jan 2013 18:09:29 +0000 (10:09 -0800)]
hashtable: style

9 years agocyclegraph: add putNode() helper
Brian Norris [Fri, 4 Jan 2013 17:53:04 +0000 (09:53 -0800)]
cyclegraph: add putNode() helper

9 years agohashtable: style
Brian Norris [Fri, 4 Jan 2013 01:01:09 +0000 (17:01 -0800)]
hashtable: style

9 years agopromise: style fixup
Brian Norris [Fri, 4 Jan 2013 00:24:54 +0000 (16:24 -0800)]
promise: style fixup

9 years agocyclegraph: fix insignificant memory leak
Brian Norris [Fri, 4 Jan 2013 00:18:10 +0000 (16:18 -0800)]
cyclegraph: fix insignificant memory leak

9 years agocyclegraph: small cleanup
Brian Norris [Thu, 3 Jan 2013 22:00:37 +0000 (14:00 -0800)]
cyclegraph: small cleanup

9 years agohashtable: add const
Brian Norris [Thu, 3 Jan 2013 22:30:18 +0000 (14:30 -0800)]
hashtable: add const

9 years agohashtable: fixup style
Brian Norris [Thu, 3 Jan 2013 22:29:16 +0000 (14:29 -0800)]
hashtable: fixup style

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

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

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

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

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

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