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