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