1 /* -*- mode: c; tab-width: 4; c-basic-offset: 4 -*- */
2 /****************************** tables.c ***************************************
4 Copyright (c) 1997 A. Krall, R. Grafl, M. Gschwind, M. Probst
6 See file COPYRIGHT for information on usage and disclaimer of warranties
8 Enth"alt Supportfunktionen f"ur:
9 - Lesen von JavaClass-Files
12 - zus"atzliche Support-Funktionen
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
18 Last Change: 1998/03/24
20 *******************************************************************************/
30 #include "threads/thread.h" /* schani */
31 #include "threads/locks.h"
34 bool runverbose = false;
36 int count_unicode_len = 0;
39 /******************************************************************************
40 ************************* Der Dateien-Sauger **********************************
41 *******************************************************************************
43 dient zum Behandeln von Java-ClassFiles ("offnen, schlie"sen,
44 einlesen von 8-, 16-, 32-, 64-bit Integers und 32-, 64- bit Floats)
46 ******************************************************************************/
48 static FILE *classfile = NULL; /* File-handle der gerade gelesenen Datei */
49 static char *classpath = ""; /* Suchpfad f"ur die ClassFiles */
53 /************************** Funktion: suck_init ******************************
55 Wird zu Programmstart einmal aufgerufen und setzt den Suchpfad f"ur
58 ******************************************************************************/
60 void suck_init (char *cpath)
67 /************************** Funktion: suck_start ******************************
69 "Offnet die Datei f"ur die Klasse des gegebenen Namens zum Lesen.
70 Dabei werden alle im Suchpfad angegebenen Verzeichnisse durchsucht,
71 bis eine entsprechende Datei ( <classname>.class) gefunden wird.
73 ******************************************************************************/
75 bool suck_start (unicode *classname)
77 #define MAXFILENAME 1000 /* Maximale Langes des Dateinamens plus Pfad */
79 char filename[MAXFILENAME+10]; /* Platz fuer '.class' */
88 while ( *pathpos == ':' ) pathpos++;
91 while ( (*pathpos) && (*pathpos!=':') ) {
92 PANICIF (filenamelen >= MAXFILENAME, "Filename too long") ;
94 filename[filenamelen++] = *(pathpos++);
97 filename[filenamelen++] = '/';
99 for (i=0; i < classname -> length; i++) {
100 PANICIF (filenamelen >= MAXFILENAME, "Filename too long");
102 c = classname -> text [i];
103 if (c=='/') c = '/'; /* Slashes im Namen passen zu UNIX */
105 if ( c<=' ' || c>'z') {
110 filename[filenamelen++] = c;
113 strcpy (filename+filenamelen, ".class");
115 classfile = fopen(filename, "r");
123 sprintf (logtext,"Can not open class file '%s'", filename);
129 /************************** Funktion: suck_stop *******************************
131 Schlie"st die offene Datei wieder.
133 ******************************************************************************/
140 while ( fread (&dummy, 1,1, classfile) > 0) rest++;
142 sprintf (logtext,"There are %d access bytes at end of classfile",
153 /************************** Lesefunktionen ***********************************
155 Lesen von der Datei in verschieden grossen Paketen
156 (8,16,32,64-bit Integer oder Float)
158 *****************************************************************************/
160 void suck_nbytes (u1 *buffer, u4 len)
162 if ( fread (buffer, 1, len, classfile) != len) panic ("Unexpected EOF");
166 void skip_nbytes (u4 len)
169 for (i=0; i<len; i++) suck_u1 ();
176 if ( fread (&b, 1,1, classfile) != 1) panic ("Unexpected EOF");
183 if ( fread (&b, 1,1, classfile) != 1) panic ("Unexpected EOF");
191 if ( fread (b, 1,2, classfile) != 2) panic ("Unexpected EOF");
192 return (b[0]<<8) + b[1];
205 if ( fread (b, 1,4, classfile) != 4) panic ("Unexpected EOF");
206 v = ( ((u4)b[0]) <<24) + ( ((u4)b[1])<<16) + ( ((u4)b[2])<<8) + ((u4)b[3]);
222 return (hi<<32) + lo;
244 for (i=0; i<4; i++) buffer[3-i] = suck_u1 ();
245 memcpy ( (u1*) (&f), buffer, 4);
247 suck_nbytes ( (u1*) (&f), 4 );
250 PANICIF (sizeof(float) != 4, "Incompatible float-format");
256 double suck_double ()
263 for (i=0; i<8; i++) buffer[7-i] = suck_u1 ();
264 memcpy ( (u1*) (&d), buffer, 8);
266 suck_nbytes ( (u1*) (&d), 8 );
269 PANICIF (sizeof(double) != 8, "Incompatible double-format" );
277 /******************************************************************************
278 ******************** Der Unicode-Symbol-Verwalter *****************************
279 *******************************************************************************
281 legt eine Hashtabelle f"ur unicode-Symbole an und verwaltet
282 das Eintragen neuer Symbole
284 ******************************************************************************/
288 #define UNICODESTART 2187 /* Startgr"osse: moeglichst gross und prim */
290 static u4 unicodeentries; /* Anzahl der Eintr"age in der Tabelle */
291 static u4 unicodehashsize; /* Gr"osse der Tabelle */
292 static unicode ** unicodehash; /* Zeiger auf die Tabelle selbst */
295 /*********************** Funktion: unicode_init ******************************
297 Initialisiert die unicode-Symboltabelle (muss zu Systemstart einmal
300 *****************************************************************************/
307 count_unicode_len += sizeof(unicode*) * unicodehashsize;
311 unicodehashsize = UNICODESTART;
312 unicodehash = MNEW (unicode*, unicodehashsize);
313 for (i=0; i<unicodehashsize; i++) unicodehash[i] = NULL;
317 /*********************** Funktion: unicode_close *****************************
319 Gibt allen Speicher der Symboltabellen frei.
320 Parameter: Ein Zeiger auf eine Funktion, die dazu n"otig ist,
321 Stringkonstanten (die mit 'unicode_setstringlink'
322 Unicode-Symbole gebunden wurden) wieder freizugeben
324 *****************************************************************************/
326 void unicode_close (stringdeleter del)
331 for (i=0; i<unicodehashsize; i++) {
334 unicode *nextu = u->hashlink;
336 if (u->string) del (u->string);
338 MFREE (u->text, u2, u->length);
343 MFREE (unicodehash, unicode*, unicodehashsize);
347 /********************* Funktion: unicode_display ******************************
349 Gibt ein unicode-Symbol auf stdout aus (zu Debugzwecken)
351 ******************************************************************************/
353 void unicode_display (unicode *u)
356 for (i=0; i < u->length; i++) {
358 if (c>=32 && c<=127) printf ("%c",c);
365 /********************* Funktion: unicode_sprint ******************************
367 Schreibt ein unicode-Symbol in einen C-String
369 ******************************************************************************/
371 void unicode_sprint (char *buffer, unicode *u)
374 for (i=0; i < u->length; i++) buffer[i] = u->text[i];
379 /********************* Funktion: unicode_fprint ******************************
381 Schreibt ein unicode-Symbol auf eine Datei aus
383 ******************************************************************************/
385 void unicode_fprint (FILE *file, unicode *u)
388 for (i=0; i < u->length; i++) putc (u->text[i], file);
392 /****************** interne Funktion: u_hashkey ******************************/
394 static u4 u_hashkey (u2 *text, u2 length)
399 for (i=0; i<length; i++) {
400 k ^= ( ((u4) (text[i])) << sh );
408 /*************** interne Funktion: u_reorganizehash **************************/
410 static void u_reorganizehash ()
415 u4 newhashsize = unicodehashsize*2;
416 unicode **newhash = MNEW (unicode*, newhashsize);
419 count_unicode_len += sizeof(unicode*) * unicodehashsize;
422 for (i=0; i<newhashsize; i++) newhash[i] = NULL;
424 for (i=0; i<unicodehashsize; i++) {
427 unicode *nextu = u -> hashlink;
428 u4 slot = (u->key) % newhashsize;
430 u->hashlink = newhash[slot];
437 MFREE (unicodehash, unicode*, unicodehashsize);
438 unicodehash = newhash;
439 unicodehashsize = newhashsize;
443 /****************** Funktion: unicode_new_u2 **********************************
445 Legt ein neues unicode-Symbol an. Der Text des Symbols wird dieser
446 Funktion als u2-Array "ubergeben
448 ******************************************************************************/
450 unicode *unicode_new_u2 (u2 *text, u2 length)
452 u4 key = u_hashkey (text, length);
453 u4 slot = key % unicodehashsize;
454 unicode *u = unicodehash[slot];
459 if (u->length == length) {
460 for (i=0; i<length; i++) {
461 if (text[i] != u->text[i]) goto nomatch;
471 count_unicode_len += sizeof(unicode) + 2 * length;
477 u->text = MNEW (u2, length);
480 u->hashlink = unicodehash[slot];
481 unicodehash[slot] = u;
482 for (i=0; i<length; i++) u->text[i] = text[i];
486 if ( unicodeentries > (unicodehashsize/2)) u_reorganizehash();
492 /********************* Funktion: unicode_new_char *****************************
494 Legt ein neues unicode-Symbol an. Der Text des Symbols wird dieser
495 Funktion als C-String ( = char* ) "ubergeben
497 ******************************************************************************/
499 unicode *unicode_new_char (char *text)
501 #define MAXNEWCHAR 500
502 u2 buffer[MAXNEWCHAR];
506 while ( (c = *text) != '\0' ) {
507 if (length>=MAXNEWCHAR) panic ("Text too long in unicode_new_char");
508 buffer[length++] = c;
511 return unicode_new_u2 (buffer, length);
515 /********************** Funktion: unicode_setclasslink ************************
517 H"angt einen Verweis auf eine Klasse an ein unicode-Symbol an.
519 ******************************************************************************/
521 void unicode_setclasslink (unicode *u, classinfo *class)
523 PANICIF (u->class, "Attempt to attach class to already attached symbol");
527 /********************** Funktion: unicode_getclasslink ************************
529 Sucht den Verweis von einem unicode-Symbol auf eine Klasse.
530 Wenn keine solche Klasse existiert, dann wird ein Fehler
533 ******************************************************************************/
535 classinfo *unicode_getclasslink (unicode *u)
537 PANICIF (!u->class, "Attempt to get unknown class-reference");
543 /********************* Funktion: unicode_unlinkclass *************************
545 Entfernt den Verweis auf eine Klasse wieder von einem Symbol
547 ******************************************************************************/
549 void unicode_unlinkclass (unicode *u)
551 PANICIF (!u->class, "Attempt to unlink not yet linked symbol");
557 /******************* Funktion> unicode_setstringlink *********************
559 H"angt einen Verweis auf einen konstanten String an ein
562 *************************************************************************/
564 void unicode_setstringlink (unicode *u, java_objectheader *str)
566 PANICIF (u->string, "Attempt to attach string to already attached symbol");
571 /********************* Funktion: unicode_unlinkstring *************************
573 Entfernt den Verweis auf einen String wieder von einem Symbol
575 ******************************************************************************/
577 void unicode_unlinkstring (unicode *u)
579 PANICIF (!u->class, "Attempt to unlink not yet linked symbol");
585 /*********************** Funktion: unicode_show ******************************
587 gibt eine Aufstellung aller Symbol im unicode-hash auf stdout aus.
588 (nur f"ur Debug-Zwecke)
590 *****************************************************************************/
597 printf ("UNICODE-HASH: %d slots for %d entries\n",
598 (int) unicodehashsize, (int) unicodeentries );
600 for (i=0; i<unicodehashsize; i++) {
603 printf ("SLOT %d: ", (int) i);
608 if (u->string) printf ("(string) ");
619 /******************************************************************************
620 *********************** Diverse Support-Funktionen ****************************
621 ******************************************************************************/
624 /******************** Funktion: desc_to_type **********************************
626 Findet zu einem gegebenen Typdescriptor den entsprechenden
629 ******************************************************************************/
631 u2 desc_to_type (unicode *descriptor)
633 if (descriptor->length < 1) panic ("Type-Descriptor is empty string");
635 switch (descriptor->text[0]) {
640 case 'Z': return TYPE_INT;
641 case 'D': return TYPE_DOUBLE;
642 case 'F': return TYPE_FLOAT;
643 case 'J': return TYPE_LONG;
645 case '[': return TYPE_ADDRESS;
648 sprintf (logtext, "Invalid Type-Descriptor: ");
649 unicode_sprint (logtext+strlen(logtext), descriptor);
655 /********************** Funktion: desc_typesize *******************************
657 Berechnet die L"ange (in Byte) eines Datenelements gegebenen Typs,
658 der durch den Typdescriptor gegeben ist.
660 ******************************************************************************/
662 u2 desc_typesize (unicode *descriptor)
664 switch (desc_to_type(descriptor)) {
665 case TYPE_INT: return 4;
666 case TYPE_LONG: return 8;
667 case TYPE_FLOAT: return 4;
668 case TYPE_DOUBLE: return 8;
669 case TYPE_ADDRESS: return sizeof(voidptr);
678 /******************************************************************************
679 ********************* Der garbage-collected Heap ******************************
680 *******************************************************************************
682 verwaltet einen Heap mit automatischer Speicherfreigabe.
684 (eine ausf"uhrliche Dokumentation findet sich in der Datei:
687 ******************************************************************************/
690 bool collectverbose = false; /* soll Meldung beim GC ausgegeben werden? */
693 #define BLOCKSIZE 8 /* Gr"osse eines Speicherblockes */
694 typedef u8 heapblock; /* Datentyp mit der Gr"osse eines Speicherblocks */
696 #if U8_AVAILABLE && SUPPORT_LONG
697 #define bitfieldtype u8
698 #define BITFIELDBITS 64
700 #define bitfieldtype u4
701 #define BITFIELDBITS 32
704 u4 heapsize; /* Gr"osse des Heap in Blocks */
705 u4 topofheap; /* Bisherige Obergrenze Heaps */
706 heapblock *heap; /* Speicher f"ur den Heap selbst */
708 bitfieldtype *startbits; /* Bitfeld f"ur Bereichsstartkennung */
709 bitfieldtype *markbits; /* Bitfeld f"ur Markierung */
710 bitfieldtype *referencebits; /* Bitfeld f"ur Folgereferenzenkennung */
712 u4 heapfillgrade; /* Menge der Daten im Heap */
713 u4 collectthreashold; /* Schwellwert f"ur n"achstes GC */
715 void **bottom_of_stack; /* Zeiger auf Untergrenze des C-Stacks */
716 chain *allglobalreferences; /* Liste f"ur alle globalen Zeiger */
718 typedef struct finalizernode {
719 struct finalizernode *next;
721 methodinfo *finalizer;
724 finalizernode *livefinalizees;
725 finalizernode *deadfinalizees;
728 typedef struct memarea { /* Datenstruktur f"ur einen Freispeicherbereich */
729 struct memarea *next;
732 typedef struct bigmemarea { /* Datenstruktur f"ur einen */
733 struct bigmemarea *next; /* Freispeicherbereich variabler L"ange */
737 #define DIFFERENTSIZES 128 /* Anzahl der 'kleinen' Freispeicherlisten */
738 memarea *memlist[DIFFERENTSIZES]; /* Die 'kleinen' Freispeicherlisten */
739 bitfieldtype memlistbits[DIFFERENTSIZES/BITFIELDBITS];
740 /* Bitfeld, in dem jeweils ein Bit gesetzt */
741 /* ist, wenn eine Liste noch etwas enth"alt */
743 bigmemarea *bigmemlist; /* Liste der gr"osseren Freispeicherbereiche */
748 /**************** Hilfsfunktion: lowest **************************************
750 liefert als Ergebnis die Nummer des niederwertigsten Bits einer
751 Zahl vom Typ bitfieldtype, das 1 ist.
752 Wenn die ganze Zahl keine 1en enth"alt, dann ist egal, was f"ur einen
753 Wert die Funktion l"iefert.
754 z.B.: lowest(1) = 0, lowest(12) = 2, lowest(1024) = 10
756 *****************************************************************************/
758 static u1 lowesttable[256] = {
759 255, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
760 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
761 5, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
762 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
763 6, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
764 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
765 5, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
766 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
767 7, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
768 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
769 5, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
770 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
771 6, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
772 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
773 5, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
774 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0 };
776 static int lowest(bitfieldtype i)
784 if (i111) return lowesttable[i111>>56];
785 else return 8+lowesttable[i11>>56];
789 if (i112) return 16+lowesttable[i112>>56];
790 else return 24+lowesttable[i1>>56];
797 if (i121) return 32+lowesttable[i121>>56];
798 else return 40+lowesttable[i12>>56];
802 if (i122) return 48+lowesttable[i122>>56];
803 else return 56+lowesttable[i>>56];
810 if (i11) return lowesttable[i11>>24];
811 else return 8+lowesttable[i1>>24];
815 if (i12) return 16+lowesttable[i12>>24];
816 else return 24+lowesttable[i>>24];
822 /******** Funktionen zum Setzen und L"oschen von Bits in Bitfeldern ***********/
824 static void setbit(bitfieldtype *bitfield, u4 bitnumber)
826 bitfield[bitnumber/BITFIELDBITS] |=
827 ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS);
830 static void clearbit(bitfieldtype *bitfield, u4 bitnumber)
832 bitfield[bitnumber/BITFIELDBITS] &=
833 ~((bitfieldtype) 1) << (bitnumber%BITFIELDBITS);
836 static bool isbitset(bitfieldtype *bitfield, u4 bitnumber)
838 return ( bitfield[bitnumber/BITFIELDBITS] &
839 ( ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS) ) ) != 0;
842 static bool isbitclear(bitfieldtype *bitfield, u4 bitnumber)
844 return ( bitfield[bitnumber/BITFIELDBITS] &
845 ( ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS) ) ) == 0;
849 /***************** Funktion: clearbitfield ************************************
851 l"oscht ein ganzes Bitfeld
853 ******************************************************************************/
855 static void clearbitfield(bitfieldtype *bitfield, u4 fieldsize)
858 t = ALIGN(fieldsize, BITFIELDBITS) / BITFIELDBITS;
859 for (i=0; i<t; i++) bitfield[i] = 0;
862 /************** Funktion: maskfieldwithfield **********************************
864 Verkn"upft zwei Bitfelder bitweise mit UND, das erste Bitfeld
865 wird mit dem Ergebnis "uberschrieben
867 ******************************************************************************/
869 static void maskfieldwithfield (bitfieldtype* bitfield,
870 bitfieldtype *maskfield, u4 fieldsize)
873 t = ALIGN(fieldsize, BITFIELDBITS) / BITFIELDBITS;
874 for (i=0; i<t; i++) bitfield[i] &= maskfield[i];
878 /************** Funktion: findnextsetbit **************************************
880 Sucht in einem Bitfeld ab einer Stelle das n"achste gesetzte Bit
881 und liefert die Nummer dieses Bits.
882 Wenn kein Bit mehr zwischen 'bitnumber' und 'fieldsize' gesetzt
883 ist, dann wird fieldsize zur"uckgeliefte.
885 ******************************************************************************/
887 static u4 findnextsetbit(bitfieldtype* bitfield, u4 fieldsize, u4 bitnumber)
889 bitfieldtype pattern;
892 if (bitnumber >= fieldsize) return fieldsize;
894 pattern = bitfield[bitnumber/BITFIELDBITS];
895 pattern >>= (bitnumber%BITFIELDBITS);
896 if (pattern) return bitnumber + lowest(pattern);
898 bitnumber = ((bitnumber + BITFIELDBITS) / BITFIELDBITS) * BITFIELDBITS;
903 /************ Funktion: findnextcombination_set_unset *************************
905 funktioniert wie findnextsetbit, allerdings sucht diese Funktion
906 nach einer Stelle, an der gleichzeitig ein Bit im ersten
907 Bitfeld gesetzt ist und im zweiten Bitfeld das entsprechende
908 Bit nicht gesetzt ist.
910 ******************************************************************************/
912 static u4 findnextcombination_set_unset
913 (bitfieldtype *bitfield1, bitfieldtype* bitfield2, u4 fieldsize, u4 bitnumber)
915 bitfieldtype pattern;
918 if (bitnumber >= fieldsize) return fieldsize;
920 pattern = bitfield1[bitnumber/BITFIELDBITS]
921 & (~bitfield2[bitnumber/BITFIELDBITS]);
922 pattern >>= (bitnumber%BITFIELDBITS);
923 if (pattern) return bitnumber + lowest(pattern);
925 bitnumber = ((bitnumber + BITFIELDBITS) / BITFIELDBITS) * BITFIELDBITS;
931 /************** Funktion: memlist_init ****************************************
933 initialisiert die Freispeicherlisten (zum nachfolgenden Eintragen
934 mit memlist_addrange).
936 ******************************************************************************/
938 static void memlist_init ()
941 for (i=0; i<DIFFERENTSIZES; i++) memlist[i] = NULL;
942 clearbitfield (memlistbits, DIFFERENTSIZES);
947 /************** Funktion: memlist_addrange ************************************
949 f"ugt einen Bereich von Heap-Bl"ocken zur Freispeicherliste
950 hinzu (in die freien Heap-Bl"ocke werden dabei verschiedene
951 Verkettungszeiger hineingeschrieben).
953 ******************************************************************************/
955 static void memlist_addrange (u4 freestart, u4 freesize)
957 if (freesize>=DIFFERENTSIZES) {
958 bigmemarea *m = (bigmemarea*) (heap+freestart);
959 m -> next = bigmemlist;
960 m -> size = freesize;
964 if (freesize*BLOCKSIZE>=sizeof(memarea)) {
965 memarea *m = (memarea*) (heap+freestart);
966 m -> next = memlist[freesize];
967 memlist[freesize] = m;
968 setbit (memlistbits, freesize);
974 /************** Funktion: memlist_getsuitable *********************************
976 sucht in der Freispeicherliste einen Speicherbereich, der m"oglichst
977 genau die gew"unschte L"ange hat.
978 Der Bereich wird dabei auf jeden Fall aus der Liste ausgetragen.
979 (Wenn der Bereich zu lang sein sollte, dann kann der Aufrufer den
980 Rest wieder mit 'memlist_addrange' in die Liste einh"angen)
982 Return (in Referenzparametern):
983 *freestart: Anfang des freien Speichers
984 *freelength: L"ange dieses Speicherbereiches
986 Wenn kein passender Speicherblock mehr gefunden werden kann, dann
987 wird in '*freelength' 0 hineingeschrieben.
989 ******************************************************************************/
991 static void memlist_getsuitable (u4 *freestart, u4 *freelength, u4 length)
994 bigmemarea *prevm = NULL;
996 if (length<DIFFERENTSIZES) {
999 if (memlist[length]) {
1000 firstfreelength = length;
1003 firstfreelength = findnextsetbit
1004 (memlistbits, DIFFERENTSIZES, length+3);
1005 /* wenn kein passender Block da ist, dann gleich nach */
1006 /* einem etwas gr"osseren suchen, damit keine kleinen */
1007 /* St"uckchen "ubrigbleiben */
1010 if (firstfreelength<DIFFERENTSIZES) {
1011 memarea *m = memlist[firstfreelength];
1012 memlist[firstfreelength] = m->next;
1013 if (!m->next) clearbit (memlistbits, firstfreelength);
1014 *freestart = ((heapblock*) m) - heap;
1015 *freelength = firstfreelength;
1022 if (m->size >= length) {
1023 if (prevm) prevm->next = m->next;
1024 else bigmemlist = m->next;
1026 *freestart = ((heapblock*) m) - heap;
1027 *freelength = m->size;
1042 /******************* Funktion: mark *******************************************
1044 Markiert ein m"oglicherweise g"ultiges Objekt.
1045 Sollte sich herausstellen, dass der Zeiger gar nicht auf ein Objekt
1046 am Heap zeigt, dann wird eben gar nichts markiert.
1048 ******************************************************************************/
1050 static void markreferences (void **rstart, void **rend);
1052 static void mark (heapblock *obj)
1054 u4 blocknum,objectend;
1056 if ((long) obj & (BLOCKSIZE-1)) return;
1058 if (obj<heap) return;
1059 if (obj>=(heap+topofheap) ) return;
1061 blocknum = obj-heap;
1062 if ( isbitclear(startbits, blocknum) ) return;
1063 if ( isbitset(markbits, blocknum) ) return;
1065 setbit (markbits, blocknum);
1067 if ( isbitclear(referencebits, blocknum) ) return;
1069 objectend = findnextsetbit (startbits, topofheap, blocknum+1);
1070 markreferences ((void**)obj, (void**) (heap+objectend) );
1074 /******************** Funktion: markreferences ********************************
1076 Geht einen Speicherbereich durch, und markiert alle Objekte, auf
1077 die von diesem Bereich aus irgendeine Referenz existiert.
1079 ******************************************************************************/
1081 static void markreferences (void **rstart, void **rend)
1085 for (ptr=rstart; ptr<rend; ptr++) mark (*ptr);
1089 /******************* Funktion: markstack **************************************
1091 Marks all objects that are referenced by the (C-)stacks of
1094 (The stack-bottom is to be specified in the call to heap_init).
1096 ******************************************************************************/
1098 static void markstack () /* schani */
1101 void **top_of_stack = &dummy;
1106 for (aThread = liveThreads; aThread != 0; aThread = CONTEXT(aThread).nextlive) {
1107 mark((heapblock*)aThread);
1108 if (aThread == currentThread) {
1109 if (top_of_stack > (void**)CONTEXT(aThread).stackEnd)
1110 markreferences ((void**)CONTEXT(aThread).stackEnd, top_of_stack);
1112 markreferences (top_of_stack, (void**)CONTEXT(aThread).stackEnd);
1115 if (CONTEXT(aThread).usedStackTop > CONTEXT(aThread).stackEnd)
1116 markreferences ((void**)CONTEXT(aThread).stackEnd,
1117 (void**)CONTEXT(aThread).usedStackTop + 16);
1119 markreferences ((void**)CONTEXT(aThread).usedStackTop - 16,
1120 (void**)CONTEXT(aThread).stackEnd);
1124 markreferences((void**)&threadQhead[0], (void**)&threadQhead[MAX_THREAD_PRIO]);
1126 if (top_of_stack > bottom_of_stack)
1127 markreferences(bottom_of_stack, top_of_stack);
1129 markreferences(top_of_stack, bottom_of_stack);
1135 /**************** Funktion: searchlivefinalizees *****************************
1137 geht die Liste aller Objekte durch, die noch finalisiert werden m"ussen
1138 (livefinalizees), und tr"agt alle nicht mehr markierten in die
1139 Liste deadfinalizess ein (allerdings werden sie vorher noch als
1140 erreicht markiert, damit sie nicht jetzt gleich gel"oscht werden).
1142 *****************************************************************************/
1144 static void searchlivefinalizees ()
1146 finalizernode *fn = livefinalizees;
1147 finalizernode *lastlive = NULL;
1151 /* alle zu finalisierenden Objekte, die nicht mehr markiert sind: */
1152 if (isbitclear (markbits, fn->objstart)) {
1153 finalizernode *nextfn = fn->next;
1155 mark (heap + fn->objstart);
1157 if (lastlive) lastlive -> next = nextfn;
1158 else livefinalizees = nextfn;
1160 fn -> next = deadfinalizees;
1161 deadfinalizees = fn;
1174 /********************** Funktion: finalizedead *******************************
1176 ruft die 'finalize'-Methode aller Objekte in der 'deadfinalizees'-
1178 Achtung: Es kann hier eventuell zu neuerlichen Speicheranforderungen
1179 (mit potentiell notwendigem GC) kommen, deshalb m"ussen manche
1180 globalen Variablen in lokale Variblen kopiert werden
1181 (Reentrant-F"ahigkeit!!!)
1183 ******************************************************************************/
1185 static void finalizedead()
1187 finalizernode *fn = deadfinalizees;
1188 deadfinalizees = NULL;
1191 finalizernode *nextfn = fn->next;
1193 asm_calljavamethod (fn->finalizer, heap+fn->objstart, NULL,NULL,NULL);
1194 FREE (fn, finalizernode);
1203 /****************** Funktion: heap_docollect **********************************
1205 F"uhrt eine vollst"andige Garbage Collection durch
1207 ******************************************************************************/
1209 static void heap_docollect ()
1211 u4 freestart,freeend;
1213 bitfieldtype *dummy;
1219 fprintf(stderr, "doing garbage collection\n");
1221 /* alle Markierungsbits l"oschen */
1222 clearbitfield (markbits, topofheap);
1224 /* Alle vom Stack referenzierten Objekte markieren */
1225 asm_dumpregistersandcall (markstack);
1227 /* Alle von globalen Variablen erreichbaren Objekte markieren */
1228 p = chain_first (allglobalreferences);
1231 p = chain_next (allglobalreferences);
1234 /* alle Objekte durchsehen, die eine finalizer-Methode haben */
1235 searchlivefinalizees();
1237 /* alle Reference-Bits l"oschen, deren Objekte nicht */
1238 /* mehr erreichbar sind */
1239 maskfieldwithfield (referencebits, markbits, topofheap);
1242 /* Freispeicherliste initialisieren */
1246 /* Heap schrittweise durchgehen, und alle freien Bl"ocke merken */
1251 /* Anfang des n"achsten freien Bereiches suchen */
1252 freestart = findnextcombination_set_unset
1253 (startbits, markbits, topofheap, freeend);
1255 /* Wenn es keinen freien Bereich mehr gibt -> fertig */
1256 if (freestart>=topofheap) goto freememfinished;
1258 /* Anfang des freien Bereiches markieren */
1259 setbit (markbits, freestart);
1261 /* Ende des freien Bereiches suchen */
1262 freeend = findnextsetbit (markbits, topofheap, freestart+1);
1264 /* Freien Bereich in Freispeicherliste einh"angen */
1265 memlist_addrange (freestart, freeend-freestart);
1267 /* Menge des freien Speichers mitnotieren */
1268 heapfreemem += (freeend-freestart);
1273 /* Die Rollen von markbits und startbits vertauschen */
1275 markbits = startbits;
1279 /* Threashold-Wert f"ur n"achstes Collect */
1280 oldfillgrade = heapfillgrade;
1281 heapfillgrade = topofheap - heapfreemem;
1282 collectthreashold = heapfillgrade*3; /* eine nette Heuristik */
1284 /* Eventuell eine Meldung ausgeben */
1285 if (collectverbose) {
1286 sprintf (logtext, "Garbage Collection: previous/now = %d / %d ",
1287 (int) (oldfillgrade * BLOCKSIZE),
1288 (int) (heapfillgrade * BLOCKSIZE) );
1294 /* alle gerade unerreichbar gewordenen Objekte mit
1295 finalize-Methoden jetzt finalisieren.
1296 Achtung: Diese Funktion kann zu neuerlichem GC f"uhren!! */
1301 /************************* Function: gc_init **********************************
1303 Initializes the garbage collection thread mechanism.
1305 ******************************************************************************/
1310 iCv gcConditionStart;
1311 iCv gcConditionDone;
1316 gcStartMutex.holder = 0;
1317 gcStartMutex.count = 0;
1318 gcStartMutex.muxWaiters = 0;
1320 gcThreadMutex.holder = 0;
1321 gcThreadMutex.count = 0;
1322 gcThreadMutex.muxWaiters = 0;
1324 gcConditionStart.cvWaiters = 0;
1325 gcConditionStart.mux = 0;
1327 gcConditionDone.cvWaiters = 0;
1328 gcConditionDone.mux = 0;
1337 /************************* Function: gc_thread ********************************
1339 In an endless loop waits for a condition to be posted, then
1340 garbage collects the heap.
1342 ******************************************************************************/
1348 intsRestore(); /* all threads start with interrupts disabled */
1350 assert(blockInts == 0);
1352 lock_mutex(&gcThreadMutex);
1356 wait_cond(&gcThreadMutex, &gcConditionStart, 0);
1362 signal_cond(&gcConditionDone);
1371 lock_mutex(&gcThreadMutex);
1373 signal_cond(&gcConditionStart);
1374 wait_cond(&gcThreadMutex, &gcConditionDone, 0);
1376 unlock_mutex(&gcThreadMutex);
1383 /************************* Funktion: heap_init ********************************
1385 Initialisiert den Garbage Collector.
1387 heapbytesize: Maximale Gr"osse des Heap (in Bytes)
1388 heapbytestartsize: Gr"osse des Heaps, bei dem zum ersten mal eine
1389 GC durchgef"uhrt werden soll.
1390 stackbottom: Ein Zeiger auf die Untergrenze des Stacks, im dem
1391 Referenzen auf Objekte stehen k"onnen.
1393 ******************************************************************************/
1395 void heap_init (u4 heapbytesize, u4 heapbytestartsize, void **stackbottom)
1398 #ifdef TRACECALLARGS
1400 heapsize = ALIGN (heapbytesize, getpagesize());
1401 heapsize = heapsize/BLOCKSIZE;
1402 heap = (void*) mmap ((void*) 0x10000000, (size_t) (heapsize * BLOCKSIZE),
1403 PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, (off_t) 0);
1404 if (heap != (void *) 0x10000000) {
1406 printf("address = %p\n", heap);
1407 panic("mmap failed\n");
1412 heapsize = ALIGN (heapbytesize, 1024);
1413 heapsize = heapsize/BLOCKSIZE;
1414 heap = MNEW (heapblock, heapsize);
1419 startbits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
1420 markbits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
1421 referencebits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
1422 clearbitfield (startbits, heapsize);
1423 clearbitfield (markbits, heapsize);
1424 clearbitfield (referencebits, heapsize);
1427 collectthreashold = heapbytestartsize/BLOCKSIZE;
1428 allglobalreferences = chain_new ();
1429 bottom_of_stack = stackbottom;
1431 livefinalizees = NULL;
1432 deadfinalizees = NULL;
1436 /****************** Funktion: heap_close **************************************
1438 Gibt allen ben"otigten Speicher frei
1440 ******************************************************************************/
1444 #ifndef TRACECALLARGS
1445 MFREE (heap, heapblock, heapsize); */
1447 MFREE (startbits, bitfieldtype, heapsize/BITFIELDBITS);
1448 MFREE (markbits, bitfieldtype, heapsize/BITFIELDBITS);
1449 MFREE (referencebits, bitfieldtype, heapsize/BITFIELDBITS);
1450 chain_free (allglobalreferences);
1452 while (livefinalizees) {
1453 finalizernode *n = livefinalizees->next;
1454 FREE (livefinalizees, finalizernode);
1460 /***************** Funktion: heap_addreference ********************************
1462 Teilt dem GC eine Speicherstelle mit, an der eine globale Referenz
1463 auf Objekte gespeichert sein kann.
1465 ******************************************************************************/
1467 void heap_addreference (void **reflocation)
1469 intsDisable(); /* schani */
1471 chain_addlast (allglobalreferences, reflocation);
1473 intsRestore(); /* schani */
1478 /***************** Funktion: heap_allocate ************************************
1480 Fordert einen Speicher vom Heap an, der eine gew"unschte Gr"osse
1481 (in Byte angegeben) haben muss.
1482 Wenn kein Speicher mehr vorhanden ist (auch nicht nach einem
1483 Garbage Collection-Durchlauf), dann wird NULL zur"uckgegeben.
1484 Zus"atzlich wird durch den Parameter 'references' angegeben, ob
1485 in das angelegte Objekt Referenzen auf andere Objekte eingetragen
1487 (Wichtig wegen Beschleunigung des Mark&Sweep-Durchlauf)
1488 Im Zweifelsfalle immer references=true verwenden.
1490 ******************************************************************************/
1492 void *heap_allocate (u4 bytelength, bool references, methodinfo *finalizer)
1494 u4 freestart,freelength;
1495 u4 length = ALIGN(bytelength, BLOCKSIZE) / BLOCKSIZE;
1497 intsDisable(); /* schani */
1499 memlist_getsuitable (&freestart, &freelength, length);
1503 if ( (topofheap+length > collectthreashold)
1504 || (topofheap+length > heapsize) ) {
1510 memlist_getsuitable (&freestart, &freelength, length);
1511 if (freelength) goto onemoretry;
1514 if (topofheap+length > heapsize) {
1515 sprintf (logtext, "Heap-Allocation failed for %d bytes",
1518 intsRestore(); /* schani */
1522 freestart = topofheap;
1523 freelength = length;
1524 setbit (startbits, topofheap);
1525 topofheap += length;
1528 if (freelength>length) {
1529 setbit (startbits, freestart+length);
1530 memlist_addrange (freestart+length, freelength-length);
1534 if (references) setbit (referencebits, freestart);
1536 heapfillgrade += length;
1539 finalizernode *n = NEW(finalizernode);
1540 n -> next = livefinalizees;
1541 n -> objstart = freestart;
1542 n -> finalizer = finalizer;
1546 intsRestore(); /* schani */
1549 sprintf (logtext, "new returns: %lx", (long) (heap + freestart));
1553 return (void*) (heap + freestart);