10 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

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

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

10 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

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

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

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

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

10 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

10 years agoaction: record last fence release from the current thread
Brian Norris [Tue, 4 Dec 2012 00:43:19 +0000 (16:43 -0800)]
action: record last fence release from the current thread

10 years agomodel: remove extraneous copy-and-paste
Brian Norris [Tue, 4 Dec 2012 00:58:58 +0000 (16:58 -0800)]
model: remove extraneous copy-and-paste

10 years agomodel: add seq-cst fence rules
Brian Norris [Tue, 4 Dec 2012 00:17:08 +0000 (16:17 -0800)]
model: add seq-cst fence rules

Add mo_graph constraints, from statements 4-6 in C++ Section 29.3. There
are probably more constraints we can choose for building may-read-from /
future values.

10 years agoaction/model: backtrack for seq-cst and release/acquire fences
Brian Norris [Tue, 4 Dec 2012 00:00:33 +0000 (16:00 -0800)]
action/model: backtrack for seq-cst and release/acquire fences

Extends backtracking support to explore all interleavings of conflicting
seq-cst fences and potentially-synchronizing write/read/fence pairs.

10 years agoaction: allow fence ModelActions to have location == NULL
Brian Norris [Mon, 3 Dec 2012 21:27:58 +0000 (13:27 -0800)]
action: allow fence ModelActions to have location == NULL

10 years agomodel: refactor build_reads_from_past
Brian Norris [Mon, 3 Dec 2012 21:05:55 +0000 (13:05 -0800)]
model: refactor build_reads_from_past

Just rearrange the logic a little, to prepare for some other additions.

10 years agomodel: add get_last_seq_cst_fence
Brian Norris [Sat, 1 Dec 2012 02:46:28 +0000 (18:46 -0800)]
model: add get_last_seq_cst_fence

10 years agomodel: rename last_seq_cst -> last_sc_write
Brian Norris [Mon, 3 Dec 2012 19:36:50 +0000 (11:36 -0800)]
model: rename last_seq_cst -> last_sc_write

10 years agomodel: rename get_last_seq_cst -> get_last_seq_cst_write
Brian Norris [Sat, 1 Dec 2012 01:54:58 +0000 (17:54 -0800)]
model: rename get_last_seq_cst -> get_last_seq_cst_write

10 years agoimpatomic: add atomic_{thread,signal}_fence() definitions
Brian Norris [Fri, 30 Nov 2012 23:05:44 +0000 (15:05 -0800)]
impatomic: add atomic_{thread,signal}_fence() definitions

The impatomic.h header is outdated. Additional information from the ISO
papers N2633, N2731, and N2752 have limited the "fence()" support to
just these two functions.

10 years agoimpatomic: remove fence member functions
Brian Norris [Fri, 30 Nov 2012 22:57:39 +0000 (14:57 -0800)]
impatomic: remove fence member functions

Recent C/C++ drafts do not include fence() as a member function for any
object. All fences apply globally (not to any particular object).

[ These changes came in the ISO papers N2633, N2731, N2752 ]

So, I discard any reference to a fence that is associated with an object
(i.e., as a member of an object or with an object parameter).

I will implement a replacement shortly, which just uses the
_ATOMIC_FENCE_(order) macro.

10 years agoMakefile: fix dependency generation
Brian Norris [Wed, 21 Nov 2012 02:27:20 +0000 (18:27 -0800)]
Makefile: fix dependency generation

- Don't regenerate make.deps for 'make clean' target
- Place the dependency on make.deps at the correct level; all "%.o"
  generations depend on it, not the top-level 'all' target

10 years agomodel: remove <list> include
Brian Norris [Tue, 20 Nov 2012 04:53:46 +0000 (20:53 -0800)]
model: remove <list> include

10 years agomodel: add const
Brian Norris [Tue, 20 Nov 2012 04:51:04 +0000 (20:51 -0800)]
model: add const

10 years agoschedule: rename get_enabled() -> get_enabled_array()
Brian Norris [Tue, 20 Nov 2012 04:40:30 +0000 (20:40 -0800)]
schedule: rename get_enabled() -> get_enabled_array()

This function actually returns the array, not a single "enabled" status.
(There's a separate get_enabled() method for getting a single status.)

10 years agomodel: rename isfinalfeasible -> is_feasible_prefix_ignore_relseq
Brian Norris [Tue, 20 Nov 2012 04:33:53 +0000 (20:33 -0800)]
model: rename isfinalfeasible -> is_feasible_prefix_ignore_relseq

This more accurately reflects its use case and the fact that it is a
slightly-weaker version of isfeasibleprefix(). Also, I integrate it into
isfeasibleprefix(), to avoid re-writing the same conditions.

10 years agomodel: replace isfinalfeasible() with stronger check
Brian Norris [Tue, 20 Nov 2012 04:29:34 +0000 (20:29 -0800)]
model: replace isfinalfeasible() with stronger check

The stronger isfeasibleprefix() check is not strictly necessary in these
cases, since we can ensure that promises are resolved before executing
these, but it make sense to have a well-defined "strength" to these
feasibility properties, then use the strongest strength that is useful.

10 years agomodel: privatize, move isfinalfeasible()
Brian Norris [Tue, 20 Nov 2012 04:17:23 +0000 (20:17 -0800)]
model: privatize, move isfinalfeasible()

This function should go with all the other "feasible" functions.

10 years agomodel: rename some 'isfeasible...' functions to 'is_infeasible...'
Brian Norris [Tue, 20 Nov 2012 04:11:21 +0000 (20:11 -0800)]
model: rename some 'isfeasible...' functions to 'is_infeasible...'

These functions can be more accurately described as checking
*infeasibility*, not necessarily feasibility. This helps clarify their
purpose, at least for my understanding.

10 years agomodel: privatize some functions
Brian Norris [Tue, 20 Nov 2012 04:03:35 +0000 (20:03 -0800)]
model: privatize some functions

Just kill finish_execution() while we're at it.

10 years agomain: remove #include's
Brian Norris [Tue, 20 Nov 2012 03:47:11 +0000 (19:47 -0800)]
main: remove #include's

10 years agomain: remove "pass-by-reference" editing in parse_options()
Brian Norris [Tue, 20 Nov 2012 03:40:12 +0000 (19:40 -0800)]
main: remove "pass-by-reference" editing in parse_options()

parse_options() can simply pass the argc/argv variables through the
model_checker_params struct now.

Also, document a few things.

10 years agothreads: remove todo (long overdue)
Brian Norris [Tue, 20 Nov 2012 03:33:32 +0000 (19:33 -0800)]
threads: remove todo (long overdue)

10 years agomain/model: move full user-program execution to ModelChecker::run
Brian Norris [Tue, 20 Nov 2012 03:32:22 +0000 (19:32 -0800)]
main/model: move full user-program execution to ModelChecker::run

We don't really need the top-level ModelChecker execution loop to be in
main.cc; it should be exposed simply as a run() method.

10 years agomodel/main: add argc/argv parameter
Brian Norris [Tue, 20 Nov 2012 03:30:41 +0000 (19:30 -0800)]
model/main: add argc/argv parameter

ModelChecker will take care of launching the user program soon.

10 years agomodel: move flags to private 'model_snapshot_members'
Brian Norris [Tue, 20 Nov 2012 03:15:47 +0000 (19:15 -0800)]
model: move flags to private 'model_snapshot_members'

10 years agomodel: add model_snapshot_members constructor/destructor
Brian Norris [Tue, 20 Nov 2012 03:04:33 +0000 (19:04 -0800)]
model: add model_snapshot_members constructor/destructor

10 years agomodel: privatize set_assert()
Brian Norris [Tue, 20 Nov 2012 02:40:50 +0000 (18:40 -0800)]
model: privatize set_assert()

10 years agorun.sh: rewrite script to handle options more gracefully
Brian Norris [Tue, 20 Nov 2012 00:39:36 +0000 (16:39 -0800)]
run.sh: rewrite script to handle options more gracefully

Now you can do:

  ./run.sh [OPTIONS]

without having to specify a particular program (defaults to

10 years agooutput: don't redirect any output for DEBUG builds
Brian Norris [Tue, 20 Nov 2012 00:37:26 +0000 (16:37 -0800)]
output: don't redirect any output for DEBUG builds

10 years agoREADME: add verbose (-v) argument
Brian Norris [Mon, 19 Nov 2012 23:51:02 +0000 (15:51 -0800)]
README: add verbose (-v) argument

10 years agomodel: optimize get_last_conflict() search
Brian Norris [Mon, 19 Nov 2012 21:10:07 +0000 (13:10 -0800)]
model: optimize get_last_conflict() search

Relaxed operations should never require backtracking, so don't even
bother with searching the list in such cases. I ran some simple
benchmarking tests with linuxrwlocks (timing results below). Also, perf
shows a significant decrease in % time spent in


$ time ./run.sh test/linuxrwlocks.o -f 10 -m 10
Number of complete, bug-free executions: 7110
Number of redundant executions: 29
Number of buggy executions: 0
Number of infeasible executions: 43578
Total executions: 50717
Total nodes created: 63463

real 0m7.274s
user 0m6.596s
sys 0m0.652s

2.10%  linuxrwlocks.o  libmodel.so          [.] ModelAction::could_synchronize_with(ModelAction const*) const


$ time ./run.sh test/linuxrwlocks.o -f 10 -m 10
Number of complete, bug-free executions: 7110
Number of redundant executions: 29
Number of buggy executions: 0
Number of infeasible executions: 43578
Total executions: 50717
Total nodes created: 63463

real 0m6.690s
user 0m6.000s
sys 0m0.664s

0.73%  linuxrwlocks.o  libmodel.so          [.] ModelAction::could_synchronize_with(ModelAction const*) const

10 years agoaction: add is_relaxed() function
Brian Norris [Mon, 19 Nov 2012 21:09:29 +0000 (13:09 -0800)]
action: add is_relaxed() function

10 years agocommon: update comment
Brian Norris [Sat, 17 Nov 2012 08:11:27 +0000 (00:11 -0800)]
common: update comment

10 years agomodel: add "# redundant" stat
Brian Norris [Sat, 17 Nov 2012 08:01:18 +0000 (00:01 -0800)]
model: add "# redundant" stat

10 years agomodel: refactor end-of-execution output
Brian Norris [Sat, 17 Nov 2012 07:55:12 +0000 (23:55 -0800)]
model: refactor end-of-execution output

10 years agomodel: print_summary() should be const
Brian Norris [Sat, 17 Nov 2012 07:51:59 +0000 (23:51 -0800)]
model: print_summary() should be const

10 years agomodel/main: disable most printing by default, add verbosity
Brian Norris [Sat, 17 Nov 2012 04:23:15 +0000 (20:23 -0800)]
model/main: disable most printing by default, add verbosity

Adds a '-v' parameter for printing verbose info on a non-DEBUG build.
This effectively creates 3 classes of runs:

 - Default build, no -v: only prints info when discovering a buggy
 - Default build, -v: prints more verbose information, on all feasible
   executions (buggy or non-buggy)
 - Debug build: Built with 'make debug'. Most verbose; prints everything
   for every execution, including infeasible executions. Also prints
   DEBUG() prints (as usual).

10 years agooutput redirection
Brian Norris [Sat, 17 Nov 2012 04:07:57 +0000 (20:07 -0800)]
output redirection

10 years agomodel: print execution # with trace
Brian Norris [Sat, 17 Nov 2012 01:45:23 +0000 (17:45 -0800)]
model: print execution # with trace

Since stats won't be printed regularly, we still want a measure of
"how many executions have run" when we print a summary trace.

10 years agoprint stats only at end of execution
Brian Norris [Sat, 17 Nov 2012 01:44:50 +0000 (17:44 -0800)]
print stats only at end of execution

10 years agoprintf -> model_print
Brian Norris [Fri, 16 Nov 2012 23:23:40 +0000 (15:23 -0800)]
printf -> model_print

As we move toward redirecting program output, we will need a special
printf function for model-checking prints. Just define a simple
model_print() for now.

10 years agomodel: correct plural ("bug" or "bugs")
Brian Norris [Fri, 16 Nov 2012 23:05:51 +0000 (15:05 -0800)]
model: correct plural ("bug" or "bugs")

10 years agomodel: rework assert_bug() and assert_user_bug() interfaces
Brian Norris [Fri, 16 Nov 2012 22:58:32 +0000 (14:58 -0800)]
model: rework assert_bug() and assert_user_bug() interfaces

We don't need assert_bug_immediate(), and we don't need some of the
optional parameters in assert_bug(). Just simplify down to two


The former is useful for all bugs triggered from model-checker threads,
and the latter is useful from a user-thread context, so that you can
immediately switch to the model-checking context and exit the program -
but *only if* the trace is currently-feasible.

10 years agodataraces: don't print an uninformative "Data race" bug msg
Brian Norris [Fri, 16 Nov 2012 22:44:32 +0000 (14:44 -0800)]
dataraces: don't print an uninformative "Data race" bug msg

Now that checkDataRaces() handles all bug reporting and assertions on
its own, we don't need an additional bug report message printed by the
caller. In some cases, this means the caller doesn't have any action to
take. In one case (a race immediately-realized from a user thread), we
still need to "bail out" to the model-checker.

10 years agodatarace: redirect "Data race @ ..." messages to model-checker bug list
Brian Norris [Fri, 16 Nov 2012 22:38:26 +0000 (14:38 -0800)]
datarace: redirect "Data race @ ..." messages to model-checker bug list

Data race information was previously printed in multiple ways: through
the datarace.cc printRace() method and through the model-checker
assert_bug() method. Start unifying that.

Other notes:
- Data race objects probably should be freed (even though they are
  snapshotted). I fix this.
- Races could be printed more than once previously, since the
  unrealizedraces vector was never cleared of realized races. Now, we
  clear this vector every time we process it (in a feasible execution),
  either stashing a bug message or dropping the race entirely.

10 years agodatarace: change "Datarace" to "Data race"
Brian Norris [Fri, 16 Nov 2012 21:59:03 +0000 (13:59 -0800)]
datarace: change "Datarace" to "Data race"

10 years agomodel: restructure statistics records
Brian Norris [Fri, 16 Nov 2012 20:02:10 +0000 (12:02 -0800)]
model: restructure statistics records

10 years agomodel: annotate SNAPSHOT for bug_message
Brian Norris [Fri, 16 Nov 2012 02:01:31 +0000 (18:01 -0800)]
model: annotate SNAPSHOT for bug_message

Since we use operator new with bug_message, it needs to be marked

10 years agomodel: temporary fix for uninitialized loads
Brian Norris [Fri, 16 Nov 2012 01:51:43 +0000 (17:51 -0800)]
model: temporary fix for uninitialized loads

This patch does two things:

(1) Convert 'set_assert()' to 'assert_bug()' to provide:
    - More unified bug printing
    - Only printing the bug for a feasible prefix
(2) Avoids the work_queue loop if a bug was asserted

Part (1) mostly provides some cosmetic fixes.
Part (2) prevents an ASSERT() from being thrown in future values, since
we don't abort the trace early enough when there's nothing to read from.

This all needs better treatment of uninitialized loads, as there are
some loose ends.

10 years agoassert bugs through common interface
Brian Norris [Thu, 15 Nov 2012 21:50:40 +0000 (13:50 -0800)]
assert bugs through common interface

- User-provied assertions (MODEL_ASSERT())
- Data races
- Deadlocks
- Unlock before lock

Notably, I have not yet converted the "uninitialized load" bug, because
it actually isn't correct yet. It needs to handle future values and lazy
synchronization better.

10 years agomodel: print bug reports at end of each execution
Brian Norris [Thu, 15 Nov 2012 21:33:13 +0000 (13:33 -0800)]
model: print bug reports at end of each execution

This ensures:
- that bug reports are printed only at the end of feasible executions
- that execution summaries are printed only for complete (or halted and
  buggy) executions that are feasible
- that all bug reports will have the same formatting (at least, ones
  that use the 'assert_bug()' function)

Note that deadlocks are the only bugs reported this way right now. I'll
fix that up soon.

10 years agomodel: add bug reporting framework
Brian Norris [Thu, 15 Nov 2012 21:25:35 +0000 (13:25 -0800)]
model: add bug reporting framework

This will help clean up bug reporting so that bugs are only printed for
complete, valid executions.

10 years agomodel: remove unnecessary DEBUG()
Brian Norris [Thu, 15 Nov 2012 21:29:44 +0000 (13:29 -0800)]
model: remove unnecessary DEBUG()

10 years agomodel: use snapshot_calloc()
Brian Norris [Thu, 15 Nov 2012 20:43:23 +0000 (12:43 -0800)]
model: use snapshot_calloc()

Also, might as well free priv on destruction.

10 years agomodel: add 'const'
Brian Norris [Thu, 15 Nov 2012 20:21:45 +0000 (12:21 -0800)]
model: add 'const'

10 years agomodel: routine to check if execution is complete
Brian Norris [Thu, 15 Nov 2012 00:46:03 +0000 (16:46 -0800)]
model: routine to check if execution is complete

Not used yet.

10 years agomake compile on linux...needed string.h
Brian Demsky [Thu, 15 Nov 2012 07:29:52 +0000 (23:29 -0800)]
make compile on linux...needed string.h

10 years agoMerge branch 'master' of /home/git/model-checker
Brian Demsky [Thu, 15 Nov 2012 07:27:30 +0000 (23:27 -0800)]
Merge branch 'master' of /home/git/model-checker

10 years agooptimize hashtable so we don't always build new ones for cyclegraph check
Brian Demsky [Thu, 15 Nov 2012 07:26:45 +0000 (23:26 -0800)]
optimize hashtable so we don't always build new ones for cyclegraph check

10 years agoremove hashtable functionality
Brian Demsky [Thu, 15 Nov 2012 06:45:26 +0000 (22:45 -0800)]
remove hashtable functionality

10 years agomake hashtables only contain primitive types or pointers
Brian Demsky [Thu, 15 Nov 2012 06:44:33 +0000 (22:44 -0800)]
make hashtables only contain primitive types or pointers

10 years agoMerge branch 'master' of /home/git/model-checker
Brian Demsky [Thu, 15 Nov 2012 04:55:23 +0000 (20:55 -0800)]
Merge branch 'master' of /home/git/model-checker

10 years agoavoid warning
Brian Demsky [Thu, 15 Nov 2012 04:55:06 +0000 (20:55 -0800)]
avoid warning

10 years agomerge
Brian Demsky [Thu, 15 Nov 2012 02:15:04 +0000 (18:15 -0800)]
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker


10 years agooptimization...don't calloc the datarace tables every single time...it is really...
Brian Demsky [Thu, 15 Nov 2012 02:11:29 +0000 (18:11 -0800)]
optimization...don't calloc the datarace tables every single time...it is really expensive for rollback

10 years agomodel: remove useless special case
Brian Norris [Thu, 15 Nov 2012 00:30:39 +0000 (16:30 -0800)]
model: remove useless special case

Why do we want to print races, etc., when exiting due to execution
length bound? If you want that, just enable debug prints.

10 years agomodel: don't export Scheduler
Brian Norris [Wed, 14 Nov 2012 23:56:55 +0000 (15:56 -0800)]
model: don't export Scheduler

I removed any users of the get_scheduler() function.

10 years agomodel/promise: use ModelChecker is_enabled() interface
Brian Norris [Wed, 14 Nov 2012 23:55:59 +0000 (15:55 -0800)]
model/promise: use ModelChecker is_enabled() interface

class Promise should not need to access Scheduler directly. Use the
ModelChecker interface.

10 years agomodel: is_deadlocked() (sort of) had a bug
Brian Norris [Wed, 14 Nov 2012 23:53:16 +0000 (15:53 -0800)]
model: is_deadlocked() (sort of) had a bug

We were comparing the boolean (is_enabled(t)) to an enum
(THREAD_DISABLED). This happened to work as we wanted to because
THREAD_DISABLED == 0 == false. But that's not really what I meant...

Anyway, this uses a proper ModelChecker::is_enabled(tid) interface.

10 years agomodel: add ModelChecker is_enabled() functions
Brian Norris [Wed, 14 Nov 2012 23:52:16 +0000 (15:52 -0800)]
model: add ModelChecker is_enabled() functions

We don't want all users to have to directly address the scheduler;
provide an interface.

10 years agoschedule: improve is_enabled() routines
Brian Norris [Wed, 14 Nov 2012 23:43:39 +0000 (15:43 -0800)]
schedule: improve is_enabled() routines

The comments don't clearly explain what is_enabled() might include
(i.e., SLEEP_SET, ENABLED, or DISABLED). Also, we need a direct accessor
keyed by thread_id_t, not just by class Thread.

10 years agomodel: fix spacing
Brian Norris [Wed, 14 Nov 2012 23:28:25 +0000 (15:28 -0800)]
model: fix spacing

10 years agomodel: move snapshot members out of header
Brian Norris [Wed, 14 Nov 2012 23:27:40 +0000 (15:27 -0800)]
model: move snapshot members out of header

This struct is only used within model.cc

10 years agoREADME
Brian Norris [Wed, 14 Nov 2012 03:31:02 +0000 (19:31 -0800)]

10 years agomain: change default future value sloppiness
Brian Norris [Wed, 7 Nov 2012 03:10:53 +0000 (19:10 -0800)]
main: change default future value sloppiness

Future value sloppiness should be set somewhat in proportion to
maxfuturedelay, and we need a value higher than 2. Set to 10 for now,
although we may change this later.

10 years agonodestack: implement expiration sloppiness parameter
Brian Norris [Wed, 7 Nov 2012 00:10:33 +0000 (16:10 -0800)]
nodestack: implement expiration sloppiness parameter

Now, a previously-explored, repeated future value will only generate a
new future-value/expiration pair if the expiration is higher than the
previous expiration + sloppiness. This prevents executions where we
continue to step up the future value expiration by a small increment,
creating the same execution.

This also rewrites the add_future_value() logic just a bit so that it is
a little bit more clear.

10 years agomain/model: add future value expiration sloppiness parameter
Brian Norris [Wed, 7 Nov 2012 00:09:59 +0000 (16:09 -0800)]
main/model: add future value expiration sloppiness parameter

Functionality not implemented yet

10 years agonodestack: limit the number of future values per read
Brian Norris [Sun, 4 Nov 2012 02:39:33 +0000 (19:39 -0700)]
nodestack: limit the number of future values per read

Not tested very thoroughly, but it seems to limit the future values set
as intended.

10 years agomain: add maxfuturevalues parameter (-M)
Brian Norris [Sun, 4 Nov 2012 01:16:45 +0000 (18:16 -0700)]
main: add maxfuturevalues parameter (-M)

Not implemented yet

10 years agocommon: early quit on MODEL_ASSERT()
Brian Norris [Sun, 4 Nov 2012 00:50:26 +0000 (17:50 -0700)]
common: early quit on MODEL_ASSERT()

If a user program hits an assertion, we should quit before executing any
further. i.e., don't even wait for the next atomic action, since the
assertion might trigger more bugs that have unintended/unforseen

10 years agomodel-assert: add MODEL_ASSERT() for user programs
Brian Norris [Sat, 3 Nov 2012 22:52:16 +0000 (15:52 -0700)]
model-assert: add MODEL_ASSERT() for user programs

10 years agomodel: refactor build_reads_from_past
Brian Norris [Tue, 6 Nov 2012 00:00:18 +0000 (16:00 -0800)]
model: refactor build_reads_from_past

A couple of if-else conditions can be merged to a single if block.

Also, I move the DBG prints for the may_read_from set into the correct
part of the if, to avoid printing false messages about the may_read_from

10 years agocommon/config: allow enable/disable ASSERT() easily
Brian Norris [Wed, 14 Nov 2012 22:39:07 +0000 (14:39 -0800)]
common/config: allow enable/disable ASSERT() easily

Now, assertions (ASSERT()) are only checked if the CONFIG_ASSERT macro
is defined. We leave this enabled for all builds for now.

10 years agorace: where possible, use "const void *" for addresses
Brian Norris [Tue, 13 Nov 2012 00:42:41 +0000 (16:42 -0800)]
race: where possible, use "const void *" for addresses

This allows more flexible use for read-only objects.

10 years agotest: add AB/BA deadlock test
Brian Norris [Wed, 7 Nov 2012 03:26:13 +0000 (19:26 -0800)]
test: add AB/BA deadlock test

10 years agomodel: add deadlock detection
Brian Norris [Wed, 7 Nov 2012 03:18:34 +0000 (19:18 -0800)]
model: add deadlock detection

This is only a simple end-of-execution deadlock detection. If we have a
true deadlock, and no other threads are spinning, then our execution
will exit --- we can recognize this state.

For more complicated deadlocks involving other spinning threads, we need
to perform some sort of depth-first-search cycle detection.

10 years agomodel: get_num_threads() should be const
Brian Norris [Wed, 7 Nov 2012 03:13:05 +0000 (19:13 -0800)]
model: get_num_threads() should be const

10 years agosnapshot: find the correct binary name
Brian Norris [Sat, 3 Nov 2012 22:31:20 +0000 (15:31 -0700)]
snapshot: find the correct binary name

This is somewhat of a neutral change; the existing /proc/*/maps check
works because our path name usually has the word 'model' in it. But
really, we should find the true, full path of the user program.

This should be extended to find more maps (e.g., for other libraries),
and it should be extended for Mac OSX too.

10 years agosnapshot: read from /proc/self/maps
Brian Norris [Sat, 3 Nov 2012 21:55:56 +0000 (14:55 -0700)]
snapshot: read from /proc/self/maps

We don't need to get the PID

10 years agomain: fixup parameter parsing for user program
Brian Norris [Fri, 2 Nov 2012 22:50:48 +0000 (15:50 -0700)]
main: fixup parameter parsing for user program

The user program expects 'optind' to be reset and for 'argv' and 'argc'
to include the program name as the first argument variable.

Note: our mmap()/mprotect()-based snapshotting does not snapshot this
'optind' global, so user-progs that use optarg() functionality might