SMP-friendly PF worked on



  • Apparently, FreeBSD developer Gleb Smirnoff has started working on a SMP-friendly version of PF for FreeBSD:

    http://lists.freebsd.org/pipermail/freebsd-pf/2012-June/006643.html

    CFT SMP-friendly pf
    Gleb Smirnoff glebius at FreeBSD.org
    Fri Jun 8 06:17:43 UTC 2012

    […]

    As you already probably know, or some may be don't yet know, the pf(4)
    subsystem in FreeBSD is currently working under a single mutex. This mutex
    is acquired right at the beginning of any packet processing, and is dropped
    at the end. While one thread is in pf(4) all other threads are blocked on
    that mutex.

    Meanwhile modern computers are getting more and more cores, and modern
    network cards getting more MSI interrupts, each serviced by a separate kernel
    thread in FreeBSD. So the single pf lock, which I call "the pf Giant" :), is
    getting a point of hard contention.

    Three and a half months ago I've started on a project "SMP-friendly pf",
    which recently have entered alpha stage. As you see from the subject of this
    mail, this is call for testing.

    Willing to test?

    The code lives in projects/pf/head branch in the SVN, and can be checked
    out with:

    svn checkout http://svn.freebsd.org/base/projects/pf/head pflock

    , where argument "pflock" is just directory name for checked out sources.
      Then you need to build world and kernel from that branch and install them.
    The branch projects/pf/head gets head merged to it quite often, so if you
    run head world with a revision equal (or at least close) to last merge, then
    you don't need to install world, however rebuilding pfctl and snmp_pf from
    that branch is necessary.
      If you are about to run this alpha pf on any important box, then you
    definitely need to establish safety measures: have a second box running
    stable/9 or head as carp(4) backup, ready to kick in, in case if new pf
    panics. pfsync(4) connection should also be established between new and
    backup boxes. pfsync(4) in the new code is wire compatible with stable/9
    or head.
      I'm already running it on routers with 100k - 200k state entries, and
    forwarding 20k - 40k pps. If you are brave, you should try, too :) Good
    luck and report any problems to me!

    Interested in details?

    From the very beginning of the project it was clear, that code is going
    to diverge significantly from original OpenBSD code. OpenBSD has always
    developed pf without taking into account that code can ever get
    multithreaded, thus quite a lot needed to be changed. Thus, I've started
    with removing the "#ifdef FreeBSD" from the code, and later I didn't
    hesitate even a fraction of second if I wanted to toss some code. The pros
    is that now code is much more readable and understandible then in head,
    the cons is that diff between us and OpenBSD is huge, although amount
    of shared code is huge, too. So, later on only manual merging of features
    from OpenBSD is possible and bulk imports of entire pf into FreeBSD are
    no longer possible.

    The locking scheme is the following:

    • There is an rwlock(9) that protects rules and all kind of data that isn't
        modified by forwarding threads. Forwarding threads reader lock it, ioctl()
        and other reconfiguring events write lock it.
    • The states and key states storage had moved from RB-trees to hashes, with
        separate mutexes per hash slot. This should give us decent parallelism
        when forwarding packets.
    • Source nodes storage moved to hash with per-slot locking.
    • pfsync(4) got separate mutex.
    • fragment reassembly got separate mutex.

    Apart from the above key changes, many other optimisations and fixes done.
    The entire diff is 22k lines large. You can view the projects history here:

    http://svnweb.freebsd.org/base/projects/pf/head/?view=log

    (the beginning is on page 2 now, at r232042) I had tried to make informative
    commit messages.

    and here are some comments, posted at openbsd-misc:

    http://www.mail-archive.com/misc@openbsd.org/msg113429.html

    Re: pf-smp alpha on freebsd
    Ryan McBride
    Mon, 18 Jun 2012 02:39:35 -0700

    No, there is no single mutex around PF specifically in OpenBSD, the
    whole kernel is wrapped in a biglock.

    I think if they work out all the nits and dead-ends we may have
    something to learn from this effort, but I don't see this code coming
    back to OpenBSD.

    It's not critical because they can change the state table implementation
    later - OpenBSD has reorganised this several times with more planned -
    but we've put quite a bit of effort into removing hash tables in our
    kernel wherever possible, partly due to their attackability.
    My
    personal preference would be to go with a lockless or lock-on-write RB
    tree for the state table, but without an SMP-safe network stack
    there's little motivation to work on such things (though it remains
    somewhere on my todo list).

    On Mon, Jun 18, 2012 at 10:06:01AM +0200, Franco Fichtner wrote:

    On Jun 17, 2012, at 7:53 PM, Ted Unangst wrote:

    On Sun, Jun 17, 2012 at 11:43, Holger Glaess wrote:

    i dident wont start about smp on openbsd but

    what about this porject ?

    Did you read the part below?  I think it's pretty clear this project
    isn't going to have much relevance for OpenBSD.

    From the very beginning of the project it was clear, that code is going
    to diverge significantly from original OpenBSD code. OpenBSD has always
    developed pf without taking into account that code can ever get
    multithreaded, thus quite a lot needed to be changed. Thus, I've started
    with removing the "#ifdef FreeBSD" from the code, and later I didn't
    hesitate even a fraction of second if I wanted to toss some code. The pros
    is that now code is much more readable and understandible then in head,
    the cons is that diff between us and OpenBSD is huge, although amount
    of shared code is huge, too. So, later on only manual merging of features
    from OpenBSD is possible and bulk imports of entire pf into FreeBSD are
    no longer possible.

    This sounds like a messy decision. Is this single-mutex stuff in pf true
    for OpenBSD as of now or a port quirk of FreeBSD's version? I worked on a
    heavily multi-threaded firewall core for a few years and I would be glad
    to help pf itself instead of a 4.5-based pf port going SMP, chasing
    rainbows and unicorns.

    Btw any ideas what OpenBSD's Ryan McBride means when he writes about "attackability" of hashes (vs RB-trees)? Does he mean that if someone is targeting your firewall, knowing that it's using hashes to store its states and the hashing algo, the adversary could create traffic that would cause increased hash collisions and thus decreased performance?



  • Latest update by the developer of SMP-friendly pf for FreeBSD:

    Gleb Smirnoff glebius at FreeBSD.org
    Thu Jun 28 12:35:52 UTC 2012
    Previous message: [CFT] SMP-friendly pf

    Hello, again.

    On Fri, Jun 08, 2012 at 10:17:37AM +0400, Gleb Smirnoff wrote:
    T>   Three and a half months ago I've started on a project "SMP-friendly pf",
    T> which recently have entered alpha stage. As you see from the subject of this
    T> mail, this is call for testing.

    I'm bit disappointed that my announce get so little response.

    Anyway, here are some results from running in production. This
    time on a busy router, that got a noticable load during busiest
    hours. It has complex ruleset with almost 400 rules, 21 vlan(4)
    interfaces running on top of lagg(4) and serves about 30 subnets
    of different size. Some subnets are behind NAT, and some or
    simple routed. The router usually got somewhere between 20k to
    60k states and 120k pf searches per second, with peaks up to
    140k searches.

    It has 4 cores and runs igb(4) NICs.

    After migrating to experimental pf branch on, the CPU load
    during busiest hours has dropped significantly:

    http://people.freebsd.org/~glebius/pflock/pflock-migration.png

    A more recent pic (taken right now):

    http://people.freebsd.org/~glebius/pflock/pflock-migration2.png

    Each high peak is a working day (in Russia in June we have had a
    6 day week followed by 3 day week). The thin red peak is buildworld+buildkernel,
    and after it the box was rebooted and since runs with SMP-friendly pf.
    As you may notice, after migration the working day peaks are much lower
    than before. Traffic volume is the same, I've checked this :)

    I hope these results would encourage someone to participate in
    early testing. :)

    By the way, I guess that the greatly reduced CPU load evident in GS' graphs might be more due to his use of hash-tables (instead of RB-trees used by stock pf) and less due to SMP, since hashes are O(1) whereas RB-trees O(logN) and his router does 120k lookups per second.

    I'd like to once again raise the question about the pro/cons of using RB-trees vs hashes for pf's state table,  and what OpenBSD's Ryan McBride meant when he wrote about "attackability" of hashes … (see previous post)



  • Related followups

    http://www.mail-archive.com/misc@openbsd.org/msg114033.html

    On Mon, Jun 18, 2012 at 2:31 AM, Ryan McBride <mcbr…@openbsd.org>wrote:

    It's not critical because they can change the state table implementation
    later - OpenBSD has reorganised this several times with more planned -
    but we've put quite a bit of effort into removing hash tables in our
    kernel wherever possible, partly due to their attackability.

    For what it's worth, DJB just published a paper introducing a new
    cryptographic PRF "SipHash" that's competitive in performance with
    other non-cryptographic hashing functions:
    http://cr.yp.to/siphash/siphash-20120620.pdf

    In the paper he proposes that using SipHash along with a random
    per-hash-table key should allow for hash tables that are resistant to
    hash flooding attacks.  I think it would be interesting to see as an
    experiment how pf performance compares with its current red-black
    trees vs SipHash-based hash tables.</mcbr…@openbsd.org>

    http://www.mail-archive.com/misc@openbsd.org/msg113974.html
    Henning Brauer
    Sat, 30 Jun 2012 03:36:37 -0700

    • Holger Glaess <gla…@glaessixs.de>[2012-06-17 11:41]:

    From the very beginning of the project it was clear, that code is going
    to diverge significantly from original OpenBSD code. OpenBSD has always
    developed pf without taking into account that code can ever get
    multithreaded, thus quite a lot needed to be changed. Thus, I've started
    with removing the "#ifdef FreeBSD" from the code, and later I didn't
    hesitate even a fraction of second if I wanted to toss some code. The pros
    is that now code is much more readable and understandible then in head,
    the cons is that diff between us and OpenBSD is huge, although amount
    of shared code is huge, too. So, later on only manual merging of features
    from OpenBSD is possible and bulk imports of entire pf into FreeBSD are
    no longer possible.

    now if they had updated their pf to a current one first we had
    certainly be willing to look at their locking changes with the goal to
    get them over. but this way? pointless. sad.


    Henning Brauer, h...@bsws.de, henn...@openbsd.org</gla…@glaessixs.de>



  • Apparently the SMP-pf has now been merged into FreeBSD-HEAD:

    http://lists.freebsd.org/pipermail/svn-src-all/2012-September/058316.html

    Log:
     Merge the projects/pf/head branch, that was worked on for last six months,
     into head. The most significant achievements in the new code:
     
      o Fine grained locking, thus much better performance.
      o Fixes to many problems in pf, that were specific to FreeBSD port.
     
     New code doesn't have that many ifdefs and much less OpenBSDisms, thus
     is more attractive to our developers.

    I'm not sure how this new development might affect pfSense, and I noticed that Ermal wasn't too happy about some aspects of this change…


  • Netgate Administrator

    Pretty interesting news. Is there a discussion thread I can read anywhere?

    Edit: It's here: http://lists.freebsd.org/pipermail/freebsd-pf/2012-September/thread.html#6740

    Steve


  • Netgate Administrator

    Quite a heated debate in that list.
    The performance figures for smp-pf look pretty promising though.

    Steve



  • I had an email exchange with the developer and I pointed out that while the raw SMP-pf performance stats are indeed very impressive, unless FreeBSD-pf will be aimed at big ISPs seeking to maximize performance, other users of pf could also benefit from features in post-OpenBSD4.7 pf like flexible nat, divert sockets, prio (or dummynet) integration, pflow.

    One area where pf lags behind Linux's netfilter/iptables (http://www.netfilter.org/), is the multitude of modules that significantly enrich the latter's functionality, and perhaps divert sockets can help close that gap.


Locked