verify.c

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

/*
 * verify.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.
 *
 *
 * Perform stages 3 of class verification.
 * Stage 1 is performed when the class is being loaded (so isn't here).
 * Stage 2 is performed in verify2.
 * stage 4 is performed as the method is being executed.
 *
 * verify3() was also originally created by someone in Transvirtual, but it only
 * returned true :)  Questions regarding this one can be sent to Rob as well.
 *
 * All other code in this file was added to assist the full versions of verify2() and
 * verify3().
 */

#include "config.h"
#include "config-std.h"

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

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

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

/*********************************************************************************
 * Type Descriptor Parsing Methods
 *********************************************************************************/
/*
 * Returns whether the given class is "trusted" (i.e. does not require verification).
 */
bool
isTrustedClass(Hjava_lang_Class* class) {
        /* recall (from main.c): -verifyremote (default) ==> verifyMode = 2
	 *                       -verify                 ==> verifyMode = 3
	 *                       -noverify               ==> verifyMode = 0
	 */
	return ((class->loader == 0 && (Kaffe_JavaVMArgs.verifyMode & 1) == 0) ||
		(class->loader != 0 && (Kaffe_JavaVMArgs.verifyMode & 2) == 0));
}

/*
 * parses a BaseType descriptor (p.100 JVML Spec 2)
 * 
 *   BaseType: B | C | D | F | I | J | S | Z
 *
 * returns the sig pointing right after the BaseType
 * or NULL if an error occurred.
 */
const char*
parseBaseTypeDescriptor(const char* sig)
{
	switch(*sig) {
	case 'B': case 'C': case 'D': case 'F': case 'I': case 'J': case 'S': case 'Z':
		return sig + 1;
	default:
		break;
	}
	
	return NULL;
}

/*
 * parses an ObjectType descriptor (p.101 JVML Spec 2)
 *
 *   ObjectType: L<classname>;
 *   <classname> is a string made from unicode characters
 *
 * precondition: *sig == 'L'
 *
 * returns the sig pointing right after the ObjectType
 * or NULL if an error occurred.
 */
const char*
parseObjectTypeDescriptor(const char* sig)
{
	for (sig++; sig != '\0' && *sig != ';'; sig++);
	
	if (sig == '\0') return NULL;
	else             return sig + 1;
}

/* parses an ArrayType descriptor (p.101 JVML Spec 2)
 *
 *   ArrayType    : [ComponentType
 *   ComponentType: FieldType
 *
 * precondition: *sig == '['
 *
 * returns the sig pointing right after the ArrayType
 * or NULL if an error occurred.
 */
const char*
parseArrayTypeDescriptor(const char* sig)
{
	while (*sig != '\0' && *sig == '[') sig++;
	
	if (*sig == '\0') return NULL;
	else              return parseFieldTypeDescriptor(sig);
}


/*
 * parses a field type descriptor (i.e. its type signature).
 *
 *   FieldType:
 *     BaseType | ObjectType | ArrayType
 *
 * returns the signatures position immediately after the field's
 * type signature, or NULL if any error has occurred.
 */
const char*
parseFieldTypeDescriptor(const char* sig)
{
	if (sig == NULL)      return NULL;
	else if (*sig == '[') return parseArrayTypeDescriptor(sig);
	else if (*sig == 'L') return parseObjectTypeDescriptor(sig);
	else                  return parseBaseTypeDescriptor(sig);
}


/*
 * parses a method type descriptor (i.e. its signature).  (p.103 JVML Spec 2)
 *
 *   MethodDescriptor:
 *     ( ParameterDescriptor* ) ReturnDescriptor
 *   ParameterDescriptor:
 *     FieldType
 *   ReturnDescriptor:
 *     FieldType | V
 *
 * returns whether the descriptor is legal
 */
bool
parseMethodTypeDescriptor(const char* sig)
{
	if (sig == NULL || *sig != '(') return false;
	
	DBG(VERIFY2, dprintf("        parsing method type descriptor: %s\n", sig); );
	
	/* parse the type parameters */
	for (sig++; sig && *sig != ')' && *sig != '\0'; sig = parseFieldTypeDescriptor(sig)) {
		DBG(VERIFY2, dprintf("            parameter sig: %s\n", sig); );
	}
	
	if (sig == NULL || *sig == '\0') {
		DBG(VERIFY2, dprintf("            error: no ReturnDescriptor\n"); );
		return false;
	}
	sig++;
	
	DBG(VERIFY2, dprintf("            ReturnDescriptor: %s\n", sig); );	
	if (*sig == 'V') {
		sig++;
		return *sig == '\0';
	}
	
	if (parseFieldTypeDescriptor(sig) != NULL) return true;
	
	return false;
}

/************************************************************************************
 * Pass 3 Verification
 *
 * Pass 3 of verification is broken up into two distinct passes.  The first, 3a,
 * checks static constraints of the bytecode (detailed on p. 134 of the JVML Spec 2).
 * The second, 3b, performs data-flow analysis on the bytecode, which checks structural
 * constraints and does type checking.
 *
 * NOTE: according to p.171 of JVML Spec 2, "Performing verification at link time
 *       is attractive in that the checks are performed just once, substantially
 *       reducing the amount of work that must be done at run time.  Other
 *       implementation strategies are possible, provided that they comply with
 *       The Java Language Specification and The Java Virtual Machine Specification."
 *
 *       In other words, we can perform pass 3 verification whenever convenient, and
 *       not necessarily at link time.  This could provide for optimizations in the
 *       future, as verification generates a lot of information that is useful to
 *       the JIT compilers.  At the moment, this same information is generated by
 *       code-analyze.c again later on.
 ************************************************************************************/

/* lengths in bytes of all the instructions */
/* 16 rows of 16 */
const uint8 insnLen[256] = {
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 0-15 */
	2, 3, 2, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1,  /* 16-31 */
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 32-47 */
	1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1,  /* 48-63 */
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 64-79 */
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 80-95 */
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 96-111 */
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 112-127 */
	1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 128-143 */
	1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 3, 3, 3, 3,  /* 144-159 */
	3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 0, 0, 1, 1, 1, 1,  /* 160-175 */
	1, 1, 3, 3, 3, 3, 3, 3, 3, 5, 1, 3, 2, 3, 1, 1,  /* 176-191 */
	3, 3, 1, 1, 1, 4, 3, 3, 5, 5, 1, 1, 1, 1, 1, 1,  /* 192-208 */
	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, 
};


/***********************************************************************************
 * Methods for Pass 3 Verification
 ***********************************************************************************/
static bool               verifyMethod(errorInfo* einfo,
				       Method* method);
static bool               loadInitialArgs(Verifier* v);


/* for verifying method calls */
static uint32             countSizeOfArgsInSignature(const char* sig);
static const char*        getNextArg(const char* sig,
				     char* buf);

/*
 * 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)) {
		return true;
	}
	
	
	/* 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, {
		/* print out the superclass hirearchy */
		Hjava_lang_Class* tmp;
		for (tmp = class->superclass; tmp; tmp = tmp->superclass) {
			dprintf("                       C|-> %s\n", CLASS_CNAME(tmp));
		}
	});
	DBG(VERIFY3, {
		/* print out the complete list of implemented interfaces */
		int i;
		for (i = class->total_interface_len - 1; i >=0; i--) {
			dprintf("                       I|-> %s\n", CLASS_CNAME(class->interfaces[i]));
		}
	});
	
	
	for (n = CLASS_NMETHODS(class), method = CLASS_METHODS(class);
	     n > 0;
	     --n, ++method) {
		
		DBG(VERIFY3, dprintf("\n  -----------------------------------\n  considering method %s.%s%s\n",
				     CLASS_CNAME(class),
				     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;
}

	
/**************************************************************************************************
 * Memory Management Macros
 **************************************************************************************************/
/* to make sure we don't forget to unalloc anything...
 * should be called during ANY EXIT FROM verifyMethod
 *
 * NOTE: we don't free the Verifier object itself, just
 * its data.
 */
void
freeVerifierData(Verifier* v)
{
	DBG(VERIFY3, dprintf("    cleaning up..."); );
	gc_free(v->status);
	if (v->blocks != NULL) {
		while (v->numBlocks > 0) {
			freeBlock(v->blocks[--v->numBlocks]);
		}
		gc_free(v->blocks);
	}
        freeSigStack(v->sigs);
        freeUninits(v->uninits);
	freeSupertypes(v->supertypes);
        DBG(VERIFY3, dprintf(" done\n"); );
}

static inline
bool
failInVerifyMethod(Verifier* v)
{
        DBG(VERIFY3, dprintf("    Verify Method 3b: %s.%s%s: FAILED\n",
			     CLASS_CNAME(v->method->class), METHOD_NAMED(v->method), METHOD_SIGD(v->method)); );
	if (v->einfo->type == 0) {
		DBG(VERIFY3, dprintf("      DBG ERROR: should have raised an exception\n"); );
		postException(v->einfo, JAVA_LANG(VerifyError));
	}
        freeVerifierData(v);
        return(false);
}

/*
 * 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);
	
	Verifier v;
	v.einfo = einfo;
	v.class = method->class;
	v.method = method;
	v.numBlocks = 0;
	v.status = NULL;
	v.blocks = NULL;
	v.sigs = NULL;
	v.uninits = NULL;
	v.supertypes = NULL;
	v.uninits = NULL;
	
	
	/**************************************************************************************************
	 * Memory Allocation
	 **************************************************************************************************/
	DBG(VERIFY3, dprintf("        allocating memory for verification (codelen = %d)...\n", codelen); );
	
        v.status = checkPtr((uint32*)gc_malloc(codelen * sizeof(uint32), KGC_ALLOC_VERIFIER));
	
	/* find basic blocks and allocate memory for them */
	verifyMethod3a(&v);
	if (!v.blocks) {
		DBG(VERIFY3, dprintf("        some kinda error finding the basic blocks in pass 3a\n"); );
		
		/* propagate error */
		return failInVerifyMethod(&v);
	}
	
	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(&v)) {
	        /* propagate error */
		return failInVerifyMethod(&v);
	}
	DBG(VERIFY3, {
	        /* print out the local arguments */
		int n;
		for(n = 0; n < v.method->localsz; n++) {
			dprintf("        local %d: ", n);
			printType(&(v.blocks[0]->locals[n]));
			dprintf("\n");
		}
	} );
	
	
	if (!verifyMethod3b(&v)) {
		return failInVerifyMethod(&v);
	}
	
	freeVerifierData(&v);
	DBG(VERIFY3, dprintf("    Verify Method 3b: done\n"); );
	return(true);
}


/* 
 * parses the next argument from sig into buf, returning pointer beyond arg.
 */
static
const char*
getNextArg(const char* sig, char* buf)
{
	const char* afterSig;
	
	if (*sig == ')') {
		buf[0] = ')';
		buf[1] = '\0';
		return sig;
	}
	/* parseFieldTypeDescriptor doesn't deal with void signatures */
	else if (*sig == 'V') {
		buf[0] = 'V';
		buf[1] = '\0';
		sig++;
		return sig;
	}
	
	for (afterSig = parseFieldTypeDescriptor(sig);
	     sig < afterSig;
	     sig++, buf++) {
		*buf = *sig;
	}