wingolog

Pfmatch, a packet filtering language embedded in Lua

3 July 2015 11:05 AM (lua | pflua | bpf | pflang | igalia | snabb | compilers | dsl | edsl)

Greets, hackers! I just finished implementing a little embedded language in Lua and wanted to share it with you. First, a bit about the language, then some notes on how it works with Lua to reach the high performance targets of Snabb Switch.

the pfmatch language

Pfmatch is a language designed for filtering, classifying, and dispatching network packets in Lua. Pfmatch is built on the well-known pflang packet filtering language, using the fast pflua compiler for LuaJIT.

Here's an example of a simple pfmatch program that just divides up packets depending on whether they are TCP, UDP, or something else:

match {
   tcp => handle_tcp
   udp => handle_udp
   otherwise => handle_other
}

Unlike pflang filters written for such tools as tcpdump, a pfmatch program can dispatch packets to multiple handlers, potentially destructuring them along the way. In contrast, a pflang filter can only say "yes" or "no" on a packet.

Here's a more complicated example that passes all non-IP traffic, drops all IP traffic that is not going to or coming from certain IP addresses, and calls a handler on the rest of the traffic.

match {
   not ip => forward
   ip src 1.2.3.4 => incoming_ip
   ip dst 5.6.7.8 => outgoing_ip
   otherwise => drop
}

In the example above, the handlers after the arrows (forward, incoming_ip, outgoing_ip, and drop) are Lua functions. The part before the arrow (not ip and so on) is a pflang expression. If the pflang expression matches, its handler will be called with two arguments: the packet data and the length. For example, if the not ip pflang expression is true on the packet, the forward handler will be called.

It's also possible for the handler of an expression to be a sub-match:

match {
   not ip => forward
   ip src 1.2.3.4 => {
      tcp => incoming_tcp(&ip[0], &tcp[0])
      udp => incoming_udp(&ip[0], &ucp[0])
      otherwise => incoming_ip(&ip[0])
   }
   ip dst 5.6.7.8 => {
      tcp => outgoing_tcp(&ip[0], &tcp[0])
      udp => outgoing_udp(&ip[0], &ucp[0])
      otherwise => outgoing_ip(&ip[0])
   }
   otherwise => drop
}

As you can see, the handlers can also have additional arguments, beyond the implicit packet data and length. In the above example, if not ip doesn't match, then ip src 1.2.3.4 matches, then tcp matches, then the incoming_tcp function will be called with four arguments: the packet data as a uint8_t* pointer, its length in bytes, the offset of byte 0 of the IP header, and the offset of byte 0 of the TCP header. An argument to a handler can be any arithmetic expression of pflang; in this case &ip[0] is actually an extension. More on that later. For language lawyers, check the syntax and semantics over in our source repo.

Thanks especially to my colleague Katerina Barone-Adesi for long backs and forths about the language design; they really made it better. Fistbump!

pfmatch and lua

The challenge of designing pfmatch is to gain expressiveness, compared to writing filters by hand, while not endangering the performance targets of Pflua and Snabb Switch. These days Snabb is on target to give ASIC-driven network appliances a run for their money, so anything we come up with cannot sacrifice speed.

In practice what this means is compile, don't interpret. Using the pflua compiler allows us to generalize the good performance that we have gotten on pflang expressions to a multiple-dispatch scenario. It's a pretty straightword strategy. Naturally though, the interface with Lua is more complex now, so to understand the performance we should understand the interaction with Lua.

How does one make two languages interoperate, anyway? With pflang it's pretty clear: you compile pflang to a Lua function, and call the Lua function to match on packets. It returns true or false. It's a thin interface. Indeed with pflang and pflua you could just match the clauses in order:

not_ip = pf.compile('not ip')
incoming = pf.compile('ip src 1.2.3.4')
outgoing = pf.compile('ip dst 5.6.7.8')

function handle(packet, len)
   if not_ip(packet, len) then return forward(packet, len)
   elseif incoming(packet, len) then return incoming_ip(packet, len)
   elseif outgoing(packet, len) then return outgoing_ip(packet, len)
   else return drop(packet, len) end
end

But not only is this tedious, you don't get easy access to the packet itself, and you're missing out on opportunities for optimization. For example, if the packet fails the not_ip check, we don't need to check if it's an IP packet in the incoming check. Compiling a pfmatch program takes advantage of pflua's optimizer to produce good code for the match expression as a whole.

If this were Scheme I would make the right-hand side of an arrow be an expression and implement pfmatch as a macro; see Racket's match documentation for an example. In Lua or other languages that's harder to do; you would have to parse Lua, and it's not clear which parts of the production as a whole are the host language (Lua) and which are the embedded language (pfmatch).

Instead, I think embedding host language snippets by function name is a fine solution. It seems fairly clear that incoming_ip, for example, is some kind of function. It's easy to parse identifiers in an embedded language, both for humans and for programs, so that takes away a lot of implementation headache and cognitive overhead.

We are left with a few problems: how to map names to functions, what to do about the return value of match expressions, and how to tie it all together in the host language. Again, if this were Scheme then I'd use macros to embed expressions into the pfmatch term, and their names would be scoped into whatever environment the match term was defined. In Lua, the best way to implement a name/value mapping is with a table. So we have:

local handlers = {
   forward = function(data, len)
      ...
   end,
   drop = function(data, len)
      ...
   end,
   incoming_ip = function(data, len)
      ...
   end,
   outgoing_ip = function(data, len)
      ...
   end
}

Then we will pass the handlers table to the matcher function, and the matcher function will call the handlers by name. LuaJIT will mostly take care of the overhead of the table dispatch. We compile the filter like this:

local match = require('pf.match')

local dispatcher = match.compile([[match {
   not ip => forward
   ip src 1.2.3.4 => incoming_ip
   ip dst 5.6.7.8 => outgoing_ip
   otherwise => drop
}]])

To use it, you just invoke the dispatcher with the handlers, data, and length, and the return value is whatever the handler returns. Here let's assume it's a boolean.

function loop(self)
   local i, o = self.input.input, self.output.output
   while not link.empty() do
      local pkt = link.receive(i)
      if dispatcher(handlers, pkt.data, pkt.length) then
         link.transmit(o, pkt)
      end
   end
end

Finally, we're ready for an example of a compiled matcher function. Here's what pflua does with the match expression above:

local cast = require("ffi").cast
return function(self,P,length)
   if length < 14 then return self.forward(P, len) end
   if cast("uint16_t*", P+12)[0] ~= 8 then return self.forward(P, len) end
   if length < 34 then return self.drop(P, len) end
   if P[23] ~= 6 then return self.drop(P, len) end
   if cast("uint32_t*", P+26)[0] == 67305985 then return self.incoming_ip(P, len) end
   if cast("uint32_t*", P+30)[0] == 134678021 then return self.outgoing_ip(P, len) end
   return self.drop(P, len)
end

The result is a pretty good dispatcher. There are always things to improve, but it's likely that the function above is better than what you would write by hand, and it will continue to get better as pflua improves.

Getting back to what I mentioned earlier, when we write filtering code by hand, we inevitably end up writing interpreters for some kind of filtering language. Network functions are essentially linguistic in nature: static appliances are no good because network topologies change, and people want solutions that reflect their problems. Usually this means embedding an interpreter for some embedded language, for example BPF bytecode or iptables rules. Using pflua and pfmatch expressions, we can instead compile a filter suited directly for the problem at hand -- and while we're at it, we can forget about worrying about pesky offsets, constants, and bit-shifts.

challenges

I'm optimistic about pfmatch or something like it being a success, but there are some challenges too.

One challenge is that pflang is pretty weird. For example, attempting to access ip[100] will abort a filter immediately on a packet that is less than 100 bytes long, not including L2 encapsulation. It's wonky semantics, and in the context of pfmatch, aborting the entire pfmatch program would obviously be the wrong thing. That would abort too much. Instead it should probably just fail the pflang test in which that packet access appears. To this end, in pfmatch we turn those aborts into local expression match failures. However, this leads to an inconsistency with pflang. For example in (ip[100000] == 0 or (1==1)), instead of ip[100000] causing the whole pflang match to fail, it just causes the local test to fail. This leaves us with 1==1, which passes. We abort too little.

This inconsistency is probably a bug. We want people to be able to test clauses with vanilla pflang expressions, and have the result match the pfmatch behavior. Due to limitations in some of pflua's intermediate languages, it's likely to persist for a while. It is the only inconsistency that I know of, though.

Pflang is also underpowered in many ways. It has terrible IPv6 support; for example, tcp[0] only matches IPv4 packets, and at least as implemented in libpcap, most payload access on IPv6 packets does the wrong thing regarding chained extension headers. There is no facility in the language for binding names to intermediate results, there is no linguistic facility for talking about fragmentation, no ability to address IP source and destination addresses in arithmetic expressions by name, and so on. We can solve these in pflua with extensions to the language, but that introduces incompatibilities with pflang.

You might wonder why to stick with pflang, after all of this. If this is you, Juho Snellman wrote a great article on this topic, just for you: What's wrong with pcap filters.

Pflua's optimizer has mostly helped us, but there have been places where it could be more helpful. When compiling just one expression, you can often end up figuring out which branches are dead-ends, which helps the rest of the optimization to proceed. With more than one successful branch, we had to make a few improvements to the optimizer to actually get decent results. We also had to relax one restriction on the optimizer: usually we only permit transformations that make the code smaller. This way we know we're going in the right direction and will eventually terminate. However because of reasons™ we did decide to allow tail calls to be duplicated, so instead of having just one place in the match function that tail-calls a handler, you can end up with multiple calls. I suspect using a tracing compiler will largely make this moot, as control-flow splits effectively lead to trace duplication anyway, and making sure control-flow joins later doesn't effectively counter that. Still, I suspect that the resulting trace shape will rejoin only at the loop head, instead of in some intermediate point, which is probably OK.

future

With all of these concerns, is pfmatch still a win? Yes, probably! We're going to start using it when building Snabb apps, and will see how it goes. We'll probably end up adding a few more pflang extensions before we're done. If it's something you're in to, snabb-devel is the place to try it out, and see you on the bug tracker. Happy packet hacking!

11 responses

  1. Stanley says:

    Answering the question "how to write my personal statement" I can say that this is a very individual thing. Sure there exists some formal rules that you can easily find in google but the most important factor is making it very individual and creative.

  2. happy new year whatsapp status says:

    New Year's eve is celebrated every year throughout the globe with great passion and zeal and with new resolutions and commitments.

  3. oneplus 5 review says:

    OnePlus series Smartphone has become very popular and the series of OnePlus is competing with other big Smartphone oneplus 5.

  4. dhruva collections says:
  5. YO YO says:
  6. dipika mishra says:

    The middle of winter has long been a time of celebration around the world. Centuries before the arrival of the man called Jesus, early Europeans celebrated light and birth in the darkest days of winter. Many peoples rejoiced during the winter solstice, when the worst of the winter was behind them and they could look forward to longer days and extended hours of sunlight.

    In Scandinavia, the Norse celebrated Yule from December 21, the winter solstice, through January. In recognition of the return of the sun, fathers and sons would bring home large logs, which they would set on fire. The people would feast until the log burned out, which could take as many as 12 days. The Norse believed that each spark from the fire represented a new pig or calf that would be born during the coming year.

    The end of December was a perfect time for celebrationFeliz Navidad 2016 Navidad 2016Feliz año nuevo 2017

    Frohe weihnachten 2016Frohe weihnachten Status für FacebookCanciones de Navidad 2016 Villancicos de Feliz Navidad 2016 en inglesCanciones de Feliz Navidad 2016
      Frohes Neues Jahr2017 Frohe weihnachten 2016 weihnachtsgrüße 2016 Frohe weihnachten
      Frohe Weihnachten und Neues Jahr 2017 Neues Jahr 2017frohe Weihnachten 2016
     
     
     Frohe Weihnachtsgrüße 2016 Weihnachtsgrüße 2016Frohe Weihnachtsgrüße
     
     Sprüche zu Weihnachten 2016Frohe Weihnachten Sprüche, Wünsche, GedichteGedichte zu weihnachten 2016Weihnachten 2016 Wünsche

    analyze big data big data search data mining with big databig data database architecturehadoop big data database sql books hadoop big data analyticsdefine big databig data computing concept of big dataanalytics data database sql technology it big data big data examples big data miningsources of big datadata analytics companybig data volumemassive data big data storeopen source big data analytics analytics tools of big databig data structurebusiness data analytics applications for big databest big data databasemanaging big databig data analysis methods what's big data big data 3vexplain big data big data intelligence big data overviewanalytics on big datamassive data analysis big data featuresdatabase of big datause of big data big data productsbig data application developmentbig data and data mininghadoop analytics toolslarge data analytics big data data sourcesbig data researchbig data analytics startupadvanced data analyticsdata management big dataanalytics for big data features of big datadatabase sql books big data analytics methodology
     database sql books database sql pdfdatabase sqldatabase sql and nosqlwhat is data analyticsbig data in securitybig data articleshadoop articleshadoop software downloadhadoop trainingsdatabase sql tutorialsdata analytics booksbig data training in gaziabadbig data training in usbig data courses in goahadoop and big dataapplications of rhow to download big data pdfhow to learn big data and get jobbig data jobs and salary packagessalary packages of big data professionalbig data professionalsbig data professionals jobs
     spanish happinesshow to become spanish translatorspanish newbiespanish loveI love you more in spanish
     love and care in spanisbheat in spanishspanish loversspanish worldhow to speak and write spanishspanish language learn spanish very easily
     download the R tutorials for beginnersdownload SAS tutorials freelearn R and sasBig data engineer salary all over india
     I love you more than anyone in spanishhow to say bad in spanishhow to say you are good in spanishwhat are benfits of spanishspanish songs download sadlearn spanish from the websitespanish learning offline
     
     
    In Rome, where winters were not as harsh as those in the far north, Saturnalia—a holiday in honor of Saturn, the god of agriculture—was celebrated. Beginning in the week leading up to the winter solstice and continuing for a full month, Saturnalia was a hedonistic time, when food and drink were plentiful and the normal Roman social order was turned upside down. For a month, slaves would become masters. Peasants were in command of the city. Business and schools were closed so that everyone could join in the fun.

  7. Norman says:

    Can I merely say just what an alleviation to find someone that truly has learned what they are speaking about online?
    generic viagra

  8. ADIL says:

    best printable 2017 Calendarbest printable 2017 Calendarbest printable 2017 Calendarbest printable 2017 Calendarbest printable Calendar 2017best printable Calendar 2007best printable Calendar 2017best printable Calendar 2017best printable Calendar 2007best printable Calendar 2017best printable Calendar 2017best printable Calendar 2017Us River map 2017Us River map 2017Us River map 2017Us River map 2017Us River map 2017Us River map 2017Us River map 2017Us River map 2007USA River map 2007USA River map 2007USA River map 2007USA River map 2007USA River map 2007USA River map 2007Map of united statesMap of united statesMap of united states

    In Rome, where winters were not as harsh as those in the far north, Saturnalia—a holiday in honor of Saturn, the god of agriculture—was celebrated.
    Beginning in the week leading up to the winter solstice and continuing for a full month, Saturnalia was a hedonistic time,
    when food and drink were plentiful and the normal Roman social order was turned upside down. For a month, slaves would become masters.
    Peasants were in command of the city. Business and schools were closed so that everyone could join in the fun.

  9. Affiliatedd says:

    ADSFGHJKironsteelcenter.com ironsteelcenter.comHarga besi beton Sni Ulir Polos Harga besi beton Sni Ulir PolosHarga besi hollow Harga besi hollowHarga besi cnp Harga besi cnpHarga besi unp Harga besi unpHarga wiremesh Harga wiremeshHarga besi wf Harga besi wfHarga besi h beam Harga besi h beamHarga Plat besi Harga Plat besiHarga pipa besi baja sch 40 sch 80 Harga pipa besi baja sch 40 sch 80Harga besi siku Harga besi sikuHarga Plat kapal besi baja bki krakatau steel Harga Plat kapal besi baja bki krakatau steelHarga bondek Harga bondekHarga baja ringan Harga baja ringanHarga Atap spandek Harga atap spandekHarga stainless steel Harga stainless steeljasa konstruksi jasa konstruksi besi baja jasa konstruksi gudang jasa konstruksi gedung jasa konstruksi undangan pernikahan undangan pernikahan simpleundangan pernikahan online udangan pernikahan pinkundangan pernikahan unik undangan pernikahan onlineundangan pernikahan murah undangan pernikahan islamiundangan pernikahan islami undangan pernikahan murahundangan pernikahan elegan undangan pernikahan artisundangan pernikahan unik dan murah contoh undangan pernikahan
    www.gudangbesibaja.com www.gudangbesibaja.comHarga besi cnp Harga besi cnpHarga besi h beam baja Harga besi h beam bajaHarga Plat besi plat kapal Harga Plat besi plat kapalHarga besi siku Harga besi sikuHarga besi unp Harga besi unpHarga besi wf baja Harga besi wf bajaHarga besi beton Sni Ulir Polos Harga besi beton Sni Ulir PolosHarga besi hollow Harga besi hollowHarga pipa besi baja sch 40 sch 80 Harga pipa besi baja sch 40 sch 80Harga wiremesh Harga wiremeshHarga bondek Harga bondekHarga besi Wf Baja Harga besi Wf Bajajasa konstruksi baja wf jasa konstruksi jembatan jasa konstruksi bangunan jasa konstruksi undangan pernikahan elegan dan murah undangan pernikahan eleganundangan pernikahan simple undangan pernikahan elegan dan murahundangan pernikahan artis undangan pernikahan putihudangan pernikahan pink undangan pernikahan unik dan murahundangan pernikahan putih undangan pernikahan unikContoh undangan pernikahan undangan pernikahan

    harga besi beton sni toko besi baja harga besi bahan bangunanharga pipa stainless steel pipa galvanis medium a besi bjkujual baja wf tabel baja krakatau steel harga besi ulir 16 mmharga stainless steel harga baja profil per kg harga besi 12 sniharga besi ulir harga besi wire mesh harga besi 8 mmdaftar harga pipa galvanis harga besi hollow stainless harga besi beton 10harga besi wf 200 harga baja hollow harga besi 13 ulirbesi kanal c galvanis steel rangka besi betondaftar harga besi beton harga pipa hollow harga besi kgjual wiremesh besi beam sni besi betonsupplier besi profil baja iwf harga besi behel 8mmbesi baja pipa galvanized harga besi beton 10mm snikonstruksi baja wf jual expanded metal harga besi ulir 10daftar harga besi hollow besi wire mesh harga sikuharga wiremesh profil baja h beam harga besi siku 4x4Supplier besi harga beam 200 besi siku hargaharga besi baja harga besi cnp 100 harga pipa besi hitamharga pipa baja jual besi cnp pipa seamlessbesi beton murah harga besi unp 100 daftar harga pipa stainless steelharga kanal c besi kanal c harga harga pipaharga besi stainless harga besi cnp 125 pipa stainlessharga besi per kg besi u galvanisharga plat stainless steel besi c pipa besi galvanisbesi unp harga besi cnp 150 harga besi hollow untuk pagarjual besi wf kanal c pipa besi hitamharga baja h beam daftar harga besi kanal c harga besi hollow 40x40

  10. dsadas says:
  11. james clark says:

    Valentine's Day, also called Saint Valentine's Day or the Feast of Saint Valentine, valentines day is an annual holiday celebrated on February 14. valentines day messages It originated as a Western Christian liturgical feast day honoring one or more early saints named Valentinus, and is recognized as a significant cultural and commercial celebration in many regions around the world, happy valentines day quotes although it is not a public holiday in any country. Valentine's Day is celebrated on February 14 Valentine's Day is also a very popular date for weddings..It is a festival of romantic love and many people give cards, letters, flowers or presents to their spouse or partner. They may also arrange a romantic meal in a restaurant or night in a hotel. Common symbols of Valentine's Day are hearts, red roses and Cupid.The most common happy valentines day images Valentine's Day symbols are the heart, particularly in reds and pinks, and pictures or models of Cupid. Cupid is usually portrayed as a small winged figure with a bow and arrow.Many people celebrate their love for their partner by sending cards or letters, giving gifts or flowers and arranging meals in restaurants or romantic nights in hotels. People who would like to have a romantic relationship with somebody may use the occasion to make this known, often anonymously. Valentine's cards are often decorated with images of hearts, red roses or Cupid. Common Valentine's Day gifts are flowers chocolates, candy, lingerie and champagne or sparkling wine

Leave a Reply