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