Project 2

Att traversera heapen i C försvåras av att minnet som standard allokeras utan metadata. T.ex. allokerar detta anrop

void *p = malloc(sizeof(binary_tree_node));

void%20%2Ap%20%3D%20malloc%28sizeof%28binary_tree_node%29%29%3B%0A

plats som rymmer en binary_tree_node, det sparas ingen information om innehållet i detta utrymme, mer än hur stort utrymmet är som p pekar på. Vi skulle vilja “fråga” minnet vilka pekare det innehåller och hur stort det är, men det kan vi alltså inte göra. Vi måste själva implementera stöd för detta.

Rimligtvis har en binary_tree_node åtminstone två pekare till höger respektive vänster subträd – så hur gör man för att hitta dem?

Ett sätt är att leta igenom det minne som pekas ut av p och tolka varje möjlig sizeof(void *) i detta utrymme som en adress. Om adressen pekar in i den aktuella heapens adressrymd⁵ anser vi att den är en pekare till det objekt som finns lagrat där (observera att pekaren inte måste peka på starten av det objektet). Då skall vi markera detta objekt som levande (dess mark-bit sätts till 1), varefter dess utrymme också letas igenom på samma sätt som binary_tree_node:en i jakt på andra pekare in i den aktuella heapen. Om ett objekt redan markerats och traverserats behöver man inte göra det igen.

Men hur vet man då vilka pekare som finns som pekar in i heapen? För att hitta dessa, de s.k. “rotpekarna”, måste man leta igenom stacken efter pekare till heapen på samma sätt som ovan, alltså gå igenom hela stackens adressrymd, inklusive register och de statiska dataareorna och leta efter pekare in i heapens adressrymd.

Vi tillåter flera förenklingar i denna uppgift – vi kräver inte stöd för pekare “in i objekt” (alltså som inte pekar till starten av ett objekt)⁶, eller scanning av den statiska dataarean⁷. Vi uppmuntrar förstås till stöd för dessa vanliga C-idiom, men det är inte nödvändigt. (Och ta inte itu med detta förrän resten av projektet är klart!)

Nu har vi sett hur man kan leta igenom både stacken och heapen efter pekare. Då skall vi titta på hur man kompakterar heapen i syfte att minska fragmentering.

Om alla levande objekt flyttas samman vid allokering kommer allt ledigt minne att vara konsekutivt och vi behöver inte föra bok över var ledigt minne finns, vilket vore fallet för mark–sweep. Därför kan allokering implementeras med så-kallad “bump pointer”. Det går till så att man har en pekare till starten av det fria minnet, “fronten”, och att allokering av \(n\) bytes returnerar den nuvarande addressen till fronten, varefter fronten flyttas \(n\) bytes. Denna typ av allokering är betydligt snabbare än en implementation som söker bland en lista av fria block för att hitta ett av lämplig storlek.

Vidare, om vi enbart opererar på levande objekt och ignorerar skräp blir tidskomplexiteten \(O(\#\textrm{levande objekt})\) istället för \(O(\#\textrm{objekt})\). Det tillåter oss att skriva en implementation som undviker steg 1 och steg 3 i beskrivningen av mark–sweep ovan.

Det är inte ovanligt att 90–95% av alla objekt är skräp vid en skräpsamling⁸, så detta är en stor tidsvinst, även om kopiering är dyrt.

Vi kommer att implementera en variant av denna efter Bartlett.

Det enklaste sättet att implementera en kompakterande skräpsamlare är att dela upp minnet i två olika minnesareor, en passiv och en aktiv. Alla objekt finns i den aktiva arean, och all allokering sker där – den passiva arean används inte.

Om man fyller den aktiva arean triggas skräpsamlingen. Den utgår från samtliga rötter och traverserar samtliga levande objekt i den aktiva arean. Varje objekt som hittas på detta sätt kopieras över⁹ in i den passiva heapen, och vi noterar kopians adress¹⁰. Alla pekare vi hittar i under traverseringens gång ersätter vi med objektets forwarding-adress så att vi till slut kopierat över alla levande objekt från den aktiva arean till den passiva, och uppdaterat alla pekare mellan objekten så att kopiorna pekar ut varandra. På samma sätt uppdaterar vi också alla rotpekare att peka på kopiorna. (Hela detta motsvarar alltså steg 2 i beskrivningen av mark–sweep.)

När traverseringen och kopieringen är klar byter vi så att den passiva arean blir aktiv, och den aktiva passiv.

Vad vi har åstadkommit nu är alltså att alla objekt innan skräpsamlingen finns i den numer passiva arean och betraktas som skräp. Endast de objekt som programmet kunde nå har flyttats över in i den nya aktiva arean vilket betyder att den använder minsta möjliga minne som fortfarande garanterar att programmets alla pekare är korrekta.

Notera att uppdelningen av minnet i två areor varav endast den ena är i bruk vid varje givet tillfälle (förutom vid skräpsamlingen då båda används) effektivt dubblar ett programs minnesanvändande. Detta har inte hindrat denna teknik från att användas i praktiken; de flesta program använder relativt lite minne, och smidig och korrekt minnesanvändning är ofta viktigare än yteffektiv. (Generationsbaserade skräpsamlare där flera olika skräpsamlingstekniker kombineras kan också hjälpa till att minska “slöseriet” med minne.)

Bilderna nedan visar en naiv implementation av en kopierande skräpsamlare. Minnet är indelat i två areor, en aktiv och en passiv. När skräpsamling triggas kopieras alla levande objekt över från den aktiva till den passiva arean, varefter den passiva arean blir aktiv och den aktiva passiv. Notera att i den nya aktiva arean är objekten kompakterade, dvs. lagda intill varandra. På detta vis undviks minnesfragmentering.

Ett problem med skräpsamling i språk som C är avsaknaden av metadata i minnet. Eftersom en pekare och en integer ser identiska ut (och en adress är ett positivt heltal!) är det möjligt att tolka heltalet 3786230 (som kanske avser slutpriset på en enrummare i Stockholms innerstad) som pekaren 0x39C5F6 (samma tal skrivet i bas 16). Har vi otur kan 0x39C5F6 råka vara en valid adress i den heap som hanteras av GC.

Vi kommer att hantera detta problem med en kombination av fyra tekniker:

• Konservativ kompaktering efter Bartlett
• Allokeringskarta
• Höga adresser (frivilligt att implementera)
• Allokering med metadata

Bartlett skiljer mellan säkra och osäkra pekare. En säker pekare är en adress som vi säkert vet är en pekare. En osäker pekare är en vars data vi inte säkert vet är en pekare. Ett typiskt användande av Bartletts teknik är för skanning av stacken i ett C-liknande språk, där vi inte vet vad det är för data vi tittar på. Pekare på stacken blir därför osäkra, medan pekare mellan objekt på heapen¹¹ blir säkra.

Vi klassificerar alltså alla pekare vi hittar som säkra eller osäkra. Att vara konservativ innebär att vi måste utgå från att en osäker pekare faktiskt är en pekare i bemärkelsen att vi måste betrakta dess utpekade objekt som levande, och samtidigt att vi måste utgå från att den osäkra pekaren faktiskt inte är en pekare vilket innebär att vi inte kan flytta dess utpekade objekt i minnet eftersom det kräver att vi ändrar pekarvärdet till den nya adressen. Exempel, om vi hittar 0x39C5F6 (slutpriset på en lägenhet) på stacken måste det objekt som ligger på den adressen överleva och inte flyttas. Flyttade vi det till t.ex. adressen 0x1C0030 måste vi uppdatera värdet på stacken till 0x1C0030 (peka om “pekaren”), vilket skulle betyda att vi ändrat slutpriset på lägenheten!

För att använda Bartletts trick för att hantera osäkerhet delar vi in minnet som vi hanterar i ett antal diskreta “sidor”¹². Istället för att dela in hela heapen i två delar – passiv och aktiv – ger vi varje sida statusen passiv eller aktiv. En osäker pekare till en adress \(A\) medför nu att den omslutande sidan \(P\) inte får flyttas vid kompaktering.

I en skräpsamlare av Bartlett-typ, se figuren nedan, är minnet indelat i många små sidor som var och en kan vara aktiv (grå) eller passiv (vit). Pekare kan också vara säkra eller osäkra (streckad pil). Objekt som utpekas av osäkra pekare får inte flyttas. Detta implementeras genom att hela sidan som objektet ligger på är oförändrad. Detta leder i exemplet i figuren till att ett skräp-objekt inte tas bort för att det råkar ligga på samma sida som ett osäkert utpekat objekt.

Ytterligare ett sätt att minska risken för felaktiga pekarvärden är att använda en allokeringskarta. En allokeringskarta är en array av booleans där varje plats i arrayen motsvarar en valid adress för en allokering, och där true betyder att något allokerats på den platsen (false – inte). Om man t.ex. har (vilket är rimligt) en minsta objektstorlek på 16 bytes[fn::Inklusive header.} behöver man alltså en array med 1024 element för att hålla reda på 16 kb. Om man använder en bitvektor där en enskild bit är en boolean behövs alltså bara 128 bytes för att hålla reda på 16 kb, vilket är <1% overhead.

Om vi återgår till vårt exempel där vi hittar 0x39C5F6 (slutpriset på en lägenhet) på stacken kan vi se om den boolean som motsvarar den adressen i allokeringskartan är true eller false. Om värdet är false kan vi helt ignorera 0x39C5F6. Om värdet är true måste vi behandla det som en pekare.

Det bitset som vi kodat tidigare på kursen (utdelat i Piazza) är fritt fram att använda för att implementera allokeringskartan.

Detta är enkelt att implementera och brukar ge hög avkastning. Använd t.ex. posix_memalign för att allokera minnet till programmets egen heap och ange en mycket hög adress som alignment. Det medför att alla pekaradresser som skapas kommer att vara väldigt stora. Eftersom program sällan manipulerar väldigt stora tal minskar risken för att ett heltal i programmet skulle råka sammanfalla med en valid minnesadress.

För att slippa leta igenom heapen på samma sätt som stacken kommer vi att använda ett format för allokering som kräver att användaren ger den information vi behöver. Vårt skall stödja två typer av allokering:

• h_alloc_struct – där programmeraren anger en slags formatsträng som beskriver minneslayouten hos objektet som skall allokeras¹³. Formatsträngen beskriver var i ett objekt eventuella pekare finns som också skall traverseras för att markera objekt som levande.
• h_alloc_raw – där programmeraren anger storleken på ett utrymme som skall reserveras¹⁴. Detta utrymme får inte innehålla pekare till andra objekt.

I alla fall ovan skall det allokerade minnet nollställas, dvs. samma beteende som calloc.

Formatsträngen förklaras enklast genom exempel. Antag att vi har en typ binary_tree_node, deklarerad enligt följande.

struct binary_tree_node {
  void *value;
  struct binary_tree_node *left;
  struct binary_tree_node *right;
  int balanceFactor;
}

struct%20binary_tree_node%20%7B%0A%20%20void%20%2Avalue%3B%0A%20%20struct%20binary_tree_node%20%2Aleft%3B%0A%20%20struct%20binary_tree_node%20%2Aright%3B%0A%20%20int%20balanceFactor%3B%0A%7D%0A

Detta utrymme kan beskrivas av formatsträngen "***i" som betyder att utrymme skall allokeras för 3 pekare, följt av en int, dvs.,

alloc("***i");

alloc%28%22%2A%2A%2Ai%22%29%3B%0A

är analogt med

alloc(3 * sizeof(void *) + sizeof(int));

alloc%283%20%2A%20sizeof%28void%20%2A%29%20%2B%20sizeof%28int%29%29%3B%0A

Notera att data alignment kan påverka en strukturs layout för mer effektiv minnesåtkomst i en strukt. Detta kan betyda att två fält efter varandra i en strukt har “tomt utrymme” mellan sig för att värdens plats i minnet skall bättre passa med ord-gränser. Man kan antingen sätta sig in i hur detta fungerar¹⁵ – notera att det är plattformsberoende – eller fundera ut hur man stänger av det.¹⁶ Ange tydligt i dokumentationen hur detta har hanterats.

En bra första iteration i implementationen av stödet för allokering med formatsträng implementerar stöd för "*" och "r", där det sistnämnda står för sizeof(int), vilket på en 64-bitars platform ger möjligheten att allokera antingen i “byggklossar” om 8 respektive 4 bytes¹⁷.

Åtminstone följande styrkoder skall kunna ingå i en formatsträng:

Ett heltal före ett specialtecken avser repetition; till exempel är "***ii" ekvivalent med "3*2i". Man kan se det som att default-värdet 1 inte måste sättas ut explicit, alltså * är kortform för 1*. En tom formatsträng är inte valid. En formatsträng som bara innehåller ett heltal, t.ex. "32", tolkas som "32c". Detta innebär att h_alloc_struct("32") är semantiskt ekvivalent med h_alloc_raw(32).

Om vi använder adresser som är “alignade” mot ord i minnet, och varje ord är minst 4 bytes, så kommer alla addresser att vara en multipel av 4, vilket betyder att de sista två bitarna i en adress i praktiken inte används. (Virtuellt minne kan medföra att vi har ett stort antal insignifikanta bitar i varje adress, detta är maskin och OS-specifikt.) Notera att man kan använda t.ex. -falign-functions=16 för att även styra vilka adresser funktionspekare får.

För att inte slösa med minnet skall vi använda de två minst signifikanta bitarna i en pekare för att koda in information om vad som finns i headern. Alltså, om en 32-bitars pekare binärt är (med little-endian) 1001000111101100-01100101000001000 pratar vi om att gömma information i de sista två, dvs. 1001000111101100011001010000010__.

Två bitar är tillräckligt för att koda in fyra olika tillstånd, t.ex.:

Notera att de två minst signifikanta bitarna måste “maskas ut” ur pekaren innan pekaren används – annars kan pekarvärde bli ogiltigt på grund av att datat vi gömt där tolkas som en del av adressen. Det betyder att varje läsning av headern som en pekare skall sätta de två minst signifikanta bitarna²⁰ till 0 i det utlästa resultatet.

Objektets header ligger alltid först i objektet, men skall inte vara synlig i några struktar (det skulle göra programmet beroende av en specifik skräpsamlare, vilket vore dåligt). Därför kommer en pekare till ett objekt alltid att peka på struktens första byte, dvs. den “pekar förbi” headern. Och om man vill komma åt headern måste man använda pekararitmetik och “backa” sizeof(header) bytes. Denna typ av design tillåter att skräpsamlaren modiferas så att headern växer och krymper utan att program som använder skräpsamlaren måste modifieras.

Vi skall använda en bitvektor för att koda in en layoutspecifikation på ett sätt som är betydligt mer yteffektivt än en formatsträng. Vi kan t.ex. använda en bit för att ange antingen en pekare eller “data”, t.ex. 11001 är samma som formatsträngen "**ii*", som ger en objektstorlek på \(32\) bytes²¹ om en pekare är 8 bytes och sizeof(int) är 4~bytes. Vi behöver också information om bitvektorns längd. Notera att vi enbart är intresserade av huruvida något är en pekare eller inte – om det är en int eller en float eller en bool kvittar.

För större allokeringar av data utan pekare behöver layoutspecifikationen enbart vara en storleksangivelse. I likhet med headern kan vi reservera en bit för att ange om layoutspecifikationen är en storlek i bytes, eller om det är en vektor med mer precis layoutinformation.

På en maskin där en pekare är 64 bitar skulle alltså 2 bitar gå åt till metadata om headern, ytterligare 1 bit gå åt till att koda in typ av layoutspecifikation, och resterande 61 bitar antingen vara en storlek i bytes eller en bitvektor och dess längd²².

Notera att eftersom den kompakta layoutspecifikationen har en övre storleksgräns (30 i exemplet i fotnoten här intill) fungerar denna representation bara för data av begränsad storlek (som också styrs av huruvida headern är 32 eller 64 bitar).