Kodprov 2017-12-08

Inlämning går till så här: ställ dig i katalogen kodprov171208. Om du har tappat bort dig i filsystemet kan du skriva cd; cd kodprov171208. Nu kan du skriva make handin för att lämna in kodprovet. När du kör detta kommando skapas en zip-fil med de filer som du har uppmanats att ändra i (inga andra), och denna fil sparas sedan på en plats där vi kan rätta provet.

Den automatiska rättningen kommer att gå till så att vi kör dina inlämningar mot vissa testfall. Du har fått ut testfall eller motsvarande i detta prov som du kan använda för att kontrollera din lösning. Om du har löst uppgifterna på rätt sätt och testfallen som du får ut passerar är det troligt att du är godkänd. Man kan förstås aldrig vara helt säker med test, och på tidigare omgångar av kodprovet har vi sett lösningar som fungerar enbart för de testfall som lämnats ut. Till exempel har vi sett lösningar där man, istället för att göra en generell (korrekt) lösning med strlen(), testade om en sträng var "foo" och i så fall returnerade 3, om det var "quux" returnerade 4, etc. där "foo" och "quux" strängarna från testfallen. En sådan lösning klarar förstås inte de testfall som vi kör mot när vi rättar, och förklarar också varför vi inte lämnar ut samma testfall i tentan som vi kör vid rättningen.

• Samma regler som för en salstenta gäller: inga mobiltelefoner, inga SMS, inga samtal med någon förutom vakterna oavsett medium.
• Du måste kunna legitimera dig.
• Du får inte på något sätt titta på eller använda gammal kod som du har skrivit.
• Du får inte gå ut på nätet.
• Du får inte använda någon annan dokumentation än man-sidor och böcker.
• Det är tillåtet att ha en bok på en läsplatta, eller skärmen på en bärbar dator. Inga andra program får köra på dessa maskiner, och du får inte använda dem till något annat än att läsa kurslitteratur.
• Du måste skriva all kod själv, förutom den kod som är given.
• Du får använda vilken editor som helst som finns installerad på institutionens datorer, men om 50 personer använder Eclipse samtidigt så riskerar vi att sänka servrarna.

Vi kommer att använda en blandning av automatiska tester och granskning vid rättning. Du kan inte förutsätta att den kod du skriver enbart kommer att användas för det driver-program som används för testning här. Om du t.ex. implementerar en länkad lista av strängar kan testningen ske med hjälp av ett helt annat driver-program än det som delades ut på kodprovet.

I mån av tid har vi tidigare år tillämpat ett system där vi ger rest för mindre fel. Det är oklart om detta system tillämpas i år, men det betyder att det är värt att lämna in partiella lösningar, t.ex. en lösning som har något mindre fel.

Det skall inte vara möjligt för någon som får en pekare till ett minne att se att kalloc() använts för att allokera det. Det skall se ut som om det är allokerat med vanlig malloc(). Därför returnerar kalloc() inte en pekare till starten av det minne som allokerats, utan en pekare h bytes inMinns att vi allokerar h + n + m bytes när användaren ber om n bytes. – dvs. en pekare som pekar förbi headern och på det första av de n bytes som hen bad om. På så sätt kan användaren göra

char *str = kalloc(4);
strcpy(str, "Hej");

utan att råka skriva över headern som håller koll på hur många bytes som är allokerade, var allokeringen skedde, etcAtt lägga metadatat "till vänster" om en pekare är ett standard-C-trick. Det kommer av att vi normalt inte vet hur många bytes allokerat minne en pekare p pekar ut, så vi kan inte räkna ut slutet av vad p pekar på, och därför inte lägga metadatat där. Om metadatat har en fix längd (vilket det har i vårt fall) är det dock möjligt att hitta det genom att "backa" i minnet, h bytes i vårt fall..

För varje kalloc()-allokerat minne HHHH_DDDDDDDDDDDDD_MM kan vi alltså prata om två pekare:

1. userland pointer som är den pekare som returneras, och som alltså pekar på det första D:etstr ovan är en userland pointer., samt
2. internal pointer som pekar på det första H:et, alltså på den faktiska starten av det allokerade minnet.

Skillnaden mellan dessa två i bytes är precis headerns storlekFunktioner för att konvertera mellan dessa två pekare headern, till datat samt för att givet en pekare ta fram dess magiska tal, finns redan implementerat!.

Alla publika funktioner i kalloc.h som tar in eller returnerar pekare tar in eller returnerar userland pointers. Internt hanterar många funktioner pekare till starten av allokerat minne. Dessa pekare har typen obj_t.

Observera att det inte finns någon strukt i kalloc.c som motsvarar hela det allokerade minnet, alltså hela h + n + m eller HHHH_DDDDDDDDDDDDD_MM. Det är omöjligt eftersom vi inte vet storleken på n vid kompileringtid! Istället använder vi pekararitmetik för att räkna ut starten på HHHH, DDDDDDDDDDDDD och MM.

Det sköts av funktionerna kalloc_header() och kalloc_object().

Ovan beskrevs hur vi kunde kontrollera i samband med anrop till kalloc_free() om det magiska talet längst bak i ett objekt fortfarande var intakt. Detta är problematiskt på två sätt:

1. Det hjälper oss dock inte att hitta minnesfel i minne som aldrig frias
2. Tiden mellan minnet förstördes och vi märker det i samband med anrop till kalloc_free() kan vara väldigt lång

Funktionen kalloc_check_integrity() löser båda dessa problem. När gör den en integritetskontroll på alla allokerade objekt. Men för att göra detta måste vi hålla koll på alla allokerade objekt!

För att hålla reda på alla allokerade objekt stoppar vi dem i en länkad lista. För att slippa allokera minne för en länk varenda gång användaren allokerar något med kalloc() stoppar vi in en next-pekare i headern på varje objekt så att varenda allokerat minne utom det sista pekar på nästa allokerade minne. På så sätt kan kalloc_check_integrity() enkelt loopa igenom minnet och hitta alla allokeringar.

Funktionen kalloc_inner_find(), som är den som du skall skriva, skall alltså ta emot en userland pointer p, och söka igenom den länkade listan av interna pekare till allokerade block för att se om någon av dessa pekare har p som sin motsvarande userland pointer. Det vill säga vi letar efter något q sådant att kalloc_object(q) == p. Finns det ett sådant q vill vi returnera en pekare till q, så att kalloc_free() kan länka ur q ur listan.

Observera att det inte går att returnera vilken pekare till q som helst – det måste vara föregående elements q. Det vill säga, om q är node->next så är det &(node->next) som skall returneras.

Det vanligaste felet i inlämnade kodprov – ofta i kombination med ett annat fel – var ett "försök" till att undvika dubbelpekare. Istället för att använda mem och stega sig fram genom den länkade strukturen med mem = &(*mem)->next användes en programsats som är syntaktiskt snarlik, men semantiskt väldigt annorlunda: *mem = (*mem)->next.

Observera att mem är en pekare till den globala variabeln first. Satsen mem = &(*mem)->next får mem att peka på next-pekaren i nästa block. Satsen *mem = (*mem)->next ändrar inte mem, men värdet i variabeln first! Denna sats länkar alltså ur ett block ur listan. Eftersom denna sats förekommer inuti while-loopen blir alltså konsekvensen av detta att iterationen länkar ur alla block och "tömmer den länkade listan".

Det betyder att en lösning som är identisk med min, men använder *mem = (*mem)->next istället för mem = &(*mem)->next endast är nästan rätt utifrån "edit distance"Alltså antalet tecken som måste ändras. – med avseende på vad koden gör är lösningen gravt felaktig. Hade vi haft tid att ge rest detta kodprov hade vi inte givit rest för detta fel.

Ett något mindre vanligt fel är att hoppa över det första blocket, t.ex. genom att aldrig testa *mem utan istället gå direkt på (*mem)->next. Ingen har begått endast detta fel, utan detta fel är alltid i kombination med något annat, vanligen det föregående.

Jag fick frågan om jag avsiktigt försökt vilseleda de som skrev kodprovet med följande formulering:

Det finns inget medvetet vilseledande i hela kodprovet! Syftet med ovanstående var att försöka motverka nästa vanliga fel. Kanske hade det blivit tydligare med tillägget "inte &q"?

Av okänd anledning – kanske för att slippa skriva &(*mem) hela tiden har många börjat med att avreferera mem (t.ex. obj_t *q = *mem;) för att på så sätt iterera över en lista av pekare till block (istället för pekare till pekare till block). Eftersom funktionen skall returnera en obj_t ** har man dock fått problem med return q; som inte typcheckar. Detta har många försökt lösa genom return &q; vilket är problematiskt eftersom &q är addressen till den lokala variabeln q som ligger på en stack frame som förstörs i och med return. Alla som har gjort denna lösning har fått en varning av gcc:

kalloc.c:203:10: warning: function returns address of local variable [-Wreturn-local-addr]

Flera har missat att göra en loop, eller på andra sätt missat att gå förbi första elementet. Detta funkar t.ex. bra för leak i testet eftersom det är den första allokeringen, men fungerar mindre bra när man testar med flera allokeringar.

Flera har, förmodligen i syfte att få till någonting som kunde typas som en dubbelpekare, använt malloc för att få en pekare till en plats som innehåller en annan pekare, och sedan använt detta som en loop-variabel istället för mem. Detta är konstigt, och tyderI min tolkning, ofc. på brist på förståelse för hur pekare till pekare fungerar. Tyvärr har dessa lösningar med ett undantag också lett till minnesläckage då free inte alltid anropats. Antingen har lösningen läckt den nya mallokeringen, eller så har det lett till att det block som skulle tas bort läcktes.