changed exception types and innerclass references to classref_or_classinfo
[cacao.git] / src / vm / classcache.c
1 /* vm/classcache.c - loaded class cache and loading constraints
2
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
7
8    This file is part of CACAO.
9
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.
14
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.
19
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
23    02111-1307, USA.
24
25    Contact: cacao@complang.tuwien.ac.at
26
27    Authors: Edwin Steiner
28
29    Changes:
30
31    $Id: classcache.c 2190 2005-04-02 10:07:44Z edwin $
32
33 */
34
35 #include <assert.h>
36 #include "vm/classcache.h"
37 #include "vm/utf8.h"
38 #include "vm/tables.h"
39 #include "vm/exceptions.h"
40 #include "mm/memory.h"
41
42 /* initial number of slots in the classcache hash table */
43 #define CLASSCACHE_INIT_SIZE  2048
44
45 /*============================================================================*/
46 /* DEBUG HELPERS                                                              */
47 /*============================================================================*/
48
49 /*#define CLASSCACHE_VERBOSE*/
50
51 #ifndef NDEBUG
52 #define CLASSCACHE_DEBUG
53 #endif
54
55 #ifdef CLASSCACHE_DEBUG
56 #define CLASSCACHE_ASSERT(cond)  assert(cond)
57 #else
58 #define CLASSCACHE_ASSERT(cond)
59 #endif
60
61 /*============================================================================*/
62 /* THREAD-SAFE LOCKING                                                        */
63 /*============================================================================*/
64
65     /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
66     /* CAUTION: The static functions below are */
67     /*          NOT synchronized!              */
68     /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!*/
69
70 #if defined(USE_THREADS) && defined(NATIVE_THREADS)
71 #  define CLASSCACHE_LOCK()    tables_lock()
72 #  define CLASSCACHE_UNLOCK()  tables_unlock()
73 #else
74 #  define CLASSCACHE_LOCK()
75 #  define CLASSCACHE_UNLOCK()
76 #endif
77
78 /*============================================================================*/
79 /* GLOBAL VARIABLES                                                           */
80 /*============================================================================*/
81
82 static hashtable classcache_hash;
83
84 /*============================================================================*/
85 /*                                                                            */
86 /*============================================================================*/
87
88 /* classcache_init *************************************************************
89  
90    Initialize the loaded class cache
91
92    Note: NOT synchronized!
93   
94 *******************************************************************************/
95
96 void 
97 classcache_init()
98 {
99         init_hashtable(&classcache_hash,CLASSCACHE_INIT_SIZE);
100 }
101
102 /* classcache_new_loader_entry *************************************************
103  
104    Create a new classcache_loader_entry struct
105    (internally used helper function)
106   
107    IN:
108        loader...........the ClassLoader object
109            next.............the next classcache_loader_entry
110
111    RETURN VALUE:
112        the new classcache_loader_entry
113   
114 *******************************************************************************/
115
116 static classcache_loader_entry *
117 classcache_new_loader_entry(classloader *loader,classcache_loader_entry *next)
118 {
119         classcache_loader_entry *lden;
120
121         lden = NEW(classcache_loader_entry);
122         lden->loader = loader;
123         lden->next = next;
124
125         return lden;
126 }
127
128 /* classcache_merge_loaders ****************************************************
129  
130    Merge two lists of loaders into one
131    (internally used helper function)
132   
133    IN:
134        lista............first list (may be NULL)
135            listb............second list (may be NULL)
136
137    RETURN VALUE:
138        the merged list (may be NULL)
139
140    NOTE:
141        The lists given as arguments are destroyed!
142   
143 *******************************************************************************/
144
145 static classcache_loader_entry *
146 classcache_merge_loaders(classcache_loader_entry *lista,
147                                  classcache_loader_entry *listb)
148 {
149         classcache_loader_entry *result;
150         classcache_loader_entry *ldenA;
151         classcache_loader_entry *ldenB;
152         classcache_loader_entry **chain;
153         
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. */
157
158         result = NULL;
159         chain = &result;
160
161         for (ldenA=lista; ldenA; ldenA=ldenA->next) {
162                 
163                 for (ldenB=listb; ldenB; ldenB=ldenB->next) {
164                         if (ldenB->loader == ldenA->loader)
165                                 goto common_element;
166                 }
167
168                 /* this loader is only in lista */
169                 *chain = ldenA;
170                 chain = &(ldenA->next);
171
172 common_element:
173                 /* XXX free the duplicated element */
174                 ;
175         }
176
177         /* concat listb to the result */
178         *chain = listb;
179
180         return result;
181 }
182
183 /* classcache_lookup_name ******************************************************
184  
185    Lookup a name in the first level of the cache
186    (internally used helper function)
187    
188    IN:
189        name.............the name to look up
190   
191    RETURN VALUE:
192        a pointer to the classcache_name_entry for this name, or
193        null if no entry was found.
194            
195 *******************************************************************************/
196  
197 static classcache_name_entry *
198 classcache_lookup_name(utf *name)
199 {
200         classcache_name_entry * c;     /* hash table element */
201         u4 key;           /* hashkey computed from classname */
202         u4 slot;          /* slot in hashtable               */
203         u2 i;
204
205         key  = utf_hashkey(name->text, name->blength);
206         slot = key & (classcache_hash.size - 1);
207         c    = classcache_hash.ptr[slot];
208
209         /* search external hash chain for the entry */
210         while (c) {
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;
214                                                 
215                         /* entry found in hashtable */
216                         return c;
217                 }
218                         
219         nomatch:
220                 c = c->hashlink; /* next element in external chain */
221         }
222
223         /* not found */
224         return NULL;
225 }
226
227 /* classcache_new_name *********************************************************
228  
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)
232    
233    IN:
234        name.............the name to look up / create an entry for
235   
236    RETURN VALUE:
237        a pointer to the classcache_name_entry for this name
238            
239 *******************************************************************************/
240  
241 static classcache_name_entry *
242 classcache_new_name(utf *name)
243 {
244         classcache_name_entry * c;     /* hash table element */
245         u4 key;           /* hashkey computed from classname */
246         u4 slot;          /* slot in hashtable               */
247         u2 i;
248
249         key  = utf_hashkey(name->text, name->blength);
250         slot = key & (classcache_hash.size - 1);
251         c    = classcache_hash.ptr[slot];
252
253         /* search external hash chain for the entry */
254         while (c) {
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;
258                                                 
259                         /* entry found in hashtable */
260                         return c;
261                 }
262                         
263         nomatch:
264                 c = c->hashlink; /* next element in external chain */
265         }
266
267         /* location in hashtable found, create new entry */
268
269         c = NEW(classcache_name_entry);
270
271         c->name = name;
272         c->classes = NULL;
273
274         /* insert entry into hashtable */
275         c->hashlink = classcache_hash.ptr[slot];
276         classcache_hash.ptr[slot] = c;
277
278         /* update number of hashtable-entries */
279         classcache_hash.entries++;
280
281         if (classcache_hash.entries > (classcache_hash.size * 2)) {
282
283                 /* reorganization of hashtable, average length of 
284                    the external chains is approx. 2                */  
285
286                 u4 i;
287                 classcache_name_entry *c;
288                 hashtable newhash;  /* the new hashtable */
289
290                 /* create new hashtable, double the size */
291                 init_hashtable(&newhash, classcache_hash.size * 2);
292                 newhash.entries = classcache_hash.entries;
293
294                 /* transfer elements to new hashtable */
295                 for (i = 0; i < classcache_hash.size; i++) {
296                         c = (classcache_name_entry *) classcache_hash.ptr[i];
297                         while (c) {
298                                 classcache_name_entry *nextc = c->hashlink;
299                                 u4 slot = (utf_hashkey(c->name->text, c->name->blength)) & (newhash.size - 1);
300                                                 
301                                 c->hashlink = newhash.ptr[slot];
302                                 newhash.ptr[slot] = c;
303
304                                 c = nextc;
305                         }
306                 }
307         
308                 /* dispose old table */ 
309                 MFREE(classcache_hash.ptr, void*, classcache_hash.size);
310                 classcache_hash = newhash;
311         }
312
313         return c;
314 }
315
316 /* classcache_lookup ***********************************************************
317  
318    Lookup a possibly loaded class
319   
320    IN:
321        initloader.......initiating loader for resolving the class name
322        classname........class name to look up
323   
324    RETURN VALUE:
325        The return value is a pointer to the cached class object,
326        or NULL, if the class is not in the cache.
327
328    Note: synchronized with global tablelock
329    
330 *******************************************************************************/
331
332 classinfo *
333 classcache_lookup(classloader *initloader,utf *classname)
334 {
335         classcache_name_entry *en;
336         classcache_class_entry *clsen;
337         classcache_loader_entry *lden;
338         classinfo *cls = NULL;
339
340         CLASSCACHE_LOCK();
341
342         en = classcache_lookup_name(classname);
343         
344         if (en) {
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;
353                                         goto found;
354                                 }
355                         }
356                 }
357         }
358 found:
359         CLASSCACHE_UNLOCK();
360         return cls;
361 }
362
363 /* classcache_store ************************************************************
364    
365    Store a loaded class
366   
367    IN:
368        initloader.......initiating loader used to load the class
369        cls..............class object to cache
370   
371    RETURN VALUE:
372        true.............everything ok, the class was stored in
373                         the cache if necessary,
374        false............an exception has been thrown.
375    
376    Note: synchronized with global tablelock
377    
378 *******************************************************************************/
379
380 bool
381 classcache_store(classloader *initloader,classinfo *cls)
382 {
383         classcache_name_entry *en;
384         classcache_class_entry *clsen;
385         classcache_loader_entry *lden;
386
387         CLASSCACHE_ASSERT(cls);
388
389 #ifdef CLASSCACHE_VERBOSE
390         fprintf(stderr,"classcache_store(%p,",initloader);
391         utf_fprint_classname(stderr,cls->name);
392         fprintf(stderr,")\n");
393 #endif
394
395         CLASSCACHE_LOCK();
396
397         en = classcache_new_name(cls->name);
398
399         CLASSCACHE_ASSERT(en);
400         
401         /* iterate over all class entries */
402         for (clsen=en->classes; clsen; clsen=clsen->next) {
403                 
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);
410                 }
411 #endif
412
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;
423                                 }
424
425                                 /* record initloader as initiating loader */
426                                 clsen->loaders = classcache_new_loader_entry(initloader,clsen->loaders);
427
428                                 /* record the loaded class object */
429                                 clsen->classobj = cls;
430
431                                 /* done */
432                                 goto return_success;
433                         }
434                 }
435                 
436         }
437
438         /* create a new class entry for this class object with */
439         /* initiating loader initloader                        */
440
441         clsen = NEW(classcache_class_entry);
442         clsen->classobj = cls;
443         clsen->loaders = classcache_new_loader_entry(initloader,NULL);
444         clsen->constraints = NULL;
445
446         clsen->next = en->classes;
447         en->classes = clsen;
448
449 return_success:
450         CLASSCACHE_UNLOCK();
451         return true;
452
453 return_exception:
454         CLASSCACHE_UNLOCK();
455         return false; /* exception */
456 }
457
458 /* classcache_find_loader ******************************************************
459  
460    Find the class entry loaded by or constrained to a given loader
461    (internally used helper function)
462   
463    IN:
464        entry............the classcache_name_entry
465        loader...........the loader to look for
466   
467    RETURN VALUE:
468        the classcache_class_entry for the given loader, or
469            NULL if no entry was found
470    
471 *******************************************************************************/
472
473 static classcache_class_entry *
474 classcache_find_loader(classcache_name_entry *entry,classloader *loader)
475 {
476         classcache_class_entry *clsen;
477         classcache_loader_entry *lden;
478         
479         CLASSCACHE_ASSERT(entry);
480
481         /* iterate over all class entries */
482         for (clsen=entry->classes; clsen; clsen=clsen->next) {
483                 
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 */
488                 }
489                 
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 */
494                 }
495         }
496
497         /* not found */
498         return NULL;
499 }
500
501 /* classcache_free_class_entry *************************************************
502  
503    Free the memory used by a class entry
504   
505    IN:
506        clsen............the classcache_class_entry to free  
507            
508 *******************************************************************************/
509
510 static void
511 classcache_free_class_entry(classcache_class_entry *clsen)
512 {
513         classcache_loader_entry *lden;
514         classcache_loader_entry *next;
515         
516         CLASSCACHE_ASSERT(clsen);
517
518         for (lden=clsen->loaders; lden; lden=next) {
519                 next = lden->next;
520                 FREE(lden,classcache_loader_entry);
521         }
522         for (lden=clsen->constraints; lden; lden=next) {
523                 next = lden->next;
524                 FREE(lden,classcache_loader_entry);
525         }
526
527         FREE(clsen,classcache_class_entry);
528 }
529
530 /* classcache_remove_class_entry ***********************************************
531  
532    Remove a classcache_class_entry from the list of possible resolution of
533    a name entry
534    (internally used helper function)
535   
536    IN:
537        entry............the classcache_name_entry
538        clsen............the classcache_class_entry to remove
539   
540 *******************************************************************************/
541
542 static void
543 classcache_remove_class_entry(classcache_name_entry *entry,
544                                                           classcache_class_entry *clsen)
545 {
546         classcache_class_entry **chain;
547
548         CLASSCACHE_ASSERT(entry);
549         CLASSCACHE_ASSERT(clsen);
550
551         chain = &(entry->classes);
552         while (*chain) {
553                 if (*chain == clsen) {
554                         *chain = clsen->next;
555                         classcache_free_class_entry(clsen);
556                         return;
557                 }
558                 chain = &((*chain)->next);
559         }
560 }
561
562 /* classcache_free_name_entry **************************************************
563  
564    Free the memory used by a name entry
565   
566    IN:
567        entry............the classcache_name_entry to free  
568            
569 *******************************************************************************/
570
571 static void
572 classcache_free_name_entry(classcache_name_entry *entry)
573 {
574         classcache_class_entry *clsen;
575         classcache_class_entry *next;
576         
577         CLASSCACHE_ASSERT(entry);
578
579         for (clsen=entry->classes; clsen; clsen=next) {
580                 next = clsen->next;
581                 classcache_free_class_entry(clsen);
582         }
583
584         FREE(entry,classcache_name_entry);
585 }
586
587 /* classcache_free *************************************************************
588  
589    Free the memory used by the class cache
590
591    NOTE:
592        The class cache may not be used any more after this call, except
593            when it is reinitialized with classcache_init.
594   
595    Note: NOT synchronized!
596   
597 *******************************************************************************/
598
599 void 
600 classcache_free()
601 {
602         u4 slot;
603         classcache_name_entry *entry;
604         classcache_name_entry *next;
605
606         for (slot=0; slot<classcache_hash.size; ++slot) {
607                 for (entry=(classcache_name_entry *)classcache_hash.ptr[slot];
608                          entry;
609                          entry = next)
610                 {
611                         next = entry->hashlink;
612                         classcache_free_name_entry(entry);
613                 }
614         }
615
616         MFREE(classcache_hash.ptr,voidptr,classcache_hash.size);
617         classcache_hash.size = 0;
618         classcache_hash.entries = 0;
619         classcache_hash.ptr = NULL;
620 }
621
622 /* classcache_add_constraint ***************************************************
623  
624    Add a loading constraint
625   
626    IN:
627        a................first initiating loader
628        b................second initiating loader
629        classname........class name
630   
631    RETURN VALUE:
632        true.............everything ok, the constraint has been added,
633        false............an exception has been thrown.
634    
635    Note: synchronized with global tablelock
636    
637 *******************************************************************************/
638
639 bool
640 classcache_add_constraint(classloader *a,classloader *b,utf *classname)
641 {
642         classcache_name_entry *en;
643         classcache_class_entry *clsenA;
644         classcache_class_entry *clsenB;
645
646         CLASSCACHE_ASSERT(classname);
647
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");
652 #endif
653
654         /* a constraint with a == b is trivially satisfied */
655         if (a == b)
656                 return true;
657
658         CLASSCACHE_LOCK();
659
660         en = classcache_new_name(classname);
661
662         CLASSCACHE_ASSERT(en);
663         
664         /* find the entry loaded by / constrained to each loader */
665         clsenA = classcache_find_loader(en,a);
666         clsenB = classcache_find_loader(en,b);
667
668         if (clsenA && clsenB) {
669                 /* { both loaders have corresponding entries } */
670
671                 /* if the entries are the same, the constraint is already recorded */
672                 if (clsenA == clsenB)
673                         goto return_success;
674
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;
681                 }
682
683                 /* yes, merge the entries */
684                 /* clsenB will be merged into clsenA */
685                 clsenA->loaders = classcache_merge_loaders(clsenA->loaders,
686                                                                                                    clsenB->loaders);
687                 
688                 clsenA->constraints = classcache_merge_loaders(clsenA->constraints,
689                                                                                                            clsenB->constraints);
690
691                 if (!clsenA->classobj)
692                         clsenA->classobj = clsenB->classobj;
693                 
694                 /* remove clsenB from the list of class entries */
695                 classcache_remove_class_entry(en,clsenB);
696         }
697         else {
698                 /* { at most one of the loaders has a corresponding entry } */
699
700                 /* set clsenA to the single class entry we have */
701                 if (!clsenA)
702                         clsenA = clsenB;
703
704                 if (!clsenA) {
705                         /* { no loader has a corresponding entry } */
706
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);
713
714                         clsenA->next = en->classes;
715                         en->classes = clsenA;
716                 }
717                 else {
718                         /* make b the loader that has no corresponding entry */
719                         if (clsenB)
720                                 b = a;
721                         
722                         /* loader b must be added to entry clsenA */
723                         clsenA->constraints = classcache_new_loader_entry(b,clsenA->constraints);
724                 }
725         }
726
727 return_success:
728         CLASSCACHE_UNLOCK();
729         return true;
730
731 return_exception:
732         CLASSCACHE_UNLOCK();
733         return false; /* exception */
734 }
735
736 /*============================================================================*/
737 /* DEBUG DUMPS                                                                */
738 /*============================================================================*/
739
740 /* classcache_debug_dump *******************************************************
741  
742    Print the contents of the loaded class cache to a stream
743   
744    IN:
745        file.............output stream
746   
747    Note: synchronized with global tablelock
748    
749 *******************************************************************************/
750
751 void
752 classcache_debug_dump(FILE *file)
753 {
754         classcache_name_entry *c;
755         classcache_class_entry *clsen;
756         classcache_loader_entry *lden;
757         u4 slot;
758
759         CLASSCACHE_LOCK();
760
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);
764         fprintf(file,"\n");
765
766         for (slot=0; slot<classcache_hash.size; ++slot) {
767                 c = (classcache_name_entry *) classcache_hash.ptr[slot];
768
769                 for (; c; c=c->hashlink) {
770                         utf_fprint_classname(file,c->name);
771                         fprintf(file,"\n");
772
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);
779                                 }
780                                 fprintf(file,"\n    constraints:");
781                                 for (lden=clsen->constraints; lden; lden=lden->next) {
782                                         fprintf(file," %p",(void *)lden->loader);
783                                 }
784                                 fprintf(file,"\n");
785                         }
786                 }
787         }
788         fprintf(file,"\n==============================================================\n\n");
789
790         CLASSCACHE_UNLOCK();
791 }
792
793 /*
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  * ---------------------------------------------------------------------
798  * Local variables:
799  * mode: c
800  * indent-tabs-mode: t
801  * c-basic-offset: 4
802  * tab-width: 4
803  * End:
804  * vim:noexpandtab:sw=4:ts=4:
805  */
806