AFastFileSystemforUNIX* RevisedJuly27,1983 MarshallKirkMcKusick,WilliamN.Joy†, SamuelJ.Leffler‡,RobertS.Fabry ComputerSystemsResearchGroup ComputerScienceDivision DepartmentofElectricalEngineeringandComputerScience UniversityofCalifornia,Berkeley Berkeley,CA94720 ABSTRACT AreimplementationoftheUNIXfilesystemisdescribed.Thereimplementationprovidessubstantiallyhigherthroughputratesbyusingmoreflexibleallocationpolicies,thatallowbetterlocalityofreferenceandthatcanbeadaptedto awiderangeofperipheralandprocessorcharacteristics.Thenewfilesystem clustersdatathatissequentiallyaccessedandprovidestwoblocksizestoallow fastaccessforlargefileswhilenotwastinglargeamountsofspaceforsmallfiles. FileaccessratesofuptotentimesfasterthanthetraditionalUNIXfilesystem areexperienced.Longneededenhancementstotheuserinterfacearediscussed. Theseincludeamechanismtolockfiles,extensionsofthenamespaceacrossfile systems,theabilitytousearbitrarylengthfilenames,andprovisionsforefficient administrativecontrolofresourceusage. *UNIXisatrademarkofBellLaboratories. †WilliamN.Joyiscurrentlyemployedby:SunMicrosystems,Inc,2550GarciaAvenue,Mountain View,CA94043 ‡SamuelJ.Leffleriscurrentlyemployedby:LucasfilmLtd.,POBox2009,SanRafael,CA94912 ThisworkwasdoneundergrantsfromtheNationalScienceFoundationundergrantMCS80-05144, andtheDefenseAdvanceResearchProjectsAgency(DoD)underArpaOrderNo.4031monitoredby NavalElectronicSystemCommandunderContractNo.N00039-82-C-0235.

FileSystem -i- Contents TABLEOFCONTENTS 1.Introduction 2.Oldfilesystem 3.Newfilesystemorganization .1.Optimizingstorageutilization .2.Filesystemparameterization .3.Layoutpolicies 4.Performance 5.Filesystemfunctionalenhancements .1.Longfilenames .2.Filelocking .3.Symboliclinks .4.Rename .5.Quotas 6.Softwareengineering References CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -1- Introduction 1.Introduction Thispaperdescribesthechangesfromtheoriginal512byteUNIXfilesystemtothenew onereleasedwiththe4.2BerkeleySoftwareDistribution.Itpresentsthemotivationsforthe changes,themethodsusedtoaffectthesechanges,therationalebehindthedesigndecisions,anda descriptionofthenewimplementation.Thisdiscussionisfollowedbyasummaryoftheresults thathavebeenobtained,directionsforfuturework,andtheadditionsandchangesthathavebeen madetotheuservisiblefacilities.Thepaperconcludeswithahistoryofthesoftwareengineering oftheproject. TheoriginalUNIXsystemthatrunsonthePDP-11†hassimpleandelegantfilesystem facilities.Filesysteminput/outputisbufferedbythekernel;therearenoalignmentconstraints ondatatransfersandalloperationsaremadetoappearsynchronous.Alltransferstothediskare in512byteblocks,whichcanbeplacedarbitrarilywithinthedataareaofthefilesystem.No constraintsotherthanavailablediskspaceareplacedonfilegrowth[Ritchie74],[Thompson79]. WhenusedontheVAX-11togetherwithotherUNIXenhancements,theoriginal512byte UNIXfilesystemisincapableofprovidingthedatathroughputratesthatmanyapplications require.Forexample,applicationsthatneedtodoasmallamountofprocessingonalargequantitiesofdatasuchasVLSIdesignandimageprocessing,needtohaveahighthroughputfromthe filesystem.Highthroughputratesarealsoneededbyprogramswithlargeaddressspacesthatare constructedbymappingfilesfromthefilesystemintovirtualmemory.Pagingdatainandoutof thefilesystemislikelytooccurfrequently.Thisrequiresafilesystemprovidinghigherbandwidththantheoriginal512byteUNIXonewhichprovidesonlyabouttwopercentofthemaximumdiskbandwidthorabout20kilobytespersecondperarm[White80],[Smith81b]. ModificationshavebeenmadetotheUNIXfilesystemtoimproveitsperformance.Since theUNIXfilesysteminterfaceiswellunderstoodandnotinherentlyslow,thisdevelopment retainedtheabstractionandsimplychangedtheunderlyingimplementationtoincreaseits throughput.Consequentlyusersofthesystemhavenotbeenfacedwithmassivesoftwareconversion. Problemswithfilesystemperformancehavebeendealtwithextensivelyintheliterature;see [Smith81a]forasurvey.TheUNIXoperatingsystemdrewmanyofitsideasfromMultics,a large,highperformanceoperatingsystem[Feiertag71].OtherworkincludesHydra[Almes78], Spice[Thompson80],andafilesystemforalispenvironment[Symbolics81a]. Amajorgoalofthisprojecthasbeentobuildafilesystemthatisextensibleintoanetworkedenvironment[Holler73].Otherworkonnetworkfilesystemsdescribecentralizedfile servers[Accetta80],distributedfileservers[Dion80],[Luniewski77],[Porcar82],andprotocolsto reducetheamountofinformationthatmustbetransferredacrossanetwork[Symbolics81b], [Sturgis80]. †DEC,PDP,VAX,MASSBUS,andUNIBUSaretrademarksofDigitalEquipmentCorporation. CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -2- Oldfilesystem 2.OldFileSystem IntheoldfilesystemdevelopedatBellLaboratorieseachdiskdrivecontainsoneormore filesystems.†Afilesystemisdescribedbyitssuper-block,whichcontainsthebasicparametersof thefilesystem.Theseincludethenumberofdatablocksinthefilesystem,acountofthemaximumnumberoffiles,andapointertoalistoffreeblocks.Allthefreeblocksinthesystemare chainedtogetherinalinkedlist.Withinthefilesystemarefiles.Certainfilesaredistinguished asdirectoriesandcontainpointerstofilesthatmaythemselvesbedirectories.Everyfilehasa descriptorassociatedwithitcalledaninode.Theinodecontainsinformationdescribingownershipofthefile,timestampsmarkinglastmodificationandaccesstimesforthefile,andanarray ofindicesthatpointtothedatablocksforthefile.Forthepurposesofthissection,weassume thatthefirst8blocksofthefilearedirectlyreferencedbyvaluesstoredintheinodestructure itself*.Theinodestructuremayalsocontainreferencestoindirectblockscontainingfurtherdata blockindices.Inafilesystemwitha512byteblocksize,asinglyindirectblockcontains128furtherblockaddresses,adoublyindirectblockcontains128addressesoffurthersingleindirect blocks,andatriplyindirectblockcontains128addressesoffurtherdoublyindirectblocks. Atraditional150megabyteUNIXfilesystemconsistsof4megabytesofinodesfollowedby 146megabytesofdata.Thisorganizationsegregatestheinodeinformationfromthedata;thus accessingafilenormallyincursalongseekfromitsinodetoitsdata.Filesinasingledirectory arenottypicallyallocatedslotsinconsecutivelocationsinthe4megabytesofinodes,causing manynon-consecutiveblockstobeaccessedwhenexecutingoperationsonallthefilesinadirec-tory. Theallocationofdatablockstofilesisalsosuboptimum.Thetraditionalfilesystemnever transfersmorethan512bytesperdisktransactionandoftenfindsthatthenextsequentialdata blockisnotonthesamecylinder,forcingseeksbetween512bytetransfers.Thecombinationof thesmallblocksize,limitedread-aheadinthesystem,andmanyseeksseverelylimitsfilesystem throughput. ThefirstworkatBerkeleyontheUNIXfilesystemattemptedtoimprovebothreliability andthroughput.Thereliabilitywasimprovedbychangingthefilesystemsothatallmodificationsofcriticalinformationwerestagedsothattheycouldeitherbecompletedorrepairedcleanly byaprogramafteracrash[Kowalski78].Thefilesystemperformancewasimprovedbyafactorof morethantwobychangingthebasicblocksizefrom512to1024bytes.Theincreasewasbecause oftwofactors;eachdisktransferaccessedtwiceasmuchdata,andmostfilescouldbedescribed withoutneedtoaccessthroughanyindirectblockssincethedirectblockscontainedtwiceasmuch data.Thefilesystemwiththesechangeswillhenceforthbereferredtoastheoldfilesystem. Thisperformanceimprovementgaveastrongindicationthatincreasingtheblocksizewasa goodmethodforimprovingthroughput.Althoughthethroughputhaddoubled,theoldfilesystemwasstillusingonlyaboutfourpercentofthediskbandwidth.Themainproblemwasthat althoughthefreelistwasinitiallyorderedforoptimalaccess,itquicklybecamescrambledasfiles werecreatedandremoved.Eventuallythefreelistbecameentirelyrandomcausingfilestohave theirblocksallocatedrandomlyoverthedisk.Thisforcedthedisktoseekbeforeeveryblock access.Althougholdfilesystemsprovidedtransferratesofupto175kilobytespersecondwhen theywerefirstcreated,thisratedeterioratedto30kilobytespersecondafterafewweeksofmoderateusebecauseofrandomizationoftheirfreeblocklist.Therewasnowayofrestoringtheperformanceanoldfilesystemexcepttodump,rebuild,andrestorethefilesystem.Anotherpossibilitywouldbetohaveaprocessthatperiodicallyreorganizedthedataonthedisktorestore localityassuggestedby[Maruyama76]. †Afilesystemalwaysresidesonasingledrive. *Theactualnumbermayvaryfromsystemtosystem,butisusuallyintherange5-13. CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -3- Newfilesystem 3.Newfilesystemorganization Asintheoldfilesystemorganizationeachdiskdrivecontainsoneormorefilesystems.A filesystemisdescribedbyitssuper-block,thatislocatedatthebeginningofitsdiskpartition. Becausethesuper-blockcontainscriticaldataitisreplicatedtoprotectagainstcatastrophicloss. Thisisdoneatthetimethatthefilesystemiscreated;sincethesuper-blockdatadoesnot change,thecopiesneednotbereferencedunlessaheadcrashorotherharddiskerrorcausesthe defaultsuper-blocktobeunusable. Toinsurethatitispossibletocreatefilesaslargeas2↑32byteswithonlytwolevelsofindirection,theminimumsizeofafilesystemblockis4096bytes.Thesizeoffilesystemblockscan beanypoweroftwogreaterthanorequalto4096.Theblocksizeofthefilesystemismaintained inthesuper-blocksoitispossibleforfilesystemswithdifferentblocksizestobeaccessiblesimul-taneouslyonthesamesystem.Theblocksizemustbedecidedatthetimethatthefilesystemis created;itcannotbesubsequentlychangedwithoutrebuildingthefilesystem. Thenewfilesystemorganizationpartitionsthediskintooneormoreareascalledcylinder groups.Acylindergroupiscomprisedofoneormoreconsecutivecylindersonadisk.Associated witheachcylindergroupissomebookkeepinginformationthatincludesaredundantcopyofthe super-block,spaceforinodes,abitmapdescribingavailableblocksinthecylindergroup,and summaryinformationdescribingtheusageofdatablockswithinthecylindergroup.Foreach cylindergroupastaticnumberofinodesisallocatedatfilesystemcreationtime.Thecurrent policyistoallocateoneinodeforeach2048bytesofdiskspace,expectingthistobefarmore thanwilleverbeneeded. Allthecylindergroupbookkeepinginformationcouldbeplacedatthebeginningofeach cylindergroup.Howeverifthisapproachwereused,alltheredundantinformationwouldbeon thetopplatter.Thusasinglehardwarefailurethatdestroyedthetopplattercouldcausetheloss ofallcopiesoftheredundantsuper-blocks.Thusthecylindergroupbookkeepinginformation beginsatafloatingoffsetfromthebeginningofthecylindergroup.Theoffsetforeachsuccessive cylindergroupiscalculatedtobeaboutonetrackfurtherfromthebeginningofthecylinder group.Inthiswaytheredundantinformationspiralsdownintothepacksothatanysingletrack, cylinder,orplattercanbelostwithoutlosingallcopiesofthesuper-blocks.Exceptforthefirst cylindergroup,thespacebetweenthebeginningofthecylindergroupandthebeginningofthe cylindergroupinformationisusedfordatablocks.† 3.1.Optimizingstorageutilization Dataislaidoutsothatlargerblockscanbetransferredinasingledisktransfer,greatly increasingfilesystemthroughput.Asanexample,considerafileinthenewfilesystemcomposed of4096bytedatablocks.Intheoldfilesystemthisfilewouldbecomposedof1024byteblocks. Byincreasingtheblocksize,diskaccessesinthenewfilesystemmaytransferuptofourtimesas muchinformationperdisktransaction.Inlargefiles,several4096byteblocksmaybeallocated fromthesamecylindersothatevenlargerdatatransfersarepossiblebeforeinitiatingaseek. ThemainproblemwithbiggerblocksisthatmostUNIXfilesystemsarecomposedofmany smallfiles.Auniformlylargeblocksizewastesspace.Table1showstheeffectoffilesystem blocksizeontheamountofwastedspaceinthefilesystem.Themachinemeasuredtoobtain thesefiguresisoneofourtimesharingsystemsthathasroughly1.2Gigabyteofon-linestorage. Themeasurementsarebasedontheactiveuserfilesystemscontainingabout920megabytesof formatedspace.Thespacewastedismeasuredasthepercentageofspaceonthedisknotcontaininguserdata.Astheblocksizeonthediskincreases,thewasterisesquickly,toanintolerable 45.6%wastewith4096bytefilesystemblocks. Tobeabletouselargeblockswithoutunduewaste,smallfilesmustbestoredinamoreefficientway.Thenewfilesystemaccomplishesthisgoalbyallowingthedivisionofasinglefile †Whileitappearsthatthefirstcylindergroupcouldbelaidoutwithitssuper-blockatthe‘‘known’’ location,thiswouldnotworkforfilesystemswithblockssizesof16Korgreater,becauseofthe requirementthatthecylindergroupinformationmustbeginatablockboundary. CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -4- Newfilesystem Spaceused%wasteOrganization 775.2Mb0.0Dataonly,noseparationbetweenfiles 807.8Mb4.2Dataonly,eachfilestartson512byteboundary 828.7Mb6.9512byteblockUNIXfilesystem 866.5Mb11.81024byteblockUNIXfilesystem 948.5Mb22.42048byteblockUNIXfilesystem 1128.3Mb45.64096byteblockUNIXfilesystem Table1−Amountofwastedspaceasafunctionofblocksize. systemblockintooneormorefragments.Thefilesystemfragmentsizeisspecifiedatthetime thatthefilesystemiscreated;eachfilesystemblockcanbeoptionallybrokeninto2,4,or8fragments,eachofwhichisaddressable.Thelowerboundonthesizeofthesefragmentsisconstrainedbythedisksectorsize,typically512bytes.Theblockmapassociatedwitheachcylinder grouprecordsthespaceavailabilityatthefragmentlevel;todetermineblockavailability,aligned fragmentsareexamined.Figure1showsapieceofamapfroma4096/1024filesystem. BitsinmapXXXXXXOOOOXXOOOO Fragmentnumbers0-34-78-1112-15 Blocknumbers0123 Figure1−Examplelayoutofblocksandfragmentsina4096/1024filesystem. Eachbitinthemaprecordsthestatusofafragment;an‘‘X’’showsthatthefragmentisinuse, whilea‘‘O’’showsthatthefragmentisavailableforallocation.Inthisexample,fragments0−5, 10,and11areinuse,whilefragments6−9,and12−15arefree.Fragmentsofadjoiningblocks cannotbeusedasablock,eveniftheyarelargeenough.Inthisexample,fragments6−9cannot becoalescedintoablock;onlyfragments12−15areavailableforallocationasablock. Onafilesystemwithablocksizeof4096bytesandafragmentsizeof1024bytes,afileis representedbyzeroormore4096byteblocksofdata,andpossiblyasinglefragmentedblock.Ifa filesystemblockmustbefragmentedtoobtainspaceforasmallamountofdata,theremainderof theblockismadeavailableforallocationtootherfiles.Asanexampleconsideran11000bytefile storedona4096/1024bytefilesystem.Thisfilewouldusestwofullsizeblocksanda3072byte fragment.Ifno3072bytefragmentsareavailableatthetimethefileiscreated,afullsizeblockis splityieldingthenecessary3072bytefragmentandanunused1024bytefragment.Thisremainingfragmentcanbeallocatedtoanotherfileasneeded. Thegranularityofallocationisthewritesystemcall.Eachtimedataiswrittentoafile,the systemcheckstoseeifthesizeofthefilehasincreased*.Ifthefileneedstoholdthenewdata, oneofthreeconditionsexists: 1)Thereisenoughspaceleftinanalreadyallocatedblocktoholdthenewdata.Thenew dataiswrittenintotheavailablespaceintheblock. 2)Nothinghasbeenallocated.Ifthenewdatacontainsmorethan4096bytes,a4096byte blockisallocatedandthefirst4096bytesofnewdataiswrittenthere.Thisprocessis repeateduntillessthan4096bytesofnewdataremain.Iftheremainingnewdatatobe writtenwillfitinthreeorfewer1024bytepieces,anunallocatedfragmentislocated,otherwisea4096byteblockislocated.Thenewdataiswrittenintothelocatedpiece. 3)Afragmenthasbeenallocated.Ifthenumberofbytesinthenewdataplusthenumberof bytesalreadyinthefragmentexceeds4096bytes,a4096byteblockisallocated.Thecontentsofthefragmentiscopiedtothebeginningoftheblockandtheremainderoftheblock isfilledwiththenewdata.Theprocessthencontinuesasin(2)above.Ifthenumberof bytesinthenewdataplusthenumberofbytesalreadyinthefragmentwillfitinthreeor *Aprogrammaybeoverwritingdatainthemiddleofanexistingfileinwhichcasespacewillalready beallocated. CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -5- Newfilesystem fewer1024bytepieces,anunallocatedfragmentislocated,otherwisea4096byteblockis located.Thecontentsofthepreviousfragmentappendedwiththenewdataiswritteninto theallocatedpiece. Theproblemwithallowingonlyasinglefragmentona4096/1024bytefilesystemisthat datamaybepotentiallycopieduptothreetimesasitsrequirementsgrowfroma1024bytefragmenttoa2048bytefragment,thena3072bytefragment,andfinallya4096byteblock.The fragmentreallocationcanbeavoidediftheuserprogramwritesafullblockatatime,exceptfora partialblockattheendofthefile.Becausefilesystemswithdifferentblocksizesmaycoexiston thesamesystem,thefilesysteminterfacebeenextendedtoprovidetheabilitytodeterminethe optimalsizeforareadorwrite.Forfilestheoptimalsizeistheblocksizeofthefilesystemon whichthefileisbeingaccessed.Forotherobjects,suchaspipesandsockets,theoptimalsizeis theunderlyingbuffersize.ThisfeatureisusedbytheStandardInput/OutputLibrary,apackage usedbymostuserprograms.Thisfeatureisalsousedbycertainsystemutilitiessuchasarchivers andloadersthatdotheirowninputandoutputmanagementandneedthehighestpossiblefile systembandwidth. Thespaceoverheadinthe4096/1024bytenewfilesystemorganizationisempirically observedtobeaboutthesameasinthe1024byteoldfilesystemorganization.Afilesystemwith 4096byteblocksand512bytefragmentshasaboutthesameamountofspaceoverheadasthe512 byteblockUNIXfilesystem.Thenewfilesystemismorespaceefficientthanthe512byteor 1024bytefilesystemsinthatitusesthesameamountofspaceforsmallfileswhilerequiringless indexinginformationforlargefiles.Thissavingsisoffsetbytheneedtousemorespaceforkeepingtrackofavailablefreeblocks.Thenetresultisaboutthesamediskutilizationwhenthenew filesystemsfragmentsizeequalstheoldfilesystemsblocksize. Inorderforthelayoutpoliciestobeeffective,thediskcannotbekeptcompletelyfull.Each filesystemmaintainsaparameterthatgivestheminimumacceptablepercentageoffilesystem blocksthatcanbefree.Ifthethenumberoffreeblocksdropsbelowthislevelonlythesystem administratorcancontinuetoallocateblocks.Thevalueofthisparametercanbechangedatany time,evenwhenthefilesystemismountedandactive.Thetransferratestobegiveninsection4 weremeasuredonfilesystemskeptlessthan90%full.Ifthereserveoffreeblocksissettozero, thefilesystemthroughputratetendstobecutinhalf,becauseoftheinabilityofthefilesystem tolocalizetheblocksinafile.Iftheperformanceisimpairedbecauseofoverfilling,itmaybe restoredbyremovingenoughfilestoobtain10%freespace.Accessspeedforfilescreatedduring periodsoflittlefreespacecanberestoredbyrecreatingthemonceenoughspaceisavailable.The amountoffreespacemaintainedmustbeaddedtothepercentageofwastewhencomparingthe organizationsgiveninTable1.Thus,asiterunningtheold1024byteUNIXfilesystemwastes 11.8%ofthespaceandonecouldexpecttofitthesameamountofdataintoa4096/512bytenew filesystemwith5%freespace,sincea512byteoldfilesystemwasted6.9%ofthespace. 3.2.Filesystemparameterization Exceptfortheinitialcreationofthefreelist,theoldfilesystemignorestheparametersof theunderlyinghardware.Ithasnoinformationabouteitherthephysicalcharacteristicsofthe massstoragedevice,orthehardwarethatinteractswithit.Agoalofthenewfilesystemisto parameterizetheprocessorcapabilitiesandmassstoragecharacteristicssothatblockscanbeallocatedinanoptimumconfigurationdependentway.Parametersusedincludethespeedoftheprocessor,thehardwaresupportformassstoragetransfers,andthecharacteristicsofthemassstoragedevices.Disktechnologyisconstantlyimprovingandagiveninstallationcanhaveseveraldifferentdisktechnologiesrunningonasingleprocessor.Eachfilesystemisparameterizedsothatit canadapttothecharacteristicsofthediskonwhichitisplaced. Formassstoragedevicessuchasdisks,thenewfilesystemtriestoallocatenewblockson thesamecylinderasthepreviousblockinthesamefile.Optimally,thesenewblockswillalsobe wellpositionedrotationally.Thedistancebetween‘‘rotationallyoptimal’’blocksvariesgreatly;it canbeaconsecutiveblockorarotationallydelayedblockdependingonsystemcharacteristics. Onaprocessorwithachannelthatdoesnotrequireanyprocessorinterventionbetweenmass CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -6- Newfilesystem storagetransferrequests,twoconsecutivediskblocksoftencanbeaccessedwithoutsufferinglost timebecauseofaninterveningdiskrevolution.Forprocessorswithoutsuchchannels,themain processormustfieldaninterruptandprepareforanewdisktransfer.Theexpectedtimetoservicethisinterruptandscheduleanewdisktransferdependsonthespeedofthemainprocessor. Thephysicalcharacteristicsofeachdiskincludethenumberofblockspertrackandtherate atwhichthediskspins.Theallocationpolicyroutinesusethisinformationtocalculatethe numberofmillisecondsrequiredtoskipoverablock.Thecharacteristicsoftheprocessorinclude theexpectedtimetoscheduleaninterrupt.Giventhepreviousblockallocatedtoafile,theallocationroutinescalculatethenumberofblockstoskipoversothatthenextblockinafilewillbe comingintopositionunderthediskheadintheexpectedamountoftimethatittakestostarta newdisktransferoperation.Forprogramsthatsequentiallyaccesslargeamountsofdata,this strategyminimizestheamountoftimespentwaitingforthedisktopositionitself. Toeasethecalculationoffindingrotationallyoptimalblocks,thecylindergroupsummary informationincludesacountoftheavailabilityofblocksatdifferentrotationalpositions.Eight rotationalpositionsaredistinguished,sotheresolutionofthesummaryinformationis2millisecondsforatypical3600revolutionperminutedrive. Theparameterthatdefinestheminimumnumberofmillisecondsbetweenthecompletionof adatatransferandtheinitiationofanotherdatatransferonthesamecylindercanbechangedat anytime,evenwhenthefilesystemismountedandactive.Ifafilesystemisparameterizedtolay outblockswithrotationalseparationof2milliseconds,andthediskpackisthenmovedtoasystemthathasaprocessorrequiring4millisecondstoscheduleadiskoperation,thethroughputwill dropprecipitouslybecauseoflostdiskrevolutionsonnearlyeveryblock.Iftheeventualtarget machineisknown,thefilesystemcanbeparameterizedforiteventhoughitisinitiallycreatedon adifferentprocessor.Evenifthemoveisnotknowninadvance,therotationallayoutdelaycan bereconfiguredafterthediskismovedsothatallfurtherallocationisdonebasedonthecharacteristicsofthenewhost. 3.3.Layoutpolicies Thefilesystempoliciesaredividedintotwodistinctparts.Atthetoplevelareglobalpoliciesthatusefilesystemwidesummaryinformationtomakedecisionsregardingtheplacementof newinodesanddatablocks.Theseroutinesareresponsiblefordecidingtheplacementofnew directoriesandfiles.Theyalsocalculaterotationallyoptimalblocklayouts,anddecidewhento forcealongseektoanewcylindergroupbecausethereareinsufficientblocksleftinthecurrent cylindergrouptodoreasonablelayouts.Belowtheglobalpolicyroutinesarethelocalallocation routinesthatusealocallyoptimalschemetolayoutdatablocks. Twomethodsforimprovingfilesystemperformancearetoincreasethelocalityofreference tominimizeseeklatencyasdescribedby[Trivedi80],andtoimprovethelayoutofdatatomake largertransferspossibleasdescribedby[Nevalainen77].Thegloballayoutpoliciestrytoimprove performancebyclusteringrelatedinformation.Theycannotattempttolocalizealldatareferences,butmustalsotrytospreadunrelateddataamongdifferentcylindergroups.Iftoomuch localizationisattempted,thelocalcylindergroupmayrunoutofspaceforcingthedatatobe scatteredtonon-localcylindergroups.Takentoanextreme,totallocalizationcanresultinasin-glehugeclusterofdataresemblingtheoldfilesystem.Theglobalpoliciestrytobalancethetwo conflictinggoalsoflocalizingdatathatisconcurrentlyaccessedwhilespreadingoutunrelated data. Oneallocatableresourceisinodes.Inodesareusedtodescribebothfilesanddirectories. Filesinadirectoryarefrequentlyaccessedtogether.Forexamplethe‘‘listdirectory’’command oftenaccessestheinodeforeachfileinadirectory.Thelayoutpolicytriestoplaceallthefilesin adirectoryinthesamecylindergroup.Toensurethatfilesareallocatedthroughoutthedisk,a differentpolicyisusedfordirectoryallocation.Anewdirectoryisplacedinthecylindergroup thathasagreaterthanaveragenumberoffreeinodes,andthefewestnumberofdirectoriesinit already.Theintentofthispolicyistoallowthefileclusteringpolicytosucceedmostofthetime. Theallocationofinodeswithinacylindergroupisdoneusinganextfreestrategy.Althoughthis CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -7- Newfilesystem allocatestheinodesrandomlywithinacylindergroup,alltheinodesforeachcylindergroupcan bereadwith4to8disktransfers.Thisputsasmallandconstantupperboundonthenumberof disktransfersrequiredtoaccessalltheinodesforallthefilesinadirectoryascomparedtothe oldfilesystemwheretypically,onedisktransferisneededtogettheinodeforeachfileinadirectory. Theothermajorresourceisthedatablocks.Sincedatablocksforafilearetypically accessedtogether,thepolicyroutinestrytoplaceallthedatablocksforafileinthesamecylindergroup,preferablyrotationallyoptimallyonthesamecylinder.Theproblemwithallocatingall thedatablocksinthesamecylindergroupisthatlargefileswillquicklyuseupavailablespacein thecylindergroup,forcingaspillovertootherareas.Usingupallthespaceinacylindergroup hastheaddeddrawbackthatfutureallocationsforanyfileinthecylindergroupwillalsospillto otherareas.Ideallynoneofthecylindergroupsshouldeverbecomecompletelyfull.Thesolution devisedistoredirectblockallocationtoanewlychosencylindergroupwhenafileexceeds32kilobytes,andateverymegabytethereafter.Thenewlychosencylindergroupisselectedfromthose cylindergroupsthathaveagreaterthanaveragenumberoffreeblocksleft.Althoughbigfiles tendtobespreadoutoverthedisk,amegabyteofdataistypicallyaccessiblebeforealongseek mustbeperformed,andthecostofonelongseekpermegabyteissmall. Theglobalpolicyroutinescalllocalallocationroutineswithrequestsforspecificblocks. Thelocalallocationroutineswillalwaysallocatetherequestedblockifitisfree.Iftherequested blockisnotavailable,theallocatorallocatesafreeblockoftherequestedsizethatisrotationally closesttotherequestedblock.Ifthegloballayoutpolicieshadcompleteinformation,theycould alwaysrequestunusedblocksandtheallocationroutineswouldbereducedtosimplebookkeeping. However,maintainingcompleteinformationiscostly;thustheimplementationofthegloballayout policyusesheuristicguessesbasedonpartialinformation. Ifarequestedblockisnotavailablethelocalallocatorusesafourlevelallocationstrategy: 1)Usetheavailableblockrotationallyclosesttotherequestedblockonthesamecylinder. 2)Iftherearenoblocksavailableonthesamecylinder,useablockwithinthesamecylinder group. 3)Ifthecylindergroupisentirelyfull,quadraticallyrehashamongthecylindergroupslooking forafreeblock. 4)Finallyiftherehashfails,applyanexhaustivesearch. Theuseofquadraticrehashispromptedbystudiesofsymboltablestrategiesusedinprogramminglanguages.Filesystemsthatareparameterizedtomaintainatleast10%freespace almostneverusethisstrategy;filesystemsthatarerunwithoutmaintaininganyfreespacetypicallyhavesofewfreeblocksthatalmostanyallocationisrandom.Consequentlythemostimportantcharacteristicofthestrategyusedwhenthefilesystemislowonspaceisthatitbefast. CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -8- Performance 4.Performance Ultimately,theproofoftheeffectivenessofthealgorithmsdescribedintheprevioussection isthelongtermperformanceofthenewfilesystem. Ourempiricstudieshaveshownthattheinodelayoutpolicyhasbeeneffective.Whenrunningthe‘‘listdirectory’’commandonalargedirectorythatitselfcontainsmanydirectories,the numberofdiskaccessesforinodesiscutbyafactoroftwo.Theimprovementsareevenmore dramaticforlargedirectoriescontainingonlyfiles,diskaccessesforinodesbeingcutbyafactorof eight.Thisismostencouragingforprogramssuchasspoolingdaemonsthataccessmanysmall files,sincetheseprogramstendtofloodthediskrequestqueueontheoldfilesystem. Table2summarizesthemeasuredthroughputofthenewfilesystem.Severalcomments needtobemadeabouttheconditionsunderwhichthesetestswererun.Thetestprogramsmeasuretheratethatuserprogramscantransferdatatoorfromafilewithoutperforminganyprocessingonit.Theseprogramsmustwriteenoughdatatoinsurethatbufferingintheoperating systemdoesnotaffecttheresults.Theyshouldalsoberunatleastthreetimesinsuccession;the firsttogetthesystemintoaknownstateandthesecondtwotoinsurethattheexperimenthas stabilizedandisrepeatable.Themethodologyandtestresultsarediscussedindetailin[Kridle83]†.Thesystemswererunningmulti-userbutwereotherwisequiescent.Therewasnocon-tentionforeitherthecpuorthediskarm.TheonlydifferencebetweentheUNIBUSandMASS-BUStestswasthecontroller.AlltestsusedanAmpexCapricorn330MegabyteWinchesterdisk. AsTable2shows,allfilesystemtestrunswereonaVAX11/750.Allfilesystemshadbeenin productionuseforatleastamonthbeforebeingmeasured. TypeofProcessorandRead FileSystemBusMeasuredSpeedBandwidth%CPU old1024750/UNIBUS29Kbytes/sec29/11003%11% new4096/1024750/UNIBUS221Kbytes/sec221/110020%43% new8192/1024750/UNIBUS233Kbytes/sec233/110021%29% new4096/1024750/MASSBUS466Kbytes/sec466/120039%73% new8192/1024750/MASSBUS466Kbytes/sec466/120039%54% Table2a−ReadingratesoftheoldandnewUNIXfilesystems. TypeofProcessorandWrite FileSystemBusMeasuredSpeedBandwidth%CPU old1024750/UNIBUS48Kbytes/sec48/11004%29% new4096/1024750/UNIBUS142Kbytes/sec142/110013%43% new8192/1024750/UNIBUS215Kbytes/sec215/110019%46% new4096/1024750/MASSBUS323Kbytes/sec323/120027%94% new8192/1024750/MASSBUS466Kbytes/sec466/120039%95% Table2b−WritingratesoftheoldandnewUNIXfilesystems. Unliketheoldfilesystem,thetransferratesforthenewfilesystemdonotappeartochange overtime.Thethroughputrateistiedmuchmorestronglytotheamountoffreespacethatis maintained.ThemeasurementsinTable2werebasedonafilesystemrunwith10%freespace. Syntheticworkloadssuggesttheperformancedeterioratestoabouthalfthethroughputrates giveninTable2whennofreespaceismaintained. ThepercentageofbandwidthgiveninTable2isameasureoftheeffectiveutilizationofthe diskbythefilesystem.Anupperboundonthetransferratefromthediskismeasuredbydoing 65536*bytereadsfromcontiguoustracksonthedisk.Thebandwidthiscalculatedbycomparing †AUNIXcommandthatissimilartothereadingtestthatweusedis,‘‘cpfile/dev/null’’,where ‘‘file’’iseightMegabyteslong. *Thisnumber,65536,isthemaximalI/OsizesupportedbytheVAXhardware;itisaremnantofthe system’sPDP-11ancestry. CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -9- Performance thedataratesthefilesystemisabletoachieveasapercentageofthisrate.Usingthismetric,the oldfilesystemisonlyabletouseabout3-4%ofthediskbandwidth,whilethenewfilesystem usesupto39%ofthebandwidth. Inthenewfilesystem,thereadingrateisalwaysatleastasfastasthewritingrate.Thisis tobeexpectedsincethekernelmustdomoreworkwhenallocatingblocksthanwhensimplyreadingthem.Notethatthewriteratesareaboutthesameasthereadratesinthe8192byteblock filesystem;thewriteratesareslowerthanthereadratesinthe4096byteblockfilesystem.The slowerwriteratesoccurbecausethekernelhastodotwiceasmanydiskallocationspersecond, andtheprocessorisunabletokeepupwiththedisktransferrate. Incontrasttheoldfilesystemisabout50%fasteratwritingfilesthanreadingthem.This isbecausethewritesystemcallisasynchronousandthekernelcangeneratedisktransferrequests muchfasterthantheycanbeserviced,hencedisktransfersbuildupinthediskbuffercache. Becausethediskbuffercacheissortedbyminimumseekorder,theaverageseekbetweenthe scheduleddiskwritesismuchlessthantheywouldbeifthedatablocksarewrittenoutinthe orderinwhichtheyaregenerated.Howeverwhenthefileisread,thereadsystemcallisprocessedsynchronouslysothediskblocksmustberetrievedfromthediskintheorderinwhichthey areallocated.Thisforcesthediskschedulertodolongseeksresultinginalowerthroughputrate. Theperformanceofthenewfilesystemiscurrentlylimitedbyamemorytomemorycopy operationbecauseittransfersdatafromthediskintobuffersinthekerneladdressspaceandthen spends40%oftheprocessorcyclescopyingthesebufferstouseraddressspace.Ifthebuffersin bothaddressspacesareproperlyaligned,thistransfercanbeaffectedwithoutcopyingbyusing theVAXvirtualmemorymanagementhardware.Thisisespeciallydesirablewhenlargeamounts ofdataaretobetransferred.Wedidnotimplementthisbecauseitwouldchangethesemantics ofthefilesystemintwomajorways;userprogramswouldberequiredtoallocatebuffersonpage boundaries,anddatawoulddisappearfrombuffersafterbeingwritten. Greaterdiskthroughputcouldbeachievedbyrewritingthediskdriverstochaintogether kernelbuffers.Thiswouldallowfilestobeallocatedtocontiguousdiskblocksthatcouldberead inasingledisktransaction.Mostdiskscontaineither32or48512bytesectorspertrack.The inabilitytousecontiguousdiskblockseffectivelylimitstheperformanceonthesediskstoless thanfiftypercentoftheavailablebandwidth.Sinceeachtrackhasamultipleofsixteensectorsit holdsexactlytwoorthree8192bytefilesystemblocks,orfourorsix4096bytefilesystemblocks. Ifthethenextblockforafilecannotbelaidoutcontiguously,thentheminimumspacingtothe nextallocatableblockonanyplatterisbetweenasixthandahalfarevolution.Theimplication ofthisisthatthebestpossiblelayoutwithoutcontiguousblocksusesonlyhalfofthebandwidth ofanygiventrack.Ifeachtrackcontainsanoddnumberofsectors,thenitispossibletoresolve therotationaldelaytoanynumberofsectorsbyfindingablockthatbeginsatthedesiredrotationalpositiononanothertrack.Thereasonthatblockchaininghasnotbeenimplementedis becauseitwouldrequirerewritingallthediskdriversinthesystem,andthecurrentthroughput ratesarealreadylimitedbythespeedoftheavailableprocessors. Currentlyonlyoneblockisallocatedtoafileatatime.AtechniqueusedbytheDEMOS filesystemwhenitfindsthatafileisgrowingrapidly,istopreallocateseveralblocksatonce, releasingthemwhenthefileisclosediftheyremainunused.Bybatchinguptheallocationthe systemcanreducetheoverheadofallocatingateachwrite,anditcancutdownonthenumberof diskwritesneededtokeeptheblockpointersonthedisksynchronizedwiththeblockallocation [Powell79]. CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -10-Functionalenhancements 5.Filesystemfunctionalenhancements ThespeedenhancementstotheUNIXfilesystemdidnotrequireanychangestothesemanticsordatastructuresviewedbytheusers.Howeverseveralchangeshavebeengenerallydesired forsometimebuthavenotbeenintroducedbecausetheywouldrequireuserstodumpandrestore alltheirfilesystems.Sincethenewfilesystemalreadyrequiresthatallexistingfilesystemsbe dumpedandrestored,thesefunctionalenhancementshavebeenintroducedatthistime. 5.1.Longfilenames Filenamescannowbeofnearlyarbitrarylength.Theonlyuserprogramsaffectedbythis changearethosethataccessdirectories.TomaintainportabilityamongUNIXsystemsthatare notrunningthenewfilesystem,asetofdirectoryaccessroutineshavebeenintroducedthatprovideauniforminterfacetodirectoriesonbotholdandnewsystems. Directoriesareallocatedinunitsof512bytes.Thissizeischosensothateachallocation canbetransferredtodiskinasingleatomicoperation.Eachallocationunitcontainsvariablelengthdirectoryentries.Eachentryiswhollycontainedinasingleallocationunit.Thefirst threefieldsofadirectoryentryarefixedandcontainaninodenumber,thelengthoftheentry, andthelengthofthenamecontainedintheentry.Followingthisfixedsizeinformationisthenull terminatedname,paddedtoa4byteboundary.Themaximumlengthofanameinadirectoryis currently255characters. Freespaceinadirectoryisheldbyentriesthathavearecordlengththatexceedsthespace requiredbythedirectoryentryitself.Allthebytesinadirectoryunitareclaimedbythedirectoryentries.Thisnormallyresultsinthelastentryinadirectorybeinglarge.Whenentriesare deletedfromadirectory,thespaceisreturnedtothepreviousentryinthesamedirectoryunitby increasingitslength.Ifthefirstentryofadirectoryunitisfree,thenitsinodenumberissetto zerotoshowthatitisunallocated. 5.2.Filelocking Theoldfilesystemhadnoprovisionforlockingfiles.Processesthatneededtosynchronize theupdatesofafilehadtocreateaseparate‘‘lock’’filetosynchronizetheirupdates.Aprocess wouldtrytocreatea‘‘lock’’file.Ifthecreationsucceeded,thenitcouldproceedwithitsupdate; ifthecreationfailed,thenitwouldwait,andtryagain.Thismechanismhadthreedrawbacks. ProcessesconsumedCPUtime,byloopingoverattemptstocreatelocks.Lockswereleftlying aroundfollowingsystemcrashesandhadtobecleanedupbyhand.Finally,processesrunningas systemadministratorarealwayspermittedtocreatefiles,sotheyhadtouseadifferentmechanism.Whileitispossibletogetaroundalltheseproblems,thesolutionsarenotstraight-forward, soamechanismforlockingfileshasbeenadded. Themostgeneralschemesallowprocessestoconcurrentlyupdateafile.Severalofthese techniquesarediscussedin[Peterson83].Asimplertechniqueistosimplyserializeaccesswith locks.Toattainreasonableefficiency,certainapplicationsrequiretheabilitytolockpiecesofa file.LockingdowntothebytelevelhasbeenimplementedintheOnyxfilesystemby[Bass81]. However,fortheapplicationsthatcurrentlyrunonthesystem,amechanismthatlocksatthe granularityofafileissufficient. Lockingschemesfallintotwoclasses,thoseusinghardlocksandthoseusingadvisorylocks. Theprimarydifferencebetweenadvisorylocksandhardlocksisthedecisionofwhentooverride them.Ahardlockisalwaysenforcedwheneveraprogramtriestoaccessafile;anadvisorylock isonlyappliedwhenitisrequestedbyaprogram.Thusadvisorylocksareonlyeffectivewhenall programsaccessingafileusethelockingscheme.Withhardlockstheremustbesomeoverride policyimplementedinthekernel,withadvisorylocksthepolicyisimplementedbytheuserprograms.IntheUNIXsystem,programswithsystemadministratorprivilegecanoverrideanyprotectionscheme.Becausemanyoftheprogramsthatneedtouselocksrunassystemadministrators,wechosetoimplementadvisorylocksratherthancreateaprotectionschemethatwascontrarytotheUNIXphilosophyorcouldnotbeusedbysystemadministrationprograms. CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -11-Functionalenhancements Thefilelockingfacilitiesallowcooperatingprogramstoapplyadvisorysharedorexclusive locksonfiles.Onlyoneprocesshasanexclusivelockonafilewhilemultiplesharedlocksmaybe present.Bothsharedandexclusivelockscannotbepresentonafileatthesametime.Ifanylock isrequestedwhenanotherprocessholdsanexclusivelock,oranexclusivelockisrequestedwhen anotherprocessholdsanylock,theopenwillblockuntilthelockcanbegained.Becauseshared andexclusivelocksareadvisoryonly,evenifaprocesshasobtainedalockonafile,anotherprocesscanoverridethelockbyopeningthesamefilewithoutalock. Lockscanbeappliedorremovedonopenfiles,sothatlockscanbemanipulatedwithout needingtocloseandreopenthefile.Thisisuseful,forexample,whenaprocesswishestoopena filewithasharedlocktoreadsomeinformation,todeterminewhetheranupdateisrequired.It canthengetanexclusivelocksothatitcandoaread,modify,andwritetoupdatethefileina consistentmanner. Arequestforalockwillcausetheprocesstoblockifthelockcannotbeimmediately obtained.Incertaininstancesthisisunsatisfactory.Forexample,aprocessthatwantsonlyto checkifalockispresentwouldrequireaseparatemechanismtofindoutthisinformation.Consequently,aprocessmayspecifythatitslockingrequestshouldreturnwithanerrorifalockcan notbeimmediatelyobtained.Beingabletopollforalockisusefulto‘‘daemon’’processesthat wishtoserviceaspoolingarea.Ifthefirstinstanceofthedaemonlocksthedirectorywhere spoolingtakesplace,laterdaemonprocessescaneasilychecktoseeifanactivedaemonexists. Sincethelockisremovedwhentheprocessexitsorthesystemcrashes,thereisnoproblemwith unintentionallocksfilesthatmustbeclearedbyhand. Almostnodeadlockdetectionisattempted.Theonlydeadlockdetectionmadebythesystemisthatthefiledescriptortowhichalockisapplieddoesnotcurrentlyhavealockofthesame type(i.e.thesecondoftwosuccessivecallstoapplyalockofthesametypewillfail).Thusa processcandeadlockitselfbyrequestinglocksontwoseparatefiledescriptorsforthesameobject. 5.3.Symboliclinks The512byteUNIXfilesystemallowsmultipledirectoryentriesinthesamefilesystemto referenceasinglefile.Thelinkconceptisfundamental;filesdonotliveindirectories,butexist separatelyandarereferencedbylinks.Whenallthelinksareremoved,thefileisdeallocated. Thisstyleoflinksdoesnotallowreferencesacrossphysicalfilesystems,nordoesitsupportintermachinelinkage.Toavoidtheselimitationssymboliclinkshavebeenaddedsimilartothescheme usedbyMultics[Feiertag71]. Asymboliclinkisimplementedasafilethatcontainsapathname.Whenthesystem encountersasymboliclinkwhileinterpretingacomponentofapathname,thecontentsofthe symboliclinkisprependedtotherestofthepathname,andthisnameisinterpretedtoyieldthe resultingpathname.Ifthesymboliclinkcontainsanabsolutepathname,theabsolutepathname isused,otherwisethecontentsofthesymboliclinkisevaluatedrelativetothelocationofthelink inthefilehierarchy. Normallyprogramsdonotwanttobeawarethatthereisasymboliclinkinapathname thattheyareusing.Howevercertainsystemutilitiesmustbeabletodetectandmanipulatesymboliclinks.Threenewsystemcallsprovidetheabilitytodetect,read,andwritesymboliclinks, andsevensystemutilitiesweremodifiedtousethesecalls. InfutureBerkeleysoftwaredistributionsitwillbepossibletomountfilesystemsfromother machineswithinalocalfilesystem.Whenthisoccurs,itwillbepossibletocreatesymboliclinks thatspanmachines. 5.4.Rename Programsthatcreatenewversionsofdatafilestypicallycreatethenewversionasatemporaryfileandthenrenamethetemporaryfilewiththeoriginalnameofthedatafile.Intheold UNIXfilesystemstherenamingrequiredthreecallstothesystem.Iftheprogramwereinterruptedorthesystemcrashedbetweenthesecalls,thedatafilecouldbeleftwithonlyits CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -12-Functionalenhancements temporaryname.Toeliminatethispossibilityasinglesystemcallhasbeenaddedthatperforms therenameinanatomicfashiontoguaranteetheexistenceoftheoriginalname. Inaddition,therenamefacilityallowsdirectoriestobemovedaroundinthedirectorytree hierarchy.Therenamesystemcallperformsspecialvalidationcheckstoinsurethatthedirectory treestructureisnotcorruptedbythecreationofloopsorinaccessibledirectories.Suchcorruption wouldoccurifaparentdirectoryweremovedintooneofitsdescendants.Thevalidationcheck requirestracingtheancestryofthetargetdirectorytoinsurethatitdoesnotincludethedirectorybeingmoved. 5.5.Quotas TheUNIXsystemhastraditionallyattemptedtoshareallavailableresourcestothegreatest extentpossible.Thusanysingleusercanallocatealltheavailablespaceinthefilesystem.In certainenvironmentsthisisunacceptable.Consequently,aquotamechanismhasbeenaddedfor restrictingtheamountoffilesystemresourcesthatausercanobtain.Thequotamechanismsets limitsonboththenumberoffilesandthenumberofdiskblocksthatausermayallocate.Aseparatequotacanbesetforeachuseroneachfilesystem.Eachresourceisgivenbothahardanda softlimit.Whenaprogramexceedsasoftlimit,awarningisprintedontheusersterminal;the offendingprogramisnotterminatedunlessitexceedsitshardlimit.Theideaisthatusersshould staybelowtheirsoftlimitbetweenloginsessions,buttheymayusemorespacewhiletheyare activelyworking.Toencouragethisbehavior,usersarewarnedwhenlogginginiftheyareover anyoftheirsoftlimits.Iftheyfailtocorrecttheproblemfortoomanyloginsessions,theyare eventuallyreprimandedbyhavingtheirsoftlimitenforcedastheirhardlimit. CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -13- Softwareengineering 6.Softwareengineering ThepreliminarydesignwasdonebyBillJoyinlate1980;hepresentedthedesignatThe USENIXConferenceheldinSanFranciscoinJanuary1981.Theimplementationofhisdesign wasdonebyKirkMcKusickinthesummerof1981.MostofthenewsystemcallswereimplementedbySamLeffler.ThecodeforenforcingquotaswasimplementedbyRobertElzatthe UniversityofMelbourne. Tounderstandhowtheprojectwasdoneitisnecessarytounderstandtheinterfacesthat theUNIXsystemprovidestothehardwaremassstoragesystems.Atthelowestlevelisaraw disk.Thisinterfaceprovidesaccesstothediskasalineararrayofsectors.Normallythisinterfaceisonlyusedbyprogramsthatneedtododisktodiskcopiesorthatwishtodumpfilesystems.However,userprogramswithproperaccessrightscanalsoaccessthisinterface.Adiskis usuallyformatedwithafilesystemthatisinterpretedbytheUNIXsystemtoprovideadirectory hierarchyandfiles.TheUNIXsysteminterpretsandmultiplexesrequestsfromuserprogramsto create,read,write,anddeletefilesbyallocatingandfreeinginodesanddatablocks.Theinterpretationofthedataonthediskcouldbedonebytheuserprogramsthemselves.Thereasonthatit isdonebytheUNIXsystemistosynchronizetheuserrequests,sothattwoprocessesdonot attempttoallocateormodifythesameresourcesimultaneously.Italsoallowsaccesstobe restrictedatthefilelevelratherthanatthedisklevelandallowsthecommonfilesystemroutines tobesharedbetweenprocesses. Theimplementationofthenewfilesystemamountedtousingadifferentschemeforformatingandinterpretingthedisk.Sincethesynchronizationanddiskaccessroutinesthemselveswere notbeingchanged,thechangestothefilesystemcouldbedevelopedbymovingthefilesystem interpretationroutinesoutofthekernelandintoauserprogram.Thus,thefirststepwasto extractthefilesystemcodefortheoldfilesystemfromtheUNIXkernelandchangeitsrequests tothediskdrivertoaccessestoarawdisk.Thisproducedalibraryofroutinesthatmapped whatwouldnormallybesystemcallsintoreadorwriteoperationsontherawdisk.Thislibrary wasthendebuggedbylinkingitintothesystemutilitiesthatcopy,remove,archive,andrestore files. Anewcrossfilesystemutilitywaswrittenthatcopiedfilesfromthesimulatedfilesystemto theoneimplementedbythekernel.Thiswasaccomplishedbycallingthesimulationlibrarytodo aread,andthenwritingtheresultantdatabyusingtheconventionalwritesystemcall.Asimilar utilitycopieddatafromthekerneltothesimulatedfilesystembydoingaconventionalreadsystemcallandthenwritingtheresultantdatausingthesimulatedfilesystemlibrary. Thesecondstepwastorewritethefilesystemsimulationlibrarytointerpretthenewfile system.Bylinkingthenewsimulationlibraryintothecrossfilesystemcopyingutility,itwas possibletoeasilycopyfilesfromtheoldfilesystemintothenewoneandfromthenewonetothe oldone.Havingthefilesysteminterpretationimplementedinusercodehadseveralmajorbenefits.Theseincludedbeingabletousethestandardsystemtoolssuchasthedebuggerstoset breakpointsandsinglestepthroughthecode.Whenbugswerediscovered,theoffendingproblem couldbefixedandtestedwithouttheneedtorebootthemachine.Therewasneveraperiod whereitwasnecessarytomaintaintwoconcurrentfilesystemsinthekernel.Finallyitwasnot necessarytodedicateamachineentirelytofilesystemdevelopment,exceptforabriefperiod whilethenewfilesystemwasbootstrapped. ThefinalstepwastomergethenewfilesystembackintotheUNIXkernel.Thiswasdone inlessthantwoweeks,sincetheonlybugsremainingwerethosethatinvolvedinterfacingtothe synchronizationroutinesthatcouldnotbetestedinthesimulatedsystem.Againthesimulation systemprovedusefulsinceitenabledfilestobeeasilycopiedbetweenoldandnewfilesystems regardlessofwhichfilesystemwasrunninginthekernel.Thisgreatlyreducedthenumberof timesthatthesystemhadtoberebooted. Thetotaldesignanddebugtimetookaboutonemanyear.Mostoftheworkwasdoneon thefilesystemutilities,andchangingalltheuserprogramstousethenewfacilities.Thecode changesinthekernelwereminor,involvingtheadditionofonlyabout800linesofcode(including CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -14- Softwareengineering comments). CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -15- Softwareengineering Acknowledgements WethankRobertElzforhisongoinginterestinthenewfilesystem,andforaddingdisk quotasinarationalandefficientmanner.WealsoacknowledgeDennisRitchieforhissuggestions ontheappropriatemodificationstotheuserinterface.WeappreciateMichaelPowell’sexplanationsonhowtheDEMOSfilesystemworked;manyofhisideaswereusedinthisimplementation. SpecialcommendationgoestoPeterKesslerandRobertHenryforactinglikerealusersduring theearlydebuggingstagewhenfileswerelessstablethantheyshouldhavebeen.Finallywe thankoursponsors,theNationalScienceFoundationundergrantMCS80-05144,andtheDefense AdvanceResearchProjectsAgency(DoD)underArpaOrderNo.4031monitoredbyNavalElectronicSystemCommandunderContractNo.N00039-82-C-0235. References [Accetta80]Accetta,M.,Robertson,G.,Satyanarayanan,M.,andThompson,M."The DesignofaNetwork-BasedCentralFileSystem",Carnegie-MellonUniver-sity,DeptofComputerScienceTechReport,#CMU-CS-80-134 [Almes78]Almes,G.,andRobertson,G."AnExtensibleFileSystemforHydra"ProceedingsoftheThirdInternationalConferenceonSoftwareEngineering, IEEE,May1978. [Bass81]Bass,J."ImplementationDescriptionforFileLocking",OnyxSystems Inc,73E.TrimbleRd,SanJose,CA95131Jan1981. [Dion80]Dion,J."TheCambridgeFileServer",OperatingSystemsReview,14,4. Oct1980.pp26-35 [Eswaran74]Eswaran,K."Placementofrecordsinafileandfileallocationinacomputernetwork",ProceedingsIFIPS,1974.pp304-307 [Holler73]Holler,J."FilesinComputerNetworks",FirstEuropeanWorkshopon ComputerNetworks,April1973.pp381-396 [Feiertag71]Feiertag,R.J.andOrganick,E.I.,"TheMulticsInput-OutputSystem", ProceedingsoftheThirdSymposiumonOperatingSystemsPrinciples, ACM,Oct1971.pp35-41 [Kridle83]Kridle,R.,andMcKusick,M.,"PerformanceEffectsofDiskSubsystem ChoicesforVAXSystemsRunning4.2BSDUNIX",ComputerSystems ResearchGroup,DeptofEECS,Berkeley,CA94720,TechnicalReport#8. [Kowalski78]Kowalski,T."FSCK-TheUNIXSystemCheckProgram",BellLabora-tory,MurrayHill,NJ07974.March1978 [Luniewski77]Luniewski,A."FileAllocationinaDistributedSystem",MITLaboratory forComputerScience,Dec1977. [Maruyama76]Maruyama,K.,andSmith,S."OptimalreorganizationofDistributed SpaceDiskFiles",CommunicationsoftheACM,19,11.Nov1976.pp 634-642 [Nevalainen77]Nevalainen,O.,Vesterinen,M."DeterminingBlockingFactorsforSequentialFilesbyHeuristicMethods",TheComputerJournal,20,3.Aug1977. pp245-247 [Peterson83]Peterson,G."ConcurrentReadingWhileWriting",ACMTransactionson ProgrammingLanguagesandSystems,ACM,5,1.Jan1983.pp46-55 [Powell79]Powell,M."TheDEMOSFileSystem",ProceedingsoftheSixthSymposiumonOperatingSystemsPrinciples,ACM,Nov1977.pp33-42 CSRGTR/7 July27,1983 McKusick,et.al.

FileSystem -16- References [Porcar82]Porcar,J."FileMigrationinDistributedComputerSystems",Ph.D.Thesis,LawrenceBerkeleyLaboratoryTechReport#LBL-14763. [Ritchie74]Ritchie,D.M.andThompson,K.,"TheUNIXTime-SharingSystem", CACM17,7.July1974.pp365-375 [Smith81a]Smith,A."Input/OutputOptimizationandDiskArchitectures:ASurvey",PerformanceandEvaluation1.Jan1981.pp104-117 [Smith81b]Smith,A."BibliographyonFileandI/OSystemOptimizationand RelatedTopics",OperatingSystemsReview,15,4.Oct1981.pp39-54 [Sturgis80]Sturgis,H.,Mitchell,J.,andIsrael,J."IssuesintheDesignandUseofa DistributedFileSystem",OperatingSystemsReview,14,3.pp55-79 [Symbolics81a]"SymbolicsFileSystem",SymbolicsInc,9600DeSotoAve,Chatsworth, CA91311Aug1981. [Symbolics81b]"ChaosnetFILEProtocol".SymbolicsInc,9600DeSotoAve,Chatsworth, CA91311Sept1981. [Thompson79]Thompson,K."UNIXImplementation",Section31,Volume2B,UNIX ProgrammersManual,BellLaboratory,MurrayHill,NJ07974.Jan1979 [Thompson80]Thompson,M."SpiceFileSystem",Carnegie-MellonUniversity,Deptof ComputerScienceTechReport,#CMU-CS-80-??? [Trivedi80]Trivedi,K."OptimalSelectionofCPUSpeed,DeviceCapabilities,and FileAssignments",JournaloftheACM,27,3.July1980.pp457-473 [White80]White,R.M."DiskStorageTechnology",ScientificAmerican,243(2), August1980. CSRGTR/7 July27,1983 McKusick,et.al.