model-checker.git
8 years agotest: insanesync: consolidate lines oopsla2013-final
Brian Norris [Wed, 17 Jul 2013 02:31:20 +0000 (19:31 -0700)]
test: insanesync: consolidate lines

8 years agotest: insanesync: remove unnecessary casting
Brian Norris [Wed, 17 Jul 2013 02:28:35 +0000 (19:28 -0700)]
test: insanesync: remove unnecessary casting

8 years agotest: insanesync: convert to C++
Brian Norris [Wed, 17 Jul 2013 02:22:52 +0000 (19:22 -0700)]
test: insanesync: convert to C++

The syntax is clearer this way, and I can make it more consistent with
the other satisfaction cycle examples I wrote.

8 years agotest: addr-satcycle: add new address-based sat. cycle example
Brian Norris [Tue, 16 Jul 2013 20:22:43 +0000 (13:22 -0700)]
test: addr-satcycle: add new address-based sat. cycle example

See the comments and assertion in the program for the description.

8 years agorun.sh: don't silently ignore a non-executable file argument
Brian Norris [Wed, 10 Jul 2013 01:44:19 +0000 (18:44 -0700)]
run.sh: don't silently ignore a non-executable file argument

If we use a file which exists but is not executable as an argument to
run.sh, run.sh will silently ignore it. This is wrong.

Instead, just check for existence of the file (or directory), and error
out with a "Permission denied" message later, when we try to run it.

8 years agotest: mo-satcycle: add new MO satisfaction cycle example
Brian Norris [Wed, 10 Jul 2013 01:33:33 +0000 (18:33 -0700)]
test: mo-satcycle: add new MO satisfaction cycle example

See the comments at the top of the file.

8 years agotest: uninit: typo
Brian Norris [Wed, 10 Jul 2013 01:18:07 +0000 (18:18 -0700)]
test: uninit: typo

8 years agoexecution: remove redundant condition, reword doc for promises_may_allow
Brian Norris [Thu, 6 Jun 2013 00:25:30 +0000 (17:25 -0700)]
execution: remove redundant condition, reword doc for promises_may_allow

promises_may_allow() doesn't actually need to check for
promises.empty(), as the loop bounds take care of that. In the same
spirit, we can reword the comments/documentation so that

 (1) it is not redundant (condition (a) is subsumed by (b))
 (2) we are more explicit about what we actually mean by "crossing
     promises"

8 years agoexecution: document additional mo_may_allow() optimization
Brian Norris [Thu, 6 Jun 2013 00:14:32 +0000 (17:14 -0700)]
execution: document additional mo_may_allow() optimization

mo_may_allow() actually performs two optimizations, not just the one
that is documented in its header.

8 years agoexecution: document promises list; it is assumed to be sorted
Brian Norris [Thu, 6 Jun 2013 00:13:55 +0000 (17:13 -0700)]
execution: document promises list; it is assumed to be sorted

Document the assumptions made about the 'promises' list.

8 years agomodel: remove redundant code (is_enabled)
Brian Norris [Wed, 5 Jun 2013 23:31:41 +0000 (16:31 -0700)]
model: remove redundant code (is_enabled)

These members should just stay implemented in execution.{cc,h}, not
model.{cc,h}.

8 years agodocs: improve Doxygen documentation
Brian Norris [Wed, 5 Jun 2013 02:06:35 +0000 (19:06 -0700)]
docs: improve Doxygen documentation

* Fix the PROJECT_NAME title

* Add include/ to documentation

* Include our generated README.html as the main page in the docs

  - NOTE: Doxygen 1.8.0+ can directly generate documentation from the
    Markdown format (i.e., README.md). This may be useful in the future
    to get more integrated support, but for now, the
    separately-generated HTML is good enough

8 years agoREADME: use markdown format for direct URL link
Brian Norris [Wed, 5 Jun 2013 01:20:42 +0000 (18:20 -0700)]
README: use markdown format for direct URL link

8 years agoREADME: more formatting, correct statement about bench.sh
Brian Norris [Tue, 4 Jun 2013 23:32:39 +0000 (16:32 -0700)]
README: more formatting, correct statement about bench.sh

8 years agoREADME: a few more formatting issues
Brian Norris [Tue, 4 Jun 2013 23:30:00 +0000 (16:30 -0700)]
README: a few more formatting issues

8 years agoMerge branch 'markdown'
Brian Norris [Tue, 4 Jun 2013 23:14:18 +0000 (16:14 -0700)]
Merge branch 'markdown'

8 years agoREADME: add more `code` formatting
Brian Norris [Tue, 4 Jun 2013 23:04:56 +0000 (16:04 -0700)]
README: add more `code` formatting

8 years agoAdd example from java showing legit satisfaction cycle
Brian Demsky [Mon, 3 Jun 2013 19:02:19 +0000 (12:02 -0700)]
Add example from java showing legit satisfaction cycle

8 years ago.gitignore: fixup VIM swapfile ignore
Brian Norris [Sun, 2 Jun 2013 00:07:37 +0000 (17:07 -0700)]
.gitignore: fixup VIM swapfile ignore

8 years agoREADME: convert to Markdown format
Brian Norris [Sun, 2 Jun 2013 00:06:33 +0000 (17:06 -0700)]
README: convert to Markdown format

Now we can easily generate an HTML version, while retaining readability
as a simple text file.

8 years agoMarkdown: add Markdown tool
Brian Norris [Sun, 2 Jun 2013 00:04:41 +0000 (17:04 -0700)]
Markdown: add Markdown tool

For conversion of Markdown format to HTML.

From:

  http://daringfireball.net/projects/markdown/

License terms are easy to comply with (see doc/Markdown/License.text).

8 years agoREADME: add bit on MODEL_ASSERT() macro oopsla2013
Brian Norris [Sat, 1 Jun 2013 23:08:16 +0000 (16:08 -0700)]
README: add bit on MODEL_ASSERT() macro

8 years agoREADME: extra "from"
Brian Norris [Sat, 1 Jun 2013 00:46:34 +0000 (17:46 -0700)]
README: extra "from"

8 years agoREADME: updated help text
Brian Norris [Sat, 1 Jun 2013 00:44:03 +0000 (17:44 -0700)]
README: updated help text

8 years agomodel: cosmetic output improvements
Brian Norris [Fri, 31 May 2013 23:50:40 +0000 (16:50 -0700)]
model: cosmetic output improvements

A few cosmetic improvements:

* Provide more uniform newlines

* Clearly show which output is produced by the test program

* Provide clear heading to show which output belongs to which program
  execution

* Label the program trace if it has bugs

I'm sure there's more that could be improved, but that's it for now.

8 years agoparams: add multi-level verbosity
Brian Norris [Fri, 31 May 2013 23:45:42 +0000 (16:45 -0700)]
params: add multi-level verbosity

Now we can have --verbose=[012], so that the default (0) is still quiet,
the easy verbose flag (--verbose or -v) is noisy but useful (1), and if
you really want some extra noise, you can choose (2). Right now, there
is some minimal extra noise in (2), but this may be expanded if we want
more run-time debuggability, rather than recompiling with 'make debug'.

8 years agoREADME: add LICENSE note
Brian Norris [Fri, 31 May 2013 22:37:30 +0000 (15:37 -0700)]
README: add LICENSE note

8 years agoREADME: improve sections, provide better intro
Brian Norris [Fri, 31 May 2013 22:32:39 +0000 (15:32 -0700)]
README: improve sections, provide better intro

8 years agoMerge remote-tracking branch 'origin/master'
Brian Norris [Wed, 29 May 2013 02:03:14 +0000 (19:03 -0700)]
Merge remote-tracking branch 'origin/master'

8 years agoREADME: add a few sections
Brian Norris [Wed, 29 May 2013 02:01:52 +0000 (19:01 -0700)]
README: add a few sections

8 years agoexecution: reformat execution traces
Brian Norris [Wed, 29 May 2013 01:32:19 +0000 (18:32 -0700)]
execution: reformat execution traces

The execution printouts were getting too wide and weren't too easy to
read. This improves the situation marginally.

8 years agoREADME: update help text
Brian Norris [Wed, 29 May 2013 01:07:35 +0000 (18:07 -0700)]
README: update help text

8 years agomain: 'plug ins' -> 'plugins'
Brian Norris [Wed, 29 May 2013 01:05:00 +0000 (18:05 -0700)]
main: 'plug ins' -> 'plugins'

8 years agotests: Makefile: add dependency information
Brian Norris [Wed, 29 May 2013 00:59:58 +0000 (17:59 -0700)]
tests: Makefile: add dependency information

Now tests will be re-compiled whenever their include files are modified.

8 years agoMakefile: remove more deferred variables
Brian Norris [Wed, 29 May 2013 00:31:44 +0000 (17:31 -0700)]
Makefile: remove more deferred variables

8 years agotests: Makefile: eliminate (some) recursive make
Brian Norris [Wed, 29 May 2013 00:01:47 +0000 (17:01 -0700)]
tests: Makefile: eliminate (some) recursive make

8 years agoexecution: bugfix - resolved promises should propagate synchronization
Brian Norris [Wed, 8 May 2013 17:09:52 +0000 (10:09 -0700)]
execution: bugfix - resolved promises should propagate synchronization

A new write ModelAction may resolve a Promise, completing a release
sequence and updating the read's clock vector. This update should be
propagated to any ModelAction later in the execution order which had
previously "happened after" the read.

8 years agoexecution: refactor common CV propagation into its own function
Brian Norris [Wed, 8 May 2013 17:05:44 +0000 (10:05 -0700)]
execution: refactor common CV propagation into its own function

There are a few occasions where we want to "fixup" a series of clock
vectors after establishing lazy synchronization (and one place where we
currently have a bug). Refactor this out to its own function so I can
reuse it elsewhere.

8 years agotypos
Brian Demsky [Mon, 6 May 2013 23:32:41 +0000 (16:32 -0700)]
typos

8 years agoprint some stats in SC Analysis
Brian Demsky [Mon, 6 May 2013 23:28:44 +0000 (16:28 -0700)]
print some stats in SC Analysis

8 years agodocument and extend trace analysis interface
Brian Demsky [Mon, 6 May 2013 20:25:00 +0000 (13:25 -0700)]
document and extend trace analysis interface

8 years agocleanup plugin interface a little more.
Brian Demsky [Mon, 6 May 2013 20:06:53 +0000 (13:06 -0700)]
cleanup plugin interface a little more.
add support for options for SCAnalysis

8 years agoadd support for analysis with options
Brian Demsky [Mon, 6 May 2013 10:05:50 +0000 (03:05 -0700)]
add support for analysis with options

8 years agoadd traceanalysis support
Brian Demsky [Mon, 6 May 2013 09:50:49 +0000 (02:50 -0700)]
add traceanalysis support

8 years agoMerge demsky's SC analysis fixup
Brian Norris [Fri, 3 May 2013 16:51:20 +0000 (09:51 -0700)]
Merge demsky's SC analysis fixup

8 years agoscanalysis: don't rely on greedy search
Brian Demsky [Fri, 26 Apr 2013 23:50:30 +0000 (16:50 -0700)]
scanalysis: don't rely on greedy search

Fix infrastructure to use search in cases where a greedy search is not
sufficient.

8 years agoscanalysis: fixup spacing
Brian Norris [Fri, 26 Apr 2013 22:37:36 +0000 (15:37 -0700)]
scanalysis: fixup spacing

8 years agotest: sctest: fix warnings
Brian Norris [Fri, 26 Apr 2013 22:29:26 +0000 (15:29 -0700)]
test: sctest: fix warnings

Perhaps we wanted to print these variables? Anyway, just make them
global, so the warnings will go away:

  gcc -o sctest.o sctest.c -Wall -g -O3 -I.. -I../include -L.. -lmodel
  sctest.c: In function ‘b’:
  sctest.c:20:6: warning: unused variable ‘r1’ [-Wunused-variable]
  sctest.c: In function ‘c’:
  sctest.c:26:6: warning: unused variable ‘r2’ [-Wunused-variable]
  sctest.c: In function ‘d’:
  sctest.c:33:6: warning: unused variable ‘r3’ [-Wunused-variable]

8 years agoFix bug that prevents graph generation from compiling.
Brian Demsky [Fri, 26 Apr 2013 20:46:35 +0000 (13:46 -0700)]
Fix bug that prevents graph generation from compiling.
Check in test case that shows theorem that I've been trying to prove for 2 days is in fact not true (and thus difficult to prove).

8 years agoaction: improve "unintialized load" bug print
Brian Norris [Wed, 24 Apr 2013 17:28:34 +0000 (10:28 -0700)]
action: improve "unintialized load" bug print

8 years agoaction: add get_{type,mo}_str() accessors
Brian Norris [Wed, 24 Apr 2013 17:11:16 +0000 (10:11 -0700)]
action: add get_{type,mo}_str() accessors

The big switch/case statements can be shortened and separated into their
own functions.

8 years agoMerge remote-tracking branch 'private/master'
Brian Norris [Tue, 23 Apr 2013 01:43:20 +0000 (18:43 -0700)]
Merge remote-tracking branch 'private/master'

8 years agoREADME: update text
Brian Norris [Tue, 23 Apr 2013 01:42:51 +0000 (18:42 -0700)]
README: update text

8 years agobug...will sometimes print SC traces in a bad order
Brian Demsky [Tue, 23 Apr 2013 00:19:25 +0000 (17:19 -0700)]
bug...will sometimes print SC traces in a bad order

8 years agocleanup printing
Brian Demsky [Mon, 22 Apr 2013 23:00:56 +0000 (16:00 -0700)]
cleanup printing

8 years agoRework how we present non-SC traces...previous presentation didn't make reasons clear.
Brian Demsky [Mon, 22 Apr 2013 22:59:22 +0000 (15:59 -0700)]
Rework how we present non-SC traces...previous presentation didn't make reasons clear.

8 years agosnapshot-interface: bugfix - terminate string from readlink()
Brian Norris [Fri, 19 Apr 2013 22:21:07 +0000 (15:21 -0700)]
snapshot-interface: bugfix - terminate string from readlink()

readlink() doesn't terminate the string for us, so our string doesn't
match properly (it will have a little extra garbage at the end).

8 years agosnapshot: debugging - show the snapshot regions that are added
Brian Norris [Fri, 19 Apr 2013 22:20:18 +0000 (15:20 -0700)]
snapshot: debugging - show the snapshot regions that are added

8 years agosnapshot-interface: don't snapshot libmodel.so
Brian Norris [Fri, 19 Apr 2013 21:47:35 +0000 (14:47 -0700)]
snapshot-interface: don't snapshot libmodel.so

We don't need to snapshot our own globals; we are careful to only place
constant pointers in global memory.

8 years agosnapshot: use perror()
Brian Norris [Fri, 19 Apr 2013 21:42:05 +0000 (14:42 -0700)]
snapshot: use perror()

8 years agomain: support long options, improve help message
Brian Norris [Wed, 17 Apr 2013 19:42:14 +0000 (12:42 -0700)]
main: support long options, improve help message

8 years agoexecution: improve documentation
Brian Norris [Fri, 19 Apr 2013 21:32:51 +0000 (14:32 -0700)]
execution: improve documentation

is_yieldblocked() wasn't documented

check_action_enabled() had incorrect documentation, since I removed the
waiter lists

8 years agoexecution: improve yield-blocking structure
Brian Norris [Fri, 19 Apr 2013 21:29:29 +0000 (14:29 -0700)]
execution: improve yield-blocking structure

We should just check the yieldblock parameter within
ModelExecution::is_yieldblock().

8 years agoTMP: improve debugging, remove print_trace()
Brian Norris [Thu, 18 Apr 2013 02:10:47 +0000 (19:10 -0700)]
TMP: improve debugging, remove print_trace()

8 years agoRemove special cases for printing SC executions.
Brian Demsky [Fri, 19 Apr 2013 00:34:41 +0000 (17:34 -0700)]
Remove special cases for printing SC executions.

Just use happens before relation instead.  Also include a criteria to keep things in execution order as much as possible.

8 years agoAdd yield block support. The idea is to not generate executions with yield actions.
Brian Demsky [Thu, 18 Apr 2013 21:53:58 +0000 (14:53 -0700)]
Add yield block support.  The idea is to not generate executions with yield actions.

While preventing yields doesn't preserve livelock, under the CHESS assumptions, it does allow us to reach all states.

8 years agodatarace: bugfix - use proper multiple-inclusion guard
Brian Norris [Thu, 18 Apr 2013 01:45:44 +0000 (18:45 -0700)]
datarace: bugfix - use proper multiple-inclusion guard

The DATARACE_H macro is never defined, so it never succeeds as a
multiple-inclusion guard.

8 years agostacktrace: remove usage of FILE in stacktrace
Brian Norris [Thu, 18 Apr 2013 00:10:20 +0000 (17:10 -0700)]
stacktrace: remove usage of FILE in stacktrace

The original print_stacktrace() function required a FILE pointer, so we
manufactured one. We really should avoid the bugs that can come from the
allocation and buffering done with FILE, since this is used on error
paths.

8 years agoBug: ModelExecution had bogus model_params reference.
Brian Demsky [Wed, 17 Apr 2013 22:51:47 +0000 (15:51 -0700)]
Bug: ModelExecution had bogus model_params reference.

Fix.

8 years agodatarace: bugfix - don't implicitly allocate global SnapVector
Brian Norris [Wed, 17 Apr 2013 20:17:46 +0000 (13:17 -0700)]
datarace: bugfix - don't implicitly allocate global SnapVector

We do not want to pollute the user's snapshotting region with the
unrealizedraces SnapVector. Allocate it in initRaceDetector(), so that
it is placed on the model-checker's snapshotting heap.

8 years agodatarace: don't export unrealized race vector
Brian Norris [Wed, 17 Apr 2013 20:15:30 +0000 (13:15 -0700)]
datarace: don't export unrealized race vector

8 years agoexecution: bugfix - no action "conflicts" with itself
Brian Norris [Wed, 17 Apr 2013 17:50:25 +0000 (10:50 -0700)]
execution: bugfix - no action "conflicts" with itself

8 years agoexecution: bugfix - backtrack seq-cst fences properly
Brian Norris [Wed, 17 Apr 2013 17:46:19 +0000 (10:46 -0700)]
execution: bugfix - backtrack seq-cst fences properly

The commented-out ATOMIC_FENCE should not be commented out; the note
that "fences don't directly cause backtracking" is false for seq-cst
fences. We intend to backtrack for all seq-cst fences, so we need to
perform the appropriate 'get conflict' search for all fences.

8 years agoexecution: correct comment on check_current_action()
Brian Norris [Wed, 17 Apr 2013 17:45:58 +0000 (10:45 -0700)]
execution: correct comment on check_current_action()

8 years agonodestack: localize the model-checker parameters
Brian Norris [Tue, 16 Apr 2013 19:27:06 +0000 (12:27 -0700)]
nodestack: localize the model-checker parameters

8 years agomodel: privatize ModelChecker::get_num_threads()
Brian Norris [Tue, 16 Apr 2013 18:58:28 +0000 (11:58 -0700)]
model: privatize ModelChecker::get_num_threads()

The public interface is now in ModelExecution.

8 years agonodestack: register ModelExecution class w/in NodeStack
Brian Norris [Tue, 16 Apr 2013 18:56:59 +0000 (11:56 -0700)]
nodestack: register ModelExecution class w/in NodeStack

8 years agopromise: add max_available_thread_idx() interface
Brian Norris [Tue, 16 Apr 2013 18:45:51 +0000 (11:45 -0700)]
promise: add max_available_thread_idx() interface

To remove an unnecessary use of global/public model->get_num_threads().

8 years agoclockvector: don't use global get_num_threads()
Brian Norris [Tue, 16 Apr 2013 18:29:11 +0000 (11:29 -0700)]
clockvector: don't use global get_num_threads()

8 years agomodel: remove leftover junk
Brian Norris [Tue, 16 Apr 2013 18:13:55 +0000 (11:13 -0700)]
model: remove leftover junk

8 years agoexecution: embed obj_map directly in class
Brian Norris [Tue, 16 Apr 2013 18:01:46 +0000 (11:01 -0700)]
execution: embed obj_map directly in class

This structure can be embedded as a full-fledged member, not a pointer.

8 years agohashtable: update documentation
Brian Norris [Tue, 16 Apr 2013 17:23:44 +0000 (10:23 -0700)]
hashtable: update documentation

Some of the existing documentation was incorrect or insufficient. Also,
add new documentation to describe the design "feature" of this table:
that 0/NULL is not a valid key.

8 years agohashtable: enforce, document non-zero keys
Brian Norris [Tue, 16 Apr 2013 16:49:01 +0000 (09:49 -0700)]
hashtable: enforce, document non-zero keys

HashTable does not support a key of "zero." ...

8 years agoexecution: convert HashTable to SnapVector
Brian Norris [Tue, 16 Apr 2013 16:30:17 +0000 (09:30 -0700)]
execution: convert HashTable to SnapVector

We don't actually need a hash table for threads, since we allocate their
indeces contiguously, at least for now. Also, HashTable is really
designed for pointer-based keys and may not accept a 0-valued key. To
avoid these problems, just switch to a snapshotted vector.

8 years agoaction: bugfix - use non-zero fence "location"
Brian Norris [Tue, 16 Apr 2013 16:46:58 +0000 (09:46 -0700)]
action: bugfix - use non-zero fence "location"

Our HashTable does not support zero-based keys (e.g., NULL pointer as a
key). So as a hack, switch to use a small, arbitrary, non-zero location
instead of NULL (0).

8 years agoexecution: embed action_list as full member
Brian Norris [Tue, 16 Apr 2013 06:23:43 +0000 (23:23 -0700)]
execution: embed action_list as full member

8 years agoexecution: add const
Brian Norris [Tue, 16 Apr 2013 06:23:25 +0000 (23:23 -0700)]
execution: add const

8 years agoexecution: embed more data structures directly in class
Brian Norris [Tue, 16 Apr 2013 03:28:09 +0000 (20:28 -0700)]
execution: embed more data structures directly in class

8 years agoexecution: embed snapshotted data structures in class
Brian Norris [Tue, 16 Apr 2013 03:20:11 +0000 (20:20 -0700)]
execution: embed snapshotted data structures in class

8 years agoexecution: make structure snapshotting
Brian Norris [Tue, 16 Apr 2013 03:11:14 +0000 (20:11 -0700)]
execution: make structure snapshotting

All members are snapshot-able.

8 years agoexecution: move execution number back to ModelChecker class
Brian Norris [Tue, 16 Apr 2013 03:08:41 +0000 (20:08 -0700)]
execution: move execution number back to ModelChecker class

8 years agoclean out includes, etc.
Brian Norris [Tue, 16 Apr 2013 02:59:53 +0000 (19:59 -0700)]
clean out includes, etc.

8 years agomodel: embed the trace_analyses in the class
Brian Norris [Tue, 16 Apr 2013 02:55:37 +0000 (19:55 -0700)]
model: embed the trace_analyses in the class

8 years agoaction: add <stdlib>
Brian Norris [Tue, 16 Apr 2013 02:53:40 +0000 (19:53 -0700)]
action: add <stdlib>

For exit() and EXIT_*

8 years agoscanalysis: allocate structures as true members of class (not pointers)
Brian Norris [Tue, 16 Apr 2013 02:48:25 +0000 (19:48 -0700)]
scanalysis: allocate structures as true members of class (not pointers)

They're all snapshotting, so it makes sense to make them legitimate
members of the SCAnalysis class.

8 years agoscanalysis: fixup spacing
Brian Norris [Tue, 16 Apr 2013 02:41:50 +0000 (19:41 -0700)]
scanalysis: fixup spacing

8 years agoMerge cleanup branch
Brian Norris [Tue, 16 Apr 2013 18:35:07 +0000 (11:35 -0700)]
Merge cleanup branch

This branch separated ModelChecker into two separate classes/modules. It was a
big disruptive change, and it was not compile-able at some points (the BROKEN
commit and some of its successors). Hence the non-fast-forward merge here, to
record the divergent portion of history as special.

8 years agoschedule: drop the ModelChecker::check_promises_thread_disabled interface
Brian Norris [Tue, 16 Apr 2013 02:37:21 +0000 (19:37 -0700)]
schedule: drop the ModelChecker::check_promises_thread_disabled interface

8 years agomodel / threads: remove global get_next_id() interface
Brian Norris [Tue, 16 Apr 2013 02:31:58 +0000 (19:31 -0700)]
model / threads: remove global get_next_id() interface

8 years agopromise: get reference to ModelExecution
Brian Norris [Tue, 16 Apr 2013 02:25:46 +0000 (19:25 -0700)]
promise: get reference to ModelExecution