Studie en implementatie van input replay door Frank Cornelis

Faculteit Toegepaste Wetenschappen Vakgroep Elektronica en Informatiesystemen Voorzitter: Prof. dr. ir. J. Van Campenhout

Studie en implementatie van input replay door Frank Cornelis

Promotor: Prof. K. De Bosschere Scriptiebegeleider: Michiel Ronsse

Scriptie ingediend tot het behalen van de academische graad van licentiaat in de informatica, optie software-ontwikkeling Academiejaar 2001-2002

Voorwoord Graag wil ik een woord van dank richten aan ieder die heeft bijgedragen tot de realisatie van deze scriptie. Allereerst dank ik prof. K. De Bosschere voor het zeer boeiende onderwerp en voor de wetenschappelijke ondersteuning. Mijn speciale dank gaat uit naar M. Ronsse, dit voor het mogen inkijken van zijn experimentele code, de intense begeleiding en de leerrijke tussentijdse vergaderingen. Ook diegene die me via de “linux-kernel mailing list” geholpen hebben, door steeds mijn vragen te behandelen, ben ik zeer erkentelijk. Tevens wens ik alle professoren te danken voor de theoretische en praktische kennis die ze mij gedurende mijn informaticastudie hebben bijgebracht. Tenslotte bedank ik mijn ouders omwille van de geboden kans en hun aanmoedigingen om deze studie tot een goed eind te brengen. Frank Cornelis 29 mei 2002

i

VOORWOORD

ii

Toelating tot bruikleen De auteur geeft de toelating deze scriptie voor consultatie beschikbaar te stellen en delen van de scriptie te kopiëren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze scriptie. Frank Cornelis 29 mei 2002

Studie en implementatie van input replay door Frank Cornelis

Scriptie ingediend tot het behalen van de academische graad van licentiaat in de informatica, optie software-ontwikkeling Academiejaar 2001-2002 Promotor: Prof. K. De Bosschere Scriptiebegeleider: Michiel Ronsse Faculteit Toegepaste Wetenschappen Universiteit Gent Vakgroep Elektronica en Informatiesystemen Voorzitter: Prof. dr. ir. J. Van Campenhout

Samenvatting Bij input replay wordt in een eerste fase de invoer van een bepaald programma vastgelegd in een bestand. Dit bestand kan later gebruikt worden in een replay-fase als invoer voor dit programma. Hiertoe wordt de normale invoer van het programma geblokkeerd en wordt de invoer, die in de record-fase werd opgeslaan, in het programma ge¨ınjecteerd. Wel is het soms gewenst om zelfs in de replay-fase bepaalde systeemoproepen, zowel voor invoer als voor uitvoer, ook effectief te laten plaatsvinden. Een voorbeeld hiervan betreft het wegschrijven naar het scherm; in replay-fase wensen we ook de schermuitvoer van het programma te bekijken. De implementatie van deze input replay werd uitgevoerd onder het besturingssysteem linux daar dit een open-broncode-initiatief betreft. Hierbij werd gebruik gemaakt van de systeemoproep ptrace, alsmede van een extensie op ptrace die speciaal voor deze thesis werd ontwikkeld. Trefwoorden: input replay, linux, ptrace

Inhoudsopgave 1 Inleiding 1.1 Probleemstelling . . . . . . . . 1.2 Belangrijke aspecten van replay 1.3 Input replay van programma’s . 1.4 Inhoud . . . . . . . . . . . . . .

. . . .

1 1 2 4 6

. . . . . . . . . . . . . .

7 7 8 9 12 15 16 17 18 18 19 21 23 28 32

. . . .

33 33 39 42 46

4 Input replay onder Linux 4.1 Ontwerp van de replay-module . . . . . . . . . . . . . . . . . . . . . . . 4.2 Het gebruik van de replay-module . . . . . . . . . . . . . . . . . . . . .

47 47 50

5 Besluit

54

A De bijgeleverde CD-ROM

55

B Een codefragment uit de replay-module

56

C Kernel tools

59

. . . .

. . . .

. . . .

. . . .

2 Implementatie van Input Replay 2.1 Situering . . . . . . . . . . . . . . . . . 2.2 Behoud van het systeemoproep-patroon 2.3 Procescommunicatie . . . . . . . . . . 2.4 Andere communicatie . . . . . . . . . . 2.5 Partiële uitvoer . . . . . . . . . . . . . 2.6 Partiële invoer . . . . . . . . . . . . . . 2.7 Procescontext . . . . . . . . . . . . . . 2.8 Recording . . . . . . . . . . . . . . . . 2.8.1 Klassen van systeemoproepen . 2.8.2 Het opslaan van de replay-data 2.8.3 Heisenbugs . . . . . . . . . . . 2.9 Replay . . . . . . . . . . . . . . . . . . 2.10 Signalen . . . . . . . . . . . . . . . . . 2.11 Replay configuratiebestanden . . . . . 3 Monitoring onder Linux 3.1 Proces Trace systeemoproep 3.2 Uitbreidingen . . . . . . . . 3.3 Implementatie . . . . . . . . 3.4 Gebruik . . . . . . . . . . .

. . . .

. . . .

. . . .

iv

. . . .

. . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

. . . .

. . . . . . . . . . . . . .

. . . .

INHOUDSOPGAVE

v

Bibliografie

60

Lijst van figuren

61

Lijst van tabellen

62

Index

63

Hoofdstuk 1 Inleiding Zoals reeds door M. Ronsse en K. De Bosschere [8] gesteld, is de theoretische basis, nodig tot input replay, vrij beperkt. Het is vooral de replay van parallellisme die een belangrijk onderzoeksdomein vormt. Zelfs interactie tussen replay van input en replay van parallellisme is af te zwakken tot input replay zonder enige vorm van parallellisme daar men onder sequenciëring het parallellisme ten aanzien van de input replay geheel kan elimineren. Desalniettemin zal hierop een uiteenzetting volgen dewelke ertoe dient bij te dragen een basis te leggen voor een implementatie van input replay.

1.1

Probleemstelling

Samen met de steeds toenemende capaciteit van de huidige generatie computersystemen, neemt ook de omvang van de software toe. De door Tanenbaum [9] geformuleerde “eerste wet van software”: Adding more code adds more bugs laat impliceren dat het aantal bugs in (systeem)software evenredig oploopt. De behoefte aan krachtige debug-tools is dan ook steeds schrijnender. Belangrijk hierbij zijn de zogenaamde cyclische debuggers. Deze zullen een programma telkens opnieuw heruitvoeren met dezelfde invoer, resulterend in steeds dezelfde uitvoer, speurend naar bugs van algoritmische aard. Doorgaans doet men hiertoe beroep op breakpoints. Bijgevolg stelt het probleem zich dat men een bepaald proces steeds van identiek dezelfde data wenst te voorzien. Dit zal dan ook door input replay worden bewerkstelligd. Niet enkel cyclische debuggers zijn afhankelijk van input replay, ook onderzoek naar niet-determinisme binnen parallelle en gedistribueerde processen vraagt hierom. Men is hier doorgaans niet gebrand op het bekomen van steeds dezelfde uitvoer zoals bij het cyclisch debuggen het geval is, maar men zal net de verschillen in uitvoer wensen te focussen. Deze verschillen duiden op niet-deterministische elementen binnen het betreffend proces. Bijgevolg is input replay ook een zeer belangrijk aspect bij de detectie van data races binnen een parallelle uitvoering. Verder kan men input replay ook aanwenden bij de bestudering van programmauitvoeringen onder deels wijzigende data-invoerstromen. Slechts één enkele datastroom 1

HOOFDSTUK 1. INLEIDING

2

uit de invoer van een programma wijzigen, laat toe selectief bepaalde delen van het betreffend proces uit te testen en te analyseren. Een dynamische implementatie van input replay is bijgevolg bepalend voor de bruikbaarheid van deze laatste. Het utopische doel “deterministische heruitvoering”, dewelke gelijktijdige replay van input en parallellisme omvat, vereist tevens de hier behandelde replay-faciliteiten. Opgemerkt dient dus te worden dat input replay slechts een klein deel uitmaakt van een veel grotere doelstelling, namelijk een complete eliminatie van niet-deterministische factoren binnen heruitvoering van software.

1.2

Belangrijke aspecten van replay

Een perfecte replay bestaat niet. Een heruitvoering verschilt steeds van zijn origineel daar het tijdstip waarop deze gebeurt reeds een factor van verschil uitmaakt. Enkel wanneer we onze waarnemingsgranulariteit1 grover maken, kunnen we tot de uitspraak “een perfecte replay” komen. Dit betekent concreet dat we steeds iets minder nauwkeurig dienen waar te nemen dan de werkelijkheid. Binnen het domein van een computerprogramma zal dit inhouden dat we over een perfecte replay spreken indien het resultaat van elke instructie bij heruitvoer hetzelfde is als bij de originele uitvoering. Ook al is het tijdstip waarop dit gebeurt niet meer hetzelfde. In dit kader kan men twee soorten waarnemingsgranulariteiten onderscheiden: • De maat van replay die het replay-systeem nodig acht om in een gevraagde replay te voorzien. Wanneer het replay-systeem een gaande replay niet meer als perfect beschouwt, zal de replay-module de gaande replay als onhoudbaar beschouwen. De replay wordt in dit geval stopgezet. Doorgaans zal deze maat onderdeel uitmaken van de specificaties waarnaar het betreffende replay-systeem werd ontwikkeld. • De maat van replay waarmee een waarnemer/gebruiker de replay als perfect zal bestempelen. Elke gebruiker kan zijn eigen eisen en bijgevolg zijn eigen maat hebben ter aanduiding van een geslaagde replay. Merk hierbij op dat een gebruiker een replay-systeem slechts bruikbaar zal vinden wanneer zijn maat tot waarnemen van een perfecte replay gelijk aan of grover is dan die gehanteerd door het replay-systeem. Uiteraard kan het zijn dat een replay correcter gebeurt dan nodig geacht door het replay-systeem, doch dit is geen vereiste. Hetzelfde geldt voor de correctheid zoals gedicteerd door de gebruiker van het replay-systeem. Een perfecte replay, zoals bepaald door een waarneming met fijne granulariteit, zal steeds een perfecte replay impliceren zoals waargenomen via een grovere granulariteit, met als uiterste een waarneming die zich beperkt tot het starten en stoppen van het te replayen proces. Het omgekeerde is niet steeds waar, met als uiterste een incorrecte replay wegens steeds voortvloeiende tijd die niet te replayen valt. 1

Granulariteit vertaald van het Engelse granularity.


3

De waarnemingsgranulariteit is gerelateerd aan het abstractieniveau waarop we effectief replayen. De waarnemingsgranulariteit is echter een maat waarmee we een replay beschouwen, terwijl het abstractieniveau duidt op het niveau waarop we effectief replayen. Deze twee hoeven niet noodzakelijk samen te vallen. Doorgaans zal een hoger abstractieniveau leiden tot kleinere replay-bestanden2 [8], ten nadele van de correctheid van de replay zoals door het replay-systeem algoritmisch gemeten via het vooraf ingestelde waarnemingsniveau. Een replay-systeem heet pragmatisch correct indien zijn abstractieniveau, gebruikt bij replay, overeenkomt met het abstractieniveau nodig om een programma zijn normale verloop te laten aannemen. Een fijnere replay-verzorging door het replay-systeem zou nutteloos zijn daar het programmaverloop hierdoor niet verder be¨ınvloed wordt. Het kan zelfs zo zijn dat een te laag abstractieniveau, aangewend door het replay-systeem, ongewenst is voor de gebruiker. Concreter zal een replay-gebruiker doorgaans meer hebben aan de foutmelding: “de functie kreeg een illegale waarde -1 als parameter”, dan aan de melding: “het register xyz kreeg de illegale waarde -1 toegekend”. Dit omdat het door het replay-systeem gehanteerde abstractieniveau en daarmee gerelateerde waarnemingsniveau te laag ligt. Merk verder op dat een te laag abstractieniveau de originele uitvoering van het te replayen systeem zelf zodanig zou kunnen be¨ınvloeden, dat deze uitvoering compleet verschilt van een uitvoering waarbij we het replay-systeem betreffend proces niet laten monitoren. Hierbij worden we geconfronteerd met zogenaamde Heisenbugs, veroorzaakt onder het monitoren door het replay-systeem. Deze bugs zijn deterministisch of nietdeterministisch geaard3 . De deterministische vorm onstaat door het probe effect van het replay-systeem, de niet-deterministische vorm doorgaans door be¨ınvloeding van het parallellisme van betreffend proces. De recording overhead door het replay-systeem dient bijgevolg zo klein mogelijk te worden gehouden, zodat het gemonitoorde proces zo weinig mogelijk wordt be¨ınvloed. Ideaal zou zijn dat de recording overhead zó laag is, dat we het replay-systeem steeds alle processen actief laten tracen en dus als vast onderdeel van de werkomgeving maken. Hierdoor zou elke anomalie, die zich tijdens bedrijf voordoet, steeds door het replaysysteem worden gedetecteerd en mogelijk gereplayet voor nader onderzoek. Elk abstractieniveau kent zijn eigen overhead, bepaald door afweging tussen space en time overhead. • De time overhead wordt veroorzaakt door de belasting van de processor(en) met het monitoren door het replay-systeem. Deze overhead kan een bepaalde impact hebben op de uitvoering van processen die men wenst te tracen. Verder kunnen restricties, opgelegd door het replay-systeem zelf, ook zorgen voor een time overhead. • De space overhead wordt doorgaans veroorzaakt door de opbouw van het replaybestand. Het gebruik van tijdelijke bestanden door het replay-systeem zal hier echter ook een aandeel in hebben. 2

Worden ook nog trace-bestanden genoemd. In sommige literatuur stelt men dat Heisenbugs louter niet-deterministisch geaard zijn. Doch sommige bugs door be¨ınvloeding zijn perfect voorspelbaar. 3


4

Een grotere time overhead leidt doorgaans tot kleinere replay-bestanden daar men, door het additionele tijdsverbruik, selectiever de data kan stockeren nodig voor de replay. Doch echter kent het replay-bestand een maximale compactheid en zal additionele time overhead op een gegeven moment niet meer resulteren in een reductie van de space overhead. In sommige gevallen kan het zijn dat —voor een bepaalde afweging tussen de space en time overheads— een lager abstractieniveau attractiever is qua overhead dan een hoger abstractieniveau. In dit geval is het verantwoord het abstractieniveau, gehanteerd door het replay-systeem, te verlagen. Andersom is dit echter niet toelaatbaar daar men hierdoor de specificaties van het replay-systeem zou schenden.

1.3

Input replay van programma’s

De aard van een programma is sterk bepalend voor de manier waarop we input replay dienen te implementeren. We zullen vooreerst dan ook de programma’s in hun drie categorieën onderverdelen. • Sequentiële programma’s Het is belangrijk onderscheid te maken tussen programma’s die parallelle code bevatten en programma’s die deze code ook effectief kunnen uitvoeren binnen een proces. Elk proces begint immers met een sequentieel verloop en kan pas later in de uitvoering tot parallellisme komen. Vooraleer we aan input replay toe zijn, moeten we de soorten invoer die een programma kent, analyseren. Er zijn twee soorten invoer te onderscheiden. – Externe invoer die wordt veroorzaakt doordat het proces via (onder andere) het besturingssysteem met andere deelsystemen communiceert. Deze is bij alle programma’s niet-deterministisch van aard. Het zal bijgevolg nodig zijn deze vorm van invoer te kunnen replayen indien we een perfecte replay wensen. – Externe invoer wordt veroorzaakt binnen het proces zelf. De verschillende instructies die binnen het proces worden uitgevoerd, zullen namelijk de (globale) datastructuren van het proces lezen (en schrijven) wat een vorm van invoer is. Bemerk dat bij sequentiële programma’s deze vorm van invoer perfect deterministisch is. Deze interne invoer wordt bij sequentiële programma’s namelijk geheel gedicteerd door de code van het programma zelf. • Parallelle programma’s Dit zijn programma’s die tijdens de uitvoering verschillende threads al dan niet binnen dezelfde virtuele geheugenruimte van betreffend proces laten lopen. Indien verschillende threads binnen dezelfde virtuele geheugenruimte via globale datastructuren voor interne invoer zorgen, kan dit een additionele bron van nietdeterminisme zijn, naast het niet-determinisme veroorzaakt door de (normale) externe invoer. Het deterministische karakter van de interne invoer wordt hier namelijk niet meer louter en alleen bepaald door de code van het programma. Bij replay van parallelle programma’s dienen we duidelijk te stellen wat het is wat we wensen te replayen.


5

– Binnen een parallel programma kan het wenselijk zijn van de verschillende processen die onderdeel uitmaken van het parallelle programma slechts één enkel proces te replayen. Indien deze verschillende processen allen elk hun eigen gescheiden virtuele adresruimte kennen, verloopt de communicatie tussen deze processen op externe wijze. Replay van één enkel proces hieruit is zoals de replay van sequentiële programma’s. Indien het betreffende proces echter zijn virtuele adresruimte deelt met andere threads, dienen we ook de interne communicatie met deze andere threads te replayen, alsook de externe communicatie van deze andere threads. – Het kan ook zijn dat we meerdere processen binnen het parallelle programma tegelijk wensen te replayen om de interactie tussen deze te bestuderen. Dit zal in deze scriptie echter niet worden behandeld. • Gedistribueerde programma’s Gedistribueerde programma’s zijn er onder twee vormen. – Het gedistribueerde karakter van het programma wordt voorzien door een bibliotheek, los van het eigenlijk besturingssysteem. Hierbij voorziet de kernel enkel in de communicatie, doorgaans via een netwerkstapel als TCP/IP. – Het besturingssysteem zelf verzorgt het gedistribueerde binnen het programma. Dit zou zich in de kernel kunnen manifesteren door elk proces, naast zijn uniek proces-ID, ook van een host-variabele te voorzien die aanduidt op welke host dit proces momenteel actief is. Afhankelijk van de klasse waaronder het gedistribueerde programma onder te brengen is, zal de input replay-module anders moeten geconstrueerd zijn. In het eerste geval zal men eigenlijk een inter-proces replay-module dienen te construeren, terwijl het tweede geval een replay-module vereist die sterk de kernel manipuleert om het gedistribueerde karakter van betreffend programma perfect te replayen. De replay van gedistribueerde programma’s komt niet aan bod in deze scriptie.

Replay van sequenti¨ ele programma’s Een sequentiële programma-uitvoer ligt compleet vast door zijn code en invoerdata. Bijgevolg vereist een perfecte heruitvoering dat beide factoren constant blijven. Om de invoerdata onder verschillende heruitvoeringen gelijk te houden, moet men in input replay voorzien. Hierdoor zullen alle niet-deterministische elementen, die sequentiële programma’s kennen, geëlimineerd zijn. Merk op dat vele omgevingen sequentiële programma’s toelaten signalen te ontvangen wat tevens een bron van niet-determinisme vormt. De replay van deze signalen is echter onder te brengen bij replay van parallellisme.

Input replay en parallellisme Wanneer we een perfecte replay van parallelle programma’s wensen, zal het niet volstaan enkel de invoer van dit programma te replayen. Ons beperken tot input replay


6

zal namelijk het niet-determinisme binnen het programma, veroorzaakt door het parallellisme zelf, niet kunnen elimineren. Slechts indien we ook het parallellisme binnen dit programma replayen, zullen we een perfecte replay kunnen verzekeren. Wanneer we in een parallellismeconservatie voorzien, zal de input replay zelfs niet eens complexer moeten gebeuren dan bij sequentiële programma’s het geval was. Onder parallellismeconservatie zal het parallelle programma zich, ten aanzien van de input replay, namelijk als een fictief sequentieel programma voordoen. Dit houdt in dat de volgorde, waarin het parallelle programma om bepaalde invoer vraagt, tijdens de verschillende heruitvoeringen dezelfde blijft wanneer ook het parallellisme perfect gereplayet wordt. Elke aanvraag tot invoer door het parallelle programma zal hier gewoon een proces-ID als extra karakteristiek hebben. Merk op dat parallellismeconservatie eigenlijk zelfs niet vereist is om een perfecte input replay te kunnen verzekeren. We dienen namelijk slechts alle invoer, die het programma kent, te conserveren. De externe invoer wordt geconserveerd zoals bij sequentiële programma’s het geval is. Verder kent het parallelle programma ook nog niet-deterministische interne invoer. Deze vindt plaats tussen de verschillende threads van het programma langs de globale datastructuren. Deze interne invoer conserveren kan inderdaad worden bewerkstelligd via parallellismeconservatie, doch andere werkwijzen bestaan. Men spreekt in dit kader over ordering-based replay en content-based replay. Parallellismeconservatie valt onder ordering-based replay. Bij content-based replay-methoden zal men trachten de data-afhankelijkheden te conserveren. Hierdoor kan men ook het niet-determinisme binnen de interne invoer geheel elimineren. Een interessante methode die hieronder valt, associeert met elk data-object een versienummer. Elke schrijfoperatie verhoogt het versienummer van het betreffende data-object. Ook wordt het aantal leesoperaties van een bepaald data-object per versienummer bijgehouden. Tijdens de replay zal men elke leesoperatie ophouden tot wanneer het versienummer van het betreffend data-object overeenkomt met dat uit de record-fase. Ook wordt elke schrijfoperatie uitgesteld totdat het gewenste aantal leesoperaties voor het huidige versienummer van betreffende data-object bereikt is. De gekende methoden gebaseerd op content-based replay leveren allen een zeer slechte prestatie. In deze scriptie zullen dan ook enkel ordering-based replay-methoden worden behandeld.

1.4

Inhoud

In een volgend hoofdstuk zullen de verschillende aspecten worden besproken die bij een implementatie van input replay komen kijken. Hoofdstuk 3 handelt over het monitoren van een proces onder het besturingssysteem linux. Verder wordt in hoofdstuk 4 de implementatie van de replay-module onder linux besproken.

Hoofdstuk 2 Implementatie van Input Replay In dit hoofdstuk zullen aspecten van input replay met betrekking tot de implementatie worden besproken, echter zonder specifiek naar de geschreven implementatie onder linux te verwijzen.

2.1

Situering invoer

verwerking

uitvoer

(A)

invoer

verwerking

uitvoer

(B)

uitvoer

(C)

invoer bewaren invoer

verwerking

bewaarde invoer

Figuur 2.1: Invoer, verwerking en uitvoer Op bovenstaand schema (fig. 2.1 A) zien we hoe een programma van invoer wordt voorzien, die verwerkt en dit als uitvoer terug aan de gebruiker levert. De code van dit programma wijzigt gedurende verschillende uitvoeringen doorgaans niet; de invoer echter wel. Door deze laatste kan het programmaverloop en bijgevolg de uitvoer steeds een andere gedaante hebben. Wat we bij input replay wensen te bekomen, is het programma steeds van identiek dezelfde invoer te voorzien om zo het gedrag van dit proces beter te kunnen bestuderen. Om het programma van identiek dezelfde invoer te voorzien, dienen we eerst een bepaalde invoer van dit programma vast te leggen. Dit zal gebeuren in een eerste fase, de record-fase (zie fig. 2.1 B). Hierbij laten we het proces gewoon zijn werk verrichten waarbij we tevens de invoer aftappen en opslaan in een zogenaamd replay-bestand voor later gebruik. Dit alles is het werk van een tracer wat onderdeel is van de replay-module. In een volgende fase, de replay-fase, gaan we deze bewaarde invoer opnieuw gebruiken als effectieve invoer voor het programma. We laten hiertoe (zie fig. 2.1 C) het proces 7

HOOFDSTUK 2. IMPLEMENTATIE VAN INPUT REPLAY

8

gewoon lopen, maar blokkeren de normale invoerkanalen van dit proces en voorzien het van vervangende invoer die werd opgeslaan in de record-fase. Bovenstaande conceptuele schema’s, afgebeeld in fig. 2.1, zijn uiteraard slechts een zeer grove benadering en zullen vervolgens verder worden uitgewerkt. Een iets realistischere situatie —toegepast op het huidige model van besturingssystemen— vinden we terug in fig. 2.2. Hierbij gebeurt alle communicatie met de buitenwereld proces systeemoproep besturingssysteem systeemoproep proces

Figuur 2.2: Processen en het besturingssysteem steeds via het besturingssysteem. Zowel de in- als uitvoer van een bepaald programma zal via het besturingssysteem gebeuren. De zogenaamde systeemoproepen zijn hiertoe het medium. Via de systeemoproepen zal een bepaald proces zijn invoer achterhalen, deze bewerken en vervolgens opnieuw via systeemoproepen als uitvoer teruggeven aan de gebruiker. Wat een proces onder buitenwereld verstaat kan zijn: • een ander gebruikersproces binnen dezelfde machine • een deel van het besturingssysteem zelf (bestandsinvoer en -uitvoer) • een proces op een andere machine (netwerkinvoer en -uitvoer) Het is belangrijk hierbij op te merken dat elke vorm van communicatie met een ander proces steeds via de systeemoproepen van het besturingssysteem zelf gaat. Om de invoer in de record-fase op te nemen, zullen concreter deze systeemoproepen worden afgetapt. Vervolgens dienen we in de replay-fase de systeemoproepen parametrisch te wijzigen opdat ze zich, voor het te replayen proces, identiek zouden gedragen als in de record-fase.

2.2

Behoud van het systeemoproep-patroon

Teneinde de replay-fase tot een goed einde te brengen, zullen we er verzekerd moeten van zijn dat het patroon, waarmee het proces in de record-fase systeemoproepen uitvoert, identiek is in de replay-fase. Behoud van het systeemoproep-patroon is bijgevolg een zeer belangrijk aspect van input replay.


9

Wanneer hieraan niet voldaan wordt, komt een correcte replay in het gedrang. Onderstel namelijk het volgende geval: Een proces in de record-fase haalt via een systeemoproep slechts éénmaal een byte op. Vervolgens beslist dit proces in de replay-fase om ditmaal via twee systeemoproepen twee bytes op te halen. Wat dienen we deze tweede systeemoproep dan te laten teruggeven? In de record-fase hebben we namelijk slechts één enkele byte opgeslaan om in de replay-fase als invoer te gebruiken. Die tweede byte improviseren is niet echt meer replayen. Indien we op zó een punt komen in de replay-fase, moeten we de replay van de invoer bijgevolg stopzetten. We kunnen immers niet meer verzekeren dat het proces een perfecte replay doormaakt. De replay heet dan onhoudbaar. In zo’n geval koppelen we de tracer los van het proces. Dit proces laten we vervolgens weer zijn gewone invoer aannemen, in geval dit uiteraard nog enigszins mogelijk is.

2.3

Procescommunicatie

Uit voorgaande stellen we vast dat er heel wat problemen kunnen optreden bij input replay. Deze problemen zijn te wijten aan communicatieproblemen die het proces kent. In deze sectie gaan we de procescommunicatie dan ook eens nader bestuderen. Er zijn twee grote klassen van communicatie mogelijk: externe en interne communicatie. Deze zullen in de volgende subsecties worden toegelicht.

Externe procescommunicatie Deze vorm is de normale vorm van communicatie1 . Hierbij zal een proces (zie fig. 2.2) via de systeemoproepen met een ander proces gaan communiceren. Dit proces kan op de lokale machine draaien, maar het kan ook dat dit proces op een andere machine draait die via een netwerk in verbinding staat. Het feit of dit andere proces al dan niet ook lokaal draait, maakt voor het te replayen proces eigenlijk weinig uit; het is gewoon een andere vorm van invoer/uitvoer, maar het is en blijft óók invoer/uitvoer. De meeste besturingssystemen zorgen zelfs voor een transparant gebruik van netwerkcommunicatie met een ander proces. Concreter gaat men hiertoe doorgaans een connectie naar communicatiemogendheden via descriptoren tot stand brengen. Vervolgens worden met behulp van deze descriptoren algemene systeemoproepen aangewend om in de eigenlijke in- en uitvoer te voorzien. Onder linux bijvoorbeeld aanvaarden de systeemoproepen read, write en close descriptoren van zowel bestanden als netwerkconnecties.

Interne procescommunicatie Deze klasse van communicatie kan voor veel problemen zorgen indien we de externe procescommunicatie exact wensen te replayen. Figuur 2.3 zal deze vorm van commu1

Verwar dit niet met SYSV IPC, wat slechts een deel uitmaakt van de externe procescommunicatie.


10

nicatie trachten te verduidelijken én ook waarom deze vorm de externe communicatie kan be¨ınvloeden. proces data thread 1

thread 2 systeemoproepen

besturingssysteem

Figuur 2.3: Meerdere threads binnen een proces Stel dat een proces meerdere threads heeft draaien binnen één en dezelfde geheugenruimte. In dit geval zullen deze verschillende threads allen dezelfde globale datastructuren kunnen gebruiken en wijzigen. Zoals gekend kan dit leiden tot race-condities [9]. De meest gekende race-conditie is die waarbij twee threads een teller, die voorheen op nul stond, trachten te verhogen. Dit zal vaak tot een waarde 2 voor de teller leiden, maar in geval van races ook tot waarde 1. Dit is te wijten aan het mogelijk niet-atomisch zijn van een increment-statement waarmee elk van deze threads de teller wensen te verhogen. Zo een increment-statement werkt doorgaans in twee stappen. In een eerste stap zal dit statement de oude waarde van de teller uit het geheugen lezen. In een tweede stap zal deze de zonet gelezen waarde met één verhogen en opnieuw wegschrijven naar het geheugen. Indien nu de eerste thread door het besturingssysteem, na het lezen van de teller, wordt onderbroken ten voordele van de tweede thread, zullen ze beiden de waarde nul uit de betreffende teller lezen. Vervolgens zullen beide threads deze met één verhogen en terug wegschrijven naar het geheugen. Dit zal resulteren in een teller met waarde 1 in plaats van de gewenste waarde 2. Als het proces (dit is één der threads) deze teller nu aanwendt als aantal te plegen systeemoproepen, dan zal dit ertoe leiden dat in sommige gevallen 2 systeemoproepen zullen plaatsvinden en in andere gevallen slechts 1 systeemoproep. Bovenstaande situatie kan bijgevolg leiden tot het verbreken van het systeemoproeppatroon (zie sectie 2.2), wat de replay onhoudbaar maakt. Belangrijk hierbij op te merken is, dat het correct gebruik van mutexes en andere lock-methoden hieraan geen uitkomst biedt. Een lock op een variabel zal er weliswaar voor zorgen dat de data die deze lock dient te beschermen consistent blijft, maar het verkrijgen van deze lock zélf is nog steeds een niet-deterministisch element. En indien het proces, afhankelijk van het verkrijgen van deze lock (wat een vrij raar gedrag zou te noemen zijn), een systeemoproep al dan niet doorvoert, dan zullen we opnieuw het systeemoproep-patroon mogelijk verbreken. Bovenstaande gevallen zijn doorgaans toe te schrijven aan de scheduler van het besturingssysteem die zich nooit hetzelfde zal gedragen in replay- als in record-fase. Doordat de scheduling tussen de verschillende concurrerende threads binnen het proces steeds verschilt, zal het verkrijgen van locks (of de toegang tot onbeschermde data) steeds een

11


element van willekeur zijn. Aan dit probleem is eventueel te verhelpen door —vanaf het moment dat een proces meerdere threads heeft— de inter-thread scheduling van het proces zelf ook op te slaan om deze later in de replay-fase ook te kunnen replayen. Merk op dat dit enkel zinvol is indien het proces meerdere threads heeft. Wanneer er slechts één enkele thread binnen het proces draait, hebben we uiteraard ook taakwisselingen (deze zijn er steeds bij een preëmptive kernel, zoals alle huidige besturingssystemen geconstrueerd zijn) maar het proces wordt hierdoor niet be¨ınvloed. Dus slechts bij meerdere threads binnen éénzelfde proces dienen we de scheduling op te slaan. En wel enkel dit deel van de scheduling die verantwoordelijk is voor de vreemde situaties zoals hierboven beschreven staan. Zo zal thread 1 thread 2 proces 1 proces 2

t1

t2

t3

t4

t5

t6

t7

t8

tijd

thread 1

Figuur 2.4: Een scheduling-schema bij twee processen voor het scheduling-schema uit fig. 2.4 slechts de scheduling-informatie op tijdstippen t1 , t2 , t4 , t7 en t8 dienen te worden bijgehouden. De informatie uit t5 is nutteloos. Hier vindt weliswaar een taakwisseling naar proces 2 plaats, maar bij terugkeer naar proces 1 is het toch opnieuw zijn eerste thread die aan de beurt komt. Dus voor proces 1 is het dan alsof er niets is gewijzigd aan de situatie, althans voor wat de scheduling betreft. Bij multi-processor systemen zal men de scheduler extra restricties opleggen om bovenstaande voorgestelde werkwijze te kunnen hanteren: Threads van éénzelfde proces mogen nooit tegelijk op verschillende processoren actief zijn. Indien dit wel het geval zou zijn, dan volstaat het niet om enkel de scheduling te conserveren om het parallellisme correct te kunnen replayen. Het parallellisme bezit dan namelijk een veel fijnere granulariteit dan gedicteerd door de scheduler. In dit geval zouden we het gehele proces in single step modus moeten laten draaien, om zo exact de volgorde te weten waarin alle threads van het proces hun instructies uitvoeren. Een parallellisme-conservatie aan de hand van single step modus levert echter een zeer slechte prestatie, meer hierover onder Prestatie op pagina 31. De meest voor de hand liggende oplossing hiervoor bestaat erin de uitvoering van een proces (met al zijn threads) te beperken tot één enkele processor. Dit is uiteraard enkel vereist voor processen die we tracen in een record-fase. De scheduler moet zich dus, in geval van recording van een bepaald proces, voor dit proces tot één enkele processor beperken. Wanneer de scheduler zich niet aan de bovenstaande regel houdt, zullen we andere record-methoden voor de scheduling-conservatie moeten bedenken. Merk hierbij op dat het mogelijk is dat we door die scheduler-restrictie het betreffend proces zullen be¨ınvloeden en zó mogelijke niet-deterministische fouten de kans laten zich al dan niet te manifesteren. De be¨ınvloeding, door het proces in single step modus te laten draaien, is echter nog groter. Meer hierover vindt men onder Heisenbugs, paragraaf 2.8.3 op pagina 21.


12

Het opslaan van het scheduling-patroon is een quasi onbegonnen werk. Men zou hiertoe in de diepste lagen van de kernel moeten controleren wanneer thread-scheduling plaatsvindt. Als het dan een scheduling betreft van het te recorden proces, dan moet het exacte moment waarop dit gebeurt worden opgeslaan. Dit exacte moment opslaan kan gebeuren door het bijhouden van de waarde van het instructiewijzerregister én het aantal keren dat de betreffende instructie reeds werd uitgevoerd. Dit laatste is nodig daar een instructie in een lus meerdere malen wordt uitgevoerd en in een functie meerder malen kan worden uitgevoerd. Tussen de verschillende uitvoeringen dienen we dan ook een onderscheid te kunnen maken. Het aantal uitvoeringen van een instructie op een bepaald geheugenadres kan op verschillende manieren worden achterhaald. De meeste processoren bieden de mogelijkheid hardware-matig het totale aantal uitgevoerde instructies bij te houden. Wanneer er echter geen hardware-oplossing beschikbaar is, zullen we ons moeten beroepen op een software-matige aanpak van het probleem. Hierbij wordt een SIC of Software Instruction Counter geconstrueerd. Deze teller laat toe exact te bepalen waar we ons in de uitvoering van een bepaald programma precies bevinden. Dit houdt in dat we het aantal uitvoeringen van een huidige instructie steeds kunnen achterhalen. Belangrijk hierbij op te merken is dat dit aantal uitvoeringen steeds bepaald wordt door het aantal achterwaartse sprongen dat het programma reeds genomen heeft. Een instructie kan namelijk slechts meerdere malen worden uitgevoerd indien er een achterwaartse sprong genomen werd. Bijgevolg volstaat het enkel de achterwaartse instructies in een programma te instrumenteren om een SIC te construeren. Dat we hierbij de basisblokken van een programma ongemoeid kunnen laten, zal sterk tot de minimale overhead van de SIC bijdragen [5]. Het enige nadeel van een software-oplossing is uiteraard dat we de code van het programma en van alle gebruikte bibliotheken dienen te instrumenteren. Bijgevolg is een hardware-oplossing meer gewenst. Het replayen van de scheduling kan op verschillende manieren gebeuren. Zo zouden we het bewaarde scheduling-patroon kunnen replayen door op de gepaste plaatsen, vóo´rdat we de replay aanvangen, breakpoints te plaatsen. Hierop kan de scheduler zich baseren om gepast tussen de threads van betreffend proces te wisselen, dit uiteraard naast de taakwisselingen die moeten gebeuren voor de overige processen binnen het systeem. De scheduler mag een dergelijke taakwissel slechts laten plaatsvinden wanneer het opgeslane uitvoeringsgetal van betreffende instructie overeenkomt met het aantal keren dat de breakpoint reeds werd bereikt. Verder dient te worden opgemerkt dat bij het gebruik van breakpoints de code van het proces zelf moet worden gewijzigd. Op sommige architecturen kan dit tot conflicten met de instructie-cache leiden. De replay-module, voor deze thesis ontwikkeld, ondersteunt meerdere threads niet qua scheduling-conservatie. Dit wil echter niet zeggen dat een proces met meerdere threads niet kan worden gereplayet. Wel is het zó dat het systeemoproep-patroon sneller zal worden doorbroken dan in het geval de scheduling zelf ook zou worden geconserveerd in de replay-fase.

2.4

Andere communicatie

Naast de communicatie via de systeemoproepen kan een proces nog enkele andere resources aanspreken om een bepaalde vorm van input (en/of output) te bekomen.


13

Deze verschillende resources zullen hier worden besproken.

I/O-poorten Stel dat een proces zeer low-level gaat qua programmering van de randapparaten, dan zal het beroep doen op de input/output-poorten. Hierbij kan het leesresultaat van deze poorten in de replay-fase verschillen van deze uit de record-fase. In geval er een afhankelijkheid bestaat met het systeemoproep-patroon, kan deze laatste opnieuw worden verbroken. Dit zal opnieuw leiden tot onhoudbare replay-situaties. Zo een afhankelijkheid is in volgend programma ingebouwd. ; Port system call dependency demo. (linux) ; The Netwide Assembler NASM 0.98 section .data msg db "Hello World!", 0x0a msg_size equ $ - msg PORT

equ

section .text global _start: mov mov mov mov int

0x80

_start

; ELF entry point

eax, ebx, ecx, edx, 0x80

; ; ; ; ;

ioperm from num turn_on kernel call

; ; ; ; ;

write fd = stdout, and error code 1 on .exit buffer ptr buffer size kernel call

101 PORT 1 1

in xor and jz

al, PORT ebx, ebx eax, 1 .exit

mov mov mov mov int


mov int

eax, 1 0x80

4 1 msg msg_size

.exit: ; exit, ebx = exit code ; kernel call

end

Dit programma leest een bepaalde I/O-poort (0x80) en zal afhankelijk van de bekomen waarde al dan niet “Hello World!” op de console afprinten. Verschillende oplossingsmethoden zijn te bedenken om aan dergelijke afhankelijke opstellingen het hoofd te bieden. Deze worden hieronder kort besproken.


14

• Blokkeren van de I/O-poorten. Zowel in de record- als in de replay-fase kunnen we gewoonweg het proces de toegang tot de poorten ontzeggen. Uiteraard is dit niet echt een zeer zinvolle methode te noemen. Het probleem is niet echt opgelost door het proces in de record-fase restricties op te leggen (Heisenbugs). • Monitoren van de I/O-poorten. Sommige processoren zijn van de functionaliteit voorzien dat er bij poorttoegang door een bepaald proces een exceptie kan worden gegenereerd. We zouden via een aangepaste exceptie-handler dan het resultaat van de poorttoegang in de recordfase kunnen opslaan en deze in de replay-fase terug in het proces injecteren. In de replay-module, ontwikkeld bij deze thesis, werd deze vorm van communicatie ongemoeid gelaten met uiteraard alle mogelijke gevolgen vandien.

I/O-geheugen Indien een I/O-geheugenblok gemapt is in de geheugenruimte van het proces dat we wensen te replayen, zullen we analoge maatregelen dienen te treffen zoals bij I/Opoorten. Hierbij zetten we de geheugenprotectiebits in het paging-subsysteem zodanig dat bij elke toegang tot de I/O-geheugengebieden opnieuw een exceptie wordt gegenereerd. Via een aangepaste exceptie-handler kunnen we vervolgens de nodige data in de record-fase opslaan en in de replay-fase deze data terug injecteren in het proces. In de replay-module, ontwikkeld bij deze thesis, werd deze vorm van communicatie ongemoeid gelaten met uiteraard alle mogelijke gevolgen vandien.

De processor Sommige processoren kunnen zelf ook voorzien in data die steeds verschillend is en moeilijk te replayen. Zo bevat de Intel Pentium processorklasse een time-stamp counter [3] dewelke elke klokpuls met één wordt verhoogd. Een proces kan deze teller lezen via de instructie RDTSC die de huidige time-stamp counter in EDX:EAX wegschrijft. Ook hier kan een proces zijn systeemoproep-patroon in de replay-fase verbreken door zich afhankelijk van deze waarde op te stellen. Zo een opstelling is hieronder weergegeven. ; Time-stamp counter system call dependency demo. (linux) ; The Netwide Assembler NASM 0.98 section .data msg db "Hello World!", 0x0a msg_size equ $ - msg section .text global _start: rdtsc xor

_start

; ELF entry point ; tsc -> edx:eax

ebx, ebx

HOOFDSTUK 2. IMPLEMENTATIE VAN INPUT REPLAY and jz

eax, 1 .exit

mov mov mov mov int


mov int

eax, 1 0x80

4 1 msg msg_size

; ; ; ; ;

15

write stdout buffer buffer size kernel call

.exit: ; exit, ebx = exit code ; kernel call

end

Dit programma leest de time-stamp counter (van de huidige processor) en zal afhankelijk van de bekomen waarde al dan niet de zin “Hello World!” op de console afprinten. Het probleem dat zich in bovenstaande code manifesteert, is op te lossen door de timestamp disable (TSD) flag in het register CR4 te zetten. Hierdoor zal het programma, bij het opvragen van de time-stamp counter, een #GP exceptie opwerpen. In de exceptiehandler (die op kernel-niveau draait) kunnen we vervolgens kijken of de instructie die de fout veroorzaakte wel degelijk een RDTSC was. Indien dit het geval is, moeten we een speciale afhandeling voorzien: • In de record-fase zullen we de time-stamp counter effectief lezen door zelf een RDTSC uit te voeren. Vervolgens gaan we het resultaat hiervan in het replaybestand opslaan en dit tevens injecteren in EDX:EAX van het betreffende proces. • In de replay-fase zullen we de time-stamp counter, die in de record-fase werd opgeslaan, terug in EDX:EAX injecteren. In de replay-module, ontwikkeld bij deze thesis, werd bovenstaande niet ge¨ımplementeerd daar dit diepgaande wijzigingen van de kernel zou vereisen. Naast deze time-stamp counter heeft elke processorklasse van Intel steeds wel enkele extra registers die voor dergelijke ongemakken kunnen zorgen. Indien elk van deze registers via een #GP te beschermen is, kunnen we steeds de werkwijze, zoals hierboven beschreven staat, hanteren om ook de instructies die betrekking hebben op deze registers te kunnen replayen. Het zou wel vrij veel werk vergen om alle references van Intel te gaan lezen, speurend naar dergelijke registers en hiervoor dan steeds oplossingen te bedenken. De behandeling van de time-stamp counter diende dan ook slechts als voorbeeld om te duiden op het feit dat de processor zelf ook een bron van niet-determinisme kan zijn.

2.5

Parti¨ ele uitvoer

In de replay-fase gaan we, zoals reeds uit fig. 2.1 (p. 7) blijkt, de echte invoer blokkeren en het proces voorzien van tevoren opgeslane invoer. Er is echter nog niets vermeld omtrent de uitvoer en we hebben impliciet aangenomen dat deze in de replay-fase ook

16


gewoon zijn taak blijft doen, daar we aan een “blackbox-proces” niets hebben. Dit is niet steeds gewenst. Via een voorbeeld trachten we dit te verduidelijken. Stel dat het betreffende proces als één van zijn uitvoeroperaties een INSERT in een tabel uit een databank doorvoert. Eén van de basisregels voor relationele databanken eist dat elke rij binnen een bepaalde tabel (relatie) uniek dient te zijn. Indien nu dit programma in zijn record-fase deze rij reeds wegschreef, is het ongewenst dat dit in de replay-fase nog eens zou gebeuren. Dit zou namelijk leiden tot een inconsistente databank. Om nog een voorbeeld aan te halen: Stel dat we via de replay-module een bepaald proces wensen te debuggen. Dit proces heeft in de record-fase een robotarm, die via het netwerk wordt bestuurd, laten crashen. Nu is het zo dat we in de replay-fase —waarin we dit proces gaan bestuderen om te kijken waar het fout liep— die robotarm niet opnieuw willen laten crashen. In dit voorbeeld is het vereist dat we de netwerkuitvoer kunnen blokkeren tijdens de replay-fase. We dienen bijgevolg over de mogelijkheid te beschikken om de uitvoer gedeeltelijk te blokkeren (zie fig. 2.5). invoer

verwerking

uitvoer

bewaarde invoer

Figuur 2.5: Partiële uitvoer Concreet moeten systeemoproepen die instaan voor de uitvoer in de replay-fase van instelbare permeabiliteit worden voorzien en dit voor uitvoer die tot inconsistenties kan leiden of onomkeerbare gevolgen met zich meedraagt.

2.6

Parti¨ ele invoer

Analoog kunnen we tijdens de replay-fase ook de invoer mogelijk uit de oorspronkelijke resources wensen te halen in plaats van uit het replay-bestand zelf. De reden hiertoe verschilt wel van die bij de partiële uitvoer. Bij de invoer zouden we dit namelijk toelaten om de grootte van het replay-bestand enigszins beperkt te houden. Wat we namelijk kunnen terughalen uit de originele systeembronnen, dienen we in de recordfase niet op te slaan in het replay-bestand. Dit kan heel wat plaats uitsparen. De voorwaarde hiertoe is echter wel dat deze systeembronnen ook in de replay-fase aanwezig dienen te zijn en tevens ongewijzigd. De aanwezigheid kunnen we vrij makkelijk achterhalen in de replay-fase. Het al dan niet gewijzigd zijn, is daarentegen niet te achterhalen daar de originele inhoud niet werd opgeslaan om plaats te besparen. Die inhoud wel opslaan, louter en alleen om te kunnen verificeren, is vrij banaal omdat we hierdoor opnieuw ons replay-bestand laten uitzetten in grootte. Wat eventueel wel kan, is een checksum of een CRC-32 opslaan ter verificatie. Toch kan het —met het oog op het debuggen van een bepaald proces— soms handig zijn dat men een bepaalde vorm van input toelaat om tijdens de replay-fase anders te zijn. Zo kan men het gedrag van het proces op de wijziging van deze ene invoerstroom bestuderen. Ook hiervoor zou men partiële invoer kunnen appreciëren.


17

Verder valt op te merken dat verschillende types van invoer onder deze partiële herbruikbaarheid kunnen vallen. Zo kent linux (onder andere) bestandsinvoer, bestandsmapping en netwerkinvoer.

2.7

Procescontext

Belangrijk bij input replay is ook het geheel eens te bekijken in functie van de procescontext. Elk proces bezit in wezen twee verschillende “contexten”. Zo is er de context in user mode en de context in kernel mode. Deze twee zullen in volgende subsecties worden behandeld.

User mode context Deze context omvat hoofdzakelijk de inhoud van de algemene registers van het proces, alsook enkele registers met betrekking tot de geheugentoegang. Het is deze context die de scheduler bij elke taakwisseling dient op te slaan en naderhand te herstellen, opdat het proces zonder problemen zou kunnen verder werken. Onder deze categorie vallen ook de registers van additionele verwerkingseenheden zoals co-processoren. Deze registers worden door de meeste schedulers (zoals die van linux) slechts opgeslaan indien de betreffende functionele eenheid ook effectief door het proces wordt gebruikt. Wanneer we een exacte replay wensen, dewelke algoritmisch aan de hand van het systeemoproep-patroon makkelijk te verificeren is, zal de user mode context van betreffend proces tijdens elke systeemoproep in replay-fase gelijk moeten zijn aan de context zoals die was in record-fase.

Kernel mode context Deze context is voor het proces niet onmiddellijk zichtbaar (wat de naam reeds deed vermoeden). Toch is deze vorm van procescontext van een niet te onderschatten belang voor het correct replayen van een proces. Dit zal worden verduidelijkt aan de hand van een voorbeeld. Indien een proces extra geheugen wenst om bepaalde datastructuren te stockeren, zal dit doorgaans gebeuren via een systeemoproep naar de kernel toe. De kernel zal hierop (hopelijk) reageren door in het geheugengebied van betreffend proces een blok nieuw geheugen te mappen. De effectieve implementatie hiervan doet er niet echt toe. Wat wel belangrijk is: een geheugengebied dient eerst door de kernel te worden gemapt vooraleer het door het user-proces kan worden gebruikt. Als het proces ongemapt geheugen gaat adresseren, zal de kernel doorgaans een exceptie genereren en het proces beëindigen onder een segmentatiefout. In de replay-fase zullen we de systeemoproep, die instaat voor het mappen van geheugen, opnieuw zijn werk moeten laten doen. Anders zal het proces, ondanks de aanvraag tot mappen van een nieuw geheugengebied, een geheugenfout maken bij toegang tot dit geheugen. Dit daar de gepaste kernel-datastructuren, die instaan voor het mappen van geheugengebieden, niet werden aangemaakt. Meer zelfs, we dienen de kernel duidelijk


18

te maken dat we exact dezelfde geheugen-mapping wensen. Maar is ditzelfde geheugengebied nog wel beschikbaar in de replay-fase? Misschien heeft een ander proces dit vóo´r ons reeds opgeëist2 . Uiteraard is dit, zoals reeds vermeld, sterk afhankelijk van de implementatie van de geheugentoekenner die in de kernel werd voorzien. Linux laat ons toe om aan bovenstaand probleem op een vrij makkelijke manier het hoofd te bieden. Algemeen kan men stellen dat resource-allocaties die, indien niet doorgevoerd tijdens de replay-fase, tot excepties kunnen leiden dus wel dienen te worden volbracht tijdens de replay. Een belangrijke opmerking hierbij is dat een perfecte replay van het proces daarom niet onmiddellijk een perfect dezelfde kernel mode context vereist. Bij replay moet enkel de user mode context exact dezelfde zijn als in de record-fase. Merk echter op dat het proces in de replay-fase denkt dat het van exact dezelfde kernel mode context is voorzien. We zullen dus, tijdens de replay, dienen te mappen tussen wat het proces denkt als kernel context te hebben én de effectieve replay-kernel context.

2.8

Recording

In deze sectie gaan we na wat er zoal in de record-fase moet worden opgeslaan. Uiteraard zal dit niet méér zijn dan nodig is om in de replay-fase het systeemoproep-patroon niet te doorbreken, daar dit het enige algoritmische criterium vormt tot een correcte replay. De systeemoproepen vormen dé manier om een proces van invoer te voorzien. Het zijn het dan ook datastromen uit deze systeemoproepen die we zullen opslaan in het replay-bestand. Om het replay-bestand in de record-fase zo efficiënt mogelijk te kunnen construeren, zullen we eerst en vooral de systeemoproepen in hun verschillende klassen onderverdelen.

2.8.1

Klassen van systeemoproepen

De systeemoproepen van alle doorsnee besturingssystemen3 die heden beschikbaar zijn, zijn in 3 categorieën onder te verdelen. Ze zijn hieronder weergegeven. 1. Systeemoproepen die enkel een return code weergeven. De systeemoproepen van de meeste besturingssystemen leveren stééds een return code terug, ter aanduiding van het al dan niet lukken van de gevraagde systeemoperatie. Nu is het zo dat sommige systeemoproepen verder niets anders terugleveren, waardoor ze in deze categorie zijn onder te brengen. 2. Systeemoproepen die een gekend geheugengebied teruggeven aan het user proces, meestal naast het leveren van een return code. De geheugengebieden die deze 2

Dit andere proces zou de tracer kunnen zijn indien de replay-module zodanig geconstrueerd is dat het te tracen proces en de tracer in éénzelfde virtuele adresruimte worden uitgevoerd. 3 Voornamelijk de UNIX-varianten duid ik hier.


19

klasse van systeemoproepen mogen wijzigen, worden doorgaans als parameters aan de systeemoproep doorgespeeld. Deze klasse is er, daar niet steeds alle terug te geven informatie in de return code past. Dit doordat de return code slechts één machinewoord in beslag neemt. Dus zullen de systeemoproepen uit deze klasse, naast de return code, ook nog enkele datastructuren in het geheugengebied van het betreffend proces opvullen. 3. Systeemoproepen die een ongekend geheugengebied van het user proces overschrijven. Men zou kunnen stellen dat deze klasse niet kan bestaan. En dit is ook zo, een user proces weet steeds wel waar de systeemoproep ergens data zal wegschrijven. Indien dit niet het geval zou zijn, is deze systeemoproep zeer gevaarlijk en zal bijgevolg nooit worden opgeroepen door deftige programma’s. Wat we onder deze klasse onderbrengen zijn weliswaar stabiele systeemoproepen, maar het is, in de record-fase, moeilijk te achterhalen waar deze systeemoproepen precies data wegschrijven. Hieronder vallen uitbreidbare systeemoproepen zoals ioctl. Elke driver is in staat zijn eigen ioctl-extensie te definiëren. Bijgevolg zouden we voor elke driver die bestaat de geheugen-blueprint van dergelijke systeemoproepen dienen te bepalen, om deze onder de tweede categorie systeemoproepen te kunnen onderbrengen. De gedachte alleen al is absurd te noemen. Elk van deze klassen kunnen nog eens opgedeeld worden in twee subklassen, naargelang we in replay-fase de systeemoproepen ook effectief laten doorvoeren, of deze slechts gaan faken (zie partiële invoer/uitvoer, secties 2.6 en 2.5). Dit betreft de zogenaamde permeabiliteitseigenschappen van systeemoproepen tijdens de replay-fase. (Meer hierover op p. 24). We zullen voor elk van deze klassen systeemoproepen vervolgens de methode(n) geven waarmee we deze dienen te bewaren om ze, later in de replay-fase, exact te kunnen afspelen.

2.8.2

Het opslaan van de replay-data

Return codes Voor alle drie de klassen —beschreven in paragraaf 2.8.1— moeten we steeds de return codes opslaan. Dit houdt niet méér in dan net ná de systeemoproep, nog vóór de terugkeer naar user mode, de inhoud van het register waarlangs de return code aan het proces wordt afgeleverd, op te slaan in ons replay-bestand. De manier waarop dit praktisch gebeurt, is sterk afhankelijk van het gebruikte besturingssysteem. Dit zal pas in een later hoofdstuk, wanneer de implementatie van de replay-module wordt besproken, aan bod komen. Gekende geheugengebieden De tweede klasse systeemoproepen (zie 2.8.1) vereist dat het geheugengebied4 , weggeschreven door de systeemoproep, net vóór terugkeer naar het user proces wordt opge4

Deze kan meerdere blokken omvatten.


20

slaan in het replay-bestand. Merk wel dat we dit niet zullen doen indien we de input partieel wensen door te laten in de replay-fase. Uit partiële input, sectie 2.6, blijkt dat het net de bedoeling was deze data niet meer in het replay-bestand te moeten opnemen om zo tot kleinere replay-bestanden te komen. In dit geval zullen we in de replay-fase de systeemoproep zelf de data moeten laten genereren. Ongekende geheugengebieden De derde klasse systeemoproepen kan zich op verschillende manier laten behandelen. • De meest makkelijk methode bestaat erin om het gehele geheugengebied van het proces net ná de systeemoproep, nog vóo´r terugkeer naar het proces zelf, op te slaan in het replay-bestand. Uiteraard is dit een plaatsverkwistende methode daar een systeemoproep doorgaans slechts een beperkt deel van het user geheugen wijzigt. • Een tweede methode bestaat erin om net vóór de systeemoproep een kopie van de gehele geheugenruimte van betreffend proces te maken. Na de systeemoproep kunnen we vervolgens de opgeslane geheugenruimte vergelijken met de actuele geheugenruimte van het proces en zo enkel de wijziging(en) opslaan die de systeemoproep veroorzaakte. Deze methode heeft als voordeel dat we het replay-bestand veel kleiner kunnen houden door enkel de geheugenwijzigingen, gemaakt door de systeemoproepen, te bewaren. Aan deze methode zijn echter enkele nadelen verbonden. We dienen namelijk een gehele kopie te maken van de geheugenruimte van het proces, wat enorm veel geheugen zal verspillen. Dit kunnen we enigszins beperken door het COW (copyon-write) paradigma toe te passen en dus vóo´r de systeemoproep de protectie van alle pagina’s van betreffend proces op read-only te zetten. Uiteraard vereist dit tamelijk diepgaande wijzigingen in het geheugenbeheer van dit proces. Wanneer nu de systeemoproep tijdens zijn uitvoer een bepaalde pagina wijzigt, zal dit een pagineringsfout veroorzaken. Hierop kunnen we de exceptie-handler de originele pagina naar een tijdelijke buffer laten kopiëren en de pagina van het proces zijn normale protectie teruggeven. Na de systeemoproep moeten we nu slechts de pagina’s in de buffer vergelijken met de overeenkomstige pagina’s uit de actuele geheugenruimte van betreffend proces. Maar dit vergelijken zal nog steeds in lineaire tijd gebeuren en is bijgevolg niet echt snel. Verder dienen we er waakzaam voor te zijn dat die paginaprotectieflags niet reeds door een ander subsysteem van de kernel worden gebruikt (fork onder linux bijvoorbeeld past ook COW toe). • Een laatste methode —dewelke ook werd ge¨ımplementeerd voor de replay-module bij deze thesis— zal de systeemoproepen zelf als het ware gaan instrumenteren. Telkens een systeemoproep een schrijfoperatie uitvoert in de geheugenruimte van betreffend proces, zal deze het adres en de grootte van de weggeschreven data toevoegen aan een gelinkte lijst. Deze gelinkte lijst maakt onderdeel uit van de kernel proces context (zie sectie 2.7 p. 17). In fig. 2.6 staat deze methode afgebeeld. Elke schrijfoperatie uitbreiden met het bijhouden van het adres en de hoeveelheid weggeschreven data in een gelinkte lijst lijkt een vrij belastende operatie.


21

proces kernel mode context

user mode context user data geheugen

user code geheugen

schrijfoperatie

systeemoproep

oproepverdeler kernel

Figuur 2.6: Schrijfoperaties instrumenteren Het alternatief echter —het lineair vergelijken van geheugengebieden— biedt een veel mindere prestatie. Verder zullen doorgaans de meeste systeemoproepen van de huidige besturingssystemen steeds een gehele blok data wegschrijven in één enkele operatie. Hierdoor zal de overhead, veroorzaakt door het opbouwen van deze gelinkte lijst, miniem zijn. Indien we dit mechanisme slechts in werking stellen wanneer we een proces wensen te tracen in een record-fase, kunnen we dit systeem vast in een bepaalde kernel configureren zonder globaal prestatieverlies. Wel zal men hiertoe de kernel moeten uitbreiden en dit op twee vlakken: – Elke schrijfoperatie dient te worden ge¨ınstrumenteerd om een element aan de gelinkte lijst toe te voegen. – Om de informatie, opgeslaan in deze gelinkte lijst, te kunnen opvragen en bewerken, wordt een systeemoproep voorzien (of een bestaande uitgebreid). Merk verder op dat we deze gelinkte lijst in de kernel context van dit proces laten huizen en niet in de user context zelf. We wensen immers het proces tijdens het tracen zo weinig mogelijk te be¨ınvloeden.

2.8.3

Heisenbugs

Zoals bij elk algoritme het geval is, zullen we ook bij tracing in de record-fase worden geconfronteerd met bepaalde bugs. De zogenaamde Heisenbugs vormen een voorname categorie. Een Heisenbug is als volgt gedefinieerd: [from Heisenberg’s Uncertainty Principle in quantum physics] A bug that disappears or alters its behavior when one attempts to probe or isolate it. (This usage is not even particularly fanciful; the use of a debugger sometimes alters a program’s operating environment significantly enough


22

that buggy code, such as that which relies on the values of uninitialized memory, behaves quite differently.) Bovenstaande klasse bugs werden Heisenbugs genoemd naar een zekere Werner Heisenberg dewelke in 1927 reeds iets gelijkaardigs formuleerde voor de quantumtheorie. Hij stelde namelijk dat het onmogelijk is gelijktijdig plaats en impuls exact te bepalen. Dit door het feit dat bij een plaatsbepaling gebruik gemaakt wordt van fotonen. Deze zullen bij impact op het waar te nemen object de impuls van dit object be¨ınvloeden. Anders geformuleerd: door waar te nemen zal men be¨ınvloeden. En het is deze laatste formulering die rechtstreeks over te dragen is op het tracen in de record-fase. Men zal namelijk door het tracen het betreffend proces al dan niet rechtstreeks of onrechtstreeks gaan be¨ınvloeden. Dit kan zelfs zodanige proporties aannemen dat het zich in de replayfase manifesteert als een doorbreking van het systeemoproep-patroon. Heisenbugs ontstaan doordat de tracer zelf een bepaalde impact heeft op het systeem waarop deze actief is. Deze tracer kan in record-fase namelijk twee factoren gaan be¨ınvloeden, zijnde: • be¨ınvloeding van de tijd Concreter zal men de uitvoersnelheid van het proces gaan be¨ınvloeden daar het tracen zelf een deel van de beschikbare processortijd zal opeisen. Men dient namelijk na elke systeemoproep het proces te inspecteren. Er volgt een voorbeeld hoe dit het proces, dat men tracet, kan be¨ınvloeden. Stel dat het betreffend proces een connectie opzet met een server via een netwerk. Dit zal steeds via een bepaald protocol gebeuren. Daar de meeste protocols timeouts kennen, om aan oneindige wachttijden het hoofd te bieden, zal het proces binnen deze time-out-intervallen dienen te opereren. Het tracen zou nu zodanig belastend kunnen zijn voor het systeem, dat deze time-out-limieten tijdens de record-fase net niet meer gehaald kunnen worden. Bijgevolg zal er een ander verloop in de verdere communicatie tussen het proces en de server plaatsvinden. • be¨ınvloeding van systeembronnen Dit ontstaat doordat het tracen in de record-fase geheugen zal opeisen om zijn werk correct te kunnen uitvoeren. Ook zal, als resultaat van de record-fase, een replay-bestand worden opgebouwd dewelke de harde schijf van het systeem zal vullen. Een voorbeeld hoe dit het getracete proces kan be¨ınvloeden, wordt hieronder gegeven. Stel dat we een harde schijf hebben met 1 GB vrije ruimte. Wanneer een proces in ongetracete toestand een bestand van 600 MB wenst weg te schrijven zal dit perfect lukken. Indien we echter de tracer het proces laten volgen en een replaybestand laten opbouwen, zal dit niet meer lukken, daar zowel het betreffende proces als de tracer een bestand, respectievelijk replay-bestand, van 600 MB wensen weg te schrijven. Daar er slechts 1 GB beschikbaar is, zal dit bijgevolg niet lukken. Opgemerkt dient te worden dat men be¨ınvloeding van de tijd ook kan onderbrengen onder de categorie systeembronnen daar de processor ook als een systeembron kan worden aanzien.


23

Beide bovenstaande voorbeelden zijn zogenaamde Heisenbugs van deterministische aard. Heisenbugs bestaan er ook in niet-deterministische vorm, doorgaans veroorzaakt door de scheduler van het besturingssysteem. Zo zal, wanneer we de scheduler afdwingen een te tracen proces op slechts één enkele processor uit te voeren, het verkrijgen van bepaalde locks totaal anders verlopen dan wanneer de threads binnen dit proces perfect gelijktijdig lopen op meerdere processoren. Men zal dus in dit geval races beletten zich al dan niet voor te doen.

2.9

Replay

Het tijdens de record-fase opgebouwde replay-bestand zal uiteraard dienen om in de replay-fase het proces van invoer te voorzien. En wel zodanig dat men het nietdeterministische karakter van de invoer verwijdert. Concreet zal men trachten het systeemoproep-patroon niet te doorbreken, daar dit hét instrument vormt om te bepalen of de replay al dan niet correct verloopt. Men zal hiertoe het proces in de replay-fase monitoren en net vóór en net ná elke systeemoproep tussenkomen. Net vóór elke systeemoproep zal men doorgaans een dummy systeemoproep installeren zodat de originele systeemoproep onderdrukt wordt. Hierdoor zal men het proces als het ware afschermen van de buitenwereld. Dit noemt men soms ook wel het proces in een sandbox laten draaien5 . Net ná elke systeemoproep zal men de nodige invoerdata in de user context van het betreffende proces injecteren om zo (hopelijk) tot de originele systeemoproep-invoer te komen. Voor elke klasse systeemoproepen (zie sectie 2.8.1 pagina 18) zal men anders te werk gaan. Deze werkwijzen zijn hieronder opgesomd. 1. Voor systeemoproepen die enkel een return code terugleveren zal men gewoon het register, waarin de return code door het proces wordt verwacht, overschrijven met de in de record-fase bewaarde return code. 2. Voor systeemoproepen die (doorgaans naast een return code) een gekend geheugengebied wijzigen, zal men de nodige data uit het replay-bestand halen en wegschrijven in het geheugen van het te replayen proces. 3. Systeemoproepen die een ongekend geheugengebied wijzigen, vallen qua behandeling ditmaal geheel onder de tweede klasse. Tijdens de record-fase zijn we er namelijk achter gekomen waar precies deze systeemoproepen data in het geheugen van het proces zullen wegschrijven. Het enige dat hierbij dient te worden opgemerkt is dat de pointers, die aan de systeemoproep als parameters worden meegegeven, en waar de systeemoproep hoort te schrijven, dezelfde moeten zijn als in de record-fase het geval was. Zoniet zal de systeemoproep ditmaal weliswaar opnieuw op de oude plaatsen gaan schrijven, maar het proces verwachtte het op een andere plaats in het geheugen. Bovenstaande werkwijze zal men herhalen voor elke systeemoproep en dit zolang het systeemoproep-patroon correct wordt gevolgd of het proces zijn gewone terminatie heeft bereikt. 5

Deze werkwijze past men ook toe op applets binnen een browser ter beveiliging van het systeem.


24

Best-effort Men kan in bepaalde gevallen toelaten dat het systeemoproep-patroon tijdelijk wordt verbroken, doorgaans onder de vorm van additionele systeemoproepen die men er tussendoor bijneemt. Het best-effort paradigma zal in de implementatie toegepast worden en pas wanneer de situatie echt onhoudbaar wordt, moet men de replay vroegtijdig onderbreken. De extra systeemoproepen die men mogelijk toelaat, zijn er slechts van een bepaalde klasse. Meestal betreft het hier systeemoproepen die foutberichten op de console wensen af te printen. Het kan zeer handig zijn deze systeemoproepen vooralsnog toe te laten, nog net vóór het systeemoproep-patroon geheel als doorbroken wordt beschouwd. Dit kan het debuggen van de replay-module aanzienlijk helpen. Wanneer extra systeemoproepen worden toegelaten, zal de replay-module in stall modus lopen. Dit omdat er verder geen data uit het replay-bestand mag worden gelezen zolang er systeemoproepen worden gepleegd die niet het verwachte patroon volgen. Uit een stall kan de replay-module op twee manieren raken: • Het systeemoproep-patroon wordt verder gevolgd waaruit men kan besluiten dat het proces zich klaarblijkelijk heeft hersteld. • De afwijking van het systeemoproep-patroon is te groot en de replay wordt bijgevolg als onhoudbaar bestempeld. De enige uitweg hier is de replay stopzetten. Dit tijdelijk verlaten van het systeemoproep-patroon kan ook nog als soft detaching worden benoemd.

Parano¨ıde replay Tot nog toe werd slechts één aspect van het replayen van de systeemoproepen behandeld, namelijk de terugkeerwaarden van de oproepen die men exact gelijk wenst te maken. Dit alles om het systeemoproep-patroon te kunnen volgen. Men zou als additionele maatstaf, om correct te replayen, de systeemoproep-parameters in de replay-fase kunnen gaan vergelijken met deze uit de record-fase. Hierdoor zou men over extra zekerheid beschikken voor het plaatsgrijpen van een perfecte replay. De replay zelf bevordert dit echter niet; het dient slechts ter additionele algoritmische controle op het replay-gebeuren. Dit brengt met zich mee dat de parameters van alle systeemoproepen in de record-fase moeten worden opgeslaan in het replay-bestand, wat de grootte van deze laatste niet ten goede zal komen.

Permeabiliteit van systeemoproepen Zoals reeds meerdere malen werd vermeld, zal men tijdens de replay-fase sommige systeemoproepen wél toelaten plaats te vinden. Dit om een aantal verschillende redenen:


25

• Omdat men partiële invoer wenst, hoofdzakelijk om de grootte van het replaybestand enigszins beperkt te kunnen houden, (Zie sectie 2.6 p. 16, Partiële invoer ). • Omdat men partiële uitvoer wenst, hoofdzakelijk omdat men zonder enige vorm van uitvoer tijdens de replay-fase het proces als blackbox zou ervaren, wat nutteloos is, (Zie sectie 2.5 p. 15, Partiële uitvoer ). • Omdat het nodig is de kernel context van het proces in replay-fase equivalent te houden aan de kernel context uit de record-fase. Indien men dit niet doet, kan het gebeuren dat het proces bepaalde excepties werpt, wat de replay opnieuw onhoudbaar zou maken. Deze categorie omvat voornamelijk de resource-allocaties, (Zie sectie 2.7 p. 17, Procescontext). In elk van deze gevallen zal men bijgevolg in de replay-fase, net vóór de systeemoproep, geen dummy systeemoproep mogen installeren en het systeem gewoon de originele systeemoproep laten uitvoeren. Wat de terugkeerwaarden van deze systeemoproepen betreft, kan men twee strategieën volgen: • Men levert het proces gewoon de terugkeerwaarden af zoals ze door de systeemoproepen in de replay-fase zonet werden gegenereerd. • De actuele terugkeerwaarden kunnen vergeleken worden met de uit de recordfase opgeslane terugkeerwaarden. Indien deze waarden verschillend zijn, zal men de replay als onhoudbaar beschouwen. Het kan ook zijn dat men in bepaalde gevallen toch nog toelaat dat systeemoproepen andere waarden terugleveren. Bij sommige systeemoproepen dient men echter meer te doen wanneer men een goede replay wenst. Dit is zo bij systeemoproepen die sterk verband houden met de kernel context van het betreffende proces, en wel in geval de kernel context uit de replay-fase niet exact overeenkomt met de kernel context uit de record-fase. Uit Procescontext (zie p. 17) blijkt dat een perfecte overeenkomst tussen de kernel contexten geenszins een vereiste is tot een perfecte replay. Men kan voor deze systeemoproepen twee strategieën volgen: • Ofwel zal men het proces in de replay-fase duidelijk maken dat de kernel context (een beetje) gewijzigd is t.o.v. die uit de record-fase. Uiteraard is dit een vrij gevaarlijke situatie daar het proces hierdoor mogelijk geen exacte replay meer kan doormaken. Een voorbeeld hiervan is een geheugenallocatie in replay-fase waarbij wel een blok geheugen van dezelfde grootte als in de record-fase werd gealloceerd, maar echter niet meer op hetzelfde geheugenadres, mogelijk doordat een ander proces op de originele plaats reeds een allocatie kreeg. Dit andere proces zou de tracer kunnen zijn indien de replay-module zodanig geconstrueerd is dat het te tracen proces en de tracer in éénzelfde virtuele adresruimte worden uitgevoerd. In geval enkel het adres van het gealloceerde geheugen verschilt, maar de allocatie zelf succesvol was, zouden we het proces in replay-fase gewoon dit nieuwe adres kunnen

26


afleveren en hopen dat die het slikt. Wat zich manifesteert doordat het proces zijn systeemoproep-patroon, omwille van deze wijziging in geheugenadres, niet zal verlaten. Deze werkwijze heeft als nadeel dat een proces, dat zijn systeemoproep-patroon afhankelijk opstelt van de teruggekregen waarden, dit patroon mogelijk zal doorbreken en bijgevolg de replay onhoudbaar maakt. • Een tweede strategie bestaat erin een mapping te voorzien tussen datgene waarover het proces denkt te beschikken als kernel context uit de record-fase en de actuele kernel context in replay-fase. In fig. 2.7 zien we zo dat de user context in de replay-fase nog steeds in termen van objecten a, b, c praat, terwijl de actuele kernel context enkel objecten a0 , b0 , c0 kent. We dienen dus tussen de objecten a, b, c en a0 , b0 , c0 te mappen opdat de replay zou lukken. user context

a, b, c

kernel context uit record−fase a

b

c mapping

a’

b’

kernel a, b, c

c’

actuele kernel context

a’, b’, c’

Figuur 2.7: Mapping van objecten uit de kernel context Een voorbeeld van zo een mapping betreft die van bestandsdescriptoren. Indien een open-systeemoproep in de replay-fase andere descriptoren aflevert dan in de record-fase6 , dienen we hier een mapping te voorzien. Zo kunnen we het proces opnieuw van exact dezelfde descriptoren voorzien als het in de recordfase kreeg. Dit is het geval wanneer we de open-systeemoproep deels permeabel maken om in partiële invoer en/of uitvoer te kunnen voorzien. In dit geval zal de descriptortoekenning geheel anders verlopen in beide fasen. Het voordeel van deze methode is dat we het proces dezelfde kernel context kunnen voorhouden als in de record-fase. Nadeel is dat we steeds tussen objecten uit de verschillende kernel contexten dienen te mappen.

Tijdsconservatie Naast een replay van de invoer dienen we ook de tijd enigszins te replayen. Meer bepaald moeten de intervallen, waarmee de data in de record-fase aan het proces wordt 6

Dit ten aanzien van de tracer. Het te replayen proces zal uiteraard door tussenkomst van de replay-module steeds dezelfde descriptoren terugkrijgen.


27

afgeleverd, in de replay-fase nagebootst worden. Indien we deze intervallen in de replayfase weglaten zal het proces weliswaar een perfecte replay kunnen doormaken, alleen zal dit proces soms iets te snel lopen en zich schijnbaar anders gedragen dan in de record-fase het geval was. Zo is het wenselijk dat een tekstverwerker zijn toetsenbordinvoer op exact hetzelfde tempo op het scherm zichtbaar maakt. Hiertoe moeten de intervallen, waarmee de toetsenbordinvoer aan het proces wordt afgeleverd, exact dezelfde te zijn in de replayfase. Om dit te bewerkstelligen zullen we in de record-fase, naast de eigenlijke invoer-data, bij sommige systeemoproepen ook nog een tijdsinterval opslaan. En wel bij deze systeemoproepen die gevoelig de tijdsduur van het proces kunnen be¨ınvloeden. In de replay-fase zullen we de opgeslane tijdsintervallen gebruiken door de lengte van dit interval te wachten, alvorens het proces verder te laten werken. Bij de ge¨ımplementeerde replay-module werden zo de systeemoproepen select en nanosleep van de hierboven beschreven functionaliteiten voorzien. Hierdoor lopen de processen in replay-fase ongeveer even snel, wat onder X-Windows zijn nut heeft.

Detaching Zoals reeds meerdere malen gesteld, kan het zijn dat in de replay-fase het replayen als onhoudbaar wordt bestempeld. De replay-fase kan om twee voorname redenen als onhoudbaar worden beschouwd: • Het systeemoproep-patroon is geheel doorbroken. Indien tijdens de replay-fase het systeemoproep-patroon niet meer wordt gevolgd, zal de replay onhoudbaar worden en dienen we ons bijgevolg los te koppelen van het proces. • Permeabele systeemoproepen leveren andere waarden terug dan die uit de recordfase. Sommige verschillen zijn te tolereren, maar diegene die niet aanvaardbaar zijn, zullen tevens een loskoppeling van het proces en de tracer vereisen. Voor de loskoppeling zijn verschillende strategieën te volgen, naargelang we ons net vóo´r of net ná een systeemoproep bevinden: • In geval we ons net vóo´r een systeemoproep bevinden, kunnen we het proces laten stoppen door het een exit-systeemoproep te laten uitvoeren (in plaats van een dummy systeemoproep). We gaan dus gewoon een oproep naar de exitsysteemoproep installeren in de context van het betreffend proces. • Indien we ons net ná een systeemoproep bevinden, kunnen we het proces geen exit-systeemoproep meer laten uitvoeren. Hierbij zullen we gewoon tot een volgende systeemoproep wachten om vervolgens vooralsnog een exit-systeemoproep te installeren. Indien het een permeabele systeemoproep betrof, zouden we de actuele terugkeerwaarde aan het proces kunnen afleveren om zo de huidige situatie (een andere dan werd verwacht) aan het proces zo goed mogelijk kenbaar te maken.

28


2.10

Signalen

Naast de scheduler is er nog een andere bron van niet-determinisme die zich zelfs bij een proces met één enkele thread kan manifesteren. Het betreft hier de zogenaamde signalen die een proces van de kernel kan ontvangen. Zo zal, wanneer zich een anomalie voordoet, de kernel (doorgaans op asynchrone wijze) een signaal naar het proces zenden. Hierdoor zal het proces zijn normale programmaverloop tijdelijk verlaten om een zogenaamde signaal handler uit te voeren dewelke het signaal zal behandelen. Zo wordt in fig. 2.8 op tijdstip t1 de hoofd-thread van het proces onderbroken om een signaal handler uit te voeren. Deze wordt beëindigd op tijdstip t2 en laat vanaf hier het eigenlijke proces verder lopen. Merk op dat de processor-context van de hoofd-thread hoofd−thread signaal handler proces t1

t2

tijd

Figuur 2.8: Een proces met signal handler weliswaar niet door de handler kan worden be¨ınvloed. Wat echter wel kan, is dat de user en/of kernel context van het proces door deze handler werd be¨ınvloed. En indien het proces zich hiervan afhankelijk opstelt, om systeemoproepen te plegen, bestaat de kans opnieuw dat we het systeemoproep-patroon verbreken. Ook kan dit patroon mogelijk worden doorbroken doordat de handler waarschijnlijk zelf systeemoproepen zal plegen. We moeten dus de signalen exact kunnen replayen indien we het systeemoproep-patroon niet wensen te doorbreken. Eigenlijk stelt zich hier hetzelfde probleem dan wanneer we het parallellisme van een bepaald proces wensen te replayen. Dit wordt ook veroorzaakt doordat het oproepen van de signaal handler bij de meeste kernels doorgaans door de scheduler zelf wordt gedaan. We zullen dus, analoog aan de scheduling-conservatie, het exacte moment opslaan wanneer de signaal handler wordt geactiveerd. Ons hiertoe louter en alleen baseren op de actuele instructie-pointer van de hoofd-thread is niet voldoende daar we hierdoor (net zoals bij de scheduling het geval was) lussen en functies verkeerdelijk kunnen tracen. Bijgevolg moet men naast de actuele instructie-pointer ook nog het aantal uitvoeringen van betreffende instructie opslaan. Om dit uitvoeringsgetal te bepalen, laten we het proces in de record-fase in single step modus draaien om zo na elke instructie in een tabel het uitvoeringsgetal van de huidige instructie met één te verhogen. Deze tabel wordt vervolgens gebruikt in geval een signaal of relevante taakwisseling zich voordoet. Het probleem bij bovenstaande geproposeerde werkwijze is dat die single step modus enorm vertragend werkt op een systeem. Enkele tests werden gedaan waarvan de resultaten in tabel 2.1 werden weergegeven. In deze tabel vinden we het aantal instructies terug, nodig om één enkele instructie in single step modus onder linux uit te voeren. Hieruit blijkt dat het proces bij single step execution ongeveer 3700 maal trager loopt, waardoor het gevaar voor Heisenbugs aanzienlijk toeneemt. De tracer die hierbij werd gebruikt doet dan nog maar het absolute minimum, weergegeven in


29

PII 391 Mhz, linux 2.4.18 PII Celeron 467 Mhz, linux 2.4.10 3713 3767 3762 3615 3753 3705 3728 3832 3730 3849 3726 3883 3719 3827 3750 3717 Tabel 2.1: De overhead door single step execution

volgend codefragment: 1 2 3 4

while ( 1 ) { waitpid ( child_pid , & status , WUNTRACED ) ; ptrace ( PTRACE_SINGLESTEP , child_pid , NULL , NULL ) ; }

Het kost dus ongeveer 3700 instructies om het proces dat men tracet zijn volgende instructie te laten uitvoeren. Hierbij heeft de tracer dus nog geen replay-bestand opgebouwd met de nodige data voor de replay! Verdere tests wezen zelfs uit dat één enkele extra systeemoproep, namelijk de getpid op lijn 4 in volgend fragment: 1 2 3 4 5

while ( 1 ) { waitpid ( child_pid , & status , WUNTRACED ) ; ptrace ( PTRACE_SINGLESTEP , child_pid , NULL , NULL ) ; getpid ( ) ; / / extra systeemoproep }

het aantal nodige instructies met zeker 400 laat stijgen. De getpid-systeemoproep is dan nog de meest eenvoudige die in de linux kernel te vinden is. Het enige dat deze doet is een getal teruggeven. Bijgevolg is single step modus quasi onbruikbaar indien we signalen en scheduling zonder gevaar voor Heisenbugs wensen te recorden en vervolgens replayen. Een methode, om de opstelling van de instructie-uitvoeringstabel te vermijden, bestaat erin om in een zeer accurate tijdsbepaling te voorzien. Zo zal de combinatie EIP en tEIP de huidige instructie exact kunnen bepalen. Merk op dat hierbij EIP zelfs niet meer nodig zou zijn, doch ter controle kan deze best steeds ook in de record-fase worden opgeslaan. Uiteraard stelt zich hier het probleem dat we in zo een exacte tijdsfunctie t moeten voorzien. Een gewone opvraging van de systeemklok is niet precies genoeg, daar in één enkele milliseconde meerdere instructies door de processor kunnen worden uitgevoerd. Indien we bijvoorbeeld bij volgende code: 1 2 3

while ( 1 ) { i++; }

op tijdstip 13:46:23.524 in de record-fase waarnamen dat een signaal handler of een


30

andere taak de processor overnam, zal een replay van dit gebeuren aan de hand van dit tijdstip niet volstaan. Binnen dit tijdstip7 kan immers de variabele i bijvoorbeeld de waarden 45 tot en met 50 aannemen. En indien de signaal handler of een andere thread binnen dit proces de waarde van de variabele i nu zal gebruiken als aantal systeemoproepen die moeten uitgevoerd worden, bestaat de kans opnieuw dat het systeemoproep-patroon wordt verbroken en bijgevolg de replay onhoudbaar wordt. De waarde deze variabele kan in de replay-fase namelijk —ondanks het feit dat het tijdstip van onderbreking exact gelijk is— verschillen van die in de record-fase. Dit komt doordat de tijdsmeting met behulp van de systeemklok niet accuraat genoeg is. We dienen over een tijdsmeting te beschikken die de CPU-tijd meet in plaats van de systeemtijd. Een eerste oplossing bestaat erin het aantal jiffies te gebruiken dat door de linux kernel zelf wordt bijgehouden. Dit getal duidt aan hoelang een proces in user modus heeft doorgebracht. Dit blijkt echter nog steeds niet accuraat genoeg te zijn, zelfs niet nadat het aantal jiffies per seconde aanzienlijk werd verhoogd. Dit brengt immers met zich mee dat de scheduler alle processor-tijd voor zich opeist. Een andere oplossing kan zijn dat men effectief het aantal verstreken klok-cycli gaat meten. De Intel Pentium processor-klasse beschikt hiertoe over een zogenaamde Timestamp Counter [3]. Dit register opvragen, levert het huidige aantal reeds uitgevoerde instructies van betreffende processor. Maar de tijd aan de hand van de TSC vastleggen, vereist echter wel enkele diepgaande wijzigingen in de linux kernel. Zo zou bij de gates en exit-points van de kernel de TSC dienen te worden gelezen en bijgehouden. Belangrijk hierbij is dat we de TSC bij de gates dienen te checken en niet daar waar ook de jiffies worden ge¨ updatet. Dit omdat het checken van de TSC bij de gates zelf onafhankelijk is van de release van de linux kernel. Bijkomend probleem is dat deze TSC niet geheel serieel is; we kunnen een out-of-order waarde van de actuele Time-stamp Counter terugkrijgen wanneer we dit register lezen. Aan dit probleem is waarschijnlijk wel het hoofd te bieden door aan de RDTSC-instructie een gekende instructiesequentie te laten voorafgaan, die het mogelijk maakt van een bepaalde instructie uit deze sequentie te zeggen wat zijn exacte time-stamp is. Doch dit kan sterk processor-afhankelijk zijn. De Intel Pentium processor bevat ook zogenaamde Performance-Monitoring Counters [4]. Deze laten toe verscheidene events binnen de processor te monitoren. Zo kunnen we via deze tellers het aantal instructies, dat de processor in user mode doorbrengt, tellen. Hierdoor zouden we het serialiserende instructiepatroon, nodig voor een correct uitlezen van de TSC, overbodig kunnen maken. In de record-fase vragen we bij de gates dan gewoon de waarde van deze teller op en we weten onmiddellijk precies hoeveel instructies het proces in user mode heeft uitgevoerd. Uiteraard zullen we steeds voor de veiligheid ook nog het EIP-register opslaan. Bij de replay-fase dienen we echter wel het opgeslane aantal cycli te kunnen gebruiken. Dit is nodig om een proces exact evenveel instructies te laten uitvoeren alvorens een scheduling of signaal handler de zaak te laten overnemen. Ook dit kunnen we via de Performance-Monitoring Counters bewerkstelligen. Deze kunnen namelijk zó ingesteld worden dat ze bij een counter overflow een lokale APIC-interrupt genereren. Deze exceptie is weliswaar niet geheel synchroon met het event zelf, maar indien we even vóór de gewenste instructie deze overflow laten plaatsgrijpen, hoeven we slechts de 7

Is eigenlijk een tijdsinterval.


31

laatste paar instructies in single step modus uit te voeren. Dit zou reeds een hele verbetering zijn tegenover het gehele proces in single step modus te laten draaien.

Prestatie Uiteraard is bovenstaande werkwijze enkel bruikbaar in geval alle threads van het betreffende proces op slechts één enkele processor draaien. Het snelheidsverlies, veroorzaakt doordat in de record-fase alle threads van betreffend proces op één enkele processor moeten draaien, zal vervolgens worden berekend. Stel dat de processoren in het theoretische model allen een snelheid van µ mips (million instructions per second) hebben, dan zal één enkele thread bijgevolg tegen een maximale snelheid van µ mips kunnen worden uitgevoerd. Indien n threads op één enkele processor draaien, zullen deze tegen een gemiddelde snelheid van µ/n mips lopen. Hierbij nemen we voor de eenvoud de overhead door de scheduling niet in rekening. Zo zullen n threads op p processoren een gemiddelde snelheid halen van, p

µ n

Het snelheidsverlies, door n threads op slechts één enkele processor te laten draaien in plaats van op p processoren, wordt bijgevolg gegeven door, p

µ µ µ − = (p − 1) n n n

Merk op dat dit lineair afhankelijk is van het aantal processoren p. Anders geformuleerd zullen deze threads, µ n =1 µ p p n maal trager lopen dan indien ze op p processoren draaiden. De restrictie om deze n threads slechts op één enkele processor te laten lopen, is echter nog steeds beter dan deze op de p beschikbare processoren te laten lopen in single step modus. Bij single step modus zullen de processoren threads namelijk tegen een veel lagere snelheid µ0 laten lopen, dewelke gegeven wordt door, µ0 =

µ ω

waarbij ω de overhead is om de processor in single step modus te laten draaien. Uit tabel 2.1 bleek voor linux dat, ω ≈ 3700 Dus n threads op p processoren, die in single step modus draaien, zullen bijgevolg aan een snelheid van, µ/ω pµ µ0 =p = p n n ωn mips lopen. En, pµ µ > n ωn


32

zolang p/ω < 1, of nog, p < ω. Dus indien we over ω (≈ 3700 onder linux) processoren beschikken, wordt de single step modus aantrekkelijker ten aanzien van de voorkoming van Heisenbugs. Uit bovenstaande blijkt dat de single step modus niet echt aan te raden is bij een implementatie van replay van parallellisme. Verder dient te worden opgemerkt dat men uit de p beschikbare processoren steeds diegene moet nemen met de grootste snelheid µ om zoveel mogelijk Heisenbugs in de record-fase uit te sluiten. Formeel kiezen we uit p processoren met snelheden, µ1 , µ2 , . . . , µp de processor met volgnummer i waarbij, µi = max(µ1 , µ2 , . . . , µp ) Merk dat de snelheid µ van een processor niet enkel van zijn effectieve aantal mips zal afhankelijk zijn. Ook de grootte van zijn cache zal bij meerdere concurrerende threads zeer bepalend zijn voor zijn snelheid. Hoe groter de cache namelijk, hoe minder er uit het geheugen hoeft te worden gehaald per taakwisseling. Hierbij is ook het aantal cache misses dus belangrijk.

2.11

Replay configuratiebestanden

Daar elk programma zijn eigen systeemoproep-permeabiliteitsinstellingen zal kennen, is het vrij logisch deze instellingen voor elk programma in een configuratiebestand te bewaren. Dit configuratiebestand kunnen we vervolgens meerdere malen gebruiken en dit zowel voor record- als voor replay-fasen. De opbouw van dit configuratiebestand moet zodanig zijn dat het in een globale policy kan voorzien qua permeabiliteit en dit voor verschillende klassen systeemoproepen die dit mogelijk vereisen. De replay-module, ontwikkeld bij deze thesis, laat zich instellen via een configuratiebestand in XML. Een voorbeeld van zo een XML-configuratiebestand is hieronder weergegeven. replayfile <showopenfilenames value="1"/> <sandbox file="filex1" type="input"/> <enforce file="replayfile" type="output" mmap="enforce"/> <enforce file="hello123" type="input"/>

Hierin bemerken we dat we naast een globale policy de bestanden ook nog eens specifiek kunnen benaderen. Deze mogelijkheid laat toe zeer krachtige replay-instellingen voor programma’s te definiëren.

Hoofdstuk 3 Monitoring onder Linux In dit hoofdstuk zal de mogelijkheid worden onderzocht om onder het besturingssysteem linux in de record-fase te voorzien. De replay-module werd ontwikkeld voor het i386-platform en draait dan ook enkel onder deze architectuur. In portabiliteit kon niet worden voorzien, daar te specifieke eigenschappen van de processor zelf werden gebruikt.

3.1

Proces Trace systeemoproep

Zoals reeds uit vorig hoofdstuk bleek, dienen we in de record-fase net ná de systeemoproepen de resultaten van deze te bewaren in een replay-bestand. Dit replay-bestand zal dan later in de replay-fase worden gebruikt om de invoer te replayen, wat het uiteindelijke doel vormt. Linux laat het monitoren van systeemoproepen zeer makkelijk toe via de zogenaamde Process Trace of ptrace-systeemoproep. De ptrace-systeemoproep wordt gebruikt om processen te controleren, er informatie uit te lezen en naar weg te schrijven. Deze systeemoproep wordt doorgaans gebruikt door debuggers om een proces in stappen uit te voeren en de inhoud van zijn variabelen te bestuderen. In het kader van een tracen via de ptrace-systeemoproep heet het proces dat tracet het ouderproces. Het ouderproces tracet bijgevolg (één van) zijn kindproces(sen). Naast de ptrace-systeemoproep kent linux ook nog de /proc interface. Deze laat toe additionele informatie omtrent elk actief proces op te vragen, zoals onder andere de command line waarmee betreffend proces werd gestart. Het gebruik van de ptrace-systeemoproep zal hieronder worden toegelicht. Dit omdat de manual pages van ptrace onder linux fouten en onduidelijkheden bevatten. De synopsis van de ptrace-systeemoproep is als volgt (de C-interface): #include <sys/ptrace.h> int ptrace(int request, pid_t pid, void *addr, void *data); Hierbij zal pid het proces-ID zijn van het proces dat men wenst te tracen. De betekenis 33

HOOFDSTUK 3. MONITORING ONDER LINUX

34

van de parameters addr en data is afhankelijk van de request-waarde. De voornaamste aanvragen die ptrace aanvaardt, zijn hieronder weergegeven. • PTRACE TRACEME Deze aanvraag duidt aan dat het huidige proces wenst te worden getracet door zijn ouderproces. Een proces voert deze aanvraag best enkel uit indien zijn ouderproces voorzien is om zijn kindproces te tracen. Elk signaal dat het kindproces te verwerken krijgt, zal tot resultaat hebben dat het kind stopt en dat zijn ouderproces wordt verwittigd via een wait. De parameters addr en data worden hier niet gebruikt. • PTRACE ATTACH Deze aanvraag koppelt het huidige proces aan het gespecificeerde proces met proces-ID pid, waardoor deze laatste een kind wordt van het huidige proces, dewelke nu het pid-proces kan beginnen tracen. Bemerk dat een getpid door het kindproces echter wel nog steeds zal resulteren in het proces-ID van zijn origineel ouderproces. In tegenstelling tot PTRACE TRACEME zal het kindproces een STOPSIG-signaal toegestuurd krijgen. Het kindproces ontvangt dit signaal niet noodzakelijk onmiddellijk. Gebruik bijgevolg wait om te wachten tot het kindproces gestopt is. De parameters addr en data worden hier niet gebruikt. • PTRACE DETACH Deze aanvraag zorgt ervoor dat we ons van het kindproces, aangeduid met pid, loskoppelen en het bijgevolg niet langer tracen. Een belangrijke opmerking hierbij is dat onder linux een kindproces via deze aanvraag zelf het tracen door zijn ouderproces kan stopzetten. De parameter data kan een signaal bevatten dat naar het kindproces zal worden gestuurd. Deze aanvraag vereist dat het kindproces wordt getracet én gestopt is met uitvoering. De parameter addr wordt hier niet gebruikt. • PTRACE KILL Deze aanvraag zendt een SIGKILL-signaal naar het kindproces om het te beëindigen. Het is nodig dat het kindproces wordt getracet én gestopt is met uitvoering. De parameters addr en data worden hier niet gebruikt. • PTRACE PEEKUSER Deze aanvraag leest een woord op offset addr uit het USER-gebied van het kindproces. Zulk gebied bevat alle actuele registerinhouden van de huidige context van het kindproces. Men mag dit gebied niet verwarren met het geheugengebied van het kindproces; het bevindt zich eigenlijk op de kernel stapel van het kindproces. De layout van het USER-gebied is terug te vinden in . Deze aanvraag vereist dat het kindproces wordt getracet én gestopt is met uitvoering. De parameter data wordt hier niet gebruikt. • PTRACE POKEUSER Deze aanvraag schrijft een woord met waarde data naar offset addr in het USERgebied van het kindproces. Het wijzigen van sommige registers uit dit gebied wordt niet toegelaten door de linux kernel wegens mogelijke integriteitsproblemen. Deze aanvraag vereist dat het kindproces wordt getracet én gestopt is met uitvoering.


35

• PTRACE PEEKDATA, PTRACE PEEKTEXT Een woord op adres addr uit het geheugengebied van het kindproces wordt gelezen en weggeschreven naar offset data in het ouderproces. De libc wrapperfunctie verschilt hier omdat deze dit woord als terugkeerwaarde levert, data wordt bij de ptrace-wrapper bijgevolg niet gebruikt. Deze aanvraag vereist dat het kindproces wordt getracet én gestopt is met uitvoering. • PTRACE POKEDATA, PTRACE POKETEXT Schrijf een woord met waarde data naar offset addr in het geheugen van het kindproces. Deze aanvraag vereist dat het kindproces wordt getracet én gestopt is met uitvoering. • PTRACE GETREGS Deze aanvraag laat toe alle registers uit het USER-gebied van het kindproces tegelijk te benaderen. Het USER-gebied wordt naar adres data van het ouderproces gekopieerd. Deze aanvraag vereist dat het kindproces wordt getracet én gestopt is met uitvoering. De parameter addr wordt hier niet gebruikt. • PTRACE SETREGS Deze aanvraag schrijft alle registers op adres data weg naar het USER-gebied van het kindproces. Deze aanvraag vereist dat het kindproces wordt getracet én gestopt is met uitvoering. De parameter addr wordt hier niet gebruikt. • PTRACE CONT Men herstart hiermee een eerder gestopt kindproces. Indien data verschillend is van NULL en verschillend van SIGSTOP wordt deze waarde als signaal naar het kindproces gezonden; anders wordt er geen signaal verstuurd. Deze aanvraag vereist dat het kindproces wordt getracet én gestopt is met uitvoering. De parameter addr wordt hier niet gebruikt. • PTRACE SYSCALL, PTRACE SINGLESTEP Analoog aan PTRACE CONT maar zal het kindproces tot aan de volgende systeemoproep respectievelijk de volgende instructie laten doorlopen. Het ouderproces wordt van deze gebeurtenis op de hoogte gebracht via een SIGTRAP-signaal. Bij PTRACE SYSCALL zal het kindproces zowel net vóór de systeemoproep als net ná de systeemoproep stoppen. Indien we ons net vóór een systeemoproep bevinden, zal de terugkeerwaarde, gestockeerd in het EAX-register, uit het USER-gebied de waarde -ENOSYS hebben. De terugkeerwaarde net ná een systeemoproep kan echter ook de waarde -ENOSYS hebben. Op de inhoud van het EAX-register kan bijgevolg niet worden voortgegaan bij de bepaling of we ons net vóór of net ná een systeemoproep bevinden. Deze aanvraag vereist dat het kindproces wordt getracet én gestopt is met uitvoering. De parameter addr wordt hier niet gebruikt. Wat de terugkeerwaarde van de ptrace-systeemoproep betreft, leveren alle aanvragen bij succes de waarde 0 terug. Een fout heeft zich voorgedaan wanneer de terugkeerwaarde negatief maar groter dan -4096 is. De ptrace-systeemoproep wordt nooit rechtstreeks opgeroepen maar steeds via een GNU libc wrapper -functie. Deze laatste verschilt enkel van de echte ptrace-systeemoproep qua foutafhandeling en uiteraard ook bij de PEEK ...-aanvragen. Deze leveren


36

hier de gevraagde waarde terug. De GNU libc ptrace-systeemoproep wrapper zal bij een fout de errno-variabele van het ouderproces gepast zetten en de waarde -1 teruggeven. Die wrapper ziet er, sterk vereenvoudigd, als volgt uit: 1 2 3

4

#define IS_PEEK_REQUEST ( req ) ( . . . ) #define IS_ERROR ( x ) ( − 4 0 9 6 < ( int ) ( x ) && ( int ) ( x ) < 0 ) extern int __ptrace ( int request , int pid , void ∗ addr , void ∗ data ) ; extern int errno ;

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

int ptrace ( int request , pid_t pid , void ∗ addr , void ∗ data ) { int res , ret ; i f ( IS_PEEK_REQUEST ( request ) ) data = &ret ; res = __ptrace ( request , pid , addr , data ) ; i f ( IS_ERROR ( res ) ) { errno = −res ; res = −1; } e l s e i f ( IS_PEEK_REQUEST ( request ) ) { errno = 0 ; return ret ; } return res ; }

Deze wrapper brengt met zich mee dat men bij aanvragen, die de gewenste waarde als terugkeerwaarde leveren, de errno-variabele expliciet moet checken. Dit doordat een waarde -1 zowel op een fout kan duiden als gewoon op een -1 als terugkeerwaarde. De waarde van de errno-variabele dient in dit geval uitsluitsel te bieden. Een correct gebruik van ptrace in deze gevallen is hieronder afgebeeld. 1 2 3 4

unsigned int value ; value = ptrace ( PTRACE_PEEKDATA , pid , addr , NULL ) ; i f ( errno ) do_error ( ) ;

Een voorbeeld Daar eender welke API zich steeds makkelijker laat doorgronden aan de hand van een voorbeeld, werd een klein programma geschreven. Dit zal het gebruik van de ptrace-systeemoproep enigszins demonstreren. Het is zeer belangrijk deze code goed te doorgronden daar men zich hierdoor een perfect beeld vormt van hoe een replay-module onder linux mogelijk kan worden geconstrueerd. 1 2 3 4 5

#include #include #include #include #include

<stdio . h> <stdlib . h> <sys / ptrace . h>

HOOFDSTUK 3. MONITORING ONDER LINUX 6 7

37

#include <sys / wait . h> #include <sched . h>

8 9

#define STACK_SIZE ( 1 0 2 4 ∗ 6 4 )

10 11 12

s t a t i c int child_func ( void ∗ param ) ; s t a t i c int go = 0 ;

13 14 15 16 17 18 19

20 21 22 23 24 25 26 27 28 29 30 31 32 33

int main ( ) { int status , pid ; char ∗ stack ; stack = malloc ( STACK_SIZE ) ; pid = clone ( child_func , stack + STACK_SIZE , SIGCHLD | CLONE_VM , NULL ) ; ptrace ( PTRACE_ATTACH , pid , NULL , NULL ) ; waitpid ( pid , & status , WUNTRACED ) ; go = 1 ; while ( 1 ) { ptrace ( PTRACE_SYSCALL , pid , NULL , NULL ) ; waitpid ( pid , & status , WUNTRACED ) ; i f ( WIFEXITED ( status ) ) exit ( 0 ) ; i f ( WIFSTOPPED ( status ) && WSTOPSIG ( status ) == SIGTRAP ) printf ( " syscall : %d ( EAX : %d)\n", (int) ptrace ( PTRACE_PEEKUSER , pid , ORIG_EAX * 4, NULL), (int) ptrace ( PTRACE_PEEKUSER , pid , EAX * 4, NULL)); } }

34 35 36 37 38 39 40 41

static int child_func (void * param ) { while (! go) ; getpid (); getppid (); return 0; }

Dit programma heeft als mogelijke uitvoer: syscall: syscall: syscall: syscall: syscall:

20 (EAX: -38) 20 (EAX: 1319) 64 (EAX: -38) 64 (EAX: 1318) 1 (EAX: -38)

Bespreking van de code Het hoofdprogramma uit bovenstaande code zal via een clone-systeemoproep (lijn 19) een tweede proces starten dat binnen dezelfde geheugenruimte (CLONE VM) opereert


38

als zijn ouderproces. Dit tweede proces zal de statements uit child func (lijn 35) uitvoeren. Op lijn 20 en 21 zal het ouderproces zijn kindproces beginnen te tracen en zal het wachten tot zijn kindproces stopt. Het stoppen van het kindproces werd ge¨ınitieerd door het attachen zelf, doch verloopt hiermee niet synchroon. Na de waitpid op lijn 21 zal het ouderproces het kindproces via de go-variabele duidelijk maken dat het mag verder lopen omdat vanaf hier het tracen succesvol is ingezet. Merk wel op dat het kindproces hier nog slaapt. Door een eerste PTRACE SYSCALL op lijn 24 wordt het echter opnieuw actief tot het een volgende systeemoproep uitvoert. Deze volgende systeemoproep is getpid op lijn 38. Hierdoor zal het kindproces opnieuw stoppen en zal naar het ouderproces een SIGTRAP-signaal worden gestuurd. Via de waitpid op lijn 25 zal het ouderproces van het gebeuren in het kindproces worden ge¨ınformeerd. Het ouderproces kan het kindproces vervolgens gaan bestuderen en bijvoorbeeld de huidige systeemoproep, die het kindproces wenst uit te voeren, achterhalen (lijn 30) of de terugkeerwaarde uitprinten (lijn 31). We stellen vast dat de systeemoproep nummer 20 —wat de getpid-systeemoproep is— in de schermuitvoer van het programma tweemaal voorkomt. Een eerste maal net vóór het plaatsgrijpen van de effectieve systeemoproep en een tweede maal net ná de uitvoering van de systeemoproep. Dit is tevens te merken aan de terugkeerwaarde die via het EAX-register aan het kindproces wordt geleverd. De eerste keer bevat dit een negatief getal (eigenlijk -ENOSYS) dat nog nergens op slaat, daar de systeemoproep hier nog dient te gebeuren. De tweede maal bevat het echter het procesnummer van het kindproces, wat in dit geval 1319 is. Voor de volgende systeemoproep, nummer 64 of getppid, stellen we vast dat het kindproces als terugkeerwaarde 1318 krijgt. Dit is inderdaad logisch daar het procesnummer van een kind dat van zijn ouder doorgaans onmiddellijk opvolgt. Tenslotte zal het kindproces via een exit-systeemoproep —het nummer hiervan is 1— worden beëindigd. Deze wordt niet expliciet door de functie child func opgeroepen, maar wordt als stub-code aan de functie aangebreid. Dit gebeurt aan de hand van een gepaste terugkeerwaarde op de stapel van child func, dewelke werd voorzien door de clone-systeemoproep. De werking van bovenstaand programma doorgronden is zeer belangrijk. Men kan namelijk zeer snel inzien dat we reeds een zeer eenvoudige replay-module zouden hebben, wanneer we in een record-fase net ná iedere systeemoproep de terugkeerwaarde opslaan en in een replay-fase diezelfde terugkeerwaarde opnieuw in het proces injecteren.

Beperkingen De ptrace-systeemoproep stelt ons in staat een proces zeer precies te monitoren. Toch kent deze functionaliteit enkele beperkingen. Deze zijn voornamelijk: • Er is geen enkele eenvoudige manier om te achterhalen welke geheugengebieden van het kindproces een systeemoproep tijdens zijn uitvoering heeft gewijzigd. Dit heeft als gevolg dat we in onze replay-module in de record-fase een kopie moeten maken van het geheugen van het kindproces om het ná de systeemoproep met de nieuwe geheugeninhoud van het kindproces te vergelijken. (Zie ook 2.8.2 p. 19) • Aanvragen om een geheel gebeugenblok te lezen of te schrijven zijn onbestaande. Deze zouden bijvoorbeeld volgende namen kunnen dragen: PTRACE GETBLOCK en PTRACE SETBLOCK.


39

Indien we met de huidige ptrace-systeemoproep een blok geheugen uit het geheugengebied van het kindproces wensen te lezen, is de enige manier hiervoor dit blok wóórd voor wóo´rd op te halen. • Er is slechts één werkwijze om te achterhalen of we ons nu net vóo´r of net ná een systeemoproep bevinden. Deze is door de positie (vóo´r of ná) zelf in een variabele in het ouderproces bij te houden. Dit kan echter fout lopen, daar sommige systeemoproepen (zoals een execve) nooit terugkeren. Beter zou zijn dat we onze huidige positie expliciet aan ptrace kunnen vragen. • De hoofdlus in het voorbeeldprogramma bezit reeds 4 systeemoproepen per iteratie. Dit zijn er 8 per systeemoproep. Eigenlijk zouden deze 4 systeemoproepen te combineren zijn tot één enkele systeemoproep. Deze zou de logische naam ptrace wait dragen en volgende zaken doen: – Een register-cache naar het USER-gebied van het kindproces wegschrijven, indien men het wenst. – Een effectieve ptrace-systeemoproep uitvoeren. Enkel de aanvragen PTRACESYSCALL, PTRACE CONT en PTRACE SINGLESTEP mogen hier worden toegelaten. – Een waitpid-systeemoproep uitvoeren. – Eventueel reeds een register-cache uit het USER-gebied van het kindproces in het geheugen laden voor de tracer in het ouderproces. Het al dan niet laden/wegschrijven van de register-cache zou kunnen gebeuren aan de hand van flags in de bovenste short van het request-woord. – Via de terugkeerwaarde duidelijk maken of we ons nu net vóór of net ná een systeemoproep bevinden. Door het aantal systeemoproepen, nodig in de hoofdlus van de tracer van de replay-module, te reduceren, zal de kans op Heisenbugs aanzienlijk verminderen (Zie ook Heisenbugs 2.8.3 p. 21).

3.2

Uitbreidingen

De ptrace-systeemoproep werd uitgebreid om aan het eerst gestelde probleem uit voorgaande opsomming het hoofd te bieden. Zoals reeds in voorgaand hoofdstuk (2.8.2 p. 19) vermeld, werd de methode, afgebeeld in fig. 3.1, ge¨ımplementeerd in de replaymodule ontwikkeld bij deze thesis. Hierbij wordt elke schrijfoperatie —zoals bijvoorbeeld put user— zodanig gewijzigd dat deze naast de effectieve schrijfoperatie ook nog een element toevoegt aan een gelinkte lijst die opgeslaan ligt in de task struct van het huidig proces, aangeduid via de kernel-variabele1 current. Dit element bevat volgende gegevens: • Het beginadres van de weggeschreven data. • De hoeveelheid weggeschreven data. 1

Is op het i386-platform eigenlijk een macro.

40

HOOFDSTUK 3. MONITORING ONDER LINUX proces current task_struct

mm

user mode context user data geheugen

user code geheugen

put_user

int 0x80

if (current−>ptrace & PT_PTRACED) {

kernel module

....... } no_trace:

entry.S: syscall

linux kernel

Figuur 3.1: Schrijfoperaties onder linux instrumenteren • Een ID-nummer van de functie/macro die de elementaire schrijfoperatie uitvoerde. Dit kan zeer handig zijn wanneer men device drivers wenst te debuggen of hun gedrag wenst te bestuderen. De eigenlijke data, die de elementaire schrijfoperaties naar het geheugen wegschrijven, wordt echter niet in deze elementen opgeslaan. Deze data is toch steeds beschikbaar in het geheugengebied van het betreffende proces. Bijgevolg zou het geheugenverspilling zijn deze data ook op te slaan in de elementen. Merk op dat de elementaire schrijfoperaties deze elementen slechts aan de gelinkte lijst toevoegen indien men betreffend proces ook effectief tracet. Hierdoor zal de overhead, veroorzaakt door de uitbreiding van de elementaire schrijfoperaties, zeer beperkt blijven. Zo vertaalt de GNU gcc C-compiler het if-statement uit fig. 3.1 op een i386platform in slechts 4 machine-instructies: movl $-8192, %eax andl %esp, %eax testb $1, 24(%eax) je .no_trace ... .no_trace: Doorgaans kan de compiler de inhoud van EAX, dewelke current bevat, in daaropvolgende code onmiddellijk gebruiken, zodat de overhead zelfs minder dan 4 machineinstructies kan zijn. Uiteraard zal de spronginstructie, bij verkeerde voorspelling door de processor, 12 klokcycli opeisen wanneer deze nog niet in de BTB2 zit. Dit omdat de statische sprongvoorspelling (op Intel-processoren) voorwaartse conditionele spronginstructies niet neemt (fall through) en we doorgaans niet tracen en bijgevolg onmiddellijk naar .no trace 2

Branch Target Buffer.


41

wensen te springen. Wanneer de spronginstructie echter door de BTB correct kan worden voorspeld, kost het slechts 1 extra klokcyclus om deze sprong uit te voeren [4]. Een processor met een grote BTB zal bijgevolg minder overhead ondervinden van de geschreven patch. De inhoud van deze “door elementaire schrijfoperaties geconstrueerde gelinkte lijst” kan men vervolgens via enkele nieuwe aanvragen van de ptrace-systeemoproep opvragen. Eigenlijk kunnen er twee soorten gelinkte lijsten opgevraagd worden: • Een ruwe geheugenverschillen-record. Deze bevat de informatie zoals door de elementaire schrijfoperaties werd voorzien. • Een genormaliseerde geheugenverschillen-record. Deze bevat een genormaliseerde vorm van de ruwe versie. Dit normaliseren van een ruwe geheugenverschillen-record houdt in dat men elementen uit de lijst, die elkaar qua adressen opvolgen, laat samensmelten. Verder worden dubbele elementen geëlimineerd en wordt de resterende lijst gesorteerd volgens de beginadressen. Bemerk hierbij dat het ook voor het normaliseren belangrijk is om de effectieve data niet ook in de elementen op te slaan. Wanneer dit wel zou worden gedaan, zou het normalisatie-algoritme ook rekening moeten houden met onder andere de volgorde waarin twee samen te smelten blokken werden geschreven. De nieuwe aanvragen aan de ptrace-systeemoproep worden hieronder toegelicht. Deze vereisen allen bij gebruik. • PTRACE RAWMEMDIFF Deze aanvraag levert het aantal elementaire schrijfoperaties, uitgevoerd door de huidige kind-systeemoproep, terug. Wanneer addr niet NULL is, wordt de grootte van de ruwe geheugenverschillen-record naar *addr weggeschreven. Verder zal, indien data niet NULL is, de ruwe geheugenverschillen-record zelf naar *data worden weggeschreven. Deze aanvraag vereist dat het kindproces wordt getracet én gestopt is met uitvoering. Het formaat van deze ruwe geheugenverschillenrecord is weergegeven in tabel 3.1. Header Het aantal elementen in deze record 1 woord = 4 bytes Na de header volgen alle elementen na elkaar. Elk element bevat volgde layout: beginadres 1 woord ID van de schrijfoperatie 1 woord grootte van het datablok 1 woord de eigenlijke data bep. door voorgaand veld Tabel 3.1: De ruwe geheugenverschillen-record


42

• PTRACE DIFFMEM Deze aanvraag levert het aantal genormaliseerde schrijfoperaties terug. Wanneer addr verschillend is van NULL, schrijft deze functie naar *addr de grootte van de genormaliseerde geheugenverschillen-record. In geval data verschilt van NULL, schrijft deze functie de genormaliseerde geheugenverschillen-record zelf naar *data. De genormaliseerde geheugenverschillen-record kan zonder wijzigingen aan de PTRACE PATCHMEM-aanvraag worden doorgegeven. Deze aanvraag vereist dat het kindproces wordt getracet én gestopt is met uitvoering. • PTRACE PATCHMEM Deze zal de door addr aangeduide genormaliseerde geheugenverschillen-record toepassen op het geheugen van het kindproces. Deze aanvraag vereist dat het kindproces wordt getracet én gestopt is met uitvoering. Hierbij is de dataparameter ongebruikt. Verder zal elke PTRACE SYSCALL-aanvraag de huidige ruwe geheugenverschillen-lijst ledigen.

3.3

Implementatie

Zoals reeds vermeld, werd de implementatie geschreven onder linux op het i386-platform, meer bepaald voor linux kernel 2.4.18. De implementatie is dan ook beschikbaar als een patch tegen deze kernel release. Centraal in deze patch is de datastructuur om de elementen uit de gelinkte lijst in op te slaan. Deze datastructuur is hierop volgend weergegeven. 1 2 3 4 5 6

struct memdiff_struct { struct list_head list ; unsigned long begin_addr ; unsigned long size ; unsigned long id ; };

Als eerste item in deze structuur vinden we een variabele, nodig voor de implementatie van een dubbel gelinkte lijst. De linux kernel voorziet in een standaard implementatie voor een gelinkte lijst onder . Er werd dan ook handig gebruik van gemaakt. Het ID-nummer kan verschillende waarden aannemen, naargelang de macro of functie die de elementaire schrijfoperatie uitvoerde. Alle functies/macro’s, die mogelijk een schrijfoperatie uitvoeren naar het geheugen van een proces, zijn —samen met hun ID— in tabel 3.2 weergegeven. Het geheugenbeheer van deze elementen, die steeds deel uitmaken van een dubbel gelinkte lijst, gebeurt aan de hand van een primaire en een secundaire cache. Twee caches werden voorzien om de opbouw van ruwe geheugenverschillen-records door de elementaire schrijfoperaties zo snel mogelijk te houden. Uiteraard zou hiervoor reeds één enkele cache volstaan, maar de voorzieningen op het vlak van geheugenbeheer in de linux kernel maakten het noodzakelijk twee caches te construeren voor maximale prestatie (zie fig. 3.2).

43


linux kernel 2.4.18 Elementaire schrijfoperatie ID include/asm/uaccess.h:__put_user_u64 MEMDIFF_ID__PUT_USER_U64 include/asm/uaccess.h:__put_user_asm MEMDIFF_ID__PUT_USER_ASM include/asm/uaccess.h:__copy_user MEMDIFF_ID__COPY_USER include/asm/uaccess.h: MEMDIFF_ID__ constant copy user CONSTANT COPY USER arch/i386/lib/usercopy.c: MEMDIFF_ID__DO_CLEAR_USER do clear user Tabel 3.2: De elementaire schrijfoperaties in de linux kernel en hun ID’s

buddy system allocator

geheugenpagina’s

secundaire cache: slab allocator

primaire cache: unused_list

record_memdiff ... ptrace

Figuur 3.2: Het geheugensysteem voor de geheugenverschillen-record Als basis geheugenbeheersysteem beschikt de linux kernel over een zogenaamde buddy system allocator [2]. Via dit systeem kan men een macht van twee aan vrije (opeenvolgende) geheugenpagina’s reserveren. Men kan via de buddy system allocator geheugenblokken tot een maximale grootte van 2 MB verkrijgen [6]. Indien nog méér (opeenvolgend) geheugen gewenst is, moet men beroep doen op de vmalloc-functie. Deze functie zorgt ervoor dat verscheidene niet opeenvolgende geheugengebieden, via een virtuele adresruimte, als één groot opeenvolgend geheugengebied kunnen worden gebruikt. Nadeel aan de buddy system allocator is dat deze de grootte van één enkele geheugenpagina als minimum allocatiegrootte kent. Op een Intel Pentium processor is dit 4 KB (of soms 2 MB in Physical Address Extension modus [4]). Indien we bovenstaande element-structuur bekijken, bemerken we dat slechts 20 bytes per element nodig zijn. We zouden, in geval we per element een pagina van 4 KB reserveren, bijgevolg veel geheugen verliezen aan interne fragmentatie. We kunnen hieraan verhelpen door meerdere elementen in één enkele pagina te stockeren. Dit vereist uiteraard het nodige beheer van deze pagina’s. Gelukkig voorziet de linux kernel zelf in een standaardoplossing om aan dit probleem het hoofd te bieden. Linux bezit namelijk een zogenaamde slab allocator. Deze werd in 1994 door Sun Microsystem ontwikkeld voor hun Solaris 2.4 besturingssysteem en werd gretig door de linux-gemeenschap overgenomen om als cache-systeem in hun kernel te dienen. De slab allocator is er ter verhelping van een aantal zaken: • Om het aantal aanvragen aan de buddy system allocator te reduceren. Een aanvraag aan de buddy system allocator kan namelijk heel wat in werking laten


44

treden indien er niet onmiddellijk genoeg geheugen beschikbaar is. Daar een slab cache steeds enkele vrije objecten beschikbaar houdt in zogenaamde slabs (=plakjes), kan een allocatie snel gebeuren. • Doordat de slab allocator zoveel mogelijk objecten in één enkele pagina probeert te stoppen, is de interne fragmentatie minimaal. • De slab allocator kent zogenaamde slab coloring. Dit zorgt ervoor dat de verschillende slabs, waarin de objecten worden gestockeerd, steeds op een ander adres beginnen. Hiermee tracht men de hardware cache zo vol mogelijk te houden, wat de prestatie ten goede komt. Als secundaire cache werd bijgevolg een slab cache gebruikt. Bovenop de secundaire cache werd echter nog een cache geplaatst, de primaire cache. Dit was nodig omdat de slab cache toch nog heel wat code uitvoert wanneer we één enkel nieuw object wensen aan te maken. Het gebruik van twee caches is niet geheel ongewoon daar de linux kernel dit zelf ook toepast, onder andere bij het beheer van buffer header-datastructuren in zijn disk cache [2]. Deze primaire cache houdt gewoon een gelinkte lijst bij van vrije elementen. Indien een schrijfoperatie een nieuw element aan de ruwe geheugenverschillen-record wenst toe te voegen, zal deze eerst de primaire cache raadplegen. In geval deze nog vrije elementen bezit, zal hieruit zelf een element worden toegekend. Wanneer de primaire cache leeg is, doet die zelf beroep op de secundaire slab cache. Deze slab cache zal zich op zijn beurt, in geval hij zelf geen vrije slabs meer heeft, beroepen op het buddy systeem. De kracht van de verschillende caches komt pas echt tot uiting wanneer een element wordt vrijgegeven. Een vrijgave van een element zal doorgaans nooit verder propageren dan de eerste cache. Tijdens het tracen dus, zal doorgaans enkel de eerste cache worden gebruikt. Slechts wannneer we stoppen met het tracen van programma’s, zal deze primaire cache geheel worden geledigd. Dit ledigen echter gebeurt enkel maar naar de secundaire cache toe. De pagina’s van de vrije elementen blijven dus door de slab cache bezet. Enkel indien het buddy systeem geheugen tekort komt, zal deze aan alle slab caches vragen om ongebruikte slabs ook effectief vrij te geven. Door het systeem met twee caches hebben we een ongelooflijk snel geheugenbeheer van de elementen, nodig voor de geheugenverschillen-records, kunnen verkrijgen.

Deadlocks Bijzondere aandacht werd besteed om geen deadlocks in de uitbreiding van de ptracesysteemoproep te introduceren. De ptrace-systeemoproep gebruikt zelf steeds een globale kernel-lock tijdens zijn uitvoering. Een globale kernel-lock mag een bepaald proces in kernel modus meerdere malen plaatsen. Hierdoor heeft men een groot aandeel van de mogelijke deadlocks in de linux kernel kunnen wegwerken. Hiervan profiteert de geschreven uitbreiding op de ptrace-systeemoproep uiteraard ook. Verder werd ook gecontroleerd of het instrumenteren van de verschillende elementaire schrijfoperaties niet tot deadlocks kan leiden. De linux kernel is hierin ook zeer goed qua beleid; deze schrijfoperaties mogen van de linux kernel slapen [7]. Dit houdt (onder andere) in dat men in deze operaties zelf ook geheugen mag alloceren. Dit is nodig om


45

een nieuw element aan de ruwe geheugenverschillen-record te kunnen toevoegen. Op functies die mogen slapen, mag men toch al geen spinlock plaatsen. Daar de allocatie van elementen in de elementaire schrijfoperaties vervat zit, zijn we verzekerd dat de allocatie zelf geen spinlocks in de weg heeft. Dit kan dus normaal gezien niet leiden tot deadlocks. Indien op een schrijfoperatie echter wel een spinlock zou zitten en de primaire cache besluit aan de secundaire cache een aanvraag tot een nieuwe element door te spelen en deze secundaire cache besluit op zijn beurt dat hiertoe een nieuwe slab nodig is en raadpleegt het buddy systeem, dan kunnen we in problemen komen. Wanneer dit buddy systeem immers besluit dat er een sweap over verschillende systemen nodig is om extra pagina’s vrij te krijgen, zou het kunnen dat deze sweap spinlocks willen plaatsen die reeds gezet zijn. Dit zou mogelijk tot een deadlock kunnen leiden. Vandaar dat de linux kernel van programmeurs afdwingt dat ze op elementaire schrijfoperaties geen spinlocks plaatsen. Daar de linux kernel in zijn elementaire schrijfoperaties nochtans rechtstreeks geen geheugen reserveert, kan het toch zijn dat bovenstaand watervaleffect wordt veroorzaakt. Het COW-systeem voor processen kan dit namelijk teweegbrengen. Wanneer een systeemoproep naar een geheugengebied van een bepaald proces wenst te schrijven, waaraan nog geen geheugenpagina werd toegekend, zal dit leiden tot een allocatie van pagina’s. Dit zou via de buddy system allocator tot deadlocks leiden. Vandaar dat linux afdwingt dat de elementaire schrijfoperaties moeten kunnen slapen. In geval linux het niet nodig zou achten dat elementaire schrijfoperaties kunnen slapen, zouden we voor de uitbreidingen op de ptrace-systeemoproep ernstig in de problemen komen. Gelukkig is linux logisch geconstrueerd en laat het zeer dynamische wijzigingen in de kernel toe.

Instrumenteren van de elementaire schrijfoperaties Daar het i386-platform onder linux slechts 5 elementaire schrijfoperaties kent (zie tabel 3.2), vereiste het dan ook niet veel werk om deze schrijfoperaties te instrumenteren, zodat ze een element aan de ruwe geheugenverschillen-record toevoegen. Het opsporen van deze 5 elementaire schrijfoperaties was echter wel een tijdverslindende bezigheid. Hiertoe dienden namelijk vele inline assembler-functies te worden onderzocht. Verder moet men bij het instrumenteren van macro’s enorm opletten. Zo is het nodig volgende macro, 1

#define DO_IT ( x ) foo ( x ) ; foo ( x )

te herschrijven als, 1 2 3 4

#define DO_IT ( x ) do { \ __typeof__ ( x ) __local_x = ( x ) ; \ foo ( __local_x ) ; foo ( __local_x ) ; \ } while ( 0 )

Het do-while-statement is nodig zodat de compiler de macro, na pre-processing, als één enkel statement zou aanzien. Verder is de localization van de x-expressie noodzakelijk om dubbele evaluatie van deze expressie te voorkomen.


3.4

46

Gebruik

In volgend codefragment wordt het gebruik van de uitbreidingen op de ptrace-systeemoproep toegelicht. 1 2 3

4 5 6 7

int raw_writes , raw_record_size ; char ∗ raw_record ; raw_writes = ptrace ( PTRACE_RAWMEMDIFF , pid , & raw_record_size , NULL ) ; raw_record = malloc ( raw_record_size ) ; ptrace ( PTRACE_RAWMEMDIFF , pid , NULL , raw_record ) ; / / . . . use raw_record . . . free ( raw_record ) ;

Men dient dus in eerste instantie de grootte van de geheugenverschillen-record op te vragen. Aan de hand hiervan kan men het nodige geheugen voor deze record reserveren. In het zonet gealloceerde geheugen kunnen we vervolgens de geheugenverschillen-record ook effectief laden. Analoge werkwijze is vereist om de genormaliseerde geheugenverschillen-records op te vragen.

Hoofdstuk 4 Input replay onder Linux In dit hoofdstuk wordt de replay-module, ontworpen voor het besturingssysteem linux, behandeld. Verder wordt het gebruik van deze module toegelicht, alsook de instelbaarheid.

4.1

Ontwerp van de replay-module

Gewapend met de uitbreidingen op de ptrace-systeemoproep, zoals die in voorgaand hoofdstuk werden behandeld, kan men “makkelijk” een replay-module onder linux construeren. De replay-module werd als een bibliotheek ontwikkeld en laat zich dan ook zo gebruiken. In fig. 4.1 staat het basisontwerp van de replay-module afgebeeld. De proces systeem− oproep

handler terug− keer

tracer

handler dispatcher

handler handler handler

besturingssysteem

replay−module

Figuur 4.1: De replay-module replay-bibliotheek omvat slechts één functie, attach tracer genaamd. Via deze functie installeert de replay-module zich tussen het besturingssysteem en het proces dat attach tracer opriep en dus gereplayet wil worden. Hierbij wordt een nieuw proces opgestart —in een nieuwe virtuele adresruimte om be¨ınvloeding van het te replayen proces door de tracer te beperken— waarin men de tracer laat koppelen aan zijn ouderproces. Door dit koppelen via de ptrace-systeemoproep wordt de tracer tijdelijk de ouder van zijn ouderproces. De attach tracer functie levert simpelweg de waarde 0 terug wanneer alles succesvol verloopt, anders wordt de waarde -1 geretourneerd. Deze functie kent geen enkele 47

HOOFDSTUK 4. INPUT REPLAY ONDER LINUX

48

parameter daar de replay-module zich geheel via omgevingsvariabelen en configuratiebestanden laat instellen. De replay-module kent twee modi, RECORD en REPLAY, en de tracer zal zich afhankelijk van de ingestelde modus anders gedragen. In bedrijf zal de tracer elke systeemoproep behandelen en via een dispatcher doorsturen naar de gepaste handler voor betreffende systeemoproep. In replay-fase zal deze tracer tevens controleren of het systeemoproeppatroon niet wordt doorbroken. Indien dit patroon wordt doorbroken, zal de tracer zich loskoppelen van het te tracen proces en wordt bijgevolg het replayen onderbroken. Verder staat deze tracer ook nog in voor soft detaching (zie p. 24). De handlers verzorgen de eigenlijke replay-faciliteiten. Elke handler staat in voor één of meerdere systeemoproepen en dit zowel voor record- als voor replay-fase. Deze handlers bewaren in de record-fase alle nodige terugkeerwaarden van de systeemoproepen in het replay-bestand om deze in de replay-fase opnieuw te injecteren in het te replayen proces. In deze handlers vinden we de verschillende behandelde concepten terug zoals beschreven in hoofdstuk 2, waaronder klassen van systeemoproepen (zie p. 18), permeabiliteit van systeemoproepen (zie p. 24) en tijdsconservatie (zie p. 26). Er zal hier dan ook niet verder worden over uitgewijd. Enkel de permeabiliteit van systeemoproepen vereist nog enige toelichting. Onder linux zijn —zoals bij elke UNIX-variant— de concepten devices en bestanden equivalent. Een device onder linux is gewoon een bestand (meestal) onder de directory /dev. De systeemoproep-permeabiliteit, nodig voor partiële in- en uitvoer, werkt dan ook zowel voor normale bestanden als voor de diverse devices die het systeem kent. De permeabiliteit van systeemoproepen werd dan ook logisch gedefinieerd binnen het domein van de bestanden. Concreet komt het erop neer dat men eigenlijk per bestand kan specificeren of er tijdens de replay-fase in partiële in- of uitvoer moet worden voorzien. Aangezien dit verschillen in kernel contexten met zich meebrengt (zie p. 17), werd in een descriptor-mapping voorzien en dit bij alle systeemoproepen die verband houden met in- en uitvoer van/naar bestanden. Het is belangrijk hierbij op te merken dat er verschillende implementatietechnieken werden gebruikt in de handlers. Zo zijn er zogenaamde stand-alone handlers welke de gehele systeemoproep volledig zelf afhandelen (zie fig. 4.1). Verder zijn er ook handlers die zich deels beroepen op andere handlers om de klus te klaren. Er zijn ook handlers die enkel door andere handlers worden opgeroepen en dus niet rechtstreeks door de tracer zelf. Deze handlers heten abstracte handlers. Elke basis-handler, dit is een handler die rechtstreeks door de tracer kan worden opgeroepen, kan dus op zijn beurt verscheidene andere handlers oproepen dewelke dit op hun beurt ook kunnen doen. Zo onstaat er als het ware een keten van handlers per systeemoproep. Doch alle handlers dienen aan een bepaalde basisconditie te voldoen. Dit zal in de volgende sectie worden toegelicht.

Het replay-bestandsformaat Aangezien de handlers voor zowel de record- als voor de replay-fase instaan, zijn deze handlers ook verantwoordelijk voor de opbouw van het replay-bestand. In de recordfase zullen deze handlers in dit replay-bestand hun nodige informatie wegschrijven. In de replay-fase zullen deze handlers vervolgens hun data opnieuw uit dit replaybestand lezen om in een correcte replay-afhandeling van hun betreffende systeemoproep

49


te kunnen voorzien. Het (mogelijk) geketend zijn van de handlers heeft invloed op de opbouw van het replay-bestand. Dit bestand kent geen vast formaat voor elke systeemoproep, maar wordt dynamisch opgebouwd. Bij elke systeemoproep zal de tracer een kleine header verzorgen in het replay-bestand dewelke slechts het nummer van de huidige systeemoproep bevat. In de record-fase wordt dit nummer door de tracer weggeschreven en in de replay-fase gebruikt de tracer dit nummer om te controleren of het systeemoproeppatroon wel wordt gevolgd alvorens te dispatchen naar de handlers toe. Elke handler zal op zijn beurt, indien hij het nodig acht, data toevoegen aan het replay-bestand zodat deze handler in de replay-fase zijn taak kan volbrengen. De enige voorwaarde waaraan een handler moet voldoen, om geen corrupt replay-bestand te veroorzaken, luidt als volgt: Exact dezelfde hoeveelheid data, als weggeschreven tijdens de record-fase, dient in de replay-fase te worden gelezen. Indien elke handler zich aan bovenstaande regel houdt, wordt het replay-bestand tijdens de record-fase mooi gelaagd opgebouwd om vervolgens in de replay-fase opnieuw te worden afgewonden door de verschillende handlers. De verschillende mogelijke lagen in een replay-bestand, gecreëerd door een handler, zijn in fig. 4.2 weergegeven. Hier handler−keten: tracer T

handler 1

handler 2

mogelijke replay−bestanden: T

2

T

1

2

(A)

T

2

1

(B)

T

1

2

(C) 1

(D)

Figuur 4.2: De opbouw van het replay-bestand hebben we een bepaalde systeemoproep die door de tracer T voor afhandeling wordt doorverwezen naar handler 1. Deze handler roept op zijn beurt handler 2 op. Dergelijke situatie doet zich veelal voor wanneer handler 2 nét niet genoeg doet om in de replay van betreffende systeemoproep te kunnen voorzien. In dit geval zal men een overkoepelende handler —hier handler 1— schrijven die ervoor zorgt dat de betreffende systeemoproep vooralsnog correct kan worden gereplayet. Zoals in figuur 4.2 (A) aangegeven, volgt na de header van de tracer T meestal een datablok door handler 2. Het kan echter zijn dat handler 1 het ook nodig acht om informatie in het replay-bestand te stockeren zodat deze een perfecte replay kan bekomen. De handler 1 kan dit ofwel net vóór of net ná de data van handler 2 plaatsen (zie fig. 4.2 (B) resp. (C)). Dit is afhankelijk van wat handler 1 beslist eerst te doen: wegschrijven van zijn data ofwel eerst handler 2 oproepen. De enige voorwaarde die men hierbij aan een handler stelt, is dat de volgorde waarin deze zijn data plaatst ten aanzien van andere handlers die hij oproept, dezelfde is als de volgorde waarin deze handler tijdens de replay-fase de data terug uit het replay-bestand leest. Anders zal dit leiden tot een verkeerd gebruik van het replaybestand tijdens de replay-fase. Verder kan het ook zijn dat een handler het nodig acht


50

zowel net vóo´r als net ná de data van zijn ouder-handler(s) data te plaatsen, zoals weergegeven in fig. 4.2 (D). Door de dynamische gelaagde opbouw van het replay-bestand is het bestandsformaat sterk afhankelijk van de versie van de gebruikte replay-module. Een replay-bestand, opgebouwd tijdens een record-fase door replay-module versie 1, zal doorgaans niet meer kunnen worden gebruikt door een replay-module versie 2. Hierdoor was het noodzakelijk ieder replay-bestand van een vaste header te voorzien die —naast het magische getal 0xbabe— een versienummer bevat van de replay-module die werd aangewend om het replay-bestand te construeren. Een replay-module zal enkel een replay-bestand gebruiken indien het versienummer uit de header exact overeenkomt met zijn eigen versienummer. Men is uiteraard sterk afhankelijk van de versie van de gebruikte replay-module, doch dit weegt echter niet op tegen de conventionele manier waarop men bestandsformaten definieert. Aangezien de linux 2.4 kernel 237 verschillende systeemoproepen kent, zouden we evenveel headers voor deze systeemoproepen moeten definiëren. Dit zou een helse bedoening zijn. Vandaar de keuze om het replay-bestand als een stream te gebruiken. Zoals reeds vermeld, zal hier niet verder worden ingegaan op de implementatie van de verschillende handlers en hoe deze precies de replay verzorgen. De uiteenzettingen hierover zouden te technisch zijn, waardoor niemand —behalve ontwerpers van replaymodules— er iets zou aan hebben. In bijlage B werd de broncode van één handler uitgeprint, dit ter documentatie.

4.2

Het gebruik van de replay-module

Instellen van de replay-module De replay-module laat zich instellen via enkele omgevingsvariabelen en configuratiebestanden. De instellingen die hier worden besproken, gelden voor de replay-module versie 0.1.13. Vooreerst worden de omgevingsvariabelen toegelicht in tabel 4.1. Via de omgevingsvariabele CONFIGFILE kan een configuratiebestand worden gespecificeerd. Dit bestand is in XML-formaat en dient steeds volgende basis-tag te bevatten: Binnen de -tag kunnen allerlei optionele instellingen gebeuren, veelal met betrekking tot de permeabiliteit van bepaalde systeemoproepen. Via de volgende tag kunnen we ook in het configuratiebestand het te gebruiken replay-bestand instellen: plaats hier uw replay-bestandsnaam Met het oog op het instellen van de permeabiliteit van bepaalde systeemoproepen kan men via volgende tag specificeren of alle namen van bestanden, die door het proces in record-fase worden geopend, op de console moeten afgedrukt worden:


51

MODE Deze variabele is vereist en kan de waarden RECORD of REPLAY aannemen, afhankelijk van de gewenste modus waarin de replay-module dient te opereren. REPLAYFILENAME Deze variabele is optioneel en kan ontkracht worden door mogelijke instellingen in het configuratiebestand. Wanneer noch de omgevingsvariabelen noch het configuratiebestand een replay-bestandsnaam specificeren, zal de replay-module automatisch een naam genereren voor het te replayen programma. CONFIGFILE Deze variabele is optioneel en specificeert een configuratiebestand. Via dit bestand is de replay-module specifieker in te stellen dan mogelijk is met de omgevingsvariabelen. AUTODETACH Deze variabele is optioneel en niet aan te raden in gebruik. Ze wordt ingesteld op het volgnummer van de systeemoproep waarop de replaymodule zich tijdens de replay-fase van het te replayen proces dient los te koppelen. Merk op dat dit zeer gevaarlijk in gebruik kan zijn. Tabel 4.1: De omgevingsvariabelen voor de replay-module

<showopenfilename value="plaats hier “0” of “1”"/> Verder kan men dan ook de permeabiliteit van bepaalde systeemoproepen instellen via de -tag. Deze tag kent twee optionele parameters policy en mmap-policy welke beiden als waarde sandbox ofwel enforce kennen. De parameter policy op sandbox instellen (wat tevens de default-instelling hiervoor is) zorgt ervoor dat alle bestandsinvoer en -uitvoer afgeschermd gebeurt. Hierbij wordt in de replay-fase alle nodige data uit het replay-bestand zelf gehaald en worden de bestanden zelf niet meer geopend. De waarde enforce aan deze parameter toekennen, zorgt er echter voor dat alle data in de replay-fase zo veel mogelijk uit de originele bestanden wordt gehaald. Bemerk dat onder linux —zoals bij elk UNIX-systeem trouwens— devices ook als bestanden worden benaderd. Bijgevolg gelden deze instellingen ook voor alle randapparaten van het systeem. Analoog kan men via de parameter mmap-policy specificeren of memory mapped bestandsinvoer en -uitvoer al dan niet zo veel mogelijk via de originele bestanden gaat. Merk dat mmap-policy="enforce" slechts zinvol is wanneer policy="enforce", daar een gemapt bestand steeds ook werkelijk dient te worden geopend opdat we dit ook effectief zouden kunnen mappen in de replay-fase. Verder kan men binnen de -tag ook nog elk bestand afzonderlijk instellen. Wanneer het globale beleid sandbox is, kan men via volgende tag toch nog toelaten bepaalde bestanden ook effectief tijdens de replay-fase te openen en te gebruiken: <enforce file="plaats hier de naam van het gewenste bestand " type="plaats hier “input” of “output”" mmap="plaats hier “sandbox” of “enforce”"/>


52

Hierbij is de mmap-parameter optioneel. Analoog kan men bij een globaal beleid enforce sommige bestanden manueel afschermen tijdens de replay-fase via de volgende tag: <sandbox file="plaats hier de naam van het gewenste bestand " type="plaats hier “input” of “output”"/> Hierdoor zal de data van deze bestanden tijdens de replay-fase uit het replay-bestand worden gehaald in plaats van uit de bestanden zelf. Deze bestanden worden tijdens de replay-fase dan ook niet meer geopend. Analoge voorzieningen werden getroffen voor de instelbaarheid van de netwerkinvoer en -uitvoer. De tag hiervoor is en dient onder de -tag te worden geplaatst. De allowdiffs-parameter kan worden gebruikt om verschillen in netwerktrafiek in de replay-fase ten opzichte van de record-fase toe te laten. Deze instelling is zeer handig voor het replayen van grafische programma’s onder X-Windows.

Installatie van de replay-module Twee pakketten moeten ge¨ınstalleerd worden om de replay-module te kunnen gebruiken. Deze zijn te vinden op de bijgeleverde CD-ROM (zie bijlage A). Allereerst moet het pakket, exptrace-versienummer .tar.gz worden ge¨ınstalleerd op het systeem. Dit pakket bevat een patch voor recente linux 2.4 kernels. Installatiehulp is te vinden in het bestand INSTALL binnen dit pakket. Een recente linux 2.4 kernel staat tevens op de bijgeleverde CD-ROM. Tenslotte moet men de eigenlijke replay-module installeren. Dit pakket heet: replay-versienummer .tar.gz Verdere hulp bij de installatie is te vinden in het README-bestand van dit pakket.

Input replay van programma’s De replay-module kan zowel dynamisch als statisch gelinkte ELF-programma’s replayen. Om de bruikbaarheid van de replay-bibliotheek te verhogen, zodat een expliciete oproep van de functie attach tracer niet nodig is, werden wrapper-modules ontwikkeld en dit zowel voor statisch als dynamisch gelinkte programma’s.


53

Input replay van statisch gelinkte programma’s Voor statisch gelinkte programma’s wordt de meest simpele record als volgt bekomen: export MODE="RECORD" replay plaats hier de command line voor het te recorden programma Dit zal een replay-bestand aanmaken in de huidige directory. Vervolgens replayen we dit programma via volgende commando’s: export MODE="REPLAY" replay plaats hier exact dezelfde command line als in de record-fase Voorbeelden van het gebruik van de replay-module zijn in het replay-pakket onder de directory tests/ te vinden. Input replay van dynamisch gelinkte programma’s Voor de replay van dynamisch gelinkte programma’s maken we gebruik van de preloader van de ld.so ELF-loader. De meest simpele record voor dynamisch gelinkte programma’s ziet er als volgt uit: export MODE="RECORD" export LD_PRELOAD="libpreload.so" plaats hier de command line voor het te recorden programma export LD_PRELOAD="" Dit replayen gebeurt door, export MODE="REPLAY" export LD_PRELOAD="libpreload.so" plaats hier exact dezelfde command line als in de record-fase export LD_PRELOAD="" Voorbeelden van het gebruik van de replay-module zijn in het replay-pakket onder de directory tests/ te vinden.

Hoofdstuk 5 Besluit Zoals door de replay-module, ontwikkeld bij deze scriptie, bewezen wordt is input replay van systeemoproepen perfect mogelijk. Verschillende methoden voor de input replay van I/O-poorten, I/O-geheugen en bepaalde processorregisters werden voorgesteld en zijn doenbaar te implementeren. Ook is —mits hardware-ondersteuning door de processor voor de constructie van een klok— replay van parallellisme zonder veel prestatieverlies best wel te implementeren. De grote uitdaging schuilt dan ook in een implementatie van een replay-module die zowel de input als het parallellisme weet te replayen.

54

Bijlage A De bijgeleverde CD-ROM De bijgeleverde CD-ROM bevat naast de broncode van de geschreven kernel patch en replay-module ook nog deze scriptie in PDF en PostScript-formaat. Verder werd ook een recente linux 2.4 kernel meegeleverd. De CD-ROM start, bij plaatsing in de speler, de browser met een overzichtspagina. Indien dit niet automatisch gebeurt, kan men index.html op de CD-ROM manueel openen. Alle meegeleverde software valt onder de GNU General Public License.

55

Bijlage B Een codefragment uit de replay-module Om enig idee te hebben van de complexiteit van de replay-module, werd hieronder een codefragment van de handler voor de mmap2-systeemoproep afgebeeld. Deze systeemoproep voorziet in bestands-geheugenmapping. Linux kernel 2.4 kent 237 systeemoproepen. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

17 18 19 20 21 22 23 24 25 26 27 28

/∗ ∗ mmap2( addr , l e n , p r o t , f l a g s , f d , p g o f f ) ∗/ s t a t i c void sc_mmap2 ( int syscall , int after_syscall ) { i f ( record ) { i f ( after_syscall ) { int ret , fd ; unsigned int addr = 0 , length = 0 , prot ; unsigned char replay_mmap = 0 ; ret = get_reg ( EAX ) ; fd = get_param5 ( ) ; prot = get_param3 ( ) ; i f ( ! IS_ERROR ( ret ) ) { unsigned int flags ; i f ( LEGAL_FD ( fd ) && ( file_descs [ fd ] . operations & FILE_OP_MMAP ) ) replay_mmap = 1 ; flags = get_param4 ( ) ; DEBUG ( " sc_mmap2 : fd %d\n", fd); DEBUG (" sc_mmap2 : addr %#x\n", ret); if (!( flags & MAP_ANONYMOUS ) && ! replay_mmap && (prot & ( PROT_READ | PROT_EXEC ))) { /* a file is being mapped ... so save content */ addr = ret; length = get_param2 (); } } else {

56

BIJLAGE B. EEN CODEFRAGMENT UIT DE REPLAY-MODULE DEBUG (" sc_mmap2 : return negative \n"); } save_ret_code (); write_replay_byte ( replay_mmap ); DEBUG (" sc_mmap2 : replay_mmap : % d\n", replay_mmap ); save_mem_area (addr , length );

29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

} } else { static unsigned int __orig_flags , __orig_prot , __orig_start , __orig_ret , __orig_offset , __orig_fd , __replay_mmap ; if (! after_syscall ) { unsigned int flags , prot , start , offset ; restore_ret_code (); __orig_ret = get_reg (EAX); __orig_start = get_param1 (); __orig_prot = get_param3 (); __orig_flags = get_param4 (); __orig_fd = get_param5 (); __orig_offset = get_param6 (); __replay_mmap = read_replay_byte (); DEBUG (" sc_mmap2 : replay mmap : % d\n", __replay_mmap ); DEBUG (" sc_mmap2 : orig fd %d\n", __orig_fd ); DEBUG (" sc_mmap2 : __orig_start %#x\n", ( int) __orig_start ); DEBUG (" sc_mmap2 : __orig_ret: %#x\n", ( int) __orig_ret ); flags = __orig_flags ; prot = __orig_prot ; start = __orig_start ; if ( flags & MAP_ANONYMOUS ) { DEBUG (" sc_mmap2 : anonymous mmap \n"); } if (! IS_ERROR ( __orig_ret )) { start = __orig_ret ; set_param1 ( start ); DEBUG (" sc_mmap2 : trying start %#x\n", ( int) start); flags |= MAP_FIXED ; set_param4 ( flags ); } if ( __replay_mmap ) { int replay_fd ; if (! LEGAL_FD ( __orig_fd )) { DEBUG (" sc_mmap2 : serious error \n"); tracer_exit (); } replay_fd = file_descs [ __orig_fd ]. replay_fd ; set_param5 ( replay_fd ); return ; } if ( IS_ERROR ( __orig_ret )) { DEBUG (" sc_mmap2 : original error returned \n");

57

BIJLAGE B. EEN CODEFRAGMENT UIT DE REPLAY-MODULE return ; // so we also need to error the same way } DEBUG (" sc_mmap2 : trying ANONYMOUS mmap \n"); flags |= MAP_ANONYMOUS ; prot |= PROT_WRITE ; offset = 0; /* is needed I guess */ /* fd doesn’t matter to sys_mmap2 when flags & MAP_ANON */ set_param3 (prot); set_param4 ( flags ); set_param6 ( offset );

80 81 82 83 84 85 86 87 88 89

} else { int ret; ret = get_reg (EAX); if ( ret != __orig_ret ) { // errors should also be the same DEBUG ("mmap : return code not the same \n"); DEBUG ("orig addr: %#x\n", __orig_ret ); DEBUG ("new addr: %#x\n", ret); if ( IS_ERROR ( __orig_ret )) { errno = - __orig_ret ; perror (" sc_mmap2 __orig_ret "); } if ( IS_ERROR (ret)) { errno = - ret; perror (" sc_mmap2 ret"); } if (! IS_ERROR ( __orig_ret )) tracer_exit (); // ok , here we just fake the old error set_reg (EAX , __orig_ret ); } DEBUG (" sc_mmap2 : returned addr %#x\n", ret); set_param1 ( __orig_start ); set_param3 ( __orig_prot ); set_param4 ( __orig_flags ); set_param5 ( __orig_fd ); set_param6 ( __orig_offset ); restore_mem_area (); }

90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118

}

119 120

}

58

Bijlage C Kernel tools dmesg Print or control the kernel ring buffer ksymoops An utility to decode Linux kernel Oops rdev Query/set image root device, RAM disk size, or video mode klogd Kernel Log Daemon modprobe High level handling of loadable modules insmod Insert loadable kernel modules rmmod Unload loadable modules lsmod List loaded modules depmod Handle dependency descriptions for loadable kernel modules ksyms Display exported kernel symbols mknod Make block or character special files genksyms Generate symbol version information kernelversion Program to report major version of kernel modinfo Display information about a kernel module

59

Bibliografie [1] Tigran Aivazian: Linux Kernel 2.4 Internals http://www.moses.uklinux.net/patches/lki.sgml [2] Daniel P. Bovet & Marco Cesati: Understanding the Linux Kernel O’Reilly (ISBN 0-596-00002-2) [3] Intel Architecture: Software Developer’s Manual Volume 2: Instruction Set Reference (Order Number 243191) [4] Intel Architecture: Software Developer’s Manual Volume 3: System Programming Guide (Order Number 243192) [5] J. M. Mellor-Crummey en T. J. LeBlanc: A Software Instruction Counter Computer Science Department, University of Rochester [6] Alessandro Rubini & Jonathan Corbet: Linux Device Drivers O’Reilly (ISBN 0-596-00008-1) [7] Paul Rusty Russel: Unreliable Guide To Locking /usr/src/linux/Documentation/DocBook/kernel-locking.pdf [8] M. Ronsse, K. De Bosschere: Execution replay and debugging ELIS, Ghent Univerity. arXiv:cs.SE/0011006 v1 - 6 Nov 2000 [9] Andrew S. Tanenbaum: Modern Operating Systems (Second edition) Prentice Hall (ISBN 0-13-031358-0)

60

Lijst van figuren 2.1

Invoer, verwerking en uitvoer . . . . . . . . . . . . . . . . . . . . . . .

7

2.2

Processen en het besturingssysteem . . . . . . . . . . . . . . . . . . . .

8

2.3

Meerdere threads binnen een proces . . . . . . . . . . . . . . . . . . . .

10

2.4

Een scheduling-schema bij twee processen . . . . . . . . . . . . . . . . .

11

2.5

Partiële uitvoer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.6

Schrijfoperaties instrumenteren . . . . . . . . . . . . . . . . . . . . . .

21

2.7

Mapping van objecten uit de kernel context . . . . . . . . . . . . . . . .

26

2.8

Een proces met signal handler . . . . . . . . . . . . . . . . . . . . . . .

28

3.1

Schrijfoperaties onder linux instrumenteren . . . . . . . . . . . . . . . .

40

3.2

Het geheugensysteem voor de geheugenverschillen-record . . . . . . . . .

43

4.1

De replay-module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

4.2

De opbouw van het replay-bestand . . . . . . . . . . . . . . . . . . . . .

49

61

Lijst van tabellen 2.1

De overhead door single step execution . . . . . . . . . . . . . . . . . .

29

3.1

De ruwe geheugenverschillen-record . . . . . . . . . . . . . . . . . . . .

41

3.2

De elementaire schrijfoperaties in de linux kernel en hun ID’s . . . . .

43

4.1

De omgevingsvariabelen voor de replay-module . . . . . . . . . . . . . .

51

62

Index patroon, 8 poorten, 13 primaire cache, 44 proces-context, 17 Process Trace, 33

abstracte handlers, 48 basis-handler, 48 best-effort, 24 buddy system allocator, 43 cache, 42 coloring, 44 content-based replay, 6 cyclische debuggers, 1

race-condities, 10 record-fase, 7 replay-bestand, 7 replay-fase, 7 replay-module, 7 return code, 18 ruwe geheugenverschillen-record, 41

data races, 1 deadlocks, 44 dummy systeemoproep, 23

input replay, 1 inter-thread scheduling, 11 interne fragmentatie, 43 interne invoer, 4

sandbox, 23 scheduler, 10 secundaire cache, 44 SIC, 12 signaal handler, 28 signalen, 28 slab allocator, 43 soft detaching, 24, 48 stall modus, 24 stand-alone handlers, 48 stream, 50 stub-code, 38 systeemoproep-patroon, 8 systeemoproepen, 8

kernel-lock, 44 keten, 48 kindproces, 33

threads, 10 time-stamp counter, 14 tracer, 7

externe invoer, 4 fall through, 40 genormaliseerde geheugenverschillen-record, 41 handlers, 48 Heisenbug, 21 Heisenbugs, 3

lock, 10 mappen, 18 mapping, 26 mutexes, 10 normaliseren, 41 ordering-based replay, 6 ouderproces, 33 63

Typeset by pdf-LATEX

Studie en implementatie van input replay door Frank Cornelis

Recommend Documents