/*

 * Copyright 1994-2007 Sun Microsystems, Inc.  All Rights Reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Sun designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Sun in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 */

/*-

 *      Verify that the code within a method block doesn't exploit any

 *      security holes.

 */

/*

   Exported function:

   jboolean

   VerifyClass(JNIEnv *env, jclass cb, char *message_buffer,

               jint buffer_length)

   jboolean

   VerifyClassForMajorVersion(JNIEnv *env, jclass cb, char *message_buffer,

                              jint buffer_length, jint major_version)

   This file now only uses the standard JNI and the following VM functions

   exported in jvm.h:

   JVM_FindClassFromClass

   JVM_IsInterface

   JVM_GetClassNameUTF

   JVM_GetClassCPEntriesCount

   JVM_GetClassCPTypes

   JVM_GetClassFieldsCount

   JVM_GetClassMethodsCount

   JVM_GetFieldIxModifiers

   JVM_GetMethodIxModifiers

   JVM_GetMethodIxExceptionTableLength

   JVM_GetMethodIxLocalsCount

   JVM_GetMethodIxArgsSize

   JVM_GetMethodIxMaxStack

   JVM_GetMethodIxNameUTF

   JVM_GetMethodIxSignatureUTF

   JVM_GetMethodIxExceptionsCount

   JVM_GetMethodIxExceptionIndexes

   JVM_GetMethodIxByteCodeLength

   JVM_GetMethodIxByteCode

   JVM_GetMethodIxExceptionTableEntry

   JVM_IsConstructorIx

   JVM_GetCPClassNameUTF

   JVM_GetCPFieldNameUTF

   JVM_GetCPMethodNameUTF

   JVM_GetCPFieldSignatureUTF

   JVM_GetCPMethodSignatureUTF

   JVM_GetCPFieldClassNameUTF

   JVM_GetCPMethodClassNameUTF

   JVM_GetCPFieldModifiers

   JVM_GetCPMethodModifiers

   JVM_ReleaseUTF

   JVM_IsSameClassPackage

 */

#include <string.h>

#include <setjmp.h>

#include <assert.h>

#include <limits.h>

#include <stdlib.h>

#include "jni.h"

#include "jvm.h"

#include "typedefs.h"

#include "opcodes.h"

#include "opcodes.length"

#include "opcodes.in_out"

#define MAX_ARRAY_DIMENSIONS 255

/* align byte code */

#ifndef ALIGN_UP

#define ALIGN_UP(n,align_grain) (((n) + ((align_grain) - 1)) & ~((align_grain)-1))

#endif /* ALIGN_UP */

#define UCALIGN(n) ((unsigned char *)ALIGN_UP((uintptr_t)(n),sizeof(int)))

#ifdef DEBUG

int verify_verbose = 0;

static struct context_type *GlobalContext;

#endif

enum {

    ITEM_Bogus,

    ITEM_Void,                  /* only as a function return value */

    ITEM_Integer,

    ITEM_Float,

    ITEM_Double,

    ITEM_Double_2,              /* 2nd word of double in register */

    ITEM_Long,

    ITEM_Long_2,                /* 2nd word of long in register */

    ITEM_Array,

    ITEM_Object,                /* Extra info field gives name. */

    ITEM_NewObject,             /* Like object, but uninitialized. */

    ITEM_InitObject,            /* "this" is init method, before call

                                    to super() */

    ITEM_ReturnAddress,         /* Extra info gives instr # of start pc */

    /* The following three are only used within array types.

     * Normally, we use ITEM_Integer, instead. */

    ITEM_Byte,

    ITEM_Short,

    ITEM_Char

};

#define UNKNOWN_STACK_SIZE -1

#define UNKNOWN_REGISTER_COUNT -1

#define UNKNOWN_RET_INSTRUCTION -1

#undef MAX

#undef MIN

#define MAX(a, b) ((a) > (b) ? (a) : (b))

#define MIN(a, b) ((a) < (b) ? (a) : (b))

#define BITS_PER_INT   (CHAR_BIT * sizeof(int)/sizeof(char))

#define SET_BIT(flags, i)  (flags[(i)/BITS_PER_INT] |= \

                                       ((unsigned)1 << ((i) % BITS_PER_INT)))

#define IS_BIT_SET(flags, i) (flags[(i)/BITS_PER_INT] & \

                                       ((unsigned)1 << ((i) % BITS_PER_INT)))

typedef unsigned int fullinfo_type;

typedef unsigned int *bitvector;

#define GET_ITEM_TYPE(thing) ((thing) & 0x1F)

#define GET_INDIRECTION(thing) (((thing) & 0xFFFF) >> 5)

#define GET_EXTRA_INFO(thing) ((thing) >> 16)

#define WITH_ZERO_INDIRECTION(thing) ((thing) & ~(0xFFE0))

#define WITH_ZERO_EXTRA_INFO(thing) ((thing) & 0xFFFF)

#define MAKE_FULLINFO(type, indirect, extra) \

     ((type) + ((indirect) << 5) + ((extra) << 16))

#define MAKE_Object_ARRAY(indirect) \

       (context->object_info + ((indirect) << 5))

#define NULL_FULLINFO MAKE_FULLINFO(ITEM_Object, 0, 0)

/* opc_invokespecial calls to <init> need to be treated special */

#define opc_invokeinit 0x100

/* A hash mechanism used by the verifier.

 * Maps class names to unique 16 bit integers.

 */

#define HASH_TABLE_SIZE 503

/* The buckets are managed as a 256 by 256 matrix. We allocate an entire

 * row (256 buckets) at a time to minimize fragmentation. Rows are

 * allocated on demand so that we don't waste too much space.

 */

#define MAX_HASH_ENTRIES 65536

#define HASH_ROW_SIZE 256

typedef struct hash_bucket_type {

    char *name;

    unsigned int hash;

    jclass class;

    unsigned short ID;

    unsigned short next;

    unsigned loadable:1;  /* from context->class loader */

} hash_bucket_type;

typedef struct {

    hash_bucket_type **buckets;

    unsigned short *table;

    int entries_used;

} hash_table_type;

#define GET_BUCKET(class_hash, ID)\

    (class_hash->buckets[ID / HASH_ROW_SIZE] + ID % HASH_ROW_SIZE)

/*

 * There are currently two types of resources that we need to keep

 * track of (in addition to the CCalloc pool).

 */

enum {

    VM_STRING_UTF, /* VM-allocated UTF strings */

    VM_MALLOC_BLK  /* malloc'ed blocks */

};

#define LDC_CLASS_MAJOR_VERSION 49

#define ALLOC_STACK_SIZE 16 /* big enough */

typedef struct alloc_stack_type {

    void *ptr;

    int kind;

    struct alloc_stack_type *next;

} alloc_stack_type;

/* The context type encapsulates the current invocation of the byte

 * code verifier.

 */

struct context_type {

    JNIEnv *env;                /* current JNIEnv */

    /* buffers etc. */

    char *message;

    jint message_buf_len;

    jboolean err_code;

    alloc_stack_type *allocated_memory; /* all memory blocks that we have not

                                           had a chance to free */

    /* Store up to ALLOC_STACK_SIZE number of handles to allocated memory

       blocks here, to save mallocs. */

    alloc_stack_type alloc_stack[ALLOC_STACK_SIZE];

    int alloc_stack_top;

    /* these fields are per class */

    jclass class;               /* current class */

    jint major_version;

    jint nconstants;

    unsigned char *constant_types;

    hash_table_type class_hash;

    fullinfo_type object_info;  /* fullinfo for java/lang/Object */

    fullinfo_type string_info;  /* fullinfo for java/lang/String */

    fullinfo_type throwable_info; /* fullinfo for java/lang/Throwable */

    fullinfo_type cloneable_info; /* fullinfo for java/lang/Cloneable */

    fullinfo_type serializable_info; /* fullinfo for java/io/Serializable */

    fullinfo_type currentclass_info; /* fullinfo for context->class */

    fullinfo_type superclass_info;   /* fullinfo for superclass */

    /* these fields are per method */

    int method_index;   /* current method */

    unsigned short *exceptions; /* exceptions */

    unsigned char *code;        /* current code object */

    jint code_length;

    int *code_data;             /* offset to instruction number */

    struct instruction_data_type *instruction_data; /* info about each */

    struct handler_info_type *handler_info;

    fullinfo_type *superclasses; /* null terminated superclasses */

    int instruction_count;      /* number of instructions */

    fullinfo_type return_type;  /* function return type */

    fullinfo_type swap_table[4]; /* used for passing information */

    int bitmask_size;           /* words needed to hold bitmap of arguments */

    /* these fields are per field */

    int field_index;

    /* Used by the space allocator */

    struct CCpool *CCroot, *CCcurrent;

    char *CCfree_ptr;

    int CCfree_size;

    /* Jump here on any error. */

    jmp_buf jump_buffer;

#ifdef DEBUG

    /* keep track of how many global refs are allocated. */

    int n_globalrefs;

#endif

};

struct stack_info_type {

    struct stack_item_type *stack;

    int stack_size;

};

struct register_info_type {

    int register_count;         /* number of registers used */

    fullinfo_type *registers;

    int mask_count;             /* number of masks in the following */

    struct mask_type *masks;

};

struct mask_type {

    int entry;

    int *modifies;

};

typedef unsigned short flag_type;

struct instruction_data_type {

    opcode_type opcode;         /* may turn into "canonical" opcode */

    unsigned changed:1;         /* has it changed */

    unsigned protected:1;       /* must accessor be a subclass of "this" */

    union {

        int i;                  /* operand to the opcode */

        int *ip;

        fullinfo_type fi;

    } operand, operand2;

    fullinfo_type p;

    struct stack_info_type stack_info;

    struct register_info_type register_info;

#define FLAG_REACHED            0x01 /* instruction reached */

#define FLAG_NEED_CONSTRUCTOR   0x02 /* must call this.<init> or super.<init> */

#define FLAG_NO_RETURN          0x04 /* must throw out of method */

    flag_type or_flags;         /* true for at least one path to this inst */

#define FLAG_CONSTRUCTED        0x01 /* this.<init> or super.<init> called */

    flag_type and_flags;        /* true for all paths to this instruction */

};

struct handler_info_type {

    int start, end, handler;

    struct stack_info_type stack_info;

};

struct stack_item_type {

    fullinfo_type item;

    struct stack_item_type *next;

};

typedef struct context_type context_type;

typedef struct instruction_data_type instruction_data_type;

typedef struct stack_item_type stack_item_type;

typedef struct register_info_type register_info_type;

typedef struct stack_info_type stack_info_type;

typedef struct mask_type mask_type;

static void read_all_code(context_type *context, jclass cb, int num_methods,

                          int** code_lengths, unsigned char*** code);

static void verify_method(context_type *context, jclass cb, int index,

                          int code_length, unsigned char* code);

static void free_all_code(int num_methods, int* lengths, unsigned char** code);

static void verify_field(context_type *context, jclass cb, int index);

static void verify_opcode_operands (context_type *, unsigned int inumber, int offset);

static void set_protected(context_type *, unsigned int inumber, int key, opcode_type);

static jboolean is_superclass(context_type *, fullinfo_type);

static void initialize_exception_table(context_type *);

static int instruction_length(unsigned char *iptr, unsigned char *end);

static jboolean isLegalTarget(context_type *, int offset);

static void verify_constant_pool_type(context_type *, int, unsigned);

static void initialize_dataflow(context_type *);

static void run_dataflow(context_type *context);

static void check_register_values(context_type *context, unsigned int inumber);

static void check_flags(context_type *context, unsigned int inumber);

static void pop_stack(context_type *, unsigned int inumber, stack_info_type *);

static void update_registers(context_type *, unsigned int inumber, register_info_type *);

static void update_flags(context_type *, unsigned int inumber,

                         flag_type *new_and_flags, flag_type *new_or_flags);

static void push_stack(context_type *, unsigned int inumber, stack_info_type *stack);

static void merge_into_successors(context_type *, unsigned int inumber,

                                  register_info_type *register_info,

                                  stack_info_type *stack_info,

                                  flag_type and_flags, flag_type or_flags);

static void merge_into_one_successor(context_type *context,

                                     unsigned int from_inumber,

                                     unsigned int inumber,

                                     register_info_type *register_info,

                                     stack_info_type *stack_info,

                                     flag_type and_flags, flag_type or_flags,

                                     jboolean isException);

static void merge_stack(context_type *, unsigned int inumber,

                        unsigned int to_inumber, stack_info_type *);

static void merge_registers(context_type *, unsigned int inumber,

                            unsigned int to_inumber,

                            register_info_type *);

static void merge_flags(context_type *context, unsigned int from_inumber,

                        unsigned int to_inumber,

                        flag_type new_and_flags, flag_type new_or_flags);

static stack_item_type *copy_stack(context_type *, stack_item_type *);

static mask_type *copy_masks(context_type *, mask_type *masks, int mask_count);

static mask_type *add_to_masks(context_type *, mask_type *, int , int);

static fullinfo_type decrement_indirection(fullinfo_type);

static fullinfo_type merge_fullinfo_types(context_type *context,

                                          fullinfo_type a,

                                          fullinfo_type b,

                                          jboolean assignment);

static jboolean isAssignableTo(context_type *,

                               fullinfo_type a,

                               fullinfo_type b);

static jclass object_fullinfo_to_classclass(context_type *, fullinfo_type);

#define NEW(type, count) \

        ((type *)CCalloc(context, (count)*(sizeof(type)), JNI_FALSE))

#define ZNEW(type, count) \

        ((type *)CCalloc(context, (count)*(sizeof(type)), JNI_TRUE))

static void CCinit(context_type *context);

static void CCreinit(context_type *context);

static void CCdestroy(context_type *context);

static void *CCalloc(context_type *context, int size, jboolean zero);

static fullinfo_type cp_index_to_class_fullinfo(context_type *, int, int);

static char signature_to_fieldtype(context_type *context,

                                   const char **signature_p, fullinfo_type *info);

static void CCerror (context_type *, char *format, ...);

static void CFerror (context_type *, char *format, ...);

static void CCout_of_memory (context_type *);

/* Because we can longjmp any time, we need to be very careful about

 * remembering what needs to be freed. */

static void check_and_push(context_type *context, const void *ptr, int kind);

static void pop_and_free(context_type *context);

static int signature_to_args_size(const char *method_signature);

#ifdef DEBUG

static void print_stack (context_type *, stack_info_type *stack_info);

static void print_registers(context_type *, register_info_type *register_info);

static void print_flags(context_type *, flag_type, flag_type);

static void print_formatted_fieldname(context_type *context, int index);

static void print_formatted_methodname(context_type *context, int index);

#endif

void initialize_class_hash(context_type *context)

{

    hash_table_type *class_hash = &(context->class_hash);

    class_hash->buckets = (hash_bucket_type **)

        calloc(MAX_HASH_ENTRIES / HASH_ROW_SIZE, sizeof(hash_bucket_type *));

    class_hash->table = (unsigned short *)

        calloc(HASH_TABLE_SIZE, sizeof(unsigned short));

    if (class_hash->buckets == 0 ||

        class_hash->table == 0)

        CCout_of_memory(context);

    class_hash->entries_used = 0;

}

static void finalize_class_hash(context_type *context)

{

    hash_table_type *class_hash = &(context->class_hash);

    JNIEnv *env = context->env;

    int i;

    /* 4296677: bucket index starts from 1. */

    for (i=1;i<=class_hash->entries_used;i++) {

        hash_bucket_type *bucket = GET_BUCKET(class_hash, i);

        assert(bucket != NULL);

        free(bucket->name);

        if (bucket->class) {

            (*env)->DeleteGlobalRef(env, bucket->class);

#ifdef DEBUG

            context->n_globalrefs--;

#endif

        }

    }

    if (class_hash->buckets) {

        for (i=0;i<MAX_HASH_ENTRIES / HASH_ROW_SIZE; i++) {

            if (class_hash->buckets[i] == 0)

                break;

            free(class_hash->buckets[i]);

        }

    }

    free(class_hash->buckets);

    free(class_hash->table);

}

static hash_bucket_type *

new_bucket(context_type *context, unsigned short *pID)

{

    hash_table_type *class_hash = &(context->class_hash);

    int i = *pID = class_hash->entries_used + 1;

    int row = i / HASH_ROW_SIZE;

    if (i >= MAX_HASH_ENTRIES)

        CCerror(context, "Exceeded verifier's limit of 65535 referred classes");

    if (class_hash->buckets[row] == 0) {

        class_hash->buckets[row] = (hash_bucket_type*)

            calloc(HASH_ROW_SIZE, sizeof(hash_bucket_type));

        if (class_hash->buckets[row] == 0)

            CCout_of_memory(context);

    }

    class_hash->entries_used++; /* only increment when we are sure there

                                   is no overflow. */

    return GET_BUCKET(class_hash, i);

}

static unsigned int

class_hash_fun(const char *s)

{

    int i;

    unsigned raw_hash;

    for (raw_hash = 0; (i = *s) != '\0'; ++s)

        raw_hash = raw_hash * 37 + i;

    return raw_hash;

}

/*

 * Find a class using the defining loader of the current class

 * and return a local reference to it.

 */

static jclass load_class_local(context_type *context,const char *classname)

{

    jclass cb = JVM_FindClassFromClass(context->env, classname,

                                 JNI_FALSE, context->class);

    if (cb == 0)

         CCerror(context, "Cannot find class %s", classname);

    return cb;

}

/*

 * Find a class using the defining loader of the current class

 * and return a global reference to it.

 */

static jclass load_class_global(context_type *context, const char *classname)

{

    JNIEnv *env = context->env;

    jclass local, global;