verify-block.c

linux下建立JAVA虚拟机的源码KAFFE

/*
 * verify-block.c
 *
 * Copyright 2004, 2005
 *   Kaffe.org contributors. See ChangeLog for details. All rights reserved.
 *
 * See the file "license.terms" for information on usage and redistribution
 * of this file.
 *
 * Code for handing of blocks in the verifier.
 */

#include "config.h"

#ifdef HAVE_STRING_H
#include <string.h>
#endif

#include "bytecode.h"
#include "baseClasses.h"
#include "classMethod.h"
#include "code.h"
#include "constants.h"
#include "debug.h"
#include "errors.h"
#include "exception.h"
#include "gc.h"
#include "itypes.h"

#include "verify.h"
#include "verify-block.h"
#include "verify-debug.h"
#include "verify-errors.h"
#include "verify-sigstack.h"
#include "verify-type.h"
#include "verify-uninit.h"


/*********************************************************
 * BASIC BLOCK MEMORY MANAGEMENT
 *********************************************************/

/*
 * allocate memory for a block info and fill in with default values
 */
BlockInfo*
createBlock(const Method* method)
{
	int i;
	
	BlockInfo* binfo = checkPtr((BlockInfo*)gc_malloc(sizeof(BlockInfo), KGC_ALLOC_VERIFIER));
	
	binfo->startAddr   = 0;
	binfo->status      = IS_INSTRUCTION | START_BLOCK;  /* not VISITED or CHANGED */
	
	/* allocate memory for locals */
	if (method->localsz > 0) {
		binfo->locals = checkPtr(gc_malloc(method->localsz * sizeof(Type), KGC_ALLOC_VERIFIER));
		
		for (i = 0; i < method->localsz; i++) {
			binfo->locals[i] = *getTUNSTABLE();
		}
	} else {
		binfo->locals = NULL;
	}
	
	
	/* allocate memory for operand stack */
	binfo->stacksz = 0;
	if (method->stacksz > 0) {
		binfo->opstack = checkPtr(gc_malloc(method->stacksz * sizeof(Type), KGC_ALLOC_VERIFIER));
		
		for (i = 0; i < method->stacksz; i++) {
			binfo->opstack[i] = *getTUNSTABLE();
		}
	} else {
		binfo->opstack = NULL;
	}
	
	return binfo;
}

/*
 * frees the memory of a basic block
 */
void
freeBlock(BlockInfo* binfo)
{
	if (binfo == NULL) return;
	
	if (binfo->locals != NULL)
		gc_free(binfo->locals);
	if (binfo->opstack != NULL)
		gc_free(binfo->opstack);
	
	gc_free(binfo);
}

/*
 * copies information from one stack of basic blocks to another
 */
void
copyBlockData(const Method* method, BlockInfo* fromBlock, BlockInfo* toBlock)
{
	toBlock->startAddr = fromBlock->startAddr;
	toBlock->lastAddr  = fromBlock->lastAddr;
	
	copyBlockState(method, fromBlock, toBlock);
}

/*
 * copies the local variables, operand stack, status, and context
 * from one block to another.
 */
void
copyBlockState(const Method* method, BlockInfo* fromBlock, BlockInfo* toBlock)
{
	uint32 n;
	
	toBlock->status  = fromBlock->status;
	
	for (n = 0; n < method->localsz; n++) {
		toBlock->locals[n] = fromBlock->locals[n];
	}
	
	toBlock->stacksz = fromBlock->stacksz;
	for (n = 0; n < method->stacksz; n++) {
		toBlock->opstack[n] = fromBlock->opstack[n];
	}
}

/*
 * returns which block the given pc is in
 */
BlockInfo*
inWhichBlock(uint32 pc, BlockInfo** blocks, uint32 numBlocks)
{
	uint32 i;
	for (i = 0; i < numBlocks; i++) {
		if (pc < blocks[i]->startAddr) continue;
		if (pc <= blocks[i]->lastAddr) return blocks[i];
	}
	
	/* shouldn't ever get here unless the specified PC is messed up */
	DBG(VERIFY3, dprintf("inWhichBlock(...): pc = %d out of range...weird.\n", pc); );
	
	return NULL;
}


/*********************************************************
 * BASIC BLOCK VERIFICATION
 *********************************************************/
/*
 * Helper function for error reporting in ENSURE_LOCAL_TYPE macro in verifyBasicBlock.
 */
static inline
bool
ensureLocalTypeErrorInVerifyBasicBlock(Verifier* v,
				       const BlockInfo* block,
				       const unsigned int n)
{
	if (block->locals[n].data.class == getTUNSTABLE()->data.class) {
		return verifyError(v, "attempt to access an unstable local variable");
	} else {
		return verifyError(v, "attempt to access a local variable not of the correct type");
	}
}

/*
 * Helper function for error reporting in ENSURE_OPSTACK_SIZE macro in verifyBasicBlock.
 */
static
bool
ensureOpstackSizeErrorInVerifyBasicBlock(Verifier* v,
					 const BlockInfo* block)

{
	DBG(VERIFY3,
	    dprintf("                here's the stack: \n");
	    printBlock(v->method, block, "                    ");
	    );
	return verifyError(v, "not enough items on stack for operation");
}

/*
 * Helper function for error reporting in CHECK_STACK_OVERFLOW macro in verifyBasicBlock.
 */
static inline
bool
checkStackOverflowErrorInVerifyBasicBlock(Verifier* v,
					  const BlockInfo* block,
					  const unsigned int n)
{
	DBG(VERIFY3,
	    dprintf("                block->stacksz: %d :: N = %d :: method->stacksz = %d\n",
		    block->stacksz,
		    n,
		    v->method->stacksz);
	    );
	DBG(VERIFY3,
	    dprintf("                here's the stack: \n");
	    printBlock(v->method, block, "                    ");
	    );
	return verifyError(v, "stack overflow");
}

/*
 * Helper function for opstack access in verifyBasicBlock.
 *
 * @return nth item on the operand stack from the top.
 */
static inline
Type *
getOpstackItem(BlockInfo* block,
	       unsigned int n)
{
	return (&block->opstack[block->stacksz - n]);
}

/*
 * Helper function for opstack access in verifyBasicBlock.
 *
 * @return first item on the operand stack from the top.
 */
static inline
Type *
getOpstackTop(BlockInfo* block)
{
	return getOpstackItem(block, 1);
}

/*
 * Helper function for opstack access in verifyBasicBlock.
 *
 * @return second item on the operand stack from the top.
 */
static inline
Type *
getOpstackWTop(BlockInfo* block)
{
	return getOpstackItem(block, 2);
}

/*
 * Helper function for opstack access in verifyBasicBlock.
 */
static inline
void
opstackPushBlind(BlockInfo* block,
		 const Type* type)
{
	block->opstack[block->stacksz++] = *(type);
}

/*
 * Helper function for opstack access in verifyBasicBlock.
 * only use for LONGs and DOUBLEs.
 */
static inline
void
opstackWPushBlind(BlockInfo* block,
		  const Type* type)
{
	opstackPushBlind(block, type);
	opstackPushBlind(block, getTWIDE());
}

/*
 * Helper function for opstack access in verifyBasicBlock.
 */
static inline
void
opstackPopBlind(BlockInfo* block)
{
	block->stacksz--;
	block->opstack[block->stacksz] = *getTUNSTABLE();
}

/*
 * Helper function for opstack access in verifyBasicBlock.
 */
static inline
void
opstackWPopBlind(BlockInfo* block)
{
	opstackPopBlind(block);
	opstackPopBlind(block);
}

/*
 * Helper function for opstack access in verifyBasicBlock.
 * pop _N things off the stack off the stack.
 */
static inline
void
opstackPopNBlind(BlockInfo* block,
		 unsigned int n)
{
	unsigned int i;

	for (i = 0; i < n; ++i) {
		opstackPopBlind(block);
	}
}

/*
 * Helper function for error reporting in OPSTACK_PEEK_T_BLIND macro in verifyBasicBlock.
 */
static
bool
opstackPeekTBlindErrorInVerifyBasicBlock(Verifier* v,
					 BlockInfo* block,
					 const Type* type)
{
	DBG(VERIFY3,
	    dprintf("                OPSTACK_TOP: ");
	    printType(getOpstackTop(block));
	    dprintf(" vs. what's we wanted: ");
	    printType(type);
	    dprintf("\n");
	    );
	return verifyError(v, "top of opstack does not have desired type");
}

/*
 * verifyBasicBlock()
 *   Simulates execution of a basic block by modifying its
 *   simulated operand stack and local variable array.
 *
 * TODO: turn at least some of the macros into static
 * inline methods
 */
bool
verifyBasicBlock(Verifier* v, BlockInfo* block)
{
	/**************************************************************************************************
	 * VARIABLES
	 **************************************************************************************************/
	uint32            pc   = 0;
	unsigned char*    code = METHOD_BYTECODE_CODE(v->method);
	
	bool wide = false;       /* was the previous opcode a WIDE instruction? */
	
	uint32 n = 0;            /* used as a general temporary variable, often as a temporary pc */
	
	Type* type = NULL;
	Type* arrayType = NULL;
	Hjava_lang_Class* class; /* for when we need a pointer to an actual class */
	
	/* for the rare occasions when we actually need a Type */
	Type  tt;
	Type* t = &tt;
	
	int tag;                 /* used for constant tag stuff */
	
	uint32     idx;          /* index into constant pool */
	const constants* pool = CLASS_CONSTANTS(v->class);
	
	const char* sig;
	
	
	/**************************************************************************************************
	 * HANDY MACROS USED ONLY IN THIS METHOD
	 *    most of these belong to one of two categories:
	 *         - those dealing with locals variables
	 *         - those dealing with the operand stack
	 **************************************************************************************************/

#define GET_IDX \
	idx = getIdx(code, pc)
	
#define GET_WIDX \
	idx = getWIdx(code, pc)
	
	
	/* checks whether the specified local variable is of the specified type. */
#define ENSURE_LOCAL_TYPE(_N, _TINFO) \
	if (!typecheck(v, (_TINFO), &block->locals[_N])) { \
		return ensureLocalTypeErrorInVerifyBasicBlock(v, block, _N); \
	} 
	
	/* only use with TLONG and TDOUBLE */
#define ENSURE_LOCAL_WTYPE(_N, _TINFO) \
	if (block->locals[_N].data.class != (_TINFO)->data.class) { \
		return verifyError(v, "local variable not of correct type"); \
	} \
	else if (block->locals[_N + 1].data.class != getTWIDE()->data.class) { \
		return verifyError(v, "accessing a long or double in a local where the following local has been corrupted"); \
	}

	
#define ENSURE_OPSTACK_SIZE(_N) \
	if (block->stacksz < (_N)) { \
		return ensureOpstackSizeErrorInVerifyBasicBlock(v, block); \
	}

#define CHECK_STACK_OVERFLOW(_N) \
	if (block->stacksz + _N > v->method->stacksz) { \
		return checkStackOverflowErrorInVerifyBasicBlock(v, block, _N); \
	}
	
#define OPSTACK_PUSH(_TINFO) \
	CHECK_STACK_OVERFLOW(1); \
	opstackPushBlind(block, _TINFO)

#define OPSTACK_WPUSH(_T) \
	CHECK_STACK_OVERFLOW(2); \
        opstackWPushBlind(block, _T)
	
	
	
	/* ensure that the top item on the stack is of type _T	*/
#define OPSTACK_PEEK_T_BLIND(_TINFO) \
	if (!typecheck(v, _TINFO, getOpstackTop(block))) { \
		return opstackPeekTBlindErrorInVerifyBasicBlock(v, block, _TINFO); \
	}
	
#define OPSTACK_PEEK_T(_TINFO) \
        ENSURE_OPSTACK_SIZE(1); \
	OPSTACK_PEEK_T_BLIND(_TINFO)
	
	/* ensure that the top item on the stack is of wide type _T
	 * this only works with doubles and longs
	 */
#define OPSTACK_WPEEK_T_BLIND(_TINFO) \
	if (getOpstackTop(block)->data.class != getTWIDE()->data.class) { \
		return verifyError(v, "trying to pop a wide value off operand stack where there is none"); \
	} else if (getOpstackWTop(block)->data.class != (_TINFO)->data.class) { \
		return verifyError(v, "mismatched stack types"); \
	}
	
#define OPSTACK_WPEEK_T(_TINFO) \
	ENSURE_OPSTACK_SIZE(2); \
	OPSTACK_WPEEK_T_BLIND(_TINFO)
	
#define OPSTACK_POP \
        ENSURE_OPSTACK_SIZE(1); \
	opstackPopBlind(block)

	/* pop a type off the stack and typecheck it */
#define OPSTACK_POP_T_BLIND(_TINFO) \
	OPSTACK_PEEK_T_BLIND(_TINFO); \
	opstackPopBlind(block)

#define OPSTACK_POP_T(_TINFO) \
	OPSTACK_PEEK_T(_TINFO); \
        opstackPopBlind(block)

#define OPSTACK_WPOP \
	ENSURE_OPSTACK_SIZE(2); \
	opstackWPopBlind(block)

	/* pop a wide type off the stack and typecheck it */
#define OPSTACK_WPOP_T_BLIND(_TINFO) \
	OPSTACK_WPEEK_T_BLIND(_TINFO); \
	opstackWPopBlind(block)

#define OPSTACK_WPOP_T(_TINFO) \
        OPSTACK_WPEEK_T(_TINFO); \
	opstackWPopBlind(block)
	
#define OPSTACK_POP_N(_N) \
        ENSURE_OPSTACK_SIZE(_N); \
	opstackPopNBlind(block, _N)
	
	
	
	/**************************************************************************************************
	 * BLOCK-LEVEL DATA FLOW ANALYASIS
	 *    this is actually pretty easy, since there are never any branches.  basically, it just
	 *    manipulates the working stack after every instruction as if it were actually running the
	 *    code so that, after verifying the block, the working block can be used to merge this block
	 *    with its successors.
	 **************************************************************************************************/
	DBG(VERIFY3,
	    dprintf("        about to verify the block...\n");
	    dprintf("        block->startAddr = %d, block->lastAddr = %d, first instruction = %d\n",
		    block->startAddr, block->lastAddr, code[block->startAddr]);
	    );
	
	pc = block->startAddr;
	while (pc <= block->lastAddr) {
		DBG(VERIFY3,
		    dprintf("            pc = %d, opcode = %d == ", pc, code[pc]);
		    printInstruction(code[pc]);
		    dprintf("\n");
		    );
		
		switch(code[pc]) {
			/**************************************************************
			 * INSTRUCTIONS FOR PUSHING CONSTANTS ONTO THE STACK
			 **************************************************************/
			/* pushes NULL onto the stack, which matches any object */
		case ACONST_NULL:
			OPSTACK_PUSH(getTNULL());
			break;
			
			/* iconst_<n> pushes n onto the stack */
		case ICONST_0: case ICONST_1: case ICONST_2:
		case ICONST_3: case ICONST_4: case ICONST_5:
			
		case ICONST_M1: /* pushes -1 onto the stack */
		case BIPUSH:    /* sign extends an 8-bit int to 32-bits and pushes it onto stack */
		case SIPUSH:    /* sign extends a 16-bit int to 32-bits and pushes it onto stack */
			OPSTACK_PUSH(getTINT());
			break;
			
		case FCONST_0:
		case FCONST_1:
		case FCONST_2:
			OPSTACK_PUSH(getTFLOAT());
			break;
			
		case LCONST_0:
		case LCONST_1:
			OPSTACK_WPUSH(getTLONG());
			break;
			
		case DCONST_0:
		case DCONST_1:
			OPSTACK_WPUSH(getTDOUBLE());
			break;
			
			
		case LDC1:
			GET_IDX;
			goto LDC_common;
		case LDC2:
			GET_WIDX;
		LDC_common:
			tag = CONST_TAG(idx, pool);
			switch(tag) {
			case CONSTANT_Integer: OPSTACK_PUSH(getTINT());    break;
			case CONSTANT_Float:   OPSTACK_PUSH(getTFLOAT());  break;
			case CONSTANT_ResolvedString:
			case CONSTANT_String:
			        /* we do this because we might be loading a class before
				 * loading String
				 */
				OPSTACK_PUSH(getTSTRING());