src/vm/classcache.c

   1 /* src/vm/classcache.c - loaded class cache and loading constraints
   2
   3    Copyright (C) 1996-2005, 2006 R. Grafl, A. Krall, C. Kruegel,
   4    C. Oates, R. Obermaisser, M. Platter, M. Probst, S. Ring,
   5    E. Steiner, C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich,
   6    J. Wenninger, 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., 51 Franklin Street, Fifth Floor, Boston, MA
  23    02110-1301, USA.
  24
  25    Contact: cacao@cacaojvm.org
  26
  27    Authors: Edwin Steiner
  28
  29    Changes: Christian Thalinger
  30
  31    $Id: classcache.c 4802 2006-04-20 22:28:57Z edwin $
  32
  33 */
  34
  35
  36 #include "config.h"
  37 #include "vm/types.h"
  38
  39 #include <assert.h>
  40
  41 #include "mm/memory.h"
  42 #include "vm/classcache.h"
  43 #include "vm/exceptions.h"
  44 #include "vm/hashtable.h"
  45 #include "vm/stringlocal.h"
  46 #include "vm/utf8.h"
  47
  48
  49 /*************************************************************************
  50
  51   Class Cache
  52
  53   The classcache has two functions:
  54
  55         1) caching the resolution of class references
  56         2) storing and checking loading constraints
  57
  58   We will use the following terms in this description:
  59
  60         N          a class name: a utf string
  61         (N,L)      a class reference with initiating loader L and class name N
  62         C          a class (object): the result of resolving a reference (N,L)
  63                We will write resultion as
  64                                 C = *(N,L)
  65         (N,L1,L2)  a loading constraint indicating that (N,L1) and (N,L2) must
  66                    resolve to the same class C. So (N,L1,L2) means
  67                                 *(N,L1) = *(N,L2)
  68
  69   The functions of the classcache require:
  70
  71     1) a mapping (N,L) |--> C for looking up prior resolution results.
  72         2) storing the current set of loading constraints { (N,L1,L2) }
  73
  74   These functions can be rearranged like that:
  75
  76     a mapping N |--> (a mapping L |--> C or NULL,
  77                           a set of constraints {(L1,L2)})
  78
  79   Thus we can treat the mapping and constraints for each name N
  80   separately. The implementation does this by keeping a hash table
  81   mapping a name N to a `classcache_name_entry` which contains all
  82   info with respect to N.
  83
  84   For a class name N we can define an equivalence relation ~N~ on
  85   class loaders:
  86
  87         L1 ~N~ L2  <==>  *(N,L1) = *(N,L2)
  88
  89   A loading constraint (N,L1,L2) implies L1 ~N~ L2.
  90
  91   Also, if two references (N,L1) and (N,L2) resolve to the same class C
  92   we have L1 ~N~ L2 because class loaders are required to return
  93   consistent resolutions for a name N [XXX].
  94
  95   A `classcache_name_entry` keeps a set of tuples { (Cx,IL,CL) },
  96   where
  97                 Cx...is a class C or NULL
  98                 IL...is the set of initiating loaders
  99                 CL...is the set of constrained loaders
 100
 101   Such a tuple is called `classcache_class_entry` in the source code.
 102
 103   The following holds for each tuple (Cx,IL,CL):
 104
 105     .  (Cx is NULL) implies IL = {}.
 106
 107         .  If Cx is a class, IL is the set of loaders that have been
 108            recorded as initiating loaders for Cx. IL may be the
 109            empty set {} in case Cx has already been defined but no
 110            initiating loader has been recorded, yet.
 111
 112     .  (IL u CL) is a subset of an equivalence class of ~N~.
 113
 114                  (This means that all loaders in IL and CL must resolve
 115                  the name N to the same class.)
 116
 117   The following holds for the set of tuples { (Cx,IL,CL) }:
 118
 119     .  For a given class C there is at most one tuple with Cx = C
 120            in the set. (There may be an arbitrary number of tuples
 121            with Cx = NULL, however.)
 122
 123         .  For a given loader L there is at most one tuple with
 124            L in (IL u CL).
 125
 126   The implementation stores sets of loaders as linked lists of
 127   `classcache_loader_entry`s.
 128
 129   Comments about manipulating the classcache can be found in the
 130   individual functions below.
 131
 132 *************************************************************************/
 133
 134
 135 /* initial number of slots in the classcache hash table */
 136 #define CLASSCACHE_INIT_SIZE  2048
 137
 138 /*============================================================================*/
 139 /* DEBUG HELPERS                                                              */
 140 /*============================================================================*/
 141
 142 /*#define CLASSCACHE_VERBOSE*/
 143
 144 /*============================================================================*/
 145 /* STATISTICS                                                                 */
 146 /*============================================================================*/
 147
 148 /*#define CLASSCACHE_STATS*/
 149
 150 #ifdef CLASSCACHE_STATS
 151 static int stat_classnames_stored = 0;
 152 static int stat_classes_stored = 0;
 153 static int stat_trivial_constraints = 0;
 154 static int stat_nontriv_constraints = 0;
 155 static int stat_nontriv_constraints_both = 0;
 156 static int stat_nontriv_constraints_merged = 0;
 157 static int stat_nontriv_constraints_one = 0;
 158 static int stat_nontriv_constraints_none = 0;
 159 static int stat_new_loader_entry = 0;
 160 static int stat_merge_class_entries = 0;
 161 static int stat_merge_loader_entries = 0;
 162 static int stat_lookup = 0;
 163 static int stat_lookup_class_entry_checked = 0;
 164 static int stat_lookup_loader_checked = 0;
 165 static int stat_lookup_name = 0;
 166 static int stat_lookup_name_entry = 0;
 167 static int stat_lookup_name_notfound = 0;
 168 static int stat_lookup_new_name = 0;
 169 static int stat_lookup_new_name_entry = 0;
 170 static int stat_lookup_new_name_collisions = 0;
 171 static int stat_rehash_names = 0;
 172 static int stat_rehash_names_collisions = 0;
 173
 174 #define CLASSCACHE_COUNT(cnt)  (cnt)++
 175 #define CLASSCACHE_COUNTIF(cond,cnt)  do{if(cond) (cnt)++;} while(0)
 176
 177 void classcache_print_statistics(FILE *file) {
 178         fprintf(file,"classnames stored   : %8d\n",stat_classnames_stored);
 179         fprintf(file,"classes stored      : %8d\n",stat_classes_stored);
 180         fprintf(file,"trivial constraints : %8d\n",stat_trivial_constraints);
 181         fprintf(file,"non-triv constraints: %8d\n",stat_nontriv_constraints);
 182         fprintf(file,"   both loaders rec.: %8d\n",stat_nontriv_constraints_both);
 183         fprintf(file,"       merged       : %8d\n",stat_nontriv_constraints_merged);
 184         fprintf(file,"   one loader rec.  : %8d\n",stat_nontriv_constraints_one);
 185         fprintf(file,"   no loaders rec.  : %8d\n",stat_nontriv_constraints_none);
 186         fprintf(file,"new loader entries  : %8d\n",stat_new_loader_entry);
 187         fprintf(file,"merge class entries : %8d\n",stat_merge_class_entries);
 188         fprintf(file,"merge loader entries: %8d\n",stat_merge_loader_entries);
 189         fprintf(file,"lookups             : %8d\n",stat_lookup);
 190         fprintf(file,"   class entries ckd: %8d\n",stat_lookup_class_entry_checked);
 191         fprintf(file,"   loader checked   : %8d\n",stat_lookup_loader_checked);
 192         fprintf(file,"lookup name         : %8d\n",stat_lookup_name);
 193         fprintf(file,"   entries checked  : %8d\n",stat_lookup_name_entry);
 194         fprintf(file,"   not found        : %8d\n",stat_lookup_name_notfound);
 195         fprintf(file,"lookup (new) name   : %8d\n",stat_lookup_new_name);
 196         fprintf(file,"   entries checked  : %8d\n",stat_lookup_new_name_entry);
 197         fprintf(file,"   new collisions   : %8d\n",stat_lookup_new_name_collisions);
 198         fprintf(file,"names rehashed      : %8d times\n",stat_rehash_names);
 199         fprintf(file,"    collisions      : %8d\n",stat_rehash_names_collisions);
 200 }
 201 #else
 202 #define CLASSCACHE_COUNT(cnt)
 203 #define CLASSCACHE_COUNTIF(cond,cnt)
 204 #endif
 205
 206 /*============================================================================*/
 207 /* THREAD-SAFE LOCKING                                                        */
 208 /*============================================================================*/
 209
 210         /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
 211         /* CAUTION: The static functions below are */
 212         /*          NOT synchronized!              */
 213         /*!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */
 214
 215 #if defined(USE_THREADS)
 216 # define CLASSCACHE_LOCK()      builtin_monitorenter(lock_hashtable_classcache)
 217 # define CLASSCACHE_UNLOCK()    builtin_monitorexit(lock_hashtable_classcache)
 218 #else
 219 # define CLASSCACHE_LOCK()
 220 # define CLASSCACHE_UNLOCK()
 221 #endif
 222
 223 /*============================================================================*/
 224 /* GLOBAL VARIABLES                                                           */
 225 /*============================================================================*/
 226
 227 hashtable hashtable_classcache;
 228
 229 #if defined(USE_THREADS)
 230 static java_objectheader *lock_hashtable_classcache;
 231 #endif
 232
 233
 234 /*============================================================================*/
 235 /*                                                                            */
 236 /*============================================================================*/
 237
 238 /* prototypes */
 239
 240 static void classcache_free_class_entry(classcache_class_entry *clsen);
 241 static void classcache_remove_class_entry(classcache_name_entry *en,
 242                                                                                   classcache_class_entry *clsen);
 243
 244 /* hash function to use */
 245
 246 #define CLASSCACHE_HASH utf_full_hashkey
 247
 248 /* classcache_init *************************************************************
 249
 250    Initialize the class cache
 251
 252    Note: NOT synchronized!
 253
 254 *******************************************************************************/
 255
 256 bool classcache_init(void)
 257 {
 258         /* create the hashtable */
 259
 260         hashtable_create(&hashtable_classcache, CLASSCACHE_INIT_SIZE);
 261
 262 #if defined(USE_THREADS)
 263         /* create utf hashtable lock object */
 264
 265         lock_hashtable_classcache = NEW(java_objectheader);
 266
 267 # if defined(NATIVE_THREADS)
 268         initObjectLock(lock_hashtable_classcache);
 269 # endif
 270 #endif
 271
 272         /* everything's ok */
 273
 274         return true;
 275 }
 276
 277 /* classcache_new_loader_entry *************************************************
 278
 279    Create a new classcache_loader_entry struct
 280    (internally used helper function)
 281
 282    IN:
 283        loader...........the ClassLoader object
 284            next.............the next classcache_loader_entry
 285
 286    RETURN VALUE:
 287        the new classcache_loader_entry
 288
 289 *******************************************************************************/
 290
 291 static classcache_loader_entry * classcache_new_loader_entry(
 292                                                                         classloader * loader,
 293                                                                         classcache_loader_entry * next)
 294 {
 295         classcache_loader_entry *lden;
 296
 297         lden = NEW(classcache_loader_entry);
 298         lden->loader = loader;
 299         lden->next = next;
 300         CLASSCACHE_COUNT(stat_new_loader_entry);
 301
 302         return lden;
 303 }
 304
 305 /* classcache_merge_loaders ****************************************************
 306
 307    Merge two lists of loaders into one
 308    (internally used helper function)
 309
 310    IN:
 311        lista............first list (may be NULL)
 312            listb............second list (may be NULL)
 313
 314    RETURN VALUE:
 315        the merged list (may be NULL)
 316
 317    NOTE:
 318        The lists given as arguments are destroyed!
 319
 320 *******************************************************************************/
 321
 322 static classcache_loader_entry * classcache_merge_loaders(
 323                                                                         classcache_loader_entry * lista,
 324                                                                         classcache_loader_entry * listb)
 325 {
 326         classcache_loader_entry *result;
 327         classcache_loader_entry *ldenA;
 328         classcache_loader_entry *ldenB;
 329         classcache_loader_entry **chain;
 330
 331         CLASSCACHE_COUNT(stat_merge_loader_entries);
 332
 333         /* XXX This is a quadratic algorithm. If this ever
 334          * becomes a problem, the loader lists should be
 335          * stored as sorted lists and merged in linear time. */
 336
 337         result = NULL;
 338         chain = &result;
 339
 340         for (ldenA = lista; ldenA; ldenA = ldenA->next) {
 341
 342                 for (ldenB = listb; ldenB; ldenB = ldenB->next) {
 343                         if (ldenB->loader == ldenA->loader)
 344                                 goto common_element;
 345                 }
 346
 347                 /* this loader is only in lista */
 348                 *chain = ldenA;
 349                 chain = &(ldenA->next);
 350
 351           common_element:
 352                 /* XXX free the duplicated element */
 353                 ;
 354         }
 355
 356         /* concat listb to the result */
 357         *chain = listb;
 358
 359         return result;
 360 }
 361
 362 /* classcache_merge_class_entries **********************************************
 363
 364    Merge two `classcache_class_entry`s into one.
 365    (internally used helper function)
 366
 367    IN:
 368        en...............the classcache_name_entry containing both class entries
 369        clsenA...........first class entry, will receive the result
 370            clsenB...........second class entry
 371
 372    PRE-CONDITION:
 373        Either both entries must have the same classobj, or one of them has
 374            classobj == NULL.
 375
 376    NOTE:
 377        clsenB is freed by this function!
 378
 379 *******************************************************************************/
 380
 381 static void classcache_merge_class_entries(classcache_name_entry *en,
 382                                                                                    classcache_class_entry *clsenA,
 383                                                                                    classcache_class_entry *clsenB)
 384 {
 385 #ifdef CLASSCACHE_VERBOSE
 386         char logbuffer[1024];
 387 #endif
 388
 389         assert(en);
 390         assert(clsenA);
 391         assert(clsenB);
 392         assert(!clsenA->classobj || !clsenB->classobj || clsenA->classobj == clsenB->classobj);
 393
 394 #ifdef CLASSCACHE_VERBOSE
 395         sprintf(logbuffer,"classcache_merge_class_entries(%p,%p->%p,%p->%p) ",
 396                         (void*)en,(void*)clsenA,(void*)clsenA->classobj,(void*)clsenB,(void*)clsenB->classobj);
 397         if (clsenA->classobj)
 398                 utf_strcat(logbuffer, clsenA->classobj->name);
 399         if (clsenB->classobj)
 400                 utf_strcat(logbuffer, clsenB->classobj->name);
 401         log_text(logbuffer);
 402 #endif
 403
 404         CLASSCACHE_COUNT(stat_merge_class_entries);
 405
 406         /* clsenB will be merged into clsenA */
 407         clsenA->loaders = classcache_merge_loaders(clsenA->loaders, clsenB->loaders);
 408         clsenB->loaders = NULL; /* these have been freed or reused */
 409
 410         clsenA->constraints = classcache_merge_loaders(clsenA->constraints,
 411                                                                                                    clsenB->constraints);
 412         clsenB->constraints = NULL; /* these have been freed or reused */
 413
 414         if (!clsenA->classobj)
 415                 clsenA->classobj = clsenB->classobj;
 416
 417         /* remove clsenB from the list of class entries */
 418         classcache_remove_class_entry(en, clsenB);
 419 }
 420
 421
 422 /* classcache_lookup_name ******************************************************
 423
 424    Lookup a name in the first level of the cache
 425    (internally used helper function)
 426
 427    IN:
 428        name.............the name to look up
 429
 430    RETURN VALUE:
 431        a pointer to the classcache_name_entry for this name, or
 432        null if no entry was found.
 433
 434 *******************************************************************************/
 435
 436 static classcache_name_entry *classcache_lookup_name(utf *name)
 437 {
 438         classcache_name_entry *c;           /* hash table element                 */
 439         u4 key;                             /* hashkey computed from classname    */
 440         u4 slot;                            /* slot in hashtable                  */
 441
 442         CLASSCACHE_COUNT(stat_lookup_name);
 443
 444         key  = CLASSCACHE_HASH(name->text, (u4) name->blength);
 445         slot = key & (hashtable_classcache.size - 1);
 446         c    = hashtable_classcache.ptr[slot];
 447
 448         /* search external hash chain for the entry */
 449
 450         while (c) {
 451                 /* entry found in hashtable */
 452                 CLASSCACHE_COUNT(stat_lookup_name_entry);
 453
 454                 if (c->name == name)
 455                         return c;
 456
 457                 c = c->hashlink;                    /* next element in external chain */
 458         }
 459
 460         /* not found */
 461
 462         CLASSCACHE_COUNT(stat_lookup_name_notfound);
 463         return NULL;
 464 }
 465
 466
 467 /* classcache_new_name *********************************************************
 468
 469    Return a classcache_name_entry for the given name. The entry is created
 470    if it is not already in the cache.
 471    (internally used helper function)
 472
 473    IN:
 474        name.............the name to look up / create an entry for
 475
 476    RETURN VALUE:
 477        a pointer to the classcache_name_entry for this name
 478
 479 *******************************************************************************/
 480
 481 static classcache_name_entry *classcache_new_name(utf *name)
 482 {
 483         classcache_name_entry *c;       /* hash table element */
 484         u4 key;                                         /* hashkey computed from classname */
 485         u4 slot;                                        /* slot in hashtable               */
 486         u4 i;
 487
 488         CLASSCACHE_COUNT(stat_lookup_new_name);
 489
 490         key  = CLASSCACHE_HASH(name->text, (u4) name->blength);
 491         slot = key & (hashtable_classcache.size - 1);
 492         c    = hashtable_classcache.ptr[slot];
 493
 494         /* search external hash chain for the entry */
 495
 496         while (c) {
 497                 /* entry found in hashtable */
 498                 CLASSCACHE_COUNT(stat_lookup_new_name_entry);
 499
 500                 if (c->name == name)
 501                         return c;
 502
 503                 c = c->hashlink;                    /* next element in external chain */
 504         }
 505
 506         /* location in hashtable found, create new entry */
 507
 508         c = NEW(classcache_name_entry);
 509
 510         c->name = name;
 511         c->classes = NULL;
 512
 513         /* insert entry into hashtable */
 514         c->hashlink = (classcache_name_entry *) hashtable_classcache.ptr[slot];
 515         CLASSCACHE_COUNTIF(c->hashlink,stat_lookup_new_name_collisions);
 516         hashtable_classcache.ptr[slot] = c;
 517
 518         /* update number of hashtable-entries */
 519         hashtable_classcache.entries++;
 520         CLASSCACHE_COUNT(stat_classnames_stored);
 521
 522         if ((hashtable_classcache.entries*2) > hashtable_classcache.size) {
 523                 /* reorganization of hashtable */
 524
 525                 classcache_name_entry *c2;
 526                 hashtable newhash;              /* the new hashtable */
 527
 528                 CLASSCACHE_COUNT(stat_rehash_names);
 529
 530                 /* create new hashtable, double the size */
 531
 532                 hashtable_create(&newhash, hashtable_classcache.size * 2);
 533                 newhash.entries = hashtable_classcache.entries;
 534
 535                 /* transfer elements to new hashtable */
 536
 537                 for (i = 0; i < hashtable_classcache.size; i++) {
 538                         c2 = (classcache_name_entry *) hashtable_classcache.ptr[i];
 539                         while (c2) {
 540                                 classcache_name_entry *nextc = c2->hashlink;
 541                                 u4 newslot =
 542                                         (CLASSCACHE_HASH(c2->name->text, (u4) c2->name->blength)) & (newhash.size - 1);
 543
 544                                 c2->hashlink = (classcache_name_entry *) newhash.ptr[newslot];
 545                                 CLASSCACHE_COUNTIF(c2->hashlink,stat_rehash_names_collisions);
 546                                 newhash.ptr[newslot] = c2;
 547
 548                                 c2 = nextc;
 549                         }
 550                 }
 551
 552                 /* dispose old table */
 553
 554                 MFREE(hashtable_classcache.ptr, void *, hashtable_classcache.size);
 555                 hashtable_classcache = newhash;
 556         }
 557
 558         return c;
 559 }
 560
 561
 562 /* classcache_lookup ***********************************************************
 563
 564    Lookup a possibly loaded class
 565
 566    IN:
 567        initloader.......initiating loader for resolving the class name
 568        classname........class name to look up
 569
 570    RETURN VALUE:
 571        The return value is a pointer to the cached class object,
 572        or NULL, if the class is not in the cache.
 573
 574    Note: synchronized with global tablelock
 575
 576 *******************************************************************************/
 577
 578 classinfo *classcache_lookup(classloader *initloader, utf *classname)
 579 {
 580         classcache_name_entry *en;
 581         classcache_class_entry *clsen;
 582         classcache_loader_entry *lden;
 583         classinfo *cls = NULL;
 584
 585         CLASSCACHE_LOCK();
 586
 587         CLASSCACHE_COUNT(stat_lookup);
 588         en = classcache_lookup_name(classname);
 589
 590         if (en) {
 591                 /* iterate over all class entries */
 592
 593                 for (clsen = en->classes; clsen; clsen = clsen->next) {
 594                         CLASSCACHE_COUNT(stat_lookup_class_entry_checked);
 595                         /* check if this entry has been loaded by initloader */
 596
 597                         for (lden = clsen->loaders; lden; lden = lden->next) {
 598                                 CLASSCACHE_COUNT(stat_lookup_loader_checked);
 599                                 if (lden->loader == initloader) {
 600                                         /* found the loaded class entry */
 601
 602                                         assert(clsen->classobj);
 603                                         cls = clsen->classobj;
 604                                         goto found;
 605                                 }
 606                         }
 607                 }
 608         }
 609
 610   found:
 611         CLASSCACHE_UNLOCK();
 612         return cls;
 613 }
 614
 615
 616 /* classcache_lookup_defined ***************************************************
 617
 618    Lookup a class with the given name and defining loader
 619
 620    IN:
 621        defloader........defining loader
 622        classname........class name
 623
 624    RETURN VALUE:
 625        The return value is a pointer to the cached class object,
 626        or NULL, if the class is not in the cache.
 627
 628 *******************************************************************************/
 629
 630 classinfo *classcache_lookup_defined(classloader *defloader, utf *classname)
 631 {
 632         classcache_name_entry *en;
 633         classcache_class_entry *clsen;
 634         classinfo *cls = NULL;
 635
 636         CLASSCACHE_LOCK();
 637
 638         en = classcache_lookup_name(classname);
 639
 640         if (en) {
 641                 /* iterate over all class entries */
 642                 for (clsen = en->classes; clsen; clsen = clsen->next) {
 643                         if (!clsen->classobj)
 644                                 continue;
 645
 646                         /* check if this entry has been defined by defloader */
 647                         if (clsen->classobj->classloader == defloader) {
 648                                 cls = clsen->classobj;
 649                                 goto found;
 650                         }
 651                 }
 652         }
 653
 654   found:
 655         CLASSCACHE_UNLOCK();
 656         return cls;
 657 }
 658
 659
 660 /* classcache_lookup_defined_or_initiated **************************************
 661
 662    Lookup a class that has been defined or initiated by the given loader
 663
 664    IN:
 665        loader...........defining or initiating loader
 666        classname........class name to look up
 667
 668    RETURN VALUE:
 669        The return value is a pointer to the cached class object,
 670        or NULL, if the class is not in the cache.
 671
 672    Note: synchronized with global tablelock
 673
 674 *******************************************************************************/
 675
 676 classinfo *classcache_lookup_defined_or_initiated(classloader *loader,
 677                                                                                                   utf *classname)
 678 {
 679         classcache_name_entry *en;
 680         classcache_class_entry *clsen;
 681         classcache_loader_entry *lden;
 682         classinfo *cls = NULL;
 683
 684         CLASSCACHE_LOCK();
 685
 686         en = classcache_lookup_name(classname);
 687
 688         if (en) {
 689                 /* iterate over all class entries */
 690
 691                 for (clsen = en->classes; clsen; clsen = clsen->next) {
 692
 693                         /* check if this entry has been defined by loader */
 694                         if (clsen->classobj && clsen->classobj->classloader == loader) {
 695                                 cls = clsen->classobj;
 696                                 goto found;
 697                         }
 698
 699                         /* check if this entry has been initiated by loader */
 700                         for (lden = clsen->loaders; lden; lden = lden->next) {
 701                                 if (lden->loader == loader) {
 702                                         /* found the loaded class entry */
 703
 704                                         assert(clsen->classobj);
 705                                         cls = clsen->classobj;
 706                                         goto found;
 707                                 }
 708                         }
 709                 }
 710         }
 711
 712   found:
 713         CLASSCACHE_UNLOCK();
 714         return cls;
 715 }
 716
 717
 718 /* classcache_store ************************************************************
 719
 720    Store a loaded class. If a class of the same name has already been stored
 721    with the same initiating loader, then the given class CLS is freed (if
 722    possible) and the previously stored class is returned.
 723
 724    IN:
 725        initloader.......initiating loader used to load the class
 726                             (may be NULL indicating the bootstrap loader)
 727        cls..............class object to cache
 728            mayfree..........true if CLS may be freed in case another class is
 729                             returned
 730
 731    RETURN VALUE:
 732        cls..............everything ok, the class was stored in the cache,
 733            other classinfo..another class with the same (initloader,name) has been
 734                             stored earlier. CLS has been freed[1] and the earlier
 735                                                 stored class is returned.
 736        NULL.............an exception has been thrown.
 737
 738    Note: synchronized with global tablelock
 739
 740    [1]...in case MAYFREE is true
 741
 742 *******************************************************************************/
 743
 744 classinfo *classcache_store(classloader *initloader, classinfo *cls,
 745                                                         bool mayfree)
 746 {
 747         classcache_name_entry *en;
 748         classcache_class_entry *clsen;
 749         classcache_class_entry *clsenB;
 750         classcache_loader_entry *lden;
 751 #ifdef CLASSCACHE_VERBOSE
 752         char logbuffer[1024];
 753 #endif
 754
 755         assert(cls);
 756         assert(cls->state & CLASS_LOADED);
 757
 758         CLASSCACHE_LOCK();
 759
 760 #ifdef CLASSCACHE_VERBOSE
 761         sprintf(logbuffer,"classcache_store (%p,%d,%p=", (void*)initloader,mayfree,(void*)cls);
 762         utf_strcat(logbuffer, cls->name);
 763         strcat(logbuffer,")");
 764         log_text(logbuffer);
 765 #endif
 766
 767         en = classcache_new_name(cls->name);
 768
 769         assert(en);
 770
 771         /* iterate over all class entries */
 772         for (clsen = en->classes; clsen; clsen = clsen->next) {
 773
 774                 /* check if this entry has already been loaded by initloader */
 775                 for (lden = clsen->loaders; lden; lden = lden->next) {
 776                         if (lden->loader == initloader) {
 777                            if (clsen->classobj != cls) {
 778                                         /* A class with the same (initloader,name) pair has been stored already. */
 779                                         /* We free the given class and return the earlier one.                   */
 780 #ifdef CLASSCACHE_VERBOSE
 781                                         dolog("replacing %p with earlier loaded class %p",cls,clsen->classobj);
 782 #endif
 783                                         assert(clsen->classobj);
 784                                         if (mayfree)
 785                                                 class_free(cls);
 786                                         cls = clsen->classobj;
 787                            }
 788                            goto return_success;
 789                         }
 790                 }
 791
 792                 /* {This entry has not been resolved with initloader} */
 793
 794                 /* check if initloader is constrained to this entry */
 795                 for (lden = clsen->constraints; lden; lden = lden->next) {
 796                         if (lden->loader == initloader) {
 797                                 /* we have to use this entry. check if it has been resolved */
 798                                 if (clsen->classobj) {
 799                                         /* check if is has already been resolved to another class */
 800                                         if (clsen->classobj != cls) {
 801                                                 /* a loading constraint is violated */
 802                                                 *exceptionptr = exceptions_new_linkageerror(
 803                                                                                         "loading constraint violated: ",cls);
 804                                                 goto return_exception;
 805                                         }
 806
 807                                         /* record initloader as initiating loader */
 808                                         clsen->loaders = classcache_new_loader_entry(initloader, clsen->loaders);
 809                                         goto return_success;
 810                                 }
 811
 812                                 /* {this is the first resolution for this entry} */
 813                                 /* record initloader as initiating loader */
 814                                 clsen->loaders = classcache_new_loader_entry(initloader, clsen->loaders);
 815
 816                                 /* maybe we can merge this entry with another one */
 817                                 for (clsenB = en->classes; clsenB; clsenB = clsenB->next) {
 818                                         /* we dont want the entry that we have already */
 819                                         if (clsenB->classobj == cls) {
 820                                                 /* this entry has the same classobj. let's merge them */
 821                                                 classcache_merge_class_entries(en,clsen,clsenB);
 822                                                 goto return_success;
 823                                         }
 824                                 }
 825
 826                                 /* record the loaded class object */
 827                                 clsen->classobj = cls;
 828                                 CLASSCACHE_COUNT(stat_classes_stored);
 829
 830                                 /* done */
 831                                 goto return_success;
 832                         }
 833                 }
 834
 835         }
 836
 837         /* {There is no class entry containing initloader as initiating
 838          *  or constrained loader.} */
 839
 840         /* we look for a class entry with the same classobj we want to store */
 841         for (clsen = en->classes; clsen; clsen = clsen->next) {
 842                 if (clsen->classobj == cls) {
 843                         /* this entry is about the same classobj. let's use it */
 844                         /* check if this entry has already been loaded by initloader */
 845                         for (lden = clsen->loaders; lden; lden = lden->next) {
 846                                 if (lden->loader == initloader)
 847                                         goto return_success;
 848                         }
 849                         clsen->loaders = classcache_new_loader_entry(initloader, clsen->loaders);
 850                         goto return_success;
 851                 }
 852         }
 853
 854         /* create a new class entry for this class object with */
 855         /* initiating loader initloader                        */
 856
 857         clsen = NEW(classcache_class_entry);
 858         clsen->classobj = cls;
 859         clsen->loaders = classcache_new_loader_entry(initloader, NULL);
 860         clsen->constraints = NULL;
 861
 862         clsen->next = en->classes;
 863         en->classes = clsen;
 864         CLASSCACHE_COUNT(stat_classes_stored);
 865
 866   return_success:
 867 #ifdef CLASSCACHE_VERBOSE
 868         classcache_debug_dump(stderr,cls->name);
 869 #endif
 870         CLASSCACHE_UNLOCK();
 871         return cls;
 872
 873   return_exception:
 874         CLASSCACHE_UNLOCK();
 875         return NULL;                            /* exception */
 876 }
 877
 878 /* classcache_store_unique *****************************************************
 879
 880    Store a loaded class as loaded by the bootstrap loader. This is a wrapper
 881    aroung classcache_store that throws an exception if a class with the same
 882    name has already been loaded by the bootstrap loader.
 883
 884    This function is used to register a few special classes during startup.
 885    It should not be used otherwise.
 886
 887    IN:
 888        cls..............class object to cache
 889
 890    RETURN VALUE:
 891        true.............everything ok, the class was stored.
 892        false............an exception has been thrown.
 893
 894    Note: synchronized with global tablelock
 895
 896 *******************************************************************************/
 897
 898 bool classcache_store_unique(classinfo *cls)
 899 {
 900         classinfo *result;
 901
 902         result = classcache_store(NULL,cls,false);
 903         if (result == NULL)
 904                 return false;
 905
 906         if (result != cls) {
 907                 *exceptionptr = new_internalerror("class already stored in the class cache");
 908                 return false;
 909         }
 910
 911         return true;
 912 }
 913
 914 /* classcache_store_defined ****************************************************
 915
 916    Store a loaded class after it has been defined. If the class has already
 917    been defined by the same defining loader in another thread, free the given
 918    class and returned the one which has been defined earlier.
 919
 920    IN:
 921        cls..............class object to store. classloader must be set
 922                             (classloader may be NULL, for bootloader)
 923
 924    RETURN VALUE:
 925        cls..............everything ok, the class was stored the cache,
 926            other classinfo..the class had already been defined, CLS was freed, the
 927                             class which was defined earlier is returned,
 928        NULL.............an exception has been thrown.
 929
 930 *******************************************************************************/
 931
 932 classinfo *classcache_store_defined(classinfo *cls)
 933 {
 934         classcache_name_entry *en;
 935         classcache_class_entry *clsen;
 936 #ifdef CLASSCACHE_VERBOSE
 937         char logbuffer[1024];
 938 #endif
 939
 940         assert(cls);
 941         assert(cls->state & CLASS_LOADED);
 942
 943         CLASSCACHE_LOCK();
 944
 945 #ifdef CLASSCACHE_VERBOSE
 946         sprintf(logbuffer,"classcache_store_defined (%p,", (void*)cls->classloader);
 947         utf_strcat(logbuffer, cls->name);
 948         strcat(logbuffer,")");
 949         log_text(logbuffer);
 950 #endif
 951
 952         en = classcache_new_name(cls->name);
 953
 954         assert(en);
 955
 956         /* iterate over all class entries */
 957         for (clsen = en->classes; clsen; clsen = clsen->next) {
 958
 959                 /* check if this class has been defined by the same classloader */
 960                 if (clsen->classobj && clsen->classobj->classloader == cls->classloader) {
 961                         /* we found an earlier definition, delete the newer one */
 962                         /* (if it is a different classinfo)                     */
 963                         if (clsen->classobj != cls) {
 964 #ifdef CLASSCACHE_VERBOSE
 965                                 dolog("replacing %p with earlier defined class %p",cls,clsen->classobj);
 966 #endif
 967                                 class_free(cls);
 968                                 cls = clsen->classobj;
 969                         }
 970                         goto return_success;
 971                 }
 972         }
 973
 974         /* create a new class entry for this class object */
 975         /* the list of initiating loaders is empty at this point */
 976
 977         clsen = NEW(classcache_class_entry);
 978         clsen->classobj = cls;
 979         clsen->loaders = NULL;
 980         clsen->constraints = NULL;
 981
 982         clsen->next = en->classes;
 983         en->classes = clsen;
 984         CLASSCACHE_COUNT(stat_classes_stored);
 985
 986 return_success:
 987 #ifdef CLASSCACHE_VERBOSE
 988         classcache_debug_dump(stderr,cls->name);
 989 #endif
 990         CLASSCACHE_UNLOCK();
 991         return cls;
 992 }
 993
 994 /* classcache_find_loader ******************************************************
 995
 996    Find the class entry loaded by or constrained to a given loader
 997    (internally used helper function)
 998
 999    IN:
1000        entry............the classcache_name_entry
1001        loader...........the loader to look for
1002
1003    RETURN VALUE:
1004        the classcache_class_entry for the given loader, or
1005            NULL if no entry was found
1006
1007 *******************************************************************************/
1008
1009 static classcache_class_entry * classcache_find_loader(
1010                                                                         classcache_name_entry * entry,
1011                                                                         classloader * loader)
1012 {
1013         classcache_class_entry *clsen;
1014         classcache_loader_entry *lden;
1015
1016         assert(entry);
1017
1018         /* iterate over all class entries */
1019         for (clsen = entry->classes; clsen; clsen = clsen->next) {
1020
1021                 /* check if this entry has already been loaded by initloader */
1022                 for (lden = clsen->loaders; lden; lden = lden->next) {
1023                         if (lden->loader == loader)
1024                                 return clsen;   /* found */
1025                 }
1026
1027                 /* check if loader is constrained to this entry */
1028                 for (lden = clsen->constraints; lden; lden = lden->next) {
1029                         if (lden->loader == loader)
1030                                 return clsen;   /* found */
1031                 }
1032         }
1033
1034         /* not found */
1035         return NULL;
1036 }
1037
1038 /* classcache_free_class_entry *************************************************
1039
1040    Free the memory used by a class entry
1041
1042    IN:
1043        clsen............the classcache_class_entry to free
1044
1045 *******************************************************************************/
1046
1047 static void classcache_free_class_entry(classcache_class_entry * clsen)
1048 {
1049         classcache_loader_entry *lden;
1050         classcache_loader_entry *next;
1051
1052         assert(clsen);
1053
1054         for (lden = clsen->loaders; lden; lden = next) {
1055                 next = lden->next;
1056                 FREE(lden, classcache_loader_entry);
1057         }
1058         for (lden = clsen->constraints; lden; lden = next) {
1059                 next = lden->next;
1060                 FREE(lden, classcache_loader_entry);
1061         }
1062
1063         FREE(clsen, classcache_class_entry);
1064 }
1065
1066 /* classcache_remove_class_entry ***********************************************
1067
1068    Remove a classcache_class_entry from the list of possible resolution of
1069    a name entry
1070    (internally used helper function)
1071
1072    IN:
1073        entry............the classcache_name_entry
1074        clsen............the classcache_class_entry to remove
1075
1076 *******************************************************************************/
1077
1078 static void classcache_remove_class_entry(classcache_name_entry * entry,
1079                                                                                   classcache_class_entry * clsen)
1080 {
1081         classcache_class_entry **chain;
1082
1083         assert(entry);
1084         assert(clsen);
1085
1086         chain = &(entry->classes);
1087         while (*chain) {
1088                 if (*chain == clsen) {
1089                         *chain = clsen->next;
1090                         classcache_free_class_entry(clsen);
1091                         return;
1092                 }
1093                 chain = &((*chain)->next);
1094         }
1095 }
1096
1097 /* classcache_free_name_entry **************************************************
1098
1099    Free the memory used by a name entry
1100
1101    IN:
1102        entry............the classcache_name_entry to free
1103
1104 *******************************************************************************/
1105
1106 static void classcache_free_name_entry(classcache_name_entry * entry)
1107 {
1108         classcache_class_entry *clsen;
1109         classcache_class_entry *next;
1110
1111         assert(entry);
1112
1113         for (clsen = entry->classes; clsen; clsen = next) {
1114                 next = clsen->next;
1115                 classcache_free_class_entry(clsen);
1116         }
1117
1118         FREE(entry, classcache_name_entry);
1119 }
1120
1121 /* classcache_free *************************************************************
1122
1123    Free the memory used by the class cache
1124
1125    NOTE:
1126        The class cache may not be used any more after this call, except
1127            when it is reinitialized with classcache_init.
1128
1129    Note: NOT synchronized!
1130
1131 *******************************************************************************/
1132
1133 void classcache_free(void)
1134 {
1135         u4 slot;
1136         classcache_name_entry *entry;
1137         classcache_name_entry *next;
1138
1139         for (slot = 0; slot < hashtable_classcache.size; ++slot) {
1140                 for (entry = (classcache_name_entry *) hashtable_classcache.ptr[slot]; entry; entry = next) {
1141                         next = entry->hashlink;
1142                         classcache_free_name_entry(entry);
1143                 }
1144         }
1145
1146         MFREE(hashtable_classcache.ptr, voidptr, hashtable_classcache.size);
1147         hashtable_classcache.size = 0;
1148         hashtable_classcache.entries = 0;
1149         hashtable_classcache.ptr = NULL;
1150 }
1151
1152 /* classcache_add_constraint ***************************************************
1153
1154    Add a loading constraint
1155
1156    IN:
1157        a................first initiating loader
1158        b................second initiating loader
1159        classname........class name
1160
1161    RETURN VALUE:
1162        true.............everything ok, the constraint has been added,
1163        false............an exception has been thrown.
1164
1165    Note: synchronized with global tablelock
1166
1167 *******************************************************************************/
1168
1169 #if defined(ENABLE_VERIFIER)
1170 bool classcache_add_constraint(classloader * a,
1171                                                            classloader * b,
1172                                                            utf * classname)
1173 {
1174         classcache_name_entry *en;
1175         classcache_class_entry *clsenA;
1176         classcache_class_entry *clsenB;
1177
1178         assert(classname);
1179
1180 #ifdef CLASSCACHE_VERBOSE
1181         fprintf(stderr, "classcache_add_constraint(%p,%p,", (void *) a, (void *) b);
1182         utf_fprint_classname(stderr, classname);
1183         fprintf(stderr, ")\n");
1184 #endif
1185
1186         /* a constraint with a == b is trivially satisfied */
1187         if (a == b) {
1188                 CLASSCACHE_COUNT(stat_trivial_constraints);
1189                 return true;
1190         }
1191
1192         CLASSCACHE_LOCK();
1193
1194         en = classcache_new_name(classname);
1195
1196         assert(en);
1197         CLASSCACHE_COUNT(stat_nontriv_constraints);
1198
1199         /* find the entry loaded by / constrained to each loader */
1200         clsenA = classcache_find_loader(en, a);
1201         clsenB = classcache_find_loader(en, b);
1202
1203         if (clsenA && clsenB) {
1204                 /* { both loaders have corresponding entries } */
1205                 CLASSCACHE_COUNT(stat_nontriv_constraints_both);
1206
1207                 /* if the entries are the same, the constraint is already recorded */
1208                 if (clsenA == clsenB)
1209                         goto return_success;
1210
1211                 /* check if the entries can be merged */
1212                 if (clsenA->classobj && clsenB->classobj
1213                         && clsenA->classobj != clsenB->classobj) {
1214                         /* no, the constraint is violated */
1215                         *exceptionptr = exceptions_new_linkageerror(
1216                                                           "loading constraint violated: ",clsenA->classobj);
1217                         goto return_exception;
1218                 }
1219
1220                 /* yes, merge the entries */
1221                 classcache_merge_class_entries(en,clsenA,clsenB);
1222                 CLASSCACHE_COUNT(stat_nontriv_constraints_merged);
1223         }
1224         else {
1225                 /* { at most one of the loaders has a corresponding entry } */
1226
1227                 /* set clsenA to the single class entry we have */
1228                 if (!clsenA)
1229                         clsenA = clsenB;
1230
1231                 if (!clsenA) {
1232                         /* { no loader has a corresponding entry } */
1233                         CLASSCACHE_COUNT(stat_nontriv_constraints_none);
1234
1235                         /* create a new class entry with the constraint (a,b,en->name) */
1236                         clsenA = NEW(classcache_class_entry);
1237                         clsenA->classobj = NULL;
1238                         clsenA->loaders = NULL;
1239                         clsenA->constraints = classcache_new_loader_entry(b, NULL);
1240                         clsenA->constraints = classcache_new_loader_entry(a, clsenA->constraints);
1241
1242                         clsenA->next = en->classes;
1243                         en->classes = clsenA;
1244                 }
1245                 else {
1246                         CLASSCACHE_COUNT(stat_nontriv_constraints_one);
1247
1248                         /* make b the loader that has no corresponding entry */
1249                         if (clsenB)
1250                                 b = a;
1251
1252                         /* loader b must be added to entry clsenA */
1253                         clsenA->constraints = classcache_new_loader_entry(b, clsenA->constraints);
1254                 }
1255         }
1256
1257   return_success:
1258         CLASSCACHE_UNLOCK();
1259         return true;
1260
1261   return_exception:
1262         CLASSCACHE_UNLOCK();
1263         return false;                           /* exception */
1264 }
1265 #endif /* defined(ENABLE_VERIFIER) */
1266
1267 /* classcache_add_constraints_for_params ***************************************
1268
1269    Add loading constraints for the parameters and return type of
1270    the given method.
1271
1272    IN:
1273        a................first initiating loader
1274        b................second initiating loader
1275        m................methodinfo
1276
1277    RETURN VALUE:
1278        true.............everything ok, the constraints have been added,
1279        false............an exception has been thrown.
1280
1281    Note: synchronized with global tablelock
1282
1283 *******************************************************************************/
1284
1285 #if defined(ENABLE_VERIFIER)
1286 bool classcache_add_constraints_for_params(classloader * a,
1287                                                                                    classloader * b,
1288                                                                                    methodinfo *m)
1289 {
1290         methoddesc *md;
1291         typedesc *td;
1292         s4 i;
1293
1294         /* a constraint with a == b is trivially satisfied */
1295
1296         if (a == b) {
1297                 return true;
1298         }
1299
1300         /* get the parsed descriptor */
1301
1302         assert(m);
1303         md = m->parseddesc;
1304         assert(md);
1305
1306         /* constrain the return type */
1307
1308         if (md->returntype.type == TYPE_ADR) {
1309                 if (!classcache_add_constraint(a, b, md->returntype.classref->name))
1310                         return false; /* exception */
1311         }
1312
1313         /* constrain each reference type used in the parameters */
1314
1315         td = md->paramtypes;
1316         i = md->paramcount;
1317         for (; i--; td++) {
1318                 if (td->type != TYPE_ADR)
1319                         continue;
1320
1321                 if (!classcache_add_constraint(a, b, td->classref->name))
1322                         return false; /* exception */
1323         }
1324
1325         /* everything ok */
1326         return true;
1327 }
1328 #endif /* defined(ENABLE_VERIFIER) */
1329
1330 /*============================================================================*/
1331 /* DEBUG DUMPS                                                                */
1332 /*============================================================================*/
1333
1334 /* classcache_debug_dump *******************************************************
1335
1336    Print the contents of the loaded class cache to a stream
1337
1338    IN:
1339        file.............output stream
1340            only.............if != NULL, only print entries for this name
1341                             (Currently we print also the rest of the hash chain to
1342                                                  get a feel for the average length of hash chains.)
1343
1344    Note: synchronized with global tablelock
1345
1346 *******************************************************************************/
1347
1348 #ifndef NDEBUG
1349 void classcache_debug_dump(FILE * file,utf *only)
1350 {
1351         classcache_name_entry *c;
1352         classcache_class_entry *clsen;
1353         classcache_loader_entry *lden;
1354         u4 slot;
1355
1356         CLASSCACHE_LOCK();
1357
1358         fprintf(file, "\n=== [loaded class cache] =====================================\n\n");
1359         fprintf(file, "hash size   : %d\n", (int) hashtable_classcache.size);
1360         fprintf(file, "hash entries: %d\n", (int) hashtable_classcache.entries);
1361         fprintf(file, "\n");
1362
1363         if (only) {
1364                 c = classcache_lookup_name(only);
1365                 slot = 0; /* avoid compiler warning */
1366                 goto dump_it;
1367         }
1368
1369         for (slot = 0; slot < hashtable_classcache.size; ++slot) {
1370                 c = (classcache_name_entry *) hashtable_classcache.ptr[slot];
1371
1372 dump_it:
1373                 for (; c; c = c->hashlink) {
1374                         utf_fprint_classname(file, c->name);
1375                         fprintf(file, "\n");
1376
1377                         /* iterate over all class entries */
1378                         for (clsen = c->classes; clsen; clsen = clsen->next) {
1379                                 if (clsen->classobj) {
1380                                         fprintf(file, "    loaded %p\n", (void *) clsen->classobj);
1381                                 }
1382                                 else {
1383                                         fprintf(file, "    unresolved\n");
1384                                 }
1385                                 fprintf(file, "        loaders:");
1386                                 for (lden = clsen->loaders; lden; lden = lden->next) {
1387                                         fprintf(file, "<%p> %p", (void *) lden, (void *) lden->loader);
1388                                 }
1389                                 fprintf(file, "\n        constraints:");
1390                                 for (lden = clsen->constraints; lden; lden = lden->next) {
1391                                         fprintf(file, "<%p> %p", (void *) lden, (void *) lden->loader);
1392                                 }
1393                                 fprintf(file, "\n");
1394                         }
1395                 }
1396
1397                 if (only)
1398                         break;
1399         }
1400         fprintf(file, "\n==============================================================\n\n");
1401
1402         CLASSCACHE_UNLOCK();
1403 }
1404 #endif /* NDEBUG */
1405
1406 /*
1407  * These are local overrides for various environment variables in Emacs.
1408  * Please do not remove this and leave it at the end of the file, where
1409  * Emacs will automagically detect them.
1410  * ---------------------------------------------------------------------
1411  * Local variables:
1412  * mode: c
1413  * indent-tabs-mode: t
1414  * c-basic-offset: 4
1415  * tab-width: 4
1416  * End:
1417  * vim:noexpandtab:sw=4:ts=4:
1418  */