Speicherverwaltung in GFA-BASIC
Irgendwann kam mir der Gedanke, selbst einen Texteditor zu schreiben. Bei meinen Vorbetrachtungen kam ich zu dem Schluss, den Text in verzeigerte und gegen Systemzugriffe geschützte Speicherblöcke zu schreiben.
Normalerweise alloziert man Speicher mittels Malloc (GEMDOS-Funktion 72). Die TOS-Version 1.0 vom 6.2.86 gestattet aber nur ca. 280 bis 290 solcher Aufrufe (TOS-Version 1.2 vom 22.4.87 ca. 800 Aufrufe). Dies genügt für einen Texteditor auf keinen Fall, so daß ich selbst gefordert war, eine Speicherverwaltung zu implementieren.
Die Aufgaben einer Speicherverwaltung sind schnell Umrissen. Auf Anforderung soll möglichst schnell ein passender Speicherblock gefunden werden, und, falls nicht vorhanden, ein größerer Block aufgespalten werden.
Bei der Rückgabe von Blöcken sollen benachbarte Speicherblöcke möglichst schnell zu einem Großen zusammengelegt werden.
Hier kam mir ein Artikel von Peter Sollich zur Hilfe, der ausführlich das Prinzip einer Speicherverwaltung behandelte. Um schnell einen der Anforderung entsprechenden Speicherblock zu finden, sortiert und verzeigert man die freien Speicher der Größe nach. Hier spricht man von der Root. Treten mehrere Blöcke mit gleicher Größe auf, so wird einer in die Root eingehängt, alle weitern enthalten nur noch Zeiger auf einen gleichgroßen. Auf der Root liegende Speicher enthalten drei Zeiger, die je vier Byte beanspruchen, plus vier Byte für den Größeneintrag. Daraus ergibt sich, daß jeder freie Block mindestens 16 Byte groß sein muß. Die verzeigerten Freispeicher nennt man Freelist. Zur Verschmelzung von benachbarten Blöcken wird eine Bitmap angelegt, in der jedes Bit 16 Byte freien Speicher repräsentiert. Die Bitmap gibt einen Überblick über den Speicher, der verwaltet wird. Jedes gesetzte Bit repräsentiert 16 Byte freien Speicher, jedes nicht gesetzte Bit 16 Byte reservierten Speicher. Bei der Prüfung auf benachbarte Blöcke muß also nur das rechte und linke Bit neben dem zurückgegebenen Block untersucht werden.
Bei der Installation der Verwaltung werden neben der Bitmap noch drei Speicherblöcke angelegt. Ein Block, der die Größe 0 repräsentiert, und ein weiterer für die Größe unendlich. Zwischen diese beiden, nennen wir sie größter und kleinster, wird nun der dritte Block eingehängt, der eigentliche freie Speicher. In der Bitmap werden die Bits für größter und kleinster gelöscht, also als reserviert markiert. Zudem wird das letzte Bit in der Bitmap auf Null gesetzt, um ein Überschreiben der Bitmap zu verhindern. Alle anderen Bits werden gesetzt.
Nun zu den Zeigern (Bild 1): Jeder Speicherblock enthält in den ersten vier Bytes seine Größe. Liegt ein freier Speicherblock auf der Root, so enthält er in Byte fünf bis acht die Startadresse des nächstgrößeren, in Byte neun bis zwölf einen Zeiger auf den nächstkleineren und schließlich in Byte dreizehn bis sechzehn die Adresse des nächsten gleichgroßen. Sollte kein gleicher Block vorhanden sein, so steht hier FALSE. Speicherblöcke, die nicht auf der Root liegen, enthalten nur den Zeiger auf den nächsten gleichen.
Zudem enthalten Blöcke, deren Größe 16 Bytes überschreiten, in den letzten vier Bytes ihre eigene Startadresse. Dieser zusätzliche Zeiger wird zur schnellen Zusammenlegung mit evtl. vorhandenen linken Nachbarn benötigt. Bei links gelegenen Nachbarn müßte in der Bitmap sonst jedes Bit, das links neben dem zurückgegebenen Block liegt, getestet werden, bis auf ein nicht gesetztes Bit getroffen wird. Aus dessen Position in der Bitmap könnte man dann die Startadresse des Nachbarn errechnen. Bei einer Speicherblockgröße von 16 kByte müßten immerhin 1000 Bits getestet werden. Soviel zum Prinzip dieser Speicherverwaltung, nun zur Implementierung in GFA-BASIC.
back%=FN speicher_inst(bytes%)
Wird hier -1 übergeben, so erhalten Sie als Rückgabe, wieviele Bytes maximal als Freispeicher installiert werden können. Ist der Übergabeparameter größer Null, wird die Verwaltung installiert. Bei korrekter Ausführung erhalten Sie TRUE, tritt ein Fehler auf, FALSE.
Zur Funktion selbst: In Zeile fünf wird getestet, wieviel Speicher alloziert werden kann (bei Übergabe-Parameter -1). Danach errechnet das Programm, wieviel Bytes für die Bitmap benötigt werden (allozierbarer Speicher geteilt durch 128). Das Teilen erfolgt durch Verschieben der Bits, was etwas schneller ist als dividieren. Zudem wird der Nachkommateil vernachlässigt, weil nur ganze Bytes in die Bitmap aufgenommen werden. Daraus ergibt sich, daß nur Größen, die ein Vielfaches von 128 sind, installiert werden. In Zeile sieben wird die Bitmap-Größe vom allozierbaren Speicher subtrahiert und in Zeile acht die Rückgabe errechnet. Bitmap-Größe mal 128 ergibt den maximal verwaltbaren Speicher. Davon werden je 16 Byte für größter und kleinster abgezogen. Weitere 16 Bytes werden benötigt, um das letzte Bit der Bitmap auf Null zu setzen. Wie schon erwähnt, schützt dies die Bitmap vor dem Überschreiben. In Zeile neun erfolgt der Rücksprung.
Nun zur eigentlichen Installation. In den Zeilen 11 bis 21 wird anhand des Übergabe-Parameters der zu allozierende Speicher berechnet. Danach wird mittels GEMDOS 72 Speicher vom Betriebssystem angefordert und dessen Startadresse in malloc_adr% abgelegt. Dies ist auch die einzige globale Variable in allen fünf Funktionen. Ab Zeile 23 werden die Größen und Zeiger eingetragen und zum Schluß die nötigen Bits in der Bitmap gesetzt. Bild 2 zeigt die fertig installierte Speicherverwaltung (Übergabeparameter 208 Bytes). Bei der Installation der Speicherverwaltung ist darauf zu achten, daß dem GEM noch genügend freier Speicher zur Verfügung steht (64 Kilobyte genügen), da sonst zum Beispiel keine Fileselectbox mehr auf dem Bildschirm erscheint. Außerdem ist eine evtl, benötigte RSC-Datei vor der Installation einzuladen.
back%=FN speicher_res(bytes%)
Diese Function reserviert bei Aufruf die in bytes% angeforderte Menge Speicher und gibt dessen Startadresse zurück. Steht kein genügend großer Speicherblock zur Verfügung, wird FALSE zurückgegeben. Die beantragte Größe kann die aufrufende Anwendung in Startadresse-4 im Langwortformat auslesen.
Zum Ablauf von Speicher res: Zu Beginn wird die beantragte Speichergröße in real% zwischengespeichert. Zum Übergabeparameter werden vier aufaddiert (für Größeneintrag) und dann geprüft, ob es sich um ein Vielfaches von 16 handelt. Ist dies nicht der Fall, wird darauf erweitert. Als nächstes wird geprüft, ob der größte freie Speicher größer oder gleich bytesVc ist. Trifft dies nicht zu, so erfolgt der Rücksprung zur Anwendung. Nun wird die Größe von bytes% vom Gesamtspeicher subtrahiert (steht in malloc_adr% +5) und danach werden die Freispeicher auf der Root durchlaufen, bis ein Block gleich oder größer bytes% gefunden wird. Dieses Durchlaufen der auf der Root liegenden Freispeicher wiederholt sich in einigen Functions und wird mit einer Repeat...Until Schleife realisiert. Ausgangspunkt ist dabei immer malloc_adr% und innerhalb der Schleife wird jedesmal der Zeiger auf den nächstgrößeren abgefragt. Ist nun ein der Anforderung passender Speicherblock gefunden, wird nach vier Fällen unterschieden:
- gleichgroß der Anforderung und keinen Zeiger auf einen gleichgroßen: Der Block wird aus der Root ausgelöst und die Startadresse in back% abgelegt.
- gleichgroß der Anforderung und einen Zeiger auf einen gleichgroßen: Hier wird der nächste gleich große Block ausgelöst, da nur ein Zeiger geändert werden muß. Startadresse des ausgelösten Blocks wird wieder in back% abgelegt.
- größer als die Anforderung und keinen Zeiger auf einen gleichen: Der Block wird aus der Root ausgelöst und die Zeiger angepaßt. Vom unteren Ende des Blockes werden der Anforderung entsprechend viele Bytes abgeschnitten und die Startadresse in back% abgelegt. Der verbleibende obere Teil wird wieder in die Root eingefügt.
- größer als die Anforderung und einen Zeiger auf einen gleichen: Prinzipiell wird hier genau so verfahren wie ohne nächsten.
Nun ist ein Speicherblock gefunden, ausgelöst und dessen Startadresse in back% abgelegt. Es muß also nur noch die Bitmap angepaßt werden. Anhand der Speicherblockgröße geteilt durch 16 wird errechnet, wieviele Bits zu löschen sind. Danach wird das Startbit errechnet, und daraus, im wievielten Byte der Bitmap mit der Löschaktion begonnen wird. Nun braucht man noch die Bit-Nummer und schon kann's losgehen. Um bei größeren Speicherblöcken eine höhere Geschwindigkeit zu erreichen, wird immer ein ganzes Byte auf Null gesetzt, falls dies möglich ist. Zum Schluß wird noch die beantragte Speicherblockgröße in die Startadresse geschrieben. Vor dem Rücksprung wird die Startadresse noch um vier erhöht, so daß die Größe in Startadresse minus vier steht und die Anwendung ab Startadresse mit dem Speicherblock tun und lassen kann, was sie will.
back%=FN speicher_frei(adr%)
Mittels speicher_frei kann schon beantragter Speicher wieder an die Verwaltung zurückgegeben werden. Übergabeparameter ist die Startadresse des als frei zu markierenden Speicherblockes. Als Rückgabe erhalten sie TRUE, tritt ein Fehler auf, FALSE.
Nun zum Ablauf: In den ersten 20 Zeilen wird auf eventuell vorhandene Fehler geprüft und die Größe wieder auf ein Vielfaches von 16 angepaßt. Danach wird errechnet, wieviele Bits in der Bitmap als frei markiert werden müssen und welches Bit die Startadresse der Rückgabe repräsentiert. Zugleich wird noch das Bit errechnet, das die Startadresse eines eventuell vorhandenen rechten Nachbarn repräsentiert, ebenfalls das letzte Bit des linken Nachbarn. Daraufhin wird die Rückgabe in der Bitmap als frei markiert. Nun erfolgt der Test auf einen rechten Nachbarn. Ist dieser vorhanden, so wird er aus der Freelist ausgetragen und dessen Größe zur Rückgabe addiert. Jetzt erfolgt der Test auf den linken Nachbarn. Für den Fall, daß ein linker Nachbar vorhanden ist, also das Bit links neben der Rückgabe gesetzt ist, wird zusätzlich ein Bit weiter links getestet. Ist dieses gesetzt, steht die Startadresse des linken Nachbarn in dessen letzten vier Bytes, ansonsten ist die Startadresse Rückgabeadresse minus 16. Auch dieser Block wird ausgelöst und zu dessen Größe die Rückgabegröße (die bereits um rechten Nachbarn erhöht ist) addiert. Nun braucht nur noch der ganze Block in die Freelist eingetragen werden.
back!= FN speicher_shrink(adr%,ngrs%)
Mit dieser Funktion können Sie reservierten Speicher einschränken. Als Übergabeparameter werden die Startadresse des Speicherblocks und die neue gewünschte Größe gefordert. Als Rückgabe erhalten Sie wieder TRUE und. falls ein Fehler auftritt. FALSE. Diese Function schneidet lediglich am unteren Ende des Speicherblocks die nicht mehr benötigten Bytes ab und gibt sie mittels FN speicher_frei an die Verwaltung zurück.
back%=FN Speicher kill(modus|)
Mit speicher_kill können Sie mit Übergabeparameter 0 die Speicherverwaltung abmelden, was bedeutet, daß der in speicher_inst allozierte Speicher ans Betriebssystem zurückgeben wird. Als Rückgabe erhalten Sie Null, wenn kein Fehler auftritt. Bei Übergabe von eins erhalten Sie als Rückgabe die Größe des Freispeichers, bei Übergabeparameter zwei die Größe des größten zusammenhängenden Freispeichers.
' (c) MAXON Computer GmbH
FUNCTION speicher_frei(adr%)
LOCAL back!,bitz%,startbit%,ltest%,rtest%, sbyte%
LOCAL bitnr&,bitm%,radr%,ladr%,suchadr% , startadr%
LOCAL bytes%,startbyte2%,ltest2%,bitnr2&
SUB adr%,4
bitm%={malloc_adr%+12}
IF adr%<malloc_adr%+32 OR ODD(adr%)
back!=FALSE
RETURN back!
ENDIF
bytes%={adr%}
ADD bytes%,4
IF ROL(SHR(bytes%,4),4)<bytes%
bytes%=ROL(SHR(bytes%,4),4)+16
ENDIF
IF adr%+bytes%>bitm%-15
back!=FALSE
RETURN back!
ENDIF
{adr%}=bytes%
{malloc_adr%+8}={malloc_adr%+8}+{adr%)
bitz%=SHR({adr%},4)
startbit%=SHR(adr%-malloc_adr%,4)+1
ltest%=startbit%-1
ltest2%=startbit%-2
rtest%=SHR(adr%+{adr%}-malloc_adr%,4)+1
sbyte%=SHR(startbit%, 3)
IF ROL(SHR(startbit%,3),3)<startbit%
INC sbyte%
ENDIF
bitnr&=ROL(sbyte%,3)-startbit%
DEC sbyte%
REPEAT
IF bitz%>7 AND bitnr&=7
BYTE{bitm%+sbyte%}=255
SUB bitz%,8
INC sbyte%
ELSE
BYTE{bitm%+sbyte%}=BSET(BYTE{bitm%+sbyte%},bitnr&)
DEC bitz%
DEC bitnr&
IF bitnr&=-1
INC sbyte%
bitnr&=7
ENDIF
ENDIF
UNTIL bitz%=0
sbyte%=SHR(rtest%,3)
IF ROL(SHR(rtest%,3),3)<rtest%
INC sbyte%
ENDIF
bitnr&=ROL(sbyte%,3)-rtest%
DEC sbyte%
IF BTST(BYTE{bitm%+sbyte%},bitnr&)
radr%=malloc_adr%+ROL(rtest%-1,4)
{adr%}={adr%}+{radr%}
startadr%=malloc_adr%
REPEAT
startadr%={startadr%+4}
UNTIL {startadr%}={radr%}
IF startadr%=radr%
IF {radr%+12}=FALSE
{{radr%+8}+4}={radr%+4}
{{radr%+4}+8}={radr%+8}
ELSE
{{radr%+8}+4}={radr%+12}
{{radr%+4}+8}={radr%+12}
BMOVE radr%+4,{radr%+12}+4,8
ENDIF
ELSE
DO
EXIT IF {startadr%+12}=radr%
startadr%={startadr%+12}
LOOP
{startadr%+12}={radr%+12}
ENDIF
ENDIF
sbyte%=SHR(ltest%,3)
IF ROL(SHR(ltest%,3),3)<ltest%
INC sbyte%
ENDIF
bitnr&=ROL(sbyte%,3)-ltest%
DEC sbyte%
IF BTST(BYTE{bitm%+sbyte%},bitnr&)
startbyte2%=SHR(ltest2%,3)
IF ROL(SHR(ltest2%,3),3)<ltest2%
INC startbyte2%
ENDIF
bitnr2&=ROL(startbyte2%,3)-ltest2%
DEC startbyte2%
IF BTST(BYTE{bitm%+startbyte2%},bitnr2&)
ladr%={adr%-4}
ELSE
ladr%=adr%-16
ENDIF
startadr%=malloc_adr%
REPEAT
startadr%={startadr%+4}
UNTIL {startadr%}={ladr%}
IF startadr%=ladr%
IF {ladr%+12}=FALSE
{{ladr%+8}+4}={ladr%+4}
{{ladr%+4}+8}={ladr%+8}
ELSE
{{ladr%+8}+4}={ladr%+12}
{{ladr%+4}+8}={ladr%+12}
BMOVE ladr%+4,{ladr%+12}+4,8
ENDIF
ELSE
DO
EXIT IF {startadr%+12}=ladr%
startadr%={startadr%+12}
LOOP
{startadr%+12}={ladr%+12}
ENDIF
{ladr%}={ladr%}+{adr%}
adr%=ladr%
ENDIF
IF {adr%}>16
{{adr%}+adr%-4}=adr%
ENDIF
suchadr%=malloc_adr%
REPEAT
suchadr%={suchadr%+4}
UNTIL {suchadr%}=>{adr%}
IF {suchadr%}={adr%}
{adr%+12}={suchadr%+12}
{suchadr%+12}=adr%
ELSE
{adr%+4}=suchadr%
{adr%+8}={suchadr%+8}
{adr%+12}=FALSE
{{adr%+8}+4}=adr%
{{adr%+4}+8}=adr%
ENDIF
back!=TRUE
RETURN back!
ENDFUNC
Listing 1: Speicher freigeben
' (c) MAXON Computer GmbH
FUNCTION speicher_res(bytes%)
LOCAL real%,back%,adr%,such_adr%,flag!
LOCAL bitz%,startbit%,sbyte%,bitm%,bitnr&
real%=bytes%
ADD bytes%,4
IF ROL(SHR(bytes%,4),4)<bytes%
bytes%=ROL(SHR(bytes%,4),4)+16
ENDIF
IF {(malloc_adr%+24}}<bytes%
back%=FALSE
RETURN back%
ENDIF
{malloc_adr%+8}={malloc_adr%+8}-bytes%
adr%=malloc_adr%
REPEAT
adr%={adr%+4}
UNTIL {adr%}=>bytes%
IF {adr%}=bytes% AND {adr%+12}=FALSE
{{adr%+8}+4}={adr%+4}
{{adr%+4}+8}={adr%+8}
back%=adr%
ELSE IF {adr%}=bytes% AND {adr%+12}<>FALSE
back%={adr%+12}
{adr%+12}={back%+12}
ELSE IF {adr%}>bytes% AND (adr%+12}=FALSE
{{adr%+8}+4}={adr%+4}
{{adr%+4}+8}={adr%+8}
flag!=TRUE
ELSE IF {adr%}>bytes% AND {adr%+12}<>FALSE
{{adr%+8}+4}={adr%+12}
{{adr%+4}+8}={adr%+12}
BMOVE adr%+4,{adr%+12}+4,8
flag!=TRUE
ENDIF
IF flag!
{adr%}={adr%}-bytes%
back%=adr%+{adr%}
IF {adr%}>16
{back%-4}=adr%
ENDIF
such_adr%=malloc_adr%
flag!=FALSE
REPEAT
such_adr%={such_adr%+4}
IF {such_adr%}={adr%}
{adr%+12}={such_adr%+12}
{such_adr%+12}=adr%
flag!=TRUE
ELSE IF {such_adr%}>{adr%}
{adr%+8}={such_adr%+8}
{adr%+4}=such_adr%
{adr%+12}=FALSE
{such_adr%+8}=adr%
{{adr%+8}+4}=adr%
flag!=TRUE
ENDIF
UNTIL flag!
ENDIF
bitz%=SHR(bytes%,4)
startbit%=SHR(back%-malloc_adr%,4)+1
sbyte%=SHR(startbit%,3)
IF ROL(SHR(startbit%,3),3)<startbit%
INC sbyte%
ENDIF
bitnr&=ROL(sbyte%,3)-startbit%
bitm%={malloc_adr%+12}
DEC sbyte%
REPEAT
IF bitz%>7 AND bitnr&=7
BYTE{bitm%+sbyte%}=0
SUB bitz%,8
INC sbyte%
ELSE
BYTE{bitm%+sbyte%}=BCLR(BYTE{bitm%+sbyte%},bitnr&)
DEC bitz%
DEC bitnr&
IF bitnr&=-1
INC sbyte%
bitnr&=7
ENDIF
ENDIF
UNTIL bitz%=0
{back%}=real%
ADD back%,4
RETURN back%
ENDFUNC
Listing 2: Speicher reservieren
' (c) MAXON Computer GmbH
FUNCTION speicher_inst(bytes%)
LOCAL bitm_gr%,spei_gr%,malloc_gr%,back%
LOCAL offset%,bitm_adr%
IF bytes%=-1
malloc_gr%=MALLOC(-1)
bitm_gr%=SHR(malloc_gr%,7)
SUB malloc_gr%,bitra_gr%
back%=ROL(SHR(malloc_gr%,7),7)-48
RETURN back%
ENDIF
ADD bytes%,48
bitm_gr%=SHR(bytes%, 7)
IF ROL(SHR(bytes%,7),7)<bytes%
INC bitm_gr%
ENDIF
spei_gr%=ROL(bitm_gr%,7)
malloc_gr%=spei_gr%+bitm gr%
IF MALLOC(-1)<malloc_gr% OR bitm_gr%<2
back%=FALSE
RETURN back%
ENDIF
malloc_adr%=MALLOC(malloc_gr%)
{malloc_adr%}=0
{malloc_adr%+16}=spei_gr%-16
{malloc_adr%+12}=malloc_adr%+spei_gr%
{malloc_adr%+32}=spei_gr%-48
{malloc_adr%+8}=spei_gr%-48
{malloc_adr%+4}=malloc_adr%+32
{malloc_adr%+24}=malloc_adr%+32
{malloc_adr%+36}=malloc_adr%+16
{malloc_adr%+40}=malloc_adr%
{malloc_adr%+44}=FALSE
bitm_adr%={malloc_adr%+12}
REPEAT
IF bitm_gr%>3
{bitm_adr%+offset%}=-1
SUB bitm_gr%,4
ADD offset%,4
ELSE
BYTE{bitm_adr%+offset%}=255
DEC bitm_gr%
INC offset%
ENDIF
UNTIL bitm_gr%=0
BYTE{bitm_adr%}=63
BYTE{bitm_adr%+offset%-1}=254
back%=TRUE
RETURN back%
ENDFUNC
Listing 3: Speicher installieren
' (c) MAXON Computer GmbH
FUNCTION speicher_kill(modus|)
LOCAL back%
SELECT modus|
CASE 0
' Speicherverwaltung abmelden
back%=MFREE(malloc_adr%)
CASE 1
' ges. Freispeicher
back%={malloc_adr%+8}
CASE 2
' größter Speicherblock
back%={{malloc_adr%+24}}
ENDSELECT
RETURN back%
ENDFUNC
Listing 4: Speicher freigeben
' (c) MAXON Computer GmbH
FUNCTION speicher_shrink(adr%,ngrs%)
LOCAL agrs%,frei%,backadr%,back!,rgr%,real%
back!=FALSE
SUB adr%,4
real%=ngrs%
IF adr%<malloc_adr%+32 OR ODD(adr%)
RETURN back!
ENDIF
agrs%={adr%}
rgr%=agrs%+4
IF ROL(SHR(rgr%,4),4)<rgr%
rgr%=ROL(SHR(rgr%,4),4)+16
ENDIF
IF agrs%<ngrs% OR adr%+rgr%=>{malloc_adr%+12}-15
RETURN back!
ENDIF
ADD ngrs%, 4
IF ROL(SHR(ngrs%,4),4)<ngrs%
ngrs%=ROL(SHR(ngrs%,4),4)+16
ENDIF
frei%=rgr%-ngrs%
back!=TRUE
IF frei%>0
backadr%=adr%+ngrs%
{backadr%}=frei%-4
ADD backadr%,4
back!=FN speicher_frei(backadr%)
IF back!
{adr%}=real%
ENDIF
ENDIF
RETURN back!
ENDFUNC
Listing 5: Teil des reservierten Speichers zurückgeben
Manfred Müller