stringintern.c

来自「This is a resource based on j2me embedde」· C语言 代码 · 共 1,144 行 · 第 1/3 页

/*
 * @(#)stringintern.c	1.38 06/10/10
 *
 * Copyright  1990-2008 Sun Microsystems, Inc. All Rights Reserved.  
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER  
 *   
 * This program 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.   
 *   
 * This program 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 at /legal/license.txt).   
 *   
 * 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 or visit www.sun.com if you need additional  
 * information or have any questions. 
 *
 */

#include "javavm/include/defs.h"
#include "javavm/export/jni.h"
#include "native/common/jni_util.h"
#include "javavm/include/indirectmem.h"
#include "javavm/include/localroots.h"
#include "generated/offsets/java_lang_String.h"
#include "javavm/include/string_impl.h"
#include "javavm/include/common_exceptions.h"
#include "javavm/include/globals.h"

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

/*
    #define CVMInternSegmentSize	943 / * or 2003, choose one. * /

    struct CVMInternSegment {
	    struct CVMInternSegment * next;
	    CVMUint32	capacity;
	    CVMUint32	load;
	    CVMUint32	maxLoad;
	    CVMStringICell	data[capacity];
	    CVMUint8	refCount[capacity];
    } CVMInternSegment;

	/ *
	// count == 255 means unused	 (CVMInternUnused)
	// count == 254 means sticky	 (CVMInternSticky)
	// count == 253 means deleted!!	 (CVMInternDeleted)
	* /
*/

/*
 * Acceptable segment sizes.
 * All must be relatively prime to the secondary hash, h1,
 * and, as a bonus, should be relatively prime to 37, used
 * in the initial hash value computation
 * Since 1 <= h1 <= 16, these sizes cannot contain the
 * factors 2, 3, 5, 7, 11, or 13.
 */
static const int CVMinternSegmentSizes[] = {
	943,	/* 41*23 */
	1511,	/* prime */
	2147,   /* 113 * 19 */
	3233,   /* 61 * 53 */
	4891,   /* 73 * 67 */
	7313,   /* 103 * 71 */
	10961,  /* 113 * 97 */
	15943   /* 149 * 107 */
};

#define CVM_INTERN_INITIAL_SEGMENT_SIZE_IDX	0
#define CVM_INTERN_MAX_SEGMENT_SIZE_IDX		7

#ifdef CVM_DEBUG

/*
 * CALL ONLY FROM DEBUGGER: NO LOCKING!!
 */

static void
CVMInternValidateSegment( struct CVMInternSegment * segp, CVMBool verbose ) {
    int capacity, i;
    CVMUint8 *  refCount;
    CVMStringICell * data;
    int nUnused, nSticky, nDeleted, nNoRef, nRef, nBad;
    CVMBool cellIsNull;

    /* do trivial consistancy checks first */
    if ( segp->nextp == NULL ){
	CVMconsolePrintf("Intern segment 0x%x->nextp == NULL\n", segp );
    } else if ( verbose ){
	CVMconsolePrintf("Intern segment 0x%x->nextp != NULL (OK)\n", segp );
    }
    if ( (capacity = segp->capacity) < CVM_INTERN_INITIAL_SEGMENT_SIZE_IDX ){
	/* could be ok for very small romized set, so don't panic! */
	CVMconsolePrintf("Intern segment 0x%x->capacity == %d\n", segp, segp->capacity );
    } else if ( verbose ){
	CVMconsolePrintf("Intern segment 0x%x->capacity == %d (OK)\n", segp, segp->capacity );
    }
    if ( segp->load > capacity ){
	CVMconsolePrintf("Intern segment 0x%x->load == %d > capacity == %d\n", segp,
	    segp->load, capacity );
    } else if (verbose){
	CVMconsolePrintf("Intern segment 0x%x->load == %d (OK)\n", segp, segp->load );
    }
    if ( segp->maxLoad > (((segp->capacity*65)/100)+1) ){
	CVMconsolePrintf("Intern segment 0x%x->maxLoad == %d\n", segp, segp->maxLoad );
    } else if ( verbose ){
	CVMconsolePrintf("Intern segment 0x%x->maxLoad == %d (OK)\n", segp, segp->maxLoad );
    }

    /* now look at all the data. */
    nUnused = nSticky = nDeleted = nNoRef = nRef = nBad = 0;
    refCount = CVMInternRefCount( segp );
    data     = segp->data;
    for ( i = 0; i < capacity; i++ ){
	cellIsNull = CVMID_icellIsNull( &data[i] );
	switch ( refCount[i] ){
	case CVMInternUnused:
	    nUnused += 1;
	    if ( !cellIsNull ){
		CVMconsolePrintf("Intern segment 0x%x->data[%d] Unused but not null\n", segp, i );
		nBad += 1;
	    }
	    break;
	case CVMInternSticky:
	    nSticky += 1;
	    if ( cellIsNull ){
		CVMconsolePrintf("Intern segment 0x%x->data[%d] Sticky but null\n", segp, i );
		nBad += 1;
	    }
	    break;
	case CVMInternDeleted:
	    nDeleted += 1;
	    if ( !cellIsNull ){
		CVMconsolePrintf("Intern segment 0x%x->data[%d] Deleted but not null\n", segp, i );
		nBad += 1;
	    }
	    break;
	default:
	    if ( refCount[i] == 0 )
		nNoRef += 1;
	    else
		nRef += 1;
	    if ( cellIsNull ){
		CVMconsolePrintf("Intern segment 0x%x->data[%d] null with ref count %d\n", segp, i, refCount[i] );
		nBad += 1;
	    }
	    break;
	}
    }
    if ( verbose ){
	CVMconsolePrintf("Intern segment 0x%x has:\n", segp );
	CVMconsolePrintf("    %d unused cells\n", nUnused );
	CVMconsolePrintf("    %d sticky cells\n", nSticky );
	CVMconsolePrintf("    %d deleted cells\n", nDeleted );
	CVMconsolePrintf("    %d 0-ref-count cells\n", nNoRef );
	CVMconsolePrintf("    %d non-0-ref-count cells\n", nRef );
    }
    if ( segp->load != ( nSticky+nDeleted+nNoRef+nRef ) ){
	CVMconsolePrintf("Intern segment 0x%x->load == %d, should be %d\n",
	    segp->load, ( nSticky+nDeleted+nNoRef+nRef ) );
    }
    if ( nBad != 0 ){
	CVMconsolePrintf("Intern segment 0x%x has %d bad cells\n", segp, nBad );
    }
}

/*
 * CALL ONLY FROM DEBUGGER: NO LOCKING!!
 */

void
CVMInternValidateAllSegments( CVMBool verbose ) {
    CVMInternSegment * curSeg, *nextSeg;
    nextSeg = (CVMInternSegment*)&CVMInternTable; /* cast away const */
    do {
	curSeg = nextSeg;
	CVMInternValidateSegment( curSeg, verbose );
	nextSeg = CVMInternNext(curSeg);
    } while ( nextSeg != NULL );
}

/*
 * CALL ONLY FROM DEBUGGER!!
 * Not a good user of the memory interface!
 * Not suitable for any general purpose whatsoever.
 * Assumes that we really have ASCII strings.
 */

static void
CVMInternPrintString( CVMStringICell *icellp ){
    struct java_lang_String *stringp = *(struct java_lang_String**)icellp;
    struct CVMArrayOfChar   *datap;
    int    i, n, off;
#undef  MAXINTERNPRINTLENGTH
#define MAXINTERNPRINTLENGTH 20
    char   c[MAXINTERNPRINTLENGTH+1];

    if ( stringp == NULL ){
	CVMconsolePrintf("<null>");
	return;
    }
    n = stringp->count;
    off = stringp->offset;
    datap = *(CVMArrayOfChar**)&(stringp->value);
    CVMconsolePrintf("(%d)", n );
    if ( n > MAXINTERNPRINTLENGTH )
	n = MAXINTERNPRINTLENGTH;
    for ( i = 0; i < n ; i ++ ){
	c[i] = (char)(datap->elems[off++]);
    }
    c[i] = 0;
    CVMconsolePrintf("%s", c );
    if ( n < stringp->count )
	CVMconsolePrintf("...");
}

/*
 * CALL ONLY FROM DEBUGGER: NO LOCKING!!
 * ASSUMES SEGMENT VALIDATED ALREADY!
 */

void
CVMInternPrintSegment( struct CVMInternSegment * segp ) {
    int capacity, i;
    CVMUint8 *  refCount;
    CVMStringICell * data;

    capacity = segp->capacity;

    /* now look at all the data. */
    refCount = CVMInternRefCount( segp );
    data     = segp->data;

    CVMconsolePrintf("Printing all Strings in 0x%x\n", segp );

    for ( i = 0; i < capacity; i++ ){
	switch ( refCount[i] ){
	case CVMInternUnused:
	case CVMInternDeleted:
	    break;
	case CVMInternSticky:
	    CVMconsolePrintf("    S    ");
	    CVMInternPrintString( &data[i] );
	    CVMconsolePrintf("\n");
	    break;
	default:
	    CVMconsolePrintf("%4d    ", refCount[i] );
	    CVMInternPrintString( &data[i] );
	    CVMconsolePrintf("\n");
	    break;
	}
    }
}

#endif /* CVM_DEBUG */

typedef CVMBool (*helperFunction)( CVMExecEnv* ee,  CVMStringICell * candidate, void * stuff);
typedef void    (*consumerFunction)( CVMExecEnv* ee,  CVMStringICell * stringCell, CVMUint8 * refCell, void * stuff);

/* all our forwards for all our helper functions here */
static CVMInternSegment * allocateNewSegment();

static CVMBool
internJavaCompare( CVMExecEnv* ee,  CVMStringICell * candidate, void * stuff);
static CVMBool
internJavaProduce( CVMExecEnv *ee, CVMStringICell * target, void * stuff );
static void
internJavaConsume( CVMExecEnv* ee,  CVMStringICell * stringCell, CVMUint8 * refCell, void * stuff);

static CVMBool
internUTFCompare( CVMExecEnv* ee,  CVMStringICell * candidate, void * stuff);
static CVMBool
internUTFProduce( CVMExecEnv *ee, CVMStringICell * target, void * stuff );
static void
internUTFConsume( CVMExecEnv* ee,  CVMStringICell * stringCell, CVMUint8 * refCell, void * stuff);

/*
 * Max chars to look at when computing simple string hash value.
 * This constant is known by JavaCodeCompact.
 */
#undef  MAX_HASH_LENGTH
#define MAX_HASH_LENGTH		16

/*
 * If gc latency is of concern, you may want to reduce these buffer sizes.
 * They affect the maximum amount of time spent gc-unsafe while copying
 * characters from the heap to a local buffer.
 * Note that PREFIX_BUFFER_SIZE MUST BE > MAX_HASH_LENGTH, which is a constant
 * of the implementation shared with the preLoader!
 */

#undef  PREFIX_BUFFER_SIZE
#define PREFIX_BUFFER_SIZE	100
#undef  ITERATION_BUFFER_SIZE
#define ITERATION_BUFFER_SIZE	50

/*
 * This intern function is shared by the the function that
 * takes a java.lang.String as an argument (called by Java code)
 * and the one that take a UTF8 string as an argument
 * (called by the linker). In order to allow us to inline
 * a simple (or usually, all) comparison, we require that the
 * string's prefix be provided us in a buffer. The length provided
 * (in bufferLength) must be MIN( fullStringLength, PREFIX_BUFFER_SIZE ).
 * 
 * If the string is actually longer, the compare function will be called
 * to finish comparing the candidate to the input data.
 * compareData will be passed along to it.
 *
 * If the string is not alread in the table, the function produceData
 * will be called to (if necessary) construct the String, and fill
 * the slot in the table.
 *
 * a note on reference counts:
 * 255:	unused slot, unreferenced
 * 254: sticky object. Immortal. ROMized or very popular
 * 253: used slot, but was deleted from table when reference count
 *	went down. Needed to make hashing work!
 * [1, 252]: produced by class loader from UTF8 string. We trust
 *	that class UNloading will cause these to be decremented.
 */


static void
internInner(
    CVMExecEnv *	ee,
    CVMJavaChar 	buffer[],
    CVMSize		bufferLength,
    CVMSize		fullLength,
    helperFunction 	compare,
    helperFunction 	produce,
    consumerFunction	consume,
    void *		callbackData
){

    CVMUint32		h, h1;
    CVMSize 		i, j, n;
    CVMSize		slotWithOpening=0;
    CVMSize		capacity;
    CVMUint8		refCount;
    CVMUint8*		refArray;
    CVMInternSegment*   curSeg,
		    *	nextSeg,
		    *   segWithOpening = NULL;
    CVMStringICell  *	candidate;


    /* calculate hash code.
     * This is similar to the one in java.lang.String, but this
     * is just a coincidence. Make sure that the ROMizer uses the
     * same one! (in order to make this easier, we will mask off
     * the high order bit.)
     */
    n = MIN(bufferLength, MAX_HASH_LENGTH);
    h = 0;
    for ( i = 0; i < n; i++ ){
	h = (h*37) + buffer[i];
    }
    h &= ~0x80000000;
    h1 = (h&15)+1;

    /*
     * Look through the segments until we either find a match.
     * or run out of places to look. Keep track of any deleted
     * cells we find along the way, because if we have to
     * do an insertion, we'd prefer to insert in one of them.
     */

    /* too bad we have to lock ourselves against mutation */
    CVMsysMutexLock(ee, &CVMglobals.internLock );
    
    nextSeg = (CVMInternSegment*)&CVMInternTable; /* cast away const */