/* src/vm/classcache.c - loaded class cache and loading constraints
- Copyright (C) 1996-2005 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 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
This file is part of CACAO.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
- 02111-1307, USA.
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
+ 02110-1301, USA.
- Contact: cacao@complang.tuwien.ac.at
+ Contact: cacao@cacaojvm.org
Authors: Edwin Steiner
Changes: Christian Thalinger
- $Id: classcache.c 3837 2005-12-01 23:50:28Z twisti $
+ $Id: classcache.c 4690 2006-03-27 11:37:46Z twisti $
*/
+#include "config.h"
+
#include <assert.h>
-#include "config.h"
#include "vm/types.h"
#include "mm/memory.h"
#include "vm/utf8.h"
+/*************************************************************************
+
+ Class Cache
+
+ The classcache has two functions:
+
+ 1) caching the resolution of class references
+ 2) storing and checking loading constraints
+
+ We will use the following terms in this description:
+
+ N a class name: a utf string
+ (N,L) a class reference with initiating loader L and class name N
+ C a class (object): the result of resolving a reference (N,L)
+ We will write resultion as
+ C = *(N,L)
+ (N,L1,L2) a loading constraint indicating that (N,L1) and (N,L2) must
+ resolve to the same class C. So (N,L1,L2) means
+ *(N,L1) = *(N,L2)
+
+ The functions of the classcache require:
+
+ 1) a mapping (N,L) |--> C for looking up prior resolution results.
+ 2) storing the current set of loading constraints { (N,L1,L2) }
+
+ These functions can be rearranged like that:
+
+ a mapping N |--> (a mapping L |--> C or NULL,
+ a set of constraints {(L1,L2)})
+
+ Thus we can treat the mapping and constraints for each name N
+ separately. The implementation does this by keeping a hash table
+ mapping a name N to a `classcache_name_entry` which contains all
+ info with respect to N.
+
+ For a class name N we can define an equivalence relation ~N~ on
+ class loaders:
+
+ L1 ~N~ L2 <==> *(N,L1) = *(N,L2)
+
+ A loading constraint (N,L1,L2) implies L1 ~N~ L2.
+
+ Also, if two references (N,L1) and (N,L2) resolve to the same class C
+ we have L1 ~N~ L2 because class loaders are required to return
+ consistent resolutions for a name N [XXX].
+
+ A `classcache_name_entry` keeps a set of tuples { (Cx,IL,CL) },
+ where
+ Cx...is a class C or NULL
+ IL...is the set of initiating loaders
+ CL...is the set of constrained loaders
+
+ Such a tuple is called `classcache_class_entry` in the source code.
+
+ The following holds for each tuple (Cx,IL,CL):
+
+ . (Cx is NULL) implies IL = {}.
+
+ . If Cx is a class, IL is the set of loaders that have been
+ recorded as initiating loaders for Cx. IL may be the
+ empty set {} in case Cx has already been defined but no
+ initiating loader has been recorded, yet.
+
+ . (IL u CL) is a subset of an equivalence class of ~N~.
+
+ (This means that all loaders in IL and CL must resolve
+ the name N to the same class.)
+
+ The following holds for the set of tuples { (Cx,IL,CL) }:
+
+ . For a given class C there is at most one tuple with Cx = C
+ in the set. (There may be an arbitrary number of tuples
+ with Cx = NULL, however.)
+
+ . For a given loader L there is at most one tuple with
+ L in (IL u CL).
+
+ The implementation stores sets of loaders as linked lists of
+ `classcache_loader_entry`s.
+
+ Comments about manipulating the classcache can be found in the
+ individual functions below.
+
+*************************************************************************/
+
+
/* initial number of slots in the classcache hash table */
#define CLASSCACHE_INIT_SIZE 2048
/*#define CLASSCACHE_VERBOSE*/
+/*============================================================================*/
+/* STATISTICS */
+/*============================================================================*/
+
+/*#define CLASSCACHE_STATS*/
+
+#ifdef CLASSCACHE_STATS
+static int stat_classnames_stored = 0;
+static int stat_classes_stored = 0;
+static int stat_trivial_constraints = 0;
+static int stat_nontriv_constraints = 0;
+static int stat_nontriv_constraints_both = 0;
+static int stat_nontriv_constraints_merged = 0;
+static int stat_nontriv_constraints_one = 0;
+static int stat_nontriv_constraints_none = 0;
+static int stat_new_loader_entry = 0;
+static int stat_merge_class_entries = 0;
+static int stat_merge_loader_entries = 0;
+static int stat_lookup = 0;
+static int stat_lookup_class_entry_checked = 0;
+static int stat_lookup_loader_checked = 0;
+static int stat_lookup_name = 0;
+static int stat_lookup_name_entry = 0;
+static int stat_lookup_name_notfound = 0;
+static int stat_lookup_new_name = 0;
+static int stat_lookup_new_name_entry = 0;
+static int stat_lookup_new_name_collisions = 0;
+static int stat_rehash_names = 0;
+static int stat_rehash_names_collisions = 0;
+
+#define CLASSCACHE_COUNT(cnt) (cnt)++
+#define CLASSCACHE_COUNTIF(cond,cnt) do{if(cond) (cnt)++;} while(0)
+
+void classcache_print_statistics(FILE *file) {
+ fprintf(file,"classnames stored : %8d\n",stat_classnames_stored);
+ fprintf(file,"classes stored : %8d\n",stat_classes_stored);
+ fprintf(file,"trivial constraints : %8d\n",stat_trivial_constraints);
+ fprintf(file,"non-triv constraints: %8d\n",stat_nontriv_constraints);
+ fprintf(file," both loaders rec.: %8d\n",stat_nontriv_constraints_both);
+ fprintf(file," merged : %8d\n",stat_nontriv_constraints_merged);
+ fprintf(file," one loader rec. : %8d\n",stat_nontriv_constraints_one);
+ fprintf(file," no loaders rec. : %8d\n",stat_nontriv_constraints_none);
+ fprintf(file,"new loader entries : %8d\n",stat_new_loader_entry);
+ fprintf(file,"merge class entries : %8d\n",stat_merge_class_entries);
+ fprintf(file,"merge loader entries: %8d\n",stat_merge_loader_entries);
+ fprintf(file,"lookups : %8d\n",stat_lookup);
+ fprintf(file," class entries ckd: %8d\n",stat_lookup_class_entry_checked);
+ fprintf(file," loader checked : %8d\n",stat_lookup_loader_checked);
+ fprintf(file,"lookup name : %8d\n",stat_lookup_name);
+ fprintf(file," entries checked : %8d\n",stat_lookup_name_entry);
+ fprintf(file," not found : %8d\n",stat_lookup_name_notfound);
+ fprintf(file,"lookup (new) name : %8d\n",stat_lookup_new_name);
+ fprintf(file," entries checked : %8d\n",stat_lookup_new_name_entry);
+ fprintf(file," new collisions : %8d\n",stat_lookup_new_name_collisions);
+ fprintf(file,"names rehashed : %8d times\n",stat_rehash_names);
+ fprintf(file," collisions : %8d\n",stat_rehash_names_collisions);
+}
+#else
+#define CLASSCACHE_COUNT(cnt)
+#define CLASSCACHE_COUNTIF(cond,cnt)
+#endif
+
/*============================================================================*/
/* THREAD-SAFE LOCKING */
/*============================================================================*/
/* */
/*============================================================================*/
+/* prototypes */
+
+static void classcache_free_class_entry(classcache_class_entry *clsen);
+static void classcache_remove_class_entry(classcache_name_entry *en,
+ classcache_class_entry *clsen);
+
+/* hash function to use */
+
+#define CLASSCACHE_HASH utf_full_hashkey
+
/* classcache_init *************************************************************
- Initialize the loaded class cache
+ Initialize the class cache
Note: NOT synchronized!
lden = NEW(classcache_loader_entry);
lden->loader = loader;
lden->next = next;
+ CLASSCACHE_COUNT(stat_new_loader_entry);
return lden;
}
classcache_loader_entry *ldenB;
classcache_loader_entry **chain;
+ CLASSCACHE_COUNT(stat_merge_loader_entries);
+
/* XXX This is a quadratic algorithm. If this ever
* becomes a problem, the loader lists should be
* stored as sorted lists and merged in linear time. */
return result;
}
+/* classcache_merge_class_entries **********************************************
+
+ Merge two `classcache_class_entry`s into one.
+ (internally used helper function)
+
+ IN:
+ en...............the classcache_name_entry containing both class entries
+ clsenA...........first class entry, will receive the result
+ clsenB...........second class entry
+
+ PRE-CONDITION:
+ Either both entries must have the same classobj, or one of them has
+ classobj == NULL.
+
+ NOTE:
+ clsenB is freed by this function!
+
+*******************************************************************************/
+
+static void classcache_merge_class_entries(classcache_name_entry *en,
+ classcache_class_entry *clsenA,
+ classcache_class_entry *clsenB)
+{
+#ifdef CLASSCACHE_VERBOSE
+ char logbuffer[1024];
+#endif
+
+ assert(en);
+ assert(clsenA);
+ assert(clsenB);
+ assert(!clsenA->classobj || !clsenB->classobj || clsenA->classobj == clsenB->classobj);
+
+#ifdef CLASSCACHE_VERBOSE
+ sprintf(logbuffer,"classcache_merge_class_entries(%p,%p->%p,%p->%p) ",
+ (void*)en,(void*)clsenA,(void*)clsenA->classobj,(void*)clsenB,(void*)clsenB->classobj);
+ if (clsenA->classobj)
+ utf_strcat(logbuffer, clsenA->classobj->name);
+ if (clsenB->classobj)
+ utf_strcat(logbuffer, clsenB->classobj->name);
+ log_text(logbuffer);
+#endif
+
+ CLASSCACHE_COUNT(stat_merge_class_entries);
+
+ /* clsenB will be merged into clsenA */
+ clsenA->loaders = classcache_merge_loaders(clsenA->loaders, clsenB->loaders);
+ clsenB->loaders = NULL; /* these have been freed or reused */
+
+ clsenA->constraints = classcache_merge_loaders(clsenA->constraints,
+ clsenB->constraints);
+ clsenB->constraints = NULL; /* these have been freed or reused */
+
+ if (!clsenA->classobj)
+ clsenA->classobj = clsenB->classobj;
+
+ /* remove clsenB from the list of class entries */
+ classcache_remove_class_entry(en, clsenB);
+}
+
/* classcache_lookup_name ******************************************************
classcache_name_entry *c; /* hash table element */
u4 key; /* hashkey computed from classname */
u4 slot; /* slot in hashtable */
-/* u4 i; */
- key = utf_hashkey(name->text, (u4) name->blength);
+ CLASSCACHE_COUNT(stat_lookup_name);
+
+ key = CLASSCACHE_HASH(name->text, (u4) name->blength);
slot = key & (hashtable_classcache.size - 1);
c = hashtable_classcache.ptr[slot];
while (c) {
/* entry found in hashtable */
+ CLASSCACHE_COUNT(stat_lookup_name_entry);
if (c->name == name)
return c;
/* not found */
+ CLASSCACHE_COUNT(stat_lookup_name_notfound);
return NULL;
}
u4 slot; /* slot in hashtable */
u4 i;
- key = utf_hashkey(name->text, (u4) name->blength);
+ CLASSCACHE_COUNT(stat_lookup_new_name);
+
+ key = CLASSCACHE_HASH(name->text, (u4) name->blength);
slot = key & (hashtable_classcache.size - 1);
c = hashtable_classcache.ptr[slot];
while (c) {
/* entry found in hashtable */
+ CLASSCACHE_COUNT(stat_lookup_new_name_entry);
if (c->name == name)
return c;
/* insert entry into hashtable */
c->hashlink = (classcache_name_entry *) hashtable_classcache.ptr[slot];
+ CLASSCACHE_COUNTIF(c->hashlink,stat_lookup_new_name_collisions);
hashtable_classcache.ptr[slot] = c;
/* update number of hashtable-entries */
hashtable_classcache.entries++;
+ CLASSCACHE_COUNT(stat_classnames_stored);
- if (hashtable_classcache.entries > (hashtable_classcache.size * 2)) {
-
- /* reorganization of hashtable, average length of
- the external chains is approx. 2 */
+ if ((hashtable_classcache.entries*2) > hashtable_classcache.size) {
+ /* reorganization of hashtable */
classcache_name_entry *c2;
hashtable newhash; /* the new hashtable */
+ CLASSCACHE_COUNT(stat_rehash_names);
+
/* create new hashtable, double the size */
hashtable_create(&newhash, hashtable_classcache.size * 2);
while (c2) {
classcache_name_entry *nextc = c2->hashlink;
u4 newslot =
- (utf_hashkey(c2->name->text, (u4) c2->name->blength)) & (newhash.size - 1);
+ (CLASSCACHE_HASH(c2->name->text, (u4) c2->name->blength)) & (newhash.size - 1);
c2->hashlink = (classcache_name_entry *) newhash.ptr[newslot];
+ CLASSCACHE_COUNTIF(c2->hashlink,stat_rehash_names_collisions);
newhash.ptr[newslot] = c2;
c2 = nextc;
CLASSCACHE_LOCK();
+ CLASSCACHE_COUNT(stat_lookup);
en = classcache_lookup_name(classname);
if (en) {
/* iterate over all class entries */
for (clsen = en->classes; clsen; clsen = clsen->next) {
+ CLASSCACHE_COUNT(stat_lookup_class_entry_checked);
/* check if this entry has been loaded by initloader */
for (lden = clsen->loaders; lden; lden = lden->next) {
+ CLASSCACHE_COUNT(stat_lookup_loader_checked);
if (lden->loader == initloader) {
/* found the loaded class entry */
RETURN VALUE:
cls..............everything ok, the class was stored in the cache,
other classinfo..another class with the same (initloader,name) has been
- stored earlier. CLS has been freed and the earlier
+ stored earlier. CLS has been freed[1] and the earlier
stored class is returned.
NULL.............an exception has been thrown.
Note: synchronized with global tablelock
+
+ [1]...in case MAYFREE is true
*******************************************************************************/
-classinfo * classcache_store(classloader * initloader,
- classinfo * cls,
- bool mayfree)
+classinfo *classcache_store(classloader *initloader, classinfo *cls,
+ bool mayfree)
{
classcache_name_entry *en;
classcache_class_entry *clsen;
+ classcache_class_entry *clsenB;
classcache_loader_entry *lden;
#ifdef CLASSCACHE_VERBOSE
char logbuffer[1024];
#endif
assert(cls);
- assert(cls->loaded != 0);
+ assert(cls->state & CLASS_LOADED);
CLASSCACHE_LOCK();
#ifdef CLASSCACHE_VERBOSE
- sprintf(logbuffer,"classcache_store (%p,%d,", (void*)initloader,mayfree);
+ sprintf(logbuffer,"classcache_store (%p,%d,%p=", (void*)initloader,mayfree,(void*)cls);
utf_strcat(logbuffer, cls->name);
strcat(logbuffer,")");
log_text(logbuffer);
/* check if this entry has already been loaded by initloader */
for (lden = clsen->loaders; lden; lden = lden->next) {
- if (lden->loader == initloader && clsen->classobj != cls) {
- /* A class with the same (initloader,name) pair has been stored already. */
- /* We free the given class and return the earlier one. */
+ if (lden->loader == initloader) {
+ if (clsen->classobj != cls) {
+ /* A class with the same (initloader,name) pair has been stored already. */
+ /* We free the given class and return the earlier one. */
#ifdef CLASSCACHE_VERBOSE
- dolog("replacing %p with earlier loaded class %p",cls,clsen->classobj);
+ dolog("replacing %p with earlier loaded class %p",cls,clsen->classobj);
#endif
- assert(clsen->classobj);
- if (mayfree)
- class_free(cls);
- cls = clsen->classobj;
- goto return_success;
+ assert(clsen->classobj);
+ if (mayfree)
+ class_free(cls);
+ cls = clsen->classobj;
+ }
+ goto return_success;
}
}
+ /* {This entry has not been resolved with initloader} */
+
/* check if initloader is constrained to this entry */
for (lden = clsen->constraints; lden; lden = lden->next) {
if (lden->loader == initloader) {
- /* we have to use this entry */
- /* check if is has already been resolved to another class */
- if (clsen->classobj && clsen->classobj != cls) {
- /* a loading constraint is violated */
- *exceptionptr = exceptions_new_linkageerror(
- "loading constraint violated: ",cls);
- goto return_exception;
+ /* we have to use this entry. check if it has been resolved */
+ if (clsen->classobj) {
+ /* check if is has already been resolved to another class */
+ if (clsen->classobj != cls) {
+ /* a loading constraint is violated */
+ *exceptionptr = exceptions_new_linkageerror(
+ "loading constraint violated: ",cls);
+ goto return_exception;
+ }
+
+ /* record initloader as initiating loader */
+ clsen->loaders = classcache_new_loader_entry(initloader, clsen->loaders);
+ goto return_success;
}
+ /* {this is the first resolution for this entry} */
/* record initloader as initiating loader */
clsen->loaders = classcache_new_loader_entry(initloader, clsen->loaders);
+ /* maybe we can merge this entry with another one */
+ for (clsenB = en->classes; clsenB; clsenB = clsenB->next) {
+ /* we dont want the entry that we have already */
+ if (clsenB->classobj == cls) {
+ /* this entry has the same classobj. let's merge them */
+ classcache_merge_class_entries(en,clsen,clsenB);
+ goto return_success;
+ }
+ }
+
/* record the loaded class object */
clsen->classobj = cls;
+ CLASSCACHE_COUNT(stat_classes_stored);
/* done */
goto return_success;
}
+ /* {There is no class entry containing initloader as initiating
+ * or constrained loader.} */
+
+ /* we look for a class entry with the same classobj we want to store */
+ for (clsen = en->classes; clsen; clsen = clsen->next) {
+ if (clsen->classobj == cls) {
+ /* this entry is about the same classobj. let's use it */
+ /* check if this entry has already been loaded by initloader */
+ for (lden = clsen->loaders; lden; lden = lden->next) {
+ if (lden->loader == initloader)
+ goto return_success;
+ }
+ clsen->loaders = classcache_new_loader_entry(initloader, clsen->loaders);
+ goto return_success;
+ }
+ }
+
/* create a new class entry for this class object with */
/* initiating loader initloader */
clsen->next = en->classes;
en->classes = clsen;
+ CLASSCACHE_COUNT(stat_classes_stored);
return_success:
+#ifdef CLASSCACHE_VERBOSE
+ classcache_debug_dump(stderr,cls->name);
+#endif
CLASSCACHE_UNLOCK();
return cls;
*******************************************************************************/
-classinfo * classcache_store_defined(classinfo *cls)
+classinfo *classcache_store_defined(classinfo *cls)
{
classcache_name_entry *en;
classcache_class_entry *clsen;
#endif
assert(cls);
- assert(cls->loaded != 0);
+ assert(cls->state & CLASS_LOADED);
CLASSCACHE_LOCK();
clsen->next = en->classes;
en->classes = clsen;
+ CLASSCACHE_COUNT(stat_classes_stored);
return_success:
+#ifdef CLASSCACHE_VERBOSE
+ classcache_debug_dump(stderr,cls->name);
+#endif
CLASSCACHE_UNLOCK();
return cls;
}
#endif
/* a constraint with a == b is trivially satisfied */
- if (a == b)
+ if (a == b) {
+ CLASSCACHE_COUNT(stat_trivial_constraints);
return true;
+ }
CLASSCACHE_LOCK();
en = classcache_new_name(classname);
assert(en);
+ CLASSCACHE_COUNT(stat_nontriv_constraints);
/* find the entry loaded by / constrained to each loader */
clsenA = classcache_find_loader(en, a);
if (clsenA && clsenB) {
/* { both loaders have corresponding entries } */
+ CLASSCACHE_COUNT(stat_nontriv_constraints_both);
/* if the entries are the same, the constraint is already recorded */
if (clsenA == clsenB)
}
/* yes, merge the entries */
- /* clsenB will be merged into clsenA */
- clsenA->loaders = classcache_merge_loaders(clsenA->loaders, clsenB->loaders);
- clsenB->loaders = NULL;
-
- clsenA->constraints = classcache_merge_loaders(clsenA->constraints,
- clsenB->constraints);
- clsenB->constraints = NULL;
-
- if (!clsenA->classobj)
- clsenA->classobj = clsenB->classobj;
-
- /* remove clsenB from the list of class entries */
- classcache_remove_class_entry(en, clsenB);
+ classcache_merge_class_entries(en,clsenA,clsenB);
+ CLASSCACHE_COUNT(stat_nontriv_constraints_merged);
}
else {
/* { at most one of the loaders has a corresponding entry } */
if (!clsenA) {
/* { no loader has a corresponding entry } */
+ CLASSCACHE_COUNT(stat_nontriv_constraints_none);
/* create a new class entry with the constraint (a,b,en->name) */
clsenA = NEW(classcache_class_entry);
en->classes = clsenA;
}
else {
+ CLASSCACHE_COUNT(stat_nontriv_constraints_one);
+
/* make b the loader that has no corresponding entry */
if (clsenB)
b = a;
IN:
file.............output stream
+ only.............if != NULL, only print entries for this name
+ (Currently we print also the rest of the hash chain to
+ get a feel for the average length of hash chains.)
Note: synchronized with global tablelock
*******************************************************************************/
#ifndef NDEBUG
-void classcache_debug_dump(FILE * file)
+void classcache_debug_dump(FILE * file,utf *only)
{
classcache_name_entry *c;
classcache_class_entry *clsen;
fprintf(file, "hash entries: %d\n", (int) hashtable_classcache.entries);
fprintf(file, "\n");
+ if (only) {
+ c = classcache_lookup_name(only);
+ slot = 0; /* avoid compiler warning */
+ goto dump_it;
+ }
+
for (slot = 0; slot < hashtable_classcache.size; ++slot) {
c = (classcache_name_entry *) hashtable_classcache.ptr[slot];
+dump_it:
for (; c; c = c->hashlink) {
utf_fprint_classname(file, c->name);
fprintf(file, "\n");
fprintf(file, "\n");
}
}
+
+ if (only)
+ break;
}
fprintf(file, "\n==============================================================\n\n");