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 2181 2005-04-01 16:53:33Z 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 /*============================================================================*/
50 #define CLASSCACHE_DEBUG
53 #ifdef CLASSCACHE_DEBUG
54 #define CLASSCACHE_ASSERT(cond) assert(cond)
56 #define CLASSCACHE_ASSERT(cond)
59 /*============================================================================*/
60 /* THREAD-SAFE LOCKING */
61 /*============================================================================*/
63 /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
64 /* CAUTION: The static functions below are */
65 /* NOT synchronized! */
66 /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
68 #if defined(USE_THREADS) && defined(NATIVE_THREADS)
69 # define CLASSCACHE_LOCK() tables_lock()
70 # define CLASSCACHE_UNLOCK() tables_unlock()
72 # define CLASSCACHE_LOCK()
73 # define CLASSCACHE_UNLOCK()
76 /*============================================================================*/
77 /* GLOBAL VARIABLES */
78 /*============================================================================*/
80 static hashtable classcache_hash;
82 /*============================================================================*/
84 /*============================================================================*/
86 /* classcache_init *************************************************************
88 Initialize the loaded class cache
90 Note: NOT synchronized!
92 *******************************************************************************/
97 init_hashtable(&classcache_hash,CLASSCACHE_INIT_SIZE);
100 /* classcache_new_loader_entry *************************************************
102 Create a new classcache_loader_entry struct
103 (internally used helper function)
106 loader...........the ClassLoader object
107 next.............the next classcache_loader_entry
110 the new classcache_loader_entry
112 *******************************************************************************/
114 static classcache_loader_entry *
115 classcache_new_loader_entry(classloader *loader,classcache_loader_entry *next)
117 classcache_loader_entry *lden;
119 lden = NEW(classcache_loader_entry);
120 lden->loader = loader;
126 /* classcache_merge_loaders ****************************************************
128 Merge two lists of loaders into one
129 (internally used helper function)
132 lista............first list (may be NULL)
133 listb............second list (may be NULL)
136 the merged list (may be NULL)
139 The lists given as arguments are destroyed!
141 *******************************************************************************/
143 static classcache_loader_entry *
144 classcache_merge_loaders(classcache_loader_entry *lista,
145 classcache_loader_entry *listb)
147 classcache_loader_entry *result;
148 classcache_loader_entry *ldenA;
149 classcache_loader_entry *ldenB;
150 classcache_loader_entry **chain;
152 /* XXX This is a quadratic algorithm. If this ever
153 * becomes a problem, the loader lists should be
154 * stored as sorted lists and merged in linear time. */
159 for (ldenA=lista; ldenA; ldenA=ldenA->next) {
161 for (ldenB=listb; ldenB; ldenB=ldenB->next) {
162 if (ldenB->loader == ldenA->loader)
166 /* this loader is only in lista */
168 chain = &(ldenA->next);
171 /* XXX free the duplicated element */
175 /* concat listb to the result */
181 /* classcache_lookup_name ******************************************************
183 Lookup a name in the first level of the cache
184 (internally used helper function)
187 name.............the name to look up
190 a pointer to the classcache_name_entry for this name, or
191 null if no entry was found.
193 *******************************************************************************/
195 static classcache_name_entry *
196 classcache_lookup_name(utf *name)
198 classcache_name_entry * c; /* hash table element */
199 u4 key; /* hashkey computed from classname */
200 u4 slot; /* slot in hashtable */
203 key = utf_hashkey(name->text, name->blength);
204 slot = key & (classcache_hash.size - 1);
205 c = classcache_hash.ptr[slot];
207 /* search external hash chain for the entry */
209 if (c->name->blength == name->blength) {
210 for (i = 0; i < name->blength; i++)
211 if (name->text[i] != c->name->text[i]) goto nomatch;
213 /* entry found in hashtable */
218 c = c->hashlink; /* next element in external chain */
225 /* classcache_new_name *********************************************************
227 Return a classcache_name_entry for the given name. The entry is created
228 if it is not already in the cache.
229 (internally used helper function)
232 name.............the name to look up / create an entry for
235 a pointer to the classcache_name_entry for this name
237 *******************************************************************************/
239 static classcache_name_entry *
240 classcache_new_name(utf *name)
242 classcache_name_entry * c; /* hash table element */
243 u4 key; /* hashkey computed from classname */
244 u4 slot; /* slot in hashtable */
247 key = utf_hashkey(name->text, name->blength);
248 slot = key & (classcache_hash.size - 1);
249 c = classcache_hash.ptr[slot];
251 /* search external hash chain for the entry */
253 if (c->name->blength == name->blength) {
254 for (i = 0; i < name->blength; i++)
255 if (name->text[i] != c->name->text[i]) goto nomatch;
257 /* entry found in hashtable */
262 c = c->hashlink; /* next element in external chain */
265 /* location in hashtable found, create new entry */
267 c = NEW(classcache_name_entry);
272 /* insert entry into hashtable */
273 c->hashlink = classcache_hash.ptr[slot];
274 classcache_hash.ptr[slot] = c;
276 /* update number of hashtable-entries */
277 classcache_hash.entries++;
279 if (classcache_hash.entries > (classcache_hash.size * 2)) {
281 /* reorganization of hashtable, average length of
282 the external chains is approx. 2 */
285 classcache_name_entry *c;
286 hashtable newhash; /* the new hashtable */
288 /* create new hashtable, double the size */
289 init_hashtable(&newhash, classcache_hash.size * 2);
290 newhash.entries = classcache_hash.entries;
292 /* transfer elements to new hashtable */
293 for (i = 0; i < classcache_hash.size; i++) {
294 c = (classcache_name_entry *) classcache_hash.ptr[i];
296 classcache_name_entry *nextc = c->hashlink;
297 u4 slot = (utf_hashkey(c->name->text, c->name->blength)) & (newhash.size - 1);
299 c->hashlink = newhash.ptr[slot];
300 newhash.ptr[slot] = c;
306 /* dispose old table */
307 MFREE(classcache_hash.ptr, void*, classcache_hash.size);
308 classcache_hash = newhash;
314 /* classcache_lookup ***********************************************************
316 Lookup a possibly loaded class
319 initloader.......initiating loader for resolving the class name
320 classname........class name to look up
323 The return value is a pointer to the cached class object,
324 or NULL, if the class is not in the cache.
326 Note: synchronized with global tablelock
328 *******************************************************************************/
331 classcache_lookup(classloader *initloader,utf *classname)
333 classcache_name_entry *en;
334 classcache_class_entry *clsen;
335 classcache_loader_entry *lden;
336 classinfo *cls = NULL;
340 en = classcache_lookup_name(classname);
343 /* iterate over all class entries */
344 for (clsen=en->classes; clsen; clsen=clsen->next) {
345 /* check if this entry has been loaded by initloader */
346 for (lden=clsen->loaders; lden; lden=lden->next) {
347 if (lden->loader == initloader) {
348 /* found the loaded class entry */
349 CLASSCACHE_ASSERT(clsen->classobj);
350 cls = clsen->classobj;
361 /* classcache_store ************************************************************
366 initloader.......initiating loader used to load the class
367 cls..............class object to cache
370 true.............everything ok, the class was stored in
371 the cache if necessary,
372 false............an exception has been thrown.
374 Note: synchronized with global tablelock
376 *******************************************************************************/
379 classcache_store(classloader *initloader,classinfo *cls)
381 classcache_name_entry *en;
382 classcache_class_entry *clsen;
383 classcache_loader_entry *lden;
385 CLASSCACHE_ASSERT(cls);
389 en = classcache_new_name(cls->name);
391 CLASSCACHE_ASSERT(en);
393 /* iterate over all class entries */
394 for (clsen=en->classes; clsen; clsen=clsen->next) {
396 #ifdef CLASSCACHE_DEBUG
397 /* check if this entry has already been loaded by initloader */
398 /* It never should have been loaded before! */
399 for (lden=clsen->loaders; lden; lden=lden->next) {
400 if (lden->loader == initloader)
401 CLASSCACHE_ASSERT(false);
405 /* check if initloader is constrained to this entry */
406 for (lden=clsen->constraints; lden; lden=lden->next) {
407 if (lden->loader == initloader) {
408 /* we have to use this entry */
409 /* check if is has already been resolved to another class */
410 if (clsen->classobj && clsen->classobj != cls) {
411 /* a loading constraint is violated */
412 *exceptionptr = new_exception_message(string_java_lang_LinkageError,
413 "loading constraint violated XXX add message");
414 goto return_exception;
417 /* record initloader as initiating loader */
418 clsen->loaders = classcache_new_loader_entry(initloader,clsen->loaders);
420 /* record the loaded class object */
421 clsen->classobj = cls;
430 /* create a new class entry for this class object with */
431 /* initiating loader initloader */
433 clsen = NEW(classcache_class_entry);
434 clsen->classobj = cls;
435 clsen->loaders = classcache_new_loader_entry(initloader,NULL);
436 clsen->constraints = NULL;
438 clsen->next = en->classes;
447 return false; /* exception */
450 /* classcache_find_loader ******************************************************
452 Find the class entry loaded by or constrained to a given loader
453 (internally used helper function)
456 entry............the classcache_name_entry
457 loader...........the loader to look for
460 the classcache_class_entry for the given loader, or
461 NULL if no entry was found
463 *******************************************************************************/
465 static classcache_class_entry *
466 classcache_find_loader(classcache_name_entry *entry,classloader *loader)
468 classcache_class_entry *clsen;
469 classcache_loader_entry *lden;
471 CLASSCACHE_ASSERT(entry);
473 /* iterate over all class entries */
474 for (clsen=entry->classes; clsen; clsen=clsen->next) {
476 /* check if this entry has already been loaded by initloader */
477 for (lden=clsen->loaders; lden; lden=lden->next) {
478 if (lden->loader == loader)
479 return clsen; /* found */
482 /* check if loader is constrained to this entry */
483 for (lden=clsen->constraints; lden; lden=lden->next) {
484 if (lden->loader == loader)
485 return clsen; /* found */
493 /* classcache_free_class_entry *************************************************
495 Free the memory used by a class entry
498 clsen............the classcache_class_entry to free
500 *******************************************************************************/
503 classcache_free_class_entry(classcache_class_entry *clsen)
505 classcache_loader_entry *lden;
506 classcache_loader_entry *next;
508 CLASSCACHE_ASSERT(clsen);
510 for (lden=clsen->loaders; lden; lden=next) {
512 FREE(lden,classcache_loader_entry);
514 for (lden=clsen->constraints; lden; lden=next) {
516 FREE(lden,classcache_loader_entry);
519 FREE(clsen,classcache_class_entry);
522 /* classcache_remove_class_entry ***********************************************
524 Remove a classcache_class_entry from the list of possible resolution of
526 (internally used helper function)
529 entry............the classcache_name_entry
530 clsen............the classcache_class_entry to remove
532 *******************************************************************************/
535 classcache_remove_class_entry(classcache_name_entry *entry,
536 classcache_class_entry *clsen)
538 classcache_class_entry **chain;
540 CLASSCACHE_ASSERT(entry);
541 CLASSCACHE_ASSERT(clsen);
543 chain = &(entry->classes);
545 if (*chain == clsen) {
546 *chain = clsen->next;
547 classcache_free_class_entry(clsen);
550 chain = &((*chain)->next);
554 /* classcache_free_name_entry **************************************************
556 Free the memory used by a name entry
559 entry............the classcache_name_entry to free
561 *******************************************************************************/
564 classcache_free_name_entry(classcache_name_entry *entry)
566 classcache_class_entry *clsen;
567 classcache_class_entry *next;
569 CLASSCACHE_ASSERT(entry);
571 for (clsen=entry->classes; clsen; clsen=next) {
573 classcache_free_class_entry(clsen);
576 FREE(entry,classcache_name_entry);
579 /* classcache_free *************************************************************
581 Free the memory used by the class cache
584 The class cache may not be used any more after this call, except
585 when it is reinitialized with classcache_init.
587 Note: NOT synchronized!
589 *******************************************************************************/
595 classcache_name_entry *entry;
596 classcache_name_entry *next;
598 for (slot=0; slot<classcache_hash.size; ++slot) {
599 for (entry=(classcache_name_entry *)classcache_hash.ptr[slot];
603 next = entry->hashlink;
604 classcache_free_name_entry(entry);
608 MFREE(classcache_hash.ptr,voidptr,classcache_hash.size);
609 classcache_hash.size = 0;
610 classcache_hash.entries = 0;
611 classcache_hash.ptr = NULL;
614 /* classcache_add_constraint ***************************************************
616 Add a loading constraint
619 a................first initiating loader
620 b................second initiating loader
621 classname........class name
624 true.............everything ok, the constraint has been added,
625 false............an exception has been thrown.
627 Note: synchronized with global tablelock
629 *******************************************************************************/
632 classcache_add_constraint(classloader *a,classloader *b,utf *classname)
634 classcache_name_entry *en;
635 classcache_class_entry *clsenA;
636 classcache_class_entry *clsenB;
638 CLASSCACHE_ASSERT(classname);
640 #ifdef CLASSCACHE_DEBUG
641 fprintf(stderr,"classcache_add_constraint(%p,%p,",a,b);
642 utf_fprint_classname(stderr,classname);
643 fprintf(stderr,")\n");
646 /* a constraint with a == b is trivially satisfied */
652 en = classcache_new_name(classname);
654 CLASSCACHE_ASSERT(en);
656 /* find the entry loaded by / constrained to each loader */
657 clsenA = classcache_find_loader(en,a);
658 clsenB = classcache_find_loader(en,b);
660 if (clsenA && clsenB) {
661 /* { both loaders have corresponding entries } */
663 /* if the entries are the same, the constraint is already recorded */
664 if (clsenA == clsenB)
667 /* check if the entries can be merged */
668 if (clsenA->classobj && clsenB->classobj && clsenA->classobj != clsenB->classobj) {
669 /* no, the constraint is violated */
670 *exceptionptr = new_exception_message(string_java_lang_LinkageError,
671 "loading constraint violated XXX add message");
672 goto return_exception;
675 /* yes, merge the entries */
676 /* clsenB will be merged into clsenA */
677 clsenA->loaders = classcache_merge_loaders(clsenA->loaders,
680 clsenA->constraints = classcache_merge_loaders(clsenA->constraints,
681 clsenB->constraints);
683 if (!clsenA->classobj)
684 clsenA->classobj = clsenB->classobj;
686 /* remove clsenB from the list of class entries */
687 classcache_remove_class_entry(en,clsenB);
690 /* { at most one of the loaders has a corresponding entry } */
692 /* set clsenA to the single class entry we have */
697 /* { no loader has a corresponding entry } */
699 /* create a new class entry with the constraint (a,b,en->name) */
700 clsenA = NEW(classcache_class_entry);
701 clsenA->classobj = NULL;
702 clsenA->loaders = NULL;
703 clsenA->constraints = classcache_new_loader_entry(b,NULL);
704 clsenA->constraints = classcache_new_loader_entry(a,clsenA->constraints);
706 clsenA->next = en->classes;
707 en->classes = clsenA;
710 /* make b the loader that has no corresponding entry */
714 /* loader b must be added to entry clsenA */
715 clsenA->constraints = classcache_new_loader_entry(b,clsenA->constraints);
725 return false; /* exception */
728 /*============================================================================*/
730 /*============================================================================*/
732 /* classcache_debug_dump *******************************************************
734 Print the contents of the loaded class cache to a stream
737 file.............output stream
739 Note: synchronized with global tablelock
741 *******************************************************************************/
744 classcache_debug_dump(FILE *file)
746 classcache_name_entry *c;
747 classcache_class_entry *clsen;
748 classcache_loader_entry *lden;
753 fprintf(file,"\n=== [loaded class cache] =====================================\n\n");
754 fprintf(file,"hash size : %d\n",classcache_hash.size);
755 fprintf(file,"hash entries: %d\n",classcache_hash.entries);
758 for (slot=0; slot<classcache_hash.size; ++slot) {
759 c = (classcache_name_entry *) classcache_hash.ptr[slot];
761 for (; c; c=c->hashlink) {
762 utf_fprint_classname(file,c->name);
765 /* iterate over all class entries */
766 for (clsen=c->classes; clsen; clsen=clsen->next) {
767 fprintf(file," %s\n",(clsen->classobj) ? "loaded" : "unresolved");
768 fprintf(file," loaders:");
769 for (lden=clsen->loaders; lden; lden=lden->next) {
770 fprintf(file," %p",(void *)lden->loader);
772 fprintf(file,"\n constraints:");
773 for (lden=clsen->constraints; lden; lden=lden->next) {
774 fprintf(file," %p",(void *)lden->loader);
780 fprintf(file,"\n==============================================================\n\n");
786 * These are local overrides for various environment variables in Emacs.
787 * Please do not remove this and leave it at the end of the file, where
788 * Emacs will automagically detect them.
789 * ---------------------------------------------------------------------
792 * indent-tabs-mode: t
796 * vim:noexpandtab:sw=4:ts=4: