A tale of two sequence numbers, or "when QoS seqno and CCMP PN don't match up"..

Many moons ago (say, 3 or 4 weeks - so hm, most-of-a-moon-ago actually) I found a rather curious failure condition in the ath(4) TX aggregation path. The colourful history is documented in FreeBSD kern/166190. In short - there are situations where sequence numbers were allocated in a different order to how frames were being added to the block-ack window tracking, and if you got unlucky, you'd cause the stack to think a frame was (far) outside the BAW.

The 30 second explanation:

Imagine you allocated four frames - sequence numbers 1, 2, 3 and 4. They have to be added to the block-ack window in precisely that order. Ie:

1. Starting condition: Window is at 0:63 (64 frame window, starting at 0, so ending at 63)
2. Add 1: Window is now at 0:63, starting at 1
3. Add 2: Window is now at 0:63, starting at 2
4. Add 3: Window is now at 0:63, starting at 3.

The reason the window pointer isn't moving along is because although you've sent the frames (or you're about to), you can't advance it until the other end has ACKed it (via a block-ack or a normal ACK.) For more information, google how 802.11n aggregation works.

The important bit here is that the window is still 0:63 and the starting point is now '3'. This continues all the way to trying to queue frame 64, where it will be outside of the current BAW and not be allowed to be transmitted. It'll sit in the software queue and wait until frame '0' has been ACKed and the BAW has been advanced to be 1:64 - at which point 63 will fall inside the window and will be transmitted.

So yes, the sender is tracking two things - the BAW and what the starting point is that they've added to the BAW.

Now, imagine instead of (1, 2, 3, 4) on the software queue, I somehow get preempted (or race between two sending threads, when using SMP) between 'allocated seqno' and 'queue to software queue'. In the existing code, a lock was held when:

• Allocating a sequence number, then it was dropped; then
• Adding it to the software queue.

Now because there was a period where no lock was being held, it's quite possible that what ends up on the software queue is (2, 1, 3, 4.) So:

1. Starting condition: Window is at 0:63
2. Add 2: Window is now 0:63, starting at 2.
3. Add 1: Window is 0:63, starting at 2; 1 is outside of the BAW (it's treated as a 'wraparound', so imagine it's 4095 seqno's away) so TX stalls.

This was the cause of the TX stalls that I was seeing originally in kern/166190. I "fixed" it by only allocating sequence numbers when the frame was about to be transmitted for the first time, and then adding it to the BAW right there. Since both sequence number allocation and adding to the BAW happened inside the same lock, everything was sweet.

Except, I totally forgot about CCMP PN. So under high enough UDP TX loads (say, > 200MBit), I'd hit the same race, but between 802.11 sequence numbers and CCMP PN sequence numbers.

CCMP PN is assigned during 802.11 encapsulation time, in the driver. In the ath(4) case, it's done during transmit and before being queued to the software queue. And it was being done outside of any locking.  So it's very possible that frames would end up on the software queue with 802.11 and CCMP PN sequence numbers out of lock-step.

What would happen?

Simply - after the 802.11n reordering occured on the receive side, the CCMP PN replay detector would notice sequence numbers out of order, and start tossing said out of order frames. Lots of packet loss ensued.

So, I sat down and started trying to address it. The simplest thing - wrap the whole encapsulation path between ieee80211_crypto_encap(), 802.11 sequence number assignment and software/hardware queueing behind the TID (well, hardware TXQ) lock. It took some time; I had to revert two earlier commits which introduced the delayed sequence number allocation.

This didn't fix things. So I was back to square one.

I started looking at all the places where the frames were being queued to the software queue and .. well, let's just say I spent Sunday swearing _at myself_ for all the weird and wonderful stupid mistakes I had made when writing/porting this code over.

The short version follows (the long version is "read the sys/dev/ath/ commit logs and the PR history"):

1. When I was queueing frames to the software queue, I'd check how deep the hardware queue was. If the hardware queue was shallow/empty, I'd direct dispatch up to two frames to the hardware to get things 'busy'. That will (hopefully) let further frames come along in the meantime and be aggregated. However, I was queueing the new frame to the hardware rather than queueing the new frame to the tail of the queue, and queueing the head frame of the queue to the hardware. That led to some out of order behaviour.
2. ath_tx_xmit_aggr() would check if the sequence number was within the block-ack window and if it wasn't, it'd queue the frame to the tail of the queue. This meant that any new frames that came along would be queued to the end of the queue, even if they had been dequeued from the head of the queue. This lead to frames on the software queue being out of order.
1. Frames on the software queue don't have to be in-sequence (as retries are prepended to the beginning of the list, and new frames are appended to the end) however they have to be in-order. If they end up being out of order, the BAW logic fails.

So, now that I allocate sequence numbers at packet queue time, I have to be triply sure that what ends up on the software queue is correctly in order, or the BAW logic will cause traffic stalls and potentially duplicate sequence number issues. Yes, this means that the old behaviour, whilst it now works right with all the right locking, requires me to correctly handle putting frames on the software queue. (Or, as I like to say, "keeping the bastard (me) honest.")

TL;DR - 802.11n aggregation works again. Now, to fix those pesky "queue full and I want to send a BAR frame so I can unblock the full queue and transmit" problems. At least that one is more tractable and easier to solve. Or is it.

FreeBSD, Netflix, CDN

The big news this week is the Netflix Openconnect platform, which was just announced. It uses off the shelf hardware - and FreeBSD + nginx.


The question is how you could spin it.


You could say "Netflix chose FreeBSD because they can keep their changes proprietary." Sure, they could. But they're not making appliances that they're selling - they're owning the infrastructure and servers. It's unclear whether they'd have to contribute back any Linux changes if they ran Linux on their open connect platform. They're making a conscious, public decision to distribute their changes back to FreeBSD - even though they don't have to.


You could say "Netflix chose FreeBSD because the people inside the company knew FreeBSD." Sure, they may have. The same thing could be said about why start-ups and tech companies choose Linux. A lot of the time its because they're chasing enterprise support from Redhat. But technology startups using Ubuntu or Debian tend not to be paying support fees - they hire smart people who know the technology. So, yes - "using what they know."


According to the Netflix Openconnect website:


"This was selected for its balance of stability and features, a strong development community and staff expertise. We will contribute changes we make as part of our project to the community through the FreeBSD committers on our team."



Let's pull this apart a little.

1. "Balance of stability and features." FreeBSD has long been derided for how slowly it moves in some areas. The FreeBSD developers tend to be a conservative bunch, trying to find the balance between new feature development and maintaining both stability and backwards compatibility.
2. "Strong community." FreeBSD has a strong technical development community and Netflix finds this very important. They're also willing to join and participate in the community like many other companies do.
3. "Staff expertise." So yes, their staff are familiar with FreeBSD. They're also familiar with Linux. They chose a platform which they have the expertise to develop, use and improve. They didn't just choose an unfamiliar platform because of marketing brochures or sales promises. I don't see any negatives here. I'm sure that Google engineers chose Linux to begin with because they were familiar with Linux.
4. "Contribute changes we make as part of our project to the community." Netflix  has committed to push improvements and fixes back to the upstream project They contributed some bug fixes in the 10GE Intel driver and IPv6 stack this week. This is collaborative open source working the way it should.

Why would Netflix push back changes and improvements into a project when they're not required to? That's something you should likely ask them. But the same good practice arguments hold for both Linux AND BSD projects:

• The project is a constantly moving target. If you don't push your changes back upstream, you risk carrying around increasingly larger changes as your project and your BSD upstream project diverge. This will just make things more difficult in the long run.
• By pushing your changes upstream, you make it easier to move with the project - including adopting improvements and new features. If you keep large changes to yourself, you will likely find it increasingly difficult to update your software to the newer upstream versions. And that upstream project is likely adding bug fixes, improvements and new features - which at some point you may wish to leverage. By pushing your changes upstream, you make it a lot easier to move to future versions of the upstream project, allowing you to leverage all those fixes and improvements without too much engineering time.
• By participating, you encourage others to adopt your technology. By pushing your changes and improvements upstream, you decrease the amount of software you have to maintain yourself (and keep patching as the upstream project moves along.) But you also start to foster technology adoption. The FreeBSD jail project started out of the desire by a hosting company to support virtualisation. Since then, the Jail infrastructure has been adopted by many other companies and individuals.
• When others use your technology, they also find and fix bugs in your technology; they may even improve it. The FreeBSD jail support has been extended to include IPv6 support, shared memory support and integrates into the VIMAGE (virtualised networking) stack (which, by the way, came from Ironport/Cisco.) As a company, you may find that the community will do quite a lot of the work that you would normally have to hire engineers to do yourself. This saves time and saves money.
• When companies contribute upstream, it encourages other companies to also contribute upstream. A common issue is "reinventing the wheel", where companies end up having to reinvent the same technology privately because no-one has contributed it upstream. They solve the same problems, they implement the same new features .. and they all spend engineering time and resources to do so.
• And when companies contribute upstream, it encourages (private) developers to contribute. Open source developers love to see their code out there in the wild, in places they never quite thought of. It's encouraging to see companies build products with their code and contribute back bug fixes and improvements. It fosters a sense of community and participation, of "give and take", rather than just "take". This is exactly the kind of thing that keeps developers coming back to contribute more - and it attracts new developers. Honestly, who wouldn't want to say that some popular device is running code that they wrote in their spare time?

So, you could rant and rave about the conspiracy side of Linux versus FreeBSD. You could rant on about GPL versus BSD. Or, you could see the more useful side of things. You could see a large company who didn't have to participate at all, agreeing to contribute back their improvements to an open source operating system. You could see that by doing so, the entire open source ecosystem benefits - not just FreeBSD. There's nothing stopping Linux or other BSD projects from keeping an eye on the improvements made by Netflix and incorporating those improvements into their own project. And it's another case of a company participating and engaging the open source community - and having that community engage them right back.

Good show, Netflix. Good show.

Fixing BAR handling and handle corner cases of things..

Part of the general 802.11n requirements is correctly handling TX aggregation and failures - where we need to pause the TX queue, send a BAR to forcibly move the remote end block-ack window to be in sync with the transmitters idea, and then continue sending frames.

This exposed a very annoying problem - what if the driver runs out of ath_buf entries to schedule TX frames? Or, what if the network stack runs out of mbufs? If we need to allocate an ath_buf/mbuf to send a BAR frame, but they're all allocated and unavailable, the driver/wireless stack will come to a grinding halt. Typically these allocated ath_buf's are allocated in the software queue, waiting for the BAR TX (or power-save wakeup) to send a frame.

So, I haven't fixed this. It's on my (very) short term to-do list. But it did expose some issues in how the net80211 BAR send code (ieee80211_send_bar()) works. In short - it didn't handle resource allocation failures at all. It worked fine if the driver send method (ic->ic_raw_xmit()) succeeded and just failed to TX the frame. But if it couldn't allocate an mbuf, or if the driver send method failed.. things just stopped. And when the BAR TX just stopped, the ath(4) software TX queue would just keep buffering frames, right until all the TX ath_buf entries were consumed.

This is obviously .. sub-optimal.

But this raises an interesting point - how much of your kernel and/or userland application handle resource shortages correctly? I've seen plenty of userland software just not check whether malloc() returned NULL and I've seen some that specifically terminate (non-gracefully) if malloc()/calloc() fails - Squid does this. But what about your network stack? How's it handle mbuf shortages? What about the driver stack? What about net80211 (ew) ? What if the kernel malloc() API has to sleep because there's no free memory available?

I don't (currently) have an answer - it's a difficult, cross-discipline problem. What I -can- do though (at least in my corner of the FreeBSD world - net80211 and ath(4)) is to start testing some of these corner cases, where I  force some resource shortages and ensure that the wireless stack and driver(s) recover somewhat gracefully. 802.11n is very unforgiving if you start dropping frames involved in an active aggregation session. So it's best I try and address these sooner rather than later.

FreeBSD/arm -

I've just found out that FreeBSD/armv6 now runs on this:

http://www.embeddedartists.com/products/kits/lpc3250_kit.php

This is excellent news. There's also been some recent work to improve pandaboard support (TI-OMAP) focusing on pmap and SMP fixes.

I'm so very glad that the FreeBSD community is pushing this ARM project along. Yes, the armv6 branch is not very well named (it supports more recent ARM platforms, not just armv6 improvements) and I'm hoping this will all make it into FreeBSD-HEAD soon.

And the winner of the most committing committer to src/sys over the last 12 months is ..

.. well, it was me. Up until last week. marius@ snuck in to take my place. I guess all of those commits I did about this time last year to start bringing FreeBSD's ath(4) support up to scratch are finally expiring out of the 12 month window.

(Source: http://people.freebsd.org/~peter/commits.html)

.. but I wouldn't call myself the most important committer. Or the most active. What I'd call myself is the "most active fixing a sorely needed corner of the codebase."

What I _could_ have done is simply do all my work in a branch and then merge it back into -HEAD when I was done. And, for about 6 months, this is what I did. The "if_ath_tx" branch is where I did most of the initial TX aggregation work.

But as time goes on, your branch diverges more and more from the master branch (-HEAD in FreeBSD) and you are faced with some uncomfortable decisions.

If you stay on the same branch point and never merge in anything from your master branch, you _may_ have a stable snapshot of code, but who knows how stable (or relevant) your work will be when you merge it back into master.

You have no idea if your work will break anything in master and you have no idea if changes in master have broken your work.

As time goes on, the delta between your branch point and the master branch increases, making it even more difficult to do that final merge back. It also has the side effect of making it increasingly likely that problems will occur with the merge (your code breaking master, master breaking your code, etc.)

So as uncomfortable as it was - and as much as I wanted things to stay stable - I did press through with relatively frequent merging. This means:

• I would pick specific development targets to work towards, at which point I'd stop developing and go into a code review/tidyup/testing phase;
• I'd do frequent merges from master back into my branch during active development - I wouldn't leave this until I was ready to merge my work back into master;
• Once I reached my development target and had done sufficient testing - including integrating changes from master back into my branch - I'd kick off a semi-formal review (read: email freebsd-wireless@) and call for testers/review;
• Only _then_ would I merge what was suitable back into master.

I wouldn't merge everything from my branch into master. In my instance, there were some debugging extensions that were easy to maintain (read: lots of device_printf() calls) but weren't suitable for FreeBSD-HEAD. But I merged the majority of my work each time.

But that doesn't always work. I managed to merge a bunch of ath(4), ath_hal(4) and net80211 fixes back into -HEAD as appropriate. But the TX aggregation code was .. well, rather large. So I attempted to break up my commit into as many small, self-contained functional changes as possible. Yes, there was a big "here's software TX queue and aggregation" as a big commit at the end but I managed to peel off more than 30% of that in the lead-up commits.

Why bother doing that?

Two words - version bisection. Once I started having users report issues, they would report something like "FreeBSD-HEAD revision X worked, revision Y didn't." (If I were lucky, of course.) Or, they'd note that a certain snapshot from a certain day worked, but the next day had a regression. If I had committed everything as one enormous commit after having spent 6 + months on the branch, I'd be in for a whole lot of annoying line-by-line debugging of issues. Instead, I was able to narrow down most of the regressions by trying all the different commits.

Now that 802.11n ath(4) TX aggregation and general 802.11n support is in the tree, I only use branches for larger scale changes that take a couple of weeks. For example, when fixing up the reset path to not drop any TX/RX frames. I do most of the bugfixing in FreeBSD-HEAD. I could do it in a branch and then do monthly merges, but I then have the same problems I've listed above.

In summary: don't underestimate how helpful it is to break down your commits into little, piecemeal, self-contained functional changes. It has the side effect of making you look really good in the committer statistics.

The initial introduction into "it's the NIC, stupid!"

I've finally hit that dreaded condition which hardware guys hate - where a NIC is behaving badly.

In my case, an IBM/Lenovo Thinkpad T60 has been modified (not by me) to take an Atheros AR9280 NIC. Unfortunately, the NIC was proving to be very unstable when doing 802.11n throughput. The investigations did show I was doing something slightly incorrect with TX descriptors (and I've since fixed that) but the stability issues remained.

The Atheros NICs can expose some host interface error conditions via the AR_INTR_SYNC_CAUSE register. These include PCI(e) transaction timeouts, illegal chip access (eg whilst the MAC is asleep), parity errors, and other rather nice things. FreeBSD's HAL and Linux ath9k does have the register definition for what the bits do - but unfortunately we don't keep statistics.

In my particular case:

• I'd see AR_INTR_SYNC_LOCAL_TIMEOUT occur. This is because a PCI(e) transaction didn't complete in time. I can tune these timeouts via a local register but that's not the point - I was seeing these errors when receiving only beacons from the access point. That's a bit silly.
  
• I'd also see AR_INTR_SYNC_RADM_CPL_DLLP_ABORT, which is an indication that the PCIe layer isn't behaving well.

I swapped it out with another AR9280 based NIC and suddenly all the instabilities have gone away. No TX hangs, no missed TX interrupts. Everything looks great.

So as an open source developer, I want to try and put some tools into the hands of the community to be able to debug what's going on - or, if that's not possible, at least get some indication that things are going wrong. Right now the only thing people see is "I see TX timeouts, it must be the driver/chip fault." There's too much going on to be able to conclude that.

My game plan is this:

• Implement statistics keeping for each of the SYNC interrupts and expose those via a diagnostic interface. Ben Grear has done something similar for Linux ath9k after a private email discussion. He's also seeing MAC sleep accesses, so it's quite likely we'll start finding/squishing these.
• Take the offending laptop/NIC to the office and attach it to a very expensive and fancy looking PCIe analyser. I'm hoping we'll find something really silly occuring - like lots of sleep state transitions, or a high number of parity errors.
• Try documenting this a lot better so users are able to understand what's going on when their NIC is misbehaving.
  

Concurrency in the TX path and when it all falls down..

I'm still (yes, still) hacking on the FreeBSD 802.11n ath(4) TX path. I'm trying to find and fix issues that creep up before I can flip on the 11n code by default.

I've become increasingly aware of the lack of locking in net80211, including some of the A-MPDU TX session management code. I know that I'll eventually have to plan out and implement some locking, but for now I'm just trying to squish whatever issues are showstoppers.

A user approached the freebsd-wireless list about two weeks ago and noticed that his 802.11n session was hanging after a bit of use. If he tried 802.11g, things worked fine. He tried SMP - and things worked fine. The symptoms? A number of frames seemed to be "stuck" and sitting in a software TX queue, not being transmitted. But other frames would be TXed fine, so it wasn't as simple as a totally confused TX BAW (Block-ack Window.)

After I managed to reproduce the issue locally, I discovered what was going on.

It was concurrency.

Specifically, that there's multiple places where ath_start() is being called, thus multiple concurrent TX is occuring.

Now, in the non-aggregate method, net80211 is doing all the sequence number assignment. I'm not so sure that in the normal case, the sequence numbers are being allocated in a consistent, sequential way - if the net80211 TX code is able to be called concurrently from multiple threads, sequence numbers can and will be occasionally "raced" and allocated in the reverse order that they're submitted to the driver. But I'm not here to fix that (however I'll eventually have to.)

In the aggregate method, the driver is doing the aggregation and sequence number assignment. For now, the driver is also doing the TX BAW tracking and frame queuing. So imagine this sequence of events:

* a frame is submitted via ath_start();

* since aggregation is enabled, it's allocated a sequence number;

* it's then thrown into the software queue;

* then at some later stage, the software queue is checked, the frame is popped out of the list and if it's inside the BAW, it's added to the BAW and TX;ed

* adding the frame to the TX BAW slides the left hand edge of the BAW to be at that sequence number. Any frames TXed with a seqno _less_ than this will be treated as outside of the BAW and put back onto the software queue for now.

Now, the locking only occurs at:

* the time the frame has the sequence number allocated;

* then when the queue is checked and the frame is popped off.

If two or more threads are allocating sequence numbers and doing work, it's quite possible that thread A will allocate (say) seqno 5, thread B will allocate seqno 6 and then add it to the BAW before thread A can. Then when thread A tries to do some work, it finds the queue has a frame with seqno 5 in it - and since it's before the left hand edge of the BAW (which is at 6, as it was successfully pushed to the hardware), it won't be transmitted and will stay in the software queue until the BAW sequence numbers wrap around to 0 and catch up.

Now, linux ath9k/mac80211 doesn't have this problem. The TX pathway is totally serialised, which means that even if multiple threads are trying to TX, only one thread will be able to enter the TX code at any time. The other threads get blocked.

So how can I solve this? The easy solution would be to serialise FreeBSD's net80211 and ath driver TX code. That way all of this nonsense will go away. For the net80211 side of things this may work - the legacy TX path, where sequence numbers are allocated by the stack, could benefit from serialisation. The throughput isn't ever going to be that great, so we wouldn't really hurt from it. But the trouble is making absolutely sure that the driver also does the same - even if I push the frames into the queue in order and ensure that they have sequential sequence numbers, there's no guarantee that a driver with concurrent entry paths into XXX_start() will de-queue the frames and push them into the hardware in the same order.

So what I've chosen to do instead is to ignore the legacy part for now, and not serialise anything. Instead, I'm doing the sequence number allocation (for aggregation, remember) -at the time I'm about to add the frame to the BAW and TX it to the hardware-. Ie, until the frame actually is able to be added to the BAW, it won't _have_ a sequence number. Since this action is done behind a lock, it's guaranteed to be sequential. The trick here is to only allocate the sequence numbers once it's known for certain that the frame _will_ be going out to the hardware.

For the legacy path, it's also likely worthwhile delaying the sequence number allocation until it's just about to go to the ifnet queue. That way the frames on the ifnet queue have sequence numbers that are in order. Then I need to fix each driver (ugh) to make sure they're dequeued fine.

I've written up the aggregation change and this so far works quite well. I don't want to tackle the legacy path yet or fix other drivers, not until I've verified this works. What I also should do is write some test cases to verify that indeed sequence numbers are being presented to the driver in order, so I can identify this happening in the wild.