/* src/vm/jit/verify/typecheck.c - typechecking (part of bytecode verification)
- Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
- C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
- E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
- J. Wenninger, Institut f. Computersprachen - TU Wien
+ Copyright (C) 1996-2005, 2006, 2007, 2008
+ CACAOVM - Verein zur Foerderung der freien virtuellen Maschine CACAO
This file is part of CACAO.
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.
- Contact: cacao@cacaojvm.org
-
- Authors: Edwin Steiner
-
- Changes: Christian Thalinger
-
- $Id: typecheck.c 5773 2006-10-13 14:34:19Z edwin $
-
*/
/*
citeseer.ist.psu.edu/article/coglio03improving.html
*/
+
#include "config.h"
-#include "vm/types.h"
-#include "vm/global.h"
#include <assert.h>
#include <string.h>
+#include "vm/types.h"
+
#ifdef ENABLE_VERIFIER
#include "mm/memory.h"
+
+#include "native/native.hpp"
+
#include "toolbox/logging.h"
-#include "native/native.h"
-#include "vm/builtin.h"
-#include "vm/jit/patcher.h"
-#include "vm/loader.h"
-#include "vm/options.h"
-#include "vm/jit/jit.h"
-#include "vm/jit/show.h"
+
#include "vm/access.h"
-#include "vm/resolve.h"
-#include "vm/exceptions.h"
+#include "vm/array.hpp"
+#include "vm/jit/builtin.hpp"
+#include "vm/exceptions.hpp"
+#include "vm/global.h"
+#include "vm/globals.hpp"
+#include "vm/loader.hpp"
+#include "vm/options.h"
+#include "vm/primitive.hpp"
+#include "vm/resolve.hpp"
+
+#include "vm/jit/jit.hpp"
+#include "vm/jit/parse.hpp"
+#include "vm/jit/show.hpp"
#include <typecheck-common.h>
#define TYPECHECK_ADR_OP(o) TYPECHECK_ADR((o).varindex)
-/****************************************************************************/
-/* TYPESTACK MACROS AND FUNCTIONS */
-/* */
-/* These macros and functions act on the 'type stack', which is a shorthand */
-/* for the types of the stackslots of the current stack. The type of a */
-/* stack slot is usually described by a TYPE_* constant and -- for TYPE_ADR */
-/* -- by the typeinfo of the slot. The only thing that makes the type stack */
-/* more complicated are returnAddresses of local subroutines, because a */
-/* single stack slot may contain a set of more than one possible return */
-/* address. This is handled by 'return address sets'. A return address set */
-/* is kept as a linked list dangling off the typeinfo of the stack slot. */
-/****************************************************************************/
-
-/* typecheck_copy_types ********************************************************
-
- Copy the types of the source variables to the destination variables.
-
- IN:
- state............current verifier state
- srcvars..........array of variable indices to copy
- dstvars..........array of the destination variables
- n................number of variables to copy
-
- RETURN VALUE:
- true.............success
- false............an exception has been thrown
-
-*******************************************************************************/
-
-static bool
-typecheck_copy_types(verifier_state *state, s4 *srcvars, s4 *dstvars, s4 n)
-{
- s4 i;
- varinfo *sv;
- varinfo *dv;
- jitdata *jd = state->jd;
-
- for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
- sv = VAR(*srcvars);
- dv = VAR(*dstvars);
-
- dv->type = sv->type;
- if (dv->type == TYPE_ADR) {
- TYPEINFO_CLONE(sv->typeinfo,dv->typeinfo);
- }
- }
- return true;
-}
-
-
-/* typecheck_merge_types *******************************************************
-
- Merge the types of the source variables into the destination variables.
-
- IN:
- state............current state of the verifier
- srcvars..........source variable indices
- dstvars..........destination variable indices
- n................number of variables
-
- RETURN VALUE:
- typecheck_TRUE...the destination variables have been modified
- typecheck_FALSE..the destination variables are unchanged
- typecheck_FAIL...an exception has been thrown
-
-*******************************************************************************/
-
-static typecheck_result
-typecheck_merge_types(verifier_state *state,s4 *srcvars, s4 *dstvars, s4 n)
-{
- s4 i;
- varinfo *sv;
- varinfo *dv;
- jitdata *jd = state->jd;
- typecheck_result r;
- bool changed = false;
-
- for (i=0; i < n; ++i, ++srcvars, ++dstvars) {
- sv = VAR(*srcvars);
- dv = VAR(*dstvars);
-
- if (dv->type != sv->type) {
- exceptions_throw_verifyerror(state->m,"Stack type mismatch");
- return typecheck_FAIL;
- }
- if (dv->type == TYPE_ADR) {
- if (TYPEINFO_IS_PRIMITIVE(dv->typeinfo)) {
- /* dv has returnAddress type */
- if (!TYPEINFO_IS_PRIMITIVE(sv->typeinfo)) {
- exceptions_throw_verifyerror(state->m,"Merging returnAddress with reference");
- return typecheck_FAIL;
- }
- }
- else {
- /* dv has reference type */
- if (TYPEINFO_IS_PRIMITIVE(sv->typeinfo)) {
- exceptions_throw_verifyerror(state->m,"Merging reference with returnAddress");
- return typecheck_FAIL;
- }
- r = typeinfo_merge(state->m,&(dv->typeinfo),&(sv->typeinfo));
- if (r == typecheck_FAIL)
- return r;
- changed |= r;
- }
- }
- }
- return changed;
-}
-
-
-/* typestate_merge *************************************************************
-
- Merge the types of one state into the destination state.
-
- IN:
- state............current state of the verifier
- dstvars..........indices of the destinations invars
- dstlocals........the destinations inlocals
- srcvars..........indices of the source's outvars
- srclocals........the source locals
- n................number of invars (== number of outvars)
-
- RETURN VALUE:
- typecheck_TRUE...destination state has been modified
- typecheck_FALSE..destination state has not been modified
- typecheck_FAIL...an exception has been thrown
-
-*******************************************************************************/
-
-static typecheck_result
-typestate_merge(verifier_state *state,
- s4 *srcvars, varinfo *srclocals,
- s4 *dstvars, varinfo *dstlocals,
- s4 n)
-{
- bool changed = false;
- typecheck_result r;
-
- /* The stack is always merged. If there are returnAddresses on
- * the stack they are ignored in this step. */
-
- r = typecheck_merge_types(state, srcvars, dstvars, n);
- if (r == typecheck_FAIL)
- return r;
- changed |= r;
-
- /* merge the locals */
-
- r = typevector_merge(state->m, dstlocals, srclocals, state->numlocals);
- if (r == typecheck_FAIL)
- return r;
- return changed | r;
-}
-
-
-/* typestate_reach *************************************************************
-
- Reach a destination block and propagate stack and local variable types
-
- IN:
- state............current state of the verifier
- destblock........destination basic block
- srcvars..........variable indices of the outvars to propagate
- srclocals........local variables to propagate
- n................number of srcvars
-
- OUT:
- state->repeat....set to true if the verifier must iterate again
- over the basic blocks
-
- RETURN VALUE:
- true.............success
- false............an exception has been thrown
-
-*******************************************************************************/
-
-static bool
-typestate_reach(verifier_state *state,
- basicblock *destblock,
- s4 *srcvars, varinfo *srclocals, s4 n)
-{
- varinfo *destloc;
- bool changed = false;
- typecheck_result r;
-
- LOG1("reaching block L%03d",destblock->nr);
- TYPECHECK_COUNT(stat_reached);
-
- destloc = destblock->inlocals;
-
- if (destblock->flags == BBTYPECHECK_UNDEF) {
- /* The destblock has never been reached before */
-
- TYPECHECK_COUNT(stat_copied);
- LOG1("block L%03d reached first time",destblock->nr);
-
- if (!typecheck_copy_types(state, srcvars, destblock->invars, n))
- return false;
- typevector_copy_inplace(srclocals, destloc, state->numlocals);
- changed = true;
- }
- else {
- /* The destblock has already been reached before */
-
- TYPECHECK_COUNT(stat_merged);
- LOG1("block L%03d reached before", destblock->nr);
-
- r = typestate_merge(state, srcvars, srclocals,
- destblock->invars, destblock->inlocals, n);
- if (r == typecheck_FAIL)
- return false;
- changed = r;
- TYPECHECK_COUNTIF(changed,stat_merging_changed);
- }
-
- if (changed) {
- LOG("changed!");
- destblock->flags = BBTYPECHECK_REACHED;
- if (destblock <= state->bptr) {
- LOG("REPEAT!");
- state->repeat = true;
- }
- }
- return true;
-}
-
-
/* typestate_save_invars *******************************************************
Save the invars of the current basic block in the space reserved by
}
-/****************************************************************************/
-/* MISC MACROS */
-/****************************************************************************/
-
-#define COPYTYPE(source,dest) \
- {if (VAROP(source)->type == TYPE_ADR) \
- TYPEINFO_COPY(VAROP(source)->typeinfo,VAROP(dest)->typeinfo);}
-
-
-/* verify_fieldaccess **********************************************************
+/* handle_fieldaccess **********************************************************
Verify an ICMD_{GET,PUT}{STATIC,FIELD}(CONST)?
*******************************************************************************/
static bool
-verify_fieldaccess(verifier_state *state,
+handle_fieldaccess(verifier_state *state,
varinfo *instance,
varinfo *value)
{
#define TYPECHECK_VARIABLESBASED
#define EXCEPTION do { return false; } while (0)
+#define VERIFY_ERROR(msg) TYPECHECK_VERIFYERROR_bool(msg)
#include <typecheck-fields.inc>
#undef EXCEPTION
+#undef VERIFY_ERROR
#undef TYPECHECK_VARIABLESBASED
return true;
}
-/* verify_invocation ***********************************************************
+/* handle_invocation ***********************************************************
Verify an ICMD_INVOKE* instruction.
*******************************************************************************/
static bool
-verify_invocation(verifier_state *state)
+handle_invocation(verifier_state *state)
{
jitdata *jd;
varinfo *dv; /* output variable of current instruction */
}
-/* verify_builtin **************************************************************
+/* handle_builtin **************************************************************
Verify the call of a builtin method.
*******************************************************************************/
static bool
-verify_builtin(verifier_state *state)
+handle_builtin(verifier_state *state)
{
jitdata *jd;
varinfo *dv; /* output variable of current instruction */
return true;
}
-/* verify_multianewarray *******************************************************
+/* handle_multianewarray *******************************************************
Verify a MULTIANEWARRAY instruction.
*******************************************************************************/
static bool
-verify_multianewarray(verifier_state *state)
+handle_multianewarray(verifier_state *state)
{
- classinfo *arrayclass;
- arraydescriptor *desc;
- s4 i;
- jitdata *jd = state->jd;
-
- /* check the array lengths on the stack */
- i = state->iptr->s1.argcount;
- if (i < 1)
- TYPECHECK_VERIFYERROR_bool("Illegal dimension argument");
-
- while (i--) {
- TYPECHECK_INT(state->iptr->sx.s23.s2.args[i]);
- }
-
- /* check array descriptor */
- if (INSTRUCTION_IS_RESOLVED(state->iptr)) {
- /* the array class reference has already been resolved */
- arrayclass = state->iptr->sx.s23.s3.c.cls;
- if (!arrayclass)
- TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with unlinked class");
- if ((desc = arrayclass->vftbl->arraydesc) == NULL)
- TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
- if (desc->dimension < state->iptr->s1.argcount)
- TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
-
- /* set the array type of the result */
- typeinfo_init_classinfo(&(VAROP(state->iptr->dst)->typeinfo), arrayclass);
- }
- else {
- const char *p;
- constant_classref *cr;
-
- /* the array class reference is still unresolved */
- /* check that the reference indicates an array class of correct dimension */
- cr = state->iptr->sx.s23.s3.c.ref;
- i = 0;
- p = cr->name->text;
- while (p[i] == '[')
- i++;
- /* { the dimension of the array class == i } */
- if (i < 1)
- TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY with non-array class");
- if (i < state->iptr->s1.argcount)
- TYPECHECK_VERIFYERROR_bool("MULTIANEWARRAY dimension to high");
-
- /* set the array type of the result */
- if (!typeinfo_init_class(&(VAROP(state->iptr->dst)->typeinfo),CLASSREF_OR_CLASSINFO(cr)))
- return false;
- }
+ jitdata *jd;
+ varinfo *dv; /* output variable of current instruction */
- /* set return type */
+ jd = state->jd;
+ dv = VAROP(state->iptr->dst);
- VAROP(state->iptr->dst)->type = TYPE_ADR;
+#define TYPECHECK_VARIABLESBASED
+#define VERIFY_ERROR(msg) TYPECHECK_VERIFYERROR_bool(msg)
+#include <typecheck-multianewarray.inc>
+#undef VERIFY_ERROR
+#undef TYPECHECK_VARIABLESBASED
- /* everything ok */
return true;
}
-
/* typecheck_invalidate_locals *************************************************
Invalidate locals that are overwritten by writing to the given local.
static void typecheck_invalidate_locals(verifier_state *state, s4 index, bool twoword)
{
- s4 i;
+ s4 javaindex;
s4 t;
- s4 mapped;
+ s4 varindex;
jitdata *jd = state->jd;
s4 *localmap = jd->local_map;
varinfo *vars = jd->var;
- i = state->reverselocalmap[index];
+ javaindex = jd->reverselocalmap[index];
- /* invalidate locals of two-word type at index i-1 */
+ /* invalidate locals of two-word type at index javaindex-1 */
- if (i > 0) {
- localmap += 5 * (i-1);
+ if (javaindex > 0) {
+ localmap += 5 * (javaindex-1);
for (t=0; t<5; ++t) {
- mapped = *localmap++;
- if (mapped >= 0 && IS_2_WORD_TYPE(vars[mapped].type)) {
- LOG1("invalidate local %d", mapped);
- vars[mapped].type = TYPE_VOID;
+ varindex = *localmap++;
+ if (varindex >= 0 && IS_2_WORD_TYPE(vars[varindex].type)) {
+ LOG1("invalidate local %d", varindex);
+ vars[varindex].type = TYPE_VOID;
}
}
}
else {
- localmap += 5 * i;
+ localmap += 5 * javaindex;
}
- /* invalidate locals at index i */
+ /* invalidate locals at index javaindex */
for (t=0; t<5; ++t) {
- mapped = *localmap++;
- if (mapped >= 0) {
- LOG1("invalidate local %d", mapped);
- vars[mapped].type = TYPE_VOID;
+ varindex = *localmap++;
+ if (varindex >= 0) {
+ LOG1("invalidate local %d", varindex);
+ vars[varindex].type = TYPE_VOID;
}
}
- /* if a two-word type is written, invalidate locals at index i+1 */
+ /* if a two-word type is written, invalidate locals at index javaindex+1 */
if (twoword) {
for (t=0; t<5; ++t) {
- mapped = *localmap++;
- if (mapped >= 0) {
- LOG1("invalidate local %d", mapped);
- vars[mapped].type = TYPE_VOID;
+ varindex = *localmap++;
+ if (varindex >= 0) {
+ LOG1("invalidate local %d", varindex);
+ vars[varindex].type = TYPE_VOID;
}
}
}
#define STORE_LOCAL(t, index) \
do { \
+ s4 temp_t = (t); \
typecheck_invalidate_locals(state, (index), false); \
- typevector_store(jd->var, (index), (t), NULL); \
+ typevector_store(jd->var, (index), (temp_t), NULL); \
} while (0)
#define STORE_LOCAL_2_WORD(t, index) \
do { \
+ s4 temp_t = (t); \
typecheck_invalidate_locals(state, (index), true); \
- typevector_store(jd->var, (index), (t), NULL); \
+ typevector_store(jd->var, (index), (temp_t), NULL); \
} while (0)
#define REACH_BLOCK(target) \
#define REACH(target) REACH_BLOCK((target).block)
-/* verify_basic_block **********************************************************
+/* handle_basic_block **********************************************************
Perform bytecode verification of a basic block.
*******************************************************************************/
static bool
-verify_basic_block(verifier_state *state)
+handle_basic_block(verifier_state *state)
{
int opcode; /* current opcode */
int len; /* for counting instructions, etc. */
branch_target_t *table;
lookup_target_t *lookup;
jitdata *jd = state->jd;
- exceptiontable *ex;
+ exception_entry *ex;
varinfo constvalue; /* for PUT*CONST */
constant_FMIref *fieldref;
LOGSTR1("\n---- BLOCK %04d ------------------------------------------------\n",state->bptr->nr);
LOGFLUSH;
- DOLOG(show_basicblock(jd, state->bptr, SHOW_STACK));
superblockend = false;
state->bptr->flags = BBFINISHED;
/* XXX could use a faster algorithm with sorted lists or */
/* something? */
len = 0;
- for (ex = state->cd->exceptiontable; ex ; ex = ex->down) {
+ for (ex = state->jd->exceptiontable; ex ; ex = ex->down) {
if ((ex->start->nr <= state->bptr->nr) && (ex->end->nr > state->bptr->nr)) {
LOG1("active handler L%03d", ex->handler->nr);
state->handlers[len++] = ex;
/* init variable types at the start of this block */
typevector_copy_inplace(state->bptr->inlocals, jd->var, state->numlocals);
+ DOLOG(show_basicblock(jd, state->bptr, SHOW_STACK));
DOLOG(typecheck_print_vararray(stdout, jd, state->bptr->invars,
state->bptr->indepth));
DOLOG(typevector_print(stdout, jd->var, state->numlocals));
}
-/* verify_init_locals **********************************************************
-
- Initialize the local variables in the verifier state.
-
- IN:
- state............the current state of the verifier
-
- RETURN VALUE:
- true.............success,
- false............an exception has been thrown.
-
-*******************************************************************************/
-
-static bool
-verify_init_locals(verifier_state *state)
-{
- int i;
- int index;
- varinfo *locals;
- varinfo *v;
- jitdata *jd = state->jd;
- int skip = 0;
-
- locals = state->basicblocks[0].inlocals;
-
- /* allocate parameter descriptors if necessary */
-
- if (!state->m->parseddesc->params)
- if (!descriptor_params_from_paramtypes(state->m->parseddesc,state->m->flags))
- return false;
-
- /* pre-initialize variables as TYPE_VOID */
-
- i = state->numlocals;
- v = locals;
- while (i--) {
- v->type = TYPE_VOID;
- v++;
- }
-
- /* if this is an instance method initialize the "this" ref type */
-
- if (!(state->m->flags & ACC_STATIC)) {
- index = jd->local_map[5*0 + TYPE_ADR];
- if (index != UNUSED) {
- if (state->validlocals < 1)
- TYPECHECK_VERIFYERROR_bool("Not enough local variables for method arguments");
- v = locals + index;
- v->type = TYPE_ADR;
- if (state->initmethod)
- TYPEINFO_INIT_NEWOBJECT(v->typeinfo, NULL);
- else
- typeinfo_init_classinfo(&(v->typeinfo), state->m->class);
- }
-
- skip = 1;
- }
-
- LOG("'this' argument set.\n");
-
- /* the rest of the arguments and the return type */
-
- if (!typeinfo_init_varinfos_from_methoddesc(locals, state->m->parseddesc,
- state->validlocals,
- skip, /* skip 'this' pointer */
- jd->local_map,
- &state->returntype))
- return false;
-
- LOG("Arguments set.\n");
- return true;
-}
-
-
/****************************************************************************/
/* typecheck() */
/* This is the main function of the bytecode verifier. It is called */
codegendata *cd;
varinfo *savedlocals;
verifier_state state; /* current state of the verifier */
- s4 i;
- s4 t;
/* collect statistics */
#ifdef TYPECHECK_STATISTICS
int count_iterations = 0;
TYPECHECK_COUNT(stat_typechecked);
- TYPECHECK_COUNT_FREQ(stat_locals,cdata->maxlocals,STAT_LOCALS);
+ TYPECHECK_COUNT_FREQ(stat_locals,jd->maxlocals,STAT_LOCALS);
TYPECHECK_COUNT_FREQ(stat_blocks,cdata->method->basicblockcount/10,STAT_BLOCKS);
TYPECHECK_COUNTIF(cdata->method->exceptiontablelength != 0,stat_methods_with_handlers);
state.stat_maythrow = false;
state.savedindices = NULL;
state.savedinvars = NULL;
+ /* check that the basicblock numbers are valid */
+
+#if !defined(NDEBUG)
+ jit_check_basicblock_numbers(jd);
+#endif
+
/* check if this method is an instance initializer method */
state.initmethod = (state.m->name == utf_init);
if (state.initmethod)
state.numlocals++; /* VERIFIER_EXTRA_LOCALS */
- state.reverselocalmap = DMNEW(s4, state.validlocals);
- for (i=0; i<jd->m->maxlocals; ++i)
- for (t=0; t<5; ++t) {
- s4 mapped = jd->local_map[5*i + t];
- if (mapped >= 0)
- state.reverselocalmap[mapped] = i;
- }
-
DOLOG(
+ s4 i;
+ s4 t;
LOG("reverselocalmap:");
for (i=0; i<state.validlocals; ++i) {
- LOG2(" %i => javaindex %i", i, state.reverselocalmap[i]);
+ LOG2(" %i => javaindex %i", i, jd->reverselocalmap[i]);
});
/* allocate the buffer of active exception handlers */
- state.handlers = DMNEW(exceptiontable*, state.cd->exceptiontablelength + 1);
+ state.handlers = DMNEW(exception_entry*, state.jd->exceptiontablelength + 1);
/* save local variables */
/* initialized local variables of first block */
- if (!verify_init_locals(&state))
+ if (!typecheck_init_locals(&state, true))
return false;
/* initialize invars of exception handlers */
/* verify reached block */
if (state.bptr->flags == BBTYPECHECK_REACHED) {
- if (!verify_basic_block(&state))
+ if (!handle_basic_block(&state))
return false;
}
} /* for blocks */