classinfo: changed type of super and interfaces 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 2186 2005-04-02 00:43:25Z 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         CLASSCACHE_LOCK();
390
391         en = classcache_new_name(cls->name);
392
393         CLASSCACHE_ASSERT(en);
394         
395         /* iterate over all class entries */
396         for (clsen=en->classes; clsen; clsen=clsen->next) {
397                 
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);
404                 }
405 #endif
406
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;
417                                 }
418
419                                 /* record initloader as initiating loader */
420                                 clsen->loaders = classcache_new_loader_entry(initloader,clsen->loaders);
421
422                                 /* record the loaded class object */
423                                 clsen->classobj = cls;
424
425                                 /* done */
426                                 goto return_success;
427                         }
428                 }
429                 
430         }
431
432         /* create a new class entry for this class object with */
433         /* initiating loader initloader                        */
434
435         clsen = NEW(classcache_class_entry);
436         clsen->classobj = cls;
437         clsen->loaders = classcache_new_loader_entry(initloader,NULL);
438         clsen->constraints = NULL;
439
440         clsen->next = en->classes;
441         en->classes = clsen;
442
443 return_success:
444         CLASSCACHE_UNLOCK();
445         return true;
446
447 return_exception:
448         CLASSCACHE_UNLOCK();
449         return false; /* exception */
450 }
451
452 /* classcache_find_loader ******************************************************
453  
454    Find the class entry loaded by or constrained to a given loader
455    (internally used helper function)
456   
457    IN:
458        entry............the classcache_name_entry
459        loader...........the loader to look for
460   
461    RETURN VALUE:
462        the classcache_class_entry for the given loader, or
463            NULL if no entry was found
464    
465 *******************************************************************************/
466
467 static classcache_class_entry *
468 classcache_find_loader(classcache_name_entry *entry,classloader *loader)
469 {
470         classcache_class_entry *clsen;
471         classcache_loader_entry *lden;
472         
473         CLASSCACHE_ASSERT(entry);
474
475         /* iterate over all class entries */
476         for (clsen=entry->classes; clsen; clsen=clsen->next) {
477                 
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 */
482                 }
483                 
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 */
488                 }
489         }
490
491         /* not found */
492         return NULL;
493 }
494
495 /* classcache_free_class_entry *************************************************
496  
497    Free the memory used by a class entry
498   
499    IN:
500        clsen............the classcache_class_entry to free  
501            
502 *******************************************************************************/
503
504 static void
505 classcache_free_class_entry(classcache_class_entry *clsen)
506 {
507         classcache_loader_entry *lden;
508         classcache_loader_entry *next;
509         
510         CLASSCACHE_ASSERT(clsen);
511
512         for (lden=clsen->loaders; lden; lden=next) {
513                 next = lden->next;
514                 FREE(lden,classcache_loader_entry);
515         }
516         for (lden=clsen->constraints; lden; lden=next) {
517                 next = lden->next;
518                 FREE(lden,classcache_loader_entry);
519         }
520
521         FREE(clsen,classcache_class_entry);
522 }
523
524 /* classcache_remove_class_entry ***********************************************
525  
526    Remove a classcache_class_entry from the list of possible resolution of
527    a name entry
528    (internally used helper function)
529   
530    IN:
531        entry............the classcache_name_entry
532        clsen............the classcache_class_entry to remove
533   
534 *******************************************************************************/
535
536 static void
537 classcache_remove_class_entry(classcache_name_entry *entry,
538                                                           classcache_class_entry *clsen)
539 {
540         classcache_class_entry **chain;
541
542         CLASSCACHE_ASSERT(entry);
543         CLASSCACHE_ASSERT(clsen);
544
545         chain = &(entry->classes);
546         while (*chain) {
547                 if (*chain == clsen) {
548                         *chain = clsen->next;
549                         classcache_free_class_entry(clsen);
550                         return;
551                 }
552                 chain = &((*chain)->next);
553         }
554 }
555
556 /* classcache_free_name_entry **************************************************
557  
558    Free the memory used by a name entry
559   
560    IN:
561        entry............the classcache_name_entry to free  
562            
563 *******************************************************************************/
564
565 static void
566 classcache_free_name_entry(classcache_name_entry *entry)
567 {
568         classcache_class_entry *clsen;
569         classcache_class_entry *next;
570         
571         CLASSCACHE_ASSERT(entry);
572
573         for (clsen=entry->classes; clsen; clsen=next) {
574                 next = clsen->next;
575                 classcache_free_class_entry(clsen);
576         }
577
578         FREE(entry,classcache_name_entry);
579 }
580
581 /* classcache_free *************************************************************
582  
583    Free the memory used by the class cache
584
585    NOTE:
586        The class cache may not be used any more after this call, except
587            when it is reinitialized with classcache_init.
588   
589    Note: NOT synchronized!
590   
591 *******************************************************************************/
592
593 void 
594 classcache_free()
595 {
596         u4 slot;
597         classcache_name_entry *entry;
598         classcache_name_entry *next;
599
600         for (slot=0; slot<classcache_hash.size; ++slot) {
601                 for (entry=(classcache_name_entry *)classcache_hash.ptr[slot];
602                          entry;
603                          entry = next)
604                 {
605                         next = entry->hashlink;
606                         classcache_free_name_entry(entry);
607                 }
608         }
609
610         MFREE(classcache_hash.ptr,voidptr,classcache_hash.size);
611         classcache_hash.size = 0;
612         classcache_hash.entries = 0;
613         classcache_hash.ptr = NULL;
614 }
615
616 /* classcache_add_constraint ***************************************************
617  
618    Add a loading constraint
619   
620    IN:
621        a................first initiating loader
622        b................second initiating loader
623        classname........class name
624   
625    RETURN VALUE:
626        true.............everything ok, the constraint has been added,
627        false............an exception has been thrown.
628    
629    Note: synchronized with global tablelock
630    
631 *******************************************************************************/
632
633 bool
634 classcache_add_constraint(classloader *a,classloader *b,utf *classname)
635 {
636         classcache_name_entry *en;
637         classcache_class_entry *clsenA;
638         classcache_class_entry *clsenB;
639
640         CLASSCACHE_ASSERT(classname);
641
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");
646 #endif
647
648         /* a constraint with a == b is trivially satisfied */
649         if (a == b)
650                 return true;
651
652         CLASSCACHE_LOCK();
653
654         en = classcache_new_name(classname);
655
656         CLASSCACHE_ASSERT(en);
657         
658         /* find the entry loaded by / constrained to each loader */
659         clsenA = classcache_find_loader(en,a);
660         clsenB = classcache_find_loader(en,b);
661
662         if (clsenA && clsenB) {
663                 /* { both loaders have corresponding entries } */
664
665                 /* if the entries are the same, the constraint is already recorded */
666                 if (clsenA == clsenB)
667                         goto return_success;
668
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;
675                 }
676
677                 /* yes, merge the entries */
678                 /* clsenB will be merged into clsenA */
679                 clsenA->loaders = classcache_merge_loaders(clsenA->loaders,
680                                                                                                    clsenB->loaders);
681                 
682                 clsenA->constraints = classcache_merge_loaders(clsenA->constraints,
683                                                                                                            clsenB->constraints);
684
685                 if (!clsenA->classobj)
686                         clsenA->classobj = clsenB->classobj;
687                 
688                 /* remove clsenB from the list of class entries */
689                 classcache_remove_class_entry(en,clsenB);
690         }
691         else {
692                 /* { at most one of the loaders has a corresponding entry } */
693
694                 /* set clsenA to the single class entry we have */
695                 if (!clsenA)
696                         clsenA = clsenB;
697
698                 if (!clsenA) {
699                         /* { no loader has a corresponding entry } */
700
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);
707
708                         clsenA->next = en->classes;
709                         en->classes = clsenA;
710                 }
711                 else {
712                         /* make b the loader that has no corresponding entry */
713                         if (clsenB)
714                                 b = a;
715                         
716                         /* loader b must be added to entry clsenA */
717                         clsenA->constraints = classcache_new_loader_entry(b,clsenA->constraints);
718                 }
719         }
720
721 return_success:
722         CLASSCACHE_UNLOCK();
723         return true;
724
725 return_exception:
726         CLASSCACHE_UNLOCK();
727         return false; /* exception */
728 }
729
730 /*============================================================================*/
731 /* DEBUG DUMPS                                                                */
732 /*============================================================================*/
733
734 /* classcache_debug_dump *******************************************************
735  
736    Print the contents of the loaded class cache to a stream
737   
738    IN:
739        file.............output stream
740   
741    Note: synchronized with global tablelock
742    
743 *******************************************************************************/
744
745 void
746 classcache_debug_dump(FILE *file)
747 {
748         classcache_name_entry *c;
749         classcache_class_entry *clsen;
750         classcache_loader_entry *lden;
751         u4 slot;
752
753         CLASSCACHE_LOCK();
754
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);
758         fprintf(file,"\n");
759
760         for (slot=0; slot<classcache_hash.size; ++slot) {
761                 c = (classcache_name_entry *) classcache_hash.ptr[slot];
762
763                 for (; c; c=c->hashlink) {
764                         utf_fprint_classname(file,c->name);
765                         fprintf(file,"\n");
766
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);
773                                 }
774                                 fprintf(file,"\n    constraints:");
775                                 for (lden=clsen->constraints; lden; lden=lden->next) {
776                                         fprintf(file," %p",(void *)lden->loader);
777                                 }
778                                 fprintf(file,"\n");
779                         }
780                 }
781         }
782         fprintf(file,"\n==============================================================\n\n");
783
784         CLASSCACHE_UNLOCK();
785 }
786
787 /*
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  * ---------------------------------------------------------------------
792  * Local variables:
793  * mode: c
794  * indent-tabs-mode: t
795  * c-basic-offset: 4
796  * tab-width: 4
797  * End:
798  * vim:noexpandtab:sw=4:ts=4:
799  */
800