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