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