1 /* vm/classcache.c - loaded class cache and loading constraints
3 Copyright (C) 1996-2005 R. Grafl, A. Krall, C. Kruegel, C. Oates,
4 R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
5 C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
6 Institut f. Computersprachen - TU Wien
8 This file is part of CACAO.
10 This program is free software; you can redistribute it and/or
11 modify it under the terms of the GNU General Public License as
12 published by the Free Software Foundation; either version 2, or (at
13 your option) any later version.
15 This program is distributed in the hope that it will be useful, but
16 WITHOUT ANY WARRANTY; without even the implied warranty of
17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 General Public License for more details.
20 You should have received a copy of the GNU General Public License
21 along with this program; if not, write to the Free Software
22 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
25 Contact: cacao@complang.tuwien.ac.at
27 Authors: Edwin Steiner
31 $Id: classcache.c 2190 2005-04-02 10:07:44Z edwin $
36 #include "vm/classcache.h"
38 #include "vm/tables.h"
39 #include "vm/exceptions.h"
40 #include "mm/memory.h"
42 /* initial number of slots in the classcache hash table */
43 #define CLASSCACHE_INIT_SIZE 2048
45 /*============================================================================*/
47 /*============================================================================*/
49 /*#define CLASSCACHE_VERBOSE*/
52 #define CLASSCACHE_DEBUG
55 #ifdef CLASSCACHE_DEBUG
56 #define CLASSCACHE_ASSERT(cond) assert(cond)
58 #define CLASSCACHE_ASSERT(cond)
61 /*============================================================================*/
62 /* THREAD-SAFE LOCKING */
63 /*============================================================================*/
65 /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
66 /* CAUTION: The static functions below are */
67 /* NOT synchronized! */
68 /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
70 #if defined(USE_THREADS) && defined(NATIVE_THREADS)
71 # define CLASSCACHE_LOCK() tables_lock()
72 # define CLASSCACHE_UNLOCK() tables_unlock()
74 # define CLASSCACHE_LOCK()
75 # define CLASSCACHE_UNLOCK()
78 /*============================================================================*/
79 /* GLOBAL VARIABLES */
80 /*============================================================================*/
82 static hashtable classcache_hash;
84 /*============================================================================*/
86 /*============================================================================*/
88 /* classcache_init *************************************************************
90 Initialize the loaded class cache
92 Note: NOT synchronized!
94 *******************************************************************************/
99 init_hashtable(&classcache_hash,CLASSCACHE_INIT_SIZE);
102 /* classcache_new_loader_entry *************************************************
104 Create a new classcache_loader_entry struct
105 (internally used helper function)
108 loader...........the ClassLoader object
109 next.............the next classcache_loader_entry
112 the new classcache_loader_entry
114 *******************************************************************************/
116 static classcache_loader_entry *
117 classcache_new_loader_entry(classloader *loader,classcache_loader_entry *next)
119 classcache_loader_entry *lden;
121 lden = NEW(classcache_loader_entry);
122 lden->loader = loader;
128 /* classcache_merge_loaders ****************************************************
130 Merge two lists of loaders into one
131 (internally used helper function)
134 lista............first list (may be NULL)
135 listb............second list (may be NULL)
138 the merged list (may be NULL)
141 The lists given as arguments are destroyed!
143 *******************************************************************************/
145 static classcache_loader_entry *
146 classcache_merge_loaders(classcache_loader_entry *lista,
147 classcache_loader_entry *listb)
149 classcache_loader_entry *result;
150 classcache_loader_entry *ldenA;
151 classcache_loader_entry *ldenB;
152 classcache_loader_entry **chain;
154 /* XXX This is a quadratic algorithm. If this ever
155 * becomes a problem, the loader lists should be
156 * stored as sorted lists and merged in linear time. */
161 for (ldenA=lista; ldenA; ldenA=ldenA->next) {
163 for (ldenB=listb; ldenB; ldenB=ldenB->next) {
164 if (ldenB->loader == ldenA->loader)
168 /* this loader is only in lista */
170 chain = &(ldenA->next);
173 /* XXX free the duplicated element */
177 /* concat listb to the result */
183 /* classcache_lookup_name ******************************************************
185 Lookup a name in the first level of the cache
186 (internally used helper function)
189 name.............the name to look up
192 a pointer to the classcache_name_entry for this name, or
193 null if no entry was found.
195 *******************************************************************************/
197 static classcache_name_entry *
198 classcache_lookup_name(utf *name)
200 classcache_name_entry * c; /* hash table element */
201 u4 key; /* hashkey computed from classname */
202 u4 slot; /* slot in hashtable */
205 key = utf_hashkey(name->text, name->blength);
206 slot = key & (classcache_hash.size - 1);
207 c = classcache_hash.ptr[slot];
209 /* search external hash chain for the entry */
211 if (c->name->blength == name->blength) {
212 for (i = 0; i < name->blength; i++)
213 if (name->text[i] != c->name->text[i]) goto nomatch;
215 /* entry found in hashtable */
220 c = c->hashlink; /* next element in external chain */
227 /* classcache_new_name *********************************************************
229 Return a classcache_name_entry for the given name. The entry is created
230 if it is not already in the cache.
231 (internally used helper function)
234 name.............the name to look up / create an entry for
237 a pointer to the classcache_name_entry for this name
239 *******************************************************************************/
241 static classcache_name_entry *
242 classcache_new_name(utf *name)
244 classcache_name_entry * c; /* hash table element */
245 u4 key; /* hashkey computed from classname */
246 u4 slot; /* slot in hashtable */
249 key = utf_hashkey(name->text, name->blength);
250 slot = key & (classcache_hash.size - 1);
251 c = classcache_hash.ptr[slot];
253 /* search external hash chain for the entry */
255 if (c->name->blength == name->blength) {
256 for (i = 0; i < name->blength; i++)
257 if (name->text[i] != c->name->text[i]) goto nomatch;
259 /* entry found in hashtable */
264 c = c->hashlink; /* next element in external chain */
267 /* location in hashtable found, create new entry */
269 c = NEW(classcache_name_entry);
274 /* insert entry into hashtable */
275 c->hashlink = classcache_hash.ptr[slot];
276 classcache_hash.ptr[slot] = c;
278 /* update number of hashtable-entries */
279 classcache_hash.entries++;
281 if (classcache_hash.entries > (classcache_hash.size * 2)) {
283 /* reorganization of hashtable, average length of
284 the external chains is approx. 2 */
287 classcache_name_entry *c;
288 hashtable newhash; /* the new hashtable */
290 /* create new hashtable, double the size */
291 init_hashtable(&newhash, classcache_hash.size * 2);
292 newhash.entries = classcache_hash.entries;
294 /* transfer elements to new hashtable */
295 for (i = 0; i < classcache_hash.size; i++) {
296 c = (classcache_name_entry *) classcache_hash.ptr[i];
298 classcache_name_entry *nextc = c->hashlink;
299 u4 slot = (utf_hashkey(c->name->text, c->name->blength)) & (newhash.size - 1);
301 c->hashlink = newhash.ptr[slot];
302 newhash.ptr[slot] = c;
308 /* dispose old table */
309 MFREE(classcache_hash.ptr, void*, classcache_hash.size);
310 classcache_hash = newhash;
316 /* classcache_lookup ***********************************************************
318 Lookup a possibly loaded class
321 initloader.......initiating loader for resolving the class name
322 classname........class name to look up
325 The return value is a pointer to the cached class object,
326 or NULL, if the class is not in the cache.
328 Note: synchronized with global tablelock
330 *******************************************************************************/
333 classcache_lookup(classloader *initloader,utf *classname)
335 classcache_name_entry *en;
336 classcache_class_entry *clsen;
337 classcache_loader_entry *lden;
338 classinfo *cls = NULL;
342 en = classcache_lookup_name(classname);
345 /* iterate over all class entries */
346 for (clsen=en->classes; clsen; clsen=clsen->next) {
347 /* check if this entry has been loaded by initloader */
348 for (lden=clsen->loaders; lden; lden=lden->next) {
349 if (lden->loader == initloader) {
350 /* found the loaded class entry */
351 CLASSCACHE_ASSERT(clsen->classobj);
352 cls = clsen->classobj;
363 /* classcache_store ************************************************************
368 initloader.......initiating loader used to load the class
369 cls..............class object to cache
372 true.............everything ok, the class was stored in
373 the cache if necessary,
374 false............an exception has been thrown.
376 Note: synchronized with global tablelock
378 *******************************************************************************/
381 classcache_store(classloader *initloader,classinfo *cls)
383 classcache_name_entry *en;
384 classcache_class_entry *clsen;
385 classcache_loader_entry *lden;
387 CLASSCACHE_ASSERT(cls);
389 #ifdef CLASSCACHE_VERBOSE
390 fprintf(stderr,"classcache_store(%p,",initloader);
391 utf_fprint_classname(stderr,cls->name);
392 fprintf(stderr,")\n");
397 en = classcache_new_name(cls->name);
399 CLASSCACHE_ASSERT(en);
401 /* iterate over all class entries */
402 for (clsen=en->classes; clsen; clsen=clsen->next) {
404 #ifdef CLASSCACHE_DEBUG
405 /* check if this entry has already been loaded by initloader */
406 /* It never should have been loaded before! */
407 for (lden=clsen->loaders; lden; lden=lden->next) {
408 if (lden->loader == initloader)
409 CLASSCACHE_ASSERT(false);
413 /* check if initloader is constrained to this entry */
414 for (lden=clsen->constraints; lden; lden=lden->next) {
415 if (lden->loader == initloader) {
416 /* we have to use this entry */
417 /* check if is has already been resolved to another class */
418 if (clsen->classobj && clsen->classobj != cls) {
419 /* a loading constraint is violated */
420 *exceptionptr = new_exception_message(string_java_lang_LinkageError,
421 "loading constraint violated XXX add message");
422 goto return_exception;
425 /* record initloader as initiating loader */
426 clsen->loaders = classcache_new_loader_entry(initloader,clsen->loaders);
428 /* record the loaded class object */
429 clsen->classobj = cls;
438 /* create a new class entry for this class object with */
439 /* initiating loader initloader */
441 clsen = NEW(classcache_class_entry);
442 clsen->classobj = cls;
443 clsen->loaders = classcache_new_loader_entry(initloader,NULL);
444 clsen->constraints = NULL;
446 clsen->next = en->classes;
455 return false; /* exception */
458 /* classcache_find_loader ******************************************************
460 Find the class entry loaded by or constrained to a given loader
461 (internally used helper function)
464 entry............the classcache_name_entry
465 loader...........the loader to look for
468 the classcache_class_entry for the given loader, or
469 NULL if no entry was found
471 *******************************************************************************/
473 static classcache_class_entry *
474 classcache_find_loader(classcache_name_entry *entry,classloader *loader)
476 classcache_class_entry *clsen;
477 classcache_loader_entry *lden;
479 CLASSCACHE_ASSERT(entry);
481 /* iterate over all class entries */
482 for (clsen=entry->classes; clsen; clsen=clsen->next) {
484 /* check if this entry has already been loaded by initloader */
485 for (lden=clsen->loaders; lden; lden=lden->next) {
486 if (lden->loader == loader)
487 return clsen; /* found */
490 /* check if loader is constrained to this entry */
491 for (lden=clsen->constraints; lden; lden=lden->next) {
492 if (lden->loader == loader)
493 return clsen; /* found */
501 /* classcache_free_class_entry *************************************************
503 Free the memory used by a class entry
506 clsen............the classcache_class_entry to free
508 *******************************************************************************/
511 classcache_free_class_entry(classcache_class_entry *clsen)
513 classcache_loader_entry *lden;
514 classcache_loader_entry *next;
516 CLASSCACHE_ASSERT(clsen);
518 for (lden=clsen->loaders; lden; lden=next) {
520 FREE(lden,classcache_loader_entry);
522 for (lden=clsen->constraints; lden; lden=next) {
524 FREE(lden,classcache_loader_entry);
527 FREE(clsen,classcache_class_entry);
530 /* classcache_remove_class_entry ***********************************************
532 Remove a classcache_class_entry from the list of possible resolution of
534 (internally used helper function)
537 entry............the classcache_name_entry
538 clsen............the classcache_class_entry to remove
540 *******************************************************************************/
543 classcache_remove_class_entry(classcache_name_entry *entry,
544 classcache_class_entry *clsen)
546 classcache_class_entry **chain;
548 CLASSCACHE_ASSERT(entry);
549 CLASSCACHE_ASSERT(clsen);
551 chain = &(entry->classes);
553 if (*chain == clsen) {
554 *chain = clsen->next;
555 classcache_free_class_entry(clsen);
558 chain = &((*chain)->next);
562 /* classcache_free_name_entry **************************************************
564 Free the memory used by a name entry
567 entry............the classcache_name_entry to free
569 *******************************************************************************/
572 classcache_free_name_entry(classcache_name_entry *entry)
574 classcache_class_entry *clsen;
575 classcache_class_entry *next;
577 CLASSCACHE_ASSERT(entry);
579 for (clsen=entry->classes; clsen; clsen=next) {
581 classcache_free_class_entry(clsen);
584 FREE(entry,classcache_name_entry);
587 /* classcache_free *************************************************************
589 Free the memory used by the class cache
592 The class cache may not be used any more after this call, except
593 when it is reinitialized with classcache_init.
595 Note: NOT synchronized!
597 *******************************************************************************/
603 classcache_name_entry *entry;
604 classcache_name_entry *next;
606 for (slot=0; slot<classcache_hash.size; ++slot) {
607 for (entry=(classcache_name_entry *)classcache_hash.ptr[slot];
611 next = entry->hashlink;
612 classcache_free_name_entry(entry);
616 MFREE(classcache_hash.ptr,voidptr,classcache_hash.size);
617 classcache_hash.size = 0;
618 classcache_hash.entries = 0;
619 classcache_hash.ptr = NULL;
622 /* classcache_add_constraint ***************************************************
624 Add a loading constraint
627 a................first initiating loader
628 b................second initiating loader
629 classname........class name
632 true.............everything ok, the constraint has been added,
633 false............an exception has been thrown.
635 Note: synchronized with global tablelock
637 *******************************************************************************/
640 classcache_add_constraint(classloader *a,classloader *b,utf *classname)
642 classcache_name_entry *en;
643 classcache_class_entry *clsenA;
644 classcache_class_entry *clsenB;
646 CLASSCACHE_ASSERT(classname);
648 #ifdef CLASSCACHE_VERBOSE
649 fprintf(stderr,"classcache_add_constraint(%p,%p,",(void*)a,(void*)b);
650 utf_fprint_classname(stderr,classname);
651 fprintf(stderr,")\n");
654 /* a constraint with a == b is trivially satisfied */
660 en = classcache_new_name(classname);
662 CLASSCACHE_ASSERT(en);
664 /* find the entry loaded by / constrained to each loader */
665 clsenA = classcache_find_loader(en,a);
666 clsenB = classcache_find_loader(en,b);
668 if (clsenA && clsenB) {
669 /* { both loaders have corresponding entries } */
671 /* if the entries are the same, the constraint is already recorded */
672 if (clsenA == clsenB)
675 /* check if the entries can be merged */
676 if (clsenA->classobj && clsenB->classobj && clsenA->classobj != clsenB->classobj) {
677 /* no, the constraint is violated */
678 *exceptionptr = new_exception_message(string_java_lang_LinkageError,
679 "loading constraint violated XXX add message");
680 goto return_exception;
683 /* yes, merge the entries */
684 /* clsenB will be merged into clsenA */
685 clsenA->loaders = classcache_merge_loaders(clsenA->loaders,
688 clsenA->constraints = classcache_merge_loaders(clsenA->constraints,
689 clsenB->constraints);
691 if (!clsenA->classobj)
692 clsenA->classobj = clsenB->classobj;
694 /* remove clsenB from the list of class entries */
695 classcache_remove_class_entry(en,clsenB);
698 /* { at most one of the loaders has a corresponding entry } */
700 /* set clsenA to the single class entry we have */
705 /* { no loader has a corresponding entry } */
707 /* create a new class entry with the constraint (a,b,en->name) */
708 clsenA = NEW(classcache_class_entry);
709 clsenA->classobj = NULL;
710 clsenA->loaders = NULL;
711 clsenA->constraints = classcache_new_loader_entry(b,NULL);
712 clsenA->constraints = classcache_new_loader_entry(a,clsenA->constraints);
714 clsenA->next = en->classes;
715 en->classes = clsenA;
718 /* make b the loader that has no corresponding entry */
722 /* loader b must be added to entry clsenA */
723 clsenA->constraints = classcache_new_loader_entry(b,clsenA->constraints);
733 return false; /* exception */
736 /*============================================================================*/
738 /*============================================================================*/
740 /* classcache_debug_dump *******************************************************
742 Print the contents of the loaded class cache to a stream
745 file.............output stream
747 Note: synchronized with global tablelock
749 *******************************************************************************/
752 classcache_debug_dump(FILE *file)
754 classcache_name_entry *c;
755 classcache_class_entry *clsen;
756 classcache_loader_entry *lden;
761 fprintf(file,"\n=== [loaded class cache] =====================================\n\n");
762 fprintf(file,"hash size : %d\n",classcache_hash.size);
763 fprintf(file,"hash entries: %d\n",classcache_hash.entries);
766 for (slot=0; slot<classcache_hash.size; ++slot) {
767 c = (classcache_name_entry *) classcache_hash.ptr[slot];
769 for (; c; c=c->hashlink) {
770 utf_fprint_classname(file,c->name);
773 /* iterate over all class entries */
774 for (clsen=c->classes; clsen; clsen=clsen->next) {
775 fprintf(file," %s\n",(clsen->classobj) ? "loaded" : "unresolved");
776 fprintf(file," loaders:");
777 for (lden=clsen->loaders; lden; lden=lden->next) {
778 fprintf(file," %p",(void *)lden->loader);
780 fprintf(file,"\n constraints:");
781 for (lden=clsen->constraints; lden; lden=lden->next) {
782 fprintf(file," %p",(void *)lden->loader);
788 fprintf(file,"\n==============================================================\n\n");
794 * These are local overrides for various environment variables in Emacs.
795 * Please do not remove this and leave it at the end of the file, where
796 * Emacs will automagically detect them.
797 * ---------------------------------------------------------------------
800 * indent-tabs-mode: t
804 * vim:noexpandtab:sw=4:ts=4: