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