nodestack: don't create empty base node
authorBrian Norris <banorris@uci.edu>
Thu, 13 Dec 2012 03:57:44 +0000 (19:57 -0800)
committerBrian Norris <banorris@uci.edu>
Sat, 15 Dec 2012 01:56:11 +0000 (17:56 -0800)
commit2d9c8d86e9a5050786c5f83ab6f18cd583984279
tree74b78cae7a9ee08c9aca414efc372a49a5e7af8d
parent545b5f4d69e8156d7f1b9560170262303156bbf1
nodestack: don't create empty base node

We don't actually need an empty base node, since the first thread will
never be backtracked. But it does mean that we no longer assume that
every newly-constructed Node has a parent.

Note that this changes the number of executions performed for some
programs. Even though the model-checker should be deterministic, this is
not a bug, AFAICT. The discrepancy seems to come from a change in
scheduling, where the scheduler order may differ after reaching a
divergence point. This is caused by the fairness support which is hacked
into Node creation, so threads may gain priority sooner in the presence
of a useless Node. In fact, before this change, (almost?) every
execution caused a thread (typically thread 1) to gain priority due to
fairness. Now, we reach this condition much more occasionally.

I made measurements of the scheduling decisions based on priority for
the execution of:

 # ./run.sh test/linuxrwlocks.o -f 10 -m 2

Previously, threads gained priority 10042 times in 7906 executions (9947
of those were for thread 1, when it would shortly become disabled).

Now, threads gain priority 68 times in 8396 executions (thread 1 never
gains priority).
nodestack.cc
nodestack.h