tables.c

   1 /* -*- mode: c; tab-width: 4; c-basic-offset: 4 -*- */
   2 /****************************** tables.c ***************************************
   3
   4         Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
   5
   6         See file COPYRIGHT for information on usage and disclaimer of warranties
   7
   8         Enth"alt Supportfunktionen f"ur:
   9                 - Lesen von JavaClass-Files
  10             - unicode-Symbole
  11                 - den Heap
  12                 - zus"atzliche Support-Funktionen
  13
  14         Authors: Reinhard Grafl      EMAIL: cacao@complang.tuwien.ac.at
  15         Changes: Mark Probst         EMAIL: cacao@complang.tuwien.ac.at
  16                  Andreas  Krall      EMAIL: cacao@complang.tuwien.ac.at
  17
  18         Last Change: 1998/03/24
  19
  20 *******************************************************************************/
  21
  22 #include <assert.h>
  23 #include <sys/mman.h>
  24 #include <unistd.h>
  25 #include "global.h"
  26 #include "tables.h"
  27 #include "asmpart.h"
  28 #include "callargs.h"
  29
  30 #include "threads/thread.h"                  /* schani */
  31 #include "threads/locks.h"
  32
  33
  34 bool runverbose = false;
  35
  36 int count_unicode_len = 0;
  37
  38
  39 /******************************************************************************
  40 ************************* Der Dateien-Sauger **********************************
  41 *******************************************************************************
  42
  43         dient zum Behandeln von Java-ClassFiles ("offnen, schlie"sen,
  44         einlesen von 8-, 16-, 32-, 64-bit Integers und 32-, 64- bit Floats)
  45
  46 ******************************************************************************/
  47
  48 static FILE *classfile = NULL;   /* File-handle der gerade gelesenen Datei */
  49 static char *classpath = "";     /* Suchpfad f"ur die ClassFiles */
  50
  51
  52
  53 /************************** Funktion: suck_init ******************************
  54
  55         Wird zu Programmstart einmal aufgerufen und setzt den Suchpfad f"ur
  56         Klassenfiles
  57
  58 ******************************************************************************/
  59
  60 void suck_init (char *cpath)
  61 {
  62         classfile = NULL;
  63         classpath = cpath;
  64 }
  65
  66
  67 /************************** Funktion: suck_start ******************************
  68
  69         "Offnet die Datei f"ur die Klasse des gegebenen Namens zum Lesen.
  70         Dabei werden alle im Suchpfad angegebenen Verzeichnisse durchsucht,
  71         bis eine entsprechende Datei  ( <classname>.class) gefunden wird.
  72
  73 ******************************************************************************/
  74
  75 bool suck_start (unicode *classname)
  76 {
  77 #define MAXFILENAME 1000           /* Maximale Langes des Dateinamens plus Pfad */
  78
  79         char filename[MAXFILENAME+10];   /* Platz fuer '.class' */
  80         u2 filenamelen;
  81         char *pathpos;
  82         u2 i,c;
  83
  84
  85         pathpos = classpath;
  86
  87         while (*pathpos) {
  88                 while ( *pathpos == ':' ) pathpos++;
  89
  90                 filenamelen=0;
  91                 while ( (*pathpos) && (*pathpos!=':') ) {
  92                     PANICIF (filenamelen >= MAXFILENAME, "Filename too long") ;
  93
  94                         filename[filenamelen++] = *(pathpos++);
  95                         }
  96
  97                 filename[filenamelen++] = '/';
  98
  99                 for (i=0; i < classname -> length; i++) {
 100                         PANICIF (filenamelen >= MAXFILENAME, "Filename too long");
 101
 102                         c = classname -> text [i];
 103                         if (c=='/') c = '/';     /* Slashes im Namen passen zu UNIX */
 104                         else {
 105                                 if ( c<=' ' || c>'z') {
 106                                         c = '?';
 107                                         }
 108                                 }
 109
 110                         filename[filenamelen++] = c;
 111                         }
 112
 113                 strcpy (filename+filenamelen, ".class");
 114
 115                 classfile = fopen(filename, "r");
 116                 if (classfile) {
 117                         return true;
 118                         }
 119
 120
 121                 }
 122
 123         sprintf (logtext,"Can not open class file '%s'", filename);
 124         error();
 125         return false;
 126 }
 127
 128
 129 /************************** Funktion: suck_stop *******************************
 130
 131         Schlie"st die offene Datei wieder.
 132
 133 ******************************************************************************/
 134
 135 void suck_stop ()
 136 {
 137         u4 rest=0;
 138         u1 dummy;
 139
 140         while ( fread (&dummy, 1,1, classfile) > 0) rest++;
 141         if (rest) {
 142                 sprintf (logtext,"There are %d access bytes at end of classfile",
 143                                  (int) rest);
 144                 dolog();
 145                 }
 146
 147         fclose (classfile);
 148         classfile = NULL;
 149 }
 150
 151
 152
 153 /************************** Lesefunktionen ***********************************
 154
 155         Lesen von der Datei in verschieden grossen Paketen
 156         (8,16,32,64-bit Integer oder Float)
 157
 158 *****************************************************************************/
 159
 160 void suck_nbytes (u1 *buffer, u4 len)
 161 {
 162         if ( fread (buffer, 1, len, classfile) != len) panic ("Unexpected EOF");
 163 }
 164
 165
 166 void skip_nbytes (u4 len)
 167 {
 168         u4 i;
 169         for (i=0; i<len; i++) suck_u1 ();
 170 }
 171
 172
 173 u1 suck_u1 ()
 174 {
 175         u1 b;
 176         if ( fread (&b, 1,1, classfile) != 1) panic ("Unexpected EOF");
 177         return b;
 178 }
 179
 180 s1 suck_s1 ()
 181 {
 182         s1 b;
 183         if ( fread (&b, 1,1, classfile) != 1) panic ("Unexpected EOF");
 184         return b;
 185 }
 186
 187
 188 u2 suck_u2 ()
 189 {
 190         u1 b[2];
 191         if ( fread (b, 1,2, classfile) != 2) panic ("Unexpected EOF");
 192         return (b[0]<<8) + b[1];
 193 }
 194
 195 s2 suck_s2 ()
 196 {
 197         return suck_u2 ();
 198 }
 199
 200
 201 u4 suck_u4 ()
 202 {
 203         u1 b[4];
 204         u4 v;
 205         if ( fread (b, 1,4, classfile) != 4) panic ("Unexpected EOF");
 206         v = ( ((u4)b[0]) <<24) + ( ((u4)b[1])<<16) + ( ((u4)b[2])<<8) + ((u4)b[3]);
 207         return v;
 208 }
 209
 210 s4 suck_s4 ()
 211 {
 212         s4 v = suck_u4 ();
 213         return v;
 214 }
 215
 216 u8 suck_u8 ()
 217 {
 218 #if U8_AVAILABLE
 219         u8 lo,hi;
 220         hi = suck_u4();
 221         lo = suck_u4();
 222         return (hi<<32) + lo;
 223 #else
 224         u8 v;
 225         v.high = suck_u4();
 226         v.low = suck_u4();
 227         return v;
 228 #endif
 229 }
 230
 231 s8 suck_s8 ()
 232 {
 233         return suck_u8 ();
 234 }
 235
 236
 237 float suck_float ()
 238 {
 239         float f;
 240
 241 #if !WORDS_BIGENDIAN
 242                 u1 buffer[4];
 243                 u2 i;
 244                 for (i=0; i<4; i++) buffer[3-i] = suck_u1 ();
 245                 memcpy ( (u1*) (&f), buffer, 4);
 246 #else
 247                 suck_nbytes ( (u1*) (&f), 4 );
 248 #endif
 249
 250         PANICIF (sizeof(float) != 4, "Incompatible float-format");
 251
 252         return f;
 253 }
 254
 255
 256 double suck_double ()
 257 {
 258         double d;
 259
 260 #if !WORDS_BIGENDIAN
 261                 u1 buffer[8];
 262                 u2 i;
 263                 for (i=0; i<8; i++) buffer[7-i] = suck_u1 ();
 264                 memcpy ( (u1*) (&d), buffer, 8);
 265 #else
 266                 suck_nbytes ( (u1*) (&d), 8 );
 267 #endif
 268
 269         PANICIF (sizeof(double) != 8, "Incompatible double-format" );
 270
 271         return d;
 272 }
 273
 274
 275
 276
 277 /******************************************************************************
 278 ******************** Der Unicode-Symbol-Verwalter *****************************
 279 *******************************************************************************
 280
 281         legt eine Hashtabelle f"ur unicode-Symbole an und verwaltet
 282         das Eintragen neuer Symbole
 283
 284 ******************************************************************************/
 285
 286
 287
 288 #define UNICODESTART  2187      /* Startgr"osse: moeglichst gross und prim */
 289
 290 static u4 unicodeentries;       /* Anzahl der Eintr"age in der Tabelle */
 291 static u4 unicodehashsize;      /* Gr"osse der Tabelle */
 292 static unicode ** unicodehash;  /* Zeiger auf die Tabelle selbst */
 293
 294
 295 /*********************** Funktion: unicode_init ******************************
 296
 297         Initialisiert die unicode-Symboltabelle (muss zu Systemstart einmal
 298         aufgerufen werden)
 299
 300 *****************************************************************************/
 301
 302 void unicode_init ()
 303 {
 304         u4 i;
 305
 306 #ifdef STATISTICS
 307         count_unicode_len += sizeof(unicode*) * unicodehashsize;
 308 #endif
 309
 310         unicodeentries = 0;
 311         unicodehashsize = UNICODESTART;
 312         unicodehash = MNEW (unicode*, unicodehashsize);
 313         for (i=0; i<unicodehashsize; i++) unicodehash[i] = NULL;
 314 }
 315
 316
 317 /*********************** Funktion: unicode_close *****************************
 318
 319         Gibt allen Speicher der Symboltabellen frei.
 320         Parameter: Ein Zeiger auf eine Funktion, die dazu n"otig ist,
 321                    Stringkonstanten (die mit 'unicode_setstringlink'
 322                    Unicode-Symbole gebunden wurden) wieder freizugeben
 323
 324 *****************************************************************************/
 325
 326 void unicode_close (stringdeleter del)
 327 {
 328         unicode *u;
 329         u4 i;
 330
 331         for (i=0; i<unicodehashsize; i++) {
 332                 u = unicodehash[i];
 333                 while (u) {
 334                         unicode *nextu = u->hashlink;
 335
 336                         if (u->string) del (u->string);
 337
 338                         MFREE (u->text, u2, u->length);
 339                         FREE (u, unicode);
 340                         u = nextu;
 341                         }
 342                 }
 343         MFREE (unicodehash, unicode*, unicodehashsize);
 344 }
 345
 346
 347 /********************* Funktion: unicode_display ******************************
 348
 349         Gibt ein unicode-Symbol auf stdout aus (zu Debugzwecken)
 350
 351 ******************************************************************************/
 352
 353 void unicode_display (unicode *u)
 354 {
 355         u2 i,c;
 356         for (i=0; i < u->length; i++) {
 357                 c = u->text[i];
 358                 if (c>=32 && c<=127) printf ("%c",c);
 359                                 else printf ("?");
 360                 }
 361         fflush (stdout);
 362 }
 363
 364
 365 /********************* Funktion: unicode_sprint ******************************
 366
 367         Schreibt ein unicode-Symbol in einen C-String
 368
 369 ******************************************************************************/
 370
 371 void unicode_sprint (char *buffer, unicode *u)
 372 {
 373         u2 i;
 374         for (i=0; i < u->length; i++) buffer[i] = u->text[i];
 375         buffer[i] = '\0';
 376 }
 377
 378
 379 /********************* Funktion: unicode_fprint ******************************
 380
 381         Schreibt ein unicode-Symbol auf eine Datei aus
 382
 383 ******************************************************************************/
 384
 385 void unicode_fprint (FILE *file, unicode *u)
 386 {
 387         u2 i;
 388         for (i=0; i < u->length; i++) putc (u->text[i], file);
 389 }
 390
 391
 392 /****************** interne Funktion: u_hashkey ******************************/
 393
 394 static u4 u_hashkey (u2 *text, u2 length)
 395 {
 396         u4 k = 0;
 397         u2 i,sh=0;
 398
 399         for (i=0; i<length; i++) {
 400                 k ^=  ( ((u4) (text[i])) << sh );
 401                 if (sh<16) sh++;
 402                      else  sh=0;
 403                 }
 404
 405         return k;
 406 }
 407
 408 /*************** interne Funktion: u_reorganizehash **************************/
 409
 410 static void u_reorganizehash ()
 411 {
 412         u4 i;
 413         unicode *u;
 414
 415         u4 newhashsize = unicodehashsize*2;
 416         unicode **newhash = MNEW (unicode*, newhashsize);
 417
 418 #ifdef STATISTICS
 419         count_unicode_len += sizeof(unicode*) * unicodehashsize;
 420 #endif
 421
 422         for (i=0; i<newhashsize; i++) newhash[i] = NULL;
 423
 424         for (i=0; i<unicodehashsize; i++) {
 425                 u = unicodehash[i];
 426                 while (u) {
 427                         unicode *nextu = u -> hashlink;
 428                         u4 slot = (u->key) % newhashsize;
 429
 430                         u->hashlink = newhash[slot];
 431                         newhash[slot] = u;
 432
 433                         u = nextu;
 434                         }
 435                 }
 436
 437         MFREE (unicodehash, unicode*, unicodehashsize);
 438         unicodehash = newhash;
 439         unicodehashsize = newhashsize;
 440 }
 441
 442
 443 /****************** Funktion: unicode_new_u2 **********************************
 444
 445         Legt ein neues unicode-Symbol an. Der Text des Symbols wird dieser
 446         Funktion als u2-Array "ubergeben
 447
 448 ******************************************************************************/
 449
 450 unicode *unicode_new_u2 (u2 *text, u2 length)
 451 {
 452         u4 key = u_hashkey (text, length);
 453         u4 slot = key % unicodehashsize;
 454         unicode *u = unicodehash[slot];
 455         u2 i;
 456
 457         while (u) {
 458                 if (u->key == key) {
 459                         if (u->length == length) {
 460                                 for (i=0; i<length; i++) {
 461                                         if (text[i] != u->text[i]) goto nomatch;
 462                                         }
 463                                         return u;
 464                                 }
 465                         }
 466                 nomatch:
 467                 u = u->hashlink;
 468                 }
 469
 470 #ifdef STATISTICS
 471         count_unicode_len += sizeof(unicode) + 2 * length;
 472 #endif
 473
 474         u = NEW (unicode);
 475         u->key = key;
 476         u->length = length;
 477         u->text = MNEW (u2, length);
 478         u->class = NULL;
 479         u->string = NULL;
 480         u->hashlink = unicodehash[slot];
 481         unicodehash[slot] = u;
 482         for (i=0; i<length; i++) u->text[i] = text[i];
 483
 484         unicodeentries++;
 485
 486         if ( unicodeentries > (unicodehashsize/2)) u_reorganizehash();
 487
 488         return u;
 489 }
 490
 491
 492 /********************* Funktion: unicode_new_char *****************************
 493
 494         Legt ein neues unicode-Symbol an. Der Text des Symbols wird dieser
 495         Funktion als C-String ( = char* ) "ubergeben
 496
 497 ******************************************************************************/
 498
 499 unicode *unicode_new_char (char *text)
 500 {
 501 #define MAXNEWCHAR 500
 502         u2 buffer[MAXNEWCHAR];
 503         u2 length = 0;
 504         u1 c;
 505
 506         while ( (c = *text) != '\0' ) {
 507                 if (length>=MAXNEWCHAR) panic ("Text too long in unicode_new_char");
 508                 buffer[length++] = c;
 509                 text ++;
 510                 }
 511         return unicode_new_u2 (buffer, length);
 512 }
 513
 514
 515 /********************** Funktion: unicode_setclasslink ************************
 516
 517         H"angt einen Verweis auf eine Klasse an ein unicode-Symbol an.
 518
 519 ******************************************************************************/
 520
 521 void unicode_setclasslink (unicode *u, classinfo *class)
 522 {
 523         PANICIF (u->class, "Attempt to attach class to already attached symbol");
 524         u->class = class;
 525 }
 526
 527 /********************** Funktion: unicode_getclasslink ************************
 528
 529         Sucht den Verweis von einem unicode-Symbol auf eine Klasse.
 530         Wenn keine solche Klasse existiert, dann wird ein Fehler
 531         ausgegeben.
 532
 533 ******************************************************************************/
 534
 535 classinfo *unicode_getclasslink (unicode *u)
 536 {
 537         PANICIF (!u->class, "Attempt to get unknown class-reference");
 538         return u->class;
 539 }
 540
 541
 542
 543 /********************* Funktion: unicode_unlinkclass *************************
 544
 545         Entfernt den Verweis auf eine Klasse wieder von einem Symbol
 546
 547 ******************************************************************************/
 548
 549 void unicode_unlinkclass (unicode *u)
 550 {
 551         PANICIF (!u->class, "Attempt to unlink not yet linked symbol");
 552         u -> class = NULL;
 553 }
 554
 555
 556
 557 /******************* Funktion> unicode_setstringlink *********************
 558
 559         H"angt einen Verweis auf einen konstanten String an ein
 560         Unicode-Symbol
 561
 562 *************************************************************************/
 563
 564 void unicode_setstringlink (unicode *u, java_objectheader *str)
 565 {
 566         PANICIF (u->string, "Attempt to attach string to already attached symbol");
 567         u->string = str;
 568 }
 569
 570
 571 /********************* Funktion: unicode_unlinkstring *************************
 572
 573         Entfernt den Verweis auf einen String wieder von einem Symbol
 574
 575 ******************************************************************************/
 576
 577 void unicode_unlinkstring (unicode *u)
 578 {
 579         PANICIF (!u->class, "Attempt to unlink not yet linked symbol");
 580         u -> string = NULL;
 581 }
 582
 583
 584
 585 /*********************** Funktion: unicode_show ******************************
 586
 587         gibt eine Aufstellung aller Symbol im unicode-hash auf stdout aus.
 588         (nur f"ur Debug-Zwecke)
 589
 590 *****************************************************************************/
 591
 592 void unicode_show ()
 593 {
 594         unicode *u;
 595         u4 i;
 596
 597         printf ("UNICODE-HASH: %d slots for %d entries\n",
 598                  (int) unicodehashsize, (int) unicodeentries );
 599
 600         for (i=0; i<unicodehashsize; i++) {
 601                 u = unicodehash[i];
 602                 if (u) {
 603                         printf ("SLOT %d: ", (int) i);
 604                         while (u) {
 605                                 printf ("'");
 606                                 unicode_display (u);
 607                                 printf ("' ");
 608                                 if (u->string) printf ("(string)  ");
 609                                 u = u->hashlink;
 610                                 }
 611                         printf ("\n");
 612                         }
 613
 614                 }
 615 }
 616
 617
 618
 619 /******************************************************************************
 620 *********************** Diverse Support-Funktionen ****************************
 621 ******************************************************************************/
 622
 623
 624 /******************** Funktion: desc_to_type **********************************
 625
 626         Findet zu einem gegebenen Typdescriptor den entsprechenden
 627         Java-Grunddatentyp.
 628
 629 ******************************************************************************/
 630
 631 u2 desc_to_type (unicode *descriptor)
 632 {
 633         if (descriptor->length < 1) panic ("Type-Descriptor is empty string");
 634
 635         switch (descriptor->text[0]) {
 636         case 'B':
 637         case 'C':
 638         case 'I':
 639         case 'S':
 640         case 'Z':  return TYPE_INT;
 641         case 'D':  return TYPE_DOUBLE;
 642         case 'F':  return TYPE_FLOAT;
 643         case 'J':  return TYPE_LONG;
 644         case 'L':
 645         case '[':  return TYPE_ADDRESS;
 646         }
 647
 648         sprintf (logtext, "Invalid Type-Descriptor: ");
 649         unicode_sprint (logtext+strlen(logtext), descriptor);
 650         error ();
 651         return 0;
 652 }
 653
 654
 655 /********************** Funktion: desc_typesize *******************************
 656
 657         Berechnet die L"ange (in Byte) eines Datenelements gegebenen Typs,
 658         der durch den Typdescriptor gegeben ist.
 659
 660 ******************************************************************************/
 661
 662 u2 desc_typesize (unicode *descriptor)
 663 {
 664         switch (desc_to_type(descriptor)) {
 665         case TYPE_INT:     return 4;
 666         case TYPE_LONG:    return 8;
 667         case TYPE_FLOAT:   return 4;
 668         case TYPE_DOUBLE:  return 8;
 669         case TYPE_ADDRESS: return sizeof(voidptr);
 670         default:           return 0;
 671         }
 672 }
 673
 674
 675
 676
 677
 678 /******************************************************************************
 679 ********************* Der garbage-collected Heap ******************************
 680 *******************************************************************************
 681
 682         verwaltet einen Heap mit automatischer Speicherfreigabe.
 683
 684         (eine ausf"uhrliche Dokumentation findet sich in der Datei:
 685         collect.doc)
 686
 687 ******************************************************************************/
 688
 689
 690 bool collectverbose = false;  /* soll Meldung beim GC ausgegeben werden? */
 691
 692
 693 #define BLOCKSIZE 8         /* Gr"osse eines Speicherblockes */
 694 typedef u8 heapblock;       /* Datentyp mit der Gr"osse eines Speicherblocks */
 695
 696 #if U8_AVAILABLE && SUPPORT_LONG
 697 #define bitfieldtype u8
 698 #define BITFIELDBITS 64
 699 #else
 700 #define bitfieldtype u4
 701 #define BITFIELDBITS 32
 702 #endif
 703
 704 u4 heapsize;                /* Gr"osse des Heap in Blocks */
 705 u4 topofheap;               /* Bisherige Obergrenze Heaps */
 706 heapblock *heap;            /* Speicher f"ur den Heap selbst */
 707
 708 bitfieldtype *startbits;     /* Bitfeld f"ur Bereichsstartkennung */
 709 bitfieldtype *markbits;      /* Bitfeld f"ur Markierung */
 710 bitfieldtype *referencebits; /* Bitfeld f"ur Folgereferenzenkennung */
 711
 712 u4 heapfillgrade;           /* Menge der Daten im Heap */
 713 u4 collectthreashold;       /* Schwellwert f"ur n"achstes GC */
 714
 715 void **bottom_of_stack;     /* Zeiger auf Untergrenze des C-Stacks */
 716 chain *allglobalreferences; /* Liste f"ur alle globalen Zeiger */
 717
 718 typedef struct finalizernode {
 719         struct finalizernode *next;
 720         u4 objstart;
 721         methodinfo *finalizer;
 722         } finalizernode;
 723
 724 finalizernode *livefinalizees;
 725 finalizernode *deadfinalizees;
 726
 727
 728 typedef struct memarea {    /* Datenstruktur f"ur einen Freispeicherbereich */
 729         struct memarea *next;
 730         } memarea;
 731
 732 typedef struct bigmemarea {   /* Datenstruktur f"ur einen */
 733         struct bigmemarea *next;  /* Freispeicherbereich variabler L"ange */
 734         u4 size;
 735         } bigmemarea;
 736
 737 #define DIFFERENTSIZES 128         /* Anzahl der 'kleinen' Freispeicherlisten */
 738 memarea *memlist[DIFFERENTSIZES];  /* Die 'kleinen' Freispeicherlisten */
 739 bitfieldtype memlistbits[DIFFERENTSIZES/BITFIELDBITS];
 740                                    /* Bitfeld, in dem jeweils ein Bit gesetzt */
 741                                    /* ist, wenn eine Liste noch etwas enth"alt */
 742
 743 bigmemarea *bigmemlist;         /* Liste der gr"osseren Freispeicherbereiche */
 744
 745
 746
 747
 748 /**************** Hilfsfunktion: lowest **************************************
 749
 750 liefert als Ergebnis die Nummer des niederwertigsten Bits einer
 751 Zahl vom Typ bitfieldtype, das 1 ist.
 752 Wenn die ganze Zahl keine 1en enth"alt, dann ist egal, was f"ur einen
 753 Wert die Funktion l"iefert.
 754 z.B.: lowest(1) = 0,   lowest(12) = 2,   lowest(1024) = 10
 755
 756 *****************************************************************************/
 757
 758 static u1 lowesttable[256] = {
 759         255, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 760         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 761         5,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 762         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 763         6,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 764         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 765         5,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 766         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 767         7,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 768         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 769         5,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 770         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 771         6,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 772         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 773         5,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 774         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0 };
 775
 776 static int lowest(bitfieldtype i)
 777 {
 778 #if BITFIELDBITS==64
 779         u8 i1 = i<<32;
 780         if (i1) {
 781                 u8 i11 = i1<<16;
 782                 if (i11) {
 783                         u8 i111 = i11<<8;
 784                         if (i111) return lowesttable[i111>>56];
 785                         else      return 8+lowesttable[i11>>56];
 786                         }
 787                 else {
 788                         u8 i112 = i1<<8;
 789                         if (i112) return 16+lowesttable[i112>>56];
 790                         else      return 24+lowesttable[i1>>56];
 791                         }
 792                 }
 793         else {
 794                 u8 i12 = i<<16;
 795                 if (i12) {
 796                         u8 i121 = i12<<8;
 797                         if (i121) return 32+lowesttable[i121>>56];
 798                         else      return 40+lowesttable[i12>>56];
 799                         }
 800                 else {
 801                         u8 i122 = i<<8;
 802                         if (i122) return 48+lowesttable[i122>>56];
 803                         else      return 56+lowesttable[i>>56];
 804                         }
 805                 }
 806 #else
 807         u4 i1 = i<<16;
 808         if (i1) {
 809                 u4 i11 = i1<<8;
 810                 if (i11) return lowesttable[i11>>24];
 811                 else     return 8+lowesttable[i1>>24];
 812                 }
 813         else {
 814                 u4 i12 = i<<8;
 815                 if (i12) return 16+lowesttable[i12>>24];
 816                 else     return 24+lowesttable[i>>24];
 817                 }
 818 #endif
 819 }
 820
 821
 822 /******** Funktionen zum Setzen und L"oschen von Bits in Bitfeldern ***********/
 823
 824 static void setbit(bitfieldtype *bitfield, u4 bitnumber)
 825 {
 826         bitfield[bitnumber/BITFIELDBITS] |=
 827           ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS);
 828 }
 829
 830 static void clearbit(bitfieldtype *bitfield, u4 bitnumber)
 831 {
 832         bitfield[bitnumber/BITFIELDBITS] &=
 833            ~((bitfieldtype) 1) << (bitnumber%BITFIELDBITS);
 834 }
 835
 836 static bool isbitset(bitfieldtype *bitfield, u4 bitnumber)
 837 {
 838         return ( bitfield[bitnumber/BITFIELDBITS] &
 839            ( ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS) ) ) != 0;
 840 }
 841
 842 static bool isbitclear(bitfieldtype *bitfield, u4 bitnumber)
 843 {
 844         return ( bitfield[bitnumber/BITFIELDBITS] &
 845             ( ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS) ) ) == 0;
 846 }
 847
 848
 849 /***************** Funktion: clearbitfield ************************************
 850
 851         l"oscht ein ganzes Bitfeld
 852
 853 ******************************************************************************/
 854
 855 static void clearbitfield(bitfieldtype *bitfield, u4 fieldsize)
 856 {
 857         u4 i,t;
 858         t = ALIGN(fieldsize, BITFIELDBITS) / BITFIELDBITS;
 859         for (i=0; i<t; i++) bitfield[i] = 0;
 860 }
 861
 862 /************** Funktion: maskfieldwithfield **********************************
 863
 864         Verkn"upft zwei Bitfelder bitweise mit UND, das erste Bitfeld
 865         wird mit dem Ergebnis "uberschrieben
 866
 867 ******************************************************************************/
 868
 869 static void maskfieldwithfield (bitfieldtype* bitfield,
 870                                 bitfieldtype *maskfield, u4 fieldsize)
 871 {
 872         u4 i,t;
 873         t = ALIGN(fieldsize, BITFIELDBITS) / BITFIELDBITS;
 874         for (i=0; i<t; i++) bitfield[i] &= maskfield[i];
 875 }
 876
 877
 878 /************** Funktion: findnextsetbit **************************************
 879
 880         Sucht in einem Bitfeld ab einer Stelle das n"achste gesetzte Bit
 881         und liefert die Nummer dieses Bits.
 882         Wenn kein Bit mehr zwischen 'bitnumber' und 'fieldsize' gesetzt
 883         ist, dann wird fieldsize zur"uckgeliefte.
 884
 885 ******************************************************************************/
 886
 887 static u4 findnextsetbit(bitfieldtype* bitfield, u4 fieldsize, u4 bitnumber)
 888 {
 889         bitfieldtype pattern;
 890
 891         for (;;) {
 892                 if (bitnumber >= fieldsize) return fieldsize;
 893
 894                 pattern = bitfield[bitnumber/BITFIELDBITS];
 895                 pattern >>= (bitnumber%BITFIELDBITS);
 896                 if (pattern) return bitnumber + lowest(pattern);
 897
 898                 bitnumber = ((bitnumber + BITFIELDBITS) / BITFIELDBITS) * BITFIELDBITS;
 899                 }
 900 }
 901
 902
 903 /************ Funktion: findnextcombination_set_unset *************************
 904
 905         funktioniert wie findnextsetbit, allerdings sucht diese Funktion
 906         nach einer Stelle, an der gleichzeitig ein Bit im ersten
 907         Bitfeld gesetzt ist und im zweiten Bitfeld das entsprechende
 908         Bit nicht gesetzt ist.
 909
 910 ******************************************************************************/
 911
 912 static u4 findnextcombination_set_unset
 913         (bitfieldtype *bitfield1, bitfieldtype* bitfield2, u4 fieldsize, u4 bitnumber)
 914 {
 915         bitfieldtype pattern;
 916
 917         for (;;) {
 918                 if (bitnumber >= fieldsize) return fieldsize;
 919
 920                 pattern =     bitfield1[bitnumber/BITFIELDBITS]
 921                           & (~bitfield2[bitnumber/BITFIELDBITS]);
 922                 pattern >>= (bitnumber%BITFIELDBITS);
 923                 if (pattern) return bitnumber + lowest(pattern);
 924
 925                 bitnumber = ((bitnumber + BITFIELDBITS) / BITFIELDBITS) * BITFIELDBITS;
 926                 }
 927 }
 928
 929
 930
 931 /************** Funktion: memlist_init ****************************************
 932
 933         initialisiert die Freispeicherlisten (zum nachfolgenden Eintragen
 934         mit memlist_addrange).
 935
 936 ******************************************************************************/
 937
 938 static void memlist_init ()
 939 {
 940         u4 i;
 941         for (i=0; i<DIFFERENTSIZES; i++) memlist[i] = NULL;
 942         clearbitfield (memlistbits, DIFFERENTSIZES);
 943         bigmemlist = NULL;
 944 }
 945
 946
 947 /************** Funktion: memlist_addrange ************************************
 948
 949         f"ugt einen Bereich von Heap-Bl"ocken zur Freispeicherliste
 950         hinzu (in die freien Heap-Bl"ocke werden dabei verschiedene
 951         Verkettungszeiger hineingeschrieben).
 952
 953 ******************************************************************************/
 954
 955 static void memlist_addrange (u4 freestart, u4 freesize)
 956 {
 957         if (freesize>=DIFFERENTSIZES) {
 958                 bigmemarea *m = (bigmemarea*) (heap+freestart);
 959                 m -> next = bigmemlist;
 960                 m -> size = freesize;
 961                 bigmemlist = m;
 962                 }
 963         else {
 964                 if (freesize*BLOCKSIZE>=sizeof(memarea)) {
 965                         memarea *m = (memarea*) (heap+freestart);
 966                         m -> next = memlist[freesize];
 967                         memlist[freesize] = m;
 968                         setbit (memlistbits, freesize);
 969                         }
 970                 }
 971 }
 972
 973
 974 /************** Funktion: memlist_getsuitable *********************************
 975
 976         sucht in der Freispeicherliste einen Speicherbereich, der m"oglichst
 977         genau die gew"unschte L"ange hat.
 978         Der Bereich wird dabei auf jeden Fall aus der Liste ausgetragen.
 979         (Wenn der Bereich zu lang sein sollte, dann kann der Aufrufer den
 980         Rest wieder mit 'memlist_addrange' in die Liste einh"angen)
 981
 982         Return (in Referenzparametern):
 983                 *freestart: Anfang des freien Speichers
 984                 *freelength: L"ange dieses Speicherbereiches
 985
 986         Wenn kein passender Speicherblock mehr gefunden werden kann, dann
 987         wird in '*freelength' 0 hineingeschrieben.
 988
 989 ******************************************************************************/
 990
 991 static void memlist_getsuitable (u4 *freestart, u4 *freelength, u4 length)
 992 {
 993         bigmemarea *m;
 994         bigmemarea *prevm = NULL;
 995
 996         if (length<DIFFERENTSIZES) {
 997                 u4 firstfreelength;
 998
 999                 if (memlist[length]) {
1000                         firstfreelength = length;
1001                         }
1002                 else {
1003                         firstfreelength = findnextsetbit
1004                                 (memlistbits, DIFFERENTSIZES, length+3);
1005                                 /* wenn kein passender Block da ist, dann gleich nach */
1006                                 /* einem etwas gr"osseren suchen, damit keine kleinen */
1007                                 /* St"uckchen "ubrigbleiben */
1008                         }
1009
1010                 if (firstfreelength<DIFFERENTSIZES) {
1011                         memarea *m = memlist[firstfreelength];
1012                         memlist[firstfreelength] = m->next;
1013                         if (!m->next) clearbit (memlistbits, firstfreelength);
1014                         *freestart = ((heapblock*) m) - heap;
1015                         *freelength = firstfreelength;
1016                         return;
1017                         }
1018                 }
1019
1020         m = bigmemlist;
1021         while (m) {
1022                 if (m->size >= length) {
1023                         if (prevm) prevm->next = m->next;
1024                                 else   bigmemlist = m->next;
1025
1026                         *freestart = ((heapblock*) m) - heap;
1027                         *freelength = m->size;
1028                         return ;
1029                         }
1030
1031                 prevm = m;
1032                 m = m->next;
1033                 }
1034
1035         *freelength=0;
1036 }
1037
1038
1039
1040
1041
1042 /******************* Funktion: mark *******************************************
1043
1044         Markiert ein m"oglicherweise g"ultiges Objekt.
1045         Sollte sich herausstellen, dass der Zeiger gar nicht auf ein Objekt
1046         am Heap zeigt, dann wird eben gar nichts markiert.
1047
1048 ******************************************************************************/
1049
1050 static void markreferences (void **rstart, void **rend);
1051
1052 static void mark (heapblock *obj)
1053 {
1054         u4 blocknum,objectend;
1055
1056         if ((long) obj & (BLOCKSIZE-1)) return;
1057
1058         if (obj<heap) return;
1059         if (obj>=(heap+topofheap) ) return;
1060
1061         blocknum = obj-heap;
1062         if ( isbitclear(startbits, blocknum) ) return;
1063         if ( isbitset(markbits, blocknum) ) return;
1064
1065         setbit (markbits, blocknum);
1066
1067         if ( isbitclear(referencebits, blocknum) ) return;
1068
1069         objectend = findnextsetbit (startbits, topofheap, blocknum+1);
1070         markreferences ((void**)obj, (void**) (heap+objectend) );
1071 }
1072
1073
1074 /******************** Funktion: markreferences ********************************
1075
1076         Geht einen Speicherbereich durch, und markiert alle Objekte, auf
1077         die von diesem Bereich aus irgendeine Referenz existiert.
1078
1079 ******************************************************************************/
1080
1081 static void markreferences (void **rstart, void **rend)
1082 {
1083         void **ptr;
1084
1085         for (ptr=rstart; ptr<rend; ptr++) mark (*ptr);
1086 }
1087
1088
1089 /******************* Funktion: markstack **************************************
1090
1091         Marks all objects that are referenced by the (C-)stacks of
1092         all live threads.
1093
1094         (The stack-bottom is to be specified in the call to heap_init).
1095
1096 ******************************************************************************/
1097
1098 static void markstack ()                   /* schani */
1099 {
1100         void *dummy;
1101         void **top_of_stack = &dummy;
1102
1103 #ifdef USE_THREADS
1104         thread *aThread;
1105
1106         for (aThread = liveThreads; aThread != 0; aThread = CONTEXT(aThread).nextlive) {
1107                 mark((heapblock*)aThread);
1108                 if (aThread == currentThread) {
1109                         if (top_of_stack > (void**)CONTEXT(aThread).stackEnd)
1110                                 markreferences ((void**)CONTEXT(aThread).stackEnd, top_of_stack);
1111                         else
1112                                 markreferences (top_of_stack, (void**)CONTEXT(aThread).stackEnd);
1113                         }
1114                 else {
1115                         if (CONTEXT(aThread).usedStackTop > CONTEXT(aThread).stackEnd)
1116                                 markreferences ((void**)CONTEXT(aThread).stackEnd,
1117                                                 (void**)CONTEXT(aThread).usedStackTop + 16);
1118                         else
1119                                 markreferences ((void**)CONTEXT(aThread).usedStackTop - 16,
1120                                                 (void**)CONTEXT(aThread).stackEnd);
1121                         }
1122                 }
1123
1124         markreferences((void**)&threadQhead[0], (void**)&threadQhead[MAX_THREAD_PRIO]);
1125 #else
1126         if (top_of_stack > bottom_of_stack)
1127                 markreferences(bottom_of_stack, top_of_stack);
1128         else
1129                 markreferences(top_of_stack, bottom_of_stack);
1130 #endif
1131 }
1132
1133
1134
1135 /**************** Funktion: searchlivefinalizees *****************************
1136
1137         geht die Liste aller Objekte durch, die noch finalisiert werden m"ussen
1138         (livefinalizees), und tr"agt alle nicht mehr markierten in die
1139         Liste deadfinalizess ein (allerdings werden sie vorher noch als
1140         erreicht markiert, damit sie nicht jetzt gleich gel"oscht werden).
1141
1142 *****************************************************************************/
1143
1144 static void searchlivefinalizees ()
1145 {
1146         finalizernode *fn = livefinalizees;
1147         finalizernode *lastlive = NULL;
1148
1149         while (fn) {
1150
1151                 /* alle zu finalisierenden Objekte, die nicht mehr markiert sind: */
1152                 if (isbitclear (markbits, fn->objstart)) {
1153                         finalizernode *nextfn = fn->next;
1154
1155                         mark (heap + fn->objstart);
1156
1157                         if (lastlive) lastlive -> next = nextfn;
1158                                        else livefinalizees = nextfn;
1159
1160                         fn -> next = deadfinalizees;
1161                         deadfinalizees = fn;
1162
1163                         fn = nextfn;
1164                         }
1165                 else {
1166                         lastlive = fn;
1167                         fn = fn->next;
1168                         }
1169                 }
1170 }
1171
1172
1173
1174 /********************** Funktion: finalizedead *******************************
1175
1176         ruft die 'finalize'-Methode aller Objekte in der 'deadfinalizees'-
1177         Liste auf.
1178         Achtung: Es kann hier eventuell zu neuerlichen Speicheranforderungen
1179         (mit potentiell notwendigem GC) kommen, deshalb m"ussen manche
1180         globalen Variablen in lokale Variblen kopiert werden
1181         (Reentrant-F"ahigkeit!!!)
1182
1183 ******************************************************************************/
1184
1185 static void finalizedead()
1186 {
1187         finalizernode *fn = deadfinalizees;
1188         deadfinalizees = NULL;
1189
1190         while (fn) {
1191                 finalizernode *nextfn = fn->next;
1192
1193                 asm_calljavamethod (fn->finalizer, heap+fn->objstart, NULL,NULL,NULL);
1194                 FREE (fn, finalizernode);
1195
1196                 fn = nextfn;
1197                 }
1198
1199 }
1200
1201
1202
1203 /****************** Funktion: heap_docollect **********************************
1204
1205         F"uhrt eine vollst"andige Garbage Collection durch
1206
1207 ******************************************************************************/
1208
1209 static void heap_docollect ()
1210 {
1211         u4 freestart,freeend;
1212         void **p;
1213         bitfieldtype *dummy;
1214         u4 heapfreemem;
1215         u4 oldfillgrade;
1216
1217
1218         if (runverbose) {
1219                 fprintf(stderr, "doing garbage collection\n");
1220                 }
1221                 /* alle Markierungsbits l"oschen */
1222         clearbitfield (markbits, topofheap);
1223
1224                 /* Alle vom Stack referenzierten Objekte markieren */
1225         asm_dumpregistersandcall (markstack);
1226
1227                 /* Alle von globalen Variablen erreichbaren Objekte markieren */
1228         p = chain_first (allglobalreferences);
1229         while (p) {
1230                 mark (*p);
1231                 p = chain_next (allglobalreferences);
1232                 }
1233
1234                 /* alle Objekte durchsehen, die eine finalizer-Methode haben */
1235         searchlivefinalizees();
1236
1237                 /* alle Reference-Bits l"oschen, deren Objekte nicht */
1238                 /* mehr erreichbar sind */
1239         maskfieldwithfield (referencebits, markbits, topofheap);
1240
1241
1242                 /* Freispeicherliste initialisieren */
1243         memlist_init ();
1244
1245
1246                 /* Heap schrittweise durchgehen, und alle freien Bl"ocke merken */
1247
1248         heapfreemem = 0;
1249         freeend=0;
1250         for (;;) {
1251                         /* Anfang des n"achsten freien Bereiches suchen */
1252                 freestart = findnextcombination_set_unset
1253                         (startbits, markbits, topofheap, freeend);
1254
1255                         /* Wenn es keinen freien Bereich mehr gibt -> fertig */
1256                 if (freestart>=topofheap) goto freememfinished;
1257
1258                         /* Anfang des freien Bereiches markieren */
1259                 setbit (markbits, freestart);
1260
1261                         /* Ende des freien Bereiches suchen */
1262                 freeend = findnextsetbit (markbits, topofheap, freestart+1);
1263
1264                         /* Freien Bereich in Freispeicherliste einh"angen */
1265                 memlist_addrange (freestart, freeend-freestart);
1266
1267                         /* Menge des freien Speichers mitnotieren */
1268                 heapfreemem += (freeend-freestart);
1269                 }
1270
1271         freememfinished:
1272
1273                 /* Die Rollen von markbits und startbits vertauschen */
1274         dummy = markbits;
1275         markbits = startbits;
1276         startbits = dummy;
1277
1278
1279                 /* Threashold-Wert f"ur n"achstes Collect */
1280         oldfillgrade = heapfillgrade;
1281         heapfillgrade = topofheap - heapfreemem;
1282         collectthreashold = heapfillgrade*3;   /* eine nette Heuristik */
1283
1284                 /* Eventuell eine Meldung ausgeben */
1285         if (collectverbose) {
1286                 sprintf (logtext, "Garbage Collection:  previous/now = %d / %d ",
1287                   (int) (oldfillgrade * BLOCKSIZE),
1288                   (int) (heapfillgrade * BLOCKSIZE) );
1289                 dolog ();
1290                 }
1291
1292
1293
1294                 /* alle gerade unerreichbar gewordenen Objekte mit
1295                    finalize-Methoden jetzt finalisieren.
1296                    Achtung: Diese Funktion kann zu neuerlichem GC f"uhren!! */
1297         finalizedead ();
1298
1299 }
1300
1301 /************************* Function: gc_init **********************************
1302
1303         Initializes the garbage collection thread mechanism.
1304
1305 ******************************************************************************/
1306
1307 #ifdef USE_THREADS
1308 iMux gcStartMutex;
1309 iMux gcThreadMutex;
1310 iCv gcConditionStart;
1311 iCv gcConditionDone;
1312
1313 void
1314 gc_init (void)
1315 {
1316     gcStartMutex.holder = 0;
1317     gcStartMutex.count = 0;
1318     gcStartMutex.muxWaiters = 0;
1319
1320     gcThreadMutex.holder = 0;
1321     gcThreadMutex.count = 0;
1322     gcThreadMutex.muxWaiters = 0;
1323
1324     gcConditionStart.cvWaiters = 0;
1325     gcConditionStart.mux = 0;
1326
1327     gcConditionDone.cvWaiters = 0;
1328     gcConditionDone.mux = 0;
1329 }
1330 #else
1331 void
1332 gc_init (void)
1333 {
1334 }
1335 #endif
1336
1337 /************************* Function: gc_thread ********************************
1338
1339         In an endless loop waits for a condition to be posted, then
1340         garbage collects the heap.
1341
1342 ******************************************************************************/
1343
1344 #ifdef USE_THREADS
1345 void
1346 gc_thread (void)
1347 {
1348     intsRestore();           /* all threads start with interrupts disabled */
1349
1350         assert(blockInts == 0);
1351
1352     lock_mutex(&gcThreadMutex);
1353
1354     for (;;)
1355     {
1356                 wait_cond(&gcThreadMutex, &gcConditionStart, 0);
1357
1358                 intsDisable();
1359                 heap_docollect();
1360                 intsRestore();
1361
1362                 signal_cond(&gcConditionDone);
1363     }
1364 }
1365 #endif
1366
1367 void
1368 gc_call (void)
1369 {
1370 #ifdef USE_THREADS
1371     lock_mutex(&gcThreadMutex);
1372
1373     signal_cond(&gcConditionStart);
1374     wait_cond(&gcThreadMutex, &gcConditionDone, 0);
1375
1376     unlock_mutex(&gcThreadMutex);
1377 #else
1378     heap_docollect();
1379 #endif
1380 }
1381
1382
1383 /************************* Funktion: heap_init ********************************
1384
1385         Initialisiert den Garbage Collector.
1386         Parameter:
1387                 heapbytesize:      Maximale Gr"osse des Heap (in Bytes)
1388                 heapbytestartsize: Gr"osse des Heaps, bei dem zum ersten mal eine
1389                                    GC durchgef"uhrt werden soll.
1390                 stackbottom:       Ein Zeiger auf die Untergrenze des Stacks, im dem
1391                                Referenzen auf Objekte stehen k"onnen.
1392
1393 ******************************************************************************/
1394
1395 void heap_init (u4 heapbytesize, u4 heapbytestartsize, void **stackbottom)
1396 {
1397
1398 #ifdef TRACECALLARGS
1399
1400         heapsize = ALIGN (heapbytesize, getpagesize());
1401         heapsize = heapsize/BLOCKSIZE;
1402         heap = (void*) mmap ((void*) 0x10000000, (size_t) (heapsize * BLOCKSIZE),
1403                PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, (off_t) 0);
1404         if (heap != (void *) 0x10000000) {
1405                 perror("mmap");
1406                 printf("address = %p\n", heap);
1407                 panic("mmap failed\n");
1408                 }
1409
1410 #else
1411
1412         heapsize = ALIGN (heapbytesize, 1024);
1413         heapsize = heapsize/BLOCKSIZE;
1414         heap = MNEW (heapblock, heapsize);
1415
1416 #endif
1417
1418         topofheap = 0;
1419         startbits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
1420         markbits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
1421         referencebits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
1422         clearbitfield (startbits, heapsize);
1423         clearbitfield (markbits, heapsize);
1424         clearbitfield (referencebits, heapsize);
1425
1426         heapfillgrade = 0;
1427         collectthreashold = heapbytestartsize/BLOCKSIZE;
1428         allglobalreferences = chain_new ();
1429         bottom_of_stack = stackbottom;
1430
1431         livefinalizees = NULL;
1432         deadfinalizees = NULL;
1433 }
1434
1435
1436 /****************** Funktion: heap_close **************************************
1437
1438         Gibt allen ben"otigten Speicher frei
1439
1440 ******************************************************************************/
1441
1442 void heap_close ()
1443 {
1444 #ifndef TRACECALLARGS
1445         MFREE (heap, heapblock, heapsize); */
1446 #endif
1447         MFREE (startbits, bitfieldtype, heapsize/BITFIELDBITS);
1448         MFREE (markbits, bitfieldtype, heapsize/BITFIELDBITS);
1449         MFREE (referencebits, bitfieldtype, heapsize/BITFIELDBITS);
1450         chain_free (allglobalreferences);
1451
1452         while (livefinalizees) {
1453                 finalizernode *n = livefinalizees->next;
1454                 FREE (livefinalizees, finalizernode);
1455                 livefinalizees = n;
1456                 }
1457 }
1458
1459
1460 /***************** Funktion: heap_addreference ********************************
1461
1462         Teilt dem GC eine Speicherstelle mit, an der eine globale Referenz
1463         auf Objekte gespeichert sein kann.
1464
1465 ******************************************************************************/
1466
1467 void heap_addreference (void **reflocation)
1468 {
1469         intsDisable();                     /* schani */
1470
1471         chain_addlast (allglobalreferences, reflocation);
1472
1473         intsRestore();                    /* schani */
1474 }
1475
1476
1477
1478 /***************** Funktion: heap_allocate ************************************
1479
1480         Fordert einen Speicher vom Heap an, der eine gew"unschte Gr"osse
1481         (in Byte angegeben) haben muss.
1482         Wenn kein Speicher mehr vorhanden ist (auch nicht nach einem
1483         Garbage Collection-Durchlauf), dann wird NULL zur"uckgegeben.
1484         Zus"atzlich wird durch den Parameter 'references' angegeben, ob
1485         in das angelegte Objekt Referenzen auf andere Objekte eingetragen
1486         werden k"onnten.
1487         (Wichtig wegen Beschleunigung des Mark&Sweep-Durchlauf)
1488         Im Zweifelsfalle immer references=true verwenden.
1489
1490 ******************************************************************************/
1491
1492 void *heap_allocate (u4 bytelength, bool references, methodinfo *finalizer)
1493 {
1494         u4 freestart,freelength;
1495         u4 length = ALIGN(bytelength, BLOCKSIZE) / BLOCKSIZE;
1496
1497         intsDisable();                        /* schani */
1498
1499         memlist_getsuitable (&freestart, &freelength, length);
1500
1501 onemoretry:
1502         if (!freelength) {
1503                 if (    (topofheap+length > collectthreashold)
1504                      || (topofheap+length > heapsize) ) {
1505
1506                         intsRestore();
1507                         gc_call();
1508                         intsDisable();
1509
1510                         memlist_getsuitable (&freestart, &freelength, length);
1511                         if (freelength) goto onemoretry;
1512                         }
1513
1514                 if (topofheap+length > heapsize) {
1515                         sprintf (logtext, "Heap-Allocation failed for %d bytes",
1516                             (int) bytelength);
1517                         dolog();
1518                         intsRestore();            /* schani */
1519                         return NULL;
1520                         }
1521
1522                 freestart = topofheap;
1523                 freelength = length;
1524                 setbit (startbits, topofheap);
1525                 topofheap += length;
1526                 }
1527         else {
1528                 if (freelength>length) {
1529                         setbit (startbits, freestart+length);
1530                         memlist_addrange (freestart+length, freelength-length);
1531                         }
1532                 }
1533
1534         if (references) setbit (referencebits, freestart);
1535
1536         heapfillgrade += length;
1537
1538         if (finalizer) {
1539                 finalizernode *n = NEW(finalizernode);
1540                 n -> next = livefinalizees;
1541                 n -> objstart = freestart;
1542                 n -> finalizer = finalizer;
1543                 livefinalizees = n;
1544                 }
1545
1546         intsRestore();                   /* schani */
1547
1548         if (runverbose) {
1549                 sprintf (logtext, "new returns: %lx", (long) (heap + freestart));
1550                 dolog ();
1551                 }
1552
1553         return (void*) (heap + freestart);
1554 }
1555
1556
1557
1558