Thursday, October 1, 2015

As requested: progress of AR9170


The progress of the AR9170 FreeBSD-ification can be found here:

Yes, I did actually keep the history of the driver bring-up here.

Wednesday, September 30, 2015

Porting a wifi driver from openbsd - AR9170

I told myself a long, long time ago that I really don't want to be working on USB wireless. It's not that I dislike USB or wireless; it's just that the hoops required to get it all working in a stable way is quite a bit to keep in your mind. But, I decided recently that it's about time I learnt how it worked and I was very sad that we still didn't have any working USB wifi devices that also operated with 802.11n.

So, I picked a NIC and dove in.

I picked if_rsu(4) - it's the RTL8188SU / RTL8192SU series hardware from Realtek. It turned out I chose reasonably well.

First off - it's a "fullmac" device - meaning that outside of a handful of things, the device firmware offloads a lot of the 802.11 complications. The driver does hardware initialisation and the wireless stack speaks WPA/WPA2/etc for negotiating encryption, but the hardware handles scanning, authentication, 802.11n aggregation negotiation and most management frame work.

Secondly - it's ported from OpenBSD. The OpenBSD folk do a good job of getting drivers up and running, but there tend to be some sharp edges and the 802.11n bits just don't work.

So, besides currently doing encryption in software, the rsu(4) driver behaves rather well. I'll write a separate article about that. This article is about the AR9170, or otus(4) driver in FreeBSD/OpenBSD parlance.

Now, the AR9170 is a ZyDAS device with an Atheros 802.11n PHY and radio. It's quite a hybrid beast. It's also buggy - there are issues with QoS frames and 802.11n aggregation that make it impossible to behave well. So, for now I'm treating it like a 11abg device and I'll worry about 802.11n when someone gives me patches to make it work.

The OpenBSD driver is based on the initial otus driver that Atheros provided to the Linux developers circa 2009. The firmware blob is closed and very old - the ar9170fw project is still out there on the internet (and I have a mirror at but I can't get it to build on a recent FreeBSD install so a firmware update will take time. But, it does seem to work.

There are a few pieces to think about when porting a USB driver. The biggest piece is that it's not memory mapped IO or IO port based - everything is a message. There are USB device control commands you can send which will sleep until they're done, but the majority of stuff is done using bulk transmit and receive endpoints and that's all conveniently asynchronous. But it complicates things in the driver world.

Memory mapped and IO port drivers treat device IO as this magical "I do it, then the next instruction executes when it's done" mostly serialised paradigm. It's a lie, of course - the intel x86 CPUs will pretend things are occuring in a specific order, but a lot of platforms require you to mark memory as uncached or use memory / cache flush operations to ensure things go out to the device in any particularly controlled manner. But USB doesn't - outside of USB control transfers, USB devices tend to look like remote network devices and this includes register accesses. Now, the RTL8188SU driver (rsu(4)) implements the firmware upload and register accesses using control transfers, so it's all pretty easy to get the driver initialisation and attaching working before you care about the asynchronous parts. But the AR9170 driver implements register accesses as firmware commands - and so I have to get a lot more of the stack up and working first.

So, here's what I did.

First up - I commented out almost all of the device driver, and focused on getting the probe, attach and detach methods working. That wasn't too hard. But yes, almost all the code was commented out.

Next up was firmware loading. This was done using control transfers, so I didn't have to worry about implementing the bulk transmit and receive endpoint handling. I had to convert the firmware load path to the FreeBSD firmware API rather than the OpenBSD API, but that was mostly trivial.

Then I realised I wasn't doing any driver locking - so yes, I ensured I did the bare minimum of driver locking required to stop the kernel panicing. OpenBSD doesn't use locks, they use old style BSD spl() levels.

Next up was command transmit and receive. Now, I needed to setup the USB endpoints - which FreeBSD makes really easy to do using a structure to define what endpoints are what. It was pretty clean. The complicated bit is the bulk callback - it handles transfer statuses and transfer initiation. This is the bit that took me a little time to wrap my head around.

The USB stuff handles things in-sequence. Everything going to an endpoint here gets handled in the sequence you queue it. It also will process the bulk callback in a single worker thread taskqueue, rather than the driver author having to worry about creating their own worker threads. So, this is what
you end up doing:

  • The bulk callback has three states: USB_ST_TRANSFERRED, USB_ST_SETUP, and everything else (error.)
  • USB_ST_TRANSFERRED says "I've finished a transfer".
  • USB_ST_SETUP says "I've been asked to initiate a transfer."
  • Any driver thread starts a transmit by calling usbd_transfer_start() on the usb_xfer struct, which will kick off a call into the bulk callback with USB_ST_SETUP.
  • So, the driver has to maintain its own queues of "pending", "active" and "waiting" transactions. "pending" is the queue to put outbound transmit messages on. "active" is the queue you put messages that you've submitted when USB_ST_SETUP is called. When USB_ST_TRANSFERRED or an error is called, you pop off the top entry from "active" and you finish with it, then you fall through to USB_ST_SETUP to start a new transfer.
It's a little complicated because you have to maintain your own submission queues in/out of the USB stack, but in practice it's just a linked list.

So, I stole the framework from rsu(4) for buffer management, transmit submission and completion. It submitted things fine. I also registered buffers for receive, and .. nothing happened. I would send a PING message to the firmware to see if it was awake, and I'd get nothing from the receive pipe.

Then I remembered an interesting bug from when I tried this in 2012 - the AR9170 firmware required the IRQ endpoint to be setup, even though no interrupt messages were ever posted. So, I set the endpoint up, started reception on it.. and now I started to see receive messages. My PING messages were being PONG'ed.

But here's the first complication - although everything is asynchronous here, a lot of places want to send a command and wait for a response. For the PING command it's waiting for a matching PONG response. For setting frequency, starting calibration, etc, you get back interesting status from the firmware. But for things like register read commands, you have to wait until you get the register value back before you can continue. We need to be able to put the caller to sleep until the response comes back, or some timeout occurs.

So, cmd_otus() submits a transfer buffer and then will msleep() on it for up to a second, waiting for a response. When a command is transmitted, a couple of things can occur:
  • Once the transfer succeeds, if the command needs no response then we just send a wakeup to notify the sender that we've sent it, and we free the buffer.
  • If the transfer succeeds but the command needs a response, then we put it on the "waiting" queue.
Then in the receive path we pull out firmware notifications and if they're responses we copy the response into the callers provided buffer, call wakeup() to wake up the caller, and free the buffer.

OpenBSD cheats - it only has one single outstanding command buffer for all threads to use.

The tricky, unimplemented bit here is error handling - if I yank out a NIC during active commands then the driver will sleep for a second, wakeup with an error and pass an error back. But, the rest of the driver doesn't know anything was sleeping, so state gets freed from underneath it. I need to go and add what OpenBSD does - refcount when the driver is entered from say, the transmit and ioctl paths, and then upon detach just wait for pending things to finish before freeing.

Ok, so that got command transmit/receive and sleep/wake notification working okay. Next up is packet reception and basic initialization. That was mostly the same - the same hardware bits are needed, the same 802.11 packet format is needed for the stack. The main differences here were in the OpenBSD versus FreeBSD net80211 interface layout - FreeBSD has vaps (virtual access points, etc) but OpenBSD does not. It's still pre-vap work, so there's only one interface. This required a little bit of splitting to put the vap bits in vap routines, and driver bits in the driver. The notable exceptions are vap_create, vap_destroy and newstate.

Next up was realising OpenBSD is also still driving 802.11 state from the driver, not from the net80211 stack. FreeBSD drives the state changes and tells the driver what to do. That required me undoing some manual state transitions (eg otus_init() setting the state to SCAN or RUN depending upon the interface mode) and just letting net80211 do it.

So, net80211 created a vap, called otus_init(), then brought up the interface, set the initial vap state to SCAN via a call to newstate and started changing channels. This worked fine. I had some locking concerns - check the driver to see what I did. It was pretty straightforward.

And then yes - because the receive path was pretty simple and I got straight 802.11 frames back, yes, I started seeing beacons in a tcpdump session. This was great.

Then I ripped up a bunch of callback code that isn't needed. A few years ago FreeBSD's USB drivers maintained their own taskqueue to defer things like crypto key setting, state changes and such. Now net80211 has a per-device taskqueue that it runs these things on, and a lot of the driver calls are done as deferred tasks. OpenBSD doesn't have this so the drivers create their own deferred task and async callback framework to schedule these. It's duplicated work and I removed all of that from the driver.

Next up is transmit. This is trickier for a few reasons.

First, FreeBSD doesn't use if_start() anymore, with network stack provided queues. I have to maintain my own queue and free net80211 node references as appropriate. It took a while to craft up a correctly behaving transmit side when I fixed rsu(4), so I just stole it for the AR9170. I'll describe that in a subsequent article about rsu.

FreeBSD's net80211 stack handles 802.11 encapsulation itself; we're not handed ethernet frames unless we ask for them. So, I don't call ieee80211_encap(). Yes, I do call for software encryption as required, and that was done.

The biggest sticking point is the rate control. FreeBSD's net80211 stack has a reasonable implementation of transmit rate control modules and it's per vap and per associated node. I don't have to do anything too manual for it. OpenBSD did a bunch of manual work to do the AMRR setup/teardown/updating, so I had to rip it out and call the ratectl init/destroy methods in the vap create/destroy methods.

Next up was what ni->ni_txrate represented. In OpenBSD it seems like an index into the rate control table. In FreeBSD it's the 802.11 rate to use! So, I ripped out a bunch of rate table stuff in the driver and replaced it with a couple of mapping functions to go 802.11 rate to AR9170 hardware rate. That worked like a charm, and transmit works fine.

The last annoying thing with transmit is how the firmware tells us about failed frames. We don't get a completion message upon each frame - the later firmware does this, but the original blob doesn't. We only get told upon retries and errors. So, I hacked up something where the transmit path counts outbound packets, the RX command path counts retries/errors, and each time I transmit a packet I update net80211 with the transmit/retry/error counts. This works pretty well.

Finally - teardown. The correct order for teardown is:
  • Shut down the MAC - eg, disable TX/RX DMA, etc
  • Disable the USB transfers, wait until they're done
  • Free the transmit/receive buffers and any net80211 node references they may have; and
  • then call ieee80211_ifdetach() to ensure vaps and the top level interface is destroyed.
The initial port called ieee80211_ifdetach() too early and the subsequent node references would refer to now-freed nodes and vaps, causing lots of hilarity.

And that's that. I haven't made 802.11n work; I haven't fixed up the radiotap support so received 802.11 packets in tcpdump actually provide the right rate/channel/etc. That's all details that I'll do when i feel like it. But, the driver is stable, there aren't any lock ordering issues that I've seen so far, and it actually behaves remarkably well.

Tuesday, July 14, 2015

FreeBSD now has NUMA? Why'd it take so long?

I just committed "NUMA" to FreeBSD. Well, no, I didn't. I did almost no actual NUMA-y work in FreeBSD. I just exposed the existing NUMA stuff in FreeBSD out and re-enabled it.

FreeBSD-9 introduced basic NUMA awareness in the physical allocator (sys/vm/vm_phys.c.) It implemented first-touch page allocation, and then fell back to searching through the domains, round-robin style. It wasn't perfect, for some workloads it was apparently okay. But it had some shortcomings - it wasn't configurable, UMA and other subsystems didn't know about NUMA domains, and the scheduler really didn't know about NUMA domains. So I'm sure there are plenty of workloads which it didn't work for.

That was all ripped out before FreeBSD-10. FreeBSD-10 NUMA just implements round-robin physical page allocation. It still tracks the per-domain physical memory regions, but it doesn't do any kind of NUMA aware allocation. From what I can gather, it was removed until something 'better' would land.

However, nothing (yet) has landed. So I decided I'd take a look into it. I found that for a lot of simple workloads (ie, where you're doing lots of anonymous memory allocation - eg, you're doing math crunching) the FreeBSD-9 model works fine. It's also a perfectly good starting point for experimenting.

So all my NUMA work in -HEAD does is provide an API to exactly the above. It doesn't teach the kernel APIs about domain aware allocations - there's currently no way to ask for memory from a specific domain when calling UMA, or contigmalloc, etc. The scheduler doesn't know about NUMA, so threads/processes will migrate off-socket very quickly unless you explicitly limit things. Devices don't yet do NUMA local work - the ACPI code is in there to enumerate which NUMA domain they're in, but it's not used anywhere just yet.

Then what is it good for?

If you're doing math workloads where you read in data into memory, do a bunch of work, and spit it out - it works fine. If you're running bhyve instances, you can run them using numactl and have them pinned to a local NUMA domain. Those coarse-grained things work fine. You can also change the system default back to round-robin and use first-touch or fixed-domain for specific processes. It's useful for exactly the same subset of tasks as it was in FreeBSD-9, but now it's at least configurable.

So what's next?

Well, my main aim is to get the minimum done so kernel side work is NUMA aware. This includes UMA, contigmalloc, malloc, mbuf allocation and such. It'd be nice to tag VM objects with a domain allocation policy, but that's currently out of scope. I'd also like to plumb in domain configuration into devices and allow devices to allocate memory for different driver threads with different policies.

But the first thing that showed up is that KVA allocation and superpages get in the way of malloc/contigmalloc working. Allocating memory in FreeBSD first allocates KVA space, then back-fills it with pages. As far as malloc/contigmalloc is concerned, KVA is KVA and it finds the first available space in a time-fast way. It then backfills it with physical pages. The superpage reservation bits (sys/vm/vm_reserv.[ch]) join together regions that are contiguous and in the same superpage and turn it into an allocation from the same superpage. These have no idea about NUMA domains. So, if you allocate a 4KiB page via malloc() from domain 0 and then try to allocate a 4KiB page from domain 1, it will likely mess it up:

  • First page gets allocated - first KVA, then the underlying 2mb superpage is allocated and a 4k page is returned - from physical memory domain 0;
  • Second page gets allocated - first KVA, and if it's adjacent or within the same 2mb superpage as the above allocation, it'll "fake" the page allocation via refcounting and it'll really be that same underlying superpage - but it's from physical memory domain 0.
I have to teach both vm_reserv and the KVA allocator about NUMA domains, enough so domain specific allocations don't use KVA that's adjacent. It was suggested that I create a second layer of KVA allocators that allocate KVA from the main resource allocator in superpage chunks (here it's 2mb) and then I do domain-specific allocations from them. It'll change how things get fragmented a bit, but it does mean that I won't fall afoul of things.

So, I'll do the above as an experiment and I'll push the VM policy evaluation up a little into malloc/contigmalloc. I'll see how that experiment goes and I'll post diffs for testing/evaluation.

Saturday, July 11, 2015

The importance of mentoring, or "how I got involved in FreeBSD"..

Here's how I was introduced into this UNIX world, or "wait, WHO was your WHAT?"

So, here's 11ish or so year old Adrian. It's the early 90s. I was hiding in my bedroom, trying to make another crystal set out of random parts and scraping away the paint at my windowsill. In walks my Aunty, who introduces her new boyfriend.

"Hi, I'm Julian." he said. That wasn't all that interesting.

"Oh, are you making a crystal set?" .. ok, so that was interesting.

And, that was that. Suddenly, someone role-model-y shows up in my life out of the blue. There I was, an 11 year old who felt very mostly alone most of the time, and someone shows up who I can look up to and think I can relate to. So, I'm a sponge for everything he shows me. Whenever he comes over, he has some new story to tell, some new thing to show me. He would show me better ways of building transistor switch circuits when I was in the "make large arcs with car alternator" phase of my early teens. And, when I saved up and bought a PC, he started to show me programming.

Now, I was already programming. My parents had saved up and bought me an Amstrad CPC464. We had a second-hand commodore 64 for a short while, but that eventually somehow stopped working and I didn't have the clue to fix it. But I was programming Locomotive BASIC and dabbling in Z80 assembly when I was 12, and had "upgraded" to Turbo Pascal 6 when I hit high school. (Yes, school taught Turbo Pascal at Grade 10 level, and I decided to learn it a bit earlier. That's .. wow, that dates me.) I hadn't yet really stumbled into C yet. I had heard about it, but I didn't have anything that could write it.

Julian explained task switching to me one day during a walk along the beach. He explained that computers can just appear to be doing multiple things at once - but the CPU only does one thing at a time, and you can just switch things really quickly to give the appearance that it's multitasking. With that bright spark planted in my head, I went home and started dreaming up ways to make my Z80 based CPC do something like this.

My mother dragged me to McDonalds to apply for a job the moment I was legally able to (14 years, 9 months) and I saw a computer at a second hand shop - it was a $500 IBM PC/AT, with EGA monitor, two floppy disks and a printer. We put down a down-payment and I paid it off myself with my minimum wage money. Once I had that home I quickly erm, "acquired" a copy of Turbo Pascal for home and was off drawing funny little fractals.

So yes - it's Julian's fault I discovered FreeBSD. Yes, this is Julian Elischer. One day he showed me his computer, running something called BSD. He was trying to explain bourne shell scripting and the installer. I nodded, very confused, and eventually went back to the VGA programming book he lent me. He also showed me fractint running in X on his monochome 486 DX2-50 laptop. I had no idea what was going on under the scenes, only that the fractals were much more interesting than the ones I was drawing. So I took the VGA book home and started learning how to use the higher resolutions available. One thing stuck in my mind: so much bit-plane work. Ugh. One other thing stuck in my mind - reading from VGA memory is one of the slowest things you can do. Don't do it. Ever. (Do you hear that console driver authors? Don't do it. It's bad.)

One day he explained pointers to me. I had erm, "acquired" a copy of Turbo C 2.0 from a friend after failing to make much traction with the less friendly versions (Tiny C, for example.) I had coded up a few things, but I didn't really "get" it. So he sat me down with a pen and paper, and drew diagrams to explain what was going on. I remember that lightbulb going off in the back of my mind, as I dimly connected the whole idea of types and sizes together - and that was it. I was off and doing bad things to C code.

I eventually saved up enough for an updated 286 motherboard, then an updated graphics card (full VGA!), then a sound blaster card, and finally a 486-DX33 motherboard. He introduced me to his friend Peter (who had, and I believe still has, a rather extensive electronics collection) and handed me a FreeBSD-1.1 CDROM. I took it home, put it in, and .. it didn't do anything. My 486 had a soundblaster pro + CD-ROM, and .. well, FreeBSD-1.1 didn't speak to that hardware. So, I eventually put Slackware Linux 3.0 on the thing, and became a Linux nerd for a bit.

I did eventually try FreeBSD-1.1 on it - after putting a lot of FreeBSD bits on a lot of floppies - but I couldn't figure out what to do when it booted. This is going to sound silly - but the lack of colorls turned me off. I know, it seems silly now, but that's honestly why I went back to Slackware.

I eventually went back to FreeBSD in the 2.x era once I had an IDE CDROM and I was working part time at an ISP after (high) school finished. Yes, I figured out how to get colorls to work, I got in trouble disagreeing with a Michael (O, not M) at iiNet about Squid on Linux versus FreeBSD, and well.. stuff. Here was this 17yo kid disagreeing with things and acting like he knew everything. I'm sure it was endearing.

Fast-forward a couple years, and I had been hacking on FreeBSD here and there. I got in a little erm, "trouble" before I finished high school, which phk reminded me of - when they granted me a commit bit. I forget when this was, but I wouldn't have been much older than 20.

So - this is why mentoring kids is important. It may seem like a waste of time; it may seem like they don't understand, but we were all there once. We wanted someone to relate to, someone to look up to, and something interesting to do. Julian was that person for me, and I owe both him and my mother (of course) pretty much everything about my existence in this silly little computer industry.

(This is also why you don't skimp on hardware support for popular, if cheaper platforms and "shiny" looking features if you want people to adopt your stuff -  but that's a different rant.)

Ok, that's done. I'm going back to hacking on VGA/VESA boot loader support for FreeBSD-HEAD. That's long overdue, and I want my pretty splash screen.

Sunday, June 28, 2015

RTL-SDR on FreeBSD, or "hey, cool, I live near an airport, I wonder if ADSB works.."

I bought one of those cheap RTL-SDR units a few months ago. There's no real kernel code required for it - all of the rtl-sdr code just uses the generic USB userland API which is shared between many operating systems.

So, getting it going was pretty easy:

# pkg install rtl-sdr

Then, using it to test ADSB is pretty easy:

# rtl_adsb -V -S 

.. this is verbose and listens to short packets.

Where I live (near San Jose Airport!) I receive a lot of ADSB transmissions. It's quite interesting.

Ok, so next - what about something more GUI like? Someone's already done it - . There's already a package for it:

# pkg install dump1090
# dump1090 --net --aggressive

Then, point a webserver at http://localhost:8080/ and watch!

Sunday, May 17, 2015

freebsd-wifi-build, or "wait, you can run freebsd on atheros MIPS access points? where do I get that?"

I've been running FreeBSD at home as my primary internet/wifi access for a few years now. It's cheap, it's easy to do, and I've tried very hard to wrap up the whole process into a mostly-simple build system that spits out a useful image to use.

It's pretty simple in concept - I take FreeBSD-HEAD, build it with some cut-down options, create a custom filesystem image with some custom boot scripts and a custom configuration file, and provide an image that you can TFTP (using a serial console and ethernet cable) or upload directly to the AP if it supports it.

The supported hardware list is here:

Now, it's not a huge list like OpenWRT, but that's mostly because I don't have an infinite supply of Atheros MIPS based routers. I think I'll get some of the TP-Link Archer series stuff next.

Building it is pretty simple:

You checkout the build repo, check out FreeBSD-HEAD, install a couple of packages, and run the build for your board. Once it's done, the images for your board appear in ../tftpboot/. There's a wiki page for each of the supported boards with a walkthrough with how to get FreeBSD going on it.

It comes up on with 'user' and 'root' users, with no password. So, the first thing you should do after installation is telnet in, configure /etc/cfg/rc.conf with your actual LAN IPs, set the user/root passwords, and then 'cfg_save' to save things. Then, reboot and voila!

The configuration file format looks like FreeBSD but it isn't. I'm keeping it somewhat hierarchical-looking in naming but flat in implementation so I can migrate it to something like a sqlite or luci backend in the future.

It's good enough for me to be able to set up an AP to be a bridge with a management IP address and configure the ethernet switch. Others have added ipfw support to do NAT and firewalling - I'm going to add configuration rules for NAT, IPFW and routing soon so it's all integrated.

It's FreeBSD, all the way through:

$ uname -a
FreeBSD tl-wdr3600 11.0-CURRENT FreeBSD 11.0-CURRENT #0 r282406M: Wed May  6 22:27:16 PDT 2015     adrian@lucy-11i386:/usr/home/adrian/work/freebsd/head-embedded/obj/mips/mips.mips/usr/home/adrian/work/freebsd/head-embedded/src/sys/TL-WDR4300  mips
$ ifconfig wlan0 list sta
18:ee:69:15:f4:12    2    1  26M 37.0   45   2703  51888 EPS  AQEHTRM RSN HTCAP WME
04:e5:36:0d:1b:0d    1    1  19M 23.0   15   1524  47072 EPS  AQEPHTR RSN HTCAP WME
cc:3a:61:0e:33:a0    3    1  19M 32.0   30   2585  43072 EPS  AQEPHTR RSN HTCAP WME
40:0e:85:1a:f1:69    4    1  19M 25.0   30   1138  54800 EPS  AQEPHTR RSN HTCAP WME
00:0f:13:97:14:54    5    1  54M 30.0   45   1808  57424 EPS  AE      RSN
00:22:fa:c2:d1:20    6    1  26M 24.5    0    574  57776 EPS  AQEHTRS RSN HTCAP WME

So if you'd like a FreeBSD based device to act as your home gateway, this is where you can start. It's not pfsense, but it's designed to run on things much smaller than pfsense supports and it's a good introduction into the world of FreeBSD embedded.

Friday, April 10, 2015

Intel DDIO, LLC cache, buffer alignment, prefetching, shared locks and packet rates.

I've been digging into the low level behaviour of high throughput packet classification and pushing for my job. The initial suggestions from everyone was "use netmap!" Which was cool, but it only seems to to fast packet work if you're only ever really flipping packets between receive and transmit rings. Once you start actually looking into the payload, you start having to take memory misses and things can slow down quite a bit. An L3 miss (ie, RAM access) on Sandybridge is ~50ns. (There's also costs involved in walking the TLB, but I won't cover that here.)

For background: .

But! Intel has this magical thing called DDIO. In theory (and there's a lot of theory here), DMA is done via a small (~10%) fraction of LLC (L3) cache, which is shared between all cores. If the data is already in cache when the CPU accesses it, it will be quick. Also, if you then wish to DMA out data from something in cache, it doesn't have to get flushed to memory first - it's just DMAed straight out of cache.

However! When I was doing packet bridge testing (using netmap + bridge, 64 byte payloads), I noticed that I was doing a significant amount of memory bandwidth. It wasn't quite at the rate of 10G worth of bridged data, but DDIO should be doing almost all of that work for me at 64 byte payloads.

So, to reproduce: run netmap bridge (eg 'bridge -i netmap:ix0 -i netmap:ix1') and run pkt-gen between two nodes.

This is the output of 'pcm-memory.x 1' from the intel-pcm toolkit (which is available as a binary package on FreeBSD.)

--                   System Read Throughput(MB/s):    300.68                  --
--                  System Write Throughput(MB/s):    970.81                  --
--                 System Memory Throughput(MB/s):   1271.48                  --

The first theory - the bridging isn't occuring fast enough to service what's in LLC before it gets flushed out by other packets. So, assume:

  1. It's 1/10th of the LLC - which is 1/10th of an 8 core * 2.5MB per core setup, is ~ 2MB.
  2. 64 byte payloads are being cached.
  3. Perfect (!) LLC use.
That's 32,768 packets at a time. Now, netmap is doing ~ 1000 packets a batch and it's keeping up line rate bridging on one core (~14 million packets per second), so it's not likely that.

Ok, so what if it's not perfect LLC usage?

Then I thought back to cache line aliasing and other issues that I've previously written about. What if the buffers are perfectly aligned (say, 2048 byte aligned) - the cache line aliasing effects should also manifest themselves as low LLC utilisation.

Luckily netmap has a twiddle - 'dev.netmap.buf_size' / 'dev.netmap.priv_buf_size'. They're both .. 2048. So yes, the default buffer sizes are aligned, and there's likely some very poor LLC utilisation going on.

So, I tried 1920 - that's 2048 - (2 * 64) - ie, two cache lines less than 2048.

--                   System Read Throughput(MB/s):    104.92                  --
--                  System Write Throughput(MB/s):    382.32                  --
--                 System Memory Throughput(MB/s):    487.24                  --

It's now using significantly less memory bandwidth to do the same thing. I'm guessing this is because I'm now using the LLC much more efficiently.

Ok, so that's nice - but what about when it comes time to actually look at the packet contents to make decisions?

I've modified a copy of bridge to do a few things, mostly inspired by netmap-ipfw:
  • It does batch receive from netmap;
  • but it then looks at the ethernet header do decap that;
  • then it gets the IPv4 src/dst addresses;
  • .. and looks them up in a (very large) traditional hash table.
I also have a modified copy of pkt-gen that will use completely random source and destination IPv4 addresses and ports, so as to elicit some very terrible behaviour.

With an empty hash set, but still dereferencing the ethernet header and IPv4 source/destination, handling a packet at a time, no batching, no prefetching and only using one core/thread to run:

  • Bridges about 6.5 million pps;
  • .. maxes out the CPU core;
  • Memory access: 1000MB/sec read; 423MB/sec write (~1400MB/sec in total).
  • Bridges around 10 million pps;
  • 98% of a CPU core;
  • Memory access: 125MB/sec read, 32MB/sec write, ~ 153MB/sec in total.
So, it's a significant drop in memory throughput and a massive increase in pps for a single core.

Ok, so most of the CPU time is now spent looking at the ethernet header in the demux routine and in the hash table lookup. It's a blank hash table, so it's just the memory access needed to see if the bucket has anything in it. I'm guessing it's because the CPU is loading in the ethernet and IP header into a cache line, so it's not already there from DDIO.

I next added in prefetching the ethernet header. I don't have the code to do that, so I can't report numbers at the moment. But what I did there was I looped over everything in the netmap RX ring, dereferenced the ethernet header, and then did per-packet processing. This was interesting, but I wanted to try batching out next. So, after some significant refactoring, I arranged the code to look like this:
  1. Pull in up to 1024 entries from the netmap receive ring;
  2. Loop through, up to 16 at a time, and place them in a batch
  3. For each packet in a batch do:
    1. For each packet in the batch: optional prefetch on the ethernet header
    2. For each packet in the batch: decapsulate ethernet/IP header;
    3. For each packet in the batch: optional prefetch on the hash table bucket head;
    4. For each packet in the batch: do hash table lookup, decide whether to forward/block
    5. For each packet in the batch: forward (ie, ignore the forward/block for now.)
I had things be optional so I could turn on/off prefetching and control the batch size.

So, with an empty hash table, no prefetching and only changing the batch size, at buf_size=1920:
  • Batch size of 1: 10 million pps;
  • Batch size of 2: 11.1 million pps;
  • Batch size of 4: 11.7 million pps.
Hm, that's cute. What about with prefetching of ethernet header? At buf_size=1920:
  • Batch size of 1: 10 million pps;
  • Batch size of 2: 10.8 million pps;
  • Batch size of 4: 11.5 million pps.
Ok, so that's not that useful. Prefetching on the bucket header here isn't worthwhile, because the buckets are all empty (and thus NULL pointers.)

But, I want to also be doing hash table lookups. I loaded in a reasonably large hash table set (~ 6 million entries), and I absolutely accept that a traditional hash table is not exactly memory or cache footprint happy. I was specifically after what the performance was like for a traditional hash table. Said hash table has 524,288 buckets, and each points to an array of IPv4 addresses to search. So yes, not very optimal by any measure, but it's the kind of thing you'd expect to find in an existing project.

With no prefetching, and a 6 million entry hash table:

At 2048 byte buffers:
  • Batch size of 1: 3.7 million pps;
  • Batch size of 2: 4.5 million pps;
  • Batch size of 4: 4.8 million pps.
At 1920 byte buffers:
  • Batch size of 1: 5 million pps;
  • Batch size of 2: 5.6 million pps;
  • Batch size of 4: 5.6 million pps.
That's a very inefficient hash table - each bucket is going to have around 11 IPv4 entries in it, and that's checking almost a cache line worth of IPv4 addresses in it. Not very nice. But, it's within a cache line worth of data, so in theory it's not too terrible.

What about with prefetching? All at 1920 byte buffers:
  • Batch size of 4, ethernet prefetching: 5.5 million pps
  • Batch size of 4, hash bucket prefetching: 7.7 million pps
  • Batch size of 4, ethernet + hash bucket prefetching: 7.5 million pps
So in this instance, there's no real benefit from doing prefetching on both.

For one last test, let's bump the bucket count from 524,288 to 2,097,152. These again are all at buf_size=1920:
  • Batch size of 1, no prefetching: 6.1 million pps;
  • Batch size of 2, no prefetching: 7.1 million pps;
  • Batch size of 4, no prefetching: 7.1 million pps;
  • Batch size of 4, hash bucket prefetching: 8.9 million pps.
Now, I didn't quite predict this. I figured that since I was reading in the full cache line anyway, having up to 11 entries in it to linearly check would be cheap. It turns out that no, that's not exactly true.

The difference between the naive way (no prefetching, no batching) to 4-packet batching, hash bucket prefetching is not trivial - it's ~ 50% faster. Going all the way to a larger hash bucket was ~75% faster. Now, this hash implementation is not exactly cache footprint friendly - it's bigger than the LLC, so with random flows and thus no real useful cache behaviour it's going to degrade to quite a few memory accesses.

This has been quite a fun trip down the optimisation peephole. I'm going to spend a bunch of time writing down the hardware performance counters involved in analysing this stuff and I'll look to write a follow-up post with details about that.

One final things: threads and locking. I wanted to clearly demonstrate the cost of shared read locks on a setup like this. There's been lots of discussions about the right kind of locking and concurrency strategies, so I figured I'd just do a simple test in this setup and explain how terrible it can get.

So, no read-locks between threads on the hash table, batch size of 4, hash bucket prefetching, buf_size=1920:
  • 1 thread: 8.9 million pps;
  • 4 threads: 12 million pps.
But with a read lock on the hash table lookups:
  • 1 thread: 7 million pps;
  • 4 threads: 4.7 million pps.
I'm guessing that as I add more threads, the performance will drop.

Even taking a rwlock as a reader lock in pthreads is expensive - it's purely just an atomic increment/decrement in FreeBSD, but it's still not free. I'm getting the lock once for two hash table lookups - ie, the source and destination IP hash table lookups are done under one lock. I'm sure if I took the lock for the whole batch hash table lookup it'd work out a little better on a small number of CPU cores, but I think this demonstrates my point - read locks aren't going to cut it when you have a frequently accessed thing to protect.

The best bit about this post? The prefetching, terrible (large) hash table performance and general cache abuse is not new. Doing batching on superscalar Intel CPUs is not new. Documenting DDIO effectiveness using non-power-of-two-aligned buffer sizes is new, but it's just a rehash of the existing cache aliasing effect. But, I now have a little test bed to experiment with these things without having to try and involve the rest of a kernel.

Yes, I'll publish code soon.