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