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         void **top_of_stack = &dummy;
 459
 460 #ifdef USE_THREADS
 461         thread *aThread;
 462
 463         for (aThread = liveThreads; aThread != 0; aThread = CONTEXT(aThread).nextlive) {
 464                 mark((heapblock*)aThread);
 465                 if (aThread == currentThread) {
 466                         if (top_of_stack > (void**)CONTEXT(aThread).stackEnd)
 467                                 markreferences ((void**)CONTEXT(aThread).stackEnd, top_of_stack);
 468                         else
 469                                 markreferences (top_of_stack, (void**)CONTEXT(aThread).stackEnd);
 470                         }
 471                 else {
 472                         if (CONTEXT(aThread).usedStackTop > CONTEXT(aThread).stackEnd)
 473                                 markreferences ((void**)CONTEXT(aThread).stackEnd,
 474                                                 (void**)CONTEXT(aThread).usedStackTop + 16);
 475                         else
 476                                 markreferences ((void**)CONTEXT(aThread).usedStackTop - 16,
 477                                                 (void**)CONTEXT(aThread).stackEnd);
 478                         }
 479                 }
 480
 481         markreferences((void**)&threadQhead[0], (void**)&threadQhead[MAX_THREAD_PRIO]);
 482 #else
 483         if (top_of_stack > bottom_of_stack)
 484                 markreferences(bottom_of_stack, top_of_stack);
 485         else
 486                 markreferences(top_of_stack, bottom_of_stack);
 487 #endif
 488 }
 489
 490
 491
 492 /**************** Funktion: searchlivefinalizees *****************************
 493
 494         geht die Liste aller Objekte durch, die noch finalisiert werden m"ussen
 495         (livefinalizees), und tr"agt alle nicht mehr markierten in die
 496         Liste deadfinalizess ein (allerdings werden sie vorher noch als
 497         erreicht markiert, damit sie nicht jetzt gleich gel"oscht werden).
 498
 499 *****************************************************************************/
 500
 501 static void searchlivefinalizees ()
 502 {
 503         finalizernode *fn = livefinalizees;
 504         finalizernode *lastlive = NULL;
 505
 506         while (fn) {
 507
 508                 /* alle zu finalisierenden Objekte, die nicht mehr markiert sind: */
 509                 if (isbitclear (markbits, fn->objstart)) {
 510                         finalizernode *nextfn = fn->next;
 511
 512                         mark (heap + fn->objstart);
 513
 514                         if (lastlive) lastlive -> next = nextfn;
 515                                        else livefinalizees = nextfn;
 516
 517                         fn -> next = deadfinalizees;
 518                         deadfinalizees = fn;
 519
 520                         fn = nextfn;
 521                         }
 522                 else {
 523                         lastlive = fn;
 524                         fn = fn->next;
 525                         }
 526                 }
 527 }
 528
 529
 530
 531 /********************** Funktion: finalizedead *******************************
 532
 533         ruft die 'finalize'-Methode aller Objekte in der 'deadfinalizees'-
 534         Liste auf.
 535         Achtung: Es kann hier eventuell zu neuerlichen Speicheranforderungen
 536         (mit potentiell notwendigem GC) kommen, deshalb m"ussen manche
 537         globalen Variablen in lokale Variblen kopiert werden
 538         (Reentrant-F"ahigkeit!!!)
 539
 540 ******************************************************************************/
 541
 542 static void finalizedead()
 543 {
 544         finalizernode *fn = deadfinalizees;
 545         deadfinalizees = NULL;
 546
 547         while (fn) {
 548                 finalizernode *nextfn = fn->next;
 549
 550                 asm_calljavamethod (fn->finalizer, heap+fn->objstart, NULL,NULL,NULL);
 551                 FREE (fn, finalizernode);
 552
 553                 fn = nextfn;
 554                 }
 555
 556 }
 557
 558
 559
 560 /****************** Funktion: heap_docollect **********************************
 561
 562         F"uhrt eine vollst"andige Garbage Collection durch
 563
 564 ******************************************************************************/
 565
 566 static void heap_docollect ()
 567 {
 568         u4 freestart,freeend;
 569         void **p;
 570         bitfieldtype *dummy;
 571         u4 heapfreemem;
 572         u4 oldfillgrade;
 573
 574
 575         if (runverbose) {
 576                 fprintf(stderr, "doing garbage collection\n");
 577                 }
 578                 /* alle Markierungsbits l"oschen */
 579         clearbitfield (markbits, topofheap);
 580
 581                 /* Alle vom Stack referenzierten Objekte markieren */
 582         asm_dumpregistersandcall (markstack);
 583
 584                 /* Alle von globalen Variablen erreichbaren Objekte markieren */
 585         p = chain_first (allglobalreferences);
 586         while (p) {
 587                 mark (*p);
 588                 p = chain_next (allglobalreferences);
 589                 }
 590
 591                 /* alle Objekte durchsehen, die eine finalizer-Methode haben */
 592         searchlivefinalizees();
 593
 594                 /* alle Reference-Bits l"oschen, deren Objekte nicht */
 595                 /* mehr erreichbar sind */
 596         maskfieldwithfield (referencebits, markbits, topofheap);
 597
 598
 599                 /* Freispeicherliste initialisieren */
 600         memlist_init ();
 601
 602
 603                 /* Heap schrittweise durchgehen, und alle freien Bl"ocke merken */
 604
 605         heapfreemem = 0;
 606         freeend=0;
 607         for (;;) {
 608                         /* Anfang des n"achsten freien Bereiches suchen */
 609                 freestart = findnextcombination_set_unset
 610                         (startbits, markbits, topofheap, freeend);
 611
 612                         /* Wenn es keinen freien Bereich mehr gibt -> fertig */
 613                 if (freestart>=topofheap) goto freememfinished;
 614
 615                         /* Anfang des freien Bereiches markieren */
 616                 setbit (markbits, freestart);
 617
 618                         /* Ende des freien Bereiches suchen */
 619                 freeend = findnextsetbit (markbits, topofheap, freestart+1);
 620
 621                         /* Freien Bereich in Freispeicherliste einh"angen */
 622                 memlist_addrange (freestart, freeend-freestart);
 623
 624                         /* Menge des freien Speichers mitnotieren */
 625                 heapfreemem += (freeend-freestart);
 626                 }
 627
 628         freememfinished:
 629
 630                 /* Die Rollen von markbits und startbits vertauschen */
 631         dummy = markbits;
 632         markbits = startbits;
 633         startbits = dummy;
 634
 635
 636                 /* Threashold-Wert f"ur n"achstes Collect */
 637         oldfillgrade = heapfillgrade;
 638         heapfillgrade = topofheap - heapfreemem;
 639         collectthreashold = heapfillgrade*3;   /* eine nette Heuristik */
 640
 641                 /* Eventuell eine Meldung ausgeben */
 642         if (collectverbose) {
 643                 sprintf (logtext, "Garbage Collection:  previous/now = %d / %d ",
 644                   (int) (oldfillgrade * BLOCKSIZE),
 645                   (int) (heapfillgrade * BLOCKSIZE) );
 646                 dolog ();
 647                 }
 648
 649
 650
 651                 /* alle gerade unerreichbar gewordenen Objekte mit
 652                    finalize-Methoden jetzt finalisieren.
 653                    Achtung: Diese Funktion kann zu neuerlichem GC f"uhren!! */
 654         finalizedead ();
 655
 656 }
 657
 658 /************************* Function: gc_init **********************************
 659
 660         Initializes the garbage collection thread mechanism.
 661
 662 ******************************************************************************/
 663
 664 #ifdef USE_THREADS
 665 iMux gcStartMutex;
 666 iMux gcThreadMutex;
 667 iCv gcConditionStart;
 668 iCv gcConditionDone;
 669
 670 void
 671 gc_init (void)
 672 {
 673     gcStartMutex.holder = 0;
 674     gcStartMutex.count = 0;
 675     gcStartMutex.muxWaiters = 0;
 676
 677     gcThreadMutex.holder = 0;
 678     gcThreadMutex.count = 0;
 679     gcThreadMutex.muxWaiters = 0;
 680
 681     gcConditionStart.cvWaiters = 0;
 682     gcConditionStart.mux = 0;
 683
 684     gcConditionDone.cvWaiters = 0;
 685     gcConditionDone.mux = 0;
 686 }
 687 #else
 688 void
 689 gc_init (void)
 690 {
 691 }
 692 #endif
 693
 694 /************************* Function: gc_thread ********************************
 695
 696         In an endless loop waits for a condition to be posted, then
 697         garbage collects the heap.
 698
 699 ******************************************************************************/
 700
 701 #ifdef USE_THREADS
 702 void
 703 gc_thread (void)
 704 {
 705     intsRestore();           /* all threads start with interrupts disabled */
 706
 707         assert(blockInts == 0);
 708
 709     lock_mutex(&gcThreadMutex);
 710
 711     for (;;)
 712     {
 713                 wait_cond(&gcThreadMutex, &gcConditionStart, 0);
 714
 715                 intsDisable();
 716                 heap_docollect();
 717                 intsRestore();
 718
 719                 signal_cond(&gcConditionDone);
 720     }
 721 }
 722 #endif
 723
 724 void
 725 gc_call (void)
 726 {
 727 #ifdef USE_THREADS
 728     lock_mutex(&gcThreadMutex);
 729
 730     signal_cond(&gcConditionStart);
 731     wait_cond(&gcThreadMutex, &gcConditionDone, 0);
 732
 733     unlock_mutex(&gcThreadMutex);
 734 #else
 735     heap_docollect();
 736 #endif
 737 }
 738
 739
 740 /************************* Funktion: heap_init ********************************
 741
 742         Initialisiert den Garbage Collector.
 743         Parameter:
 744                 heapbytesize:      Maximale Gr"osse des Heap (in Bytes)
 745                 heapbytestartsize: Gr"osse des Heaps, bei dem zum ersten mal eine
 746                                    GC durchgef"uhrt werden soll.
 747                 stackbottom:       Ein Zeiger auf die Untergrenze des Stacks, im dem
 748                                Referenzen auf Objekte stehen k"onnen.
 749
 750 ******************************************************************************/
 751
 752 void heap_init (u4 heapbytesize, u4 heapbytestartsize, void **stackbottom)
 753 {
 754
 755 #ifdef TRACECALLARGS
 756
 757         heapsize = ALIGN (heapbytesize, getpagesize());
 758         heapsize = heapsize/BLOCKSIZE;
 759         heap = (void*) mmap ((void*) 0x10000000, (size_t) (heapsize * BLOCKSIZE),
 760                PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, (off_t) 0);
 761         if (heap != (void *) 0x10000000) {
 762                 perror("mmap");
 763                 printf("address = %p\n", heap);
 764                 panic("mmap failed\n");
 765                 }
 766
 767 #else
 768
 769         heapsize = ALIGN (heapbytesize, 1024);
 770         heapsize = heapsize/BLOCKSIZE;
 771         heap = MNEW (heapblock, heapsize);
 772
 773 #endif
 774
 775         topofheap = 0;
 776         startbits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
 777         markbits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
 778         referencebits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
 779         clearbitfield (startbits, heapsize);
 780         clearbitfield (markbits, heapsize);
 781         clearbitfield (referencebits, heapsize);
 782
 783         heapfillgrade = 0;
 784         collectthreashold = heapbytestartsize/BLOCKSIZE;
 785         allglobalreferences = chain_new ();
 786         bottom_of_stack = stackbottom;
 787
 788         livefinalizees = NULL;
 789         deadfinalizees = NULL;
 790 }
 791
 792
 793 /****************** Funktion: heap_close **************************************
 794
 795         Gibt allen ben"otigten Speicher frei
 796
 797 ******************************************************************************/
 798
 799 void heap_close ()
 800 {
 801 #ifndef TRACECALLARGS
 802         MFREE (heap, heapblock, heapsize); */
 803 #endif
 804         MFREE (startbits, bitfieldtype, heapsize/BITFIELDBITS);
 805         MFREE (markbits, bitfieldtype, heapsize/BITFIELDBITS);
 806         MFREE (referencebits, bitfieldtype, heapsize/BITFIELDBITS);
 807         chain_free (allglobalreferences);
 808
 809         while (livefinalizees) {
 810                 finalizernode *n = livefinalizees->next;
 811                 FREE (livefinalizees, finalizernode);
 812                 livefinalizees = n;
 813                 }
 814 }
 815
 816
 817 /***************** Funktion: heap_addreference ********************************
 818
 819         Teilt dem GC eine Speicherstelle mit, an der eine globale Referenz
 820         auf Objekte gespeichert sein kann.
 821
 822 ******************************************************************************/
 823
 824 void heap_addreference (void **reflocation)
 825 {
 826         intsDisable();                     /* schani */
 827
 828         chain_addlast (allglobalreferences, reflocation);
 829
 830         intsRestore();                    /* schani */
 831 }
 832
 833
 834
 835 /***************** Funktion: heap_allocate ************************************
 836
 837         Fordert einen Speicher vom Heap an, der eine gew"unschte Gr"osse
 838         (in Byte angegeben) haben muss.
 839         Wenn kein Speicher mehr vorhanden ist (auch nicht nach einem
 840         Garbage Collection-Durchlauf), dann wird NULL zur"uckgegeben.
 841         Zus"atzlich wird durch den Parameter 'references' angegeben, ob
 842         in das angelegte Objekt Referenzen auf andere Objekte eingetragen
 843         werden k"onnten.
 844         (Wichtig wegen Beschleunigung des Mark&Sweep-Durchlauf)
 845         Im Zweifelsfalle immer references=true verwenden.
 846
 847 ******************************************************************************/
 848
 849 void *heap_allocate (u4 bytelength, bool references, methodinfo *finalizer)
 850 {
 851         u4 freestart,freelength;
 852         u4 length = ALIGN(bytelength, BLOCKSIZE) / BLOCKSIZE;
 853
 854         intsDisable();                        /* schani */
 855
 856         memlist_getsuitable (&freestart, &freelength, length);
 857
 858         if (!freelength) {
 859                 if ( (topofheap+length > collectthreashold) || (topofheap+length > heapsize) ) {
 860                         intsRestore();
 861                         gc_call();
 862                         intsDisable();
 863
 864                         memlist_getsuitable (&freestart, &freelength, length);
 865                         if (freelength)
 866                                 goto have_block; /* phil */
 867                 }
 868
 869                 if (topofheap+length > heapsize) {
 870                         sprintf (logtext, "Heap-Allocation failed for %d bytes",
 871                                          (int) bytelength);
 872                         dolog();
 873                         intsRestore();            /* schani */
 874                         return NULL;
 875                 }
 876
 877                 freestart = topofheap;
 878                 freelength = length;
 879                 setbit (startbits, topofheap);
 880                 topofheap += length;
 881         }
 882
 883  have_block:
 884         if (freelength>length) {
 885                 setbit (startbits, freestart+length);
 886                 memlist_addrange (freestart+length, freelength-length);
 887         }
 888
 889         if (references)
 890                 setbit (referencebits, freestart);
 891
 892         setbit (startbits, freestart);  /* phil */
 893
 894         heapfillgrade += length;
 895
 896         if (finalizer) {
 897                 finalizernode *n = NEW(finalizernode);
 898                 n -> next = livefinalizees;
 899                 n -> objstart = freestart;
 900                 n -> finalizer = finalizer;
 901                 livefinalizees = n;
 902         }
 903
 904         intsRestore();                   /* schani */
 905
 906         if (runverbose) {
 907                 sprintf (logtext, "new returns: %lx", (long) (heap + freestart));
 908                 dolog ();
 909         }
 910
 911         return (void*) (heap + freestart);
 912 }