Wireless update - DFS wrapup

Now that the DFS work has been completed, tested and paid for, I guess I can now write about it.

The DFS work was sponsored by KBC Networks, a wireless product company based in the USA. The eventual aim is to integrate this DFS work into their mesh product. I can't talk any further about what's going on there, except to say that they very graciously allowed the FreeBSD work to be released back to the community.

So FreeBSD now has:

• Updated DFS master (hostap) and DFS slave (station) support in net80211;
  
• Updated regulatory domain entries for the USS ("FCC3");
• Changes to the ath(4) driver to fix corner cases in DFS master and DFS slave modes.

All of this work is now in FreeBSD-HEAD and will be available in FreeBSD-9.0.

Future work will hopefully include DFS IBSS and DFS mesh functionality. This work didn't include 802.11n DFS - but that's not too difficult to do (hint: if someone would like the mini-project, please contact me!)

Along with that was a port of the Atheros radar detection code (from Fusion, their earlier carrier codebase) which is currently proprietary. The Linux wireless developers have been working towards DFS compliance for a while, but haven't yet integrated working radar detection into any drivers. So this was a good exercise in uncharted territory to see how difficult it would be.

It turns out that it wasn't terribly difficult at all. After spending a bit of time chasing down missing bits in the FreeBSD atheros HAL driver, the third party doing said radar code porting managed to get FreeBSD doing radar detection at the same level as the commercial firmware.

During this particular exercise we discovered a few things about the software radar detection, which I think the community at large should know about.

The process of getting a device FCC/ETSI certified is just that - the whole device. This includes the NIC, the internal cabling, the enclosure, the antenna(s) and any external cabling. Maybe even whether it's indoors or outdoors, I wasn't involved in that. This likely has repercussions for any open source DFS implementation - although the DFS machinery in a specific FreeBSD release could be certified, the software based radar matching code may need tuning for the specific hardware used. So it's likely that Linux/FreeBSD can't just publish a single "ath_dfs" source module that will work for all Atheros NICs - or even a single NIC. It's likely that things will need tuning based on how a given NIC is used, the environment it's intending to be used in, and a variety of other things I haven't even thought about yet.

So if/when this does occur, the open source wireless community (FreeBSD, Linux, NetBSD, OpenBSD, DragonflyBSD, whatever..) will have to be responsible and not just simply run an "ath_dfs" radar module, assuming that it works. For complete, correct, certified behaviour, it's going to likely need the community to work with vendors and users in order to create "working, certified" combinations of hardware and software. So, if a vendor (call them U) wishes to release a new "SR-M" NIC, they could work with the open source wireless community to create a certified NIC+board+enclosure+antenna combination and publish a set of radar patterns and settings. They could leverage the proposed existing open source radar pattern matching code and simply add whatever configuration is needed. Users should then be responsible - they should only use the given radar dfs code with the correct setup. If they wish to run a modified setup, they should work with the vendor and upstream community to get things re-certified.

This way the DFS and radar pattern matching code is open source - what then changes is the radar patterns and configuration, which depends upon the NIC, cabling, antenna and environment.

For home users/developers, having a set of certified hardware combinations will make things easier for them.

For commercial vendors, if they adopt open-source FreeBSD or Linux on their platforms then (in an ideal world) they could get their equipment certified once (which as I note, they have to do anyway) and then publish the relevant radar patterns and configuration. The rest of the driver (including the radar pattern matching source and the general DFS support) would already be open source. Users can then use this when running their own kernel/distribution/OS on that platform.

I know this is all very fluffy and assumes that vendors/users act in a responsible, open manner. But I think this is what needs to occur if the open source community wishes to see stable, supported DFS regulatory compliance in their open source project.

To wrap this up, if you're a company wishing to leverage open source on their (Atheros) wireless platform and are interested in regulatory compliance, please drop me a line. I'll put you in contact with the relevant people inside Qualcomm Atheros to discuss how to best achieve this.

FreeBSD: DFS update

I've spent the last few weeks sorting out the DFS support in FreeBSD. I've made some decent progress with it however there's still a long way to go. This has been paid work and I'm glad to see increasing interest in 802.11 support under FreeBSD.

I've debugged DFS channel switching behaviour in station and access point mode. This now functions correctly in both instances.

The ath driver now behaves "better" when doing a DFS channel change. The driver would change channels and wait for the first beacon to program the beacon timers - which are then used to signal when there's a lack of beacons (and thus net80211 marks the state as "SCAN" and begins hunting for another AP.) If a channel change occured to a channel that required a CAC (clear access check) and a radar event occured, a second channel switch would occur - and there'd never be any beacons on that channel. The NIC would sit there forever waiting to hear a first beacon that never came.

I've updated the FCC3 regulatory domain to include frequency bands that require DFS.

I've also introduced some radar device setup and event parsing code into the ath HAL layer which would allow an interested party to tinker with radar detection/classification code on the AR5212 series NICs. I don't have permission to commit the radar frame decoding code for the 11N NICs - I'm working on this.

Finally, I've introduced a radar detection layer - called "ath_dfs" - which currently does nothing (hence the only module is "dfs_null".) This provides all the hooks needed to do radar detection, classification and signaling.

Now, what I haven't done:

• The project also includes working porting the radar classification code and getting it to work. This unfortunately won't be open sourced. I'm going to try and get as much of the radar hardware setup and radar event frame parsing code committed to FreeBSD so an interested party can begin tinkering with this.
• I haven't yet ported a lot of the "channel interference" support. It's there, but I haven't really fleshed it out to be useful and then used it.
  
• There's no DFS support for 11N yet - in particular, 11N HT/40 channels aren't correctly marked as "interference" or "radar"; 11N channels also aren't scanned for during DFS channel selection. That's a later project.
• I need to extend things a bit to handle the weather radar stuff when doing DFS - the ETSI requirements include different channel quiet/scan times.
• There's no support in net80211 (yet) for the DFS, TPC and Quiet elements. This is going to be required for a fully compliant DFS implementation.
• I've not investigated implementing/fixing up the DFS support for IBSS and mesh modes.
  

However, even though there are shortcomings and some missing support in the DFS support, FreeBSD-9.0 will support DFS STA mode well enough to correctly obey instructions from a DFS-compliant access point.

Unintentional side-effects - IPv4/IPv6 load balancing..

Here's a fun one:

1310397101.830 416 X TCP_MISS/200 700 GET http://www.freebsd.org/layout/images/front_get_back.png adrian DIRECT/[2001:4f8:fff6::22] image/png
1310397101.835 413 X TCP_MISS/200 851 GET http://www.freebsd.org/layout/images/front_get_tr.png adrian DIRECT/69.147.83.34 image/png

Since the ipcache code already balances outbound connections between multiple hosts, any IPv6 hosts get similarly load balanced.. between IPv4 hosts as well.

I may end up adding in logic to connect to "only v4" and "only v6" in forward.c...

Lusca update: IPv6 server work is now working

I'm now using the Lusca IPv6 branch for browsing both IPv4 and IPv6 sites.

There's a bunch of little things to update and test, including testing the neighbor selection, peer and ICP code. It's still not yet doing transparent interception or TPROXY - that'll be among the last thing to work on. Finally, there's a bunch of connection timeout handling code which currently is being ignored - there's no convenient place to attach a timeout handler now since the file descriptor isn't created up front; it's created only once the DNS resolution is complete.

My main focus at the moment is testing and verifying the peer, neighbor selection and ICP code out.

But yes, it is actually working!

Lusca development update - IPv6 is almost working

Now that I've (hopefully!) completely finished with university, I can get back into using my hard-earned money from Xenion to get more Lusca development done. (And yes, I'll also be doing wireless development too, fear not.)

The IPv6 branch is a bit messy at the moment, but it's almost able to handle IPv6 server requests.

The problem? The existing code which handles connecting to remote hosts (ie, src/comm.c) doesn't "know" about IPv6. It assumes all sockets are IPv4 and that all hostnames which are returned are also IPv4.

There's unfortunately a lot of dirty code in there - commReuseFD() is the main culprit and a good example of this. The 30 second version - since the commConnectStart() API assumes the socket is already created before the connect() occurs, any "connect retry" (for multiple hostnames and multiple attempts at the same end-host) requires the socket to be closed and recreated. But the FD has to stay the same. So commReuseFD() manually creates a new FD, makes it look like the old FD, then calls dup2() to get it into the same FD as the old one.

The "Correct" Fix is to modify the API to not take an FD, but to return an FD on successful connect() to the remote destination. There's some problems with this though, most notably in the request forwarding layer where the FD is created and comm close handlers are assigned before the connection is attempted. I need to make sure that there's no code which calls comm_close() on the active connection whilst connect() is going on - as said code expects the FD to be valid and assigned by this point.

The "Dirty" fix is to modify commConnectStart() and commReuseFD() to check the FD address family and destroy/create a "new" socket with the correct address family.

The "Problem" is that the code allows the outgoing address to be specified, both for transparent interception (source address spoofing) and to be set via an ACL match. Since IPv4 and IPv6 addresses are now possible, the API will have to be modified to handle this case.

What I'm likely going to do is something inspired by Squid-3. I'll teach the forwarding layer about "try v4 destinations" and "try v6 destinations". The administrator can then configure whether to try v4 or v6 destinations first. Only one outgoing address has to be provided - either "v4" or "v6"; and commConnectStart() will only try connecting to IP addresses that match the family of the outgoing address. That way if a host resolves to a mix of v4 and v6 addresses, they'll be tried in a "v4" group, then a "v6" group (or vice versa.) It's a bit dirty, but it's likely doable in the short-term.

In the long term, I'd like to fix the API up to be less messy and return an FD, rather than take an existing FD and abuse that. But that can come later.

Implementing 11n TX aggregation, why it's not so easy..

The only real missing bit from the initial 11n support for ath(4) in FreeBSD is now TX aggregation. This is also quite a tricky thing to do right, because (like everything related to these Atheros NICs) it's all done in software.

I'm about half way through the first part - implementing per-node, per-TID software queues. Since A-MPDU sessions are implemented using TIDs (although in net80211 they're linked to WME access classes (AC), hm!) traffic for each TID has to be individually managed.

The basic premise is quite simple. Frames are queued based on the destination node and TID. Non-QoS frames to a unicast destination (ie, a known station) go to the "non-QoS TID" (TID 16 in FreeBSD's net80211 stack.) Multicast frames go to the software-driven multicast/content-after-beacon (cabq) queue. Then a separate task handles de-queuing packets form these queues and queuing them to the hardware.

The reality however is a little more difficult than that.

Firstly, frames are queued from multiple contexts. The most obvious is the per-interface queue (ie wlanX). These may run in parallel and target the same hardware, so now I need to add locking to the per-node structure. Previously this wasn't (much) of a problem since the TX code simply directly dispatched to the hardware, and these queues are correctly locked. However now there's software-driven queues (which need new locks) along with some more per-node state. That all needs locking.

Next, the rate control code wasn't at all locked. I've begun wrapping them in per-node locks. Making sure I get this correct isn't easy.

Then there's the question of marking nodes and TIDs that have traffic to send. Right now that's done by adding each node to a linked list of "ready nodes". I then check all the TIDs for that node and dequeue what packets I have to. It's ugly code, but it works well enough for testing. I'll finish off implementing what ath9k and the Atheros reference code does (ie, maintaining both a "node" and "TID" linked list, so I can directly walk which TIDs need walking), but there's implications here for getting "QoS" right. (Ie, which order do you dequeue packets? How many do you dequeue from which queue in order for things to be "fair" ?) I'm going to leave all of these questions unanswered for now (as they're not handled in the current code anyway) and hope someone else steps up to it!

At this point I now have a mostly-clean (for values of "clean") implementation of per-node, per-TID software queues. I'm still in the process of tidying all of this up in preparation to commit to -HEAD before I begin the aggregation code. I'll cover that in a moment.

Then there's handling the aggregation session stuff.

Firstly, there's handling the ADDBA exchange (ie, establishing an A-MPDU session.) When this is done, any unicast traffic pending to that node/TID needs to be paused and kept around until the ADDBA request/response occurs. This is known as "pausing" the queue. I've a hack in place to do this and will implement a correct "pause" API soon to clean it up.

Next there's handling packets already queued to the hardware. This crept up on me without warning.

Firstly - a little background. The ADDBA exchange establishes the initial sequence number and window size to use as the "window" for subsequent data exchanges. After that, any packets being queued to the destination must fall within this window (typically say 64 sequence numbers long.) The window stays a fixed size, but the window itself slides along when TX packets are successfully completed. Since packets may be lost at any time (whether aggregate or not), the window doesn't move until the sequence numbers at the beginning of the window are successfully received.

So for example, say my window begins at "0", my window size is "4" and the station sends 4 packets with sequence numbers "0", "1", "2", "3". If I receive all four packets correctly and thus send back a block-ACK indicating this, the new window position will begin at "4". I can then send packets "4", "5", "6" and "7". I can't send "8", even if I have it in my queue.

But say the other end only received "0", "1" and "3". "2" wasn't received, so I have to retransmit it. I can only advance the window to "2". I can't advance it to "3", since I didn't receive "2". I could advance it to "1", but that'd be pointless as I've already received it. So in this instance, both the station and access point would advance the window position to "2" and the station would then retransmit "2". If it's coded correctly, it could transmit "2", "4", "5". It can't transmit "6", as that's outside the window size of 4 packets. It could just retransmit "2" if it wanted to and not the others. In fact, it could transmit "4", "5" and "2" - the receiver would then be responsible for re-ordering the packets and only passing them up to the network layer once all the packets in the correct order are available.

Finally, if I don't receive "2" (say I just can't seem to transmit it), the STA need to do a few things. It first has to pause the queue so no further packets are queued to the hardware. At this point, packets may be queued to the hardware, but they'll be for sequence numbers greater than "2" but still within the block-ack window. Once the hardware has finished completing packets (successfully or not), it needs to send a "BAR" frame to the access point to establish a new starting point for the sequence number window. In this instance it could set it to "3", but what if "3" was already in the hardware queue and was successfully transmitted? That would confuse the hell out of the other end. So it looks at the last successfully transmitted sequence number was, then sends the "BAR" with a starting sequence number 1 after that.

So, if "2" came back as having failed too many times, but "3" and "4" were in the hardware TX queue, the driver will pause the queue, wait for pending frames to complete, then look at what happened. If "3" and "4" were successfully transmitted, it would send a BAR with the sequence beginning at "5". If "3" was successfully transmitted but not "4", it would send a BAR with the sequence beginning at "4". But if "3" failed, and "4" didn't - it would set the BAR at "3" and then try retransmitting it. Finally (and this is another strange corner case I have to handle!) if "3" came back as having failed - and it failed too many times! - but "4" TX'ed ok, then I have to set the initial sequence number at "5" and send the BAR.

The other end (in this instance, the hostap) would then receive the BAR, set the new expected sequence number to be whatever was sent (say "5" in this instance), flush all pending packets in the reorder queue - even if there are missing packets (in the above example, "3" may be missing but "4" was received ok, so the receive stack would've been waiting for "3" to be received before sending it all up to the network layer!) and send back a block-ACK to the STA confirming the new window position.

Now (phew!) given all of that, you can see what kind of complicated stuff is needed to properly handle all corner cases when doing software (re)transmitting of packets. I haven't even begun to talk about how to handle sending and re-sending aggregate frames! All of the above needs to be implemented before I can do that.

So! The above is what I'm now working on. Once that's done, I'll work on handling what's known as "filtered frames" (and that'll be brain-dumped in a future blog post, but it has to do with handling power save stations correctly, or A-MPDU sessions will be torn down prematurely!) and then when THAT is all done and stable, I'll look at handling aggregates.

And when I handle aggregates correctly, we'll finally have fast 11n TX in FreeBSD. Then I can enable "ATH_ENABLE_11N" by default. :-)

Uninformed programmers, or "stop assuming virtual memory is awesome."

I decided I needed to vent a bit post-exam. So where better to find some clue-void post to answer than slashdot.

The post, and my reply:

http://news.slashdot.org/comments.pl?sid=2229598&cid=36408502

In summary, the original poster:

"In short, don't worry about fine-tuning what's "in memory". Don't change behavior based on total amount of memory in the system. Operating systems (OpenBSD aside) ALREADY DO THAT. Just let the memory manager do its job, and give it enough information (via interactivity information, memory priority, etc.) to do its job properly. Don't try to hack around problems at the wrong layers."

And my response:

"You assume that the OS will make sensible paging decisions. You assume you can hint to the OS that you're going to make sensible paging decisions. You hope the application, which is likely big, multithreaded and such, is doing the sensible thing of not wrapping large accesses to "memory things" (eg big trees of data, as an example, or image caches, or whatever takes up more than a small bit of RAM) in mutexes. You assume that your application is using memory in a sensible fashion, and not simply using a few bytes here and there in each allocated chunk."

I hate to say it, but if you're assuming that virtual memory is the be all and end all of your memory management method, you're setting yourself up for some really bad worse case behaviour. Since you have no control as to where and when the OS decides to punt pages to disk, you can't possibly begin to design methods around it. You can only hope that the OS doesn't page out the data you've got locked, or that the malloc implementation you're using doesn't handle fragmentation poorly.