src/vm/classcache.c

   1 /* vm/classcache.c - loaded class cache and loading constraints
   2
   3    Copyright (C) 1996-2005 R. Grafl, A. Krall, C. Kruegel, C. Oates,
   4    R. Obermaisser, M. Platter, M. Probst, S. Ring, E. Steiner,
   5    C. Thalinger, D. Thuernbeck, P. Tomsich, C. Ullrich, J. Wenninger,
   6    Institut f. Computersprachen - TU Wien
   7
   8    This file is part of CACAO.
   9
  10    This program is free software; you can redistribute it and/or
  11    modify it under the terms of the GNU General Public License as
  12    published by the Free Software Foundation; either version 2, or (at
  13    your option) any later version.
  14
  15    This program is distributed in the hope that it will be useful, but
  16    WITHOUT ANY WARRANTY; without even the implied warranty of
  17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18    General Public License for more details.
  19
  20    You should have received a copy of the GNU General Public License
  21    along with this program; if not, write to the Free Software
  22    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  23    02111-1307, USA.
  24
  25    Contact: cacao@complang.tuwien.ac.at
  26
  27    Authors: Edwin Steiner
  28
  29    Changes:
  30
  31    $Id: classcache.c 2083 2005-03-25 14:25:15Z edwin $
  32
  33 */
  34
  35 #include <assert.h>
  36 #include "vm/classcache.h"
  37 #include "vm/tables.h"
  38 #include "vm/utf8.h"
  39 #include "vm/exceptions.h"
  40 #include "mm/memory.h"
  41
  42 /* initial number of slots in the classcache hash table */
  43 #define CLASSCACHE_INIT_SIZE  2048
  44
  45 /*============================================================================*/
  46 /* DEBUG HELPERS                                                              */
  47 /*============================================================================*/
  48
  49 #ifndef NDEBUG
  50 #define CLASSCACHE_DEBUG
  51 #endif
  52
  53 #ifdef CLASSCACHE_DEBUG
  54 #define CLASSCACHE_ASSERT(cond)  assert(cond)
  55 #else
  56 #define CLASSCACHE_ASSERT(cond)
  57 #endif
  58
  59 /*============================================================================*/
  60 /* GLOBAL VARIABLES                                                           */
  61 /*============================================================================*/
  62
  63 static hashtable classcache_hash;
  64
  65 /*============================================================================*/
  66 /*                                                                            */
  67 /*============================================================================*/
  68
  69 /* classcache_init *************************************************************
  70
  71    Initialize the loaded class cache
  72
  73 *******************************************************************************/
  74
  75 void
  76 classcache_init()
  77 {
  78         init_hashtable(&classcache_hash,CLASSCACHE_INIT_SIZE);
  79 }
  80
  81 /* classcache_new_loader_entry *************************************************
  82
  83    Create a new classcache_loader_entry struct
  84    (internally used helper function)
  85
  86    IN:
  87        loader...........the ClassLoader object
  88            next.............the next classcache_loader_entry
  89
  90    RETURN VALUE:
  91        the new classcache_loader_entry
  92
  93 *******************************************************************************/
  94
  95 static classcache_loader_entry *
  96 classcache_new_loader_entry(classloader *loader,classcache_loader_entry *next)
  97 {
  98         classcache_loader_entry *lden;
  99
 100         lden = NEW(classcache_loader_entry);
 101         lden->loader = loader;
 102         lden->next = next;
 103
 104         return lden;
 105 }
 106
 107 /* classcache_merge_loaders ****************************************************
 108
 109    Merge two lists of loaders into one
 110    (internally used helper function)
 111
 112    IN:
 113        lista............first list (may be NULL)
 114            listb............second list (may be NULL)
 115
 116    RETURN VALUE:
 117        the merged list (may be NULL)
 118
 119    NOTE:
 120        The lists given as arguments are destroyed!
 121
 122 *******************************************************************************/
 123
 124 static classcache_loader_entry *
 125 classcache_merge_loaders(classcache_loader_entry *lista,
 126                                  classcache_loader_entry *listb)
 127 {
 128         classcache_loader_entry *result;
 129         classcache_loader_entry *ldenA;
 130         classcache_loader_entry *ldenB;
 131         classcache_loader_entry **chain;
 132
 133         /* XXX This is a quadratic algorithm. If this ever
 134          * becomes a problem, the loader lists should be
 135          * stored as sorted lists and merged in linear time. */
 136
 137         result = NULL;
 138         chain = &result;
 139
 140         for (ldenA=lista; ldenA; ldenA=ldenA->next) {
 141
 142                 for (ldenB=listb; ldenB; ldenB=ldenB->next) {
 143                         if (ldenB->loader == ldenA->loader)
 144                                 goto common_element;
 145                 }
 146
 147                 /* this loader is only in lista */
 148                 *chain = ldenA;
 149                 chain = &(ldenA->next);
 150
 151 common_element:
 152                 /* XXX free the duplicated element */
 153                 ;
 154         }
 155
 156         /* concat listb to the result */
 157         *chain = listb;
 158
 159         return result;
 160 }
 161
 162 /* classcache_lookup_name ******************************************************
 163
 164    Lookup a name in the first level of the cache
 165    (internally used helper function)
 166
 167    IN:
 168        name.............the name to look up
 169
 170    RETURN VALUE:
 171        a pointer to the classcache_name_entry for this name, or
 172        null if no entry was found.
 173
 174 *******************************************************************************/
 175
 176 static classcache_name_entry *
 177 classcache_lookup_name(utf *name)
 178 {
 179         classcache_name_entry * c;     /* hash table element */
 180         u4 key;           /* hashkey computed from classname */
 181         u4 slot;          /* slot in hashtable               */
 182         u2 i;
 183
 184         key  = utf_hashkey(name->text, name->blength);
 185         slot = key & (classcache_hash.size - 1);
 186         c    = classcache_hash.ptr[slot];
 187
 188         /* search external hash chain for the entry */
 189         while (c) {
 190                 if (c->name->blength == name->blength) {
 191                         for (i = 0; i < name->blength; i++)
 192                                 if (name->text[i] != c->name->text[i]) goto nomatch;
 193
 194                         /* entry found in hashtable */
 195                         return c;
 196                 }
 197
 198         nomatch:
 199                 c = c->hashlink; /* next element in external chain */
 200         }
 201
 202         /* not found */
 203         return NULL;
 204 }
 205
 206 /* classcache_new_name *********************************************************
 207
 208    Return a classcache_name_entry for the given name. The entry is created
 209    if it is not already in the cache.
 210    (internally used helper function)
 211
 212    IN:
 213        name.............the name to look up / create an entry for
 214
 215    RETURN VALUE:
 216        a pointer to the classcache_name_entry for this name
 217
 218 *******************************************************************************/
 219
 220 static classcache_name_entry *
 221 classcache_new_name(utf *name)
 222 {
 223         classcache_name_entry * c;     /* hash table element */
 224         u4 key;           /* hashkey computed from classname */
 225         u4 slot;          /* slot in hashtable               */
 226         u2 i;
 227
 228         key  = utf_hashkey(name->text, name->blength);
 229         slot = key & (classcache_hash.size - 1);
 230         c    = classcache_hash.ptr[slot];
 231
 232         /* search external hash chain for the entry */
 233         while (c) {
 234                 if (c->name->blength == name->blength) {
 235                         for (i = 0; i < name->blength; i++)
 236                                 if (name->text[i] != c->name->text[i]) goto nomatch;
 237
 238                         /* entry found in hashtable */
 239                         return c;
 240                 }
 241
 242         nomatch:
 243                 c = c->hashlink; /* next element in external chain */
 244         }
 245
 246         /* location in hashtable found, create new entry */
 247
 248         c = NEW(classcache_name_entry);
 249
 250         c->name = name;
 251         c->classes = NULL;
 252
 253         /* insert entry into hashtable */
 254         c->hashlink = classcache_hash.ptr[slot];
 255         classcache_hash.ptr[slot] = c;
 256
 257         /* update number of hashtable-entries */
 258         classcache_hash.entries++;
 259
 260         if (classcache_hash.entries > (classcache_hash.size * 2)) {
 261
 262                 /* reorganization of hashtable, average length of
 263                    the external chains is approx. 2                */
 264
 265                 u4 i;
 266                 classcache_name_entry *c;
 267                 hashtable newhash;  /* the new hashtable */
 268
 269                 /* create new hashtable, double the size */
 270                 init_hashtable(&newhash, classcache_hash.size * 2);
 271                 newhash.entries = classcache_hash.entries;
 272
 273                 /* transfer elements to new hashtable */
 274                 for (i = 0; i < classcache_hash.size; i++) {
 275                         c = (classcache_name_entry *) classcache_hash.ptr[i];
 276                         while (c) {
 277                                 classcache_name_entry *nextc = c->hashlink;
 278                                 u4 slot = (utf_hashkey(c->name->text, c->name->blength)) & (newhash.size - 1);
 279
 280                                 c->hashlink = newhash.ptr[slot];
 281                                 newhash.ptr[slot] = c;
 282
 283                                 c = nextc;
 284                         }
 285                 }
 286
 287                 /* dispose old table */
 288                 MFREE(classcache_hash.ptr, void*, classcache_hash.size);
 289                 classcache_hash = newhash;
 290         }
 291
 292         return c;
 293 }
 294
 295 /* classcache_lookup ***********************************************************
 296
 297    Lookup a possibly loaded class
 298
 299    IN:
 300        initloader.......initiating loader for resolving the class name
 301        classname........class name to look up
 302
 303    RETURN VALUE:
 304        The return value is a pointer to the cached class object,
 305        or NULL, if the class is not in the cache.
 306
 307 *******************************************************************************/
 308
 309 classinfo *
 310 classcache_lookup(classloader *initloader,utf *classname)
 311 {
 312         classcache_name_entry *en;
 313         classcache_class_entry *clsen;
 314         classcache_loader_entry *lden;
 315
 316         en = classcache_lookup_name(classname);
 317
 318         if (en) {
 319                 /* iterate over all class entries */
 320                 for (clsen=en->classes; clsen; clsen=clsen->next) {
 321                         /* check if this entry has been loaded by initloader */
 322                         for (lden=clsen->loaders; lden; lden=lden->next) {
 323                                 if (lden->loader == initloader) {
 324                                         /* found the loaded class entry */
 325                                         CLASSCACHE_ASSERT(clsen->classobj);
 326                                         return clsen->classobj;
 327                                 }
 328                         }
 329                 }
 330         }
 331
 332         /* not found */
 333         return NULL;
 334 }
 335
 336 /* classcache_store ************************************************************
 337
 338    Store a loaded class
 339
 340    IN:
 341        initloader.......initiating loader used to load the class
 342        cls..............class object to cache
 343
 344    RETURN VALUE:
 345        true.............everything ok, the class was stored in
 346                         the cache if necessary,
 347        false............an exception has been thrown.
 348
 349 *******************************************************************************/
 350
 351 bool
 352 classcache_store(classloader *initloader,classinfo *cls)
 353 {
 354         classcache_name_entry *en;
 355         classcache_class_entry *clsen;
 356         classcache_loader_entry *lden;
 357
 358         CLASSCACHE_ASSERT(cls);
 359
 360         /* XXX lock table */
 361
 362         en = classcache_new_name(cls->name);
 363
 364         CLASSCACHE_ASSERT(en);
 365
 366         /* iterate over all class entries */
 367         for (clsen=en->classes; clsen; clsen=clsen->next) {
 368
 369 #ifdef CLASSCACHE_DEBUG
 370                 /* check if this entry has already been loaded by initloader */
 371                 /* It never should have been loaded before! */
 372                 for (lden=clsen->loaders; lden; lden=lden->next) {
 373                         if (lden->loader == initloader)
 374                                 CLASSCACHE_ASSERT(false);
 375                 }
 376 #endif
 377
 378                 /* check if initloader is constrained to this entry */
 379                 for (lden=clsen->constraints; lden; lden=lden->next) {
 380                         if (lden->loader == initloader) {
 381                                 /* we have to use this entry */
 382                                 /* check if is has already been resolved to another class */
 383                                 if (clsen->classobj && clsen->classobj != cls) {
 384                                         /* a loading constraint is violated */
 385                                         *exceptionptr = new_exception_message(string_java_lang_LinkageError,
 386                                                         "loading constraint violated XXX add message");
 387                                         return false; /* exception */
 388                                 }
 389
 390                                 /* record initloader as initiating loader */
 391                                 clsen->loaders = classcache_new_loader_entry(initloader,clsen->loaders);
 392
 393                                 /* record the loaded class object */
 394                                 clsen->classobj = cls;
 395
 396                                 /* done */
 397                                 return true;
 398                         }
 399                 }
 400
 401         }
 402
 403         /* create a new class entry for this class object with */
 404         /* initiating loader initloader                        */
 405
 406         clsen = NEW(classcache_class_entry);
 407         clsen->classobj = cls;
 408         clsen->loaders = classcache_new_loader_entry(initloader,NULL);
 409         clsen->constraints = NULL;
 410
 411         clsen->next = en->classes;
 412         en->classes = clsen;
 413
 414         /* done */
 415         return true;
 416 }
 417
 418 /* classcache_find_loader ******************************************************
 419
 420    Find the class entry loaded by or constrained to a given loader
 421    (internally used helper function)
 422
 423    IN:
 424        entry............the classcache_name_entry
 425        loader...........the loader to look for
 426
 427    RETURN VALUE:
 428        the classcache_class_entry for the given loader, or
 429            NULL if no entry was found
 430
 431 *******************************************************************************/
 432
 433 static classcache_class_entry *
 434 classcache_find_loader(classcache_name_entry *entry,classloader *loader)
 435 {
 436         classcache_class_entry *clsen;
 437         classcache_loader_entry *lden;
 438
 439         CLASSCACHE_ASSERT(entry);
 440
 441         /* iterate over all class entries */
 442         for (clsen=entry->classes; clsen; clsen=clsen->next) {
 443
 444                 /* check if this entry has already been loaded by initloader */
 445                 for (lden=clsen->loaders; lden; lden=lden->next) {
 446                         if (lden->loader == loader)
 447                                 return clsen; /* found */
 448                 }
 449
 450                 /* check if loader is constrained to this entry */
 451                 for (lden=clsen->constraints; lden; lden=lden->next) {
 452                         if (lden->loader == loader)
 453                                 return clsen; /* found */
 454                 }
 455         }
 456
 457         /* not found */
 458         return NULL;
 459 }
 460
 461 /* classcache_free_class_entry *************************************************
 462
 463    Free the memory used by a class entry
 464
 465    IN:
 466        clsen............the classcache_class_entry to free
 467
 468 *******************************************************************************/
 469
 470 static void
 471 classcache_free_class_entry(classcache_class_entry *clsen)
 472 {
 473         classcache_loader_entry *lden;
 474         classcache_loader_entry *next;
 475
 476         CLASSCACHE_ASSERT(clsen);
 477
 478         for (lden=clsen->loaders; lden; lden=next) {
 479                 next = lden->next;
 480                 FREE(lden,classcache_loader_entry);
 481         }
 482         for (lden=clsen->constraints; lden; lden=next) {
 483                 next = lden->next;
 484                 FREE(lden,classcache_loader_entry);
 485         }
 486
 487         FREE(clsen,classcache_class_entry);
 488 }
 489
 490 /* classcache_remove_class_entry ***********************************************
 491
 492    Remove a classcache_class_entry from the list of possible resolution of
 493    a name entry
 494    (internally used helper function)
 495
 496    IN:
 497        entry............the classcache_name_entry
 498        clsen............the classcache_class_entry to remove
 499
 500 *******************************************************************************/
 501
 502 static void
 503 classcache_remove_class_entry(classcache_name_entry *entry,
 504                                                           classcache_class_entry *clsen)
 505 {
 506         classcache_class_entry **chain;
 507
 508         CLASSCACHE_ASSERT(entry);
 509         CLASSCACHE_ASSERT(clsen);
 510
 511         chain = &(entry->classes);
 512         while (*chain) {
 513                 if (*chain == clsen) {
 514                         *chain = clsen->next;
 515                         classcache_free_class_entry(clsen);
 516                         return;
 517                 }
 518                 chain = &((*chain)->next);
 519         }
 520 }
 521
 522 /* classcache_free_name_entry **************************************************
 523
 524    Free the memory used by a name entry
 525
 526    IN:
 527        entry............the classcache_name_entry to free
 528
 529 *******************************************************************************/
 530
 531 static void
 532 classcache_free_name_entry(classcache_name_entry *entry)
 533 {
 534         classcache_class_entry *clsen;
 535         classcache_class_entry *next;
 536
 537         CLASSCACHE_ASSERT(entry);
 538
 539         for (clsen=entry->classes; clsen; clsen=next) {
 540                 next = clsen->next;
 541                 classcache_free_class_entry(clsen);
 542         }
 543
 544         FREE(entry,classcache_name_entry);
 545 }
 546
 547 /* classcache_free *************************************************************
 548
 549    Free the memory used by the class cache
 550
 551    NOTE:
 552        The class cache may not be used any more after this call, except
 553            when it is reinitialized with classcache_init.
 554
 555 *******************************************************************************/
 556
 557 void
 558 classcache_free()
 559 {
 560         u4 slot;
 561         classcache_name_entry *entry;
 562         classcache_name_entry *next;
 563
 564         for (slot=0; slot<classcache_hash.size; ++slot) {
 565                 for (entry=(classcache_name_entry *)classcache_hash.ptr[slot];
 566                          entry;
 567                          entry = next)
 568                 {
 569                         next = entry->hashlink;
 570                         classcache_free_name_entry(entry);
 571                 }
 572         }
 573
 574         MFREE(classcache_hash.ptr,voidptr,classcache_hash.size);
 575         classcache_hash.size = 0;
 576         classcache_hash.entries = 0;
 577         classcache_hash.ptr = NULL;
 578 }
 579
 580 /* classcache_add_constraint ***************************************************
 581
 582    Add a loading constraint
 583
 584    IN:
 585        a................first initiating loader
 586        b................second initiating loader
 587        classname........class name
 588
 589    RETURN VALUE:
 590        true.............everything ok, the constraint has been added,
 591        false............an exception has been thrown.
 592
 593 *******************************************************************************/
 594
 595 bool
 596 classcache_add_constraint(classloader *a,classloader *b,utf *classname)
 597 {
 598         classcache_name_entry *en;
 599         classcache_class_entry *clsenA;
 600         classcache_class_entry *clsenB;
 601
 602         CLASSCACHE_ASSERT(classname);
 603
 604 #ifdef CLASSCACHE_DEBUG
 605         fprintf(stderr,"classcache_add_constraint(%p,%p,",a,b);
 606         utf_fprint_classname(stderr,classname);
 607         fprintf(stderr,")\n");
 608 #endif
 609
 610         /* a constraint with a == b is trivially satisfied */
 611         if (a == b)
 612                 return true;
 613
 614         /* XXX lock table */
 615
 616         en = classcache_new_name(classname);
 617
 618         CLASSCACHE_ASSERT(en);
 619
 620         /* find the entry loaded by / constrained to each loader */
 621         clsenA = classcache_find_loader(en,a);
 622         clsenB = classcache_find_loader(en,b);
 623
 624         if (clsenA && clsenB) {
 625                 /* { both loaders have corresponding entries } */
 626
 627                 /* if the entries are the same, the constraint is already recorded */
 628                 if (clsenA == clsenB)
 629                         return true;
 630
 631                 /* check if the entries can be merged */
 632                 if (clsenA->classobj && clsenB->classobj && clsenA->classobj != clsenB->classobj) {
 633                         /* no, the constraint is violated */
 634                         *exceptionptr = new_exception_message(string_java_lang_LinkageError,
 635                                         "loading constraint violated XXX add message");
 636                         return false; /* exception */
 637                 }
 638
 639                 /* yes, merge the entries */
 640                 /* clsenB will be merged into clsenA */
 641                 clsenA->loaders = classcache_merge_loaders(clsenA->loaders,
 642                                                                                                    clsenB->loaders);
 643
 644                 clsenA->constraints = classcache_merge_loaders(clsenA->constraints,
 645                                                                                                            clsenB->constraints);
 646
 647                 if (!clsenA->classobj)
 648                         clsenA->classobj = clsenB->classobj;
 649
 650                 /* remove clsenB from the list of class entries */
 651                 classcache_remove_class_entry(en,clsenB);
 652         }
 653         else {
 654                 /* { at most one of the loaders has a corresponding entry } */
 655
 656                 /* set clsenA to the single class entry we have */
 657                 if (!clsenA)
 658                         clsenA = clsenB;
 659
 660                 if (!clsenA) {
 661                         /* { no loader has a corresponding entry } */
 662
 663                         /* create a new class entry with the constraint (a,b,en->name) */
 664                         clsenA = NEW(classcache_class_entry);
 665                         clsenA->classobj = NULL;
 666                         clsenA->loaders = NULL;
 667                         clsenA->constraints = classcache_new_loader_entry(b,NULL);
 668                         clsenA->constraints = classcache_new_loader_entry(a,clsenA->constraints);
 669
 670                         clsenA->next = en->classes;
 671                         en->classes = clsenA;
 672                 }
 673                 else {
 674                         /* make b the loader that has no corresponding entry */
 675                         if (clsenB)
 676                                 b = a;
 677
 678                         /* loader b must be added to entry clsenA */
 679                         clsenA->constraints = classcache_new_loader_entry(b,clsenA->constraints);
 680                 }
 681         }
 682
 683         /* done */
 684         return true;
 685 }
 686
 687 /*============================================================================*/
 688 /* DEBUG DUMPS                                                                */
 689 /*============================================================================*/
 690
 691 /* classcache_debug_dump *******************************************************
 692
 693    Print the contents of the loaded class cache to a stream
 694
 695    IN:
 696        file.............output stream
 697
 698 *******************************************************************************/
 699
 700 void
 701 classcache_debug_dump(FILE *file)
 702 {
 703         classcache_name_entry *c;
 704         classcache_class_entry *clsen;
 705         classcache_loader_entry *lden;
 706         u4 slot;
 707
 708         fprintf(file,"\n=== [loaded class cache] =====================================\n\n");
 709         fprintf(file,"hash size   : %d\n",classcache_hash.size);
 710         fprintf(file,"hash entries: %d\n",classcache_hash.entries);
 711         fprintf(file,"\n");
 712
 713         for (slot=0; slot<classcache_hash.size; ++slot) {
 714                 c = (classcache_name_entry *) classcache_hash.ptr[slot];
 715
 716                 for (; c; c=c->hashlink) {
 717                         utf_fprint_classname(file,c->name);
 718                         fprintf(file,"\n");
 719
 720                         /* iterate over all class entries */
 721                         for (clsen=c->classes; clsen; clsen=clsen->next) {
 722                                 fprintf(file,"    %s\n",(clsen->classobj) ? "loaded" : "unresolved");
 723                                 fprintf(file,"    loaders:");
 724                                 for (lden=clsen->loaders; lden; lden=lden->next) {
 725                                         fprintf(file," %p",(void *)lden->loader);
 726                                 }
 727                                 fprintf(file,"\n    constraints:");
 728                                 for (lden=clsen->constraints; lden; lden=lden->next) {
 729                                         fprintf(file," %p",(void *)lden->loader);
 730                                 }
 731                                 fprintf(file,"\n");
 732                         }
 733                 }
 734         }
 735         fprintf(file,"\n==============================================================\n\n");
 736 }
 737
 738 /*
 739  * These are local overrides for various environment variables in Emacs.
 740  * Please do not remove this and leave it at the end of the file, where
 741  * Emacs will automagically detect them.
 742  * ---------------------------------------------------------------------
 743  * Local variables:
 744  * mode: c
 745  * indent-tabs-mode: t
 746  * c-basic-offset: 4
 747  * tab-width: 4
 748  * End:
 749  * vim:noexpandtab:sw=4:ts=4:
 750  */
 751