[Alg] garbage collection: references (ptr-to-ptr)

[Zoijar]

Ik heb voor een java-like taal een compiler met two-space garbage collection geimplementeerd. Heel kort: Een object wordt gerepresenteerd als pointer naar een struct op de heap. Alle addressen van pointers in het programma (stack) worden opgeslagen in een root set. Bij garbage collection worden al deze rootset pointers recursief gevolgd, en mogelijk wordt het struct naar een andere heap locatie gekopieerd en word de programma pointer aangepast. Dit werkt goed, en is standaard two-space garabage collection.

Nu heb ik ook functies die call-by-reference argumenten kunnen hebben. Net zoals zeg maar een reference in C++ (bv. void foo(vector& v);) Het probleem zit hem erin dat die references pointers naar pointers naar heap structs zijn. Mocht het nu zo zijn dat de reference wijst naar een object in een object op de heap, dan lukt het garbage collecten niet. Dit omdat als het object verplaatst wordt, de dubbele pointer geen juist address meer heeft.

Voorbeeld:

code:

class A is
   var q: A;
end

procedure foo(var aref : A) is begin
(* hier wordt er garbage collected en wordt aref invalid *)
aref.blaat(); (* crash, inhoud aref is null-pointer *)
end

a:= new A;
a.q := new A;

foo(a.q); (* pass-by-ref *)

Waarbij het argument 'aref' van foo als reference wordt gepassed (vandaar de 'var' ervoor)

Nu is mijn vraag uiteraard of iemand een (idee voor) oplossing heeft voor dit. Sorry dat ik het niet beter it kan leggen, maar dat zou meerdere blz tekst kosten...en ik verwacht niet dat iemand daar doorheen gaat lezen. Ik hoopte dat iemand misschien ooit is garabge collection heeft geimplementeerd en tegen dit probleem is aangelopen, over zich herinnerd er iets over gelezen te hebben.

[.oisyn]

ik snap je uitleg niet helemaal, maar kun je je reference object (dus wat altijd op de stack staat) niet uitbreiden met een attribuut wat aangeeft of het object waar ie naar wijst op de heap of op de stack staat, zodat je garbage collector daar rekening mee kan houden?

[tomato]

Ik begrijp je vraag ook niet helemaal (maar dat ligt vast niet aan je uitleg ), maar beschrijft dit niet kort wat je bedoelt?

Recall that an object may be reachable through multiple references, so gc_process_pointer_address must be careful not to copy the same object twice. This can be achieved by leaving a forwarding pointer in the header of the from-space version of an object after it has been copied to to-space. If this pointer is nonzero, gc_process_pointer_address knows that the object has already been moved. In that case, it must not copy the object, but it only needs to adjust the reference to the from-space object.

Het probleem dat ontstaat lijkt niet hetzelfde te zijn, maar naar mijn idee gaat het wel over two-space garbage collection met objecten die via meerdere references bereikbaar zijn.

hier (het is maar een uitleg voor een opdracht)

[Zoijar]

haha lol, ja dat is dus precies de opdracht die ik aan het doen ben voor de VU tot nu toe volle punten....

Hmmm tsja ik kan het gewoon niet uitleggen, maar kom er (nog) niet uit... wat jullie me vertelde wist ik al, op zich heb ik het ook al helemaal werkende. Het gaat dus niet om de pointers zelf, maar om de references wat pointers naar pointers zijn. Dat is een extra indirectie die niet rechtsreeks in het algorithme valt. Pointers worden dus goed aangepast, maar pointers naar [pointers op de heap] niet...het is een vrij speciaal geval, komt eigenlijk niet vaak voor, maar ik wil toch graag dat m'n code altijd werkt...hmm ok in ieder geval bedankt ik denk er nog wel even over; moet toch lukken...

[jvdmeer]

Laat ik positief beginnen ik weet niets over two-space-garbage collection. Ik heb ook geen VU ofzo gedaan.

Volgens mij (nogmaals, weet er niets van, maar kan hopelijk wel logisch denken) moet kan dit met een soort two-pass idee. En dan zit ik te denken aan 3 algoritme's:
• Je loopt eenmalig de hele stack af, en je slaat alle pointers op die naar pointers wijzen, en daarna in de tweede stap (de eigenlijke garbage-collection) zal je steeds als je een struct verplaatst alle opgeslagen pointers moeten controleren of die ook naar die struct wijzen. Zo ja, moet je de betreffende pointers ook opruimen.
• Tweede mogelijkheid is eigenlijk het omgekeerde: je voert de garbage-collection standaard uit, en na/tijdens het verplaatsen van een struct, sla je de oude en nieuwe locatie van de struct tijdelijk op. Na afloop loop je nogmaals de hele stack af, en wijzigt de pointers die naar oude locaties wijzen in de nieuwe locaties.
• Is een tragere manier en combineert beide bovenstaande eigenlijk: Tijdens de garbage-collection wordt er een struct verplaatst. Zodra dat gebeurt, ga je de hele stack aflopen en wijzigt alle pointers die ook naar die struct wijzen.

De 1e twee methodes slaan tijdens het proces data op, wat niet erg handig is. Door dit opslaan kan een mooie optimalisatie in de weg staan.

Voor mij verdient de derde methode de voorkeur, simpel te implementeren, eenvoudige werking en doeltreffend, maar waarschijnlijk niet de snelste.

[Zoijar]

Je eerste methode valt wel goed te implementeren. En volgens mij werkt het ook goed.

Denk even hardop... Als de struct waar een pointer naar wijst niet verplaatst wordt (ie. het is een garbage struct) dan is de pointer ook niet meer geldig wat hij wel zou moeten zijn. Dus een pointer naar iets binnen een struct moet er voor zorgen dat de struct zelf niet als garbage gezien wordt. Dus ik sla alle adresen van pointers op in een apparte stack, zoals bij methode 1 (die code genereer ik toch al voor objecten, dus niet veel extra werk).
Nou is het mooie van two-space gc, dat als een struct verplaatst wordt er een "forwarding pointer" achterblijft in de oude locatie die de nieuwe locatie aangeeft. Als ik dus van een pointer naar iets binnen een struct kan uitvinden wat de locatie van de struct zelf is, dan kan ik ofwel de struct kopieren als dit nog niet gedaan is, ofwel de forwarding pointer gebruiken. Hiermee kan ik via verschil tussen oude en nieuwe locatie de pointer zelf aanpassen. Ook wordt de struct nu zeker verplaatst, ofwel door normale gc, ofwel door de pointer stack uit methode 1 af te lopen. En de pointer blijft dan geldig.

Het probleem is dan nu om de locatie van de omvattende struct te vinden. Ik denk dat ik m'n compiler hier wel code voor kan laten genereren, en dan pointer te representeren als 2 velden: een object pointer, en een offset binnen het object. Of: een object pointer en het adres van de oude pointer; waar dan is inhoud(oude_ptr) - object_ptr gelijk is aan de offset binnen het object.

Waar het dan uiteindelijk op neerkomt is, de stack van twee-veld pointers aflopen. Bij elke normale gc doen op object_ptr, en vervolgens inhoud(oude_ptr) schrijven met de nieuwe locatie+offset.

Ik denk at het zo moet lukken, toch? Of zie ik iets over het hoofd? Het is ook snel, omdat er niets wordt onnodig afgescanned. Alle pointers in de stack die worden doorlopen moeten toch gedaan worden. Bedankt voor de suggesties, ze hebben het denk process in gang gezet Ik wist even niet meer waar ik moest beginnen...