10 years agoMerge branch 'brian'
Brian Norris [Tue, 3 Jul 2012 21:16:02 +0000 (14:16 -0700)]
Merge branch 'brian'

10 years agoAdding relevant comments for fork based implementation.
Subramanian Ganapathy [Thu, 21 Jun 2012 19:21:37 +0000 (12:21 -0700)]
Adding relevant comments for fork based implementation.

10 years agoMakefile: compile *.cc separately
Brian Norris [Tue, 3 Jul 2012 19:54:03 +0000 (12:54 -0700)]
Makefile: compile *.cc separately

This Makefile rule doesn't have to include all *.cc files at once. They can be
compiled separately.

Note that this slows down compilation slightly, but it also allows better
parallel (jobserver) compilation; for example, you can use `make -j4' to
perform separate compilations using 4 different threads, utilizing a multi-core
system more effectively.

10 years agonodestack: revert may_read_from to a normal member variable, not pointer
Brian Norris [Tue, 3 Jul 2012 18:03:51 +0000 (11:03 -0700)]
nodestack: revert may_read_from to a normal member variable, not pointer

Because we don't control the 'new' operator for STL sets, I can't properly
ensure that it is allocated in non-snapshotting memory. So just make
may_read_from a normal member variable within class Node, so that its
initial 'allocation' is performed as part of the instantiation of its
subsuming Node object.

10 years agoaction: add {get,set}_value(), assign default value
Brian Norris [Tue, 3 Jul 2012 16:23:11 +0000 (09:23 -0700)]
action: add {get,set}_value(), assign default value

10 years agoadd documentation
Brian Norris [Mon, 25 Jun 2012 20:24:50 +0000 (13:24 -0700)]
add documentation

10 years agonodestack: only create may_read_from sets for read operations
Brian Norris [Mon, 25 Jun 2012 19:22:31 +0000 (12:22 -0700)]
nodestack: only create may_read_from sets for read operations

10 years agonodestack: re-associate ModelAction/Node relationship
Brian Norris [Mon, 25 Jun 2012 19:07:39 +0000 (12:07 -0700)]
nodestack: re-associate ModelAction/Node relationship

Currently, the Node that is returned by ModelAction::get_node() actually
represents the Node that is parent to the ModelAction. This works well for
some of the backtracking computations (since the backtracking set is held
in the parent Node), but it creates confusion when performing computations
such as the following:

 Node *node;
 ModelAction *act = node->get_action();
 Node *node2 = act->get_parent();

 ASSERT(node == node2); // Fails
 ASSERT(node->get_parent() == node2); // Succeeds

So this patch changes this behavior so that the first assertion (above)
succeeds and the second one fails. This is probably more desirable in the
long run.

10 years agonodestack: add Node::get_parent() function
Brian Norris [Mon, 25 Jun 2012 18:47:24 +0000 (11:47 -0700)]
nodestack: add Node::get_parent() function

As I add more complicated backtracking and may-read-from relationships,
each Node might need some structural information to be able to reach its
parent Node.

To support this:
* the NodeStack should provide the parent information via Node constructor
* the Node should provide a get_parent() method

10 years agomodel: make print_list() into a static C function
Brian Norris [Thu, 21 Jun 2012 22:13:56 +0000 (15:13 -0700)]
model: make print_list() into a static C function

This function does not need to be a class member function. It only performs
a standard 'printing' option on a STL list of ModelAction objects.

10 years agomodel: make comment more accurate
Brian Norris [Thu, 21 Jun 2012 18:17:40 +0000 (11:17 -0700)]
model: make comment more accurate

add_action_to_lists() does not only work on the per-object, per-thread action
list. It performs several pieces of bookkeeping.

10 years agoaction: add const qualifier
Brian Norris [Thu, 21 Jun 2012 18:16:38 +0000 (11:16 -0700)]
action: add const qualifier

10 years agoclockvector: add const qualifiers
Brian Norris [Thu, 21 Jun 2012 09:38:31 +0000 (02:38 -0700)]
clockvector: add const qualifiers

10 years agoclockvector: add documentation
Brian Norris [Thu, 21 Jun 2012 09:37:47 +0000 (02:37 -0700)]
clockvector: add documentation

10 years agoMerge branch 'sandbox' (remove finalize())
Brian Norris [Thu, 21 Jun 2012 09:11:15 +0000 (02:11 -0700)]
Merge branch 'sandbox' (remove finalize())

Merge in the fix from Subramanian and me that eliminates the need for a
finalize() call. It was a kind of bug, in a way, that hopefully is fixed now...

10 years agosnapshot: switch back to mprotect-based snapshotting
Brian Norris [Thu, 21 Jun 2012 09:10:12 +0000 (02:10 -0700)]
snapshot: switch back to mprotect-based snapshotting

Subramanian accidentally switched this configuration macro in his last

10 years agomodel: build up 'may_read_from' set
Brian Norris [Thu, 21 Jun 2012 09:04:11 +0000 (02:04 -0700)]
model: build up 'may_read_from' set

Finally wire up the model-checker so that it builds the may_read_from set
for every 'read' action. I think this is working OK, although I don't have
much to really test it on yet.

Also, improve comments to describe the process in check_current_action().

10 years agomodel: add build_reads_from_past() function
Brian Norris [Thu, 21 Jun 2012 08:59:01 +0000 (01:59 -0700)]
model: add build_reads_from_past() function

Add function that will build up the initial set of all past writes that a
'read' action may read from.

10 years agoaction: add happens_before() function
Brian Norris [Thu, 21 Jun 2012 08:56:50 +0000 (01:56 -0700)]
action: add happens_before() function

Now I can easily compare two ModelActions with the happens_before()
relationship. Of course, the clock vectors are not fully complete yet, but
this sets the stage...

10 years agoclockvector: fix 'happens_before', change name to 'synchronized_since'
Brian Norris [Thu, 21 Jun 2012 08:48:03 +0000 (01:48 -0700)]
clockvector: fix 'happens_before', change name to 'synchronized_since'

First, the 'happens_before' function needed to use an inclusive 'less-than'
(i.e., <=) instead of 'strictly less-than' (i.e., <) in order to fit with
most of the algorithm.

Second, the association of 'happens_before' directly with the ClockVector is
not very intuitive to use. I will write an additional happens_before()
function that can easily compare two ModelAction objects. So change this
happens_before() (with it awkward usage) to be called synchronized_since(),
representing whether the ClockVector's thread has previously synchronized
with the ModelAction's thread.

10 years agoaction: add 'get_cv()' accessor function
Brian Norris [Thu, 21 Jun 2012 08:05:15 +0000 (01:05 -0700)]
action: add 'get_cv()' accessor function

10 years agonodestack: add 'may_read_from' set
Brian Norris [Thu, 21 Jun 2012 07:54:01 +0000 (00:54 -0700)]
nodestack: add 'may_read_from' set

Each Node (at least, each Node that is a 'read') will be associated with a
may_read_from set - the set of all possible ModelActions to read from. For now,
this interface handles only actions that exist in the past. It won't properly
retain information from future actions.

10 years agonodestack: don't perform linear search to check if backtrack is empty
Brian Norris [Tue, 19 Jun 2012 23:33:52 +0000 (16:33 -0700)]
nodestack: don't perform linear search to check if backtrack is empty

Add a simple add/remove counter to record when threads are 'added' and
'removed' from the backtracking set.

10 years agoaction: add const qualifiers
Brian Norris [Tue, 19 Jun 2012 23:00:57 +0000 (16:00 -0700)]
action: add const qualifiers

10 years agoaction: replace condition check with ASSERT()
Brian Norris [Tue, 19 Jun 2012 22:51:06 +0000 (15:51 -0700)]
action: replace condition check with ASSERT()

Now that the ModelChecker and NodeStack have been refactored a bit, I don't
need to rely on create_cv() to avoid overwriting a previously-existing
clockvector; create_cv() will now be called at most once per ModelAction. So
change this condition to an ASSERT().

10 years agonodestack/model: refactor explore_action(), change return semantics
Brian Norris [Tue, 19 Jun 2012 22:44:13 +0000 (15:44 -0700)]
nodestack/model: refactor explore_action(), change return semantics

ModelChecker would like to know when a new ModelAction is being inserted
into the NodeStack vs. when the new ModelAction should be discarded in
favor of a pre-existing one (due to replay). So I change the semantics of
NodeStack::explore_action() such that it does not always return a
ModelAction; now it returns NULL if the ModelAction was accepted into the
NodeStack, otherwise returning the ModelAction that was already in the

Now, ModelChecker can choose when to create new clock vectors as well as
other operations (to come) that may be performed only upon *first*
exploration of a new ModelAction.

Additionally, ModelChecker is now responsible for free-ing the ModelAction
if it is not going to be kept in NodeStack.

There should be no change in functionality.

10 years agonodestack: more documentation
Brian Norris [Tue, 19 Jun 2012 17:30:19 +0000 (10:30 -0700)]
nodestack: more documentation

10 years agocyclegraph: make this compile...
Brian Norris [Tue, 19 Jun 2012 17:04:58 +0000 (10:04 -0700)]
cyclegraph: make this compile...

You need 'inttypes' for 'uintptr_t'

10 years agoMerge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
Brian Demsky [Mon, 18 Jun 2012 18:44:13 +0000 (11:44 -0700)]
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker

10 years agobuilds
Brian Demsky [Mon, 18 Jun 2012 18:43:32 +0000 (11:43 -0700)]

10 years agoadd hashtable
Brian Demsky [Sun, 17 Jun 2012 13:10:35 +0000 (06:10 -0700)]
add hashtable

10 years agoDoxyfile: exclude malloc.c
Brian Norris [Fri, 15 Jun 2012 06:55:25 +0000 (23:55 -0700)]
Doxyfile: exclude malloc.c

I don't think we really want documentation for the dlmalloc code. It provides
several Doxygen warnings/complaints, and it muddies up some of the output HTML.
Maybe we can fix this up somehow later, but it's not really worth doing right

10 years agoMerge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker
Brian Demsky [Fri, 15 Jun 2012 06:29:55 +0000 (14:29 +0800)]
Merge branch 'master' of ssh://demsky.eecs.uci.edu/home/git/model-checker

10 years agofixup some doc wording
Brian Norris [Fri, 15 Jun 2012 06:20:20 +0000 (23:20 -0700)]
fixup some doc wording

10 years agoadd more documentation
Brian Norris [Fri, 15 Jun 2012 06:09:05 +0000 (23:09 -0700)]
add more documentation

I'm trying to add doxygen comments next to the definitions (not the
declaration) as much as possible, to keep the documentation as close to the
actual code as much as possible, helping to prevent errors as functionality

10 years agosubramanian lied when he said he fixed these...
Brian Demsky [Fri, 15 Jun 2012 05:59:42 +0000 (13:59 +0800)]
subramanian lied when he said he fixed these...

10 years agoMakefile: force `make docs' to depend on all source files
Brian Norris [Fri, 15 Jun 2012 05:51:30 +0000 (22:51 -0700)]
Makefile: force `make docs' to depend on all source files

That way, if I change a file that might have documentation comments in it,
`make docs' will rerun doxygen.

10 years ago(snapshot) removing mbFinalize and usage of finalize
Subramanian Ganapathy [Thu, 14 Jun 2012 23:13:59 +0000 (16:13 -0700)]
(snapshot) removing mbFinalize and usage of finalize

Now there is no need for finalize mechanism at all.
All that was required was resetting the rollback id

10 years agosnapshot: refactor the fork-based stack initialization
Brian Norris [Thu, 14 Jun 2012 22:31:44 +0000 (15:31 -0700)]
snapshot: refactor the fork-based stack initialization

This complicated code block uses a getcontext()/setcontext() pair with an
'alreadySwapped' boolean (int) to perform basically the same functionality as
'swapcontext()'. Refactor this code to make it simpler.

10 years agosnapshot: remove unused 'uc_link' context
Brian Norris [Thu, 14 Jun 2012 22:30:25 +0000 (15:30 -0700)]
snapshot: remove unused 'uc_link' context

The 'currentContext' variable was never initialized, and so doesn't perform any
useful functionality as a 'uc_link' address. Remove it.

10 years agosnapshotimp: reindent file
Brian Norris [Thu, 14 Jun 2012 16:29:42 +0000 (09:29 -0700)]
snapshotimp: reindent file

10 years agosnapshot: don't put entire if (...) on one line
Brian Norris [Thu, 14 Jun 2012 16:28:15 +0000 (09:28 -0700)]
snapshot: don't put entire if (...) on one line

It's harder to read the failure conditions if you put if (...) and the
following statement all on one line.

10 years agosnapshot: define macros with type size_t
Brian Norris [Thu, 14 Jun 2012 16:22:31 +0000 (09:22 -0700)]
snapshot: define macros with type size_t

The SHARED_MEMORY_DEFAULT and STACK_SIZE_DEFAULT macros need to be of type
size_t, so cast them when they're defined, not when they're used.

10 years agosnapshot: use (void *) instead of (char *)
Brian Norris [Thu, 14 Jun 2012 16:19:41 +0000 (09:19 -0700)]
snapshot: use (void *) instead of (char *)

10 years agosnapshot: rearrange #if a little
Brian Norris [Thu, 14 Jun 2012 16:16:47 +0000 (09:16 -0700)]
snapshot: rearrange #if a little

HandlePF() is only used in mprotect-based snapshotting, so keep it entirely
within the #if block.

10 years agosnapshot: remove extra blank lines
Brian Norris [Thu, 14 Jun 2012 06:57:01 +0000 (23:57 -0700)]
snapshot: remove extra blank lines

10 years agosnapshot: make other file-scope functions static
Brian Norris [Thu, 14 Jun 2012 06:55:45 +0000 (23:55 -0700)]
snapshot: make other file-scope functions static

10 years agosnapshot: don't export page-aligning functions
Brian Norris [Thu, 14 Jun 2012 06:53:44 +0000 (23:53 -0700)]
snapshot: don't export page-aligning functions

Declare these functions static and move them upward in the file.

10 years agorename struct Snapshot_t => struct Snapshot
Brian Norris [Thu, 14 Jun 2012 06:51:07 +0000 (23:51 -0700)]
rename struct Snapshot_t => struct Snapshot

10 years agosnapshot: don't declare sTheRecord in both #if and #else
Brian Norris [Thu, 14 Jun 2012 06:39:59 +0000 (23:39 -0700)]
snapshot: don't declare sTheRecord in both #if and #else

10 years agosnapshot: remove 'extern "C"' block
Brian Norris [Thu, 14 Jun 2012 06:28:10 +0000 (23:28 -0700)]
snapshot: remove 'extern "C"' block

We do not need to wrap this function in 'extern "C"' for two reasons:

1) It's not actually exported and used in C code
2) You only need this sort of declaration in the header file that may be
   included in both C++ and C compilation. But snapshot.cc should only be
   compiled by the C++ compiler, and snapshot.h is not included in any C

10 years agosnapshot-interface: don't export SnapshotGlobalSegments()
Brian Norris [Thu, 14 Jun 2012 06:20:43 +0000 (23:20 -0700)]
snapshot-interface: don't export SnapshotGlobalSegments()

SnapshotGlobalSegments() is only used within snapshot-interface.cc, so declare
it static and remove it from the header.

10 years agosnapshot: replace DumpIntoLog() with lighter-weight debugging
Brian Norris [Thu, 14 Jun 2012 06:13:29 +0000 (23:13 -0700)]
snapshot: replace DumpIntoLog() with lighter-weight debugging

This file I/O "debug" messaging gets in the way. Make the debugging code simple
and succinct, or don't put it in at all. Now, you can enabled SnapShot
debugging by adding this near the top of snapshot.cc:


10 years agosnapshot: move comments to the right place
Brian Norris [Thu, 14 Jun 2012 05:08:57 +0000 (22:08 -0700)]
snapshot: move comments to the right place

10 years agoRemoving comment asking to fix fork(), has been fixed now
Subramanian Ganapathy [Wed, 13 Jun 2012 20:07:22 +0000 (13:07 -0700)]
Removing comment asking to fix fork(), has been fixed now

10 years agofixing calloc(), fix Makefile
Subramanian Ganapathy [Wed, 13 Jun 2012 19:58:54 +0000 (12:58 -0700)]
fixing calloc(), fix Makefile

Adding sbrk() calls and hooked into free also to avoid freeing sbrked memory...
checked both fork and paged implementation. seems to work Also everytime we
switch between fork and paged impl, we need to rebuild so adding snapshot.h as
dependency to mymemory.cc in makefile

10 years agolibatomic: perform write before context switch
Brian Norris [Thu, 7 Jun 2012 00:34:47 +0000 (17:34 -0700)]
libatomic: perform write before context switch

Atomic actions block a thread at the "switch_to_master" function call, so under
the current structure (which isn't quite fit for relaxed modeling yet...) we
should perform the memory write before calling "switch_to_master".

If not, we can observe sequences like the following, where x is an atomic
variable. All actions are seq_cst:

 Initially, x = 0

 Thread    Action
 ------    ------
 1         r1 = x;       // r1 = 0
 1          x = r1 + 1;  //  x = 1, not stored yet?
 2         r2 = x;       // r2 = 0
 2          x = r2       //  x = 1, not stored yet?

Then, depending on scheduling, Thread 1 or Thread 2 might complete first, with
its write being performed *after* it receives control again.

10 years ago.gitignore: ignore docs directory
Brian Norris [Wed, 6 Jun 2012 19:22:07 +0000 (12:22 -0700)]
.gitignore: ignore docs directory

10 years agoaction: fix some comments
Brian Norris [Wed, 6 Jun 2012 16:48:54 +0000 (09:48 -0700)]
action: fix some comments

10 years agoMakefile: have `mrclean' depend on `clean'
Brian Norris [Wed, 6 Jun 2012 16:46:44 +0000 (09:46 -0700)]
Makefile: have `mrclean' depend on `clean'

10 years agomore comments
Brian Demsky [Wed, 6 Jun 2012 09:16:04 +0000 (02:16 -0700)]
more comments

10 years agomore doc changes
Brian Demsky [Wed, 6 Jun 2012 09:01:38 +0000 (02:01 -0700)]
more doc changes

10 years agomore documentation
Brian Demsky [Wed, 6 Jun 2012 08:53:30 +0000 (01:53 -0700)]
more documentation

10 years ago1) Add more comments.
Brian Demsky [Wed, 6 Jun 2012 08:46:49 +0000 (01:46 -0700)]
1) Add more comments.
2) Change is_dependent to is_synchronizing and make it capture actual synchronizing behavior...
3) Add more support for RMW operations.

10 years agomore documentation
Brian Demsky [Wed, 6 Jun 2012 07:45:15 +0000 (00:45 -0700)]
more documentation

10 years agomore docs
Brian Demsky [Wed, 6 Jun 2012 07:13:23 +0000 (00:13 -0700)]
more docs

10 years agoadd support for docs
Brian Demsky [Wed, 6 Jun 2012 06:51:02 +0000 (23:51 -0700)]
add support for docs

10 years agosnapshot: zero out entire siginfo_t
Brian Norris [Tue, 5 Jun 2012 19:54:52 +0000 (12:54 -0700)]
snapshot: zero out entire siginfo_t

We should initialize this variable to all zeros, just to be safe.

10 years agoChanges needed to run on OS X... Example runs on my laptop now. No need to push...
Brian Demsky [Mon, 4 Jun 2012 05:35:41 +0000 (22:35 -0700)]
Changes needed to run on OS X...  Example runs on my laptop now.  No need to push code back and forth to test...

Out of time for fun hack, have to get back to real work now.  :(

10 years agohack some stuff towards running on mac... unrelated bugs still..
Brian Demsky [Mon, 4 Jun 2012 01:05:39 +0000 (18:05 -0700)]
hack some stuff towards running on mac...  unrelated bugs still..

10 years agosnapshot: remove duplicate definition of finalize()
Brian Norris [Thu, 31 May 2012 18:40:25 +0000 (11:40 -0700)]
snapshot: remove duplicate definition of finalize()

finalize() was moved to snapshot-interface.h but wasn't removed from snapshot.h

10 years agouse EXIT_SUCCESS and EXIT_FAILURE
Brian Norris [Thu, 31 May 2012 02:49:03 +0000 (19:49 -0700)]

We were wildly inconsistent with our exit status. We might as well follow the
C standard.

10 years agouserprog: use atomics allocated on "heap"
Brian Norris [Thu, 31 May 2012 02:42:07 +0000 (19:42 -0700)]
userprog: use atomics allocated on "heap"

Just for kicks, since snapshotting is working properly. We might as well test

10 years agoAdding fixes for the fork based implementation, also removed some redundant code...
Subramanian Ganapathy [Wed, 30 May 2012 23:52:38 +0000 (16:52 -0700)]
Adding fixes for the fork based implementation, also removed some redundant code pointed to by Prof. Demsky

10 years agocheck in message
Brian Demsky [Wed, 30 May 2012 07:23:38 +0000 (00:23 -0700)]
check in message

10 years agosnapshot-interface: replace Subramanian's /proc/*/maps checking
Brian Norris [Tue, 29 May 2012 20:37:33 +0000 (13:37 -0700)]
snapshot-interface: replace Subramanian's /proc/*/maps checking

Subramanian's code needed rewriting. It didn't actual snapshot any globals, and
it was also written so that it would never snapshot libmodel.so. I rewrite this
code and fix these problems, after Brian Demsky has fixed the problem with
dynamic linking of the HandlePF() code.

10 years agofix bug...this is another evil one...
Brian Demsky [Wed, 30 May 2012 07:18:44 +0000 (00:18 -0700)]
fix bug...this is another evil one...

10 years agonode: do not use static member variable
Brian Norris [Wed, 30 May 2012 15:06:02 +0000 (08:06 -0700)]
node: do not use static member variable

Static member variables of a class are going to be snapshotted. Move them so
they aren't static in order to prevent this.

(This can create interesting behavior, where the "total number of nodes
created" is decreasing at times!)

10 years agosnapshot: move declarations to the right interface header
Brian Norris [Wed, 30 May 2012 06:35:15 +0000 (23:35 -0700)]
snapshot: move declarations to the right interface header

We should have a minimal set of code/declarations in the snapshot-interface.h
header. And it should not include other headers unless necessary. With this
change, the model checker code only needs to use snapshot-interface.h.

10 years agosnapshot: rename MyFuncPtr to VoidFuncPtr
Brian Norris [Wed, 30 May 2012 06:29:06 +0000 (23:29 -0700)]
snapshot: rename MyFuncPtr to VoidFuncPtr

Better descriptive name.

10 years agosnapshot: rename USE_CHECKPOINTING to USE_MPROTECT_SNAPSHOT
Brian Norris [Wed, 30 May 2012 06:20:37 +0000 (23:20 -0700)]

"Checkpointing" is a generic name for either method. USE_MPROTECT_SNAPSHOT is a
more descriptive name.

10 years agosnapshot-interface: don't redefine PAGESIZE
Brian Norris [Tue, 29 May 2012 20:22:09 +0000 (13:22 -0700)]
snapshot-interface: don't redefine PAGESIZE

10 years agosnapshot-interface: bugfix - fixup array indeces
Brian Norris [Tue, 29 May 2012 19:30:35 +0000 (12:30 -0700)]
snapshot-interface: bugfix - fixup array indeces

When removing code, I missed a few magic numbers in the code.

10 years agonodestack: push 'create_cv' functionality responsibility back to ModelChecker
Brian Norris [Tue, 29 May 2012 17:46:42 +0000 (10:46 -0700)]
nodestack: push 'create_cv' functionality responsibility back to ModelChecker

It doesn't really make sense to have NodeStack call the 'create_cv' function
for a ModelAction. This commit separates the functionality of 'explore_action'
from 'create_cv', calling each separately from the higher-level
'check_current_action' model-checking function.

10 years agomodel: thread creation establishes synchronization
Brian Norris [Tue, 29 May 2012 17:29:59 +0000 (10:29 -0700)]
model: thread creation establishes synchronization

First, I add a get_parent_action() wrapper which finds either the last action
in the current thread (get_last_action()) or if NULL, finds the parent
thread-creation action.

Then, using this functionality, I provide the correct 'parent' to the
explore_action() function, which performs the clock-vector creation.

10 years agothreads: add 'creation' information
Brian Norris [Tue, 29 May 2012 17:21:06 +0000 (10:21 -0700)]
threads: add 'creation' information

The 'creation' field will hold the ModelAction that created the thread. For the
main user-thread, this is NULL.

10 years agolibthreads: pass 'class Thread' object as ModelAction 'location'
Brian Norris [Tue, 29 May 2012 17:17:23 +0000 (10:17 -0700)]
libthreads: pass 'class Thread' object as ModelAction 'location'

Currently, the 'location' parameter is unused for THREAD_CREATE. I need to
provide a reference from a Thread object to the ModelAction which created it,
so I will use this parameter as an entry point into the ModelChecker, which can
build the necessary reference later.

10 years agomodel: move bookkeeping to add_action_to_lists()
Brian Norris [Mon, 28 May 2012 19:58:56 +0000 (12:58 -0700)]
model: move bookkeeping to add_action_to_lists()

I keep a lot of bookkeeping info for efficiently locating ModelActions (e.g.,
in lists, maps, vectors). Let's just perform the dirty calculations in a single
function to help separate logical functions a little better.

10 years agomodel: set 'last action in thread' as an action's parent
Brian Norris [Mon, 28 May 2012 19:45:54 +0000 (12:45 -0700)]
model: set 'last action in thread' as an action's parent

This is a step toward synchronizing clock vectors properly: on exploration of
an action, we use only the last action in the current thread as the 'parent'
(or NULL).

Note that this still does not include the parent thread in determining each
ModelAction's parent.

10 years agomodel: log the last action in each thread
Brian Norris [Mon, 28 May 2012 19:42:54 +0000 (12:42 -0700)]
model: log the last action in each thread

The last action in each thread is needed for some model-checking computations.
This could be expanded to a full-fledged per-thread list if needed...

10 years agonodestack: compute parent ModelAction externally
Brian Norris [Mon, 28 May 2012 19:20:01 +0000 (12:20 -0700)]
nodestack: compute parent ModelAction externally

For a particular ModelAction, the 'parent' may be the last action in the
current thread, or otherwise, the action in the parent thread that created the
current thread. This calculation is not suitable for within the NodeStack (and
the current implementation is wrong, taking the last action performed by *any*
thread as the parent). Thus, I set up the method calls to pass the 'parent' to
explore_action() and leave the details to further work.

10 years agoclockvector: fixup initialization
Brian Norris [Mon, 28 May 2012 19:12:04 +0000 (12:12 -0700)]
clockvector: fixup initialization

Two related fixes:

Even if parent is NULL, pass the current ModelAction to ClockVector

When no parent is present, do not make special case for initializing
clock[0] = 1. This is only correct for a single case (the root Action)
and is already handled in other ways.

10 years agonodestack: construct Node with 'number of threads', not 'parent node'
Brian Norris [Mon, 28 May 2012 17:16:34 +0000 (10:16 -0700)]
nodestack: construct Node with 'number of threads', not 'parent node'

I don't really want to base the number of threads off of a 'parent'; I can
just record the global 'number of threads' as a Node parameter.

10 years agomodel: add obj_thrd_map
Brian Norris [Sat, 26 May 2012 02:17:51 +0000 (19:17 -0700)]
model: add obj_thrd_map

Provides a mapping of ModelActions so that we can efficiently sort through the
actions on a particular object (memory location) in a particular thread.

10 years agoMakefile: add 'make debug'
Brian Norris [Sat, 26 May 2012 01:35:27 +0000 (18:35 -0700)]
Makefile: add 'make debug'

This is sort of hacky, but it works! Now (after cleaning), you can recompile
with 'make debug' to enable my debugging features (not Subramanian's).

10 years agoaction: enhance print() message
Brian Norris [Sat, 26 May 2012 02:19:15 +0000 (19:19 -0700)]
action: enhance print() message

Include clock vector, realign

10 years agonodestack: create ModelAction clock vectors
Brian Norris [Sat, 26 May 2012 02:16:06 +0000 (19:16 -0700)]
nodestack: create ModelAction clock vectors

Only create the clock vector if the ModelAction will be retained in our
nodestack, and hence will be used for synchronization, etc.

10 years agoaction: add create_cv() and read_from()
Brian Norris [Sat, 26 May 2012 02:13:36 +0000 (19:13 -0700)]
action: add create_cv() and read_from()

These functions provide basic wrapper functionality for creating and updating
the clock vector for a particular ModelAction.

10 years agoclockvector: bugfix - fixup vector initialization, size
Brian Norris [Sat, 26 May 2012 03:28:58 +0000 (20:28 -0700)]
clockvector: bugfix - fixup vector initialization, size

This fixes a few bugs in ClockVector:

- The parent-less vector is the initial-thread creation, so set its vector
  clock[0] = 1
- The clock vector's data should be initialized to 0
- A clock vector cannot determine its size simply by the size of its parent (+1
  if 'act' is THREAD_CREATE); other threads could have been created, giving an
  inconsistent result here. Instead of trying to be smart about calculating
  num_threads from the parent, then, I just ask for it globally.

10 years agomodel: add get_num_threads()
Brian Norris [Sat, 26 May 2012 03:28:30 +0000 (20:28 -0700)]
model: add get_num_threads()