verify.c

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

			
			BRANCH_IN_BOUNDS(newpc, "jsr");
			status[newpc] |= START_BLOCK;
			
			/* the next instruction is a target for branching via RET */
			pc = NEXTPC;
			BRANCH_IN_BOUNDS(pc, "jsr/ret");
			status[pc] |= START_BLOCK;
			continue;
			
		case RET:
			status[pc] |= END_BLOCK;
			if (!wide) {
				GET_IDX(idx, pc);
			} else {
				GET_WIDX(idx, pc);
				
				status[pc] ^= IS_INSTRUCTION;
				status[pc] |= WIDE_MODDED;
				
				wide = false;
				pc += 2;
			}
			CHECK_LOCAL_INDEX(idx);
			pc = NEXTPC;
			continue;
			
			
		case LOOKUPSWITCH:
			ENSURE_NON_WIDE;
			status[pc] |= END_BLOCK;
			
			/* default branch...between 0 and 3 bytes of padding are added so that the
			 * default branch is at an address that is divisible by 4
			 */
			n = (pc + 1) % 4;
			if (n) n = pc + 5 - n;
			else   n = pc + 1;
			newpc = pc + DWORD(code, n);
			BRANCH_IN_BOUNDS(newpc, "lookupswitch");
			status[newpc] |= START_BLOCK;
			DBG(VERIFY3,
			    dprintf("          lookupswitch: pc = %d ... instruction = ", newpc);
			    printInstruction(code[newpc]);
			    dprintf("\n");
			    );
			
			/* get number of key/target pairs */
			n += 4;
			low = DWORD(code, n);
			if (low < 0) {
				VERIFY_ERROR("lookupswitch with npairs < 0");
			}
			
			/* make sure all targets are in bounds */
			for (n += 4, high = n + 8*low; n < high; n += 8) {
				newpc = pc + DWORD(code, n+4);
				BRANCH_IN_BOUNDS(newpc, "lookupswitch");
				status[newpc] |= START_BLOCK;
				
				DBG(VERIFY3,
				    dprintf("          lookupswitch: pc = %d ... instruction = ", newpc);
				    printInstruction(code[newpc]);
				    dprintf("\n");
				    );
			}
			
			pc = high;
			continue;
			
			
		case TABLESWITCH:
			ENSURE_NON_WIDE;
			status[pc] |= END_BLOCK;
			
			/* default branch...between 0 and 3 bytes of padding are added so that the
			 * default branch is at an address that is divisible by 4
			 */
			n = (pc + 1) % 4;
			if (n) n = pc + 5 - n;
			else   n = pc + 1;
			newpc = pc + DWORD(code, n);
			BRANCH_IN_BOUNDS(newpc, "tableswitch");
			status[newpc] |= START_BLOCK;
			DBG(VERIFY3,
			    dprintf("          tableswitch: pc = %d ... instruction = ", newpc);
			    printInstruction(code[newpc]);
			    dprintf("\n");
			    );
			
			/* get the high and low values of the table */
			low  = DWORD(code, n + 4);
			high = DWORD(code, n + 8);
			if (high < low) {
				DBG(VERIFY3, dprintf("ERROR: low = %d, high = %d\n", low, high); );
				VERIFY_ERROR("tableswitch high val < low val");
			}
			n += 12;
			
			/* high and low are used as temps in this loop that checks
			 * the validity of all the branches in the table
			 */
			for (high = n + 4*(high - low + 1); n < high; n += 4) {
				newpc = pc + DWORD(code, n);
				BRANCH_IN_BOUNDS(newpc, "tableswitch");
				status[newpc] |= START_BLOCK;
				
				DBG(VERIFY3,
				    dprintf("          tableswitch: pc = %d ... instruction = ", newpc);
				    printInstruction(code[newpc]);
				    dprintf("\n");
				    );
			}
			
			pc = high;
			continue;
			
			
			/* the rest of the ways to end a block */
		case RETURN:
		case ARETURN:
		case IRETURN:
		case FRETURN:
		case LRETURN:
		case DRETURN:
		case ATHROW:
			ENSURE_NON_WIDE;
			status[pc] |= END_BLOCK;
			break;
			
			
		default:
			if (wide == true) {
				VERIFY_ERROR("illegal instruction following wide instruction");
			}
		}
		
		pc = NEXTPC;
	}
	
	
	DBG(VERIFY3, dprintf("    Verifier Pass 3a: second pass to locate illegal branches and count blocks...\n"); );
	
	/* newpc is going to stand for the PC of the previous instruction */
	for (newpc = 0, pc = 0; pc < codelen; pc++) {
		if (status[pc] & IS_INSTRUCTION) {
			if (status[pc] & START_BLOCK) {
				blockCount++;
				
				if (newpc < pc) {
				        /* make sure that the previous instruction is
					 * marked as the end of a block (it would only
					 * have been marked so if it were some kind of
					 * branch).
					 */
					status[newpc] |= END_BLOCK;
				}
			}
			
			newpc = pc;
		}
		else if (status[pc] & START_BLOCK) {
			VERIFY_ERROR("branch into middle of instruction");
		}
	}
	
	
	DBG(VERIFY3, dprintf("        perusing exception table\n"); );
	if (method->exception_table != 0) {
		jexceptionEntry *entry;
		for (n = 0; n < method->exception_table->length; n++) {
			entry = &(method->exception_table->entry[n]);
			
			pc = entry->handler_pc;
			if (pc >= codelen) {
				VERIFY_ERROR("exception handler is beyond bound of method code");
			}
			else if (!(status[pc] & IS_INSTRUCTION)) {
				VERIFY_ERROR("exception handler starts in the middle of an instruction");
			}
			
			status[pc] |= (EXCEPTION_HANDLER & START_BLOCK);
			
			
			/* verify properties about the clause
			 *
			 * if entry->catch_type == 0, it's a finally clause
			 */
			if (entry->catch_type != 0) {
				if (entry->catch_type == NULL) {
					entry->catch_type = getClass(entry->catch_idx, method->class, einfo);
				}
				if (entry->catch_type == NULL) {
					DBG(VERIFY3, dprintf("        ERROR: could not resolve catch type...\n"); );
					entry->catch_type = UNRESOLVABLE_CATCHTYPE;
					
					VERIFY_ERROR("unresolvable catch type");
				}
				if (!instanceof(javaLangThrowable, entry->catch_type)) {
					VERIFY_ERROR("Exception to be handled by exception handler is not a subclass of Java/Lang/Throwable");
				}
			}
		}
	}
	
	
	DBG(VERIFY3, dprintf("        done, %d blocks found.\n", blockCount); );
	
	
	DBG(VERIFY3, dprintf("    Verifier Pass 3a: third pass to allocate memory for basic blocks...\n"); );
	
	blocks = checkPtr((BlockInfo**)gc_malloc(blockCount * sizeof(BlockInfo*), GC_ALLOC_VERIFIER));
	
	for (inABlock = true, n = 0, pc = 0; pc < codelen; pc++) {
		if (status[pc] & START_BLOCK) {
			blocks[n] = createBlock(method);
			blocks[n]->startAddr = pc;
			n++;
			
			inABlock = true;
			
			
			DBG(VERIFY3, dprintf("        setting blocks[%d]->startAddr = %d\n",
					     n-1, blocks[n-1]->startAddr); );
		}
		
		if (inABlock && (status[pc] & END_BLOCK)) {
			blocks[n-1]->lastAddr = pc;
			
			inABlock = false;
			
			
			DBG(VERIFY3, dprintf("        setting blocks[%d]->lastAddr = %d\n",
					     n-1, blocks[n-1]->lastAddr); );
		}
	}
	
	
	DBG(VERIFY3, dprintf("    Verifier Pass 3a: done\n"); );
	
	*numBlocks = blockCount;
	return blocks;
	
	
#undef CHECK_LOCAL_INDEX	
#undef NEXTPC
#undef BRANCH_IN_BOUNDS
#undef GET_IDX
#undef GET_WIDX
#undef CHECK_POOL_IDX
#undef ENSURE_NON_WIDE
#undef VERIFY_ERROR
}


/*
 * verifyMethod3b()
 *    The Data-flow Analyzer
 *
 * The data-flow algorithm is taken from the JVM 2 spec, which describes it more or less as follows:
 *
 *  0  data-flow analyzer is initialised
 *       - for the first instruction of the method, the local variables that represent parameters
 *         initially contain values of the types indicated by the method's type descriptor.
 *       - the operand stack is empty.
 *       - all local variables contain an illegal value.
 *       - for the other instructions, which have not been examined yet, no information is available
 *         regarding the operand stack or local variables.
 *       - the "changed" bit is only set for the first instruction.
 *
 *  1  select a VM instruction whose "changed" bit is set
 *
 *       - if no such instruction remains, the method has successfully been verified.
 *       - otherwise, turn off the "changed" bit of the selected instruction.
 *
 *  2  model the effect of the instruction on the operand stack and local variable array by:
 *
 *       - if the instruction uses values from the operand stack, ensure that there are a
 *         sufficient number of values on the stack and that the top values on the stack are
 *         of an appropriate type.
 *       - if the instruction uses a local variable, ensure that the specified local variable
 *         contains a value of the appropriate type.
 *       - if the instruction pushes values onto the operand stack, ensure that there is sufficient
 *         room on the operand stack for the new values.  add the indicated types to the type of the
 *         modeled operand stack.
 *       - if the instruction modifies a local variable, record that the local variable now contains
 *         a type.
 *
 *  3  determine the instructions that can follow the current instruction.  successor instructions
 *     can be one of the following:
 *
 *       - the next instruction, if the current instruction is not an unconditional control tranfer
 *         instruction (ie - goto, return, or athrow).  basically check to make sure you don't
 *         "fall off" the last instruction of the method.
 *       - the target of a conditional or unconditional branch or switch.
 *       - any exception handlers for this instruction.
 *
 *  4  merge the state of the operand stack and local variable array at the end of the execution of the
 *     current instruction into each of the successor instructions.
 *
 *     (see merge function below)
 *
 *  5  continue at step 1.
 */
static
bool
verifyMethod3b(errorInfo* einfo, const Method* method,
	       const uint32* status,
	       BlockInfo** blocks, const uint32 numBlocks,
	       SigStack** sigs,
	       UninitializedType** uninits)
{
	const uint32 codelen      = METHOD_BYTECODE_LEN(method);
	const unsigned char* code = METHOD_BYTECODE_CODE(method);
	
	uint32 curIndex;
	BlockInfo* curBlock;
	BlockInfo* nextBlock;
	
#define VERIFY_ERROR(_MSG) \
        KFREE(curBlock); \
        if (einfo->type == 0) { \
        	postExceptionMessage(einfo, JAVA_LANG(VerifyError), \
				     "in method \"%s.%s\": %s", \
				     CLASS_CNAME(method->class), METHOD_NAMED(method), _MSG); \
	} \
	return(false)
	
	
	uint32 pc = 0, newpc = 0, n = 0;
	int32 high = 0, low = 0;  /* for the switching instructions */
	
	
	
	DBG(VERIFY3, dprintf("    Verifier Pass 3b: Data Flow Analysis and Type Checking...\n"); );
	DBG(VERIFY3, dprintf("        memory allocation...\n"); );
	curBlock = createBlock(method);
	
	
	DBG(VERIFY3, dprintf("        doing the dirty data flow analysis...\n"); );
	blocks[0]->status |= CHANGED;
	curIndex = 0;
	while(curIndex < numBlocks) {
		DBG(VERIFY3,
		    dprintf("      blockNum/first pc/changed/stksz = %d / %d / %d / %d\n",
			    curIndex,
			    blocks[curIndex]->startAddr,
			    blocks[curIndex]->status & CHANGED,
			    blocks[curIndex]->stacksz);
		    dprintf("          before:\n");
		    printBlock(method, blocks[curIndex], "                 ");
		    );
		
		if (!(blocks[curIndex]->status & CHANGED)) {
			DBG(VERIFY3, dprintf("        not changed...skipping\n"); );
			curIndex++;
			continue;
		}
		
		blocks[curIndex]->status ^= CHANGED; /* unset CHANGED bit */
		blocks[curIndex]->status |= VISITED; /* make sure we've visited it...important for merging */
		copyBlockData(method, blocks[curIndex], curBlock);
		
		if (curBlock->status & EXCEPTION_HANDLER && curBlock->stacksz > 0) {
			VERIFY_ERROR("it's possible to reach an exception handler with a nonempty stack");
		}
		
		
		if (!verifyBasicBlock(einfo, method, curBlock, sigs, uninits)) {
			VERIFY_ERROR("failure to verify basic block");
		}
		
		
		DBG(VERIFY3, dprintf("          after:\n"); printBlock(method, curBlock, "                 "); );
		
		
		/*
		 * merge this block's information into the next block
		 */
		pc = curBlock->lastAddr;
		if (code[pc] == WIDE && code[pc + insnLen[code[pc]]] == RET)
			pc += insnLen[code[pc]];
		switch(code[pc])
			{
			case GOTO:
				newpc = pc + 1;
				newpc = pc + WORD(code, newpc);
				nextBlock = inWhichBlock(newpc, blocks, numBlocks);
				
				if (!merge(einfo, method, curBlock, nextBlock)) {
					VERIFY_ERROR("error merging operand stacks");
				}
				break;
				
			case GOTO_W:
				newpc = pc + 1;
				newpc = pc + DWORD(code, newpc);
				nextBlock = inWhichBlock(newpc, blocks, numBlocks);
				
				if (!merge(einfo, method, curBlock, nextBlock)) {
					VERIFY_ERROR("error merging operand stacks");
				}
				break;
					
			case JSR:
				newpc = pc + 1;
				newpc = pc + WORD(code, newpc);
				goto JSR_common;
			case JSR_W:
				newpc = pc + 1;
				newpc = pc + DWORD(code, newpc);
			JSR_common:
				nextBlock = inWhichBlock(newpc, blocks, numBlocks);
				
				if (!merge(einfo, method, curBlock, nextBlock)) {
					VERIFY_ERROR("jsr: error merging operand stacks");
				}
	
				/*
				 * args, we need to verify the RET block first ...
				 */
				for (;curIndex<numBlocks && blocks[curIndex]!=nextBlock; curIndex++);
				assert (curIndex < numBlocks);
				continue;
				
			case RET:
				if (status[pc] & WIDE_MODDED) {
					n = pc + 1;
					n = WORD(code, n);
				} else {
					n = code[pc + 1];
				}
				
				if (!IS_ADDRESS(&curBlock->locals[n])) {
					VERIFY_ERROR("ret instruction does not refer to a variable with type returnA