Transcript A Fast Multi-Scale Method for Drawing Large Graphs

A Portable Virtual Machine
for Program Debugging
and Directing
Camil Demetrescu
University of Rome “La Sapienza”
Irene Finocchi
University of Rome “Tor Vergata”
Motivation
Devising powerful methodologies and
tools for assuring software reliability
Directors
reactive systems that monitor the run-time
environment reacting to events generated
by the processes
What kind of events? Variable referencing, program
interruption, memory allocation/ deallocation,
function calls, memory accesses...
Difficulties of implementation
• Low-level OS primitives
• Instrumenting assembly
code
portability
• Instrumenting
source code
programming
efforts, flexibility
• Interpreted
execution
efficiency
(high level languages)
Directing through virtual
machines
Interpreting intermediate level languages
(e.g., Java bytecodes)
• Capabilities of introspection
• Targeting multiple languages
• Targeting “difficult” languages (C, C++
need instructions to manipulate addresses)
• Running in reversible mode
(very useful for error localization)
Our contribution
The Leonardo Virtual Machine
Provides advanced facilities for implementing
directors with low effort:
Fine grained monitoring of memory accesses
Reversible computing capabilities
Continuous monitoring (not just on demand)
by means of a flexible event handling
mechanism
Architectural layers
Interpreted applications
(directors, visualizers,
analysis tools)
Native applications
(editors, compilers)
Leonardo Virtual
Machine
Virtual
CPU
Kernel
Leonardo Library (LL-Win32, LL-Qt)
Hardware / operating system
Virtual CPU
• Stack-based
 Only 5 registers
 About 100 elementary instructions
 About 180 lines of C code
• Handlers installed by external clients are
executed at critical instructions (e.g.,
ld / st / jsr / rts)
Memory protection
• Typically, processes prevented from getting
outside their logical address space
• … but how to avoid damages inside it?
Memory mask for detecting illegal
accesses to each memory word
2 bits per
word
Stack protection
• 101 out of 107 VCPU instructions access
the top of the stack
• Run-time checks for overflow / underflow
would be very inefficient
• Combine compile-time & run-time checking
• Static analysis to compute max stack
usage in a subroutine
• Run-time checks necessary only on
function calls (jsr)
Reversibility
• State = registers + memory image
• Incremental log of state changes
• Only special points are checkpointable
Forward execution: at each checkpoint a new
log record is pushed onto a history stack
Log record = addresses + values of memory words
changed in the transaction
Backward execution: the log record on the top
of the history stack is used to restore the state
Optimizations
Buffering techniques to reduce I/Os
Multiple changes of the same word are not saved
Stack optimization: data over the top of the
execution stack are not part of the state
saved in the
log record
transaction
Stack-preserving transactions
• A stack-preserving transaction pushes temporary
data on the top of the stack and pop them
leaving the final height unchanged
• LVM executables satisfy this property:
transactions between consecutive
checkpoints within the same subroutine are
stack-preserving
• We support reversibility at different granularities
Event handling: an example
#include <lvm.h>
#define LINE 4096
static ui4 sMems;
static ui4 sMiss;
static ui4 sB;
/* # of mem accesses */
/* # of cache misses */
/* current line address */
void _MemAccessH(ui4 inBase, ui4 inSize){
ui4 theB1 = inBase/LINE;
ui4 theB2 = (inBase+inSize-1)/LINE;
if (sB != theB1) { sB = theB1; ++sMiss; }
if (sB != theB2) { sB = theB2; ++sMiss; }
++sMems;
}
Event handling: an example
void main(){
/* create new process */
ui4 thePID = KNewProc(“bubblesort.leo”, 0, 0);
/* install mem access handlers */
KNewAsyncEvtH(thePID, KMEM_READ_EVENT,
0, (KEvtHT)_MemAccessH);
KNewAsyncEvtH(thePID, KMEM_WRITE_EVENT,
0, (KEvtHT)_MemAccessH);
/* start process, wait for termination */
KStartProc(thePID);
KWaitSyncEvtH(thePID, KHALT_EVENT,0, NULL);
}
/* output results */
KPuts("# Mem accesses = "); KPrintlnUI4(sMems);
KPuts("# Cache misses = "); KPrintlnUI4(sMiss);
Experiments: running times
Experiments: history log
Future work
Trading time for space: a (partial) re-execution
based approach to reversibility
Implementation of directors:
 memory monitor
 tools for software visualization
Just in time compilation
Further information and source code at:
http://www.leonardo-vm.org/
Feedback is welcome!