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 "sysdep/threads.h"
31 #include "threads/thread.h" /* schani */
32 #include "threads/locks.h"
35 bool runverbose = false;
37 int count_unicode_len = 0;
40 /******************************************************************************
41 ************************* Der Dateien-Sauger **********************************
42 *******************************************************************************
44 dient zum Behandeln von Java-ClassFiles ("offnen, schlie"sen,
45 einlesen von 8-, 16-, 32-, 64-bit Integers und 32-, 64- bit Floats)
47 ******************************************************************************/
49 static FILE *classfile = NULL; /* File-handle der gerade gelesenen Datei */
50 static char *classpath = ""; /* Suchpfad f"ur die ClassFiles */
54 /************************** Funktion: suck_init ******************************
56 Wird zu Programmstart einmal aufgerufen und setzt den Suchpfad f"ur
59 ******************************************************************************/
61 void suck_init (char *cpath)
68 /************************** Funktion: suck_start ******************************
70 "Offnet die Datei f"ur die Klasse des gegebenen Namens zum Lesen.
71 Dabei werden alle im Suchpfad angegebenen Verzeichnisse durchsucht,
72 bis eine entsprechende Datei ( <classname>.class) gefunden wird.
74 ******************************************************************************/
76 bool suck_start (unicode *classname)
78 #define MAXFILENAME 1000 /* Maximale Langes des Dateinamens plus Pfad */
80 char filename[MAXFILENAME+10]; /* Platz fuer '.class' */
89 while ( *pathpos == ':' ) pathpos++;
92 while ( (*pathpos) && (*pathpos!=':') ) {
93 PANICIF (filenamelen >= MAXFILENAME, "Filename too long") ;
95 filename[filenamelen++] = *(pathpos++);
98 filename[filenamelen++] = '/';
100 for (i=0; i < classname -> length; i++) {
101 PANICIF (filenamelen >= MAXFILENAME, "Filename too long");
103 c = classname -> text [i];
104 if (c=='/') c = '/'; /* Slashes im Namen passen zu UNIX */
106 if ( c<=' ' || c>'z') {
111 filename[filenamelen++] = c;
114 strcpy (filename+filenamelen, ".class");
116 classfile = fopen(filename, "r");
124 sprintf (logtext,"Can not open class file '%s'", filename);
130 /************************** Funktion: suck_stop *******************************
132 Schlie"st die offene Datei wieder.
134 ******************************************************************************/
141 while ( fread (&dummy, 1,1, classfile) > 0) rest++;
143 sprintf (logtext,"There are %d access bytes at end of classfile",
154 /************************** Lesefunktionen ***********************************
156 Lesen von der Datei in verschieden grossen Paketen
157 (8,16,32,64-bit Integer oder Float)
159 *****************************************************************************/
161 void suck_nbytes (u1 *buffer, u4 len)
163 if ( fread (buffer, 1, len, classfile) != len) panic ("Unexpected EOF");
167 void skip_nbytes (u4 len)
170 for (i=0; i<len; i++) suck_u1 ();
177 if ( fread (&b, 1,1, classfile) != 1) panic ("Unexpected EOF");
184 if ( fread (&b, 1,1, classfile) != 1) panic ("Unexpected EOF");
192 if ( fread (b, 1,2, classfile) != 2) panic ("Unexpected EOF");
193 return (b[0]<<8) + b[1];
206 if ( fread (b, 1,4, classfile) != 4) panic ("Unexpected EOF");
207 v = ( ((u4)b[0]) <<24) + ( ((u4)b[1])<<16) + ( ((u4)b[2])<<8) + ((u4)b[3]);
223 return (hi<<32) + lo;
245 for (i=0; i<4; i++) buffer[3-i] = suck_u1 ();
246 memcpy ( (u1*) (&f), buffer, 4);
248 suck_nbytes ( (u1*) (&f), 4 );
251 PANICIF (sizeof(float) != 4, "Incompatible float-format");
257 double suck_double ()
264 for (i=0; i<8; i++) buffer[7-i] = suck_u1 ();
265 memcpy ( (u1*) (&d), buffer, 8);
267 suck_nbytes ( (u1*) (&d), 8 );
270 PANICIF (sizeof(double) != 8, "Incompatible double-format" );
278 /******************************************************************************
279 ******************** Der Unicode-Symbol-Verwalter *****************************
280 *******************************************************************************
282 legt eine Hashtabelle f"ur unicode-Symbole an und verwaltet
283 das Eintragen neuer Symbole
285 ******************************************************************************/
289 #define UNICODESTART 2187 /* Startgr"osse: moeglichst gross und prim */
291 static u4 unicodeentries; /* Anzahl der Eintr"age in der Tabelle */
292 static u4 unicodehashsize; /* Gr"osse der Tabelle */
293 static unicode ** unicodehash; /* Zeiger auf die Tabelle selbst */
296 /*********************** Funktion: unicode_init ******************************
298 Initialisiert die unicode-Symboltabelle (muss zu Systemstart einmal
301 *****************************************************************************/
308 count_unicode_len += sizeof(unicode*) * unicodehashsize;
312 unicodehashsize = UNICODESTART;
313 unicodehash = MNEW (unicode*, unicodehashsize);
314 for (i=0; i<unicodehashsize; i++) unicodehash[i] = NULL;
318 /*********************** Funktion: unicode_close *****************************
320 Gibt allen Speicher der Symboltabellen frei.
321 Parameter: Ein Zeiger auf eine Funktion, die dazu n"otig ist,
322 Stringkonstanten (die mit 'unicode_setstringlink'
323 Unicode-Symbole gebunden wurden) wieder freizugeben
325 *****************************************************************************/
327 void unicode_close (stringdeleter del)
332 for (i=0; i<unicodehashsize; i++) {
335 unicode *nextu = u->hashlink;
337 if (u->string) del (u->string);
339 MFREE (u->text, u2, u->length);
344 MFREE (unicodehash, unicode*, unicodehashsize);
348 /********************* Funktion: unicode_display ******************************
350 Gibt ein unicode-Symbol auf stdout aus (zu Debugzwecken)
352 ******************************************************************************/
354 void unicode_display (unicode *u)
357 for (i=0; i < u->length; i++) {
359 if (c>=32 && c<=127) printf ("%c",c);
366 /********************* Funktion: unicode_sprint ******************************
368 Schreibt ein unicode-Symbol in einen C-String
370 ******************************************************************************/
372 void unicode_sprint (char *buffer, unicode *u)
375 for (i=0; i < u->length; i++) buffer[i] = u->text[i];
380 /********************* Funktion: unicode_fprint ******************************
382 Schreibt ein unicode-Symbol auf eine Datei aus
384 ******************************************************************************/
386 void unicode_fprint (FILE *file, unicode *u)
389 for (i=0; i < u->length; i++) putc (u->text[i], file);
393 /****************** interne Funktion: u_hashkey ******************************/
395 static u4 u_hashkey (u2 *text, u2 length)
400 for (i=0; i<length; i++) {
401 k ^= ( ((u4) (text[i])) << sh );
409 /*************** interne Funktion: u_reorganizehash **************************/
411 static void u_reorganizehash ()
416 u4 newhashsize = unicodehashsize*2;
417 unicode **newhash = MNEW (unicode*, newhashsize);
420 count_unicode_len += sizeof(unicode*) * unicodehashsize;
423 for (i=0; i<newhashsize; i++) newhash[i] = NULL;
425 for (i=0; i<unicodehashsize; i++) {
428 unicode *nextu = u -> hashlink;
429 u4 slot = (u->key) % newhashsize;
431 u->hashlink = newhash[slot];
438 MFREE (unicodehash, unicode*, unicodehashsize);
439 unicodehash = newhash;
440 unicodehashsize = newhashsize;
444 /****************** Funktion: unicode_new_u2 **********************************
446 Legt ein neues unicode-Symbol an. Der Text des Symbols wird dieser
447 Funktion als u2-Array "ubergeben
449 ******************************************************************************/
451 unicode *unicode_new_u2 (u2 *text, u2 length)
453 u4 key = u_hashkey (text, length);
454 u4 slot = key % unicodehashsize;
455 unicode *u = unicodehash[slot];
460 if (u->length == length) {
461 for (i=0; i<length; i++) {
462 if (text[i] != u->text[i]) goto nomatch;
472 count_unicode_len += sizeof(unicode) + 2 * length;
478 u->text = MNEW (u2, length);
481 u->hashlink = unicodehash[slot];
482 unicodehash[slot] = u;
483 for (i=0; i<length; i++) u->text[i] = text[i];
487 if ( unicodeentries > (unicodehashsize/2)) u_reorganizehash();
493 /********************* Funktion: unicode_new_char *****************************
495 Legt ein neues unicode-Symbol an. Der Text des Symbols wird dieser
496 Funktion als C-String ( = char* ) "ubergeben
498 ******************************************************************************/
500 unicode *unicode_new_char (char *text)
502 #define MAXNEWCHAR 500
503 u2 buffer[MAXNEWCHAR];
507 while ( (c = *text) != '\0' ) {
508 if (length>=MAXNEWCHAR) panic ("Text too long in unicode_new_char");
509 buffer[length++] = c;
512 return unicode_new_u2 (buffer, length);
516 /********************** Funktion: unicode_setclasslink ************************
518 H"angt einen Verweis auf eine Klasse an ein unicode-Symbol an.
520 ******************************************************************************/
522 void unicode_setclasslink (unicode *u, classinfo *class)
524 PANICIF (u->class, "Attempt to attach class to already attached symbol");
528 /********************** Funktion: unicode_getclasslink ************************
530 Sucht den Verweis von einem unicode-Symbol auf eine Klasse.
531 Wenn keine solche Klasse existiert, dann wird ein Fehler
534 ******************************************************************************/
536 classinfo *unicode_getclasslink (unicode *u)
538 PANICIF (!u->class, "Attempt to get unknown class-reference");
544 /********************* Funktion: unicode_unlinkclass *************************
546 Entfernt den Verweis auf eine Klasse wieder von einem Symbol
548 ******************************************************************************/
550 void unicode_unlinkclass (unicode *u)
552 PANICIF (!u->class, "Attempt to unlink not yet linked symbol");
558 /******************* Funktion> unicode_setstringlink *********************
560 H"angt einen Verweis auf einen konstanten String an ein
563 *************************************************************************/
565 void unicode_setstringlink (unicode *u, java_objectheader *str)
567 PANICIF (u->string, "Attempt to attach string to already attached symbol");
572 /********************* Funktion: unicode_unlinkstring *************************
574 Entfernt den Verweis auf einen String wieder von einem Symbol
576 ******************************************************************************/
578 void unicode_unlinkstring (unicode *u)
580 PANICIF (!u->class, "Attempt to unlink not yet linked symbol");
586 /*********************** Funktion: unicode_show ******************************
588 gibt eine Aufstellung aller Symbol im unicode-hash auf stdout aus.
589 (nur f"ur Debug-Zwecke)
591 *****************************************************************************/
598 printf ("UNICODE-HASH: %d slots for %d entries\n",
599 (int) unicodehashsize, (int) unicodeentries );
601 for (i=0; i<unicodehashsize; i++) {
604 printf ("SLOT %d: ", (int) i);
609 if (u->string) printf ("(string) ");
620 /******************************************************************************
621 *********************** Diverse Support-Funktionen ****************************
622 ******************************************************************************/
625 /******************** Funktion: desc_to_type **********************************
627 Findet zu einem gegebenen Typdescriptor den entsprechenden
630 ******************************************************************************/
632 u2 desc_to_type (unicode *descriptor)
634 if (descriptor->length < 1) panic ("Type-Descriptor is empty string");
636 switch (descriptor->text[0]) {
641 case 'Z': return TYPE_INT;
642 case 'D': return TYPE_DOUBLE;
643 case 'F': return TYPE_FLOAT;
644 case 'J': return TYPE_LONG;
646 case '[': return TYPE_ADDRESS;
649 sprintf (logtext, "Invalid Type-Descriptor: ");
650 unicode_sprint (logtext+strlen(logtext), descriptor);
656 /********************** Funktion: desc_typesize *******************************
658 Berechnet die L"ange (in Byte) eines Datenelements gegebenen Typs,
659 der durch den Typdescriptor gegeben ist.
661 ******************************************************************************/
663 u2 desc_typesize (unicode *descriptor)
665 switch (desc_to_type(descriptor)) {
666 case TYPE_INT: return 4;
667 case TYPE_LONG: return 8;
668 case TYPE_FLOAT: return 4;
669 case TYPE_DOUBLE: return 8;
670 case TYPE_ADDRESS: return sizeof(voidptr);
679 /******************************************************************************
680 ********************* Der garbage-collected Heap ******************************
681 *******************************************************************************
683 verwaltet einen Heap mit automatischer Speicherfreigabe.
685 (eine ausf"uhrliche Dokumentation findet sich in der Datei:
688 ******************************************************************************/
691 bool collectverbose = false; /* soll Meldung beim GC ausgegeben werden? */
694 #define BLOCKSIZE 8 /* Gr"osse eines Speicherblockes */
695 typedef u8 heapblock; /* Datentyp mit der Gr"osse eines Speicherblocks */
697 #if U8_AVAILABLE && SUPPORT_LONG
698 #define bitfieldtype u8
699 #define BITFIELDBITS 64
701 #define bitfieldtype u4
702 #define BITFIELDBITS 32
705 u4 heapsize; /* Gr"osse des Heap in Blocks */
706 u4 topofheap; /* Bisherige Obergrenze Heaps */
707 heapblock *heap; /* Speicher f"ur den Heap selbst */
709 bitfieldtype *startbits; /* Bitfeld f"ur Bereichsstartkennung */
710 bitfieldtype *markbits; /* Bitfeld f"ur Markierung */
711 bitfieldtype *referencebits; /* Bitfeld f"ur Folgereferenzenkennung */
713 u4 heapfillgrade; /* Menge der Daten im Heap */
714 u4 collectthreashold; /* Schwellwert f"ur n"achstes GC */
716 void **bottom_of_stack; /* Zeiger auf Untergrenze des C-Stacks */
717 chain *allglobalreferences; /* Liste f"ur alle globalen Zeiger */
719 typedef struct finalizernode {
720 struct finalizernode *next;
722 methodinfo *finalizer;
725 finalizernode *livefinalizees;
726 finalizernode *deadfinalizees;
729 typedef struct memarea { /* Datenstruktur f"ur einen Freispeicherbereich */
730 struct memarea *next;
733 typedef struct bigmemarea { /* Datenstruktur f"ur einen */
734 struct bigmemarea *next; /* Freispeicherbereich variabler L"ange */
738 #define DIFFERENTSIZES 128 /* Anzahl der 'kleinen' Freispeicherlisten */
739 memarea *memlist[DIFFERENTSIZES]; /* Die 'kleinen' Freispeicherlisten */
740 bitfieldtype memlistbits[DIFFERENTSIZES/BITFIELDBITS];
741 /* Bitfeld, in dem jeweils ein Bit gesetzt */
742 /* ist, wenn eine Liste noch etwas enth"alt */
744 bigmemarea *bigmemlist; /* Liste der gr"osseren Freispeicherbereiche */
749 /**************** Hilfsfunktion: lowest **************************************
751 liefert als Ergebnis die Nummer des niederwertigsten Bits einer
752 Zahl vom Typ bitfieldtype, das 1 ist.
753 Wenn die ganze Zahl keine 1en enth"alt, dann ist egal, was f"ur einen
754 Wert die Funktion l"iefert.
755 z.B.: lowest(1) = 0, lowest(12) = 2, lowest(1024) = 10
757 *****************************************************************************/
759 static u1 lowesttable[256] = {
760 255, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
761 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
762 5, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
763 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
764 6, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
765 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
766 5, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
767 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
768 7, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
769 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
770 5, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
771 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
772 6, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
773 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
774 5, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,
775 4, 0,1,0,2,0,1,0,3,0,1,0,2,0,1,0 };
777 static int lowest(bitfieldtype i)
785 if (i111) return lowesttable[i111>>56];
786 else return 8+lowesttable[i11>>56];
790 if (i112) return 16+lowesttable[i112>>56];
791 else return 24+lowesttable[i1>>56];
798 if (i121) return 32+lowesttable[i121>>56];
799 else return 40+lowesttable[i12>>56];
803 if (i122) return 48+lowesttable[i122>>56];
804 else return 56+lowesttable[i>>56];
811 if (i11) return lowesttable[i11>>24];
812 else return 8+lowesttable[i1>>24];
816 if (i12) return 16+lowesttable[i12>>24];
817 else return 24+lowesttable[i>>24];
823 /******** Funktionen zum Setzen und L"oschen von Bits in Bitfeldern ***********/
825 static void setbit(bitfieldtype *bitfield, u4 bitnumber)
827 bitfield[bitnumber/BITFIELDBITS] |=
828 ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS);
831 static void clearbit(bitfieldtype *bitfield, u4 bitnumber)
833 bitfield[bitnumber/BITFIELDBITS] &=
834 ~((bitfieldtype) 1) << (bitnumber%BITFIELDBITS);
837 static bool isbitset(bitfieldtype *bitfield, u4 bitnumber)
839 return ( bitfield[bitnumber/BITFIELDBITS] &
840 ( ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS) ) ) != 0;
843 static bool isbitclear(bitfieldtype *bitfield, u4 bitnumber)
845 return ( bitfield[bitnumber/BITFIELDBITS] &
846 ( ((bitfieldtype) 1) << (bitnumber%BITFIELDBITS) ) ) == 0;
850 /***************** Funktion: clearbitfield ************************************
852 l"oscht ein ganzes Bitfeld
854 ******************************************************************************/
856 static void clearbitfield(bitfieldtype *bitfield, u4 fieldsize)
859 t = ALIGN(fieldsize, BITFIELDBITS) / BITFIELDBITS;
860 for (i=0; i<t; i++) bitfield[i] = 0;
863 /************** Funktion: maskfieldwithfield **********************************
865 Verkn"upft zwei Bitfelder bitweise mit UND, das erste Bitfeld
866 wird mit dem Ergebnis "uberschrieben
868 ******************************************************************************/
870 static void maskfieldwithfield (bitfieldtype* bitfield,
871 bitfieldtype *maskfield, u4 fieldsize)
874 t = ALIGN(fieldsize, BITFIELDBITS) / BITFIELDBITS;
875 for (i=0; i<t; i++) bitfield[i] &= maskfield[i];
879 /************** Funktion: findnextsetbit **************************************
881 Sucht in einem Bitfeld ab einer Stelle das n"achste gesetzte Bit
882 und liefert die Nummer dieses Bits.
883 Wenn kein Bit mehr zwischen 'bitnumber' und 'fieldsize' gesetzt
884 ist, dann wird fieldsize zur"uckgeliefte.
886 ******************************************************************************/
888 static u4 findnextsetbit(bitfieldtype* bitfield, u4 fieldsize, u4 bitnumber)
890 bitfieldtype pattern;
893 if (bitnumber >= fieldsize) return fieldsize;
895 pattern = bitfield[bitnumber/BITFIELDBITS];
896 pattern >>= (bitnumber%BITFIELDBITS);
897 if (pattern) return bitnumber + lowest(pattern);
899 bitnumber = ((bitnumber + BITFIELDBITS) / BITFIELDBITS) * BITFIELDBITS;
904 /************ Funktion: findnextcombination_set_unset *************************
906 funktioniert wie findnextsetbit, allerdings sucht diese Funktion
907 nach einer Stelle, an der gleichzeitig ein Bit im ersten
908 Bitfeld gesetzt ist und im zweiten Bitfeld das entsprechende
909 Bit nicht gesetzt ist.
911 ******************************************************************************/
913 static u4 findnextcombination_set_unset
914 (bitfieldtype *bitfield1, bitfieldtype* bitfield2, u4 fieldsize, u4 bitnumber)
916 bitfieldtype pattern;
919 if (bitnumber >= fieldsize) return fieldsize;
921 pattern = bitfield1[bitnumber/BITFIELDBITS]
922 & (~bitfield2[bitnumber/BITFIELDBITS]);
923 pattern >>= (bitnumber%BITFIELDBITS);
924 if (pattern) return bitnumber + lowest(pattern);
926 bitnumber = ((bitnumber + BITFIELDBITS) / BITFIELDBITS) * BITFIELDBITS;
932 /************** Funktion: memlist_init ****************************************
934 initialisiert die Freispeicherlisten (zum nachfolgenden Eintragen
935 mit memlist_addrange).
937 ******************************************************************************/
939 static void memlist_init ()
942 for (i=0; i<DIFFERENTSIZES; i++) memlist[i] = NULL;
943 clearbitfield (memlistbits, DIFFERENTSIZES);
948 /************** Funktion: memlist_addrange ************************************
950 f"ugt einen Bereich von Heap-Bl"ocken zur Freispeicherliste
951 hinzu (in die freien Heap-Bl"ocke werden dabei verschiedene
952 Verkettungszeiger hineingeschrieben).
954 ******************************************************************************/
956 static void memlist_addrange (u4 freestart, u4 freesize)
958 if (freesize>=DIFFERENTSIZES) {
959 bigmemarea *m = (bigmemarea*) (heap+freestart);
960 m -> next = bigmemlist;
961 m -> size = freesize;
965 if (freesize*BLOCKSIZE>=sizeof(memarea)) {
966 memarea *m = (memarea*) (heap+freestart);
967 m -> next = memlist[freesize];
968 memlist[freesize] = m;
969 setbit (memlistbits, freesize);
975 /************** Funktion: memlist_getsuitable *********************************
977 sucht in der Freispeicherliste einen Speicherbereich, der m"oglichst
978 genau die gew"unschte L"ange hat.
979 Der Bereich wird dabei auf jeden Fall aus der Liste ausgetragen.
980 (Wenn der Bereich zu lang sein sollte, dann kann der Aufrufer den
981 Rest wieder mit 'memlist_addrange' in die Liste einh"angen)
983 Return (in Referenzparametern):
984 *freestart: Anfang des freien Speichers
985 *freelength: L"ange dieses Speicherbereiches
987 Wenn kein passender Speicherblock mehr gefunden werden kann, dann
988 wird in '*freelength' 0 hineingeschrieben.
990 ******************************************************************************/
992 static void memlist_getsuitable (u4 *freestart, u4 *freelength, u4 length)
995 bigmemarea *prevm = NULL;
997 if (length<DIFFERENTSIZES) {
1000 if (memlist[length]) {
1001 firstfreelength = length;
1004 firstfreelength = findnextsetbit
1005 (memlistbits, DIFFERENTSIZES, length+3);
1006 /* wenn kein passender Block da ist, dann gleich nach */
1007 /* einem etwas gr"osseren suchen, damit keine kleinen */
1008 /* St"uckchen "ubrigbleiben */
1011 if (firstfreelength<DIFFERENTSIZES) {
1012 memarea *m = memlist[firstfreelength];
1013 memlist[firstfreelength] = m->next;
1014 if (!m->next) clearbit (memlistbits, firstfreelength);
1015 *freestart = ((heapblock*) m) - heap;
1016 *freelength = firstfreelength;
1023 if (m->size >= length) {
1024 if (prevm) prevm->next = m->next;
1025 else bigmemlist = m->next;
1027 *freestart = ((heapblock*) m) - heap;
1028 *freelength = m->size;
1043 /******************* Funktion: mark *******************************************
1045 Markiert ein m"oglicherweise g"ultiges Objekt.
1046 Sollte sich herausstellen, dass der Zeiger gar nicht auf ein Objekt
1047 am Heap zeigt, dann wird eben gar nichts markiert.
1049 ******************************************************************************/
1051 static void markreferences (void **rstart, void **rend);
1053 static void mark (heapblock *obj)
1055 u4 blocknum,objectend;
1057 if ((long) obj & (BLOCKSIZE-1)) return;
1059 if (obj<heap) return;
1060 if (obj>=(heap+topofheap) ) return;
1062 blocknum = obj-heap;
1063 if ( isbitclear(startbits, blocknum) ) return;
1064 if ( isbitset(markbits, blocknum) ) return;
1066 setbit (markbits, blocknum);
1068 if ( isbitclear(referencebits, blocknum) ) return;
1070 objectend = findnextsetbit (startbits, topofheap, blocknum+1);
1071 markreferences ((void**)obj, (void**) (heap+objectend) );
1075 /******************** Funktion: markreferences ********************************
1077 Geht einen Speicherbereich durch, und markiert alle Objekte, auf
1078 die von diesem Bereich aus irgendeine Referenz existiert.
1080 ******************************************************************************/
1082 static void markreferences (void **rstart, void **rend)
1086 for (ptr=rstart; ptr<rend; ptr++) mark (*ptr);
1090 /******************* Funktion: markstack **************************************
1092 Marks all objects that are referenced by the (C-)stacks of
1095 (The stack-bottom is to be specified in the call to heap_init).
1097 ******************************************************************************/
1099 static void markstack () /* schani */
1106 if (currentThread == NULL) {
1107 void **top_of_stack = &dummy;
1109 if (top_of_stack > bottom_of_stack)
1110 markreferences(bottom_of_stack, top_of_stack);
1112 markreferences(top_of_stack, bottom_of_stack);
1115 for (aThread = liveThreads; aThread != 0;
1116 aThread = CONTEXT(aThread).nextlive) {
1117 mark((heapblock*)aThread);
1118 if (aThread == currentThread) {
1119 void **top_of_stack = &dummy;
1121 if (top_of_stack > (void**)CONTEXT(aThread).stackEnd)
1122 markreferences((void**)CONTEXT(aThread).stackEnd, top_of_stack);
1124 markreferences(top_of_stack, (void**)CONTEXT(aThread).stackEnd);
1127 if (CONTEXT(aThread).usedStackTop > CONTEXT(aThread).stackEnd)
1128 markreferences((void**)CONTEXT(aThread).stackEnd,
1129 (void**)CONTEXT(aThread).usedStackTop);
1131 markreferences((void**)CONTEXT(aThread).usedStackTop,
1132 (void**)CONTEXT(aThread).stackEnd);
1136 markreferences((void**)&threadQhead[0],
1137 (void**)&threadQhead[MAX_THREAD_PRIO]);
1140 void **top_of_stack = &dummy;
1142 if (top_of_stack > bottom_of_stack)
1143 markreferences(bottom_of_stack, top_of_stack);
1145 markreferences(top_of_stack, bottom_of_stack);
1151 /**************** Funktion: searchlivefinalizees *****************************
1153 geht die Liste aller Objekte durch, die noch finalisiert werden m"ussen
1154 (livefinalizees), und tr"agt alle nicht mehr markierten in die
1155 Liste deadfinalizess ein (allerdings werden sie vorher noch als
1156 erreicht markiert, damit sie nicht jetzt gleich gel"oscht werden).
1158 *****************************************************************************/
1160 static void searchlivefinalizees ()
1162 finalizernode *fn = livefinalizees;
1163 finalizernode *lastlive = NULL;
1167 /* alle zu finalisierenden Objekte, die nicht mehr markiert sind: */
1168 if (isbitclear (markbits, fn->objstart)) {
1169 finalizernode *nextfn = fn->next;
1171 mark (heap + fn->objstart);
1173 if (lastlive) lastlive -> next = nextfn;
1174 else livefinalizees = nextfn;
1176 fn -> next = deadfinalizees;
1177 deadfinalizees = fn;
1190 /********************** Funktion: finalizedead *******************************
1192 ruft die 'finalize'-Methode aller Objekte in der 'deadfinalizees'-
1194 Achtung: Es kann hier eventuell zu neuerlichen Speicheranforderungen
1195 (mit potentiell notwendigem GC) kommen, deshalb m"ussen manche
1196 globalen Variablen in lokale Variblen kopiert werden
1197 (Reentrant-F"ahigkeit!!!)
1199 ******************************************************************************/
1201 static void finalizedead()
1203 finalizernode *fn = deadfinalizees;
1204 deadfinalizees = NULL;
1207 finalizernode *nextfn = fn->next;
1209 asm_calljavamethod (fn->finalizer, heap+fn->objstart, NULL,NULL,NULL);
1210 FREE (fn, finalizernode);
1219 /****************** Funktion: heap_docollect **********************************
1221 F"uhrt eine vollst"andige Garbage Collection durch
1223 ******************************************************************************/
1225 static void heap_docollect ()
1227 u4 freestart,freeend;
1229 bitfieldtype *dummy;
1235 fprintf(stderr, "doing garbage collection\n");
1237 /* alle Markierungsbits l"oschen */
1238 clearbitfield (markbits, topofheap);
1240 /* Alle vom Stack referenzierten Objekte markieren */
1241 asm_dumpregistersandcall (markstack);
1243 /* Alle von globalen Variablen erreichbaren Objekte markieren */
1244 p = chain_first (allglobalreferences);
1247 p = chain_next (allglobalreferences);
1250 /* alle Objekte durchsehen, die eine finalizer-Methode haben */
1251 searchlivefinalizees();
1253 /* alle Reference-Bits l"oschen, deren Objekte nicht */
1254 /* mehr erreichbar sind */
1255 maskfieldwithfield (referencebits, markbits, topofheap);
1258 /* Freispeicherliste initialisieren */
1262 /* Heap schrittweise durchgehen, und alle freien Bl"ocke merken */
1267 /* Anfang des n"achsten freien Bereiches suchen */
1268 freestart = findnextcombination_set_unset
1269 (startbits, markbits, topofheap, freeend);
1271 /* Wenn es keinen freien Bereich mehr gibt -> fertig */
1272 if (freestart>=topofheap) goto freememfinished;
1274 /* Anfang des freien Bereiches markieren */
1275 setbit (markbits, freestart);
1277 /* Ende des freien Bereiches suchen */
1278 freeend = findnextsetbit (markbits, topofheap, freestart+1);
1280 /* Freien Bereich in Freispeicherliste einh"angen */
1281 memlist_addrange (freestart, freeend-freestart);
1283 /* Menge des freien Speichers mitnotieren */
1284 heapfreemem += (freeend-freestart);
1289 /* Die Rollen von markbits und startbits vertauschen */
1291 markbits = startbits;
1295 /* Threashold-Wert f"ur n"achstes Collect */
1296 oldfillgrade = heapfillgrade;
1297 heapfillgrade = topofheap - heapfreemem;
1298 collectthreashold = heapfillgrade*3; /* eine nette Heuristik */
1300 /* Eventuell eine Meldung ausgeben */
1301 if (collectverbose) {
1302 sprintf (logtext, "Garbage Collection: previous/now = %d / %d ",
1303 (int) (oldfillgrade * BLOCKSIZE),
1304 (int) (heapfillgrade * BLOCKSIZE) );
1310 /* alle gerade unerreichbar gewordenen Objekte mit
1311 finalize-Methoden jetzt finalisieren.
1312 Achtung: Diese Funktion kann zu neuerlichem GC f"uhren!! */
1317 /************************* Function: gc_init **********************************
1319 Initializes anything that must be initialized to call the gc on the right
1322 ******************************************************************************/
1329 /************************** Function: gc_call ********************************
1331 Calls the garbage collector. The garbage collector should always be called
1332 using this function since it ensures that enough stack space is available.
1334 ******************************************************************************/
1340 assert(blockInts == 0);
1344 if (currentThread == NULL || currentThread == mainThread)
1347 asm_switchstackandcall(CONTEXT(mainThread).usedStackTop, heap_docollect);
1352 /************************* Funktion: heap_init ********************************
1354 Initialisiert den Garbage Collector.
1356 heapbytesize: Maximale Gr"osse des Heap (in Bytes)
1357 heapbytestartsize: Gr"osse des Heaps, bei dem zum ersten mal eine
1358 GC durchgef"uhrt werden soll.
1359 stackbottom: Ein Zeiger auf die Untergrenze des Stacks, im dem
1360 Referenzen auf Objekte stehen k"onnen.
1362 ******************************************************************************/
1364 void heap_init (u4 heapbytesize, u4 heapbytestartsize, void **stackbottom)
1367 #ifdef TRACECALLARGS
1369 heapsize = ALIGN (heapbytesize, getpagesize());
1370 heapsize = heapsize/BLOCKSIZE;
1371 heap = (void*) mmap ((void*) 0x10000000, (size_t) (heapsize * BLOCKSIZE),
1372 PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS | MAP_FIXED, -1, (off_t) 0);
1373 if (heap != (void *) 0x10000000) {
1375 printf("address = %p\n", heap);
1376 panic("mmap failed\n");
1381 heapsize = ALIGN (heapbytesize, 1024);
1382 heapsize = heapsize/BLOCKSIZE;
1383 heap = MNEW (heapblock, heapsize);
1388 startbits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
1389 markbits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
1390 referencebits = MNEW (bitfieldtype, heapsize/BITFIELDBITS);
1391 clearbitfield (startbits, heapsize);
1392 clearbitfield (markbits, heapsize);
1393 clearbitfield (referencebits, heapsize);
1396 collectthreashold = heapbytestartsize/BLOCKSIZE;
1397 allglobalreferences = chain_new ();
1398 bottom_of_stack = stackbottom;
1400 livefinalizees = NULL;
1401 deadfinalizees = NULL;
1405 /****************** Funktion: heap_close **************************************
1407 Gibt allen ben"otigten Speicher frei
1409 ******************************************************************************/
1413 #ifndef TRACECALLARGS
1414 MFREE (heap, heapblock, heapsize); */
1416 MFREE (startbits, bitfieldtype, heapsize/BITFIELDBITS);
1417 MFREE (markbits, bitfieldtype, heapsize/BITFIELDBITS);
1418 MFREE (referencebits, bitfieldtype, heapsize/BITFIELDBITS);
1419 chain_free (allglobalreferences);
1421 while (livefinalizees) {
1422 finalizernode *n = livefinalizees->next;
1423 FREE (livefinalizees, finalizernode);
1429 /***************** Funktion: heap_addreference ********************************
1431 Teilt dem GC eine Speicherstelle mit, an der eine globale Referenz
1432 auf Objekte gespeichert sein kann.
1434 ******************************************************************************/
1436 void heap_addreference (void **reflocation)
1438 intsDisable(); /* schani */
1440 chain_addlast (allglobalreferences, reflocation);
1442 intsRestore(); /* schani */
1447 /***************** Funktion: heap_allocate ************************************
1449 Fordert einen Speicher vom Heap an, der eine gew"unschte Gr"osse
1450 (in Byte angegeben) haben muss.
1451 Wenn kein Speicher mehr vorhanden ist (auch nicht nach einem
1452 Garbage Collection-Durchlauf), dann wird NULL zur"uckgegeben.
1453 Zus"atzlich wird durch den Parameter 'references' angegeben, ob
1454 in das angelegte Objekt Referenzen auf andere Objekte eingetragen
1456 (Wichtig wegen Beschleunigung des Mark&Sweep-Durchlauf)
1457 Im Zweifelsfalle immer references=true verwenden.
1459 ******************************************************************************/
1461 void *heap_allocate (u4 bytelength, bool references, methodinfo *finalizer)
1463 u4 freestart,freelength;
1464 u4 length = ALIGN(bytelength, BLOCKSIZE) / BLOCKSIZE;
1466 intsDisable(); /* schani */
1468 memlist_getsuitable (&freestart, &freelength, length);
1472 if ( (topofheap+length > collectthreashold)
1473 || (topofheap+length > heapsize) ) {
1479 memlist_getsuitable (&freestart, &freelength, length);
1480 if (freelength) goto onemoretry;
1483 if (topofheap+length > heapsize) {
1484 sprintf (logtext, "Heap-Allocation failed for %d bytes",
1487 intsRestore(); /* schani */
1491 freestart = topofheap;
1492 freelength = length;
1493 setbit (startbits, topofheap);
1494 topofheap += length;
1497 if (freelength>length) {
1498 setbit (startbits, freestart+length);
1499 memlist_addrange (freestart+length, freelength-length);
1503 if (references) setbit (referencebits, freestart);
1505 heapfillgrade += length;
1508 finalizernode *n = NEW(finalizernode);
1509 n -> next = livefinalizees;
1510 n -> objstart = freestart;
1511 n -> finalizer = finalizer;
1515 intsRestore(); /* schani */
1518 sprintf (logtext, "new returns: %lx", (long) (heap + freestart));
1522 return (void*) (heap + freestart);