verify.c

kaffe Java 解释器语言,源码,Java的子集系统,开放源代码

 *       code-analyze.c again later on.
 ************************************************************************************/

/* lengths in bytes of all the instructions */
/* 16 rows of 16 */
static const uint8 insnLen[256] = {
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
	2, 3, 2, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
	1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
	1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
	1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 3, 
	3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 0, 0, 1, 1, 1, 1, 
	1, 1, 3, 3, 3, 3, 3, 3, 3, 5, 1, 3, 2, 3, 1, 1, 
	3, 3, 1, 1, 1, 4, 3, 3, 5, 5, 1, 1, 1, 1, 1, 1, 
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 
};


/* these retrieve the word (16 bits) or double world (32 bits) of bytecode starting
 * at pc = _PC
 */
#define	WORD(_CODE, _PC)  ((int16)( \
			   (_CODE[(_PC)+0] << 8) | \
			   (_CODE[(_PC)+1])))
#define	DWORD(_CODE, _PC) ((int32)( \
			   (_CODE[(_PC)+0] << 24) | \
			   (_CODE[(_PC)+1] << 16) | \
			   (_CODE[(_PC)+2] << 8) | \
			   (_CODE[(_PC)+3])))


/*
 * types for type checking (pass 3b)
 */
static Type  verify_UNSTABLE;
static Type* TUNSTABLE = &verify_UNSTABLE;

static Type  verify_INT;
static Type* TINT = &verify_INT;
       
static Type  verify_FLOAT;
static Type* TFLOAT = &verify_FLOAT;
       
static Type  verify_LONG;
static Type* TLONG = &verify_LONG;
       
static Type  verify_DOUBLE;
static Type* TDOUBLE = &verify_DOUBLE;

/* used for the second space of LONGs and DOUBLEs
 * in local variables or on the operand stack
 */
static Type  _WIDE;
static Type* TWIDE = &_WIDE;
#define IS_WIDE(_TINFO) ((_TINFO)->data.class == TWIDE->data.class)



static Type  verify_NULL;
static Type* TNULL = &verify_NULL;
#define IS_NULL(_TINFO) ((_TINFO)->data.class == TNULL->data.class)


static const char* OBJECT_SIG  = "Ljava/lang/Object;";
static Type  verify_OBJ;
static Type* TOBJ = &verify_OBJ;

static const char* OBJARR_SIG = "[Ljava/lang/Object;";
static Type  verify_OBJARR;
static Type* TOBJARR = &verify_OBJARR;


static const char* STRING_SIG = "Ljava/lang/String;";
static Type  verify_STRING;
static Type* TSTRING = &verify_STRING;


static const char* CHARARR_SIG = "[C";
static Type  verify_CHARARR;
static Type* TCHARARR = &verify_CHARARR;

static const char* BYTEARR_SIG = "[B";
static Type  verify_BYTEARR;
static Type* TBYTEARR = &verify_BYTEARR;

static const char* BOOLARR_SIG = "[Z";
static Type  verify_BOOLARR;
static Type* TBOOLARR = &verify_BOOLARR;

static const char* SHORTARR_SIG = "[S";
static Type  verify_SHORTARR;
static Type* TSHORTARR = &verify_SHORTARR;

static const char* INTARR_SIG = "[I";
static Type  verify_INTARR;
static Type* TINTARR = &verify_INTARR;

static const char* LONGARR_SIG = "[J";
static Type  verify_LONGARR;
static Type* TLONGARR = &verify_LONGARR;

static const char* FLOATARR_SIG = "[F";
static Type  verify_FLOATARR;
static Type* TFLOATARR = &verify_FLOATARR;

static const char* DOUBLEARR_SIG = "[D";
static Type  verify_DOUBLEARR;
static Type* TDOUBLEARR = &verify_DOUBLEARR;


#define IS_PRIMITIVE_ARRAY(_TINFO) \
           (((_TINFO)->data.class) == TCHARARR->data.class  || ((_TINFO)->data.class) == TBYTEARR->data.class || \
	    ((_TINFO)->data.class) == TSHORTARR->data.class || ((_TINFO)->data.class) == TINTARR->data.class  || \
	    ((_TINFO)->data.class) == TLONGARR->data.class  || \
            ((_TINFO)->data.class) == TFLOATARR->data.class || ((_TINFO)->data.class) == TDOUBLEARR->data.class)



/***********************************************************************************
 * Methods for Pass 3 Verification
 ***********************************************************************************/
#ifdef KAFFE_VMDEBUG
static void printInstruction(const int opcode);
static void printType(const Type*);
static void printBlock(const Method* method, const BlockInfo* binfo, const char* indent);
#endif

static BlockInfo*         createBlock(const Method* method);
static void               copyBlockData(const Method* method, BlockInfo* fromBlock, BlockInfo* toBlock);
static void               copyBlockState(const Method* method, BlockInfo* fromBlock, BlockInfo* toBlock);
static void               freeBlock(BlockInfo* binfo);

static BlockInfo*         inWhichBlock(uint32 pc, BlockInfo** blocks, uint32 numBlocks);


static SigStack*          pushSig(SigStack* sigs, const char* sig);
static void               freeSigStack(SigStack* sigs);

static bool               checkUninit(Hjava_lang_Class* this, Type* type);
static UninitializedType* pushUninit(UninitializedType* uninits, const Type* type);
static void               popUninit(const Method*, UninitializedType*, BlockInfo*);
static void               freeUninits(UninitializedType* uninits);


static bool               verifyMethod(errorInfo* einfo, Method* method);
static BlockInfo**        verifyMethod3a(errorInfo* einfo,
					 Method* method,
					 uint32* status,     /* array of status info for all opcodes */
					 uint32* numBlocks); /* number of basic blocks */
static bool               verifyMethod3b(errorInfo* einfo,
					 const Method* method,
					 const uint32* status,
					 BlockInfo** blocks,
					 const uint32 numBlocks,
					 SigStack** sigs,
					 UninitializedType** uninits);

static bool               merge(errorInfo* einfo, const Method* method, BlockInfo* fromBlock, BlockInfo* toBlock);
static bool               verifyBasicBlock(errorInfo*,
					   const Method*,
					   BlockInfo*,
					   SigStack**,
					   UninitializedType**);

static const char*        getNextArg(const char* sig, char* buf);
static bool               loadInitialArgs(const Method* method, errorInfo* einfo,
					  BlockInfo* block, SigStack** sigs, UninitializedType** uninits);

static bool               isReference(const Type* type);
static bool               isArray(const Type* type);
static bool               sameType(Type* t1, Type* t2);
static bool               sameRefType(Type* t1, Type* t2);
static void               resolveType(errorInfo* einfo, Hjava_lang_Class* this, Type *type);

static bool               mergeTypes(errorInfo*, Hjava_lang_Class* this,
				     Type* t1, Type* t2);
static Hjava_lang_Class*  getCommonSuperclass(Hjava_lang_Class* t1,
					      Hjava_lang_Class* t2);


static bool               typecheck(errorInfo*, Hjava_lang_Class* this, Type* t1, Type* t2);

static const char*        getReturnSig(const Method*);
static uint32             countSizeOfArgsInSignature(const char* sig);
static bool               checkMethodCall(errorInfo* einfo, const Method* method,
					  BlockInfo* binfo, uint32 pc,
					  SigStack** sigs, UninitializedType** uninits);


/*
 * Initialize Type structures needed for verification
 */
void
initVerifierPrimTypes(void)
{
	TUNSTABLE->tinfo = TINFO_SYSTEM;
	TUNSTABLE->data.class = (Hjava_lang_Class*)TUNSTABLE;
	
	TWIDE->tinfo = TINFO_SYSTEM;
	TWIDE->data.class = (Hjava_lang_Class*)TWIDE;
	
	
	TINT->tinfo = TINFO_PRIMITIVE;
	TINT->data.class = intClass;
	
	TLONG->tinfo = TINFO_PRIMITIVE;
	TLONG->data.class = longClass;
	
	TFLOAT->tinfo = TINFO_PRIMITIVE;
	TFLOAT->data.class = floatClass;
	
	TDOUBLE->tinfo = TINFO_PRIMITIVE;
	TDOUBLE->data.class = doubleClass;
	
	
	TNULL->tinfo = TINFO_CLASS;
	TNULL->data.class = (Hjava_lang_Class*)TNULL;
	
	TOBJ->tinfo = TINFO_SIG;
	TOBJ->data.sig = OBJECT_SIG;
	
	TOBJARR->tinfo = TINFO_SIG;	
	TOBJARR->data.sig = OBJARR_SIG;
	
	
	TSTRING->data.sig = STRING_SIG;
	TSTRING->tinfo = TINFO_SIG;
	
	
	TCHARARR->tinfo = TINFO_SIG;
	TCHARARR->data.sig = CHARARR_SIG;
	
	TBYTEARR->tinfo = TINFO_SIG;
	TBYTEARR->data.sig = BYTEARR_SIG;
	
	TBOOLARR->tinfo = TINFO_SIG;
	TBOOLARR->data.sig = BOOLARR_SIG;
	
	TSHORTARR->tinfo = TINFO_SIG;
	TSHORTARR->data.sig = SHORTARR_SIG;
	
	TINTARR->tinfo = TINFO_SIG;
	TINTARR->data.sig = INTARR_SIG;
	
	TLONGARR->tinfo = TINFO_SIG;
	TLONGARR->data.sig = LONGARR_SIG;
	
	TFLOATARR->tinfo = TINFO_SIG;
	TFLOATARR->data.sig = FLOATARR_SIG;
	
	TDOUBLEARR->tinfo = TINFO_SIG;	
	TDOUBLEARR->data.sig = DOUBLEARR_SIG;
}


/*
 * Verify pass 3:  Check the consistency of the bytecode.
 *
 * This is the k-razy step that does data-flow analysis to prove the safety of the code.
 */
bool
verify3(Hjava_lang_Class* class, errorInfo *einfo)
{
	uint32 n;
	bool success = true;
	Method* method;
	
	/* see if verification is turned on, and whether the class we're about to verify requires verification
	 *
	 * NOTE: we don't skip interfaces here because an interface may contain a <clinit> method with bytecode
	 */
	if (isTrustedClass(class)) {
		goto done;
	}
	
	
	/* make sure it's initialized...we had some problems because of this */
	einfo->type = 0;
	
	
	DBG(VERIFY3, dprintf("\nPass 3 Verifying Class \"%s\"\n", CLASS_CNAME(class)); );
	DBG(VERIFY3, {
		Hjava_lang_Class* tmp;
		for (tmp = class->superclass; tmp; tmp = tmp->superclass) {
			dprintf("                        |-> %s\n", CLASS_CNAME(tmp));
		}
	});
	
	for (n = CLASS_NMETHODS(class), method = CLASS_METHODS(class);
	     n > 0;
	     --n, ++method) {
		
		DBG(VERIFY3, dprintf("\n  -----------------------------------\n  considering method %s%s\n",
				     METHOD_NAMED(method), METHOD_SIGD(method)); );
		
		/* if it's abstract or native, no verification necessary */
		if (!(METHOD_IS_ABSTRACT(method) || METHOD_IS_NATIVE(method))) {
			DBG(VERIFY3, dprintf("  verifying method %s\n", METHOD_NAMED(method)); );
			
			if (!parseMethodTypeDescriptor(METHOD_SIGD(method))) {
				postExceptionMessage(einfo, JAVA_LANG(ClassFormatError),
						     "Method %s.%s has invalid signature, %s",
						     CLASS_CNAME(class), METHOD_NAMED(method), METHOD_SIGD(method));
				success = false;
				goto done;
			}
			else if (!verifyMethod(einfo, method)) {
				if (einfo->type == 0) {
					postExceptionMessage(einfo, JAVA_LANG(InternalError),
							     "failure to verify method %s.%s ... reason unspecified",
							     CLASS_CNAME(class), METHOD_NAMED(method));
				}
				success = false;
				goto done;
			}
		}
	}
	
	
 done:
	DBG(VERIFY3, dprintf("\nDone Pass 3 Verifying Class \"%s\"\n", CLASS_CNAME(class)); );
	return success;
}

/*
 * Controls the verification of a single method.  It allocates most of the memory needed for
 * verification (when encountering JSRs, more memory will need to be allocated later),
 * loads the initial arguments, calls pass3a, then calls pass3b and cleans up.
 */
static
bool
verifyMethod(errorInfo *einfo, Method* method)
{
        /* to save some typing, etc. */
	int codelen  = METHOD_BYTECODE_LEN(method);
	
	uint32* status = NULL; /* the status of each instruction...changed, visited, etc.
				* used primarily to help find the basic blocks initially
				*/

	SigStack* sigs = NULL;
	
	UninitializedType* uninits = NULL;
	
	uint32      numBlocks = 0;
	BlockInfo** blocks    = NULL;
	
	
	/**************************************************************************************************
	 * Memory Management Macros
	 **************************************************************************************************/
	/* to make sure we don't forget to unalloc anything...
	 * should be called during ANY EXIT FROM THIS METHOD
	 */
#define CLEANUP \
	DBG(VERIFY3, dprintf("    cleaning up..."); ); \
	KFREE(status); \
        if (blocks != NULL) { \
		while (numBlocks > 0) { \
			freeBlock(blocks[--numBlocks]); \
		} \
		KFREE(blocks); \
	} \
        freeSigStack(sigs); \
        freeUninits(uninits); \
        DBG(VERIFY3, dprintf(" done\n"); )
	
#define FAIL \
        DBG(VERIFY3, dprintf("    Verify Method 3b: %s.%s%s: FAILED\n", \
			     CLASS_CNAME(method->class), METHOD_NAMED(method), METHOD_SIGD(method)); ); \
	if (einfo->type == 0) { \
		DBG(VERIFY3, dprintf("      DBG ERROR: should have raised an exception\n"); ); \
		postException(einfo, JAVA_LANG(VerifyError)); \
	} \
        CLEANUP; \
        return(false)
	
	
	/**************************************************************************************************
	 * Memory Allocation
	 **************************************************************************************************/
	DBG(VERIFY3, dprintf("        allocating memory for verification (codelen = %d)...\n", codelen); );
	
        status   = checkPtr((char*)gc_malloc(codelen * sizeof(uint32), GC_ALLOC_VERIFIER));
	
	/* find basic blocks and allocate memory for them */
	blocks = verifyMethod3a(einfo, method, status, &numBlocks);
	if (!blocks) {
		DBG(VERIFY3, dprintf("        some kinda error finding the basic blocks in pass 3a\n"); );
		
		/* propagate error */
		FAIL;
	}
	
	DBG(VERIFY3, dprintf("        done allocating memory\n"); );
	/**************************************************************************************************
	 * Prepare for data-flow analysis
	 **************************************************************************************************/
	
	/* load initial arguments into local variable array */
	DBG(VERIFY3, dprintf("    about to load initial args...\n"); );
	if (!loadInitialArgs(method, einfo, blocks[0], &sigs, &uninits)) {
	        /* propagate error */
		FAIL;
	}
	DBG(VERIFY3, {
	        /* print out the local arguments */
		int n;
		for(n = 0; n < method->localsz; n++) {
			dprintf("        local %d: ", n);
			printType(&blocks[0]->locals[n]);
			dprintf("\n");
		}
	} );
	
	
	if (!verifyMethod3b(einfo, method,
			    status, blocks, numBlocks,
			    &sigs, &uninits)) {
		FAIL;
	}
	
	CLEANUP;
	DBG(VERIFY3, dprintf("    Verify Method 3b: done\n"); );
	return(true);
	

#undef FAIL
#undef CLEANUP
}