Brian Demsky [Thu, 25 Oct 2012 23:28:19 +0000 (16:28 -0700)]
check in test
Brian Demsky [Thu, 25 Oct 2012 23:25:09 +0000 (16:25 -0700)]
add test from nitpick paper...
Brian Demsky [Thu, 25 Oct 2012 04:37:02 +0000 (21:37 -0700)]
embarrassing bug...fixed...
Brian Norris [Fri, 19 Oct 2012 22:27:37 +0000 (15:27 -0700)]
model: fix - RMW cannot break release sequences
I misinterpreted the spec's description of release sequences.
Brian Norris [Fri, 12 Oct 2012 18:05:26 +0000 (11:05 -0700)]
Doxygen: document subdirectories
Document include/, but ignore doc/, benchmarks/, and test/.
Brian Norris [Fri, 12 Oct 2012 18:05:12 +0000 (11:05 -0700)]
thread_id_t: add comments
Brian Norris [Fri, 12 Oct 2012 17:52:00 +0000 (10:52 -0700)]
fixup 'int' vs. 'thread_id_t' usage
Brian Norris [Fri, 12 Oct 2012 17:24:18 +0000 (10:24 -0700)]
modeltypes: move to include/ dir, for now
The <mutex> header uses some small amount of private model-checker
information, so just move the common typedefs to our external include/
directory.
Brian Norris [Fri, 12 Oct 2012 17:21:41 +0000 (10:21 -0700)]
mutex: define empty destructor
I don't think we really need the destructor. It causes undefined
reference compilation errors though:
... undefined reference to `std::mutex::~mutex()'
Brian Norris [Fri, 12 Oct 2012 17:14:44 +0000 (10:14 -0700)]
condition_variable: move header
Move from "conditionvariable.h" to "include/condition_variable". This
allows the normal C++11 #include syntax of:
#include <condition_variable>
Brian Demsky [Fri, 12 Oct 2012 06:56:40 +0000 (23:56 -0700)]
add two test cases
Brian Demsky [Fri, 12 Oct 2012 06:56:12 +0000 (23:56 -0700)]
forgot to add two files...
bug fixes...
Brian Demsky [Fri, 12 Oct 2012 05:51:45 +0000 (22:51 -0700)]
commit untested condvar code
Brian Demsky [Fri, 12 Oct 2012 05:01:33 +0000 (22:01 -0700)]
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
Brian Norris [Fri, 12 Oct 2012 00:08:20 +0000 (17:08 -0700)]
move other interface headers to include/
We want all external interface headers (i.e., any #include'd in user
programs) to be in the include/ directory.
Brian Demsky [Thu, 11 Oct 2012 23:54:20 +0000 (16:54 -0700)]
compiles with condition variables file added...
still need model checker support
Brian Norris [Thu, 11 Oct 2012 23:48:39 +0000 (16:48 -0700)]
mutex: move mutex.h to standard name/location
The important exported interfaces should be in the include/ dir. Also,
C++11 programs should use this header as:
#include <mutex>
Brian Norris [Thu, 11 Oct 2012 17:28:22 +0000 (10:28 -0700)]
include/: add small header comments
Brian Norris [Thu, 11 Oct 2012 17:18:18 +0000 (10:18 -0700)]
impatomic: add multiple-inclusion guards
Brian Norris [Thu, 11 Oct 2012 02:24:29 +0000 (19:24 -0700)]
action: improve printing
The 'value' field of a ModelAction might actually represent a signed
number, a pointer, or something else entirely, so values look very huge
and uninformative when printed, especially in decimal. Hexadecimal
representation makes everything a little more readable, I think.
While I'm at it, I adjust the spacing a little and make VALUE_NONE into
a different magic number which is more recognizable in hex.
Brian Norris [Wed, 10 Oct 2012 23:01:30 +0000 (16:01 -0700)]
Makefile: add benchmarks to top-level
Brian Norris [Wed, 10 Oct 2012 22:42:27 +0000 (15:42 -0700)]
segfault file/line breakpoint info
This can give easy info for using gdb. e.g.:
For debugging, place breakpoint at: snapshot.cc:92
Brian Norris [Wed, 10 Oct 2012 22:21:32 +0000 (15:21 -0700)]
Merge remote-tracking branch 'origin/master'
Brian Norris [Wed, 10 Oct 2012 22:16:59 +0000 (15:16 -0700)]
impatomic: add strong/weak compare_exchange
According to n2748.html, there was a change to allow spurious failure of
compare_exchange operations. Thus, there is no longer a
compare_exchange() operation, but rather a pair of
compare_exchange_{strong,weak)(). I resolve this for compilation
purposes now by editing the impatomic header (mostly with Vim macros for
patterned copy-paste-substitute) and adding an _ATOMIC_CMPSWP_WEAK_
macro, which is just an alias for _ATOMIC_CMPSWP_. Thus, we don't
simulate spurious failure yet.
See:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2748.html
Brian Demsky [Wed, 10 Oct 2012 21:33:30 +0000 (14:33 -0700)]
make scheduler choose fair schedules when threads with priority are sleeping...
Brian Norris [Wed, 10 Oct 2012 18:43:52 +0000 (11:43 -0700)]
action: add NULL dereference assertion
In user programs, we might find a NULL atomic object being dereferenced,
causing strange model-checker behavior which will track memory address 0
as an atomic object. This may result in apparently-uninitialized
variables, for instance.
So, just nip these in the bud with an assertion. Perhaps these things
can transformed into some more informative type of warning in the
future, where user-visible bugs might print helpful messages.
Brian Norris [Wed, 10 Oct 2012 18:41:38 +0000 (11:41 -0700)]
threads: correct 'thrd_yield()'
The C11 thrd_yield() interface should return void. Also, it doesn't need
to do anything in our model-checker for now. I'm leaving its
implementation commented out for now, in case we find it helps for
fairness, for instance. Note that I made its location parameter non-NULL
now, too, so that we can identify the Thread, if we ever use it.
Brian Demsky [Wed, 10 Oct 2012 01:10:37 +0000 (18:10 -0700)]
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
Brian Demsky [Wed, 10 Oct 2012 01:10:10 +0000 (18:10 -0700)]
make linux_rw locks work again
Brian Norris [Wed, 10 Oct 2012 00:58:32 +0000 (17:58 -0700)]
Merge remote-tracking branch 'origin/master'
Brian Norris [Wed, 10 Oct 2012 00:55:31 +0000 (17:55 -0700)]
impatomic: rename all 'swap' to 'exchange'
n2427.html seems to have some very old definitions. I think this all
should be 'exchange', not 'swap'.
Note that there are other issues where we don't have the correct
function names available. But this fixes some of the problems.
Brian Demsky [Wed, 10 Oct 2012 00:54:43 +0000 (17:54 -0700)]
fix some of the bugs related to barrier example...
Brian Norris [Wed, 10 Oct 2012 00:48:56 +0000 (17:48 -0700)]
include: add multiple-inclusion guards
Brian Norris [Tue, 9 Oct 2012 23:30:43 +0000 (16:30 -0700)]
.gitignore: ignore 'benchmarks' folder
Now, you can clone the benchmarks repository under the name 'benchmarks'
and have it compile-ready (but ignored by this repository) with:
git clone <URI/model-checker-benchmarks.git> benchmarks
cd benchmarks
make
Future updates can be pulled in via a 'git pull' from that directory:
cd benchmarks
git pull
Brian Norris [Tue, 9 Oct 2012 21:10:45 +0000 (14:10 -0700)]
tests: use <stdatomic.h>
While I'm at it, rearrange the header listings.
Brian Norris [Tue, 9 Oct 2012 19:09:02 +0000 (12:09 -0700)]
move libthreads.h -> include/threads.h
Helps user programs to be able to just use C11 <threads.h>
Brian Norris [Tue, 9 Oct 2012 19:05:32 +0000 (12:05 -0700)]
rename threads.h -> threads-model.h
There's a name conflict with the C11 <threads.h>
We might as well just avoid the conflict entirely
Brian Norris [Tue, 9 Oct 2012 19:02:42 +0000 (12:02 -0700)]
include: add <atomic> header
Brian Demsky [Tue, 9 Oct 2012 06:35:21 +0000 (23:35 -0700)]
did a little more looking at infeasible executions...
another obvious property we missed...kills about 1/3 of the infeasible executions...
Brian Norris [Wed, 3 Oct 2012 19:07:33 +0000 (12:07 -0700)]
model: JOIN/LOCK unification
Make join and lock actions use similar code paths.
This used to trigger a bug, due to the lack of a private snapshotting
heap.
Brian Norris [Tue, 9 Oct 2012 02:34:43 +0000 (19:34 -0700)]
datarace: reformat datarace printing
Brian Norris [Tue, 9 Oct 2012 01:59:26 +0000 (18:59 -0700)]
threads: allocate on user's snapshotting heap
The following comment is included in threads.h to explain this choice:
Intentionally NOT allocated with MODELALLOC or SNAPSHOTALLOC. Threads
should be allocated on the user's normal (snapshotting) heap to allow
their allocation/deallocation to follow the same pattern as the rest
of the backtracked/replayed program.
This fix solves problems seen in certain test programs regarding a
Thread being allocated in different locations for different executions.
Brian Norris [Tue, 9 Oct 2012 01:42:22 +0000 (18:42 -0700)]
schedule: bugfix - fix typo in wake
The Thread should be re-enabled, not disabled, when waking up.
Brian Norris [Tue, 9 Oct 2012 01:36:06 +0000 (18:36 -0700)]
user_main: pass remaining arguments to the user program
Brian Norris [Tue, 9 Oct 2012 01:34:35 +0000 (18:34 -0700)]
main: rename 'real_main()' to 'model_main()'
Brian Demsky [Tue, 9 Oct 2012 00:20:20 +0000 (17:20 -0700)]
mistake
Brian Demsky [Tue, 9 Oct 2012 00:19:32 +0000 (17:19 -0700)]
be much more careful about sending values backwards...
also implement hashing for traces...just an easy way to confirm whether we lose new traces...
Brian Demsky [Mon, 8 Oct 2012 21:48:47 +0000 (14:48 -0700)]
be even more aggressive about sleep sets...
if an action was sleeping, it should only read from a value that could potentially result in synchronization with a release done while it was sleeping
Brian Norris [Mon, 8 Oct 2012 20:53:42 +0000 (13:53 -0700)]
mymemory: re-indent
Brian Norris [Mon, 8 Oct 2012 20:51:58 +0000 (13:51 -0700)]
model: stack-allocated vector should use ModelAlloc
Brian Norris [Mon, 8 Oct 2012 20:46:11 +0000 (13:46 -0700)]
utilize SnapshotAlloc STL allocator
Brian Norris [Mon, 8 Oct 2012 20:36:11 +0000 (13:36 -0700)]
mymemory: add SnapshotAlloc STL allocator
Now, we just need to go through the tedious process of rewriting all our
STL definitions
Brian Norris [Mon, 8 Oct 2012 20:26:57 +0000 (13:26 -0700)]
mymemory: implement snapshot_*() allocations on model-checker's heap
Brian Norris [Mon, 8 Oct 2012 20:26:07 +0000 (13:26 -0700)]
mymemory: add basic model_snapshot_space
I will begin to utilize the 'model_snapshot_space' as the
model-checker's private snapshotting heap.
Brian Norris [Mon, 8 Oct 2012 20:04:24 +0000 (13:04 -0700)]
rename again (snapshot_space -> user_snapshot_space)
I will be adding a separate model_snapshot_space
Brian Norris [Mon, 8 Oct 2012 20:11:13 +0000 (13:11 -0700)]
mymemory: kill system_malloc()
Not needed
Brian Norris [Mon, 8 Oct 2012 19:58:01 +0000 (12:58 -0700)]
snapshot: use snapshot_space only in mprotect-based
We don't need this heap for fork-based snapshotting, so clearly separate
the functionality here.
This also makes PageAlignedAdressUpdate() available only for
mprotect-based snapshotting.
Brian Norris [Mon, 8 Oct 2012 19:46:53 +0000 (12:46 -0700)]
snapshot: don't need any snapshotting space for fork-based
I have no idea why this was here in the first place. Somebody didn't
know what they were doing...
Brian Norris [Mon, 8 Oct 2012 19:38:53 +0000 (12:38 -0700)]
rename 'mySpace' to 'snapshot_space'
Brian Norris [Mon, 8 Oct 2012 19:34:22 +0000 (12:34 -0700)]
mymemory: make DontFree() static
Brian Norris [Mon, 8 Oct 2012 19:30:06 +0000 (12:30 -0700)]
mymemory: reformat spacing
Brian Norris [Mon, 8 Oct 2012 19:21:15 +0000 (12:21 -0700)]
mymemory: kill system_free()
This function is not used
Brian Norris [Mon, 8 Oct 2012 19:13:07 +0000 (12:13 -0700)]
snapshot: remove global 'basemySpace'
Why was this here?
Brian Norris [Mon, 8 Oct 2012 17:31:41 +0000 (10:31 -0700)]
test: linuxrwlocks: fixup spacing
Brian Norris [Mon, 8 Oct 2012 17:25:29 +0000 (10:25 -0700)]
model: remove todo
Brian Demsky [Mon, 8 Oct 2012 08:21:35 +0000 (01:21 -0700)]
merge massive speedup with release sequence support...
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
Conflicts:
schedule.cc
schedule.h
Brian Demsky [Mon, 8 Oct 2012 08:15:06 +0000 (01:15 -0700)]
add support for sleep sets...
Brian Norris [Mon, 8 Oct 2012 06:30:48 +0000 (23:30 -0700)]
test: add "double release sequence" test
This test uses two separate load-acquire's to establish the same release
sequence. This can cause problems with the current release sequence
fixups, so that we find an execution where one synchronizes and the
other doesn't, even when reading from the same sequence.
Brian Norris [Mon, 8 Oct 2012 06:25:48 +0000 (23:25 -0700)]
Merge branch 'norris'
Brian Norris [Mon, 8 Oct 2012 06:24:21 +0000 (23:24 -0700)]
model: add todo synchronization comment
Brian Norris [Mon, 8 Oct 2012 06:16:03 +0000 (23:16 -0700)]
model: be sure trace is "final feasible" before continuing to fixup
Release sequences fixup can break pretty badly if there are outstanding
promises. Solution: check for final-feasible traces before continuing to
fixup.
Brian Norris [Mon, 8 Oct 2012 05:19:01 +0000 (22:19 -0700)]
tests: add some normal loads/stores to test data races
These tests had become less useful, since the model-checker would ignore
release sequence fixup in the absence of pending data races. So add some
normal loads and stores to our tests, inducing some data races and some
proper synchronization.
Brian Norris [Mon, 8 Oct 2012 05:17:12 +0000 (22:17 -0700)]
model: check data races during release sequence fixup
This solves two problems:
1. I wasn't even checking for resolved data races after fixing up
release sequence(s)
2. Launching of release sequence fixups now requires that there be
pending data races
Brian Norris [Sun, 7 Oct 2012 22:23:37 +0000 (15:23 -0700)]
model: add release sequence model_thread ASSERT()
This ASSERT() should ensure that model-checker threads are always
'future_ordered'.
Brian Norris [Sat, 6 Oct 2012 02:20:21 +0000 (19:20 -0700)]
model: launch release sequence fixup actions when necessary
This should complete the "release sequence fixup" step. The ModelChecker
will launch new fixup actions, associating them with the special
'model_thread'.
Brian Norris [Sat, 6 Oct 2012 02:18:13 +0000 (19:18 -0700)]
model: add special model-checker Thread to ModelChecker
Note the change in take_step(), so that we base the "current thread" off
of the provided ModelAction, rather than thread_current() (i.e., the
Scheduler). This is because the Scheduler will never run the
model-checker thread.
Brian Norris [Sat, 6 Oct 2012 01:29:45 +0000 (18:29 -0700)]
schedule: do not allow model-checker thread to enter scheduler
Brian Norris [Sat, 6 Oct 2012 00:50:37 +0000 (17:50 -0700)]
threads: add constructor for model-checker thread
This thread will never have its own stack, and it should never be
inserted into the Scheduler.
Brian Norris [Sat, 6 Oct 2012 00:42:03 +0000 (17:42 -0700)]
threads: add flag for a special type of "model-checker thread"
Special model-checker thread(s) might be needed when producing special
model-checker ModelActions.
Brian Norris [Sat, 6 Oct 2012 00:39:49 +0000 (17:39 -0700)]
action: add Thread parameter to constructor
We will need to create ModelActions that are forced to associate with a
specific Thread (contrary to the Scheduler's knowledge), so add a
constructor parameter.
Brian Norris [Fri, 5 Oct 2012 07:07:10 +0000 (00:07 -0700)]
model: add process_relseq_fixup()
This performs the bulk of the release sequence finalization step.
Brian Norris [Sat, 6 Oct 2012 02:34:01 +0000 (19:34 -0700)]
common: improve backtrace function
Utilize freely-available backtrace function that helps make output more
readable. Previous implementation is kept for now, as it is simpler and
more well-tested.
Brian Norris [Sat, 6 Oct 2012 02:28:19 +0000 (19:28 -0700)]
add stacktrace header, under WTFPL
Download:
http://idlebox.net/2008/0901-stacktrace-demangled/stacktrace.h
WTFPL:
http://sam.zoy.org/wtfpl/
Brian Norris [Sun, 7 Oct 2012 23:18:07 +0000 (16:18 -0700)]
model: wire up rest of release seq. resolution backtracking
I still need to actually initiate the special ModelAction fixups.
Brian Norris [Sun, 7 Oct 2012 23:12:00 +0000 (16:12 -0700)]
nodestack: add release sequence breakage backtracking
End-of-execution resolution of release sequences requires a search
procedure in which we test various attempts at breaking our pending
release sequences. This provides the NodeStack infrastructure.
Brian Norris [Fri, 5 Oct 2012 05:38:37 +0000 (22:38 -0700)]
action: add MODEL_FIXUP_RELSEQ action_type
This type will be used as a special model-checker action for fixing up
release sequences. Each action corresponds to "finalizing" one release
sequence: either force a particular write to break the sequence or else
allow the synchronization to occur.
Currently, this action_type won't do anything, as it's not hooked up in
ModelChecker.
Brian Norris [Sun, 7 Oct 2012 22:04:08 +0000 (15:04 -0700)]
model: disabled threads are "future ordered"
If a Thread is not currently enabled, then it will synchronize with
another (currently-enabled) Thread if/when it wakes up. Thus, it
qualifies as "future ordered" within the release sequence code: it
cannot contribute future writes that will break current pending release
sequences.
Brian Norris [Sun, 7 Oct 2012 22:02:16 +0000 (15:02 -0700)]
model: use proper size_t printf format
Brian Norris [Sun, 7 Oct 2012 21:57:42 +0000 (14:57 -0700)]
schedule: add is_enabled() function
The release sequence functionality needs to check whether a Thread is
currently enabled (rather than finding this information in a particular
Node).
Also, rename the (private) 'is_enabled' field to avoid a name conflict.
Brian Demsky [Sat, 6 Oct 2012 01:50:24 +0000 (18:50 -0700)]
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
Brian Demsky [Sat, 6 Oct 2012 00:15:49 +0000 (17:15 -0700)]
create enumeration for enabled information...switch from bools to the enumeration
Brian Norris [Sat, 6 Oct 2012 00:07:49 +0000 (17:07 -0700)]
cyclegraph: fix indentation
Brian Norris [Sat, 6 Oct 2012 00:03:01 +0000 (17:03 -0700)]
cyclegraph: flag cycles for reflexive edges
The cyclegraph shouldn't fail (i.e., ASSERT()) when reflexive edges are
added; instead, they should be declared as cycles.
Brian Demsky [Fri, 5 Oct 2012 02:44:14 +0000 (19:44 -0700)]
1) more comments
2) rename is_synchronizing with
3) realize that reordering is only necessary if we create a synchronization...not needed to break one...
Brian Demsky [Fri, 5 Oct 2012 00:37:38 +0000 (17:37 -0700)]
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
Brian Demsky [Fri, 5 Oct 2012 00:37:12 +0000 (17:37 -0700)]
changes
Brian Norris [Thu, 4 Oct 2012 21:59:44 +0000 (14:59 -0700)]
nodestack: destroy Nodes properly in ~NodeStack()
Brian Norris [Thu, 4 Oct 2012 21:57:37 +0000 (14:57 -0700)]
nodestack: use initializer list
Brian Norris [Thu, 4 Oct 2012 19:11:05 +0000 (12:11 -0700)]
model: remove unnecessary boolean variable
Brian Norris [Thu, 4 Oct 2012 19:42:13 +0000 (12:42 -0700)]
model: assign "pending" return values in release_seq_heads()
Now that the lazy pending release sequences list is improved, return
more information from release_seq_heads().
Note that this change also affects the behavior of the last double loop;
now, even after discovering write(s) from one thread that might break the
release sequence, I continue exploring other threads. This has some pros
and cons:
Con:
* may cause more work in exploring many threads without gaining any
extra information
Pro:
* may help discover a write that *certainly* breaks the sequence,
whereas previously, we might have exited with an uncertain status
* builds a more thorough, complete set of writes that might break the
release sequence
The last point is the main intention, since we will require a complete
set for end-of-execution fixups. The others balance out to a net benefit
(and possibly a bugfix).