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