Stacken och heapen

Variablerna i C-koden, value och smaller är namn som vi väljer väl som programmerare eftersom de hjälper oss att läsa koden. När programmet väl kör så finns inte dessa namn kvar³, utan de har ersatts av adresser⁴.

I fallet stupid så är adressen för value adressen till den aktuella stack frame:en + 0, eftersom det är den första variabeln på stacken. Adressen för smaller är sizeof~(int) bytes efter adressen till value⁵.

Man kan tänka på current-pekaren i Figur 1 som en char *-pekare. Vi kan typomvandla den till en struct stack_frame_for_stupid*; då skulle åtkomst till value bli ((SFFS) current)->value alternativt *(current+0) och åtkomst till smaller bli ((SFFS) current)->smaller alternativt *current+sizeof(int)}.

När man tar adressen till en variabel, t.ex. &value får man tillbaka den adress i minnet där det värde som variabeln innehåller finns lagrat. T.ex. skulle &value i den tredje delfiguren från vänster i Figur 1 vara 0x314 och &smaller på samma stackframe vara 0x318.

Det betyder att tilldelningen smaller = value - 1 som sker i funktionen kommer att läsa 4 bytes⁶ från 0x314 tolka dem som ett heltal, subtrahera 1 från talet, och sedan spara resultatet på minnesadressen 0x318.

Varje variabel innehåller alltså ett värde. Det värdet ligger på stacken, d.v.s. är lagrat i en stack frame. Varje variabel har också en adress, som avser den plats i minnet där dess värde ligger. Igen, detta är en förenkling som inte är helt sann, men duger för oss här. Själva variabelnamnet är en bekvämlighet för oss programmerare och är inte sparat i programmet. (Igen, namnen kan vara sparade för debugging.) Programmet kan inte inspektera en variabels namn, etc.

Låt en icke-namngiven funktion ha följande funktionskropp. Denna funktion har tre lokala variabler; med samma storleksantaganden som tidigare har den en stack frame som är 12 bytes stor.

int x = 42;
int *y = &x;
int *z = NULL;
z = y;
(*z)++;
y++;

int%20x%20%3D%2042%3B%0Aint%20%2Ay%20%3D%20%26x%3B%0Aint%20%2Az%20%3D%20NULL%3B%0Az%20%3D%20y%3B%0A%28%2Az%29%2B%2B%3B%0Ay%2B%2B%3B%0A

Notera att x är ett heltal, medan y och z är pekarvariabler – de innehåller adresser till platser i minnet. I detta fall kommer dessa adresser att avse platser på stacken (d.v.s., y och z är pekare till stacken). Värdet i t.ex. y är alltså en adress – om vi vill läsa värdet som y pekar på måste vi använda avrefereringsoperatorn, *, och skriva *y vilket betyder “gå till den minnesadress som är lagrad i y, läs sizeof(int) bytes, och behandla dem som en int.” – eftersom y är en pekare till just en int.

När vi tar adressen till x på rad 2 returneras den adress som värdet 42 ligger på. Låt säga att att det var 0x112. Innehållet i y är då adressen 0x112, vilket vi normalt ritas som en pil till den platsen. Givet detta antagande kan vi nu besvara frågorna på sid. 1, “vad är värdena på x, y och z?”

Svaret denna gång är att x fortfarande är 43, z är 0x112 och y är 0x116. Att y är 0x116 och inte 0x113 kommer av C:s definition av pekararitmetik. När man inkrementerar eller adderar till en pekare görs detta i steg om \(n\) där \(n\) är storleken av den typ som pekas ut. Eftersom y pekar på en int, blir y++ likvärdigt med 0x116. Detta förenklar programmeringen och minskar risken för att vi råkar läsa t.ex. de sista tre tecknen av en int och det första av en annan, vilket vore resultatet om y var 0x113 och vi försökte läsa *y.

Om du är med så här långt borde du förstå att även om y och z pekar på samma plats i minnet (iallafallefter rad 4 och innan den sista raden) så är de olika variabler som tar upp var sina 4 bytes i minnet, och en tilldelning till den ena förändrar inte den andra.

Notera att alla lokala variabler lagrar sina data på stacken. Ponera följande kod:

char *s1 = "Hello, world";
char s2[13];
strcpy(s2, s1);

char%20%2As1%20%3D%20%22Hello%2C%20world%22%3B%0Achar%20s2%5B13%5D%3B%0Astrcpy%28s2%2C%20s1%29%3B%0A

Hur stor är stack frame:en för en funktion utan parametrar och med denna kropp?

Svaret är 17 bytes – igen, givet att en pekare är 4 bytes, och att ingen avrundning sker, t.ex. till 20 som är närmaste multipel av 4, vilket kan antas vara storleken på ett ’’ord’’ i vår hypotetiska dator – eftersom C allokerar utrymmet för s2 på stacken. Den första raden reserverar minnet för strängen "Hello, world" i programmets statiska dataarea, och sedan utrymme för en pekare på stacken som får peka dit. Den andra raden reserverar 13 tecken på stacken, men ingen pekare.

Men hur kan då s2 fungera som en char *? Minns att variabler “försvinner” vid kompilering, och att deras värden normalt har en adress. Det betyder att innebörden av variabeln s1 för vårt program är en adress till en plats på stacken där det ligger en adress till en char, och att innebörden av s2 är en adress till en plats på stacken där det ligger en char. Man kan tilldela s1 = s2, men inte s2 = s1 av just denna anledning. Den första tilldelningen sparar adressen till det första tecknet i s2 i s1. Den andra tilldelningen är nonsens eftersom s1 är variabel som innehåller en adress och s2 är en variabel som innehåller en array av char:s.

Samma situation uppstår med struktar. Givet följande strukt:

typedef struct _point 
{
  int x, y;
} point, *Point;

typedef%20struct%20_point%20%0A%7B%0A%20%20int%20x%2C%20y%3B%0A%7D%20point%2C%20%2APoint%3B%0A

kan vi skriva följande funktionskropp. (Notera syntaxen för att initiera värdena på x och y i p.) Man man även ange posternas namn vid initiering: point p = { .y=1, .x=2 };:

point p = {0, 0};
Point pp = &p;

point%20p%20%3D%20%7B0%2C%200%7D%3B%0APoint%20pp%20%3D%20%26p%3B%0A

där den första variabeln tar upp 8 bytes i minnet, (sizeof(point) = 8, givet våra tidigare antaganden.) medan den andra tar upp 4 bytes. Notera att p och pp avser samma objekt i minnet. När man vill modifiera y i p skriver man p.y; när man vill modifiera y via pp skriver man pp->y. Punkten är en operator som indexerar sig in i variabel av strukt-typ (p.y är likvärdigt med *(((int~*)&p)+1), eftersom y är det andra fältet i strukten.}, medan “piloperatorn” (->) indexerar sig in i variabler av typen pekare-till-strukt.

Konsekvent använt blir följden att .-operatorn opererar på data som bara är synligt för den körande funktionen, medan ->-operatorn opererar på data som kan vara synligt även för andra (t.ex. för att det utpekade värdet ligger på heapen, eller på en annan stack frame). Man kan naturligtvis skriva t.ex. (*pp).y istället för pp->y, men då måste avrefereringsoperatorn användas, vilket igen signalerar att vi manipulerar data via en pekare, och förändringarna kan därför vara synliga utanför den aktuella funktionen. C:s syntax visar sålunda tydligt när man följer en pekare och att man därför inte vet i vilken utsträckning den aktuella förändringen kan ses av andra! Läs gärna -> som “nu följer vi en pekare (till någonstans i minnet)”.

Värt att notera att C har värdesemantik, vilket betyder att följande kod skapar två olika punkter genom att ta en kopia av p och spara i q.

point p;
p.x = 10;
p.y = 7;
point q = p; // kopiera hela p in i q
q.x = 5;
assert(p.x == q.x); // failar

point%20p%3B%0Ap.x%20%3D%2010%3B%0Ap.y%20%3D%207%3B%0Apoint%20q%20%3D%20p%3B%20%2F%2F%20kopiera%20hela%20p%20in%20i%20q%0Aq.x%20%3D%205%3B%0Aassert%28p.x%20%3D%3D%20q.x%29%3B%20%2F%2F%20failar%0A

Samma sak händer när man skickar runt pekarvariabler – själva innehållet i variablerna, minnesadresserna, kopieras. Platsen där de ligger förblir dock orörd.

C hanterar minnet på stacken själv; kompilatorn räknar ut varje funktions stack frame-storlek och de faktiska motsvarigheterna till current och top flyttas fram och tillbaka ’’automagiskt’’ vid varje nytt funktionsanrop eller -retur. Denna minneshantering är snabb och effektiv, men begränsad. Eftersom funktionen tar bort en stackframe när en funktion returnerar är följande kod nonsens:

char *bogus() 
{
  char result[16];
  strcpy(result, "Hello, world");
  return result; /* !!! */
}

char%20%2Abogus%28%29%20%0A%7B%0A%20%20char%20result%5B16%5D%3B%0A%20%20strcpy%28result%2C%20%22Hello%2C%20world%22%29%3B%0A%20%20return%20result%3B%20%2F%2A%20%21%21%21%20%2A%2F%0A%7D%0A

På raden !!! förstörs stack frame:en och därmed result. Egentligen förstörs den inte förrän i och med nästa funktionanrop. Detta kommer nämligen att allokera en ny stack frame som skriver över result. Om vi vill allokera minne som skall ha en godtyckligt lång livstid måste vi allokera på heapen.