You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by gs...@apache.org on 2007/04/13 20:26:28 UTC
svn commit: r528575 [5/6] - in /harmony/enhanced/drlvm/trunk:
src/test/regression/H3225/ vm/vmcore/include/ vm/vmcore/src/verifier/
Modified: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_real.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_real.h?view=diff&rev=528575&r1=528574&r2=528575
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_real.h (original)
+++ harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_real.h Fri Apr 13 11:26:27 2007
@@ -17,7 +17,7 @@
/**
* @author Pavel Rebriy, Alexei Fedotov
* @version $Revision: 1.1.2.3.4.4 $
- */
+ */
#ifndef _VERIFIER_REAL_H_
@@ -45,55 +45,97 @@
*/
//===========================================================
/**
- * Define debug mode for verifier.
+ * Defines a debug mode for verifier.
*/
#ifdef NDEBUG
-#define _VERIFY_DEBUG 0
+#define _VF_DEBUG 0
#else // NDEBUG
-#define _VERIFY_DEBUG 1
+#define _VF_DEBUG 1
#endif // NDEBUG
/**
- * Debugging and trace message defines.
- * @note Debug messages is available only in debug mode,
- * trace messages is available in any mode.
- * @note Verifier trace looks like: 'verifier' + component of verifier
- */
-#if _VERIFY_DEBUG
-#define VERIFY_DEBUG(info) ECHO("vf_debug: " << info)
-#else // _VERIFY_DEBUG
-#define VERIFY_DEBUG(info)
-#endif // _VERIFY_DEBUG
-#define VERIFY_TRACE(comp, mess) TRACE2("verifier." comp, mess)
-#define VERIFY_REPORT(context, error_message ) \
- { \
- stringstream stream; \
- stream << error_message; \
- vf_set_error_message( stream, (context) ); \
- }
-#define VERIFY_REPORT_CLASS(context, method, error_message ) \
- VERIFY_REPORT(context, \
- "(class: " << class_get_name( (context)->m_class ) \
- << ", method: " << method_get_name( method ) \
- << method_get_descriptor( method ) \
- << ") " << error_message )
-#define VERIFY_REPORT_METHOD(context, error_message ) \
- VERIFY_REPORT_CLASS(context, (context)->m_method, error_message )
+ * Both debug and trace channels are available only at debug mode.
+ * A debug channel is visible for a user while a trace channel should be
+ * enabled via <code>-Xtrace:verifier</code> command line option.
+ */
+#if _VF_DEBUG
+#define VF_DEBUG( info ) ECHO( "vf_debug: " << info )
+#define VF_DUMP( category, expr ) { \
+ static LogSite logSite = { UNKNOWN, NULL }; \
+ if( logSite.state && is_trace_enabled( "vfdump." category, &logSite ) ) { \
+ expr; \
+ } \
+}
+#define VF_STOP assert(0)
+#else
+#define VF_DEBUG(info)
+#define VF_DUMP(category, expr)
+#define VF_STOP DIE("Aborted at " __FILE__ "(" << __LINE__ << ")")
+#endif // _VF_DEBUG
+
+#define VF_TRACE(comp, message) TRACE2("verifier." comp, message)
+/**
+ * Verifer dump domains. They can be specified in a command line in
+ * a following form <code>-Xtrace:vfdump.<domain></code>.
+ */
+/** Type constraints for a class. */
+#define DUMP_CONSTRAINT "constraint"
+/** An instruction array. */
+#define DUMP_INSTR "instr"
+/** A control flow graph. */
+#define DUMP_GRAPH "graph"
+/** A graph with cleaned dead nodes and inlined subroutines. */
+#define DUMP_MOD "mod_graph"
+/** A graph in a dot format. */
+#define DUMP_DOT "dot"
+/** A modified graph in a dot format. */
+#define DUMP_DOT_MOD "mod_dot"
+/** Node map vectors. */
+#define DUMP_NODE_MAP "map.node"
+/** Instruction map vectors. */
+#define DUMP_INSTR_MAP "map.instr"
+/** Merged map vectors. */
+#define DUMP_MERGE_MAP "map.merge"
+/** A path to subroutine <code>ret</code> instruction. */
+#define DUMP_NODESTACK "node.stack"
+
+
+/** Store a verification error in a verification context. */
+#define VF_SET_CTX( ctx, error_message ) \
+{ \
+ stringstream stream; \
+ stream << error_message; \
+ vf_set_error_message( stream, ( ctx ) ); \
+}
+
+/** Dump a current class and method. */
+#define VF_REPORT_CTX( ctx ) "(class: " << class_get_name( (ctx)->m_class ) \
+ << ", method: " << method_get_name( (ctx)->m_method ) \
+ << method_get_descriptor( (ctx)->m_method ) << ") "
+
+/** Report a verification error. */
+#define VF_REPORT( ctx, error_message ) \
+ VF_SET_CTX( ctx, VF_REPORT_CTX( ctx ) << error_message )
+
+/** Abort a verifier abnormally. */
+#define VF_DIE( error_message ) \
+ VF_DEBUG( "Verifer aborted: " << error_message ); \
+ VF_STOP;
/**
* Define source code line and source file name parameters and arguments.
*/
-#if _VERIFY_DEBUG
-#define VERIFY_SOURCE_PARAMS UNREF int line_, UNREF const char *file_
-#define VERIFY_SOURCE_ARGS0 __LINE__, __FILE__
-#define VERIFY_SOURCE_ARGS1 line_, file_
-#define VERIFY_REPORT_SOURCE file_ << "(" << line_ << "): "
-#else // _VERIFY_DEBUG
-#define VERIFY_SOURCE_PARAMS int
-#define VERIFY_SOURCE_ARGS0 0
-#define VERIFY_SOURCE_ARGS1 0
-#define VERIFY_REPORT_SOURCE ""
-#endif // _VERIFY_DEBUG
+#if _VF_DEBUG
+#define VF_SOURCE_PARAMS UNREF int line_, UNREF const char *file_
+#define VF_SOURCE_ARGS0 __LINE__, __FILE__
+#define VF_SOURCE_ARGS1 line_, file_
+#define VF_REPORT_SOURCE file_ << "(" << line_ << "): "
+#else // _VF_DEBUG
+#define VF_SOURCE_PARAMS int
+#define VF_SOURCE_ARGS0 0
+#define VF_SOURCE_ARGS1 0
+#define VF_REPORT_SOURCE ""
+#endif // _VF_DEBUG
//===========================================================
// Verifier contant pool checks
@@ -103,64 +145,64 @@
* Constant pool checks.
*/
// for handler id = 0 is legal value
-#define CHECK_HANDLER_CONST_POOL_ID( id, len, context ) \
- if( (id) >= (len) ) { \
- VERIFY_REPORT_METHOD( context, "Illegal constant pool index in handler" ); \
- return VER_ErrorHandler; \
+#define CHECK_HANDLER_CONST_POOL_ID( id, len, ctx ) \
+ if( (id) >= (len) ) { \
+ VF_REPORT( ctx, "Illegal constant pool index in handler" ); \
+ return VER_ErrorHandler; \
}
// for handler id = 0 is legal value
-#define CHECK_HANDLER_CONST_POOL_CLASS( context, id ) \
- if( (id) && class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_Class ) { \
- VERIFY_REPORT_METHOD( context, "Illegal type in constant pool for handler, " \
- << id << ": CONSTANT_Class is expected" ); \
- return VER_ErrorHandler; \
+#define CHECK_HANDLER_CONST_POOL_CLASS( ctx, id ) \
+ if( (id) && class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_Class ) { \
+ VF_REPORT( ctx, "Illegal type in constant pool for handler, " \
+ << id << ": CONSTANT_Class is expected" ); \
+ return VER_ErrorHandler; \
}
-#define CHECK_CONST_POOL_ID( id, len, context ) \
- if( !(id) || (id) >= (len) ) { \
- VERIFY_REPORT_METHOD( context, "Illegal constant pool index" ); \
- return VER_ErrorConstantPool; \
+#define CHECK_CONST_POOL_ID( id, len, ctx ) \
+ if( !(id) || (id) >= (len) ) { \
+ VF_REPORT( ctx, "Illegal constant pool index" ); \
+ return VER_ErrorConstantPool; \
}
-#define CHECK_CONST_POOL_CLASS( context, id ) \
- if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_Class ) { \
- VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, " \
- << id << ": CONSTANT_Class is expected" ); \
- return VER_ErrorConstantPool; \
+#define CHECK_CONST_POOL_CLASS( ctx, id ) \
+ if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_Class ) { \
+ VF_REPORT( ctx, "Illegal type in constant pool, " \
+ << id << ": CONSTANT_Class is expected" ); \
+ return VER_ErrorConstantPool; \
}
-#define CHECK_CONST_POOL_METHOD( context, id ) \
- if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_Methodref ) { \
- VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, " \
- << id << ": CONSTANT_Methodref is expected" ); \
- return VER_ErrorConstantPool; \
+#define CHECK_CONST_POOL_METHOD( ctx, id ) \
+ if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_Methodref ) { \
+ VF_REPORT( ctx, "Illegal type in constant pool, " \
+ << id << ": CONSTANT_Methodref is expected" ); \
+ return VER_ErrorConstantPool; \
}
-#define CHECK_CONST_POOL_INTERFACE( context, id ) \
- if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_InterfaceMethodref ) { \
- VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, " \
- << id << ": CONSTANT_InterfaceMethodref is expected" ); \
- return VER_ErrorConstantPool; \
+#define CHECK_CONST_POOL_INTERFACE( ctx, id ) \
+ if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_InterfaceMethodref ) { \
+ VF_REPORT( ctx, "Illegal type in constant pool, " \
+ << id << ": CONSTANT_InterfaceMethodref is expected" ); \
+ return VER_ErrorConstantPool; \
}
-#define CHECK_CONST_POOL_FIELD( context, id ) \
- if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_Fieldref ) { \
- VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, " \
- << id << ": CONSTANT_Fieldref is expected" ); \
- return VER_ErrorConstantPool; \
+#define CHECK_CONST_POOL_FIELD( ctx, id ) \
+ if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_Fieldref ) { \
+ VF_REPORT( ctx, "Illegal type in constant pool, " \
+ << id << ": CONSTANT_Fieldref is expected" ); \
+ return VER_ErrorConstantPool; \
}
-#define CHECK_CONST_POOL_TYPE( context, id ) \
- if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_NameAndType ) { \
- VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, " \
- << id << ": CONSTANT_NameAndType is expected" ); \
- return VER_ErrorConstantPool; \
+#define CHECK_CONST_POOL_TYPE( ctx, id ) \
+ if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_NameAndType ) { \
+ VF_REPORT( ctx, "Illegal type in constant pool, " \
+ << id << ": CONSTANT_NameAndType is expected" ); \
+ return VER_ErrorConstantPool; \
}
-#define CHECK_CONST_POOL_STRING( context, id ) \
- if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_String ) { \
- VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, " \
- << id << ": CONSTANT_String is expected" ); \
- return VER_ErrorConstantPool; \
+#define CHECK_CONST_POOL_STRING( ctx, id ) \
+ if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_String ) { \
+ VF_REPORT( ctx, "Illegal type in constant pool, " \
+ << id << ": CONSTANT_String is expected" ); \
+ return VER_ErrorConstantPool; \
}
-#define CHECK_CONST_POOL_UTF8( context, id ) \
- if( class_get_cp_tag( (context)->m_class, (id) ) != _CONSTANT_Utf8) { \
- VERIFY_REPORT_METHOD( context, "Illegal type in constant pool, " \
- << id << ": CONSTANT_Utf8 is expected" ); \
- return VER_ErrorConstantPool; \
+#define CHECK_CONST_POOL_UTF8( ctx, id ) \
+ if( class_get_cp_tag( (ctx)->m_class, (id) ) != _CONSTANT_Utf8) { \
+ VF_REPORT( ctx, "Illegal type in constant pool, " \
+ << id << ": CONSTANT_Utf8 is expected" ); \
+ return VER_ErrorConstantPool; \
}
//===========================================================
@@ -168,9 +210,15 @@
//===========================================================
/**
+ * Verifier error codes.
+ */
+typedef Verifier_Result vf_Result;
+
+/**
* Constraint check types enum.
*/
-typedef enum {
+typedef enum
+{
VF_CHECK_NONE = 0,
VF_CHECK_PARAM,
VF_CHECK_ASSIGN,
@@ -186,12 +234,13 @@
VF_CHECK_INVOKESPECIAL,
VF_CHECK_UNINITIALIZED_THIS,
VF_CHECK_NUM
-} vf_CheckConstraint_t;
+} vf_CheckConstraint;
/**
* Stack map entry types enum.
*/
-typedef enum {
+typedef enum
+{
// original types
SM_TOP = 0,
SM_INT,
@@ -199,35 +248,35 @@
SM_NULL,
SM_REF,
SM_UNINITIALIZED,
- SM_UNINITIALIZED_THIS,
SM_LONG_LO,
SM_DOUBLE_LO,
SM_LONG_HI,
SM_DOUBLE_HI,
SM_RETURN_ADDR,
// additional types
+ SM_ANY, // matches any value
SM_COPY_0,
SM_COPY_1,
SM_COPY_2,
SM_COPY_3,
SM_UP_ARRAY,
- SM_RETURN,
- SM_TERMINATE,
SM_WORD,
SM_WORD2_LO,
SM_WORD2_HI,
SM_NUMBER
-} vf_MapType_t;
+} vf_MapType;
/**
* Each instruction has a descriptive bitmap.
*/
-typedef enum {
- VF_TYPE_INSTR_NONE = 0,
- VF_TYPE_INSTR_RETURN = 1,
- VF_TYPE_INSTR_THROW = 2,
- VF_TYPE_INSTR_SUBROUTINE = 3
-} vf_CodeType;
+typedef enum
+{
+ VF_INSTR_NONE = 0,
+ VF_INSTR_RETURN = 1,
+ VF_INSTR_THROW = 2,
+ VF_INSTR_JSR = 3,
+ VF_INSTR_RET = 4
+} vf_InstrType;
//===========================================================
// Verifier predefined structures
@@ -235,37 +284,147 @@
/**
* @ingroup Handles
- * The handle of the verifier context.
+ * A handle of a verifier context.
+ */
+typedef const struct vf_Context *vf_ContextHandle;
+/**
+ * @ingroup Handles
+ * A handle of a subroutine information.
+ */
+typedef const struct vf_SubContext *vf_SubContextHandle;
+/**
+ * @ingroup Handles
+ * A graph handle.
+ */
+typedef const class vf_Graph *vf_GraphHandle;
+/**
+ * @ingroup Handles
+ * A handle of a graph node.
+ */
+typedef const struct vf_Node *vf_NodeHandle;
+/**
+ * @ingroup Handles
+ * A map vector handle.
+ */
+typedef const struct vf_MapVector *vf_MapVectorHandle;
+/**
+ * @ingroup Handles
+ * A handle of an instruction.
+ */
+typedef const struct vf_Instr *vf_InstrHandle;
+
+//===========================================================
+// Code instruction structures.
+//===========================================================
+
+/**
+ * Valid types structure.
+ */
+struct vf_ValidType
+{
+ unsigned number; ///< number of types
+ const char *string[1]; ///< type array
+};
+
+/**
+ * Stack map entry structure.
+ */
+struct vf_MapEntry
+{
+ vf_ValidType *m_vtype; ///< valid type for reference
+ union
+ {
+ unsigned m_new; ///< program count of opcode new for uninitialized
+ unsigned m_pc; ///< program count of return address for subroutine
+ };
+ union
+ {
+ unsigned short m_local; ///< number of local variable
+ unsigned short m_index; ///< constant pool index for access check
+ };
+ unsigned short m_type:5; ///< stack map type @see vf_MapType
+ unsigned short m_ctype:4; ///< constraint type @see vf_CheckConstraint
+ unsigned short m_is_local:1; ///< local variable modify flag
+ ///< true - modify local, false - modify stack
+};
+
+/**
+ * A bytecode instruction.
+ */
+struct vf_Instr
+{
+ unsigned char *m_addr; ///< a start of a bytecode instruction
+ unsigned *m_off; ///< an array of instruction branches
+ vf_MapEntry *m_invector; ///< a stack map IN instruction vector
+ vf_MapEntry *m_outvector; ///< a stack map OUT instruction vector
+ unsigned m_offcount; ///< a number of instruction branches
+ union
+ {
+ vf_NodeHandle m_node; ///< contains a node handle if the corresponding
+ ///< basic block starts at the instruction, <code>NULL</code> otherwise
+ bool m_is_bb_start; ///< if this is a begin of a basic block
+ };
+ unsigned short m_minstack; ///< a minimal stack for instruction
+ unsigned short m_inlen; ///< an IN stack vector length
+ unsigned short m_outlen; ///< an OUT stack vector length
+ short m_stack; ///< a stack change
+ vf_InstrType m_type; ///< an instruction type @see vf_InstrType
+};
+
+/**
+ * A byte of a bytecode.
+ */
+struct vf_BCode
+{
+ vf_InstrHandle m_instr; ///< a pointer to vf_Context.m_instr
+ bool m_is_bb_start:1; ///< <code>true</code> if the block starts here
+};
+
+/**
+ * Constant pool parse structure.
*/
-typedef const struct vf_Context* vf_ContextHandle;
+union vf_Parse
+{
+ struct
+ {
+ vf_MapEntry *m_invector; ///< method IN stack vector
+ vf_MapEntry *m_outvector; ///< method OUT stack vector
+ const char *m_name; ///< invoked method name
+ unsigned short m_inlen; ///< IN vector length
+ unsigned short m_outlen; ///< OUT vector length
+ } method;
+ struct
+ {
+ vf_MapEntry *f_vector; ///< field type map vector
+ unsigned short f_vlen; ///< field type map vector len
+ } field;
+};
-/// Verifier context structure.
-typedef struct vf_Context vf_Context_t;
-/// Verifier structure for a byte of a bytecode.
-typedef struct vf_BCode vf_BCode_t;
-/// Verifier valid types structure.
-typedef struct vf_ValidType vf_ValidType_t;
-/// Verifier stack map entry structure.
-typedef struct vf_MapEntry vf_MapEntry_t;
-/// Verifier code instruction structure.
-typedef struct vf_Code vf_Code_t;
-/// Verifier constant pool parse structure.
-typedef union vf_Parse vf_Parse_t;
-/// Verifier graph structure declaration.
-class vf_Graph;
-/// Verifier type constraint structure.
-typedef struct vf_TypeConstraint vf_TypeConstraint_t;
-/// Verifier hash table structure.
-typedef struct vf_Hash vf_Hash_t;
-/// Verifier hash table entry structure.
-typedef struct vf_HashEntry vf_HashEntry_t;
-/// Verifier pool structure.
-typedef struct vf_VerifyPool vf_VerifyPool_t;
-/// Verifier pool internal structure.
-typedef struct vf_VerifyPoolInternal vf_VerifyPoolInternal_t;
-/// Verifier structure of class loader constraint data.
-typedef struct vf_ClassLoaderData vf_ClassLoaderData_t;
+//===========================================================
+// Pool structures.
+//===========================================================
+
+/**
+ * Internal structure of memory pool.
+ */
+struct vf_PoolInternal
+{
+ void *m_memory; ///< pool entry memory
+ char *m_free; ///< free space in pool entry
+ vf_PoolInternal *m_next; ///< next pool entry
+ size_t m_freesize; ///< size of free space in pool entry
+};
+/**
+ * Head structure of memory pool.
+ */
+struct vf_Pool
+{
+ vf_PoolInternal *m_pool; ///< pool entry
+ size_t m_memory; ///< allocated memory size
+ size_t m_used; ///< used memory size
+ size_t m_maxuse; ///< max used memory size
+};
//===========================================================
// Verifier memory management functions diclarations
@@ -274,219 +433,127 @@
/**
* Memory pool entry size.
*/
-#define VERIFY_POOL_ENTRY_SIZE 0x2000
+#define VF_POOL_ENTRY_SIZE 0x2000
/**
* Macros hide source line and source file name function arguments.
*/
-#define vf_error() \
- vf_error_func(VERIFY_SOURCE_ARGS0)
-#define vf_calloc(number, size_element) \
- vf_calloc_func((number), (size_element), VERIFY_SOURCE_ARGS0)
-#define vf_malloc(size) \
- vf_malloc_func((size), VERIFY_SOURCE_ARGS0)
-#define vf_free(pointer) \
- vf_free_func((pointer), VERIFY_SOURCE_ARGS0)
-#define vf_realloc(pointer, resize) \
- vf_realloc_func((pointer), (resize), VERIFY_SOURCE_ARGS0)
-#define vf_create_pool() \
- vf_create_pool_func(VERIFY_SOURCE_ARGS0)
-#define vf_alloc_pool_memory(pool, size) \
- vf_alloc_pool_memory_func((pool), (size), VERIFY_SOURCE_ARGS0)
-#define vf_clean_pool_memory(pool) \
- vf_clean_pool_memory_func((pool), VERIFY_SOURCE_ARGS0)
-#define vf_delete_pool(pool) \
- vf_delete_pool_func((pool), VERIFY_SOURCE_ARGS0)
-
-/**
- * Function performs abend exit from VM.
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
- * @see VERIFY_SOURCE_PARAMS
- * @see vf_error
- */
-void
-vf_error_func( VERIFY_SOURCE_PARAMS );
+#define vf_calloc(number, size_element) \
+ vf_calloc_func((number), (size_element), VF_SOURCE_ARGS0)
+#define vf_malloc(size) \
+ vf_malloc_func((size), VF_SOURCE_ARGS0)
+#define vf_free(pointer) \
+ vf_free_func((pointer), VF_SOURCE_ARGS0)
+#define vf_realloc(pointer, resize) \
+ vf_realloc_func((pointer), (resize), VF_SOURCE_ARGS0)
+#define vf_create_pool() \
+ vf_create_pool_func(VF_SOURCE_ARGS0)
+#define vf_palloc(pool, size) \
+ vf_palloc_func((pool), (size), VF_SOURCE_ARGS0)
+#define vf_clean_pool(pool) \
+ vf_clean_pool_func((pool), VF_SOURCE_ARGS0)
+#define vf_delete_pool(pool) \
+ vf_delete_pool_func((pool), VF_SOURCE_ARGS0)
/**
* Function allocates an array in memory with elements initialized to zero.
* @param number - number of elements
* @param element_size - size of element
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
* @return Pointer to allocated memory block.
- * @see VERIFY_SOURCE_PARAMS
+ * @see VF_SOURCE_PARAMS
* @see vf_calloc
* @note Assertion is raised if <i>number</i> or <i>element_size</i>
* are equal to zero or if out of memory error is arisen.
* @note Trace is available with argument <b>verifier:memory</b>.
*/
-void *
-vf_calloc_func( unsigned number, size_t element_size, VERIFY_SOURCE_PARAMS );
+void *vf_calloc_func( unsigned number, size_t element_size,
+ VF_SOURCE_PARAMS );
/**
* Function allocates memory blocks.
* @param size - size of memory block
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
* @return Pointer to allocated memory block.
- * @see VERIFY_SOURCE_PARAMS
+ * @see VF_SOURCE_PARAMS
* @see vf_malloc
* @note Assertion is raised if <i>size</i> is equal to zero
* or if out of memory error is arisen.
* @note Trace is available with argument <b>verifier:memory</b>.
*/
-void *
-vf_malloc_func( size_t size, VERIFY_SOURCE_PARAMS );
+void *vf_malloc_func( size_t size, VF_SOURCE_PARAMS );
/**
* Function releases allocated memory blocks.
* @param pointer - pointer to allocated block
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
- * @see VERIFY_SOURCE_PARAMS
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @see VF_SOURCE_PARAMS
* @see vf_free
* @note Assertion is raised if <i>pointer</i> is equal to null.
* @note Trace is available with argument <b>verifier:memory</b>.
*/
-void
-vf_free_func( void *pointer, VERIFY_SOURCE_PARAMS );
+void vf_free_func( void *pointer, VF_SOURCE_PARAMS );
/**
* Function reallocates memory blocks.
* @param pointer - pointer to allocated block
* @param resize - new size of memory block
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
* @return Pointer to reallocated memory block.
- * @see VERIFY_SOURCE_PARAMS
+ * @see VF_SOURCE_PARAMS
* @see vf_realloc
* @note Assertion is raised if <i>resize</i> is equal to zero
* or if out of memory error is arisen.
* @note If <i>pointer</i> is equal to null function works like vf_malloc_func.
* @note Trace is available with argument <b>verifier:memory</b>.
*/
-void *
-vf_realloc_func( void *pointer, size_t resize, VERIFY_SOURCE_PARAMS );
+void *vf_realloc_func( void *pointer, size_t resize, VF_SOURCE_PARAMS );
/**
* Function creates memory pool structure.
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
* @return Pointer to created memory pool.
- * @see VERIFY_SOURCE_PARAMS
+ * @see VF_SOURCE_PARAMS
* @see vf_create_pool
- * @see vf_VerifyPool_t
+ * @see vf_Pool
* @note Trace is available with argument <b>verifier:memory:pool</b>.
*/
-vf_VerifyPool_t *
-vf_create_pool_func( VERIFY_SOURCE_PARAMS );
+vf_Pool *vf_create_pool_func( VF_SOURCE_PARAMS );
/**
* Function allocates memory blocks in current pool.
* @param pool - pointer to memory pool structure
* @param size - memory block size
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
* @return Pointer to allocated memory block.
- * @see VERIFY_SOURCE_PARAMS
- * @see vf_alloc_pool_memory
- * @see vf_VerifyPool_t
+ * @see VF_SOURCE_PARAMS
+ * @see vf_palloc
+ * @see vf_Pool
* @note Trace is available with argument <b>verifier:memory:pool</b>.
*/
-void *
-vf_alloc_pool_memory_func( vf_VerifyPool_t *pool, size_t size, VERIFY_SOURCE_PARAMS );
+void *vf_palloc_func( vf_Pool *pool, size_t size, VF_SOURCE_PARAMS );
/**
* Function cleans given pool.
* @param pool - memory pool structure
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
- * @see VERIFY_SOURCE_PARAMS
- * @see vf_clean_pool_memory
- * @see vf_VerifyPool_t
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @see VF_SOURCE_PARAMS
+ * @see vf_clean_pool
+ * @see vf_Pool
* @note Trace is available with argument <b>verifier:memory:pool</b>.
*/
-void
-vf_clean_pool_memory_func( vf_VerifyPool_t *pool, VERIFY_SOURCE_PARAMS );
+void vf_clean_pool_func( vf_Pool *pool, VF_SOURCE_PARAMS );
/**
* Function releases memory from given pool.
* @param pool - memory pool structure
- * @note <i>VERIFY_SOURCE_PARAMS</i> - debug parameters source line and source file name
- * @see VERIFY_SOURCE_PARAMS
+ * @note <i>VF_SOURCE_PARAMS</i> - debug parameters source line and source file name
+ * @see VF_SOURCE_PARAMS
* @see vf_delete_pool
- * @see vf_VerifyPool_t
+ * @see vf_Pool
* @note Trace is available with argument <b>verifier:memory:pool</b>.
*/
-void
-vf_delete_pool_func( vf_VerifyPool_t *pool, VERIFY_SOURCE_PARAMS );
-
-//===========================================================
-// Code instruction structures.
-//===========================================================
-
-/**
- * A byte of a bytecode.
- */
-struct vf_BCode {
- unsigned m_instr; ///< a number + 1 of code instruction at
- ///< vf_Context.m_code
- unsigned m_mark : 1; ///< control flow branch flag
-};
-
-/**
- * Valid types structure.
- */
-struct vf_ValidType {
- unsigned number; ///< number of types
- const char *string[1]; ///< type array
-};
-
-/**
- * Stack map entry structure.
- */
-struct vf_MapEntry {
- vf_ValidType_t *m_vtype; ///< valid type for reference
- union {
- unsigned m_new; ///< program count of opcode new for uninitialized
- unsigned m_pc; ///< program count of return address for subroutine
- };
- union {
- unsigned short m_local; ///< number of local variable
- unsigned short m_index; ///< constant pool index for access check
- };
- unsigned short m_type : 5; ///< stack map type @see vf_MapType_t
- unsigned short m_ctype : 4; ///< constraint type @see vf_CheckConstraint_t
- unsigned short m_is_local : 1; ///< local variable modify flag
- ///< true - modify local, false - modify stack
-};
-
-/**
- * Complete struct of bytecode instructions.
- */
-struct vf_Code {
- unsigned char *m_addr; ///< address of bytecode instruction
- unsigned *m_off; ///< array of instruction branches
- vf_MapEntry_t *m_invector; ///< stack map IN instruction vector
- vf_MapEntry_t *m_outvector; ///< stack map OUT instruction vector
- unsigned m_offcount; ///< number of instruction branches
- unsigned short m_minstack; ///< minimal stack for instruction
- unsigned short m_inlen; ///< stack map IN instruction vector length
- unsigned short m_outlen; ///< stack map OUT instruction vector length
- short m_stack; ///< stack change for instruction
- vf_CodeType m_type; ///< instruction flag @see vf_CodeType_t
- bool m_basic_block_start : 1; ///< begin of a basic block
-};
-
-/**
- * Constant pool parse structure.
- */
-union vf_Parse {
- struct {
- vf_MapEntry_t *m_invector; ///< method IN stack vector
- vf_MapEntry_t *m_outvector; ///< method OUT stack vector
- const char *m_name; ///< invoked method name
- int m_inlen; ///< IN vector length
- int m_outlen; ///< OUT vector length
- } method;
- struct {
- vf_MapEntry_t *f_vector; ///< field type map vector
- int f_vlen; ///< field type map vector len
- } field;
-};
+void vf_delete_pool_func( vf_Pool *pool, VF_SOURCE_PARAMS );
//===========================================================
// Verifier hash table structures.
@@ -495,10 +562,11 @@
/**
* Structure of hash entry.
*/
-struct vf_HashEntry {
+struct vf_HashEntry
+{
const char *key; ///< hash entry key
void *data; ///< pointer to hash entry data
- vf_HashEntry_t *next; ///< next hash entry
+ vf_HashEntry *next; ///< next hash entry
};
/**
@@ -511,83 +579,83 @@
* Hash table constructor.
* @note Function allocates memory for hash pool and hash table.
*/
- vf_Hash();
+ vf_Hash ();
/**
* Hash table constructor.
* @param pool - external memory pool
* @note Function allocates memory for hash pool and hash table.
*/
- vf_Hash( vf_VerifyPool_t *pool);
+ vf_Hash ( vf_Pool *pool );
/**
* Hash table destructor.
* @note Function release memory for hash pool and hash table.
*/
- ~vf_Hash();
+ ~vf_Hash ();
/**
* Function looks up hash entry which is identical to given hash key.
* @param key - given hash key
* @return Hash entry which is identical to given hash key.
- * @see vf_HashEntry_t
+ * @see vf_HashEntry
*/
- vf_HashEntry_t * Lookup( const char *key );
+ vf_HashEntry *Lookup( const char *key );
/**
* Function looks up hash entry which is identical to given hash key.
* @param key - given hash key
* @param len - hash key length
* @return Hash entry which is identical to given hash key.
- * @see vf_HashEntry_t
+ * @see vf_HashEntry
*/
- vf_HashEntry_t * Lookup( const char *key, unsigned len );
+ vf_HashEntry *Lookup( const char *key, size_t len );
/**
* Function creates hash entry which is identical to given hash key.
* @param key - given hash key
* @return Hash entry which are identical to given hash key.
- * @see vf_HashEntry_t
+ * @see vf_HashEntry
* @note Created hash key and hash entry is allocated into hash memory pool.
*/
- vf_HashEntry_t * NewHashEntry( const char *key );
+ vf_HashEntry *NewHashEntry( const char *key );
/**
* Function creates hash entry which is identical to given hash key.
* @param key - given hash key
* @param len - hash key length
* @return Hash entry which are identical to given hash key.
- * @see vf_HashEntry_t
+ * @see vf_HashEntry
* @note Created hash key and hash entry is allocated into hash memory pool.
*/
- vf_HashEntry_t * NewHashEntry( const char *key, size_t len );
+ vf_HashEntry *NewHashEntry( const char *key, size_t len );
-private:
- vf_VerifyPool_t *m_pool; ///< hash memory pool
- vf_HashEntry_t **m_hash; ///< hash table
+ private:
+ vf_Pool *m_pool; ///< hash memory pool
+ vf_HashEntry **m_hash; ///< hash table
const unsigned HASH_SIZE; ///< hash table size
bool m_free; ///< need to free pool
/**
- * Function checks key identity.
+ * Checks key identity.
* @param hash_entry - checked hash entry
* @param key - checked key
* @return If keys are identical function returns <code>true</code>,
* else returns <code>false</code>.
- * @see vf_HashEntry_t
+ * @see vf_HashEntry
*/
- bool CheckKey( vf_HashEntry_t *hash_entry, const char *key );
+ bool CheckKey( vf_HashEntry *hash_entry, const char *key );
/**
- * Function checks key identity.
+ * Checks key identity.
* @param hash_entry - checked hash entry
* @param key - checked key
* @param len - checked key length
* @return If keys are identical function returns <code>true</code>,
* else returns <code>false</code>.
- * @see vf_HashEntry_t
+ * @see vf_HashEntry
*/
- bool CheckKey( vf_HashEntry_t *hash_entry, const char *key, size_t len );
+ bool CheckKey( vf_HashEntry *hash_entry, const char *key, size_t len );
/**
* Hash function.
@@ -603,22 +671,23 @@
* @return Hash index relevant to key.
*/
unsigned HashFunc( const char *key, size_t len );
-}; // struct vf_Hash
+}; // struct vf_Hash
//===========================================================
// Verifier type constraint structures.
//===========================================================
/**
- * Verifier type constraint structure.
+ * A list of constraints.
*/
-struct vf_TypeConstraint {
- const char *source; ///< constraint source class name
- const char *target; ///< constraint target class name
- method_handler method; ///< constraint for method
- vf_TypeConstraint_t *next; ///< next constraint
- unsigned short index; ///< constant pool index
- unsigned short check_type; ///< constraint check type @see vf_CheckConstraint_t
+struct vf_TypeConstraint
+{
+ const char *m_source; ///< constraint source class name
+ const char *m_target; ///< constraint target class name
+ method_handler m_method; ///< constraint for method
+ vf_TypeConstraint *m_next; ///< next constraint
+ unsigned short m_index; ///< constant pool index
+ unsigned short m_check_type; ///< constraint check type @see vf_CheckConstraint
};
/**
@@ -644,20 +713,20 @@
* @param type - given class name
* @param len - class name length
* @return Created valid type structure.
- * @see vf_ValidType_t
+ * @see vf_ValidType
*/
- vf_ValidType_t * NewType( const char *type, size_t len );
+ vf_ValidType *NewType( const char *type, size_t len );
/**
* Function creates valid type which is identical to an element of a given array type.
* @param array - array valid type
* @return Created valid type of a given array element.
- * @see vf_ValidType_t
+ * @see vf_ValidType
*/
- vf_ValidType_t * NewArrayElemType( vf_ValidType_t *array );
+ vf_ValidType *NewArrayElemType( vf_ValidType *array );
/**
- * Function checks types and create constraints if it's necessarily.
+ * Checks types and create constraints if it's necessarily.
* @param required - required type
* @param available - available type
* @param index - constant pool index
@@ -665,13 +734,12 @@
* @return If available type satisfy to required type
* function will return <code>false</code> (is it error?),
* else will return <code>true</code> (is it error?).
- * @see vf_ValidType_t
- * @see vf_CheckConstraint_t
+ * @see vf_ValidType
+ * @see vf_CheckConstraint
*/
- bool CheckTypes( vf_ValidType_t *required,
- vf_ValidType_t *available,
- unsigned short index,
- vf_CheckConstraint_t check_type);
+ bool CheckTypes( vf_ValidType *required,
+ vf_ValidType *available,
+ unsigned short index, vf_CheckConstraint check_type );
/**
* Function merges two valid types.
@@ -679,12 +747,12 @@
* @param second - second merged type
* @return Function returns created valid type corresponding with merge result.
* @return Function returns <code>NULL</code> if vector wasn't merged.
- * @see vf_ValidType_t
+ * @see vf_ValidType
*/
- vf_ValidType_t * MergeTypes( vf_ValidType_t *first, vf_ValidType_t *second );
+ vf_ValidType *MergeTypes( vf_ValidType *first, vf_ValidType *second );
/**
- * Function dumps constraint collection in stream.
+ * Dumps constraint collection in stream.
* @param out - pointer to output stream
* @note If <i>out</i> is equal to null, output stream is <i>cerr</i>.
*/
@@ -693,44 +761,44 @@
/**
* Function returns the methods constraints array.
* @return Array of the methods constraints.
- * @see vf_TypeConstraint_t
+ * @see vf_TypeConstraint
*/
- vf_TypeConstraint_t * GetClassConstraint();
+ vf_TypeConstraint *GetClassConstraint();
/**
- * Function sets current context method.
+ * Sets current context method.
* @param method - current context method
*/
void SetMethod( method_handler method );
/**
- * Function sets restriction from target class to source class.
+ * Sets restriction from target class to source class.
* @param target - target class name
* @param source - source class name
* @param index - constant pool index
* @param check_type - constraint check type
- * @see vf_CheckConstraint_t
+ * @see vf_CheckConstraint
*/
void SetRestriction( const char *target,
- const char *source,
+ const char *source,
unsigned short index,
- vf_CheckConstraint_t check_type );
+ vf_CheckConstraint check_type );
-private:
- vf_VerifyPool_t *m_pool; ///< collection memory pool
- vf_Hash_t *m_Hash; ///< hash table
- method_handler m_method; ///< current context method
- vf_TypeConstraint_t *m_restriction; ///< array of the class constraints
-}; // vf_TypePool
+ private:
+ vf_Pool *m_pool; ///< collection memory pool
+ vf_Hash *m_Hash; ///< hash table
+ method_handler m_method; ///< current context method
+ vf_TypeConstraint *m_restriction; ///< array of the class constraints
+}; // vf_TypePool
//===========================================================
// Verifier type constraint structures.
//===========================================================
-void vf_clean_pool_memory_func( vf_VerifyPool_t *pool, VERIFY_SOURCE_PARAMS );
+void vf_clean_pool_func( vf_Pool *pool, VF_SOURCE_PARAMS );
/**
- * Structure of verifier context
+ * Verification context.
*/
struct vf_Context
{
@@ -738,116 +806,126 @@
/**
* Verifier context constructor
*/
- vf_Context() : m_class(NULL), m_type(NULL), m_error(NULL),
- m_method(NULL), m_graph(NULL), m_pool(NULL), m_code(NULL),
- m_codeNum(0), m_nodeNum(0), m_edgeNum(0)
+ vf_Context ():m_class( NULL ), m_type( NULL ), m_error( NULL ),
+ m_method( NULL ), m_graph( NULL ), m_pool( NULL ), m_instr( NULL ),
+ m_last_instr( NULL ), m_retnum( 0 ), m_verify_all( false )
{
- vf_ContextDump zero1 = {0};
- vf_ContextVType zero2 = {0};
-
- m_dump = zero1;
+ vf_ContextVType zero2 = { 0 };
m_vtype = zero2;
}
+ void SetMethod( method_handler method )
+ {
+ m_method = method;
+
+ // get method parameters
+ m_len = method_get_code_length( method );
+ m_bytes = method_get_bytecode( method );
+ m_handlers = method_get_exc_handler_number( method );
+
+ // get method limitations
+ m_maxlocal = method_get_max_local( method );
+ m_maxstack = method_get_max_stack( method );
+
+ // cache in the context if the method is a constructor
+ m_is_constructor =
+ memcmp( method_get_name( method ), "<init>", 7 ) == 0;
+ }
+
/**
* Verifier context destructor
*/
- ~vf_Context() {}
+ ~vf_Context ()
+ {
+ if( m_pool ) {
+ vf_delete_pool( m_pool );
+ }
+ if( m_type ) {
+ delete m_type;
+ }
+ }
/**
- * Function clears context.
+ * Clears context.
*/
void ClearContext()
{
m_method = NULL;
m_is_constructor = false;
m_graph = NULL;
- m_code = NULL;
- m_bc = NULL;
- m_codeNum = 0;
- m_nodeNum = 0;
- m_edgeNum = 0;
- vf_clean_pool_memory( m_pool );
- } // vf_ClearContext
+ m_instr = NULL;
+ m_bc = NULL;
+ m_last_instr = NULL;
+ m_retnum = 0;
+ vf_clean_pool( m_pool );
+ } // vf_ClearContext
public:
- vf_TypePool *m_type; ///< context type constraint collection
- char *m_error; ///< context error message
- vf_Graph *m_graph; ///< context control flow graph
- vf_VerifyPool_t *m_pool; ///< context memory pool
- vf_Code_t *m_code; ///< context code instruction of method
- vf_BCode_t* m_bc; ///< bytecode to code mapping
- class_handler m_class; ///< context class
- method_handler m_method; ///< context method
- unsigned m_codeNum; ///< code instruction number
- unsigned m_nodeNum; ///< graph node number
- unsigned m_edgeNum; ///< graph edge number
- bool m_is_constructor; ///< <code>true</code> if the
- ///< method is a constructor
-
- /**
- * Structure contains useful valid types
- */
- struct vf_ContextVType {
- vf_ValidType_t *m_class; ///< context a given class valid type
- vf_ValidType_t *m_throwable; ///< context java/lang/Throwable valid type
- vf_ValidType_t *m_object; ///< context java/lang/Object valid type
- vf_ValidType_t *m_array; ///< context [Ljava/lang/Object; valid type
- vf_ValidType_t *m_clone; ///< context java/lang/Cloneable valid type
- vf_ValidType_t *m_serialize; ///< context java/io/Serializable valid type
- } m_vtype;
+ vf_TypePool *m_type; ///< context type constraint collection
+ char *m_error; ///< context error message
+ vf_Graph *m_graph; ///< control flow graph
+ vf_Pool *m_pool; ///< memory pool
+ vf_InstrHandle m_instr; ///< method instructions
+ vf_InstrHandle m_last_instr; ///< the pointer follows
+ ///< the last instruction at <code>m_instr</code>
+ vf_BCode *m_bc; ///< bytecode to instruction mapping
+ unsigned m_retnum; ///< a number of <code>ret</code>s
+
+ /**
+ * Cached method info.
+ */
+ class_handler m_class; ///< a context class
+ method_handler m_method; ///< a context method
+ unsigned m_len; ///< bytecode length
+ unsigned char *m_bytes; ///< bytecode location
+ unsigned short m_handlers; ///< a number of exception handlers
+ unsigned short m_maxstack; ///< max stack length
+ unsigned short m_maxlocal; ///< max local number
+ bool m_is_constructor; ///< <code>true</code> if the
+ ///< method is a constructor
+
+ vf_SubContext *m_sub_ctx; ///< aggregate subroutine info
+ vf_MapVector *m_map; ///< a stack map for control flow analysis,
+ ///< vectors themselves are allocated from the graph pool
+ vf_MapEntry *m_method_invector; ///< method parameters
+ unsigned short m_method_inlen; ///< a length of <code>m_method_invector</code>
+ vf_MapEntry *m_method_outvector; ///< method return value
+ unsigned short m_method_outlen; ///< a length of <code>m_method_outvector</code>
+
+ vf_MapEntry *m_buf; ///< used to store intermediate stack states
+ ///< during data flow analysis
+
+ bool m_verify_all; ///< if <code>true</code> need to verify more checks
/**
- * Structure contains debug dump flags
+ * Contains useful valid types.
*/
- struct vf_ContextDump {
- unsigned m_verify : 1; ///< verify all flag
- unsigned m_with_subroutine : 1; ///< verified method has subroutine
- unsigned m_constraint : 1; ///< dump type constraints for class
- unsigned m_code : 1; ///< print code array in stream
- unsigned m_graph : 1; ///< print original control flow graph
- unsigned m_mod_graph : 1; ///< print modified control flow graph
- unsigned m_dot_graph : 1; ///< dump original control flow graph in file in DOT format
- unsigned m_dot_mod_graph : 1; ///< dump modified control flow graph in file in DOT format
- unsigned m_node_vector : 1; ///< print data flow node vectors
- unsigned m_code_vector : 1; ///< print data flow node code instruction vectors
- unsigned m_merge_vector : 1; ///< print result of merge data flow vectors
- } m_dump;
+ struct vf_ContextVType
+ {
+ vf_ValidType *m_class; ///< a given class
+ vf_ValidType *m_throwable; ///< java/lang/Throwable
+ vf_ValidType *m_object; ///< java/lang/Object
+ vf_ValidType *m_array; ///< [Ljava/lang/Object;
+ vf_ValidType *m_clone; ///< java/lang/Cloneable
+ vf_ValidType *m_serialize; ///< java/io/Serializable
+ } m_vtype;
-}; // struct vf_Context
+}; // struct vf_Context
//===========================================================
// Other structures.
//===========================================================
/**
- * Head structure of memory pool.
- */
-struct vf_VerifyPool {
- vf_VerifyPoolInternal_t *m_pool; ///< pool entry
- size_t m_memory; ///< allocated memory size
- size_t m_used; ///< used memory size
- size_t m_maxuse; ///< max used memory size
-};
-
-/**
- * Internal structure of memory pool.
- */
-struct vf_VerifyPoolInternal {
- void *m_memory; ///< pool entry memory
- char *m_free; ///< free space in pool entry
- vf_VerifyPoolInternal_t *m_next; ///< next pool entry
- size_t m_freesize; ///< size of free space in pool entry
-};
-
-/**
* Structure of class loader constraint data.
*/
-struct vf_ClassLoaderData {
- vf_VerifyPool_t *pool; ///< constraint memory pool
- vf_Hash_t *string; ///< string pool hash table
+struct vf_ClassLoaderData
+{
+ vf_Pool *pool; ///< constraint memory pool
+ vf_Hash *string; ///< string pool hash table
};
+
//===========================================================
// Verifier debug data
//===========================================================
@@ -855,9 +933,9 @@
/**
* Array of opcode names. Available in debug mode.
*/
-#if _VERIFY_DEBUG
+#if _VF_DEBUG
extern const char *vf_opcode_names[];
-#endif // _VERIFY_DEBUG
+#endif // _VF_DEBUG
//===========================================================
// Verifier functions.
@@ -865,13 +943,12 @@
/**
* Function creates bytecode control flow graph.
- * @param context - verifier context
+ * @param ctx - verifier context
* @return Result of graph creation.
- * @see vf_Context_t
- * @see Verifier_Result
+ * @see vf_Context
+ * @see vf_Result
*/
-Verifier_Result
-vf_create_graph( vf_Context_t *context );
+vf_Result vf_create_graph( vf_Context *ctx );
/**
* Checks control flow and data flow of graph.
@@ -880,55 +957,50 @@
*
* @return a result of graph checks
*/
-Verifier_Result
-vf_check_graph( vf_Context_t *context );
+vf_Result vf_check_graph( vf_Context *ctx );
/**
- * Function provides data flow checks of verifier graph structure.
- * @param context - verifier context
+ * Provides data flow checks of verifier graph structure.
+ * @param ctx - verifier context
* @return Check result.
- * @see vf_Context_t
- * @see Verifier_Result
+ * @see vf_Context
+ * @see vf_Result
*/
-Verifier_Result
-vf_check_graph_data_flow( vf_Context_t *context );
+vf_Result vf_check_graph_data_flow( vf_Context *ctx );
/**
- * Function parses method, class or field descriptors.
- * @param descr - descriptor of method, class or field
- * @param inlen - returned number of <i>IN</i> descriptor parameters
- * @param outlen - returned number of <i>OUT</i> descriptor parameters (for method)
- * @note Assertion is raised if <i>descr</i> or <i>inlen</i> are equal to null.
+ * Parses method, class or field descriptors.
+ * @param descr descriptor of method, class or field
+ * @param inlen returned number of <i>IN</i> descriptor parameters
+ * @param outlen returned number of <i>OUT</i> descriptor parameters (for method)
+ * @note Assertion is raised if <i>descr</i> or <i>inlen</i> are equal to <code>NULL</code>.
* @note Parameter <i>outlen</i> may be equal to null (for class or field descriptor).
*/
-void
-vf_parse_description( const char *descr, int *inlen, int *outlen);
+void vf_parse_description( const char *descr, unsigned short *inlen,
+ unsigned short *outlen );
/**
- * Function parses descriptor and sets input and output data flow vectors.
- * @param descr - descriptor of method, class or field
- * @param inlen - number of entries for <i>IN</i> data flow vector
- * @param add - additional number of entries to <i>IN</i> data flow vector
- * @param outlen - number of entries for <i>OUT</i> data flow vector (for method)
- * @param invector - pointer to <i>IN</i> data flow vector
- * @param outvector - pointer to <i>OUT</i> data flow vector
- * @param context - verifier context
+ * Parses a descriptor and sets input and output data flow vectors.
+ * @param descr a descriptor of method, class or field
+ * @param inlen a number of entries for <i>IN</i> data flow vector
+ * @param add an additional number of entries to <i>IN</i> data flow vector
+ * @param outlen a number of entries for <i>OUT</i> data flow vector (for method)
+ * @param invector a pointer to <i>IN</i> data flow vector
+ * @param outvector a pointer to <i>OUT</i> data flow vector
+ * @param ctx a verifier context
* @note Assertion is raised if <i>descr</i> is equal to null.
* @note Parameter <i>invector</i> may be equal to null
* if sum of parameters <i>inlen + add</i> is equal to zero.
* @note Parameter <i>outvector</i> may be equal to null
* if parameter <i>outlen</i> is equal to zero.
- * @see vf_MapEntry_t
- * @see vf_Context_t
*/
void
vf_set_description_vector( const char *descr,
- int inlen,
- int add,
- int outlen,
- vf_MapEntry_t **invector,
- vf_MapEntry_t **outvector,
- vf_Context_t *context);
+ unsigned short inlen,
+ unsigned short add,
+ unsigned short outlen,
+ vf_MapEntry **invector,
+ vf_MapEntry **outvector, vf_ContextHandle ctx );
/**
* Gets a class name from a constant pool.
@@ -938,51 +1010,46 @@
*
* @return a pointer to UTF8 constant pool entry
*/
-static inline const char*
-vf_get_cp_class_name( class_handler klass,
- unsigned short index )
+static inline const char *
+vf_get_cp_class_name( class_handler klass, unsigned short index )
{
unsigned short class_name_index =
- class_get_cp_class_name_index(klass, index);
- const char* name = class_get_cp_utf8_bytes(klass, class_name_index);
+ class_get_cp_class_name_index( klass, index );
+ const char *name = class_get_cp_utf8_bytes( klass, class_name_index );
return name;
-} // vf_get_cp_class_name
+} // vf_get_cp_class_name
/**
- * Function creates valid type by given class name.
- * @param class_name - class name
- * @param context - verifier context
- * @return Valid type structure corresponding to given class name.
- * @see vf_ValidType_t
- * @see vf_Context_t
+ * Creates a valid type from a given class name.
+ * @param class_name a class name
+ * @param ctx a verifier context
+ * @return a valid type structure corresponding to the given class name
*/
-vf_ValidType_t *
-vf_create_class_valid_type( const char *class_name, vf_Context_t *context );
+vf_ValidType *vf_create_class_valid_type( const char *class_name,
+ vf_ContextHandle ctx );
/**
- * Function provides constraint checks for current class.
- * @param context - verifier context
+ * Provides constraint checks for current class.
+ * @param ctx - verifier context
* @return Check result.
* @note Provides only checks with loaded classes.
* @note All unchecked constraints are saved to class loader verify data.
- * @see vf_Context_t
- * @see Verifier_Result
+ * @see vf_Context
+ * @see vf_Result
*/
-Verifier_Result
-vf_check_class_constraints( vf_Context_t *context );
+vf_Result vf_check_class_constraints( vf_Context *ctx );
/**
* Function compares two valid types.
* @param type1 - first checked type
* @param type2 - second checked type
* @return If types are equal returns <code>true</code>, else returns <code>false</code>.
- * @see vf_ValidType_t
+ * @see vf_ValidType
*/
-bool
-vf_is_types_equal( vf_ValidType_t *type1, vf_ValidType_t *type2 );
+bool vf_is_types_equal( vf_ValidType *type1, vf_ValidType *type2 );
/**
- * Function checks access to protected field/method.
+ * Checks access to protected field/method.
* If function cannot check constraint because of any class isn't loaded,
* function return unloaded error to store restriction to the class
* for future constraint check.
@@ -990,45 +1057,42 @@
* @param instance_name - name of instance class
* @param index - constant pool index
* @param check_type - access check type
- * @param ctex - verifier context
+ * @param ctx - verifier context
* @return Check result.
* @note Provides only checks with loaded classes.
- * @see vf_CheckConstraint_t
- * @see vf_Context_t
- * @see Verifier_Result
- */
-Verifier_Result
-vf_check_access_constraint( const char *super_name, // name of super class
- const char *instance_name, // name of instance class
- unsigned short index, // constant pool index
- vf_CheckConstraint_t check_type, // access check type
- vf_Context_t *ctex); // verifier context
+ * @see vf_CheckConstraint
+ * @see vf_Context
+ * @see vf_Result
+ */
+vf_Result vf_check_access_constraint( const char *super_name, // name of super class
+ const char *instance_name, // name of instance class
+ unsigned short index, // constant pool index
+ vf_CheckConstraint check_type, // access check type
+ vf_Context *ctx ); // verification context
/**
- * Sets error message of verifier.
+ * Sets error message of a verifier.
*
* @param[in] stream stringstream object with a message
- * @param[in] ctex a verifier context
+ * @param[in] ctx a verifier context
*/
static inline void
-vf_set_error_message( stringstream &stream,
- vf_Context_t *ctex)
+vf_set_error_message( stringstream & stream, vf_Context *ctx )
{
- if( ctex->m_error ) {
+ if( ctx->m_error ) {
// free old message
- vf_free( ctex->m_error );
+ vf_free( ctx->m_error );
}
// create message
size_t len = stream.str().length();
if( len ) {
- ctex->m_error = (char*)vf_malloc( len + 1 );
- memcpy( ctex->m_error, stream.str().c_str(), len );
- ctex->m_error[len] = '\0';
+ ctx->m_error = (char*)vf_malloc( len + 1 );
+ memcpy( ctx->m_error, stream.str().c_str(), len );
+ ctx->m_error[len] = '\0';
} else {
- ctex->m_error = NULL;
+ ctx->m_error = NULL;
}
- return;
-} // vf_set_error_message
+} // vf_set_error_message
/**
* Checks a version of a class file.
@@ -1038,26 +1102,26 @@
* @return <code>true</code> if a class version is less than 1.4
*/
static inline bool
-vf_is_class_version_14( vf_Context_t *context )
+vf_is_class_version_14( vf_ContextHandle ctx )
{
- return (class_get_version(context->m_class) < 49) ? true : false;
-} // vf_is_class_version_14
+ return ( class_get_version( ctx->m_class ) < 49 ) ? true : false;
+} // vf_is_class_version_14
/**
* Returns branch target for a given branch number.
*
- * @param[in] code a reference to instruction
+ * @param[in] instr a reference to instruction
* @param[in] branch_num a branch number
*
* @return an absolute bytecode position to which the executuion
* branches
*/
static inline int
-vf_get_code_branch( vf_Code_t* code, unsigned branch_num )
+vf_get_instr_branch( vf_InstrHandle instr, unsigned branch_num )
{
- assert(branch_num < code->m_offcount);
- return code->m_off[branch_num];
-} // vf_get_instruction_branch
+ assert( branch_num < instr->m_offcount );
+ return instr->m_off[branch_num];
+} // vf_get_instruction_branch
/**
* Allocates memory for a new stack map vector.
@@ -1066,16 +1130,13 @@
* @param[in] len vector length
* @param[in] pool memory pool
*/
-static inline void
-vf_new_vector( vf_MapEntry_t** vector,
- unsigned len,
- vf_VerifyPool_t *pool)
+static inline void
+vf_new_vector( vf_MapEntry **vector, unsigned len, vf_Pool *pool )
{
// create new vector
- (*vector) = (vf_MapEntry_t*) vf_alloc_pool_memory(pool,
- len * sizeof(vf_MapEntry_t));
- return;
-} // vf_new_vector
+ ( *vector ) = (vf_MapEntry*)vf_palloc( pool,
+ len * sizeof( vf_MapEntry ) );
+} // vf_new_vector
/**
* Sets a reference data type for a given stack map vector entry.
@@ -1085,24 +1146,53 @@
* @param[in] type reference type
*/
static inline void
-vf_set_vector_stack_entry_ref( vf_MapEntry_t* vector,
- unsigned num,
- vf_ValidType_t* type)
+vf_set_vector_stack_entry_ref( vf_MapEntry *vector,
+ unsigned num, vf_ValidType *type )
{
// set a stack map vector entry by ref
vector[num].m_type = SM_REF;
vector[num].m_vtype = type;
-} // vf_set_vector_stack_entry_ref
+} // vf_set_vector_stack_entry_ref
+
+/**
+ * Calculates an index of instruction.
+ * @param[in] pc a bytecode index at instruction start
+ * @param[in] ctx a verification context
+ * @return an instruction index
+ */
+static inline unsigned
+vf_bc_to_instr_index( unsigned short pc, vf_ContextHandle ctx )
+{
+ vf_InstrHandle instr = ctx->m_bc[pc].m_instr;
+ assert( instr );
+ return instr - ctx->m_instr;
+}
+
+/**
+ * For a given instruction gets a start pointer of the next instruction or the
+ * pointer which follows the last bytecode of the method for the last instruction.
+ * @param[in] instr an instruction handle
+ * @param[in] ctx a verification context
+ * @return a pointer which follows a given instruction
+ */
+static inline const unsigned char *
+vf_get_instr_end( vf_InstrHandle instr, vf_ContextHandle ctx )
+{
+ if( instr + 1 == ctx->m_last_instr ) {
+ return ctx->m_bytes + ctx->m_len;
+ }
+ return ( instr + 1 )->m_addr;
+}
/**
* Calls destructor of graph, if any.
*
* @param[in] context a context of verifier
*/
-void vf_free_graph( vf_Context_t* context );
+void vf_free_graph( vf_Context *context );
/**
- * Inline subroutines in the call graph.
+ * Mark subroutine code.
*
* <p>Here is the algorithm sketch: we define subroutine boundaries with
* simplified data flow analysis and duplicate subroutine nodes
@@ -1110,11 +1200,19 @@
* <a href="http://wiki.apache.org/harmony/Subroutine_Verification">wiki
* page</a>.</p>
*
- * @param[in] context a verifier context
+ * @param ctx a verifier context
+ * @return VER_OK if no graph structure inconsistencies were detected during marking,
+ * an error code otherwise
+ */
+vf_Result vf_mark_subroutines( vf_Context *ctx );
+
+/**
+ * Inline subroutines in the call graph.
+ *
+ * @param ctx a verifier context
* @return VER_OK if subroutines were inlined successfully,
* an error code otherwise
*/
-Verifier_Result
-vf_inline_subroutines(vf_ContextHandle context);
+vf_Result vf_inline_subroutines( vf_Context *ctx );
#endif // _VERIFIER_REAL_H_
Modified: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.cpp
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.cpp?view=diff&rev=528575&r1=528574&r2=528575
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.cpp (original)
+++ harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.cpp Fri Apr 13 11:26:27 2007
@@ -16,24 +16,578 @@
*/
#include "ver_subroutine.h"
-static vf_Result
-MarkTopcode(vf_ContextHandle context, vf_NodeHandle nh) {
+#ifdef _VF_DEBUG
+/**
+ * Gets a subroutine number for a node. The function is slow and should be used for
+ * debugging purposes only.
+ * @param[in] sub a given subroutine handle
+ * @param[in] ctx a verification context
+ * @return a sequential subroutine number in a list
+ */
+unsigned vf_get_sub_num(vf_SubHandle sub, vf_ContextHandle ctx)
+{
+ unsigned index = 0;
+ for (vf_SubHandle s = ctx->m_sub_ctx->m_sub; s; s = s->m_next) {
+ if (s == sub) { // subroutine found
+ return index;
+ }
+ index++;
+ }
+ VF_DIE("vf_get_sub_num: Cannot find a subroutine " << sub <<
+ " in a list");
+ return 0;
+}
+
+void vf_Graph::DumpSub(vf_SubHandle sub)
+{
+ if (sub) {
+ VF_DEBUG("Subroutine:");
+ if (sub->m_entry) {
+ VF_DEBUG(" Entry node: " << GetNodeNum(sub->m_entry));
+ } else {
+ VF_DEBUG(" Entry node undefined");
+ }
+ if (sub->m_ret) {
+ VF_DEBUG(" Return node: " << GetNodeNum(sub->m_ret));
+ } else {
+ VF_DEBUG(" Return node undefined");
+ }
+ }
+} // vf_Graph::DumpSub
+
+static void DumpNodeStack(vf_Context *ctx)
+{
+ vf_NodeStackHandle p_element = ctx->m_sub_ctx->m_path_start;
+ bool fork_found = false;
+ unsigned count = 0;
+
+ VF_DEBUG("Dumping path: ");
+ for (; p_element; p_element = p_element->m_next, count++) {
+ if (p_element == ctx->m_sub_ctx->m_path_fork) {
+ fork_found = true;
+ VF_DEBUG("Fork");
+ }
+ VF_DEBUG(" Node #" << ctx->m_graph->GetNodeNum(p_element->m_node));
+ }
+ assert(fork_found || !ctx->m_sub_ctx->m_path_fork);
+ VF_DEBUG("Totally " << count << " nodes");
+} // DumpNodeStack
+#endif // _VF_DEBUG
+
+
+/**
+ * Allocates memory for subroutine context.
+ * @param ctx a verification context
+ */
+static void AllocateSubContext(vf_Context *ctx)
+{
+ vf_Pool *pool = ctx->m_pool;
+
+ vf_SubContext *sub_ctx = (vf_SubContext *) vf_palloc(pool,
+ sizeof(vf_SubContext));
+ ctx->m_sub_ctx = sub_ctx;
+ sub_ctx->m_pool = pool;
+} // AllocateSubContext
+
+
+/**
+ * Adds a new subroutine into subroutine array.
+ * @param[in] ret_node a node containing a corresponding <code>ret</code>
+ * @param[in] sub_ctx a subroutine verification context
+ * @return a sub handle
+ */
+static vf_Sub *AddNewSub(vf_NodeHandle ret_node, vf_SubContext * sub_ctx)
+{
+ vf_Sub *sub = (vf_Sub *) vf_palloc(sub_ctx->m_pool, sizeof(vf_Sub));
+ sub->m_next = sub_ctx->m_sub;
+ sub_ctx->m_sub = sub;
+ sub->m_ret = ret_node;
+ return sub;
+} // AddNewSub
+
+/**
+ * Adds a node to the subroutine.
+ * @param[in] sub a subroutine
+ * @param[in] node a node which is a part of this subroutine
+ */
+static void AddSubNode(vf_Sub *sub, vf_Node *node)
+{
+ assert(!node->m_sub); // node is added once
+ node->m_sub = sub;
+ sub->m_nodenum++;
+ // a number of out edges for reachable node won't
+ // change while removing a dead code
+ sub->m_out_edgenum += node->m_outnum;
+} // AddNewSub
+
+static inline vf_Result ResolveSubroutineEntryPoint(vf_Node *node,
+ vf_Context *ctx)
+{
+ //initialize vector
+ vf_MapVector *map = ctx->m_map;
+
+ // the path element node to iterate from
+ vf_NodeStackHandle p_element = ctx->m_sub_ctx->m_path_fork;
+ if (!p_element) {
+ p_element = ctx->m_sub_ctx->m_path_start;
+ map->m_number = ctx->m_maxlocal;
+ unsigned index;
+ for (index = 0; index < map->m_number; index++) {
+ map->m_local[index].m_type = SM_ANY;
+ }
+
+ map->m_depth = p_element->m_node->m_inmap.m_depth;
+ for (index = 0; index + 1 < map->m_depth; index++) {
+ map->m_stack[index].m_type = SM_ANY;
+ }
+ map->m_stack[index].m_type = SM_RETURN_ADDR;
+ map->m_stack[index].m_pc =
+ p_element->m_node->m_start->m_addr - ctx->m_bytes;
+ }
+
+ VF_DUMP(DUMP_NODESTACK, DumpNodeStack(ctx));
+ for (; p_element; p_element = p_element->m_next) {
+ vf_Result result =
+ vf_set_node_out_vector(p_element->m_node, map, ctx);
+ if (result != VER_OK) {
+ return result;
+ }
+ }
+
+ // since a copy flag is set for SM_RETURN_ADDR entries,
+ // <code>ctx->m_buf</code> contains the last processed entry, i. e.
+ // an entry for <code>ret</code>
+ assert(ctx->m_buf->m_pc);
+ assert(SM_RETURN_ADDR == ctx->m_buf->m_type);
+ assert(node->m_outmap.m_depth == ctx->m_map->m_depth);
+ ((vf_Sub *) node->m_sub)->m_entry =
+ ctx->m_graph->GetNodeFromBytecodeIndex(ctx->m_buf->m_pc);
return VER_OK;
-} // MarkTopcode
+} // ResolveSubroutineEntryPoint
+
+static vf_Result MarkNode(vf_NodeStack &stack, vf_Context *ctx);
-static vf_Result
-InlineMarkedSubNodes(vf_ContextHandle context) {
+/**
+ * Fills <code>m_sub</code> field of the node using <code>m_sub</code> field of
+ * the next node using the following rules:
+ * <ul>
+ * <li>If the mark of the next node is empty, it doesn't count.</li>
+ * <li>If the mark of this node is empty, it is set to the following node
+ * mark.</li>
+ * <li>Otherwise node marks should be equal, or an error should be reported.</li>
+ * </ul>
+ */
+static inline vf_Result
+MergeSubMarks(vf_Node *node, vf_NodeHandle next_node, vf_Context *ctx)
+{
+ if (next_node->m_sub) {
+ VF_TRACE("sub.mark", "sub[" << ctx->m_graph->GetNodeNum(node)
+ << "] := sub[" << ctx->m_graph->GetNodeNum(next_node->
+ m_sub->m_ret)
+ << "] (" << vf_get_sub_num(next_node->m_sub, ctx) << ")");
+ if (node->m_sub == NULL) {
+ AddSubNode((vf_Sub *) next_node->m_sub, node);
+ } else if (node->m_sub != next_node->m_sub) {
+ VF_REPORT(ctx,
+ "A subroutine splits execution into "
+ "several ret instructions");
+ return VER_ErrorJsrMultipleRet;
+ }
+ }
return VER_OK;
-} // InlineMarkedSubNodes
+} // MergeSubMarks
-vf_Result
-vf_inline_subroutines(vf_ContextHandle context) {
- vf_Result r = MarkTopcode(context, context->m_graph->GetFirstNode());
+/**
+ * Marks an edge end node.
+ */
+static inline vf_Result
+FollowEdge(vf_Node *node, vf_NodeStack &stack, vf_Context *ctx)
+{
+ vf_Result r = MarkNode(stack, ctx);
if (VER_OK != r) {
return r;
}
- r = InlineMarkedSubNodes(context);
+ return MergeSubMarks(node, stack.m_node, ctx);
+} // FollowEdge
+
+/**
+ * Marks a <code>jsr</code> edge end node. If the subroutine returns, marks a node, which
+ * follows the edge start node.
+ */
+static inline vf_Result
+FollowJsrEdge(vf_Node *node, vf_NodeStack &stack, vf_Context *ctx)
+{
+ bool set_start = !ctx->m_sub_ctx->m_path_start;
+ if (set_start) {
+ ctx->m_sub_ctx->m_path_start = &stack;
+ }
+ vf_Result r = MarkNode(stack, ctx);
+ if (VER_OK != r) {
+ return r;
+ }
+
+ if (stack.m_node->m_sub) {
+ // if this jsr returns we need to process a node which
+ // follows after edge start node
+ if (stack.m_node->m_sub->m_entry != stack.m_node) {
+ VF_REPORT(ctx, "Subroutines merge their execution");
+ return VER_ErrorDataFlow;
+ }
+
+ ctx->m_sub_ctx->m_path_fork = &stack;
+
+ // select and check the following node
+ stack.Set(node + 1, stack.m_node->m_sub->m_ret->m_outmap.m_depth);
+ if (VF_NODE_END_ENTRY == stack.m_node->m_type) {
+ VF_REPORT(ctx, "Falling off the end of the code");
+ return VER_ErrorBranch;
+ }
+ assert(VF_NODE_CODE_RANGE == stack.m_node->m_type);
+
+ r = MarkNode(stack, ctx);
+ ctx->m_sub_ctx->m_path_fork = NULL;
+ if (VER_OK != r) {
+ return r;
+ }
+ }
+
+ if (set_start) {
+ ctx->m_sub_ctx->m_path_start = NULL;
+ }
+ return MergeSubMarks(node, stack.m_node, ctx);
+} // FollowJsrEdge
+
+/**
+ * Marks a given node and follows <i>out</i> edges.
+ * @param[in] stack a reference to the stack element for the given node
+ * @param[in] ctx a verification context
+ * @return VER_OK if marking was successful, an error code otherwise
+ */
+static vf_Result MarkNode(vf_NodeStack &stack, vf_Context *ctx)
+{
+ vf_Graph *graph = ctx->m_graph;
+ vf_Result r;
+
+ vf_Result result =
+ vf_check_node_stack_depth(stack.m_node, stack.m_depth, ctx);
+ if (result != VER_Continue) {
+ return result;
+ }
+ VF_TRACE("sub.mark",
+ "Processing node " << graph->GetNodeNum(stack.m_node));
+
+ if (VF_NODE_CODE_RANGE == stack.m_node->m_type) {
+ vf_InstrType last_instr_type = stack.m_node->m_end->m_type;
+
+ if (VF_INSTR_RET == last_instr_type) {
+ if (!ctx->m_sub_ctx->m_path_start) {
+ VF_REPORT(ctx, "Reached ret not using jsr branches");
+ return VER_ErrorJsrOther;
+ }
+ vf_Sub *sub = AddNewSub(stack.m_node, ctx->m_sub_ctx);
+ AddSubNode(sub, stack.m_node);
+ r = ResolveSubroutineEntryPoint(stack.m_node, ctx);
+ if (VER_OK != r) {
+ return r;
+ }
+ }
+ }
+
+ vf_NodeStack next_stack;
+ stack.m_next = &next_stack;
+ for (vf_EdgeHandle outedge = stack.m_node->m_outedge;
+ outedge; outedge = outedge->m_outnext) {
+ next_stack.Set(outedge->m_end, stack.m_depth);
+ if (!vf_is_jsr_branch(outedge, ctx)) {
+ r = FollowEdge(stack.m_node, next_stack, ctx);
+ } else {
+ assert(VF_NODE_CODE_RANGE == outedge->m_end->m_type);
+ assert(!outedge->m_outnext);
+ r = FollowJsrEdge(stack.m_node, next_stack, ctx);
+ }
+ if (VER_OK != r) {
+ return r;
+ }
+ }
+
+ return VER_OK;
+} // MarkNode
+
+
+vf_Result vf_mark_subroutines(vf_Context *ctx)
+{
+ vf_Graph *graph = ctx->m_graph;
+ AllocateSubContext(ctx);
+
+ vf_NodeStack bottom =
+ { (vf_Node *) ctx->m_graph->GetStartNode(), 0, NULL };
+ vf_Result r = MarkNode(bottom, ctx);
return r;
-} // InlineSubroutines
+} // vf_mark_subroutines
+
+static vf_Result AddDupCount(vf_Sub *sub, unsigned &count, vf_Context *ctx)
+{
+ VF_TRACE("dupcount", "Calculating a duplication count for a subroutine #"
+ << vf_get_sub_num(sub, ctx));
+ if (ALL_BITS_SET == sub->m_dupcount) {
+ VF_REPORT(ctx, "Found a recursive subroutine call sequence");
+ return VER_ErrorJsrRecursive;
+ }
+
+ if (!sub->m_dupcount) {
+ sub->m_dupcount = ALL_BITS_SET;
+
+ unsigned sum = 0;
+ for (vf_EdgeHandle inedge = sub->m_entry->m_inedge;
+ inedge; inedge = inedge->m_innext) {
+ vf_NodeHandle node = inedge->m_start;
+
+ if (vf_is_jsr_branch(inedge, ctx)) {
+ assert(!inedge->m_outnext);
+ if (node->m_sub == NULL) {
+ sum++;
+ } else if (node->m_sub != sub) {
+ AddDupCount((vf_Sub *) node->m_sub, sum, ctx);
+ } // else this call served as unconditional internal branch
+ } else if (node->m_sub != sub) {
+ VF_REPORT(ctx,
+ "A subroutine splits execution into "
+ "several ret instructions");
+ return VER_ErrorJsrMultipleRet;
+ }
+ }
+ sub->m_dupcount = sum;
+ }
+
+ VF_TRACE("dupcount", "A duplication count for a subroutine #"
+ << vf_get_sub_num(sub, ctx) << " is " << sub->m_dupcount);
+ count += sub->m_dupcount;
+ return VER_OK;
+} // AddSubDupCount
+
+static void InlineSubNodes(vf_ContextHandle ctx)
+{
+ vf_Graph *graph = ctx->m_graph;
+ vf_Sub *sub;
+
+ for (sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+ sub->m_nodes =
+ (vf_NodeHandle *) vf_palloc(ctx->m_sub_ctx->m_pool,
+ sub->m_nodenum * sizeof(vf_NodeHandle));
+ }
+
+ // populate subroutine node get the next node after the start node
+ vf_Node *node = (vf_Node *) graph->GetStartNode() + 1;
+ for (; VF_NODE_END_ENTRY != node->m_type; node++) {
+ if (node->m_sub) {
+ vf_Sub *sub = (vf_Sub *) node->m_sub;
+ node->m_nodecount = sub->m_index;
+ sub->m_nodes[sub->m_index++] = node;
+ }
+ }
+
+ for (sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+ // clear sub indices
+ assert(sub->m_nodenum == sub->m_index);
+ sub->m_index = 0;
+ // duplicate subroutine nodes
+ assert(sub->m_dupcount);
+ if (sub->m_dupcount == 1) {
+ continue;
+ }
+ vf_NodeHandle *p_node = sub->m_nodes;
+ vf_Node *new_node = sub->m_copies =
+ graph->AddNodes((sub->m_dupcount - 1) * sub->m_nodenum);
+ for (unsigned node_index = 0; node_index < sub->m_nodenum;
+ node_index++, p_node++) {
+ for (unsigned index = 1; index < sub->m_dupcount;
+ index++, new_node++) {
+ *new_node = **p_node;
+ // edges are outdated, delete them
+ new_node->m_inedge = new_node->m_outedge = NULL;
+ new_node->m_outnum = 0;
+ VF_TRACE("sub.inline",
+ "Copied node " << graph->GetNodeNum(*p_node)
+ << " to " << graph->GetNodeNum(new_node));
+ }
+ }
+ }
+ assert(0 == ctx->m_graph->HasMoreNodeSpace());
+
+} // InlineSubNodes
+
+/**
+ * Redirects subroutine calls to separate subroutine copies.
+ */
+static void InlineInEdges(vf_ContextHandle ctx)
+{
+ vf_Graph *graph = ctx->m_graph;
+
+ for (vf_SubHandle sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+ ((vf_Sub *) sub)->m_following_nodes =
+ (vf_Node **) vf_palloc(ctx->m_sub_ctx->m_pool,
+ sub->m_dupcount * sizeof(vf_Node *));
+ vf_NodeHandle sub_entry_copy =
+ sub->m_copies + sub->m_entry->m_nodecount * (sub->m_dupcount -
+ 1) - 1;
+ vf_EdgeHandle *p_next_edge =
+ (vf_EdgeHandle *) & sub->m_entry->m_inedge;
+ vf_Edge *inedge = (vf_Edge *) sub->m_entry->m_inedge;
+ while (inedge) {
+ if (vf_is_jsr_branch(inedge, ctx)) {
+ if (sub->m_index) {
+ assert(sub->m_copies);
+ assert(sub->m_dupcount);
+ // remove the edge from the list
+ *p_next_edge = inedge->m_innext;
+ // redirect jsr edge to correspondent subroutine copy
+ inedge->m_end = sub_entry_copy + sub->m_index;
+ }
+ // store return point
+ vf_Node *next_node = (vf_Node *) inedge->m_start + 1;
+ assert(VF_NODE_CODE_RANGE == next_node->m_type);
+ sub->m_following_nodes[((vf_Sub *) sub)->m_index++] =
+ next_node;
+ }
+ p_next_edge = &inedge->m_innext;
+ inedge = (vf_Edge *) inedge->m_innext;
+ }
+ assert(sub->m_index); // there was at least one branch
+ }
+} // InlineInEdges
+
+/**
+ * Subroutine calls are redirected to correspondent subroutine copies,
+ * other edges are just duplicated.
+ */
+static void InlineOutEdges(vf_ContextHandle ctx)
+{
+ vf_Graph *graph = ctx->m_graph;
+
+ for (vf_SubHandle sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+ if (!sub->m_copies) {
+ continue;
+ }
+ vf_Node *copy = sub->m_copies;
+ for (unsigned node_index = 0; node_index < sub->m_nodenum;
+ node_index++, copy += sub->m_dupcount - 1) {
+ vf_NodeHandle node = sub->m_nodes[node_index];
+
+ for (vf_EdgeHandle outedge = node->m_outedge; outedge;
+ outedge = outedge->m_outnext) {
+ vf_NodeHandle end_node = outedge->m_end;
+ vf_SubHandle end_sub = end_node->m_sub;
+
+ vf_Node *c = copy;
+ if (NULL == end_sub) {
+ for (unsigned index = 1; index < sub->m_dupcount; index++) {
+ graph->NewEdge(c++, (vf_Node *) end_node);
+ }
+ } else if (node->m_sub == end_sub) {
+ vf_Node *e = sub->m_copies +
+ end_node->m_nodecount * (sub->m_dupcount - 1);
+ for (unsigned index = 1; index < sub->m_dupcount; index++) {
+ graph->NewEdge(c++, e++);
+ }
+ } else {
+ assert(vf_is_jsr_branch(outedge, ctx));
+ assert(!outedge->m_outnext);
+ // an end node
+ vf_Node *e = end_sub->m_copies +
+ end_sub->m_entry->m_nodecount *
+ (end_sub->m_dupcount - 1) - 1;
+ // a node next to the start node
+ vf_Node *n = c + (sub->m_dupcount - 1);
+ for (unsigned index = 1;
+ index < node->m_sub->m_dupcount; index++) {
+ // direct jsr edge to correspondent subroutine copy
+ graph->NewEdge(c++, e + end_sub->m_index);
+ // store return point
+ assert(VF_NODE_CODE_RANGE == n->m_type);
+ end_sub->m_following_nodes[((vf_Sub *) end_sub)->
+ m_index++] = n++;
+ }
+ }
+ }
+ }
+ }
+} // InlineOutEdges
+
+/**
+ * Adds a back branch from <code>ret</code> nodes to a node
+ * which follows the correspondent <code>jsr</code> call node.
+ */
+static void InlineRetEdges(vf_ContextHandle ctx)
+{
+ vf_Graph *graph = ctx->m_graph;
+ for (vf_SubHandle sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+
+ vf_Node *ret_node = (vf_Node *) sub->m_ret;
+ vf_Node **next_node = sub->m_following_nodes;
+ graph->NewEdge(ret_node, *(next_node++));
+
+ vf_Node *ret_node_copy =
+ sub->m_copies + ret_node->m_nodecount * (sub->m_dupcount - 1);
+ for (unsigned index = 1; index < sub->m_dupcount; index++) {
+ // direct ret entry to the return point
+ graph->NewEdge(ret_node_copy++, *(next_node++));
+ }
+ }
+ assert(0 == ctx->m_graph->HasMoreEdgeSpace());
+} // InlineRetEdges
+
+/**
+ * Checks that every subroutine copy gets its call and
+ * all edges are created.
+ */
+static void CheckDupCounts(vf_ContextHandle ctx)
+{
+#if _VF_DEBUG
+ for (vf_SubHandle sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+ assert(sub->m_dupcount == sub->m_index);
+ }
+#endif // _VF_DEBUG
+}
+
+/**
+ * Calculates a number of additional nodes and edges and adds them
+ * to the graph.
+ */
+vf_Result vf_inline_subroutines(vf_Context *ctx)
+{
+ if (NULL == ctx->m_sub_ctx->m_sub) {
+ // subroutines are not reachable
+ return VER_OK;
+ }
+
+ unsigned count;
+ unsigned nodes = 0, edges = 0;
+ for (vf_Sub *sub = ctx->m_sub_ctx->m_sub; sub; sub = sub->m_next) {
+ vf_Result r = AddDupCount(sub, count, ctx);
+ if (VER_OK != r) {
+ return r;
+ }
+ // one copy already present in the graph
+ nodes += (sub->m_dupcount - 1) * sub->m_nodenum;
+ edges += (sub->m_dupcount - 1) * sub->m_out_edgenum;
+ // there is an additional edge from every ret
+ edges += sub->m_dupcount;
+ }
+ ctx->m_graph->CreateEdges(edges);
+
+ if (nodes) {
+ ctx->m_graph->CreateNodes(nodes);
+ InlineSubNodes(ctx);
+ }
+ InlineInEdges(ctx);
+
+ if (nodes) {
+ InlineOutEdges(ctx);
+ }
+
+ CheckDupCounts(ctx);
+ InlineRetEdges(ctx);
+ return VER_OK;
+} // vf_inline_subroutines
Modified: harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.h
URL: http://svn.apache.org/viewvc/harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.h?view=diff&rev=528575&r1=528574&r2=528575
==============================================================================
--- harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.h (original)
+++ harmony/enhanced/drlvm/trunk/vm/vmcore/src/verifier/ver_subroutine.h Fri Apr 13 11:26:27 2007
@@ -16,8 +16,119 @@
*/
#include "ver_graph.h"
+/**
+ * @ingroup Handles
+ * A handle of subroutine verification context.
+ */
+typedef const struct vf_SubContext *vf_SubContextHandle;
+/**
+ * @ingroup Handles
+ * A handle of subroutine verification context.
+ */
+typedef const struct vf_NodeStack *vf_NodeStackHandle;
+
+/**
+ * Subroutine info.
+ */
+struct vf_Sub
+{
+ /**
+ * A reference to the next subroutine.
+ */
+ vf_Sub *m_next;
+ /**
+ * A node which starts with subroutine entry point.
+ */
+ vf_NodeHandle m_entry;
+ /**
+ * A node which ends with ret instruction.
+ */
+ vf_NodeHandle m_ret;
+ /**
+ * A number of different <code>jsr</code> sequences to access
+ * this subroutine.
+ */
+ unsigned m_dupcount;
+ /**
+ * A number of nodes for this subroutine.
+ */
+ unsigned m_nodenum;
+ /**
+ * Subroutine nodes.
+ */
+ vf_NodeHandle *m_nodes;
+ /**
+ * Subroutine node copies. For each of <code>m_nodenum</code> nodes
+ * from <code>m_nodes</code> the (m_dupcount - 1) node copies follow
+ * one by one starting from this pointer.
+ * <code>NULL</code> when m_dupcount == 1.
+ */
+ vf_Node *m_copies;
+ /**
+ * For each of m_dupcount subroutine copies contain a return node for
+ * this copy.
+ */
+ vf_Node **m_following_nodes;
+ /**
+ * A number of edges between subroutine nodes.
+ */
+ unsigned m_out_edgenum;
+ /**
+ * A current duplication index.
+ */
+ unsigned m_index;
+};
+
+/**
+ * A stack of subsequent nodes representing a path traversing the graph, in
+ * particular a path to a <code>ret</code> node.
+ */
+struct vf_NodeStack
+{
+ /**
+ * A current node.
+ */
+ vf_Node *m_node;
+ /**
+ * An <i>out</i> stack depth of the node.
+ */
+ unsigned m_depth;
+ /**
+ * When a next stack element is created, points to the next stack element.
+ */
+ vf_NodeStackHandle m_next;
+
+ void Set(vf_NodeHandle node, unsigned depth)
+ {
+ m_node = (vf_Node *) node;
+ m_depth = depth;
+ m_next = NULL;
+ }
+};
+
/**
- * Verifier error codes.
+ * Aggregated subroutine data.
*/
-typedef Verifier_Result vf_Result;
+struct vf_SubContext
+{
+ /**
+ * Dedicated memory pool.
+ */
+ vf_Pool *m_pool;
+ /**
+ * A head of a list of subroutine descriptors.
+ */
+ vf_Sub *m_sub;
+ /**
+ * A start of a path to the current <code>ret</code>.
+ */
+ vf_NodeStackHandle m_path_start;
+ /**
+ * After the <code>ret</code> is resolved a <code>ctx->m_map</code> contains a
+ * correct input map for a node which follows <code>jsr</code> call. This is
+ * a pointer to the corresponding node stack. If this pointer is
+ * <code>NULL</code> we start from <code>m_path_start</code> stack entry.
+ */
+ vf_NodeStackHandle m_path_fork;
+};