Category Archives: 802.11n

Today’s Journey: Making AP mode power-save work better

I've been working on improving the net80211 and ath driver support for AP mode power save.

There's a few parts to it:

A station can tell an access point it's going to sleep by setting the power mgmt bit to 1 in a TXed frame;
The AP will then update the TIM entry in the beacon frames it sends out to reflect whether that station has any traffic queued;
A station can signal an AP that it's awake by sending a data frame with the power mgmt bit set to 0;
.. or it can request a frame at a time by using PS-POLL;
There's also the uAPSD stuff which I haven't yet implemented and won't likely do so for a while.

Now, it shouldn't be that difficult. Except, that it is.

If an AP has a bunch of frames queued to a station that has gone to sleep, it will keep trying to transmit those frames. That wastes air-time and results in annoying levels of packet loss.

When you're doing 802.11n, there's a whole lot more traffic going on and a lot more room to cause massive traffic issues if you drop frames. But you don't want to keep failing to transmit those frames or you'll end up spending a lot of time transmitting BAR frames to the station.

If the driver maintains a queue of frames (for say, software retransmit) then it also needs to ensure that the TIM bit is set correctly. Otherwise the AP may set the TIM bit to 0 because the net80211 stack has no queued frames to that node; but the driver itself has some frames. Thus, the station won't wake up and you'll see increased packet latency.

When PS-POLL is received, frames need to first be leaked from the driver queue BEFORE it starts leaking frames from the net80211 power save queue. The last thing you want is the wrong set of frames to go out.

So, I've spent the last few months extending the driver and network stack to make this feasible. There's new net80211 driver methods for tying into the TIM update process, the node power save status and the PS-POLL handling. The filtered frames handling in the ath driver is another precursor to this - it means that frames can be failed out very quickly and retried when appropriate.

(No, I'm not implementing software retransmit for non-11n traffic just yet. I will eventually. Just not yet.)

The final bits that I've been working on have been tricky.

When a node goes to sleep, you want to pause the driver transmission to the node - otherwise it will keep trying to transmit whatever is in the driver queue. For 11n this is terrible; it means that frames will keep failing to be transmitted and with enough failures, the traffic will stop whilst a BAR frame is sent. Grr.

Next was figuring out how to send frames whilst the node is "paused". I introduced a per-node "leak" counter which tells the driver transmit path that even though the node is asleep, a single frame should be scheduled. If one isn't available, the next frame sent will be scheduled. This handles the PS-POLL "null" response - ie, if there's nothing in the queue, the net80211 stack will queue a null data response with the MORE bit clear. That way the station will know there's currently nothing to receive.

But then, something odd started happening. Devices would disassociate and re-associate, but they'd still be marked as "asleep". So no traffic would occur. After digging into it a bit, I discovered that the only time a station transitions back to awake is when it receives a DATA frame with the power mgmt bit set to 0. Seeing management/control traffic from the station isn't enough. So for now, I just always transmit management/control frames regardless if the station is asleep or awake - except BAR frames. Those get software queued if the node is asleep. Now that management/control frames are transmitted directly, a station can re-associate and be marked as 'awake.'

Then I found that once a station re-associates, it should have all of its current association state reset. It may have had a bunch of aggregate frames queued to the hardware and those need to finish transmitting before we can start transmitting new data to the re-associated station. It may even have been in the middle of receiving a BAR frame! So, I have to gently (well, "gently") reset the association state to allow for currently queued frames to be cleaned up, but reset things like filtered frame state and BAR TX. Ew, but it needs to be done.

Also, if there's data queued to an asleep station and a BAR frame needs to go out, the BAR frame needs to go into the head of the software queue, not the tail. Otherwise it will have to wait for the queue to be transmitted - which, if there's a gap in the transmit block-ack window (hence needing the BAR), no further transmission will occur. Oops!

I then found that a sufficiently chatty node could end up filling the software queue full of buffers destined to it. This is a general problem in the ath driver which I'll eventually fix, but it became a huge problem with power save enabled. So, I've introduced a per-node maximum queue depth when it's asleep. That should limit the amount of pain that a single sleeping node can cause. I'll eventually introduce a limit for how many buffers an individual node can consume whether it's awake or asleep but that's for another day.

There's likely lots more corner cases that need to be addressed before I can merge this into -HEAD. I'm still seeing my macbook pro occasionally disassociate and not automatically re-associate and I'm not sure why. But things are behaving much, much better with sleeping devices.

Hey, look, it’s lots of atheros NICs in one laptop

So after many months of evenings and a whole lot of work internally to get the AR9380 HAL release vetted by legal, I bring you: a single, unified ath(4) and ath_hal(4) driver which works on all chipsets.

Now, the only chipsets I can fit _in_ this laptop:

[100309] ath0: mem 0xebf00000-0xebf0ffff irq 17 at device 0.0 on pci3
ath0: AR9280 mac 128.2 RF5133 phy 13.0
[100309] ath1: mem 0xedf00000-0xedf1ffff irq 18 at device 0.0 on pci4
ath1: AR9380 mac 448.3 RF5110 phy 0.0
[100309] ath2: mem 0xe4310000-0xe431ffff irq 16 at device 0.0 on cardbus0
ath2: AR5212 mac 5.9 RF5112 phy 4.3

.. that's an AR9280, AR5212 and AR9380 in the same laptop.

And, that's a 3x3 AR9380:

static_rix (-1) ratemask 0xffffffff
[ 250] cur rate 20 MCS since switch: packets 1 ticks 2647581
[ 250] last sample (6 Mb) cur sample (0 ) packets sent 9
[ 250] packets since sample 9 sample tt 0
[1600] cur rate 22 MCS since switch: packets 15 ticks 2647530
[1600] last sample (21 MCS) cur sample (0 ) packets sent 6049
[1600] packets since sample 0 sample tt 532
TX Rate TXTOTAL:TXOK EWMA T/ F avg last xmit
[ 6 Mb: 250] 4:4 (100.0%) 4/ 0 760uS 2640242
[20 MCS: 250] 9:9 (100.0%) 9/ 0 440uS 2647581
[20 MCS:1600] 969:969 (100.0%) 57/ 0 572uS 2647445
[21 MCS:1600] 1517:1517 (100.0%) 74/ 0 613uS 2647557
[22 MCS:1600] 1990:1990 (100.0%) 92/ 0 529uS 2647557
[23 MCS:1600] 73986:73462 ( 99.5%) 5661/ 0 755uS 2647538

Now, I'm sure the AR5210 will work with an AR9280 and an AR9380 in the same laptop - it's just that the hardware form factor won't let me fit them all at the same time.

Hey, look, it’s lots of atheros NICs in one laptop

Now, the only chipsets I can fit _in_ this laptop:

.. that's an AR9280, AR5212 and AR9380 in the same laptop.

And, that's a 3x3 AR9380:

Now, I'm sure the AR5210 will work with an AR9280 and an AR9380 in the same laptop - it's just that the hardware form factor won't let me fit them all at the same time.

AR9380 support on FreeBSD; why it’s taken so long..

There's now public, open source support for the AR9380 and later chips for FreeBSD.

It's not yet in the -HEAD tree - I'll get to that.

Let me take you on a bit of a journey.

I started a little side project late last year - I wanted to see if I could make the AR9380 HAL from the Qualcomm Atheros mainline driver (10.x branch) work on FreeBSD. I was hoping that the HAL API hadn't drifted all that much over the years.

Why do this? Two reasons:

I wanted to see if I could open source the HAL and have it work with FreeBSD; and
I didn't want to take on a similar project to what ath9k had to do - which is to take the existing HAL, convert it into something Linux-upstream-compatible, then push THAT into open source.

There's only one of me, and I don't want to spend all of my evenings trying to figure out which changes to the internal driver HAL need merging into "my" version of the HAL. I want to leverage all of the development and debugging that we do internally for the HAL. The ath9k team (both public and internally) need to do a lot of manual inspection and coding in order to pick up fixes and features from the internal driver. Since there's one of me, I'd rather optimise my time (read: get some sleep at some point.)

Then there's the third point that I didn't mention above:

I want to see how feasible it is to do snapshots from our internal codebase and push those out, rather than having to maintain a separate driver tree (sometimes based on the internal driver tree, sometimes re-implemented) and all the associated complication there.

This bit is pretty important. There's plenty of code I didn't want to open up. The bulk of the AR9300 HAL is already open sourced via the ath9k driver in Linux. So for the most part I'm open sourcing what we already have open sourced. However, I want to try and streamline the process for taking internally developed code and push it open.

This involves a few things.

Firstly, how much of the internal driver code is written with the idea that it's going to appear in the public eye? It depends what you think of as public - are your company developers "public" ? Are your customers with source code "public" ? It may not necessarily be "the general community." When you're writing code that's eventually going to be open sourced, you may need to make some decisions about how you structure your code.

For me, it was (mostly) easy. A very large amount of the "stuff that shouldn't be released" was already wrapped up in #ifdef's - stuff like emulation code, for example. So the public HAL snapshot is actually missing a lot of code that our internal version has. All I did (heh!) was pass it through 'unifdef'.

Next is whether the code is nice to look at. Is it formatted well? Is it well designed? Does it compile without warnings? Even on clang? These should be thought about whether or not your target audience is public or not. It's just good design. Companies may be worried about exposing the code, as if it will show badly on them. Well, yes, you should. But hey - we the open community would rather you release the code and take constructive criticism instead of keeping it closed. Who knows, it may actually help you!

The Linux upstream push is actually good here - the Linux system maintainers don't take "bad code". They hold the developers to a higher standard and this is forcing companies to think a bit more about how they develop things. Now, whether companies view this as a cost-centre or a benefit is not something I wish to discuss here. The point is that by working in the Linux upstream community, companies are being forced to tidy up their game a little.

Ok, enough of the back-story. How'd it actually all happen?

The short version - there was API drift, yes. There was a bunch of driver layer stuff that needed to happen. But it wasn't terribly painful. It required me to clean up the driver a bit and implement some nicer tools.

The long version:

There was an internal attempt to partly convert the HAL code internally over to a format that is Linux-upstream compatible. This involved a variety of formatting changes - function names and indentation changed. It also involved a variety of variable / method changes - eg halMciSupport became hal_mci_support. The boolean type changed - HAL_BOOL and AH_TRUE/AH_FALSE became bool, true & false. These needed to be renamed back to the HAL style before I could make it compile.
FreeBSD stripped out the HAL_CHANNEL stuff from its HAL, replacing it with a direct reference to the net80211 type (struct ieee80211_channel.) This made things slightly tidier but it did put an external dependency on the HAL. I may end up going through the FreeBSD HAL and undoing this at some point; but it's a big job.
A variety of APIs changed over time. Although the bulk of the APIs stayed the same, they grew parameters (eg 11n TX and RX antenna and chain configuration); the TX descriptor APIs now take a list of TX buffers rather than a single TX buffer, and other random other things.

So, what was I going to do?

My first cut was to just take a snapshot of the HAL and rename / shuffle things around enough to make it compile.

The first thing I did was to create a set of HAL stub functions. All the stub functions did was print out their method name and return. This way I wasn't surprised by a NULL pointer dereference when the HAL or driver called an unimplemented method - I'd get told which method was being called.

I started with the bare minimum code needed to support probe and attach - which required a surprising amount of code to be converted over. But it was mostly mechanical work. And it worked - enough to get things probing and attaching. I didn't bother with frame transmission and reception just yet - getting probe/attach was enough.

Then I realised that I wanted to this in a git branch, so I could import future versions of the HAL into master and then merge it into my branch. That's what I did. The HAL from 10.x was in master, and my FreeBSD port lived in 'local/freebsd'.

Next was figuring out whether to rename/fix API functions, or to use glue functions in order to deal with API differences. I've fixed some API differences (eg the reset path), but I ended up using a lot of wrapper functions to get the APIs to line up.

The important bits to bring up (in rough order) in order to see whether things are working:

Probe/attach/detach;
The reset path;
The initial calibration path (ADC calibration, IQ calibration, NF/AGC calibration);
The radio configuration path (ie, programming the analog section with the right frequencies, channel width, filter setup and such);
Interrupt handling;
ANI support;
RX path.

The RX path was the important bit. Once frame RX was working, I could do things like run the NIC in monitor mode and verify that HT20 and HT40 were working. And yes, that's pretty much what I did.

But at this point, the RX path exposed the first major API change - the whole FIFO setup that the AR9380 and later required. They don't support the list-based TX and RX that previous NICs supported. (Well, they _kind_ of do on the TX side, see below.)

The major change here required in the driver is that the RX descriptor is actually in the same memory area as the RX buffer. Ie, the first 'x' bytes of the passed in buffer is where the NIC DMAs the RX completion information to. Previous NICs have two areas for each RX frame - a RX descriptor area and an RX buffer area. Descriptors are in non-cachable memory, so I had to teach the FIFO RX path to support descriptors in cachable memory. I also had to teach the RX path to "skip" the 'x' bytes in order to hand the start of the data payload up to the net80211 stack. Finally, there's two RX FIFOs - one for high priority frames (beacons, uAPSD frames, PS-POLL frames, etc) and low-priority frames (everything else.) I had to teach the stack about this.

So, you can see the changes to the RX code - there's now a set of methods that implement RX - stop, start, flush, descriptor processing. The legacy routines stayed where they were. The new routines just overrode those methods.

And with that, RX came to life.

Next was TX. TX is a bit more special. There's only 8 TX FIFO entries per hardware queue (QCU 0..9); so I can't just push all the frames I want into the list. I also have four TX data buffer pointers per descriptor, rather than one per descriptor in the past. Finally, the TX status FIFO is completely separate from the TX FIFO itself - legacy chips would put the TX status at the end of the final descriptor in a frame.

This required some pretty significant refactoring of the TX path in order to expose the correct hooks to do this all properly. I won't go into the details here - suffice to say that I'm still working on it.

The next problem with TX was figuring out exactly what TX descriptor flags I was setting incorrectly. I eventually gave in and wrote some ALQ based logging which dumps the TX and RX descriptors into an ALQ log which I can then read from userland. This made it very, very easy to inspect what was going on - I was even finding bugs with the earlier chipset code!

Initially I used this to discover I wasn't correctly filling out all four buffer pointers in each TX descriptor. I can't leave any NULL if there's more descriptors for a given frame.

Then I used it to discover whether I was setting up the general flags right - TX chainmask, TX rate, duration, etc. I (re) discovered a hardware limitation with the AR9380 - I need to pad aggregate frames that use RTS with a little more pad delimiters or the transmission underruns. I was able to take these text dumps and give them to the Qualcomm Atheros MAC/PHY team for assistance and they were very impressed by the sophistication of my debugging tools.

Now I have the TX and RX side working. I pushed all of the driver side code into the public FreeBSD repository. I promised people that I would eventually open up the HAL side of things, but I figured that keeping the driver side of this closed was just plain silly. It also meant that if I did stop working on things (for whatever reason), the driver side was done - all that would need porting was the HAL.

Then I began the internal process to get the HAL opened up. I won't go into this in too much detail - suffice to say it took some engineering and legal review to get approval for this. The approval came in about two weeks ago and I pushed the repository into github shortly afterward.

Shortly after that, people started testing it and filing bugs. This part made me happy - there's a few small bugs that are actually in our 10.x mainline tree. I'll be pushing fixes back into the internal driver tree soon.

So, what's next?

I need to push the repository into a vendor branch in FreeBSD, then merge it into the kernel tree so it can be compiled by default.

I then need to get an updated version of the HAL approved by legal/engineering and push that update into the public git repository. Once that's done, I'll do a git merge into my branch and fix up whatever merge issues there are. This updated HAL includes some fixes for TX power and the AR95xx embedded SoC that we've just released. I hope to try and do a HAL update every month or two based on what bugs and features are introduced into the internal mainline driver.

I still have a bunch of driver work to finish up - notably I need to finish optimising the TX FIFO path in the driver and I need to implement MCI support. But the driver is now usable for me at least and I hope it'll become increasingly usable by others.

This has been a long and interesting trip.

Why PCI latency timers matter..

My latest "are you serious?" moment recently was trying to figure out the root cause of this performance issue with the AR5416 cardbus NIC on some of my test laptops.

Now, the AR5416 is Atheros' first 802.11n NIC, so it has some rough edges. But I was seeing some ridiculously bad transmission failures and I couldn't pinpoint them.

Not only that, I was seeing great performance (~ 130mbit TCP) on a specific laptop (Lenovo T41p) but the Lenovo T60 and T400 both performed extremely poorly.

To make matters weirder - the NIC performed great when speaking to another NIC in the same laptop. Just not to another physically separate device.

So, after much digging, here's what I discovered.

Firstly - I used my athalq packet descriptor logging and inspection tool (that's in FreeBSD-HEAD - no custom closed source code here!) to investigate the TX frames being sent to the hardware. What I found was troubling - large numbers of frames had TX data and TX delimiter underruns.

I then discovered that my code for counting TX data / delimiter underruns was totally incorrect - it's possible to see both a data/delimiter underrun error _with_ a valid transmitting frame. What was going on was cute - the hardware would start transmitting an aggregate frame but the DMA wouldn't keep up during said transmission and half way through the frame it would underrun. This only happened at higher MCS rates.

So making shorter aggregate frames fixed it, as well as increasing the delimiter count between frames. Both had the effect of reducing the likelihood of the NIC failing to transmit a longer aggregate. But they weren't solutions.

So I went digging. What I found was pretty simple in theory: the PCI latency timer on the NIC was being set to something appropriate (0xa8) but the PCI latency timer on the cardbus PCI bridge itself was not (0x20.) So any other bus activity would cause the NIC to not get the bus and it'd miss its DMA window.

Once I manually fixed the PCI bridge latency timer to be 0xa8, everything returned to normal.

However - there's only one thing on this PCI bridge - the cardbus interface itself. That's why it's so kooky. I would've thought that I'd have to up the value on the rest of the PCI bridges up to the root complex. There's no latency timer for PCIe, so it's not a problem there. So there's likely some very subtle timing involved that's just plain broken by default on how the BIOS initialises this cardbus slot and FreeBSD is not overriding it.

Now, if you see crappy performance on the PCI/cardbus 802.11n NICs in FreeBSD, you can check the output of 'athstats' to see if you do see TX underruns of any sort. If you are, the hardware isn't meeting the DMA deadlines it needs to DMA out frames and you need to do some further digging into your system to see why.

Be careful of adding debugging, as microseconds count..

.. after tinkering with the TDMA code a bit more, I discovered why I was seeing larger swings in the TDMA slot timings.

Two words: Debug Code.

Well, to be more specific - I added some debugging code that by default didn't do anything. But it was still there; it checked a debug flag and didn't log anything if it was disabled. But that would take time to execute. Since that debugging code sat _between_ the routines doing math with the RX timestamp and the nexttbtt register, it would calculate a slightly larger TSF offset.

Once I moved the debug code out from where it is and grouped all that register access and math together, the slot timing swings dropped by a few microseconds and everything went back to smooth.

Tsk. I should've known better.

At least now the TDMA code is working well on the 802.11n chips. Yes, it's still only 802.11abg rates, but it works. I've also found the PCU MISC_MODE bit to enforce packets don't transmit outside of the burst window and that is working quite fine with TDMA.

So, I think I can say "mission accomplished." I'll tidy up a few more things and make sure TX only occurs in one data queue (as mentioned in my previous post, they all burst independently at the moment..) and then patiently wait for someone to implement 802.11n adhoc negotiation so 802.11n MCS rates and aggregation magically begins to work. Once that's done, 802.11n TDMA will become a reality.

Getting TDMA working on 802.11n chipsets

A few years ago, a bunch of clever people figured out how to implement TDMA using the Atheros 802.11abg NICs. Sam Leffler has a great write-up here. He finished that particular paper with some comments about the (then) upcoming 802.11n chipsets from Atheros and how they would be better suited to the kinds of tricks he pulled with the Atheros MAC.

But, if you tried bringing up TDMA on the Atheros 802.11n chips, it plain just didn't work. Lots of people gnashed teeth about it. I was knee deep in TX aggregation work at the time so I just pushed TDMA to the back of my mind.

How it works is pretty cute in itself. To setup a TX "slot", the beacon timer is used to gate the TX queues to be able to start transmitting. Then a "channel ready time" burst length is configured, which is the period of time the TX queue can transmit. Once that timer expires, no new TX is allowed to begin. Sam then slides the slave TX window along based on when it sees a beacon from the master, as everything is synchronised against that.

Luckily, someone did some initial investigation and discovered that a couple of things were very very wrong.

Firstly, when fetching the next target beacon transmission time ("TBTT"), the AR5212 era NICs returned it in TU, but the AR5416 and later returned it in TSF.

Secondly, the TSF from each RX frame on the AR5212 is only 15 bits; on the AR5416 and later its 32 bits. The wrong logic was used when extending the RX frame timestamp from the AR5416 from 32 bits to 64 bits, and it was causing the TSF to jump all over the place.

So with that in place, he managed to stop the NICs from spewing stuck beacons everywhere (a classic "whoa, who setup the timers wrong!" symptom) and got two 11n NICs configured in a TDMA setup. But he reported the traffic was very unstable, so he had to stop.

Fast-forward about 12 months. I've finished the TX aggregation and BAR handling; I've debugged a bunch of AP power save handling and I'm about to reimplement some things to allow me to finish of AP power save handling (legacy/ps-poll and uapsd) in a sane, correct fashion. I decide, "hey, TDMA shouldn't be that hard to fix. Hopefully there are no chip bugs, right?" So, I plug in a pair of AR5413 (pre-11n NICs) and get it up and running. Easy. Then I plug in an AR5416 as the slave node, and .. it worked. Ok, so why was he reporting such bad results?

Firstly, Sam exposed a bunch of useful TDMA stats from "athstats". Specifically, if you start tinkering with TDMA, do this:

$ athstats -i ath0 -o tdma 1

input output bexmit tdmau tdmadj crcerr phyerr TOR rssi noise rate
619817 877907 25152 25152 -4/+6 142 143 1 74 -96 24M
492 712 20 20 -0/+7 0 0 0 74 -96 24M
496 720 20 20 -2/+6 0 0 0 74 -96 24M
500 723 21 21 -6/+4 0 0 0 75 -96 24M

When I was debugging the initial AR5416 TDMA stuff, the tdma adjust figures bounced everywhere between 0 and 1000uS off. That was obviously not stable.

So, I looked at what debugging was in the driver itself. There was some (check if_ath_debug.h for the TDMA and TDMA timer flags), and after a bit of digging I realised that every time the TSF was just about to converge, it would be bumped out 1000uS. Then it would slowly drift back to converge, then it'd fall out 1000uS. This kept repeating. It made no sense; every time it calculated the delta between the expected and real TSF, it would "bump" the TSF by that much. That way the TSF would actually be correct. It shouldn't be out by almost as much the next RX'ed frame.

I did some initial testing to ensure the TSF was running at the expected 1uS interval (it was) and the master side was also running at the expected 1uS interval (it also was), so it wasn't out of sync clocks. The TSF bump must not be "right".

Enter the next bug - on the AR5416 and later, the TSF writes must be done as a 64 bit write. Ie, you write TSF_L32 first, then TSF_U32. At that point it gets internally updated and everything is consistent. If you don't do that, it doesn't latch.

Ok, so that fixed the intial drift. But after about 60 seconds, the TSF adjust parameters started varying ridiculously wildly. Ok, so 60 seconds equaled around 65,535 TU (where a TU is 1.024 milliseconds) so I began to wonder if I was seeing something wrap at that point.

Enter the next bug. The math involved in calculating the expected slot time was based on the 64 bit TSF and it was converted down to a 16 bit TU value from 0 .. 65535 TU. On the AR5212 era chips, the nexttbtt timer had a 16 bit resolution. When the nexttbtt value was read from that register, it was already 16 bits. So the "TSF delta" between the expected and real slot time was calculated between these two 16 bit values. However, on the AR5416 and later, the nexttbtt value was a 32 bit TSF (microsecond) value. Even when converted to a TU (1.024 millisecond) value, it would wrap at a value much greater than 65,535 TU. So the comparison would soon be between a value from 0..65,535 TU and 0 .. much-bigger-than-65,535 TU. The tsfdelta would become very, very negative.. and things would go nuts.

Ok, so that fixed another behavioural issue. Things were looking good. The slot time sync was stable. So I started passing traffic. Everything looked good.. for about 60 seconds. Then everything went slightly nuts again. But only with traffic. The timing calculations went way, way out.

Here's an example of the beacons coming in. Note that the expected beacon interval here is 49,152uS.

[34759308] [100933] BEACON: RX TSF=67127545 Beacon TSF=3722387514 (49152)

[34759357] [100933] BEACON: RX TSF=67176714 Beacon TSF=3722436670 (49156)

[34759442] [100933] BEACON: RX TSF=67262432 Beacon TSF=3722521354 (84684)

[34759454] [100933] BEACON: RX TSF=67275216 Beacon TSF=3722533850 (12496)

[34759504] [100933] BEACON: RX TSF=67325995 Beacon TSF=3722583802 (49952)

[34759552] [100933] BEACON: RX TSF=67374479 Beacon TSF=3722632108 (48306)

[34759602] [100933] BEACON: RX TSF=67424546 Beacon TSF=3722681282 (49174)

[34759652] [100933] BEACON: RX TSF=67475842 Beacon TSF=3722731578 (50296)

[34759701] [100933] BEACON: RX TSF=67525900 Beacon TSF=3722780730 (49152)

The master beacons were not coming in stable in any way. The main reason this would happen is if the air was busy at the master target beacon transmission time. So it would delay transmitting the beacon until the air was free.

This is where I decided it was about time I inserted some tracing into the TDMA code. I had introduced some ALQ based tracing in the ath(4) driver recently, specifically to trace TX and RX descriptors. I decided to add TDMA trace points. That way I could look at the TDMA recalculation along with the TX and RX from the driver.

What I found was very .. grr-y. After about 60 seconds (surprise), the TX would burst FAR past the 2.5 milliseconds it was supposed to. Why the heck was that happening?

After a bunch of staring-at-documentation and talking with some people well-versed in how the Atheros MAC worked, we realised the only real explanation is that the beacon timer was firing after the burst time, retriggering the timer. But why would it be? I stared at the debugging output a little more, and look at what I saw:

[34759258] [100933] BEACON: RX TSF=67077388 Beacon TSF=3722338362 (49152)

[34759258] [100933] SLOTCALC: NEXTTBTT=67081216 nextslot=67081224 tsfdelta=8 avg (5/8)

[34759258] [100933] TIMERSET: bt_intval=8388616 nexttbtt=65510 nextdba=524078 nextswba=524070 nextatim=65511 flags=0x0 tdmadbaprep=2 tdmaswbaprep=10

[34759259] [100933] TSFADJUST: TSF64 was 67077561, adj=1016, now 67078577

.. everything here is fine. We're programming nexttbtt in TU, not TSF (because the HAL API specifies it in TU for the older, pre-11n chips. Ok. Suspiciously close to the 65,535 TU boundary.

Then:

[34759308] [100933] BEACON: RX TSF=67127545 Beacon TSF=3722387514 (49152)

[34759308] [100933] SLOTCALC: NEXTTBTT=22528 nextslot=67131381 tsfdelta=-11 avg (5/7)

[34759308] [100933] TSFADJUST: TSF64 was 67127704, adj=11, now 67127715

Ok, but it's just a TSF adjust, no biggie. But, then this happened:

[34759357] [100933] BEACON: RX TSF=67176714 Beacon TSF=3722436670 (49156)

[34759357] [100933] SLOTCALC: NEXTTBTT=71680 nextslot=67180550 tsfdelta=6 avg (5/7)

[34759357] [100933] TIMERSET: bt_intval=8388616 nexttbtt=71 nextdba=566 nextswba=558 nextatim=72 flags=0x0 tdmadbaprep=2 tdmaswbaprep=10

[34759357] [100933] TSFADJUST: TSF64 was 67176888, adj=1018, now 67177906

At this point, it was clear. nexttbtt was very very small. Somehow it was very very small - 71 TU is very, very much before the current TSF of somewhere around 67,127,545. At this point the Next TBTT timer would just keep continously firing. And this would keep re-gating the TX queue, allowing it to just plain keep bursting. That explains why everything was going crazy during traffic.

This again was another example of the code assuming it was an AR5212 era NIC. The nexttbtt value was being trimmed to be between 0 and 65,535 TU. After I fixed that and fixed up the math a bit, nexttbtt was being correctly programmed and suddenly everything started working. And quite well.

So, now the basics are working. I'll audit the math to ensure everything wraps consistently at the 32-bit TSF boundary (ie, 4 billion microseconds, give or take) as that doesn't take too long to occur. But the 11n chips now behave the same as the 11a chips do when doing TDMA.

So what's next?

The "tx time" calculation needs to be aware of the 11n rate configuration, so it can calculate the guard time correctly. Right now it uses the non-11n aware rate -> duration HAL function;
The TX path has to be rejiggled a bit to ensure _all_ traffic gets stuffed into one TX queue (well, besides beacons.) Management and higher priority traffic has to do this too. If not, then multiple TX queues can burst and they'll burst separately, blowing out the TX slot timing;
Someone needs to get 11n adhoc working, so that 11n rates are negotiated during adhoc peer establishment. Then aggregation can just magically work at that point (the TDMA code reuses a lot of adhoc mode vap behaviour code);
802.11e / 802.11n delayed block-ACK support needs to be implemented;
Then when doing TDMA, we can just burst out an aggregate or two inside the given slot time, then wait for a delayed block ACK to come back from the remote peer in the next slot time! Yes, I'd like to try and reuse the standard stuff for doing delayed block-ack rather than implementing something specific for 802.11n aggregation + TDMA.
.. and yes, it'd be nice for this to support >2 slave terminals, but that's a bigger project.

Right now I think I'll tackle #1 and then make sure the 11n NICs can be configured in a static MCS rate, without aggregation. The rest will have to be up to someone else in the community. My plate is full.

So, TDMA on the 802.11n NICs is now working. Go forth and hack!

Power save, CABQ, multicast frames, EAPOL frames and sequence numbers (or why does my Macbook Pro keep disassociating?)

I do lots of traffic tests when I commit changes to the FreeBSD Atheros HAL or driver. And I hadn't noticed any problems until very recently (when I was doing filtered frames work.) I noticed that my macbook pro would keep disassociating after a while. I had no idea why - it would happen with or without any iperf traffic. Very, very odd.

So I went digging into it a bit further (and it took quite a few evenings to narrow down the cause.) Here's the story.

Firstly - hostapd kept kicking off my station. Ok, so I had to figure out why. It turns out that the group rekey would occasionally fail. When it's time to do a group rekey, hostapd will send a unicast EAPOL frame to each associated station with the new key and each station must send back another EAPOL frame, acknowledging the fact. This wasn't happening so hostapd would just disconnect my laptop.

Ok, so then I went digging to see why. After adding lots of debugging code I found that the EAPOL frames were actually making to my Macbook Pro _AND_ it was ACKing them at the 802.11 layer. Ok, so the frame made it out there. But why the hell was it being dropped?

Now that I knew it was making it to the end node, I could eliminate a bunch of possibilities. What was left:

Sequence number is out of order;
CCMP IV replay counter is out of order;
Invalid/garbled EAPOL frame contents.

I quickly ruled out the EAPOL frame contents. The sequence number and CCMP IV were allocated correctly and in order (and never out of sequence from each other.) Good. So what was going on?

Then I realised - ok, all the traffic is in TID 16 (the non-QoS TID.) That means it isn't a QoS frame but it still has a sequence number; so it is allocated one from TID 16. There's only one CCMP IV number for a transmitter (the receiver tracks a per-TID CCMP IV replay counter, but the transmitter only has one global counter.) So that immediately rings alarm bells - what if the CCMP IV sequence number isn't being allocated in a correctly locked fashion?

Ok. So I should really fix that bug. Actually, let me go and file a bug right now. There.

There. Bug filed. PR 172338.

Now, why didn't this occur back in Perth? Why is it occuring here? Why doesn't it occur under high throughput iperf (150Mbps+) but it is when the iperf tests are capped at 100Mbps ethernet speeds? Why doesn't it drop my FreeBSD STAs?

Right. So what else is in TID 16? Guess what I found ? All the multicast and broadcast traffic like ARPs are in TID 16.

Then I discovered what was really going on. The pieces fell into place.

My mac does go in and out of powersave - especially when it does a background scan.
When the mac is doing 150Mbps+ of test traffic, it doesn't do background scans.
When it's doing 100Mbps of traffic, the stack sneaks in a background scan here and there.
Whenever it goes into background scan, it sends a "power save" to the AP..
.. and the AP puts all multicast traffic into the CABQ instead of sending it to the destination hardware queue.
Now, when this occured, the EAPOL frames would go into the software queue for TID 16 and the ARP/multicast/etc traffic would go into the CABQ
.. but the CABQ has higher priority, so it'll be transmitted just after the beacon frame goes out, before the EAPOL frames in the software queue.

Now, given the above set of conditions, the ARP/multicast traffic (which there's more of in my new place, thanks to a DSL modem that constantly scans the local DHCP range for rogue/disconnected devices) would be assigned sequence numbers AFTER the EAPOL frames that went out but are sitting in the TID 16 software queue. The Mac would receive those CABQ frames with later sequence numbers, THEN my EAPOL frame. Which would be rejected for being out of sequence.

The solution? Complicated.

The temporarily solution? TID 16 traffic is now in a higher priority hardware queue, so it goes out first. Yes, I should mark EAPOL frames that way. I'll go through and tidy this up soon. I just needed to fix this problem before others started reporting the instability.

The real solution is complicated. It's complicated because in power save mode, there's both unicast and multicast traffic going into the same TID(s) but different hardware queues. Given this, it's quite possible that the traffic in the CABQ will burst out before the unicast packets with the same TID make it out via another hardware queue.

I'm still thinking of the best way to fix this.

Lessons learnt from fiddling with the rate control code..

(Note before I begin: a lot of these ideas about rate control are stuff I came up with before I began working at my current employer.)

Once I had implemented filtered frames and did a little digging, I found that the rate control code was doing some relatively silly things. Lots of rates were failing quite quickly and the rate control was bouncing all over the place.

The first bug I found was that I was checking the TX descriptor completion before I had copied it over - and so I was randomly failing TX when it didn't fail. Oops.

Next, don't call the rate control code on filtered frames. They've been filtered, not transmitted. My code wasn't doing that - I'm just pointing it out to anyone else who is implementing this.

Then I looked at what was going on with rate control. I noticed that whenever the higher transmission rates failed, it took a long time for the rate control code to try and sample them again. I went and did some digging - and found it was due to a coding decision I had made about 18 months ago. I treated higher rate failures with a low EWMA success rate as successive failures. The ath_rate_sample code treats "successive failures" as "don't try to probe this for ten seconds." Now, there's a few things you need to know about 802.11n:

The higher rates fail, often;
The channel state changes, often;
Don't be afraid to occasionally try those higher rates; it may actually work out better for you even under higher error rates.

So given that, I modified the rate control code a bit:

Only randomly sample a few rates lower than the current one; don't try sampling all 6, 14 or 22 rates below the high MCS rates;
Don't treat low EWMA as "successive failures"; just let the rate control code oscillate a bit;
Drop the EWMA decay time a bit to let the oscillation swing a little more.

Now the rate control code behaves much better and recovers much quicker during unstable channel conditions (eg - adrian walking around a house whilst doing iperf tests.)

Given this, what could I do better? I decided to start reading up on what the current state of play with 802.11n aware rate control and rapidly came to the conclusion that - wow, we likely could do it better. The Linux minstrel_ht algorithm is also based on John Bickett's sample rate code, but instead of using a EWMA and minimising packet transmission time, it uses the EWMA to calculate a theoretical throughput and maximises that. So, that sounds good, right?

Except that the research shows that 802.11n channels can vary very frequently and very often, especially at the higher MCS rates. The higher MCS rates can become better and worse within a window of a second or two. So, do you want to try and squeeze the last of throughput out of that, or not?

Secondly, using "throughput" as a metric is fine if your air time is .. well, cheap. But what if you have many, many clients on an AP? Your choice of maximising throughput based on what the error rate predicts your data throughput is doesn't take airtime into account. In fact, if you choose a higher MCS rate with a higher error rate but higher throughput, you may actually be wasting more air with those retransmissions. Great for a single station, but perhaps not so great when you have lots.

So what's the solution? The open source rate control stuff doesn't take the idea of "air utilisation" into account. There's enough data available to create an air time model, but no-one is using it yet. Patches are gratefully accepted. :-)

Finally, the current packet scheduler is pretty simple and stupid (and does break in a lot of scenarios, sigh.) It's just a FIFO, servicing nodes/TIDs with traffic in said FIFO mechanism. But that's not very fair - both from a "who is next" standpoint and "what's the most efficient use of the air" view. In addition, the decision about which node/TID to schedule next is done totally separate to the rate control decision. Rate control occurs rather late in the packet transmission process (ie, once we've committed to queuing it to the hardware.) Wouldn't it be better to have the packet scheduler and rate control code joined at the hip, where the scheduler doesn't aggressively schedule traffic to a slow/lossy end node?

Lots of things to think about..

Filtered frames support, or how not to spam the air with useless transmission attempts

I haven't updated this blog in a while - but that doesn't mean I haven't been a busy little beaver in the world of FreeBSD Atheros support.

A small corner part of correct and efficient software retransmission handling is what Atheros hardware calls "filtered frames", or what actually happens - "how to make sure the hardware doesn't just spam the air with transmission attempts to a dead remote node."

So here's the run-down.

You feed the Atheros hardware a set of frames to transmit. There's a linked list (or FIFO for the more recent hardware) of TX descriptors which represent the fragments of each frame you're transmitting. The hardware will attempt each one in turn and then return a TX completion status explaining what happened. For frames without ACKs the TX status is "did I get a chance to squeeze this out into the air" - there's no ACK, so there's no way to know if it made it out there. But for frames with ACKs, there's a response from the remote end which the transmitter uses, and it'll attempt retransmission in hardware before either succeeding or giving up. Either way, it tells you what happened.

The reality is a little more complicated - there's multiple TX queues with varying TX priorities (implementing the 802.11 "WME" QoS mechanism. There's all kinds of stuff going on behind the scenes to figure out which queue wins arbitration, gets access to the air to transmit, etc, etc. For this particular discussion it doesn't matter.

Now, say you then queue 10 frames to a remote node. The hardware will walk the TX queue (or queues) and transmit those frames one at a time. Some may fail, some may not. If you don't care about software retransmission then you're fine.

But say you want to handle software retransmission. Say that retransmission is for legacy, non-aggregation / non-blockack sessions. You transmit one frame at a time. Each traffic identifier (TID) has its own sequence number space, as well as the "Non-QoS" traffic identifier (ie, non-QoS traffic that does have a sequence number.) By design, each frame is transmitted in order, with incrementing sequence numbers. The receiver throws away frames that are out of sequence. That way packets are delivered in order. They may not be reliably received, but the sequence number ordering is enforced.

So, you now want to handle software retransmission of some frames. You get some frames that are transmitted and some frames that weren't. Can you retransmit the failed ones? Well, the answer is "sure", but there are implications. Specifically, those frames may now be out of sequence, so when you retransmit them the receiver will simply drop them. You could choose to reassign them new sequence numbers so the receiver doesn't reject them out of hand, but now the receiver is seeing out-of-order frames. It doesn't see out of sequence frames, but the underlying payloads are all jumbled. This makes various protocols (like TCP) very unhappy. If you're running some older PPTP VPN sessions, the end point may simply drop your now out-of-order frames. So it's very important that you actually maintain the order of frames to a station.

Given that, how can you actually handle software retransmission? The key lies in this idea of "filtered frames." The Atheros MAC has what it calls a "keycache", where it stuffs encryption keys for each destination node (and multicast keys, and WEP keys..) So upon reception of a frame, it'll look in the keycache for that particular station MAC, then attempt to decrypt the data with that key. Transmission is similar - there's keycache entries for each destination station and the TX descriptor has a TX Key ID.

Now, I don't know if the filtered frame bit is stored in the keycache entry or elsewhere (I should check, honest) but I'm pretty sure it is.

So the MAC has a bit for each station in the keycache (I think!) and when a TX fails, it sets that bit. That bit controls whether any further TX attempts to that station will actually occur. So when the first frame TX to that station fails, any subsequent attempts are automatically failed by the MAC, with the TX status "TX destination filtered." Thus, anything already in the hardware TX queue(s) for that destination get automatically filtered for you. The software can then grab those frames in the order you tried them (which is in sequence number order, right?) and since _all_ frames are filtered, you don't have to worry about some intermediary frames being transmitted. You just queue them in a software queue, wait until the node is alive again, and then set the "clear destination mask (CLRDMASK)" bit in the next TX attempt.

This gives you three main benefits:

All the frames are filtered at the point the first fails, so you get all the subsequent attempted frames back, in the order you queued them. This makes life much easier when retransmitting them;
The MAC now doesn't waste lots of time trying to transmit to destinations that aren't available. So if you have a bunch of UDP traffic being pushed to a dead or far away node, the airtime won't be spent trying to transmit all those frames. The first failure will filter the rest, freeing up the TX queue (and air) to transmit frames to other destinations;
When stations go into power save mode, you may have frames already in the hardware queue for said station. You can't cancel them (easily/cleanly/fast), so instead they'll just fail to transmit (as the receiver is asleep.) Now you just get them filtered; you store them away until the station wakes up and then you retransmit them. A little extra latency (which is ok for some things and not others!) but much, much lower packet loss.

This is all nice and easy. However, there are a few gotchas here.

Firstly, it filters all frames to that destination. For all TIDs, QoS or otherwise. That's not a huge deal; if however you're me and you have per-TID queues you need to requeue the frames into the correct queues to retry. No biggie.

Secondly, if a station is just far away or under interference, you'll end up filtering a lot of traffic to it. So a lot of frames will cycle through the filtered frames handling code. Right now in FreeBSD I'm treating them the same as normal software retransmissions and dropping them after 10 attempts. I have a feeling I need to fix that logic a bit as under heavy dropping conditions, the traffic is being prematurely filtered and prematurely dropped (especially when the node is going off-channel to do things like background scans.) So the retransmission and frame expiry is tricky. You can't just keep trying them forever as you'll just end up wasting TX air time and CPU time transmitting lots of frames that will just end up being immediately filtered. Yes, tricky.

Thirdly, there may be traffic that needs to go out to that node that can't be filtered. If that's the case, you may actually end up with some subsequent frames being transmitted. You then can't just naively requeue all of your failed/filtered frames or you'll transmit some frames out of sequence. You then _have_ to drop anything with a sequence number or that was queued _before_ the successfully transmitted frame.

Luckily for 802.11n aggregation sessions the third point isn't a big deal - you already can transmit out of sequence (just within the block-ack window or BAW), so you can just retransmit filtered frames with sequence numbers in any particular sequence. Life is good there.

So what have I done in FreeBSD?

I have filtered frames support working for 802.11n aggregation sessions. I haven't yet implemented software retransmission (and all of the hairy logic to handle point #3 above) for non-aggregate traffic, so I can't do filtered frames there. But I'm going to have to do it in order to nicely support AP power save operation.

Reading rate control information from userland..

I've begun working on exporting the ath(4) driver rate control information. The "current" way to extract this information has been to issue a sysctl to the rate control module, which dumps debugging state to the kernel console. This is quite suboptimal. Instead, I'm now packaging that up via a driver ioctl() call. It's temporary (hah, famous last words in the software industry :) and it's driver specific for now. The thirty second summary:

There's a new ioctl to ath(4) to query the rate control module for a single associated MAC address (or the BSS MAC when running as a STA);
Since the rate control is currently done at the driver level rather than at the VAP level, the call is to the driver rather than via the VAP (wlanX) interface;
There's no easy way to get "all" station details whilst maintaining correct locking.

The last point deserves a little more explanation. I've introduced (well, _using_ now) a per-node lock when doing rate control updates. I acquire this lock when copying the rate control data out, so the snapshot is consistent.

So to fetch the state for a node, the following occurs:

Call the net80211 layer to find an ieee80211_node for the given mac address - that involves locking the node table and getting a reference for the node (if found);
Then locking the ath_node associated with it;
Copy the data out;
Unlock the ath_node;
Decrement the ieee80211_node reference counter (which requires the node table lock.)

Now, the node table lock only occurs whilst fetching the node reference. It isn't held whilst doing the actual rate control manipulation. Compare to what I'd do if I wanted to walk the node table. The net80211 API for doing this holds the node lock whilst waking the node list. This means that I'll end up holding the node table lock whilst acquiring the ath_node lock. Now, that's fine - however, if I then decide somewhere else to try and do any ieee80211 operation whilst holding the ath_node lock, I may find myself with a lock ordering problem.

So for now the API will just support doing a single lookup for a given MAC, rather than trying to pull all of the rate control table entries down at once.

Here's an example output from the command:

adrian@marilyn:~/work/freebsd/ath/head/src/tools/tools/ath/athratestats]> ./athratestats -i ath1 -m 06:16:16:03:40:d0
static_rix (-1) ratemask 0xf
[ 250] cur rate 5 Mb since switch: packets 1 ticks 43028655
[ 250] last sample (11 Mb) cur sample (0 ) packets sent 10708
[ 250] packets since sample 16 sample tt 6275
[1600] cur rate 11 Mb since switch: packets 15 ticks 43025720
[1600] last sample (5 Mb) cur sample (0 ) packets sent 2423
[1600] packets since sample 7 sample tt 12713
[ 2 Mb: 250] 9:9 (100%) (EWMA 100.0%) T 11 F 0 avg 2803 last 42176930
[ 5 Mb: 250] 3139:3139 (100%) (EWMA 100.0%) T 3273 F 0 avg 1433 last 43028656
[ 5 Mb:1600] 29:29 (100%) (EWMA 100.0%) T 39 F 0 avg 5303 last 42192044
[11 Mb: 250] 7560:7560 (100%) (EWMA 100.0%) T 7838 F 0 avg 1857 last 43026094
[11 Mb:1600] 2394:2394 (100%) (EWMA 100.0%) T 2581 F 0 avg 2919 last 43026411

Don’t let anyone tell you that FreeBSD doesn’t "do" 802.11n:

This is from my FreeBSD-HEAD 802.11n access point, currently doing ~ 130MBit/s TCP:



# athstats -i ath0
41838297     data frames received
31028383     data frames transmit
78260        short on-chip tx retries
3672         long on-chip tx retries
197          tx failed 'cuz too many retries
MCS13        current transmit rate
8834         tx failed 'cuz destination filtered
477          tx frames with no ack marked
239517       rx failed 'cuz of bad CRC
10           rx failed 'cuz of PHY err
    10           OFDM restart
42043        beacons transmitted
143          periodic calibrations
-0/+0        TDMA slot adjust (usecs, smoothed)
45           rssi of last ack
51           avg recv rssi
-96          rx noise floor
812          tx frames through raw api
41664029     A-MPDU sub-frames received
42075948     Half-GI frames received
42075981     40MHz frames received
13191        CRC errors for non-last A-MPDU subframes
129          CRC errors for last subframe in an A-MPDU
2645042      Frames transmitted with HT Protection
351457       Number of frames retransmitted in software
23299        Number of frames exceeding software retry
30674735     A-MPDU sub-frame TX attempt success
374408       A-MPDU sub-frame TX attempt failures
8676         A-MPDU TX frame failures
443          listen time
6435         cumulative OFDM phy error count
161          ANI forced listen time to zero
3672         missing ACK's
78260        RTS without CTS
1469003      successful RTS
239605       bad FCS
2            average rssi (beacons only)
Antenna profile:
[0] tx  1466665 rx        1
[1] tx        0 rx 41838296

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:

Starting condition: Window is at 0:63 (64 frame window, starting at 0, so ending at 63)
Add 1: Window is now at 0:63, starting at 1
Add 2: Window is now at 0:63, starting at 2
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:

Starting condition: Window is at 0:63
Add 2: Window is now 0:63, starting at 2.
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"):

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.
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.

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.

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.

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.

FreeBSD on the TP-Link TL-WR1043nd!

I've now included (almost) all of the support needed to run FreeBSD natively on the TP-Link TL-WR1043nd. It's a 3-antenna, 2x2 stream 2.4ghz 802.11n AP which you can get for under AUD $100.

It supports hostap mode (which is what I bet most of you want to use) and I'm currently using it at home alongside my Ubiquiti Routerstation Pro based hostap (which is what I use to test out all the other pre-11n and 11n NICs that I currently own.)

I currently get around 50mbit TCP throughput - but I leave full FreeBSD-HEAD debugging on. I'm sure I can push the unit closer to 100mbit. (Compare to the Routerstation Pro + AR9160 hostap - where I routinely get 160mbit of TCP throughput.)

What works (read: what I've tested):

Ethernet (at least the WAN port);
Wireless - 802.11bgn - 20/40mhz operation as well as legacy operation (and both, if that's what you need);
Serial console - if you've soldered in one.

The firmware image stores the configuration in a 64k flash partition which is read upon boot. You can modify files in /etc and then save these to flash via "cfg_save".

What isn't supported:

The onboard switch - so I believe the only port available at the present moment is the WLAN port;
The GPIO lines aren't being configured, so the WLAN, status and USB/QSS buttons don't function.

I haven't tested out Multi-SSID mode yet. The earlier AR9130 revisions have some issues with multi-SSID mode and handling block-ack tracking, so I _think_ I'll need to somehow disable aggregation on the second and later VAP interfaces. Just keep that in mind if you're tinkering.

Further details about the hardware and how to build the software for yourself can be found here in my FreeBSD wifi development project wiki.

No, I won't (yet) be putting up firmware images for people to test. Things are changing quite rapidly and there's no easy way to reflash a unit once you've placed FreeBSD on it - you'll need to have added a serial console to the device.

FreeBSD 802.11n update: 27 November 2011.

I've merged in most of the reset related fixes from my git tree into FreeBSD-HEAD. This means that normal resets (eg stuck beacon, calibration resets, etc) shouldn't drop frames any longer.

Frames are still dropped during things like channel/operation mode changes and channel scanning (which does do a channel change.) I'll have to look into that at a later stage. If you're using this in station mode you will likely need to disable background scanning or your aggregation sessions may occasionally drop. You'll have random messages logged when frames are dropping during a flush or reset, so just check your system dmesg log for anything from the ath driver.

I'll be next working on correctly handling failed/filtered frames and then adding some transition stuff to net80211 so the TIM/ATIM bitmaps can be kept correctly up to date. This should fix some of the power saving issues that I'm sure exist.

Unfortunately transmitting BAR frames is still quite a bit off. There's a lot more tidying up that I'd like to do before I start down the path of handling BAR TX, including trying to figure out how to better handle packet transmission and reception when the NIC is off-channel (eg when doing a background channel scan.)

I also have a long list of things I'd like to do to the rate control code and all the surrounding code which sets up rates and creates aggregates. The code I ported/wrote is a little too verbose and duplicate-y for me. That likely will occur after the christmas break.

Enjoy!

FreeBSD is now doing (even more) 802.11n..

I held off merging in my 802.11n work as much as possible but I decided that I'd like to get it done before the end of the year. Even though 9.0-RELEASE is still around the corner, I decided that it would be better to merge in what I have into -HEAD and then tidy that up then wait for what could be a few more months.

So, it's in there, bugs and all, supporting both station and hostap mode. No, wds, adhoc, mesh and TDMA aren't currently supported (I have enough bugs to worry about for the time being, without trying to debug the other operating modes. But I'd like to.)

What works:

TX and RX aggregation!
The rest of the 802.11n negotiation stuff, mostly thanks to Bernhard Schmidt who fixed up a lot of the net80211 quirks.
Lots of ANI changes which hopefully make noisy environments more stable.

What doesn't yet work:

Interface resets cause frames to be dropped from the RX and TX queues. This messes up aggregation and causes sessions to hang. I'm fixing that up in a git branch at the moment.
BAR TX - I'll implement BAR TX soon - it's just tricky to get right.
Filtered frames - ie, TX failed frames from the hardware. Instead of the current method of "always try", the hardware supports failing the current and subsequent frames in a set. That way a hostap seeing a station going into power saving mode can quickly abort all TX frames to said station and then only retransmit them when the station indicates it's again awake. If I don't do this then the hardware will constantly fail a lot of frames, causing BAR frames to be TXed when they likely shouldn't be.

But it's enough to try. So if you have an AR5416, AR9160, AR9220, AR9280, AR9285, AR9227 or AR9287, give it a whirl. If you have a pre-11n NIC then please, give it a go too. I'd like to ensure that the hardware support for earlier chipsets hasn't broken.

If you'd like to use this in production on a hostap then please keep in mind that power saving support isn't entirely functional and featured, so stations which go into frequent power saving mode may have some performance issues. I'll tinker with this some more soon.

Finally, thank you very much to Hobnob, Inc. for sponsoring this work and Qualcomm Atheros for providing me source code, documentation and assistance in understanding how all of this works.