The BSD Packet Filter: A New Architecture for User ...

1 TheBSDP acketFilter:A NewArchitectureforUser-levelPacketCaptur e StevenMcCanne andVanJacobson LawrenceBerkeleyLaboratoryOneCyclotronRo adBerkeley, Thiscopyingcanbeminimizedbydeployinga kernelagentcalledapacketfilter, (BPF)usesa new, straightforwardbufferingstrategythatmake sitsoverallperformanceupto100timesfaster thanSun s s Unixusersdependonhavingreliable, , thisdependencemeansthatnetworktroublecan makeit impossibletogetusefulworkdoneandincreasi nglyusersandsystemadministratorsfindthat a ,ideally, thesetoolsshouldbeavailablewheretheprobl emsare allowsuchtoolstobeconstructed,a kernelmustcontainsomefacilitythatgivesus er-levelprogramsaccesstoraw,unprocessedn etworktraffic.[7] Mostoftoday s workstationoperatingsystemscontainsucha facility, ,NIT[10] in Thisisa preprintofa papertobepresentedatthe1993 WinterUSENIX conference,January25 29,1993,SanDiego,CA. ThisworkwassupportedbytheDirector, OfficeofEnergyResearch,ScientificComputi ngStaff, ,theUltrixPacketFilter[2] in DEC s UltrixandSnoopinSGI s adapttheXeroxAlto packetfilter to aUnixkernel[8].

2 Whencompletedin 1980,theCMU/StanfordPacketFilter, CSPF, provideda muchneededandwidelyusedfacility. Howeverontoday s machinesitsperformance,andtheperformance ofitsdescendents,leavemuchtobede-sired a designthatwasentirelyappropriatefora 64 KBPDP-11 is simplynota goodmatchtoa , BPF, a 10to 150timesfasterthanSun s : BPFusesa re-designed,register-based filtermachine thatcanbeimplementedefficientlyontoday s memory-stack-basedfiltermachinethatworke dwellonthePDP-11 butis apoormatchtomemory-bottleneckedmodernCPU s. BPFusesa simple,non-sharedbuffermodelmadepos-sibl ebytoday s usualcases , wepresentthedesignofBPF, outlinehowitinterfaceswiththerestofthesy stem, , wepresentperformancemeasurementsofBPF, NIT, ,forexample,theAT&TSTREAMS buffermodelusedbyNITwhichhasenoughoption stobeTuringcompletebutappearsto TheBSDP acketFilter2 TheNetworkTapBPFhastwomaincomponents:the networktapandthepacketfilter. a packetshouldbeacceptedand,if so,howmuchofit to copyto illustratesBPF s packetarrivesata networkinterfacethelinkleveldevicedriver normallysendsit listeningonthisinterface,thedriverfirstc allsBPF.

3 BPFfeedsthepacketto eachparticipatingpro-cess filter . Thisuser-definedfilterdecideswhethera packetis ,BPFcopiestherequestedamountofdatato thebufferassociatedwiththatfilter. thepacketwasnotaddressedto thelocalhost, , networkmonitorlink level driverlink level driverlink level driverprotocol stackbufferfilter networkmonitorbufferfilter rarpduserkernelkernelnetworkBPFF igure1:BPFO verviewSincea processmightwanttolookateverypacketonane tworkandthetimebetweenpacketscanbeonlya fewmicroseconds,it is notpossibletodoa readsystemcallperpacketandBPFmustcollect thedatafromseveralpacketsandreturnit asa unitwhenthemonitoringapplicationdoesa maintainpacketboundaries,BPFencapsulates thecaptureddatafromeachpacketwitha headerthatincludesatimestamp,length, smallsubsetofnetworktraffic,a min-imizememorytraffic,themajorbottlenec kinmostmodernworkstations,thepacketshoul dbefiltered inplace ( ,wherethenetworkinterfaceDMAengineputit) ,ifthepacketis notaccepted, ,SunOS s STREAMSNIT[10] copiesthepack-etsbeforefilteringandasa resultsuffersa (nitpf(4M)) sitsontopofthepacketcapturemodule(nitif( 4M)).

4 Eachpacketreceivedis copiedtoanmbuf,andpassedoff toNIT, whichthenallocatesa thensentupstreamtothepacketfilter, ,a copyofeachpacketis alwaysmade, , ,andtookourmeasurementsona ,howlongit takeseachsystemtostashthepacketintoa buffer. ForBPFwesimplymeasuredthebeforeandaftert imesofthetapcall,bpftap(), usingtheSparcstation s ()plustheadditionaloverheadofcopyingprom iscuouspacketstombufs.(Promiscuouspack-e tsarethosepacketswhichwerenotaddressedto thelocalhost,andarepresentonlybecausethe packetfilterisrun-ning.)Inotherwords,wei ncludedtheperformancehitthatNITtakesforn otfilteringpacketsin obtainaccuratetimings, plottedthemeanprocessingperpacketversusp acketsize,fortwoconfigurations:an acceptall filter , anda rejectall ,theSTREAMSNIT bufferingmodule(nitbuf(4M)) , acceptall , Jan.,1993 SanDiego,CA3 Packet Size (bytes) Mean Per Packet Overhead (usec)0 200 400 600 800 1000 1200 1400 1600 NIT Incremental Overhead: 216 ns/byte BPF Incremental Overhead: 148 ns/byte Figure2:NITversusBPF: acceptall NITlinesshowthatBPFdoesitscopiesatmemory speed(148ns/byte)whileNITruns45%slower(2 16ns/byte).

5 2 They-interceptgivesthefixedper-packetpro cessingoverhead:Theoverheadofa BPFcallisabout6 s whileNITis15timesworseat 89 s showstheresultsforthe rejectall rejectall filterandpusheddirectlyontopoftheNITinte r-facemodule(theNITbufferingmodulewasnot used).Sincethefilterdiscardsallpackets,t heprocessingtimeshouldbeconstant, true weseeessentiallythesamefixedcostaslastti me(5 sinsteadof6 sincerejectingavoidsa calltotheBPFcopyroutine) , asex-plainedearlier, NITdoesn t filterpacketsin placebutinstead2 Thisdifferenceis duetothefactthatNITis notascarefulaboutalign-mentasBPF. ThenetworkdriverwantstheIPheaderalignedo na longwordboundary, butanEthernetheaderis 14bytessothestartofthepacketis longwordalignedboundary,aninefficient, onceinthismeasurement,andagainat theuser-level,whenforinstance,a networkmonitorliketcpdumporetherfindmust copythenetwork-layerportionofthepacketto a (aSTREAMS bufferdescriptor) ,thepacketdatais copiedintoa regionofthemblkwhilelargepacketsmustusea moreelaborateallocatorinvolvingadditiona ldblk( datablock ) discardedbythefilter.

6 Forlargepackets,thisgratuitouscopymakesN ITalmosttwoordersofmagnitudemoreexpensiv ethanBPF(450 s s).Themajorlessonhereisthatfilteringpack etsearlyandinplacepaysoff. Whilea STREAMS-likedesignmightap-pearto bemodularandelegant, claimthatevena STREAMS-basednetworktapshouldincludethep acketfilteringandbufferingfunctionalityi nitslowestlayer. Thereis verylittledesignadvantageinfactor-ingthe packetfilterintoa separatestreamsmodule,butgreatperformanc eadvantagein integratingthepacketfilterandthetapintoa thedesignof thebuffer-ingmodel,5it packetcapturefacilityrejectfarmorepacket sthantheyacceptand,thus,goodperformanceo fthepacketfilteris criticalto requiredbecausethefilteris a separateSTREAM modulepushedontopofthecapturemoduleand,t hus,thecapturemodulemustcopydatatoSTREAM bufferstosendit ,thedocumentationnotesthiscapture/ filter separationis a feature,nota , TheBSDP acketFilterPacket Size (bytes) Mean Per Packet Overhead (usec)0 200 400 600 800 1000 1200 1400 1600 0100200300400500 NITBPF136 NIT Incremental Overhead: 210 ns/byte BPF Incremental Overhead: 0 ns/byte Figure3:NITversusBPF: rejectall Apacketfilterissimplya thevalueof thefunctionistruethekernelcopiesthepacke tfortheapplication.

7 If it isfalsethepacketis :a booleanexpressiontree(usedbyCSPF)anda directedacycliccontrolflowgraphorCFG(fir stusedbyNNStat[1] andusedbyBPF).Forexample,Figure4 il-lustratesthetwomodelswitha thepredicateis true,thelefthandbranchif ,anyfilterthatcanbeexpressedinonecanbeex pressedintheother. However, inimplementationtheyareverydifferent:The treemodelmapsnaturallyintocodeforastackm achinewhiletheCFGmodelmapsnaturallyintoc odefora ,wewillarguethattheCFGapproachlendsitsel fto a (Tree) ,orperforma filterprogramis a program,if thetopofstackhasa non-zerovalueorthestackis emptythenthepacketisaccepted,otherwiseit is :6 bethemajorbottleneckinmod-ernarchitectur es,a filtermodelthatcanusevaluesinmachineregi stersandavoidthismemorytrafficwillbemore efficient. , willcom-putethevalueof evenif shortcircuit operatorsto thefiltermachine,someinefficiencyis intrinsic:Becauseofthe6 Notethatit isnotourintentiontodenigrateCSPF oritsenormouscontributiontothecommunity wesimplywishtoinvestigatetheimple-mentat ionimplicationsof ,theincrementalgainfroma moreefficientfilterdesignwasnegligiblean d,asa result,thedesignersofCSPF investedlesseffortinthefiltermachineryan d,indeed,havepointedoutthatthe filterlanguageisnota resultofcarefulanalysisbutratherembodies severalaccidentsofhistory [8].

8 WinterUSENIX Jan.,1993 SanDiego, RepresentationFALSETRUE yesyesnonoCFG RepresentationFigure4 , packetfield,independentofotherleaves, ,it is alwayspossibletoreorderthegraphinsucha waythatatmostoneparseis , recognizedbythedesigners,is itsinabilitytoparsevariablelengthpacketh eaders, ,TCPheadersencapsulatedin a variablelengthIPheader. Be-causetheCSPF instructionsetdidn t includeanindirectionoperator, onlypacketdataat fixedoffsetsis ,theCSPF modelis restrictedtoa singlesixteenbitdatatypewhichresultsina , thedesigndoesnotpermitaccessto ,it offersa novelgeneralizationofpacketfiltering:The ideaofputtingapseudo-machinelanguageinte rpreterin thekernelprovidesa7 Thisgraphreorderingis,however, a (partoftcpdump[4])containsa thesubjectofa ,sinceCSPF treatsa packetasa simplearrayofbytes,thefilteringmodelis completelyprotocolindepen-dent.(Theappli cationthatspecifiesthefilteris responsibleforencodingthefilterappropria telyfortheunderlyingnet-workmediaandprot ocols.)TheBPFmodel,describedin thenextsection,is hasa packetmanytimes,theCFGmodelallowsparsein formationtobe builtinto ,packetparsestateis remembered inthegraphsinceyouknowwhatpathsyoumustha vetra-versedto reachto a particularnodeandoncea subexpressionis evaluatedit neednotberecomputedsincethecontrolflowgr aphcanalwaysbe(re-)organizedsothevalueis onlyusedat :CFGF ilterFunctionfor hostfoo.

9 Forexample,Figure5 showsa CFGfilterfunctionthatac-ceptsallpacketsw ithanInternetaddressfoo. We considerascenariowherethenetworklayerpro tocolsareIP, ARP, andReverseARP, , ,theIPhostaddressfieldsarequeried,whilei nthecaseofARPpackets, IP, wedonotneed6 BPF :TreeFilterFunctionfor hostfoo .tocheckthatit mightbeARPorRARP. Intheexpressiontreemodel,showninfigure6, ,andtheaveragenumberofcomparisonsis controlflowgraphratherthananexpressiontr eeasthetheoreticalunderpinningsofthefilt erpseudo-machineis a necessarysteptowardsanefficientimplement ationbutitis theexperienceandpseudo-machinemodelsofCS PFandNNStat[1], theBPFmodelunderwentseveralgenerations(a ndseveralyears) believethecurrentmodelofferssufficientge neralitywithnosacrificein , constraint1 is meansthatwemustprovidea fairlygeneralcomputationalmodel,withcont rolflow, sufficientALUop-erations, requiresthatweonlyevertoucha is commonfora filterto comparea givenpacketfieldagainsta setofvalues,thencompareanotherfieldagain stanothersetofvalues, ,a filtermightmatchpacketsaddressedto a setofmachines,ora , wewouldliketocachethepacketfieldinaregis terandcompareit thefieldisencapsulatedina variablelengthheader, ,onalignmentrestrictedmachines, ,forpacketsinmbufs, ,weshouldnotdoit meansthatwewillhaveanefficientinstruc-ti ondecodingstepbutit precludesanorthogonaladdressingmodedesig nunlesswearewillingto accommodatea ,whilethreeaddressinstructionsmakesensef ora realprocessor(wheremuchworkis donein parallel) , , Constraint5 is a , it ,eachnodeintheflowgraphcomputesitscorres pondingpredicatebycomput-inga showsthefilterfunctionofFigure5 , anindexregister(x)

10 , a scratchmemorystore,andanimplicitprogramc ounter. STRU CTION Scopya valueintotheaccumulatororindexregister. Thesourcecanbeanimmediatevalue,packetdat aata fixedoffset,packetdataata variableoffset,thepacketlength, Jan.,1993 SanDiego,CA7 TRUEFALSEldh [12]jeq #0x800ld [38]jeq #foold [28]jeq #foold [26]jeq #foold [30]jeq #foojeq #0x805jeq #0x8035 Figure7:BPFP rogramfor hostfoo . TOREIN STRU CTION IN STRU CTION Sperformarithmeticorlogicontheaccumulato rusingtheindexregisterora CHIN STRU CTION Saltertheflowofcontrol,basedoncomparison testbetweena RN IN STRU CTION EOU SIN STRU CTION Scompriseeverythingelse currently, :opcode:16jt:8jf:8 a haveadoptedthis assemblersyntax asa macros,thedetailsofwhichweomithere(see[6 ] forfulldetails). [k][x+k]ldh[k][x+k]ld#k#lenM[k][k][x+k]l dx#k#lenM[k]4*([k]&0xf)stM[k]stxM[k]jmpL jeq#k,Lt, Lfjgt#k,Lt, Lfjge#k,Lt, Lfjset#k,Lt, Lfadd#kxsub#kxmul#kxdiv#kxand#kxor#kxlsh #kxrsh#kxret#kataxtxaTable1:BPFI nstructionSetTheloadinstructionssimplyco pytheindicatedvalueintotheaccumulator(ld ,ldh,ldb) orindexregister(ldx).