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 2186 2005-04-02 00:43:25Z 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);
391 en = classcache_new_name(cls->name);
393 CLASSCACHE_ASSERT(en);
395 /* iterate over all class entries */
396 for (clsen=en->classes; clsen; clsen=clsen->next) {
398 #ifdef CLASSCACHE_DEBUG
399 /* check if this entry has already been loaded by initloader */
400 /* It never should have been loaded before! */
401 for (lden=clsen->loaders; lden; lden=lden->next) {
402 if (lden->loader == initloader)
403 CLASSCACHE_ASSERT(false);
407 /* check if initloader is constrained to this entry */
408 for (lden=clsen->constraints; lden; lden=lden->next) {
409 if (lden->loader == initloader) {
410 /* we have to use this entry */
411 /* check if is has already been resolved to another class */
412 if (clsen->classobj && clsen->classobj != cls) {
413 /* a loading constraint is violated */
414 *exceptionptr = new_exception_message(string_java_lang_LinkageError,
415 "loading constraint violated XXX add message");
416 goto return_exception;
419 /* record initloader as initiating loader */
420 clsen->loaders = classcache_new_loader_entry(initloader,clsen->loaders);
422 /* record the loaded class object */
423 clsen->classobj = cls;
432 /* create a new class entry for this class object with */
433 /* initiating loader initloader */
435 clsen = NEW(classcache_class_entry);
436 clsen->classobj = cls;
437 clsen->loaders = classcache_new_loader_entry(initloader,NULL);
438 clsen->constraints = NULL;
440 clsen->next = en->classes;
449 return false; /* exception */
452 /* classcache_find_loader ******************************************************
454 Find the class entry loaded by or constrained to a given loader
455 (internally used helper function)
458 entry............the classcache_name_entry
459 loader...........the loader to look for
462 the classcache_class_entry for the given loader, or
463 NULL if no entry was found
465 *******************************************************************************/
467 static classcache_class_entry *
468 classcache_find_loader(classcache_name_entry *entry,classloader *loader)
470 classcache_class_entry *clsen;
471 classcache_loader_entry *lden;
473 CLASSCACHE_ASSERT(entry);
475 /* iterate over all class entries */
476 for (clsen=entry->classes; clsen; clsen=clsen->next) {
478 /* check if this entry has already been loaded by initloader */
479 for (lden=clsen->loaders; lden; lden=lden->next) {
480 if (lden->loader == loader)
481 return clsen; /* found */
484 /* check if loader is constrained to this entry */
485 for (lden=clsen->constraints; lden; lden=lden->next) {
486 if (lden->loader == loader)
487 return clsen; /* found */
495 /* classcache_free_class_entry *************************************************
497 Free the memory used by a class entry
500 clsen............the classcache_class_entry to free
502 *******************************************************************************/
505 classcache_free_class_entry(classcache_class_entry *clsen)
507 classcache_loader_entry *lden;
508 classcache_loader_entry *next;
510 CLASSCACHE_ASSERT(clsen);
512 for (lden=clsen->loaders; lden; lden=next) {
514 FREE(lden,classcache_loader_entry);
516 for (lden=clsen->constraints; lden; lden=next) {
518 FREE(lden,classcache_loader_entry);
521 FREE(clsen,classcache_class_entry);
524 /* classcache_remove_class_entry ***********************************************
526 Remove a classcache_class_entry from the list of possible resolution of
528 (internally used helper function)
531 entry............the classcache_name_entry
532 clsen............the classcache_class_entry to remove
534 *******************************************************************************/
537 classcache_remove_class_entry(classcache_name_entry *entry,
538 classcache_class_entry *clsen)
540 classcache_class_entry **chain;
542 CLASSCACHE_ASSERT(entry);
543 CLASSCACHE_ASSERT(clsen);
545 chain = &(entry->classes);
547 if (*chain == clsen) {
548 *chain = clsen->next;
549 classcache_free_class_entry(clsen);
552 chain = &((*chain)->next);
556 /* classcache_free_name_entry **************************************************
558 Free the memory used by a name entry
561 entry............the classcache_name_entry to free
563 *******************************************************************************/
566 classcache_free_name_entry(classcache_name_entry *entry)
568 classcache_class_entry *clsen;
569 classcache_class_entry *next;
571 CLASSCACHE_ASSERT(entry);
573 for (clsen=entry->classes; clsen; clsen=next) {
575 classcache_free_class_entry(clsen);
578 FREE(entry,classcache_name_entry);
581 /* classcache_free *************************************************************
583 Free the memory used by the class cache
586 The class cache may not be used any more after this call, except
587 when it is reinitialized with classcache_init.
589 Note: NOT synchronized!
591 *******************************************************************************/
597 classcache_name_entry *entry;
598 classcache_name_entry *next;
600 for (slot=0; slot<classcache_hash.size; ++slot) {
601 for (entry=(classcache_name_entry *)classcache_hash.ptr[slot];
605 next = entry->hashlink;
606 classcache_free_name_entry(entry);
610 MFREE(classcache_hash.ptr,voidptr,classcache_hash.size);
611 classcache_hash.size = 0;
612 classcache_hash.entries = 0;
613 classcache_hash.ptr = NULL;
616 /* classcache_add_constraint ***************************************************
618 Add a loading constraint
621 a................first initiating loader
622 b................second initiating loader
623 classname........class name
626 true.............everything ok, the constraint has been added,
627 false............an exception has been thrown.
629 Note: synchronized with global tablelock
631 *******************************************************************************/
634 classcache_add_constraint(classloader *a,classloader *b,utf *classname)
636 classcache_name_entry *en;
637 classcache_class_entry *clsenA;
638 classcache_class_entry *clsenB;
640 CLASSCACHE_ASSERT(classname);
642 #ifdef CLASSCACHE_VERBOSE
643 fprintf(stderr,"classcache_add_constraint(%p,%p,",(void*)a,(void*)b);
644 utf_fprint_classname(stderr,classname);
645 fprintf(stderr,")\n");
648 /* a constraint with a == b is trivially satisfied */
654 en = classcache_new_name(classname);
656 CLASSCACHE_ASSERT(en);
658 /* find the entry loaded by / constrained to each loader */
659 clsenA = classcache_find_loader(en,a);
660 clsenB = classcache_find_loader(en,b);
662 if (clsenA && clsenB) {
663 /* { both loaders have corresponding entries } */
665 /* if the entries are the same, the constraint is already recorded */
666 if (clsenA == clsenB)
669 /* check if the entries can be merged */
670 if (clsenA->classobj && clsenB->classobj && clsenA->classobj != clsenB->classobj) {
671 /* no, the constraint is violated */
672 *exceptionptr = new_exception_message(string_java_lang_LinkageError,
673 "loading constraint violated XXX add message");
674 goto return_exception;
677 /* yes, merge the entries */
678 /* clsenB will be merged into clsenA */
679 clsenA->loaders = classcache_merge_loaders(clsenA->loaders,
682 clsenA->constraints = classcache_merge_loaders(clsenA->constraints,
683 clsenB->constraints);
685 if (!clsenA->classobj)
686 clsenA->classobj = clsenB->classobj;
688 /* remove clsenB from the list of class entries */
689 classcache_remove_class_entry(en,clsenB);
692 /* { at most one of the loaders has a corresponding entry } */
694 /* set clsenA to the single class entry we have */
699 /* { no loader has a corresponding entry } */
701 /* create a new class entry with the constraint (a,b,en->name) */
702 clsenA = NEW(classcache_class_entry);
703 clsenA->classobj = NULL;
704 clsenA->loaders = NULL;
705 clsenA->constraints = classcache_new_loader_entry(b,NULL);
706 clsenA->constraints = classcache_new_loader_entry(a,clsenA->constraints);
708 clsenA->next = en->classes;
709 en->classes = clsenA;
712 /* make b the loader that has no corresponding entry */
716 /* loader b must be added to entry clsenA */
717 clsenA->constraints = classcache_new_loader_entry(b,clsenA->constraints);
727 return false; /* exception */
730 /*============================================================================*/
732 /*============================================================================*/
734 /* classcache_debug_dump *******************************************************
736 Print the contents of the loaded class cache to a stream
739 file.............output stream
741 Note: synchronized with global tablelock
743 *******************************************************************************/
746 classcache_debug_dump(FILE *file)
748 classcache_name_entry *c;
749 classcache_class_entry *clsen;
750 classcache_loader_entry *lden;
755 fprintf(file,"\n=== [loaded class cache] =====================================\n\n");
756 fprintf(file,"hash size : %d\n",classcache_hash.size);
757 fprintf(file,"hash entries: %d\n",classcache_hash.entries);
760 for (slot=0; slot<classcache_hash.size; ++slot) {
761 c = (classcache_name_entry *) classcache_hash.ptr[slot];
763 for (; c; c=c->hashlink) {
764 utf_fprint_classname(file,c->name);
767 /* iterate over all class entries */
768 for (clsen=c->classes; clsen; clsen=clsen->next) {
769 fprintf(file," %s\n",(clsen->classobj) ? "loaded" : "unresolved");
770 fprintf(file," loaders:");
771 for (lden=clsen->loaders; lden; lden=lden->next) {
772 fprintf(file," %p",(void *)lden->loader);
774 fprintf(file,"\n constraints:");
775 for (lden=clsen->constraints; lden; lden=lden->next) {
776 fprintf(file," %p",(void *)lden->loader);
782 fprintf(file,"\n==============================================================\n\n");
788 * These are local overrides for various environment variables in Emacs.
789 * Please do not remove this and leave it at the end of the file, where
790 * Emacs will automagically detect them.
791 * ---------------------------------------------------------------------
794 * indent-tabs-mode: t
798 * vim:noexpandtab:sw=4:ts=4: