mm/heap.old.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
  35 /******************************************************************************
  36 ********************* Der garbage-collected Heap ******************************
  37 *******************************************************************************
  38
  39         verwaltet einen Heap mit automatischer Speicherfreigabe.
  40
  41         (eine ausf"uhrliche Dokumentation findet sich in der Datei:
  42         collect.doc)
  43
  44 ******************************************************************************/
  45
  46
  47 bool collectverbose = false;  /* soll Meldung beim GC ausgegeben werden? */
  48
  49
  50 #define BLOCKSIZE 8         /* Gr"osse eines Speicherblockes */
  51 typedef u8 heapblock;       /* Datentyp mit der Gr"osse eines Speicherblocks */
  52
  53 #if U8_AVAILABLE && SUPPORT_LONG
  54 #define bitfieldtype u8
  55 #define BITFIELDBITS 64
  56 #else
  57 #define bitfieldtype u4
  58 #define BITFIELDBITS 32
  59 #endif
  60
  61 u4 heapsize;                /* Gr"osse des Heap in Blocks */
  62 u4 topofheap;               /* Bisherige Obergrenze Heaps */
  63 heapblock *heap;            /* Speicher f"ur den Heap selbst */
  64
  65 bitfieldtype *startbits;     /* Bitfeld f"ur Bereichsstartkennung */
  66 bitfieldtype *markbits;      /* Bitfeld f"ur Markierung */
  67 bitfieldtype *referencebits; /* Bitfeld f"ur Folgereferenzenkennung */
  68
  69 u4 heapfillgrade;           /* Menge der Daten im Heap */
  70 u4 collectthreashold;       /* Schwellwert f"ur n"achstes GC */
  71
  72 void **bottom_of_stack;     /* Zeiger auf Untergrenze des C-Stacks */
  73 chain *allglobalreferences; /* Liste f"ur alle globalen Zeiger */
  74
  75 typedef struct finalizernode {
  76         struct finalizernode *next;
  77         u4 objstart;
  78         methodinfo *finalizer;
  79         } finalizernode;
  80
  81 finalizernode *livefinalizees;
  82 finalizernode *deadfinalizees;
  83
  84
  85 typedef struct memarea {    /* Datenstruktur f"ur einen Freispeicherbereich */
  86         struct memarea *next;
  87         } memarea;
  88
  89 typedef struct bigmemarea {   /* Datenstruktur f"ur einen */
  90         struct bigmemarea *next;  /* Freispeicherbereich variabler L"ange */
  91         u4 size;
  92         } bigmemarea;
  93
  94 #define DIFFERENTSIZES 128         /* Anzahl der 'kleinen' Freispeicherlisten */
  95 memarea *memlist[DIFFERENTSIZES];  /* Die 'kleinen' Freispeicherlisten */
  96 bitfieldtype memlistbits[DIFFERENTSIZES/BITFIELDBITS];
  97                                    /* Bitfeld, in dem jeweils ein Bit gesetzt */
  98                                    /* ist, wenn eine Liste noch etwas enth"alt */
  99
 100 bigmemarea *bigmemlist;         /* Liste der gr"osseren Freispeicherbereiche */
 101
 102
 103
 104
 105 /**************** Hilfsfunktion: lowest **************************************
 106
 107 liefert als Ergebnis die Nummer des niederwertigsten Bits einer
 108 Zahl vom Typ bitfieldtype, das 1 ist.
 109 Wenn die ganze Zahl keine 1en enth"alt, dann ist egal, was f"ur einen
 110 Wert die Funktion l"iefert.
 111 z.B.: lowest(1) = 0,   lowest(12) = 2,   lowest(1024) = 10
 112
 113 *****************************************************************************/
 114
 115 static u1 lowesttable[256] = {
 116         255, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 117         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 118         5,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 119         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 120         6,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 121         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 122         5,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 123         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 124         7,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 125         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 126         5,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 127         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 128         6,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 129         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 130         5,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
 131         4,   0,1,0,2,0,1,0,3,0,1,0,2,0,1,0 };
 132
 133 static int lowest(bitfieldtype i)
 134 {
 135 #if BITFIELDBITS==64
 136         u8 i1 = i<<32;
 137         if (i1) {
 138                 u8 i11 = i1<<16;
 139                 if (i11) {
 140                         u8 i111 = i11<<8;
 141                         if (i111) return lowesttable[i111>>56];
 142                         else      return 8+lowesttable[i11>>56];
 143                         }
 144                 else {
 145                         u8 i112 = i1<<8;
 146                         if (i112) return 16+lowesttable[i112>>56];
 147                         else      return 24+lowesttable[i1>>56];
 148                         }
 149                 }
 150         else {
 151                 u8 i12 = i<<16;
 152                 if (i12) {
 153                         u8 i121 = i12<<8;
 154                         if (i121) return 32+lowesttable[i121>>56];
 155                         else      return 40+lowesttable[i12>>56];
 156                         }
 157                 else {
 158                         u8 i122 = i<<8;
 159                         if (i122) return 48+lowesttable[i122>>56];
 160                         else      return 56+lowesttable[i>>56];
 161                         }
 162                 }
 163 #else
 164         u4 i1 = i<<16;
 165         if (i1) {
 166                 u4 i11 = i1<<8;
 167                 if (i11) return lowesttable[i11>>24];
 168                 else     return 8+lowesttable[i1>>24];
 169                 }
 170         else {
 171                 u4 i12 = i<<8;
 172                 if (i12) return 16+lowesttable[i12>>24];
 173                 else     return 24+lowesttable[i>>24];
 174                 }
 175 #endif
 176 }
 177
 178
 179 /******** Funktionen zum Setzen und L"oschen von Bits in Bitfeldern ***********/
 180
 181 static void setbit(bitfieldtype *bitfield, u4 bitnumber)
 182 {
 183         bitfield[bitnumber/BITFIELDBITS] |=
 184           ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS);
 185 }
 186
 187 static void clearbit(bitfieldtype *bitfield, u4 bitnumber)
 188 {
 189         bitfield[bitnumber/BITFIELDBITS] &=
 190            ~((bitfieldtype) 1) << (bitnumber%BITFIELDBITS);
 191 }
 192
 193 static bool isbitset(bitfieldtype *bitfield, u4 bitnumber)
 194 {
 195         return ( bitfield[bitnumber/BITFIELDBITS] &
 196            ( ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS) ) ) != 0;
 197 }
 198
 199 static bool isbitclear(bitfieldtype *bitfield, u4 bitnumber)
 200 {
 201         return ( bitfield[bitnumber/BITFIELDBITS] &
 202             ( ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS) ) ) == 0;
 203 }
 204
 205
 206 /***************** Funktion: clearbitfield ************************************
 207
 208         l"oscht ein ganzes Bitfeld
 209
 210 ******************************************************************************/
 211
 212 static void clearbitfield(bitfieldtype *bitfield, u4 fieldsize)
 213 {
 214         u4 i,t;
 215         t = ALIGN(fieldsize, BITFIELDBITS) / BITFIELDBITS;
 216         for (i=0; i<t; i++) bitfield[i] = 0;
 217 }
 218
 219 /************** Funktion: maskfieldwithfield **********************************
 220
 221         Verkn"upft zwei Bitfelder bitweise mit UND, das erste Bitfeld
 222         wird mit dem Ergebnis "uberschrieben
 223
 224 ******************************************************************************/
 225
 226 static void maskfieldwithfield (bitfieldtype* bitfield,
 227                                 bitfieldtype *maskfield, u4 fieldsize)
 228 {
 229         u4 i,t;
 230         t = ALIGN(fieldsize, BITFIELDBITS) / BITFIELDBITS;
 231         for (i=0; i<t; i++) bitfield[i] &= maskfield[i];
 232 }
 233
 234
 235 /************** Funktion: findnextsetbit **************************************
 236
 237         Sucht in einem Bitfeld ab einer Stelle das n"achste gesetzte Bit
 238         und liefert die Nummer dieses Bits.
 239         Wenn kein Bit mehr zwischen 'bitnumber' und 'fieldsize' gesetzt
 240         ist, dann wird fieldsize zur"uckgeliefte.
 241
 242 ******************************************************************************/
 243
 244 static u4 findnextsetbit(bitfieldtype* bitfield, u4 fieldsize, u4 bitnumber)
 245 {
 246         bitfieldtype pattern;
 247
 248         for (;;) {
 249                 if (bitnumber >= fieldsize) return fieldsize;
 250
 251                 pattern = bitfield[bitnumber/BITFIELDBITS];
 252                 pattern >>= (bitnumber%BITFIELDBITS);
 253                 if (pattern) return bitnumber + lowest(pattern);
 254
 255                 bitnumber = ((bitnumber + BITFIELDBITS) / BITFIELDBITS) * BITFIELDBITS;
 256                 }
 257 }
 258
 259
 260 /************ Funktion: findnextcombination_set_unset *************************
 261
 262         funktioniert wie findnextsetbit, allerdings sucht diese Funktion
 263         nach einer Stelle, an der gleichzeitig ein Bit im ersten
 264         Bitfeld gesetzt ist und im zweiten Bitfeld das entsprechende
 265         Bit nicht gesetzt ist.
 266
 267 ******************************************************************************/
 268
 269 static u4 findnextcombination_set_unset
 270         (bitfieldtype *bitfield1, bitfieldtype* bitfield2, u4 fieldsize, u4 bitnumber)
 271 {
 272         bitfieldtype pattern;
 273
 274         for (;;) {
 275                 if (bitnumber >= fieldsize) return fieldsize;
 276
 277                 pattern =     bitfield1[bitnumber/BITFIELDBITS]
 278                           & (~bitfield2[bitnumber/BITFIELDBITS]);
 279                 pattern >>= (bitnumber%BITFIELDBITS);
 280                 if (pattern) return bitnumber + lowest(pattern);
 281
 282                 bitnumber = ((bitnumber + BITFIELDBITS) / BITFIELDBITS) * BITFIELDBITS;
 283                 }
 284 }
 285
 286
 287
 288 /************** Funktion: memlist_init ****************************************
 289
 290         initialisiert die Freispeicherlisten (zum nachfolgenden Eintragen
 291         mit memlist_addrange).
 292
 293 ******************************************************************************/
 294
 295 static void memlist_init ()
 296 {
 297         u4 i;
 298         for (i=0; i<DIFFERENTSIZES; i++) memlist[i] = NULL;
 299         clearbitfield (memlistbits, DIFFERENTSIZES);
 300         bigmemlist = NULL;
 301 }
 302
 303
 304 /************** Funktion: memlist_addrange ************************************
 305
 306         f"ugt einen Bereich von Heap-Bl"ocken zur Freispeicherliste
 307         hinzu (in die freien Heap-Bl"ocke werden dabei verschiedene
 308         Verkettungszeiger hineingeschrieben).
 309
 310 ******************************************************************************/
 311
 312 static void memlist_addrange (u4 freestart, u4 freesize)
 313 {
 314         if (freesize>=DIFFERENTSIZES) {
 315                 bigmemarea *m = (bigmemarea*) (heap+freestart);
 316                 m -> next = bigmemlist;
 317                 m -> size = freesize;
 318                 bigmemlist = m;
 319                 }
 320         else {
 321                 if (freesize*BLOCKSIZE>=sizeof(memarea)) {
 322                         memarea *m = (memarea*) (heap+freestart);
 323                         m -> next = memlist[freesize];
 324                         memlist[freesize] = m;
 325                         setbit (memlistbits, freesize);
 326                         }
 327                 }
 328 }
 329
 330
 331 /************** Funktion: memlist_getsuitable *********************************
 332
 333         sucht in der Freispeicherliste einen Speicherbereich, der m"oglichst
 334         genau die gew"unschte L"ange hat.
 335         Der Bereich wird dabei auf jeden Fall aus der Liste ausgetragen.
 336         (Wenn der Bereich zu lang sein sollte, dann kann der Aufrufer den
 337         Rest wieder mit 'memlist_addrange' in die Liste einh"angen)
 338
 339         Return (in Referenzparametern):
 340                 *freestart: Anfang des freien Speichers
 341                 *freelength: L"ange dieses Speicherbereiches
 342
 343         Wenn kein passender Speicherblock mehr gefunden werden kann, dann
 344         wird in '*freelength' 0 hineingeschrieben.
 345
 346 ******************************************************************************/
 347
 348 static void memlist_getsuitable (u4 *freestart, u4 *freelength, u4 length)
 349 {
 350         bigmemarea *m;
 351         bigmemarea *prevm = NULL;
 352
 353         if (length<DIFFERENTSIZES) {
 354                 u4 firstfreelength;
 355
 356                 if (memlist[length]) {
 357                         firstfreelength = length;
 358                         }
 359                 else {
 360                         firstfreelength = findnextsetbit
 361                                 (memlistbits, DIFFERENTSIZES, length+3);
 362                                 /* wenn kein passender Block da ist, dann gleich nach */
 363                                 /* einem etwas gr"osseren suchen, damit keine kleinen */
 364                                 /* St"uckchen "ubrigbleiben */
 365                         }
 366
 367                 if (firstfreelength<DIFFERENTSIZES) {
 368                         memarea *m = memlist[firstfreelength];
 369                         memlist[firstfreelength] = m->next;
 370                         if (!m->next) clearbit (memlistbits, firstfreelength);
 371                         *freestart = ((heapblock*) m) - heap;
 372                         *freelength = firstfreelength;
 373                         return;
 374                         }
 375                 }
 376
 377         m = bigmemlist;
 378         while (m) {
 379                 if (m->size >= length) {
 380                         if (prevm) prevm->next = m->next;
 381                                 else   bigmemlist = m->next;
 382
 383                         *freestart = ((heapblock*) m) - heap;
 384                         *freelength = m->size;
 385                         return ;
 386                         }
 387
 388                 prevm = m;
 389                 m = m->next;
 390                 }
 391
 392         *freelength=0;
 393 }
 394
 395
 396
 397
 398
 399 /******************* Funktion: mark *******************************************
 400
 401         Markiert ein m"oglicherweise g"ultiges Objekt.
 402         Sollte sich herausstellen, dass der Zeiger gar nicht auf ein Objekt
 403         am Heap zeigt, dann wird eben gar nichts markiert.
 404
 405 ******************************************************************************/
 406
 407 static void markreferences (void **rstart, void **rend);
 408
 409 static void mark (heapblock *obj)
 410 {
 411         u4 blocknum,objectend;
 412
 413         if ((long) obj & (BLOCKSIZE-1)) return;
 414
 415         if (obj<heap) return;
 416         if (obj>=(heap+topofheap) ) return;
 417
 418         blocknum = obj-heap;
 419         if ( isbitclear(startbits, blocknum) ) return;
 420         if ( isbitset(markbits, blocknum) ) return;
 421
 422         setbit (markbits, blocknum);
 423
 424         if ( isbitclear(referencebits, blocknum) ) return;
 425
 426         objectend = findnextsetbit (startbits, topofheap, blocknum+1);
 427         markreferences ((void**)obj, (void**) (heap+objectend) );
 428 }
 429
 430
 431 /******************** Funktion: markreferences ********************************
 432
 433         Geht einen Speicherbereich durch, und markiert alle Objekte, auf
 434         die von diesem Bereich aus irgendeine Referenz existiert.
 435
 436 ******************************************************************************/
 437
 438 static void markreferences (void **rstart, void **rend)
 439 {
 440         void **ptr;
 441
 442         for (ptr=rstart; ptr<rend; ptr++) mark (*ptr);
 443 }
 444
 445
 446 /******************* Funktion: markstack **************************************
 447
 448         Marks all objects that are referenced by the (C-)stacks of
 449         all live threads.
 450
 451         (The stack-bottom is to be specified in the call to heap_init).
 452
 453 ******************************************************************************/
 454
 455 static void markstack ()                   /* schani */
 456 {
 457         void *dummy;
 458
 459 #ifdef USE_THREADS
 460     thread *aThread;
 461
 462         if (currentThread == NULL) {
 463                 void **top_of_stack = &dummy;
 464
 465                 if (top_of_stack > bottom_of_stack)
 466                         markreferences(bottom_of_stack, top_of_stack);
 467                 else
 468                         markreferences(top_of_stack, bottom_of_stack);
 469         }
 470         else {
 471                 for (aThread = liveThreads; aThread != 0;
 472                          aThread = CONTEXT(aThread).nextlive) {
 473                         mark((heapblock*)aThread);
 474                         if (aThread == currentThread) {
 475                                 void **top_of_stack = &dummy;
 476
 477                                 if (top_of_stack > (void**)CONTEXT(aThread).stackEnd)
 478                                         markreferences((void**)CONTEXT(aThread).stackEnd, top_of_stack);
 479                                 else
 480                                         markreferences(top_of_stack, (void**)CONTEXT(aThread).stackEnd);
 481                         }
 482                         else {
 483                                 if (CONTEXT(aThread).usedStackTop > CONTEXT(aThread).stackEnd)
 484                                         markreferences((void**)CONTEXT(aThread).stackEnd,
 485                                                                    (void**)CONTEXT(aThread).usedStackTop);
 486                                 else
 487                                         markreferences((void**)CONTEXT(aThread).usedStackTop,
 488                                                                    (void**)CONTEXT(aThread).stackEnd);
 489                         }
 490             }
 491
 492                 markreferences((void**)&threadQhead[0],
 493                                            (void**)&threadQhead[MAX_THREAD_PRIO]);
 494         }
 495 #else
 496     void **top_of_stack = &dummy;
 497
 498     if (top_of_stack > bottom_of_stack)
 499         markreferences(bottom_of_stack, top_of_stack);
 500     else
 501         markreferences(top_of_stack, bottom_of_stack);
 502 #endif
 503 }
 504
 505
 506 /**************** Funktion: searchlivefinalizees *****************************
 507
 508         geht die Liste aller Objekte durch, die noch finalisiert werden m"ussen
 509         (livefinalizees), und tr"agt alle nicht mehr markierten in die
 510         Liste deadfinalizess ein (allerdings werden sie vorher noch als
 511         erreicht markiert, damit sie nicht jetzt gleich gel"oscht werden).
 512
 513 *****************************************************************************/
 514
 515 static void searchlivefinalizees ()
 516 {
 517         finalizernode *fn = livefinalizees;
 518         finalizernode *lastlive = NULL;
 519
 520         while (fn) {
 521
 522                 /* alle zu finalisierenden Objekte, die nicht mehr markiert sind: */
 523                 if (isbitclear (markbits, fn->objstart)) {
 524                         finalizernode *nextfn = fn->next;
 525
 526                         mark (heap + fn->objstart);
 527
 528                         if (lastlive) lastlive -> next = nextfn;
 529                                        else livefinalizees = nextfn;
 530
 531                         fn -> next = deadfinalizees;
 532                         deadfinalizees = fn;
 533
 534                         fn = nextfn;
 535                         }
 536                 else {
 537                         lastlive = fn;
 538                         fn = fn->next;
 539                         }
 540                 }
 541 }
 542
 543
 544
 545 /********************** Funktion: finalizedead *******************************
 546
 547         ruft die 'finalize'-Methode aller Objekte in der 'deadfinalizees'-
 548         Liste auf.
 549         Achtung: Es kann hier eventuell zu neuerlichen Speicheranforderungen
 550         (mit potentiell notwendigem GC) kommen, deshalb m"ussen manche
 551         globalen Variablen in lokale Variblen kopiert werden
 552         (Reentrant-F"ahigkeit!!!)
 553
 554 ******************************************************************************/
 555
 556 static void finalizedead()
 557 {
 558         finalizernode *fn = deadfinalizees;
 559         deadfinalizees = NULL;
 560
 561         while (fn) {
 562                 finalizernode *nextfn = fn->next;
 563
 564                 asm_calljavamethod (fn->finalizer, heap+fn->objstart, NULL,NULL,NULL);
 565                 FREE (fn, finalizernode);
 566
 567                 fn = nextfn;
 568                 }
 569
 570 }
 571
 572
 573
 574 /****************** Funktion: heap_docollect **********************************
 575
 576         F"uhrt eine vollst"andige Garbage Collection durch
 577
 578 ******************************************************************************/
 579
 580 static void heap_docollect ()
 581 {
 582         u4 freestart,freeend;
 583         void **p;
 584         bitfieldtype *dummy;
 585         u4 heapfreemem;
 586         u4 oldfillgrade;
 587
 588
 589         if (runverbose) {
 590                 fprintf(stderr, "doing garbage collection\n");
 591                 }
 592                 /* alle Markierungsbits l"oschen */
 593         clearbitfield (markbits, topofheap);
 594
 595                 /* Alle vom Stack referenzierten Objekte markieren */
 596         asm_dumpregistersandcall (markstack);
 597
 598                 /* Alle von globalen Variablen erreichbaren Objekte markieren */
 599         p = chain_first (allglobalreferences);
 600         while (p) {
 601                 mark (*p);
 602                 p = chain_next (allglobalreferences);
 603                 }
 604
 605                 /* alle Objekte durchsehen, die eine finalizer-Methode haben */
 606         searchlivefinalizees();
 607
 608                 /* alle Reference-Bits l"oschen, deren Objekte nicht */
 609                 /* mehr erreichbar sind */
 610         maskfieldwithfield (referencebits, markbits, topofheap);
 611
 612
 613                 /* Freispeicherliste initialisieren */
 614         memlist_init ();
 615
 616
 617                 /* Heap schrittweise durchgehen, und alle freien Bl"ocke merken */
 618
 619         heapfreemem = 0;
 620         freeend=0;
 621         for (;;) {
 622                         /* Anfang des n"achsten freien Bereiches suchen */
 623                 freestart = findnextcombination_set_unset
 624                         (startbits, markbits, topofheap, freeend);
 625
 626                         /* Wenn es keinen freien Bereich mehr gibt -> fertig */
 627                 if (freestart>=topofheap) goto freememfinished;
 628
 629                         /* Anfang des freien Bereiches markieren */
 630                 setbit (markbits, freestart);
 631
 632                         /* Ende des freien Bereiches suchen */
 633                 freeend = findnextsetbit (markbits, topofheap, freestart+1);
 634
 635                         /* Freien Bereich in Freispeicherliste einh"angen */
 636                 memlist_addrange (freestart, freeend-freestart);
 637
 638                         /* Menge des freien Speichers mitnotieren */
 639                 heapfreemem += (freeend-freestart);
 640                 }
 641
 642         freememfinished:
 643
 644                 /* Die Rollen von markbits und startbits vertauschen */
 645         dummy = markbits;
 646         markbits = startbits;
 647         startbits = dummy;
 648
 649
 650                 /* Threashold-Wert f"ur n"achstes Collect */
 651         oldfillgrade = heapfillgrade;
 652         heapfillgrade = topofheap - heapfreemem;
 653         collectthreashold = heapfillgrade*3;   /* eine nette Heuristik */
 654
 655                 /* Eventuell eine Meldung ausgeben */
 656         if (collectverbose) {
 657                 sprintf (logtext, "Garbage Collection:  previous/now = %d / %d ",
 658                   (int) (oldfillgrade * BLOCKSIZE),
 659                   (int) (heapfillgrade * BLOCKSIZE) );
 660                 dolog ();
 661                 }
 662
 663
 664
 665                 /* alle gerade unerreichbar gewordenen Objekte mit
 666                    finalize-Methoden jetzt finalisieren.
 667                    Achtung: Diese Funktion kann zu neuerlichem GC f"uhren!! */
 668         finalizedead ();
 669
 670 }
 671
 672 /************************* Function: gc_init **********************************
 673
 674   Initializes anything that must be initialized to call the gc on the right
 675   stack.
 676
 677 ******************************************************************************/
 678
 679 void
 680 gc_init (void)
 681 {
 682 }
 683
 684 /************************** Function: gc_call ********************************
 685
 686   Calls the garbage collector. The garbage collector should always be called
 687   using this function since it ensures that enough stack space is available.
 688
 689 ******************************************************************************/
 690
 691 void
 692 gc_call (void)
 693 {
 694 #ifdef USE_THREADS
 695         assert(blockInts == 0);
 696
 697         intsDisable();
 698         if (currentThread == NULL || currentThread == mainThread)
 699                 heap_docollect();
 700         else
 701                 asm_switchstackandcall(CONTEXT(mainThread).usedStackTop, heap_docollect);
 702         intsRestore();
 703 #else
 704         heap_docollect();
 705 #endif
 706 }
 707
 708
 709 /************************* Funktion: heap_init ********************************
 710
 711         Initialisiert den Garbage Collector.
 712         Parameter:
 713                 heapbytesize:      Maximale Gr"osse des Heap (in Bytes)
 714                 heapbytestartsize: Gr"osse des Heaps, bei dem zum ersten mal eine
 715                                    GC durchgef"uhrt werden soll.
 716                 stackbottom:       Ein Zeiger auf die Untergrenze des Stacks, im dem
 717                                Referenzen auf Objekte stehen k"onnen.
 718
 719 ******************************************************************************/
 720
 721 void heap_init (u4 heapbytesize, u4 heapbytestartsize, void **stackbottom)
 722 {
 723
 724 #ifdef TRACECALLARGS
 725
 726         heapsize = ALIGN (heapbytesize, getpagesize());
 727         heapsize = heapsize/BLOCKSIZE;
 728         heap = (void*) mmap ((void*) 0x10000000, (size_t) (heapsize * BLOCKSIZE),
 729                PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, (off_t) 0);
 730         if (heap != (void *) 0x10000000) {
 731                 perror("mmap");
 732                 printf("address = %p\n", heap);
 733                 panic("mmap failed\n");
 734                 }
 735
 736 #else
 737
 738         heapsize = ALIGN (heapbytesize, 1024);
 739         heapsize = heapsize/BLOCKSIZE;
 740         heap = MNEW (heapblock, heapsize);
 741
 742 #endif
 743
 744         topofheap = 0;
 745         startbits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
 746         markbits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
 747         referencebits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
 748         clearbitfield (startbits, heapsize);
 749         clearbitfield (markbits, heapsize);
 750         clearbitfield (referencebits, heapsize);
 751
 752         heapfillgrade = 0;
 753         collectthreashold = heapbytestartsize/BLOCKSIZE;
 754         allglobalreferences = chain_new ();
 755         bottom_of_stack = stackbottom;
 756
 757         livefinalizees = NULL;
 758         deadfinalizees = NULL;
 759 }
 760
 761
 762 /****************** Funktion: heap_close **************************************
 763
 764         Gibt allen ben"otigten Speicher frei
 765
 766 ******************************************************************************/
 767
 768 void heap_close ()
 769 {
 770 #ifndef TRACECALLARGS
 771         MFREE (heap, heapblock, heapsize); */
 772 #endif
 773         MFREE (startbits, bitfieldtype, heapsize/BITFIELDBITS);
 774         MFREE (markbits, bitfieldtype, heapsize/BITFIELDBITS);
 775         MFREE (referencebits, bitfieldtype, heapsize/BITFIELDBITS);
 776         chain_free (allglobalreferences);
 777
 778         while (livefinalizees) {
 779                 finalizernode *n = livefinalizees->next;
 780                 asm_calljavamethod (livefinalizees->finalizer,
 781                                                         heap+livefinalizees->objstart,
 782                                                         NULL,NULL,NULL);
 783                 FREE (livefinalizees, finalizernode);
 784                 livefinalizees = n;
 785         }
 786 }
 787
 788
 789 /***************** Funktion: heap_addreference ********************************
 790
 791         Teilt dem GC eine Speicherstelle mit, an der eine globale Referenz
 792         auf Objekte gespeichert sein kann.
 793
 794 ******************************************************************************/
 795
 796 void heap_addreference (void **reflocation)
 797 {
 798         intsDisable();                     /* schani */
 799
 800         chain_addlast (allglobalreferences, reflocation);
 801
 802         intsRestore();                    /* schani */
 803 }
 804
 805
 806
 807 /***************** Funktion: heap_allocate ************************************
 808
 809         Fordert einen Speicher vom Heap an, der eine gew"unschte Gr"osse
 810         (in Byte angegeben) haben muss.
 811         Wenn kein Speicher mehr vorhanden ist (auch nicht nach einem
 812         Garbage Collection-Durchlauf), dann wird NULL zur"uckgegeben.
 813         Zus"atzlich wird durch den Parameter 'references' angegeben, ob
 814         in das angelegte Objekt Referenzen auf andere Objekte eingetragen
 815         werden k"onnten.
 816         (Wichtig wegen Beschleunigung des Mark&Sweep-Durchlauf)
 817         Im Zweifelsfalle immer references=true verwenden.
 818
 819 ******************************************************************************/
 820
 821 void *heap_allocate (u4 bytelength, bool references, methodinfo *finalizer)
 822 {
 823         u4 freestart,freelength;
 824         u4 length = ALIGN(bytelength, BLOCKSIZE) / BLOCKSIZE;
 825
 826         intsDisable();                        /* schani */
 827
 828         memlist_getsuitable (&freestart, &freelength, length);
 829
 830 onemoretry:
 831         if (!freelength) {
 832                 if ((topofheap+length > collectthreashold) ||
 833                     (topofheap+length > heapsize)) {
 834
 835                         intsRestore();
 836                         gc_call();
 837                         intsDisable();
 838
 839                         memlist_getsuitable (&freestart, &freelength, length);
 840                         if (freelength) goto onemoretry;
 841                         }
 842
 843                 if (topofheap+length > heapsize) {
 844                         sprintf (logtext, "Heap-Allocation failed for %d bytes",
 845                             (int) bytelength);
 846                         dolog();
 847                         intsRestore();            /* schani */
 848                         return NULL;
 849                         }
 850
 851                 freestart = topofheap;
 852                 freelength = length;
 853                 setbit (startbits, topofheap);
 854                 topofheap += length;
 855                 }
 856         else {
 857                 if (freelength>length) {
 858                         setbit (startbits, freestart+length);
 859                         memlist_addrange (freestart+length, freelength-length);
 860                         }
 861                 }
 862
 863         if (references) setbit (referencebits, freestart);
 864
 865         heapfillgrade += length;
 866
 867         if (finalizer) {
 868                 finalizernode *n = NEW(finalizernode);
 869                 n -> next = livefinalizees;
 870                 n -> objstart = freestart;
 871                 n -> finalizer = finalizer;
 872                 livefinalizees = n;
 873                 }
 874
 875         intsRestore();                   /* schani */
 876
 877         if (runverbose) {
 878                 sprintf (logtext, "new returns: %lx", (long) (heap + freestart));
 879                 dolog ();
 880                 }
 881
 882         return (void*) (heap + freestart);
 883 }