[PDF] rust os phill
[PDF] rust programming language book github
[PDF] rv rentals in paris texas
[PDF] rv requirements
[PDF] rv seating capacity
[PDF] rvc form e
[PDF] rwandan francs to dollars in 1994
[PDF] rythme cardiaque au repos
[PDF] rythme cardiaque au repos femme
[PDF] rythme cardiaque au repos selon l'age
[PDF] s corp tax return due date
[PDF] s1 form france
[PDF] s1106 ameli
[PDF] s3 and s4 classes in r
[PDF] s4 constructor
IN DEGREE PROJECT COMPUTER SCIENCE AND ENGINEERING,
SECOND CYCLE, 30 CREDITS
, STOCKHOLMSWEDEN2018
Safe Kernel Programming
with Rust
JOHANNES LUNDBERG
KTH ROYAL INSTITUTE OF TECHNOLOGY
SCHOOL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE
SafeKernelProgramming
withRust
JOHANNESLUNDBERG
Masterin ComputerScience
Date:August 14,2018
Supervisor:JohanMontelius
Examiner:MadsDam
Schoolof ComputerScienceand Communication
iii
Abstract
Writingbugfree computercodeis achallengingtaskinalow-level languagelikeC. WhileC compilersare gettingbetterand betteratde- tectingpossiblebugs, theystill havealong waytogo. Forapplication programmingwehavehigherlevel languagesthat abstractawayde- tailsin memoryhandlingand concurrentpr ogramming.However, a lotofan operatingsystem'ssour cecodeis stillwritten inC andthe kernelisexclusively writteninC. Howcanwe makewriting kernel codesafer?What arethe performancepenaltieswe havetopayfor writingsafecode? Inthis thesis,wewill answerthesequestions using theRustpr ogramminglanguage.A RustKernelProgrammingInter- faceisdesigned andimplemented, andanetwork devicedriveris then portedtoRust. TheRustcode isanalyzedto determinethesafeness andthe twoimplementationsar ebenchmarkedfor performanceand comparedtoeachother. Itisshown thatakernel devicedrivercanbe writtenentirely insafeRustcode,butthe interfacelayerr equiresome unsafecode.Measur ementsshowunexpected minorimprovementsto performancewithRust. iv
Sammanfattning
Contents
1Introduction1
1.1Operatingsystem's kernel.. ... ... .. ... ... ..1
1.2Problem description.... ... ... ... ... ... ..1
1.3Purpose. ... ... ... ... ... .. ... ... ... ..2
1.4Goals. ... ... ... ... ... .. ... ... ... ... 2
1.5Methodology. ... ... ... ... .. ... ... ... .3
1.6Limitations. ... ... ... ... ... ... .. ... ... 5
2Background6
2.1Operatingsystem ... ... ... ... .. ... ... ... 6
2.2Kerneland userland.. ... ... ... ... .. ... ..6
2.3Consequencesof software bugs.. ...... ... ... .7
2.4Bugsin thekernel. ... ... ... ... .. ... ... ..7
2.5Rust. ... ... ... ... ... ... .. ... ... ... .8
2.6Relatedwork ... ... ... ... .. ... ... ... ... 13
3Methodology16
3.1Cross-compile Rust..... ... ... .. ... ... ... 18
3.2Portdriver toRust. ... ... ... ... .. ... ... .18
3.3Analysis. ... ... ... ... ... ... .. ... ... .19
4Portinga networkdevicedriver 21
4.1Setup ... ... ... ... ... ... .. ... ... ... .21
4.2RustKPI. ... ... ... ... ... .. ... ... ... ..22
4.3Ruste1000 ... ... ... ... .. ... ... ... ... .23
5Evaluation25
5.1UnsafeCode ... ... ... ... .. ... ... ... ... 25
5.2Performance. ... ... ... ... ... ... .. ... ..28
v viCONTENTS
6Conclusions36
6.1Safeness. ... ... ... ... .. ... ... ... ... .36
6.2Performance. ... ... ... ... .. ... ... ... ..37
6.3Future work..... ... ... ... ... .. ... ... .38
Bibliography39
ADevelopmentprocess 43
A.1Kernelbindings ... .. ... ... ... ... ... ... .43 A.2Mutexes. ... .. ... ... ... ... ... ... ... .44 A.3Malloc ... ... ... ... ... ... ... .. ... ... 44 A.4Concatenateidentifiers ... ... ... ... ... .. ... 44 A.5Automaticcode conversion.. ... ... .. ... ... .44
BListings45
B.1Helloworld kernelmodulein Rust.. ... .. ... ... 45 B.2Hardwar esetup....... ... ... .. ... ... ... 46 B.3LLVM targetconfiguration... ...... ... .. ... .47 B.4e1000C files.. .. ... ... ... ... ... ... ... .48
Chapter1
Introduction
1.1Operatingsystem's kernel
Inanoperating system,everythingis builtaround thekerneland the kernelmanages allinteractionbetween theuser, thesoftware appli- cationsandthe hardware. Therefore itisimportantthatthekernel ishighlyoptimized orthewhole systemwillsuf ferfrom badperfor- mance.To accomplishthis,apowerful,low-levellangu ageisr equired, andforthis reason,the kernelisusually writteninC.InC,the pro- grammerhavefull controland areexpected tomanageeverything whenitcomes tomemory safety.This hassomepr oblematicconse- quencesdescribedin thenextsection.
1.2Problemdescription
Inuserland,applications runin isolatedcompartmentsand oneill- behavingapplicationwill seldomaf fectotherapplications. However, evenifthe applicationscanbe writtenina safer,higher levellanguage itisa falsesenseof safetybecausethey alldependon thekernel.The monolithickernelis essentiallyonebig Cprogram withoutisolated partswhere onesmallbuginone placecancause thewholesystem to fail 1 .Someof thecommonbugs inCcode are: •Doublefree-Freeing memorythathasalreadybeen freed. 1 Themicro kerneldesigntriesto solvethisby isolatingdifferentpartsof theker- nelfrom eachotherbutitdoesn'tsolve theunderlyingpr oblem. 1
2CHAPTER1. INTRODUCTION
•Useafterfree -Accessmemory thathasbeen freed. •Dataraces-Failure touseproperlockingmechanism. Inthebest case,anyof thesebugsin thekernelwould causethesystem tocrash.In theworstcase, theywouldcause subtleerrors thatare difficulttodetectandthat wouldcause allkindsof weirdbehavior intheoperating system.Onecould almostsay, thewholeoperating systemdependson avery fragilecore, similartoa houseofcar ds.
1.3Purpose
Kernelprogramming isinherentlyunsafeandmaking itsaferis notan easytasksince thecodeis runningclose tothehar dwareand hasto behighlyoptimized forperformance.In thepast,ther ehavebeen a fewattempts tomakekernel programmingsafer .Thisinclude sthings fromlanguagecustomizationwith trustedcompilersandtype safeas- semblylanguageto transactionalsemanticsfor systemcalls. Inrecent yearsanewpossiblewayof makingkernelpr ogramming safehassurfaced. Thisis theprogramming languageRust.Among otherfeatures, Rusthasbuiltinstaticanal ysisbasedon ownershipthat catchesbugsthat wouldotherwisego unnoticedina languagelikeC. Itis amodernal ternativetoC andC++that claimstopreventmany ofthe bugscommonto Clikelanguages. Thepurposeof thisthesisis toevaluateRust forsafe kernelprogramming. Asingle devicedriver willbeported toRustto testthethesis. Furtherportingof otherdevice driversorkernel interfacesisleft aspossiblefutur ework.
1.4Goals
Thegoalis todetermineif itisfeasible touseRust asasafer alternative toCin kernellevelpr ogramming.To answerthisquestion wehaveto lookattwo different aspects.
Safeness
Rustcomes intwoflavors, safeRustwith itsstrictcompiler rulesand staticanalysisand unsafeRust, whichunlocksthe powerofraw point- ersandthe riskto"shoot oneselfinthe foot".To beableto inter-
CHAPTER1.INTR ODUCTION3
facewithfor eignlanguagesand dolow-levelmanipulationofmem- ory,Rusthastheability tocompilecode inanunsafe modewhere it permitstheuse ofrawpointers andotherthings regarded as"unsafe". Unsafecodeis required whenwritinglow-level code,typicallyfound inthekernel, butit shouldbekept toaminimum. Forrefer ence,Rust itselfuses unsafecodeinternally towrapthings likerawpointers in safeinterfaces.This thesisshou ldshowhow muchunsafecode isre- quiredtowriteafunctional devicedriverin Rust.
Performance
Aspreviously mentioned,performanceiscriticalinthe operatingsys- tem'skernel andmemorysafety comesata price.Sincethe Rustcom- pilerwilladd thingslike boundarychecksto itssmartpointers, there willbesome performancepenalty. Thisthesisshould showhowmuch theperformance differbetween anativeCimplementationandan equivalentRustimplementation.
1.5Methodology
Themethodologycan bedividedinto thefollowingsteps, listedin chronologicalorder.
Cross-compileRust
Rustbydefault comeswithsupport forcross compilingtodif ferent targetoperatingsystemsand architectures.Itdoesnot howeversup- porta kerneltarget outofthe boxsosomemanualsetupand configu- rationis required. Amongother,aLLVMtarget configurationforthe kernelhas tobewritten. ARustKPI(Rust KernelProgramming Inter- face)iscr eatedasa loadablekernelmodulebyr eusingalot ofthecode foundin Rust'sstandard library.
Porting
Sincethekernel iswritten inCther eexistsno devicedriverswritten inRust.T obe abletocompareperformancebetween RustandC, one
4CHAPTER1. INTRODUCTION
devicedriveris ported 2 fromCtoRust. Thekernelconsists ofvarious subsystemsanddevice drivers,manythat couldbea potentialporting targetforthisthesis. Somerequir ementsare: •Performance-Itshould besomething thatcangenerate high
CPUload andbebenchmarked.
•Fewdependencies-Thework loadshouldbe reasonable,i.e. too manydependenciesto different kernelprogramming interfaces wouldbetoo time-consumingtoport. •Comparison-The Rustimplementationshould becomparable tothe originalCim plementationtogive fairperformancecom- parisonresults. Afterconsideringsystems likeUSBand storageI/O,it wasde- cidedthata suitablecandidate forportingis Intel'sEthernetnetwork carddriver,"e1000".This driverdependsonlyonafew kernelpro- gramminginterfacesapart fromIfLib andnoother driverorsystem dependsonit. Asa networkcard driveritcan alsobepushed togen- eratehighCPU loads.The driverinterfaceswith RustKPIandis cross- compiledforthe kernelthe sameway.
Analysis
WheneverunsafeRust isused inthe codeithas tobeexplicitly marked withanunsafe{...}block.Thedevice drivercode willbeana- lyzedforany usageof unsafeand thecodewithin eachunsafeblock furtherdividedinto differ entcategories,each categorybeingoneac- tionthatRust regar dsasunsafe. Thesafecodewillbeassumedtobe safeasguaranteed bytheRust compiler.
Benchmarks
Iperf[1]is usedto benchmarktheperformance. Iperfisa toolfor networkperformancemeasur ementandit hasbothclientandserver functionality.Iperfruns adurationof tensecondsandoutputsthe averagebitrateand numberof bytestransferred. Toanalyzedeeper theCPU utilizationofRust andCimplementation, CPUutilizationof 2 Portingis whensource codeisr e-writtenfromonelanguageto another,or from oneoperatingsystem toanother.
CHAPTER1.INTR ODUCTION5
kernelthreads aremeasuredduring maximumtransferratebetweena
Bhyvevirtualmachine anditshost.
1.6Limitations
Inthisthesis, thefocus isonthe devicedriver codeanda fewassump- tionsar emaderegardingthe surroundingenvir onments.
Unsafecode
Somecallsto Cfunctionsand Rustunsafefunctions willbewrapped ina safeinterfacefor convenience.Itis assumedthatthe inputcanbe trustedsothatthese areconsider edassafe andnotcounted asunsafe codeforeach invocation.
Rustcompiler
Itisassumed thattheRust compilerisbug freeand cankeepits guar- anteesregar dingmemorysafety.
Kernelmanaged objects
Thekernelis managingsomeobjects usedbythe Rustcode.It isas- sumedthatall pointersto theseobjectshanded totheRustcodebythe kernelare correctandvalid.
PerformanceofRustcode
Sincee1000was portedtoIfLib
3 ,alot oftheheavy liftingis nowdone byIfLib andthedriver codeismostly incharge ofkeepingan internal stateandmanipulating hardware registers.This willlikelyreducethe possibleperformancedif ference inCvsRustimplementations.Port- ingIfLibto Rustas wellwouldp robablygive amore interestingper - formancecomparison. 3 AsofFr eeBSD12code commontonetworkdevicedrivers havebeenmoved to ashared library,IfLib,tosimplify devicedriverdevelopment.
Chapter2
Background
2.1Operatingsystem
Mostcomputersexcept forthesmallest embeddeddevicesr unsome kindofoperating system.Popular operatingsystemson desktopand laptopcomputers areWindows,macOSand Linux.Alsoavailableon personalcomputers butmore popularonservers aretheBSDUnix derivativesFreeBSD, OpenBSD,NetBSDandothers.Windows and macOSare proprietaryandthusnotsuitable forthispurpose.Linux andthe BSDderivativesar eopensour ce,whichmeans thatallofthe softwarethatcomeswith theoperatingsystem isfreely available.Al- thoughanyopen sourceoperating systemcould beused,inthisthesis themostcommon oftheBSD derivatives,FreeBSD [2]isused.
2.2Kernelanduserland
Acommonway todesign anoperatingsystem isbyusing amono- lithickernel.In amonolithic kernel,thekernel isessentiallyone big program,usuallywritteninC. Externalmodulescan beloadedduring runtimetoaddsupport forhardwar edevicesor addnewservices. Userlandisthe partof theoperatingsystem thatexistsoutside of thekernel.Her eiswher etheusers'applications areexecuted inan unprivilegedmode.Access tothe kernelandhar dwareis privileged andis donethr oughsystemcalls tothekernel,whichrunsinprivi- legedmode. Inmodernpr ocessorsprivileged modeiscontr olledby hardwaretoincreasesecurity. 6
CHAPTER2.BA CKGROUND7
Normallyapplicationsexecute inuserland wherethey arekept iso- latedfrom eachotherandthekernel.Ther eare varioussecuritymea- suresinplacetopr otectasystem againstill-behavingapplications.
2.3Consequencesofsoftware bugs
Writingbugfreecomputer codeisa challengingtaskinalow-level languagelikeC. WhileCcompilers aregetting betterandbetter atde- tectingpossiblebugs, theystillhave alongway togo.For application programmingwehavehigher levellanguagesthat abstractawayde- ever,alotof anoperating system'ssource codeisstill writteninC and thekernelis exclusivelywrittenin C. It'sworthmentioning thegravityof theproblems thatsoftware bugscancause. Forexample:
TheNortheastblackout of2003
Aracecondition inthe softwarecaused aseveraldays longelectric blackoutinNortheast USA.[3]
Therac25
Aracecondition inthesoftwar eofa radiationtherapymachine caused themachineto givemassiveover dosesofradiation. Thebugcaused severaldeaths.[4]
2.4Bugsin thekernel
Whilethere aremanyeasilyaccessiblesolutions foruserlandapplica- tions,like usinghigherlevel languages,tohelp avoidthesekinds of accidents,thatis notthe caseforthe kernel.Someexisting techniques usedtopr eventbugsin thekernelarestaticanalysis bythecompiler , codereview andmanualtesting.Noneofthem canmakeany guaran- teesaboutmemory safetyand kerneldevelopersar einneed ofbetter toolstowrite safecode. Therehasbeenattempts tosolvet hisinthepastandsome propos- alsare presentedintherelated worksection.Inthisthesisthe Rust
8CHAPTER2. BACKGROUND
programminglanguage[5]isused asa waytoenfor cesafepr ogram- minginthe kernelandthe goalof thisthesisi stodetermine ifRustis feasibleto useforsafe kernelprogramming.
2.5Rust
Rustwasfirst developedbyGraydon Hoarein 2010butsince shortly afteritsintr oductionitis developedbyMozilla'sRustdeveloperteam. Rustwasdesigned toeliminate manyofthe bugscommon toCand
C++whilenot sacrificingperformance.
Asstatedon Rust'swebsite [5]
Rustisa systemsprogramming languagethatr unsblaz-
inglyfast,pr eventssegfaults, andguaranteesthreadsafety.
Features
•zero-costabstractions •movesemantics •guaranteedmemory safety •threadswithoutdataraces •trait-basedgenerics •patternmatching •typeinfer ence •minimalr untime •efficientCbindings Rustisa languagethatis capableofboth highlevelpr ogramming ofapplicationsas wellaslow-level systemsprogramming. Itdoesnot dependongarbage collectionso itisalso possibletouse inthekernel, asproven byLevyetal., whobuilta kernelin Rust[6]and theRedox teamwhoar ewritingan operatingsystemcompletelyinRust,Redox [7].The Rustbook[8] isacompr ehensiveresour ceforanyone looking formore informationaboutRustandfor moredeeper backgroundin- formationthere alsoexistsmanyresearch papersthathas influenced thedesign ofRust.For example,Rust'stype systemisinfluenced by theCyclonepr oject[9]wher etheCprogramming languageismade saferbyusing statically-scopedregions andtrackedpointers. Tracked
CHAPTER2.BA CKGROUND9
pointersincludeunique pointers,something thatiscentral toRust. Theyalsofound agreat synergybetween regionsand trackedpointers andtheyuse theLIFOr egionmachineryto supportborrow pointers, alsosomethingcentral toRust. Inthepaper ExternalUniquenessis UniqueEnough[10], ClarkandW rigstadshowwith ownershiptypes thatanexternal refer enceisunique whileatthesametimepermitting internalrefer ences. ThreeLayerCakemodel[11]. Inthismodel messagepassingis used forI/Oin thetop layer.The middlelayeruse fork/joinfordivide and conquer.Finallythebottom layeruse SIMDtoparal lelizecomputa- tionsevenfurther wherepossible. InRust'sbibliography alsolisted are,amongother, MicrosoftResear ch'sSingularityprojectpapers[12] and[13].These papersdescribehow safeconcurr encyisachieved in SingularityOSthr oughisolatedpr ocessesandmessagepassingwith channels,somethingthat isa corefeatur einRust.
Rustsafe code
Thedefaultmode forRustis "safeRust".Safe inthiscontext meaning "guaranteedmemorysafety" and"free ofcertainclass ofbugs",not safeasin sandboxedor withlimitedAPI access.Thecompiler makes assertionsatcompile timetoensur ememorysafety .Rustcan ensure memorysafetywith outusinggarbage collectionbecauseofitscentral feature,ownership.Here followsashort descriptionofsomeofRust's featuresandterminologythatis importantto graspinor dertounder - standhowthe languageworks.
Ownership
InRust,every objectcan haveexactlyone owner
1 .Anobject cannot bemovedout ofanownership butcanbe copiedifit implementsthe
Copytrait.
Movesemantics
Ifavariable, ofatype thatdoesnot implementtheCopy trait,isas- signedtoanother variabletheownership istransferred andtheold 1 Avariableowns thedataor objectith oldsorpoints to.Objectscan beshar edby usinghigherlevel constructs likesmartpointers.
10CHAPTER2. BACKGROUND
variablebecomesinvalid. Anyattempt toaccessthe oldvariablewill resultinacompileerr or.Primitive typesimplementthe Copytrait.
Borrow
Tosharean objectonehastoborrow arefer enceto it.Multipleim- mutablerefer encescanexistsimultaneously.Aborrowwill endwhen therefer enceisdropped,i.e.goesoutofscope.
Mutableborrow
Declarationofa newvariableor borrowof arefer enceis alwaysim- mutableunlessexplicitly statedtobe mutable.Formutable references, therecanexistonly oneatany giventimeto prevent dataracesor in- consistentstates.Any attempttoborr owanothermutable reference whileone alreadyexists willresultincompileerr or.
Lifetimes
Referencesareboundby lifetimes.Inmostcases,thesear einferr edby thecompilerbut sometimesonehas toexplicitly assignalifetime to aborr owtotellthecompilerhow longthatr eferencewill existsothe compilercanmake thecorrect analysis.
Rustunsafe code
TheRustbook refersto unsafeRustas asecondlanguage.Therear e conservative.Sometimesthe Rustcompilerwill playittoosafeand the programmerneedstobypass itsstrictr ulesbyusing unsafecode.The otherisbecause theunderlying hardware incomputersis inherently unsafeandRust needstoallow theprogrammer toaccesshar dwareor donearhar dwarepr ogramming.TheseactionsareunsafeinRust: •Dereferencearawpointer. •Callanunsafe functionormethod. •Accessormodify fieldsina union. •Accessor modifyamutable staticvariable.
CHAPTER2.BA CKGROUND11
•Implementanunsafe trait. Rawpointersar efrequently usedwheninterfacingwithC code orimplementinglow-level buildingblocks.It isimportantto keepin mindthe dangerswithraw pointerscompared torefer encesorsmart pointers.Rawpointers •areallowedtoignor etheborr owingrule sandhavebothim- mutableand mutablepointers,or multiplemutablepointers to thesamelocation. •aren'tguaranteedtopointto validmemory. •areallowedtobe null. •don'timplementany automaticclean-up. Itshouldbe mentionedthat evenwithinan unsafeblock,the com- pilerstillchecks references formemorysafety .Unsafecodedoesnot disableanycompiler functionality,it enablesextrafunctionality .For detailsonhow unsafecode isusedin practice,seethe nextsection.
CvsRust comparison
Let'slookat twopracticalexamples onhowRust eliminatessome commonbugs.
Danglingpointer
int return_reference(){ inti=0; return&i;
Listing2.1:Dangling pointerinC
fnreturn_reference<'a>()-> &'ai32{ leti:i32=0; &i
Listing2.2:Dangling pointerinRust
12CHAPTER2. BACKGROUND
Thisisjust oneofmany examples ofsituationswher eonecan end upwithdangling pointers.Whilea modernC compilerwillgive a warningforr eturningar eferencetoalocalvariable, itwillhappily ignoreitandcompilethe codeinlisting 2.1toan executablethatwill crashonexecution. TheRustcode in2.2will failcompilationwith the followingerr or: error[E0597]:'i'does notlivelong enough -->src/main.rs:4:6 4|&i |^ borrowedvaluedoes notlivelong enough 5|} |-borrowed valueonlylives untilhere
Listing2.3:Dangling pointerinRust. Compileerror
TheRustborr ow-checkerdoesnot allowreferencestodata where ther eferencewilloutlivethedata.
Multiplepointers tosamedata
Thiscanlead toseveralbugs likeuseafter freeand dataraces. voidmain(){ int x=malloc( sizeof(int)); int y=x; printf("%d%d\n", x, y);
Listing2.4: Multiplepointersin C
fnmain(){ letx:Box
=Box::new(0i32); lety=x; println!("{:?}{:?}",x,y); Listing2.5:Multiple pointersinRust
anerror byitselfbutit showsthatit iseasyto createmultiplemutable pointerstothe samedata whichthe programmerhas tokeeptrack of.Thissituation caneasilylead tobugs likeuseafter freeif free() iscalledon onepointerwhile theotheris stillinuse. InRust,the ownershipmodeldoes notallowedthis tohappenand thecodein listing2.5 willcausethe followingcompileerr or: CHAPTER2.BA CKGROUND13
error[E0382]:use ofmovedvalue: 'x' -->src/main.rs:4:27 3| lety= x;
|-value movedhere 4|println!("{:?} {:?}",x,y);
|^value usedhereafter move =note:move occursbecause 'x'hastype 'std::boxed::Box< i32>',whichdoes notimplementthe 'Copy'trait Listing2.6:Multiple pointersinRust. Compileerror
SinceBoxdoesnot implementtheCopy trait,theownership ofthedata ismovedto thenew variableandthe oldvariablebecomes invalid. 2.6Relatedwork
Inthis andrelated research paperstheword"safe"is usedinsitua- tionslike"safe code"or"safe programming"and thiscanhave dif- ferentmeanings.Aswe willseein thissection,some research referto "trustedcode"andsomer efertoit as"well-behaving"or "bugfree" code.Ina fewpapersthey alsooverlap. Relatedwork usingRust
Redox Redox[7]is anoperatingsystem entirelywritten inRustand it'susingquotesdbs_dbs17.pdfusesText_23