Typechecker. More...

Macros
#define	TYPECHECK_CHECK_TYPE(i, tp, msg)

#define	TYPECHECK_INT(i) TYPECHECK_CHECK_TYPE(i,TYPE_INT,"Expected to find integer value")

#define	TYPECHECK_LNG(i) TYPECHECK_CHECK_TYPE(i,TYPE_LNG,"Expected to find long value")

#define	TYPECHECK_FLT(i) TYPECHECK_CHECK_TYPE(i,TYPE_FLT,"Expected to find float value")

#define	TYPECHECK_DBL(i) TYPECHECK_CHECK_TYPE(i,TYPE_DBL,"Expected to find double value")

#define	TYPECHECK_ADR(i) TYPECHECK_CHECK_TYPE(i,TYPE_ADR,"Expected to find object value")

#define	TYPECHECK_INT_OP(o) TYPECHECK_INT((o).varindex)

#define	TYPECHECK_LNG_OP(o) TYPECHECK_LNG((o).varindex)

#define	TYPECHECK_FLT_OP(o) TYPECHECK_FLT((o).varindex)

#define	TYPECHECK_DBL_OP(o) TYPECHECK_DBL((o).varindex)

#define	TYPECHECK_ADR_OP(o) TYPECHECK_ADR((o).varindex)

#define	TYPECHECK_VARIABLESBASED

#define	EXCEPTION do { return false; } while (0)

#define	VERIFY_ERROR(msg) TYPECHECK_VERIFYERROR_bool(msg)

#define	TYPECHECK_VARIABLESBASED

#define	OP1 VAR(state->iptr->sx.s23.s2.args[0])

#define	TYPECHECK_VARIABLESBASED

#define	OP1 state->iptr->sx.s23.s2.args[0]

#define	TYPECHECK_VARIABLESBASED

#define	VERIFY_ERROR(msg) TYPECHECK_VERIFYERROR_bool(msg)

#define	EXCEPTION do { return false; } while (0)

#define	VERIFY_ERROR(msg) TYPECHECK_VERIFYERROR_bool(msg)

#define	CHECK_LOCAL_TYPE(index, t)

#define	STORE_LOCAL(t, index)

#define	STORE_LOCAL_2_WORD(t, index)

#define	REACH_BLOCK(target)

#define	REACH(target) REACH_BLOCK((target).block)

#define	TYPECHECK_VARIABLESBASED

#define	STATE state

#define	METHOD (state->m)

#define	IPTR iptr

#define	BPTR (state->bptr)

#define	MAXPARAMS 255

Functions
static void	typestate_save_invars (verifier_state *state)

static void	typestate_restore_invars (verifier_state *state)

static bool	handle_fieldaccess (verifier_state state, varinfo instance, varinfo *value)

static bool	handle_invocation (verifier_state *state)

static bool	handle_builtin (verifier_state *state)

static bool	handle_multianewarray (verifier_state *state)

static void	typecheck_invalidate_locals (verifier_state *state, s4 index, bool twoword)

static bool	handle_basic_block (verifier_state *state)

bool	typecheck (jitdata *jd)

Detailed Description

Typechecker.

What's the purpose of the `typechecker`?

The typechecker analyses (the intermediate repr. of) the bytecode of each method and ensures that for each instruction the values on the stack and in local variables are of the correct type whenever the instruction is executed.

type checking is a mandatory part of bytecode verification.

How does the typechecker work?

The JVM stack and the local variables are not statically typed, so the typechecker has to infer the static types of stack slots and local variables at each point of the method. The JVM spec imposes a lot of restrictions on the bytecode in order to guarantee that this is always possible.

Basically the typechecker solves the data flow equations of the method. This is done in the usual way for a forward data flow analysis: Starting from the entry point of the method the typechecker follows the CFG and records the type of each stack slot and local variable at each point ¹. When two or more control flow paths merge at a point, the union of the types for each slot/variable is taken. The algorithm continues to follow all possible paths ² until the recorded types do not change anymore (ie. the equations have been solved).

If the solution has been reached and the resulting types are valid for all instructions, then type checking terminates with success, otherwise an exception is thrown.

Why is this code so damn complicated?

Short answer: The devil's in the details.

While the basic operation of the typechecker is no big deal, there are many properties of Java bytecode which make type checking hard. Some of them are not even addressed in the JVM spec. Some problems and their solutions:

Finding a good representation of the union of two reference types is difficult because of multiple inheritance of interfaces.

Solution: The typeinfo system can represent such "merged" types by a
list of proper subclasses of a class. Example:

    typeclass=java.lang.Object merged={ InterfaceA, InterfaceB }

represents the result of merging two interface types "InterfaceA"
and "InterfaceB".

When the code of a method is verified, there may still be unresolved references to classes/methods/fields in the code, which we may not force to be resolved eagerly. (A similar problem arises because of the special checks for protected members.)³

Solution: The typeinfo system knows how to deal with unresolved
class references. Whenever a check has to be performed for an
unresolved type, the type is annotated with constraints representing
the check. Later, when the type is resolved, the constraints are
checked. (See the constrain_unresolved_... and the resolve_...
methods.)

Checks for uninitialized object instances are hard because after the invocation of <init> on an uninitialized object all slots/variables referring to this object (and exactly those slots/variables) must be marked as initialized.
```
Solution: The JVM spec describes a solution, which has been
implemented in this typechecker.
```

Note that some checks mentioned in the JVM spec are unnecessary ⁴ and not performed by either the reference implementation, or this implementation.

— Footnotes

¹ Actually only the types of slots/variables at the start of each basic block are remembered. Within a basic block the algorithm only keeps the types of the slots/variables for the "current" instruction which is being analysed.

² Actually the algorithm iterates through the basic block list until there are no more changes. Theoretically it would be wise to sort the basic blocks topologically beforehand, but the number of average/max iterations observed is so low, that this was not deemed necessary.

³ This is similar to a method proposed by: Alessandro Coglio et al., "A Formal Specification of Java Class Loading" [7]. An important difference is that Coglio's subtype constraints are checked after loading, while our constraints are checked when the field/method is accessed for the first time, so we can guarantee lexically correct error reporting.

⁴ Alessandro Coglio "Improving the official specification of Java bytecode verification" [3].

Definition in file typecheck.cpp.

Macro Definition Documentation

#define BPTR (state->bptr)

#define CHECK_LOCAL_TYPE	(	index,
		t
	)

Value:

do {                                                             \
        if (!typevector_checktype(jd->var, (index), (t)))            \
             VERIFY_ERROR("Local variable type mismatch");           \
    } while (0)

Definition at line 478 of file typecheck.cpp.

#define EXCEPTION do { return false; } while (0)

Definition at line 475 of file typecheck.cpp.

#define EXCEPTION do { return false; } while (0)

Definition at line 475 of file typecheck.cpp.

#define IPTR iptr

#define MAXPARAMS 255

Definition at line 682 of file typecheck.cpp.

#define METHOD (state->m)

#define OP1 VAR(state->iptr->sx.s23.s2.args[0])

#define OP1 state->iptr->sx.s23.s2.args[0]

#define REACH ( target ) REACH_BLOCK((target).block)

Definition at line 506 of file typecheck.cpp.

#define REACH_BLOCK ( target )

Value:

do {                                                             \
        if (!typestate_reach(state, (target),                        \
                             state->bptr->outvars, jd->var,          \
                             state->bptr->outdepth))                 \
                return false;                                        \
    } while (0)

Definition at line 498 of file typecheck.cpp.

#define STATE state

#define STORE_LOCAL	(	t,
		index
	)

Value:

do {                                                             \
         Type temp_t = (t);                                          \
         typecheck_invalidate_locals(state, (index), false);         \
         typevector_store(jd->var, (index), (temp_t), NULL);         \
    } while (0)

Definition at line 484 of file typecheck.cpp.

#define STORE_LOCAL_2_WORD	(	t,
		index
	)

Value:

do {                                                             \
         Type temp_t = (t);                                          \
         typecheck_invalidate_locals(state, (index), true);          \
         typevector_store(jd->var, (index), (temp_t), NULL);         \
    } while (0)

Definition at line 491 of file typecheck.cpp.

#define TYPECHECK_ADR ( i ) TYPECHECK_CHECK_TYPE(i,TYPE_ADR,"Expected to find object value")

Definition at line 196 of file typecheck.cpp.

#define TYPECHECK_ADR_OP ( o ) TYPECHECK_ADR((o).varindex)

Definition at line 203 of file typecheck.cpp.

#define TYPECHECK_CHECK_TYPE	(	i,
		tp,
		msg
	)

Value:

do {                                                             \
        if (VAR(i)->type != (tp)) {                                  \
            exceptions_throw_verifyerror(state->m, (msg));           \
            return false;                                            \
        }                                                            \
    } while (0)

Definition at line 180 of file typecheck.cpp.

#define TYPECHECK_DBL ( i ) TYPECHECK_CHECK_TYPE(i,TYPE_DBL,"Expected to find double value")

Definition at line 194 of file typecheck.cpp.

#define TYPECHECK_DBL_OP ( o ) TYPECHECK_DBL((o).varindex)

Definition at line 202 of file typecheck.cpp.

#define TYPECHECK_FLT ( i ) TYPECHECK_CHECK_TYPE(i,TYPE_FLT,"Expected to find float value")

Definition at line 192 of file typecheck.cpp.

#define TYPECHECK_FLT_OP ( o ) TYPECHECK_FLT((o).varindex)

Definition at line 201 of file typecheck.cpp.

#define TYPECHECK_INT ( i ) TYPECHECK_CHECK_TYPE(i,TYPE_INT,"Expected to find integer value")

Definition at line 188 of file typecheck.cpp.

#define TYPECHECK_INT_OP ( o ) TYPECHECK_INT((o).varindex)

Definition at line 199 of file typecheck.cpp.

#define TYPECHECK_LNG ( i ) TYPECHECK_CHECK_TYPE(i,TYPE_LNG,"Expected to find long value")

Definition at line 190 of file typecheck.cpp.

#define TYPECHECK_LNG_OP ( o ) TYPECHECK_LNG((o).varindex)

Definition at line 200 of file typecheck.cpp.

#define TYPECHECK_VARIABLESBASED

#define VERIFY_ERROR ( msg ) TYPECHECK_VERIFYERROR_bool(msg)

Definition at line 476 of file typecheck.cpp.

#define VERIFY_ERROR ( msg ) TYPECHECK_VERIFYERROR_bool(msg)

Definition at line 476 of file typecheck.cpp.

#define VERIFY_ERROR ( msg ) TYPECHECK_VERIFYERROR_bool(msg)

Definition at line 476 of file typecheck.cpp.

Function Documentation

static bool handle_basic_block ( verifier_state * state )

static

Definition at line 523 of file typecheck.cpp.

static bool handle_builtin ( verifier_state * state )

static

Definition at line 363 of file typecheck.cpp.

static bool handle_fieldaccess	(	verifier_state *	state,
		varinfo *	instance,
		varinfo *	value
	)

static

Definition at line 297 of file typecheck.cpp.

static bool handle_invocation ( verifier_state * state )

static

Definition at line 331 of file typecheck.cpp.

static bool handle_multianewarray ( verifier_state * state )

static

Definition at line 394 of file typecheck.cpp.

bool typecheck ( jitdata * jd )

Definition at line 684 of file typecheck.cpp.

static void typecheck_invalidate_locals	(	verifier_state *	state,
		s4	index,
		bool	twoword
	)

static

Definition at line 422 of file typecheck.cpp.

static void typestate_restore_invars ( verifier_state * state )

static

Definition at line 263 of file typecheck.cpp.

static void typestate_save_invars ( verifier_state * state )

static

Definition at line 223 of file typecheck.cpp.

Macros

Functions

Detailed Description

What's the purpose of the typechecker?

How does the typechecker work?

Why is this code so damn complicated?

Macro Definition Documentation

Function Documentation

What's the purpose of the `typechecker`?