Unpredictability and particularly irreproducibility is associated with this non-conventional internal state:
If one was able to capture the internal state of the HAVEGE generator at a given point then he/she would be (theoretically) able to replicate the generated sequence from this point until the next occurrence of an interruption or until a new external event on the system bus or the memory system.
Capturing the internal state on the fly is unfeasible:
However, collecting the internal state of the HAVEGE generator is infeasible
at user-level. The user itself cannot collect and reestablish the internal
state. For instance, to indirectly determine that a particular cache
block was present, one has to access it, but then other internal states
are modified (similar to Heisenberg's criteria).
Following the internal state is unfeasible:
Another possible mean to reproduce the sequence would be to set
the internal state of the generator in a known state at the beginning of
execution. Then, one can try to follow the sequence of instructions
through only monitoring external events to the process.
The internal state at the initiation of the generator depends on many
parameters such as the exact date of launching (cycle accurate), the exact
contents
of the disk, their response time (cycle accurate), the memory content,
etc.
Moreover to follow the internal state, one has also to be able to monitor
every external events, but also internal events during the initiliazation
phase.
An analysis of the internal state of HAVEGE on an UltraSparc II
We describe below part of the volatile information that belongsto the internal state of the HAVEGE generator on an UltraSparc II workstation. A very similar analysis can be done for the other processors.
L1 Data cache From the HAVEGE generator, each of the 512 32-byte cache lines of the L1 data cache can be considered as in one of seven possible states. Either it maps one of the two possible 32-byte blocks A0 or A1 from the Walk table or it maps a block irrelevant from HAVEGE. If it maps a relevant block then it maps only one or or both the 16-byte subblocks. That is, the L1 cache is in one of 7**512 possible states.
Data TLB The loop in HAVEGE touches 128 memory pages. From the HAVEGE algorithm perspective, an entry in the data TLB has 129 possible states: mapping one of the 128 pages or mapping another (irrelevant) page. The data TLB on the Ultrasparc features 64 entries and is fully associative. From the HAVEGE generator perspective, the internal hardware state is represented by an ordered set of 64 pages. In normal mode, i.e long after the last interruption, these pages all belong to the Walk table: there are such 128!/ 64! such possible combinations.
L1 instruction cache
The inner loop body in the self modifying walk (just) fits in the L1 instruction cache. The L1 instruction cache is two-way set-associative and branch prediction is embedded in the instructioncache. It features 256 sets.
Only two instruction blocks I0 and I1 from the main HAVEGE loop are mapped onto a given sets of the instruction cache. A LRU replacement policy is implemented on the instruction cache. Therefore, from the HAVEGE perspective, each set has 7 different possible states, B being an instruction block independent from the HAVEGE algorithm: (I0, I1), (I1, I0), ( B, I0), (B, I1), (I0, B), (I1, B) and (B, B). Then from HAVEGE perspective, the instruction cache can be in at least different states 256**7.
On the UltraSparc II, the instruction cache also handles the branch prediction for both targets and directions. For targets, from the HAVEGE perspective, two states are visible: either the target is correct or it is not. For the Ultrasparc II, the main loop in HAVEGE features 151 conditional branches and 75 calls. From the HAVEGE perspective, the target prediction generator features at least 2**226 different states. A 2-bit counter is associated with each conditional branch, therefore from the HAVEGE perspective, the branch predictor can be at least in 4**150 different states.
Summary
Considering only the three memorization structures above, it appears that the internal state of the HAVEGE generator includes thousands of binary internal volatile hardware states. A significant fraction of these states are destructed (modified) on each interruption. Each of these states influences the self modifying walks in HAVEGE.
Moreover, many other volatile hardware states (pipeline states, buffer
contents and status, L2 caches, etc.) are part of the HAVEGE internal state.
Some of the volatile hardware states touched by an operating system interrupt
that are part of the internal HAVEGE state are correlated. For instance
when an instruction block is evicted then its associated branch prediction
information is also evicted, moreover the next instruction block has also
a high probability to be also evicted. Nevertheless, there is little correlation
between the blocks evicted from the data cache, and the blocks evicted
from the instruction cache, or between the branch prediction information
destructed and the pages evicted from the data TLB.